Scaling Graph Similarity Learning with Graph Neural Networks

Scaling Graph Similarity Learning with Graph Neural Networks Ahmet Tüzen1*, Helge Langseth1 and Kjetil Nørvåg1

arXiv:2611.09805v1 [cs.LG] 6 Nov 2026

1*

Department of Computer Science, Norwegian University of Science and Technology, Trondheim, Norway.

*Corresponding author(s). E-mail(s): ahmet.tuzen@ntnu.no; Contributing authors: helge.langseth@ntnu.no; noervaag@ntnu.no; 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. Keywords: graph similarity learning, graph neural networks, large-scale graphs, graph edit distance, maximum common subgraph

1

1 Introduction Graphs represent entities and the relations between them, and many real-world data, such as social and biological networks, are naturally described in this form. Graph structures are therefore widely adopted across many areas, such as social networks and biological networks, and are a common data structure in machine learning and data mining. Graph matching is the problem of finding an optimal node-to-node correspondence between two graphs. In many real-world applications, requiring exact matching is impractical, and approximate formulations that measure graph similarity are more appropriate. This has motivated research on graph similarity learning, which aims to quantify the degree of similarity between graphs as a continuous score rather than finding correspondences. Both graph matching and graph similarity computation are computationally challenging. Graph Edit Distance (GED) (Bunke & Allermann, 1983) quantifies the similarity between two graphs by the cost of edit operations (e.g., node and edge insertions and deletions) required to transform one graph into the other, with lower values indicating higher similarity. Maximum Common Subgraph (MCS) (Bunke & Shearer, 1998) identifies the largest isomorphic subgraph shared by two graphs. Computing these metrics is NP-hard and quickly becomes intractable as the graph size increases (P. Yang et al., 2024). This computational barrier limits their applicability in real-world settings where graphs may contain hundreds or thousands of nodes. A toy example of graph matching and GED is given in Appendix A. Graph Neural Networks (GNNs) (Gori, Monfardini, & Scarselli, 2005; Scarselli, Gori, Tsoi, Hagenbuchner, & Monfardini, 2009) are widely used for learning on graphstructured data. GNNs iteratively aggregate information from neighboring nodes, which allows them to capture both local neighborhood properties and broader graph patterns (Zhou et al., 2020). GNNs have demonstrated strong performance across a wide range of graph-level downstream tasks, including node classification, graph classification, anomaly detection, and graph generation. Recent studies have adopted GNN architectures for graph matching and graph similarity learning (Ma, Ahmed, Willke, & Yu, 2021). However, existing GNN-based graph similarity methods are limited in scale (Jiang, Ning, & Dong, 2023). Most approaches are designed for and evaluated on datasets containing small graphs. Many rely on operations such as node-level crossgraph attention or pairwise node comparisons, which typically scale quadratically with graph size. In addition, the lack of large-scale benchmark datasets has prevented a systematic study of whether these methods can scale to the graph sizes encountered in domains such as social network analysis. To address these challenges, we propose FiLSim (FiLM-conditioned Large-graph Similarity), a scalable GNN-based framework for graph similarity learning. Our framework combines a shared GNN-based encoder with simple feature augmentation, graph-level pooling over the outputs of all encoder layers, and a prediction module based on Feature-wise Linear Modulation (FiLM) (Perez, Strub, de Vries, Dumoulin, & Courville, 2018) that operates on graph-level embeddings. This design allows each graph to be encoded independently and avoids expensive node-level alignment. We also introduce a systematic data-generation approach that produces large-scale synthetic datasets from real graphs, which allows us to train and evaluate FiLSim at 2

previously unexplored scales. We consider static, undirected graphs whose nodes are either unlabeled or carry discrete labels. We use GED with a unit cost for every edit operation. The main contributions of this work are summarized as follows:

• Scalable Pipeline: We demonstrate that a simplified GNN-based framework replacing node-level cross-graph alignment with efficient graph-level pooling can compute graph similarity at scales of more than 150,000 nodes without sacrificing performance on small benchmarks. • Large-Scale Graph Datasets: We construct large-scale synthetic graph datasets from real graphs with more than 150,000 nodes in the main experiments and more than 300,000 nodes in the extended experiments, i.e., graphs more than 1000× larger than those in existing benchmark datasets. We provide a sequential approach to generating these datasets, in which each label is an upper bound on the GED by construction, and all pairs among the generated graphs are labeled. • Comprehensive Evaluation: Through experiments on all datasets, we demonstrate that our method achieves the lowest error on all benchmark datasets and is the only method that remains accurate on all large-scale datasets, whereas each baseline runs out of memory or fails to learn on at least one of them. • Cost and Design Analysis: We measure the cost of every stage of training and inference and ablate each component of the model, showing that the encoding cost grows linearly with the graph size and quantifying the contribution of each design choice.

2 Preliminaries In this section, we introduce the notation used throughout the paper, define the graph distance and similarity measures we predict, formalize the learning problem, and provide the necessary background on GNNs.

Definition 1 (Graphs). A graph is defined as G = (V, E, X ), where V = {v1 , v2 , . . . , vn } is a set of n nodes, and E ⊆ V × V is the set of m = |E| undirected edges. X ∈ Rn×d0 is the node feature matrix, whose i-th row is the d0 -dimensional feature vector of vi . If a graph carries a node feature matrix, it is an attributed graph. If a graph does not carry node features, i.e., G = (V, E ), we refer to it as a plain graph. For a pair of graphs G1 and G2 , with Gi = (Vi , Ei , Xi ), we write ni = |Vi | and mi = |Ei |. Definition 2 (Graph edit distance). Let the edit operations be node insertion, node deletion, edge insertion, edge deletion, and, for graphs with node labels, node relabeling, each with a cost of 1. GED(G1 , G2 ) is the minimum number of edit operations that transform G1 into a graph isomorphic to G2 . Definition 3 (Maximum common subgraph). MCS(G1 , G2 ) is the number of nodes of the largest induced subgraph of G1 that is isomorphic to an induced subgraph of G2 .

3

Both GED and MCS are symmetric, and computing them exactly is NPhard (McCreesh, Prosser, & Trimble, 2017; Zeng, Tung, Wang, Feng, & Zhou, 2009).

2.1 Graph Similarity Learning Given a pair of graphs (G1 , G2 ), the goal of graph similarity learning is to learn a function f : G × G → R≥0 that predicts a similarity or distance y between the two inputs, where G denotes the space of all graphs. Since GED and MCS are symmetric, f should satisfy f (G1 , G2 ) = f (G2 , G1 ). The function f is typically parameterized by neural networks and learned from a i training set D = {(Gi1 , Gi2 , y i )}N i=1 , where y is the ground-truth GED or MCS between i i G1 and G2 . In practice, graph similarity models are used to compare a graph against many others, e.g., to rank a collection of graphs by their similarity to a query graph, which requires scoring a large number of pairs. Learned models that compute cross-graph node interactions typically cost O(n1 n2 ) per pair, which becomes computationally expensive for graphs with thousands of nodes and for collections with many graphs.

2.2 Graph Neural Networks GNNs are a class of deep models designed to operate on graph structures. At each (l) layer l, a node u updates its representation hu based on its previous representation (l) and the aggregated message aggu from its neighbors N (u) = {v : (u, v ) ∈ E}:

  (l) h(l) h(l−1) , agg(l) , u = UPDATE u u n o (l) agg(l) h(l−1) : v ∈ N (u) . u = AGGREGATE v Both UPDATE(l) and AGGREGATE(l) are differentiable functions, typically implemented as neural networks, and AGGREGATE is permutation-invariant (e.g., (0) sum, mean, max). The initial representations hu are computed from the node inputs (Section 4.1). Gated Graph Neural Networks. The Gated Graph Neural Network (GGNN) (Li, Zemel, Brockschmidt, & Tarlow, 2016) sums transformed neighbor representations and updates node states with a Gated Recurrent Unit (GRU) (Cho et al., 2014):

agg(l) u =

X

Θ(l) h(l−1) , v

v∈N (u)

  (l) (l−1) h(l) , u = GRU aggu , hu

4

where Θ(l) is a learnable weight matrix. The GRU gating mechanism enables each node to decide how much of its previous representation to keep at each layer. In the original formulation, the same GRU is shared across all propagation steps. After L layers of message passing, a graph-level representation zG is obtained via a readout function: n o zG = READOUT h(L) . u :u∈V READOUT is typically implemented using pooling methods such as sum, mean, max, or attention-based pooling. The choice of pooling mechanism affects which graph-level information is preserved, and we treat it as a hyperparameter.

3 Related Work 3.1 Computing Graph Similarity Measures Exact computation of graph similarity measures such as GED and MCS is computationally expensive, as both problems are NP-hard (Zeng et al., 2009). A* search (Hart, Nilsson, & Raphael, 1968; Riesen, Fankhauser, & Bunke, 2007) computes exact GED; however, exact GED computation remains infeasible for graphs with more than 16 nodes (Blumenthal & Gamper, 2020). To address this, various approximation approaches have been proposed, including beam search (Neuhaus, Riesen, & Bunke, 2006) and reductions to an assignment problem between the node sets (Fankhauser, Riesen, & Bunke, 2011). For MCS, McSplit (McCreesh et al., 2017) and GLSearch (Y. Bai, Xu, Sun, & Wang, 2021) rely on branch-and-bound search whose worst-case time complexity remains exponential. All of these approaches operate on each graph pair individually, so their cost grows with both the graph size and the number of pairs within a dataset.

3.2 GNN-Based Graph Similarity Learning A comprehensive overview of deep graph similarity learning is given by Liu, Liu, et al. (2025); here, we focus on GNN-based methods for GED and MCS prediction. Initial studies applying GNNs to graph similarity learning established two designs that later work builds on. SimGNN (Y. Bai et al., 2019) employs graph-level embedding functions to summarize each graph and combines these representations with histogram features extracted from pairwise comparison to predict similarity scores. Instead of deriving graph-level representations, GraphSim (Y. Bai, Ding, Gu, Sun, & Wang, 2020) computes a node-node pairwise similarity matrix after each GCN (Kipf & Welling, 2017) layer, then uses CNNs to capture fine-grained structural differences. These two models reflect a trade-off: node-level comparison captures finer differences between graphs, but it must be computed for every pair, and its cost scales with the product of the graph sizes. We therefore group subsequent work by how it treats cross-graph information.

3.2.1 Node-Level Cross-Graph Matching A substantial amount of research has been conducted to strengthen graph similarity prediction through explicit node-level alignment between input graphs. A common 5

design for this alignment is cross-graph attention, in which nodes in one graph attend to nodes in the other during encoding. GMN (Li, Gu, Dullien, Vinyals, & Kohli, 2019) introduces a cross-graph attention mechanism to compute node similarities before aggregating to graph-level similarity scores. Another line of work utilizes node-level matching more directly for edit operations. GraphEdX (Jain, Roy, Meher, Chakrabarti, & De, 2024) formulates GED with general edit costs as a quadratic assignment problem and replaces each cost term with a neural set divergence computed under node and node-pair alignments. GEN (Liu et al., 2026) incorporates edit-operation costs into node-matching costs and models dependencies between matches within and across graphs, enabling globally guided alignment in a single step without iterative refinement. These methods differ in how they align the two graphs, but they share a similar computational cost. Even when node embeddings are computed independently, the interaction or alignment step operates on all cross-graph node pairs; its cost therefore scales with the product of the graph sizes and must be repeated for every graph pair.

3.2.2 Pair-Independent Graph-Level Embeddings Methods in this group encode each graph independently and compute similarity only from the two resulting graph-level embeddings. Because no information is exchanged between the two graphs, the embedding of a graph can be computed once and reused when it reappears. GraSP (Zheng, Shi, & Yang, 2025) simplifies the overall architecture by removing node-level comparisons and enriching node representations with randomwalk positional encodings. Other models use cross-graph information during training but not at inference. EGSC (Qin et al., 2021) trains a teacher model that fuses the graph-level embeddings of both graphs, and then distills the resulting representation into a Siamese Graph Isomorphism Network (GIN) (K. Xu, Hu, Leskovec, & Jegelka, 2019) student that has no cross-graph interaction. ERIC (Zhuo & Tan, 2022) applies node-graph alignment as a regularization term during training and removes it at inference, so the similarity is computed from graph-level embeddings alone. It further combines a Neural Tensor Network (NTN) (Socher, Chen, Manning, & Ng, 2013) and an ℓ2 distance across GNN layers into a multi-scale GED discriminator. Other methods shape the embedding space itself so that its geometry reflects the target measure. GREED (Ranjan et al., 2022) adopts a Siamese GIN architecture and predicts GED and SED (subgraph edit distance) by using graph-level embeddings acquired by a series of neural networks. TaGSim (J. Bai & Zhao, 2021) decomposes GED into counts of individual edit operation types and predicts graph edit vectors from type-aware graph-level embeddings. G2R (Liu, Chen, Liu, He, & Li, 2025) represents nodes as closed regions and summarizes each graph as a region whose shape reflects its structure and whose volume reflects its size. The overlap between two graph regions approximates the MCS, and their disjoint parts are used for GED.

3.2.3 Edit-Path Recovery Methods in this group additionally predict a node matching from which an edit path is recovered. Since every recovered path is a feasible sequence of edit operations, its 6

length is an upper bound on the true GED. Noah (L. Yang & Zou, 2021) and GENNA* (R. Wang, Zhang, Yu, Yan, & Yang, 2021) use learned node matching to guide an A*-based search for the edit path. Other methods derive the edit path directly from a predicted matching matrix. GEDGNN (Piao et al., 2023) predicts a node matching matrix and a cost matrix, and recovers an edit path through k -best matching. Cheng, Yan, Wu, Huang, and Zhang (2025) propose three sets of algorithms: a supervised method based on a learnable Sinkhorn algorithm (GEDIOT), an unsupervised approach based on optimal transport and Gromov-Wasserstein discrepancy (GEDGW), and their ensemble method (GEDHOT). Recovering an edit path requires a node correspondence between the two graphs, so all methods in this group compute at least an n1 × n2 matching matrix for every pair, and those that add search or sampling repeat this cost over several candidates. However, these methods provide an interpretable edit path and a GED upper bound, which other methods do not.

3.3 Ground-Truth Labels and Synthetic Pair Generation Since exact GED computation is limited to small graphs, the commonly used benchmarks introduced with SimGNN (Y. Bai et al., 2019) provide exact labels only for graphs with at most 10 nodes, while labels for larger graphs are obtained from approximate solvers. M. Xu and Chang (2025) observe that some of the provided IMDB dataset (Yanardag & Vishwanathan, 2015) labels are therefore not exact and can be either smaller or larger than the true GED, and regenerate them with an exact algorithm. For graphs beyond the reach of exact solvers, several works generate pairs synthetically by applying a known number of edit operations ∆ to a graph and using ∆ as the label. GEDGNN (Piao et al., 2023) and GEN (Liu et al., 2026) follow this strategy, the latter on graphs with 100 to 400 nodes. Since a shorter edit path between the two graphs may exist, ∆ is in general only an upper bound on the true GED.

3.4 Node Features and Embedding Comparison Message-passing GNNs are at most as expressive as the 1-WL test (Morris et al., 2019; K. Xu et al., 2019). Positional encodings (PEs) address this by adding structural information to the node features, such as Laplacian eigenvector encodings (LapPE) (Dwivedi et al., 2023) and random-walk encodings (RWPE) (Dwivedi, Luu, Laurent, Bengio, & Bresson, 2022). For graphs without node attributes, a cheaper alternative is the Local Degree Profile (LDP) (Cai & Wang, 2018), which describes each node by its degree and summary statistics of neighborhood degrees and can be computed in time linear in the number of edges. Once the two graphs are encoded, a head combines their embeddings into a similarity score. The most common choice is the NTN (Socher et al., 2013), adopted by SimGNN, which models interactions between two graph-level embeddings via a bilinear tensor. It has since been used in many models, including TaGSim, ERIC, GEDGNN, GENN-A*, and GraSP. For d-dimensional embeddings and k output channels, NTN

7

requires O(d2 k ) parameters and computation per pair, and its bilinear form is not symmetric in the two graphs, whereas both GED and MCS are symmetric. Feature-wise linear modulation (FiLM) (Perez et al., 2018) conditions a network on external information by scaling and shifting each feature channel. GNNFiLM (Brockschmidt, 2020) uses it within message passing, where each node modulates the messages it receives from its neighbors. Outside graph similarity, CountGNN (Yu, Liu, Fang, & Zhang, 2023) predicts the number of subgraph isomorphisms with edge-centric message passing to capture fine-grained structural information. It modulates the input-graph representation conditioned on the query graph to improve matching. Since this modulation is applied to the edge representations of the input graph, the input-graph representation has to be recomputed for each query.

3.5 Scale in Graph Similarity Learning Most graph similarity learning methods are evaluated on the benchmarks introduced with SimGNN and GraphSim, whose graphs are small (AIDS: avg. ∼9 nodes, LINUX: avg. ∼8 nodes, IMDB: avg. ∼13 nodes) (Y. Bai et al., 2019, 2020). There are a few exceptions, but they either remain in the range of hundreds of nodes or rely on search operations. GEDGNN and GEN are trained on synthetic pairs with up to 400 nodes, and INFMCS (Lan, Hong, Ma, & Ma, 2024) is evaluated on graphs with a few hundred nodes. G2R is trained on graphs with at most 50 nodes and evaluated zero-shot on graphs with 1,000 to 2,000 nodes for MCS, but its error increases beyond a few hundred nodes. GLSearch handles pairs with up to roughly one million nodes, but it is a search procedure under a fixed budget per pair. FGWAlign (Tang, Zhao, Kong, Zhou, & Li, 2025) computes upper bounds on GED for graphs with more than 10,000 nodes without learning. To the best of our knowledge, no learned GED or MCS predictor has been trained and evaluated on graph pairs with thousands of nodes.

4 Methodology In this section, we introduce our proposed framework for graph similarity learning. FiLSim encodes each graph once, independently of the graph it is compared to, and scores pairs only from the resulting graph embeddings. We describe the node input features (Section 4.1), the encoder and pooling (Section 4.2), the similarity prediction module (Section 4.3), the training objective (Section 4.4), the construction of our large-scale datasets (Section 4.5), and the complexity of the framework (Section 4.6). Figure 1 illustrates the overall architecture.

4.1 Feature Augmentation Although graph similarity metrics fundamentally rely on structural information, node features can provide important complementary information. Many real-world graphs, however, lack meaningful node features or contain only categorical labels that do not reflect topology. We therefore augment the node input of every graph with a structural descriptor that can be computed in time linear in the graph size.

8

Distance

<

Local Degree Profile (LDP) shared weights

< <

GGNN Pooling Module

Layer L Layer 1

FiLM Interaction Module Loss

Layer Combination

Feature Augmentation

GNN Encoder

Prediction Module

Fig. 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 ŷ, and is trained on a weighted sum of a regression and a ranking loss.

For plain graphs, we create node features xu of node u ∈ V depending on the graph type. If the graph has node labels, xu is the one-hot encoding of the node label. If there are no node labels, xu is the one-hot encoding of degree deg(u). For all graphs, we add the LDP (Cai & Wang, 2018) fu ∈ R5 of each node u: the degree of u and the minimum, maximum, mean, and standard deviation of its neighbors’ degrees. Both inputs are computed once per graph in O(n + m) time. For high-degree and large graphs, we limit the size of the one-hot encoding and apply log(1 + ·) to LDP to compress its range. We project the node features and LDP with learnable linear layers Wx and Wf and combine them either by a learned weighted sum,

h(0) u = λ Wx xu + (1 − λ) Wf fu , (0)

where λ = σ (θλ ) is the sigmoid of a learnable parameter, or by concatenation, hu = [Wx xu ∥ Wf fu ], where each projection then has dimension d/2. The combination method is a hyperparameter that is selected per dataset.

4.2 GNN Encoder and Graph-Level Pooling (0)

Starting from the initial node representations hu , both input graphs are processed by a shared GGNN encoder in a Siamese (Bromley, Guyon, LeCun, Säckinger, & Shah, 1993) architecture. Both graphs of a pair pass through the same network with shared weights, which encodes each graph independently. This places both graphs in the same embedding space, which is required for comparing their embeddings directly. Since the encoder never sees the other graph of a pair, each graph is encoded once, and its embedding can be reused for every pair it appears in. Sharing the weights also halves the number of encoder parameters. We investigate two variants of the GGNN encoder that differ in how the L messagepassing steps are performed:

9

Single-Block GGNN. This variant applies one GGNN block with L messagepassing steps. Each step has its own weight matrix Θ(l) , while a single GRU is shared across all steps. A nonlinearity and dropout are applied once, after the last step: 
 H(L) = Dropout ReLU GGNNL (H(0) ) , (l)

where H(l) ∈ Rn×d stacks the node representations hu . Sharing the GRU reduces the number of parameters compared to the stacked variant, while the per-step computation remains the same. Stacked GGNN. This variant stacks L single-step GGNN layers, each with its own weight matrix and GRU, and adds a residual connection (He, Zhang, Ren, & Sun, 2016) after every layer:


 H(l) = H(l−1) + Dropout ReLU GGNN(l) (H(l−1) ) ,

l = 1, . . . , L.

The residual connections preserve the representation of the previous layer. Before pooling, we combine the outputs of all layers (for the single-block variant, (0) (L) hu and hu ). We then obtain zG by pooling the combined node representations.

4.3 Similarity Prediction Module The graph embeddings zG1 and zG2 obtained from pooling are passed to the prediction module, the only component of the framework that is evaluated per pair. It combines a learned interaction score with the distance between the two embeddings. We condition each embedding on the other with FiLM (Perez et al., 2018):

z̃1 = 1 + γ (zG2 ) ⊙ WzG1 + β (zG2 ),
z̃2 = 1 + γ (zG1 ) ⊙ WzG2 + β (zG1 ),

(1)

where γ and β are produced by a shared two-layer MLP, and W is a shared linear projection. The last layer of the MLP is initialized to zero, so the modulation is inactive at the start of training (γ = β = 0). We then combine z̃1 and z̃2 through their sum and absolute difference and map the concatenation to a scalar score s: 
 s = MLPscore ReLU MLPout ([ z̃1 + z̃2 ∥ |z̃1 − z̃2 | ]) . (2) Both operations are invariant to the order of the two graphs, and the FiLM parameters are shared between the two directions, so s is symmetric in G1 and G2 . The final prediction combines s with the Euclidean distance between the graph embeddings through a learnable weight α ∈ [0, 1]:

ŷGED = −α s + (1 − α) ∥zG1 − zG2 ∥2 , ŷMCS = α s − (1 − α) ∥zG1 − zG2 ∥2 . 10

For GED, a larger value indicates less similar graphs, whereas for MCS a larger value indicates more similar graphs. Therefore, the signs of both terms are opposite between the two formulas. Intuitively, the distance term ties the prediction directly to the geometry of the embedding space, while the interaction score can model dependencies between the two graphs that a distance alone cannot express. Compared to the NTN widely adopted in prior work (Section 3.4), which learns a weight for every pair of embedding dimensions in each of its slices, the prediction module of FiLSim operates on a projection of the embeddings and therefore has far fewer parameters.

4.4 Training Objective We train the model end-to-end on raw GED and MCS values with a loss that combines a primary regression loss with a ranking loss. The primary loss penalizes the absolute error of each prediction, and the ranking term encourages the predictions to align with the targets across pairs. The total loss is L = w Lprimary + (1 − w) Lranking with a fixed weight w ∈ (0, 1].

4.5 Large-Scale Dataset Generation Existing graph similarity benchmarks consist of small graphs, which prevents a systematic evaluation of scalability to real-world applications where graphs may contain thousands of nodes. At the same time, computing exact GED or MCS for such graphs is prohibitively expensive, so labels cannot be obtained by direct computation. We therefore derive collections of graphs from real-world graphs through controlled edit sequences, for which an upper bound on the GED of every pair is known by construction. A simpler construction would derive each graph independently from the source graph. However, at large scale, two such graphs share almost no edits, so the label of a pair is approximately the sum of the edit counts of the two graphs. In that case, the closest graphs to any query graph are simply the graphs with the fewest edits, regardless of the query graph. The task would be trivial, since even the ranking would not require comparing the two graphs. To avoid this, we generate graphs in a tree-like structure, in which each graph inherits the edits of its parent. Two graphs then share the edits of their common ancestors, so the label depends on the pair rather than on each graph separately. We use the source graphs as plain graphs and discard their node features and class labels if they exist. Our label counts only node and edge edits, so features would not affect it. In addition, inserting nodes would require artificial features, and their use might introduce bias. The large-scale datasets therefore evaluate only structural similarity. Starting from a real-world source graph G0 , we generate M graphs one after another. The first graph is derived from G0 , and each subsequent graph is derived from a parent randomly chosen among the recently generated graphs. Each derivation step applies a random number of edits, proportional to the size of G0 , using four operations:

11

• node deletion, together with its edges, • edge deletion, • edge insertion between two nodes that share a neighbor, • node insertion, connecting a new node to an existing node and some of its neighbors. A deleted node or edge is never added back. The source graph itself is not part of the dataset. Each node keeps its identity throughout the generation, so it is known which nodes two graphs have in common. To transform Ga into Gb , it is then sufficient to delete the nodes and edges that appear only in Ga and to insert those that appear only in Gb . We use the number of these operations as the label, y (Ga , Gb ) = |Va △Vb | + |Ea △Eb |, where △ denotes the symmetric difference. Since GED is the cost of the cheapest edit path, this label is an upper bound on the exact GED. Unlike prior synthetic constructions (Section 3.3), which label only a graph and its edited copy, we label all pairs among the generated graphs. For the large-scale datasets, we evaluate only GED prediction, since the construction provides labels only for GED.

4.6 Complexity Analysis The cost of FiLSim can be considered per graph and per pair. For a graph with n nodes and m edges, the input features are computed once in O(n + m) time. Each of the L GGNN steps aggregates messages over the edges in O(md) and applies the weight matrix and the GRU to every node in O(nd2 ), so the encoder costs O(L(md + nd2 )). Pooling is linear in the number of nodes. The cost per graph is therefore linear in both n and m. Only the prediction module depends on the pair, and its cost does not depend on the size of the graphs. Graph embeddings can therefore be computed once and reused: comparing Q query graphs against R reference graphs requires Q + R encoder passes and Q·R evaluations of the prediction module. We use this procedure in all evaluations. Models that compare the two graphs at the node level typically introduce at least an O(n1 n2 d) term per pair. Even when they encode each graph independently, this term has to be computed for every pair, so the comparison cannot be reduced or precomputed. We give the complexity comparison in Appendix B.

5 Experiments In this section, we evaluate FiLSim. We first describe the datasets, baseline methods, evaluation metrics, and implementation, and then present the results.

5.1 Datasets We evaluate our method on four widely used benchmark datasets for graph similarity learning and on large-scale datasets constructed from real-world graphs. Table 1 summarizes the key statistics of the datasets.

12

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. Dataset

# Graphs

Avg. Nodes

Avg. Edges

Avg. Degree

PTC AIDS700nef LINUX IMDBMulti

344 700 1000 1500

25.56 8.90 7.58 13.00

25.96 8.80 6.93 65.94

2.03 1.98 1.83 10.14

Cora PubMed Amazon Computers ogbn-arxiv

200 200 200 200

2,703 19,633 13,717 169,344

5,272 44,053 244,029 1,156,152

3.90 4.49 35.58 13.65

5.1.1 Benchmark Datasets Following GraphSim (Y. Bai et al., 2020), we use four benchmark datasets with their ground-truth GED and MCS values. For AIDS700nef and LINUX, GED values are computed exactly with A* (Hart et al., 1968; Riesen et al., 2007). For IMDBMulti and PTC, where exact computation is expensive, the GED label is the minimum of three approximate methods (Beam (Neuhaus et al., 2006), Hungarian (Riesen & Bunke, 2009), and VJ (Fankhauser et al., 2011)). MCS values are computed with McSplit (McCreesh et al., 2017). We keep the original 80/20 training/test split for each dataset and randomly select one-fifth of the training graphs for validation. This split is fixed for all runs. The datasets include AIDS700nef (X. Wang, Ding, Tung, Ying, & Jin, 2012; Zeng et al., 2009) (molecular graphs from the AIDS antiviral screen), LINUX (X. Wang et al., 2012) (program dependence graphs), IMDBMulti (Yanardag & Vishwanathan, 2015) (actor co-appearance networks), and PTC (Shrivastava & Li, 2014) (chemical compound graphs). LINUX and IMDBMulti consist of plain graphs, for which we use one-hot node degrees as node features, whereas AIDS700nef and PTC have node labels, for which we use their one-hot encodings (Section 4.1).

5.1.2 Large-Scale Datasets To systematically evaluate scalability, we use the large-scale datasets described in Section 4.5. In the main text, we report results on four of them, chosen to cover different sizes and densities: Cora (Z. Yang, Cohen, & Salakhutdinov, 2016) (small and sparse), PubMed (Z. Yang et al., 2016) (more nodes, still sparse), Amazon Computers (Shchur, Mumme, Bojchevski, & Günnemann, 2018) (fewer nodes than PubMed, but much denser), and ogbn-arxiv (Hu et al., 2020) (169K nodes and 1.16M edges). The remaining datasets are provided in Appendix C. For each real-world graph, we generate M ∈ {50, 200, 1000} graphs, label each pair with an upper bound on its GED, and split the graphs similarly to benchmark datasets.

13

5.2 Baseline Models We compare against the following graph similarity learning methods, grouped as in Section 3: methods with node-level cross-graph matching (SimGNN (Y. Bai et al., 2019), GMN (Li et al., 2019), GraphEdX (Jain et al., 2024), GEN (Liu et al., 2026)), methods that compare pair-independent graph-level embeddings (EGSC (Qin et al., 2021), ERIC (Zhuo & Tan, 2022), GREED (Ranjan et al., 2022), GraSP (Zheng et al., 2025), G2R (Liu, Chen, et al., 2025)), and methods that recover edit paths (GEDGNN (Piao et al., 2023), GEDIOT (Cheng et al., 2025)). All baselines use the same datasets, splits, and evaluation code as our method. Each baseline is run with its official implementation and its own training target. The implementation details are given in Appendix G.

5.3 Evaluation Metrics All metrics are computed on raw GED and MCS values. Each test graph is compared with all reference graphs, i.e., the training and validation graphs. We report the Mean Absolute Error (MAE) over all test pairs and the Relative Absolute Error (RAE) (Witten, Frank, & Hall, 2011), the ratio of the model’s total absolute error to that of always predicting the mean training label, so that values below 1 indicate an improvement over this predictor. Additionally, we use Spearman’s rank correlation coefficient (ρ) (Spearman, 1904) and Kendall’s rank correlation coefficient (τ ) (Kendall, 1938) to assess how well the predicted ranking aligns with the ground-truth ranking. To complement them, we include Precision at 10 (P@10), the fraction of the ground-truth 10 most similar reference graphs that also appear among the predicted 10 most similar ones, where the most similar graphs are those with the smallest GED or the largest MCS. While ρ and τ measure the quality of the whole ranking, P@10 focuses on the accuracy of top-ranked predictions. For efficiency, we report the inference time per 10,000 graph pairs, measured on the test pairs with each method’s own implementation on the same experimental setup. Further details of the evaluation metrics are in Appendix F.

5.4 Implementation We implement FiLSim in Python with PyTorch (Paszke et al., 2019) and PyTorch Geometric (Fey & Lenssen, 2019), building on the implementation of GraSP (Zheng et al., 2025). All experiments run on a single NVIDIA A100 GPU with 40 GB of memory and 64 GB of host memory. The code is available at https://github.com/ahmetTuzen/ FiLSim. Early stopping and hyperparameter selection use only the validation set. The test set is used once for the final evaluation. Further training details are given in Appendix D.

5.5 Experimental Setup All methods, including FiLSim, are trained under the same time limits: 2 hours of training (and validation, if the method uses it) on the benchmark datasets and 6 hours

14

on the large-scale datasets. The same limits apply to inference. Runs that cannot complete a single pass over the training pairs within the time limit or that exhaust memory are reported as TO or OOM, respectively. To account for randomness, we repeat each experiment with 10 seeds on the benchmark datasets and 3 seeds on the large-scale datasets. The data split is fixed across seeds. Due to space limitations, the main tables report the mean over seeds, and the standard deviations are given in Appendix H. In the main text, we report MAE for the benchmark datasets and RAE for the large-scale datasets; the other measure, along with P@20, is listed in Appendix H. Baselines whose implementations report only GED are additionally trained with MCS labels, except for GEDGNN and GEDIOT, which require GED node matchings and are therefore not evaluated on MCS. Here, we report only the main findings; detailed explanations and discussions are left to the extended experiments in Appendix H.

5.6 Results on Benchmark Datasets Tables 2 and 3 report the results on the four benchmark datasets for GED and MCS, respectively. Across both tasks, FiLSim has the lowest error on all four datasets and the best ranking metrics on all datasets except LINUX. For GED, FiLSim is the best method in all accuracy metrics on AIDS700nef, IMDBMulti, and PTC, with the largest gains in MAE. On LINUX, it has the lowest error, while the ranking metrics of many methods are close to the ceiling. Within the training budget, methods with node-level interaction do not outperform FiLSim on these datasets. The results for MCS follow a similar pattern: FiLSim is the best method in all accuracy metrics on AIDS700nef, IMDBMulti, and PTC, and has the lowest error on LINUX. Although FiLSim compares the two graphs only on their embeddings, it is the most accurate method on the benchmark datasets. While its scoring time is slightly longer than that of other graph-level methods, FiLSim offers the best overall performance.

5.7 Results on Large-Scale Datasets Table 4 reports the results on the large-scale datasets with M = 200. FiLSim has the best ranking metrics on all four large-scale datasets and the lowest RAE on two of them; on Cora and PubMed, G2R has a slightly lower RAE. The gap to the best baseline is largest on Amazon Computers and ogbn-arxiv. On ogbn-arxiv, the other methods either run out of memory or fail to learn a useful similarity, and only FiLSim remains accurate. FiLSim compares graphs only through their embeddings, so its encoding cost grows linearly with graph size (Section 5.8). However, a graph-level design alone is not sufficient, as most graph-level baselines fail on the large-scale datasets. Our experiments therefore lead to two findings: (1) strong performance on benchmark datasets does not necessarily extend to the large-scale datasets, and (2) a linear cost does not guarantee accurate predictions on large graphs.

15

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. AIDS700nef

Model

IMDBMulti

MAE↓

ρ↑

τ↑

P@10↑

Time↓

MAE↓

ρ↑

τ↑

P@10↑

Time↓

SimGNN GMN GraphEdX GEN

1.376 0.730 0.542 0.590

0.738 0.880 0.931 0.925

0.594 0.751 0.823 0.814

0.325 0.561 0.807 0.773

2.158 13.505 1.866 0.098

34.989 4.341

0.767 0.938

0.677 0.829

2.118 14.933

3.830

0.939

0.686 0.870 TO 0.870

0.843

0.280

EGSC ERIC GREED GraSP G2R

0.736 0.665 0.695 0.618 0.656

0.890 0.905 0.901 0.923 0.912

0.764 0.785 0.779 0.814 0.795

0.628 0.712 0.675 0.767 0.746

0.001 25.251 0.001 35.344 <0.001 3.672 0.002 4.088 0.001 31.392

0.888 0.797 0.929 0.945 0.805

0.825 0.745 0.856 0.890 0.740

0.851 0.849 0.833 0.859 0.890

<0.001 <0.001 <0.001 0.001 0.001

GEDGNN GEDIOT

0.877 0.729

0.853 0.901

0.718 0.779

0.572 0.721

23.383 34.152

32.968 18.502

0.737 0.824

0.644 0.742

0.674 0.757

23.209 35.416

FiLSim

0.532 0.937 0.834

0.830

0.005

2.235 0.959 0.916

0.905

0.003

LINUX

Model

PTC

MAE↓

ρ↑

τ↑

P@10↑

Time↓

MAE↓

ρ↑

τ↑

P@10↑

Time↓

SimGNN GMN GraphEdX GEN

1.060 0.134 0.139 0.089

0.878 0.972 0.972 0.973

0.778 0.905 0.906 0.904

0.872 0.982 0.991 0.992

2.134 12.877 0.837 0.078

9.898 3.039 9.512 3.793

0.922 0.933 0.848 0.937

0.816 0.830 0.724 0.841

0.415 0.475 0.481 0.589

2.348 14.494 751.344 0.531

EGSC ERIC GREED GraSP G2R

0.141 0.078 0.323 0.059 0.031

0.974 0.920 0.974 0.916 0.967 0.904 0.975 0.922 0.973 0.898

0.981 0.991 0.972 0.990 0.995

<0.001 0.001 <0.001 0.001 0.001

4.850 3.990 3.635 3.672 3.857

0.934 0.939 0.919 0.946 0.949

0.835 0.844 0.810 0.853 0.856

0.573 0.574 0.437 0.581 0.616

0.001 0.002 0.002 0.004 0.004

GEDGNN GEDIOT

0.271 0.228

0.968 0.972

0.906 0.912

0.952 0.967

23.267 34.533

38.990 38.133

0.639 0.558

0.500 0.508

0.316 0.350

23.805 38.201

FiLSim

0.020

0.974

0.909

0.992

0.003

2.436 0.958 0.872

0.642

0.007

5.8 Efficiency In addition to the time measurements in Sections 5.6 and 5.7, we measure the training and inference cost of FiLSim. At inference, each test graph is scored with all reference graphs. FiLSim encodes each graph independently, so every graph is encoded once, and only its embedding is passed to the prediction module, which reduces the computation time substantially. To test the effect of this design, we also run the same model in pairwise mode, where both graphs are re-encoded for each pair, similar to models with cross-graph comparisons. Table 5 compares the two encoding approaches, along with the total time and memory required for both training and inference. The measured times match the expected ratio: for the large-scale datasets with M = 200, there are 40 test graphs and 160 reference graphs, so pairwise encoding requires 2 × 40 × 160 encoder passes, whereas our approach requires 40 + 160, which is 64× fewer. Training is more expensive, but it fits on a single GPU for every dataset. Figure 2 illustrates the cost of encoding a single graph, measured on the mediansized graph of each dataset. On the benchmark graphs, encoding takes about 2 to 3

16

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. AIDS700nef

Model

IMDBMulti

MAE↓

ρ↑

τ↑

P@10↑

Time↓

MAE↓

ρ↑

τ↑

P@10↑

Time↓

SimGNN GMN GraphEdX GEN

0.711 0.422 0.482 0.303

0.756 0.888 0.880 0.933

0.623 0.778 0.764 0.836

0.387 0.769 0.771 0.874

2.203 16.762 1.576 0.098

0.451 0.197

0.870 0.881

0.909 0.937

2.121 15.248

0.295

0.868

0.784 0.798 TO 0.772

0.879

0.277

EGSC ERIC GREED GraSP G2R

0.436 0.339 0.472 0.331 0.303

0.892 0.907 0.881 0.926 0.920

0.785 0.806 0.769 0.829 0.820

0.740 0.801 0.761 0.871 0.823

0.001 0.001 <0.001 0.002 0.001

0.233 0.361 0.289 0.141 0.087

0.880 0.862 0.876 0.883 0.880

0.801 0.774 0.787 0.804 0.781

0.912 0.868 0.899 0.947 0.959

<0.001 <0.001 <0.001 0.001 0.001

FiLSim

0.264 0.935 0.839

0.889

0.003

0.081 0.885 0.808

0.964

0.002

LINUX

Model

PTC

MAE↓

ρ↑

τ↑

P@10↑

Time↓

MAE↓

ρ↑

τ↑

P@10↑

Time↓

SimGNN GMN GraphEdX GEN

0.368 0.084 0.105 0.048

0.751 0.813 0.813 0.813

0.654 0.715 0.715 0.714

0.666 0.992 0.998 0.994

2.157 13.539 0.912 0.077

1.707 1.581 5.339 1.392

0.725 0.790 0.516 0.865

0.586 0.653 0.398 0.748

0.397 0.511 0.415 0.634

2.325 16.718 751.328 0.673

EGSC ERIC GREED GraSP G2R

0.081 0.046 0.158 0.035 0.021

0.812 0.719 0.812 0.715 0.812 0.719 0.814 0.721 0.812 0.701

0.980 0.990 0.992 0.995 0.994

0.001 0.001 0.001 0.001 0.001

1.482 1.201 1.988 1.143 1.149

0.813 0.840 0.797 0.868 0.884

0.687 0.717 0.665 0.753 0.771

0.499 0.553 0.540 0.636 0.633

0.001 0.002 0.002 0.004 0.004

FiLSim

0.015 0.814 0.715

0.997

0.003

0.804 0.924 0.827

0.721

0.009

milliseconds regardless of size. For the large-scale datasets, both encoding time and memory usage increase with the total number of nodes and edges. LDP remains cheap on every dataset, since computing it requires only a single pass over the edges. On the other hand, random-walk encodings take longer as the graph size increases. Although random-walk encodings can be precomputed, their cost grows faster than the graph size, whereas the cost of LDP does not. The inference cost of FiLSim is illustrated in Figure 3. For large-scale datasets, the cost is dominated by the GNN encoder, data transfer, and pooling, the order of which depends on the dataset. On the benchmark datasets, the order is different: pair scoring is the most expensive part, because the graphs are small and the number of pairs is high. Even on the largest datasets, memory usage of FiLSim is far below the limits. Stages are timed separately, so their sum can differ slightly from the end-to-end scoring time in Table 5.

5.9 Ablation Study To assess the contribution of each design choice, we remove or replace one component of FiLSim at a time while keeping all other components unchanged. We first compare FiLM with NTN, the most widely adopted prediction module, across all datasets (Table 6). The remaining variants (Table 7) are evaluated only on AIDS700nef and

17

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. Cora

Model RAE↓

ρ↑

SimGNN GMN GraphEdX GEN

2.734 0.309

0.950

1.058

EGSC ERIC GREED GraSP G2R

τ↑

PubMed P@10↑

Time↓ 19.795 268.426

0.195

0.045 0.822 0.723 OOM 0.144 0.077

2.734 0.992 0.224 0.301 0.188

0.033 0.987 0.955 0.989

0.023 0.914 0.835 0.925

0.045 0.078 0.844 0.711 0.866

0.191 0.030 0.102 0.267 0.428

GEDGNN GEDIOT

2.734 2.692

0.162 0.187

0.112 0.128

0.176 0.187

204.246 63.290

FiLSim

0.190

0.991 0.939

0.913

0.285

RAE↓

ρ↑

P@10↑

Time↓ 958.379 2511.166

2.591 1.010 1.089

0.085 -0.270 -0.187 0.013 0.181 0.105 0.298 OOM 0.177 0.984 0.908 0.833

RAE↓

τ↑

Time↓

SimGNN 34.948 -0.165 -0.114 0.077 GMN 0.715 0.697 0.538 0.502 GraphEdX OOM GEN OOM EGSC ERIC GREED GraSP G2R

-0.242 -0.167 -0.150 -0.104 0.189 0.151 0.908 0.762

GEDGNN GEDIOT

2.763

FiLSim

0.241 0.979 0.895

0.179

0.063 0.056 0.181 0.085 0.652

OOM 0.129 0.150 0.852

3.134

0.185

0.986 0.914

0.880

1.573

ogbn-arxiv

P@10↑

1.609 1.070 2.768 0.380

ρ↑

0.653 0.203 0.686

OOM OOM

Amazon Computers

Model

τ↑

88.598 -0.271 -0.188 0.061 0.564 0.755 0.582 0.562 OOM 2879.634 OOM

Time↓

517.722 2060.480

OOM OOM OOM OOM

16.889 15.390 1.637 6.484 3.926

OOM OOM 0.187 0.173 OOM 0.212 0.183

13.015

2.048

ρ↑

τ↑

P@10↑

879.037

RAE↓

-

0.252

0.958

0.289

34.922

OOM OOM 0.342 0.956 0.831

0.713

12.452

Amazon Computers due to their computational cost. Ablations are grouped by the component of FiLSim they target, with horizontal lines separating them. The choice of the prediction module has a clear effect on the results. Among the 36 comparisons, NTN is better in only 3 cases, and the two modules are tied in 1 case, making FiLM the better choice for this task. Additionally, FiLM has fewer learnable parameters, making it an even stronger option between the two. The ablation results show that the contribution of each component depends on the dataset and the task. The FiLM-based score is the main contributor to the prediction: using only the distance degrades all metrics, whereas using only the score changes the results slightly and even lowers the RAE on AIDS700nef (MCS) and Amazon Computers. LDP is a cheap alternative to random-walk encodings, which perform similarly on AIDS700nef but run out of memory when computed for all graphs of Amazon Computers. The primary loss alone gives results comparable to FiLSim, while the ranking loss alone leads to large RAE values on MCS and on Amazon Computers. In the without-message-passing variant, we remove all edges, so each node is updated only from its own input features. This degrades all metrics on AIDS700nef, whereas on 18

Table 5 Training and scoring cost of FiLSim. Time is the median, including validation time. Training Dataset

Inference

Time (min) Peak GPU (GB) Encode once (s) Pairwise (s) Peak GPU (GB)

AIDS700nef IMDBMulti LINUX PTC

9 22 16 7

0.18 0.29 0.15 0.41

0.04 0.10 0.05 0.01

0.6 4.3 1.0 0.3

0.89 0.79 0.65 0.20

Cora PubMed Amazon C. ogbn-arxiv

120 154 165 306

8.72 8.27 8.87 10.50

0.18 1.01 1.31 7.97

11.6 66.0 85.0 509.7

1.75 1.72 4.02 1.66

(a) Encoding time

(b) Peak GPU memory

(c) Positional encoding time

40 ogbn-arxiv

5

Amazon Computers

PubMed

102

PubMed

Cora

Time (ms, GPU)

Amazon Computers

benchmarks

Memory (MB)

10

benchmarks

Time (ms)

20

LDP RW-16

104

103

103

102

benchmarks

ogbn-arxiv

101

Cora

100

2 101

102

103

104

Nodes per graph

105

101

102

103

104

Nodes per graph

105

101

102

103

104

105

Nodes per graph

Fig. 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.

Amazon Computers the ranking metrics remain close to those of FiLSim. The FiLMbased score is the main contributor to the prediction: using only the distance degrades all metrics, whereas using only the score changes the results slightly and even makes it better in some cases. However, the FiLM-based score alone is not robust; on ogbnarxiv, using only this score yields constant predictions, whereas combining it with the distance does not.

6 Conclusion In this work, we investigated the scalability of graph similarity learning by showing that a simplified pipeline without expensive cross-graph node interactions can achieve strong performance on standard benchmarks while scaling to large graphs. Our approach adopts a FiLM-based prediction module and extends pairwise GED prediction to graphs with more than 150,000 nodes, where none of the baselines remain accurate, and to graphs averaging over 300,000 nodes in the extended experiments in the appendix. We further show that asymptotic efficiency alone does not guarantee scalability: existing graph-level methods of equivalent complexity fail to converge, 19

(a) Time per stage AIDS700nef

35 ms

IMDBMulti

80 ms

LINUX

45 ms

PTC

12 ms

Cora

182 ms

PubMed

1.0 s

Amazon Computers

1.3 s

ogbn-arxiv

8.1 s

10−3

10−2

10−1

100

(b) Host memory

(c) GPU memory

64 GB limit

40 GB limit

1

101

Data transfer Feature embedding

10

100

1

GB

Wall-clock time (seconds) GNN Encoder Pooling

Pair scoring Peak host memory

10

GB Peak GPU memory

Fig. 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.

Table 6 Comparison of the FiLM and NTN prediction modules. Better scores are in bold.

Task

Dataset

ρ↑

RAE↓

P@10↑

NTN

FiLM

NTN

FiLM

NTN

FiLM

GED

AIDS700nef IMDBMulti LINUX PTC Cora PubMed Amazon C. ogbn-arxiv

0.293 0.043 0.046 0.156 0.199 0.201 0.347 0.333

0.265 0.027 0.009 0.102 0.190 0.185 0.241 0.342

0.922 0.948 0.973 0.943 0.990 0.978 0.935 0.958

0.937 0.959 0.974 0.958 0.991 0.986 0.979 0.956

0.738 0.863 0.986 0.583 0.900 0.812 0.360 0.680

0.830 0.905 0.992 0.642 0.913 0.880 0.852 0.713

MCS

AIDS700nef IMDBMulti LINUX PTC

0.212 0.093 0.070 0.226

0.198 0.047 0.019 0.223

0.935 0.881 0.812 0.912

0.935 0.885 0.814 0.924

0.897 0.935 0.994 0.712

0.889 0.964 0.997 0.721

degrade ranking quality, or exhaust memory at this scale, whereas FiLSim remains accurate. Through experiments on four benchmark datasets and four large-scale synthetic datasets, we demonstrated that FiLSim achieves strong performance across diverse graph types and sizes. Our large-scale dataset generation methodology provides a systematic approach for creating large-scale datasets with GED upper-bound labels for all pairs, without requiring expensive pairwise distance computations. The generated

20

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). 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) Distance only (α=0)

0.267 0.326

0.936 0.913

0.826 0.732

0.181 2.851

0.932 0.864

0.882 0.715

0.230 2.757

0.979 0.613

0.857 0.530

w/o LDP RW-16 instead of LDP w/o node features

0.271 0.255 0.524

0.935 0.940 0.773

0.818 0.831 0.463

0.195 0.194 0.803

0.935 0.934 0.451

0.884 0.893 0.212

0.270

0.793

0.341

0.961 OOM 0.945

Primary loss only Ranking loss only

0.268 0.328

0.937 0.921

0.829 0.744

0.201 1.991

0.934 0.910

0.884 0.820

0.221 2.831

0.976 0.980

0.865 0.645

w/o message passing w/o MP and LDP

0.292 0.471

0.921 0.817

0.735 0.399

0.360 0.575

0.857 0.718

0.654 0.401

0.290 0.260

0.978 0.965

0.845 0.802

0.773

datasets allow graph similarity methods to be evaluated on graphs with hundreds of thousands of nodes. Our study has several limitations, each of which points to future work. Our labels on the large-scale datasets are upper bounds on the GED rather than exact values, so the reported errors are measured against these bounds. The large-scale dataset generation only covers GED labels, and extending it to MCS labels and evaluation remains open. Our framework predicts scalar similarity scores and does not recover edit paths or per-operation counts; applications requiring interpretable edit sequences would need structured-output methods.

References Akiba, T., Sano, S., Yanase, T., Ohta, T., Koyama, M. (2019). Optuna: A next-generation hyperparameter optimization framework. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 2623–2631). Bai, J., & Zhao, P. (2021). TaGSim: Type-aware graph similarity learning and computation. Proceedings of the VLDB Endowment , 15 (2), 335–347, https://doi.org/ 10.14778/3489496.3489513

Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., Wang, W. (2019). SimGNN: A neural network approach to fast graph similarity computation. ACM International Conference on Web Search and Data Mining (pp. 384–392). Bai, Y., Ding, H., Gu, K., Sun, Y., Wang, W. (2020). Learning-based efficient graph similarity computation via multi-scale convolutional set matching. AAAI Conference on Artificial Intelligence (Vol. 34, pp. 3219–3226). Bai, Y., Xu, D., Sun, Y., Wang, W. (2021). GLSearch: Maximum common subgraph detection via learning to search. International Conference on Machine Learning 21

(Vol. 139, pp. 588–598). Blumenthal, D.B., & Gamper, J. (2020). On the exact computation of the graph edit distance. Pattern Recognition Letters , 134 , 46–57, https://doi.org/10.1016/ j.patrec.2018.05.002

Brockschmidt, M. (2020). GNN-FiLM: Graph neural networks with feature-wise linear modulation. International Conference on Machine Learning (pp. 1144–1152). Bromley, J., Guyon, I., LeCun, Y., Säckinger, E., Shah, R. (1993). Signature verification using a “Siamese” time delay neural network. Advances in Neural Information Processing Systems (Vol. 6, pp. 737–744). Bunke, H., & Allermann, G. (1983). Inexact graph matching for structural pattern recognition. Pattern Recognition Letters , 1 (4), 245–253, https://doi.org/10 .1016/0167-8655(83)90033-8

Bunke, H., & Shearer, K. (1998). A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters , 19 (3–4), 255–259, https:// doi.org/10.1016/S0167-8655(97)00179-7

Cai, C., & Wang, Y. (2018). A simple yet effective baseline for non-attributed graph classification. arXiv preprint 1811.03508. Cheng, Q., Yan, D., Wu, T., Huang, Z., Zhang, Q. (2025). Computing approximate graph edit distance via optimal transport. Proceedings of the ACM on Management of Data , 3 (1), 1–26, https://doi.org/10.1145/3709673

Cho, K., van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., Bengio, Y. (2014). Learning phrase representations using RNN encoder– decoder for statistical machine translation. Conference on Empirical Methods in Natural Language Processing (pp. 1724–1734). Dwivedi, V.P., Joshi, C.K., Luu, A.T., Laurent, T., Bengio, Y., Bresson, X. (2023). Benchmarking graph neural networks. Journal of Machine Learning Research , 24 (43), 1–48,

Dwivedi, V.P., Luu, A.T., Laurent, T., Bengio, Y., Bresson, X. (2022). Graph neural networks with learnable structural and positional representations. International Conference on Learning Representations.

22

Fankhauser, S., Riesen, K., Bunke, H. (2011). Speeding up graph edit distance computation through fast bipartite matching. International Workshop on Graph-Based Representations in Pattern Recognition (pp. 102–111). Fey, M., & Lenssen, J.E. (2019). Fast graph representation learning with PyTorch Geometric. International Conference on Learning Representations Workshop on Representation Learning on Graphs and Manifolds. Gori, M., Monfardini, G., Scarselli, F. (2005). A new model for learning in graph domains. IEEE International Joint Conference on Neural Networks (Vol. 2, pp. 729–734). Hart, P.E., Nilsson, N.J., Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics , 4 (2), 100–107, https://doi.org/10.1109/TSSC.1968.300136

He, K., Zhang, X., Ren, S., Sun, J. (2016). Deep residual learning for image recognition. IEEE Conference on Computer Vision and Pattern Recognition (pp. 770–778). Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., . . . Leskovec, J. (2020). Open Graph Benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems. Jain, E., Roy, I., Meher, S., Chakrabarti, S., De, A. (2024). Graph edit distance with general costs using neural set divergence. Advances in Neural Information Processing Systems (Vol. 37, pp. 73399–73438). Jiang, N., Ning, B., Dong, J. (2023). International Conference on Image, Vision and Computing, title=A survey of GNN-based graph similarity learning (pp. 650–654). Kendall, M.G. (1938). A new measure of rank correlation. Biometrika , 30 (1–2), 81–93, https://doi.org/10.1093/biomet/30.1-2.81

Kipf, T.N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations. Lan, Z., Hong, B., Ma, Y., Ma, F. (2024). More interpretable graph similarity computation via maximum common subgraph inference. IEEE Transactions on Knowledge and Data Engineering , 36 (11), 6588–6599, https://doi.org/10.1109/ TKDE.2024.3387044

Li, Y., Gu, C., Dullien, T., Vinyals, O., Kohli, P. (2019). Graph matching networks for learning the similarity of graph structured objects. International Conference

23

on Machine Learning (Vol. 97, pp. 3835–3845). Li, Y., Zemel, R., Brockschmidt, M., Tarlow, D. (2016). Gated graph sequence neural networks. International Conference on Learning Representations. Liu, Z., Chen, Y., Liu, N., He, J., Li, D. (2025). Graph2Region: Efficient graph similarity learning with structure and scale restoration. IEEE Transactions on Knowledge and Data Engineering , , https://doi.org/10.1109/TKDE.2025 .3617461

Liu, Z., Liu, N., Chen, Y., He, J., Ma, S., Li, D. (2026). Rethinking flexible graph similarity computation: One-step alignment with global guidance. IEEE International Conference on Data Engineering (pp. 1435–1448). Liu, Z., Liu, N., Chen, Y., Wen, Z., He, J., Li, D. (2025). Graph theory-based deep graph similarity learning: A unified survey of pipeline, techniques, and challenges. Transactions on Machine Learning Research , ,

Ma, G., Ahmed, N.K., Willke, T.L., Yu, P.S. (2021). Deep graph similarity learning: A survey. Data Mining and Knowledge Discovery , 35 , 688–725, https://doi.org/ 10.1007/s10618-020-00733-5

McCreesh, C., Prosser, P., Trimble, J. (2017). A partitioning algorithm for maximum common subgraph problems. International Joint Conference on Artificial Intelligence (pp. 712–719). Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., Grohe, M. (2019). Weisfeiler and Leman go neural: Higher-order graph neural networks. AAAI Conference on Artificial Intelligence (Vol. 33, pp. 4602–4609). Neuhaus, M., Riesen, K., Bunke, H. (2006). Fast suboptimal algorithms for the computation of graph edit distance. Joint IAPR International Workshops on Structural, Syntactic, and Statistical Pattern Recognition (pp. 163–172). Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., . . . Chintala, S. (2019). PyTorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems (Vol. 32, pp. 8024–8035). Perez, E., Strub, F., de Vries, H., Dumoulin, V., Courville, A. (2018). FiLM: Visual reasoning with a general conditioning layer. AAAI Conference on Artificial Intelligence (Vol. 32). Piao, C., Xu, T., Sun, X., Rong, Y., Zhao, K., Cheng, H. (2023). Computing graph edit distance via neural graph matching. Proceedings of the VLDB Endowment ,

24

16 (8), 1817–1829, https://doi.org/10.14778/3594512.3594514

Qin, C., Zhao, H., Wang, L., Wang, H., Zhang, Y., Fu, Y. (2021). Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation. Advances in Neural Information Processing Systems (Vol. 34, pp. 14110–14121). Ranjan, R., Grover, S., Medya, S., Chakaravarthy, V., Sabharwal, Y., Ranu, S. (2022). GREED: A neural framework for learning graph distance functions. Advances in Neural Information Processing Systems (Vol. 35, pp. 22518–22530). Riesen, K., & Bunke, H. (2009). Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing , 27 (7), 950– 959, https://doi.org/10.1016/j.imavis.2008.04.004

Riesen, K., Fankhauser, S., Bunke, H. (2007). Speeding up graph edit distance computation with a bipartite heuristic. Mining and Learning with Graphs (pp. 21–24). Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G. (2009). The graph neural network model. IEEE Transactions on Neural Networks , 20 (1), 61–80, https://doi.org/10.1109/TNN.2008.2005605

Shchur, O., Mumme, M., Bojchevski, A., Günnemann, S. (2018). Pitfalls of graph neural network evaluation. arXiv preprint 1811.05868. Shrivastava, A., & Li, P. (2014). A new space for comparing graphs. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (pp. 62–71). Socher, R., Chen, D., Manning, C.D., Ng, A. (2013). Reasoning with neural tensor networks for knowledge base completion. Advances in Neural Information Processing Systems (Vol. 26, pp. 926–934). Spearman, C. (1904). The proof and measurement of association between two things. The American Journal of Psychology , 15 , 72–101, https://doi.org/10.2307/ 1412159

Tang, J., Zhao, X., Kong, L., Zhou, X., Li, J. (2025). Fused Gromov-Wasserstein alignment for graph edit distance computation and beyond. Proceedings of the VLDB Endowment , 18 (10), 3641–3654, https://doi.org/10.14778/3748191.3748221

25

Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., . . . SciPy 1.0 Contributors (2020). SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods , 17 (3), 261–272, https:// doi.org/10.1038/s41592-019-0686-2

Wang, R., Zhang, T., Yu, T., Yan, J., Yang, X. (2021). Combinatorial learning of graph edit distance via dynamic embedding. IEEE Conference on Computer Vision and Pattern Recognition (pp. 5237–5246). Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H. (2012). An efficient graph indexing method. IEEE International Conference on Data Engineering (pp. 210–221). Witten, I.H., Frank, E., Hall, M.A. (2011). Data mining: Practical machine learning tools and techniques (3rd ed.). Morgan Kaufmann. Xu, K., Hu, W., Leskovec, J., Jegelka, S. (2019). How powerful are graph neural networks? International Conference on Learning Representations. Xu, M., & Chang, L. (2025). Graph edit distance estimation: A new heuristic and a holistic evaluation of learning-based methods. Proceedings of the ACM on Management of Data , 3 (3), 1–24, https://doi.org/10.1145/3725304

Yanardag, P., & Vishwanathan, S.V.N. (2015). Deep graph kernels. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 1365– 1374). Yang, J., & Leskovec, J. (2012). Defining and evaluating network communities based on ground-truth. IEEE International Conference on Data Mining (pp. 745– 754). Yang, L., & Zou, L. (2021). Noah: Neural-optimized A* search algorithm for graph edit distance computation. IEEE International Conference on Data Engineering (pp. 576–587). Yang, P., Wang, H., Yang, J., Qian, Z., Zhang, Y., Lin, X. (2024). Deep learning approaches for similarity computation: A survey. IEEE Transactions on Knowledge and Data Engineering , 36 (12), 7893–7912, https://doi.org/10.1109/ TKDE.2024.3422484

Yang, R., Shi, J., Xiao, X., Yang, Y., Liu, J., Bhowmick, S.S. (2020). Scaling attributed network embedding to massive graphs. Proceedings of the VLDB Endowment , 14 (1), 37–49, https://doi.org/10.14778/3421424.3421430

26

Yang, Z., Cohen, W., Salakhutdinov, R. (2016). Revisiting semi-supervised learning with graph embeddings. International Conference on Machine Learning (pp. 40–48). Yu, X., Liu, Z., Fang, Y., Zhang, X. (2023). Learning to count isomorphisms with graph neural networks. AAAI Conference on Artificial Intelligence (Vol. 37, pp. 4845–4853). Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L. (2009). Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment , 2 (1), 25–36, https://doi.org/10.14778/1687627.1687631

Zheng, H., Shi, J., Yang, R. (2025). GraSP: Simple yet effective graph similarity predictions. AAAI Conference on Artificial Intelligence (Vol. 39, pp. 22884– 22892). Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., . . . Sun, M. (2020). Graph neural networks: A review of methods and applications. AI Open , 1 , 57–81, https://doi.org/10.1016/j.aiopen.2021.01.001

Zhuo, W., & Tan, G. (2022). Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems (Vol. 35, pp. 30181–30193).

Appendix A

Graph Matching and Graph Edit Distance Examples

Classical exact graph-matching approaches aim to find precise node-to-node correspondences between graph pairs, as shown in Figure 4. The graph matching problem is a challenge across many fields, such as computer vision (visual tracking, action recognition), bioinformatics, and source/binary code analysis. Since the two graphs in Figure 4 are isomorphic, their GED is 0. A toy example of GED is illustrated in Figure 5.

Appendix B

Complexity Comparison

Table 8 compares the cost of FiLSim with the baselines in our main experiments. We group the baselines as in Section 3 and report the cost per graph and per pair. The original papers report their complexity in different forms; hence, we rewrite them in the form used in Section 4.6, where an L-layer message-passing encoder with MLP or GRU updates incurs a cost of O(L(md + nd2 )) per graph. The table compares cost classes rather than exact operation counts.

27

Fig. 4 Graph matching example: two isomorphic graphs, with dashed lines showing corresponding nodes.

insert node + insert edge

delete edge

Fig. 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 .

Except for the pair-independent group, the per-pair cost contains at least one term that grows with n1 n2 , since these methods compute cross terms between all nodes of the two graphs. In GMN, these interactions are applied inside the encoder, so node representations depend on the pair and no part of the computation can be shared across pairs. The remaining methods in these groups encode each graph independently, but still compare the two graphs at the node level. SimGNN is discussed separately in Section 3 as one of the first GNN-based models, but we include it in the node-level group. Edit-path recovery methods additionally extract an edit path from the predicted node matching. We list the cost of this extra step in a separate column, since it is not required to predict the GED value. GEDGNN and GEDIOT extract K candidate node matchings with k -best matching in O(Kn3 ), where n = max(n1 , n2 ). In the pair-independent group, the per-pair cost depends only on the embedding dimension. It ranges from O(dz ) for GREED and G2R to O(d2z k ) for the NTN used in GraSP. EGSC combines the two embeddings using an MLP at a cost of O(d2z ). The cost of the prediction module of FiLSim lies between these two extremes: it is cheaper than an NTN but more expensive than a norm. None of these per-pair costs depends on the graph size.

28

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. Group

Methods

Cross-graph operation

Per graph

Node-level matching

SimGNN1 , GMN2 , GraphEdX3 , GEN

histogram, attention, or alignment over node pairs

O(L(md + nd2 ))2 ≥ O(n1 n2 d)

-

Edit-path recovery

GEDGNN1 , GEDIOT1

node matching matrix

O(L(md + nd2 ))

≥ O(n1 n2 d)

O(Kn3 )

none

O(L(md + nd2 ))

O(dz ) to O(d2z k) -

none

O(L(md + nd2 ))

O(dz d + d2 + dk) -

PairGREED, independent G2R, EGSC, ERIC4 , GraSP1 , 5 FiLSim

-

Per pair

Edit path

1

Uses an NTN, which adds O(d2z k) per pair.

2

GMN applies cross-graph interactions inside the encoder; the encoder cost is paid per pair.

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(n4max d) time and O(n4max ) memory per pair.

4

Low-rank NTN, O(dz d′ k) with d′ ≪ dz .

5

Additionally precomputes random-walk positional encodings, reported as O(rn2 ) for walk length r.

Table 9 Benchmark dataset statistics. Dataset

# Graphs

Train / Val / Test

Avg. n

Max. n

Avg. m

Max. m

344 700 1000 1500

220 / 55 / 69 448 / 112 / 140 640 / 160 / 200 960 / 240 / 300

25.56 8.90 7.58 13.00

109 10 10 89

25.96 8.80 6.93 65.94

108 14 13 1467

PTC AIDS700nef LINUX IMDBMulti

Appendix C C.1

Datasets

Benchmark Datasets

In addition to the details in Section 5.1, we provide further information here. Table 9 gives the number of graphs in each split and the average and maximum graph sizes in both the number of nodes and edges.

C.2

Large-Scale Datasets

Table 10 lists the main properties of the ten real-world graphs used to build the largescale datasets. For each graph and each M , the generated graphs are split into 64%, 16%, and 20% for training, validation, and testing. The number of graphs and pairs in each split is given in Table 11. Training pairs are sampled from all distinct pairs 29

of training graphs, and each validation or test graph is compared with all training and validation graphs, excluding the graph itself. Table 12 gives the statistics of the generated graph datasets. Table 10 Main statistics of real-world graphs used to build the large-scale datasets. Graph

n

m

Avg. Degree

Wiki (R. Yang et al., 2020) Cora (Z. Yang et al., 2016) CiteSeer (Z. Yang et al., 2016) BlogCatalog (R. Yang et al., 2020) Flickr (R. Yang et al., 2020) Amazon Computers (Shchur et al., 2018) PubMed (Z. Yang et al., 2016)

2,405 2,708 3,327 5,196 7,575 13,752 19,717

11,596 5,278 4,552 171,743 239,738 245,861 44,324

9.64 3.90 2.74 66.11 63.30 35.76 4.50

ogbn-arxiv (Hu et al., 2020) com-DBLP (J. Yang & Leskovec, 2012) com-Amazon (J. Yang & Leskovec, 2012)

169,343 317,080 334,863

1,157,799 1,049,866 925,872

13.67 6.62 5.53

Table 11 Number of graphs and pairs per split for the large-scale datasets. The counts are the same for all ten graphs. M

Train / Val / Test

Train pairs

Val pairs

Test pairs

50 200 1000

32 / 8 / 10 128 / 32 / 40 640 / 160 / 200

496 8,128 204,480

312 5,088 127,840

400 6,400 160,000

Appendix D

Implementation Details

Software. The package versions and installation instructions are given in the repository. To ensure reproducibility, each run is seeded. All experiments are run on a single NVIDIA A100 GPU with 40 GB of memory and 64 GB of host memory. Training. We train in steps, where each step uses one batch of training pairs. In each pass over the training set, each graph appears once as the first and once as the second graph of a pair. We use the Adam optimizer with weight decay and gradient clipping along with a validation-based learning-rate scheduler that reduces the learning rate if there is no improvement on the validation set. We define the validation objective for FiLSim as ρ + τ + 0.5 P@10 + 0.5 P@20 − 0.5 RAE. Every 250 steps, we evaluate on the validation set and keep the best checkpoint based on the validation objective. Training stops when the validation objective does not 30

Table 12 Statistics of the generated graphs. GED label: min / median / max of the GED upper bound used as the label, over all pairs. Graph

M

Avg. n

Avg. m

GED label

Wiki

50 200 1000

2,403 2,403 2,398

11,582 11,593 11,554

18 / 301 / 736 17 / 524 / 1,310 14 / 781 / 1,825

Cora

50 200 1000

2,703 2,703 2,703

5,267 5,272 5,259

14 / 199 / 467 15 / 369 / 866 11 / 472 / 1,013

CiteSeer

50 200 1000

3,327 3,327 3,324

4,557 4,560 4,531

16 / 203 / 492 13 / 349 / 840 11 / 498 / 1,269

BlogCatalog

50 200 1000

5,186 5,186 5,190

171,302 171,227 171,495

299 / 4,648 / 11,949 221 / 7,570 / 18,114 203 / 10,350 / 20,810

Flickr

50 200 1000

7,575 7,568 7,570

239,786 239,904 239,032

192 / 4,703 / 11,428 225 / 8,079 / 19,403 174 / 12,638 / 28,778

Amazon C.

50 200 1000

13,737 13,717 13,721

244,742 244,029 244,284

381 / 4,816 / 10,920 368 / 11,118 / 26,696 312 / 14,461 / 30,219

PubMed

50 200 1000

19,685 19,633 19,639

44,275 44,053 43,939

119 / 1,601 / 4,255 98 / 2,967 / 6,738 102 / 4,118 / 8,698

ogbn-arxiv

50 200 1000

169,212 169,344 169,186

1,156,984 1,156,152 1,155,069

2,355 / 28,868 / 69,312 1,943 / 51,288 / 126,624 1,895 / 67,648 / 148,871

com-DBLP

50 200 1000

316,587 316,810 316,439

1,047,236 1,051,380 1,044,017

2,809 / 33,969 / 79,419 2,514 / 54,375 / 133,354 2,313 / 70,367 / 166,320

com-Amazon

50 200 1000

334,856 334,415 334,323

928,747 921,061 925,118

2,887 / 30,334 / 74,171 2,653 / 55,931 / 125,546 2,605 / 75,092 / 162,620

improve or when the time limit is reached. The weights α and λ are initialized to 0.5. The one-hot degree is capped at 128 (only meaningful for large graphs) and log(1 + ·) is applied to LDP. For hyperparameter optimization, we adopt Optuna (Akiba, Sano, Yanase, Ohta, & Koyama, 2019). Benchmark datasets. We run up to 250 trials per dataset. The three best configurations are retrained with 10 seeds, and we report the one with the best mean validation objective. The batch size is fixed to 128. Large-scale datasets. Since training on large datasets is more expensive than on the benchmarks, we limit the hyperparameter search. The GNN encoder is fixed to the Stacked GGNN (d = 128, L = 4. We search only for the other hyperparameters at M = 200 within a 24-hour wall-clock time limit, resulting in 64 to 82 completed trials

31

for the seven smaller graphs and 38 to 49 trials for the three largest graphs (ogbnarxiv, com-DBLP, and com-Amazon). As with the benchmark datasets, we retrain the configuration with the best validation objective, but with 3 seeds instead of 10.

Appendix E

Hyperparameters

We select the hyperparameters of FiLSim for each dataset and task separately, with Optuna and the validation objective defined in Appendix D. On all datasets, each optimization trial trains for at most 20,000 steps, and the validation objective is measured every 250 steps. In all searches, a trial stops early when the validation objective does not improve for 10 to 40 validations, depending on the dataset size. We then retrain the best configurations with 10 seeds on the benchmark datasets and 3 seeds on the large-scale datasets. The detailed hyperparameter space can be found in our repository. Some settings are fixed rather than searched: training is measured in optimization steps, not epochs. Training pairs are sampled at random from the training graphs in every pass. The model with the best validation objective is evaluated on the test set. We use the Adam optimizer with a plateau-based learning-rate scheduler that reduces the learning rate when the validation objective no longer improves.

Appendix F

Evaluation Metrics

All metrics are computed on raw GED or MCS values. Let Q be the set of query graphs (test or validation graphs) and R the reference set, which contains all training and validation graphs, with Q = |Q| and R = |R| as in Section 4.6. For a query graph q , we compare it with every reference graph r ∈ R (excluding r = q during validation). We write yqr for the label and ŷqr for the prediction, and P for the set of all evaluated pairs. Error. MAE and RAE are computed over all evaluated pairs: 1 X |ŷqr − yqr |, |P| (q,r)∈P P (q,r)∈P |ŷqr − yqr | RAE = P , (q,r)∈P |yqr − ȳ|

MAE =

where ȳ is the mean label over all pairs of training graphs. RAE does not depend on the scale of the labels; therefore, it is more suitable than MAE for comparing results across graph sizes. Ranking. For each q , we rank the reference graphs by their labels and by the predictions, and compute Spearman’s ρ and Kendall’s τ using SciPy (Virtanen et al., 2020). We report the mean over query graphs. Precision at k. For each q , the true top-k set contains the k most similar reference graphs, i.e., those with the smallest GED or the largest MCS. Reference graphs may share the same label, and we include all graphs tied with the k -th graph in the true set. Hence, the true set can contain more than k graphs. P@k is the number of graphs 32

among the k most similar ones according to the predictions that are in the true set, divided by k . We report precision at k = 10 and k = 20 as the mean over all query graphs. Comparison across M . On the large-scale datasets, the labels grow with M as shown in Table 12, and the reference set contains more graphs for larger M as shown in Table 11. MAE and P@k therefore cannot be compared directly across different values of M , while RAE, ρ, and τ are better suited for this comparison.

Appendix G

Baselines

For all baselines, we use their public repositories. Each method is trained on the same split as FiLSim, with its own input features and target. Their predictions are converted back to raw GED or MCS values, and all metrics are computed with our evaluation code. The training budget is 2 hours on the benchmark datasets and 6 hours on the large-scale datasets, and runs that cannot complete a single pass over the training pairs within the budget are reported as TO. When a run exceeds the memory limit, we repeatedly halve the batch size, down to 4 on the benchmark datasets and 1 on the large-scale datasets. We use 10 seeds on the benchmark datasets and 3 on the largescale datasets. For graph-level methods, the reported time results are derived from cached graph embeddings. Below, we list all deviations from the published setups and the design choices we make for each baseline.

• SimGNN: We enable the histogram features and increase the number of epochs for the large graphs. • GMN: The repository trains with a margin loss, which does not produce GED values. Instead, we regress the distance between the two graph vectors onto the target using MSE, as is also done in other papers (Jain et al., 2024). • GraphEdX: We use λ = 1, which matches the unit-cost GED. • GEN: We run it as published. • GraSP: The repository evaluates on the validation set only in the last 5% of the epochs; we change it to match the budget. • GREED: We run as published. • ERIC: The validation window follows the budget, as in the GraSP modification. • EGSC: The teacher and the student share one budget, divided in the ratio of their epoch numbers in the repository. Only the student is used at inference. • G2R: We run as published. • GEDGNN and GEDIOT: We report the predicted GED value and do not run the k -best edit-path search, which is applied after training and is extremely slow for all test pairs. As ground-truth matchings, we use the TaGED matchings of the repository. Both are trained on the GPU, like the other methods. Since training needs GED node matchings, they are not evaluated on MCS.

Appendix H

Extended Experiments

This section reports the complete results behind the tables and figures of Sections 5.6 to 5.8: all metrics with standard deviations on the benchmark datasets, all large-scale 33

datasets and collection sizes, the training cost (Appendix H.3), and the case study (Appendix H.4).

H.1

Benchmark Datasets

Tables 13 and 14 extend Tables 2 and 3 with the relative absolute error (RAE) and P@20, and give the standard deviation over the same 10 seeds. GED. The detailed results align with the main experiments. RAE of FiLSim ranges from 0.009 on LINUX to 0.265 on AIDS700nef, i.e., the total error of FiLSim is between 0.9% and 26.5% of that of the mean predictor. P@20 follows P@10, and FiLSim has the highest P@20 on all four datasets (tied with ERIC on LINUX). The standard deviations indicate that these results are not sensitive to the seed: the standard deviations of the ranking metrics of FiLSim are at most 0.009 across the 10 seeds, whereas several baselines vary much more. On PTC, GEDGNN and GEDIOT have an RAE above 1, meaning that these models produce larger errors than the mean predictor. On IMDBMulti, G2R has the second-highest P@10 and P@20 but also one of the largest errors, so it identifies the most similar graphs but does not recover the scale of GED. On LINUX, all methods except SimGNN lie within a narrow range in ρ, τ , and P@k , which is a consequence of the tied labels. GraphEdX cannot complete a single pass over the IMDBMulti training pairs within the time limit, so it is reported as a timeout. MCS. Measurements show the same pattern for MCS. FiLSim is the best method across all six metrics on AIDS700nef, IMDBMulti, and PTC, including RAE and P@20. On LINUX, it has the lowest MAE and RAE, the best ρ (tied with GraSP), and the best P@20. The exceptions are τ on LINUX, where GraSP, EGSC, and GREED are slightly higher, and P@10 on LINUX, where GraphEdX is slightly higher. On this dataset, ρ is between 0.812 and 0.814 for all methods except SimGNN, indicating that the ranking metrics are close to their ceiling and that the remaining differences come from how each method orders graphs with equal labels. The variation across seeds is small for most methods. The largest differences between methods are on PTC, which contains the largest graphs among the benchmark datasets. The additional metrics and standard deviations do not change the conclusions of the main experiments. FiLSim is the most accurate method in the error metrics on all datasets and both tasks, and in the ranking metrics on all datasets except LINUX. FiLSim is among the most stable methods across seeds. Since it achieves the lowest errors and the highest ranking metrics across most datasets, FiLSim learns not only the graph order but also the GED and MCS values.

H.2

Large-Scale Datasets

In addition to the four large-scale datasets in Section 5.1, we provide six further datasets derived from Wiki, CiteSeer, BlogCatalog, Flickr, com-DBLP, and comAmazon, and we report all ten datasets for M ∈ {50, 200, 1000}. Since computation on these datasets is expensive, we select the best configuration on the validation set at M = 200 and reuse it for M = 50 and M = 1000 without further search. The details of these datasets are given in Appendix C.2. Due to computational constraints, we did

34

35

Model SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R GEDGNN GEDIOT FiLSim SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R GEDGNN GEDIOT FiLSim SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R GEDGNN GEDIOT FiLSim SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R GEDGNN GEDIOT FiLSim

Dataset AIDS700nef

IMDBMulti

LINUX

PTC

RAE 0.686±0.057 0.364±0.007 0.270±0.002 0.294±0.003 0.367±0.009 0.331±0.006 0.346±0.005 0.308±0.004 0.327±0.011 0.437±0.009 0.363±0.030 0.265±0.004 0.429±0.026 0.053±0.013 TO 0.047±0.002 0.310±0.013 0.433±0.030 0.045±0.002 0.050±0.003 0.385±0.020 0.404±0.126 0.227±0.096 0.027±0.001 0.492±0.095 0.062±0.003 0.065±0.003 0.042±0.004 0.066±0.010 0.036±0.003 0.150±0.001 0.027±0.016 0.014±0.002 0.126±0.015 0.106±0.019 0.009±0.002 0.415±0.053 0.127±0.006 0.398±0.050 0.159±0.004 0.203±0.027 0.167±0.014 0.152±0.004 0.154±0.003 0.162±0.017 1.633±0.091 1.597±0.382 0.102±0.002

MAE 1.376±0.114 0.730±0.015 0.542±0.005 0.590±0.006 0.736±0.017 0.665±0.011 0.695±0.011 0.618±0.008 0.656±0.022 0.877±0.018 0.729±0.060 0.532±0.008 34.989±2.112 4.341±1.023 TO 3.830±0.155 25.251±1.033 35.344±2.406 3.672±0.154 4.088±0.249 31.392±1.637 32.968±10.265 18.502±7.793 2.235±0.068 1.060±0.204 0.134±0.007 0.139±0.006 0.089±0.009 0.141±0.021 0.078±0.006 0.323±0.003 0.059±0.035 0.031±0.005 0.271±0.032 0.228±0.040 0.020±0.004 9.898±1.258 3.039±0.143 9.512±1.192 3.793±0.089 4.850±0.652 3.990±0.333 3.635±0.088 3.672±0.083 3.857±0.396 38.990±2.172 38.133±9.133 2.436±0.036

0.922±0.032 0.933±0.006 0.848±0.013 0.937±0.002 0.934±0.005 0.939±0.004 0.919±0.005 0.946±0.001 0.949±0.003 0.639±0.173 0.558±0.241 0.958±0.001

0.878±0.041 0.972±0.000 0.972±0.000 0.973±0.000 0.974±0.001 0.974±0.000 0.967±0.001 0.975±0.000 0.973±0.000 0.968±0.002 0.972±0.001 0.974±0.000

0.767±0.012 0.938±0.005 TO 0.939±0.001 0.888±0.013 0.797±0.024 0.929±0.006 0.945±0.003 0.805±0.017 0.737±0.041 0.824±0.037 0.959±0.001

0.738±0.027 0.880±0.006 0.931±0.001 0.925±0.001 0.890±0.002 0.905±0.002 0.901±0.002 0.923±0.001 0.912±0.002 0.853±0.006 0.901±0.013 0.937±0.001

ρ

0.816±0.038 0.830±0.008 0.724±0.015 0.841±0.002 0.835±0.005 0.844±0.005 0.810±0.006 0.853±0.002 0.856±0.003 0.500±0.147 0.508±0.157 0.872±0.001

0.778±0.051 0.905±0.001 0.906±0.001 0.904±0.001 0.920±0.001 0.916±0.002 0.904±0.001 0.922±0.001 0.898±0.001 0.906±0.005 0.912±0.003 0.909±0.001

0.686±0.013 0.870±0.009 TO 0.870±0.002 0.825±0.012 0.745±0.022 0.856±0.009 0.890±0.005 0.740±0.014 0.644±0.040 0.742±0.039 0.916±0.001

0.594±0.025 0.751±0.007 0.823±0.002 0.814±0.002 0.764±0.002 0.785±0.003 0.779±0.003 0.814±0.002 0.795±0.003 0.718±0.007 0.779±0.015 0.834±0.002

τ

0.415±0.084 0.475±0.031 0.481±0.018 0.589±0.016 0.573±0.016 0.574±0.015 0.437±0.022 0.581±0.011 0.616±0.011 0.316±0.074 0.350±0.070 0.642±0.007

0.872±0.078 0.982±0.002 0.991±0.002 0.992±0.005 0.981±0.008 0.991±0.003 0.972±0.005 0.990±0.005 0.995±0.001 0.952±0.011 0.967±0.019 0.992±0.003

0.677±0.038 0.829±0.012 TO 0.843±0.015 0.851±0.007 0.849±0.009 0.833±0.019 0.859±0.006 0.890±0.006 0.674±0.065 0.757±0.024 0.905±0.005

0.325±0.031 0.561±0.026 0.807±0.007 0.773±0.010 0.628±0.013 0.712±0.010 0.675±0.011 0.767±0.012 0.746±0.010 0.572±0.015 0.721±0.027 0.830±0.009

P@10

0.542±0.087 0.579±0.023 0.547±0.018 0.683±0.008 0.675±0.012 0.678±0.010 0.562±0.010 0.689±0.007 0.719±0.004 0.398±0.080 0.436±0.070 0.737±0.004

0.898±0.058 0.987±0.002 0.987±0.002 0.992±0.002 0.980±0.007 0.993±0.002 0.970±0.003 0.988±0.003 0.992±0.002 0.951±0.009 0.974±0.013 0.993±0.002

0.684±0.036 0.840±0.016 TO 0.860±0.011 0.859±0.006 0.855±0.005 0.846±0.016 0.875±0.005 0.895±0.004 0.700±0.045 0.770±0.028 0.924±0.003

0.446±0.038 0.661±0.022 0.840±0.005 0.827±0.007 0.716±0.010 0.778±0.009 0.754±0.009 0.827±0.005 0.805±0.010 0.653±0.019 0.783±0.021 0.867±0.007

P@20

Table 13 GED prediction on the benchmark datasets, all metrics. Mean ± standard deviation over 10 seeds. MAE: mean absolute error, RAE: relative absolute error, TO: timeout. Best result in bold, second best underlined, and third best in italic.

36

Model SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R FiLSim SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R FiLSim SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R FiLSim SimGNN GMN GraphEdX GEN EGSC ERIC GREED GraSP G2R FiLSim

Dataset AIDS700nef

IMDBMulti

LINUX

PTC

RAE 0.534±0.011 0.317±0.013 0.362±0.004 0.227±0.008 0.327±0.009 0.255±0.009 0.355±0.007 0.248±0.005 0.227±0.008 0.198±0.005 0.260±0.023 0.114±0.016 TO 0.170±0.019 0.134±0.017 0.208±0.049 0.167±0.006 0.081±0.010 0.050±0.004 0.047±0.002 0.464±0.068 0.106±0.011 0.133±0.004 0.060±0.005 0.102±0.011 0.058±0.007 0.200±0.002 0.044±0.007 0.027±0.005 0.019±0.002 0.473±0.028 0.438±0.019 1.479±0.362 0.386±0.020 0.410±0.029 0.333±0.014 0.551±0.031 0.317±0.013 0.318±0.007 0.223±0.004

MAE 0.711±0.015 0.422±0.017 0.482±0.005 0.303±0.011 0.436±0.012 0.339±0.012 0.472±0.010 0.331±0.007 0.303±0.010 0.264±0.007 0.451±0.040 0.197±0.027 TO 0.295±0.033 0.233±0.030 0.361±0.084 0.289±0.011 0.141±0.017 0.087±0.006 0.081±0.003 0.368±0.054 0.084±0.009 0.105±0.003 0.048±0.004 0.081±0.008 0.046±0.006 0.158±0.001 0.035±0.005 0.021±0.004 0.015±0.001 1.707±0.100 1.581±0.070 5.339±1.307 1.392±0.073 1.482±0.105 1.201±0.052 1.988±0.112 1.143±0.048 1.149±0.025 0.804±0.014

0.725±0.027 0.790±0.010 0.516±0.099 0.865±0.011 0.813±0.014 0.840±0.014 0.797±0.007 0.868±0.009 0.884±0.006 0.924±0.003

0.751±0.021 0.813±0.000 0.813±0.000 0.813±0.000 0.812±0.002 0.812±0.001 0.812±0.000 0.814±0.001 0.812±0.001 0.814±0.000

0.870±0.003 0.881±0.001 TO 0.868±0.003 0.880±0.002 0.862±0.008 0.876±0.002 0.883±0.001 0.880±0.000 0.885±0.000

0.756±0.008 0.888±0.007 0.880±0.002 0.933±0.003 0.892±0.005 0.907±0.004 0.881±0.006 0.926±0.002 0.920±0.003 0.935±0.001

ρ

0.586±0.025 0.653±0.011 0.398±0.086 0.748±0.016 0.687±0.014 0.717±0.014 0.665±0.007 0.753±0.010 0.771±0.006 0.827±0.003

0.654±0.021 0.715±0.001 0.715±0.001 0.714±0.001 0.719±0.002 0.715±0.001 0.719±0.000 0.721±0.001 0.701±0.001 0.715±0.001

0.784±0.004 0.798±0.001 TO 0.772±0.005 0.801±0.002 0.774±0.009 0.787±0.003 0.804±0.001 0.781±0.000 0.808±0.000

0.623±0.008 0.778±0.008 0.764±0.002 0.836±0.003 0.785±0.005 0.806±0.004 0.769±0.007 0.829±0.002 0.820±0.002 0.839±0.001

τ

0.397±0.034 0.511±0.014 0.415±0.055 0.634±0.053 0.499±0.020 0.553±0.027 0.540±0.024 0.636±0.023 0.633±0.016 0.721±0.010

0.666±0.046 0.992±0.002 0.998±0.002 0.994±0.004 0.980±0.014 0.990±0.006 0.992±0.002 0.995±0.004 0.994±0.003 0.997±0.001

0.909±0.009 0.937±0.011 TO 0.879±0.024 0.912±0.019 0.868±0.028 0.899±0.017 0.947±0.003 0.959±0.005 0.964±0.002

0.387±0.018 0.769±0.021 0.771±0.005 0.874±0.013 0.740±0.017 0.801±0.007 0.761±0.016 0.871±0.009 0.823±0.009 0.889±0.006

P@10

0.492±0.025 0.606±0.017 0.487±0.063 0.707±0.039 0.628±0.021 0.655±0.024 0.632±0.018 0.724±0.014 0.719±0.012 0.800±0.008

0.740±0.048 0.994±0.002 0.998±0.001 0.997±0.003 0.985±0.007 0.996±0.002 0.991±0.002 0.998±0.002 0.996±0.002 0.999±0.001

0.922±0.006 0.950±0.008 TO 0.889±0.019 0.928±0.013 0.884±0.016 0.914±0.014 0.957±0.004 0.968±0.003 0.969±0.001

0.471±0.011 0.796±0.017 0.792±0.006 0.896±0.007 0.792±0.011 0.835±0.003 0.794±0.016 0.895±0.005 0.854±0.008 0.904±0.004

P@20

Table 14 MCS prediction on the benchmark datasets, all metrics. Mean ± standard deviation over ten seeds. MAE: mean absolute error, RAE: relative absolute error, TO: timeout. Best result in bold, second best underlined, and third best in italic.

not extend the baselines to these datasets and M values. Table 15 extends Table 4, without the runs that exceed the memory limit. Values above 1,000 are shown as >1,000. Table 16 gives the results of FiLSim on all ten datasets and M values, where values above 10,000 are shown as >10,000. Table 15 confirms the results of Table 4 with all metrics and their standard deviations. FiLSim achieves the best ranking metrics on all four datasets and the lowest RAE on all datasets except Cora and PubMed, where G2R has a slightly lower RAE but lower ranking metrics. The results of FiLSim are also stable across seeds, while several baselines vary strongly between seeds or predict a constant value in all seeds (shown as - for ρ and τ ). On Cora, GMN, GREED, and GraSP also achieve rank correlations above 0.9, but among the baselines, only G2R does so on more than one dataset, and it also fails on ogbn-arxiv. Table 16 shows how the results of FiLSim change with the collection size M . From M = 50 to M = 200, the rank correlation improves on most datasets, likely because the number of training pairs grows with the square of M . At M = 1000, ρ remains above 0.95 on all seven datasets derived from the smaller graphs, while P@k decreases, which is expected since the reference set grows with M (Appendix F). On the three largest datasets, the results at M = 1000 are clearly lower. Here, the fixed training budget of 6 hours is not sufficient. At M = 1000, validation alone takes about 45% of the training time on these datasets (Table 17). These results therefore likely reflect the training budget and the configuration selected at M = 200, which is not tuned for M = 1000, rather than a limit of the model.

H.3

Training Cost

Table 17 reports the training cost of FiLSim for every dataset. It includes the wallclock time until the best validation step is reached, the total training time, the time per training step, the share of training time spent on validation, and the peak GPU memory. Total times can exceed the 6-hour limit by about one minute because the last validation run is completed after the limit is reached.

H.4

Case Studies

Figures 6 and 7 show example queries from the AIDS700nef and PTC test sets for GED and MCS. In each example, the top row shows the reference graphs ranked by the ground-truth value, and the bottom row shows the reference graphs ranked by the prediction of FiLSim. The main differences from the ground truth lie within the groups of tied graphs, since several reference graphs share the same GED or MCS value, and FiLSim orders them by small differences in its continuous predictions.

37

38

Model SimGNN GMN GEN EGSC ERIC GREED GraSP G2R GEDGNN GEDIOT FiLSim SimGNN GMN EGSC ERIC GREED G2R FiLSim SimGNN GMN EGSC ERIC GREED GraSP G2R GEDIOT FiLSim GREED G2R FiLSim

Dataset Cora

PubMed

Amazon C.

ogbn-arxiv

>1,000 >1,000 >1,000

>1,000 >1,000 >1,000 >1,000 >1,000 >1,000 >1,000 >1,000 975.351±120.121

>1,000 677.724±38.684 >1,000 >1,000 >1,000 212.715±26.104 222.412±13.464

0.187±0.000 0.212±0.019 0.831±0.010

-0.165±0.134 0.697±0.147 -0.242±0.000 -0.150±0.163 0.189±0.000 0.908±0.027 0.179±0.159 0.979±0.002 0.252±0.000 0.289±0.030 0.956±0.006

34.948±29.231 0.715±0.109 1.609±1.003 1.070±0.058 >1,000 2.768±0.000 0.380±0.038 2.763±0.004 0.241±0.030 >1,000 0.958±0.004 0.342±0.017

-0.114±0.091 0.538±0.110 -0.167±0.000 -0.104±0.111 0.151±0.000 0.762±0.034 0.129±0.125 0.895±0.004

-0.271±– 0.755±0.048 -0.270±0.001 0.181±0.103 0.984±0.003 0.986±0.003

88.598±148.968 0.564±0.032 2.591±0.000 1.010±0.001 1.089±0.192 0.177±0.022 0.185±0.011

-0.188±– 0.582±0.043 -0.187±0.001 0.105±0.081 0.908±0.008 0.914±0.008

0.822±0.001 0.144±0.251 0.023±0.076 0.914±0.010 0.835±0.042 0.925±0.012 0.112±0.001 0.128±0.000 0.939±0.001

0.950±0.001 0.195±0.360 0.033±0.115 0.987±0.003 0.955±0.020 0.989±0.003 0.162±0.001 0.187±0.000 0.991±0.000

τ -

ρ -

RAE 2.734±0.000 0.309±0.005 1.058±0.256 2.734±0.000 0.992±0.003 0.224±0.013 0.301±0.048 0.188±0.013 2.734±0.000 2.692±0.004 0.190±0.008

MAE 377.855±0.000 42.653±0.628 146.256±35.369 377.855±0.000 137.089±0.403 31.019±1.861 41.610±6.636 25.978±1.829 377.855±0.000 372.094±0.500 26.257±1.093

0.173±0.002 0.183±0.024 0.713±0.015

0.077±0.043 0.502±0.075 0.063±0.019 0.056±0.004 0.181±0.001 0.085±0.000 0.652±0.065 0.150±0.043 0.852±0.010

0.061±0.042 0.562±0.054 0.085±0.000 0.013±0.000 0.298±0.149 0.833±0.020 0.880±0.011

0.045±0.000 0.723±0.026 0.077±0.030 0.045±0.000 0.078±0.051 0.844±0.039 0.711±0.046 0.866±0.017 0.176±0.004 0.187±0.001 0.913±0.012

P@10

0.238±0.001 0.240±0.006 0.778±0.008

0.107±0.062 0.568±0.051 0.090±0.032 0.091±0.034 0.264±0.000 0.128±0.000 0.752±0.028 0.175±0.005 0.893±0.006

0.107±0.038 0.613±0.030 0.129±0.000 0.062±0.000 0.328±0.118 0.892±0.017 0.908±0.014

0.123±0.000 0.800±0.009 0.147±0.063 0.123±0.000 0.125±0.045 0.892±0.017 0.823±0.032 0.921±0.012 0.257±0.001 0.268±0.001 0.940±0.003

P@20

Table 15 GED prediction on the four large datasets, all metrics. Mean ± standard deviation over three seeds. MAE: mean absolute error, RAE: relative absolute error. Best result in bold, second best underlined, and third best in italic.

39

M 50 200 1000 50 200 1000 50 200 1000 50 200 1000 50 200 1000 50 200 1000 50 200 1000 50 200 1000 50 200 1000 50 200 1000

Dataset Cora

CiteSeer

PubMed

Wiki

BlogCatalog

Flickr

Amazon C.

ogbn-arxiv

com-DBLP

com-Amazon

RAE 0.238±0.021 0.190±0.008 0.168±0.002 0.172±0.006 0.202±0.017 0.187±0.040 0.367±0.041 0.185±0.011 0.225±0.031 0.290±0.004 0.232±0.011 0.229±0.012 0.414±0.016 0.205±0.023 0.256±0.006 0.288±0.027 0.248±0.015 0.236±0.009 0.372±0.008 0.241±0.030 0.291±0.007 0.352±0.014 0.342±0.017 0.664±0.017 0.325±0.007 0.355±0.010 0.638±0.012 0.326±0.007 0.313±0.010 0.576±0.022

MAE 19.450±1.685 26.257±1.093 22.124±0.270 15.603±0.524 26.887±2.199 27.025±5.811 258.053±28.756 222.412±13.464 258.404±35.399 40.362±0.601 45.966±2.247 52.555±2.817 905.177±35.666 597.536±66.618 735.942±17.629 631.294±58.721 732.234±44.384 875.688±32.976 684.999±13.863 975.351±120.121 1213.036±30.118 4544.548±180.218 6556.686±316.644 >10,000 4221.987±90.587 6579.477±185.073 >10,000 4317.737±93.764 6480.177±213.594 >10,000

0.963±0.004 0.957±0.003 0.793±0.017

0.922±0.002 0.925±0.011 0.711±0.012

0.896±0.013 0.956±0.006 0.737±0.023

0.932±0.016 0.979±0.002 0.957±0.000

0.961±0.010 0.977±0.008 0.974±0.001

0.918±0.015 0.983±0.001 0.971±0.002

0.952±0.002 0.986±0.002 0.986±0.001

0.981±0.000 0.986±0.003 0.973±0.008

0.972±0.004 0.986±0.004 0.982±0.009

0.976±0.008 0.991±0.000 0.989±0.000

ρ

0.865±0.007 0.834±0.008 0.610±0.017

0.799±0.002 0.793±0.013 0.534±0.011

0.795±0.009 0.831±0.010 0.555±0.020

0.824±0.014 0.895±0.004 0.827±0.001

0.874±0.019 0.891±0.016 0.869±0.001

0.802±0.018 0.911±0.005 0.863±0.004

0.862±0.002 0.914±0.007 0.903±0.003

0.912±0.001 0.914±0.008 0.862±0.022

0.904±0.004 0.922±0.016 0.896±0.033

0.911±0.017 0.939±0.001 0.917±0.001

τ

0.920±0.020 0.744±0.020 0.625±0.033

0.893±0.021 0.730±0.015 0.469±0.015

0.877±0.015 0.713±0.015 0.551±0.013

0.843±0.015 0.852±0.010 0.723±0.008

0.877±0.023 0.843±0.016 0.729±0.013

0.830±0.010 0.871±0.016 0.726±0.012

0.863±0.021 0.890±0.010 0.865±0.004

0.913±0.006 0.880±0.011 0.524±0.053

0.947±0.006 0.911±0.012 0.863±0.013

0.930±0.026 0.913±0.012 0.867±0.002

P@10

0.922±0.010 0.805±0.007 0.588±0.037

0.892±0.003 0.757±0.005 0.434±0.007

0.897±0.003 0.778±0.008 0.510±0.008

0.920±0.013 0.893±0.006 0.757±0.008

0.940±0.005 0.887±0.018 0.782±0.007

0.913±0.010 0.891±0.015 0.778±0.010

0.948±0.003 0.897±0.009 0.880±0.002

0.970±0.000 0.908±0.014 0.624±0.048

0.938±0.008 0.937±0.012 0.879±0.018

0.948±0.008 0.940±0.003 0.891±0.002

P@20

Table 16 FiLSim on all large-scale datasets and collection sizes M . Mean ± standard deviation over three seeds. RAE: relative absolute error. P@k is not comparable across M , since the number of reference graphs grows with M .

Ranking by ground-truth GED Rank 1 1

Rank 2 2

Rank 3 2

1.0

1.7

1.9

Rank 1 8

Rank 2 8

Rank 3 8

7.7

7.7

7.5

Rank 4 2

Rank 5 3

Rank 10 3

Rank 559 17

Rank 560 18

3.1

16.4

16.9

Rank 10 6

Rank 559 0

Rank 560 0

6.7

0.0

0.0

Query graph

Ranking by prediction 1.9

2.6

Ranking by ground-truth MCS Rank 4 8

Rank 5 8

Query graph

Ranking by prediction 7.4

7.4

Fig. 6 Example queries from the AIDS700nef test set, GED (top) and MCS (bottom).

40

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. Dataset

Task/M

to best

total

ms/step

Val. (%)

Peak GPU

AIDS700nef

GED MCS

6.3 5.8

9.5 9.2

18.0 19.3

5.0 4.7

0.18 0.21

IMDBMulti

GED MCS

16.0 12.6

22.3 18.0

35.4 30.4

6.4 7.1

0.29 0.27

LINUX

GED MCS

10.0 15.6

15.6 21.8

31.0 35.3

4.4 3.8

0.15 0.19

PTC

GED MCS

4.2 5.2

7.4 9.5

18.5 24.6

2.3 1.8

0.41 0.64

Cora

50 200 1000

13.7 84.1 70.2

55.3 120.3 109.5

167.8 218.7 231.1

0.2 0.5 2.4

6.08 8.72 8.72

CiteSeer

50 200 1000

27.9 40.2 36.2

58.9 69.2 69.0

175.5 174.0 189.8

0.2 0.6 2.7

8.25 9.54 9.54

PubMed

50 200 1000

79.3 121.6 201.9

106.4 153.5 238.5

169.9 185.7 191.1

0.7 2.7 11.9

8.31 8.27 8.30

Wiki

50 200 1000

10.9 49.8 109.7

50.9 82.0 148.9

154.2 196.0 230.6

0.1 0.4 1.9

4.81 7.74 7.72

BlogCatalog

50 200 1000

14.3 87.9 301.6

122.4 169.4 360.1

371.0 502.3 560.0

0.2 0.7 3.3

10.85 10.86 10.88

Flickr

50 200 1000

33.6 226.5 351.4

187.8 318.4 360.1

569.2 564.4 550.6

0.3 1.0 5.0

10.84 10.85 10.84

Amazon C.

50 200 1000

101.7 105.9 246.1

156.7 165.4 310.6

328.2 348.2 353.5

0.5 1.8 8.5

8.88 8.87 8.87

ogbn-arxiv

50 200 1000

75.9 267.6 359.9

110.0 305.5 360.7

195.9 249.3 194.9

3.9 11.3 45.2

10.46 10.50 10.51

com-DBLP

50 200 1000

163.3 350.4 356.0

215.0 360.2 361.0

298.3 298.4 300.9

3.9 14.0 45.1

19.70 19.79 19.78

com-Amazon

50 200 1000

141.3 330.3 344.8

188.3 360.2 361.0

272.6 272.0 272.9

4.1 14.4 46.0

19.90 19.90 19.93

41

Ranking by ground-truth GED Rank 1 1

Rank 2 2

Rank 3 2

0.7

1.8

2.1

Rank 1 22

Rank 2 21

Rank 3 21

21.9

21.0

21.0

Rank 4 3

Rank 5 3

Rank 10 6

Rank 274 204

Rank 275 207

7.2

202.1

212.0

Rank 10 14

Rank 274 0

Rank 275 0

14.7

0.3

-0.1

Query graph

Ranking by prediction 3.5

3.5

Ranking by ground-truth MCS Rank 4 21

Rank 5 19

Query graph

Ranking by prediction 21.0

20.8

Fig. 7 Example queries from the PTC test set, GED (top) and MCS (bottom).

42