{"id":"9f88b39b-3de7-434d-aac9-3a2b0a356df3","arxiv_id":"2412.12185","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"GNA predicts GED and produces hard one-to-one node alignments via an unsupervised Gumbel-Sinkhorn module, outperforming prior soft-alignment models on three datasets.","lead":"This paper proposes GNA, a graph neural network that predicts graph edit distance while also producing a one-to-one node matching between two graphs, with no node-alignment labels. It combines a GIN encoder, a cost network, and a Gumbel-Sinkhorn module that outputs a hard, doubly stochastic alignment matrix, and reports gains over prior methods on three graph datasets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The matching module pads only the smaller graph with dummy rows (Eq. 6), so every original G1 node is forced to match a G2 node; it cannot represent deleting a node from the smaller graph, which breaks the claimed equivalence to classical GED and the interpretable alignment.","rationale":"The reader's weakest assumption concerns whether GIN embeddings alone make the linear assignment in Eq. 3 a faithful replacement for the quadratic assignment problem. That is a legitimate concern, but I think a more concrete and more load-bearing problem sits one level earlier: even if the embeddings were perfect, the assignment problem that GNA actually solves has the wrong feasible set. In Section 4.2 the smaller graph is padded only by adding rows to its embedding matrix, and the matching module outputs a square doubly stochastic matrix of size |V2| x |V2|. Consequently every original node of the smaller graph is forced to be matched to some node of the larger graph; there is no dummy column that would allow deleting such a node. Classical GED is symmetric in insertions and deletions, and the optimal edit path for pairs with unequal sizes frequently deletes nodes from the smaller graph. The model cannot represent those paths, so the one-to-one alignment it provides is not, in general, the optimal GED alignment, and the predicted edit distance is structurally biased whenever substitution is more expensive than deletion plus insertion. This directly attacks the paper's central claim of providing interpretable, classical-GED-like one-to-one node alignment, and it is testable on small graphs where exact GED can be computed. The issue is addressable by padding both rows and columns in the cost and matching matrices and retraining, which is why I do not recommend outright rejection; the verdict should remain conditional, but the condition should include this correction and a re-evaluation of Table 2. My agreement with the reader is partial because the embedding-capacity concern is related but secondary: fixing the embeddings cannot fix the missing dummy columns.","tokens_in":13107,"tokens_out":16141,"duration_ms":190947,"concrete_test":"Construct synthetic test pairs with |V1|<|V2| whose exact A* GED optimal edit path deletes at least one node of G1, and run the trained GNA. Because the matching matrix is |V2| x |V2| with no dummy columns, GNA's argmax assignment must place every original G1 row in a real G2 column; it cannot mark a deletion of that node. If for any such pair the predicted GED is systematically higher than exact GED, or if the alignment substitutes nodes that A* deletes, the representability flaw is confirmed. I would also rerun Table 2 after adding dummy columns to Eq. 6 and retraining, to see whether the reported gains survive a corrected edit-operation space.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The hard one-to-one assignment is built on a |V2| x |V2| cost/matching matrix obtained by appending |V2|-|V1| dummy rows to the smaller graph's embedding matrix (Section 4.2, Eq. 6). No dummy columns are created. In a permutation matrix of this size, each of the |V1| original rows must be matched to a distinct G2 column: every original G1 node is therefore substituted, never deleted. Classical GED, as defined in Section 3, permits insertions, deletions, and substitutions of nodes in either graph, and for many pairs with |V1|<|V2| the optimal edit path deletes at least one node from the smaller graph. GNA's feasible set excludes such edit paths by construction, so the output alignment cannot in general be the optimal GED alignment, and the predicted GED can be biased upward whenever deleting a small-graph node is cheaper than substituting it into the larger graph. This is independent of whether GIN embeddings capture subgraph structure: even with perfect node embeddings, the relaxed linear assignment in Eq. 3 is not solved over the same editing operations as classical GED. The qualitative case studies in Section 5.6 do not check whether GNA ever produces a deletion of an original smaller-graph node, so this representational gap is invisible in the reported validation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GNA, a graph neural network model that approximates Graph Edit Distance and also outputs a hard one-to-one node alignment, trained without node-alignment ground truth. A GIN encoder produces node embeddings; a costing module builds a node-pair edit-cost matrix; a Gumbel-Sinkhorn module generates a doubly stochastic matching matrix; and the element-wise product of matching and cost, plus a graph-level bias, is passed through a sigmoid and trained with MSE against normalized GED. Experiments on AIDS, Linux, and IMDB compare GNA with seven baselines on MAE, Accuracy, rank correlations, and P@10, and the paper includes ablation and visualization studies. Source code is released.","tokens_in":13407,"tokens_out":13337,"duration_ms":145198,"significance":"If the central claims hold, the paper would make a modest but useful contribution to interpretable graph similarity computation by showing that a differentiable Sinkhorn-based alignment layer can be trained end-to-end from GED targets alone and that the resulting alignment offers visual interpretability. The empirical comparison spans three standard benchmarks and seven baselines, the code is released, and the case studies in Section 5.6 are a genuine strength. The performance claim is plausible but is currently not fully supported by the reported tables, and the alignment module as formulated does not represent all edit operations permitted by classical GED, so the main interpretability claim needs technical revision.","major_comments":[{"comment":"The padding scheme appends only |V2|-|V1| dummy rows to the smaller graph and never creates dummy columns. In the resulting |V2| x |V2| permutation matrix, every original G1 row must be assigned to a distinct G2 column, so no edit path that deletes a node of the smaller graph can be represented. Classical GED as defined in Section 3 permits deletions from either graph, and when deleting a small-graph node is cheaper than substituting it, the feasible set here excludes the optimal edit path. This contradicts the paper's repeated claim that the hard alignment is consistent with classical GED and weakens the interpretability interpretation in Section 5.6. The model needs either a rectangular matching formulation with dummy columns on both sides, or the claims should be restricted to a substitution-only alignment.","section":"4.2, Eq. (6); 4.3, Eq. (9)"},{"comment":"The normalization denominator max(|V1|,|V2|)+max(|E1|,|E2|) is not an upper bound on GED under standard unit-cost edits. For example, take two 10-node graphs whose edge sets are disjoint and have 20 edges each: transforming one into the other requires at least 40 edge deletions and insertions, while the denominator equals 10 + 20 = 30. The normalized ground truth can therefore exceed 1, while the prediction in Eq. (14) is confined to [0,1] by the sigmoid, so the training target can be unreachable. The normalization should be changed to a true upper bound, or a proof of the bound must be supplied.","section":"4.4, Eq. (15)"},{"comment":"The abstract's headline claim of 'up to 16% reduction in the Mean Squared Error' is not supported anywhere in the paper: Table 2 reports MAE, Accuracy, rho, tau, and P@10, but no MSE values or MSE improvements are given. Either add an MSE column and report the reduction, or revise the abstract so the quantitative claim matches the metrics actually reported.","section":"Abstract; Table 2"},{"comment":"No error bars, standard deviations, or statistical significance tests are reported, yet some of the claimed improvements are small or in the opposite direction (e.g., Linux rho: GNA 0.964 vs GEDGNN 0.963; IMDB MAE: GNA 1.425 vs GEDGNN 1.398, where GEDGNN is better). Without repeated runs or paired tests, the claim that GNA outperforms the baselines across all metrics is not statistically established. Please add repeated-run statistics and, ideally, paired significance tests.","section":"5.3, Table 2"},{"comment":"The Gumbel-Sinkhorn iterations with temperature tau=0.1 produce a continuous doubly stochastic matrix, not a binary {0,1} permutation matrix. The paper does not describe any discretization, rounding, or straight-through estimator that would produce the hard one-to-one alignment claimed as a contribution and displayed in Figure 4. As written, the matching module outputs a soft alignment at inference, so both the 'hard alignment' claim and the interpretability guarantee are not established. The authors should specify how the binary matrix is extracted or adjust the claims to soft alignments.","section":"4.3, Eqs. (10)-(12); 5.6"}],"minor_comments":[{"comment":"Equation (9) writes LRL_theta(H1) while the text says LRL is applied to the padded H*1; to obtain a |V2| x |V2| matching matrix, the padded embedding must be used. Please correct the notation.","section":"4.3, Eq. (9)"},{"comment":"The sentence 'the denominator is the original GED value' is incorrect; the denominator is the normalization factor max(|V1|,|V2|)+max(|E1|,|E2|). Please correct the wording.","section":"4.4, Eq. (15)"},{"comment":"The introduction lists GOTSim among soft-alignment methods, while Section 2.2 credits GOTSim with deriving one-to-one node alignment from a similarity matrix and an addition/deletion cost matrix. The novelty claim of being 'first' to provide one-to-one node matching should be reconciled with this description of GOTSim.","section":"1 vs 2.2"},{"comment":"The ablation text says that removing Gumbel-Sinkhorn is intended to 'relax the bijection limitation' but then reports a performance decline; please clarify what 'relax' means here and report numeric ablation values rather than only figures.","section":"5.4"},{"comment":"There are typos including 'similarity similarity task' in Section 5.4 and 'Howvever' in Section 2.1; these should be corrected.","section":"5.3 and 2.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a reasonable empirical paper, but the load-bearing issues are the asymmetric padding, which breaks the claimed equivalence to classical GED edit paths, and the normalization target that can exceed 1. Both are fixable with a reformulation or a precise restriction of the claims. The novelty claim with respect to GOTSim should be checked carefully before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Take a look at this paper if you work on GED approximation. It has a clean idea and good numbers, but there is a real conceptual gap in the matching module that the authors do not acknowledge.\n\nWhat is actually new: GNA uses a Gumbel-Sinkhorn module to generate a hard, bijective node alignment without node-level labels, and feeds that alignment plus a cost matrix into the GED predictor. The ablation shows the bijection helps. The empirical results are solid on AIDS, Linux, and IMDB, often beating SimGNN, GOTSim, and GEDGNN on MAE and retrieval metrics. Code is public.\n\nThe soft spot the stress test caught is real. In Eq. 6, they pad the smaller graph's embedding matrix with dummy rows only, then form a |V2| x |V2| permutation matrix. That means every original node of G1 must be matched to a distinct node of G2; no original G1 node can be deleted. Classical GED permits deletions from either graph, and for pairs where |V1|<|V2| the optimal edit script often deletes a G1 node. GNA's feasible set excludes those scripts, so the output alignment is not in general the optimal edit path, and the predicted GED can be biased. The case studies only show deletions of larger-graph nodes, so the limitation is invisible in the reported validation. This does not kill the method as an approximator, but it undercuts the claim of interpretability \"more similar to classical intractable methods.\"\n\nThere is also a novelty overstatement. GOTSim already derives one-to-one node alignment from a learned similarity matrix, as the related work itself says. The paper should claim the specific mechanism (Gumbel-Sinkhorn, no alignment labels) rather than being first to provide one-to-one matching. And the abstract's 16% MSE reduction does not appear in Table 2, which reports MAE and ranking metrics. That needs either the MSE numbers or a corrected abstract. Minor: no significance tests or error bars on the main table.\n\nWho it is for: people building GED approximations with interpretable alignments. It deserves review, but a serious referee should push on the deletion issue and the novelty framing. I would send it out, not desk reject.","headline":"GNA gets hard one-to-one node alignment working without node-level labels and posts strong numbers, but the padding scheme quietly forbids deleting nodes from the smaller graph, and the novelty claim overstates GOTSim's prior one-to-one alignment.","tokens_in":13945,"tokens_out":2935,"would_cite":false,"duration_ms":33573,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that a graph neural network with a differentiable Gumbel-Sinkhorn layer can predict graph edit distance and output a valid one-to-one node alignment, trained only on graph-level similarity scores.","keywords":["Graph Similarity","Graph Representation","Model Interpretability","Graph Edit Distance","Node Alignment","Gumbel-Sinkhorn","Graph Neural Network","Graph Retrieval"],"falsifier":"Compute exact GED and the exact optimal alignment for a sample of small graphs ($\\le 10$ nodes) with A* search, then compare GNA's predicted permutation and predicted GED against those ground truths; if the model often returns a different one-to-one correspondence while still predicting an accurate similarity score, then the linear relaxation is capturing the right score for the wrong structural reason.","tokens_in":12853,"feed_emoji":"🔗","tokens_out":5435,"duration_ms":59794,"temperature":0.7,"pith_summary":"Graph edit distance (GED), the minimal cost of turning one graph into another, is NP-hard to compute exactly, and neural approximations usually hide the node-correspondence step that classical algorithms make visible. This paper proposes GNA, a model that predicts GED while also outputting a hard one-to-one alignment between nodes of the two graphs, without any node-level alignment labels. The authors relax the classical quadratic assignment problem to a linear one in a learned node-embedding space, then use a differentiable Gumbel-Sinkhorn module to produce a doubly stochastic permutation matrix. On three real-world graph datasets, they report that GNA reduces mean squared error by up to 16% and improves retrieval ranking metrics by up to 12% compared with existing neural baselines. The central message is that interpretability via bijective node alignment need not come at the cost of accuracy; in their experiments it helps prediction.","feed_headline":"One-to-one node matching improves graph similarity prediction","feed_subtitle":"The model maps every node to exactly one partner, needs no alignment labels, and beats existing baselines.","key_machinery":"The central mechanism is the relaxation of the quadratic assignment problem of GED to a linear assignment in node-embedding space, combined with Gumbel-Sinkhorn normalization to enforce a doubly stochastic, one-to-one permutation matrix in a differentiable way. The GIN encoder supplies node features that are assumed to encode subgraph and edge structure, so that the node-node cost matrix alone can stand in for the full adjacency-matching objective. The cost matrix and matching matrix are multiplied elementwise to produce the predicted edit distance, with the Sinkhorn iterations providing the hard, interpretable alignment that soft-alignment methods lack.","core_discovery":"GNA treats GED prediction as a prediction task with a differentiable bijective matching layer. Given two graphs, a three-layer GIN encoder produces node features that, the paper argues, capture both subgraph structure and edge information, which reduces the quadratic assignment underlying GED to a linear assignment over node embeddings. A costing module computes pairwise substitution costs, with padded nodes carrying graph-level embeddings to represent insertion and deletion. A matching module feeds transformed embeddings through Gumbel-Sinkhorn iterations to obtain a doubly stochastic, approximately binary permutation matrix that enforces one-to-one matching. The predicted GED is the elementwise product of the cost matrix and the matching matrix plus an NTN bias, trained with mean squared error against normalized GED. The paper claims this is the first method to predict graph similarity while producing one-to-one node matching without alignment ground truth, and reports superior accuracy on both similarity estimation and retrieval, with an ablation showing that both the bijection constraint and the add/delete costs matter.","pith_inferences":["Quantitative comparison of GNA's predicted alignments against exact optimal alignments on small graphs would directly test the linear relaxation; the paper's evaluation of alignment quality is mostly visual.","Because the model needs no alignment labels, it could transfer to settings such as knowledge graph or social network alignment where similarity scores exist but correspondence ground truth is scarce.","The Gumbel-Sinkhorn temperature, set to 0.1 in the experiments, controls the trade-off between differentiability and closeness to a true permutation; tuning it per task is a natural extension.","If the relaxation is faithful, the matching matrix could be reused as a differentiable proxy for the full edit path, potentially enabling end-to-end learning of edge-level edit operations as the paper's future-work direction suggests."],"forward_implications":["Neural GED predictors can be made interpretable without extra labels: the model's permutation matrix shows which nodes map to which, much like classical edit paths.","Enforcing bijective alignment improves accuracy on similarity regression and retrieval, not just transparency; the ablation attributes this to the Gumbel-Sinkhorn constraint.","Insertion and deletion costs can be read off the alignment: padded rows and columns identify nodes that must be added or deleted when graph sizes differ.","The same architecture applies to any domain-agnostic similarity task on undirected unweighted graphs where a GED or MCS score is the supervision signal."],"supporting_citations":[{"why":"Supplies the GIN encoder whose sum aggregation is relied on to encapsulate subgraph and edge structure, justifying the linear relaxation.","marker":"[28]"},{"why":"GEDGNN provides the three-layer GIN setting, the elementwise cost-matching GED prediction, and the main supervised node-matching baseline.","marker":"[5]"},{"why":"SimGNN contributes the bilateral-branch design and the NTN bias, and serves as the representative end-to-end baseline.","marker":"[17]"},{"why":"GOTSim is the unsupervised differentiable optimal-alignment baseline and the source of the stacked cost-matrix interaction layers.","marker":"[10]"},{"why":"Provides the padding strategy used to handle graphs of unequal size in the cost module.","marker":"[9]"},{"why":"Establishes the equivalence between GED and maximum common subgraph in the subgraph case, motivating the alignment view of similarity.","marker":"[1]"},{"why":"GPN is a state-of-the-art edit-path search baseline used in the retrieval comparisons.","marker":"[26]"}],"fun_headline_variants":["Bijective node matching boosts graph similarity accuracy","Graph similarity via differentiable one-to-one node matching","Hard node alignment improves graph retrieval without labels","Neural node alignment makes graph similarity interpretable","One-to-one matching reduces graph similarity error by 16%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole approach rests on the assumption that the GIN node embeddings alone capture enough subgraph and edge structure that the linear node-assignment problem is a faithful substitute for the full quadratic assignment problem of GED; the paper asserts this but gives no proof or quantitative check.","fun_headline_variants_meta":{"raw":{"variants":["Bijective node matching boosts graph similarity accuracy","Graph similarity via differentiable one-to-one node matching","Hard node alignment improves graph retrieval without labels","Neural node alignment makes graph similarity interpretable","One-to-one matching reduces graph similarity error by 16%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00025,"raw_usage":{"total_tokens":1592,"prompt_tokens":1022,"completion_tokens":570,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":498}},"tokens_in":638,"tokens_out":570,"duration_ms":6753,"temperature":1.0,"reasoning_tokens":498,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:26:11.697280+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute exact GED and the exact optimal alignment for a sample of small graphs ($\\le 10$ nodes) with A* search, then compare GNA's predicted permutation and predicted GED against those ground truths; if the model often returns a different one-to-one correspondence while still predicting an accurate similarity score, then the linear relaxation is capturing the right score for the wrong structural reason.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GEDGNN provides the three-layer GIN setting, the elementwise cost-matching GED prediction, and the main supervised node-matching baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"SimGNN contributes the bilateral-branch design and the NTN bias, and serves as the representative end-to-end baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GOTSim is the unsupervised differentiable optimal-alignment baseline and the source of the stacked cost-matrix interaction layers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the padding strategy used to handle graphs of unequal size in the cost module."},{"cited_title":"Bunke, On a relation between graph edit distance and maximum common subgraph, Pattern recognition letters 18 (8) (1997) 689–694","cited_arxiv_id":null,"evidence_quote":"Establishes the equivalence between GED and maximum common subgraph in the subgraph case, motivating the alignment view of similarity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"GPN is a state-of-the-art edit-path search baseline used in the retrieval comparisons."}],"review_version":1}