- 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
- What measurable advantage is specifically attributable to the primal–dual pricing mechanism over independently retrained no-price models and matched analytic solvers?
- 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?
- From Tables 11–12, why deploy four rounds when eight substantially improve recovery for about five additional milliseconds?