acceptodds
Under review as a conference paper at ICLR 2027

Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

Abstract

Maximum common edge subgraph (MCES) matching finds a partial vertex correspondence between two labeled graphs that preserves as many labeled edges as possible. Molecular similarity search requires matching many graph pairs, making the cost of repeated queries important. The strongest baseline attains accurate MCES solutions but trains a separate network for each pair. We introduce Equivariant Neural Primal–Dual Assignment (ENPDA), which learns a shared matching policy and applies it to new pairs without further training, answering queries roughly three orders of magnitude faster than the strongest baseline and recovering its training cost after only a few dozen queries. The policy recomputes exact objective marginals for candidate matches and learns corrections and step sizes that update their scores. Target prices respond to competition when several source vertices favor the same target. Four update rounds and a Hungarian projection produce a partial one-to-one matching. We prove per-pair guarantees that hold for any network parameters. In exact arithmetic, reordering either graph reorders the continuous assignment and price states accordingly, the projected matching is one-to-one, and repaired prices give a valid MCES upper bound. Subtracting the preserved-edge count bounds the optimality gap; combined with structural and exact incident-assignment caps, these certificates prove global optimality for 60 of 291 native test pairs. On three molecular benchmarks with no graphs shared across training, validation, and test, ENPDA improves over an analytic counterpart with the same update and projection budget by 7.4–8.6 accuracy points; after one second of additional refinement search, 2.5–3 points of the gain remain. Transferred without fine-tuning to edge-deletion tasks built from social and protein graphs, the policy gains 9.1–17.6 points over the analytic counterpart. When output matchings must keep aromatic rings intact, ENPDA recovers more reference bonds than the baselines on all three datasets.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural Combinatorial Optimization, Graph Matching, Maximum Common Edge Subgraph

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_imJ1OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes ENPDA, a reusable neural policy for maximum common edge subgraph matching. It combines exact objective marginals, learned recurrent updates, and target-capacity prices, followed by Hungarian projection to produce a partial one-to-one correspondence. A separate linear relaxation converts repaired prices into valid upper bounds. Training uses objective-generated pseudo-correspondences without optimal-solution labels. The authors evaluate a fixed-depth Core and a search-augmented Solver on graph-disjoint molecular benchmarks, controlled cross-domain tasks, aromatic-cycle-constrained matching, and retrieval. Results demonstrate improved short-budget matching quality, while the accompanying bounds certify optimality for a subset of test pairs.

Critical strengths

1.The paper addresses repeated MCES queries through a reusable matching policy, allowing instance-specific adaptation without per-pair retraining. 2.Graph-disjoint evaluation and matched-budget controls provide credible evidence that learning improves short-budget matching quality. 3.The method integrates exact objective marginals with learned updates and feasible projection, complemented by mathematically valid upper bounds independent of training quality.

Critical weaknesses

1.The headline speedup compares ENPDA-Core at 58–68% reference-edge recovery with NGA at 98–99%, conflating efficiency with solution quality. Using the higher-quality Solver substantially reduces the speed advantage and makes it dataset-dependent. Without comparisons at matched recovery levels, the reported speedup and amortization crossover do not establish a cost advantage at comparable solution quality.

2.The central primal–dual contribution is insufficiently substantiated. The full model has no statistically established matching-quality advantage over an independently retrained no-price model, while certification relies on a separate relaxation and neural prices do not tighten the strongest combined bound. Improving direct price repair alone does not justify the central role assigned to this mechanism or establish a substantive algorithmic advance.

3.The paper’s mathematical formulation contains clear gaps in its justification. Equation (7) supervises the model to imitate a teacher mapping that is not guaranteed to be optimal, while Equation (8) compares teacher-agreement losses rather than preserved-edge counts. Since the analytic model’s loss is constant with respect to the learned parameters, this term merely activates an additional teacher-imitation gradient when the threshold is exceeded. This disconnect becomes more consequential in Equation (9). Even when the soft assignments satisfy column-capacity constraints, both teacher NLL and the soft edge reward can improve while Hungarian decoding returns a worse MCES solution. Theorems 1–2 establish equivariance and feasibility but leave this central optimization gap unresolved.

4.The experiments do not adequately isolate the claimed contribution. Prices provide no statistically established matching-quality benefit over retrained no-price models, and the Solver’s final-quality gains over its analytic counterpart are also unestablished. Classical comparisons lack a verified common end-to-end deadline, while teacher quality and individual loss terms remain insufficiently examined.

Questions for authors
  1. What measurable advantage is specifically attributable to the primal–dual pricing mechanism over independently retrained no-price models and matched analytic solvers?
  2. How do the teacher-imitation losses in Equations (7)–(8) and the soft reward in Equation (9) translate into better discrete MCES solutions after Hungarian decoding?
  3. From Tables 11–12, why deploy four rounds when eight substantially improve recovery for about five additional milliseconds?
Reviewer_7mJKOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes ENPDA, a reusable neural matching policy for maximum common edge subgraph problems. The method combines exact association-graph objective marginals with learned corrections, adaptive step sizes, and target prices, followed by Hungarian projection. Training uses objective-generated teacher mappings, while a separate relaxation provides valid optimality bounds. Experiments demonstrate improved initial solutions and short-budget refinement over matched analytic controls, alongside molecular matching, transfer, and retrieval evaluations.

Critical strengths
  1. The paper addresses a meaningful limitation of per-instance neural optimization. The learned policy consistently improves matching quality under matched update and projection budgets, and gains remain after one second of refinement.

  2. The evaluation is careful about graph identity overlap, independently retrained controls, clustered confidence intervals, numerical repeatability, and complete training costs.

  3. The feasibility and certificate guarantees are clearly formulated. The authors also distinguish these guarantees from convergence claims and acknowledge the limitations of the empirical results.

Critical weaknesses
  1. The methodological contribution appears incremental. The approach combines association-graph modeling, learned iterative updates, Hungarian decoding, and a discrete search portfolio. Although this integration is useful, the evidence does not clearly establish the distinctive contribution of the proposed primal–dual mechanism. The independently retrained no-price model shows no statistically established accuracy disadvantage, and learned prices do not improve the strongest combined upper bound. The theoretical results establish structural properties and certificate validity, but provide limited insight into why the proposed dynamics improve MCES optimization.

  2. The headline speedup and amortization claims compare substantially different solution qualities. Core recovers approximately 58–68% of reference edges, whereas the three-fit NGA baseline reaches approximately 98–99%. These measurements do not establish a comparable-quality speedup.

  3. The near-optimal Solver results provide limited evidence of an additional accuracy benefit from learning. Improvements over the matched analytic Solver are only 0.09–0.13 percentage points, with confidence intervals containing zero. The runtime reductions on AIDS and MCF-7 are valuable, but the strongest accuracy contribution remains concentrated in shorter-budget settings.

  4. The theoretical results appear sound under the stated assumptions. However, the guarantees primarily concern structural equivariance, projection feasibility, and valid post hoc bounds. They do not establish convergence, monotonic objective improvement, or an approximation guarantee for the learned dynamics. In particular, the repaired-price bound is valid for any nonnegative price vector, so its validity does not demonstrate the effectiveness of the proposed neural primal–dual updates.

Questions for authors
  1. What is the complete runtime trade-off between repaired-price certificates and the tighter exact incident-assignment bound, including weight construction and scale selection?

  2. Which existing results best support an efficiency advantage at comparable solution quality, particularly against a single NGA fit and RASCAL?

  3. How does the frozen mirror-assignment reference used for teacher generation compare with ENPDA-Core in accuracy and runtime under the same decoding and refinement budget?

Reviewer_ppNzOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies the challenge of computing maximum common edge subgraph (MCES) between given pairs of graphs. The challenge lies when applications require multiple solves of this optimization problem between different graph pairs, as occurs in molecule search. Prior work has studied computing the association common graph (ACG) between any given graph pair, and then performing neural graduated assignment (NGA) to learn a node assignment to maximise edge overlap. This is slow for setups where there need to be multiple such solves, which motivates an amortized optimization framework which exploits a learned shared structure from training to better inform the MCES graduated assignment update during inference.

This paper's proposed method ENPDA proposes multiple rounds of an auction style update , with a Hungarian solver at the end to generate the injective node mapping. The ENPDA-Core has a learning component to adjust the auction scores and step sizes, while the Analytic-Core is exactly the same with fixed handcrafted updates rather than learned adjustment. The authors further add a search wrapper, which is applied on top of these *-Core proposals to get the corresponding ENPDA-Solver and Analytic-Solver. These *-Solver variants perform a combination of matching reconstruction , local-neighborhood search, and simulated-annealing to improve the solution over several minutes per graph pair.

All of these methods are compared on well known molecular graph datasets, against NGA and classical solvers such as RASCAL and McSplit.

Critical strengths

The experiments as presented seem to be designed rigorously. While I again have serious complaints about the writing and presentation, I appreciated the below

  • Particular care is taken to ensure training-test-val splits contain unique graphs
  • To get better confidence intervals which account for correlation of graph pairs which share a molecule, they cluster graph pairs if they share a molecule and then resample over the clusters.
  • The analytic control counterpart cleanly isolates the contribution to the learned part.
  • The ablation on prices tries both zeroing out the prices in the current trained model and training a fresh “no-price” model
  • They check for deterministic reproducibility under appropriate pytorch flags
Critical weaknesses

Experimental claims

I tried to verify the central claims of the paper and it seems to me there is a serious gap between what is presented as claims in the abstract/intro and what the experimental numbers actually tell us.

The proposed auction algorithm setup (ENPDA-Core/Analytic-Core) while being significantly faster than NGA baseline, performs significantly worse. Table 1a clearly shows the *-Core methods trail significantly behind (~60% v/s ~98%) other methods. It is only when *-Core methods are augmented with the search wrapper, aka the corresponding ENPDA-Solver/Analytic-Solver, that the performances are comparable to NGA/RASCAL baselines.

Even then against NGA, ENPDA-Solver is only slightly more accurate, and the paper itself says ENPDA-Solver is "faster than NGA on MOLHIV and MCF-7 and slower on AIDS". The numbers are confirmed from Table 13 which reports average accuracy and mean runtimes for NGA and *-Solver variants. Similarly for RASCAL, Table 23 clearly shows that ENPDA is slightly less accurate and about five times slower overall.

As such claims in the abstract like “answering queries roughly three orders of magnitude faster than the strongest baseline” and in the introduction like “ENPDA-Core averages 0.19 seconds per query versus 164–170 seconds for three NGA fits” are completely misleading since it does not take the actual performance into account.

Of course, this also means that the search protocol (which is comparable in runtime to the NGA style baseline) is doing most of the heavy lifting.

Another case in point, the paper itself states in lines 408-409 “Under the same refinement budgets, the four-stream analytic Solver trails ENPDA-Solver by 0.09– 0.13 accuracy points, with all paired intervals crossing zero (Table 13).” Also since the Analytic-Solver and ENPDA-solver perform very similarly, in the setting that actually matters (with the search components which is comparable to NGA/RASCAL) I do not see any benefit of the learned component once search is added, which renders a large part of the discussions in the paper moot.

To summarize my understanding, the learned ENPDA-Core gives a better initial starting guess compared to Analytic-Core, but it is significantly worse than NGA/RASCAL. With the search module, the *-Solver variants are extremely close to NGA in accuracy, take time in minutes per graph pair similar to NGA, and the learned component shows no benefit (Analytic-Solver is comparable to ENPDA-Solver).

Writing /Presentation

There are significant writing issues which which makes it near impossible to evaluate this work based on the scientific merit. The abstract starts off reasonably, but after the first three sentences becomes completely incomprehensible to me as a human reader. For example nothing in the abstract hints we are looking at an auction setup, but jumps straight into “target prices”. Note other undefined terms “exact objective marginals”, “repaired prices”, “structural and exact incident-assignment caps”, “analytic counterpart” and “native test pairs”. The sentences are disconnected, full of qualification phrases “In exact arithmetic”, “with no graphs shared across training, validation, and test”, and nothing clearly states the central idea.

Similar problems continue in the rest of the main text. The handcrafted update rules are presented without intuition and the several constants never justified. It is extremely difficult to make sense of the experimental results with disconnected numbers and qualifications such as “The largest bin uses median 0.89 GiB incremental GPU memory. These are scaling and feasible-bound results, not exact accuracies”. Section 5 states negative findings, but the actual numbers are in the appendix (Table 13,18,23), and it contradicts the positive framing of abstract/introduction. Also the same quantities are reported with different values across tables - for example ENPDA-Core numbers change across Tables 8, 10, 13,17 for each dataset.

Questions for authors

Currenly I do not have any quesitons for the authors whose answers could materially affect my assessment. My feedback is detailed above.

It is possible that there is an interesting technique and result at the heart of it all, but the paper needs a very drastic rewrite focusing on clear communication of the methodology and an accurate framing of what the experimental results indicate regarding the utility of the proposed methods.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.