Gelato: Graph Edit Distance via Autoregressive Neural Combinatorial Optimization
Authors: Paolo Pellizzoni
Till Hendrik Schulz
Karsten Borgwardt
Venue: ICLR 2026 Poster (2026)
Keywords: graph edit distance
neural combinatorial optimization
graph matching
graph neural networks
Primary area: learning on graphs and other geometries & topologies

Abstract: The graph edit distance (GED) is a widely used graph dissimilarity measure that quantifies the minimum cost of the edit operations required to transform one graph into another. Computing it, however, involves solving the associated NP-hard graph matching problem. Indeed, exact solvers already struggle to handle graphs with more than 20 nodes and classical heuristics frequently produce suboptimal solutions. This motivates the development of machine-learning methods that exploit recurring patterns in problem instances to produce high-quality approximate solutions. In this work, we introduce Gelato, a graph neural network model that constructs GED solutions incrementally by predicting a pair of nodes to be matched at each step. By conditioning each prediction autoregressively on the previous choices, it is able to capture complex structural dependencies. Empirically, Gelato achieves state-of-the-art results, even when generalizing to graphs larger than the ones seen during training, and runs orders of magnitude faster than competing ML-based methods. Moreover, it remains effective even under limited or noisy supervision, alleviating the demand for costly ground-truth generation.

Published as a conference paper at ICLR 2026
GELATO: GRAPH EDIT DISTANCE VIA AUTOREGRES- SIVE NEURAL COMBINATORIAL OPTIMIZATION
Paolo Pellizzoni; Till Hendrik Schulz, Karsten Borgwardt Max Planck Institute of Biochemistry, Martinsried, Germany (pel lizioizon,, tschulz, borgwardt, (ttee)eeiicccoioeeeeece
ABSTRACT
The graph edit distance (GED) is a widely used graph dissimilarity measure that quantifies the minimum cost of the edit operations required to transform one graph into another. Computing it, however, involves solving the associated NP-hard graph matching problem. Indeed, exact solvers already struggle to handle graphs with more than 20 nodes and classical heuristics frequently produce suboptimal solutions. This motivates the development of machine learning methods that ex- ploit recurring patterns problem instances to produce high-quality approximate solutions. In this work, we introduce GELATO, graph neural network model that constructs GED solutions incrementally by predicting a pair of nodes to be matched at each step. By conditioning each prediction autoregressivvly on the previous choices, is able to capture complex structural dependencies. Empiri- cally, GELATO achieves state-of-the-art results, larger than the ones seen during training, and runs orders of magnitude faster than competing ML-based methods. Moreover, it remains effective even under limited or noisy supervision, alleviating the demand for costly ground-truth generation.
when generalizing to graphs
INTRODUCTION
Graphs are a common representation for structured data, with applications in domains such as chem- istry. biology, social networks, and computer vision (Wu et al. 2021). A fundamental challenge in graph analysis is measuring the similarity between two graphs. Perhaps the most natural definition of such (dis d is the graph edit distance (GED), which quantifies the minimum cumulative cost of transforming one graph into another through a sequence of edit operations, including node and edge insertions, deletions, and substitutions (Bunke & Riesen 2009; Blumenthal & Gamper) 2017). In practice, GED computations are commonly formulated as a graph matching problem, which provides finite and algorithmically tractable representation of edit paths.
Despite its conceptual appeal, computing the GED is a notoriously NP-hard problem (Bougleux et al., 2017). with exact solvers, often based either A search (Riesen et al., 2007 or integer linear programming (Lerouge et al.) (017)) struggling to solve instances with more than 20 nodes. Classical heuristies have been proposed to mitigate this challenge, but often trade their computa- tional efficiency with unsatisfactory solution quality (Carletti et al., 2015 Blumenthal et al. 2020).
This difficulty has sparked growing interest in machine learning (ML) approaches to approximate the GED. While earlier works (Bai et al.] 2019 Ranjan et al.) (022) focused on regressing the sealar value for the GED, these approaches do not return the edit path or the matching that would yield the predicted distance value, thus lacking interpretability. Moreover, such predicted values might not be integral upper bounds the GED, and could therefore not be attained by any matching.
More recent work has instead focused on the combinatorial nature of the problem, seeking to find good feasible solutions (i.e., edit paths or matchings) the problem via ML models, thus providing interpretable matchings, and, more importantly, guaranteeing that the provided distances are upper bounds to the true distance. Some models like GENNA * (Wang et al.) (2021) and MATA * (Liu al.) 2023b) use ML to guide the A search, but show limited scalability, hindering their applicability. Other models like GEDGNN (Piao et al. 2023) and GEDIIOT (Cheng et al., 2025) take the approach
"Equal contribution.

---

Published as a conference paper at ICLR 2026
GELATO
GELATO
select next pair (u
select next pair (ug.0,)
Conceptual visualization GELATO. Graph matchings are generated in a step-by-step manner. In each step, GELATO is fed autoregressively the previous partial matching, and it predicts the next source-target node pair to be matched, until every source node has been mapped.
Figure I:
of transforming the graph matching problem into some variant of linear assignment problem, which is polynomially solvable, by learning the assignment costs. This approach is used also in several classical heuristics (Blumenthal al.] 2020). However, since it computes all assignment costs independently from each other. it might miss the interdependencies between node matches.
Contributions In this work, we formulate the solution of the GED problem a sequential decision-making process, where solution (i.e., node matching) is constructed incrementally in step-by-step manner, as visualized in Figure In particular, each intermediate matching defines a subproblem, and our model proceeds in autoregresiive fashion: it predicts the next pair of nodes to be matched conditioned on the set of matches predicted so far. This autoregressive process ensures that the decision cach stage leverages both the structural information of the graphs and the history of previous matches, allowing the model to make more accurate predictions. This novel recursive formulation naturally connects GED to the broader field of neural combinatorial optimization (Ben- gio et al. 2021 Cappart et al. 2023), where learning to exploit structural regularities across problem instances is key efficiency and generalization (Drakulic et al. 2023
To this end, we introduce GELATO (Graph Edit distance Learning via Autoregressive neural combinaTorial Optimization), model that autoregressively predicts node matches using a graph neural network, progressively constructing an approximate solution to the GED instance at hand.
Empirically, we show that GELATO achieves state-of-the-ard solution quality on both established and newly introduced benchmarks, and performs well on graphs larger than those seen during training. Moreover, GELATO substantially faster, often by up two orders of magnitude, than compet- ing ML-based approaches, and remains effective even when trained with limited or noisy supervi- sion. This robustness directly addresses one of the central bottlenecks in GED research, namely the scarcity of ground-truth matchings, whose exact computation is NP-hard.
1.1 ADDITIONAL RELATED WORK
The task of regressing the GED value has been pioneered by SIMGNN (Bai et al. 2019) and later tackled by several models, including GMN (Li al. 2019), H2MN (Zhang al.) 2021), 1), ERIC
(Zhuo & Tan 2022), GREED (Ranjan et al. 2022), GRAPHEDX Jain et al. 20024a). and GRAPHSIM (Bai et al. 2020). Beyond the models mentioned in the introduction, several works have tackled the harder yet more informative task of producing GED solutions, such as GOTSIM (Doan et al. 202T
and NOAH (Yang Zou, 2021). Recently Verma al. (2025) introduced GRAIL, an LLM based
model that produces code for GED heuristics.
The deep graph matching (Fey al., 2020) field, albeit related to the GED one, focuses on matching
fewer and larger graphs, often coming from computer vision (Gao et al. (202 Liu et al. (2025). and usually maximizing the affinity of matched nodes and edges (Yu et al. 2019) rather than minimizing cumulative costs. In this setting, Liu al. (2023a) introduced a model that predicts node matches sequentially, and is trained with reinforcement learning rather than supervised learning.
In general, neural combinatorial optimization focuses on designing beachine-eearingg.e based heuris- ties for NP-hard problems, with examples including TSP (Vinyals et al.) 2013; Bello et al. 2016
Khalil et al. 2017), CVRP (Nazari et al.) 2018) and the knapsack problem (Drakulic et al.
2023
Approaches span both supervised learning (Fu et al. (20T)) and reinforcement learning (Kool et al. 2019) Zhhang et al. 2024). Further related work is discussed in Appendix B
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
A graph is tuple G = (Vo, EG, la), with Va a finite set of nodes, Eg S {fu, u u u E Va) set of undirected edges, and lo VG U Egg + E a function assigning nodes and edges to label of finite alphabet Σ. The neighborhood of a node is given by NV() = {w E Va {u,w} E Ec}.
Graph Edit Distance The graph edit distance assesses the similarity between two graphs. In par- ticular, it is computed as the minimum cumulative cost of the edit operations required to transform one graph into another, with edit operations being node and edge insertion, deletion, and substitu- tion, each with associated costs. If the costs are a metric, GED is metric (Justice & Hero 2006).
In fact, GED can be equivalently defined as a graph matching problem or as a quadratic assignment problem, which is more suitable for being solved algorithnically (Bougleux et al.] 2017). We define the set of valid matchings M(1,, G2) = {n C Vi x V/2 V(u, v') E /4 u = u' > v'), ", i.c set of node pairs such that no source node and target node is repeated. Given a valid matching μ E MMG1,, G2). we call μ = {(u,E): : u E V1, Bu, v) E ju} the set of source node deletions and u² = {{E, v): U V2, 3(u, v) E [r] the set of target node deletions. We denote j == u μr U ptt We call a node pair (u, v) E fa a match, to distinguish it from a matching.
Definition 1 (Graph Edit Distance (Bougleux al. (017)). Let G1 and G2 be graphs. The graph edit distance (GED) between G1 and G2 is defined by GED(G1, G2) = min c(p), with
<(u)
Σ
Ga(G1, U2) +
Σ
ce(Gi, Gz, (u, w). (1,
(u,v)p
(u,r),(,,)EE
where is the cost function for node edit operations and ce for edge edit operations (see Def. 3).
Graph neural networks Message passing graph neural networks (GNNs), for a given graph G, produce for each node E Vg, each layer E = 1....,f, L. the embeddings h E Rd by taking into account messages coming from its neighbors Nu)). More formally, the embedding of node u is updated as h. = fupd (h fagg (Khe- :u E <N(x)B)) where fags and f fupd are the aggregate and the update operations, respectively. The first layer of the GNN is fed with the initial node embeddings n. e.g., one-hot encodings of the node labels.
3 GRAPH EDIT DISTANCE AS A DECISION PROCESS
In this section, we highlight how the graph edit distance problem can be naturally cast as a sequen- tial decision process (Bellman| 1954), and how this perspective can be exploited in the design of machine learning models. This connects the GED problem with a broader line of work on neural combinatorial optimization, where problems are framed as sequential or Markov decision processes in order to leverage policy-based models and dynamic search strategies (Drakulic et al. 2023).
In particular, sequential decision process in the context of combinatorial optimization is discrete and deterministic framework for solving problems where a solution is constructed step by step. At each step, the system is in state S representing partial solution, and the algorithm selects an action a E A(s) from the feasible set of actions. The action maps the current state to a successor state via a transition function (s, + s'. The objective to construct sequence of actions that leads from an initial state to a terminal state while minimizing the cost of the terminal state. This formulation mirrors the principles of classical dynamic programming. where optimal solutions are obtained by decomposing the problem into subproblems and reasoning recursively over states.
Intuitively, the GED problem solution can be formulated as sequential decision process by pro- gressively building the matching between the source and target graph. At each step, one selects a node of the source graph and assigns it to a node of the target graph, while ensuring consistency with the partial matching constructed so far. To define this formally, we first introduce generalization of the GED problem where some matches are already fixed.
Definition 2 (Graph edit distance with fixed matches). Ler G1, G2 be graphs. Let μ E M(G G2) be matching between G and G2. Then the graph edit distance with fixed matches (GEDFM) problem on (G,, G2. μ)) asks to find μ¹" arg min pCu c(v). We denote the value of the optimal solution as GEDFM (G, c(p").
3

---

Published as a conference paper at ICLR 2026
cool
000
18
(a)
(b)
(c)
Figure 2: (a) A pair of graphs and possible surrogate cost matrix for node pairs. Entries with the same color must have the same value, as their node pairs are indistinguishable. (b) The two node matchings based on the matrix in panel (a) have the same linear-assignmett cost, but the one the right is suboptimal due to inconsistent matches, such as (u,, and (us, 0z). This happens because the linear assignment cannot capture pairwise dependencies between matches. (c) Once the match (#1, 01) is fixed and interpreted as an auxiliary edge, pairs (us, 03) and (us, 0i)) are not indistinguishable anymore. Thus, autoregressive models can make more informed choice.
To formulate the GED problem as a decision process, we define the state space as the set of GEDFM instances. In particular, for the GED problem input graphs G1, G2, we define the initial state as the GEDFM instance (G1, G2, 0). Note that each state = (G1, μ). even if leaves some nodes unmatched, represents valid solution the matching problem between G₁ and G2. Indeed, the unmatched nodes belong to the set of source and target deletions jtt and μ Therefore, in our search space, any such state also valid terminal state. Then, state s (G1, G2. p), the set of actions is any pair of unmatched source and target nodes, i.e. A(G,, G2, = {(u, v) E Vi x V2 7(w, 2) ja with w or = w). This defines the recursion
min GEDFM(G1, G2, pt) min {c(w) AGI GEDEM(G1, G2, (u,,)((
This recursive formulation mirrors the structure exploited in classical search-based approaches such as A+, A straightforward constructive heuristic would be to select, at each state, a single action guided by surrogate scoring function. In our method, we replace hand-designed surrogates with learned policy, by predicting the next action directly from the current state using GNN. This casts GED as a sequential prediction problem, where the node matching is built autoregressively and each decision is conditioned on previous ones, which allows to capture dependencies between matches.
based heuristic algorithms, which include, with some slight variations, both classical heuristics such as NODE and BRANCH (Blumen- thal et al.) 2020), but also several ML-based ones such as GEDGNN (Piao et al. (023)) and GOTSIM (Doan et al. 202T). These algorithms first compute surrogate cost associated with matching each node u E V1 to u E V2, obtaining a surrogate cost matrix C E | Once this matrix is obtained, the matching is computed by solving the linear assignment problem on C. Since C' is not updated as the matching progresses, these methods cannot adapt decisions to previous choices and thus fail to capture interdependencies between assignments. Indeed, for certain graph pairs, such as the ones represented in Figure 2, no function based on node orbits can yield matrix C that guarantees the optimal GED solution, showing that such models are not expressive enough.
A class of non-sequential methods is the one of
If, however, we use a sequential method and the surrogate cost matrix is updated after each action, it information from earlier matches and capture these dependencies. In fact, Lemma (discussed in Appendix [D) shows that there exists function such that greedily selecting pair at each step recovers the optimal solution, although computing this function in general is intractable. However, under a restricted distribution of instances (e.g., small molecules, which have recurring substructures (Pellizzoni et al. (025)), we can learn such function with a ML model. This insight is the core of our model's architecture.
3.1 AN EFFICIENT STATE-SPACE FOR GED WITH PARTIAL MATCHES
Having formalized the GED problem as a sequential decision process, we address the problem of exploring its state space efficiently. The core principle in the dynamic programming paradigm is to exploit overlapping subproblems to reduce the search space. Crucially, each subproblem must be represented in an efficient and concise way obtain reduction of the search space.
4

---

Published as a conference paper at ICLR 2026
reduxe
reduce
(n) instance
matching
Figure 4: Solid arrows show optimal p². While (ug, 03) $ j²,, it is automorphic to (M2, 02) E p², and hence included in M (24 U2) not auto- morphic to any pair in je" and is thus in M
Two different GEDFM instances are mapped via reduce to the same, smaller sub- problem, thus reducing the search space.
Figure 3:
In our case, for each partial solution for the GED problem (i.e., a GEDFM instance), we construct possibly smaller GEDFM instance that corresponds to the same subproblem. Since multiple partial solutions will be mapped to the same subproblem, we effectively reduce the size of the search space.
Intuitively, we reduce the graphs in a given instance by removing all nodes that cannot influence the subsequent matches. Clearly, if a node has not been matched yet, it cannot be removed. Similarly, a matched node u has an unmatched neighbor v, then u cannot be removed, as it may influence the choice of the match for However, if node and all of its neighbors are matched, it can no longer directly influence any other match, and therefore, can be removed. In particular, consider GEDFM instance (G1, G2, (4) and let μ reduee C μ be all pairs (u, v) for which all neighbors of or all neighbors of are matched. Formally, rroduce = {u, v) E fA Vw E (N,),,3(u 2) Vz E (v),, E(w, z) E n}. Remove from G2 all nodes with (u, v) E j.eeuuee (and their incident edges), and analogously from G2 all nodes with (u, v) E pedduce Let the resulting graphs be G and Gz and let μ² p Then, we denote the constructed instance (G). G2yy H²) reduce G2.
The following result shows that the optimal solutions for the original and reduced instances are equivalent, meaning that if we restrict an optimal matching μx" of an instance to the nodes that are not deleted in the reduction, it remains an optimal matching for the reduced instance.
Theorem 1. Let (G1, G2. μ)) be GEDFM instance and p* 2 an optimal matching for it. Then, the instance (G', G2 p²) = reduce(G, G2: p)) has an optimal matching μ² n Ví)..
Figure depicts distinct GEDFM instances that are equivalent to the same subproblem, which is smaller GEDFM instance. Here, the nodes U1, Ug 11, v2 are deleted from the graphs in the instance on the left, which yields the reduced instance the center. Similarly, the deletion of wi, W2. 21, and from the instance on the right yields (possibly after renaming the nodes) the reduced instance the center, even though the original instances were different. In fact, this reduction procedure generally leads to considerably smaller state-space compared to naively rep- resenting GEDFM instances. Feeding the reduced instances to our ML model then enables it to learn from more compact instance space, possibly making the learning process easier, as formalized in Section 3).
(Drakulic et al. 2023
4 GELATO: AN AUTOREGRESSIVE MODEL FOR GED PREDICTION
In this section, we describe the architecture of our model, GELATO (Graph Edit distance Learning via Autoregressive neural combinaTTorial Optimization). In a nutshell, the model GNN that takes as input graph representation for GEDFM instance, and outputs prediction for an action to taken, i.c. a pair of yet-unmatched nodes to be matched. This is trained as link prediction task, with ground-truth given by the optimal graph matchings the training instances. Then, at inference time, a sequence of actions is predicted autoregressively until the matching is completed. This matching is the output of the model. The next sections detail each of the components.
4.1 FROM GED SUBPROBLEMS TO GRAPHS
In order to process GEDFM instances with GNN model, encode them graphs. In particular, let (G1, G2, ()) be a GEDFM instance. Let = (Vn, Ei,, S (r) be graph obtained as the disjoint union of the two graphs, with nodes of G labeled with additional label src, nodes of G2 labeled
5

---

Published as a conference paper at ICLR 2026
with label trg. Moreover, it contains additional edges (u, 2) Vi V22 for each match (u, μ. which take part in the message passing. Practical implementation details are reported in Section F2
In fact, can show (Lemma 2) that the map (G1, G2, (i) H is injective. Therefore, graph- encoded instance discards no information, and is sufficient to make accurate predictions. In practice, encode the and trg labels as 2-dimensional one-hot encodings appended to node features. Moreover, we label edge-encodes matches with a label match, encoded as a binary flag appended the edge attribute vectors, to facilitate the decoding process. Finally, given a GEDFM instance, we remark that we first transform it into its reduced subproblem, as described in Section 3.1 and then into its graph-encoded representation before feeding it to the oction-predictes model.
4.2 MODEL ARCHITECTURE
The action predictor is implemented as a GNN model for link prediction tasks. First, node and edge labels are embedded via a linear layer to vectors ha and eu,v in a d-dimensional space. We then use GINE message passing layers (Hu et al. 2020a), as they can take into account also edge features, and they are provably as expressive as I- WL (Xu et 2018). Moreover, we endow each layer with batch normalization (loffe & Szegedy 2015) and residual connections, as they have been shown to be beneficial to the predictive performance of GNN models (Luo et al. 2025). In particular, we have
1+1 hi ReL. (BatchNorm MLPP
Σ (EN
ReLUUN, + (eret++e.w)))))) en..l))) RRd.
Once the node-level representations are obtained after & layers, one can obtain a scalar representa- tion for pair of (source and target) nodes by concatenating them and feeding them to MLP as follows: Ou,e = MLP ( ( This can be interpreted as the logit of the likelihood the match (u, 2) to be chosen as the next action in the decision process.
4.3 TRAINING
The goal of the model is, given (graph- -ruphh-encoded GEDFM instance (G1, G2, p). to predict the next pair of nodes to match. To do so, the model is trained as link prediction task (Zhang Chen 2018), where each link is formed by pair of unmatched source and target nodes.
In particular, the model trained, for a training instance (G1, G2, ()) with ground-truth matching r", to give a high likelihood to any pair of nodes in the optimal matching that is not yet included in the current matching, i..., μr' \. We thus don't make the model learn a pre-specified order which valid action.
to perform actions: any matching that belongs to ju" \ j is regarded
Ground truth construction Given a set of graph pairs, we obtain the optimal matchings using an exact solver such as MIP-F2 (Lerouge al. 2017). Then, for each such pair (G1, G2), construct multiple training instances by sampling set U of source graph nodes, and letting the partial matching be μ {(u,r) v) n²= u E U}. Since the optimal solution for the instance (G1, G2, 11) is still μ², this allows us to generate several training instances for each graph pair while computing the optimal solution only once, which automatically yields a data-auugenting effect.
Dealing with automorphic matches An issue that might arise during training is that conflicts may occur two node pairs are indistinguishabl,, but only one is part of the optimal matching μ²", Since indistinguishable pairs must be assigned identical embeddings, this conflict provides contradictory supervision the model. For instance, consider the graphs of Figure where the optimal matching 4² is depicted by solid green arrows. While the node pair (u2, U3) is not in μ² and would thus naively be considered a negative edge, is indistinguishable from (u2, 02) E 1=" Formally, this indistinguishabilty is caused by automorphisms. See Appendix Appendix[[for>> formal definition. However, we can show (Lemma 3) that a pair of nodes (u, v) & μ²' automorphic to a pair (w, 2) E μ², denoted here by (u,
(w, 2). then there exists another optimal solution D² such that (u, v) v². Therefore (2, v) should be considered a positive link. Then, we take positive link set as M+ := (1* \ /1)/~,, i.e., each pair-automorphism class in the ground truth is added once, and the negative set as M := (A(G,, M)) \M 1 i.c. each auir-automorphism class that is not in the positive set is added once.

---

Published as a conference paper at ICLR 2026
4.4 INFERENCE
At inference, we pursue a sequential process as described in Section 3 Given two graphs G1 and G2, the process starts with GED instance (G1, G2, 0). At each step. likelihoods are computed via the GNN model for all unmatched node pairs (u, v), and the pair with the highest score is selected. Formally, at each step, given a graph-encoded instance (G1, G2. pt), we choose the next match to be arg (, G2.H) Ou,e. Then, we create a new instance (G1, G2, f U {(u, e)}). which is reduced via the map reduce. This instance then encoded as graph, and finally used as the input for the next step. Once all nodes of the smallest graph are matched, the process is completed.
While a greedy strategy as the one described above can give satisfactory results, is very sensitive to the choice of the first match. Indeed, while in later steps the model is informed by previous matches (e.g., on average, neighbors matched nodes are more likely to be matched), in the first step there is no matching information to exploit. Therefore, to explore the solution space more broadly, use a simple ensembling strategy that considers multiple starting pairs. More precisely, at the initial instance (G1. G2, 9). we select the top-A scoring node pairs (with respect to O,,v), and use each such seed to initialize a separate search branch. In fact, to avoid selecting redundant pairs, we select the top-k up automorphisms. Clearly, ke 1 reduces to the standard greedy strategy.
5 EXPERIMENTAL EVALUATION
In this section, we experimentally evaluate the predictive performance of GELATO on a set of novel benchmark datasets, which we provide publicly and in an easy-to-use format alongside our code at /ttps://qithul com/ wwon//orrwwrdtaao. LeaLLaablellaaa Gatoo
Datasets We consider the established SimGNN (Bai et al., 2019) datasets AIDS, LINUX and IMDB, restricted to graphs up to 16 nodes. Moreover, we generate three additional datasets, taking all graphs from the ZINC, molhiv and code2 datasets (Gömez-Bommarelll et al. 2018 Hu et al. 2020b). with up to 16, 16 and 22 nodes respectively. This includes datasets with no labels, only node labels, and both edge and node labels. We randomly split the graphs into training, validation, and test sets using 60:20:20 ratio. Following Jain et al. (2024b); Roy et al. (2025), who identified that the established GED benchmark datasets are polluted by isomorphic graphs, we ensure that no two graphs across different splits are isomorphic, to prevent data leakage. Moreover, for ZINC and molhiv we additionally create a second test set "larger" with graphs from 17 to 24 nodes, and for code2 from 23 to 30 nodes. For each split, we generate graph pairs by randomly sampling from the available graphs, and compute the ground-truth GEDs and corresponding matchings using M1P-F2 (Lerouge et al.) (017). All experiments uniform edit costs, and we report additional experiments with different edit costs in Appendix H Further details on datasets can be found in Appendix E
We emphasize that our datasets, constructed avoid data leakage and providing ground-truth solu- tions for larger graphs, offer a fairer evaluation benchmark for both this work and future research.
Evaluation metrics We evaluate performance using two metries: normalized mean average error (nMAE) and exact hit rate (EHR). The nMAE measures the average error relative to the true values,
defined as I/N N 16e-9.
max((1.))) where y/s denotes the true GED value and 9; the predicted value. For methods returning matchings, we have that 9. - y 2 and the metric measures the optimality gap. The EHR defines the fraction of predictions that exactly match the ground-truth GED value.
Baselines We evaluate a diverse set of baseline methods, including classical and learning- based approaches. Among the classical methods, we consider B BRANCH. REFINE (Blumenthal et al. 2020). and MIP-F2 (Lerouge et al., 2017) with a timelimit of 0.1s For learning- based approaches, we consider the best best-performing ones, including GEDGNN (Piao et al. 2023), GEDHOT (Cheng et al.) 2025). and MATA* * (L.iu et al.) 2023b), which produce (hard) matchings, as well as GREED (Rajjan al. 2022) and GRAPHEDX (Jain et al.] 2024a)), which do not. We re-train all (earning-basee approaches on our datasets using the default settings. Finally, we consider the recent GRAIL (Vermal et al. 2025) approach, which leverages large language models generate code for GED heuristics.
For GELATO, we fix the number of GNN layers to L = 5 and the embedding dimension to d = 128, which yields a good trade-off between representational power and memory requirements. See Section G for results with different byperparameters. We train the link prediction task using the cross-entropy loss with the Adam optimizer (Ir 10-3). We use up to 10 randomly selected pairs
7

---

Published as a conference paper at ICLR 2026
Method
AIDS
LINUX
IMD8-16
ZING-16
mothiv-16
code2-22
oMAF
EHR
aMAF
EHR
1MAF
FHR
IMAR
RHR
oMAR
EHR
aMAR
EHR
MrP-P2nu
63.2g1
0.3
25.3
73.
43.7se7
6.1g9
24.1
17.3
20.
41. 41.22
BRANCH
1.9
6244aa
51.
11.1az
101
1.0aas
62.8u.
79.9
7.7
REFINE
38.3.1
20.0
56.227
36.621
5.0
93.42
52 62
1.4as
28.321
6.26x7
182.
GREED
10.3nn
das
55.6.20
4.7ars
64.6.
M.7ax
24.7214
9.
23
28.9
K-lata
36 N6.7
GRAPHEDX
8.0bua
51.5isa
13.8.a4
81.4.4
17.7.sa
49.2-1a
7.7
35.3
9,9roa
21.
6.0
09.
MATA
3.7-24
89.8
0.4ea
18.
10.7-u>
14.1aa
15.5isa
5.1iaa
61.l
GEDGNN
21.1au
38. 7
6.7
85.8..
2.3us
95.
16. 06.
3.5ax
32.1asa
18
17.0ka
14.2
GEDHOT
6.8
06.8...
0.6-aa
98,2-s4
98.8.6.
27. 27.5
7.1eaa
22.5
9.9
9.0caa
64.8
GRAIL
2,7
82.1
0.0
100.0.aa
0.0
99.9
12.7
21.3
8.5raa
38.
5.8
60.4
GBLATO
0.1ga
99.3
0.
30.0ga
0.1gx
99.9gm
0.7go
91.3g1
0.
95.3k
0.6ba
95.7ga
Table I: Overall solution quality of methods in terms of nMAE (L) and EHR (1) in %.
of training graphs, subsampling from each 40 random sub-instances, as described in Section 4.3
Model selection is based on validation nMAE. We use ensembling with k = 32, unless noted. We report mean and standard deviation over five runs, each using 1000 random pairs of test graphs.
5.1
MAIN RESULTS
We start by evaluating the overall solution quality of our approach. Table [ demonstrates that GELATO consistently outperforms all baseline methods on both considered evaluation metrics, or matches the strongest baselines on datasets where results are close to optimal. The improvements are particularly substantial on AIDS, ZINC-16, molhiv-16, and ZINC-22, where GELATO achieves nMAE that is one order of magnitude lower than the second-best performing baseline. On LINUX and 16DB-16, the performance is already quite saturated, which limits the scope for further differ- entiation. Notably, even relatively simple baselines, such as BRANCH and REFINE, quite com- petitive on these two benchmarks. This can likely be attributed to the high number of isomorphic graphs in the test sets, as well as high degree of automorphisms, which increases the likelihood of many matchings being optimal. Since ZINC-16 and molhiv- 16 have edge labels, and most ML- based baselines do not explicitly use edge labels, we report additional results on datasets variants with no edge labels in 2 The results further confirm GELATO's 's superior performance.
Finally, we report in Table inffrrence times, in milliseconds per pair. We observe that the runtimes of the heuristics generated by GRAIL vary depending on the code selected for each dataset. Con- cerning the learning- based methods, MATA scales exponentially with graph size, while GEDGNN and GEDIIOT suffer from high computational demands due to their reliance on linear assignments and ensembling, often exceeding one second per pair. Compared to these learning-baat based methods, GELATO, due to its GPU-friendly implementation, achieves runtimes two orders of magnitude lower. For a more comprehensive comparison highlighting GELATO'S 's efficiency, we provide the inference runtimes on CPUs in Appendix H demonstrating that GPU runtimes up to 10 times faster than those on CPU. Additionally, we report the training runtimes of all learning- methods, showing that GELATO 's training is faster compared to other methods that generate matchings.
5.2 GENERALIZATION TO LARGER GRAPH SIZES
We now assess the generalizing capabilities of GELATO to larger graphs compared to the ones seen during training. This setting reflects the most critical use case for GED prediction models. For small graphs, exact or near-optimal solutions can be obtained using classical algorithms such as MIP-F2, while becomes computationally infeasible as graph size grows. Thus, the practical value of ML- based approaches lies in their ability to transfer knowledge from small training instances to larger instances, where exact solvers are no longer applicable.
Graphs from the "larger" test sets were grouped based on their node counts, with 500 pairs randomly sampled from each group. We report mean and standard deviations over five runs To put results into perspective, we also include groups from the (in-distribution) test sets. The results, illustrated in F show that while the performance of GELATO decreases with increasing graph sizes, the decline is gradual and does not accelerate compared to the in-distribution sizes. This suggests that the reduction in performance is likely due to the complexity of the problem (e.g. the number of feasible solutions) scaling with the graph size, rather than the model's ability to
8

---

Published as a conference paper at ICLR 2026
Method
ZING-16
molhiv-16
Method
AIDS
LINUX
IMDB-16
ZINC-16
mothic-16
code2-22
aMAE
EHR
aMAE
EHR
MIP-F2nan
51,6.c
4.30xx
03.2
10.7.a7
MIr-22ma
100
100.0gor
100.bbo
100.0ke>
100.0ga
100.0
BRANCH
127.3
1.0ua
11d.0.t
0.4.s
BRANCH
0.1pea
0.0
0.1en
0,1aea
Dilase
0.3
REFINE
63.3
1.0aaa
45.2
3.E
REFNEE
0.2
0.1oa
0.2
0.3cca
0.
2.9
GREED
9.3eaa
1:21
1.2
2..2
GREED
0.leaa
0.1an
0.1ena
0.
D.lana
0.
GRAPHEOX
0.5
45.3.c.
8,7-ua
40.3
GRAPHEoX
0.3re.
0.3-aa
0.3koa
0.3ica
0.3ua
0,3ica
MATA
19.3.ss
13.6.aa
19.5-ac
16.0
MATA
6.8raa
7.
174.0
24.2.44
37.5
6329.8 8
GEDGNN
d1.0..
6,7
GEDGNN
7.2.0ua
1383 2.
1252
2813.9
GEDHOT
22.0ax
12.9
18.5
21
GEDHOT
12
960 Sussa
2064 Jasks
165
$951 Bas
GRABL
8.3
39.6a1 v
6.5ass
52.621
GRAIL
8-4g
8.
23.4
44.1a
189
99 4i
GRLATO
0.7
92.3ko
0.5ces
95. BLos
GELATO
3.2a.
2.8c
3.60
4.2ac
4.
6.3
Table 2: Solution quality on edge- unlabeled graphs. Eval. metrics in %6
Table 3: Average inference runtime per graph pair (ms).
ZINC
molhiv
code2
50
60
50
GELATO
in
GEDOROT
40
40
40
GRAI
20-
20
20
MIP-F
15:16
17:15
21:22
15:16
17:18
21:22
19:20
23:22
23:34
Graph size
Grigh size
Grogh sine
Figure 5: Test solution quality across different graph sizes (EHR in %). Training was conducted on graph pairs up to size 16. 16, and 22. The dashed line separates in- from out-of-distribution data.
generalize. Only results for code2 show a slightly different behavior, as the performance on unseen graph sizes seems decline a faster pace, which might be due to distribution shift in the graphs.
Additionally, the results demonstrate that GELATO consistently outperforms all baselines across all graph sizes, showing its strong performance in both in-distribution and out-of of-distribution cases.
5.3 ABLATION STUDIES AND ROBUSTNEES TO LIMITED SUPERVISION
In the following, we isolate and assess the impact of key components and parameters of GELATO. Results are reported in Table 4 As a baseline for the ablation studies, we set k 1, reducing inference to the greedy strategy. As expected, this results a noticeable performance drop compared to GELATO with k- 32. highlighting the importance of broad search space coverage. However, even with = I, our approach still outperforms all baseline methods in several cases.
First, we ablate the role of sequential decision making by predicting the entire matching in one step, instead of generating it autoregressively. Specifically, given two graphs G1 and G2, and pairwise match log- ligeeiilisoods between vertices E V1 and V2, computed from Ou,e, compute the matching corresponding to the optimal linear assignment between Vi and Vz. The results (row "No sequential process") show a significant performance drop when this strategy is applied, clearly demonstrating that the autoregressive approach is critical to the performance of GELATO.
Second, we ablate the instance reduction discussed in Section 3.1 which shrinks the search space. In this ablation, we omit the reduction step and operate directly on the original, unreduced instances. The results (row "No instance reduction") show that the reduction has an overall positive impact on predictive performance, albeit to a lesser degree compared to the sequential decisions.
Third, we investigate the strategy for selecting positive and negative links in the presence of au- tomorphic matches. Recall from Section 4.3, that we choose as positive links the set (n* \ p)/~ and ensure that no pair automorphic to any element in μa" is contained in the negative link set to avoid contradictions in the training data. Instead, we now consider the naive strategy which for an instance (G,, G2, 14) selects the set μ \ as positive links and all others A(G,, G2, M) (n" as nega- tives. The results (see row "Automorphic matches") vary across different datasets, with performance deteriorating in some cases, but improving in others. One possible explanation for the observed im- provements is that the naive strategy effectively wwwn-weights all automorphic pairs and therefore postpones matching them, which may be beneficial on some datasets. In fact, using the two training strategies dataset-specific hyperparameter can yield even better solution quality.

---

Published as a conference paper at ICLR 2026
Method
LINUX
IMDB-16
ZING-16
molhiv-16
code2-22
nMAR
FHR
aMAR
FHR
aMAR
EHR
MMAR
FHR
1MAR
EHR
oMAR
FHR
GELATO (k=1)
6.4-aa
74.3
9.0
92.8
4.0bas
98.1
8.6
41.4.u
5.4
52.8
20.6.sa
65.3
No soqucutial process
61.0us
11.0iax
81.5
60.6..a
15.9
2.0kwa
2.5raa
38.8.La
25.0
No instance reduction
8.0
68.7
50.9
84.5asa
4.5e93
97.0ge
9.4ea7
38.2
5. 5.5em
51.5g2a
14.5gi
60.9
Automorphic matches
7.5
72.22
16.5
90.0g
0.1
40-4
8.7axs
41.2a
6.36m
00.3cr
9.5
70.l
Table 4: Ablation studies of key components of GELATO. Solution quality metrics reported in %.
ZINC-15
codo22 22
100
100
5388 (66)
80
95
95
80-
80
80-
60
70-
60
32
122
32 125
32 6% Embodking dimscrioo
125
5
32
Emiookiing Miseriion
Enssuble
Lages
Emsemble
Figure 6: Hyperparameter study on ZINC-16 and code2-22 with varying embedding dimension d, number of layers L. and ensembling size k. while keeping other parameters at default values 128, = 5 and k = 32. We report mean and standard deviation over five runs.
Moreover, Figure 6 shows, on the ZINC-16 and code2-22 dataset, how the solution quality varies depending on the embedding dimension d, the number of GNN layers L and the number of ensem- bles kt Results show that lowering the embedding dimension or the number of layers reduces model capacity. On the other hand, increasing them yields modest gains compared to Table I at higher memory cost. Larger ensembles consistently improve results, but increase runtime. Complete results on all datasets reported in Section G There, we also show that ablating residual connections and batch normalizations results in a slight decrease in solution quality.
Finally, in Table 5 we investigate the sensitivity of GELATO to limited noisy supervision. A limiting factor for training GED prediction models is the NP-hardness of computing the ground-truth matchings to be used supervision signal. Towards this end, we investigate how sensitive GELATO is to being trained on fewer graph pairs, as well as on instances with suboptimal matchings.
On the ZINC and code2 datasets, which are the ones whose ground- truth computation is the most com- putationally challenging, we train GELATO on only 10t and 10 graph pairs. Moreover, we also train it on 10a graph pairs, where the matchings are computed with MIP-F2 under strict timelimit Tmax of second and 0.1 seconds, and may thus be suboptimal. While the solu- tion quality degrades, expected, as the supervision signal worsens, observe that GELATO still achieves state-of-the performance under all weak supervision scenarios, even when training on only 10 pairs, whose generation takes at most 0.4 -ours (i.e., roughly 3 minutes 8 cores).
ZINC-16
code2-22
Data gen.
#MAE
EHR
Data gon.
iMAE
EHR
10k pairs
4.1
1.5res
83.1
1.9
2.0as.
90.6iea
10K pairs. Tiax 18
2.0
1.7.a.
81.6reo
1.2 h
1.6ua
93.33
10k pairs,
Timee 0.1s
0.3
3.75e1
62.6
0.3
1.8
87.3
pairs
5.5gn4
52.
0.2
4.3g
77.5
Table 5: Solution quality with limited supervision
CONCLUSIONS
In this paper we developed GELATO, a state-of-the-ee machine learning model for solving the graph edit distance problem, based on a novel autoregressive formulation. However, it could be further improved by designing better inference strategies (e.g., beam search) and hyperparameter search. Moreover, we believe that the field can benefit by focusing on the generalization to larger instances, which can be enabled by the datasets we provide here. Moreover, removing the need for supervision from optimal matchings, which are computationally expensive to compute, would be significant contribution. This could be achieved by using reinforcement learning (Piraay Grimm 2024), as recently shown for network alignment (Liu et al. 2023a). Finally, machine learning could be leveraged even in algorithms with optimality guarantees. For example, integrating GELATO into branch-and- aanch-and-bound methods for exact graph edit distance may reduce the time to reach optimality.
10

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
Code and datasets are available htwp:///aiatttt////tttta../////a http:///ggg..baocoo//////a/aaaaa
Moreover, the details needed to reproduce our implementation and experimental setup are reported in Appendix F
ETHICS STATEMENT
This paper presents work whose goal is to advance the field of machine leamnin. There are many indirect potential societal consequences of our work, none which we feel must be specifically high- lighted here.
REFERENCES
Jiyang Bai and Peixiang Zhao. Tagsim: Type-aware graph similarity learning and computation. Proceedings the VLDB Endowment, 15(2), 2021.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In ACM WSDM, 2019.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning- based efficient graph similarity computation via multi-scale convolutional set matching. AAAI, 2020.
Richard Bellman. The theory of dynamic programming. Bulletin of the American Mathematical Society, 60(6):503-5155 1954.
Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.0994 1,09940, 2016.
Yoshua Bengio. Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: a methodological tour d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
David B Blumenthal and Johann Gamper. Improved lower bounds for graph edit distance. JEEE Transactions on Knowledge and Data Engineering, 30(3):503-516, 2017.
David B Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, and Luc Brun. Compar- ing heuristics for graph edit distance computation. The VLDB journal, 29(1):419-458 2020.
Sébastien Bougleux, Lue Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. Graph edit distance quadratic assignment problem. Pattern Recognition Letters, 87: 38-46, 2017. Advances in Graph-based Pattern Recognition.
Horst Bunke and Kaspar Riesen. Graph edit distance-optimas and suboptimal algorithms with ap- plications. Analysis of Complex Networks: From Biology to Linguistics, pp. 113-143, 2009.
Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 2023.
Vincenzo Carletti, Benoit Gaüzere, Luc Brun, and Mario Vento. Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance. In Graph-Based Representations in Pattern Recognition, pp. 188-197, 2015.
Qihao Cheng, Da Yan, Tianhao Wu, Zhongyi Huang, and Qin Zhang. Computing approximate graph edit distance via optimal transport. Proceedings of the ACM on Management of Data, 3(1):1-26, 2025.
Khoa D Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K. Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. ACM SIGIR, 2021.
11

---

Published as a conference paper at ICLR 2026
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisim- ulation quotienting for efficient neural combinatorial optimization. In NeurIPS, 2023.
Frank Emmert-Streib, Matthias Dehmer, and Yongtang Shi. Fifty years of graph matching, network alignment and network comparison. Information sciences, 346:180- 197, 2016.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.024440 2019.
Matthias Fey, Jan E. Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. Deep graph matching consensus. In ICLR, 2020.
Zua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In AAAI, 2021.
Gao, Xiao Huang, and Jundong Li. Unsupervised graph alignment with wasserstein distance discriminator. In ACM SIGKDD, 2021a.
Quankai Gao, Fudong Wang, Nan Xue, Jin-Gang Yu, and Gui-Song Xia. Deep graph matching under quadratic constraint. In CVPR, pp. 5069-5078, 2021b.
Rafael Gómezz-oomarellli, Jennifer N Wei, David Duvenaud, José Miguel Hernnndez-Lobato, Benjamín Sänchez-Lengeling Dennis Sheberla, Jorge Aguilera-lparaaguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268-277) 2018.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://www
gurobi comm
Jiashu He, Charilaos Kanatsoulis, and Alejandro Ribeiro. T-gae: Transferable graph autoencoder for network alignment. In The Third Learning on Graphs Conference, 2024.
Jaeseung Heo, Seungheom Lee, Sungsoo Ahn, and Dongwoo Kim. Epic: graph augmentation with edit path interpolation via learnable cost. In IJCAI, 2024.
André Hottung, Yeong-Dae Kwon, and Kevin Tierney Efficient active search for combinatorial optimization problems. In ICLR, 2022.
W Hu, B Liu, Gomes, M Zitnik, P Liang, V Pande, and J Leskovec. Strategies for pre-training graph neural networks. In ICLR, 2020a.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in neural information processing systems, 2020b.
Wei Huang, Hanchen Wang, Dong Wen, Wenjie Zhang, Ying Zhang, and Xuemin Lin. Dif- fged: Computing graph edit distance via diffusion-based graph matching. arXiv preprint M.Xiv:2503.1824. 2025.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. pmlr, 2015.
Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De. Graph edit distance with general costs using neural set divergence. In NeurlPS, 2024a.
Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De. Graph edit distance evaluation datasets: Pitfalls and mitigation. In Learning on Graphs Conference, 2024b.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 2019.
Derek Justice and Alfred Hero. A binary linear programming formulation of the graph edit distance. IEEE Transactions Pattern Analysis and Machine Intelligence, 1200-112001121 2006.
12

---

Published as a conference paper at ICLR 2026
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial opti- mization algorithms over graphs. NeurIPS, 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In ICLR, 2019.
Francesco Leonardi, Markus Orsi, Jean-Louis Reymond, and Kaspar Riesen. Gedan: Learning the edit costs for graph edit distance. arXiv preprini arXiv:2508.0311/ 2025.
Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, and Sébastien Adam. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, 72:254-265, 2017.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals. and Pushmeet Kohli. Graph matching net- works for learning the similarity graph structured objects. In ICML,, 2019.
Chang Liu, Zetian Jiang, Runzhong Wang, Lingxiao Huang, Pinyan Lu, and Junchi Yan. Revocable deep reinforcement learning with affinity regularization for outlie-rrouust graph matching. In ICLR, 2023a.
He Liu, Tao Wang, Congyan Lang, Yidong Li, and Haibin Ling. Deep probabilistic graph matching. IEEE Transactions Knowledge and Data Engineering, 2025.
Junfeng Liu, Min Zhou, Shuai Ma, and Lujia Pan. Mata*: Combining learnable node matching with a* algorithm for approximate graph edit distance computation. In CIKM, 2023b.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In NeurlPS, 2023.
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Can classic gmns be strong baselines for graph-level tasks? simple architectures meet excellence. In ICML, 2025.
Mohammadreza Nazari, Afshin Oroojlooy. Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In NeurlPS, 2018.
Michel Neuhaus and Horst Bunke. A probabilistic approach to learning costs for graph edit distance. In ICPR, 2004.
Paolo Pellizzoni, Carlos Oliver, and Karsten Borgwardt. Structure- and function-aware substitution matrices via learnable graph matching. In Research in Computational Molecular Biology, 2024.
Paolo Pellizzoni, Till Hendrik Schulz, and Karsten Borgwardt. Graph neural networks (often) count substructures. In International Conference on Learning Representations, 2025.
Chengzhi Piao, Tingyang Xu, Xiangguo Sun, Yu Rong, Kangfei Zhao, and Hong Cheng. Computing graph edit distance via neural graph matching. Proceedings of the VLDB Endowment, 16(8): 1817-1829, 2023.
Jonathan Pirmay and Dominik G. Grimm. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. Transactions on Machine Learning Research, 2024.
Can Qin, Handong Zhao, Lichen Wang, Huan Wang, Yulun Zhang, and Yun Fu. Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation. In NeurIPS, 2021.
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. Greed: A neural framework for learning graph distance functions. In NeurIPS, 2022.
Kaspar Riesen. Stefan Fankhauser, and Horst Bunke. Speeding up graph edit distance computation with bipartite heuristic. In ML.G, pp. 21-24, 2007.
13

---

Published as a conference paper at ICLR 2026
Michal Rolinek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In ECCV, pp. 407- 424, 2020.
Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Inter- pretable neural subgraph matching for graph retrieval. In AAAI, 2022.
Indradyumna Roy, Saswat Meher, Eeshaan Jain, Soumen Chakrabarti, and Abir De. Position: Graph matching systems deserve better benchmarks. In ICML Learning Position Paper Track, 2025.
Samidha Verma, Arushi Goyal, Ananya Mathur, Ankit Anand, and Sayan Ranu. Grail: Graph edit distance and node alignment using llm-generated code. In ICML, 2025.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. In NewrIPS, 2015.
Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, and Xiaokang Yang. Combinatorial learn- ing of graph edit distance via dynamic embedding. In CVPR, 2021.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 ( 24, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In ICLR, 2018.
Lei Yang and Lei Zou. Noah: Neural-optimized a* search algorithm for graph edit distance compu- tation. In ICDE, 2021.
Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Learning deep graph matching with channel-independenn embedding and hungarian attention. In ICLR, 2019.
Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching. In CVPR, pp- 2684- 2693, 2018.
Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling. ICLR, 2024.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in neural information processing systems, volume 31, 2018.
Zhen Zhang, Jiajun Bu, Martin Ester, Zhao Li. Chengwei Yao, Zhi Yu, and Can Wang. H2mn: Graph similarity learning with hierarchical hypergraph matching networks. In ACM SIGKDD, 2021.
Wei Zhuo and Guang Tan. Efficient graph similarity computation with alignment regularization. In NeurIPS, volume 35, pp. 1118811119,,,, 2022.
14

---

Published as a conference paper at ICLR 2026
A LIMITATIONS
While our model shows state-of-the-ar performance, we believe can be improved in several ways, which could be addressed by future work. First, GELATO relies on a simple ensembling strategy at inference time, and designing better inference strategies, such as beam search, could lead to significant performance boosts. Moreover, a dataset-specific hyperparameter search for the GNN's architecture and training strategy could further improve results.
Moreover, we believe that crucial advance in the field would be improving the solution quality on graphs larger than the ones seen at training time. In fact, removing the need for supervision from optimal matchings, which computationally expensive to compute, would be possible approach to tackle such a challenge.
B ADDITIONAL RELATED WORK
Graph Edit Distance Additional learning-based methods that tackle the GED problem are TAGSIM (Bai & Zhao 2021), and EGSC (Qin et al., 2021), which address the problem of learn- ing graph dissimilarities, as well as IsONET (Roy et al.j 2022), which focuses on graph retrieval. Finally, a recent unpublished preprint proposed DIFFGED (Huang et al. 2025). diffusion- -based model for graph edit distance that shows promising performance. However, their code is not pub- licly available yet.
Usually edit costs (Definition 3 are considered to be known. In fact, the task of learning the edit costs, pioncered by Neuhaus & Bunke (2004), has been tackled with machine learning the context of dataset augmentations (Heo et al. 2024), biochemistry (Pellizzoni et al. 2024), and general GED
[Loonarii et al. 2025).
Deep graph matching and network alignment The deep graph matching (Fyy et al. 2020) or
deep network alignment research field (Emmert--Steib et al. 2016 He et al., 2024) is adjacent to the graph edit distance learning one. Although the graph matching (or network alignment) and the graph edit distance are largely equivalent problems, the focus of learning-basee methods to solve the two problems has historically been quite different in terms of objectives, modeling, and scale.
In GED-related works the focus is usually on computing a metric space over several small graphs (e.g.. molccules) and simple edit costs. On the other hand, in works entailing learning-bast based graph matchings, the focus is usually on fewer and larger graphs, often coming from computer vision (Gao et al.] 22221b; Liu et al. 2025)), and more complex costs, usually presented in the form of an affinity matrix (Zanfir & Sminchisescu 2018: Yu et al. al.| 2211), which possibly depend on continuous node features. Usually, the task maximize the affinities of matched node and edges, or to recover some ground -ruth alignment between the graphs. Several papers tackled the graph matching problem using deep learning, including approaches based on attention (Yu al. 2019), on differentiating through combinatorial solvers (Rolinck et al. 2020), on unsupervised methods (Gao formulations (Gao et al., (021b). In this setting,
al., 2021a) la) and on candrattc-asiggmment Liu et al. (2023)) introduced the R RM model, which maximizes an affinity score by predicting node matches sequentially, similarly to GELATO. Besides from the different objective function to the one GELATO seeks to optimize, RGM relies on more computationally expensive product graph, where each node represents pairs nodes from the original graphs. Moreover, RGM does not seem to exploit any reduction of the search space, allowed by our Theorem [ Finally, the model is trained with reinforcement learning rather than supervised learning.
Neural Combinatorial Optimization The neural combinatorial optimization field, pioneered by Vinyals et al. (2015) and Bello et al. (2016), uses deep learning to construct heuristic solutions to NP-hard problems, usually focusing on routing problems such as TSP or CVRP. Approaches include supervised learning methods (Vinyals et al. 2015 Joshi et al. 2019 Fu et al. 2021 Luo et al. 2023). 9, like we do in this paper, but also reinforcement saaatorcemeet--larinnggg. based methods (Nazari et al.
2018 Kool et al.] 2019 Hottung et al., 2022 Zhang al. 2024 Pirmay & Grimm 2024). See the
review in Bengio et al. (2021) for an overview of the field, and Cappart et al. 2003 for a focus on graph-related problems.
15

---

Published as a conference paper at ICLR 2026
C ADDITIONAL PRELIMINARIES
In the following, we provide additional definitions that complement Section 2
C.I GRAPH EDIT DISTANCE
Recall that, given two graphs G₁ F4,,Fi and G2 (V2, Fg, 62), the graph edit distance (GED) between G1 and G2 is defined by GED((1 G2) M(G c(u), with
c(u) Σ Cn(Gi, G2, (L.))P
Σ
ce G2, (u, w), (v,
where Cn is the cost function for node edit operations and c. for edge edit operations. We then define formally these cost functions.
Definition 3 (Edit cost functions). Let G1 (V,, (1) and G2 (V22 E2, f2) be graphs. For pair of nodes u E V1 U {s} and v E V2 U {e}, we define
if and v =
(e2())
ifu E, V2,
Ca (G1,,, G2, u.
8iel (1)(1)
ifu Ví, v =
8 (aulle E2(v))
if E Ev, v V2,
where 8 the cost of inserting a node, 8ãel the cost of deleting a node, and 8thb measures the cost of substituting node with
For pair of edges (u,w) E E1 U {o} and 2), E Fg 1 {E}, we define
0
if (u, w) = and (u,2) = E, if (u, w) (v,z) E EE,,
Jin (f2r,
co(Gi, G2, (u, (), (v,
if (u, EL, (v,2) E, if (u, Er, (v, E2, where 8in is the cost of inserting an edge, dāe the cost of deleting an edge, and &uub measures the cost of substituting one edge with another.
(f,,(( w))
(intle((u, w), (2(,,))
Importantly, in this paper we consider the cost function to be fixed for an entire dataset, i.e., it does not change from one instance another.
Moreover, we consider only the case in which (f2(U, 2)) + (E w)) > (E, (E (u, (2 2)), as this is needed to ensure the equivalence between GED and graph matching (Bougleus et al. 2017 Proposition 1). If this is not the case, once can simply Semble (&1 (u,, w), f2(
0i (2)( + dāa (fi(,, (w).)..
C.2 ISOMORPHISMS AND AUTOMORPHISMS
We say that two graphs G and H are isomorphic, denoted as H. if there exists a bijec- tive mapping Va Vn. called isomorphism, such that la(v) = -E Vu E Vo. and v)((u,v) = (((((())) (())), Yuu E Eg, and (*(u), [()) E EØ and only if [u, t} E Ec.
The group of isomorphisms from G to itself is called the automorphism group Aut(G). Given graph G and nodes u, u E VG. we say that they belong to the same orbit if 3π E (u) such that (u))
Moreover, we can define isomorphisms for graph matchings. In particular, given G1, Gu, P E M(G1, G2), and G¹, G2,, μl M(G G2), say that (G1, G2, μ)) is isomorphic to (Gi, Gh jt) there exists a bijective mapping π V, UV, + V' such that (i) kly; is an isomorphism from G G/, (ii) i m|y, is an isomorphism from G2 to G% and (iii) ((=(n), (v))): (u, v) p) n².
16

---

Published as a conference paper at ICLR 2026
Then, can define the automorphism group Aut Aut G2, ji) the group of isomorphisms from (G1, G2. ju) to itself. In particular, given two pairs of nodes (u E V12 x V2 and (w, 2) E Vi x V2, say they are automorphic, denoted as (G,, H2, u) (G,, G2. He w, 2), if Fo E Aut(Gi, G2,14) such that (=(u), x(U)) = (w,z), Given a set of graphs G. we denote the set of pair-orbits VM = {(Gi, G2, u, u): G1, G2 E 9, μ E M(G1, G2),
V1, E V2)/>.
In fact, identifying pair-automorphisin in matchings can be reduced to finding node automorphisms in the graph representation of the instance. For computational efficiency, we use WL classes, en- riched with homomorphism counts from small cycles, as a proxy for automorphisms.
D PROOFS
Lemma 1. Let G be of graphs. Consider the following algorithm, given GEDFM instance (G1, G2, 1)) and a function C:: VM - RR
1. select (u, v) = arg (ax G2,
2. set 1 == ((u,v))
3. if A(G,,
0 return, otherwise go to step
Then, there exists function C* VMM -> TR such that, for any pair of graphs G1, G2 E 9, the algorithm above called with (G1, 0) and function C* outputs an optimal matching pt, Le. such that c(p²) GED(G1, G2).
Proof. We construct such a function. Let fi be a map (G1, G2, + V/ mapping GEDFM instances the missing matches to get an optimal matching v. Let then f2 = min of1 be map that selects one match out of the set, based on some arbitrary but universal ordering on matches. Then, we can let C' (G1, G2, (4, a, b) if fz(G1, G2. p)) (a, b), and otherwise.
Then, we have that at each step of the algorithm, pair (u, v) belonging to an optimal matching is chosen. Therefore, when the algorithm, terminates, output is an optimal matching.
Theorem D Let (G1, G2. be GEDFM instance and pº 2 optimal matching for it. Then, the instance (Gi, G2. v/) reduce(Gi, G2; p)) has an optimal matching μ² (V x Vi).
Proof. Recall that f arg mag uSU G2,1),,))
We have that
eG1,, G2,
Σ (u.e)CD
en G2,
Σ
Ce G2, (u,
(w))))
uCw
Σ (u.e)ePa
G2,
Σ
GG,,
(R,F)EM
Σ
ce(Gi, G2, (u, (u, (v,
Σ
co ((G,,C2,(e (2, (,, (v. (v.
(w.e)eR
Σ
CG,,,,2,,,0)
Σ
Ce,G1, (1, +C,
(
(u.))EPA
(w.2)EP
where does not depend on the choice v.
Splitting the over edge costs, then have
(G,,G2,1)-
Σ
C, U)
Σ (W.D)ER)
C. (u, (u,z))
(u.D)EP)
(w.2)Ep)a
Σ
Σ
Ce G2, (u, +C.
(w.z)En (u.
17

---

Published as a conference paper at ICLR 2026
Note that for any (u, u) V \ ja both and unmatched, so Ví and Vz. Therefore, all pairs considered in the first and second sum are in V x Vz. Note that for (u, v) E Vi x Vi we have C, (G,, G2, v) Cn (G), G22, v), both nodes maintained in the reduced graphs. Moreover, (u, v): (w, 2) E V x V2. we have cel (e(G1, G2, w), (v, z)) Ce(G", G22, (u, w); (v, z)), both edges maintained in the reduced graphs
We now focus on the last sum. In particular, consider (w, 2) E f Jl. This happens either w or have no unmatched neighbors. Then, for any (u, v) D μs, since both a and are unmatched, we have that (u, w) $ Ej. Then we have that E(u,))Er) Co G2, (u, w), ()) is constant in v.
We can therefore write
G2,
Σ Cn 2,) (u.))
Σ (u.D)ERIN (wN,))E0A
ce(Gi, G2, (u, (u,
+
Σ (n
+C'.
(w.:)En'
Given matching v E MMGI,GG) such that μ le
V3) E M Gy), Then, we have that v \ 1 = v' \ n.. Since a valid solution to the reduced instance must have p C v', we have that the map v + v/ is bijection between valid solutions of the original and the reduced instance.
Consider // (V V22 E MIG G2y). We then have that =itt"=UULt = u Vi, Pu, v) / U [(E, v): u E V2 (u, v) E v/). Then, noticing that a node u E Vi or E 1/2 is unmatched in v if and only if E V or v E Vi respectively is unmatched in v/, we have that D \ = V Ar..
This lets write c(G1, G2, v) only function of v' as follows:
c(C1, (2.
Σ
ea Ca C2, u. +
Σ
(u.))Em/
(w,))
Σ
+
(N.") (w.s))H
Σ (W.
Ca( U2, +)
Σ
ce(Gi, (u, C³.
( (w.a)ge
Finally, we turn our attention to cGG Gizy 1/). We can write
(G, Σ
U2),,)
Σ (1,
ce (u,
(w.w)e
uew w
Σ
Ga
Σ (MY))n
Ca G2, u)
(u.))E we
Σ
Co Gz (1,)))
Σ
ce G2 (u, (v.2))
(u,0)E7
(w.))....))E
(W.))E
Σ
Cn C2,,,)
Σ
co(C', (1, + C".
( (w.)))w
In particular, for any valid instance M(G1, G2), we have that e(Gi, G2, c(G G2 v/+ + K. with K constant not depending on the choice of v. Then, if D² is an optimal solution to (G,, G2, then n/ = V² n (V( Vi) is an optimal solution to (Gi, G2 v²).
Lemma 2. The map (G, G2, 11) = H injective and there exists a map decode such that decode encode id.
18

---

Published as a conference paper at ICLR 2026
Proof. To prove injectivity it suffices to exhibit the left inverse decode such that decode encode id. Given a graph H = (VH, En, EH) that arises from the encoding of (G1, G2. (), define
V = { E VH (t) marks with sre J. V = { VH (v) marks with trg }.
By construction V and 1/ form a partition of Vи into the nodes of G1 and G2 respectively, We then define
E = (u, v) E En uu Vi J. E = { (u, E Eh u VV2 }.
which by construction correspond to the edges of 11 and G2 respectively, Finally, we recover the matching edges
v = (u, v) E En E Vi, VE VEV2,
which by construction correspond to the node matches in μ. Finally, we let be the function Ex, without the additional sre and trg labels.
Let G1 = (Vi, F4, () and G (V2, F22 f), and set decode H) (Gi, G2,
Therefore encode admits left inverse and injective.
Lemma 3. Let (G1, Gz, n) be a GEDFM instance and μ¹ an optimal solution to it. Let pair of nodes (u, v) V1 x V/2 such that (u, v) E μ². Let also (w, 2) E 4e" be such that (u,v) v) and (w, automorphic. Then, there exists optimal solution v such that v) E Ev".
Proof. Since (u, v) and (w: z) are automorphic, there exists a matching automorphism a e Aut(Gi, G2, u) such that T(w) w and x=z)
Let then = {(x(a), r(b):: (a, E μ*). By definition of matching automorphism, we have that {(T(a), T(b)): (a, E p} = 14, and since μ², we have that S v. Thus is a feasible solution.
We have Cn = Ela (G1, G2, a. b) = Eledren (, G2, n. (c), (()). Since
On is permutation-equivariann we have Cn = E(onjen" (G ( c,
Eledee en (G1, G2, c, c,d), which is the node cost for μ²" We can obtain the same result for edge costs. Thus, μ² and have the same cost, and v is optimal.
Finally, since (w, 2) E μ², we have that (u, v) = x(ww),(2)) E by construction.
E DATASETS
In this section, we discuss details about the datasets we use and introduce in the paper, including instructions on how to download and how to use them.
In our experiments, consider the established SimGNN (Bai et al. 2019) datasets AIDS, LINUX and IMDB. In particular, AIDS and LINUX contain graphs up to 10 nodes, and thus were provided with ground truths. On the other hand, IMDB contains graphs with up to 50 nodes. In the original datasets, ground truths were provided only for graphs with up to 10 nodes, and suboptimal values for others. Instead, we take the subset of graphs up to 16 nodes, and compute optimal matchings. We denote this dataset as IMDB-16. AIDS is endowed with node labels, but no edge labels. LINUX and IMDB on the other hand have unlabeled node and edges.
Moreover, we generate three additional datasets, taking all graphs from the ZINC, molhiv and code2 datasets (E6mez-Bombarc et al., 2018, Hu et al.) (020b). Due to computational constraints in computing the optimal matchings, respectively. We denote these datasets as ZINC-16 16, molhiv-16 and code2-22. code2 is endowed with node labels, but edge labels. ZINC and molhiy have labels on both node and edges, but also consider a version with no edge labels.
select the subsets of graphs with up to 16, 16 and 22 nodes,
The graph datasets that consider cover multiple domains, including molecular graphs (AIDS, molhiy-16, 16, ZINC-16), software networks (LINUX), movie collaboration networks (IMDB-16), and Python program syntax trees (code2-22).
19

---

Published as a conference paper at ICLR 2026
We randomly split the graphs into training, validation, and test sets using 60:20:20 ratio. Jain al. (2024a) identified that the established GED benchmark datasets are polluted by isomorphic graphs. Their approach is to remove isomorphic copies of graphs. Instead, retain all graphs, but ensure that no two graphs across different splits are isomorphic to prevent data leakage. Retaining isomorphic copies allows
have consistent number of graphs with previous works, and to include (both for training and testing purposes) instances where the edit distance is O.
Table reports some statistics about the datasets. In particular, report the number of graphs, the number of unique graphs up to isomorphism, the average number of nodes and edges, and the number of node and edge labels. Moreover, we report the number of pairs of graphs for which the optimal GED (with unit costs) and corresponding matching was computed, as well the average, minimum and maximum value of such GEDs.
Dataset
# graphs
# nodes
avg.
node
edge labels
pairs
GED
classes
avg. min.
edges
labels
avg.
min.
AIDS
700
8.9.1.
10
8.8
245350
9.0s2.7
LINUX
1000
7.621a
10
6.92
500500
4.7gme
IMDB-16
1185
167
9.6ras
16
33.4mus
175773
22.1esa.7
101
ZINC-16
836
835
14.5a:
9
16
15.0
16
349866
14. 222
27
molhiv-16
6734
6733
13.5us
2
16
14.
41
455993
16.9
0
37
code2-22
2087
785
21.2
11
22
20.2
58
435008
12.8
0
46
Table 6: Summary of dataset statistics.
Moreover, for ZINC and molhiv we additionally create second "larger" with graphs from 17 to 24 nodes, and for code2 from 23 to 30 nodes, which are meant to probe the generalization abilities of GED prediction models.
For each dataset and each split, we generate graph pairs by randomly sampling from the available graphs, and compute the ground-truth graph edit distances and corresponding matchings using the MIP-F2 (Lerouge et al. 2017) formulation of GED as an integer linear programming (IIPP) problem. The IIPs are solved using the Gurobi (Gurobi Optimization, L.C (2024) solver, with warm-starts given by the REFINE local search heuristic (Blumenthal et al.) 2020).
We make our dataset publicly available and easily installable, order to offer a fairer evaluation benchmark also for future research. The code can be obtained from GitHub:
git clone hugegttbbb...crri.ooogard/////o.
con:
Then, our dataset class can be easily used, for example, as follows:
From Gelato. arc. dataset Import GraphKatcch ngnataset
dataset GraphMat of Inggataaes (name= (name="aids', nun pun_pairs=100g spl (t= for data in dataset:
print (data.x_ shape, data. wew.sedde_nndeeeee shape, eete.aaggeattt_s... shape) eegee_iddeeeeeeeeeeeeeeee data. print (dsta..ne) mat chiing.hhppa
source graph target graph matching
print (deta x_t..happ
F EXPERIMENTAL SETUP
In this section, we discuss additional details about the experimental setup.
F.1 BASELINES
For GREED (Ranjan et al. 2022). we used the default parameters suggested by the authors. Specif- ically, set the number of GIN layers to with a hidden dimension of d 64. We used all available graph pairs from the training set for training, and, analogously, the complete validation set for validation. GREED minimizes RMSE in the loss function using the Adam optimizer (Ir=10-3),
20

---

Published as a conference paper at ICLR 2026
and training continued until the pre-implemented early stopping criterion was met. We report the mean and standard deviation over five runs, each using 1000 graph pairs. We utilize the same test sets used as in all other methods. Since GREED outputs continuous regression values, round the predictions to the nearest integer in case of EHR statistics.
For MATA * (Liu al. 2023b), we largely adhered to the default parameter settings recommended by the authors. The model consists of three GNN layers (i.e. SEGen layers), each with a hidden dimension of d = 64. The model uses a binary cross-entropy loss function using an Adam optimizer, with a learning rate set to 10-s, Training was conducted on all available training graph pairs. During training. MATA * employs mini-batch gradient descent with batch size of 128. Model evaluation was performed every 200 epochs over total of 10,000 epochs. We chose the model with the best validation performance, measured in terms of nMAF. In all experiments, we set the parameter top- k = 4, which governs the number of explored matches for each node. To calculate the GED, we first extracted the matchings considered internally by MATA* During this process, we modified line 133 in file Mata . cpp by swapping the inputs q and g (i.e., the source and target graphs) in the function call a > iinit (q, g, g....). We believe this was the intended order based on the function's 's definition and description. Notably, with this adjustment, the results either remained consistent or even showed a significant improvement. Finally, we report the mean and standard deviation over five runs, each using 1000 graph pairs. We use the same test sets considered as in all other methods.
For GEDGNN (Piao et al. 2023). we used the default parameters provided by the original authors. Specifically, the model consists of three GIN layers with hidden dimensions of 64, 32, and 16, respectively. A binary cross-entropy loss is used to minimize the discrepancy between the predicted and ground truth matchings, optimized using Adam optimizer with learning of 10-3 We train on all available training graph pairs over a total of 20 epochs. Model selection was based on the best validation performance in terms of nMAE. We set the parameter k 100, which governs the number of considered node matchings and from which the best is finally selected. For evaluation, we report the mean and standard deviation over five runs, each conducted on 1000 graph pairs, using the same test sets as in all other methods.
In case of GEDHOT (Cheng et al. 2025), we adopted the default parameters specified by the authors. Specifically, the model architecture consists of three GIN layers with hidden dimensions of 128, 64, and 32. GEDIIOT is an ensemble method that combines GEDIOT and GEDGW. While GEDGW is an unsupervised method that produces matchings via solving a surrogate optimization problem, GEDIOT is trained using a loss function consisting of an MSE loss and a binary cross-entropy loss, which is optimised via the Adam optimizer at a learning rate 10-3 We train the model all available graph pairs for 20 epochs and select the best-performing model based on the validation nMAE value. We set the parameter l 100, i.e., the number of considered matchings, from which the best is finally selected. For evaluation, we report the mean and standard deviation over five runs, each using 1000 graph pairs We use the same test sets as for all other methods ensure fair comparison.
To evaluate Verma al. (2025), we used all functions discovered by GRAIL that were provided by the authors. To select the optimal programs, we ran all 43 function ensembles on a validation set of 1000 randomly selected graph pairs and chose the one with the lowest nMAF value for testing- We note that we modified the matching cost computation to correct rare issue in the original implementation that occurred when singleton nodes were present. Results are reported as the mean and standard deviation over five independent runs, each using 1000 graph pairs, employing the same test sets as for all other methods for consistency.
For GRAPHEDX (Jain et al., 2024a), we followed the parameter choices recommended by the au- thors. Specifically, we utilized the model designed to take into account node labels. For edge edits, employed the XOR neural surrogate function, and for node edits, used AlignDiff, sug- gested by the overall best performance in the original study. We trained the model on all available training graph pairs and validated it all available validation graph pairs. Model selection was based on the best validation performance, measured using nMAE. Training was halted when the validation performance did not improve for 10 consecutive epochs. The model was optimized us- ing Adam with a learning rate of 0.001, minimizing a bounded loss term on edge, node, and label alignment distances. For evaluation, we report the mean and standard deviation over five runs, each conducted on 1000 graph pairs, using the same test sets as those used in all other methods
21

---

Published as a conference paper at ICLR 2026
F.2 SETUP FOR GELATO
The action predictor is a GNN model, implemented following the formulas in Section 4.2 At inference time, given an instance (G1, G2, 0), we first transform it into a single PyTorch Geometric graph (i.e. as a tuple x, edge_index and edge_attry following the specification described in Section 4.1 Note that at the first step, no reduction is performed.
GELATO is implemented in PyTorch Geometric Fey & Lenssen 2019).
Recall that, at each step, given a graph-encoded instance (G1; G2, Ju), we choose the next match to arg (ux(u.)) AUC, Ou,, and we create a new instance (G1, p U {(u, v))). This implemented by simply adding the edge (u, v) and its label to the edge index and edge aatr vectors. Then, the reduction is performed by identifying the nodes that would be deleted by the reduce map, and removing all edges adjacent to them. From the peessage-passingg perspective this is the same as deleting the nodes, but it allows to avoid re-indexing the representation of the graphs at each step. We note that, the presence of BatchNorm, the embeddings of these isolated nodes can still marginally influence the embeddings of the non-deleted nodes during training (but not during inference). although this does not seem to affect the performance empirically. This reduced graph is then fed to the action- action-predictt predictor GNN.
In the experiments, unless otherwise specified, we fix the number of GNN layers to L = 5 and the embedding dimension to d 128. We train the link prediction task using the cross-entropy loss with the Adam optimizer, with learning rate Ir = 10-3 and no weight decay, for 30 epochs. We use up to 2 10a randomly selected pairs of training graphs, subsampling from each 40 random sub-instances, as described in Section 4.3 Model selection is based on the validation nMAE, which is computed at the end of each training epoch. At inference time, we use ensembling with k 32, unless otherwise stated, and the matching attaining the lowest cost is returned.
We now describe the setup for ablation studies, For the "No sequential process" row, we train only with instances with no fixed partial matchings. At inference, we do the following. Given two graphs G2 and G2,, we compute the logits Ou,e between vertices E V1 and v E V2. We then compute log-likelhhoods as lu,, log( (sigmoid((o...)), We then compute the matching corresponding to the optimal linear assignment between Vı and V/2 iie. MiA = arg max,, E(u,))e lu.p- Assuming independence between choices, this maximizes the likelihood of the matching. For the "No in- stance reduction" row, perform both training and inference without reducing the instances with the map reducc. Finally, for the "Automorphic matches" row, we perform training with the naive strategy which for an instance (G1, G2, 14) selects the set μ \ μ as positive links and all others A(G,, G2, M) \ 4 as negatives. Inference is performed in the same way as in the standard model.
F.3 COMPUTING INFRASTRUCTURE
The experiments are run on a cluster equipped with Intel(R) Xeon(R) Silver 4116 CPUs and NVIDIA H100 GPUs The code is based on PyTorch and Geomerci
G HYPERPARAMETER STUDIES FOR GELATO
In this section, we discuss the sensitivity of GELATO its hyperparameters. In particular, we study the effect of the use of batch normalization and residual connections, as well as the embedding dimension d, the number of GNN layers L, and the ensemble size k:
First, Figure 7 reports, for all datasets, the EHR (L) when ablating batch normalizations or residual connections from the GNN layers. We fix d = 128, L = and = 32, which are the values used for Table [ Here, we see that the ablation consistently decreases solution quality, albeit with only minor degradation.
Figure 8 reports, for all datasets, the EHR ()) when varying the embedding dimension d {32, 64, 228). and while keeping C = 5 and k = 32, which are the values used for Table I The results show that, generally, the solution quality increases with the dimensionality, and that lowering the embedding dimension from the default of = 128 reduces model capacity. On the other hand, increasing the dimensionality to d = 256 yields modest gains, but increases the memory
22

---

Published as a conference paper at ICLR 2026
AID8
LINUX
BMD8-18
180
45
02211
23-
No. Saii
Suslay moneeii
Detek
RedKan
Sadka mww.
Delak
Yeslgg Vesggeeetn
16
molity
codkd
100
25
0200
Do Datoaaaaa
So bomettic
Delekt
3o Adb topeccio
Ditak
Batbhom
Figure 7: Solution quality for GELATO w.r.t EHR (4), ablating the batch normalization and the skip connections in the GNN layers. We report mean standard deviation over five runs.
requirements (from roughly 200k parameters to 800k) and runtimes (e.g. from 4.2 0.1 to 0.1 milliseconds per pair on ZINC).
AIDS
LINUX
IMDB 16
100
90-
64
126
216
302
64
126
235
322
04
125
295
2INC:16
munlav-16
cock22222
300
40
1110
30
750
128
64
Figure 8: Solution quality for GELATO w.r.t EHR (L), varying the embedding dimension (32, 64, 128, 256} with -= and 32. We report mean and standard deviation over five runs.
Tigure9rreood for all datasets, the EHR (L) when varying the number of GNN layers (3, 7). and while keeping d 128 and 32, which are the values used for Table I Similarly to the analysis above, the results show that increasing the number of GNN layers generally improves solution quality, at the expense of increased runtime (e.g. 4.8 + 0.1 milliseconds per pair ZINC for L 7) and memory requirements. Once again, moving from L = 5 to f = 7 yields diminishing returns, but decreasing it to L 3 significantly decreases the capacity. Interestingly, choosing = 1, i.c. considering only one-hop neighborhoods, drastically reduces the solution quality. For example, AIDS, the EHR drops only 13%.
Finally, Figure 10 reports, for all datasets, the EHR (L) when varying the size the ensemble 23 25 2 j. with d 128 and L 5. As already reported in Table 4 ensembling yields considerable gains to the solution quality, as alleviates the sensitivity to the choice of the first match. The results show that increasing the number of ensembles monotonically increases the
23

---

Published as a conference paper at ICLR 2026
AIDS
LINUX
DIDB-16
140
1230 (5)
95-
2INC-36
cOCK2-22
45
COU1 (5)
30
Lager
Layen
Laprrs
Figure 9: Solution quality for GELATO w.r.t. EHR (4), while varying the number of GNN layers 5, with d = 128 and 32. report mean and standard deviation over five runs.
lution quality, albeit at the cost of increased runtimes. Indeed, increasing k to 128 increases the inference time on ZINC to 6.3 + 0.1 milliseconds per pair. Interestingly, on ZINC, moving from the standard &o 32 128 improves the EHR from 91 % to 97%, significantly reducing the gap to optimality.
AID8
LINUX
BNDB 18
360
30
22
135
22
munliiv-16
.00
40
31
135
27
175
Ersczble atc
Exsenble skoc A
Ecseniile stec
EHR (L), while varying the size of the ensemble k 25, with d = 128, L = 5. We report mean and standard deviation over five runs.
Figure 10: Solution quality for GELATO
In conclusion, the hyperparameter study shows that the choices of hyperparameters used in the main results sensible choices that balance good solution quality with memory requirements and runtimes. However, they also showcase that, if better solution quality required, GELATO can yield better results by increasing its dimensionality, its number of GNN layers, and the number of ensembles.
H ADDITIONAL EXPERIMENTIL RESULTS
In this section, we report additional experimental result that were excluded from the main paper for space constraints.
24

---

Published as a conference paper at ICLR 2026
report the results of Table using two additional metrics. In particular, we report respectively the mean average error (MAE) and the root mean squared error (RMSE).
Additional metrics First, in Table 7 and in Table &
The MAE is defined 2/N Σ 0: yil where yi denotes the true GED value and ÿ; the value of the predicted matching. For GREED, which does not return a matching, we take ii as the scalar predicted GED. Note that for all methods except GREED, the returned matchings must be upper bounds to the optimal solution, so we have DJ- ys 2 O.
Similarly, the RMSE is defined as (1/N E 3x))) V/ where yi denotes the true GED value and 5J the value of the predicted matching. For GREED, which does not return matching, we take ds as the scalar predicted GED.
The results show that, even when evaluating the models using these different metrics, GELATO retains state-of-the-art solution quality, with a wide margin to the second-best performing method, on all datasets except LINUX and IMDB-16. On these two latter datasets, both GRAIL and GELATO provide near npar-optimal solutions, with the former method yielding slightly better solution quality, as observed in Table
Method
AIDS
LINUX
IMDB-16
ZINC-16
molhiv-16
code2-22
GREED
0.814
0.48550.014
1.030so.om
1.35 030
1.53720.004
1.025
GRAPHEDX
0.586
0.382+o.00s
3.258 0.100
0.92+o.015
1.530eo.026
0.418:0.015
MATA
0.509 044
0.2442o.026
0.086 0201
2.468Lo 07s
2. 2..70
0.65 1g0.013
GEDGNN
1.7411. 043
0.3944...0
0.357
6.490 168
5.03520.03:
2.320 082
GEDHOT
0.524+o.um o25
0,.33++.00m
0.050+o.019
3.753+o.0ss
3.365+o.0a7
0.966-
GRAIL
0.224+o.mm
0.000+
0.002 0.004
1.759+..ne oss
1.323+0.019
0. 0.708
GELATO
0.012+o.004
0.002+o.002
0.004 o.00
0.098+a.015
0.053+o.009
0.054=n.010
Table 7: Overall solution quality of methods w.r.t. MAE (L).
Method
AIDS
LINUX
IMDB-16
ZINC-16
molhiv-16
code2-22
GREED
1.02920.017
0.655ra a
1.94920.0me
1.719ta.ozz
2.06920.0m0
1.482 078
GRAPHEDX
0.740
0.503 oas
2.94220.207
1.188to.00 032
1.978
0.579
MATA*
0.96620.04s
0.849
0.728
2.94140.om 078
2.730
1.183 031
GEDGNN
2.69720.070
1.1772 062
2..
7.371a0.1a1
4.914.0.00m
3.704...o 092
GEDHOT
0.998
0,270+a.ozr
0.468+o.100
4.441+o.100
4.190-o.04r
1.627 034
GRAII.
0.5632o.019
0.0131o 028
20.062
2.250 ooe
1.883
1.29320 o4n
GELATO
0.0541a.0s0 0.16720-017
0.12020.056
0.3391a.080
0.273_o.053
0.286 037
Table 8: Overall solution quality of methods w.r.t. RMSE (L).
Moreover, in Table 9 and Table 10
report the results on the edge-unlabeled variants of the with respect to MAE and RMSE, respectively. Similarly to the results
datasets, as done in Table 2 in the main paper, GEL.ATO achieves the best solution quality also with respect to these two metrics.
we report the results of the experiments on generalization to larger graph sizes, reported in Figure with respect to nMAE (lower is better). We can see that general trend is the same as reported in Figure 5, with GELATO providing better solution quality compared to all baselines for all instance size ranges.
Moreover, in Figure II
Non-unit edit costs While in the main paper performed all experiments with unit edit costs, GELATO can natively support any edit cost function. On the other hand, all other methods that return matchings which were considered baselines do not seem to support non-unit edit costs.
We report results on AIDS and ZINC-16, using two sets of non-unit edit costs. First, we consider the case where node operations more expensive than edge operations. In particular, according to
25

---

Published as a conference paper at ICLR 2026
Method
ZINC-16
molhiv-16
Method
ZINC-16
molhiv-
GREED
1.14 o17
0.842
GREED
1.44720.04
1.0742o.os oss
GRAPHEDX
0.686+0.015
0.654+0.024
GRAPHEDX
0.875+o.02
0.828ro.02
MATA
2.29
2.30220
MATA *
2.74720.037
2.81 2.00310.011
GEDGNN
5. 5.938+o.dm ooo
5.272+0.070
GEDGNN
6.799+0.0
6, 6,253+o.10
GEDHOT
2.6144 4+0.040
2.126+0.058
GEDHOT
3.132+o.04
2.731+0.004
GRAIL
1.01 1+0
0.763
GRAIL
1.444+0.00
1.221+o
GELATO
0.086+0.com
0.052+a.00
GELATO
0.340+o.04
0.264+o.o4
Table 9: Overall solution quality of methods on edge-unlabeled datasets w.r.t. MAE (L).
Table 10: Overall solution quality of methods on edge-unlabeled datasets w.r.t. RMSE (L).
ZINC
molhiv
vode2
230
200
2100
150
150
150
150
300
100
50
00
100
GEDINI
40
40
20
20
30
13:34
15:16
17-18
19-20
21-22
23-24
13:14
15:16
17-18
19.20
21-22
23:24
19:20
21:22
23-34
25.26
27-25
20.30
Graph
Graph
Graph
Figure 11: Performance of methods across graph sizes measured by mMAE (L) in %. Training was conducted on graph pairs up to size 16 or 22. The dashed line separates in-distribution from out-of- distribution graphs.
Definition 3 we set 8 8 dit 10 and & o 0ā.t = 1. For brevity, we denote this 10, 8 1. Second, we consider the case where edge operations are more expensive than node operations. In particular, we set 5t 1, 8 10.
Results, reported in Table II] show that GELATO shows state-of-the-arr performance also in the presence of non-unit edit costs, with solution quality generally aligning with the solution quality datasets with unit edit costs.
AIDS
ZINC-16
Method
8" = 10, 8" =1
8"
11 8"
10
5"
= 10, 8" =
5" = 1, 6" 10
1MAE
EHR
nMAE
EHR
nMAE
EHR
nMAE
EHR
MIP-F2.011
0.8
89.0
31.7416
57.6
8.520
18.8a1 s
72.520.
3.8
BRANCH
20.0
3.420.2
2
1.8
24.0ao.a
1.0go.a
195.9
1.0go.s
REFINE
7.9-1.2
42.2r1.a
121.7+13.a
16.4t1.a
12.4+2.7
5.2tu.a
155.5+300
0.8+a.
GREED
7.5
12.3
15.0to.9
6.9to.
6.8toa
8.7
14.8rua
3.8
GELATO
0.2
98.3+o.s
0.9.
98.9
0.9
83.0
0.7
77.8
Table 11: Solution quality of methods with non-unit edit costs, w.r.t. aMAE (L) and EHR (f) in %.
Transfer-learning across datasets An interesting question is whether the weights learned for one datasets can be used at inference time for another dataset transfer learning fashion, or whether the weights are dataset-specific.
26

---

Published as a conference paper at ICLR 2026
An issue to take into account is that for different datasets, node and edge features might have dif- ferent meanings. For example, the same one-hot encoding which represents a carbon atom in the mo dataset represents type of Python function in the code2-22 dataset. Even across datasets from the same field, the problem persists. Indeed, in the ZINC molecular dataset, atom types are indexed differently form the 1o dataset. Therefore, model would be unable transfer the patterns learned on one dataset to another one.
This issue does not arise in unlabeled datasets, such LINUX and IMDB-16, the model exploits only the graph topology. Table [2 reports the EHR (t) in this transfer learning setting on the two unlabeled datasets. We notice that while there is some degradation, likely due the differences in the graph distributions across the two datasets, the solution quality remains quite satisfactory.
Moreover, to circumvent the issue with features on labeled graphs, we introduce new molecular dataset, moltox- 16. This dataset is obtained from the OGB repository (Hu et al. 2020b). specifically by taking all the graphs with less than 16 nodes from the ogbg- moltox21 dataset. Since molhiv- and moltox-16 16 both are obtained from OGB and belong to the same domain (molecules), they share the same feature space. Table reports the EHR (1) when doing transfer learning between these two molecular datasets. Indeed in this case we can observe that the drop in performance, albeit present, minimal. This shows that the model indeed able to apply the molecular patterns learned on one dataset to the other one, in both directions.
Finally, Table reports EHR (T) when doing transfer learning between labeled datasets that do not share common feature space. As expected, the degradation in solution quality is much more pronounced. In this scenario, in light of the results of Table on limited or noisy supervision, is better to spend some computational resources for producing few ground truth matching, and using those to train a specialized model for the data distribution at hand.
Testing
Testing
Training
Training
LINUX
IMDB-16
molhiv-16
moltox-16
LINUX
1.. 88.5
99.9
molhiv-16 16 moltox-16
95.320.8
97. 07.8
IMDB- 16
99.9...1
91.7+0.7
98. 1
Table 12: Transfer learning performance w.r.t. EHR (f) unlabeled graphs from dif- ferent domains.
Table 13: Transfer learning performance w.r.t. EHR (1) on molecular graphs with shared features.
Testing
Training
ZINC-16
molhiv-16
code2-22
ZINC-16
91. 91.1e1a
19.0to.
19.8
mo
39.8Lo.o
95.32o.
58.2
code2-22
4.6
4.6
95.7
Table 14: Transfer learning performance w.r.t. EHR (1) on labeled graphs with different features.
Inference times on CPU In Table 15 we report the inference running times of GELATO when on CPU rather than on GPU. Clearly, this results in slower inference times (by up an order of magnitude). However, inference with GELATO remains faster than other ML-based methods that return matchings, especially for larger graphs. Finally, we remark that runtime considerations are heavily dependent on the system at hand.
We report the training times for all considered learning-basd approaches. Ta- ble 16 provides the total runtimes of the complete training process for each method using the setups described in Section F. The reported times include both model training and the evaluation conducted during training. Note that variation in runtimes across methods is also influenced by author- proposed default parameter settings, the use of mechanisms such as early stopping, and whether a method sup- ports native parallelization.
Training times
27

---

Published as a conference paper at ICLR 2026
Method
AIDS
LINUX
IMDB-16 ZINC-16
molhiv-16 code2-22
GPU (H100)
3.2+o.2
2.9+o.1
3.6+o.2 24.7+
4.2+o.2 27.1=0.1
4.1+o.1
5.3+
CPU
11.5+a.1
8.2+0.2
24.9
61.2+o.1
Table 15: Average inference runtime per graph pair (ms) on GPU and CPU.
Overall, GELATO requires lower training times compared to the other ML-based methods that return solutions, i.e. MATA ", GEDGNN and GEDHOT.
Method
AIDS
LINUX
IMDB-16 ZINC-16 molhiv-16 code2-22
GREED
929
610
2342
2188
2885
1582
GRAPHEDX
2806
6743
523
3820
7800
4962
MATA *
7592
7993
11349
8247
15738
75007
GEDGNN
26852
29564
13900
49694
57057
83584
GEDHOT
22148
36353
14523
36506
44731
56648
GELATO
5422
4760
7850
9194
11979
7216
Table 16: Total training runtime for the ML-bbaed methods (s).
I USE OF LARGE LANGUAGE MODELS
Large Language Models have been used while writing this paper to polish writing (e.g., grammar, spelling, word choice). Moreover, they have been used to write parts of the code (e.g. parsing files, vectorizing tensor operations) used for the experiments.
28


Reviews:
[{"review_id": "bsBdwHRPiL", "reviewer": "Reviewer_W2sn", "summary": "In this paper, the authors present Gelato, an RL agent framework for solving graph edit distance. The authors first formulate the editing problem as a matching problem, and then train an RL agent to assign matched node pairs sequentially. The experimental evaluation shows that the proposed RL framework outperforms existing non-RL learning methods.", "questions": "* I will be happy to reconsider this manuscript if the authors could provide more discussion with the relevant work, [Liu et al: Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching](https://openreview.net/pdf?id=QjQibO3scV_)\n* What will the performance look like if the methodology in Liu et al. is directly applied to GED learning?\n* If I understand it correctly, different models are trained on different datasets. What will the accuracy look like if a model is trained on, say, the AIDS dataset and tested on other datasets? Is it possible to plot a confusion matrix to report the generalization ability? This question is important because the agent is learning the QAP, and we should expect it to generalize with such a general form.\n* Is it possible to train a general agent by mixing multiple training datasets?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "* This paper is well written with a self-contained story.\n* The evaluation on various datasets demonstrates the utility of the proposed RL method, and the empirical improvements over existing methods are impressive.", "weaknesses": "* This manuscript overlooks an important prior work, [Liu et al: Revocable Deep Reinforcement Learning with Affinity Regularization for Outlier-Robust Graph Matching](https://openreview.net/pdf?id=QjQibO3scV_). Liu et al presented an RL framework for the QAP form of graph matching, which is also used in Gelato. Though the underlying application and datasets are different, the methodologies of both papers seem relevant. I will be more convinced of the contribution and novelty of this paper if the authors can show the technical differences, unique innovations, and insights compared to Liu et al.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wpoAJ0Y2ow", "reviewer": "Reviewer_F8dj", "summary": "This paper addresses the problem of Graph Edit Distance (GED) estimation by framing it as a sequential decision-making task. The authors propose GELATO, an autoregressive framework built on a GNN backbone, in which a graph matching solution is incrementally constructed step-by-step. In line with classical search-based algorithms for GED, the method introduces a dynamic programming–style decomposition of the problem, where partial matchings and their induced subproblems are reduced while preserving equivalence to the optimal solution set. The model is trained using node-level matching supervision and evaluated on several benchmark datasets, with experiments demonstrating improved generalization to larger graph sizes compared to some previous learning-based GED predictors.", "questions": "Please refer to the weaknesses for some questions.  \n\n\nIn addition,  I would like to better understand the practical utility and trade-offs of using an autoregressive approach as opposed to existing one-shot GED predictors. In general, one would expect autoregressive inference to incur higher computational cost, due to stepwise decoding and possible sensitivity to early decisions that may require techniques such as parallel beam search. While the ability to produce interpretable edit paths is a meaningful benefit, the paper does not clearly analyze what is gained and what is sacrificed in moving from one-shot estimation to autoregressive decoding. \n\nIn the reported timing comparisons, the authors attribute improved runtime to the fact that GELATO is “GPU-friendly,” whereas several baselines are not. This makes it difficult to disentangle architectural advantages of the autoregressive formulation from implementation differences. It is desirable to have a more direct study of these trade-offs including inference latency, resource usage, prediction accuracy improvements, etc. \n\nAlso, is there any reason why GraphEDX (Jain et al., 2024) has been omitted as a baseline. I would  consider it a decent exemplar of GPU-frienly one-shot predictor for comparison.  I suspect  GraphEDX does not scale well to larger graphs. However, a comparison on in-distribution graphs, highlighting accuracy vs. interpretability vs. inference costm, would be intersting.\n\nMinor comment: The authors highlight Jain et al., 2024 in the dataset isomorphism issue, but perhaps [1] would be a better reference in this regard. \n\n[1] Position: Graph Matching Systems Deserve Better Benchmarks. In Forty-second International Conference on Machine Learning Position Paper Track.\n\n\n\nOverall, I am positive on the motivation and approach of this paper, but have questions about the neural architecture design and trade-offs around the autoregressive design.", "limitations": "", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Strengths**\n\n- GED prediction often requires resolving symmetries and tie-breaking, further exacerbated by expressivity limitations of standard GNNs. This make the sequential decision framework, in line with  traditional heuristic search methods for GED, well-motivated. I also like the analysis showing that the reduced subproblem maintains equivalence of optimal solutions. \n\n-  Despite relying on explicit node-level matching supervision, which would usually count as a disadvantage, the paper shows robust generalization to larger graphs, which confirms practical utility of the approach.\n\n- By generating incremental matchings, the method offers interpretability advantages compared to one-shot predictors.", "weaknesses": "**Weaknesses**\n\n1.  The statement of Theorem 1 differs between the main paper and the appendix, and the notation in the main paper version is unclear. Since the theorem plays a central conceptual role, the paper would benefit from, aligning the statements across sections, clarifying notation, and adding a brief intuitive explanation (2–3 sentences) to the main body to highlight why equivalence is preserved.\n\n2. The architecture section does not clearly specify how partial matchingsare represented internally.  Do cross-graph edges introduced by a partial matching participate in message passing? If so, the graph structure is dynamically modified, which may have unintended representational implications.  If not, how are embeddings of partially matched nodes coupled or tied together?  Similarly, the implementation of the reduce operation in the neural pipeline is not clearly described.\n\n3. The choice of a 128-dimensional embedding for comparatively small graphs is not well justified, since the node embedding matrix is larger than the adjacency matrix!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h8qZT3caDF", "reviewer": "Reviewer_eo4E", "summary": "GELATO solves the graph edit distance (GED) problem\nby reformulating it as a sequential decision making process.\nThe graph neural network (GNN) is trained to predict one matching node pair at a time,\ngiven a partially matched pair of graphs,\nwith efficiency and soundness considerations such as\noverlapping state space and automorphisms,\nallowing for autoregressive inference to generate the full matching\nto compute the GED.\nComprehensive experiments show that GELATO achieves high solution quality compared to baselines,\nwhile taking less time, especially compared to approaches with an non-neural matching/search component.\nFurther analyses include generalization on larger graphs, robustness under limited supervision and ablations.", "questions": "1. What is the basis for selection of 3 baselines out of 8 in Section 5.2 / Figure 5?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The paper proposes a novel method, with well-motivated and carefully-considered components.\n\nThe experiments are comprehensive and the results are strong.\n\nThe experiments support the main motivations for this research,\ne.g. generalization to larger graphs and faster inference times.", "weaknesses": "While the paper is well-written overall,\nsome more-involved parts of the method could be better explained,\nespecially the state-space reduction and automorphism considerations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "N77qBSPxjf", "reviewer": "Reviewer_jqC1", "summary": "This paper proposes a novel method to approximate the graph edit distance ( GED). The major contribution is the use of a neural network to solve the GED sequentially.", "questions": "No further comments.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The proposed method is interesting as it allows to construct the edit paths.", "weaknesses": "The designation of “autoregressive” seems not to be correct, or at best not well justified. The proposed method can be clearly defined as sequential. At the end, it uses roughly a search-based strategy in the same spirit as A* and related methods.\n\nA major issue is that there are no guarantees of optimality for the proposed method. Moreover, it is well known that sequential optimization is non-optimal in general.\n\nWhile the authors provide some theoretical results, they cannot be explored in practice. For instance, Lemma 1, which motivates the greedy selection, cannot be exploited because the optimal function cannot be computed in practice, making these results intractable.\n\nIt would be relevant to provide a comprehensive ablation study beyond Section 5.3. For instance, it is not clear if the batch normalization and the residual connections are beneficial or not. Moreover, the paper does not justify the choice of the values of most hyperparameters, such as the number of layers of the GIN set to 5, embedding dimension, number of randomly selected pairs, resembling with k=32...\n\nThe computational complexity needs to be studied in depth. The authors mainly present the inference runtime, but not the training runtime.\n\nThe expression “Any state is also a terminal state” is misleading.\n\nThere are several spelling and grammatical errors that can be easily identified and corrected, such as “We define a the set…”, as well as GINE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)