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
Figure 1: Overview of FiLSim . Given two input graphs G1 and G2 , the pipeline consists of three stages. First, the feature augmentation module combines the node features with the Local Degree Profile (LDP) into the initial node representations h(0) . Second, a shared GGNN encoder computes node representations, whose layer outputs are combined and pooled into fixed-size graph embeddings zG1 and zG2 . Since each graph is encoded independently, these embeddings can be cached and reused across pairs. Finally, the prediction module combines a FiLM-based interaction score s with the distance between the two embeddings to predict y^ , and is trained on a weighted sum of a regression and a ranking loss.
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
Table 1: Statistics of the datasets. For the large-scale datasets, values are given for M=200 . Other large-scale datasets and M values are listed in Table 12 .
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
Table 2: GED prediction results on the benchmark datasets, mean over 10 seeds. ↓ : lower is better, ↑ : higher is better. Time: inference time in seconds per 10,000 test pairs. Best result in bold , second best underlined , and third best in italic . TO : timeout.
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
Table 3: MCS prediction results on the benchmark datasets, mean over 10 seeds. ↓ : lower is better, ↑ : higher is better. Time: inference time in seconds per 10,000 test pairs. Best result in bold , second best underlined , and third best in italic . TO : timeout.
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
Table 4: GED prediction on the large-scale datasets with M=200 graphs, mean over 3 seeds. RAE: relative absolute error. Time: inference time in seconds per 10,000 test pairs. Best result in bold , second best underlined , and third best in italic . OOM : out of memory; -: constant prediction (ranking metrics) or RAE above 1,000.
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
Table 5: Training and scoring cost of FiLSim . Time is the median, including validation time.
Figure 2: Cost of FiLSim by graph size. (a) Time and (b) peak GPU memory to encode one graph (median size). (c) Time to compute structural encodings per graph: LDP and random-walk encodings with 16 steps. Shaded area: benchmark datasets.
Figure 3: Stage breakdown of inference of FiLSim . (a) Wall-clock time per stage and total time. (b) Peak host memory of the process and (c) peak GPU memory. Dashed lines: memory limits.
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
Table 6: Comparison of the FiLM and NTN prediction modules. Better scores are in bold .
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 ( α=1 )
0.267
0.936
0.826
0.181
0.932
0.882
0.230
0.979
0.857
Distance only ( α=0 )
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
Table 7: Ablation of FiLSim on AIDS700nef for GED and MCS (mean over 5 seeds; FiLSim row: mean over 10 seeds), and on Amazon Computers ( M=200 ) for GED (mean over 3 seeds).
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Graph matching example: two isomorphic graphs, with dashed lines showing corresponding nodes.
Figure 5: Example of graph edit distance. Each step transforms the previous graph by node or edge insertions or deletions; GED(G0,Gk) is the minimum number of such operations between G0 and Gk .
Group
Methods
Cross-graph operation
Per graph
Per pair
Edit path
Node-level matching
SimGNN 1 1 1 Uses an NTN, which adds O(dz2k) 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 nmax in the dataset and aligns all node pairs of the two graphs, which costs O(nmax4d) time and O(nmax4) memory per pair. , GEN
histogram, attention, or alignment over node pairs
O(L(md+nd2)) 2 2 2 GMN applies cross-graph interactions inside the encoder; the encoder cost is paid per pair.
≥O(n1n2d)
-
Edit-path recovery
GEDGNN 1 1 1 Uses an NTN, which adds O(dz2k) per pair. , GEDIOT 1 1 1 Uses an NTN, which adds O(dz2k) per pair.
node matching matrix
O(L(md+nd2))
≥O(n1n2d)
O(Kn3)
Pair- independent
GREED, G2R, EGSC, ERIC 4 4 4 Low-rank NTN, O(dzd′k) with d′≪dz . , GraSP 1 1 1 Uses an NTN, which adds O(dz2k) per pair. , 5 5 5 Additionally precomputes random-walk positional encodings, reported as O(rn2) for walk length r .
none
O(L(md+nd2))
O(dz) to O(dz2k)
-
FiLSim
-
none
O(L(md+nd2))
O(dzd+d2+dk)
-
Appendix
Table 8: Time complexity of FiLSim and the baselines in our main experiments, grouped as in Section 3 . n,m : nodes and edges of a graph; n1,n2 : sizes of the two graphs in a pair; d : hidden dimension (also used in our prediction module); dz : graph embedding dimension; k : output dimension of the NTN and of the interaction module of FiLSim ; L : number of layers; K : number of candidate matchings.
Dataset
# Graphs
Train / Val / Test
Avg. n
Max. n
Avg. m
Max. m
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
Appendix
Table 9: Benchmark dataset statistics.
Graph
n
m
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
Appendix
Table 10: Main statistics of real-world graphs used to build the large-scale datasets.
M
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
Appendix
Table 11: Number of graphs and pairs per split for the large-scale datasets. The counts are the same for all ten graphs.
Graph
M
Avg. n
Avg. m
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
Appendix
Table 12: Statistics of the generated graphs. GED label: min / median / max of the GED upper bound used as the label, over all pairs.
Dataset
Task/ M
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
Appendix
Table 17: Training cost of FiLSim . Time columns are the median over seeds of the wall-clock time per run. to best : time until the best validation objective, in minutes; total : wall-clock time of the whole training, in minutes; ms/step : time per training step in milliseconds; Val. (%) : share of validation in the total training time; Peak GPU : maximum over seeds of the peak GPU memory during training, in GB.
Figure 6: Example queries from the AIDS700nef test set, GED (top) and MCS (bottom).
Figure 7: Example queries from the PTC test set, GED (top) and MCS (bottom).
As graphs scale to billions of nodes and edges, graph Machine Learning workloads are constrained by the cost of multi-hop traversals over exponentially growing neighborhoods. While various system-level and algorithmic optimizations have been proposed to accelerate Graph Neural Network (GNN) pipelines, data management and movement remain the primary bottlenecks at scale. In this paper, we explore whether graph sparsification, a well-established technique that reduces edges to create sparser neighborhoods, can serve as a lightweight pre-processing step to address these bottlenecks while preserving model quality. We develop an extensible experimental framework that integrates graph sparsification into GNN training and inference pipelines, and use it to study how four representative sparsification methods interact with four GNN architectures, across six graphs and two learning tasks (node classification and link prediction). Our central finding is counter-intuitive: removing a large fraction of a graph's edges, often the majority, has only a small effect on model quality, and sometimes improves it. For example, the K-Neighbor sparsifier removes 83.3% of the edges of the Products graph while GCN accuracy drops by only 0.2 percentage points, and on the Arxiv link prediction task, sparsification raises GraphSAGE test AUC from 0.86 to 0.95. Because the runtime costs scale with the number of edges, these reductions translate into substantial speedups. Our results show that the pre-processing overhead is quickly amortized, making sparsification practical even for very large graphs.
Graph Neural Networks (GNNs) have been widely adopted for their ability to compute expressive node representations in graph datasets. However, serving GNNs on large graphs is challenging due to the high communication, computation, and memory overheads of constructing and executing computation graphs, which represent information flow across large neighborhoods. Existing approximation techniques in training can mitigate the overheads but, in serving, still lead to high latency and/or accuracy loss. To this end, we propose Reforge, a system that enables low-latency GNN serving for large graphs with minimal accuracy loss through two key ideas. First, Reforge employs selective recomputation of precomputed embeddings, which allows for reusing precomputed computation subgraphs while selectively recomputing a small fraction to minimize accuracy loss. Second, we develop computation graph parallelism, which reduces communication overhead by parallelizing the creation and execution of computation graphs across machines. Our evaluation with large graph datasets and GNN models shows that Reforge significantly outperforms state-of-the-art techniques.
Geon-Woo Kim, Donghyun Kim, Jeongyoon Moon +5
The University of Texas at Austin · Georgia Institute of Technology
Graph neural networks (GNNs) rely on message passing over graph edges, making their computational and memory costs strongly dependent on graph density. Graph sparsification offers a natural way to reduce these costs, but removing edges indiscriminately can distort important communication structure and degrade predictive performance. We introduce Scaffold, a topology-based, unsupervised graph sparsification framework derived from support graph theory preconditioners. Scaffold explicitly controls two complementary structural quantities: dilation, which measures the length of rerouting paths induced by removed edges, and congestion, which measures how strongly these rerouted paths concentrate on the retained support. By jointly controlling dilation and congestion, Scaffold preserves short communication paths while avoiding structural bottlenecks. To our knowledge, Scaffold is the first scalable GNN sparsification framework to use a joint supporting-path dilation-congestion criterion. Across 19 homophilic and heterophilic benchmarks spanning small to large graphs, Scaffold achieves the best aggregate rank among the evaluated sparsification and related methods. Using only 10%-50% of the original edges per sparse support, Scaffold recovers or closely approaches full-graph GNN performance while using less than half the memory of full-graph training and reducing end-to-end training time, including sparsification overhead. We provide an open-source software package at https://github.com/siddhartha047/Scaffold.
Siddhartha Shankar Das, Sai Karthik Navuluru, S M Ferdous +7
Pacific Northwest National Laboratory · University of Texas at Dallas · University of North Carolina at Charlotte +3