The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
SimGNN: A Neural Network Approach to Fast Graph Similarity Computation
Open accessAbstract
Graph similarity search is among the most important graph-based applications, e.g. finding the chemical compounds that are most similar to a query compound. Graph similarity/distance computation, such as Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), is the core operation of graph similarity search and many other applications, but very costly to compute in practice. Inspired by the recent success of neural network approaches to several graph applications, such as node or graph classification, we propose a novel neural network based approach to address this classic yet challenging graph problem, aiming to alleviate the computational burden while preserving a good performance. The proposed approach, called SimGNN, combines two strategies. First, we design a learnable embedding function that maps every graph into an embedding vector, which provides a global summary of a graph. A novel attention mechanism is proposed to emphasize the important nodes with respect to a specific similarity metric. Second, we design a pairwise node comparison method to supplement the graph-level embeddings with fine-grained node-level information. Our model achieves better generalization on unseen graphs, and in the worst case runs in quadratic time with respect to the number of nodes in two graphs. Taking GED computation as an example, experimental results on three real graph datasets demonstrate the effectiveness and efficiency of our approach. Specifically, our model achieves smaller error rate and great time reduction compared against a series of baselines, including several approximation algorithms on GED computation, and many existing graph neural network based models. Our study suggests SimGNN provides a new direction for future research on graph similarity computation and graph similarity search.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946
Binary Codes capable of currecting deletions, insertions, and reversals
Levenshtein, V. I. (1965) · Soviet physics. Doklady · Cited by 14,807
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2017) · arXiv · doi:10.48550/arxiv.1710.10903 · Cited by 12,107
node2vec: Scalable Feature Learning for Networks
Grover, A., & Leskovec, J. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939754 · Cited by 10,926
Inductive Representation Learning on Large Graphs
Hamilton, W. L., Ying, R., & Leskovec, J. (2017) · arXiv · doi:10.48550/arxiv.1706.02216 · Cited by 10,639
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123
The proof and measurement of association between two things
Spearman, C. (1904) · The American Journal of Psychology · doi:10.2307/1412159 · Cited by 8,039
A NEW MEASURE OF RANK CORRELATION
KENDALL, M. G. (1938) · Biometrika · doi:10.1093/biomet/30.1-2.81 · Cited by 7,269
Modeling Relational Data with Graph Convolutional Networks
Schlichtkrull, M., Kipf, T. N., Bloem, P., van den Berg, R., Titov, I., & Welling, M. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-93417-4_38 · Cited by 5,570
LINE: Large-scale Information Network Embedding
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., & Mei, Q. (2015) · Proceedings of the 24th International Conference on World Wide Web · doi:10.1145/2736277.2741093 · Cited by 5,416
Advances In Deep Learning On Graphs (Gsp'18 Workshop)
Defferrard, M. (2016) · Figshare · doi:10.5281/zenodo.1286817 · Cited by 4,613
Structural Deep Network Embedding
Wang, D., Cui, P., & Zhu, W. (2016) · Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2939672.2939753 · Cited by 2,845
(1961) · Journal of the Optical Society of America · doi:10.1364/josa.51.000248 · Cited by 2,288
Reasoning With Neural Tensor Networks for Knowledge Base Completion
Socher, R., Chen, D., Manning, C. D., & Ng, A. Y. (2013) · Cited by 1,667
Molecular graph convolutions: moving beyond fingerprints
Kearnes, S., McCloskey, K., Berndl, M., Pande, V., & Riley, P. (2016) · Journal of Computer-Aided Molecular Design · doi:10.1007/s10822-016-9938-8 · Cited by 1,631
A shortest augmenting path algorithm for dense and sparse linear assignment problems
Jonker, R., & Volgenant, A. (1987) · Computing · doi:10.1007/bf02278710 · Cited by 1,230
Convolutional Neural Network Architectures for Matching Natural Language Sentences
Hu, B., Lu, Z., Li, H., & Chen, Q. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.03244 · Cited by 1,098
Yanardag, P., & Vishwanathan, S. V. N. (2015) · Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2783258.2783417 · Cited by 1,021
On Graph Kernels: Hardness Results and Efficient Alternatives
Gärtner, T., Flach, P., & Wrobel, S. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45167-9_11 · Cited by 879
A graph distance metric based on the maximal common subgraph
Bunke, H., & Shearer, K. (1998) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00179-7 · Cited by 754
Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec
Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., & Tang, J. (2018) · Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining · doi:10.1145/3159652.3159706 · Cited by 717
Approximate graph edit distance computation by means of bipartite graph matching
Riesen, K., & Bunke, H. (2009) · Image and Vision Computing · doi:10.1016/j.imavis.2008.04.004 · Cited by 651
On a relation between graph edit distance and maximum common subgraph
Bunke, H. (1997) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00060-3 · Cited by 530
IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning
Riesen, K., & Bunke, H. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-89689-0_33 · Cited by 498
Comparing stars: on approximating graph edit distance
Zeng, Z., Tung, A. K. H., Wang, J., Feng, J., & Zhou, L. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687631 · Cited by 399
Cyclic pattern kernels for predictive graph mining
Horváth, T., Gärtner, T., & Wrobel, S. (2004) · Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1014052.1014072 · Cited by 308
Graph Classification using Structural Attention
Lee, J. B., Rossi, R., & Kong, X. (2018) · Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining · doi:10.1145/3219819.3219980 · Cited by 280
Attention-based Graph Neural Network for Semi-supervised Learning
Thekumparampil, K. K., Wang, C., Oh, S., & Li, L.-J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.03735 · Cited by 235
Pairwise Word Interaction Modeling with Deep Neural Networks for Semantic Similarity Measurement
He, H., & Lin, J. (2016) · Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies · doi:10.18653/v1/n16-1108 · Cited by 232
Drug Similarity Integration Through Attentive Multi-view Graph Auto-Encoders
Ma, T., Xiao, C., Zhou, J., & Wang, F. (2018) · Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/483 · Cited by 220
Fast Suboptimal Algorithms for the Computation of Graph Edit Distance
Neuhaus, M., Riesen, K., & Bunke, H. (2006) · Lecture Notes in Computer Science · doi:10.1007/11815921_17 · Cited by 213
Matching Node Embeddings for Graph Similarity
Nikolentzos, G., Meladianos, P., & Vazirgiannis, M. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10839 · Cited by 199
Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching
Fankhauser, S., Riesen, K., & Horst Bunke, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20844-7_11 · Cited by 150
An Efficient Graph Indexing Method
Xiaoli, W., Ding, X., Tung, A. K. H., Ying, S., & Jin, H. (2012) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2012.28 · Cited by 133
Graph edit distance as a quadratic assignment problem
Bougleux, S., Brun, L., Carletti, V., Foggia, P., Gaüzère, B., & Vento, M. (2016) · Pattern Recognition Letters · doi:10.1016/j.patrec.2016.10.001 · Cited by 126
On the exact computation of the graph edit distance
Blumenthal, D. B., & Gamper, J. (2018) · Pattern Recognition Letters · doi:10.1016/j.patrec.2018.05.002 · Cited by 125
A Novel Software Toolkit for Graph Edit Distance Computation
Riesen, K., Emmenegger, S., & Horst Bunke, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38221-5_15 · Cited by 96
Similarity Search in Graph Databases: A Multi-Layered Indexing Approach
Liang, Y., & Zhao, P. (2017) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2017.129 · Cited by 77
Approximate Graph Edit Distance by Several Local Searches in Parallel
Daller, É., Bougleux, S., Gaüzère, B., & Brun, L. (2018) · International Conference on Pattern Recognition Applications and Methods · doi:10.5220/0006599901490158 · Cited by 27
Substructure Assembling Network for Graph Classification
Zhao, X., Zong, B., Guan, Z., Zhang, K., & Zhao, W. Z. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11742 · Cited by 23
Chen, T., Wang, Z., Li, L., Li, D., Li, Z., Chang, X., Bian, P., Liang, G., Wang, Q., & Xie, T. (2025) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.ecoop.2025.6
Self-citation
Cited by
Self-supervised Learning: Generative or Contrastive
Liu, X., Zhang, F., Hou, Z., Mian, L., Wang, Z., Zhang, J., & Tang, J. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3090866 · Cited by 1,087
Deep learning approaches for similarity computation: A survey
Yang, P., Wang, H., Yang, J., Qian, Z., Zhang, Y., & Lin, X. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3422484 · Cited by 28
Metadata
- Authors
- Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., & Wang, W.
- Venue
- Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining
- Publisher
- ACM
- Published
- 2019-01-30
- Pages
- 384-392
- OpenAlex
- W2906943923
- Cited by
- 325
- References
- 42
- FWCI
- 11.05
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.