S^3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics

Summary: Introduces subgraph similarity search under aggregated neighbor-difference semantics, jointly capturing keyword and structural similarity beyond isomorphism/edit distance. Keyword-set and neighbor-difference lower bounds, plus a dedicated index, enable effective pruning and scalable search. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14182
Venue: VLDB
Year: 2025
Pagerank: 5.2755515e-05
Overall Rank: 9,383 | 35.63%
DOI: 10.14778/3749466.3749648

Incoming Non-self Citations Over Time

Authors

1. Qi Wen (East China Normal University)
2. Yutong Ye (East China Normal University; Kent State University)
3. Xiang Lian (Kent State University)
4. Mingsong Chen (East China Normal University)

BibTeX Citation

@article{wen_vldb25,
        title = {{S\^{}3AND: Efficient Subgraph Similarity Search Under Aggregated Neighbor Difference Semantics}},
        author = {Wen, Qi and Ye, Yutong and Lian, Xiang and Chen, Mingsong},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {11},
        pages = {3708--3720},
        doi = {10.14778/3749466.3749648},
        url = {https://doi.org/10.14778/3749466.3749648},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,280	Periodic Community Search in Temporal Graphs: Time Series-based Methods	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
659	Efficient Subgraph Matching by Postponing Cartesian Products	2016	SIGMOD	0.00015214062
1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00012699518
1,102	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012166591
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
2,035	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	9.2787188e-05
2,285	NeMa: Fast Graph Search with Label Similarity	2013	VLDB	8.8052998e-05
3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB	7.3491042e-05
3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	7.0933895e-05
4,372	Schemaless and Structureless Graph Querying	2014	VLDB	6.7384384e-05
6,149	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.9581422e-05
9,149	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB	5.3134506e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,579	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD
2	2,190	Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching	2021	SIGMOD
3	1,812	Efficient SimRank-based Similarity Join Over Large Graphs	2013	VLDB
4	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
5	3,311	Connected Substructure Similarity Search	2010	SIGMOD
6	4,853	Efficient Subgraph Search over Large Uncertain Graphs	2011	VLDB
7	3,522	A Partition-Based Approach to Structure Similarity Search	2014	VLDB
8	9,149	Semantic SPARQL Similarity Search Over RDF Knowledge Graphs	2016	VLDB
9	6,149	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB
10	3,548	Efficient Subgraph Similarity Search on Large Probabilistic Graph Databases	2012	VLDB