NeMa: Fast Graph Search with Label Similarity

Summary: NeMa: neighborhood-based subgraph search for labeled, heterogeneous networks. It defines a unified node-level cost combining structure and label similarity to yield top-k matches; NP-hard, solved with a heuristic inference-model and optimizations, outperforming keyword search and baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hfbeab6609d1fe7a3
Venue: VLDB
Year: 2013
Pagerank: 8.7738068e-05
Overall Rank: 2,238 | 84.96%
DOI: 10.14778/2535568.2535571

Incoming Non-self Citations Over Time

Authors

1. Arijit Khan (University of California Santa Barbara)
2. Yinghui Wu (University of California Santa Barbara)
3. Charu C. Aggarwal (IBM)
4. Xifeng Yan (University of California Santa Barbara)

BibTeX Citation

@article{khan_vldb13,
        title = {{NeMa: Fast Graph Search with Label Similarity}},
        author = {Khan, Arijit and Wu, Yinghui and Aggarwal, Charu C. and Yan, Xifeng},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {3},
        pages = {181--192},
        doi = {10.14778/2535568.2535571},
        url = {https://doi.org/10.14778/2535568.2535571},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 17 of 17 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
948	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00012908602
1,572	Scalable Subgraph Enumeration in MapReduce	2015	VLDB	0.0001019315
1,955	Exemplar Queries: Give me an Example of What You Need	2014	VLDB	9.3136735e-05
3,570	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.195367e-05
4,468	Schemaless and Structureless Graph Querying	2014	VLDB	6.5841276e-05
4,585	Event Pattern Matching over Graph Streams	2015	VLDB	6.5156965e-05
5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.1126446e-05
7,990	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD	5.4100383e-05
8,345	Mining Top-k Pairs of Correlated Subgraphs in a Large Network	2020	VLDB	5.3491485e-05
9,332	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	5.1917722e-05
9,576	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB	5.154741e-05
9,847	ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs	2020	VLDB	5.1206606e-05
9,867	GARUDA: A System for Large-Scale Mining of Statistically Significant Connected Subgraphs	2016	VLDB	5.1154699e-05
10,238	Graph Exploration: From Users to Large Graphs	2017	SIGMOD	5.0544949e-05
10,792	Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries	2026	VLDB	4.9769913e-05
12,071	Simulation-based Approximate Graph Pattern Matching	2020	SIGMOD	4.9769913e-05
12,322	NED: An Inter-Graph Node Metric Based On Edit Distance	2017	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012087459
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022588961
438	Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism	2008	VLDB	0.00018278591
443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018190518
1,150	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011804185
1,247	SAPPER: Subgraph Indexing and Approximate Matching in Large Graphs	2010	VLDB	0.00011348258
1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010875727
1,804	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.5980088e-05
2,128	Query Rewriting for Semistructured Data	1999	SIGMOD	8.9984814e-05
2,731	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.0802025e-05
2,774	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0313907e-05
4,495	Supporting Ontology-based Semantic Matching in RDBMS	2004	VLDB	6.5742479e-05
5,099	Querying Graph Patterns	2011	PODS	6.2713809e-05
5,606	Capturing Topology in Graph Pattern Matching	2012	VLDB	6.0667077e-05
7,019	A Gauss Function Based Approach for Unbalanced Ontology Matching	2009	SIGMOD	5.6169036e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,901	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
2	5,481	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD
3	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
4	12,065	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
5	6,030	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
6	8,668	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
7	7,208	Boosting Graph Similarity Search through Pre-Computation	2021	SIGMOD
8	9,576	S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics	2025	VLDB
9	6,235	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB
10	1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD