Scaling Graph Similarity Learning with Graph Neural Networks
Organizations: Department of Computer Science, Norwegian University of Science and Technology, Trondheim, Norway.
Abstract
Graph similarity computation is an important task in graph mining with many real-world applications, such as chemical compound analysis, program dependence comparison, and social network analysis. The problem is computationally challenging: Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), which quantify the distance between graphs and identify their largest shared subgraph, respectively, are NP-hard to compute exactly. To address these computational challenges, Graph Neural Networks (GNNs) have been applied to this problem. However, existing GNN-based approaches have primarily focused on small-scale graph datasets, while scalability to larger scales remains underexplored. In this work, we propose FiLSim, a scalable GNN-based framework, and investigate whether a simplified GNN pipeline can maintain competitive performance on standard benchmarks while scaling to large graphs. We additionally propose a sequential graph-editing strategy to construct large-scale graph datasets with reliable GED labels to evaluate scalability. The proposed framework is evaluated on four benchmark datasets and four newly created large-scale datasets, demonstrating its effectiveness and scalability. FiLSim remains accurate on graphs with more than 150{,}000 nodes, where the baseline methods run out of memory or fail to learn, and scores all test pairs within seconds on a single GPU.
Figures & tables
| Dataset | # Graphs | Avg. Nodes | Avg. Edges | Avg. Degree |
|---|---|---|---|---|
| PTC | 344 | 25.56 | 25.96 | 2.03 |
| AIDS700nef | 700 | 8.90 | 8.80 | 1.98 |
| LINUX | 1000 | 7.58 | 6.93 | 1.83 |
| IMDBMulti | 1500 | 13.00 | 65.94 | 10.14 |
| Cora | 200 | 2,703 | 5,272 | 3.90 |
| PubMed | 200 | 19,633 | 44,053 | 4.49 |
| Model | AIDS700nef | IMDBMulti | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| MAE | P@10 | Time | MAE | P@10 | Time | |||||
| SimGNN | 1.376 | 0.738 | 0.594 | 0.325 | 2.158 | 34.989 | 0.767 | 0.686 | 0.677 | 2.118 |
| GMN | 0.730 | 0.880 | 0.751 | 0.561 | 13.505 | 4.341 | 0.938 | 0.870 | 0.829 | 14.933 |
| GraphEdX | 0.542 | 0.931 | 0.823 | 0.807 | 1.866 | TO | ||||
| GEN | 0.590 | 0.925 | 0.814 | 0.773 | 0.098 | 3.830 | 0.939 | 0.870 | 0.843 | 0.280 |
| EGSC | 0.736 | 0.890 | 0.764 | 0.628 | 0.001 | 25.251 | 0.888 | 0.825 | 0.851 | 0.001 |
| Model | AIDS700nef | IMDBMulti | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| MAE | P@10 | Time | MAE | P@10 | Time | |||||
| SimGNN | 0.711 | 0.756 | 0.623 | 0.387 | 2.203 | 0.451 | 0.870 | 0.784 | 0.909 | 2.121 |
| GMN | 0.422 | 0.888 | 0.778 | 0.769 | 16.762 | 0.197 | 0.881 | 0.798 | 0.937 | 15.248 |
| GraphEdX | 0.482 | 0.880 | 0.764 | 0.771 | 1.576 | TO | ||||
| GEN | 0.303 | 0.933 | 0.836 | 0.874 | 0.098 | 0.295 | 0.868 | 0.772 | 0.879 | 0.277 |
| EGSC | 0.436 | 0.892 | 0.785 | 0.740 | 0.001 | 0.233 | 0.880 | 0.801 | 0.912 | 0.001 |
| Model | Cora | PubMed | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| RAE | P@10 | Time | RAE | P@10 | Time | |||||
| SimGNN | 2.734 | - | - | 0.045 | 19.795 | 88.598 | -0.271 | -0.188 | 0.061 | 958.379 |
| GMN | 0.309 | 0.950 | 0.822 | 0.723 | 268.426 | 0.564 | 0.755 | 0.582 | 0.562 | 2511.166 |
| GraphEdX | OOM | OOM | ||||||||
| GEN | 1.058 | 0.195 | 0.144 | 0.077 | 2879.634 | OOM | ||||
| EGSC | 2.734 | - | - | 0.045 | 0.191 | 2.591 | - | - | 0.085 | 0.653 |
| Training | Inference | ||||
|---|---|---|---|---|---|
| Dataset | Time (min) | Peak GPU (GB) | Encode once (s) | Pairwise (s) | Peak GPU (GB) |
| AIDS700nef | 9 | 0.18 | 0.04 | 0.6 | 0.89 |
| IMDBMulti | 22 | 0.29 | 0.10 | 4.3 | 0.79 |
| LINUX | 16 | 0.15 | 0.05 | 1.0 | 0.65 |
| PTC | 7 | 0.41 | 0.01 | 0.3 | 0.20 |
| Cora | 120 | 8.72 | 0.18 | 11.6 | 1.75 |
| Task | Dataset | RAE | P@10 | ||||
| NTN | FiLM | NTN | FiLM | NTN | FiLM | ||
| GED | AIDS700nef | 0.293 | 0.265 | 0.922 | 0.937 | 0.738 | 0.830 |
| IMDBMulti | 0.043 | 0.027 | 0.948 | 0.959 | 0.863 | 0.905 | |
| LINUX | 0.046 | 0.009 | 0.973 | 0.974 | 0.986 | 0.992 | |
| PTC | 0.156 | 0.102 | 0.943 | 0.958 | 0.583 | 0.642 | |
| Cora | 0.199 | 0.190 | 0.990 | 0.991 | 0.900 | 0.913 | |
| AIDS700nef, GED | AIDS700nef, MCS | Amazon C., GED | |||||||
| RAE | P@10 | RAE | P@10 | RAE | P@10 | ||||
| FiLSim | 0.265 | 0.937 | 0.830 | 0.198 | 0.935 | 0.889 | 0.241 | 0.979 | 0.852 |
| Score only ( ) | 0.267 | 0.936 | 0.826 | 0.181 | 0.932 | 0.882 | 0.230 | 0.979 | 0.857 |
| Distance only ( ) | 0.326 | 0.913 | 0.732 | 2.851 | 0.864 | 0.715 | 2.757 | 0.613 | 0.530 |
| w/o LDP | 0.271 | 0.935 | 0.818 | 0.195 | 0.935 | 0.884 | 0.270 | 0.961 | 0.793 |
| RW-16 instead of LDP | 0.255 | 0.940 | 0.831 | 0.194 | 0.934 | 0.893 | OOM | ||
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| Group | Methods | Cross-graph operation | Per graph | Per pair | Edit path |
|---|---|---|---|---|---|
| Node-level matching | SimGNN 1 1 1 Uses an NTN, which adds per pair. , GMN 2 2 2 GMN applies cross-graph interactions inside the encoder; the encoder cost is paid per pair. , GraphEdX 3 3 3 The official implementation pads each graph to the largest graph size in the dataset and aligns all node pairs of the two graphs, which costs time and memory per pair. , GEN | histogram, attention, or alignment over node pairs | 2 2 2 GMN applies cross-graph interactions inside the encoder; the encoder cost is paid per pair. | - | |
| Edit-path recovery | GEDGNN 1 1 1 Uses an NTN, which adds per pair. , GEDIOT 1 1 1 Uses an NTN, which adds per pair. | node matching matrix | |||
| Pair- independent | GREED, G2R, EGSC, ERIC 4 4 4 Low-rank NTN, with . , GraSP 1 1 1 Uses an NTN, which adds per pair. , 5 5 5 Additionally precomputes random-walk positional encodings, reported as for walk length . | none | to | - | |
| FiLSim | - | none | - |
| Dataset | # Graphs | Train / Val / Test | Avg. | Max. | Avg. | Max. |
|---|---|---|---|---|---|---|
| PTC | 344 | 220 / 55 / 69 | 25.56 | 109 | 25.96 | 108 |
| AIDS700nef | 700 | 448 / 112 / 140 | 8.90 | 10 | 8.80 | 14 |
| LINUX | 1000 | 640 / 160 / 200 | 7.58 | 10 | 6.93 | 13 |
| IMDBMulti | 1500 | 960 / 240 / 300 | 13.00 | 89 | 65.94 | 1467 |
| Graph | Avg. Degree | ||
|---|---|---|---|
| Wiki ( R. Yang et al., (2020) ) | 2,405 | 11,596 | 9.64 |
| Cora ( Z. Yang et al., (2016) ) | 2,708 | 5,278 | 3.90 |
| CiteSeer ( Z. Yang et al., (2016) ) | 3,327 | 4,552 | 2.74 |
| BlogCatalog ( R. Yang et al., (2020) ) | 5,196 | 171,743 | 66.11 |
| Flickr ( R. Yang et al., (2020) ) | 7,575 | 239,738 | 63.30 |
| Amazon Computers ( Shchur et al., (2018) ) | 13,752 | 245,861 | 35.76 |
| Train / Val / Test | Train pairs | Val pairs | Test pairs | |
|---|---|---|---|---|
| 50 | 32 / 8 / 10 | 496 | 312 | 400 |
| 200 | 128 / 32 / 40 | 8,128 | 5,088 | 6,400 |
| 1000 | 640 / 160 / 200 | 204,480 | 127,840 | 160,000 |
| Graph | Avg. | Avg. | GED label | |
|---|---|---|---|---|
| Wiki | 50 | 2,403 | 11,582 | 18 / 301 / 736 |
| 200 | 2,403 | 11,593 | 17 / 524 / 1,310 | |
| 1000 | 2,398 | 11,554 | 14 / 781 / 1,825 | |
| Cora | 50 | 2,703 | 5,267 | 14 / 199 / 467 |
| 200 | 2,703 | 5,272 | 15 / 369 / 866 | |
| 1000 | 2,703 | 5,259 | 11 / 472 / 1,013 |
| Dataset | Task/ | to best | total | ms/step | Val. (%) | Peak GPU |
|---|---|---|---|---|---|---|
| AIDS700nef | GED | 6.3 | 9.5 | 18.0 | 5.0 | 0.18 |
| MCS | 5.8 | 9.2 | 19.3 | 4.7 | 0.21 | |
| IMDBMulti | GED | 16.0 | 22.3 | 35.4 | 6.4 | 0.29 |
| MCS | 12.6 | 18.0 | 30.4 | 7.1 | 0.27 | |
| LINUX | GED | 10.0 | 15.6 | 31.0 | 4.4 | 0.15 |
| MCS | 15.6 | 21.8 | 35.3 | 3.8 | 0.19 |
Graph Neural Networks
Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.
See all 780 papers