Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN
Authors: Wei Huang
Hanchen Wang
Dong Wen
Shaozhen Ma
Wenjie Zhang
Xuemin Lin
Venue: NeurIPS 2025 poster ()
Keywords: Graph Edit Distance
Graph Neural Networks
Combinatorial Optimization
Primary area: deep_learning

Abstract: Graph Edit Distance (GED) is a fundamental graph similarity metric widely used in various applications. However, computing GED is an NP-hard problem. Recent state-of-the-art hybrid GED solver has shown promising performance by formulating GED as a bipartite graph matching problem, then leveraging a generative diffusion model to predict node matching between two graphs, from which both the GED and its corresponding edit path can be extracted using a traditional algorithm. However, such methods typically rely heavily on ground-truth supervision, where the ground-truth node matchings are often costly to obtain in real-world scenarios. In this paper, we propose GEDRanker, a novel unsupervised GAN-based framework for GED computation. Specifically, GEDRanker consists of a matching-based GED solver and introduces an interpretable preference-aware discriminator. By leveraging preference signals over different node matchings derived from edit path lengths, the discriminator can guide the matching-based solver toward generating high-quality node matching without the need for ground-truth supervision. Extensive experiments on benchmark datasets demonstrate that our GEDRanker enables the matching-based GED solver to achieve near-optimal solution quality without any ground-truth supervision.

Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN
Wei Huang University of New South Wales W. huanguunsu edu.au au
Hanchen Wang University of Technology Sydney Hanchen. Wang@uts edu.
Dong Wen University of New South Wales dong. wenSunsw. edu. au
Shaozhen Ma
University of New South Wales shaozhen, mw@unsw............ edu, au
Wenjie Zhang
Xuemin Lin
University of New South Wales wenj ie. zhangdunsw.
Shanghai Jiaotong University xuemin. lin@sjtu edu. cn
edw.eauwwwwwuuuuuaemmmmmoeeeeee. edu. au
Abstract
Graph Edit Distance (GED) is fundamental graph similarity metric widely used in various applications. However, computing GED is NP-hard problem. Recent state-of-the-ar hybrid GED solver has shown promising performance by formu- lating GED bipartite graph matching problem, then leveraging generative diffusion model to predict node matching between two graphs, from which both the GED and its corresponding edit path can be extracted using a traditional algo- rithm. However, such methods typically rely heavily on ground ground-truth supervision, where the ground-truth node matchings are often costly to obtain in real-world scenarios. In this paper, we propose GEDRanker, novel unsupervised GAN- based framework for GED computation. Specifically, GFDRanker consists of a matching based GED solver and introduces an interpretable preference-an awaree discriminator. By leveraging preference signals over different node matchings derived from edit path lengths, the discriminator solver toward generating high-quality node matching without the need for ground- truth supervision. Extensive experiments on benchmark datasets demonstrate that our GEDRanker enables matching-
guide the matching-base bbaedd
GED solver to achieve near-optimal solution quality without any ground -ruth supervision. The source code is available at httts:://iithut httpi/ttuu..mmmiiu...t... com/ppupuppiuu// Sat.upiiiiu/EReaeeer....e GEDRanker
Introduction
Graph Edit Distance (GED) is a widely used graph similarity metric 2 that determines the minimum number of edit operations required to transform one graph into another. It has broad a)
applications in domains such as pattern recognition 4 (5] and computer vision 6 7]. Figure T
illustrates an example of an optimal edit path for transforming G1 to G2 with GED(G, G2) 4. GED is particularly appealing due its interpretability and its ability to capture both attribute-level and structural-level similarities between graphs. Traditional exact approaches for computing GED NP-hardness of GED computation, these methods fail to scale to graphs with more than 16 nodes 9 making them impractical for large graphs.
rely on A search [8] 9 [0]. However, due
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

G₁
M1 Mg
1/
Relabel
Node
Delete
11
(r) Optimal Eddt
Optimal Node Notching
Figure I: (a) An optimal edit path for converting 11 to G2 with GED G2) = 4. (b) An optimal node matching matrix from which optimal edit path can be derived.
To address the limitations of traditional algorithms, hybrid approaches that combine deep learning with traditional algorithms have been widely explored. Recent hybrid approaches have focused on reformulating GED as bipartite graph matching problem. Specifically, GEDGNN [ and GEDIOT [12] propose to train a node matching model that predicts a single node matching probability matrix, where top-k edit paths can be extracted sequentially from the predicted matrices using traditional algorithm. Later on, the current ttate-of-the-- art GED solver, DifIGED [3], employs a generative diffusion model to predict top-k high quality node matching probability matrices in parailel, which parallelized the extraction of top-k edit paths. Notably, DifIGED has achieved near-optimal solution quality, closely approximating the ground-truth GED with remarkable computational efficiency. Unfortunately, all existing hybrid GED solvers heavily rely on supervised learning, requiring ground- truth node matching matrices and GED values, which are often infeasible to obtain practice due to the NP-hard nature of GED computation. This limits the usability of existing GED methods in real-world scenarios. Therefore, developing an unsupervised training framework for GED solvers is crucial for enhancing real-world applicability. Despite its importance, this direction remains largely underexplored.
In this paper, we propose GEDRanker, a novel GAN-based framework that enables the unsupervised training of matching- GED solver without relying on ground-truth node matching matrices. Unlike existing unsupervised training techniques commonly used in other problems, such as REIN- FORCE [14. GEDRanker provides more effective and interpretable learning objective (i.e., loss function) that enables GED solver to directly optimize a GED-related score. Specifically, we design an efficient unsupervised training strategy that incorporates a preference-aware discriminator. Rather than directly estimating the resulting edit path length of the node matching matrix, our preference- aware discriminator evaluates the preference over different node matching matrices, thereby providing richer feedback to guide the matching-basee GED solver toward exploring high-quality solutions.
Contributions. To the best of our knowledge, GEDRanker is the first framework that enables unsupervised training of supervised neural methods for GED computation, offering a scalable and label-free alternative supervised approaches. Experimental results benchmark datasets show that the current state-of-the-an ahtt-arttoo supervised matching-bar based GED solver, when trained under our unsupervised framework, achieves near-optimal solution quality comparable supervised training with the same number of epochs, and outperforms all other supervised learning methods and traditional GED solvers.
Related Work
Traditional Approaches. Early approaches for solving GED are primarily based on exact combi- natorial algorithms, such as A search with handcrafted heuristics I0 While effective on small graphs, these methods are computationally prohibitive on larger graphs due to the NP-hardness of GED computation. To improve scalability, various approximate methods have been developed. These include bipartite matching formulations solved by the Hungarian algorithm [5] or the Volgenant-
Jonker algorithm (16), as well as heuristic variants like A A search [8] that limits the search space to enhance efficiency. However, such approximations often suffer from poor solution quality.
Deep Learning Approaches. More recently, deep learning methods have emerged as promising alternatives. SimGNN [17 and successors [18 20, 21 22 23 formulate GED estimation as a regression task, enabling fast prediction of GED values. However, these methods do not recover the edit path, which is often critical in real applications. As a result, the predicted GED can smaller than the true value, leading infeasible solutions for which no valid edit path exists.

---

Hybrid Approaches. To address the limitations of regression -base deep learning methods, hybrid frameworks have been extensively studied to jointly estimate GED and recover the corresponding edit path. A class of approaches, including Noah (24]. GENN-A* [25] and MATA* * 2d integrate GNNs with A search by generating dynamic heuristics or candidate matches. However, these methods still inherit the scalability bottlenecks of A A search. To improve both solution quality and computational efficiency, GEDGNN [ and GEDIOT [12] reformulate GED estimation as bipartite node matching problem. In this setting, a node matching model is trained to predict a node matching probability matrix, from which top-k edit paths are sequentially extracted using traditional algorithms. To further enhance solution quality and enable parallel extraction of top-k candidates, DiffGED (13), employs a generative diffusion- based node matching model to predict top-k node matching matrices in parallel, achieving near-optimal accuracy with significantly reduced running time. Motivated by its effectiveness and efficiency, we adopt the current state-of-the-ar diffusion- node matching model as the base GED solver of our unsupervised training framework.
3 Preliminaries
3.1 Problem Formulation
Problem Definition (Graph Edit Distance Computation). Given two graphs G1 = (V, Fr, In) and G2 (V2, Foz, I22), where V, F and I. represent the node set, edge set, and labeling function, respectively, we consider three types of edit operations: (1) Node insertion or deletion; (2) Edge insertion or deletion; (3) Node relabeling. An edit path is defined as a sequence of edit operations that transforms G₁ into G2. The Graph Edit Distance (GED) is the length of the optimal edit path that requires the minimum number of edit operations. In this paper, we aim not only to predict GED, but also to recover the corresponding edit path for the predicted GED.
Edit Path Generation. Given pair of graphs G1 and G2 (assuming |Vi > |V2), let {0, 1 V x/Va denote a binary node matching matrix that satisfy the following constraint:
V2s Σ +
Vil Σ Ttlli
V V1,
1
Vu V22
(I)
where [u]][M]] = 1 if node v E V12 is matched to node E V2; otherwise T[u][u]] O. Each E Vi matches to exactly one u E V2, and each u E V22 matches to at most one v E V1. Given n, an edit path can be derived with linear time complexity of (
E1 + E2]) as follows:
(I) For each node u E V2, if is matched to (u)... If u is not matched to any node, then insert a new node with label L2(u) into V.. and match it u. The overall time complexity of this step is ((VV2)).
node e Vi and (v) + L2(u,, then relabel (v)
(2) Suppose u. o E V1 are matched to u, u' E V2, respectively. If (c, E E1 but (u, w') & E2, then delete (v, e²) from E1. If (u, u') E Eg but (v, x²) E1, then insert (v, o') into E1. The overall time complexity of this step is O + |E2)).
Figure (b) shows an optimal node matching matrix from which the optimal edit path in Figure aa) derived. Thus, computing GED can be reformulated as finding the optimal node matching matrix n that minimizes the total number of edit operations c(G), G2, T²) in the resulting edit path.
Greedy Node Matching Matrix Decoding. Let E [0, 1] Val be node matching probability matrix, where t [[] [)] denotes the matching probability between node with node A binary node matching matrix x can be greedily decoded from गे with time complexity of ((1V))2115)) as follows:
(1) Select node pair (v, u) with the highest probability in ft, and set π r|u][u] = 1.
(2) Set all values in the v-th row and u-th column of f to -o0.
(3) Repeat steps (1) and (2) for [V| iterations.
Therefore, GED can be estimated by training a node matching model to generate node matching probability matrix that, when decoded, yields a node matching matrix minimizing the edit path length.
3

---

3.2 Supervised Diffesion-based Node Matching Model
The supervised diffusion- based node matching model
[3 consists of forward process and a reverse process. Intuitively, the forward process progressively corrupts the ground-truth node matching matrix '- over time steps to create sequence of increasing noisy latent variables, such that ((*) = II (()"(x²=) with x = π², where r' with >> the noisy node matching matrix that does not need to satisfy the constraint defined in Equation[]] Next, a denoising network Is takes as input a graph pair (G1, G2), a noisy matching matrix n², and the corresponding time step is trained to reconstruct n" from n². During inference, the reverse process begins from randomly sampled noisy matrix π's, and iteratively applies 9s to refine it towards a high-quality node matching matrix over sequence of time steps (lo, 41;-., (s) with S T, to and Is T, such that pa(afoots G1, G2) = p( II Po P [ G1,G2)
Forward Process. Specifically, let ग E {0. 13 M denote the one-hot encoding of node matching matrix π {0, 1|11///[Va] The forward process corrupts x'~1 to xf as: q(-"|=(|]
1 [- Br 3t
3,
Cat(TT)p - Q.), where Q+
is the transition probability matrix, Cat is the
1-
1
categorical distribution and 3, denotes the corruption ratio. The t-step marginal can be written as: q(> (=9) = Cat( T) where Q, = QiQ2..Q.. this allows x' to be sampled efficiently from x² during training.
Reverse Process. Starting from a randomly sampled noisy node matching matrix rts, each step of the reverse process denoises Tt to Th1-1 as follows:
q(> 1| T²) q "
1
1. (g( 2177)
a( (T0)
Po 1 G1, G2) = o (gp, G2, (t))
(2)
- G1, G2) = Σ | नt (T
(T G2)
Ti ~ (T | G1 G2)
where q(='t-1|7"1 [1)=",==)) 77) is the posterior, is the Sigmoid activation. and p ( G, G') is the node matching probabilities predicted by gø. the detailed architecture go is described in Appendix A.3
During inference, for each reverse step except the final step, a binary noisy node matching matrix . is sampled from (m /== G1, G2) via Bernoulli sampling. For the final reverse step, decode (= G1, G2) following the greedy method described in Section 3.1 obtain constrained binary node matching matrix T The detailed procedure of reverse process can be found Appendix A. To enhance the solution quality, & random initial 7 could be sampled in parallel, and à independent reverse processes could be performed in parallel to generate & candidate node matching matrices, the one results in the shortest edit path will be the final solution.
Supervised Training Strategy. In the supervised learning setting, at each training step. given pair of graphs, random time step is sampled, and a noisy matching matrix x' is sampled from p(<'|=") where n² = x² is the ground-truth optimal node matching matrix. The denoising network Is then takes as input graph pair (G1, G2), noisy matching matrix n², and the time step f, and is trained to recover π from n' by minimizing:
[ [1/]]
Cree(m+)
[T][l log (u[w))) + (1 n"" [u] (u][u]) log (1 Ag (ol(u)) (3)
V
where tig the node matching probability matrix such that: मे (gs (G1, G2, n², t)). However, this training strategy heavily relies on pre-computation of the ground-truth node matching matrix.
Proposed Approach: GEDRanker
4.1 Unsupervised Training Strategy
In practice, the ground-truth x* is often unavailable, making impractical to directly apply the supervised training strategy. Assuming the same set of training graphs as in the supervised learning

---

Tlat
Lp, .) + L
c Nay) -4
e,Or, Cz. Tuel
Greedy Decoding
Update
Record
D2
Fue))
Nv Mlant
BPR Fhun)
((")
dGGr GG,
Fg + (
D2
D,C,, C3
Tre
Sinkhamn
Time step
DdC.,
Cesplore
Cg.
Cree + ACresplore
An overview of GEDRanker. For each training step, given a pair of training graphs, maintain a record of the current best node matching matrix से and the node matching matrix obtained from the previous training step Tiast- noisy matching n² is sampled step i and denoised by the denoising network So to produce node matching scores. The resulting matching probability matrix ago obtained via Gumbel-Sinkhor and greedily decoded to Tg. The preference-aveee aware discriminator Dg is trained to learn a preference ordering over म. That and Tg.. Next, Is is trained to recover ग and maximize the preference score Da G2, "g.) Finally, the record updated by Tg.
Figure 2:
random diffusion time
setting, modified training strategy is to store randomly initialized binary constrained node matching matrix as the current best solution म for each training graph pair. At each training step, for a given pair of graphs, ((<((r"), with nt = म, then Io is trained to recover ग from x² by minimizing Lrea(R)- If the node matching matrix Tg. decoded from ag.- (gg (G1, G2, T t)) yields shorter edit path (i.e., c(G1, G2, T < c(G1, G22, R)), then स is updated to Tgs- This guarantees that Io progressively finds better solution during training, while recovering the current best solution.
sample random I, and sample noisy matching matrix n² from
However, the training objective the above approach fundamentally exploitative, as only focused on recovering the currently best solution rather than actively exploring alternative solutions. While exploitation is beneficial later stages when high-quality solution is available, is inefficient in the early stages of training, where the current best solution is likely far from optimal. In such cases, blindly recovering a suboptimal node matching matrix is ineffective and can mislead ga into poor learning directions, and hinder its ability explore better solutions. Therefore, effective training objective should prioritize exploring for better solutions in the early stages and shift its focus toward recovering figh-uuaitty solutions in the later stages.
RL-based Training Objective.
widely adopted strategy for guiding de 's exploration towards better solutions is the use of reinforcement learning, specifically the REINFORCE (14), such that:
VOJ(Ø) = E,,,, [[c(G], (1GG,,G, ) b) V log a (g. |G, G2, n' t))]
(4)
where c(G1, G2, Tg. is the cost of the edit path computed according to the Edit Path Generation procedure in Section 3.1 and b is baseline used to reduce gradient variance. This method adjusts the parameters of go to increase or decrease the matching probability of each node pair based on the resulting edit path length, encouraging the model generate node matching probability matrices that are more likely to yield shorter edit paths.
Unfortunately, this approach suffers from several limitations: (1) It does not directly optimize the graph edit distance and lacks interpretability, as the edit path length only serves as a scale for gradient updates; (2) It assumes all node pairs in Tgo contribute equally to the edit path length, thus all node pairs are assigned with the same scale, making difficult to distinguish correctly predicted node matching probabilities from incorrect ones; (3) It ignores the combinatorial dependencies among node pairs, but the generated edit path is highly sensitive to such dependencies, limiting gs 's ability efficiently explore high quality solutions.
GAN-based Training Objective. To overcome the limitations of REINFORCE, our GAN-based framework, GEDRanker, leverages discriminator Da to guide go 's exploration for better solutions.
5

---

Algorithm/ 1 Gumbel-Sinkhom
Input: 9o (o(G1, n², t), number of iterations K, temperature
I: Sample Gumbel noise Z E IR Vi with Z [[v][u] Gumbel(O, 1);
2: fg. - (gg(G1. G2, x², ,t,)) 2)/T;
3: for = to K do
4: [go|[i[[u] - no [[][[]] - log Ewers exp [u] [u]::)):
(row-wise normalization)
5: #g..1 Fg.[ui[(/ < के [o] - log Σ Even exp(# [o'][
(column-wise normalization)
6: end for
7: Tgo < gg.(
8: return Tgoi
Specifically, given a node matching matrix n, the discriminator Da is trained to evaluate a and assign GED-related score D& D G2, r). If corresponds to shorter edit path, then it will be assigned with higher score; otherwise, a lower score. Therefore, Iø is trained to maximize Do(G,, G2, m
However, the binary node matching matrix Ty. greedily decoded from kg. = (g G2, n', t)). This decoding process is non-differentiable, preventing Is from learning via gradient- optimiza- tion. To address this issue, we employ the Cuubel--Sinhoon method [27] to obtain differentiable approximation of g.. during training as outlined in Algorithm [1] Intuitively,
-Sinhhnn works by adding Gumbel noise to (G, G2, n², t). followed by applying the Sinkhorn operator to produce a close approximation of a binary node matching matrix that satisfies the constraint defined in Equa- tion 1 Let S() denote the Gumbel-Sinkhore operation, we compute Åg. = ((0g(G G2, x², ()) during training. and decode Tg. from S(ya G2, T" ()) to generate the edit path, rather than decoding from (go(G1, G2, n², ,)). Since Ag. is now differentiable and closely approximates the decoded go we can now train to maximize Do G2, gg.) ) by minimizing the following loss:
Lesplore - Do G2, #g.
Do G2, (gp((1, G2, ()))
Through this GAN-based approach, 9o can directly optimize a GED-related score and provides interpretabilityy. Moreover, the discriminator D3 learn to capture the dependencies between node pairs, and distinguish the influence of each predicted value in aa on the generated edit path, thus can guide the training of Os in more efficient way. Overall, Io is trained to minimize:
Lg. = Lreo(s) Meeplore
where À is a hyperparameter that is dynamically decreased during training, encouraging exploration in the early stages and gradually shifting the focus toward exploitation in the later stages.
4.2 Discriminator
The discriminator Dg is designed to assign a GED-related score to a given node matching matrix m based on graph pair. What score should D, output?
natural approach train Da is directly predict the resulting edit path length of क by minimizing the following loss:
Lo. = (Do -xxp) c(G1, G2, T) 2 ))²
(7)
|1/ + [/]]
where the edit path length is normalized by exp(- V E (0, 1). Ideally, shorter edit path
cG C2
should result a higher score, allowing 9ø to learn to optimize the normalized GED. While this approach is straightforward and reasonable, can it guide 9s towards the correct exploration direction?
Suppose we have two node matching matrices Ja and T2, with exp(- e(.r..2.m)xx [V]++V]]
0.4 and
exp(- Vi Vol
Ga x2)x2) = 0.6. Considering two cases, in Case 1, we have (G1, G2 σΙ) = 0.1 and
Dn G2, T2) 0.9, resulting in LD, = 0.18. In Case 2, we have G G2 m)) = 0.6 and
(D G2 m2) = 0.4, resulting in Lo, = 0.08. Clearly, Case 2 is preferred by Dg due to the lower LD. Consequently, based on the interpretable Lesplore Is would be encouraged to generate मı over

---

T2 as it results in a lower loss. However, πi actually corresponds to longer edit path, meaning that the exploration direction of 9e misled by Dg. and such case would happen frequently when Dg is not well trained. Thus, what matters for Do is not learning the precise normalized edit path length, but rather ensuring the correct preference ordering over different π.
Preference-aware Training Objective. To ensure that De learns the correct preference, we intro- duce a preference-aware discriminator. node matching matrix with a shorter edit path should be preferred (>) over one with a longer edit path. The objective of the preference-aware discrimina- tor is to guarantee that the score assigned to the preferred node matching matrix is ranked higher than that of the less preferred one. Specifically, at each training step, given pair of graphs, we have the current best node matching matrix i and the predicted node matching probability matrix Tg S(go(G, G2, म", ,)). The preference-aware discriminator is trained to minimize the following Bayes Personalized Ranking (BPR) loss (8]
log (DoGi, G2, Rge) Do G2,5) log o (Do(Gi, G2, #) - Do G2, )
R))
if (G G2, Too) cG1, G2, π) if (Gi, G2, Mgo) 2 cGi, G2, 7
LBPR ()
BPR encourages the preference-aware discriminator to increase the preference score of the better node matching matrix while simultancously decreasing the preference score of the worse one, thereby promoting a clear separation between high and low quality solutions. Note that, other ranking loss functions, such as Hinge Loss, could be an alternative. Now, Case 1 yields lower loss of LBPR(m).mg) = 1, whereas Case 2 results in higher loss of LBPR(M).))) = 0.7981. Consequently, Da would choose Case 1, and 96 would be encouraged to generate T2 over T- Notably, for the special case where c(G1, G2, Tas) = c(Gi, G2, LBPR(t, #) is computed in both directions ensure that the loss is minimized only if Ag. and क are assigned with the same preference score.
Moreover, finding better solution becomes increasingly challenging training progresses. Con- sequently, म is updated less frequently in later training stages, leading to a scenario where a single node matching matrix may dominate म. In this case, the discriminator can only learn to rank fg. against this specific म. but may fail to correctly rank a against other node matching matrices. To deal with such case, store additional historical node matching matrix Tast decoded from fg. in the previous training step. We then compute an additional ranking loss LBPR(A,, ((n)) to encourage a more robust ranking mechanism. Overall, the discriminator is trained to minimize the following loss:
LD. -BPPR( .n) + LBPR(R Fba))
The overall framework of GEDRanker is illustrated in Figure 2 and outlined in Algorithm 3
Discriminator Architecture. To effectively capture the dependencies among node pairs and distinguish the influence of each predicted node matching on the resulting edit path, our Do leverages GIN (29) and Anisotropic Graph Neural Network (AGNN) [30 31 32) to compute the embeddings of each node pair, then estimates the preference score directly based on these embeddings. Due to the space limitation, more details about the architecture of Dg can be found in Appendix A.3 and
5 Experiments
5.1 Experimental Settings
We conduct experiments on three widely used real world datasets: AIDS700 [77 Linux B3 17], and IMDB 17 34). Each dataset is split into 60%, 20% and 20% training graphs, validation graphs and testing graphs, respectively. We construct training, validation, and testing graph pairs, and generate their corresponding ground-truth GEDs and node matching matrices for evaluation following the strategy described in [1]. More details of the datasets can be found in Appendix B..
Datasets.
Baselines. We categorize baseline methods and our GEDRanker into three groups: (1) Traditional
approximation methods: Hungarian [5), VJ [66 and GEDGW [2] (2) Supervised hybrid methods:
Noah 244 GENN-A* (25). MATA * 226. GEDGNN M... GEDIOT [12 and DiffGED [13: (3)
Unsupervised hybrid method: GEDRanker. Due to the space limitations, the implementation details
of our GaDRanker could be found in Appendix B.2
7

---

Table 1: Overall performance testing graph pairs. Methods with running time exceeding 24 hours are marked with -. 1: higher is better. 4: lower is better. Bold: best in its own group. Trad, SL and UL denotes Traditional, Supervised Learning and Unsupervised Learning, respectively. Results for baselines, except for GEDIOT and GEDGW, are taken from 13
Datasets
Models
Type
MAE 1
Accurucy
p
7
p@ 1
p@20
Time(s) 1
Hungarian
Trad
8.247
1.1%
0.547
0.431
52.8%
39.9%
0.00011
VJ
Trad
14.085
0.6%
0.372
0.284
41.9%
52%
0.00017
GEDGW
Trad
0.811
53.9%
0.866
0.78
84.9%
85.7 %
0.39255
Noah
SL
3,057
6.6%
0.751
0.629
74.1%
76.9%
0.6158
AIDS700
GENN-A*
SL.
0.632
61.5%
0.903
0.815
85.6%
88%
2. 2.98919
MATA
SL
0.838
58.7%
0.8
0.718
73.6%
77.6%
0.00487
GEDGNN
SL
1.098
52.5%
0.845
0.752
89. 19%1%
88.3%
0.39448
GEDIOT
SL
1.188
53.5%
0.825
0.73
88.6%
86.7%
0.39357
DifGED
SL
0.022
98%
0.992
99.8%
99.7 %
0.0763
GEDRanker (Ours)
UL
0.088
92.6%
0.984
0.969
99.1%
99.1 %
0.0759
Hungarian
Trad
5.35
7.4%
0.696
0.605
74.8%
79.6%
0.00009
VJ
Trad
11.123
0.4%
0.594
0.5
72.8%
76%
0.00013
GEDGW
Trad
0.532
75.4% %
0.919
0.864
90.5%
92.2 %
0.1826
Noah
SL
1.596
9%
0.9
0.834
92 6%.
96%
0. 0.24445
Linux
GENN-A*
ST.
0.213
89.4%
0.954
0.905
99.1%
98. 98%
0.681 76
MATA
SL
0.18
92.3%
0.937
0.893
88.5%
91.8%
0.00464
GEDGNN
SL
0.094
96.6%
0.979
0.969
98 18.9%
99.3%
0. 0.12863
GEDIOT
SL
0.117
95.3%
0.978
0.966
98.8%
99%
0.13535
DifGGED
SL
0.0
100 %
1.0
1.0
100%
100%
0,06982
GEDRanker (Ours)
UL
0.01
99.5%
0.997
0.995
100%
99.8 %
0.06973
Hungarian
Trad
21.673
45.1%
0.778
0.716
83.8%
81.9%
0.0001
VJ
Trad
44.078
26.5%
0.4
0.339
60.1%
62%
0.00038
GEDGW
Trad
0.349
93.9%
0.966
0.953
99.1 1
98.3
0.37496
Noah
SL.
IMDB
GENN-A*
SL
MATA
SL
GEDGNN
SL
2.469
85.5%
0.898
0.879
92.4%
92.1%
0.42428
GEDIOT
SL.
2.822
84.5%
0.9
0.878
92.3%
92.7%
0.41959
DifGED
SL
0.937
94.6%
0.982
0.973
97.5%
98.3
0.15105
GEDRanker (Ours) UL
1.019
94%
0.999
0.97
96.1%
97%
0.15111
Evaluation Metrics. We evaluate the performance of each model using the following metries: (1) Mean Absolute Error (MAB) measures average absolute error between the predicted GED and the ground-truth GED; (2) Accuracy measures the proportion of test pairs whose predicted GED equals the ground-truth GED; (3) Spearman's 's Rank Correlation Coefficient (p), and (4) Kendall's Rank Correlation Coefficient (T) both measure the matching ratio between the ranking results of the predicted GED and the ground-truth GED for each query test graph; (5) Precision at 10/20 (p@ 10, p@ 20) measures the proportion of predicted top-10/20 most similar graphs that appear the ground-truth top-10/2 10/20 similar graphs for each query test graph. (6) Time (s) measures the average running time of each test graph pair.
5.2 Main Results
Table I presents the overall performance of each method on the test graph pairs. Among supervised methods, the diffusion-based node matching model DiffGED achieves near-optimal accuracy across all datasets. Our unsupervised GEDRanker, which trains diffusion-basse without ground-truth labels but with the same number of training epochs, also outperforms other supervised methods and achieves optr-optimal solution quality, with an insignificant performance gap compared to DiffGED.
node matching model
Furthermore, compared to the traditional approximation method GEDGW, GEDRanker consistently achieves higher solution quality while maintaining shorter running times across all datasets. It is worth noting that on the IMDB dataset, GEDGW exhibits a lower MAF, this is because IMDB contains synthetic large graph pairs, where approximated ground-truth GED values might be higher

---

Table 2: Ablation study.
Datasets
Models
MAE
Accuracy
p
T
p@ 1@101
p@201 1
GEDRanker (plain)
0.549
65.4%
0.905
0.837
91.7%
91.5%
GEDRanker (RI.)
0.458
69.3%
0.921
0.86
91.1%
92.7%
AIDS700
GEDRanker (GED)
0.237
82.3%
0.956
0.919
97.6%
96.5%
GEDRanker (Hinge)
0.114
90.5%
0.98
0.96
98.9%
98.6%
GEDRanker
0.088
92.6% %
0.984
0.969
99.1% %
99.1% %
GEDRanker (plain)
0.079
96.2%
0.984
0.973
98.1%
98.3%
GEDRanker (RL)
0.04
98%
0.99
0.984
99.2%
99.2%
Linux
GEDRanker (GED)
0.017
99.2%
0.995
0.992
99.4%
99.6%
GEDRanker (Hinge)
0.002
99.9%
0.999
0.999
100%
100%
GEDRanker
0.01
99.5%
0.997
0.995
100%
99.8%
than the actual ground-truth GED values. As result, lower MAE only reflects the predicted GED values are close the approximated ground-truth values.
5.3 Ablation Study
Exploration Ability. To evaluate the significant of the exploration during unsupervised learning as well as the exploration ability of our proposed GEDRanker, we create three variant models: (1)
GEDRanker (plain), which simply trains ge only recover the current best solution using Crea(#) (#)
without any exploration; (2) GEDRanker (RL), which guides gø 's exploration using REINFORCE by
replacing Leaplore with Equation 4 (3) GEDRanker (GED), which replaces the preference-aware
discriminator with a discriminator that directly estimates the edit path length (Equation 7
Table 2 presents the performance of each variant model on testing graph pairs. The results show that the performance of GEDRanker (plain) drops significantly without exploration, indicating that purely exploitative approach focused solely on recovering the current best solution is insufficient. Furthermore, Figure 3 shows the average edit path length of the best found solutions on training graph pairs. Obviously, GEDRanker (plain) exhibits the weakest ability to discover better solutions, which misleads 9s into recovering suboptimal solutions.
For the variant models that incorporate exploration, GEDRanker (RL), which guides the exploration of 9e using REINFORCE, slightly improves the overall performance and exploration abil-
ity compared GEDRanker (plain) demonstrated in Table [
Bvg EditPate Lorgth
and Figure 3 However, there still remains a significant perfor-
GBS GiS
mance gap compared to our GAN-based approaches GEDRanker
and GEDRanker (GED). This gap arises because REINFORCE cannot directly optimize GED and struggles to capture the de-
pendencies among node pairs well as the individual impact of each node pair on the resulting edit path, whereas our GAN- framework is able to capture both effectively.
50
100
150
200
Epoch
(a) AIDS700
Moreover, the preference-awere aware discriminator used in GEDRanker further enhances the exploration ability, compared the discriminator used in GEDRanker (GED) that directly estimates the edit path length. As shown in Figure 3 average edit path length of the best solution found by GEDRanker converges to a near-optimal value significantly faster than all variant models. indicating a strong ability to explore for high quality solutions. Consequently, this allows 96 more epochs to recover high quality solutions, thereby improving the overall performance, demonstrated in Table
12.
Avg Edit Pate Length
50
100
150
200
Epoch
(b) Linux
In contrast, GEDRanker (GED) struggles identify better so- lutions during the early training phase. This observation aligns with our earlier analysis: diseriminator that directly estimates edit path length may produce incorrect preferences over differ- ent и when Do not yet well-trained, thereby misguiding the exploration direction of go- As training progresses, the edit path
Figure 3: Average edit path length of the best found node matching matrices on training graph pairs.

---

estimation becomes more accurate, such incorrect preference occurs less frequently, thus its exploration ability becomes better than GEDRanker (plain) and GEDRanker (RI.).
Ranking Loss. For the preference-aware discriminator, adopt the BPR ranking loss. To evaluate the effect of alternative ranking loss, we introduce a variant model, GEDRanker (Hinge), which replaces BPR with a Hinge loss rank the preference over different node matching matrices и, Following the same setting as in Equation g the Hinge loss is computed with a margin of 1 when the two node matching matrices yield different edit path lengths, and with margin of O when they result in the same edit path length. In the latter case, the loss is computed in both directions to encourage their predicted scores be as similar as possible. The detailed Hinge loss is shown in Appendix [A.4]
The overall performance of GEDRanker (Hinge) is very close to that of GEDRanker with BPR loss, and both outperform all non-preference-awane variants, as shown in Table 2 further validating the effectiveness of our proposed preference-aware discriminator. However, as shown in Figure 3 the exploration ability of GEDRanker (Hinge) is less stable compared to GEDRanker. On the AIDS700 dataset, they both exhibit similar exploration trends, while on the Linux dataset, GEDRanker (Hinge) performs poorly during the early training phase. This discrepancy arises because Hinge loss produces non-smooth, discontinuous gradients. and it is sensitive to the choice of margin, making optimization less stable. Therefore, we choose adopt BPR loss for our preference aware discriminator.
Conclusion
In this paper, we propose GEDRanker, the first unsupervised training framework for GED computation. Specifically, GEDRanker adopts GAN-based design, consisting node matching- based GED solver and a preference-aware discriminator that evaluates the relative quality of different node matching matrices. Extensive experiments on benchmark datasets demonstrate that GEDRanker enables the current state-of-the the- supervised GED solver achieve near-optimal performance under a fully unsupervised setting, while also outperforming all other supervised and traditional baselines.
Acknowledgments
Hanchen Wang supported by ARC DE250100226. Dong Wen is supported by ARC DP230101445 and ARC DE240100668.
References
[1] K. Gouda and M. Arafa, "An improved global lower bound for graph edit similarity search." Puttern Recognition Letters, vol. 58, pp. 8-14, 2015.
[2] Y. Liang and P. Zhao, "Similarity search in graph databases: A multi-layered indexing approach," in 2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 2017, pp. 783-794.
[3] H. Bunke, "On a relation between graph edit distance and maximum common subgraph," " Pattern recognition letters, vol. 18, no. 8, pp. 689-694, 1997.
[4] P. Maergner, V. Pondenkandath, M. Alberti, M. Liwicki, K. Riesen, R. Ingold, and A. Fischer, "Combining graph edit distance and triplet networks for offline signature verification," Pallern Recognition Letters, vol. 125, pp. 527-533, 2019.
[5] H. Bunke and G. Allermann, "Inexact graph matching for structural pattern recogmition," " Pattern Recognition Letters, vol. 1, no. 4, pp. 245-253, 1983.
[6] M. Cho, K. Alahari, and J. Ponce, "Learning graphs to match," in Proceedings of the IEEE International Conference on Computer Vision, 2013, pp. 25-32.
[7] L. Chen, G. Lin, S. Wang, and Q. Wu, "Graph edit distance reward: Learning to edit scene graph," in Computer Vision-ECCV ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XIX 16. Springer, 2020, pp. 539-554.
[8] M. Neuhaus, K. Riesen, and Bunke, "Fast suboptimal algorithms for the computation of graph edit distance," in Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR
10

---

International Workshops. SSPR 2006 and SPR 2006, Hong Kong, China, August 17-19, 2006. Proceedings. Springer, 2006, pp. 163-172.
[9] D. B. Blumenthal and J. Gamper, "On the exact computation of the graph edit distance," Pattern Recognition Letters, vol. 134, pp. 46-57, 2020.
[10] L. Chang, X. Feng, X. Lin, L. Qin, W. Zhang, and D. Ouyang, "Speeding up ged verification for graph similarity search," in 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 2020. pp. 793-804.
[11] C. Piao, T. Xu, X. Sun, Y. Rong, K. Zhao, and H. Cheng, "Computing graph edit distance via neural graph matching," Proceedings of the VLDB Endowment, vol. 16, no. 8, pp. 1817-1829, 2023.
[12] Q. Cheng, D. Yan, T. Wu, Z. Huang, and Q. Zhang, "Computing approximate graph edit distance via optimal transport," Proceedings of the ACM on Management of Data, vol. 3, no. 1, pp. 1-26, 2025.
[13] W. Huang, H. Wang, D. Wen, W. Zhang, Y. Zhang, and X. Lin, "Diffged: Computing graph edit distance via diffusion-based graph matching," arXiv preprini arXiv: 18245, 2025.
[14] R. J. Williams, "Simple statistical learning," Machine learning. vol. 8, pp. 229-256, 1992.
algorithms for connectionstreinfooceemem
[15] K. Riesen and H. Bunke, "Approximate graph edit distance computation by means of bipartite graph matching," Image and Vision computing, vol. 27, no. 7, pp. 950-959, 2009.
[16] H. Bunke, K. Riesen, and S. Fankhauser, "Speeding up graph edit distance computation through fast bipartite matching." 2011.
[17] Y. Bai, H. Ding, S. Bian, T. Chen, Y. Sun, and W. Wang. "Simggnn A neural network approach to fast graph similarity computation," in Proceedings of the twelfth ACM international conference on web search and data mining, 2019, pp. 384-392.
[18] J. Bai and P. Zhao, "Tagsim: aape- graph similarity learning and computation," Proceed- ings of the VLDB Endowment, vol. 15, no. 2, 2021.
[19] W. Zhuo and G. Tan, "Efficient graph similarity computation with alignment regularization," Advances in Neural Information Processing Systems, vol. 35, pp. 30 181-30 193, 2022.
[20] X. Ling, L. Wu, Wang, Ma, Xu, A. X. Liu, C. Wu, and S. Ji, "Multilevel graph matching networks for deep graph similarity learning," IEEE Transactions on Neural Networks and Learning Systems, vol. 34, no. 2, pp. 799-813, 2021.
[21] Y. Bai, H. Ding, K. Gu, Y. Sun, and W. Wang. "L.earnig- based efficient graph similarity computation via multi-scale convolutional set matching," " in Proceedings of the AAAI conference on artificial intelligence, vol. 34, no. 04, 2020, pp. 3219-3226.
[22] Z. Zhang, J. Bu, M. Ester, 7. Li, C. Yao, Z. Yu, and C. Wang, "H2mn: Graph similarity learning with hierarchical hypergraph matching networks," in Proceedings of the 27th ACM SIGKDD conference on knowledge discovery & data mining, 2021, pp. 2274-2284.
[23] C. Qin, H. Zhao, L. Wang, H. Wang, Y. Zhang, and Y. Fu, "Slow learning and fast infer- ence: Efficient graph similarity computation via knowledge distillation," Advances in Neural Information Processing Systems, vol. 34, pp. 14010-14 121, 2021.
[24] I.. Yang and I.. Zou, "Noah: Neural-optimized a* search algorithm for graph edit distance computation," " in 2021 IEEE 37th International Conference on Data Engineering (ICDE).
IEEE, 2021, pp. 576-587.
[25] R. Wang, T. Zhang, T. Yu, Yan, and X. Yang, "Combinatorial learning of graph edit distance via dynamic embedding." " in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 5241-5250.
[26] J. Liu, M. Zhou, S. Ma, and L. Pan, "Mata*: Combining Icarnable node matching with a algorithm for approximate graph edit distance computation." in Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, 2023, pp. 1503-1512.
[27] G. Mena. D. Belanger, S. Linderman, and J. Snock, "Learning latent permutations with gumbel- sinkhorn networks," arXiv preprint 1rXiv:1802.08666 2018.
[28] Rendle, C. Freudenthaler, Z. Gantner, and Schmidt-Thieme "Bpr: Bayesian personalized ranking from implicit feedback," arXiv preprint
2012.
11

---

[29] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, "How powerful are graph neural networks?" arXiv preprint arXiv: 2018.
[30] C. K. Joshi, Q. Cappart, L.-M. Rousseau, and T. Laurent, "Learning the travelling salesperson problem requires rethinking generalization," arXiv preprint w1Xi::200.077544, 2020.
[31] Z. Sun and Y. Yang. "Difusco: Graph-based diffusion solvers for combinatorial optimization." Advances in Neural Information Processing Systems, vol. 36, pp. 3706-3731, 2023.
[32] R. Qiu, Z. Sun, and Y. Yang. "Dimes: A differentiable meta solver for combinatorial optimization problems," Advances in Neural Information Processing Systems, vol. 35, pp. 25 531-25 546, 2022.
[33] X. Wang, X. Ding, A. K. Tung, S. Ying, and H. Jin, "An efficient graph indexing method," in 2012 IEEE 28th International Conference Data Engineering. TEEE, 2012, pp. 210-221.
[34] P. Yanardag and S. Vishwanathan, "Deep graph kemels,"" in Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, 2015, pp. 1365- 1374.
[35] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, t.. Kaiser, and I. Polosukhin, "Attention all you need," Advances neural information processing systems, vol. 30, 2017.
[36] T. Cai, S. Luo, K. Xu, D. He, T-y. Liu, and L. Wang, "Graphnorm: A principled approach to accelerating graph neural network training." International Conference on Machine Learning. PMLR, 2021, pp. 1204-1215.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope. The key contributions are clearly described at the end of both the abstract and introduction. These contributions are thoroughly elaborated in Section
4
and Appendix [ and validated through extensive experiments presented in Section S and Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, we have discussed the limitations of this work in Appendix D
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our paper fully disclose all the information needed reproduce the main experimental results, the details of implementations and experimental settings can be found in Section [.I and Appendix
We also provide the code and data supplementary
materials.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibilityy can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
14

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Yes, provide the data and code in supplementary materials, with sufficient instructions to reproduce the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
gededdeii///////e/eeeeeeessssse/ CodeSubmiee isi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: Yes, have provide all the training and test details in Section 5.1 and Appendix [
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[No]
Justification:
No previous work reports error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Yes, we provide sufficient information on computer resources neede to repro- duce the experiments in Appendix B.2
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http::
Answer: [Yes]
Justification: Yes, the authors have carefully reviewed the NeurIPS Code of Ethics, and the research in this paper conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The proposed work focuses on Graph Edit Distance (GED), which is primarily foundational research method aimed at improving the computational efficiency of graph similarity measurements. not specifically tied to real- wol-world applications, and it does not directly involve any obvious negative social impact.
16

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., denloymemt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our work does no involve the release of high-risk models, such as pretrained language models, image generators, or scraped datasets. Therefore, our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators original owners of assets used in the paper properly credited and cited. The license and terms of use are properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
17

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: Yes, new assets introduced the paper are well documented, and detailed documentation for the code is provided in the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
18

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy htte:s////errrpsccc/ooooorrrrrrs for what should or should not be described.
19

---

elsv ()))
9+
Es
Pule* Ot.
"a Gs)
Pe(*"|e") (5.00)
Figure 4: Reverse process of diffusion-basee node matching model during inference.
Appendix
A Detailed Method
Algorithm 2 Reverse Process
Input: A pair of graphs (G,, G2);
1: n (0 [Vix
do 2: for = So pTt", G1, G2) σ (go(G), G2, t'),
3:
4: i x - | ,1, G2);
then
5:
p
6: else
7:
- ( G1, G2));;
8: end if
9:
end for
10: return "
Algorithm 3 GEDRanker Training Strategy
1: Initialize म Greedy(#t). Mast Greedy(f), with â ~ U(0, 1)
2: for each epoch
3: Sample ( ~~ ((1, T)) and n' ~ {
4: #gg. + (( G2, n ,));
5: Tgo + Greedy (fta);
6:
Compute (G G2, ). Do G2, Do G2, Mast);
7:
Compute LD, and update Do:
8:
Compute (G1, G2, Ag.);
9:
Compute Ly. and update Jdi
10:
if c(G,, G2 TTo)) < <GG1,, (G,1,G,F 7) then
Update + Tgoi
12:
end if
Update Tast f- Tgsi
14:
end for
A.1 Diffusion-based Node Matching Model Reverse Process
The detailed reverse process of diffusion-basse node matching model is illustrated in Figure 4 and outlined in Algorithm 2
A.2
GEDRanker
The detailed unsupervised training strategy of GEDRanker is outlined in Algorithm
20

---

A.3 Network Architecture
Network Architecture of Do- The denoising network Je takes as input graph pair (G1, G2), noisy matching matrix n², and the corresponding time step i, then predicts a matching score for each node pair. Intuitively, 96 works by computing pair embedding of each node pair, followed by computing the matching score of each node pair based on its pair embedding.
Specifically, for each node V1 and V2, initialize the node embeddings h. and h2 the one-hot encoding of their labels L1 (w) and Ly(u), respectively. For each node pair (u, u) E T', we construct two directional pair embeddings h and h to ensure permutation invariance, since the input graph pair has no inherent order, i.e.. GED(G, G2) =GED(G2, G1). Both It. and ha are initialized using the sinusodial embeddings
(35) of x [u][[N] Moreover, the time step embedding he
initialized as the sinusodial embedding of
Each layer / of ge consists of two stage update. In the first stage, we independently update the node embeddings of each graph based on its own graph structure using siamese GIN [2 as follows:
h GNG, (MLP((1 + d) 1,
E
v'EN (v)
(10)
h = GNG, (MLP(( h
Σ h/w 1)
M'EN, (u)
where e' is learnable scalar, MLP denotes multi-layer perceptron, GNG, and GNg, denote graph normalization (36] over G₃ and G2, respectively.
In the second stage, simultancously update the node embeddings of both graphs and the pair embeddings via Anisotropic Graph Neural Network (AGNN) [0 Bll [2], which incorporates the noisy interactions between node pairs and the corresponding time step
h W/n h W
_ Wiih + Wihh. + Wih
h Wih Wihh Wih
h
on h + MLP(RRILU(GN, + Wihh))
(11)
h i + MLP(ReLU(GN,, Wihh))
h. h. + R. + Σ wh O ((h).)))
w'el/
h4 h ReLLUGGN,,
Σ v'EV
whih o (h
where W W 2: W W/ W 5: W
6: Wi are learnable parameters at layer I, GN,, denote the graph normalization over all node pairs and GNG,G, denote the graph normalization over all nodes in both graphs G₁ and G2.
For L-layer denoising network Jo. the final matching score of each node pair is computed as follows:
I6 (G1, G2, T [)] MLP( MLP(H
(12)
Network Architecture of Dø. The discriminator Do takes as input graph pair (G1, G2) and matching matrix и,, then predicts overall score for л. To better evaluate π, Dg adopts the same structure as 9ø. which computes the embeddings of each node pair in R,, and computes the overall score based on the pair embeddings. Specifically, computing the embeddings for each node pair enables Do to distinguish the influence of individual node pairs in x, while the use of AGNN allows Da to effectively capture complex dependencies between node pairs. An overview of Dy network architecture is presented in Figure 5)a)
21

---

Σ
Sinusoldal
AGNN
AGNN
MLP
Da(Gi, C2.
(a) Network architecture of Dj in GEDRanker
Pair-wise Interaction
9p
DelGr, G.
GIN
GIN
14
(b) Network architecture of Dg in GEDRanker (cost)
Figure 5: Comparison of Dg 's network architecture.
However, since D9 does not include the time step as an input, we remove the time step component from AGNN of the second update stage follows:
h = W h Wh
f With Wihh + Wihh
h w.'h wihht + wish'
h Ny + MLP(RELU(GN,
(13)
h um
= i + (H., Σ wi (hh(.)))
h. h. + ReLU(GNG,
w'EV,
h Ri ReLU (Wih
Σ Wi (h
V'EV
For L-layer discriminator Dg. the overall score of is computed as follows:
Do m2, = Σ
(MLP(hL.)) + MLP(h
(14)
(U.u)TT
A.4 Alternative Ranking Loss
Hinge Loss. Hinge loss could be an alternative ranking loss for our preference-aware discriminator.
At each training step, for a pair of graphs, given the current best node matching matrix म and the
22

---

predicted go. the discriminator can be trained to minimize the following Hinge loss:
max(0, Do(G1, G2. R) Do C2, *ga) + margin)
if (f G2 Too) S (G1, G2, R)
Liinge(Faas m)
max(0, Do(G1, G2, Rag) (o G2, #) + margin)
if (G1, G2, Tag) ) 2 (G1 G2, T))
(15)
(G1, G2 T), otherwise 1. where margin is set 0 if c(1,, G2, Tgp)
B Experimental Setting
B.1
Dataset
We conduct experiments on three widely used real world datasets: AIDS700 17, Linux 33 17
and IMDB 17 34]. Table T shows the statisties of the datasets. For each dataset, split into 60%, 20% and 20% as training graphs, validation graphs and testing graphs, respectively.
To construct training graph pairs, all training graphs with no more than 10 nodes are paired with each other. For these small graph pairs, the ground-truth GEDs and node matching matrices are obtained using the exact algorithm. For graph pairs with more than 10 nodes, ground-truth labels are infeasible to obtain, we follow the strategy described in [1]] to generate 100 synthetic graphs for each training graph with more than 10 nodes. Specifically, for given graph, apply A random edit operations to it, where A is randomly distributed in [1, 10) for graphs with more than 20 nodes, and randomly distributed in [1, 5] for graphs with no more than 20 nodes. A is used ground-truth GED.
approximation of the
To form the validation/testing graph pairs, each validation/testing graph with more than 10 nodes is paired with 100 randomly selected training graphs with no more than 10 nodes. And each validation/testing graph with more than 10 nodes is paired with 100 synthetic graphs.
Table 3: Dataset statistics.
Dataset
# Graphs
Avg V
Avg E
Max V
Max
E
Number of Labels
AIDS700
700
8.9
8.8
10
14
29
Linux
1000
7.6
6.9
10
13
IMDB
1500
13
65.9
89
1467
1
B.2
Implementation Details
Network. The denoising network 96 consists of 6 layers with output dimensions [128, 64, 32, 32,32), 32], while the discriminator Dg consists of 3 layers with output dimensions [128, 64, 32/.
Training. During training, the number of time steps T for the forward process is 1000 with a linear noise schedule, where 3o = 10-1 and 3r = 0.02. For the Gumbel-SSnkhom operator, the number of iterations K' set to 5 and the temperature 7 is set to Moreover, we train go and Dg for 200 epochs with batch size of 128. The loss weight À for Lexptor in Lgs (Equation 6) is linearly annealed from from 1 to 0 during the first 100 epochs, and fixed For the optimizer, We adopt RMSProp with learning rate of 0.001 and weight decay of 5 x 10-4.
for the remaining 100 epochs.
During inference, the number of time steps S for the reverse process is set 10 with linear denoising schedule. For each test graph pair, we generate i = 100 candidate node matching matrices in parallel.
Inference.
Testbed. All experiments are performed using an NVIDIA GeForce RTX 3090 24GB and an Intel Core 19-199900 1290K2 CPU with 128GB RAM.
23

---

Table 4: Overall performance unseen testing graph pairs.
Datasets
Models
Type
MAE
Accuracy
PT
7
p 10
p@
Time(s) 1
Hungarian
Trad
8.237
1.5%
0.527
0.416
54.3%
60.3%
0.0001
VJ
Trad
14.171
0.9%
0.391
0.302
44.9%
52.9%
0.00016
GEDGW
Trad
0,828
53%
0.85
0.764
86.4%
85.8
0.38911
Noah
ST.
3.174
6.8%
0.735
0.617
77.8%
76.4%
0.5765
AIDS700
GENN-A*
SL
0.508
67.1%
0.917
0.836
87.1%
90.6%
3. 3.443226
MATA
SL
0.885
56.0%
0.77
0.689
73.2%
76.6%
0.00486
GEDGNN
SL
1.155
50.5%
0.838
0.746
89.1%
87.6%
0.39344
GEDIOT
SL
1.348
47 47.4%
0.81
0.71
88.4%
86.1/%
0.39707
DifGGED
SL
0.024
96.4 %
0.993
0.986
99.7%
99.7 %
0.07546
GEDRanker (Ours)
UL
0.101
91.4%
0.981
0.963
99
99 %
0.07616
Hungarian
Trad
5.423
7.5%
0.725
0.623
75%
77%
0.00008
VJ
Trad
11.174
0.4%
0.613
0.512
70.6%
74.5%
0.00013
GEDGW
Trad
0.568
73.5%
0.925
0.865
90.9%
91.5 %
0.17768
Noah
ST.
1.879
8%
0.872
0.796
84.3%
92.2%
0.25712
Linux
GENN-A
SL
0.142
92.9%
0.976
0.94
99.6%
99.6%
1.17702
MATA
SL
0.201
91.5%
0.948
0.903
86.2%
90.2%
0.00464
GEDGNN
ST.
0.105
96.2%
0.979
0.968
98.6%
98.5%
0.121669
GEDIOT
SL
0.14
94.8%
0.973
0.959
98. 0%
98.3%
0.12826
DifIGED
SL
0.0
100 %
1.0
1.0
100%
100 %
0.06901
GEDRanker (Ours)
UL
0.008
99.6%
0.998
0.997
99.5%
99.7
0.07065
Hungarian
Trad
21.156
45.9%
0.776
0.717
84.2%
82.1%
0.00012
VJ
Trad
44.072
26.6%
0.4
0.359
60.1%
63.1%
0.00037
GEDGW
Trad
0.349
93.9%
0.966
0.953
99.2%
98.3%
0.37384
Noah
SL
IMDB
GENN-A#
SL
MATA
SL
GEDGNN
ST.
2.484
85.5%
0.895
0.876
92.3%
91.7%
0.42662
GEDIOT
SL
2.83
84.4%
0.989
0.876
92.5%
92.4%
0. 42269
DifGGED
SL
0.932
94.6%
0.982
0.974
97.5%
98.4%
0.15107
GRDRanker (Ours)
UL.
1,025
93.9%
0.998
0.968
96
%
0.15012
C More Experimental Results
C.1 Generalization Ability
To evaluate the generalization ability of GEDRanker, we construct testing graph pairs by pairing each testing graph with 100 unseen testing graphs, instead of with training graphs. The overall performance on these unseen pairs is reported in Table On unseen testing pairs, our unsupervised GEDRanker continues achieve near-optimal performance, with only marginal gap compared to the supervised DifIGED, and consistently outperforms all other supervised and traditional basclines. Furthermore, compared to the results in Table [ there no significant performance drop, demonstrating the generalization ability of our GEDRanker.
C.2 Scalability
Table 5: Overall performance large testing graph pairs.
Datasets
Models
Average GED |
Time(s)
Hungarian
234.656
0.00016
VJ
219.465
0.00039
IMDB-lame
GEDGW
140.278
0.4032
DiffGED (small)
143.607
0.1911
GEDRanker (Ours)
140.138
0.1904
24

---

Table 6: Ablation study Dø's network architecture.
Datasets
Models
MAE +
Accuracy
P
7
p@ 10 f
p@20 t
GEDRanker (cost)
0.528
66.3%
0.907
0.841
90.4%
92%
AIDS700
GEDRanker
0.088
92.6%
0.984
0.969
99.1 %
99.1% %
GEDRanker (cost)
0.102
94.9%
0.98
0.965
96.8%
97.1%
Linux
GEDRanker
0.01
99.5%
0.997
0.995
100 %
99.8%
20
Ground truth
12
Ground truth
GEDRanker
GEDRanker
18-
SEEDaakanncoom
Avg Edit Path Length
GEDRarker(cost)
10
16
14-
12
50
100
150
200
50
100
150
200
Epoch
Epech
(a) AIDS700
(b) Linux
Figure 6: Impact of Dy's network architecture on the average edit path length of the best found node matching matrices training graph pairs.
To evaluate the scalability of GEDRanker, construct training pairs by pairing each large training graph in the IMDB dataset with all other large training graphs, instead of using synthetic graphs. For testing, we form pairs by pairing each large testing graph with 100 large training graphs. Since the scalability of GEDRanker can be inherently influenced by the base model, DifIGED, Therefore, method's effectiveness on large graphs is to evaluate how
an appropriate way demonstrate enhances the scalability of the base model in practice. To do so, we train the base model (DifIGED) only small real-world IMDB graph pairs where ground-truth labels are available, then evaluate on the large testing graph pairs to see the scalability the original base model, and compare with GEDRanker that enables the training of base model large graph pairs without requiring ground-truth supervision. For clear reference, we also compare with traditional methods, and we report the average estimated GED across all testing pairs, along with the average inference time per testing pair.
5allmariuummizzee the overall performance of each method. Under this practical setting, that the supervised DiftGED underperforms the optimization algorithm GEDGW in terms average unsupervised training strategy (GEDRanker), DifIGED can be
GED. However, by leveraging trained on large graphs and subsequently outperforms GEDGW both average GED and running time, hightlighting its scalability.
C.3 Ablation Study on the Network Architecture of D3
To evaluate the impact of Dy's network architecture the performance of GEDRanker, we create a variant model, GEDRanker (cost), that adopts an alternative network design inspired by typical architectures used in regression-based GED estimation [2]. Figure 5(b) shows overview of the network architecture of Da in GEDRanker (cost).
Specifically, given graph pair (G1, G2) and node matching matrix æ, compute nodes embed- dings using GIN. Based on the pairwise node interactions, we then construct a matching cost matrix C' E IR/V [Val, Finally, the score (G1 G2, T) is estimated by (T,, C). The overall architecture of Dg can be represented follows:
25

---

Table 7: Ablation study loss weight X.
Datasets
Models
MAE 4
Accuracy t
P
T
p 10 f
p@20 1
GEDRanker (plain)
0.549
65.4%
0.905
0.837
91.7%
91.5%
AIDS700
GEDRanker (explore)
1.334
39.3%
0.789
0.689
76.5%
79.9%
GEDRanker
0.088
92.6%
0.984
0.969
99.1%
99.1%
GaDRanker (plain)
0.079
96.2%
0.984
0.973
98.1%
98.3%
Linux
GEDRanker (explore)
0.146
93.4%
0.973
0.955
96.6%
98.2%
GEDRanker
0.01
99.5%
0.997
0.995
100%
99.8%
20
GEDRankeripain)
12
GeDRankeripann Gmoundrruth
Simund-rutth
18
GEORanker
Avg Edit Path Length
GEORanker
10
Rug Edit Path
10-
150
100
150
Epoch
Epech
(a) AIDS700
(b) Linux
Figure 7: Impact of X's network architecture the average edit path length of the best found node matching matrices on training graph pairs.
h = GNa, (MLP((1+e) h +
Σ ))
('ENo,(t)
h = GNG. (ML((1 + c) k-
Σ h171))
(1ENGz(u)
(16)
H. = [h
H2 [
C MMMPPHHHHWWW H H,W,HH H. H,,HH,)
Do (T,
where we L 3 and n 16.
Table shows the overall performance of GEDRanker (cost). Surprisingly, GEDRanker (cost) performs significantly worse than GEDRanker. This phenomenon can be attributed to the following reasons: (1) Although GEDRanker (cost) estimates the score by assigning each node pair in æ an individual cost from C, these costs fixed for each node pair, irrespective of the actual value in и. The final score computed as a simple linear combination (R, C'), which neglects the complex dependencies and interactions among node pairs. In contrast, Dd in our GEDRanker directly computes node pair embeddings conditioned on the value in π, and leverages AGNN to capture interactions among node pairs; (2) The node matching matrix
inherently sparse, with most of its elements being O. This sparsity significantly limits the ability of Dg to learn correct C as only a few nonzero elements contribute gradient updates. contrast, Dg our GEDRanker transforms each value in into embeddings that enables effective gradient updates even the value is 0 in π.
Consequently, Do in GEDRanker (cost) struggles estimate the correct preference order different म, thereby misguiding 9o 's exploration direction, as demonstrated in Figure ultimately results in inferior performance.
This
C.4 Ablation Study on Loss Weight À
In our GEDRanker, 9o trained to minimize f.g, ferec(s) + XLexptores where the loss weight is dynamically anncaled during training to prioritize exploration in the early stages and shift go
26

---

Table 8: Ablation study the decay schedule of X.
Decay Schedule
Datasets
MAE +
Accuracy t
P
T
p@ 10
p@20 1
AIDS
0.088
92.6% %
0.984
0.969
99.1%
99.1%
Linear
Linux
0.01
99.5%
0.997
0.995
100%
99.8%
AIDS
0.130
90.2%
0.977
0,955
99.2% %
98.9%
Cosine
Linux
0.012
99.4%
0.996
0.994
99.8%
99.7%
AIDS
0.095
91.7%
0.981
0.963
99.0%
99.2% %
Step
Linux
0.013
99.4%
0.996
0.994
99.9%
99.7%
focus toward recovering high-quality (exploitation) in the later stages. In Section 5.3 evaluated GEDRanker (plain), which trains Ie without any exploration by setting X = 0. To understand the impact of prioritizing exploration through the entire training process, we create a variant model, GEDRanker (explore), where À is fixed at 1.
Table 7 compares the performance of GEDRanker under different settings of X. It is unexpected to observe that GEDRanker (explore) performs extremely poorly on the AIDS700 dataset. Al- though GEDRanker (explore) demonstrates strong exploration ability comparable GEDRanker, as illustrated in Figure 7 its performance is still significantly worse.
The reason for this phenomenon lies in the mismatch between the training objective and the reverse diffusion process during inference.
standard diffusion model, the reverse process is designed to gradually remove noise from the noisy node matching matrix step by step through Markov chain (see Equation 2) During this process, 9s is expected to correctly remove the noise from T². However, GEDRanker (explore) prioritizes exploration throughout the entire training process. This excessive focus on exploration prevents gę from learning the essential noise-removal patterns required by the reverse process. Although Je might still output high-quality node matching probability matrices at some steps, still disrupts the reverse diffusion path, causing significant misalignment with the expected denoising trajectory. Consequently, errors accumulated during reverse process, leading to inferior performance.
In contrast, our GEDRanker dynamically decreases À during training, promoting strong exploration in the early stages, while gradually shifting focus toward effective denoising of nO in alignment with reverse diffusion process. This balanced strategy enables both thorough exploration during training and high-qualit, solutions during inference.
C.5 Ablation Study the Decay Schedule of À
For GEDRanker, we adopt a linear decay schedule for X. To investigate the impact of different decay strategies, we further experiment with cosine decay and step decay: (1) Cosine decay provides similarly smooth transition as linear decay. Compared with the linear scheduler, it assigns more weight to exploration during the early stages and reduces the exploration weight more aggressively in the later stages. (2) Step decay maintains À = 1 throughout the entire exploration phase and then directly drops it to for exploitation.
As shown in Table S, the performance of GEDRanker under different decay schedules exhibits no significant gap, indicating that our method is effective and robust without relying complex scheduling strategies.
C.6 Compatibility
Our unsupervised training method is not limited to DiffGED and can be easily integrated with other hybrid matching- frameworks.
demonstrate the compatibility of GEDRanker, we integrate it with GEDGNN. As shown in Table GEDGNN trained with our unsupervised method achieves performance comparable to that of GEDGNN trained with supervision, highlighting both the effectiveness and compatibility of our approach.
27

---

Table 9: Performance of GEDGNN trained with unsupervised method.
Setting
Datasets
MAE 4
Accuracy
p t 1
p@ 10 t
p@20
AIDS
1.098
52.5%
0.845
0.752
89.1%
88.3%
Supervised
Linux
0.094
96.6%
0.979
0.969
98.9%
99.3%
IMDB
2.469
85.5%
0.898
0.879
92.4%
92.1%
AIDS
1.279
44.6%
0.809
0.712
82.6%
83.7%
Unsupervised
Linux
0.078
96.3%
0.982
0.971
98.2%
98.7%
IMDB
2.536
85.2%
0.896
0.876
92.0%
91.9%
D Discussion of Limitations
Although GEDRanker has demonstrated promising results on the three most commonly used real- world GED datasets, one notable limitation of this paper is that, for pairs of larger graphs, obtaining ground-truth GED values becomes infeasible. As a result, we can only evaluate the differences in estimated GED values among baseline methods, rather than the actual gap between the estimated GED values and the real GED values. This also prevents us from evaluating ranking- maaeed metrics for each test query graph in such scenarios.
28


Reviews:
[{"review_id": "4E7MY72ahV", "reviewer": "Reviewer_eHfB", "summary": "This paper proposes an unsupervised diffusion model training method for node matching between input two graphs. Instead of using supervised node matching information, the author trains the model so as to (i) mimic the current best coupling, (ii) reduce the cost of coupling (iii) increase the preference score obtained from discriminator. The proposed method demonstrates comparable accuracy to existing supervised methods. The author further conducts ablation study about the proposed modules.", "questions": "More evaluation on large scale datasets.\n\nEvaluation on training cost.\n\nEvaluation on the learned discriminator.", "limitations": "Discussed in the appendix.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n\nThe author proposes novel task to train node matching unsupervisedly. To this end, the author proposes several training strategy and loss functions.\n\nThe proposed model learned unsupervisedly shows comparable performance to DiffGED trained supervisedly. This shows that this unsupervised approach is promising.\n\nThe author conducts several ablation study about the proposed modules. All the proposed modules contributes to the performance.\n\n\nWeakness\n\nI want to see the evaluation on the correlation between the discriminator’s preference and true edit distance.\n\nI also want to see the evaluation on the training cost. Since we need to train additional discriminator module, I think we need to train longer epoch than supervised case.\nFurther, I am curious about the semi-supervised performance.\n\nI think the performance may depend on the initial matching policy $\\bar{\\pi}$. What if we initialize $\\bar{\\pi}$ with current best unsupervised method such as GEDGW?\n\nAlso, I think the proposed method is effective in the larger-scale case since we cannot obtain the ground truth supervised information. However, in Table 5, the accuracy of the proposed method is close to the traditional GEDGW. I want to know more evaluation on this large-scale area.", "was_revised": true, "final_justification": "The author rebuttal addressed  my concerns. Therefore, I increase the score.", "rebuttal": "Thanks for providing constructive comments. Below we address each point in detail.\n\n### **1. Evaluation of the discriminator**\n\nWe first would like to clarify that the discriminator is used **solely to guide the training of the matching model** and is **trained in an online manner** based on the distribution of latest solutions sampled from the matching model during exploration phase. It is **NOT used during inference**; therefore, it is **NOT trained to perfectly compute** the preference over all node matching matrices and is also **NOT expected to generalize** to unseen graph pairs. It only aims to provide a relatively good training signal that guides the matching model within the current training epoch. Similar to those discriminators used in image generation, they are not intended to serve as a useful or generalizable image classifier after training. \n\nTherefore, we only need to evaluate **discriminator's online performance**, and an reasonable evaluation is to see **whether it can help the generator to explore better solutions more efficiently during training** (this is also what we only really need to care about). This is demonstrated in Figure 3 of our paper, the discriminator is very effective in helping the generator to find near-optimal solutions for training data.\n\nAn alternative evaluation is to show **the loss curve of the discriminator**, which is an indicator of the correlation between the discriminator's preference and true edit distance during training. However, we are **not allowed to post the any visualization results** during the rebuttal period, we will show it in the camera-ready version. \n\n\n---\n\n### **2. Evaluation of the training cost**\nAgain, please note that, the discriminator is **trained in an online manner** with the matching model using the latest sampled data, all performance results of our GEDRanker are trained with **the same number of epochs** as supervised learning methods. And the results demonstrate that our GEDRanker can achieve **similar performance as supervised learning method with the same number of epochs**. This is mainly due to the design of the preference-aware GAN, which is our core contribution. \n   \nBut we do have extra training cost per epoch, the extra training cost comes from **the sampling of solutions** and **the forward/backward pass of the discriminator**. But note that, the extra training cost of the discriminator **only occurs in the exploration phase**, and the discriminator is lighter than the generator (less number of parameters). Below is the training cost per epoch of exploration stage and exploitation stage for our unsupervised approach:\n\n| Dataset | Exploration Stage | Exploitation Stage |\n|---------|-------------------|--------------------|\n| AIDS    | 58s | 38s |\n| Linux   | 1m55s | 1m12s |\n| IMDB    | 3m11s | 2m07s |\n\nBelow is the training cost per epoch for supervised learning:\n| Dataset |  |\n|---------|--------------|\n| AIDS    | 15s | \n| Linux   | 28s |\n| IMDB    | 53s | \n\nDuring the exploration stage, the additional time cost arises from both the discriminator and the solution sampling. While the cost of solution sampling is unavoidable in unsupervised learning, it could be further reduced by efficient C++ implementation. For the discriminator, in our implementation we did not parallelize multiple forward passes (line 6 of Algorithm 3) due to hardware limitations. With a more powerful machine, this cost **could be further reduced through parallelization**, ideally cutting the discriminator-related time by half. \n\nDuring the exploitation stage, the addtional time cost arises from the solution sampling only.\n\nAnd note that the cost of the generator in unsupervised learning is the same as in supervised learning.\n\n---\n\n### **3. Evaluation of semi-supervised learning**\nRegarding the performance of semi-supervised case, we perform experiments by initializing 30% of total training graph pairs' best solutions using the ground-truth solutions. Below are the results of GEDRanker under semi-supervised setting:\n\n|Method| Dataset | MAE   | Accuracy    | ρ     | τ     | pk10  | pk20  |\n|----|---------|-------|--------|-------|-------|-------|-------|\n|Semi-supervised| AIDS    | 0.062 | 94.6%  | 0.989 | 0.978 | 99.2% | 99.2% |\n|| Linux   | 0.003 | 99.8%  | 0.999 | 0.998 | 100%  | 99.8% |\n|| IMDB    | 1.229 | 92.8%  | 0.965 | 0.955 | 96.3% | 96.9% |\n|Unsupervised|AIDS|0.088|92.6%|0.984|0.969|99.1%|99.1%|\n||Linux|0.01|99.5%|0.997|0.995|100%|99.8%|\n||IMDB|1.019|94%|0.999|0.97|96.1%|97%|\n\nFor the AIDS and Linux datasets, semi-supervised learning with 30% ground-truth slightly improves performance compared to unsupervised learning without any ground-truth. For IMDB dataset, the results are evaluated based on the **approximated** synethic ground-truth (might be larger than the exact ground-truth), therefore they only indicate the distance between the predicted GED and the **approximated** ground-truth GED (the predicted GED could be better than the approximated ground-truth GED).\n\n---\n\n### **4. Matching initalization**\nA good initialization of the current best solution can indeed reduce the number of epochs required for exploration. However, obtaining initial solutions for training data using ** GEDGW is computationally expensive**. As shown in Table 1, **GEDGW requires at least $2-6\\times$ longer inference time** compared to GEDRanker and DiffGED, where the latter two are evaluated with **10 forward passes** of the network. The gap becomes even larger during training, as GEDRanker and DiffGED **only require a single forward pass** of the matching network, making **GEDGW at least $20-60\\times$ slower**. And the number of training data is more than the number of testing data. Therefore, **using GEDGW as an initialization for training data is too costly in practice**. Furthermore, since GEDGW is NOT an exact algorithm and only provides **sub-optimal solutions**, initializing the best solution with GEDGW could **bias GEDRanker to explore within a sub-optimal region**. In our framework, we simply use randomly initialized solutions, and Figure 3 shows that even with random initialization, GEDRanker can still efficiently converge to near-optimal solutions.\n\n\n---\n\n### **5.Scalability**\n\nWe would like to clarify that, for IMDB-large dataset, we **don't know what the optimal GED is**, so we cannot know whether if both of GEDRanker and GEDGW are just close to the optimal results, hence resulting in close performance. But our method can find **a smaller GED and with a shorter time**. It is worth noting that GEDGW is an **optimization** algorithm, meaning its performance cannot be further improved easily **without extra time cost on the test instances** (and some of them can only output a fixed approximation). In contrast, neural methods **offer the potential for performance improvement** through increased training data, longer training epochs, or other techniques, these do not require extra time cost on the test instances. Therefore, comparison with the optimization algorithms is **NOT the primary focus** of this work.\n\nMore importantly, please note that **the scalability can be inherently influenced by the base model**, DiffGED. Therefore, we think a more appropriate way to demonstrate our method's effectiveness on large graphs is by evaluating **how it enhances the scalability of the base model in practice**. To this end, we train the base model (DiffGED) only on small real-world IMDB graph pairs where ground-truth labels are available. We then evaluate it on the IMDB-large graph pairs used in Table 5 to see the scalability of the original base model, and compared with our GEDRanker that enables the training of base model on large graph pairs without requiring ground-truth supervision. Following are the evaluation results:\n\n| Method     | Average GED | Time(s) |\n|------------|-------------|---------|\n| DiffGED    | 143.607      | 0.1911  |\n| GEDGW      | 140.278      | 0.4032  |\n| GEDRanker  | 140.138      | 0.1904  |\n\nUnder this practical setting, we can see that the supervised DiffGED underperforms the optimization algorithm GEDGW in terms of average GED. However, by leveraging our unsupervised training strategy (GEDRanker), DiffGED can be trained on large graphs and subsequently outperforms GEDGW in both average GED and running time."}, {"review_id": "GKW3EgMjyN", "reviewer": "Reviewer_RQNJ", "summary": "The authors propose GEDRanker, a novel unsupervised learning framework employing a GAN paradigm. GEDRanker consists of a matching-based GED solver, a preference-aware discriminator that provides a more interpretable and effective learning objective by evaluating and ranking node matching matrices based on their relative quality rather than relying on ground-truth supervision, and an effective training strategy that adaptively integrates exploitation and exploration during training.\n\nIn terms of performance, GEDRanker achieves near-optimal GED solution quality without supervision, consistently outperforming traditional approximate methods and closely matching supervised state-of-the-art methods in terms of accuracy and efficiency.", "questions": "1. The proposed method uses a preference-aware discriminator trained with a ranking loss. How stable is this training approach in practice, and how sensitive is the model's performance to the initialization of the discriminator? Were multiple runs with different seeds performed to evaluate training stability?\n\n2. Have you explored or considered alternative exploration-exploitation strategies beyond linearly annealing $\\lambda$ in your training objective? Not sure whether we should investigate adaptive strategies, e.g., reinforcement-learning-inspired adaptive exploration scheduling or dynamic $\\lambda$ adjustments based on current performance trends.\n\n3. How well does the discriminator generalize the learned preferences to completely unseen graph pairs that may differ structurally or in size distributions from those seen during training?", "limitations": "The authors have not explicitly addressed the limitations and potential negative societal impacts. The author should clearly discuss the known limitations regarding scalability or conditions under which GEDRanker may perform suboptimally.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper proposes the first unsupervised GAN-based approach for GED computation. Its unique use of a preference-aware discriminator provides an innovative direction compared to existing reinforcement-learning or supervised strategies.\n2. The presentation is clear and it has comprehensive motivation and background effectively position the paper within existing literature.\n3. The method demonstrates performance competitive with state-of-the-art supervised methods, emphasizing the value of unsupervised training and has strong experimental validation across widely-used benchmark datasets.\n\n\nWeaknesses:\n1. Hyperparameter sensitivity or case studies could be expanded to better demonstrate robustness and generalizability.\n2. Practical significance could be even better supported by demonstrating the method’s performance or limitations explicitly in large-scale or more varied real-world scenarios.", "was_revised": true, "final_justification": "Overall, the authors have addressed all major concerns with strong empirical results and thoughtful reasoning. The proposed method is novel, effective, and well-supported by the experimental results. I recommend accept.", "rebuttal": "Thanks for providing constructive comments. Below we address each point in detail.\n\n---\n\n### **Q1. Stability**\n\nWe would like to demonstrate the stability of our approach from several perspectives:\n\n- First, we have demonstrated the curve of the average edit path length of the best found solution during training in Figure 3, where we evaluated our GEDRanker with **an alternative ranking loss**, and we have discussed its stability in Section 5.3 (Ranking Loss). Overall, our proposed method is stable, and even with an alternative ranking loss, it can still achieve excellent performance. \n\n- To further demonstrate the stability of our approach, we train another supervised hybrid approach GEDGNN with our unsupervised approach:\n\n  >| Setting      | Dataset | MAE   | Accuracy   | ρ     | τ     | pk10  | pk20  |\n  >|--------------|---------|-------|-------|-------|-------|-------|-------|\n  >| Supervised   | AIDS    | 1.098 | 52.5% | 0.845 | 0.752 | 89.1% | 88.3% |\n  >|              | LINUX   | 0.094 | 96.6% | 0.979 | 0.969 | 98.9% | 99.3% |\n  >|              | IMDB    | 2.469 | 85.5% | 0.898 | 0.879 | 92.4% | 92.1% |\n  >| Unsupervised | AIDS    | 1.279 | 44.6% | 0.809 | 0.712 | 82.6% | 83.7% |\n  >|              | LINUX   | 0.078 | 96.3% | 0.982 | 0.971 | 98.2% | 98.7% |\n  >|              | IMDB    | 2.536 | 85.2% | 0.896 | 0.876 | 92.0% | 91.9% |\n  \n  The performance of GEDGNN trained with our unsupervised method is similar to that of GEDGNN trained under supervision, this again demonstrates the robustness of our approach. Here we don't need to show the performance of GEDIOT trained with our unsupervised framework, this is because GEDIOT adopts the same architecture as GEDGNN, with the only difference being an additional Sinkhorn layer applied to the output node matching matrix. To adapt GEDIOT to our unsupervised training framework, we simply replace the Sinkhorn layer with the Gumbel-Sinkhorn trick, this naturally becomes GEDGNN + our unsupervised method. \n\n- Regarding the initialization of the discriminator, for the results reported in the paper, we used the same seed as baseline methods **for a fair comparsion**. To demonstrate the stability, we randomly initialize the discriminator over 4 seeds, following are the results with mean&std:\n>| Dataset | MAE (±)       | ACC (±)         | ρ (±)          | τ (±)          | pk10 (±)        | pk20 (±)        |\n>|---------|---------------|-----------------|----------------|----------------|-----------------|-----------------|\n>| AIDS    | 0.089 ± 0.0026 | 92.39% ± 0.43%  | 0.984 ± 0.003  | 0.968 ± 0.0026 | 99.07% ± 0.064% | 99.11% ± 0.028% |\n>| Linux   | 0.010 ± 0.0015 | 99.49% ± 0.0173%| 0.9966 ± 0.0006| 0.9948 ± 0.0005| 99.98% ± 0.05%  | 99.79% ± 0.017% |\n>| IMDB    | 1.016 ± 0.0064 | 94.08% ± 0.2217%  | 0.996 ± 0.0022 | 0.969 ± 0.0010 | 96.15% ± 0.2646%  | 97.08% ± 0.2217%  |\n\n  Overall, the performance is stable.\n\n- Please also see the response to Q2, which can further demonstrate the stability of our approach.\n\n---\n\n### **Q2. Evaluation of $\\lambda$ schedule**\n\n- First, we would like to clarify that the primary focus of our work is to **efficiently explore high-quality solutions within a limited number of epochs**. If we can efficiently explore high quality solutions during the exploration stage, then we are able to shift toward exploitation using **a simple controllable decay**, **without the need for designing complex** exploration-exploitation balance mechanism and tunning.\n\n- To demonstrate this, we also experimented with cosine decay and step decay: (1) Cosine decay provides a similar smooth transition as linear decay. Compared to the linear scheduler, cosine decay allocates more weight to exploration during the early exploration stages, and reduces the exploration weight more aggressively in the later exploration stages. (2) Step decay keeps $\\lambda=1$ during the whole exploration phase then directly drops $\\lambda$ to 0 for exploitation. Below are the results of GEDRanker trained with cosine decay and step decay:\n\n  >| Decay Type   | Dataset | MAE   | Accuracy    | ρ     | τ     | pk10  | pk20  |\n  >|--------------|---------|-------|--------|-------|-------|-------|-------|\n  >| Linear       | AIDS    | 0.088 | 92.6%  | 0.984 | 0.969 | 99.1% | 99.1% |\n  >|              | Linux   | 0.010 | 99.5%  | 0.997 | 0.995 | 100%  | 99.8% |\n  >|              | IMDB    | 1.109 | 94%    | 0.999 | 0.97  | 96.1% | 97%   |\n  >| Cosine       | AIDS    | 0.130 | 90.2%  | 0.977 | 0.955 | 99.2% | 98.9% |\n  >|              | Linux   | 0.012 | 99.4%  | 0.996 | 0.994 | 99.8% | 99.7% |\n  >|              | IMDB    | 1.037 | 94.5%  | 0.979 | 0.97  | 97.2% | 97.8% |\n  >| Step         | AIDS    | 0.095 | 91.7%  | 0.981 | 0.963 | 99.0% | 99.2% |\n  >|              | Linux   | 0.013 | 99.4%  | 0.996 | 0.994 | 99.9% | 99.7% |\n  >|              | IMDB    | 1.187 | 93.4%  | 0.97  | 0.96  | 96.7% | 97.4% |\n\n  The results show that there's no significant performance gap between these 3 types of decay, this further demonstrates that our method is effective and robust, it does not require complex schedule design.\n\n- Regarding the RL-based adaptive exploration scheduling, it is not well-suited to our framework, as it can lead to **unstable fluctuations between exploration and exploitation**. Such instability may hinder the diffusion-based model from learning the correct denoising process, ultimately **breaking the denoising chain** during inference. Consequently, issues similar to those observed in GEDRanker (explore) in Appendix C.4 may arise (can find good solutions for training data, but performs poorly on unseen data). This would require a more sophisticated RL strategy specifically tailored to diffusion-based models, which is undesirable because our method is intended to **remain simple and easily adaptable to other supervised matching-based approaches** (this was demonstrated in the response to Q1). Our results demonstrate that a simple linear decay schedule is sufficient to achieve good performance.\n\n- Regarding the dynamic adjustments based on current performance trends, we have tried it, but found it **difficult to control**. For instance, when the model is able to discover only a few better solutions, it is unclear whether the exploration ratio should be increased or decreased. Reducing exploration may **trap the model in a locally sub-optimal region**, whereas increasing it may be also **harmful when the model does not need further exploration**. This again can **cause fluctuation between unstable exploration and exploitation**, and requires complex design and tunning.\n\n---\n\n### **Q3. Evaluation of the discriminator**\n\nNote that the discriminator is used **solely to guide the training of the matching model** and is **trained in an online manner** based on the distribution of latest solutions sampled from the matching model during exploration phase. It is **NOT used during inference**; therefore, it is **NOT expected to generalize to unseen graph pairs**. Moreover, the discriminator is **NOT trained to perfectly compute** the preference over all node matching matrices, it **only aims to provide a relatively good training signal** that guides the matching model within the current training epoch. Similar to those discriminators used in image generation, they are not intended to serve as a useful or generalizable image classifier after training. \n\nTherefore, we only need to evaluate **discriminator's online performance**, and the only thing we really need to care about is **whether the discriminator can help the generator to explore better solutions more efficiently during training**. This is demonstrated in Figure 3 of our paper, the discriminator is very effective in helping the generator to find near-optimal solutions for training data.\n\nAnother evaluation of the discriminator can be showing **the loss curve of the discriminator during training**, but we are **not allowed to post the any visualization results** during the rebuttal period, we will show it in the camera-ready version."}, {"review_id": "WB3bjCbLlE", "reviewer": "Reviewer_9zJG", "summary": "Recent neural frameworks have been shown to be effective at learning the Graph Edit Distance (GED). However, these supervised frameworks require ground-truth GED for training, which is NP-hard to compute. The paper proposes an unsupervised technique to overcome this issue. The backbone model is diffusion-based and trained to generate a node mapping matrix, from which an edit path can be generated. Instead of matching the ground-truth node mapping matrix (which is unavailable), the proposed method tries to match the best mapping matrix found so far, which is iteratively updated after being compared with the new matrix returned by the model. In addition, the method tries to reduce the resulted edit distance directly. In order to do this, the authors introduce a discriminator $D$ which takes as input the two graphs and a mapping matrix and output a score reversely proportional to the edit distance. The additional objective is to maximize $D(G_1, G_2, \\pi)$ where $\\pi$ is the mapping matrix returned by the model (and passed through a Gumbel-Sinkhorn operator for differentiability). The discriminator uses the Bayes Personalized Ranking loss to better enforce the ordering of the edit paths, i.e. a longer edit path will have a lower score. Overall, I have enjoyed reading this paper.", "questions": "This paper is extremely well-written and I enjoyed reading it! Only major concern is W1 in weaknesses. A few more questions are as follows:\n\n- In Equation 4, how is the cost function $c(\\cdot)$ calculated? Is it based on the procedure of Edit Path Generation written in section 3.1? This should be specified in the paper. \n- How compatible is your method with other hybrid approaches besides DiffGED? \n- In section C.1 in the appendix, how well is your method performing on \\textbf{large}, unseen graph pairs, in comparison to other baselines? In other words, how is generalizability of the proposed method affected by the graph size? \n- Have you tried other scheduler for the dynamical decrease of $\\lambda$ other than the linear scheduler? \n- A few typos: sapce (line 247),  categorizebaseline (line 255).", "limitations": "They have adequately addressed it.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The paper touches upon an important and relatively underexplored problem: supervised methods for learning GED require ground-truth labels that are NP-hard to compute. \n\n- The paper proposes a novel solution: encouraging the model to progressively come up with better answers. In addition, the length of the edit path is reduced directly via a clever use of the Discriminator and the Gumbel-Sinkhorn trick to get around the indifferentiability caused by working in the discrete graph space. \n\n- A wide range of evaluation metrics are used and reported. \n\n**Weaknesses:**\n\n- W1: Datasets of larger graphs (e.g. the OGB datasets) should be used for evaluation. This is because the main motivation for the paper is the NP-hardness of computing the ground-truth GED, which becomes costly for larger graphs. For IMDB-Large, the method returns a very high edit path (in absolute terms), which is undesirable. This is acknowledged in the Limitations section. \n\n- W2: The regression-based neural frameworks (SimGNN and its successors) should also be included as baselines. There can be applications in which only the numerical GED value is important.", "was_revised": true, "final_justification": "The rebuttal has addressed the comments with new experiments.", "rebuttal": "Thanks for enjoying reading our paper XD! Below we address each point in detail.\n\n---\n\n### **W1. Scalability**\n\nWe would like to clarify that, for IMDB-large dataset, the founded average GED = 140.138 is **NOT necessarly high** for large graphs (e.g., the range of GED for a pair of graphs with 50 nodes is [0,50*49/2+50=1275]), we just **don't know how far it is from the actual optimal GED**. But comparing with the traditional methods, our method can find **a smaller GED and with a shorter time**. And IMDB-large is sufficiently large for GED computation compared to other widely-used GED datasets, as traditional exact algorithms could take $10^2$ seconds even just on a single graph pair of 30 nodes.\n\nPlease also note that the scalability can be **inherently influenced by the base model**, DiffGED. Therefore, we think a more appropriate way to demonstrate our method's effectiveness on large graphs is by evaluating **how it enhances the scalability of the base model in practice**. To this end, we train the base model (DiffGED) only on small real-world IMDB graph pairs where ground-truth labels are available. We then evaluate it on the IMDB-large graph pairs used in Table 5 to see the scalability of the original base model, and compared with our GEDRanker that enables the training of base model on large graph pairs without requiring ground-truth supervision. Following are the evaluation results:\n\n| Method     | Average GED | Time(s) |\n|------------|-------------|---------|\n| DiffGED    | 143.607      | 0.1911  |\n| GEDGW      | 140.278      | 0.4032  |\n| GEDRanker  | 140.138      | 0.1904  |\n\nUnder this practical setting, we can see that the supervised DiffGED underperforms the optimization algorithm GEDGW in terms of average GED. However, by leveraging our unsupervised training strategy (GEDRanker), DiffGED can be trained on large graphs and subsequently outperforms GEDGW in both average GED and running time. It is worth noting that GEDGW is an **optimization algorithm**, meaning its performance cannot be further improved easily **without extra time cost on the test instances** (and some of them can only output a fixed approximation). In contrast, neural methods **offer the potential for performance improvement** through increased training data, longer training epochs, or other techniques, these do not require extra time cost on the test instances. Therefore, comparison with the optimization algorithms is **NOT the primary focus** of this work.\n\n---\n\n### **W2. Regression-based baselines**\n\nRegression-based neural frameworks are **NOT the focus of our work**, as **their objective is NOT to minimize the edit cost** (their ground-truth labels are the GED scores and they make continuous value prediction). While they may achieve very low MAE by making continuous number prediction, their accuracy can be very poor and they can make **infeasible predictions** (e.g., the predicted GED < the actual GED). But we can include them as interesting baselines.\n\n---\n\n### **Q1. Cost function**\n\nYes, the cost function is computed based on the lenght of the founded edit path, we will specify it in the paper.\n\n---\n\n### **Q2. Integration with other hybrid approaches**\n\nWe choose DiffGED as our base model, as it significantly outperforms all other hybrid approaches in terms of both effectiveness and efficiency. However, our method is **NOT limited to DiffGED** and can be **easily integrated with other hybrid matching-based frameworks**. For example, the following results show the performance of GEDGNN when trained using our unsupervised method:\n\n| Setting      | Dataset | MAE   | Accuracy   | ρ     | τ     | pk10  | pk20  |\n|--------------|---------|-------|-------|-------|-------|-------|-------|\n| Supervised   | AIDS    | 1.098 | 52.5% | 0.845 | 0.752 | 89.1% | 88.3% |\n|              | LINUX   | 0.094 | 96.6% | 0.979 | 0.969 | 98.9% | 99.3% |\n|              | IMDB    | 2.469 | 85.5% | 0.898 | 0.879 | 92.4% | 92.1% |\n| Unsupervised | AIDS    | 1.279 | 44.6% | 0.809 | 0.712 | 82.6% | 83.7% |\n|              | LINUX   | 0.078 | 96.3% | 0.982 | 0.971 | 98.2% | 98.7% |\n|              | IMDB    | 2.536 | 85.2% | 0.896 | 0.876 | 92.0% | 91.9% |\n\nThe performance of GEDGNN trained with our unsupervised method is similar to that of GEDGNN trained under supervision, which demonstrates the effectiveness of our apporach. \n    \nHere we don't need to show the performance of GEDIOT trained with our unsupervised framework, this is because GEDIOT adopts the same architecture as GEDGNN, with the only difference being an additional Sinkhorn layer applied to the output node matching matrix. To adapt GEDIOT to our unsupervised training framework, we simply replace the Sinkhorn layer with the Gumbel-Sinkhorn trick, this naturally becomes GEDGNN + our unsupervised method. \n\n---\n\n### **Q3. Generalization ability w.r.t. graph size**\n\nTo better demonstrate the generalizability of our method **with respect to the graph size**, we follow the same setting as described in the original paper of DiffGED. Specifically, instead of training each method on a combination of real small graph pairs and synthetic large graph pairs from IMDB, we train each method on real small graph pairs only, then evaluate on the whole IMDB dataset that contains a combination of small real graph pairs and large synthetic graph pairs:\n\n| Method     | MAE   | Accuracy   | ρ     | τ     | pk10  | pk20  |\n|------------|-------|-------|-------|-------|-------|-------|\n| GEDGNN     | 7.943 | 77.1% | 0.844 | 0.815 | 88.2% | 87.6% |\n| GEDIOT     | 7.761 | 76.8% | 0.860 | 0.827 | 90.5% | 89.9% |\n| DiffGED    | 5.789 | 83.0% | 0.892 | 0.874 | 90.1% | 90.8% |\n| GEDRanker  | 8.564 | 81.0% | 0.860 | 0.844 | 87.6% | 88.3% |\n\nPlease be aware of that, these results are evaluated based on the **approximated** synethic ground-truth (might be larger than the exact ground-truth), therefore they only indicate the **distance between the predicted GED and the approximated ground-truth GED** (the predicted GED could be better than the approximated ground-truth GED).\n\nMoreover, the overall generalization ability is not only affected by our unsupervised training method, but can also be **affected by the generalization ability of the base model**.\n\nAdditionally, our GEDRanker **faces a more challenging setting** compared to baseline methods: our GEDRanker **not only need to generalize** to large unseen graphs, but also need to be **trained without any ground-truth supervision on small graphs**, where baseline models can be trained with ground-truth supervision on small graphs. Under this more challenging setting, GEDRanker can still achieve similar generalization ability as DiffGED, which further demonstrates the effectiveness of our approach.\n\n---\n\n### **Q4. Evaluation of $\\lambda$ schedule**\n\nFirst, we would like to clarify that the primary focus of our work is to **efficiently explore high-quality solutions within a limited number of epochs**. If we can efficiently explore high quality solutions during the exploration stage, then we are able to shift toward exploitation using a **simple controllable decay**, **without the need** for designing complex exploration-exploitation balance mechanism and tunning. \n\nTo demonstrate this, we also experimented with cosine decay and step decay: (1) Cosine decay provides a similar smooth transition as linear decay. Compared to the linear scheduler, cosine decay allocates more weight to exploration during the early exploration stages, and reduces the exploration weight more aggressively in the later exploration stages. (2) Step decay keeps $\\lambda=1$ during the whole exploration phase then directly drops $\\lambda$ to 0 for exploitation. Below are the results of GEDRanker trained with cosine decay and step decay:\n\n| Decay Type   | Dataset | MAE   | Accuracy    | ρ     | τ     | pk10  | pk20  |\n|--------------|---------|-------|--------|-------|-------|-------|-------|\n| Linear       | AIDS    | 0.088 | 92.6%  | 0.984 | 0.969 | 99.1% | 99.1% |\n|              | Linux   | 0.010 | 99.5%  | 0.997 | 0.995 | 100%  | 99.8% |\n|              | IMDB    | 1.109 | 94%    | 0.999 | 0.97  | 96.1% | 97%   |\n| Cosine       | AIDS    | 0.130 | 90.2%  | 0.977 | 0.955 | 99.2% | 98.9% |\n|              | Linux   | 0.012 | 99.4%  | 0.996 | 0.994 | 99.8% | 99.7% |\n|              | IMDB    | 1.037 | 94.5%  | 0.979 | 0.97  | 97.2% | 97.8% |\n| Step         | AIDS    | 0.095 | 91.7%  | 0.981 | 0.963 | 99.0% | 99.2% |\n|              | Linux   | 0.013 | 99.4%  | 0.996 | 0.994 | 99.9% | 99.7% |\n|              | IMDB    | 1.187 | 93.4%  | 0.97  | 0.96  | 96.7% | 97.4% |\n\nThe results show that there's no significant performance gap between these 3 types of decay, this further demonstrates that our method is effective and robust, it does not require complex schedule design."}, {"review_id": "ralnfgJPkR", "reviewer": "Reviewer_Y63G", "summary": "The paper provides a novel method to approximate the graph edit distance (GED), by investigating an unsupervised framework thanks to a reformulation using a generative adversarial network (GAN).", "questions": "no further questions.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The major strength of this work is that it seeks to provide an unsupervised framework for learning the GED.\n\nThe paper suffers from several major weaknesses.\n\nThe authors pretend that this is the first unsupervised learning framework for GED computation, as given for instance in the subsection “Contributions” at the end of Section 1. However, this is not correct, since there are many other unsupervised learning methods for GED computation. See for instance:\n- Bommakanti, A., Vonteri, H. R., Ranu, S., & Karras, P. (2024). EUGENE: Explainable Unsupervised Approximation of Graph Edit Distance. arXiv preprint arXiv:2402.05885.\nThat paper also provides several references to other works that provide unsupervised methods, such as F1 (Lerouge et al., 2017), ADJ-IP (Justice & Hero, 2006), COMPACT-MIP (Blumenthal & Gamper, 2020), and BRANCH-TIGHT (Blumenthal & Gamper, 2018).\nOverall, the paper is not well positioned within the literature of related work, and thus the experiments are missing a comparative analysis with such related work.\n\nThe main contribution of the paper seems to be the usage of the Gumbel-Sinkhorn method, as opposed to REINFORCE. While this seems to be sound, the authors need to highlight this contribution within the appropriate literature. It seems that the authors are not aware of the broad work on the usage of the Gumbel-Sinkhorn method to compute the GED. See for instance:\n- Jain, E., Roy, I., Meher, S., Chakrabarti, S., & De, A. (2024). Graph edit distance with general costs using neural set divergence. Advances in Neural Information Processing Systems, 37, 73399-73438.\n- Wang, J., Zhu, H., Xie, H., Wang, F. L., Xu, X., & Wang, Y. (2024). Graph Similarity Computation via Interpretable Neural Node Alignment. arXiv preprint arXiv:2412.12185.\n- Pei, M., Yu, J., Chen, C., Wang, H., Wang, X., & Zhang, Y. (2025). IGFM: An Enhanced Graph Similarity Computation Method with Fine-Grained Analysis. Data Science and Engineering, 1-15.\n- Roy, I., Jain, E., Meher, S., Chakrabarti, S., & De, A. (2024). Graph Edit Distance with General Costs Using Neural Set Divergence. In The Third Learning on Graphs Conference. https://openreview.net/pdf?id=rpF6eqVkPu\n\nThe paper is difficult to read and understand because some parts are overstressed and others are not described enough. \n\nIt feels weird how the problem is presented using REINFORCE from a 1992 paper, before seeking to overcome the limitations of that work that is more than 30 years old.\n\nThe description of the supervised diffusion-based node matching model [13] in Section 3.2 is not justified explicitly. One can wonder about the interest of that model within the proposed method. Besides the caption of Figure 2 that provides little insight, the main text does not clearly describe the integration of that diffusion-based model.\n\nAt the end, the proposed method relies mainly on the work [13], which is a preprint in arXiv that seems not to be peer-reviewed (to the best of our knowledge).\n\nOn the quality of writing, there is room for improvement in order to make the paper more accessible to readers. For instance, GAN is never defined in the paper, although it is central to this work.", "was_revised": true, "final_justification": "I thank the authors for the clarifications on all the major issues raised in my review, which were mainly related to the positioning of this work in the literature. Considering the overall reviews and the rebuttal discussions, I have accordingly raised my score.", "rebuttal": "We would like to clarify the following points.\n\n---\n\n### **W1. Clarification on EUGENE and optimization-based methods**\n\nEUGENE is actually an **optimization-based method** (similar in nature to GEDGW), it is **NOT a neural unsupervised learning method** (it does not involve any neural network/deep learning). Moreover, the so-called \"unsupervised methods\" referenced by EUGENE are also **optimization methods** (e.g., linear programming), **NOT neural unsupervised methods**. \n\nThe key distinction between optimization and neural unsupervised methods lies in generalizability: **optimization methods do not involve neural networks**, and they **cannot be trained on training graphs**, instead, their **optimization process must be repeated for each test graph pair** (of course in this case, they could in some sense be called ''unsupervised''), making them non-generalizable and time consuming. In contrast, neural unsupervised methods, once trained, can be **directly applied to unseen test graph pairs via neural networks without further optimization**. And our framework is the first method that **enables the unsupervised training of supervised neural methods**. Moreover, we have already compared and outperformed the latest SOTA optimization algorithm, GEDGW, recently accepted by SIGMOD2025. \n\n---\n\n### **W2. Clarification on the main contribution**\n\n**Gumbel-Sinkhorn is NOT our main contribution**, we have clearly stated that **the main contribution of our work is the preference-aware GAN-based training framework** (line41-49). Gumbel-Sinkhorn only serves as a tool to enable smooth gradient flow between the generator and the discriminator. \n\nAlso, please note that the objective of our task is to **find the actual edit path that minimizes the total cost** (discrete value), where the ground-truth labels are the edit paths/matching matrices in the supervised case. In contrast, for the papers you referenced, they focus on **formulating GED as a regression problem** (predicts a continuous value), where their ground-truth labels are the GED scores. The nature of the objectives/outputs is **completely different**. \n\nWhile regression-based approach may achieve very low MAE by making continuous number prediction, **their accuracy can be very poor and they can make infeasible predictions** (e.g., the predicted GED < the actual GED). Therefore, regression-based approach is **NOT the focus of our work**.\n\n---\n\n### **W3. Clarification on REINFORCE**\n\nAlthough REINFOCE is introduced in 1992, it is still the most well-known and widely used fundamental unsupervised RL method, particularly in lots of unsupervised frameworks for other NP-hard problems (even in LLM+RL). For example:\n\n    André Hottung, Yeong-Dae Kwon, Kevin Tierney: Efficient Active Search for Combinatorial Optimization Problems. ICLR 2022\n    Qiu, R., Sun, Z., & Yang, Y. (2022). Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35, 25531-25546.\n    Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., & Li, F. (2024, March). Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 18, pp. 20284-20292).\n    Back to Basics: Revisiting REINFORCE-Style Optimization for Learning from Human Feedback in LLMs (Ahmadian et al., ACL 2024).\n\n---\n\n### **W4. Clarification on the integration with the diffusion-based model**\n\nThe majority of Section 4 focuses on replacing the supervised training strategy of the diffusion-based model described in Section 3.2 with our unsupervised training strategy (line 142-148). In particular, Section 4.1 and Algorithm 3 provide all the necessary details for integrating GEDRanker with the diffusion-based model (see line 3 of Algorithm 3). Figure 2 illustrates the complete unsupervised training pipeline, the only part it needs to be integrated with the diffusion-based model is the forward process $q(\\pi^t|\\pi^0)$. \n\nAlso, please note that, our framework is not specifically designed for the diffusion-based model only. We select the diffusion-based model as our base model due to its superior performance and efficiency over all other existing hybrid methods, our framework can be easily adopted to future SOTA matching-based methods. To demonstrate this, we train an older matching-based approach GEDGNN with our unsupervised approach:\n| Setting      | Dataset | MAE   | Accuracy   | ρ     | τ     | pk10  | pk20  |\n|--------------|---------|-------|-------|-------|-------|-------|-------|\n| Supervised   | AIDS    | 1.098 | 52.5% | 0.845 | 0.752 | 89.1% | 88.3% |\n|              | LINUX   | 0.094 | 96.6% | 0.979 | 0.969 | 98.9% | 99.3% |\n|              | IMDB    | 2.469 | 85.5% | 0.898 | 0.879 | 92.4% | 92.1% |\n| Unsupervised | AIDS    | 1.279 | 44.6% | 0.809 | 0.712 | 82.6% | 83.7% |\n|              | LINUX   | 0.078 | 96.3% | 0.982 | 0.971 | 98.2% | 98.7% |\n|              | IMDB    | 2.536 | 85.2% | 0.896 | 0.876 | 92.0% | 91.9% |\n\nThe performance of GEDGNN trained with our unsupervised method is similar to that of GEDGNN trained under supervision, which demonstrates the compatibility and the effectiveness of our apporach. \n\n---\n\n### **W5. Clarification on DiffGED**\n\nWe have provided the implementations of all baseline methods including DiffGED. Through our implementation and experimental results, we demonstrate that DiffGED is indeed highly effective and efficient, which justifies our choice of it as the base model.\n\n---\n\n### **W6. Clarification on GAN**\n\nGAN is a well-known framework. We have already provided an overview of its core idea in the context of our work in Section 4.1. (GAN-based Training Objective line180-184)"}]

Author rebuttal:

Meta-review: This paper presents an unsupervised framework for graph node matching and Graph Edit Distance (GED) estimation, designed to avoid reliance on ground-truth GED labels, which are expensive to collect. The model uses a diffusion-based backbone to generate node mapping matrices and derives edit paths from them. Instead of supervised matching, training proceeds by engaging a preference-aware discriminator. The discriminator evaluates mappings, ensuring that shorter edit paths are favored over longer ones. This GAN-inspired setup provides a more interpretable objective and balances exploration with exploitation during training. Experimental results show that GEDRanker achieves near-optimal GED solutions without supervision, outperforming traditional approximate methods and approaching the accuracy and efficiency of supervised state-of-the-art models.

This is a useful and competent submission that is certainly a poster accept.  The novelty of unsupervised GED is somewhat overstated. Y63G has suggested a better bibliography against which to position the work.  Apart from those works, the paper itself states that supervised diffusion-based node matching models [11] already exist, although the removal of supervision from this family of approaches is a worthy contribution.

Otherwise, reviewers had fairly routine questions about notation, definitions, and experimental details, which were largely adequately addressed during rebuttal.

A couple of additional writing issues:

L153 Given there is no need for supervision, it is not immediately clear how the training graph pairs are collected or sampled.  Presumably a training graph pair is offered as-is, without any GED value or correspondence as supervision.

L166 caption "rank the preference over" is confusing language.  Reword.

Since the title says "preference-aware"  and the abstract says "without the need for ground-truth labels", the abstract itself should clearly state that no supervision is needed, and what data is needed from outside during training, vs. what can be generated internally.
Decision: Accept (poster)