GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
Authors: Samidha Verma
Arushi Goyal
Ananya Mathur
Ankit Anand
Sayan Ranu
Venue: ICML 2025 poster (2025)
Keywords: Graph Edit Distance
Large Language Model
Code Discovery
Cross-domain generalization
Interpretability
Primary area: general_machine_learning->sequential_network_and_time_series_modeling
TL;DR: GRAIL leverages LLMs and automated prompt engineering, guided by an evolutionary algorithm, to generate programs for accurate, cross-domain generalizable, and interpretable Graph Edit Distance computation.

Abstract: Graph Edit Distance (GED) is a widely used metric for measuring similarity between two graphs. Computing the optimal GED is NP-hard, leading to the development of various neural and non-neural heuristics. While neural methods have achieved improved approximation quality compared to non-neural approaches, they face significant challenges: (1) They require large amounts of ground truth data, which is itself NP-hard to compute. (2) They operate as black boxes, offering limited interpretability. (3) They lack cross-domain generalization, necessitating expensive retraining for each new dataset. We address these limitations with GRAIL, introducing a paradigm shift in this domain. Instead of training a neural model to predict GED, GRAIL employs a novel combination of large language models (LLMs) and automated prompt tuning to generate a *program* that is used to compute GED. This shift from predicting GED to generating programs imparts various advantages, including end-to-end interpretability and an autonomous self-evolutionary learning mechanism without ground-truth supervision. Extensive experiments on seven datasets confirm that GRAIL not only surpasses state-of-the-art GED approximation methods in prediction quality but also achieves robust cross-domain generalization across diverse graph distributions.

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
Samidha Verma Arushi Goyal? * Ananya Mathur
Ankit Anand
Sayan Ranu !2
Abstract
Input graph pair
Cost-1
Cost #2
Graph Edit Distance (GED) is a widely used met- ric for measuring similarity between two graphs. Computing the optimal GED is NP-hard, leading to the development of various neural and non- neural heuristics. While neural methods have achieved improved approximation quality com- pared to non-neural approaches, they face signifi- cant challenges: (1) They require large amounts of ground truth data, which itself NP-hard to compute. (2) They operate as black boxes, offer- ing limited interpretability. (3) They lack cross- domain generalization, necessitating expensive retraining for each new dataset. We address these limitations with GRAIL, introducing a paradigm shift in this domain. Instead of training a neural model to predict GED, GRAIL employs a novel combination of large language models (LLMs) and automated prompt tuning to generate a pro- gram that is used to compute GED. This shift from predicting GED to generating programs imparts various advantages, including end-to-end inter- pretability and an autonomous self-evolutionary learning mechanism without ground-truth super- vision. Extensive experiments on seven datasets confirm that GRAIL not only surpasses state-of- the-art GED approximation methods in prediction quality but also achieves robust cross-domain gen- eralization across diverse graph distributions.
Node substitution
Edge Node insertion
Figure 1. Illustration of edit path from 9i to with GED 3.
and edge labels. Fig. 1 presents an example. Computing GED is NP-hard (Ranjan et al., 2022) and APX-hard (Fan et al., 2020; Bommakanti et al., 2024a). Owing to its nu- merous applications (Blumenthal, 2019; Ranu al., 2014; Bommakanti al., 2024b), polynomial-time heuristics designed in practice.
1.1. Existing Works and their Limitations
Existing heuristics to approximate GED can be broadly grouped into two paradigms: non-neural and neural.
Non-Neural Methods:
Computing GED exactly or approx- imating it within provable bounds is challenging, leading to the development of various heuristic approaches (Blumen- thal et al., 2020). These methods utilize techniques such as transformations to the linear sum assignment (NODE (Justice & Hero, 2006), BRANCH-TICHE Gamper, 2018)), mixed integer programming (MIP) (LP- GED-FF (Lerouge et al., 2017a), ADJ-IP (Justice & Hero, 2006), COMPACT-MIP (Blumenthal & Gamper, 2020)), and local search methods (IPFP (Leordeanu et al., 2009)).
(Blumenthal &
Unlike black-box neural methods, these approaches not only approximate GED but also provide the edit path, offering in- sights into structural modifications. However, their approxi- mation quality is often inferior to neural approaches (Ranjan et al., 2022; Bai et al., 2019), driving the shift toward neural architectures. Additionally, these methods often involve solving complex optimization problems, such as MIP, to derive node alignments between graphs
1. Introduction and Related Work
Graph Edit Distance (GED) quantifies the dissimilarity be- tween two graphs as the minimum number of edits required to transform graph into another. An edit may com- prise adding deleting nodes and edges or replacing node
Neural Methods: Recent advancements favor graph neural networks (GNNs) for GED approximation due to their supe- rior accuracy over non-neural methods (Ranjan et al., 2022: Zhang et al., 2021; Bai et al., 2019; Piao al., 2023; Wang et al., 2021; Zhuo & Tan, 2022; Jain et al., 2024; Bai et al., 2020; Doan et al., 2021; Li et al., 2019). These models take pairs of graphs with known GED values as input and are trained to predict GED distances. However, since computing true GED is NP-hard, training these models efficiently for large graphs or datasets remains a significant challenge.
"qqual contribution Yardi School of Artificial Intelligence, IIT Delhi, India 'Department of Computer Science and Engincering, ITT Delhi, India Google DeepMind, Montreal, Canada. Corre- spondence to: Samidha Verma < samidha, verma @ scai. inn. Arushi Goyal <cs5200418 ac. Mathur <cs5200416 1er004416@idd.a... at...ac.iin.... in>> Ankit Anand <anan- dank google.com>. comm>, Sayan Ranu <syaanaanu @ in.>..
Ananya
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGenrated Code
Name
End-to-end interpretable
Cross-domain generalization
Non-reliant on NP-hard
Accurate
supervision
GREED (Ranjan et al., 2022)
X
GEDGNN (Piao et al., 2023)
O
НºN (Zhang et al., 2021)
X
X
ERIC (Zhuo& & Tan, 2022)
X
X
GRAPHEDX (Jain et ul., 2024)
X
X
GRAPHOTSIM (Doan ct al., 2021)
X
X
GRAPHSIM (Bai ct al., 2020)
X
X
TAGSIM (Bai & Zhao, 2021)
X
X
GMN (I.i et al., 2019)
X
X
GENN-A (Wang et al., 2021)
O
X
X
SIMGNN (Bai et al., 2019)
X
Non-ncural approaches (Blumenthal et al., 2020)
GRAIL
Table 1. Summary of the drawbacks of existing algorithms and the proposed algorithm GRAIL. v indicates satisfaction of desirable property, X indicates -atsssiifaction, and O indicates partial satisfaction. While GEDGNN, GENN-A", traditional non-neura approaches achieve partial interpreabiility by providing edit paths corresponding to the GED, they do not explain the semantic reasoning behind these paths. In contrast, GRAIL achieves end-to-end interpretability through code-based output, where each decision can be traced to its underlying logical reasoning. Non-neural approaches utilize unsupervised learning, enabling cross-domain generalization. However, their approximation errors are significantly higher on average than neural approaches, as demonstrated in $
Among the leading algorithms, GREED (Ranjan et al., 2022) employs siamese GNNs with an inductive bias to learn GED while preserving its metric properties. M2NN (Zhang et al., 2021) utilizes a hierarchical hypergraph matching network for graph similarity learning. Other state-of-the-art approaches, such as (Piao al., 2023), ERIC (Zhuo & Tan, 2022), and GraphEdX (Jain al.. 2024), further explore GNN-based architectures for GED prediction. Despite supe- rior approximation quality, these methods suffer from key limitations given below.
distributions lead to increased approximation error. This limitation necessitates generating ground-truth data and training separate models for each dataset. Given that gen- erating training data NP-hard, this pipeline becomes highly resource-intensive.
1.2. Contributions
We address the above-outlined limitations through GRAIL: Graph Edit Distance and Node Alignment using LLM- Generated Code. GRAIL introduces paradigm shift in the domain of GED approximations through the following novel innovations.
Lack of interpretability: Most neural methods only pre- dict the GED and not the corresponding edit path. The edit path is essential for various applications such as identify- ing functions of protein complexes (Singh et al., 2008), image alignment (Conte et al., 2003), and uncovering gene-drug regulatory pathways (Chen al., 2019). Few neural methods that predict the edit path (Piao et al., 2023; Wang et al., 2021) rely expensive ground truth compu- tation, which can only be attained for very small graphs (Nz 10 nodes). For larger graphs, random edits are made to synthetic graphs to generate the training samples.
Problem formulation: We shift the learning objective from approximating GED to learning program that ap- proximates GED. This reformulation provides end-to-end interpretabilityy as each algorithmic decision can traced to its underlying logical reasoning. Moreover, by elevat- ing the output to higher level of abstraction through code generation, achieve superior generalization across datasets, domains, graph sizes, and label distributions.
LLM-guided program discovery: The algorithmic framework of GRAIL is grounded on three novel design choices. First, we map the problem of approximating GED to maximum weight bipartite matching, where the weights of the bipartite graph are computed using an LLM- generated program. Second, the prompt provided the L.M is tuned through evolutionary algorithm (Romera- Paredes et al., 2024). Third, our prompt-tuning method- ology eliminates the need for ground-truth GED data by designing prediction framework where the prediction is guaranteed to be an upper bound to the true GED. Hence, minimizing the upper-bound equivalent to minimizing the approximation error, thereby overcoming critical bottleneck of existing neural approaches.
NP-hard training data: The training dataset for neural methods consists of graph pairs and their true GED. GED computation is NP-hard. Therefore, generating this train- ing data is prohibitively expensive and restricted to small graphs only. Hence, approximation error deteriorates on larger graphs. (Ranjan et al., 2022)
Lack of generalization: Neural GED approximators struggle to generalize across datasets. For datasets from different domains (e.g., chemical compounds vs. function- call graphs), the node label sets often differ. Since the number of parameters in a GNN depends on the feature dimensions of the nodes, GNNs fail to generalize across domains. Even within the same domain, as demonstrated later in $5, distribution shifts in structural and node label
Comprehensive Empirical Evaluation: Through ex- tensive experiments across 6 datasets, we demonstrate
2

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
that GRAIL discovers foundational code-based heuristics. Specifically, these heuristics not only surpass the state-of- the-art methods in GED computation but also exhibit gen- eralization across diverse datasets and domains. This cru- cial feature eliminates the need for costly dataset-specific training, thereby addressing a significant limitation of existing neural algorithms.
Definition 4 (Graph edit distance (GED)), The GED be-
tween graphs In and G2 is the minimum GED across all possible node mappings.
GED (2) min (GI, VTEM
(I)
Here, M denotes the universe of all possible mappings.
2. Preliminaries and Problem Formulation
The problem is hard (NP-hard and APX-hard) since the
cardinality of M is nl, where max ( [21].
Definition 1 (Graph), We represent node-labeled undi-
rected graph as g G(V, C, f) where V = {11, [11v] } is the set of nodes, & C V x V is the edge set and L V + Σ is a labeling function that maps nodes to labels, where E is the set of all labels.
The problem of learning to code for approximating GED is defined as follows.
Problem 1 (Learning to code for GED), Given a set of train- ing graph pairs T 1191, (1),, (G2, (2), (Gnrg)) }. learn program P (Ge, (i) + Z+ that takes as input graph pair (Gr, ( E TT, and outputs non-negative inte- gral distance that minimizes
In unlabeled graphs, all nodes are assigned the same label. Definition 2 (Node Mapping). A node mapping between two graphs Gi and G2, each consisting of n nodes, refers to a bijection π. : V1= + V2. where every node v E V1 is uniquely mapped to node TTV) E V2.
Σ P(G.,9)) GED 9D1
(2)
Extension to graphs of difffernt sizes: When dealing with two graphs 9j and 92 with different numbers of nodes, nı and n2 respectively, such that n1 < n2, the smaller graph Gi can extended to match the size of G2 by introducing ni - n2 additional isolated dummy nodes. These new nodes are labeled with unique identifier, c, indicating that they are placeholders with no connections. From this point on- ward, we assume that any pair of graphs in consideration have an equal number of nodes, with smaller graphs being augmented by dummy nodes as necessary.
Note that our training set consists solely of graph pairs, without requiring their true GED, which is computationally prohibitive due to its NP-hardness. As we will elaborate in the next section, we identify polynomial-ting time computable upper bounds for the true GED and reformulate the opti- mization objective to minimize this upper bound. This au- tonomous self-evolutionary learning mechanism overcomes a significant limitation of neural GED approximators.
Definition 3 (GED under a node mapping r). Given a node mapping n, the cost function for calculating graph edit distance between graphs 91 EV L1) and G2(V2, E2, fz) is expressed as:
3. Approximation Strategy
The true GED corresponds to the minimum distance across all possible node mappings (Def. 4). However, enumerating all such mappings is computationally infeasible due to its factorial complexity relative to graph size. To overcome this challenge, we approximate the GED by evaluating a small subset of mappings (e.g., 15) and selecting the minimum distance among them. These mappings are generated by programs derived from the LLM, as detailed in $ 4. Impor- tantly, this approximated GED serves as an upper bound to the true GED, as considers only a subset of all possible node mappings.
GED,(GI,9)) G2) = Σ (1) # (2(())))))
ME
Σ Σ (ei((11) v2) e (v22))
2
1IEV DE
where, v) returns if the edge (u, E & in graph Gi, 0 otherwise.
I(A) is the indicator function, which is 1 if the condition holds, and otherwise.
3.1. Node Mappings through Bipartite Matching
Interpretation of edit path from node mapping: The first part of the equation captures node mismatches where it evaluates the label differences between nodes in Gi and Go. Mapping a dummy node to a real node (or vice versa) results in label mismatch, reflecting the insertion or deletion of node, while mismatch between real nodes denotes substitution. The second part of the equation captures edge mismatches. Specifically, if an existing edge in Gi (i.c., ei (e), 12) = 1) is mapped to a non-existing edge in O2 (i.e.. e2( (11), (v2)) = 0) or vice versa, the cost is representing edge deletion and insertion, respectively.
The task of mapping nodes between two graphs can be approximated as Maximum Weight Bipartite Matching.
Definition 5 (Maximum Weight Bipartite Matching). Given a weighted bipartite graph B(V, E, W) with node sets v and U, and weighted edge set E V x U + R where W : - Th assigns weights to edges, find a subset of edges E C E that (1) induces a bijection between nodes in V and nodes in U, and (2) maximizes the total weight of the mapped edges, i.e., Eesg- W(e). Here, W(e) represents the weight of edge e.
3

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Gennrated Code
Program
GED Approximation Module
LLM
CODE/
Compute weight matrix with progrsm
Fully connected weighted bipertite graph
<G1, G2
Filter
Executes
2. Terminates within time limit
For each graph training
Start
Prompt
Maximum weight bipartite matching
Top-b programs sampled randomly selected islands
Insert
Program pool
CODE/
Mallgreey has converged?
Island
Ieland
Island 2
Yes
Island 5
Island
Answer set (Greedy [Alg 1) output on program pool)
Figure Pipeline of GRAIL..
Maximum weight bipartite matching can be solved op- timally in polynomial time using the Hungarian algo- rithm (Kuhn, 1955). Additionally, several heuristics have been proposed, such as the Hoperoft-Kary Algo- rithm (Hoperoft & Karp. 1973), the Neighbor-biased map- per (He & Singh, 2006), or greedy selection of the highest- weight edges while maintaining the one-to-one mapping constraint. We use the notation xB)) to denote the node mapping obtained from B.
3.2. Budget-constraine Selection of Node Maps
Let = (P,, .Pm) be the set of programs generated by the LLM and N (P.)) denote the mapping produced by pro- gram P. D. From Def. 4, we know GED=(P)) (91, 92) Z GED 92), i.e., each program provides upper bound the true GED. The smaller the upper bound, the closer are to the true GED. Our goal is to select subset A C D of b programs that minimize the cumulative upper bounds across all train graph pairs. < |D] denotes the maximum number of mappings we are allowed to evaluate. These programs will finally be used during inference for unseen graph pairs. Formally, this presents us with the following optimization problem.
To use maximum weight bipartite matching for ap- proximating GED, for given graphs E and C2(V2, &2, C2), construct a fully connected, weighted bipartite graph B(V1, V2, E, W) where edge set & ((11,2) U2) U1 E V1, 02 E V23'. The weight of an edge U2) is set based on some policy, which should ideally reflect the probability of U2 being mapped to 02 in the opti- mal GED mapping. Maximum weight bipartite matching is then performed on B using any standard algorithm, and the GED is computed based the mapping π (B).
Problem 3 (Map Selection). Given programs D
[P1, ... Pm), }, select A such that:
A" arg min {J(A)} VACD, (Al=b
(4)
J(A) Σ
min
(2),
(5)
PEA
(GI
The quality of the mapping with respect to approximating GED, therefore, rests on the edge weights in the bipartite graph. We will use an LLM to learn the policy, in the form of a program, with the following minimization objective.
((A) quantifies the quality of the subset of mappings in A.
Theorem 3.1. Prob. 3 is NP-hard.
Proof. The proposed optimization problem reduces to the
Problem 2 (Weight Matrix Generation). Given train set T ((G..g)).-- (Gn, G.) generate a program P that takes as input each pair (9t, 9 E T and outputs a corre- sponding weight matrix W, IR (gllix
Set Cover problem (Cormen et al., 2009), rendering it NP- hard. For the formal proof, please refer App. A.2.1. O
Owing to NP-hardness, finding the optimal subset of mappings A" is not feasible in polynomial time. We establish that J(A) is monotonic and submodular (refer App. A.2.2). This enables us to use the greedy hill-climbing algorithm (Alg. 1) select a sub-optimal but reasonable subset of programs, Agreedy-
x Vil minimizing
Σ (GE.))
Here, Wi denotes the weight of edge vy) where Us E V. to node Vj V/. T(P) denotes the mapping generated by maximum weight bipartite matching on the bipartite graph formed by P.
4. GRAIL: Proposed Methodology
Recall, assume the smaller graph is padded with dummy nodes to ensure [V] = |)2)
In & 6, we decompose Prob. into two subproblems: weight selection bipartite graph (Prob. 2) and budget-

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
constrained map selection (Prob. 3). Prob. 3 is solved (ap- proximately) using Alg. 1. Hence, to complete our approxi- mation scheme, we need to solve Prob. 2.
the corresponding nodes share the same label, i.e., 2 (v:) (z(";) for e V1 and vy E V2, and [i other- wise. Additionally, the header of the function that the LLM needs to generate is explicitly provided.
Fig. 2 presents the pipeline of GRAIL. The process begins with an initial prompt that specifies a trivial program for weight selection, and the LLM is tasked with improving this program for GED computation via bipartite matching (details in 4.1). Each newly generated program is veri- fied for syntactic correctness and must terminate within predefined time limit. If these criteria are met, the program is evaluated on the training set of graph pairs and added to the program pool along with its score, which reflects its marginal contribution to I [Agreeddy). A new prompt is then constructed by sampling the highest-scoring programs from the current pool. The LLM refines these programs, generating new candidates further enhance performance. These newly generated programs are evaluated and added to the pool following the same procedure. This iterative process continues until J (Agreedy converges, ensuring that improvements stabilize across iterations. The following sections detail each step of this process.
The initial prompt includes a trivial pro- gram where Ve, E Vi, 0j E V2, [[i = O. In subsequent iterations, k high-scoring programs are sampled for inclu- sion in the prompt, where k is a hyper-parameter. The scoring and sampling methodology are described in $ 4.2.
Top-k Programs:
4.2. Prompt Tuning
Filter: After program is generated, it undergoes a filtering step to verify that it executes and terminates on training graph pairs within a predefined time limit. Programs that fail this filter are discarded. For those that pass, we compute their score and add them our program database DD
Score computation: In Prob. 3, we take the minimum GED across all selected mappings in the answer set. A program's 's utility, therefore, depends on how it complements other programs in the answer set. Hence, we define its score as the marginal contribution to the objective function J (Agresdy). Specifically, we execute Alg. on the current pool of programs, where A {PI,.... P.) represents the subset of programs selected up to iteration i. If program P is added in the i 1-th iteration due to providing the highest marginal contribution, its score is computed as:
4.1. Prompt Specification
The prompt is computer program consisting of three distinct components: (1) the problem description, (2) the task specification, and (3) the top-k programs generated so far based on a scoring function. A sample prompt is provided in Fig. 4 in the Appendix. Here, is set to 2.
score - - ((A)
(AA(()))
(6)
The problem description includes the definition of GED, which is embedded as a comment within the program (refer to Fig. 4).
Problem Description:
Evolutionary program selection: The next stage involves selecting programs from the pool to be included in the next prompt. We use the evolutionary algorithm proposed in Funsearch (Romera-Paredee programs generated by LLM. Since the programs evolve through mutations introduced by the LLM, the selection mechanism optimizes two distinct objectives. First, the sampled programs should have high scores. Second, the sampled programs should have smaller length improving the interpretability of generated programs.
al., 2024) for evolving our
Task Specification: The LLM's task is defined through a comment specifying the inputs it should expect and the required output. The output is a weight matrix W e [x for the bipartite graph, where Wii. J] quantifies the strength of mapping node v, E V1 to node by E V/2 in the context of GED computation. The input includes the graph pair represented by their adjacency matrices and an initial weight matrix W E | with the same dimensions and semantics as the output. During execution, the input weight matrix wo is initialized such that [i,] = if
The evolutionary algorithm follows the islands model (Gor- don & Whitley, 1993). Specifically, the population of ex- isting programs is partitioned into islands, where is hyperparameter. Initially, all islands are empty. When a program is added to the pool, it is randomly assigned to an island. Subsequently, to decide which k programs are included in the prompt, we randomly choose an island. Sim- ilar to Funsearch, the programs within each island are then split into clusters depending on score. After selecting the island, clusters are selected based softmax distribution on score. Within clusters, the programs are selected based on length (smaller is better). Hence, the program selection mechanism for the next prompt favors higher scores and shorter lengths. More details of the process can be found in Comera-Pareder et al. (2024). The LLM is then tasked with
Algorithm 1 The greedy approach
Require:
Train data T (Ti,.... .T, where 7i (G., is a pair of graphs, budget
Ensure: solution set set Agrendy (ggresdy =
1: Agreedy t
2: while size((Areeed)) S b (within budget) do
3: p arg magg
(A(pgo)))) J [Apras U (P))}
4: Agready Agrendy U {
5: Return Agrondy
5

---

GRAIL: Graph Edit Distance and Node Alignment using L.M-GGenrated Code
further improving these programs.
Table 2. Datasets used for benchmarking GRAIL.
With this design, each island evolves independently. To enable fertilizziii among islands, we periodically discard half of the islands which have the lowest score. The discarded islands are replaced by iterating over each of the surviving islands, and selecting its best program to seed the replacement population.
Name
Graphs
Avg
[
Avg [F]
labels Domain
ogbg-molhiv
39650
24
52
119
Molecules
ogbg-molpcha
436313
26
56
119
Molecules
oghg-code2
139468
37
72
97
Software
AIDS
700
29
Molecules
Linux
1000
7
Unlabeled Software
IMDB
1500
13
65
Unlabeled Movies
ogbg-ppa
39650
243.4
2226.1
Unlabeled Protein
4.3. Training and Inference
Training: As illustrated in Fig. 2, each iteration involves generating a program, scoring it, and assigning it to an island before constructing and executing a new prompt. The quality of the program pool is measured by J (Agreedy) serving as an analog to a loss function in our framework. This iterative process continues until J (Agreedy) converges, defined as its improvement over the last iterations falling below predefined threshold, akin to the patience parameter in neural model training.
Morris et al. (2020), the other four datasets are made avail-
able by Hu et al. (2021).
Benchmark Algorithms: The recent baselines are listed in Table 1. From this set, we benchmark GRAIL against GREED (Ranjan et al., 2022), GEDGNN (Piao et al., 2023), ERIC (Zhuo & Tan, 2022), GRAPHEDX (Jain et al., 2024) and HºMN (Zhang et al., 2021). We omit SIMGNN, GRAPHOTSIM, GMN, GRAPHSIM, TAGSIM and GENN- A*, since they have been outperformed by the considered baselines of GREED, GRAPHEDX, GEDGNN and ERIC. Details of setup are provided in App. A.I.
Overall, GRAIL. seeks to minimize the upper bound of GED. With this strategy, we bypass the need for ground-truth GED data, a key bottleneck in training neural approaches. This unique design is not feasible in neural pipelines since the prediction
Among non-neural baselines we include the best-performing heuristics from the benchmarking study in Blumenthal et al. (2020): namely, LP-GED-F2, COMPACT-MIP, ADJ-IP, BRANCH-TIGHT, NODE and IPFP.
either side of the true distance.
During inference, we directly return I (Agreedy) for the given input graph pair. Note that since the output of the training phase is executable code, inference is CPU- bound, enabling it to operate in low-resource environments.
Inference:
GRAIL-MIX is variant of GRAIL trained on mixture of graph pairs from multiple datasets, while maintaining the same training set size as GRAIL. The programs discovered by GRAIL-MIX are used for inference across all datasets to assess whether a single training instance can generalize across domains, eliminating dataset-specific training.
5. Experiments
In this section, we benchmark GRAIL and establish that:
Approximation Error: GRAIL achieves low approxi- mation errors and consistently ranks among the top al- gorithms across all six datasets. Notably, unlike neural approximators, it achieves this performance without rely- ing on extensive NP-hard ground-truth GED training data.
Train- Validation-Test Split: To construct the test set for particular dataset, we select 1000 graph pairs uniformly at random and compute their true GED. The procedure for computing the ground truth GED is discussed in App. 1.4.1. The training and validation sets depend on the algorithm.
Foundational heuristies: GRAIL breaks new ground by generating heuristics that generalize across diverse datasets, including those featuring unseen node labels and varying graph sizes. This exceptional adaptability sets GRAIL apart, as no existing neural GED approximators have demonstrated such versatility.
Neural Algorithms: All neural approaches are trained on 10,000 graph pairs per dataset. This training time exceeds 15 days for certain datasets (see Fig. 6a).
GRAIL and GRAIL-MIX: GRAIL is trained with only
1. 1,000 graph pairs per dataset. As discussed already, GRAIL does not require ground-truth GED. In GRAIL- MIX, we choose 166 graph pairs from each of the datasets listed in Table 2 except ogbg-ppa. Both GRAIL and GRAIL-MIX do not use validation set.
The codebase of GRAIL and the programs generated for the various datasets are available at ht https: / //git/tthh///// com/ wwleideiiiiii itdd/dddddaarr
5.1. Experiment Setup
Non-Neural Baselines: These unsupervised algorithms do not require any training or validation datasets.
Gem Pro has been used for all experiments. Fur- ther details of the software and hardware environments and hyper-parameters used for GRAIL are listed in App. 1. Datasets: Table 2 summarizes the datasets used in this study. A detailed description of the data semantics is included in App. A.4. While AIDS, Linux and IMDB are obtained from
We employ two metrics: Root Mean Squared Error (RMSE) and Exact Match Ratio (EMR). EMR quantifies the proportion of test graph pairs for which the predicted GED exactly matches the true GED. (See App. A.4.2 for details.)
Metrics:
6

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Gennrated Code
Table 3. RMSE Comparison: The top-3 lowest RMSES per datasct highlighted in green shades, with darker shades denoting better
RMSE. An asterisk (*) marks the better value when additional decimal places resolve ties after rounding to two decimal places.
Type
Methods
AIDS
Linux
IMDB
ogbg-molhiv
ogbg-code2
ogbg-molpeha
Avg. Rank
LLM
GRAIL
0.57
0.55
2.96*
3.18
GRAIL-MIX
0.64
0.11
0.53
2,96
4.10
3.40
2.17
GREED
0.61
4.8
3.02
5.52
2.48
3.5
GEDGNN
0.92
0.29
4.43
1.75
16.68
4.58
5
Neural
ERIC
1,08
0.30
42.44
3.56
17.55
2.79
6.5
HºMN
1.14
0.60
57.8
12.01
11.96
5.50
8.33
GRAPHEDX
0,78
0.27
32.36
14.14
21.46
10.01
8.33
ADJ-IP
0.85
0.50
42.18
10.21
14.94
8.06
7.33
NODE
2.71
1.24
61.03
4.97
4.94
8.17
Non Neural LP-GED-F2
1.96
0.23
55.26
12.86
16.03
10.30
8.83
BRANCH
3.31
2.45
7.36
9.86
12.64
11.31
9.33
COMPACT-MIP
2.69
65.88
19.46
8.81
10
IPFP
4.18
2.29
69.45
13.69
15.19
10.02
11.5
Table EMR Comparison: The top-3 highest EMRs per dataset are highlighted in green shades, with darker shades denoting better FMRs. The EMR values for GRAIL in App. (Table 9). We omit them here GRAII-MIX performs similarly datasets. For focused comparison, we only include the top-3 baselines from Table 3, since the remaining do not provide competitive performance. For
ties after rounding two decimals, asterisk (*) marks the higher value. Values in (0.99, are shown as
Methods
AIDS
Linux
IMDB
ogbg-molhiv
ogbg-code2
ogbg-molpeha
Avg. Rank
GRAIL-MIX
0.80
0.20
0.12
0.12
1.83
GREED
0.58
0.79
0.17
0.23
0.09
0.21
2.17
ERIC
0.37
0.92
0.08
0.21
0.01
0.18
2.83
GEDGNN
0.35
0.85
0.07
0.57
0.01
0.09
3.17
RMSE vs LLM Calls
2.3
Top-b
10.2
4000
Submodular
Avg. Upper Bound
10.0
Avg. Upper Bound
1.9
9.8
3000
1.7
RMSE
9.6
2000
1.3
9.2
1.1
1000
0.7
8.8
0.5
2.5. 5.0 7.5 10 12.5 15.017.520.0
GRAIL MIX
ADJ
NODE
LP GED F2
50
LLM Calls
100
250
Budget
(a) ogag-ppa
(b) AIDS
ACDS
Figure 3. (a) GRAIL-MIX at scale: Performance of GRAIL-MIX the ogbg-ppa dataset when compared the top-3 non-neural
baselines on the basis of average rank Table 3. (b) Impact of function budget on upper bound. (c) Impact of greedy submodular optimization on performance
set.
6. Approximation Strategy
functions. These foundation functions eliminate the need for dataset-specific training.
6.1. Empirical Analysis of Approximation Errors
Tables and 4 benchmark GRAIL in terms of RMSE and EMR. Several important observations emerge.
Third, GRAII.-MIX outperforms GRAIL in three datasets, indicating positive cross-dataset knowledge transfer.
First, GRAIL and GRAII--MIX comprehensively outperform the baselines despite using any ground truth for training. This is critical advantage as it saves time in expensive ground truth computation (Refer to Fig. 6a). The improve- ment is the highest in the IMDB dataset, which we specifi- cally analyze in & 6.4
Fourth, inspected why GRAIL significantly underper- formed in comparison to GREED for ogbg-molpcba dataset. We observed that adapting the neighborhood depth used for computing node similarities can substantially improve performance. GREED leverages jumping knowledge to com- bine node embeddings from depths to learn which depth is most effective for GED approxima- tion. In Tables and 4 GRAIL uses fixed topological depth across all nodes. When GRAIL adopts similar strategy of computing GEDS across multiple depths and selecting the
allowing an MLP
Second, the efficacy of GRAIL-MIX across datasets demon- strates that the discovered programs are universally appli- cable multiple datasets and can be called as foundation

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGenrated Code
Table 5. Intra-Domain Generalizability: RMSE of the best neural method, GREED, and GRAIL. Off-diagonal entries represent cross-
datasct performance. NA symbolizes that it's not possible to train a single model covering the train-test combination.
AIDS
ogbg-molhiv
ogbg-molpcha
Test set Train Set
GREED
GRAIL
GREED
GRAIL
GREED
GRAIL
AIDS
0.61
0.57
5.71
0.64
4,58
0.59
ogbg-molhiy
NA
3.02
3.02
2.96
3.86
2.89
ogbg-molpcha
NA
3.59
2.16
3.54
2.48
3.18
Table Inter-Domain Generalizability: Generalization GRAIL across domains, dataset sizes, and node label distributions by training on one dataset and measuring RMSE on others. Off-diagonal entries represent cross-dataset performance. The best two results for each test set(row) have been highlighted in shades green, with darker being better.
Test set Train set
AIDS
IMDB
Linux
ogbg-molhiv
ogbg-code2
ogbg-molpeba
AIDS
0.57
0.63
0.65
0.64
0.62
0.59
IMDB
0.88
0.55
0.88
0.78
0.74
0.87
Linux
0.18
0.22
0.13
0.24
0.16
0.24
oghg-molhiv
3.02
2,93
3.08
2.96
2.96
2.89
ogbg-code2
4.44
4.32
4.74
4.07
4.22
4.5
ogbg-molpcha
3.59
3.63
3.61
3.54
3.64
3.18
minimum the final estimate, its RMSE improves from 3.18 (depth 1) to 2.68 (depths 1,2.3), becoming competitive with GREED 's RMSE of 2.48. This suggests that dynami- cally adapting neighborhood depth can further improve the approximation quality of GRAI...
the ogbg datasets, making it impossible to derive com- mon feature space. GRAII. generalizes well across all train- test dataset pairs, while GREED struggles except for ogbg- molhiv and ogbg-molpeba. This is because both datasets are adopted from the same parent dataset MoleculeNet (Wu et al., 2018; Hu et al., 2020) with similar topological fea- tures (Table 2).
As an extended experiment, we compare our method with ensemble of 15 non-neural methods from (Blumenthal et al., 2020) and show that GRAIL performs better in both RMSE and EMR metrics while being 168x faster. The detailed results are provided in App. 1.
Inter-domain: Table 6 showcases the ability of the func- tions discovered by dataset-specific training of GRAIL to generalize across other datasets. We do not observe a signif- icant increase in RMSE on the off-diagonal entries, which showcases positive knowledge transfer and an ability not seen in neural approximators.
We compare the minimum, maximum, and average RMSE of individual functions discovered by GRAIL and nen-neural heuristics in App. A.5.2. GRAIL achieves better average and maximum RMSE across all datasets, while the non- neural ensemble has better minimum RMSE in 4 out of 6 datasets. This is expected, as GRAIL focuses on learning diverse, complementary heuristics via a submodular loss, rather than optimizing for a single best function.
Generalization to graph size: In this experiment, we eval- uate GRAIL-MIX on the ogbg-ppa dataset, which has been omitted from prior benchmarking due to the large size of its graphs (See Table 2). Given the computational infeasibility of ground-truth GED computation for these graphs, neural approximators cannot be trained on this dataset. To assess the generalization capability of GRAIL-MIX, we compare the upper bound provided by its programs against the top-3 non-neural heuristics (based on Table 3). The results illustrated in Fig. 3a. We observe that GRAIL-MIX provides 30% to 45% tighter upper bounds. Fig. 7 in the appendix further substantiates that GRAIL generalizes better to large graphs than neural baselines.
6.2. Generalizability
An intrinsic requirement of all machine learning methods is that the training and test data are sampled from the same dis- tribution. Thus, the neural baselines depend on training data tailored to the test dataset, limiting their ability to transfer knowledge due to reliance on dataset-specific features. In contrast, GRAIL learns symbolic logical rules in the form of programs, facilitating out-of-domain and -ustr--distribution generalization. We now evaluate this capability.
6.3. Ablation Study and Parameters
GRAIL comprises of main components: the GED Ap- proximation Module that reduces GED approximation to bipartite matching and learns weights of the bipartite graph using an LLM (Refer $ 3) and Prompt-Tunee tionary program selection (Refer & 4.1). In this section, we conduct an ablation study to assess the utility of each component and the impact of the budget parameter.
nomain: Neural models are limited by feature di- mensionality. making zero-shot generalization infeasible. However, for domains such as chemical compounds, a uni- form feature space allows training a single model. We re- train the best neural baseline, GREED, and compare its intra-domain generalizability with GRAIL in Table 5. Note that the AIDS dataset has smaller feature dimension than
via evolu-
8

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
Table 7. Ablation Study:
Comparison of GRAIL with variants without GED Approximation Module ("Direet fis (15)") and Evolutionary Prompt Selection (Random). The best performing method has been highlighted in green.
Metric
Method
AIDS
Linux
IMDB
ogbg-molhiv
ogbg-code2
ogbg-molpcha
GRAIL
0,57
0.13
0,55
2.96
4.22
3.18
RMSE
Direct fis (15)
7.95
2.81
112.64
7.47
25.68
9.71
Random
0,94
0.38
0.93
3.48
4.42
4.19
GRAIL
0.83
0.99
0.18
0.11
0.12
EMR
Direct fns (15)
0.01
0.14
0.09
0.02
0
0.02
Random
0.67
0.97
0.97
0.14
0.10
0.07
Utility of GED Approximation Module: gate whether the reduction to bipartite matching is necessary. Specifically, we directly prompt the LLM to generate code for computing GED, bypassing the intermediate step of predicting weights for a bipartite graph. To ensure a fair comparison, we adopt the same setup as GRAIL, using an ensemble of 15 heuristics and selecting the minimum pre- dicted value across each graph pair the final GED. As shown in Table 7, performance deteriorates significantly under this setting.
Here, we investi-
10 in the Appendix illustrate the graph structures, the edits made by GRAIL and its closest competitor GEDGNN, and the node similarity matrices generated by these algorithms. The program discovered by GRAIL-MMXX shown in Fig. 11, achieves the ground truth GED of 4, while GEDGNN pre- diets a GED of 20. This program assigns node similarity scores based on degree similarity and that of their neigh- bors. Since IMDB is unlabeled, feature similarity does not influence the results.
Examining GEDGNN's 's similarity matrix reveals a different score distribution compared to GRAIL. For instance, node I in Graph I has the second- hiihh- similarity to nodes 2 and in GRAIL-MIX, but GEDGNN assigns low similarity to these nodes, favoring nodes 0 and 6 instead. GERAI-MMIX decision aligns with the similarity in their degrees (degree of 9 for node in Graph 1 versus 7 for nodes 2 and 9 in Graph 2). In contrast, GEDGNN, as neural network, operates as a black box. We hypothesize that the poor performance of GEDGNN and other GNN-based algorithms in IMDB is due to the dataset's unlabeled nature and high density, leading to oversquashing. (Giovanni et al., 2024).
Impact of Evolutionary Prompt Selection: We assess the impact of the genetic evolution as described in $ 4.1, by randomly selecting programs from the program pool for the prompt instead of using the genetic algorithm. The RMSE increases by 2 to 3 times average, as shown in Table 7.
Impact of Submodularity: What happens if, instead of selecting the top-b functions using greedy submodular opti- mization, we evolve and score functions individually based on their upper bounds (Eq. 3) and select the top-6 solely based on this criterion? Fig. 3b illustrates the impact on RMSE across training iterations (LLM calls). While select- ing the top-b functions through submodular optimization shows clear trend of decreasing RMSE on the test set, inde- pendently choosing the top-b functions based on individual scores results in significantly higher RMSE, with progres- sive worsening trend indicative of overfitting to the training set. This result underscores the importance of submodular- ity in selecting functions that complement one another and perform well collectively (See Fig. 8 for additional metrics).
We also qualitatively compare the GRAIL'S heuristics with non-neural ones, and reason why GRAIL outperforms them in App. A.5.3.
7. Conclusions and Future Directions
This paper introduced a new paradigm of computing GED by leveraging LLMs to autonomously generate programs. Unlike traditional methods that rely on neural networks and require computationally expensive, NP-hard ground truth data, our method employs a self-evolutionary strategy to dis- cover programs without any ground truth data. Remarkably, these programs not only surpass state-of-the-an methods on average but are also interpretable and demonstrate strong transferability across various datasets and domains. While our approach is demonstrated on GED computation, we be- lieve is generalizable to other combinatorial problems with similar constraints, both within and beyond graph-related tasks. An interesting direction for future work is to criti- cally analyze the programs discovered by our method with domain experts and to develop mechanisms that facilitate closer cooperation between human and LLM agents.
Impact of budget b: For the true GRD, all possible map- pings (factorial in the graph size) must be considered. In- stead, GRAIL restricts this to b mappings, where each map- ping is generated by a program. Fig. 3c, we plot how affects the upper bound. As shown, the upper bound con- verges at 15 functions. Similar trends are observed in other datasets (see Fig. 5).
6.4. Interpretability: Case Study on IMDB
To shed light on the superior performance of GRAIL over GNN-based neural approximators, we analyze graph pair from the IMDB dataset, where GRAIL shows the highest improvement over all baselines (Table 3). Figures and

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGenrated Code
Acknowledgements
computation. CoRR, abw/190..002666666 00265, 2019. URL http:
The authors extend their sincere gratitude to Alexander Novikov (Research scientist, Google DeepMind) for his thorough review of the initial draft of this work. His insight- ful comments and constructive feedback were instrumental in refining the manuscript and enhancing its clarity. Ananya Mathur thanks the IIT Delhi CSE Research Acceleration Fund for the generous travel grant given to her. Samidha Verma thanks Yardi School of Artificial Intelligence for sup- porting her research and Google for sponsoring her travel through the Google PhD Fellowship.
908 002.5.
Blumenthal, D. B. and Gamper, J. Improved lower bounds for graph edit distance. IEEE Transactions on Knowledge and Data Engineering, 30(3):003-53) 2018. doi: 10.
1 1099TKDDE.001.2272222
Blumenthal, D. B. and Gamper, J. On the exact computation of the graph edit distance. Pattern Recogn. Lett., 134 (C):46-57 June 2020. ISSN 0167-8655. doi: 10.1016/ 2atrre..018.05.0000 URL https: http//doi.ooo org/10. 1016/ j. patrec. 2018.1.101.. 05.002.
Impact Statement
Blumenthal, D. B., Boria, N., Gamper, J., Bougleux, S., and Brun, L. Comparing heuristics for graph edit distance computation. The VLDB jourmal, 29(1)419-4558 2020.
This work introduces a novel approach to Graph Edit Dis- tance (GED) computation by leveraging large language mod- els (LLMs) and evolutionary algorithms generate inter- pretable programs for GED approximation. Unlike exist- ing methods, our approach prioritizes transparency, inter- pretability, and cross-domain generalization while achieving state-of-the-art performance in approximation accuracy.
Bommakanti, A., Vonteri, H. R., Ranu, S., and Karras, P. Eu- gene: Explainable unsupervised approximation of graph edit distance, 2024a. URI. peetps://arxive
2bs.2200..5888
The societal implications of this work are significant. By ad- dressing key limitations of neural approaches- succheess-uhhtee as their reliance costly ground truth data, lack of interpretabil- ity, and domain-specifie retraining- potential to make graph similarity computation more acces- sible and efficient across a variety of applications, including bioinformatics, social network analysis, and cheminformat- ics. Moreover, the transparency of program-based solutions could foster trust and reliability in critical domains where understanding the computation process is essential, such healthcare or legal systems.
Bommakanti, A., Vonteri, H. R., Skitsas, K., Ranu, S., Mot- tin, D., and Karras, P. Fugal: Prature-fortified unrestricted graph alignment. The Thirly-eighth Annual Conference on Neural Information Processing Systems, 2024b.
method has the
Chen, J., Peng, H., Han, G., Cai, H., and Cai. J. Hogmmne: a higher order graph matching with multiple network constraints model for gene-drug regulatory modules iden- tification. Bioinformaties, 35(4):602-610 2019.
Conte, D., Foggia, P., Sansone, C., and Vento, M. Graph matching applications in pattern recognition and image processing. Proceedings 2003 International Confer- ence on Image Processing
We do not foresee any ethical concerns arising out of our work.
( (Cat. No.03CH37429), 2:11-
21, 2003. URL htt.h:t////// /aapi./pppp.////// semant inmmannticcchooo org / Cttp/oorruuaaac 26783422:229929999
References
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithmss, Third Edition. The MIT Press, 3rd edition, 2009. ISBN 0262033844.
Bai, J. and Zhao, P. Tagsim: type-aware graph similarity
learning and computation. Proc. VLDB Endow., 15(2): 335-347, October 2021. ISSN 2150-8097. doi: 10.
949773344894966.4855.. URL htwph:ttp///ett http://c..ooooooooooooo 10.14778
Doan, K. D., Manchanda, S., Mahapatra, S., and Reddy, C. K. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. In SIGIR, pp. 665 674, 2021.
Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., and Wang, W. Simgnn: A neural network approach to fast graph simi- larity computation. In WSDM, WSDM '1,, pp. 384-392. 2019.
Fan, Z., Mao, C., Wu, Y., and Xu, J. Spectral graph match- ing and regularized quadratic relaxations: Algorithm and theory. In III H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learn- ing, volume 119 of Proceedings of Machine Learning Research, pp. 2985-2995, PMLR, 13-18 Jul 2020.
Bai, Y., Ding, H.. Gu, K., Sun, Y., and Wang, W. Learning- based efficient graph similarity computation via multi- scale convolutional set matching. AAAI, pp. 3219-3226, Apr. 2020.
Giovanni, F. D., Rusch, T. K., Bronstein, M., Deac, A., Lackenby, M., Mishra, S., and Veličković, P. How does
Blumenthal, D. B. New techniques for graph edit distance
10

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
over-squashing affect the power of GNNs? Transac- fions Machine Learning Research, 2024. ISSN 2835- 8856, URL https: http:///pppeeeeeeeeeeeeee net/ ftt.i/wwwmwe//oommm forum? 1d-KJRoOvRMNs.
compute the graph edit distance. Pattern Recognition, 72: 254-265, 2017a.
Lerouge, J., Abu-Aisheh, Z.,, Raveaux, R., Héroux, P., and Adam, S. New binary linear programming for- mulation to compute the graph edit distance. Pat- tern Recognition, 72:254-265, 2017b. ISSN 0031- 3203. doi:
Gordon, V. S. and Whitley, L. D. Serial and parallel genetic algorithms function optimizers. In Proceedings of the 5th International Conference Genetic Algorithms, pp. 177-183, San Francisco, CA. USA, 1993. Morgan Kaufmann Publishers Inc. ISBN 1558602992.
029. http://ntttss//wwscceeeeeeeeeeed
Haveliwala, T. H. Topic-sensitive pagerank. In Proceedings of the 11th international conference on World Wide Web, pp. 517-526, 2002.
Li, Y., Gu, C., Dullien, T., Vinyals, O., and Kohli, P. Graph matching networks for learning the similarity of graph structured objects. In ICML, pp. 3835-3845, 2019.
He, H. and Singh, A. Closure-tree: An index structure for graph queries. In 22nd International Conference Data Engineering (ICDE'06), pp. 38 38, 2006. doi: 10.1 10910CDD.20006333
Morris, C., Kriege, N. M., Bause, F,, Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of benchmark datasets for Icarning with graphs. CoRR, abs/2007.0866 2020. URL abs abs/2007.o 00022007..66.....
Hoperoft, J. E. and Karp, R. M. An n'5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal Computing, 2(4):225-22) 231, 1973.
Piao, C., Xu, T., Sun, X., Rong, Y., Zhao, K., and Cheng, H. Computing graph edit distance via neural graph matching. Proceedings of the VLDB Endowment, 16(8):1817-1829, 2023.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, Open graph benchmark: Datasets for machine learning on graphs. Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Sys- tems, volume 33, pp. 221 22118-2213. Curran Associates, Inc., 2020.
Ranjan, R., Grover, S., Medya, S., Chakaravarthy, V., Sab- harwal, Y., and Ranu, S. Greed: A neural framework for learning graph distance functions. Advances in Neural Information Processing Systems, 01-22518-22535 2022.
Ranu, S., Hoang, M., and Singh, A. Answering top-k rep- resentative queries on graph databases. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 1163-1174, 2014.
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning graphs, 2021. URL https: / /aaiiviivvv..///iv org/ abs 00687.
Romera-Pareder B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, J., Ellenberg, S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468 475, 2024.
Jain, E., Roy, I., Meher, S., Chakrabarti, S., and De, A. Graph edit distance with general costs using neural set divergence. In The Thirty-eighth Annual Conference Neural Information Processing Systems, 2024.
Justice, D. and Hero, A. binary linear programming formulation of the graph edit distance. IEEE Transac- tions Pattern Analysis and Machine Intelligence, 28 (8):1200-1211) 2006. doi: 10. 10.1109/TPMMI.2000 152.
Singh, R. Xu, J., and Berger, B. Global align- ment of multiple protein interaction networks with application to functional orthology detection. Pro- ceedings of the National Academy of Sciences, 105(35);:2263--2766 2008. doi: 10.1073/pnas.
Kuhn, H. W. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2): 83-97, 1955.
0806627105. URL stttps:// http:://wwwwww /www, pnas. oacas..rr/// doi/ abs/10.
0806627105.
Leordeanu, M., Hebert, M., and Sukthankar, R. integer projected fixed point method for graph matching and map inference. Advances neural information processing systems, 22, 2009.
Szklarezyk, D., Gable, A. L., Lyon, D., Junge, A., Wyder, S., Huerta-Cepas, J., Simonovie, M., Doncheva, N. T., Morris, J. H., and et al., P. B. String v11: protein-protein association networks with increased coverage, support- ing functional discovery in genome- winde experimental datasets. Nucleic Acids Research, D7D11).607-D613, 2019.
Lerouge, J., Abu-Aisheh, Z., Raveaux, R., Héroux, P., and Adam, S. New binary linear programming formulation to

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGnerated Code
Wang, R., Zhang, T., Yu, T., Yan, and Yang. X. Com- binatorial learning of graph edit distance via dynamic embedding. In IEEE Conference on Computer Vision and Pattern Recognition, 2021.
Wang, X., Ding, X., Tung, K. H., Ying, S., and Jin, H. An efficient graph indexing method. In Proceedings of the 2012 IEEE 28th International Conference Data Engineering (ICDE 12), pp. 210-221, USA, 2012. IEEE Computer Sociery.
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513-530, 2018.
Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https:// openreview http::/ee//orrreeeeeeeeeeeee iirriiddrGGssr 6iA5Km.
Yanardag, P. and Vishwanathan, S. Deep graph kernels. In Proceedings the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15), pp. 1365-1374, New York, NY, USA, 2015. Association for Computing Machinery.
Zhang, Z., Bu, J., Ester, M., Li, Z., Yao, C., Yu, Z., and Wang, C. H2mn: Graph similarity learning with hierarchical hypergraph matching networks. In Pro- ceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery Data Mining, KDD '21, pp- 2274-2284, New York, NY, USA, 2021, Association for Computing Machinery. ISBN 9781450383325. doi: 10. 1145/34445588.4477388 URL https: odri 10 10.1145/344758.344
Zhuo, W. and Tan, G. Efficient graph similarity computa- tion with alignment regularization. Advances in Neural Information Processing Systems, 35:30181-30191 2022.
Zimik, M., Feldman, M. W., and et al., J. L. Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences, 116 (10):442 4433, 2019.
12

---

GRAIL: Graph Edit Distance and Node Alignment using LLM--Generted Code
A. Appendix
A.I. Neural GED Approximation Methods
GREED (Ranjan et al., 2022): GREED utilizes a Siamese Graph Neural Network (GNN) to generate embeddings for graph pairs and learns to approximate the GED by preserving its metric properties. This is achieved by minimizing the RMSE between the norm of the embedding difference and the ground truth GED.
We use the default hyperparameters used by the authors. Training uses learning rate of 1e-3, weight decay of 1e-3, with a cyclie learning rate schedule (step_size size_up/down -0000 and early stopping patience of cycles. The authors use an 8-layer Graph Isomorphism Network (GIN) (Xu et al., 2019). The hidden layer dimension is set to 64.
GEDGNN (Piao et al., 2023): GEDGNN learns graph embeddings using a GNN followed by two computation heads, a cross matrix module that predicts the matching. Further, combination of a cross matrix module and a neural tensor network, combined with the predicted matching matrix, is used to predict the GED value. GEDGNN does proteprocsssing with k-best matching algorithm for producing the edit path. Using this algorithm, they prune out bad matchings that have a larger edit path, enabling them to lower the bound for the GED estimate.
We have used the parameter values as described by the authors. We use 3-layered GIN with hidden dimensions 1 128, 64, and 32, respectively. 16 parameter matrices with size 32 x 32 are used in each cross matrix module. The default value of k used during testing i.e. 100. Model training was done for 20 epochs, i.e., when the loss becomes smaller than 0.001. During training, the dropout rate is set to 0.5, the learning rate to 0.001, and the weight decay to 0.0005, GEDGNN employs a loss function that combines the matching loss and the GED value loss, with the latter weighted by a hyperparameter A. As specified in the paper, À is set to 10 for the AIDS and Linux datasets and to 1 for the remaining datasets, which adhere to in our implementation.
ERIC (Zhuo& & Tan, 2022): ERIC is graph similarity model that learns node alignment implicitly through a regularizer, removing the need for a separate alignment module. It computes similarity using a Neural Tensor Network and MLP on graph-level embeddings, which are formed by concatenating outputs from a 5-layer GIN with 10 10-dimensional node embeddings. The model is trained using a combined loss that integrates both the regularizer and the similarity prediction. Training is performed using the Adam optimizer (learning rate 0.001, weight decay 0.0005), with a batch size of 256 and early stopping with a patience of 100 epochs.
MºMN (Zhang al., 2021): H MMMN involves converting each input graph into hypergraph capture high-order structural relationships. It performs subgraph-level matching using hyperedges as subgraphs, coarsens the hypergraphs with a hyperedge pooling operator that is based on Personalized PageRank (Haveliwala, 2002). Then it employs a subgraph matching module, which compares important hyperedges from two graphs to capture fine-grained structural similarities. Finally embeddings are aggregated via a readout function and passed through an MLP to get the predicted GED value.
We use the default hyperparameters used by the authors. All datasets use 3 hypergraph neural networks (HGNN) layers, 100-dimensional node embeddings, and a weight decay of 0.0005. Learning rate is set to 0.0001. Subgraph construction based on a random walk of length and a 2-hop neighborhood. The restart ratio for PageRank 0.1, and the number of power iterations is 10. Each model is trained for 10,000 epochs with early stopping triggered if validation loss does not improve for 100 consecutive epochs.
GRAPHEDX (Jain al., 2024): GRAPHEDX is composed of two main components: EMBED, and PERMNET. EMBED, includes a GNN module with 5 message-passing layers that generate 10-dimensional node embeddings using a GRU-based update function and Linear-ReLU-E Rehu--Lneuur structure. After propagation, separate Linear-ReLut Linear network, computes 20-dimensional edge embeddings from the combined node features and adjacency indicators. PERMNET, then takes the final node embeddings from two graphs and processes them through Linear-ReLU-- ReLU-LincarL network to map them to a fixed size (10 for Linux, 20 for others). A similarity matrix is computed using L1 distance, and 20 iterations of Sinkhorn normalization with temperature T= = 0.01 are applied to generate a soft permutation matrix P. which is used to compute the final soft edge alignment matrix S.
13

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
A.2. Proofs
A.2.1. NP-IIARDNESS EQ. 4
Reduction to Prove NP-Hardness
We reduce the Set Cover problem the given problem in polynomial time demonstrate its NP-hardness.
Given universe of elements U' E2......... en b, the set cover problem seeks to determine if there exist b sets .,...., S.. E S whose union covers all elements of U.
collection of sets S = 1 S2, ..... Sm where S; C U, and budget ......
Given an instance of the set cover problem, we construct a bipartite graph B = E,, where V = S, u = U, and an edge (S,, ez) E & exists if and only if S; covers ey. Each edge (S has a weight:
if S, covers Ej, if S; does not cover Ej-
e()
where A > 0.
The objective is to select nodes from V (representing sets S) such that Eq. is minimized on graph B.
If Set Cover of size exists, then all n elements can be covered by 6 sets. This means we select the corresponding nodes A" C V, then every node in V/ will have at least one edge of weight from some node in A incident on it. Hence, ((A") will return cumulative sum of n..
Conversely, if no Set Cover of size exists, then some elements will not be covered by the selected sets, and their corresponding nodes in ll will have only edges of edge weights + A from nodes AA".
Therefore, a solution to the Set Cover problem exists iff selecting the corresponding nodes A" C V leads to I(A") = n. Conversely, J (AA)) n, it implies that b-set cover exists.
A.2.2. MONOTONICITY AND SUBMODULARITY
Lemma 1. Monotonicity: (A4 S ifA2
Proof. Since (AA') computes minimum over all available mappings in A', the minimum can only reduce when additional mappings are added to form A.
Lemma 2. Submodularity: I(A) - J(AU ((4))
Proof. We seek to show that the marginal reduction in ((A) when program (mapping) P is added to A is atmost as large as adding P to its subset A'. We establish this through proof by contradiction.
Let us assume
AFE J J(A))
Due to the min operator in Eq. 5, Eq. implies that the additional number of graph pairs where P contributes to the minimum mapping is higher when added to A than when added to A'. This creates a contradiction, since if P contributes to the minimum of graph pair in AU {P), then it guaranteed to contribute to the minimum for the same pair in A' U (P) as well.
A.3. Experiments
A.3.1. SETUP
All experiments ran a machine equipped with Intel Xeon Gold 6142 CPU @ @IGHz and a GeForce GTX 1080 Ti GPU, While non-neural methods and GRAIL run on the CPU, neural baselines exploit the GPU. For the LLM, we use Gemini 1.5 Pro. In particular, we have used the initial stable version of Gemini 1.5 Pro, i.c., gemini-1..-pro-0000 which was released on May 24, 2024.
Hyper-parameters: Table lists the hyper-paramette used for GRAIL.. stands for the number of functions per response
14

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
prioriity_@leerohh: [ist(iss(inttl) graphie tist[list[int],, weights: List[List (fleatll) Uistllss/ffoatt)
Carputes the Graph Edit Distance (GED), neasure of the dissinilarity between two graphs.
required transform graph The prinary operations considered in GED calculations Lnctude:
GED defined ninimun
Problem description
Insertion/Delationn Adding renaving
cost
++Edga Insortion/Delatt batioonze Adding renoving an adga batween two nodoc incurs cost of +1.
**boode Nelebeeiiggees Modifying the tabel of node Iif labels are present) adds cost for each nisnacch.
Args:
graph1: adjaceccy natrix
graph.
Task specification
graph2: The adjaceicy natrix of Lhe second graph,
weights: weight natrix represencing
procabilities napping nodes between "uraph1" and "uraph2'. Each entry is probbiility value, wiere higher value indicates higher likelihood and similarity of rapoing nodas. The size of the weight natrix deternined
naximum number nodes both
squared.
Returns:
entry represents probability node in "graph1" being napped to node in "graph2" in a way that mininizes the overall graph edit distance.
refined weight
(
nаx node len(araph1)
weights [10.0] nak_node range(max_nodal)
return weights
cef priority vafgraph1: [is[[ist[int]l, graphzs tsst[Uss(intt), weights: (st(Uss((taat]]) ust(uus=[toatt)] Inaroved version "priority_ve" ... ten(graph1)
ten(graph2]
Top-k programs(k=2)
moxini,
ref refinee__wighhts [10.3] * max_node for in range(max_node]]
for 1 in range(n11:
for j in range(n2):
weichbor_sinilarite
for k in range(n1);
range(n2):
if [araph1 [k] = 11 and (1] 1):
neighbor_sitt nesgibor.cimilarity swwilarity
weights [K]
ref wighhts [j] weightorrsiriierrie
Function header for k+1 program
retined weights
priority (orrphhi List[List (int)l, graphis listilüst(intt), weightss (it((lit(floatt)] List[lár: Inproved version "priority_ve v2"
Figure Example an input prompt to GRAIL
generated by the LLM and is the function budget employed for submodularity while training. We decided to use k as 2, since with greater values of k, we observed no significant improvement in quality metrics. This was also observed in FunSearch (Romera-Paredes et al., 2024). For the function budget b, we observed that value of 15 was good enough for most datasets (Refer Fig. 5).
A.4. Datasets
The semantics of these datasets are as follows:
ogbg-molhiv and ogbg-molpeba: These are chemical compound datasets, with each graph representing molecule.
Hyper-parameter
Value
2
b
15
number of islands
5
temperature
0.99
Algorithm for bipartite matching
Neighbor- biased mapper (He & Singh, 2006)
Table H. parameers used for GRAIL
15

---

GRAIL: Graph Edit Distance and Node Alignment using LLM--Gnnrated Code
a) AIDS
b) IMDB
c) ogbg-molpcba
10.2
62.9
22.0
10.0
Average Upper Bound
9.8
21.5
9.6
02.5
62.4
10.0
15.0
20.0
10.0
15.0
20.0
5.0
10.0
15.0
20.0
Budget (b)
Figure 5, Avg. Upper Bound function budget (b) for submodular greedy selection
Nodes these graphs correspond to atoms and are labeled with their atomic numbers, while edges denote the chemical bonds between atoms. These datasets vary in size and complexity, with a rich diversity molecular structures, enabling to the robustness and generalizability of our method.
ogbg-code2: This dataset comprises a vast collection of Abstract Syntax Trees (ASTs) generated from nearly 450,000 Python method definitions. Each graph this dataset represents an AST, with nodes labeled from predefined of 97 categories, capturing various syntactic constructs within the methods. These graphs are considered undirected, simplifying the representation while preserving structural relationships.
oghg-ppa: This dataset includes undirected protein association neighborhoods extracted from protein-protein interaction networks of 1,581 species(S<klarczyk et al., 2019) across 37 diverse taxonomic groups. To build these neighborhoods, 100 proteins were randomly selected from each species, and 2-hop protein association neighborhoods were constructed around each selected protein(Zitnik et al., 2019). In these graphs, proteins are represented as nodes, and edges indicate biologically relevant associations between them.
This dataset is collection of graphs sourced from the AIDS antiviral screen database, each graph representing chemical compound's molecular structure. These graphs are labeled, capturing meaningful properties the compounds, and are compact size, containing no more than 10 nodes.
AIDS:
Linux: A collection of program dependence graphs where nodes correspond to statements and edges indicate dependencies between statements. The graph sizes this dataset are also limited to 10 nodes. This dataset is unlabeled and was introduced in (Wang al., 2012).
This dataset consists of ego-networks actors and actresses who have shared screen time in movies. Each graph represents an ego- -etwore where the nodes correspond individuals (actors or actresses), and the edges denote shared appearances in films. This dataset is unlabeled and was introduced in (Yanardag & Vishwanathan, 2015).
IMDB:
1. GROUND-TRUTH DATA GENERATION
We employ MIP-F2 (Lerouge et al., 2017b) generate ground truth GED. MIP-F2 returns the lower and upper bounds of GED. We compute these bounds with time limit of 600 seconds per pair. Pairs with equal lower and upper bounds are included the ground truth.
A.4.2. METRICS
We use the following two metrics quantify accuracy:
Evaluates the prediction accuracy by measuring the disparities between actual and predicted values. For graph pairs, it is defined as:
RMSE:
ER (true-ged, pred 3
16

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGenrated Code
Exact Match Ratio: Represents the proportion of graph pairs where the predicted GED exactly matches the actual GED, For graph pairs, it is defined as:
Σ (true-ged, pred-ged,)
where I(-) an indicator function that returns I if the condition inside is true, and 0 otherwise. A higher Exact Match Ratio indicates better predictive accuracy at the individual graph pair level.
Method
AIDS
Linux
IMDB
ogbg-molhiv
ogbg-code2
ogbg-molpeba
GRAIL.
0.83
0.99
0.18
0.11
0.12
Table 9, EMR results of GRAIL for all datasets. Values in the range (0.99,1) are denoted as R
A.5. GRAIL vs. Non-neural Methods
1. COMPARISON OF GRAIL. WITH ENSEMBLE OF NER-NE METHODS
Similar to GRAIL, several non-neural heuristics also consider multiple solutions. Specifically, sainch-and-boume methods (e.g., BRANcH) and MIP approaches (LP-GED-F2, ADJ-IP, COMPACT-MIP MIP) explore multiple candidate solutions that satisfy the given constraints, selecting the one with the tightest upper bound.
In this experiment, we compare GRAIL with ensemble of non-neural GED approximators. Specifically, we select the 15 non-neural heuristics from (Blumenthal et al., 2020), based on their tightness of upper bounds. The set of 15 heuristics used in the ensemble includes, ADJ-IP, NODE, LP-GED-F2, BRANCI-TIGGIT, COMPACT-MIP. IPFP, BRANCH-CONST,, BRANCH- COMPPATT BRANCH-FASE BP- BE-M, BRANCH, K K-REFINE, STAR, REFINE, and F1
For each graph pair, we apply all 15 non-neural heuristics and choose the minimum computed distance. As shown in Table 10, GRAIL continues outperform this ensemble approach. It should also be noted that GRAIL approximately 168x faster than the ensemble.
Method
AIDS
LINUX
IMDB
ogbg- molhiv
ogbg-code2
ogbg- molpeba
Non-Neural Ensemble
0.73
0.23
0.72 0.55
3.13
7.10
3.66
GRAI.
0.57
0.13
2.96
4.22
3.18
Table 10. RMSE of non-neural ensemble and GRAIL across datascts. The best RMSE has been highlighted with green color
A.5.2. COMPARISON OF INDIVIDUAL FUNCTIONS' PERFORMANCE
In Table 11, we report the best, worst, and average RMSE for the 15 heuristics identified by GRAII,, denoted as Min, Max, and Avg, respectively. Similarly, we provide the Min, Max, and Avg RMSEs for the ensemble of non-neural heuristics as specified in section A.
Notably, the best non-neural heuristic outperforms the best function identified by GRAII in out of datasets. However, this result aligns with our expectations, as GRAIL does not aim find single optimal function with the lowest RMSE. Instead, leveraging a submodular loss function, it seeks a diverse set of complementary heuristics that collectively minimize RMSE across the training set of graph pairs
A.5.3. QUALITATIVE COMPARISON OF DISCOVERED HEURISTICS vs. EXISTING NON-NEURAL HEURISTICS
The heuristics discovered by GRAIL are fundamentally different from the top-performing heuristics in (Blumenthal et al., 2020). Specifically:
NODE and BRANCH transform GED into linear sum assignment problem.
17

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGenrated Code
Method Datasets
AIDS
Linux
IMDB
ogbg-molhiv
ogbg-code2
ogbg-molpeba
Mín GRAIL
1.90
0.49
3.19
6.23
6.48
Max GRAIL
3,33
1.32
7.48
8.27
17.97
9.40
Avg. GRAIL
2.57
0.96
5.04
7.16
12.10
7.96
Min Non-Neural
0.85
0.23
3.90
4.50
8.34
4.
Max Non-Neural
15.23
6.72
69.45
24.97
92.67
29.22
Avg Non-Neural
7.62
4.08
16.99
16.52
39.24
19.37
Table 11. RMSE of individual functions discovered by GRAIL. compared to non-ncural methods across datascts. The best Min. RMSE has heen highlighted with green color
LP-GED-F2, ADI-IP, and COMPACT-MIP use mixed integer programming.
IPFP reduces GRD to the quadratic assignment problem (QAP), which is also NP-hard and relies on heuristics to approximate the QAP.
In contrast, GRAIL'S discovered heuristics compute similarity between all node pairs across the two graphs followed bipartite matching. This similarity is determined by measuring the distance between various vertex invariants- node labels, degree, etc. etc.-within their t-hop neighborhoods. The heuristics differ in their choice of vertex invariants, distance functions, and I.
The heuristics discovered by GRAIL can, in principle, replace those used by NODE or BRANCH. Qualitatively, NODE does not consider edge information, and the cost matrix is primarily constructed based on the cost of node relabelling, insertion, or deletion. BRANCH, on the other hand, takes the node labels and the labels of the edge end points into consideration when constructing the cost matrix.
In contrast, the heuristics discovered by GRAIL are more general. They consider the label information of nodes and edge end points as well as compute the cost based on vertex invariants such as the degree distributions of the nodes to be matched and their k-hop neighborhoods. Finally, normalization and weighing factors are also introduced while constructing the cost matrix, as seen in Fig. 11. Thus, the cost matrix perhaps more rich in terms of assessing the cost of aligning two nodes from a graph pair.
The complete repository of discovered heuristics is available at http::::/gttub..c////aaaaa////// inside periiiscovered_prograaa
A.6. Efficiency Analysis
The training and inference time analysis is shown in Fig. 6.
Training Time: From Fig. 6a, we observe that GRAII. is significantly more efficient than the neural baselines. Neural methods require NP-hard ground truth training data, which involves extensive computation times of up to 15 days. Additionally, note that GRAIL-MIX requires training only once while performing on par with GRAIL and neural baselines in terms of approximation enror (see Table 3).
Inference Time: We compare the inference time of GRAIL with the top three neural and non-neural methods from Table shown in Fig. 6b. At the onset, we point that while GRAIL infers CPUs and provides the node mapping in addition to the predicted GED, neural baselines rely GPUs and only provide the GED. Hence, neural methods have lower computational workload while having access to more powerful computational resources. Results indicate that GRAIL achieves faster inference times than neural baselines for smaller and sparser datasets, such as AIDS and Linux. However, inference times increase for larger and denser datasets, such as IMDB and ogbg, due to the computational overhead of computing mappings. The maximum recorded inference time 94.6 seconds for 968 graph pairs in the ogbg-code2 dataset (~ 0.1 seconds per pair), which remains reasonable considering the various advantages of GRAIL, including its independence from ground truth data, one-time training for GRAIL-MIX, and strong generalization capabilities. Furthermore, the efficiency of GRAIL's programs can be further improved through human intervention or translation to more efficient languages, such as C.
18

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGnerated Code
Training Time
Ground Gen.
AIDS
Linux
IMDB
10
10"
Time (hrs)
Time (hrs)
Time (hrs)
10'
10"
10
10"
ogbg-molhiv
ogbg-code2
ogbg-molpcba
10
10'
10
Time (hrs)
(hrs)
Time (hrs)
10
10'
10
10
10"
(a) Training Time
AIDS
Linux
IMDB
me Hewoonba
Time
GRM
09020
catesee gott
1007 waoe
P2
GRM.
Mare
GEDGMe gel
wane ogbg-mo
1p-d20 Pa
agbg-mollhiv
ogbg-code2
7pa
Time benoreea)
ORML
GEbeees gioz
UP-020
Grodie gisl
wode
U2-220P2
woot UP aopa
(b) Inference Time
Figure (a) Training Time: Comparison of GRAIL with the top-3 neural methods in Table (b) Inference Time: Comparison GRAIL with the top-3 neural and non-neural methods in Table 3. The top-3 methods have been selected based avg. ranks. Note:
Ground truth generation time is the same for a dataset (9 hrs 43 min AIDS, hrs 25 min Linux, 124 his 25 min IMDB, 379 hrs 19 min mohg-molhiv, 21 hrs 42 min ogbg-code2, 414 hrs 30 min oghg-molpcha) for all neural methods, hut appears be different in the plots due to log scale conversion.
19

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
RMSE VS. Graph Size (IMDB)
RMSE Graph Size (Linux]
RMSE vs. Graph Size (ogbg-code22
22.5
70
GREED
GCDGNN
20.0
GRAIL-MIX
17.5
Average RMSE
0.6
40
30
10.0
7.5
10
5.0
0.0
10:25
1.25
25-35
35:45
Average Graph Size
Figure Avg. RMSE vs. Avg. Graph Size comparison on IMDB, Linux and ogbg-code2 datasets. GRAIL-MIX outperforms the best baselines both smaller and larger graph sizes. The rate of increase of error is lower for GRAIL-MIX as opposed to GREED and GEDGNN with increasing average graph size.
RMSE vs LLM Calls
EMR vs LLM Calls
2.3
Top-b
0.8
2.1
Submodular
1.9
1.7
RMSE
1.5
EMR
Top-b
0.6
1.3
Submodular
1.1
0.5
0.9
0.5
100
150
100
LLM Calls
LLM Calls
Figure 8. Performance comparison of Top-b vs. Greedy Submodular on the test set of AIDS dataset with an increasing number of LLM calls.
20

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code
Graph 1 Pair 587
Graph 2 Pair 587 (GRAIL-MIX)
Graph 2 Pair 587 (GEDGNN)
Deletion
Addition
Mapped edges
Figure IMDB Case Study: The left-most graph represents Graph 1, while the middle and right-most graphs depict Graph with predicted edits from GRAIL-MIX (Fig: 11) and GEDGNN, respectively. The red and green edges in each graph indicate the edge edits predicted by both methods. Ground Truth GED:4, GRAIL-MIL MIX GED:4, GEDGNN Mapping's GED: 20.
Heatmap of Normalized Weight Matrix (GRAIL MIX)
Heatmap of Norma ized Weight Matrix (GEDGNN)
202
6.456
333
456
339
2.202
038
0.633
1222
0.00
362
142
0.8
0.8
A 8.01
5.118 0.251
0.155
0.118
D 115
0.013
0.155
175
0.751
~ 0.098
0.202 0.00n
0.027
0.002
0.077
5.094
0.027
0.211
0,000
0.013
0:511
0.253
0.000
0.233
0.000
C2 (hode Hidood
G1 (Node Inded)
0.6
0,013
0.1.9
0,213
0.135
0.375
0.253
DLD93
0.202
0.000
0.202
02727
0.215
0.000
0.4
0,010
2,052
088
0.200
0.092
D 000
0,010
0.000
222
0.081
0.252
0.274
0,000
0.120
0.274
0.120
0.252
120
0.730
0.000
0.081
0.2
02
0,010
8,052
0-081
0,000
0.052
000
0,010
0,000
205
0.083
0.232
0.574
0,000
0.120
0.974
0.110
0.232
120
0.720
0.000
8
62 (Mode Inoix!
G2 (Node Indext
(a)
(b)
Figure 10. IMDB Case Study: Heatmap of weight matrix generated by (a) GRAIL-MIX (Fig: 11) and (b) GEDGNN
21

---

GRAIL: Graph Edit Distance and Node Alignment using LLM-GGenrrted Code
det priority__Ilgrapht: lust(lis(iint),, graph2: (isll weights: lst(Uist(int]) lss([ust(floatl): n1 ten(graph1)
ten(graph2)
max_node nax(n1,
graph1_np= np.array(graph1)
graph2 np np.array(graph2)
reights_npp ng.array(weighhts)
degrees1 Sraphi_np.sum(xxisee
degrees2 graph2__ng.sumaxlsst
ref iniiggs np. zeros (max_node, nax_node), dtype=float)
Initializing with feature-based weight similarity of nodes (graph 1) and j (graph
range(n1);
neighbers__i np.whereeggraphh_ppp 1)
for in range(n2):
scare 0.0
weights_np. shape
weights_np..sapp
weights_np(1,
Degree comparison of nodes (graph and (graph 2).
degree_diff (bs(degrees [i] degrees2 (j1)
score / degree diff) & hich score if degree diff is low
neighbors__j np.whhere(graph2_np
[]] #neighbours
newghbors
Initial Feature-based similarity of neighbors of nodes (graph 1) and (graph 2.
1f neighbors_i.sihe and neighbors_j. s_size
beighhorrweighht
fig.innnngggooo__rrreesssee neightorr_weghht..sutt cormon neichbars
1), neightors_j]
comnon_neightors
neighbor simibartsiiillritty 6
neighbors__is _isiize and neighbors_ j.size
degree adeggrsee wtwighherrrs..rssaeeeeeeeeee degrees2 [neightosss neighbor_sitee similarity insighbor_weight score neighhorrssmillrrtee refined_weightttli. 1] score
Weighted degree similarity neighbors nodes (graph 1) and (graph 2.
[1 (irre__dffss))..smm
total_score refined_ weiintd_ sn2).sun()
if total_score
Aggregation and normalization
refined refined_wwrghhs/ (Ing :n2] /= tatal_score
else:
lefi :n2] (nl n2) n2)
else
return refineddweigghts..tttss.
Figure 11. IMDB Case Study: Program discovered by GRAIL-MIX that has minimum individual RMSE on IMDB dataset.
22


Reviews:
[{"review_id": "T8w32rAajH", "reviewer": "Reviewer_YCYA", "summary": "This paper addresses the problem of computing graph edit distance. In contrast to existing neural and non-neural methods, the authors propose an LLM-based approach, referred as GRAIL, by transforming the graph edit distance computation into two sub-problems - (1) Weight selection in a bipartite graph and (2) budget constrained map selection. GRAIL overcomes limitations of neural methods by eliminating reliance on NP-hard ground truth data, achieving superior accuracy, cross-domain generalization, and interpretability across diverse datasets.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No - The problem of graph edit distance is decomposed into two subproblems of 1) Weight selection in a bipartite graph and (2) budget constrained map selection. However, it is not proved / discussed how this decomposition is going to help solving the problem. Please check the detailed comment below.", "methods_and_evaluation_criteria": "No - the fundamental comparison with directly using LLM to solve GED is missing.", "theoretical_claims": "No - I have not formally checked the correctness of the theoretical claims. But they intuitively seem to be correct.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This paper is related to the broader literature on the computation of graph edit distance which is quite fundamental in graph ML.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "**Strengths**:\n\n1. The paper proposes to use LLMs to compute graph edit distance - which itself is very interesting.\n\n2. The paper is very well-written. The overall flow is quite interesting. I really like the way authors put definitions and problems to make everything formal but still easy-to-follow.\n\n3. Some experiments, especially the ablation studies are insightful.\n\n\n**Weaknesses**:\n\n1. There is a fundamental problem in the proposed idea. The authors decompose the problem of graph edit distance (GED) into two subproblems: \n  - Weight selection in a bipartite graph\n  - Budget constrained map selection\n  \nThe authors show some submodular property based guarantee of a greedy algorithm for budget constraint map selection problem. But unfortunately they did not show the relation of the optimal solution of the budget constraint map selection problem with the actual problem they are trying to solve - which is graph edit distance. For example, if I solve the budget constraint map selection problem optimally for a given D = {P_1 ,..., P_m}, will it be able to achieve any guarantee of the performance on GED? \n\n\"The weight of an edge (v1, v2) is set based on some policy, which should ideally reflect the probability of v1 being mapped to v2 in the optimal GED mapping\" - I think this subproblem (referred as *weight selection in a bipartite graph*) is at least as hard as learning GED between two graphs G1 and G2 directly. So it is not at all clear what is the advantage of decomposing GED into two subproblems. The solution of Subproblem 1 (*Weight selection in a bipartite graph*) in the paper is quite superficial in nature. It does not also have any guarantee.\n\n2. The paper keeps claiming that GRAIL minimizes an upper bound of GED. However, it is never proved or clarified if this upper bound has any approximation guarantee on the optimal solution or is it a trivial upper bound? If the individual programs are not good, a subset of them minimizing Eq. 4 will not help solving GED.\n\n3. The superior performance of GRAIL in Tables 3 and 4 are NOT attributed properly. Can it be just because of the inherent reasoning capability of LLMs? One baseline should have been using the same LLM to compute GED directly with some smart prompting and good / diverse in-context examples. \n\n4. In L230, what is the guarantee that J(A_greedy) converges?\n\n5. Although GRAIL demonstrates generalization to larger graphs, the computational overhead of generating and evaluating programs for dense or massive graphs may still pose challenges, especially in real-time applications.", "other_comments_or_suggestions": "I would like to suggest the authors to think more on the weight selection in a bipartite graph subproblem. They should also investigate LLM's capability on solving GED directly in a fair way.", "questions_for_authors": "See above.", "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": "Ayqmmg37rM", "reviewer": "Reviewer_isZf", "summary": "This paper presents a novel paradigm for computing Graph Edit Distance (GED) by harnessing the capabilities of LLMs to autonomously generate executable programs. Departing from conventional approaches that depend on neural networks and computationally intensive, NP-hard ground truth data, our methodology adopts a self-evolutionary strategy to uncover programs without the need for any ground truth data. Notably, these programs not only outperform state-of-the-art methods on average but also offer interpretability and exhibit robust transferability across diverse datasets and domains.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the constructive feedback on our work. Below, we outline the changes made to address the reviewer's concerns. If the reviewer finds our responses satisfactory, we would sincerely appreciate a reconsideration of our paper’s rating.\n\n-------------\n\n**W1.** **I am concerned that the effectiveness of this work is heavily reliant on the capabilities of large language models, rather than the inherent architectural design proposed in the paper.** \n\n**Ans:** Our approach has four main components: \n 1. Reducing GED to bipartite matching\n 2. Learning weights of the bipartite graph using LLM\n 3. Prompt-tuning:\n     - Scoring programs using submodular optimization \n     - Genetic evolution.\n\nFig 3c in the manuscript is an ablation study showing that submodular optimization indeed helps (lines 417--430).\n\nTo further enhance our ablation study, we have conducted the following additional experiments to establish that just the LLM is not sufficient to obtain good performance.\n\n1. **Is reduction to bipartite matching necessary?** We directly ask the LLM to predict code for GED instead of weights of the bipartite graph. The results deteriorate dramatically as shown below (Direct). \n\n|    | DATASET| AIDS  | Linux | IMDB  | ogbg-molhiv | ogbg-code2 | ogbg-molpcba |\n|-----------|-----------|-------|-------|-------|---|---|-----|\n| **RMSE**      |  **GRAIL**         |            **0.57**  | **0.13**  | **0.55**  | **2.96**        | **4.22**        | **3.18**  |\n|           |  **Direct fns (15)**              |7.95  | 2.81   | 112.64| 7.47        | 25.68       | 9.71        |\n| **EMR**|**GRAIL**              |**0.8**     |**~1**    | **~1**    | **0.2**         | **0.12**        | **0.12**        |\n|            |  **Direct fns (15)**              | 0.01  | 0.14  | 0.09  | 0.02        | 0           | 0.02        |\n\n2. **Is genetic evolution necessary?** We randomly select programs from our pool for the prompt instead of genetic algorithm. The RMSE increases by 2 to 3 times on average. \n\n| Metric | Method  | AIDS  | LINUX | IMDB  | ogbg-molhiv | ogbg-code2 | ogbg-molpcba |\n|--------|--------|-------|-------|------|-------------|------------|--------------|\n| RMSE   | GRAIL  | **0.57** | **0.13** | **0.55** | **2.96**    | **4.22**   | **3.18**     |\n|        | Random | 0.94  | 0.38  | 0.93    | 3.48        | 4.42       | 4.19            |\n| EMR    |GRAIL  | **0.83** | **~1** | **0.99** | **0.18**    | **0.11**   | **0.12**     |\n|        | Random | 0.67  | 0.97  | 0.97    | 0.14        | 0.10       | 0.07           |\n\n**W2.** **In the main text, there is a lack of detailed introduction of related works, which is not conducive to readers who are not familiar with the field to understand the background and significance of this work.**\n    \n**Ans:** We propose adding the following more detailed description of related works in the main manuscript. We will also add an even more detailed version, particularly on neural methods, in the appendix.\n\n>### **Non-Neural Methods**  \n>Computing GED exactly or approximating it within provable bounds is challenging, leading to the development of various heuristic approaches \\citepBlumenthal}. These methods utilize techniques such as transformations to the linear sum assignment (**NODE** \\citep{NODE_ADJ_IP}, **BRANCH-TIGHT** \\citep{BRANCH_TIGHT}), mixed integer programming (**MIP**) (**LP-GED-F2** \\citep{lerouge2017new}, **ADJ-IP** \\citep{NODE_ADJ_IP}, **COMPACT-MIP** \\citep{COMPACT-MIP}), and local search methods (**IPFP** \\citep{leordeanu2009integer}).  \n\n>Unlike black-box neural methods, these approaches not only approximate GED but also provide the edit path, offering insights into structural modifications. However, their *approximation quality* is often inferior to neural approaches~\\citep{ranjan2022greed, simgnn}, driving the shift toward neural architectures. Additionally, these methods often involve solving complex optimization problems, such as **MIP**, to derive node alignments between graphs.  \n\n>### **Neural Methods**  \n>Recent advancements favor graph neural networks (GNNs) for GED approximation due to their superior accuracy over non-neural methods \\citep{ranjan2022greed,h2mn,simgnn,piao2023computing,genn,eric,graphedx,graphsim,graphotsim,icmlged}. These models take pairs of graphs with known GED values as input and are trained to predict GED distances. However, since computing true GED is NP-hard, training these models efficiently for large graphs or datasets remains a significant challenge.  \n\n>Among the leading algorithms, **GREED** \\citep{ranjan2022greed} employs siamese GNNs with an inductive bias to learn GED while preserving its metric properties. **H$^2$MN** \\citep{h2mn} utilizes a hierarchical hypergraph matching network for graph similarity learning. Other state-of-the-art approaches, such as **GEDGNN** \\citep{piao2023computing}, **ERIC** \\citep{eric}, and **GraphEdX** \\citep{graphedx}, further explore GNN-based architectures for GED prediction.", "claims_and_evidence": "Yes, the evidence is supported by clear and convincing evidence", "methods_and_evaluation_criteria": "Yes, the proposed method makes sense for the application.", "theoretical_claims": "There are many theoretical proofs in the appendix, and they all seem to be very solid.", "experimental_designs_or_analyses": "The design of the experiment is comprehensive.", "relation_to_broader_scientific_literature": "The use of large language models will bring new insights and inspiration to the field.", "essential_references_not_discussed": "The author should have discussed most of the relevant works.", "other_strengths_and_weaknesses": "**Strengths**\n\nS1. GRAIL is novel in that it uses a large language models generator to calculate graph editing distance (GED).\n\nS2. The manuscript is well written, such as the Introduction Section provides an easy access to the existing challenges and contributions.\n\nS3. The analysis of the experiment seems very reasonable and comprehensively shows that the proposed method is effective.\n\n**Weaknesses**\n\nW1. I am concerned that the effectiveness of this work is heavily reliant on the capabilities of large language models, rather than the inherent architectural design proposed in the paper.\n\nW2. In the main text, there is a lack of detailed introduction of related works, which is not conducive to readers who are not familiar with the field to understand the background and significance of this work.", "other_comments_or_suggestions": "Answer the W1-W2", "questions_for_authors": "Answer the W1-W2", "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": "yAG2B3wJbp", "reviewer": "Reviewer_cLnD", "summary": "In this paper, the authors introduced a new paradigm of computing GED by leveraging LLMs to autonomously generate programs. Unlike traditional methods that rely on neural networks and require computationally expensive, NP-hard ground truth data, proposed method employs a self-evolutionary strategy to discover programs without any ground truth data.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1: Is the role of the LLM merely to generate code programs? What are the advantages of this approach compared to manually collecting a series of graph edit distance programs?**\n    \n**Ans:** Yes, the LLM's role is to generate code as  responses to strategically curated prompts. This approach offers several advantages over manually collecting heuristics. \n\n* First, the LLM can explore an essentially *infinite space of heuristics*, far beyond what is feasible by human design alone. \n* Second, it enables *rapid iterative improvements* through prompt-tuning and feedback, which greatly accelerates the development cycle compared to the slow, trial-and-error process of manual design. \n* Finally, there is no comprehensive repository of human-devised heuristics for GED—the most extensive benchmark we know is by Blumenthal et al.—and our LLM-generated methods not only broaden the search space but also consistently outperform these limited manual methods.\n\n    \n**W2: In Table 3 and Table 4, GRAIL does not perform optimally on ogbg-molpcba. It is recommended that the authors provide reasons and insights for this observation.**\n    \n**Ans:** In this dataset, GRAIL is outperformed by GREED. GRAIL constructs a bipartite graph between node pairs across graphs, where edge weights encode similarity based on topological and node label similarities within their $l$-hop neighborhoods. The LLM-generated code computes these similarities, with $l=2$ fixed across all datasets.\n\nIn contrast, GREED employs _jumping knowledge_, concatenating node embeddings from multiple hops (1 to 7), allowing an MLP to learn which depth is most effective for GED approximation. If we adopt a similar strategy in GRAIL—computing GED using $l=1,2,3$ and selecting the minimum (as the tightest upper bound corresponds to the minimum)—GRAIL achieves performance competitive with GREED. The detailed results are presented below.\n\nThis finding suggests that, in ogbg-molpcba, using a uniform topological depth for all nodes is suboptimal for GED approximation. Adapting the neighborhood depth dynamically can significantly improve accuracy.\n    \n### RMSE values of Grail at various topological depths compared to the RMSE of GREED, which is 2.48\nDepth | GRAIL |\n---|---|\n$l=1$ | 3.18\n$l=1,2$ | 2.73\n$l=1,2,3$ | 2.68\n\n---------------\n\n**Summary:** We appreciate the reviewer’s constructive feedback and the opportunity to improve our work. We hope that our additional clarifications effectively address the outstanding concerns. If the reviewer finds our manuscript strengthened by these revisions, we would be grateful for a reassessment of our work’s rating.", "claims_and_evidence": "Yes, the claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "I believe that the method in this paper is relatively reasonable.", "theoretical_claims": "The paper does not include theoretical proofs, so there is no need to verify the correctness of the theoretical claims in the paper.", "experimental_designs_or_analyses": "Yes, the experimental designs and analysis of the paper are reasonable.", "relation_to_broader_scientific_literature": "No", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths\n1.  The structure of the paper is clear and easy to follow.\n2.  The method is effective in comparison to baseline methods.\n\nWeaknesses\n1. Is the role of the LLM merely to generate code programs? What are the advantages of this approach compared to manually collecting a series of graph edit distance programs?\n2. In Table 3 and Table 4, GRAIL does not perform optimally on ogbg-molpcba. It is recommended that the authors provide reasons and insights for this observation.", "other_comments_or_suggestions": "No", "questions_for_authors": "Please refer to the weaknesses section.", "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": "lxNxMitp4M", "reviewer": "Reviewer_vS7D", "summary": "This paper presents an evolutionary-based algorithm that generates better programs by large language models to calculate heuristics scores for graph edit distance. With generated scores, the LLM-discovered algorithm achieved better heuristic prediction than other GED methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1(a) Take the top-15 performing GED heuristics from \\[Blumenthal et al. 2020\\] and evaluate the performance of that \"ensembled\" algorithm**\n\n**Ans:** First, we would like to clarify that several non-neural heuristics also consider multiple solutions. Specifically, branch-and-bound methods (e.g., **BRANCH**) and MIP approaches (**LP-GED-F2, ADJ-IP, COMPACT-MIP**) explore multiple candidate solutions that satisfy the given constraints, selecting the one with the tightest upper bound. \n\nNonetheless, we have conducted the suggested experiment. Specifically, we select the 15 non-neural heuristics from Blumenthal et al., based on their tightness of upper bounds. For each graph pair, we applied all 15 heuristics and chose the minimum computed distance. As shown in the results below, **GRAIL continues to outperform this ensemble approach**. We also note that Grail is more than $\\approx 168$-times faster.\n\n1. ADJ-IP\n2. NODE\n3. LP-GED-F2\n4. BRANCH-TIGHT\n5. COMPACT-MIP\n6. IPFP\n7. BRANCH-CONST\n8. BRANCH-COMPACT\n9. BRANCH-FAST\n10. BP-BEAM\n11. BRANCH\n12. K-REFINE\n13. STAR\n14. REFINE\n15. F1\n\n### RMSE\n|Dataset|Ensemble Non-neural|GRAIL|\n|-|-|-|\n| AIDS|0.73|**0.57**|\n| LINUX|0.23|**0.13**|\n| IMDB|0.72|**0.55**|\n| molhiv|3.13|**2.96**|\n| code2|7.10|**4.22**|\n| molpcba|3.66|**3.18**|\n\n**W1(b) -   Take each scoring function generated by LLM and compare that with traditional heuristics.**\n\n**Ans:** \"In the table below, we report the best, worst, and average RMSEs for the 15 heuristics identified by Grail, denoted as Min, Max, and Avg, respectively. Similarly, we provide the Min, Max, and Avg RMSEs for the ensemble of non-neural heuristics.\n\nNotably, the best non-neural heuristic outperforms the best function identified by Grail in 4 out of 6 datasets. However, this result aligns with our expectations, as Grail does not aim to find a single optimal function with the lowest RMSE. Instead, leveraging a submodular loss function, it seeks a diverse set of complementary heuristics that collectively minimize RMSE across the training set of graph pairs.\"\n\n|Dataset|AIDS|Linux|IMDB|molhiv|code2|molpcba|\n|-|-|-|-|-|-|-|\n| **Min** Grail | 1.90 | 0.49| 3.19| 6.23| 6.48| 6.61|\n| **Max** Grail|3.33 |1.32| 7.48|8.27|17.97|9.40|\n| **Avg.** Grail| 2.57|0.96| 5.04|7.16|12.10|7.96|\n| **Min** Non-Neural |0.85|0.23| 3.90 |4.50|8.34 |4.94|\n| **Max** Non-Neural|15.23|6.72|69.45|24.97|92.67|29.22|\n| **Avg** Non-Neural|7.62|4.08|16.99|16.52|39.24 |19.37|\n\n**W2(a):** **Qualitative evaluation of how the generated heuristics look like and how different are they from those published ones.**\n    \n**Response:**  The heuristics discovered by Grail are fundamentally different from the top-performing heuristics in Blumenthal et al. Specifically:  \n\n- **NODE** and **BRANCH** transform GED into a linear sum assignment problem.  \n- **LP-GED-F2, ADJ-IP,** and **COMPACT-MIP** use mixed integer programming.  \n- **IPFP** reduces GED to the quadratic assignment problem (QAP), which is also NP-hard and relies on heuristics to approximate the QAP.  \n\nIn contrast, our discovered heuristics compute similarity between all node pairs across the two graphs followed bipartite matching. This similarity is determined by measuring the distance between various vertex invariants—such as node labels, degree, etc.—within their $l$-hop neighborhoods. The heuristics differ in their choice of vertex invariants, distance functions, and $l$. \n\nWe provide one example in **Fig. 11**. The complete repository of discovered heuristics is available at https://anonymous.4open.science/r/GRAIL-FEE5/ inside src/discovered_programs.  \n\n**W2(b). It is very likely that those GED heuristics papers are part of the LLM training dataset, therefore showing quantitatively that LLM discovered something different from existing literature is important for the novelty of this manuscript.**\n\n**Response:** While the possibility of the heuristics being part of the training data can't be ruled out, we hypothesize that if the LLM has seen them during training, then it should be able to directly retrieve the programs without reducing GED to a bipartite matching problem, and then prompt tuning.\n\nTo test this hypothesis, we prompted the LLM to generate code for GED directly, rather than predicting the weights of the bipartite graph. As shown below (**Direct**), the results deteriorate significantly, suggesting that the LLM alone is unable to retrieve effective heuristics without our structured formulation.\n\n||DATASET|AIDS|Linux|IMDB|molhiv|code2|molpcba|\n|-|-|-|-|-|-|-|-|\n| **RMSE**|**GRAIL**|**0.57**|**0.13**|**0.55**|**2.96**|**4.22**|**3.18**|\n| |  **Direct fns (15)**|7.95|2.81|112.64| 7.47| 25.68| 9.71|\n| **EMR**|**GRAIL**|0.8 |~1|~1| 0.2| 0.12|0.12|\n| | **Direct fns (15)**| 0.01| 0.14| 0.09|0.02|0|0.02|\n---------\n**Summary:** We appreciate the reviewer’s insightful suggestions and have incorporated the recommended experiments to further validate our approach. We hope these results clarify the merits of our work.", "claims_and_evidence": "(+) All claims seem well-grounded by empirical evaluations on various graph datasets.", "methods_and_evaluation_criteria": "(+) Most peer methods and evaluation criteria make sense for the problem.", "theoretical_claims": "(+) I checked the theoretical claims and they are straightforward and align with my intuition. Therefore I did not check the detailed proofs.", "experimental_designs_or_analyses": "(+) Most numerical evaluations are sound and the improvement is solid and impressive.\n\n(-) One concern is that the LLM-generated algorithm allows 15 different scoring functions while most non-neural GED heuristics contain only one scoring function, the following two baselines should be considered to decouple the improvement from simply adding more scoring functions:\n* Take the top-15 performing GED heuristics from [Blumenthal et al. 2020] and evaluate the performance of that \"ensembled\" algorithm\n* Take each scoring function generated by LLM and compare that with traditional heuristics.\n\n(-) Also, it is worth doing a qualitative evaluation of how the generated heuristics look like and how different are they from those published ones. It is very likely that those GED heuristics papers are part of the LLM training dataset, therefore showing quantitatively that LLM discovered something different from existing literature is important for the novelty of this manuscript.", "relation_to_broader_scientific_literature": "(+) This paper has its novelty due to the fundamental nature of GED (and other NP-hard problems) and tackling them by LLM-generated algorithms is interesting.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I would be more than glad to see the authors' responses to my questions on 1 scoring function vs 15 and potential qualitative evaluations. That is the critical limitation for me to be more positive about this submission or turn negative.", "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:

Meta-review: This paper proposes GRAIL, a two-stage approach using large language models (LLMs) to generate heuristic programs for approximating graph edit distance (GED). GRAIL aims to address limitations of existing neural and non-neural methods and demonstrates strong empirical results.  
   
**Reviewer Comments:**    
- **Reviewer vS7D** recognized the novelty of leveraging LLMs for GED and the comprehensive experiments, but questioned if the improvements were simply due to ensembling multiple scoring functions rather than methodological breakthroughs. After rebuttal, was more positive but recommended additional qualitative comparisons to prior heuristics.  
- **Reviewers isZf and cLnD** appreciated the empirical results and clarity, but both expressed concern that GRAIL’s effectiveness may mostly derive from LLM capabilities rather than algorithmic advancement. They also noted limited discussion of related work and baseline diversity, though these were partially addressed in the rebuttal.  
- **Reviewer YCYA** had major theoretical concerns: they questioned the motivation for decomposing GED into two subproblems and pointed out that the proposed decomposition and upper-bound minimization lack clear theoretical justification or guarantees. YCYA also noted the absence (at original submission time) of fair baselines directly prompting LLMs for GED, and remained unconvinced even after the rebuttal.  
   
**Author Response:**    
The authors provided new experiments and clarifications in response to reviewer critiques. However, the fundamental issues regarding the theoretical grounding and the actual advantage of the two-stage decomposition over direct LLM approaches remain insufficiently addressed.  
   
**Conclusion:**    
While this submission has some strengths in empirical evaluation, taking into account the substantive unresolved theoretical concerns and considering the overall quality of other papers in my batch, I recommend weak accept of this submission.
Decision: Accept (poster)