Neighborhood Based Fast Graph Search in Large Networks

Summary: Proposes Ness, a neighborhood-based similarity for top-k approximate subgraph/graph matching in large labeled networks, avoiding isomorphism and edit-distance. An information-propagation model embeds networks into vectors for fast indexing; robust to noise, with subgraph match NP-hard, graph similarity polynomial. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4442
Venue: SIGMOD
Year: 2011
Pagerank: 0.00012838714
Overall Rank: 1,280 | 91.11%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
1,626	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.0001108491
1,630	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011073047
1,962	Exemplar Queries: Give me an Example of What You Need	2014	VLDB	9.9463687e-05
2,118	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB	9.5036922e-05
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05
3,208	VIIQ: Auto-Suggestion Enabled Visual Interface for Interactive Graph Query Formulation	2015	VLDB	7.3837748e-05
7,290	Searching with XQ: the eXemplar Query Search Engine	2014	SIGMOD	4.768315e-05
8,209	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	4.5537353e-05
9,231	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD	4.3648789e-05
11,569	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.1905499e-05
11,826	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
155	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00040666376
172	Algorithmics and Applications of Tree and Graph Searching	2002	PODS	0.00038837872
202	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00034881375
351	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00026351742
576	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00019858777
616	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00019068362
864	APEX: An Adaptive Path Index for XML Data	2002	SIGMOD	0.00015781693
895	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00015498104
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014759406
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
1,444	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011941836
2,943	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	7.8463193e-05
5,158	Towards Proximity Pattern Mining in Large Graphs	2010	SIGMOD	5.6510256e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,848	Effective Community Search over Large Spatial Graphs	2017	VLDB	0.00010331574
1,907	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010130702
2,726	Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks	2020	VLDB	8.2266116e-05
2,291	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.0894835e-05
8,504	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB	4.491551e-05
3,972	Efficient Size-Bounded Community Search over Large Networks	2021	VLDB	6.5724209e-05
10,702	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.1905499e-05
210	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034086264
6,835	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD	4.9065543e-05
2,557	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.5484449e-05