Neural Graduated Assignment for Maximum Common Edge Subgraphs
Authors: Chaolong Ying
Yingqi Ruan
Xuemin Chen
Yaomin Wang
Tianshu Yu
Venue: ICLR 2026 Poster (2026)
Keywords: maximum common edge subgraphs
quadratic assignment programming
graph similarity
graduated assignment
Primary area: learning on graphs and other geometries & topologies
TL;DR: This paper proposes a neural graduated assignment approach to address the problem of finding the maximum common edge subgraph.

Abstract: The Maximum Common Edge Subgraph (MCES) problem is a crucial challenge with significant implications in domains such as biology and chemistry. Traditional approaches, which include transformations into max-clique and search-based algorithms, suffer from scalability issues when dealing with larger instances. This paper introduces ``Neural Graduated Assignment'' (NGA), a simple, scalable, unsupervised-training-based method that addresses these limitations. Central to NGA is stacking of differentiable assignment optimization with neural components, enabling high-dimensional parameterization of the matching process through a learnable temperature mechanism. We further theoretically analyze the learning dynamics of NGA, showing its design leads to fast convergence, better exploration-exploitation tradeoff, and ability to escape local optima. Extensive experiments across MCES computation, graph similarity estimation, and graph retrieval tasks reveal that NGA not only significantly improves computation time and scalability on large instances but also enhances performance compared to existing methodologies. The introduction of NGA marks a significant advancement in the computation of MCES and offers insights into other assignment problems.

Published as a conference paper at ICLR 2026
NEURAL GRADUATED ASSIGNMENT FOR MAXIMUM COMMON EDGE SUBGRAPHS
Chaolong Ying', Yingqi Ruan', Xuemin Chen', Yaomin Wang', Tianshu Yut* i School of Data Science, The Chinese University of Hong Kong, Shenzhen $ School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen {chaolongying, yingqi ruan, xueminchen, yaominwang link. cuhk. edu. cn, yutianshu@ cuhk. edu. on
ABSTRACT
The Maximum Common Edge Subgraph (MCES) problem is a crucial challenge with significant implications in domains such as biology and chemistry. Tradi- tional approaches, which include transformations into max-clique and search- based algorithms, suffer from scalability issues when dealing with larger instances. This paper introduces "Neural Graduated Assignment" (NGA), simple, scalable, method that addresses these limitations. Central NGA is stacking of differentiable assignment optimization with neural components, enabling high-din nigh-dimensional parameterization of the matching process through a learnable temperature mechanism. We further theoretically analyze the learning dynamics of NGA, showing its design leads to fast convergence, better exploration- exploitation tradeoff, and ability to escape local optima. Extensive experiments across MCES computation, graph similarity estimation, and graph retrieval tasks reveal that NGA not only significantly improves computation time and scalability on large instances but also enhances performance compared to existing methodolo- gies. The introduction of NGA marks a significant advancement the computation of MCES and offers insights into other assignment problems.
INTRODUCTION
Background. The Maximum Common Edge Subgraph (MCES) problem is a cornerstone task in combinatorial optimization (Ndiaye & Solnon 2011), particularly significant within the realms of biology and chemistry (Ehrlich & Rarey] (011)) As a variant of the broader Maximal Common Subgraph (MCS) problem (Bunke & Shearer 1998), MCES stands alongside the Maximal Common Induced Subgraph (MCIS) in its complexity and utility. Efficiently solving the MCES problem at scale is of both theoretical and practical significance in this context. For instance, in drug discovery, identifying MCES between molecules can reveal shared pharmacological properties. In cybersecurity, comparing network traffic graphs via MCES enables the detection of recurring attack patterns (Ehrlich) & Rarey| 201 Established approaches for solving MCES have been successfully integrated into widely-used cheminformaties libraries such RDKit (Bento al., 2020) and Molassembler (Sobez & Reiher 2020). which have become indispensable in both industrial and academic research.
Problem & Existing Challenges. MCES involves identifying subgraph that contains the maximum number of edges common to both input graphs. An example is in Figure [I] It is inherently NP. complete (Garey Johnson 1979), posing signifi- cant computational challenges in terms of scalabil- ity and efficiency. Historically, it has been tackled through transformations into the maximum clique problem (Bomze et al.] 1999) or search-based al- gorithms (Raymond et al.) 20022 McCreesh al. 2017; 2016). However, these traditional methods
For two labeled graphs, e.g. molecu- lar graphs, the MCES is highlighted in circle and the node correspondences are encoded in arrowed lines.
Figure I:
"Corresponding author

---

Published as a conference paper at ICLR 2026
often struggle with large-scale graphs: transformations can introduce additional computational overhead, while search-based branch-and-Be and-bundd approaches suffer from exponential scaling, ren- dering them impractical for complex instances. This challenging landscape underscores the need for novel techniques that can deliver efficient and reliable solutions to the MCES problem without compromising accuracy.
Our approach. To address the challenges of MCES, we propose Neural Graduated Assignment (NGA) - novel neuralized optimization framework designed to approximate MCES solutions in polynomial time. Inspired by annealing mechanism in statistical physics (Gold & Rangarajan 1996), our approach seeks find an assignment matrix that identifies node correspondences between the two graphs, such that the number of preserved edges - ie.. edges that exist between matched node pairs in both graphs is maximized. NGA tackles the aforementioned intrinsic challenges in the MCES problem by: (1) constructing an Association Common Graph (ACG) and formulating MCES as Quadratic Assignment Problem (QAP), which ensures the extraction of exact common subgraphs between input graphs; (2) iteratively updating the learned assignments through a high- high-dimensiooal and learnable temperature parameterization; and (3) optimizing this formulation via unsupervised training" thereby eliminating the need for training data. During optimization, the learned assignments correspond to a current identified common edge subgraph that serves as a lower bound, which is progressively and monotontically improved toward the optimal MCES, An illustrative example of such improved lower bound is provided in Figure Of the Appendix.
Theory. Despite the simplicity, we theoretically justify the superiority of NGA by showing: (1) how NGA updates around local optima; (2) the implicit exploration-exploiatiio mechanism impacts the optimization trajectory; and (3) the accelerating effect on the convergence. By embedding these operations within a neural context, NGA achieves strong scalability, adaptability, and seamless integration with machine learning frameworks. This theoretical underpinning lays the groundwork for new class of algorithms capable of rethinking assignment problems from neural perspective.
Results & Contribution. To validate the efficacy of our approach, we conduct a series of challenging experiments across various settings, including large-scale MCES computation, graph similarity estimation, and structure- ciency and performance of our method compared to existing ones. These findings not only highlight the potential of our approach in advancing MCES computation but also suggest its applicability to diverse domains. We summarize our contributions follows:
graph retrieval. The results consistently demonstrate the superior effi-
A novel and strong approach. We for the first time formulate the MCES problem via the construction of an ACG, and based on this formulation, we propose NGA the first neural- style algorithm to approximate the MCES solution efficiently in polynomial time without relying on exhaustive exploration of the solution space, delivering superior performance.
Training-data- NGA operates in fully unsupervised manner, climinating the need for
supervision signals. In cases where enumeration or search of the exact solution becomes computationally infeasible, our approach provides efficient approximations.
Theoretical analysis. We provide the first theoretical analysis on the behavior of dynamic and parameterized temperature in NGA, shedding light on its behavior at local optima, convergence properties and adaptive dynamics.
Interpretability, scalability, and versatility. NGA is inherently interpretable, producing explicit MCES structures. It also exhibits strong scalability, making it suitable for large- scale graph data. Furthermore, NGA can be extended tasks such as graph similarity computation and graph retrieval, highlighting its broad applicability.
2 RELATED WORK
Efforts Solving MCS. MCS has been extensively studied in recent research, either by reduction to the maximum clique problem (McCreesh et al.) (017)) or by directly identifying matching pairs within the original problem formulation. McSplit (McCreesh et al., 2017), which belongs to the latter category, introduces an efficient maanchanddbounte algorithm leveraging node labeling and
Unsupervised training means that no information about the MCES itself-such as what the MCES is or the MCES size-is required during training, including in the loss function (Schuetz al. 2022
2

---

Published as a conference paper at ICLR 2026
partitioning techniques to reduce memory and computational requirements during the search. Building on this, GLSearch (Bai et al. 2021) employs a GNN-based Deep Q-Network to select matched node pairs instead of relying heuristies, significantly improving search efficiency. For the MCES problem, RASCAL (Raymond et al. 2002) proposes a branching-basee its maximum clique formulation, incorporating several heuristics to accelerate the search process. Additionally, MCES has been formulated as an integer programming problem and solved using a branch-and-cut enumeration algorithm (Bahiense et al., 2012). However, these methods suffer from high computational costs, making them less scalable for solving challenging MCS problems.
search method to solve
Efforts on Graph Similarity Computation and Graph Retrieval. Recent efforts have explored the application of MCS in various tasks, particularly in graph similarity computation and graph retrieval. For assessing graph similarity, one established approach is the use of Graph Edit Distance (GED) (Zhao et al.) 2013 Zheng et al., 2013). Alternatively, MCS provides a robust method for evaluating the structural similarity of graphs, especially in molecular applications. For example, SimGNN (Bai et al. 2019) integrates nove-level and graph-level embeddings to compute a similarity score, while GMN et al. 2019) introduces a novel cross grashh attention mechanism for learning graph similarity. Similarly, INFMCS (Lan et al. (024) presents an interpretable framework that implicitly infers MCS to learn graph similarity. In the domain of graph retrieval, where the goal is to locate the most relevant similar graphs database based on query graph, various model architectures have been proposed. For instance, ISONET (Roy et al., 2022b) employs subgraph matching within an interpretable framework to calculate similarity scores. Furthermore, XMCS (Roy et al. (022a) proposes late and early interaction networks to infer MCS as similarity metric, offering competitive performance terms of both accuracy and computational speed.
PRELIMINARY
In this section, we briefly review the background of this topic, as well as elaborate on the notations. Additional background can be found in Appendix A
Let G E, H. E) be an undirected and labeled graph with n nodes, where V the node set, E is the edge set, A E {0, 1 jaxn is the adjacency matrix, H E R=* is the node feature matrix, and E E mux is the edge feature matrix. In a labeled graph, nodes and edges features refer to their labels. For example, in molecular graphs, atom types and bond types are considered as labels.
Maximum Common Edge Subgraph. Two graphs, G1 and Gg. are isomorphic there exists a bijective mapping between their nodes such that any nodes in G1 connected by an edge if and only if their corresponding images in G2 are also connected. A common subgraph of two graphs G1 and G2 is graph G12 that is isomorphic to subgraph of G1 and a subgraph of G2. Although there are possibly many common subgraphs between two graphs, our focus will be on the MCES (Bahiense) al. 2012), which is a subgraph with the maximal number of edges common to both G₁ and G2-
Quadratic Assignment Problem. Given two graphs G₁ and G2, the goal is to find a hard assign- ment matrix E 10, column constraints. The optimization problem is formalized as:
x 1> that maximizes a compatibility function while adhering to row and
maxp s.t.
vec(P) Avec(P)
Pe P 10, X22 m122 Pl,, Ln, P 112
where A is the affinity matrix derived from the structural information of G1 and G2 and 1, is column vector of length n whose elements are all equal to 1. A common practice to relax P into soft assignment matrix S E [0, 1 allowing continuous values, and optimizes the following relaxed objective:
max vec(S) T A Avec(S)
3

---

Published as a conference paper at ICLR 2026
A ssociation C Common Graph Construction (Sec. 4.2.1)
mi components
A
GNN: S
ACG:A
Paramotorize: w w
Parametenize
Sinkhom
Sinkhom
Losst
8
emnheddings
Sinkhorn( H
vee( S. 2
embeshiings
H
S
Update A ssignment with NGA (Sec. 4.2.2)
Initial ssignment (Sec. 4.2.1)
Figure 2: An overview of Neural Graduated Assignment.
4
METHODOLOGY
4.1 OVERVIEW
The MCES problem is intricately connected to graph matching, both involve finding correspon- dences between the structures of two graphs. Specifically, the MCES problem aims to find the largest subgraph that is isomorphic to subgraphs in both input graphs. This can be viewed as special case of partial graph matching, where the matched pairs of nodes and edges constitute common subgraphs. Typically, graph matching seeks to find an assignment matrix P as follows (Grohe et al., 2018 Liu
et al. 2023
Ying et al. 2025):
argminp |A PAP 1
(3)
However, a prominent challenge for the MCES of labeled graphs is ensuring that the corresponding nodes and edges in the common subgraphs have compatible labels, which are considered in typical graph matching problems. One possible solution would be to add penalty term for incompatible labels. However, directly optimizing Eq. 3 with penalty term is intractable, it cannot guarantee that the obtained subgraph is a valid common subgraph. To this end, we present a novel approach centered around the construction of an ACG, which enables the extraction exact common subgraphs. Building this framework, we propose a new formulation for the MCES problem. This formulation leverages the ACG and facilitates optimization by learning an assignment between the nodes of the two input graphs, resulting in an efficient and scalable solution for MCES computation. An overview of our method is shown in Fig. 2 In the following, Section 4.2.1 presents the construction of the ACG and formulates the MCES problem
QAP, Section 4.2.2 describes the proposed NGA method, and Section 4.2.3 introduces the Gumbel sampling strategy used during inference.
4.2
UNSUPERVISED TRAINING OF MCES
4.2.1
ACG FOR LEARNING CORRESPONDENCES
To efficiently explore solutions MCES, we proposed to construct an ACG, where compatible nodes and edges can be identified. We define the ACG of G and G2 G OG.. It is constructed on the node set VGG OG2) = V(G2) x V(G2) where the respective node labels are compatible and two nodes (u, v)) and (uj- vy) being adjacent whenever the three conditions are met together
(u, uz) E(G1), (wt, u,) E(G2), w(u, uy) w(,, vz). where wus, uz) = w(v;, Ui)) indicates that the labels of nodes and edges are compatible. The design of ACG leads to a behavbe property as follow.
(4)
Proposition 1. Denote the node set of G P1022 Vo (u, E V(Gi), V(G2)). Consider a set of subgraphs of G1QGa where each node of G1 and Gz is selected at most once, i.e. any two nodes (u, v4)) and (uz, U2) in this satisfy u, # uj and F Uz. Any subgraph in this set is valid common subgraph of G2 and G2, and finding the MCES of two graphs is reduced to finding the largest subgraph in this set.
4

---

Published as a conference paper at ICLR 2026
Since only the common edges are included in the ACG, Proposition shows that we always extract common subgraphs from the constructed ACG. Besides, the use ACG allows any assignment to be mapped to common subgraph, thereby enhancing interpretability. Formal proof of Proposition [] can be found in Appendix B] Considering the adjacency matrix Ao of GiOG2 as the affinity matrix, can then give the QAP formulation of objective J for MCES
J(S) = vec(S)* vec((S))
We model the initial node-to tode-to-node correspondence in close analogy related approahches (Bai et al. 2019 Fey et al., 2019) by computing the node similarities of input graphs G1 and G2. Specifically, given latent node embeddings HI
0o (A1, X1, E and H₂ a (A2, X2, E2) computed by
shared neural network V 88. the initial soft correspondences are obtained as
( = H, E R
S = Sinkhorn(So) E [o, 10
(6)
where Sinkhorn(.) is normalization operator to obtain double-stochastie assignment matri- ces (Sinkhorn Knopp 1967). In our implementation, Va, is a GNN to obtain permutation equivariant node representations (Hamilton et al. 2017).
4.2.2 NEURAL GRADUATED ASSIGNMENT
Since many nodes have the same labels in molecular graphs, the initial assignment is a soft probability distribution where many entries have moderate probabilities, which leaves significant ambiguity in the assignments. Traditional assignment based optimization methods often rely on a predefined temperature parameter /3 iteratively refine solutions by controlling the scale of probabilities or soft assignments. However, using a fixed or manually scheduled temperature introduces two key limitations: (1) Manual Tuning Overhead: Selecting an optimal schedule or fixed value for 3 often requires exhaustive tuning, depending on the specific task or dataset. (2) Limited Adaptability: A fixed or scheduled is static and cannot dynamically adapt to the complexity of individual problems or local structures within data.
To address these limitations, we propose NGA, an end-to-end trainable framework in which we use learnable parameters as the temperature schedule. The NGA architecture is summarized in Alg. [ and the overall training and inference framework are summarized in Alg. [ NGA maintains the iterative refinement process. The key innovation lies in replacing the sealar temperature parameter
with a parameterized form: 31 = w(( w at the (th iteration layer, where ((!), w!!) dx learnable weights. By allowing the model to optimize temperature directly as part of the learning process, our method adapts dynamically to the structure of the problem and the stage of optimization,
eliminating the dependence on manual tuning while achieving superior performance.
Algorithm NGA Architecture
Algorithm 2 Model Training and Inference
1: Input: The adjacency matrix of ACG Ag. inital assignment matrix ((O), number of iter- ations m, learnable parameters w(O, w!!
1: Input: Molecular graphs G1 and G2
2: Output: MCES G2 and G2
3: Build ACG G.
4: // Training Stage
for / (1....,m) m)
2: Output: refined assignment matrix S
for epoch 2, do
6: Init assignment S(0) with Eg. 6
3: for 1 to do
4: vec(S(") + Ag Agvec(S
7: Refine S to with Alg. |
5: S(I) ( w())
8: Backpropagation w.r.t. loss in Eq.
9: end for
6: S()) Sinkhorn(S
10: // Inference Stage
7: end for
11: Decode P with P = Hungarian(S))
8: Output S = (m)
12: Get MCES w.r.t. P via Eq.
4.2.3 GUMBEL SAMPLING FOR OPTIMIZATION
Since S is relaxed from P. the Hungarian algorithm (Burkard al. 2012 is commonly employed as deterministic post- post-processing step to bridge the gap between them, i.e. P = Hungarian(S), The adjacency matrix of predicted common subgraph Apred is obtained by:
Apred (vec(P)vec(P))
Ao,
(7)
5

---

Published as a conference paper at ICLR 2026
where @ is the Hadamard product of matrices.
From probabilistic perspective, S represents a latent distribution of assignment matrices. Assignment with the highest probability is selected by Hungarian algorithm. However, there may be better solutions within the distribution, especially when the quality solutions can be easily assessed. Therefore, switch Gumbel-Sinkhomn (Mena et al. 2018) by substituting Eq. (6) with
S Sinkhorn ($ + g):
(8)
where g sampled from a standard Gumbel distribution with the cumulative distribution function. The Gumbel term models the distribution of extreme values derived from another distribution. With Eq. (8), we can sample repeatedly batch of assignment matrices from the original distribution in differentiable way. This property actively benefits solution space exploration and makes it easier to find the optimal solution. These sampled assignment matrices are discretized by Hungarian algorithm and evaluated by Eq. (7) The best-performing solution among them is chosen as the final solution. The balance between exploration and speed can adjusted by tuning the number of Gumbel samples.
5 THEORETICAL ANALYSIS
In this section, we investigate the behavior of NGA from theoretical aspects, particularly answering subsequent essential questions: 1) How NGA escapes from local optima in Theorem [ 2) Why NGA demonstrates better convergence and performance over standard GA in Proposition Upon these thcoretical findings, argue that NGA offers adaptive exploration-explottatoon mechanism, leading to well-behaved learning dynamics.
Theorem 1. Given a local optimum ((), the change AJ = J(S!++1) J(S()) satisfies
AJ =
A
15)+ Var(h) + 0(
(9)
2
where haj = [Aovoc(S())ss, Var(h) is the variance, ((S()) vec(S(!)) Ao vec(S()) is the objective, >; and pú are the Lagrange multipliers.
Proposition 2. Under typical gradient descent conditions where the gradient pushes 31 in a consistent direction for multiple iterations, the product parameterization 31 W Wa can adaptively adjust the learning rate and induces an accelerating effect on the magnitude of updates to ft.
The proof of Theorem can be found in Appendix [.] This theorem quantifies the objective change around a local optima w.r.t. 3r In general, AJ has an additional constant term related to Lagrange multipliers, but still decreases through the variance term when B1 < 0. This demonstrates that NGA's update is capable of escaping local optimum under mild conditions.
Another contributing factor to the effectiveness of NGA lies in the gradient update aspect. As shown in Proposition 2 the product parameterization 3 ( w!!) can adaptively adjust the learning rate and leads to faster convergence than scalar parameterization. This makes the training process more stable and efficient. This adaptive behavior particularly beneficial when addressing complex, high-dimensional data. Detailed theoretical and empirical validations can be found in Appendix D.2
We then analyze how switching 3 positive and negative interchangeably can help the optimization. To this end, we make the following definition:
Definition 1. In Alg. 1 let 31 (1) w!!) then define two phases according to the value of 3r: 1. Exploration phase: E = [13 < 0.: Exploitation phase: S = [1 > 0}.
Appendix D.I provides a proof explaining why the sign of 31 represents these two processes, respectively. Imposing a negative and learnable 3 in NGA grants the model the ability to balance exploration and exploitation. By allowing the two phases, NGA effectively incorporates exploration and exploitation into the optimization, avoiding premature convergence and enabling the identification of better solutions.

---

Published as a conference paper at ICLR 2026
6 EXPERIMENTS
We evaluate the performance of our proposed method on MCES problems by comparing it with several baselines across three widely used molecular datasets, covering diverse graph structures. Our results show that NGA significantly outperforms search-based methods in computational efficiency, achieving comparable or better accuracy while reducing runtime by several orders of magnitude. This allows our method to scale to larger graphs that are infeasible for traditional search, highlighting its effectiveness and scalability in real-world applications.
Beyond solving the MCES problem, we further examine its practical impact on two related tasks: graph similarity computation and graph retrieval. By effectively solving MCES, our method achieves strong performance in these tasks, offering a reliable basis for similarity measurement and retrieval. This confirms that NGA not only addresses MCES effectively but also benefits related applications.
6.1 EXPERIMENTAL SETUP
Baselines. The MCES problem is NP-complete (Garey & Johnson 1979 Raymond et al. 2002).
meaning no known polynomial-tim solutions exist. While search-based algorithmss can find exact solutions with enough computational resources, they quickly become infeasible for large graphs. Non-search- based methods aim to approximate solutions efficiently without exhaustive search. We compare our method with search-based RASCAL (Raymond et al.) (002) and Mcsplit (McCreesh et al. 2017). and use Graduated Assignment (GA) (Rangarajan et al. 1996b] [Gold & Rangarajan 1996) and Gurobi solver as baselines since we can formulate MCES a QAP. Similar to these solvers,
our NGA tries to solve each MCES instance case by case. We also adapt supervised learning method
NGM (Wang et al., 2021) and unsupervised learning method GANN-GA (Wang et al., 2023) for comparison. For the graph similarity and retrieval tasks, we compare with state-of-the-ar baselines:
Metr (Lou et al., 2020), SimGNN (Bai al. 2019), GMN (Li et al. 2019), XMCS (Roy et al..
2022a), and INFMCS (Lan et al. 2024 Appendix details baseline choices and configurations.
For fair comparisons, supervised learning approaches are trained for a total of 200 epochs. This duration is selected to provide sufficient learning time for the models to converge, ensuring robust evaluation of their performance. For unsupervised learning and search methods, we follow previous works (Bai et al. (021) to set practical time budget of 60 seconds for each instance. This constraint reflects real-world scenarios where computation time is limited and must be optimized for efficiency. While search methods are capable of identifying exact solutions given unlimited computational resources, this assumption is impractical for handling large graph pairs in real-world applications.
several graph datasets commonly employed in graph-related tasks: AIDS and MCF-7 from TU Dataset (Morris et al.) 2020), and MOLHIV from OGB (Hu et al. 2020), covering various molecular structures. Ground truth is obtained using exact solvers (Raymond et al. 2002). with solution time and dataset statistics in Appendix C.I While exact MCES solutions are feasible for small graphs, they become intractable for large ones. Unlike prior works that limit graphs to 15 nodes (Bai et al., 2019 Lan et al. 2024). we focus on harder instances by selecting molecules with over 30 atoms, and randomly sample 1000 graph pairs per dataset for MCES and similarity evaluation. For graph retrieval, we use 100 query and 100 target graphs, yielding 10,000 query-targer pairs. This setup enables a realistic assessment of scalability and efficiency.
Datasets. To evaluate model across diverse domains,
Evaluation. For MCES and graph similarity tasks, we split the dataset into 80% training, 10% validation, and 10% testing. For graph retrieval, this split is applied to the query graphs. Supervised methods are trained on the training set, with hyperparameters tuned on the validation set and evaluated on the test set. Other methods are directly evaluated on the test set. Since all methods yield common subgraphs, MCES accuracy is measured by the percentage of the common graph size, defined as:
E (CS(G1, G2))
Acc
(10)
E (MCES(G1, G2))
As for the graph similarity computation, the Johnson similarity [Jhnsson 1985) is calculated as
(IV (Gre) + I8 (G12)))
sim +I (V)) [
(11)
7

---

Published as a conference paper at ICLR 2026
where G12 is the MCES between graphs G1 and G2, and we use Root Mean Square Error (RMSE) as the evaluation metric. For graph retrieval, we evaluated all models using three metrics: Mean Reciprocal Rank (MRR), Precision 10 (P@ 10), and Mean Average Precision (MAP). These metries collectively provide insights into the retrieval capability from various perspectives.
6.2 IMPLEMENTATION DETAILS
Hyperparameters. In our method, we use two neural networks: the first oo an 8-layer Graph Convolutional Network (GCN) (Kipf & Welling, 2016), which utilizes 32 feature channels. In our NGA model, the number of iterations mn is set to and the hidden dimension of learnable weights is set to 32. For the Sinkhorn layer, we set the number of iterations to 20 to allow for sufficient optimization. The GumbelSinkhorn layer is configured with 10 times sampling. The model is trained using the Adam (Kingma 2014) optimizer with learning rate of 0.001. These hyperparameter settings were chosen to balance model performance and computational efficiency, allowing for effective training and convergence across the evaluated tasks.
Training Details of NGA. The training and inference processes are summarized in Alg. 2 Similar to conventional MCES solvers (McCreesh et al. 2017 Raymond et al. 2002), our method addresses one pair of molecular graphs from the test set at a time. During the traming stage, our method learns to optimize the objective in Eq. ( In the inference stage, the assignment matrix S learned at the training stage is transformed into an assignment matrix P. which is then used to compute the MCES result with Eq. 7 Specifically, when Gumbel sampling is employed for optimization, Eq. (6) in line 6 is replaced with Eq. (8). Under this setup. in lines 11-12, M assignment matrices are generated using M sampled Gumbel noises, leading to M predicted MCES results. These results are evaluated using Eq. (5. and the result with the best objective value is retained as the final output.
Model Configuration. Our implementation of NGA and the baseline methods was conducted using Pytorch and PyG (Paszke et al. 2017 Fey & Lenssen 2019). Most baseline methods were adapted from their official source code repositories ensure consistency with their original implementations. However, for INFMCS, no official source code was publicly available, so we implemented this method from scratch, closely following the algorithmic details and hyperparameter settings described the original paper (Lan et al.) (024)) Our implementation was rigorously validated against the reported results in the literature to ensure correctness. Given the molecular nature of our dataset, we utilized the atom encoder and bond encoder from the Open Graph Benchmark library for feature encoding in all models employing GNN as their backbone. This ensured a fair and consistent representation of molecular data across all GNN-based baselines and our proposed method. The experiments are conducted using an AMD EPYC 7542 CPU and a single NVIDIA 3090 GPU.
6.3 SOLVING MCES PROBLEMS
The key property of NGA is its ability to approximate solutions in polynominal time complexity. As shown in Table our model outperforms baselines on all datasets. Our results are very close to optimal in all datasets, which shows that NGA can effectively approximate solutions within limited time. We have additionally analyzed how often the MCES found by NGA matches the optimal solution in Appendix G.T The supervised graph matching method does not perform well, possibly because the MCES problem is inherently multi-modal, meaning it has multiple equally optimal solutions. is thus difficult for supervised learning method to learn some patterns from multiple ground truth node matching signals. The search method, on the other hand, suffers from scalability issues due to the NP-complete nature of the MCES problem. In the following part, we provide several case studies that investigate the effects of increasing the time budget on performance.
We selected several cases for detailed analysis. The largest MCES solution found thus far as time grows is illustrated in Figure (in Appendix G.2). The visualizations of the MCES structures identified by our NGA method and the second- method, RASCAL, are shown in Figure and Figure 10 (in Appendix G.2). From these figures, it is evident that our method can find better solutions in less time, demonstrating its superiority over other competitive baselines.
https://githhb..e wwt../oo.//aasaaccee sttp////r/sttafo///gggg
8

---

Published as a conference paper at ICLR 2026
AIUS
MOLHIV
MCK-
Molecule
Molecule
Figure 3: Visualization of MCES with NGA. Matched atoms and bonds are highlighted in red, with
circles of the same color indicating correspondences.
Table 3: Comparison of graph retrieval results in terms of three evaluation metrics.
Mean Reciprocal Rank (MRR)
Precision at (P 10)
Mean Average Precision (MAP) T
AIDS
MOLHIV
MCF-7
AIDS
MOLHIV
MCF-7
AIDS
MOLHIV
MCF-7
NeuroMatch
0.676
0.870
0.730
0,911
SimGNN
0.419
0.207
0.468
0.870
0.830
0.850
0.875
0.726
0,703
GMN
0.238
0.291
0.279
0.400
0.310
0.540
0.683
0.699
0.652
XMCS
0.575
0.192
0.530
0.850
0.770
0.730
0.890
0.712
0.753
INEMCS
0.560
0.261
0.324
0.800
0.540
0.840
0.914
0.489
0.788
NGA (ours)
0.844
0.806
0,803
0.890
0.980
0.890
0.974
0.951
0.966
Table I: Results of Accuracy (%) + for MCES.
Table 2: Results of MSE (x10-3) J. for graph similarity.
Dataset
AIDS
MOLHIV
MCF-7
RASCAL
90.67
88.74
90.26
Dataset
AIDS
MOLHIV
MCF-7
FMCS
60.63
67.99
71.54
Mcsplit
61.32
72.74
69.23
NeuroMatch
13.92
19.17
17.34
GlSeeach
43.47
41.12
42.08
SimGNN
15.42
14.38
20.29
NGM
33.34
52.21
42.38
GMN
39.38
29.77
24.03
GANN-GM
49.76
72.18
63.47
XMCS
36.42
21.47
32.22
GA
70.99
71.09
72.92
INEMCS
25.18
16.39
31.12
Gurobi
74.52
78.67
80.76
NGA (ours)
1.13
0.66
0.99
NGA (ours)
98.64
99.20
97.94
6.4 GRAPH SIMILARITY COMPUTATION AND GRAPH RETRIEVAL
In the graph similarity computation experiments, we compare NGA with several baselines. As shown in Table our method surpasses other compared methods by an order of magnitude. Although some methods, such XMCS and INFMCS, learn similarity by implicitly inferring the size of MCES, they disregard the detailed structure of the MCES solution. Our method can learn to generate precise approximation of the MCES structure, leading to lower similarity computation errors.
The graph retrieval results are summarized Table 3 where three evaluation metrics are employed to assess performance from different perspectives. As another application of MCES, graph retrieval emphasizes the relative similarity between graphs rather than the precise computation of graph similarity. However, in where group of target graphs share similar characteristics with the query graph, distinguishing their differences may require analyzing the details common substructures. The experimental results demonstrate that method is stable in retrieval scenarios.

---

Published as a conference paper at ICLR 2026
100
100
95
95
Accuracy (%)
Accuracy (%)
85
85
80
AIDS
80
AIDS MOLHIV
MOLHIV
75
MCF-7
MCF-7
2
64
128
The number of iterations in NGA
Hiiden dimension learnable weights
(a) Varying number of iteration
(b) Varying hidden dimension d
Figure 4: How NGA performs on MCES with different parameters.
6.5 MORE ANALYSIS
In this section, we first analyze the hyperparameters to better understand their impact on the per- formance of NGA. Details of the ablation study are provided in Appendix F and the analysis of the number of Gumbel samples is shown in Appendix G.4 Here, we summarize the impact of the number of iterations m and the hidden dimensions d in Figure
When m O, our method excludes the NGA process entirely, relying solely on similarities computed by the graph feature encoder (Eq. (6)). In this scenario, we observe sharp decrease performance, highlighting the critical role of NGA in achieving strong results. Unlike traditional GA, which requires dozens of iterations to converge, our method delivers competitive performance with as few as two iterations (layers). This demonstrates that the parameterization of temperature is more effective than employing a static parameterization.
Moreover, the hidden dimension significantly affects the expressiveness of our model. When the hidden dimension d small, the expressiveness rather limited. evidenced in Figure 4bb) when d 1, the performance of NGA is comparable to that of traditional method. However, d increases, the performance stcadily improves until saturates at higher dimensions. This further validates the effectiveness of the temperature parameterization in NGA in accordance with Proposition 2 Based on this analysis, we set m = 4 and 32 in all experiments to strike balance between performance and computational efficiency.
To broaden the scope and potential impact of our work, we have conducted additional experiments on subset of QAPLIB (Burkard et al. 1997) instances across different categories in Appendix G.5 where our method exhibits competitive performance compared with baseline methods.
7 CONCLUSION
This study introduces Neural Graduated Assignment (NGA), novel approach to the Maximum Com- mon Edge Subgraph (MCES) problem, of which the scalability remains challenge for traditional methods. Drawing inspirations from annealing mechanism in statistical physics, NGA employs neural architecture to iteratively refine the assignment process, leveraging high-dimensional learnable parameters to improve computational efficiency, scalability, and adaptive problem-solving Empirical results show that NGA significantly outperforms prior methods in both runtime and accuracy, demon- strating strong performance across tasks like graph similarity and retrieval. The introduction of this versatile method offers substantial contributions to the understanding and resolution of assignment problems, suggesting pathways for future exploration and innovation in related areas.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
This work was supported by the National Key R&D Program of China under grant 2022YFA1003900
ETHICS AND REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our research, we provide a comprehensive set of resources. Code is open-sourced at htthtt:://// http::://ggttbb.. com/LOCO-CUHKSZ//M /CC/ A detailed README file offers step-by-step guidance for setting up the computational environment and reproducing the experiments described in this paper.
This research focuses on methodological and technical contributions. It does not involve human subjects, personal data, sensitive information. We not aware of any direct ethical concerns arising from this work.
REFERENCES
Laura Bahiense, Gordana Manić, Breno Piva, and Cid C De Souza. The maximum common edge subgraph problem: polyhedral investigation. Discrete Applied Mathematics, (6)255532533 2012.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the twelfth ACM international conference on web search and data mining, pp. 384-392, 2019.
Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning to search. In International Conference on Machine Learning, pp. 588-598. PMLR, 2021.
A Patrícia Bento, Anne Hersey, Eloy Félix, Greg Landrum, Anna Gaulton, Francis Atkinson, Louisa J Bellis, Marleen De Veij, and Andrew R Leach. An open source chemical structure curation pipeline using rdkit. Journal of Cheminformatics, 12:1-16 2020.
Immanuel M Bomze, Marco Budinich, Panos M Pardalos, and Marcello Pelillo. The maximum clique problem. Handbook of Combinatorial Optimization: Supplement Volume A, pp. 1-74, 1999.
Horst Bunke and Kim Shearer. A graph distance metric based on the maximal common subgraph. Pattern recognition letters, 19(3-4):255-255) 1998.
Rainer Burkard, Mauro Dell' Amico, and Silvano Martello. Assignment problems: revised reprint. SIAM, 2012.
Rainer E Burkard, Stefan E Karisch, and Franz Rendl. Qaplib quadratic assignment problem library. Journal of Global optimization, 10(4):391-403, 1997.
Minsu Cho, Jungmin Lee, and Kyoung Mu Lee. Reweighted random walks for graph matching. In
Computer Vision-ECCV 2010: 11th European Conference on Computer Vision, Heraklion, Crete, Greece, September 5-11, 2010, Proceedings, Part V 11, pp. 492-505. Springer, 2010.
Diane J Cook and Lawrence Holder. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research, 1:231-255, 1993.
Surnjani Djoko, Diane J. Cook, and Lawrence B. Holder. An empirical study of domain knowledge and its benefits to substructure discovery. IEEE Transactions on Knowledge and Data Engineering, 944)5575-586, 1997.
HanssChhistiaa Ehrlich and Matthias Rarey. Maximum common subgraph isomorphism algorithms and their applications in molecular science: review. Wiley Interdisciplinary Reviews: Computa- tional Molecular Science, 1(1):68-79, 1.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: /903. 02428.. 2019.
11

---

Published as a conference paper at ICLR 2026
Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. In International Conference on Learning Representations, 2019.
Marcelo Fiori, Pablo Sprechmann, Joshua Vogelstein, Pablo Musé, and Guillermo Sapiro. Robust multimodal graph matching: Sparse coding meets graph matching. Advances neural information processing systems, 26, 2013.
Michael R Garey and David S Johnson. Computers and intractability, volume 174. freeman San Francisco, 1979.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pp- 1263-1272. PMLR. 2017.
Steven Gold and Anand Rangarajan. A graduated assignment algorithm for graph matching. IEEE Transactions on pattern analysis and machine intelligence, 18(4):377-388, 1996.
Martin Grohe, Gaurav Rattan, and Gerhard Woeginger. Graph similarity and approximate isomor- phism. arXiv preprint arXiv: arXiv:/802.088 /802.00099 2018.
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3), 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in neural information processing systems, 13:22118-221333 2020.
Tom Jacobs and Rebekka Burkholz. Mask in the mirror: Implicit sparsification. In The Thirteenth International Conference on Learning Representations, 2025.
Tom Jacobs, Chao Zhou, and Rebekka Burkholz. Mirror, mirror of the flow: How does regularization shape implicit bias? In Forty-second International Conference on Machine Learning, 2025.
Mark Johnson.
Relating metrics, lines and variables defined on graphs problems in medicinal chemistry. In Graph theory with applications to algorithms and computer science, pp. 457-470, 1985.
Diederik Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.0220 02907, 2016.
Chris Kolb, Tobias Weber, Bernd Bischl, and David Rügamer. Deep weight factorization: Sparse learning through the lens of artificial symmetries. In The Thirteenth International Conference on Learning Representations, 2025.
Zixun Lan, Binjie Hong, Ye Ma, and Fei Ma. More interpretable graph similarity computation via maximum common subgraph inference. IEEE Transactions on Knowledge and Data Engineering, 2024.
Marius Leordeanu and Martial Hebert. A spectral technique for correspondence problems using pairwise constraints. In Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, volume 2, pp. 1482-1489. IEEE, 2005.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference machine learning, pp. 3835-3845. PMLR, 2019.
Zhiyuan Li, Tianhao Wang, Jason D Lee, and Sanjeev Arora. Implicit bias of gradient descent on reparametrized models: On equivalence to mirror descent, Advances in Neural Information Processing Systems, 35:34626-34640, 2022.
12

---

Published as a conference paper at ICLR 2026
Xuanzhou Liu, Lin Zhang, Jiaqi Sun, Yujiu Yang, and Haiqin Yang. D2match: leveraging deep learning and degeneracy for subgraph matching. In International Conference on Machine Learning. pp. 22454-22472 PMLR, 2023.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching, arXiv preprini wxXi:2207.00309, 2020.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. Advances in Neural Information Processing Systems, 00:49555-495777 2023.
Ciaran McCreesh, Samba Ndojh Ndiaye, Patrick Prosser, and Christine Solnon. Clique and constraint models for maximum common (connected) subgraph problems. In International Conference on Principles and Practice of Constraint Programming, pp. 350-368, 2016.
Ciaran McCreesh, Patrick Prosser, and James Trimble. A partitioning algorithm for maximum common subgraph problems. 2017.
Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning latent permutations with gumbel- sinkhorn networks. arXiv preprint
2018
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663, 2020.
Samba Ndojh Ndiaye and Christine Solnon. Cp models for maximum common subgraph problems. In International Conference on Principles and Practice of Constraint Programming, pp. 637-644. Springer, 2011.
Deepti Pachauri, Risi Kondor, and Vikas Singh. Solving the multi-way matching problem by permutation synchronization. Advances in neural information processing systems, 26, 2013.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 15:11551-4,, 2022.
Anand Rangarajan, Steven Gold, and Eric Mjolsness. A novel optimizing network architecture with applications. Neural Computation, 865):044110000, 1996a.
Anand Rangarajan, Alan L Yuille, Steven Gold, and Eric Mjolsness. A convergence proof for the softassign quadratic assignment algorithm. Advances neural information processing systems, 1996b.
John W Raymond, Fleanor J Gardiner, and Peter Willett. Rascal: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45(6))631-644, 2002.
Indradyumna Roy, Soumen Chakrabarti, and Abir De. Maximum common subgraph guided graph retrieval: late and carly interaction networks. Advances in Neural Information Processing Systems, 35:32112-32122 2022a.
Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 8115-8123 2022b.
Martin JA Schuetz, J Kyle Brubaker, and Helmut G Katzgraber. Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence, 4(4):367-377, 2022.
Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices.
Pacific Journal of Mathematics, 21(2):343-348, 1967.
13

---

Published as a conference paper at ICLR 2026
Jan-Grimo Sobez and Markus Reiher. Molassembler: Molecular graph construction, modification, and conformer generation for inorganic and organic molecules. Journal of chemical information and modeling, (008):384-33900 2020.
Joshua T Vogelstein, John M Conroy, Vince Lyzinski, Louis J Podrazik, Steven G Kratzer, Eric Harley, Donniell E Fishkind, R Jacob Vogelstein, and Carey E Priebe. Fast approximate quadratic programming for graph matching. PLOS one, 10(4):e012102. 2015.
Runzhong Wang. Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learning lawler's quadratic assignment problem with extension to hypergraph and multiple-graph matching, IEEE Trunsactions on Puttern Analysis and Machine Intelligence, (19)):261-5277) 2021.
Runzhong Wang. Junchi Yan, and Xiaokang Yang. Unsupervised learning of graph matching with mixture of modes via discrepancy minimization. IEÉE Transactions on Pattern Analysis and Machine Intelligence, 45000:10500-10511 2023.
Yifan Xia, Tianwei Ye, Huabing Zhou, Zhongyuan Wang, and Jiayi Ma. Multi-shape matching with cycle consistency basis via functional maps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pp. 8575 3575-8583, 2025.
Xifeng Yan, Philip S Yu, and Jiawei Han. Substructure similarity search in graph databases. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pp. 766-777, 2005.
Chaolong Ying, Xinjian Zhao, and Tianshu Yu. Boosting graph pooling with persistent homology. In Advances in Neural Information Processing Systems, volume 37, pp. 19087-19113 2024.
Chaolong Ying, Yinan Zhang, Lei Zhang, Jiazhuang Wang, Shujun Jia, and Tianshu Yu. Um3: Unsupervised map to map matching. arXiv preprint arXiv:2508. 16874, 2025.
Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. A path following algorithm for the graph matching problem. IEEE transactions pattern analysis and machine intelligence, 31(12): 2227-2242, 2008.
Xiang Zhao, Chuan Xiao, Xuemin Lin, Qing Liu, and Wenjie Zhang. A partition-based approach to structure similarity search. Proceedings of the VLDB Endowment, 763):199-180 2013.
Xinjian Zhao, Chaolong Ying. Yaoyao Xu, and Tianshu Yu. Graph learning with distributional edge layouts. In Proceedings of the 31 ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. I, pp. 2055-2066, 2025.
Weiguo Zheng, Lei Zou, Xiang Lian, Dong Wang, and Dongyan Zhao Graph similarity search with edit distance constraint in large graph databases. In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, pp. 1595-1660 1600. ACM, 2013.
14

---

Published as a conference paper at ICLR 2026
G, Oxetane
G Ether
MCIS
MCES
Figure 5: The maximum common induced subgraph (MCIS) and the maximum common edge subgraph (MCES) of two labeled graphs.
A MORE BACKGROUND
Maximum Common Subgraph. The maximum common subgraph (MCS) problem (Bunke & Shearer 1998) is fundamental topic in graph theory with significant implications in various real- world applications. Given two graphs, the goal of the MCS problem is to find the largest subgraph that isomorphic to subgraph of both input graphs. The MCS problem inherently captures the degree of similarity between two graphs, is domain-indeeeenden,, and therefore finds extensive applications across various fields, such substructure similarity search in databases Yan al.) 2005), source code analysis (Djoko et al. 1997) and computer vision (Cook & Holder 1993). The MCS problem can be broadly categorized into two variants: the maximum common induced subgraph (MCIS) and the maximum common edge subgraph (MCES). The key distinction between these variants lies in the structural constraints: MCIS focuses on finding subgraph that preserves both vertex and edge connectivity, whereas MCES concentrates maximizing common edge structure without enforcing vertex-induces constraints (Ndiaye & Solnon! 201T). An example of MCIS and MCES is shown in Figure This paper focuses the MCES problem, which is particularly applicable to practical tasks in bioinformatics, such as finding similar substructures in compounds with similar properties (Ehrlich) & Rarey 2011), where the edge-based relationships often carry significant biological meaning.
Graph Similarity. A key challenge pharmaceutical research involving small molecules is organizing individual compounds into structurally related families or clusters. Manually sorting through large databases can be labor-intensive, which why automated methods are frequently employed. These automated clustering techniques require a similarity metric for pairwise structure comparison and clustering algorithm to categorize compounds into related groups
Graph Retrieval. Graph retrieval involves identifying and ranking target graphs based on their similarity to given query graph GG (Roy et al., 2022b a). The task can be framed ranking problem, where a graph retrieval system assigns similarity scores or distance metrics to target graphs relative to Gg. The process typically consists of two steps: first, calculating a similarity score for each target graph G.; and second, ranking the target graphs in decreasing order of similarity. The quality of graph retrieval algorithm depends on its ability to place the most relevant graphs at the top of the ranking. A key challenge in this domain is the design of effective scoring functions. In this work, we adopt the Johnson similarity as scoring function, where the target graph with the highest similarity to G, is deemed the most relevant and ranked highest.
15

---

Published as a conference paper at ICLR 2026
Graph Neural Networks. Graph Neural Networks (GNNs) are a class of deep learning models specifically designed to process data represented as graphs. By leveraging the graph structure, GNNs can capture complex dependencies and interactions, enabling them to learn rich representations of nodes and entire graphs. These models utilize message passing mechanisms to iteratively aggregate information from neighboring nodes, ultimately allowing them to excel in various applications. As GNNs continue to evolve, they offer powerful tools for tackling challenges in machine learning and artificial intelligence across diverse domains (Hamilton et al. 2017] Ying et al.) 2024 Zhao et al.
2025). Given an input graph, typical GNNs compute node emheddings h Vu E V with T layers of iterative message passing (Gilmer et al. 2017):
h ((+1) vb
h VEN.
Eh olew))
(12)
for each E |0, - 1], where Nº {o E Vl(u, r) E}, while up and o are neural networks, e.g. implemented using multilayer perceptrons (MLPs).
Graduated Assignment. The Graduated Assignment (GA) is classical optimization method rooted in principles of statistical physics and commonly applied to assignment problems such as graph matching (Gold & Rangarajan 1996 Cho al. 2010). GA operates by iteratively updating soft assignment matrix, which represents the probabilistic relationship between elements of two sets (e.g., nodes, edges) that are being matched. One should note that GA not a neural method and only consists of forward updates.
B ASSOCIATION COMMON GRAPH EXPLANATION
Proposition 1. Denote the node set of GIOG2 as Vo = v(l, E V(Gi), v E }. Consider set of subgraphs of G Gz22 where each node of of G1 and G2 is selected at most once, i.e. any two nodes (u,, 0t) and (uz, Uz) in this set satisfy u, + új and v, + Uj. Any subgraph in this set is a valid common subgraph of G1 and G2, and finding the MCES of two graphs is reduced to finding the largest subgraph in this set.
Proof. Denote the node set of GlOG2 as Vo ((u,, vj) u, E v(Gi), E V(G2)), In every common subgraph G' of G1 and G2, each vertex is isomorphic to a distinct vertex in V(G,) and V(22). If the subgraph of the ACG we select contains two vertices in the same row, implies that a vertex in G2 corresponds to two vertices in G,, which is not valid. To prevent duplication in the mapping between the two graphs, we define subgraph of the association graph as valid if and only if it satisfies the following conditions:
V(G) S Vo-
E(G) C E [VG - (in())(G))) V(G2) Vu, uz), (ux,,) V(G), i k
(13)
We aim to show that each valid subgraph G can be transformed into a common subgraph G' of Gi and G2, satisfying [EG) [-))). In this way, finding the MCES of two graphs is reduced to finding the largest subgraph in this set. Let Gi denote the set of all valid subgraphs of G OG2, and let G2 denote the of all common subgraphs of G1 and G2. We claim that there exists surjective function ʃ 91 - G2 that transforms G into G', such that [ = [G)) If this claim holds, each subgraph of the association graph G₁ OG2 corresponds to a common subgraph of G1 and G2 without omitting any common subgraph. Consequently, the subgraph with the largest number of edges corresponds to the MCES. Here we give the construction of f. and the proof of the surjection of function f. The edge set of G is given by È (((u, vi), (uy, U5)) ((u,, Uz). (u,, vy)) (z)) E E From this edge set, we restore all the edge information in the original graph G1, denoted as {(u,, uz) ([u,, v;), (uj, 0;)) E] C i. The corresponding vertex set is naturally defined as [uk 3u, (uk. 4) E E'). Thus, the subgraph G' = (E', Vn) C G1 is uniquely determined, and define f(G) G¹. Similarly, we construct G" {E" C (()),, D" C ((2))) G2. Since the matching pair in E is unique, G' is isomorphic to G" Hence, G' = f(G) is the desired common subgraph of G2 and G2. Furthermore, it is straightforward to verify that E(G) = ((((
16

---

Published as a conference paper at ICLR 2026
A
0
Mangaaian
NGA
Figure 6: An illustration of the ACG. Each value in the soft assignment S or hard assignment P corresponds to a node in the ACG Ag and thus can be considered as node features Ag.
Next, we represent the node information of a valid subgraph of G OG2 using an assignment matrix. Let P (Paj), where Pú if and only if (ui, 0y) E (G). Since the association graph is already known, the assignment matrix
sufficient to restore the valid subgraph. Thus, from this point forward, only need to work with the assignment matrix. Any assignment can be be mapped to a common subgraph, thereby enhancing interpretability of our formulation of MCES. Consider an
example in Figure [ where NGA outputs an assignment matrix with entries Pt. P2b P3c In this case, the assignment represents valid subgraph G with vertices V(G) = {1a, 2b, 3c}. Using association graph, straightforward to derive the unique corresponding subgraph G and the original common subgraph G" by applying the function f. Thus, instead of working directly with G' or G, we can represent the subgraph using only the assignment matrix.
C EXPERIMENTAL SETUP
C.1 DATASETS
Table 4: The statistics of datasets.
#graphs
#nodes
#edges
AIDS
2000
~55.7
16.2
MCF-7
27770
2624
288.5
MOLHIV
41127
25.5
27.5
The key statistics of datasets used in this paper are summarized in Table 4 distributions of three datasets are illustrated in Figure
The solution time
C.2 DISCUSSION OF BASELINE METHODS
For our comparison, we select baseline methods that are directly or indirectly related solving the MCES problem. RASCAL and FMCS are the most relevant baselines, as they are specifically designed to solve MCES. While some methods, such as Mcsplit, are primarily developed for the MCIS problem, they are still capable of generating common subgraphs. According to the definition of MCES, the number of edges in the common subgraph of an MCIS will always be less than or equal to that of an MCES, i... {(MCIS G2)) | (MCESS G2)) As such, MCIS solvers also valid comparisons. However, some methods are not suitable for serving as compared baselines. Some studies, such as (Bahiense et al. 2012). disregard edge labels that essential for molecular graphs.
17

---

Published as a conference paper at ICLR 2026
Sa Sokiten time
Sokutlen- ti
6
Selution time
-00
<50
-00
160, 3603] [2000, 20036) >-2000
(50, 2620)
[50, 2600)
O
(1602, 20000]
[7600, 20000)
>28000
2200002
(a) AIDS
(b) MOLHIV
(c) MCF-7
Figure 7: Solution time distributions three datasets
XMCS and INFMCS, on the other hand, only implicitly infer the size of the MCS for downstream tasks without providing explicit MCS structures. As result, these methods are used only as baselines in our graph similarity computation and graph retrieval experiments.
Besides, we provide time complexity comparison between baseline methods and ours this section. For notation simplicity, we assume that both the input graphs have N nodes and E edges. The construction of the ACG requires enumerating all edge pairs between the two input graphs G and G2, leading to time complexity of OEE²). In practice, however, this cost is very limited because molecular graphs are typically sparse - each atom usually has only a few neighbors (typically up to 4) due to chemical valency constraints and thus E < N2. Besides, exists only when the corresponding pair of edges in G1 and G2 satisfy the compatibility constraints. Consequently, the actual number of edges M in ACG satisfies M < E N The space complexity of constructing the ACG is O(M). To handle this efficiently. we can store the ACG using sparse data structures, such sparse tensors, which allow memory usage scale with ((M) rather than with the dense upper bound. This ensures that the space overhead remains manageable even for relatively large graphs.
edge in the ACG
The initial assignments are obtained by GNN with a complexity of O(N2d). Therefore, the overall complexity is O(M + The complexity of NGA iteration O(m{(M + _N2)), where m is the number of iterations and & is the number of epochs in training. Overall, the time complexity of our method is O(mk (M + N2)). GA has the same iteration process as our method, which has a complexity of (mm(M + N2)). NGM has the same complexity as our method, which (mm((M + N²)). The rest baseline methods, including RASCAL, FMCS and Mcsplit have complexity of approximately O(2%) ) due to the NP-complete nature of the MCES problem. Compared with these baseline methods, our proposed method provides efficient approximations of the solution in polynomial time without relying on exhaustive exploration of the solution space.
D CONVERGENCE ANALYSIS
In this section, we first analyze the convergence behavior under our learnable temperature parameteri- zation, and then prove the advantages of product parameterization.
D.1 CONVERGENCE BEHAVIOR UNDER LEARNABLE PARAMETERS
The quadratic assignment objective function in Eq. ① is formulated as follows (Rangarajan et al. 1996a) with regularizations:
E E(S, 11v) vec(S)T Ao vec(S)) + TT (S1n, 1,,)
+ v(S In; 1m2) I vec(()) vec(S)
(14)
+ 1 Σ
S Slog S,
8
18

---

Published as a conference paper at ICLR 2026
where E is the energy function, 7l and are Lagrange parameters for constraint satisfaction, y is parameter for the amplifiiiiiiiooo term, and | is deterministic annealing control parameter.
We analyze the convergence behavior at each iteration layer and temporarily omit the layer index (i) for simplicity and denote 3 = W W2 as the learnable parameter. In the first part of the proof, we show that proper choice of parameter 7, is guaranteed decrease the energy function. The energy function in Eq. 14) can be simplified by collecting together all quadratic terms in S, i.e. we define
(m)
Ao + +1I
(15)
Consider the following algebraic transformation:
X
oTo
+ min( x Tox
(16)
2
2
and convert the quadratie form into simpler, more tractable linear form:
1
A o
B BSS
2
+ 1a (S1, - 1m,) + +(S 1m - lm2)
(17)
+ 1
8 Σ S log S
We use deg; represent the degree of node i and degmax max deg.. By setting degmux + where e is a small quantity, the following equation holds for any nonzero vector x:
x
Aox + x diag(1)x
X, Xx, + Σ
(degi + degmax deg, + E)
t=1
1=1
deg:x 2 +
Σ
x;Xjai + Σ
deg;x?)
(18)
i==1
5=1
+
[degmaz deg;
1=1
2 axj(x, + xx,
x Σ
(degmaz - dg +
0
which proves that A is positive definite.
Extremizing Eq. (17 with respect a, have
vec A
vec(S)
(19)
is a minimum, which means that setting vec(S) is guaranteed to decrease the energy function.
In the second part of the proof, we show how the energy function in Eq. increases or decreases according to Sr. In the first part of the proof, we set vec (S), referring o as the original value of
vec(S). To achieve convergence, we need to show that E( a) 2 TE EE(ve(S)), ()) in Eq. (7). The here is the new doubly stochastic matrix gained after executing the Sigmoid and Sinkhorn operator. After each iteration, the new matrix S always reduces the value of the objective function.
Minimizing Eq. [1 with respect Sai. get
1
log S., = =[A(?) 2aa (1a, + vi)
1
(20)
B1
B
19

---

Published as a conference paper at ICLR 2026
From Eq. (00
get the summation
Bi Σ Sai log Sai =
vec(s)² A n²= vec(S))
(21)
1 Σ
+ uvec(()) 1m1
Sai
13
and
31 Jui log Sai
(22)
0 A (1) o 1 o1 + voo1,
1
Σ
oai
B1
From Eq. 21 and Eq. 22 we get
E(o, 0) E(vee(S))
A (7) (-vec(S)²
( Ab10)) o)
aai log Oai
Σ
Sai
log Sai
(23)
31
B1
Σ
Joi log aai
3
S.i
By the non-negativity of the Kullback-Leibler measure, E( o) -
उ. oo 2 0
when 3t > 0 and vice versa. The doubly stochastic property of and a ensures that the Lagrange parameters can be eliminated from the energy function Eq. (I7). The new matrix S gained after setting = veo(S) guarantees the decrease of the energy function.
We distill the core of the proof to highlight the key aspects. At each temperature, the algorithm performs the following steps repeatedly until it reaches convergence.
Step vec(S) Step 2:
Step 2a: Sar f- exp(31 ((4)))ai bj
(24)
Step 2b: S Sinkhorn ($)
Return to Step 1 until convergence.
Our proof shows that when suitably constructed energy function is affect by the temperature parameter 3 during both Step and Step 2. This energy function corresponds to Eq. (17 without the terms involving the Lagrange parameters.
D.2 PROOF OF FASTER CONVERGENCE FOR PRODUCT PARAMETERIZATION
Proposition 2. Under typical gradient descent conditions where the gradient pushes 31 in consistent direction for multiple iterations. the product parameterization 31 W Wa can adaptively adjust the learning rate and induces accelerating effect the magnitude of updates to Bt.
Proof. Let J(S)= vec(S)T Ao vec(S)and g(()
aj be the gradient of the loss step L. For T
direct scalar parameterization B and learning rate 17, the gradient update reads:
8 + (t) ng(().
(25)
For the product parameterization, the update is:
Wi(++ W.() (g)
Wz(1 () W2(1) (g(()
(26)
20

---

Published as a conference paper at ICLR 2026
Let's examine how Pi changes over time. After one update,
(t 1) Wi(t+ 1) W2(t + 1)
(Wi(t) + ng(t) (W2))((()))))) (W2(t) (g(()
(t) (((t)))()))))))))))))))))))))))) W2(t)+
Wi(() + (o(() wa(t) W (1(()
=(((t) + ng(() (IW |[ [[)(()))))((((()))))))))))))))))
+ +r)
(27)
This is nonlinear update equation with respect the gradient g(t), containing both the first-order term ng((() (I11 + (W2(D))²² and the second-order term 1f ((()) If we omit the higher
order gradients, the term (t) T 2 (1) can adaptively adjust the learning rate.
Let's analyze the scenario where the gradient g(t) > 0 for several consecutive iterations, indicating that increasing Br would increase the loss. This common scenario in optimization where the algorithm consistently moves in beneficial direction. For the direct scalar parameterization, the update is
Bi(L+ + 1) (() + nl9(())
(28)
After l iterations with approximately constant gradient magnitude [gl. we get 3:(1 k) (() + An/gl-
(29)
Let Wi(0) Wo. (2 Uo as the initialization state, we can derive:
(Wo + Up)
(1 + nl)))* + (Wo- Uo)
Wi(k) =
(1 n)91)*
2
2
(30)
(2(k) R (Wo + Uo) (1 nl9))*
(Wo- Uo)
(1 1lg))*
2
2
Thus, the first-order term becomes:
nigl +|
7191 ( (|
2 + ((1 + 17/91)2 +(1 )/
(31)
2
+ 2 (W: Un) ((1+
n1.9)) )*
which grows exponentially with the iteration count k. Therefore, the product parameterization leads accelerating updates to 3r. In contrast, the direct scalar parameterization has constant update magnitude nig regardless of the iteration count. Aside from this, this reparameterization naturally
introduces bounds the magnitude of 3r |3:1 S [
(1)
[
L
Moreover, this proposition is supported by empirical evidence. Specifically, we provide the loss curves in Figure 13 Compared to parameterizing the temperature learnable scalar, method exhibits faster convergence. Within the same training time, this results in improved performance. As shown in Table 5 from Appendix F the product parameterization (NGA) outperforms the scalar version (NGA-Scalar) by approximately 15%. These results highlight the effectiveness of our method compared to directly parameterizing 3 as a learnable scalar.
Recent works in the implicit-biis literature have shown that reparameterized models- parielllaat those involving quadratic or low-rank factorizations can induce non-trivial optimization dynamics that resemble adaptive or mirrordeeseettllkk updates. For example. Li et al. (2022) and Jacobs jtt al. (2025) demonstrate that such reparameterizations implicitly modify the effective geometry of gradient descent, leading to adaptive learning-rate behaviors without explicit scheduling. Related work on sparsity-inducing training (Jacobs & Burkholz) 2025 Kolb et al. (2025) further illustrates how factored parameterizations shape convergence trajectories and amplify or damp particular update directions.
Our product parameterization of the temperature term shares conceptual similarities with these findings. These perspectives provide additional insight into why our reparameterizztions can yield favorable optimization behavior in our setting.
21

---

Published as a conference paper at ICLR 2026
E BEHAVIOR AT LOCAL OPTIMA
Before proving Theorem ! we first conclude the following Lemma.
Lemma 1. For a local optimum S and for |3t] sufficiently small, the following property holds:
((++1) ij = 11 (is - h)) + 0133()
(32)
n
where bay (l) and h is the mean of hig over all i and j.
Proof. First, we can characterize the pre-Sinkhorn matrix M through its log-space representation: In M = Byhyy
(33)
By the Sinkhorn-Knon Knopp theorem (Sinkhorn & Knopp 1967, there exist diagonal matrices D, and
De with positive entries such that:
s (1+ D,M D.
(34)
doubly stochastic. Taking logarithm have:
In S (1+1) In D (0) Schii In ( ())
(35)
by
Let's 's define the potentials u, = In D and Uy = =In ( These satisfy:
exp(u, + Sehys - 02)) = =s! -s!+1)
(36)
Σ (1++1) j
Σ exp(u: + 3iyhi + U1) =
1j
(37)
Σ ((++1) = Σ explu: + Syhij + Uj) = 1
When 3t = 0, the Sinkhorn algorithm has trivial solution:
$ (1+1) - u
2 In
(38)
For small [8t], we can view the solution as a perturbation around this base solution. By the implicit function theorem, if the Sinkhorn algorithm converges (guaranteed by our assumptions) and [3]] is sufficiently small, the functions involved are smooth.
Let's write the system of equations that defines our problem. For the doubly stochastic constraints (Eq. (37
F. 3, Σ exp(u; + B.hhe + +0z) 0 Vi
(39)
C,(,,,,)) Σ exp(u: + Sihig + - 1 Vj
(40)
For this system, the smoothness can be verified by checking the insingularity of the Jacobian matrix. Therefore, by the implicit function theorem, there exist unique (up addition of constants) functions u4 (41) and (8) in a neighborhood of 33 = O that satisfy our constraints and are continuously differentiable. Since these functions differentiable at 31 0, we write their Taylor expansions:
u, (B: u 3r (1) + 0(13/1)
(41)
" (8, (0) + B:00 (1) + ((
where us (1)) du
dR a,=0- Then the potentials u, and ny are analytic functions of 3 near To determine u: (1) and we use the row and column sum constraints:
dø = and uz
dv:
Σ exp(u: + Bihey + 0z))
(42)
22

---

Published as a conference paper at ICLR 2026
Substituting the expansions (as when 3t
0, we have u; (0)
= (0)
In
1
In + 8ru; (1) + 0(
U,
2
(43)
1
In + B + 0(3319)
by =
2
into the numerator of S (++1):
exp(Bthis + u, + 0z)
exp(3ihis Inn + Bi + ) +(1811)))
exx((3 + 3 + O(Bi()) )
(44)
n
(1 + ((i) + +u - + 0(1813))
1
Inside the exponential:
u, Brhis Vj
= ( Inn n + Bru. (1) + 0(1311)) + Bihis + + In n + Brof' + +((8(13)
1
(45)
2
= Inn + Br(u, (1) + his + + ) + 0(13113)
Therefore:
exp(u; + Bihis + +U²)
exp(- lno + :c( (2) + big + ) + 0(131))
(46)
= exp(3i(u4) (1) + his + o0 0(181)))
For small [&t], using Taylor expansion of exponential: (xp(3i("u)) (1) + hij + + 0(181))
(47)
= 1 -1+B((1 B1(,
(1) + hig + ( + 0(191))
Then we have:
Σ explu: + Schig + v2)
1 (1 + =.(((u?" + his + (0)++(1333))
(48)
n
Σ + 3:(u (2) byg + 0 + O(
For this equation to be consistent for small |.,1. we must have:
E(al + his + vfl)) 0, Elu hij + +z
(49)
These equations determine u and of up an additive constant.
Next, we check how the overall behavior of ((++) when |3] is sufficiently small. For the assignment matrix:
1 (1+1)
exp(Bihuj + u, + vz) Σk. exp(3i + up + Vm
(50)
23

---

Published as a conference paper at ICLR 2026
Substitute Eq. 43 into the numerator, get the same formulation as Eq. (44 For [ sufficiently small, the subsequent Sinkhorn layer can converge very fast. Therefore, in the denominator:
Σ k,m
(ethkm + uk + vm)
+ B1 + us + t + 0(13113)
(1)
(51)
n
k,m
= 1 + Br(
Mtmm +
Σ k
()) + (
u
72
k,m
m
Let's define = // Ek km hpm- Using Eq. 1 1+ + b) + O(a(a - b)3) for small a, b:
449 and the division formula (1 + a)/(1 + b) =
(1 + Bellig + + +
s(tT)
1+ Bi(n22 Σx u
(1) +E ) + (1
- [11+ B/ir + ui + toj - -n h Σ
(1) (2)
(1)
Σ
2 + ) +((3))
(52)
u
m
[1 + Bi - h) + +(11131
n
where h is the mean of haj.
Having Lemma 1 we can further conclude the following theorem.
Theorem 1. Given local optimum (()), the change A. J(S(++1) J(S()) satisfies
AJ = 2
Σ A 8
En)++
(5) Var(h) + ((
(9)
where hij = [AAoec((S)))ss Var(h) is the variance, ((S()) vec(S(!)) Ao vec(S!") is the objective, x; and μú are the Lagrange multipliers.
Proof. Expand the change objective value, have:
AJ = (()(++))) - ((S
(53)
(rec((((1)-sS))) ) T Ao Aovec((()) + vee(s((t1)s$)) (
From Lemmal
S ((41) //
1 [1 (( - h) + +0(3111 - $D
(54)
Let's analyze the first term in Eq. (53
vec(S((+1) 5(0) T Ao vec(s())
Σ [1 + B/ik h) + 0(13/13)] -S )hij
hij
(55)
Σ n
1 his
B1 Σ
(hig Chis
hihus 0(13119)
n i.j
Since Var(h) = 122 Ei, h12 n
vec( - - Ao Aec((((()) =
- 1hi B: Var(h) + +(181)
(56)
24

---

Published as a conference paper at ICLR 2026
At the local optimum, by KKT conditions:
2huj X; 14j =0
(57)
for entries where ! >
X and My are Lagrange multipliers. Therefore,
Σ 6,
1haj has = Σ
1 5 1/
x M4
n
2
f
(58)
Σ 13))
=
3
using the doubly stochastic constraints. It is easy to show that the second-order term 0(13(3)) Therefore, summing the two terms we have
AJ
A - Σ (4) + 8r Var(h) + 0(131)
(59)
2
F ABLATION STUDY
To better understand the contribution of each component our framework, we conduct an ablation study by systematically removing or modifying key modules, This analysis highlights the effective- ness of individual design choices and demonstrates how each component contributes to the overall performance. The results are summarized in Table
We first propose an ablated variant named NGA-w/o GNN, which removes GNN and instead employs randomly initialized matrix for ( Experimental results reveal that this simplified variant maintains strong performance in solving MCES, thereby demonstrating the crucial role and inherent effectiveness of our subsequent NGA refinement algorithm. While this variant achieves satisfactory results, the integration of GNN generates more optimized initial node assignments through learned representations. This enhanced initialization, when coupled with the NGA refinement process, translates to superior overall performance.
To demonstrate the effectiveness of the exploration and exploitation process of our proposed NGA, we tested variant of our method where we use the Sigmoid function to restrict 3 > 0, denoted as NGA--Psitive. This variant disables the exploration ability of our method. We observe that restricting to positive values significantly degrades performance, indicating that allowing negative temperatures is crucial for effective exploration and for enabling NGA to escape local minima.
To systematically evaluate the sensitivity of NGA Gumbel sampling, conduct ablation by varying the number of samples M. Empirical analysis in 5) that the performance increases sublinearly with M, demonstrating the expected exploatioon-computttio trade-off. Besides, the marginal gain becomes statistically insignificant when M > 10. For comparison, we also imple- ment -u--uubel,, an variant of GA incorporating the Gumbel-Sinkhorn sampling. Under identical experimental protocols, GA-Gum Gumbeel demonstrates consistent performance gains over baseline GA. However, our proposed NGA still significantly outperforms GA-Gumbel, highlighting the necessity of our parameterization of the temperature.
Finally, to demonstrate the superiority of the product parameterization 3 in NGA, we introduce two variants: (1) NGA-Manual employs a manually configured temperature schedule initialized with negative values that gradually transitions to positive values, aligned with the mean parameter
distribution patterns observed in Fig. 11 (2) NGA-Scalar parameterizes temperature as a learnable scalar. In Table 5 both variants exhibit suboptimal performance, primarily due to constrained adaptive capacity and limited expressive power. This performance gap underscores the importance of our design. Note that MLP is composed of learnable weights, which is equivalent to our original implementation.
25

---

Published as a conference paper at ICLR 2026
Table Results of Ablation Study in terms of Accuracy (%)
for solving MCES problem.
Dataset
AIDS
MOLHIV
MCF-7
GA
70.99
71.09
72.92
GA-Gumbel
75.08
74.46
76.12
NGA-w/o GNN
97.45
98.77
97.11
NGA-Positive
83.42
85.63
80.32
NGA-Manual
74.27
70.90
76.45
AGA-Scalar
77.48
82.27
72.94
NGA
98.64
99.20
97.94
S0n dfd 0003
130
2.8
30/2
3003
Tre--eecndo
(a) AIDS
(b) MOLHIV
(c) MCF-7
Figure 8: Comparison of the best MCES solution size found so far on different dataset.
G ADDITIONAL EXPERIMENTAL RESULTS
G.1 ADDITIONAL RESULTS FOR SOLVING MCES
We have additionally conducted a detailed analysis of the quality of the solutions obtained by proposed NGA. In particular, we examine how frequently the MCES identified by NGA coincides with the optimal solution. This evaluation provides deeper insights into the effectiveness and reliability of NGA beyond average performance metrics. The results highlights not only the overall accuracy of the method but also stability across different problem instances. summary of these results is provided in T
Table 6: The percentage of optimal solutions of MCES obtained different datasets.
AIDS
MCF-7
MOLHIV
49%
56%
61%
G.2 RESULTS FOR CASE STUDY
In this section, select several instances from the three datasets as case studies. We give a time budget 3600 seconds and record the best solution found so far for different methods, as shown in Figure 8 On the AIDS and MCF-7 datasets, method can find better solutions within the time budget. On the MOLHIV dataset, both NGA and RASCAL find the best solution, but NGA takes much shorter time.
Specifically, we take AIDS dataset as an example and give detailed illustration about how optimization pushes the solution found far to approximate the optimal MCES. As shown in Figure 9 the current identified common edge subgraph serves as a lower bound, which gradually improved as the optimization process goes.
26

---

Published as a conference paper at ICLR 2026
Molecule
Figure 9: The size of the common edge subgraph found by NGA (serving lower bound) increases over the course of the optimization process (runtime seconds). Matched atoms and bonds are highlighted in red.
Figure 10: Visualization results of MCES for RASCAL.
G.3
EMPIRICAL EVIDENCE
We conduct extensive experiments to demonstrate the empirical evidence of the effectiveness of proposed method. The experiments performed three datasets, and all test instances included. Specifically, we measure the parameterized temperature at different iterations during the training process, particularly after the model has converged. The learned sequence of temperatures across layers represents the optimization trajectory of the problem. This trajectory includes both positive and negative values, where the negative values often play critical role in escaping local optima.
As shown in Figure IT] the parameterized temperature varies with different iterations in NGA, reveal- ing stable trends across the datasets. In the initial iterations of NGA, we observe cautious exploration of the parameter space, characterized by relatively small and stable values of the parameterized tem- perature. As the NGA iteration progresses, the algorithm transitions strategy, reflected by significant increase the magnitude of the parameterized temperature. Our empirical results consistently align with the theoretical analysis, highlighting distinct patterns along the optimization trajectory. These patterns reflect the dynamic behavior the algorithm, where early stages focus exploration and later stages emphasize convergence, guided by the learned temperature sequence.
more aggressive convergence
Importantly, the values shown in Figure I correspond to converged near-converged states. We additionally visualize how | changes in the optimization process in Figure 12 Empirically, we ob- serve that [.3|] takes smaller magnitudes during the early and intermediate iterations preeiselllylllyy when
27

---

Published as a conference paper at ICLR 2026
Seede
(a) AIDS
(b) MOLHIV
(c) MCF-7
Figure 11: Distribution of parameterized temperature values across iterations in NGA on different datasets.
(a) AIDS
(b) MOLHIV
MCF-7
Figure 12: Mean values of parameterized temperature in different NGA iteration layers across epoch on different datasets.
escaping shallow local optima relevant while larger magnitudes emerge in the final refinement phase, consistent with the intended design of NGA. This aligns with the theoretical role of Theorem which analyzes updates around a stationary point rather than global dynamics across layers.
G.4 ADDITIONAL PARAMETER ANALYSIS
To systematically evaluate the sensitivity of our method Gumbel-Sinkhom sampling, we conducted an ablation study by varying the number of samples M. Empirical analysis in [4]ureea4]eeall that the performance increases sublinearly with M, demonstrating the expected exploration-compuree trade-off. Besides, the marginal gain becomes statistically insignificant when M 2 10. Based on these findings, we select M 10 as the optimal trade-off.
G.5 RESULTS ON QAP INSTANCES
To demonstrate the applicability of method address the general QAP problem, conducted additional experiments on Goopmans-Beckmann QAP benchmarks: QAP20, QAP50, and QAP100,
(a) AIDS
(b) MOLHIV
(c) MCF-7
Figure 13: Loss curves across epochs on different datasets. NGA-Scalar represents an variant of NGA by setting the temperature value learnable scalar.
28

---

Published as a conference paper at ICLR 2026
MOLIIV
MCFF7
5
10
20
Nomber Gambel samples
Figure 14: How the number of Gumbel samples affect NGA.
corresponding to problems with 20, 50, and 100 nodes. In each task, location node coordinates uniformly sampled from the unit square [0, 1J2. The flow fij between facility and is sampled uniformly from [0, 1], symmetrized, diagonal entries
to zero, and randomly set probability = 0.7. We train with up to 5120 instances and evaluate on a test set 256 instances from the same distribution. Since these tasks do not involve the MCES-specific structure, omit ACG construction and directly use the NGA module (Alg- D.. We compare our method with the heuristic solver SM (Leordeanu & Hebert 2005) and the learning-based solver NeuOpt (Ma et al. 2023). The results are summarized in Table Our method achieves competitive or superior solutions across these QAP instances.
with
Table Total Assignment Cost (lower better) on Koopmans- Beckmann's QAP benchmarks
Method
QAP20
QAP50
QAPI00
SM
70.07
446.62
1800.75
NeuOpt
61.37
430.61
1789.22
NGA
62.17
407.59
1726.54
Besides, we conduct additional experiments on a subset of QAPLIB instances across different categories. The compared methods include GLAG (Fiori et al. 2013). PATH (Zaslavskiy et al. 2008 FAQ (Vogelstein et al. 2013). The results are summarized in Table g These results show that while method is primarily designed for MCES, it can still perform competitively general QAP, further demonstrating the versatility of our approach.
Table 8: Total Assignment Cost (lower is better) on 16 Benchmark Examples of the QAPLIB Library
QAP
PATH
GLAG
FAQ
NGA
chr
18048
61430
13088
17598
chrl5a
19086
78296
29018
17352
chr15c
16206
82452
11936
20978
chr20b
5560
13728
2764
3366
chr22b
8500
21970
8774
8580
esc16b
300
320
314
292
roul2
256320
353998
254336
251094
roul5
391270
521882
371458
389048
rou20
778284
1019622
759838
813576
tai10a
152534
218604
157954
145270
tai15a
419224
544304
397376
418618
tail7a
530978
708754
520754
537896
tai20a
753712
1015832
736140
802464
tai30a
1903872
2329604
1908814
1861206
tai35a
2555110
3083180
2531558
2789834
tai40a
3281830
4001224
3237014
3214724
29

---

Published as a conference paper at ICLR 2026
Table 9: MCES results on unlabeled dataset
Dataset
AIDS-unlabeled
RASCAL
89.74
FMCS
61.53
Mcsplit
74.47
GLSearch
68.13
NGM
55.20
GA
67.44
Gurobi
83.89
NGA
93.72
NGA-GPS
94.37
G.6 RESULTS ON UNLABELED DATASETS
To further enhance the generalizability our method, we have additionally conducted experiments on unlabeled graphs. Specifically, constructed an unlabeled version of the AIDS dataset, denoted as AIDS-unlabeled, where all atom types were replaced by carbon atoms (C) and all bonds were converted to single C-C bonds. This transformation results in unlabeled graphs while preserving the overall structural diversity of the original dataset.
In the unlabeled settings, additional structural embeddings may provide meaningful information. We replaced the original GCN backbone in our method NGA with a Graph Transformer architecture equipped with structural encodings (Rampášek et al. (022) and name this variant NGA-GPS, This variant naturally incorporates positional and structural information, enabling NGA to operate effectively when explicit labels are absent.
The experimental settings follow those used in our paper (Appendix 6.2) For NGA and NGA-GPS, we employ an 8-layer GNN with 32 hidden dimensions. The NGA-GPS is equipped with random walk based structural encodings and the multi-head attention mechanism with 4 heads. For the other baseline methods, we also adhere to the configurations described our paper. The experimental results in Table show that our method maintains strong performance even in the unlabeled setting, demonstrating its robustness and potential applicability beyond labeled molecular graphs.
H LIMITATIONS AND FUTURE WORK
This work focuses on labeled graphs, leaving open the question of how handle unlabeled ones. When node or edge labels are absent, learning correspondences relies solely on graph structure, which increases the number of potential matches per node, enlarges the solution space, and makes the problem significantly more challenging.
Multi-graph MCES is meaningful and practically relevant extension of the classical pairwise MCES formulation. In this work, we focus on the pairwise setting, which is the standard and well-established definition of MCES and also a necessary first step toward addressing the long-standing standinn and more general challenge. Pairwise MCES provides the fundamental building block top of which multi- graph formulations are typically constructed. A feasible path toward multi-graph MCES to combine pairwise MCES computations with cycle-consistency constraints, which has been long studied in multi-graph matching (Pachauri et al. 2013) Xia et al.] (025).. Our method can be extended along these lines-by running NGA across all graph pairs and enforeing consistency-to obtain a principled multi-graph solution. We view this direction as natural and promising extension of our work.
I DISCUSSION ON GRAPH LABELS
In the MCES formulation, common subgraph requires exact matching of compatible labels. There- fore, the choice of labels directly reflects what consider as "common structure." Labels can be domain-specific features aligned with the MCES problem definition.
Concrete examples across domains:
30

---

Published as a conference paper at ICLR 2026
Molecular graphs: Atom types (C, N, O) and bond types (single, double, aromatic) are natural labels because pharmacological similarity requires exact chemical structure matching.
Social networks: User attributes (occupation, location, age group) could serve as labels when finding common community structures.
Knowledge graphs: Entity types and relation types naturally define what constitutes matching substructures.
If the application requires tolerance label noise similarity rather than exact matching, could:
Preprocess labels by clustering fine- tne-grained categories into coarser groups
Define softer compatibility functions in the ACG construction (modifying Eq. to allow approximate matching)
Formulate different problem variant (e.g.. approximate common subgraph)
J LLM USAGE STATEMENT
During the preparation of this manuscript, utilized large language model (LLM) writing assistant. The LLM's role was strictly limited to improving the clarity, grammar, and readability of our text through sentence polishing and paragraph restructuring. The LLM did not contribute to research ideation, experimental design, data analysis, or the formulation conclusions. All scientific content and claims the sole responsibility of the human authors.
31


Reviews:
[{"review_id": "6wiDvaLNCK", "reviewer": "Reviewer_iuLj", "summary": "This paper introduces Neural Graduated Assignment (NGA), a novel unsupervised neural optimization framework for solving the Maximum Common Edge Subgraph (MCES) problem. The authors formulate MCES as a Quadratic Assignment Problem (QAP) via the construction of an Association Common Graph (ACG). The core innovation lies in replacing the fixed temperature parameter in classical Graduated Assignment (GA) with a learnable, high-dimensional temperature parameterization, which enables adaptive exploration and exploitation during optimization. The method is unsupervised, scalable, and theoretically analyzed for its convergence and local optima escape behavior. Extensive experiments on molecular datasets demonstrate that NGA significantly outperforms existing methods in accuracy, scalability, and efficiency, and shows strong performance in downstream tasks like graph similarity computation and retrieval.", "questions": "1，ACG Scalability: What is the time and space complexity of constructing the ACG? How does it scale with graph size and label dimensionality? Could approximate or sparse ACG constructions be used for very large graphs?\n\n2， Generalization to Unlabeled Graphs: Have you considered or experimented with unlabeled graphs? Could structural embeddings (e.g., positional encodings) replace or complement label information in such cases?\n\n3， Training Stability: The product parameterization β_l = W_1^T  W_2 can lead to unstable gradients. Did you observe such issues during training? Were any techniques (e.g., gradient clipping, normalization) used to stabilize training?\n\n4, Choice of Parameterization: Why was the product form W_1^T  W_2 ​ chosen over other parameterizations (e.g., MLP or direct scalar)? Was this motivated by empirical performance or theoretical insights?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1, Novel Formulation and Guarantees: The introduction of the Association Common Graph (ACG) is a crucial contribution. It provides an elegant way to ensure that any valid subgraph extracted from it is a correct common subgraph of the input graphs. This formulation cleanly transforms the MCES problem into a QAP with inherent structural guarantees, a foundational step that enables the subsequent neural optimization.\n2, Rigorous Theoretical Underpinning: The paper goes beyond empirical results by providing a solid theoretical analysis. It explains how NGA escapes local optima (Theorem 1) by leveraging the variance of the gradient, and why the product parameterization accelerates convergence (Proposition 2) compared to a scalar one. This theoretical grounding significantly strengthens the methodological claims.\n\n3, Differentiable and Adaptive Optimization Core: The proposed Neural Graduated Assignment (NGA) mechanism is the paper's central innovation. By replacing the static temperature in classical GA with a learnable, high-dimensional parameterization (  β_l = W_1^T  W_2), the method dynamically balances exploration and exploitation. This design eliminates cumbersome manual scheduling and allows the model to adapt its optimization trajectory to the specific problem instance, leading to faster convergence and better performance.", "weaknesses": "1.Limited Discussion on Unlabeled Graphs: The method assumes labeled graphs (node/edge features). While this is reasonable for molecular data, many real-world graphs are unlabeled or partially labeled. The paper does not discuss how NGA might be adapted to such settings, which limits its generalizability.\n\n2, Computational Overhead of ACG: The construction of the ACG is central to the method but may become computationally expensive for very large graphs. The paper does not analyze the scalability of ACG construction in depth, nor does it compare its overhead relative to the overall optimization.\n\n3, Theoretical Assumptions: The theoretical analysis relies on small ∣ β_l ​ ∣ assumptions (Lemma 1), which may not always hold in practice. The empirical distribution of  ∣ β_l ​ ∣  (Fig. 11) shows both small and large values, so the applicability of the theory across all layers is not fully justified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0RgKKcUlnO", "reviewer": "Reviewer_6SDK", "summary": "This work tackles the Maximum Common Edge Subgraph (MCES) problem: given two labeled graphs, the goal is to find the largest shared subgraph with the maximum number of common edges. This problem is especially relevant in molecular analysis and is NP-complete. The proposed method, Neural Graduated Assignment (NGA), is an unsupervised, learnable approximation with three main components: (i) it constructs an Association Common Graph (ACG) that only considers node and edge pairs that are label-compatible; (ii) it learns a soft node-to-node assignment that is iteratively refined using a learnable, high-dimensional temperature, which the authors argue improves convergence behavior; and (iii) it discretizes this soft assignment into a final match, using multiple sampled candidates at inference time to encourage exploration. The experiments evaluate NGA both on MCES quality and on downstream tasks such as graph similarity prediction and graph retrieval. NGA outperforms prior baselines under time-constrained scenarios on molecular datasets. Ablation studies support several design choices (use of high-dimensional temperature, sampling strategy, etc.) and provide insight into optimization dynamics.", "questions": "1. Why would supervised methods perform badly with multiple ground truths? Don't most tasks in deep learning have multiple equally good solutions anyway?\n2. How do the methods compare in number of learnable parameters?\n3. Can the labels/features be anything? How would the method perform if they are e.g. too fine-grained or noisy? For instance, in molecular datasets we know that the atom types are a good label, but in other instances we might not know what to choose.\n4. Relatedly, if the graphs are unlabeled, would it make sense to create the labels by another procedure (e.g. by structural cues) and then run the method? Would this perform better than not giving them any labels?\n5. How does complexity change if the ACG is not sparse? In which (non-molecular) settings can that occur?\n6. Which (non-molecular) domains are other realistic targets for NGA, and which remain out of scope under the current assumptions?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The method explicitly balances exploration and exploitation of the solution space.\n- The paper provides a clear analysis of the optimization dynamics, which gives provable guarantees for convergence.\n- The experiments are thorough: multiple tasks (MCES, similarity, retrieval), strong ablations, and consistent gains over competitive baselines.\n- It provides a better trade-off between scalability and performance than the prior works.", "weaknesses": "1. The method is not reusable for more than one pair of graphs at a time.\n2. The paper assumes molecular settings, which have particular properties: the ACG is sparse, the node and edge labels are known and meaningful, etc.\n3. Runtime is mainly evaluated under a fixed time cap; it would be useful to see quality vs. time curves or difficulty-stratified results.\n4. Minor: some citation formatting issues in the appendix (e.g. lines 719,855,885).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ExiBJ3gFAS", "reviewer": "Reviewer_xBg1", "summary": "This paper introduces the *Neural Graduated Assignment* (NGA), a neural optimization framework designed to solve the MCES problem efficiently. Traditional algorithms for solving MCES suffer from scalability issues, especially when dealing with large graphs. The NGA approach overcomes these limitations by leveraging a learnable temperature mechanism and unsupervised training, allowing the algorithm to scale efficiently and avoid computational bottlenecks. The paper provides theoretical justification for the efficacy of NGA, demonstrating its ability to balance exploration and exploitation in the search process. Experimental results show that NGA significantly improves computation time, scalability, and performance compared to existing methods, making it a promising solution for MCES and related problems.", "questions": "1. Could you provide more details on how the learnable temperature schedule in NGA compares to other dynamic temperature annealing methods in optimization? Is there a specific advantage in using this formulation over others?\n\n2. Could you provide an analysis of CPU/GPU memory usage w.r.t. the scale of graphs?\n\n3. How does the performance of NGA change when applied to graphs with significant amounts of noise or missing data? How would NGA perform in scenarios with highly asymmetric graph pairs (e.g., when the graphs have very different numbers of nodes/edges)? Could you analyze the robustness of NGA?\n\n4. What impact does the choice of neural network architecture have on the overall performance of NGA? Would other architectures, like graph transformers, yield better results?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel Approach: NGA represents advancement in solving the MCES problem by integrating neural components with traditional optimization frameworks. The use of a learnable temperature schedule and the end-to-end trainability of the model is an innovative approach.\n\n2. Theoretical Foundation: The authors provide a strong theoretical analysis of NGA, including its convergence properties and the mechanisms through which it escapes local optima. This adds robustness to the method and makes it more reliable in practical use.\n\n3. Extensive Experiments: The paper includes thorough experimentation across multiple datasets and tasks, such as MCES computation, graph similarity estimation, and graph retrieval, showing that NGA outperforms existing methods in terms of both accuracy and computational efficiency.", "weaknesses": "1. The paper's reliance on modeling MCES as a QAP leads to O(N²) space complexity due to the affinity matrix. For large graphs (e.g., those with more than 100 nodes), this could pose significant memory challenges, making the method less feasible for very large-scale graphs. The paper does not provide an analysis of memory usage, which is a crucial aspect when considering practical applications for large datasets.\n\n2. While the paper claims that NGA is interpretable, the exact mechanisms through which the model learns to assign graph correspondences are not fully clear. The interpretability of the learned assignments, especially in complex graph structures, could be more thoroughly discussed.\n\n3. While the paper compares well against traditional solvers and some learning-based graph matching models (NGM), it could be strengthened by a comparison to other recent neural approaches for combinatorial optimization on graphs, e.g., unsupervised methods for graph matching.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)