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

Ananya Mathur; Ankit Anand; Arushi Goyal; Samidha Verma; Sayan Ranu

REVIEW 1 major objections 5 minor 42 references

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

T0 review · 1 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that an LLM can be steered by evolutionary prompt tuning to write short programs that, through maximum-weight bipartite matching, give tight upper bounds on graph edit distance and beat supervised neural and non-neural…

desk verdict GRAIL has a genuinely useful idea—LLM-evolved code for GED upper bounds—but the main selection loop as written is sign-inverted and cannot work; fix that before believing the empirical claims. read the letter →

arxiv 2505.02124 v1 pith:VQGXDYXD submitted 2025-05-04 cs.LG

Samidha Verma , Arushi Goyal , Ananya Mathur , Ankit Anand , Sayan Ranu This is my paper · ORCID

classification cs.LG

keywords grapheditdistanceLLMprogramgenerationevolutionaryprompttuningbipartitematchingupperboundoptimizationsubmodularselectioncross-domaingeneralizationinterpretableheuristics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that graph edit distance (GED), a similarity measure whose exact computation is NP-hard, can be approximated by asking a large language model to write small graph-alignment programs and then evolving those programs through prompt feedback. The key move is to measure each program not by how close its output is to a labeled GED but by how tight an upper bound its induced node mapping gives on the true GED; because every mapping produced by a program is a feasible edit path, the bound is guaranteed to be an upper bound, so minimizing it never needs ground-truth labels. On six benchmark datasets the discovered programs report lower RMSE than existing neural and non-neural baselines, and a version trained once on a mixture of datasets transfers to all tested domains. A sympathetic reader would care because this replaces the pipeline of generating NP-hard training labels and training black-box models with an interpretable, self-evolving program search.

What carries the argument

The load-bearing mechanism is the reduction of GED approximation to maximum-weight bipartite matching with LLM-generated weights, combined with an upper-bound objective. Concretely, a program maps a graph pair to a weight matrix; running a bipartite matching algorithm, here the Neighbor-biased mapper, gives a bijection between nodes, and evaluating the edit cost of that bijection gives an upper bound on the true GED. Since any single mapping is feasible, the prediction cannot undercut the true distance, which makes the training signal (the sum over training pairs of the minimum upper bound among selected programs) a surrogate for approximation error that requires no labels. The evolutionary prompt loop keeps the top-scoring short programs, asks the LLM to improve them, filters for executability and runtime, and reselects a budget of complementary programs by greedy submodular maximization.

What would settle it

Hold the model, prompt template, and datasets fixed, but replace the evolutionary top-k feedback with a loop that always feeds the initial trivial program back to the LLM; if the resulting answer set still matches GRAIL's RMSE, then the claimed discovery process is not what carries the result.

Watch

Extended reading notes

Core claim

GRAIL treats GED approximation as the problem of learning a program that outputs a weight matrix for a fully connected bipartite graph between the nodes of two graphs; a maximum-weight bipartite matching on that graph yields a node mapping, and the GED of that mapping is an upper bound on the true GED. The paper claims that an LLM, prompted with the problem definition and the best programs found so far, can mutate and combine programs until the greedy submodular selection of a budget of programs stops improving the training objective, which sums over training pairs the minimum upper bound among selected programs. Because this objective is an upper bound and is monotone submodular, greedy selection yields a good answer set, and because the program pool is evolved by LLM prompt feedback, no ground-truth GED is needed. Empirically, the resulting programs outperform the neural baselines GREED, GEDGNN, ERIC, H2MN, and GRAPHEDX, as well as the leading non-neural heuristics, on the six benchmark datasets, including a trained-once mixture variant.

Load-bearing premise

The load-bearing premise is that the LLM, when shown the current best programs and asked to mutate them, will keep producing new programs that improve the training objective; if the model fails to generate useful mutations, the whole loop degenerates to the trivial zero-weight program and the method collapses.

Editorial extensions

If this is right

Approximating GED no longer requires NP-hard ground-truth labels; training a GRAIL-style system needs only unlabeled graph pairs and LLM calls.
The discovered programs are executable, short code, so the resulting heuristic and the node alignment it induces are open to inspection and manual improvement.
A single program set trained once on a mixture of datasets transfers across domains, graph sizes, and label sets, eliminating per-dataset retraining.
Because every predicted GED is an upper bound on the true distance, the method can never quietly underestimate similarity, a useful property for downstream search and filtering.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An implication the paper leaves implicit is that the upper-bound guarantee makes the program set usable as an admissible pruning rule in similarity search: any pair whose upper bound already exceeds a query threshold can be safely discarded.
The method's ceiling is set by the LLM's mutation diversity, which suggests a testable extension: seeding the prompt pool with human-written heuristic programs, or with programs from several different LLMs, and measuring whether the discovered answer set improves.
The interpretability claim could be quantified by measuring the shortest program length that still reaches a given RMSE, and comparing those programs against the best known hand-designed GED heuristics.
The reported ground-truth evaluation is confined to graphs of at most a few dozen nodes; an extension would test the upper-bound gap on larger graphs using exact solvers or tight lower bounds where available.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Read GRAIL. The core idea is good: instead of training a neural net to predict GED, evolve an LLM-written program that outputs bipartite-matching weights, and use the resulting mapping's cost as a ground-truth-free upper bound. That reformulation, the submodular map selection, and the interpretable code output are genuine additions, and the cross-domain results (IMDB, Linux, molecules) are the kind of thing that would make this a useful paper if the machinery works. Credit where due: the paper ships code, uses only 1,000 training pairs, and the upper-bound objective is a legitimate way to avoid NP-hard labels.

But there is a load-bearing flaw in the text. Section 3.2 defines J(A) to be minimized; adding a program can only decrease J, so J(A∪{P})−J(A) is never positive. Algorithm 1 line 3 nevertheless takes arg max over that non-positive quantity, which selects the program with the smallest (least negative) reduction. Equation 6 assigns that same quantity as score, and §4.2 says the sampler prefers high scores—again favoring programs that barely reduce the bound. Lemma 2's submodularity inequality is also written for the wrong sign. If the implementation follows the paper, the central evolutionary loop cannot discover improving programs, and the reported gains would be impossible. The obvious correction is to maximize J(A)−J(A∪{P}) (equivalently, work with −J), but the text as written does not say that.

The empirical section has softer problems. GEDGNN beats GRAIL on ogbg-molhiv (RMSE 1.75 vs 2.96; EMR 0.57 vs 0.20), so 'comprehensively outperforms' is wrong. There are no error bars or seeds for a stochastic LLM pipeline, Table 6 claims inter-domain generalization without comparing to any neural baseline on off-diagonal entries, and a natural unsupervised baseline like EUGENE is cited but not benchmarked. The NP-hardness reduction in A.1.1 is also too loose to verify: it constructs a bipartite graph but never connects it to a training set T.

Bottom line: this is a promising direction and deserves serious referee time, but the version as written is not acceptable. The authors need to confirm the code's selection sign, fix Algorithm 1/Eq. 6/Lemma 2, add variance estimates, and moderate the claims. I would not cite it until those are resolved.

Referee Report

1 major / 5 minor

Summary. The paper proposes GRAIL, a framework that uses an LLM in an evolutionary loop to generate executable programs that compute node similarity matrices for maximum-weight bipartite matching. The resulting node mappings yield upper bounds on the true graph edit distance, and a greedy selection chooses a bounded set of complementary programs. The authors report RMSE and exact-match-ratio results on six benchmark datasets, plus a variant (GRAIL-MIX) trained on a mixture of datasets to demonstrate cross-domain transfer. The central claim is that GRAIL achieves competitive or better approximation quality than neural and non-neural baselines without any ground-truth GED supervision during training.

Significance. The idea of replacing a neural regressor with an LLM-evolved program is novel and, if sound, would be a meaningful contribution to the GED approximation literature. The upper-bound formulation is elegant and genuinely avoids the need for NP-hard training labels, in contrast to most neural baselines. The paper also emphasizes interpretability of the discovered programs and releases its codebase, which is a further strength. However, the significance is heavily contingent on the correctness of the evolutionary selection loop and on the reliability of the empirical comparison; the concerns below show that both require substantial revision before the claims can be accepted.

major comments (1)

[§A.1.2, Lemma 2] The submodularity inequality is stated in the wrong direction. For A′ ⊆ A, the marginal decrease from adding P is larger for the smaller set; a concrete assignment shows J(A∪{P})−J(A) ≥ J(A′∪{P})−J(A′) rather than the reverse. For example, with a single graph pair and costs c_a=3, c_b=1, c_P=2, take A'={a}, A={a,b}. Then J(A')=3, J(A)=1, J(A'∪{P})=2, J(A∪{P})=1, so J(A∪{P})−J(A)=0 and J(A'∪{P})−J(A')=−1, violating the claimed inequality. The monotonicity lemma is correct, but the proof of submodularity does not go through, so the greedy selection in Algorithm 1 is not justified as a submodular greedy method. If the authors instead define the gain function G(A)=J(∅)−J(A), then G is monotone submodular, and the standard (1−1/e) guarantee applies to selecting the b programs with maximum final gain; the paper should be rewritten around that formulation.

minor comments (5)

[§5.1, Tables 3 and 4] The empirical comparison reports a single run for each variant, with no error bars or multiple seeds. GRAIL is stochastic in two ways: the LLM is sampled at temperature 0.99, and the island/cluster selection in the evolutionary loop is randomized. Different runs can therefore produce different programs and different RMSE/EMR values. Given that several comparisons are decided by small margins (e.g., AIDS RMSE 0.57 vs 0.61; ogbg-molhiv 2.96 vs 3.02), the reported rankings and the claim that GRAIL "consistently ranks among the top algorithms" are not yet supported. At minimum, the authors should report the mean and standard deviation over at least several independent evolutionary runs.
[§5.3, Tables 5 and 6] The inter-domain generalization claim is not directly supported by the experiments. Table 6 shows GRAIL models transferring across datasets, but there is no neural baseline evaluated on the same off-diagonal transfer tasks; Table 5 only compares GREED within the molecule domain, and the "NA" entries mean the comparison set is incomplete. Therefore the statement that this ability is "not seen in neural approximators" (end of §5.3) is an overreach. The authors should either include cross-domain runs of neural baselines on the same train/test combinations or restrict the claim to what the experiments show.
[§5.2, Table 3] The statement that GRAIL "comprehensively outperform[s] the baselines" is too strong, since GREED achieves lower RMSE than GRAIL on ogbg-molpcba (2.48 vs 3.18) and GEDGNN achieves lower RMSE on ogbg-molhiv (1.75 vs 2.96). The wording should be softened to "on average" or "in most datasets."
[Abstract] The abstract says "seven datasets," but Tables 3 and 4 benchmark only six; ogbg-ppa is used only in the scale experiment of Fig. 3a. Please correct the count.
[§4.2] There is a typo in the sentence "Since the programs evolve through mutations introduced by the LLM, the selection mechanism optimizes two distinct objectives." The comma after "LLM" should be removed or the sentence restructured.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: GRAIL's predictions are evaluated against externally computed ground-truth GED, and the upper-bound objective is not a re-labeled fit.

full rationale

GRAIL's claimed derivation is self-contained. Training minimizes J(A) = sum over training pairs of min_{P in A} GED_{pi(P)}(G1,G2) (Eq. 5), and since Definition 4 defines true GED as the minimum over all mappings, every GED_{pi(P)} is a guaranteed upper bound on the true GED. The objective is therefore not defined in terms of the test quantity; for any training pair, |pred - true| = pred - true because pred >= true, so minimizing the upper bound is legitimately equivalent to minimizing approximation error on those pairs. Test performance is measured against held-out ground truth computed by MIP-F2 (Appendix A.3.1) and is not used to fit any parameter. The paper's citations, including FunSearch, are used as algorithmic building blocks and are not load-bearing uniqueness claims. One internal concern is worth separating from circularity: Algorithm 1 and Eq. 6 define score(P) = J(A union {P}) - J(A), which by monotonicity is non-positive, so selecting the arg max would prefer the program with the smallest reduction; this is an optimization-sign inconsistency, not a circular reduction of the reported predictions to the training inputs.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The method introduces no new physical or mathematical entities. Its main assets are the LLM oracle and the evolutionary search, which are inputs rather than invented objects. The free parameters are standard hyperparameters, and the axioms are the upper-bound property, submodularity, LLM competence, and exactness of the filtered ground truth.

free parameters (5)

b (function budget) = 15
Selected by ablation (Fig. 3b); the answer set size at inference.
k (top programs in prompt) = 2
Hyper-parameter chosen based on no significant improvement for larger k (App. A.2.1).
number of islands = 5
Hyper-parameter for evolutionary selection.
temperature = 0.99
LLM sampling temperature for program generation.
LLM model = Gemini 1.5 Pro (gemini-1.5-pro-001)
The fixed language model used; results may differ with other models.

assumptions (4)

standard math For any node mapping π, the edit cost GEDπ(G1,G2) is an upper bound on the true GED(G1,G2).
Direct consequence of Definition 4, where GED is the minimum over all mappings; used in Section 3 to justify replacing the true GED loss with an upper-bound objective.
standard math J(A) is monotone and submodular, enabling greedy selection.
Claimed by Lemma 1 and 2 in App. A.1.2; true for functions that are a sum of minimums over element costs, though the proof in the appendix is informal.
ad hoc to paper The LLM can be evolved via prompts to produce programs that improve J(A) on training pairs and transfer to test pairs.
Empirical premise of Sections 4.1-4.3; without it the method degenerates to a single trivial mapping.
domain assumption MIP-F2 with a 600-second time limit gives exact GED values for the test pairs that are kept.
App. A.3.1; test pairs are filtered to those with matching lower and upper bounds, which is reasonable for small graphs but not guaranteed for larger ones.

how reviews work

0 comments

Cite this review

Pith. "Pith review of GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code." pith.science (2026). https://pith.science/paper/VQGXDYXD

@misc{pith2026250502124,
  author       = {Pith},
  title        = {Pith review of: GRAIL: Graph Edit Distance and Node Alignment Using LLM-Generated Code},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VQGXDYXD}},
  note         = {Machine review of arXiv:2505.02124}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2505.02124 by the authors.

**Figure 2.** Pipeline of GRAIL. GED is computed based on the mapping π(B). 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. Problem 2 (Weight Matrix Generation). Given train set T = {⟨G1, G ′ 1 ⟩, · · · ,⟨Gn, G ′ n ⟩}, generate a program P that take… view at source ↗

**Figure 3.** (a) GRAIL-MIX at scale: Performance of GRAIL-MIX on the ogbg-ppa dataset when compared to the top-3 non-neural baselines on the basis of average rank in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (8 more)

**Figure 4.** Figure 4: Example of an input prompt to GRAIL Hyper-parameters: Table H lists the hyper-parameters used for GRAIL. k stands for the number of functions per response generated by the LLM and b is the function budget employed for submodularity while training. We decided to use k a…

**Figure 5.** Figure 5: Avg. Upper Bound vs function budget (b) for submodular greedy selection • ogbg-molhiv and ogbg-molpcba: These are chemical compound datasets, with each graph representing a molecule. Nodes in these graphs correspond to atoms and are labeled with their atomic numbers, w…

**Figure 6.** Figure 6: (a) Training Time: Comparison of GRAIL with the top-3 neural methods in [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]

**Figure 7.** Figure 7: Avg. RMSE vs. Avg. Graph Size comparison on IMDB, Linux and ogbg-code2 datasets. GRAIL-MIX outperforms the best baselines at 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…

**Figure 8.** Figure 8: Performance comparison of Top-b vs. Greedy Submodular on the test set of AIDS dataset with an increasing number of LLM calls. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_8.png]

**Figure 9.** Figure 9: IMDB Case Study: The left-most graph represents Graph 1, while the middle and right-most graphs depict Graph 2 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 method…

**Figure 10.** Figure 10: IMDB Case Study: Heatmap of weight matrix generated by (a) GRAIL-MIX (Fig: 11) and (b) GEDGNN 18 [PITH_FULL_IMAGE:figures/full_fig_p018_10.png]

**Figure 11.** Figure 11: IMDB Case Study: Program discovered by GRAIL-MIX that has minimum individual RMSE on IMDB dataset. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 30 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...
[2]

and Zhao, P

Bai, J. and Zhao, P. Tagsim: type-aware graph similarity learning and computation. Proc. VLDB Endow., 15 0 (2): 0 335–347, October 2021. ISSN 2150-8097. doi:10.14778/3489496.3489513. URL https://doi.org/10.14778/3489496.3489513

arXiv 2021
[3]

Simgnn: A neural network approach to fast graph similarity computation

Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., and Wang, W. Simgnn: A neural network approach to fast graph similarity computation. In WSDM, WSDM '19, pp.\ 384–392, 2019

work page 2019
[4]

Learning-based efficient graph similarity computation via multi-scale convolutional set matching

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

work page 2020
[5]

Blumenthal, D. B. New techniques for graph edit distance computation. CoRR, abs/1908.00265, 2019. URL http://arxiv.org/abs/1908.00265

arXiv 1908
[6]

Blumenthal, D. B. and Gamper, J. Improved lower bounds for graph edit distance. IEEE Transactions on Knowledge and Data Engineering, 30 0 (3): 0 503--516, 2018. doi:10.1109/TKDE.2017.2772243

arXiv 2018
[7]

Blumenthal, D. B. and Gamper, J. On the exact computation of the graph edit distance. Pattern Recogn. Lett., 134 0 (C): 0 46–57, June 2020. ISSN 0167-8655. doi:10.1016/j.patrec.2018.05.002. URL https://doi.org/10.1016/j.patrec.2018.05.002

doi:10.1016/j.patrec.2018.05.002 2020
[8]

B., Boria, N., Gamper, J., Bougleux, S., and Brun, L

Blumenthal, D. B., Boria, N., Gamper, J., Bougleux, S., and Brun, L. Comparing heuristics for graph edit distance computation. The VLDB journal, 29 0 (1): 0 419--458, 2020

work page 2020

Show all 42 references

[9]

R., Ranu, S., and Karras, P

Bommakanti, A., Vonteri, H. R., Ranu, S., and Karras, P. Eugene: Explainable unsupervised approximation of graph edit distance, 2024 a . URL https://arxiv.org/abs/2402.05885

2024
[10]

R., Skitsas, K., Ranu, S., Mottin, D., and Karras, P

Bommakanti, A., Vonteri, H. R., Skitsas, K., Ranu, S., Mottin, D., and Karras, P. Fugal: Feature-fortified unrestricted graph alignment. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 b

2024
[11]

Hogmmnc: a higher order graph matching with multiple network constraints model for gene--drug regulatory modules identification

Chen, J., Peng, H., Han, G., Cai, H., and Cai, J. Hogmmnc: a higher order graph matching with multiple network constraints model for gene--drug regulatory modules identification. Bioinformatics, 35 0 (4): 0 602--610, 2019

2019
[12]

Graph matching applications in pattern recognition and image processing

Conte, D., Foggia, P., Sansone, C., and Vento, M. Graph matching applications in pattern recognition and image processing. Proceedings 2003 International Conference on Image Processing (Cat. No.03CH37429), 2: 0 II--21, 2003. URL https://api.semanticscholar.org/CorpusID:267842199

2003
[13]

H., Leiserson, C

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. ISBN 0262033844

2009
[14]

D., Manchanda, S., Mahapatra, S., and Reddy, C

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

2021
[15]

Spectral graph matching and regularized quadratic relaxations: Algorithm and theory

Fan, Z., Mao, C., Wu, Y., and Xu, J. Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Res...

2020
[16]

D., Rusch, T

Giovanni, F. D., Rusch, T. K., Bronstein, M., Deac, A., Lackenby, M., Mishra, S., and Veli c kovi \'c , P. How does over-squashing affect the power of GNN s? Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https://openreview.net/forum?id=KJRoQvRWNs

2024
[17]

Gordon, V. S. and Whitley, L. D. Serial and parallel genetic algorithms as function optimizers. In Proceedings of the 5th International Conference on Genetic Algorithms, pp.\ 177–183, San Francisco, CA, USA, 1993. Morgan Kaufmann Publishers Inc. ISBN 1558602992

1993
[18]

and Singh, A

He, H. and Singh, A. Closure-tree: An index structure for graph queries. In 22nd International Conference on Data Engineering (ICDE'06), pp.\ 38--38, 2006. doi:10.1109/ICDE.2006.37

2006 doi
[19]

Hopcroft, J. E. and Karp, R. M. An n\^ 5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2 0 (4): 0 225--231, 1973

1973
[20]

Open graph benchmark: Datasets for machine learning on graphs

Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Syste...

2020
[21]

Open graph benchmark: Datasets for machine learning on graphs, 2021

Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs, 2021. URL https://arxiv.org/abs/2005.00687

2021 arXiv
[22]

Graph edit distance with general costs using neural set divergence

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 on Neural Information Processing Systems, 2024

2024
[23]

and Hero, A

Justice, D. and Hero, A. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 0 (8): 0 1200--1214, 2006. doi:10.1109/TPAMI.2006.152

2006 doi
[24]

Kuhn, H. W. The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2 0 (1-2): 0 83--97, 1955

1955
[25]

An integer projected fixed point method for graph matching and map inference

Leordeanu, M., Hebert, M., and Sukthankar, R. An integer projected fixed point method for graph matching and map inference. Advances in neural information processing systems, 22, 2009

2009
[26]

New binary linear programming formulation to compute the graph edit distance

Lerouge, J., Abu-Aisheh, Z., Raveaux, R., H \'e roux, P., and Adam, S. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, 72: 0 254--265, 2017 a

2017
[27]

New binary linear programming formulation to compute the graph edit distance

Lerouge, J., Abu-Aisheh, Z., Raveaux, R., Héroux, P., and Adam, S. New binary linear programming formulation to compute the graph edit distance. Pattern Recognition, 72: 0 254--265, 2017 b . ISSN 0031-3203. doi:https://doi.org/10.1016/j.patcog.2017.07.029. URL https://www.scie...

2017 doi
[28]

Graph matching networks for learning the similarity of graph structured objects

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

2019
[29]

M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M

Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, abs/2007.08663, 2020. URL https://arxiv.org/abs/2007.08663

2007 arXiv
[30]

Computing graph edit distance via neural graph matching

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 0 (8): 0 1817--1829, 2023

2023
[31]

Greed: A neural framework for learning graph distance functions

Ranjan, R., Grover, S., Medya, S., Chakaravarthy, V., Sabharwal, Y., and Ranu, S. Greed: A neural framework for learning graph distance functions. Advances in Neural Information Processing Systems, 35: 0 22518--22530, 2022

2022
[32]

Answering top-k representative queries on graph databases

Ranu, S., Hoang, M., and Singh, A. Answering top-k representative queries on graph databases. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pp.\ 1163--1174, 2014

2014
[33]

P., Dupont, E., Ruiz, F

Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J., Ellenberg, J. S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 0 (7995): 0 468--475, 2024

2024
[34]

Global alignment of multiple protein interaction networks with application to functional orthology detection

Singh, R., Xu, J., and Berger, B. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105 0 (35): 0 12763--12768, 2008. doi:10.1073/pnas.0806627105. URL https://www.pnas....

2008 doi
[35]

L., Lyon, D., Junge, A., Wyder, S., Huerta-Cepas, J., Simonovic, M., Doncheva, N

Szklarczyk, D., Gable, A. L., Lyon, D., Junge, A., Wyder, S., Huerta-Cepas, J., Simonovic, M., Doncheva, N. T., Morris, J. H., and et al., P. B. String v11: protein–protein association networks with increased coverage, supporting functional discovery in genome-wide experimenta...

2019
[36]

Combinatorial learning of graph edit distance via dynamic embedding

Wang, R., Zhang, T., Yu, T., Yan, J., and Yang, X. Combinatorial learning of graph edit distance via dynamic embedding. In IEEE Conference on Computer Vision and Pattern Recognition, 2021

2021
[37]

Wang, X., Ding, X., Tung, A. K. H., Ying, S., and Jin, H. An efficient graph indexing method. In Proceedings of the 2012 IEEE 28th International Conference on Data Engineering (ICDE '12), pp.\ 210--221, USA, 2012. IEEE Computer Society

2012
[38]

N., Gomes, J., Geniesse, C., Pappu, A

Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Geniesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9 0 (2): 0 513--530, 2018

2018
[39]

and Vishwanathan, S

Yanardag, P. and Vishwanathan, S. Deep graph kernels. In Proceedings of 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

2015
[40]

H2mn: Graph similarity learning with hierarchical hypergraph matching networks

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 Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, pp.\ 2274–2284, New York, NY, USA...

2021
[41]

and Tan, G

Zhuo, W. and Tan, G. Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, 35: 0 30181--30193, 2022

2022
[42]

W., and et al., J

Zitnik, 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 0 (10): 0 4426--4433, 2019

2019

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

[2] [2]

and Zhao, P

Bai, J. and Zhao, P. Tagsim: type-aware graph similarity learning and computation. Proc. VLDB Endow., 15 0 (2): 0 335–347, October 2021. ISSN 2150-8097. doi:10.14778/3489496.3489513. URL https://doi.org/10.14778/3489496.3489513

arXiv 2021

[3] [3]

Simgnn: A neural network approach to fast graph similarity computation

Bai, Y., Ding, H., Bian, S., Chen, T., Sun, Y., and Wang, W. Simgnn: A neural network approach to fast graph similarity computation. In WSDM, WSDM '19, pp.\ 384–392, 2019

work page 2019

[4] [4]

Learning-based efficient graph similarity computation via multi-scale convolutional set matching

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

work page 2020

[5] [5]

Blumenthal, D. B. New techniques for graph edit distance computation. CoRR, abs/1908.00265, 2019. URL http://arxiv.org/abs/1908.00265

arXiv 1908

[6] [6]

Blumenthal, D. B. and Gamper, J. Improved lower bounds for graph edit distance. IEEE Transactions on Knowledge and Data Engineering, 30 0 (3): 0 503--516, 2018. doi:10.1109/TKDE.2017.2772243

arXiv 2018

[7] [7]

Blumenthal, D. B. and Gamper, J. On the exact computation of the graph edit distance. Pattern Recogn. Lett., 134 0 (C): 0 46–57, June 2020. ISSN 0167-8655. doi:10.1016/j.patrec.2018.05.002. URL https://doi.org/10.1016/j.patrec.2018.05.002

doi:10.1016/j.patrec.2018.05.002 2020

[8] [8]

B., Boria, N., Gamper, J., Bougleux, S., and Brun, L

Blumenthal, D. B., Boria, N., Gamper, J., Bougleux, S., and Brun, L. Comparing heuristics for graph edit distance computation. The VLDB journal, 29 0 (1): 0 419--458, 2020

work page 2020