GRAIL: Graph Edit Distance and Node Alignment using LLM-Generated Code

W1(a) Take the top-15 performing GED heuristics from $Blumenthal et al. 2020$ and evaluate the performance of that "ensembled" algorithm

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.

Nonetheless, 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.

1. ADJ-IP
2. NODE
3. LP-GED-F2
4. BRANCH-TIGHT
5. COMPACT-MIP
6. IPFP
7. BRANCH-CONST
8. BRANCH-COMPACT
9. BRANCH-FAST
10. BP-BEAM
11. BRANCH
12. K-REFINE
13. STAR
14. REFINE
15. F1

RMSE

W1(b) - Take each scoring function generated by LLM and compare that with traditional heuristics.

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.

Notably, 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."

W2(a): Qualitative evaluation of how the generated heuristics look like and how different are they from those published ones.

Response: The heuristics discovered by Grail are fundamentally different from the top-performing heuristics in Blumenthal et al. Specifically:

• NODE and BRANCH transform GED into a linear sum assignment problem.
• LP-GED-F2, ADJ-IP, and COMPACT-MIP use mixed integer programming.
• IPFP reduces GED to the quadratic assignment problem (QAP), which is also NP-hard and relies on heuristics to approximate the QAP.

In 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$.

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

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.

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.

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

---

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.

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?

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.

• First, the LLM can explore an essentially infinite space of heuristics, far beyond what is feasible by human design alone.
• 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.
• 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.

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.

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.

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

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

RMSE values of Grail at various topological depths compared to the RMSE of GREED, which is 2.48

---

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.

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.

---

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.

Ans: Our approach has four main components:

1. Reducing GED to bipartite matching
2. Learning weights of the bipartite graph using LLM
3. Prompt-tuning:
   • Scoring programs using submodular optimization
   • Genetic evolution.

Fig 3c in the manuscript is an ablation study showing that submodular optimization indeed helps (lines 417--430).

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

1. 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).

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

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.

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.

Non-Neural Methods

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}).

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.

Neural Methods

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.

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.