Graph Edit Distance with General Costs Using Neural Set Divergence
Authors: Eeshaan Jain
Indradyumna Roy
Saswat Meher
Soumen Chakrabarti
Abir De
Venue: NeurIPS 2024 poster (2024)
Keywords: graph neural network
graph edit distance
Primary area: graph_neural_networks
TL;DR: Neural graph edit distance network with uniform and non-uniform costs

Abstract: Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs in terms of the minimum-cost edit sequence, which transforms one graph to the other.
GED is related to other notions of graph similarity, such as graph and subgraph isomorphism, maximum common subgraph, etc. However, the computation of exact GED is NP-Hard, which has recently motivated the design of neural models for GED estimation.
However, they do not explicitly account for edit operations with different costs. In response, we propose $\texttt{GraphEdX}$, a neural GED estimator that can work with general costs specified for the four edit operations, viz., edge deletion, edge addition, node deletion, and node addition.
We first present GED as a quadratic assignment problem (QAP) that incorporates these four costs.
Then, we represent each graph as a set of node and edge embeddings and use them to design a family of neural set divergence surrogates. We replace the QAP terms corresponding to each operation with their surrogates. 
Computing such neural set divergence requires aligning nodes and edges of the two graphs.
We learn these alignments using a Gumbel-Sinkhorn permutation generator, additionally ensuring that the node and edge alignments are consistent with each other. Moreover, these alignments are cognizant of both the presence and absence of edges between node pairs.
Through extensive experiments on several datasets, along with a variety of edit cost settings, we show that $\texttt{GraphEdX}$ consistently outperforms state-of-the-art methods and heuristics in terms of prediction error. The code is available at https://github.com/structlearning/GraphEdX.

Graph Edit Distance with General Costs Using Neural Set Divergence
Eeshaan Jain"t
Indradyumna Roy*i
Saswat Meher!
Soumen Chakrabarti!
Abir De
TPPI. *IIT Bombay
eeshaan. jain@epfl.iiinnncc.ccmm. (saswatmeher soumen, , indraroy15 1 actr::/ss.sarrrce.e..eeeaeee iitb ac
Abstract
Graph Edit Distance (GED) measures the (dis-)similarity between two given graphs, in terms of the minimum-cov edit sequence that transforms one graph to the other. However, the exact computation of GED is NP-Hard, which has recently motivated the design neural methods for GED estimation. However, they do not explicitly account for edit operations with different costs. In response, we propose GRAPHEDX, a neural GED estimator that can work with general costs specified for the four edit operations, viz., edge deletion, edge addition, node deletion and node addition. We first present GED as a quadratic assignment problem (QAP) that incorporates these four costs. Then, and edge embeddings and use them to design a family of neural set divergence surrogates. We replace the QAP terms corresponding each operation with their surrogates. Computing such neural set divergence require aligning nodes and edges of the two graphs. We learn these alignments using Gumbel-SSnkine Sinkhorn permutation generator, additionally ensuring that the node and edge alignments are consistent with each other. Moreover, these alignments are cognizant of both the presence and absence of edges between node pairs. Experiments on several datasets, under a variety edit cost settings, show that GRAPHEDX consistently outperforms state-of-the-ee methods and heuristics in terms of prediction error. The code available at h/tpt::///tttbbb// www.sstructlearnnnngg/ooooooe/ee GrappiEE.............
represent each graph
of node
Introduction
The Graph Edit Distance (GED) between a source graph, G. and a target graph, G", quantifies the minimum cost required to transform G into graph isomorphic G'. This transformation involves sequence of edit operations, which can include node and edge insertions, deletions and substitutions. Each type of edit operation may incur different and distinctive cost, allowing the GED framework to incorporate domain- domain-specific knowledge. Its flexibility has led to the widespread use of GED for comparing graphs across diverse applications including graph retrieval [5, 6]. pattern recognition [47], image and video indexing [51, 49] and chemoinformatics [21]. Because costs for addition and deletion may differ, GED not necessarily symmetric, i.e., GED G') * GED G). This flexibility allows GED to model a variety of graph comparison scenarios, such as finding the Maximum Common Subgraph [43] and checking for Subgraph Isomorphism [13]. In general, it is hard to even approximate GED [32]. Recent work [5, 6, 19, 56, 39] has leveraged graph neural networks (GNNs) to build neural models for GED computation, but many these approaches cannot account for edit operations with different costs. Moreover, several approaches [40, I, 56, 6] cast GED as the Euclidean distance between graph embeddings, leading to models that are overly attuned to cost-invariant edit sequences.
'Equal contribution. Eeshaan Jain this work while at Bombay.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

1.1
Present work
We propose a novel neural model for computing GED, designed to explicitly incorporate the various costs of edit operations. Our contributions are detailed as follows.
Neural set divergence surrogates for GED We formulate GED under general (non-uniform) cost as a quadratic assignment problem (QAP) with four asymmetric distance terms representing edge deletion, edge addition, node deletion and node addition. The edge-edit operations involve quadratic dependencies on a node alignment plan a proposed mapping of nodes from the source graph to the target graph. To avoid the the complexity of QAP [45], we design a family of differentiable set divergence surrogates, which can replace the QAP objective with more benign one. In this approach, each graph is represented as a set of embeddings of nodes and node-pairs (edges or non-edges). We replace the original QAP distance terms with their corresponding set divergences, and obtain the node alignment from differentiable alignment generator modeled using a Gumbel-SSnkhorr network. This network produces soft node permutation matrix based on contextual node embeddings from the graph pairs, enabling the computation of the overall set divergence a differentiable manner, which facilitates end-to-end training. Our proposed model relies on late interaction, where the interactions between the graph pairs occur only at the final layer, rather than during the embedding computation in the GNN. This supports the indexing of embedding vectors, thereby facilitating efficient retrieval through LSH [25, 24, 12]. inverted index [20]. graph based ANN [34, 37] etc.
Learning all node-pair representations The optimal sequence of edits in GED is heavily influenced by the global structure of the graphs. A perturbation in one part of the graph can have cascading effects, necessitating edits in distant areas. To capture this sensitivity to structural changes, we associate both edges as well as non-edges with suitable expressive embeddings that capture the essence of subgraphs surrounding them. Note that the embeddings for non-edges are never explicitly computed during GNN message-passing operations. They are computed only once, after the GNN has completed its usual message-passing through existing edges, thereby minimizing additional computational overhead.
Node-edge consistent alignment To ensure edge-consistency in the learned node alignment map, we explicitly compute the node-pair alignment map from the node alignment map and then utilize this derived map to compute collective edge deletion and addition costs. More precisely, if (u, v) E G and (u', e') E G' are matched, then the nodes and v are constrained to match with u' and of (or, of and u') respectively. We call our neural framework as GRAPHEDX.
Our experiments across several real datasets show that (1) GRAPHEDXX outperforms several state-of- the-art methods including those that use early interaction; (2) the performance of current state-of- the-art methods improves significantly when their proposed distance measures are adjusted reflect GED-specific distances, as in our approach.
2 Related work
Heuristics for Graph Edit Distance GED was first introduced in [46]. Bunke and Allermann [14] used it as a tool for non exact graph matching. Later on, [13] connected GED with maximum common subgraph estimation. Blumenthal [7] provide an excellent survey. As they suggest, combinatorial heuristics to solve GED predominantly follows three approaches: (1) Linear sum assignment problem with error- correccorr,,,on, which include [27, 41, 53, 55] (2) Linear programming. which predominantly uses standard tools like Gurobi, (3) Local search [42]. However, they can be extremely time consuming, especially for a large number of graph pairs. Among them Zheng et al. [55] operate in our problem setting, where the cost of edits are different across the edit operations, but for the same edit operation, the cost is same across node or node pairs.
Optimal Transport In our work, we utilize Graph Neural Networks (GNNs) to represent each graph as a set of node embeddings. This transforms the inherent Quadratic Assignment Problem (QAP) of graph matching into Linear Sum Assignment Problem (LSAP) on the sets of node embeddings. Essentially, this requires solving an optimal transport problem in the node embedding space. The use of neural surrogates for optimal transport was first proposed by Cuturi [16], who introduced entropy regularization to make the optimal transport objective strictly convex and utilized Sinkhorn iterations [50] to obtain the transport plan. Subsequently, Mena et al. [35] proposed the neural Gumbel Sinkhorn network as a continuous and differentiable surrogate of a permutation matrix, which we incorporate into our model.
2

---

In various generative modeling applications, optimal transport costs are used as loss functions, such as in Wasserstein GANs [1, 3]. Computing the optimal transport plan is a significant challenge. with approaches leveraging the primal formulation [52, 33], the dual formulation with entropy regularization [17, 48, 22], or Input Convex Neural Networks (ICNNs) [2].
Neural graph similarity computation Most earlier works on neural graph similarity computation have focused on training with GED values as ground truth [5, 19, 40, 56, 39, 54, 311, while some have used MCS as the similarity measure [6. 5]. Current neural models for GED approximation primarily follow two approaches. The first approach uses a trainable nonlinear function applied to graph embeddings to compute GED [5, 39, 6, 56, 54, 19]. The second approach calculates GED based on the Euclidean distance in the embedding space [31, 40).
Among these models, GOTSIM [19] focuses solely on node insertion and deletion, and computes node alignment using a combinatorial routine that is decoupled from end-to-end training. However, their network struggles with training efficiency due to the operations on discrete values, which are not amenable to backpropagation. With the exception of GREED [40] and Graph Embedding Network (GEN) [31], most methods use early interaction or nonlinear scoring functions, limiting their adaptability efficient indexing and retrieval pipelines.
3 Problem setup
The source graph is denoted by G = (V, E) and the target graph by G² (V', Both graphs are undirected and are padded with isolated nodes to equalize the number of nodes to N. The adjacency matrices for G and G" after padding are A' E [0,
Notation
N*N N (Note that we will use M not M', for the transpose of matrix M.) The sets of padded nodes in G and G' are denoted by PaddedNodesq and PaddedNodes respectively. We construct 7j E {0, 1), where nj n7i4| = 0 PaddedNNodes and otherwise (same for G'). The embedding of node u E V computed at propagation layer k by the GNN, is represented as æ (u). Edit operations, denoted by edit, belong to one of four types, viz., (i) node deletion, (ii) node addition, (iii) edge deletion, (iv) edge addition. Each operation edit is assigned a cost cost (edit). The node and node-pair alignment maps are described using (hard) permutation matrices P E 10,1)NXA and S E (0. (()))(()) respectively. Given that the graphs are undirected, node-pair alignment need only be specified across at most (2) pairs. When hard permutation matrix is relaxed to a coubly-stochasee matrix. We use P and S to refer to both hard and soft permutationns, depending on the context. We denote PN as the set of all hard permutation matrices of dimension N; [N] as {l..... N. and || || II
matrix, we call it a soft permutation
describe En,, A [u, w]]. For two binary variables c1, E {0, 13, we denote Jc1, 02) as (c) XOR
c2), i.e., ((1 c102 + (1 - (1 - -2)-
Graph edit distance with general cost We define an edit path as a sequence of edit operations fedita, edit,,,..J :: and (G, G') as the set of all possible edit paths that transform the source graph G into a graph isomorphic to the target graph G¹. Given O G') and the cost associated with each operation edit, the GED between G and G' is the minimum collective cost across all edit paths in (G, G'). Formally, we write [14, 7]:
GED(G, =
min editt., (EOGG))))) Ele[lo]) cost (edit))..
In this work, we assume fixed cost for each of the four types of edit operations. Specifically, we use a a 6 and h to represent the costs for edge deletion, edge addition, node deletion, and node addition, respectively. These costs are not necessarily uniform, in contrast to the assumptions made in previous works [5, 31, 56, 39]. Additional discussion on GED with node substitution in presence of labels can be found in Appendix B.
Problem statement Our objective is to design neural architecture for predicting GED under a general cost framework, where the edit costs n a 1 and 1 are not necessarily the same. During the learning stage, these four costs specified, and remain fixed across all training instances D = ((G,, G GED [ Note that the edit paths are not supervised. Later, given a test instance G, G", assuming the same four costs, the trained system has to predict GED(G,
4 Proposed approach
In this section, we first present an alternative formulation of GED as described in Eq. (1), where the edit paths are induced by node alignment maps. Then, we adapt this formulation to develop
3

---

GRAPHEDX, a neural set distance surrogate, amenable to end-to-ena training. Finally, we present the network architecture of GRAPHEDX.
4.1 GED computation using node alignment map
Given the padded graph pair G and G', deleting node u V can be viewed as aligning node u with some padded node v' E PaddedNodescy. Similarly, adding new node u' to G can be seen as aligning some padded node u E PaddedNodessc with node u' E V Likewise, adding an edge to G corresponds to aligning non-edge (u, v) & E' with an edge (u', E G'. Conversely, deleting an edge G corresponds to aligning an edge (u, v) E G with a non-edge (u', ,'), $ G'.
Therefore, GED(G, G') can be defined in terms of node alignment map. Let II represent the set of all node alignment maps и [N] + [A]] from V to V'. Recall that nG [u] 0 u e PaddedNodese and 1 otherwise.
E aa [((u,)) EA ( (())) & E + a I[(u,,, v) EA (T(U), E EFI)
min relly
2
+
( (1 no (T))) + b. (1- (o-n nor [r(I)))
In the above expression, the first sum iterates over all pairs of (u,v) v) [N] x [N] and the second sum iterates over u E [N]. Because both graphs are undirected, the fraction 1/2 accounts for double counting of the edges. The first and second terms quantify the cost of deleting and adding the edge
(u, v) from and to G. respectively. The third and the fourth terms evaluate the cost of deleting and adding node u from and G, respectively.
GED as a Quadratic Assignment Problem In its current form, Eq. (2) cannot be immediately adapted to differentiable surrogate. To circumvent this problem, we provide equivalent matricized form of Eq. (2), using a hard node permutation matrix P instead of the aligmment map æ. We compute the asymmetric distances between A and PA'PT and combine them with weights a and a Notably, ReLU (A PA'PT) [u, v) is non-zero the edge (u, v) E E is mapped to a non-edge (u', vd) E En with Plu, u'] = P ee u'] = 1, indicating deletion of the edge (u, v) from G. Similarly, ReLU (PA'P A) [u, u| becomes non-zero an edge (u, v) is added G. Therefore, for the edit operations involving edges, we have:
[[(u,)) v) E E' (T(U), (())) & = ReLU (A- PA'PT) [u,
(3)
(PA'PT A) [u. Similarly, we note that ReLU (Na(M) No (T())) > 0 if
[[(,,)) v) & (T((), E = ReLU ReLU
(4)
PaddedNodese and x(u) E PaddedNodesce, which allows us to compute the cost of deleting the node u from G. Similarly, we use ReLU (7or [T[)]] no [u]) to account for the addition of the node to G. Formally, we write:
nG[u] (1 No (=)) ReLU (Mc[u) no (m)))),
(5)
(1 - -o[[l) no [x(]] = ReLU [T()] - nalu)).
(6)
Using Eqs. (3)- we rewrite Eq. (2) as:
a 111 + す |ReLU (PA'PT - AlI
GED(G, G') = min PEPN 2
|eLLU (A-PA'P
11
+ 0 ||ReLU (NG Pno)) II1 + 6 |ReeLU (Pna- na]ln (7)
The first and the second term denote the collective costs of deletion and addition of edges, respectively. The third and the fourth terms present matricized representation of Eqs. (5)- (6). The above problem can be viewed as a quadratic assignment problem (QAP) on graphs, given that the hard node permutation matrix P has a quadratic involvement in the first two terms. Note that, in general, GED(G, G') + GED(G", G). However, the optimal edit paths for these two GED values, encoded by the respective node permutation matrices, are inverses of each other, as formally stated in the following proposition (proven in Appendix B).
Proposition 1 Given a fixed set of values b 1 a aa let P be an optimal node permutation matrix corresponding to GED (G. G'), computed using Eq. (7). Then, p' PP is an optimal node permutation corresponding to GED(G', G).
Connection to different notions of graph matching The above expression of GED can be used to represent various notions of graph matching and similarity measures by modifying the edit costs. These include graph isomorphism, subgraph isomorphism, and maximum common edge subgraph

---

Edlt, AddNode
Edity DelEdge +)
Edits Addbilp(e..
Edity (t.
Padding
R
X
MLP
X
MPNN
RIS: A (8)))
PP X
PERMNETT
MPNN
AddEap((s.))
G
MLP
X
Figure 1: Top: Example graphs G and G' are shown with color-coded nodes to indicate alignment corresponding the optimal edit path transforming G to G'. Bottom: GRAPHEDX's ' GED prediction pipeline. G and G' are independently encoded using MPNNo. and then padded with zero vectors to equalize sizes, resulting in contextual node representations X, X' E Nxd, For each node-pair, the corresponding embeddings and edge presence information are gathered and fed into MLP, to obtain R. R' E R (NN-N1)) -11/2/xx Simultaneously, X, X are fed into PERMNET to obtain the soft node alignment P (16. which constructs the node-pair alignment matrix S E N( N)N2)X(N11))2 as (((,,)) u); (u', v')]= = Plu, u') P(u, v'] + Plu, v/ P (w, u']. Finally, X, X,X' P are used to approxi- mate node insertion and deletion costs, while R, R', S are used to approximate edge insertion and deletion costs. The four costs are summed to give the final prediction GED,,, (G, G') (8).
detection. For example, by setting all costs to one, GED G') = minp \1l A PA'P 1| ng Pno III. which equals zero only when G and G" are isomorphic. Further discussion on this topic is provided in Appendix B.
4.2 GRAPHEDX model
Minimizing the objective in Eq. (7) is a challenging problem. In similar problems, recent methods have approximated the hard node permutation matrix P with a soft permutation matrix obtained using Sinkhorn iterations on neural cost matrix. However, the binary nature of the adjacency matrix and the pad indicator 77 still impede the flow of gradients during training. To tackle this problem, we make relaxations in two key places within each term in Eq. (7), leading to our proposed GRAPHEDX model.
(1) We replace the binary values in nG. nG. and A' with real values from node and node-pair embeddings: X Nxd and R E TR (DD) These embeddings are computed using GNN guided neural module EMBED, with parameter 0. Since the graphs are undirected, R gathers the embeddings of the unique node-pairs, resulting in (2) rows instead of N
(2) We substitute the hard node permutation matrix P with a soft alignment matrix, generated using differentiable alignment planner PERMNET & with parameter ø. Here, P is doubly stochastic matrix, with P(u, u'] indicating the "score" " or "probability"" of aligning u + u'. Additionally, we also compute the corresponding node-pai alignment matrix S.
Using these relaxations, approximate the four edit costs in Eq. (7) with four continuous set distance surrogate functions.
|ReLL (A PA'PTI II, A
RR R' S), |ReLU (PA'PT A) A (R, RS)')
||ReLU (NG Pro) Il, + (x, X' P): |[ReLU (PTо nc)ll + A X P). This gives us an approximated GED parameterized by and á.
(G, G¹) = a a (R, R' +)+a RR
(8)
+ A
+ P).
Note that since R and R' contain the embeddings of each mode-pair only once, there is need to multiply 1/2 in the first two terms, unlike Eq. (7). Next, we propose three types of neural surrogates approximate each of the four operations.
(1) ALIGNDIFF Given the node-pair embeddings R and R' for the graph pairs G and G', we apply the soft node-pair alignment S to R'. We then define the edge edits in terms of asymmetric
5

---

differences between R and SR' which serves as replacement for the corresponding terms in
Eq. (7). We write A (R, R' 5) and A 8 (R. R'
5) as:
(R, R'| S) - | (R - SR') 1I, A
(R, R' S) - ||ReLU (SR'' - R) (9)
Similarly, for the node edits, we can compute A
X, X' P) and (X, X' P) as:
A [X X' P) = ||ReLU (x IX
1 X | = ||ReLU (PX'
(2) DIFFALIGN In Eq. (9), we first aligned R' using S and then computed the difference from R. Instead, here we first computed the pairwise differences between R' and R for all pairs of node-pairs (e, e'), and then combine these differences with the corresponding alignment scores S(e, el). We compute the edge edit surrogates A A R, R' S) and * RR R' S) as:
R. R' S) = Σ
ReLU (Rle, ] R' R' [e::)) ele,
(10)
e,e'
A R R' = Σ
|ReLU (R' [ Rle, :II, Sle,
(11)
Here, e and e' represent node-pairs, which are not necessarily edges. When the node-pair alignment matrix S is a hard permutation, A and A remain the same across ALIGNDIFF and DIFNALIGN (as shown in Appendix B). Similar to Eqs. (10) (10)-(1)) we can com- pute A (X, X' P) = Enw |ReLU (X(u: - (x'',; Plu, w'] and A (')
E.. ReLU (X'[u':) X (u,:Dil Plu, u'].
(3) COR-DIFFALIGN As indicated by the combinatorial formulation of GED in Eq. (7), the edit cost of a particular node-pair is non-zero only when an edge is mapped to a non-edge or vice-versa. However, the surrogates for the edge edits in ALIGNDIFF because they can assign non-zero costs to the pairs (e (u, v), = v')) even when both e and e' are either edges or non-edges. To address this, we explicitly discard such pairs from the surrogates defined in Eqs. (10)-11). This is ensured by applying XOR operator J..-)) between the corresponding entries in the adjacency matrices, i.e., A [u, u] and A'"u', v/). and then multiplying this result with the underlying term. Hence, we write:
DIFFALIGN fail to capture this condition
A ( R
Σ
A), ||RALU (R(e,)] R'''' R'ee,, (12)
e=(a,))
c'=(1',0")
A (
Σ
J(Alu, v). A'lu', (/ul,))) v/) ||RELU (R'(c', R[e, :1l, S(e,e").
(13)
Similarly, the cost contribution for node operations arises from mapping padded node to non non-padded node or vice versa. We account for this by multiplying J [(nc[u) [o'"w)) with each term of A e (' and A (x X' P) computed using DIFFALIGN. Hence, compute A @ [X, X',X'1 P) =E uu Mnaalu [u], no (u')) ||ReLU [x - ['uu', :))l2 Plu, u'] and - J [u], (u() |[ReLU (X'(u' (X'LL - X(u, :)l,, P(u, v/).
Enw A ((X,,, X' P) = En,e'
Comparison between ALIGNDIFF, DIFFALIGN and XOR-DIFFALIGN ALIGNDIFF and DIF- FALIGN become equivalent when S is hard permutation. However, when S is doubly stochastic, the above three surrogates, ALIGNDIFE, DIFFALIGN and XOR- DIFFFIIFA,,G,, are not equivalent. As move from ALIGNDIFF to DIFFALIGN to XOR-DOI DIFFII,ALLIN, we increasingly align the design to the inherent inductive biases of GED, thereby achieving a better representation of its cost structure.
Suppose we are computing the GED between two isomorphic graphs, G and G', with uniform costs for all edit operations. In this scenario, we idcally expect a neural network to consistently output a zero cost. Now consider a proposed soft alignment S which is close to the optimal alignment. Under the ALIGNDIFF design, the aggregated value Σ., S(e, e'] R'R' [e', 2'
where e and e' represent two edges matched in the optimal alignment- can accumulate over the large number of N - 1)/ /2 node-pairs.
This aggregation leads to high values of R[e. :] SR'(e', : implying that ALIGNDIFF IFF captures an aggregate measure of the cost incurred by spurious alignments, but cannot disentangle the effect of individual misalignments, making difficult for ALIGNDIFF to learn the optimal alignment.
In contrast, the DIFFALIGN approach, which relies on pairwise differences between embeddings to explicitly guide S towards the optimal alignment, significantly ameliorates this issue. For example, in the aforementioned setting of GED with uniform costs, the cost associated with each pairing

---

(e, e') is explicitly encoded using correctly aligned. Moreover, this representation allows DIFFALIGN to isolate the cost incurred by each misalignment, making it easier to train the model to reduce the cost of these spurious matches to zero.
:l]l. and is explicitly set to zero for pairs that are
However, DIFFALIGN does not explicitly set edge-to-edge and non-edge-to-non-edge mapping costs to zero, potentially leading to inaccurate GED estimates, XOR-DIIFALINN addresses these concerns by applying a XOR of the adjacency matrices to the cost matrix, ensuring that non-zero cost is computed only when mapping an edge to a non-edge or vice versa. This resolves the issues in both ALFGNDIFF and DIFFALIGN by focusing on mismatches between edges and non-edges, while disregarding redundant alignments that do not contribute the GED.
Amenability to indexing and approximate nearest neighbor (ANN) search. All of the aforemen- tioned distance surrogates based on a late interaction paradigm, where the embeddings of G and G' are computed independently of each other before computing the distances A. This is particularly useful in the context of graph retrieval, as it allows for the corpus graph embeddings to be indexed a-priori, thereby enabling efficient retrieval of relevant graphs for new queries.
When the edit costs are uniform, our predicted GED (8) becomes symmetric with respect to G and G'. In such cases, ALINNL and ALIGN yield a structure similar to the Wasserstein distance induced by L1 norm. This allows us to leverage ANN techniques like Quadtree However, while the presence of the XOR operator J within each term in Eq. (12) - (13) of XOR- DIFFALIGN enhances the interaction between G and G', this same feature prevents XOR-DIFF from being cast to an ANN-amenable setup, unlike ALIGN and ALIGNDIFF.
Flowtree [4].
4.3 Network architecture of EMBED, and PERMNET,
In this section, we present the network architectures of the two components of GRAPHEDXX, viz., EMBED, and PERMNET as introduced in items (1) and (2) in Section 4.2. Notably, in our proposed graph representation, non-edges and edges alike are embedded non-zero vectors. In other words, all mode-pairs are endowed with non-trivial embeddings. We then explain the design approach for edge-consistent node alignment.
Neural architecture of EMBED EMBED, consists of a message passing neural network MPNN, and decoupled neural module MLP,- Given the graphs G,G', MPNN, with K prop-
agation layers is used to iteratively compute the node embeddings (Ix (u) E Rd u juev V3 and (zk E Rd uu V'}, then collect them into X and X' after padding, i.e.,
X = (m) u E [N]] = MG) X' (x' / E [N]] = MPNNo(G"). (14) The optimal alignment S is highly sensitive to the global structure of the graph pairs, i.e., Sie, el) can significantly change when we perturb G G' in regimes distant from e or e'. Conventional representations mitigate this sensitivity while training models, by setting non-edges to zero, rendering them invariant structural changes. To address this limitation, we utilize more expressive graph representations, where non-edges are also embedded using trainable non-zero vectors. This approach allows information to be captured from the structure around the nodes through both edges and non-edges, thereby enhancing the representational capacity of the embedding network. For each mode-pair& e = (u, v) E G (and equivalently (u, w)), and é' = (u', v') E G', the embeddings of the corresponding nodes and their connectivity status are concatenated, and then passed through an MLP to obtain the embedding vectors r(e), r' (e') E RDD For e = (u, v) E G. we compute r(e) as: Alu, ul).
xx (v) A(u, v)) + MLPx(Ex(1)) || [| We can compute (e) in similar manner. The property r((u, v)) r((e, u)) reflects the undirected property of graph. Finally, the vectors r(e) and (ce') are stacked into matrices and R', both with dimensions RR
r (e) = MLPs(xx(
(15)
x x We would like to highlight that r((u, v)) or r'((',, (((u',,)) v')) are computed only once for all node- pairs, after the MPNN completes its final Kth layer of execution. The message passing in the MPNN occurs only over edges. Therefore, this approach does not significantly increase the time complexity.
Neural architecture of PERMNET, The network PERMNET provides P as a soft node alignment matrix by taking the node embeddings as input, i.e., P = PERMNET (X, X'). PERMNET is implemented in two steps. In the first step, we apply a neural network cæ on both æx and a'g. and then compute the normed difference between their outputs to construct the matrix C, where Clu, u'] lcca (wx(w) ca (a's (u'))) Next, we apply iterative Sinkhorn normalizations [16,
7

---

35] on exp(-C//T) to obtain a soft node alignment P. Therefore,
p= Sinkhorn [[exp (-1lay |co (æx(u)) co (2'x
(16)
Here, I is a temperature hyperparameter. In a general cost setting, GED is typically asymmetric, so it may be desirable for Clu, u'] to be asymmetric with respect to and x'. However, as noted in Proposition 1, when we compute GED(G", G), the alignment matrix P = PERMNET (X', X) should satisfy the condition that P' PT, where P is computed from Eq. (16). The current form of C' supports this condition, whereas an asymmetric form might not, shown in Appendix B.
We construct S E ( x (
as follows. Each pair of nodes (u, v) G and (u', o') in G' can be mapped in two ways, regardless of whether they are edges non-edges: (1) node u u' and V + E' which is denoted by P(u, P'e, e']; (2) node u + s' and v + u', which is denoted by Plu, Plu,"1P P(e, Combining these two scenarios,
compute the node-pair alignment matrix S as: S((u,)) v), (u',"") = Piu, P(u, o'] + Plu, o' Ple, u'). This explicit formulation of S from P ensures mutually consistent permutation across nodes and node-pairs.
Experiments
We conduct extensive experiments on GRAPHEDX to showcase the effectiveness of our method across several real-world datasets, under both uniform and non-uniform cost settings for GED. Additiinna experimental results can be found in Appendix D.
5.1 Setup
Datasets We experiment with seven real-world datasets: Mutagenicity (Mutag) [18], Ogbg- Codee
(Code2) [23]. Ogbg-Molhiv (Molhiv) [23], Ogbg-Molpcba (Molpcba) [23], AIDS [36], Linux [5] and
Yeast [36]. For each dataset's ' training, test and validation sets Daplit. we generate (PPatt + |Deplil graph pairs, considering combinations between every two graphs, including self- self-pairing. We calculate the exact ground truth GED using the F2 solver [29], implemented within GEDLIB [10]. For GED with uniform cost setting, we set the cost values b b a a
For GED with non-uniform cost setting, we use o = 3, D a = 2, の = 1. Further details on dataset generation and statisties are presented in Appendix C. In the main paper, we present results for the first five datasets under both uniform and non-uniform cost settings for GED. Additional experiments for Linux and Yeast, as well as GED with node label substitutions, are presented in Appendix D.
Baselines We compare our approach with nine otate-of-the-art methods. These include two variants of GMN [31]: (I) GMN-Match and (2) GMN-Embed; (3) ISONET [44], (4) GREED [40], (5) ERIC [56]. (6) SimGNN [5]. (7) H2MN [54], (8) GraphSim [6] and (9) EGSC [39]. To compute the GED, GMN-Match GMN-Embed, and GREED use the Euclidean distance between the vector representation of two graphs. ISONET uses asymmetric distance specifically tailored to subgraph isomorphism. H2MN an early interaction network that utilizes higher-order node similarity through hypergraphs. ERIC, SimGNN, and EGSC leverage neural networks to calculate the distance between two graphs. Furthermore, the last three methods predict a score based on the normalized GED the form of exp (-2GED(G, G')/(IVI + [V')). Notably, none of these baseline approaches have been designed to incorporate non-uniform edit costs into their models. To address this limitation, when working with GED under non-uniform cost setting, we include the edit costs as initial features in the graphs for all baseline models. In Appendix D.3, we compare the performance of baselines without features.
cost
Evaluation Given a dataset = {(G,, G², GED(G,, (,),,,G))) G.)) we divide it into training, valida- tion and test folds with split ratio 60:20:20. We train the models using the Mean Squared Error (MSE) between the predicted GED and the ground truth GED as the loss. For model evaluation, we calculate the Mean Squared Error (MSE) between the actual and predicted GED on the test set. For ERIC, SimGNN and EGSC, we rescale the predicted score to obtain the true (unscaled) GED as GED G') = -(V] + IVl') (2) In Appendix D, we also report Kendall's Tau (KTau) to evaluate the rank correlation across different experiments.
5.2 Results
Selection of ( X' X' and AR, R' (S) We start by comparing the performance of the nine different combinations (three for edge edits, and three for node edits) of our neural distance sur-
8

---

rogates from the cartesian space of (ALIGDAA DIFFALIGN, XOR- DIFFALIGN) x Node- (ALIGNDIFF, DIFFALIGN, DIFIIINAL Table 2 summarizes the results. We make the following observations. (1) The best combinations share the KOR-DIFFALIGN on the edge edit for- mulation, because, KOR-DIFFAL.CE offers more inductive bias, by zeroing the edit cost of aligning an edge to edge and non-edge to non-edge, as we discussed in Section 4.2. Consequently, one can limit the cartesian space to only three surrogates for node edits, while using fixed surrogate for edge edits, (2) There is no clear winner between ALIGN and ALIGNDIFF. GRAPHEDX is chosen from the model which has the lowest validation error, and the numbers in Table 2 are the test set. Hence, in datasets such as AIDS under uniform cost, or Molhiv under non non-uniform cost, the model chosen for GRAPHEDX doesn't 't have the best test set performance.
as the
Edge edit
Node edit
GED with uniform cost
GED with non-uniform cost
Muing
Crde2
Molhiv
Melpcha
ATDS
Matag
Code2
Molhiv
Molpcha
AIDS
DIVAAIINN
DRVALIGN
0,579
0.740
0.820
0.778
0.003
1.208
2.451
1.835
1.825
1.417
DIPPALION
ALIGNDIFF
0.587
0,742
0,806
0.779
0.597
1:211
2.116
1.887
1.811
1.319
DIFFALIGN
XOR
0.538
0.794
0.777
0.580
1.146
1.896
1.822
ALIGNDIFF
DIFFALION
0.537
0,513
0,815
0.773
0.606
1.185
1.689
1.874
1.758
1.391
ALIGNDIFF
ALIGNDIFF
0.833
0.773
1.338
1.488
1.859
1.326
ALIGNDIFF
XOR
0.533
0.826
0,812
0.780
0.575
1.196
1.741
1,870
1.815
1.374
XOR
ALIGNDEFF
0.492
0,429
0.788
0.766
0.565
L134
1.478
1.872
1.742
1.252
XOR
DIRFALION
0,510
0.634
0,781
0.765
0.574
1.148
1 1,89
1.804
1.757
1.340
XOR
XOR
0.530
1,588
0.807
0.764
0.564
1.195
2 507
1.855
1.677
1.319
GRAPHEDX
0.492
0,429
0.781
0.764
0.565
1.134
1.478
1.804
1.677
1.252
Table 2: Prediction error measured in terms of MSE of the nine combinations of our neural set
distance surrogate across five datasets on test set, for GED with uniform costs and non-uniform costs.
For GED with uniform (non-uniform) costs we have 8 = 6 = d = a = 1 (b = 3, 6
1, 0 2, の 1.) The GRAPHEDX model was selected based on the lowest MSE on the validation set, and we report the results of the MSE on the test set. Green ( yelllow) numbers report the best (second best) performers.
Comparison with baselines We compare the performance of GRAPHEDX against all state-of-the-a baselines for GED with both uniform and non-uniform costs. Table 3 summarizes the results. We make the following observations. (1) GRAPHEDS outperforms all the baselines by a significant margin. For GED with uniform costs, this margin often goes high as 15%. This advantage becomes even more pronounced for GED with non-uniform costs, where our method outperforms the baselines by a margin as high as 30%, seen in Code2. (2) There is no clear second-best method. Among the baselines, EGSC and ERIC each outperforms the others in two out of five datasets for both uniform and non-uniform cost settings. Also, EGSC demonstrates competitive performance in AIDS.
GED with uniforn cost
GED with non-uniform cost
Mutag
Code2
Molhiv
Molpcha
AIDS
Mutag
Code2
Molhiv
Molpcha
AIDS
GMN-Match Match [31]
0.797
1.677
1.318
1,73
0.821
69.210
13.472
76.923
23,985
31.522
GMN-Embed [31]
1.032
1.358
1.859
1,951
1.044
72.495
13:425
78.254
28.437
33.221
ISONET [44)
1.187
0,879
1.354
1.106
1.600
3,369
3.025
3.451
2.781
5.513
GREED [40]
1.398
1.869
1.708
1,550
1.004
68.732
11.095
78,300
26.057
34.354
ERIC [56]
0.719
1.363
1.165
0.862
0.731
1.981
12.767
3,377
2.057
1,581
SimGNN [5]
1.471
2.667
1.609
1.456
1.455
4,747
5,212
4.145
3,465
4,316
H2MN [54]
1.278
7.240
1.521
1.402
1.114
3,413
9.435
3.782
3.396
3.105
GraphSim [6]
2.005
3,139
2,577
1.656
1.936
5,370
7,405
6.643
3,928
5,266
EGSC [39]
0.765
4.165
1.138
0.938
0.627
1.758
3.957
2.371
2.133
1.693
GRAPHEDX
0.492
0.429
0.781
0.764
0.565
1,134
1,78
1,804
1.677
1.252
Table 3: Prediction error measured in terms of MSE of GRAPHEDX and all the state-of-the-
art baselines across five datasets on test set, for GED with uniform costs and non-uniform costs. For GED with uniform (non-unfiform) costs we have 5 b = a a 1
(6 = 3, l = 1 = 2, th = 1.) GRAPHEDX represents the best model based on the vali- dation set from the cartesian space of Edge- | DIFF DIFFALIGN, ALIGGN) x Node- (ALIGNDIFF, DIFFALIGN, XIF-DIFFALIGN) Green ( yeellow) numbers report the best (second best) performers.
Impact of cost-guided GED Among the baselines, GMN-Match, GMN-Embed and GREED compute GED using the euclidean distance between the graph embeddings, ie., GED G*) = ||æG - 122. whereas we compute it by summing the set distance surrogates between the node and edge embedding sets. To understand the impact of our cost guided distance, we adapt it to the graph-level embeddings used by the above three baselines as follows: GED(G, = 8 a 2
||ReLU (xc ) + 8 th ||ReLU (xc' - x- Table 4 summarizes the results in
9

---

Unitorm cost
Non-uniferm cnd
Mutog
Code2
Molhiv
Molpcha
AIDS
Mutag
Code2
Molhiv
Mutag
Code2
Molhiv
GMN Match
1.057
5:224
1.388
1.432
0.868
GMN-Maach
0.797
1.677
1.318
69.210
13,472
76.925
2.159
4.070
3.523
4.657
1.818
GMN-Mateh
0.654
0.960
1,008
1.592
2.906
2.162
ISONET
0.876
1.129
1.617
1.332
1.142
GMN-Ember
1,32
1.358
1.859
72.495
13.425
78.254
GREED
4,983
2.923
GMN-Embed
1.011
1.179
1.409
2.368
3.272
3,413
ERIC
0.886
6.323
1.537
1.278
1.602
GREED
1.398
1.869
1.708
68.732
11.095
78.300
SimGNN
1.160
5.909
1.888
2.172
1.418
GREED
2.133
1.850
1.644
2.456
5.429
3.827
H2MN
1.277
6.783
1.891
1.666
1.290
GRAPHEDX
0.492
0.429
0.781
L.14
1.478
1.804
GraphSim
1,043
4. 4.708
1.817
1.748
1,561
EGSC
8.742
1.273
1.426
Table Impact of cost guided distance in terms of MSE; represents the variant of the baseline with cost-guided distance. Green (bold) shows the best among all methods (only baselines).
GRAPHEDX
0.431
0.820
0.792
0.846
0.538
Table 5: MSE for different methods with unit node substitution cost in uniform cost setting, Green (yellow) show (second) best method.
terms of MSE, which shows that (1) our set-divergence-batt cost guided distance reduces the MSE by significant margin in most cases (2) the margin of improvement is more prominent with GED involving non non-uniform costs, where the modeling of specific cost values crucial (3) GRAPHEDX outperforms the baselines even after changing their default distance to our cost guided distance.
Performance for GED under node substitution cost The scoring function in Eq. 8 can also be extended to incorporate node label substitution cost, which has been described in Appendix B. Here, we compare the performance of our model with the baselines in terms of MSE where we include node substitution cost 6", with cost setting as 6 = 6 = b =0==a a = a 1. In Table 5, we report the results across 5 datasets equipped with node labels, passed one-hot encoded node features. We observe that (1) our model outperforms all other baselines across all datasets by significant margin; (2) there is no clear second winner but ERIC, EGSC and ISONET performs better than the others.
Benefits of using all node-pairs representation
In Table 6, we compare against
()) Edge-only (edge + edge): where only consider the edges that are present, resulting in S heing an edge-alignment matrix, and
Mutag
Code2
Molhiv
R, R' E [Bmax[[B],e"" D (ii) Edge-only (pair + pair): In this variant, the embeddings of the non- edges in R, R' RNNN-1)/2XD are explicitly set zero. in terms of MSE, which show that (1) both these sparse representations perform significantly worse compared to our method using non-trivial representa- tions for both edges and non-edges, and (2) Edge-only (edge - edge) performs better than Edge-only (pair + pair). This underscores the importance of explicitly modeling trainable non-edge embeddings to capture the sensitivity of GED to global graph structure.
Edge-only (edge + edge)
0.566
0.683
0.858
Edge-only (puir - pair) GRAPHEDX
0.596
0.760
0,862
0,492
0.429
0,781
Table 6: Comparison of variants edge represen- tation under uniform cost setting. Green (yellow) numbers report the best (second best) performers.
6 Conclusion
Our work introduces a novel neural model for computing GED that explicitly incorporates general costs of edit operations. By leveraging graph representations that recognize both edges and non-edges, together with the design of suitable set distance surrogates, we achieve more robust neural surrogate for GED. Our experiments demonstrate that this approach outperforms state-of-the-an methods, especially in settings with general edit costs, providing flexible and effective solution for range of applications. Future work could focus on extending the GED formulation to richly-attributed graphs by modeling the structure of edit operations and the similarity of all node-pair features.
Limitations Our neural model for GED showcases significant improvements in accuracy and flexibility for modeling edit costs. However, there are some limitations to consider. (1) While computing graph representations over (2) x (N) node-pairs does not require additional parameters due to parameter-sharing. it does demand significant memory resources. This could pose challenges, especially with larger-sized graphs. (2) The assumption of fixed edit costs across all graph pairs within a dataset might not reflect real-world scenarios where costs vary based on domain-specific factors and subjective human relevance judgements. This calls for more specialized approaches to accurately model the impact of each edit operation, which may differ across node pairs.
Ackmowledgements Indradyumna acknowledges Qualcomm Innovation Fellowship, Abir and Soumen acknowledge grants from Amazon, Google, IBM and SERB.
10

---

References
[1] Adler and S. Lunz. Banach wasserstein gan. Advances in neural information processing systems, 31, 2018.
[2] B. Amos, L. Xu, and J. Z. Kolter. Input convex neural networks. In International Conference on Machine Learning, pages 146-155. PMLR, 2017.
[3] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pages 214-223. PMLR, 2017.
[4] A. Backurs, Y. Dong, P. Indyk, I. Razenshteyn, and T. Wagner. Scalable nearest neighbor search for optimal transport. International Conference on machine learning, pages 497-506. PMIR, 2020.
[5] Y. Bai, H. Ding, S. Bian, Chen, Y. Sun, and W. Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 384-392 392, 2019.
[6] Y. Bai, H. Ding, K. Gu, Y. Sun, and W. Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3219-3226, 2020.
[7] D. B. Blumenthal. New techniques for graph edit distance computation. arXiv preprini arXiv: 00265, 2019.
[8] D. B. Blumenthal and J. Gamper. Improved lower bounds for graph edit distance. IEEE Transactions on Knowledge and Data Engineering. 30:503-516, 2018. URL https://api. semanticscholat Trrg/CorpusID. 34388055
[9] D. B. Blumenthal, E. Daller, Bougleux, L. Brun, and J. Gamper. Quasimetric graph edit distance as compact quadratic assignment problem. In 2018 24th International Conference Pattern Recognition (ICPR), pages 934-939, 2018. doi: 10.1109//CP..2011.854444 85466555.
[10] D. B. Blumenthal, S. Bougleux, J. Gamper, and L. Brun. Gedlib: A c++ library for graph edit distance computation. In D. Conte, J.-Y. Ramel, and Foggia, editors, Graph-Base Representations in Pattern Recognition, pages 14-24, Cham, 2019. Springer International Publishing. ISBN 778-3-030-20081-7.
[11) S. Bougleux, I.. Brun, V. Carletti, P. Foggia, B. Gaüzère, and M. Vento. Graph edit distance as quadratic assignment problem. Puttern Recognition Letters, 87:38-46, 2017. ISSN 0167-8655. doi: https://dol.org/1100100066 patree. 10.001. URL https: /wwww//wwcc/ooo///// sciencedirect. com/ Advances in Graph-based Pattern Recogni-
scimmme//artticee//1//////66666. tion.
[12] A. Z. Broder, M. Charikar, A. M. Frieze, and M. Mitzenmacher. Min-wise independent permutations. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. pages 327-336, 1998.
[13] H. Bunke. On a relation between graph edit distance and maximum common subgraph. Pattern Recognition Letters, 18(8):689 694, 1997.
[14] H. Bunke and G. Allermann. Inexact graph matching for structural pattern recognition. Pattern Recognition Letters, 1(4):245-253, 1983.
[15] L. Chang, X. Feng, X. Lin, L. Qin, and W. Zhang. Efficient graph edit distance computation and verification via anchor-aware lower bound estimation. arXiv preprint arXiv: arXiv:I709.00 777000699000 2017.
[16] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
[17] M. Daniels, T. Maunu, and P. Hand. Score-based generative neural networks for large-scale optimal transport. Advances in neural information processing systems, 34:12955-12965, 2021.

---

[18] A. K. Debnath, R. L. Lopez de Compadre, G. Debnath, A. J. Shusterman, and C. Hansch. Structure-activity relationship mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal Chem- istry, 34(2)786-7977 1991. doi: 10.1021/jm0010aal/ URL. https::///oo. org/ 10. 1021/ jm00106a046.
[19] K. D. Doan, S. Manchanda, S. Mahapatra, and C. K. Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 665-674, 2021.
[20] M. Douze, A. Guzhva, C. Deng. J. Johnson, G. Szilvasy, P.-E. Mazaré, M. Lomeli, L. Hosseini, and H. Jégou. The faiss library. arXiv preprint arXiv:2401. 1.028/, 2024.
[21] C. graph edit distance as molecular similarity measure. Journal of chemical information and modeling, (14)::410-112)) 2019.
A. Fernandez, and F. Serratosa. Ligand-based based virtual screening using
[22] A. Genevay, M. Cuturi, G. Peyré, and F. Bach. Stochastic optimization for large-scale optimal transport. Advances in neural information processing systems, 29, 2016.
[23] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:221 18-32133, 2020.
[24] Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing. pages 604 613, 1998.
[25] P. Indyk, R. Motwani, P. Raghavan, and S. Vempala. mensional spaces. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 618-625, 1997.
hashing in multidi-
[26] S. Ivanov. S. Sviridov, and E. Burnaev. Understanding isomorphism bias in graph data sets. arXiv 1910. 12091, 2019. URL httt:::t///aiiiii htw.aaawwwi..rgg//////1///. 12091.
[27] D. Justice and A. Hero. A binary linear programming formulation of the graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2808): 1214, 2006.
[28] M. G. Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81-93, 1938.
[29] J. Lerouge, Z. Abu-Aisheh, R. Raveaux, P. Héroux, and S. Adam. New binary linear pro- gramming formulation to compute the graph edit distance. Pattern Recognition, 72:254- 265, 2017. ISSN 0031-3203. doi: http:://o...ng//00oooo//ppooopop
11001001111.1110222100000.02.. URL
[30] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.0549: 2015.
[31] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference machine learning, pages 3835-3845. PMLR, 2019.
[32] C.-L. Lin. Hardness of approximating graph transformation problem. In D.-Z. Du and X.-S. Zhang, editors, Algorithms and Computation, pages 74-82, Berlin, Heidelberg, 1994. Springer Berlin Heidelberg. ISBN 978 580-4-340-4
[33] 7. Lou, J. You, C. Wen, A. Canedo, J. Leskovec, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03092. 2020.
[34] Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4))824-8366 2018.
12

---

[35] G. Mena, D. Belanger. S. Linderman, and J. Snoek. Learning latent permutaaiions with gumbel- sinkhorn networks. arXiv preprint 102.:0802.08665,, 2018. URL https://axxiv..ort org org/df// 1802. 08665. pdf.
[36] C. Morris, N. M. Kriege, Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs, 2020.
[37] B. Naidan, L. Boytsov, Y. Malkov, and D. Novak. Non-metric space library manual. arXiv preprint arviv: 1508. 05470, 2015.
[38] E. Ozdemir and C. Gunduz-Demir. A hybrid classification model for digital pathology using structural and statistical pattern recognition. IEEE Transactions on Medical Imaging, 32(2):
474 414,483,22 2013. doi: 10. 1119/TM..001..230001
[39] C. Qin, H. Zhao, L. Wang. H. Wang, Y. Zhang, and Y. Fu. Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation. In Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[40] R. Ranjan, S. Grover, Medya, V. Chakaravarthy, Sabharwal, and S. Ranu. Greed: neural framework for learning graph distance functions, Advances in Neural Information Processing Systems, 35:22518-222 1--2230, 2022.
[41] K. Riesen and H. Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image and Vision Computing, 27(7):950-959, 2009. ISSN 0262-8856. doi: https://doi.ogg org/ 1001 2008. 04.004 URL https: /www. sciencedirect. com/ 7th IAPR-TCI5 Workshop on Graph-based
science/ articlll/c//////oeeeoooooooeeeee pttppp/022285600000000000333 Representations (GbR 2007).
[42] K. Riesen, A. Fischer, and H. Bunke. Combining bipartite graph matching and beam search for graph edit distance approximation. In Artificial Neural Networks in Pattern Recognition: 6th IAPR TC International Workshop, ANNPR 2014, Montreal, QC. Canada, October 6-8, 2014. Proceedings 6, pages 117-128. Springer, 2014.
[43] I. Roy, S. Chakrabarti, and A. De. Maximum common subgraph guided graph retrieval: late and early interaction networks. Advances in Neural Information Processing Systems, 35: 32112 1211222,,,,, 2022.
[44] I. Roy. V. Velugoti, Chakrabarti, and De. Interpretable Neural Subgraph Matching for Graph Retrieval. AAAI, 2022.
[45] S. Sahni and T. Gonzalez. P-complete approximation problems. J. ACM, 23(3):555 1976. ISSN 0004-5411. doi: 10. 10.1145/321958.321999 URL httptt//:///o/ ort.o.........0.... 1145/ 011958.321977
[46] A. Sanfeliu and K.-S. Fu. distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, pages 353-362, 1983.
[47] A. Sanfeliu, R. Alquézar, J. Andrade, Climent, F. Serratosa, and J. Vergés. Graph-based representations and techniques for image processing and image analysis. Pattern recognition, 35(3):639-650, 2002.
[48] V. Seguy, B. B. Damodaran, R. Flamary, N. Courty, A. Rolet, and M. Blondel. Large-scale optimal transport and mapping estimation. arXiv preprint 1rXiv:1711.02288 2017.
[49] K. Shearer, H. Bunke, and S. Venkatesh. Video indexing and similarity retrieval by largest common subgraph detection using decision trees. Pattern Recognition, 34(5):1075-1091 2001.
[50] R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-34 334448,, 1967.
[51] S. Tirthapura, D. Sharvit, P. Klein, and B. B. Kimia. Indexing based on edit-distance matching of shape graphs. In Multimedia storage and archiving systems III, volume 3527, pages 25-36. SPIE, 1998.
13

---

[52] Y. Xie, M. Chen, H. Jiang, T. Zhao, and H. Zha. On scalable and efficient computation of large scale optimal transport. In International Conference on Machine Learning, pages 6882-6892. PMLR, 2019.
[53] Z. Zeng, A. K. Tung, J. Wang, J. Feng, and L. Zhou, Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25 02:25-366660 2009.
[54] Z. Zhang, J. Bu, M. Ester, Z. 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, KDD '21, page 2274-2284, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383322 doi: 10.1 10.1145/344554..44055 34663328.. URL https: /toii org/10. 1111/114444444 3467328.
[55] W. Zheng, L. Zou, X. Lian, D. Wang, and D. Zhao. Efficient graph similarity search over large graph databases. IEEE Transactions on Knowledge and Data Engineering, 27(())964 978. 2014.
[56] W. Zhuo and G. Tan. Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, 35:30181-30193, 2022.
14

---

Graph Edit Distance with General Costs Using Neural Set Divergence (Appendix)
Contents
Broader impact
16
B Discussion on our proposed formulation of GED
17
B.1 Modification of scoring function from label substitution
17
B.2 Proof of Proposition
17
B.3 Connections with other notions of graph matching
18
B.4 Relation between ALIGNDIFF and DIFFALIGN
18
B.5 Proof that our design ensures conditions of Proposition
19
B.6 Alternative surrogate for GED
19
Details about experimental setup
21
C.I Generation of datasets..
C.2 Details about state-of-the-art baselines
21
C.3 Details about GRAPHEDX
................................
23
C,4 Evaluation metrics
23
C.5 Hardware and license
24
Additional experiments
25
D.I
Comparison of performance of GRAPHEDX on non-uniform cost Edge-GED
25
D.2
Comparison of GRAPHEDX with baselines on uniform and non-uniform cost setting
26
D.3 Comparison of GRAPHEDX with baselines with and without cost features
27
D.4 Comparison of GRAPHEDX with baselines with node substitution cost
28
D.5
Performance evaluation for edge-only vs. all-node-pair representations
28
D.6 Effect of using cost-guided scoring function on baselines
29
D.7 Results on performance the alternate surrogates for GED
29
D.8 Comparison zero-shot performance on other datasets
29
D.9 Importance of node-edge consistency
30
D.10 Comparison of nine possible combinations proposed set distances
31
D.I1 Comparison performance of our model with baselines using scatter plot
32
D.12 Comparison of performance of our model with baselines using error distribution...
32
D.13 Comparison of combinatorial optimisation gadgets for GED prediction
33
D.14 Prediction timing analysis..
34
D.15 Visualization (optimal edit path) + Pseudocode
34
15

---

A Broader impact
Graphs serve as powerful representations across diverse domains, capturing complex relationships and structural notions inherent in various systems. From biological networks to social networks, transportation networks, and supply chains, graphs provide a versatile framework for modeling interactions between interconnected entities. In domains where structure-similart, based applications are prevalent, GED emerges as a valuable and versatile tool.
For example, in bio-informatics, molecular structures can naturally be represented as graphs. GED computation expedites tasks such as drug discovery, protein-protedd interaction modeling, and molecular similarity analysis by identifying structurally similar molecular compounds. Similarly, in social network analysis, GED can measure similarities between user interactions, aiding in friend recommendation systems community detection tasks. In transportation networks, GED- based tools assess similarity between road networks for route planning or traffic optimizations. Further applications include learning to edit scene graphs, analyzing gene regulatory pathways, fraud detection, and more
Moreover, our proposed variations of GED, particularly those amenable to hashing, find utility in retrieval based setups. In various information retrieval systems, hashed graph representations can be used to efficiently index and retrieve relevant items using our GED based scores. Such applications include image retrieval from image databases where images are represented as scene graphs, retrieval of relevant molecules from molecular databases, etc.
Furthermore, our ability effectively model different edit costs in GED opens up new possibilities in various applications. In recommendation systems, it can model user preferences of varying importance, tailoring recommendations based on user-specific requirements or constraints. Similarly. in image or video processing, different types of distortions may have varying impacts perceptual quality, and GED with adaptive costs can better assess similarity. In NLP tasks such as text similarity understanding and document clustering, assigning variable costs to textual edits corresponding to word insertion, deletions or substitutions, provides more powerful framework for measuring textual similarity, improving performance in downstream tasks such plagiarism detection, summarization, etc.
Lastly, and most importantly, the design of our model encourages interpretable alignment-driven justifications, thereby promoting transparency and reliability while minimizing potential risks and negative impacts, in high stake applications like drug discovery.
16

---

B Discussion on our proposed formulation of GED
B.1 Modification of scoring function from label substitution
To incorporate the effect of node substitution into account when formulating the GED, we first observe that the effect of node substitution cost b" only comes into account when a non non-padded node maps to non non con-padded node, In all other cases, when a node is deleted or inserted, we do not additionally incur any substitution costs. Note that, we consider the case when node substitution cannot be replaced by node addition and deletion, i.e., b < 1 + 1 Such constraint on costs has uses multiple applications [9, 38]. Let L. denote the set of node labels, and f(u), ('(x') E L denote the node label corresponding to nodes and u' in G and G' respectively. We construct the node label matrix L for G as follows: L {0. 1) 1 such that L | one_hott ane_hot(((i)) ie., L is the one-hot indicator matrix for the node labels, which each row corresponding the one-hot vector of the label. Similarly, we can construct L' for G'. Then, the distance between labels of two nodes u V and u' V can be given as [|, L' :][l.- To ensure that only valid node to node mappings contribute to the cost, we multiply the above with A(u, u') AND(na (u), na [u']). This allows us write the expression for GED with node label substitution cost as
GED(G, G')
min PEPN
|eLU (A- PA'P 1l
+
||eLLU (PA'PT -1)
2
2
6 ||ReLU (no - Pno)lll 6 ||ReLU - -c)ll
4
A(u, [|][u, L[u :ill Plu,u']
AL(LL(1)))
We can design neural surrogate for above in the same way done in Section 4.2, and write
GFDo, G') = a RR R' (JS) + a A R' S)
+ A X' P) + 6 (x.
+ 1L'A"LLL''
(17)
In this case, to account for node substitutions in the proposed permutation, we use L[u.:] and [' as the features for node u in and node u' in G', respectively. We present the comparison of our method including subsitution cost with state-of-the-an baselines in Appendix D.
B.2 Proof of Proposition
Proposition Given fixed set of values of 60, 6,,6 a _..a" @ let P be an optimal node permutation matrix corresponding to GED(G, G'), computed using Eq. (7). Then, p' P is an optimal node permutation corresponding to GED(G', G).
Proof: Noticing that ReLU (c d) max(c, d) d, we can write
ReLU (A- PA'PT) I1.1 || |max ( A, PA'PT) - PA'P 11,1
PA |1,, E
The last equality follows since max(A A, PA'P)) 2 PA'PT element-wise, and PA'P 1,1 = A 11,1 = 2 E'|. Similarly, we can rewrite
ReLU (PA'PT A) | ReLU (nG - Pmo) )l
and |ReLU (Pnc* nc)ll 1. and finally rewrite Eq. (7)
@ + a
GED(G, = min PEPN
|max (A, PA'P Il - 8 - 0
2
(18)
8
+ 6
+
mmx (nx: nc. Pnoy |l 1 19
2
e + 8
GED = min
|max AA, PAP )l1 a 6 a E
PEPx
2
(19)
b +
6
+
|axx PnG Mln - | |
2
17

---

We can rewrite the max term as follows:
max A, A.PAP
Σ max A, PA'P" }(u,
Σ max
PP APPT, PA'PT)u
Σ P Pmax PT AP,A)) [u,
Σ max P AP, (P,,')u,,))
|| PT AP, A' || A', PT AP)
Similarly write |maxxnn Png ||| function b b0 9 9 the terms containing E E 1
max NG', P nG) Given a fixed set of cost
V V are constant and do not affect V'I, Using the above equations,
choosing optimal P. Let == a E"I a we can write:
E
V b
6
|mxx A, PA'PT)
+
maxx(nc.) Pre )ll
2
+ t a
6thh
+ +
| PT AP)
+
| P PTna)ll
2
2
Let the first term be p(G, G' P). Then second term be expressed p(G', G P and PT)
p(G, G' P) = p(G', PT) for all P E Pv. If P is the optimal solution of minper, p(G, G' P)
then, p(G', G PT)
pG"' G| P) for any permutation P. Hence, P' = =PP PN one optimal permutation for GED(G',
G P) S D(G,G'
B.3 Connections with other notions of graph matching
Graph isomorphism: When we set all costs to zero, we can write that GED(G, G") = mine 0.5 A- PA'PT 1.1 + ||L - Pnolls ll.. In such a scenario, GED(G, G") is symmetric, i.e., GED(G', G) GED(G, G') and becomes zero only when G and G' are isomorphic.
Subgraph isomorphism: Assume 1 8
Then, if we set the cost of edge addition
to be arbitrarily small as compared to the cost of edge deletion, i.e,, a < 1 This yields GED(G, G') = m En,, ReLU (A PA'P [u, v)), which can be reduced to zero for some permutation C.
Maximum common edge subgraph: From Appendix B.2, )|l
write that GED(G, G*) mine (. + a || (A, PA'PT)] + 0.5(b + bo) || Pno HI, - E 10|v'l 8 IV.. When @ @ and 6 6 = 0, then GED G') = max A, PA'P Il,,
@
+ E min, 1.)PP))ll, Il,. Here, min(A, PA'P") char-
acterizes maximum common edge subgraph and |lmin( A, PA'PT)] !li,, provides the number of edges it.
B.4 Relation between ALIGNDIFF and DIFFALIGN
Lemma 2 Lei 2, E NxM, and S E Bzz
NxN
be double stochastic. Then,
|eeLU (Z- SZ''ll,
Σ ||RLLU (Z z D'il S
18

---

Proof: We can write,
|ReLU (Z --ZZZ
11,1
Σ
ReLU Zii,j] > Sli,k| [k.
ReLU
S[i, Z(i S A (Ks
1
R 2 [i. )1)
Σ
ReLU [Z Z' =II S
where (+) follows since >, S(ū,k] k] = 1 vi E [N] and (**) follows due convexity of ReLU ()
Now, notice that when S E Px. then Slú, :] is one element while 0 at the rest. that case, we have
RcLU Σ
S
S k| z (1) = Σ
ReLU [Z.. 5l)
Σ>
St, (i..i) (k.
where kg is the index where S :] is 1. Hence, we have an equality when S is hard permuta- tion. Replacing (Z, Z with (R, R') and (X, X'), we get that ALIGNDIFF and DIFFALIGN equivalent when S is a hard permutation matrix, and moreover DIFF ALIGN is an upper bound on ALIGNDIFF when S is soft permutation matrix.
B.5 Proof that design ensures conditions of Proposition 1
Here we show why it necessary to have a symmetric form for Clu, xd] in PERMNET For GED(G,G"),
Clu, o] |ca (xx (u)) co (xxx (c))lI
For GED G),
C" u] || (x)x())
(v)) - ca (x (1))ll
Because the Sinkhorn cost Clu, is symmetric, using the above equations we can infer,
Clu, u] = C"(u, u). which implies C' = C
This leads to P PT |ReLU (co (u)( co (x'r (1) we cannot ensure Clu, e] C²(u, ud,, which fails to sat- isfy P = P
we use an asymmetric Sinkhorn cost (Clu, v] =
B.6
Alternative surrogate for GED
From Appendix B.2, we have
GED(G, G') min PEPN 2
+
|max A, PA'P ) -33 - 0
6
6
2 |max(nc: Pne }ll - b- V
Following the relaxations done in Section 4.2, we propose an alternative neural surrogate by replacing |max(A, A, PA'P Ill,, by ||max (R, R')ll, and |mmax maxx(TG,. (G, Pne )ll by ||max(X PX)
which gives us the approximated GED parameterized by and Φ as
_ + +
GED,,o(G,G))
||max R, SR' Iln, -0 - $
2
(20)
8 + 6
|max X,
2
We call this neural surrogate as MAX. We note that element-wise maximum over A and PA'PT only allows non-edge to non-edge mapping attribute value of zero. However, the neural surrogate described in Equation 20 fails to capture this, due to the presence of the soft alignment matrix S. To address this, we explicitly discard such pairs from MAX by applying an OR operator over the edge presence between concerned node pairs, derived from the adjacency matrices A and A' and
19

---

populated in OR A, A) E (f) given by OR( A [u, v), A' v')). Similarly, the indication of
node presence can be given be given as OR(NG: NG' [1, x = OR 7G [u], no [u]). Hence, we write
a + の
(GD
|OR A, A O max R2 SR') 1l, I|,,
a 1.' a [
2
0 b
|OR(NG; ))r) O max X, PX 6 8 1
(21)
We call this formulation MAX-OR. We provide the comparison between MAX, MAX-OR, and our models in Appendix D.
20

---

Details about experimental setup
C.1 Generation of datasets
We have evaluated the performance of our methods and baselines on seven real-world datasets: Mutagenicity (Mutag), Ogbg-Code2
Code2 (Code2), Ogbg-Molhiv (Molhiv), Ogbg-Molpcba (Molpcba). AIDS, Linux and Yeast. We split each dataset into training, validation, and test splits in ratio of 60:20:20. For each split D, we construct (ID)((D) [D] + 1))/2 source and target graph instance pairs as follows: S = {(G,, G2) G,, G, E DDDE j}. We perform experiment in four GED regimes:
1. GED under uniform cost functions, where b 10 a a² 1 and substitution costs are
2. GED under non-uniform cost functions, where b = 3, 6 1, 0 2, a and substitution
costs are 0
3. edge GED under non-uniform cost functions, where 6 = 6 0. a = 2, a = 1, and
substitution costs 0
4. GED with node substitution under uniform cost functions, where 5 = b = a = a
1
= 1, as
well as the node substitution cost 6a =
We emphasize that we generated clean datasets by filtering out isomorphic graphs from the original datasets before performing the training, validation, and test splits. This step is crucial prevent isomorphism bias in the models, which can occur due to leakage between the training and testing splits, as highlighted by [26].
For each graph, we have limited the maximum number of nodes to twenty, except for Linux, where the limit is ten. Information about the datasets is summarized in Table 7. Mutag contains nitroaromatic compounds, with each node having labels representing atom types. Molhiv and Molpeba contain molecules with node features representing atomic number, chirality, and other atomic properties. Code2 contains abstract syntax trees generated from Python codes. AIDS contains graphs of chemical compounds, with node types representing different atoms. For Molhiv, Molpcba and Linux, we have randomly sampled 1,000 graphs from each original dataset.
Avg. GED uniform cost
Avg. GED non-uniform
#Graphs
Train Pairs
Val Pairs
# Test Pairs
Avg.
[V]
Avg. [E]
Mutag
729
95703
10585
10878
16.01
15.76
11.15
cost 18.57
Code2
128
2926
325
378
18.77
17.77
10.02
16.43
Molhiv
1000
180300
20100
20100
15.01
15.65
11.77
19.86
Molpcba
1000
180300
20100
20100
17.52
18.67
9.58
15.73
AIDS
911
149331
16653
16836
10.97
10.97
7.38
12.07
Yeast
1000
180300
20100
20100
16.59
17.04
10.65
17.74
Linux
89
1431
153
190
8.71
8.35
4.91
7.94
Table 7: Salient characteristics of data sets.
C.2 Details about state-of-the-art baselines
We compared our model against nine sate-offtheeart neural baselines and three combinatorial GED baselines. Below, we provide details of the methodology and hyperparameter settings used for each baseline. We ensured that the number of model parameters were in a comparable range. Specifically, we set the number of GNN layers to 5, each with a node embedding dimension of 10, to ensure consistency and comparability with our model. The following hyperparameters are used for training: Adam optimiser with learning rate of 0.001 and weight decay of 0.0005, batch size of 256, early stopping with patience of 100 epochs, and Sinkhorn temperature set to 0.01. Neural Baselines:
GMN-Match and GMN-Embed Graph Matching Networks (GMN) use Euclidean distance to assess the similarity between graph-level embeddings of each graph. GMN is available in two variants: GMN- Embed, a late interaction model, and GMN-Match, an early interaction model. For this study, we used the official implementation of GMN compute Graph Edit Distance (GED). ISONET ISONET utilizes the Gumbel-Sinkhorn operator to learn asymmetric edge alignments between two graphs for subgraph matching. In our study, we extend ISONET's approach predict the Graph Edit Distance (GED) score. We utilized the official PyTorch implementation provided by the authors for our experiments.?
Phttps://github http://hhhhh.o.oommmmmaaaaaaa//a
21

---

GREED GREED utilizes a siamese network architecture to compute graph-level embeddings in parallel for two graphs. It calculates the Graph Edit Distance (GED) score by computing the norm of the difference between these embeddings. The official implementation provided by the authors
was used for our experiments."
ERIC ERIC utilizes a regularizer to learn node alignment, eliminating the need for an explicit node alignment module. The similarity score is computed using a Neural Tensor Network (NTN) and a Multi-Layer Perceptron (MLP) applied to the final graph-level embeddings of both graphs. These embeddings are derived by concatenating graph-level embeddings from each layer of Graph Isomorphism Network (GIN). The model is trained using combined loss from the regularizer and the predicted similarity score. For our experiments, we used the official Py Torch implementation compute the Graph Edit Distance (GED). The GED scores were inverse normalized from the model output to predict the absolute GED.
SimGNN SimGNN leverages both graph-level and node-level embeddings each layer of the GNN. The graph-level embeddings are processed through a Neural Tensor Network to obtain a pair-level embedding. Concurrently, the node-level embeddings are used to compute pairwise similarity matrix between nodes, which is then converted into a histogram feature vector. A similarity score is calculated by passing the concatenation of these embeddings through a Multi- Layer Perceptron (MLP). . We used the official PyTorch implementation of SimGNN and inverse normalization of the predicted Graph Edit Distance (GED) score to obtain the absolute GED value." H2MN H2MN presents an early interaction model for graph similarity tasks. Instead of learning pairwise node relations, this method attempts find higher-order node similarity using hypergraphs. At each time step of the hypergraph convolution, a subgraph matching module is employed to learn cross-graph similarity. After the convolution layers, readout function is utilized obtain graph- level embeddings. These embeddings are then concatenated and passed through Multi-Layer Perceptron (MLP) to compute the similarity score. We used the official Py PyTorch implementation of H2MN.
GraphSim GraphSim uses GNN, where at each layer, a node-to-node similarity matrix is computed using the node embeddings. These similarity matrices are then processed using Convolutional Neural Networks (CNNs) and Multi-Layer Perceptrons (MLPs) to calculate a similarity score. We utilized the official PyTorch implementation."
EGSC We used the Teacher model proposed by Efficient Graph Similarity Computation (EGSC), which leverages Embedding Fusion Network (EFN) each layer of the Graph Isomorphism Network (GIN). The EFN generates a single embedding from a pair of graph embeddings. The embeddings of the graph pair from each layer are concatenated and subsequently passed through an additional EFN layer and a Multi-Layer Perceptron (MLP) to obtain the similarity score. To predict the absolute Graph Edit Distance (GED), we inversely normalized the GED score obtained from the output of EGSC. We utilized the official PyTorch implementation provided by the authors for our experiments.
Combinatorial Baselines: We use the GEDLIB library for implementation of all combinatorial baselines.
Bipartite [41] Bipartite an approximate algorithm that considers nodes and surrounding edges of nodes into account try to make bipartite matching between two graphs. They use linear assignment algorithms to match nodes and their surroundings in two graphs.
Branch [8], Branch Tight [8] improve upon [41] by decomposing graphs into branches. Branch Tight algorithm is another version of Branch that calculates a tighter lower bound but has a higher time complexity than Branch.
Anchor Aware GED Chang et al. [15] provides an approximation algorithm that calculates a tighter lower bound using the anchor aware technique.
httppp///gggtabb..omm/oo////rrr
6 htttpp//ggthabbb.cmm//aaaaaaaagp
http::///ghhhbbbooo/yyyueegggggp
Computatiommtttio
22

---

IPFP [11] is an approximation algorithm which handles node and edge mapping simultaneously unlike previously discussed methods. This solves quadratic assignment problem on edges and nodes.
F2 [29] uses a binary linear programming approach to find a higher lower bound on GED calculation.
This method was used with a very high time limit to generate Ground truth for our experiments.
C.3 Details about GRAPHEDX
At the high level, GRAPHEDX consists of two components EMBED, and PERMNET
Neural Parameterization of EMBEDg: EMBED, consists of two modules: GNN denoted as MPNN, and a MIPP, The MPNN, consists of K propagation layers used to compute node embeddings of dimension = 10. At each layer k, we compute the updated the node embedding as follows:
Fk+1 (w) UPDATE (x(U),
Σ vEnnr(())
LRI (Z)) 2x)))
(22)
where LRLg is a Reeear-ReLU-LLnear network, with d = 10 features, and the UPDATE, network consists of Gated Recurrent Unit [30]. In case of GED setting under uniform cost and GED setting under non-umin non-uniform cost, we set the initial node features æn(u) 11 following [30]. However, in case of computation of GED with node substitution costs, we explicitly provide the one-hot labels as node features. Given the node embeddings and edge-presence indicator obtained from the adjacency matrices, after 5 layer propogations, we compute the edge embeddings r(e) using MIPo. which is decoupled from M MLPa consists of a Linear-ReLU-Lee the 2d + 1 = 21 dimensional input consisting of forward (xx(u) || (x()) A(u, v)) and backward (x (w) Øx((1 (u) A [U, u|) signals to D 20 dimensions.
network that maps
Neural Parameterization of PERMNET Given the node embeddings xx(() (-) and (*x(-), we first pass them through a neural network Go which consists of Linear-ReLU-Linn ReLU-Linear network transforming the features from d = 10 to N dimensions, which is the number of nodes after padding. Except for Linux where N 10, all other datasets have N = 20. We obtain the matrix C such that Clu, w'] = [< (u)) calar' (n'))l Using temperature 7 = 0.01, we perform Sinkhorn iterations on (xpp(-Cr) as follows for
iterations to get P:
Ps NORMCOL (NoRMRow (Pk-1))
where Po exp(-ep exp(-C/r). Here NORMROW(M)) (T) normalization function and NORMCOL((M)E j] M Mi,j/// M,, denotes the column nor- malization function. We note that the soft alignment P obtained does not depend the GED cost values, as discussed in Appendix B. The soft alignment P for nodes is used to construct soft alignment S for as follows: S[[u, v), (u', e')] Plu, u') Plc, v'] Plu, of) Plu,
M Mi, J/E M[ejj] denotes the row
C.4 Evaluation metrics
Given the dataset S consisting of input pairs of graphs (G, G') along with the ground truth GED(G, G') and model prediction GED(G, ("),,, evaluate the performance of the model us- ing the Root Mean Square Error (RMSE) and Kendall- Tau (KTau) [28] between the predicted GED scores and actual GED values.
MSE: It evaluates how the predicted GED values are from the ground truth. better performing model is indicated by lower MSE value.
MSE
Σ (G
(GED(G, - GED(G,
(23)
S
KTTa:: Selection of relevant corpus graphs via graph similarity scoring is crucial to graph retrieval setups. In this context, we would like the number of concordant pairs N,, (where the ranking of ground truth GED and model prediction agree) be high, and the discordant pairs N_ (where the two disagree) to be low. Formally, we write
KTau N4 N
(24)
(8))
23

---

For the methods which compute similarity score between the pair of graphs through the notion of normalized GED, we map the similarity score back to the GED as GED(G, G') VV+ log(s+ <) where 10-? 7 is added for stability of the logarithm.
C.5 Hardware and license
We implement models using Python 3. 1.. and PyTorch 2.0.0. The training of models and the baselines was performed across servers containing Intel Xcon Silver 4216 2.1OHHz CPUs, and Nvidia RTX A6000 GPUs. Running times of all methods are compared on the same GPU.
24

---

D Additional experiments
In this section, we present results from various additional experiments performed to measure the performance of our model under different cost settings.
D.1 Comparison of performance GRAPHEDX on non-uniform cost Edge-GED
We consider another cost setting where the node costs are explicitly set to O, and a =, a ======2 2. such a case, GRAPHEDX only consists of A (R, Rt' S) and A (R, R' S) terms. To showcase the importance of aligning edges through edge alignment,
generate alternate model, where the alignment happens through the terms x X, X' P) and A th (X,X' X' P). where we set b = and 6 2, and set the edge costs to O. We call this model NodeSwap (w/o XOR), and the corresponding XOR variant as NodeSwap + XOR. In Table 8, we compare the performance variants of GRAPHEDX with NodeSwap (w/o XOR) and the rest of the baselines predict the Edge GED score an non-uniform cost setting. From the results, we can infer that the performance of edge- alignment based model to predict Edge-GEI GEg outperforms the corresponding node-alignment version.
MSE - STD
T
Mutag
Molhiv
Linux
Mutag
Molhiv
Linux
GMN-Maich
11.276 0.143
13.586
0.171
4.893 0.522
0.600
0.562
0.453
GMN-Embed
13.627 0.179
16.482 +: 0.188
4.363 0.420
0.556
0.529
0.484
ISONET
1.468 0.020
2.142 0.023
1.930 0.186
0.846
0.802
0.659
GREED
11.906 0.148
0.136
3.847 0.397
0.588
0.558
0.512
BRIC
1.900 #
0.024
3.361 0.353
0.823
0,805
0.510
SimGNN
3.138 1 0.052
3.771 4.044
5.089 0.524
0.784
0.736
0.410
H2MN
3
0.047
5.443 0.566
0.748
0.741
0.358
GraphSim
4.696 0.076
5,200 0.074
6.597
0.720
0.694
0.316
EGSC
1.71 0.028
2.187 0.025
2.803
0.260 0.260
0.823
0.797
0.608
NodeSwap (w/o XOR)
1,246 + 0.017
1.858 + 0.019
0.997 0.124
0,857
0,814
0.757
NodeSwap XOR
11.984 0.227
11.158 4 0.196
10.959 + 1.116
0.586
0.604
0.321
GRAPHEDX (w/o XOR)
1.174 0.016
1.842 + 0.019
0.976 + 0.115
0,863
0.815
0.764
GRAPHEDX + XOR
1.125 + 0.016
1,855
0.020
0.922 + 0.108
0.866
0.817
0.780
Table 8: Comparison of edge-alignment based GED scoring function with node-alignment based GED
scoring function and state-of-the-arr baselines under the cost setting: a 2, a = 1, 6 = 6 0.
In case of NodeSwap (w/o XOR), we swap the edge costs and node costs, and expect the model to learn the alignments in Edge GED through node alignment only. Green (yellow) numbers report the best (second best) performers.
25

---

D.2 Comparison of GRAPHEDX with baselines on uniform and non-uniform cost setting
Tables 9 and 10 report performance in terms of MSE under uniform and non-uniform cost settings, respectively. Table 11 reports performance in terms of K'Tau under both uniform and non-uniform cost settings. The results are similar to those in Table 3, where our model is the clear winner across all datasets, outperforming the second-best performer by a significant margin. There is no consistent second-best model, but ERIC, EGSC, and ISONET perform comparably and better than the others.
Maiag
Code2
Molhiv
Molpcba
AIDS
Linux
Yeast
GMN Match
0.797 0.013
1.677
0.187
0.020
0.011
0.521
0.010
0.687
0..88
1.175
0.013
GMN-Emnee
1,022 + 0.016
1.358 + 0.104
1,859 + 0.020
1,951 + 0.020
1.044 + 0.013
0.736 1 0.100
1.767 + 0.021
ISONET
1.187 + 0.021
0.879
0.061
1.354 + 0.015
1.106 0.011
1,640 + 0.020
1.185 + 0.115
1.578 = 0.019
GREED
1.398 + 0.033
1.869 +0
1,708 + 0.019
1,550 + 0.017
1,004 + 0.012
1,331 + 00
1423 + 0.015
ERIC
0.719 0.011
1,363 0.110
1,165 + 0.018
0,862 + 0.009
0.731 = 0.008
1.664 4 0.260
0.969 + 0.010
SimGNN
1,471 + 0.024
2.667 + 0.215
1.609 + 0.020
1.456
1.455 0.020
7.232
1.999 + 0.043
H2MN
1.278 +: 0.021
7.240 + 0.527
1.521 + 0.020
1.402 + 0.020
1.114 + 0.015
2.238 + 0.247
1.153 + 0.018
GraphSim
3.139
0.206
2.577 0.064
2.900 0.318
0.030
EGSC
0.765 + 0.011
4,165 + 0.285
1,138
+ 0.016
0.938 + 0.010
0.627 - 0.007
2.411 + 0.325
0.950 + 0.010
GRAPHEDX
0,492 0.007
0.429 0.036
0,781
0.008
0.764 + 0.007
0.565 0.00%
0.043
0.717 0.007
Table 9: Comparison with baselines terms of MSE including standard error for uniform cost setting
(b = b 0 a 1). Green (yellow) numbers report the best (second best) performers.
Maing
Codc2
Molhay
Molpehu
AIEX
Lmux
Yeust
GMN-MMatch
69.210=
0.833
13:472 = 0.900
76.923 1 0.862
23,985 -: 0.224
31.522 = 0.313
21.319
- 2:256
63.179 = 1.127
GMN-Embed
72.495
0.915
13.425 1 1.035
78.254 1: 0,865
28.437 1: 0.268
33.221 -: 0.523
20.591
4: 2
60.949 1. 0.663
ISONET
0.062
0.206
3,451
1
2.781 0.029
5,513
0.299
0.061
GREED
68.732
0.867
11.095 1: 0.773
78.300 1: 0.795
26.057 1: 0.238
34.354 -: 0.557
20.667
1: 2.140
60.652
0.704
ERIC
0.032 1,981
12.767
+ 1.177
3.377 + 0,020
2.057 + 0.020
1,581 + 0.017
7,809 + 0.911
2.341 0.030
SimGNN
5.212
0.07
0.546
0.060
H2MN
3.433
0.053
9.435 + 0.728
3.782 + 0.046
3.396 + 0.046
3,105 = 0.043
5,848 + 0.611
3.678 + 0.046
GraphSim
5,370
0.092
7.405 : 0.577
6.643 + 0.181
3,928
0.053
5,266 0.081
6.815 - 0.628
6,907 0.137
EGSC
1,758
0.026
3.957
0.365
2.371
0.025
0.022
0.023
0.496
ORAPHEDX
1.144 = 0.016
1,478
- 0,118
1800
0.019
1.677 + 0.016
1,252 = 0.014
0,914 0.110
L6603 + 0.016
Table 10: Comparison with baselines in terms of MSE including standard eπror for non- non-uniform cost
setting (b
6 = = 2,a 1). Green (yellow) numbers report the best (second best)
performers.
GED with unilorm cosl
nom-unitorn cost
Mutag
Malpcha
Linux
Yeast
Mutag
Molhiv
Molppba
AIDS
GMN-Matth
0,901
0.876
0.887
0.797
0.824
0.826
0,822
0.606
0.781
0.519
0.596
0.611
0.4%
0.610
EmbeeE
0.887
0.892
0.856
0.723
0.796
0.815
0.815
0.603
0.790
0.607
0.534
0.601
0.531
0.573
ISONET
0.885
0.918
0.878
0.793
0.756
0.786
0.827
0.887
0.908
0.875
0.817
0.755
0.776
0.834
GREED
0.573
0.878
0.757
0.756
0.598
0.522
ERIC
0.999
0.892
0.897
0.820
0.837
0.736
0.868
0.620
0.804
0.895
0.841
0.855
0.633
0.886
SimGNN
0.871
0.856
0.877
0.776
0.775
0.377
0.834
0.862
0.874
0.872
0.804
0.768
0.731
0.843
HDMN
0.578
0.711
0,879
0.781
0.794
0.661
0.848
0.873
0.813
0.875
0.801
0.792
0.681
0.851
GraphSim
0.730
0.601
0.851
0.744
EGSC
0.905
0.815
0.896
0.309
0.850
0.664
0.868
0.912
0.894
0.900
0.836
0.858
0.696
0.884
GRAPHPDX
0.926
0.937
0.910
0.311
01857
0.882
0,336
0,929
0.912
0.912
0.858
0.871
0,875
0.898
Table 11: Comparison with baselines in terms of K'Tau for both uniform and non-uniform cost
settings, where for uniform cost settings costs are b
1,0h
1 and for non-uniform
cost settings costs are 8 = 3, b 1, の 2, 0 = 11 Green (yellow) numbers report the best
(second best) performers.
26

---

D.3 Comparison of GRAPHEDX with baselines with and without cost features
Table 12 reports performance in terms of MSE under non-uniform cost setting, with and without costs used as features to the baselines. We notice that that in some cases, providing cost features boost the performance of baselines significantly, and in few cases, withholding the costs gives slight improvement in performance. However, GRAPHEDX, which uses costs in the distance formulation rather than features, outperforms all baselines by significant margin.
Cost used as features
Mutag
Code2
Molhiv
Molpcha
AIDS
Linux
Yeast
69.210
13.472
76,923
23.985
31.522
21.519
63.179
GMN-Match
X
68.635
12.769
84.113
24.471
31.636
20.255
62.715
72.495
13.425
78.254
28.437
33.221
20.591
60.949
GMN-Emhed
87.581
18.189
80.797
30,276
34.752
20.227
59,941
3.369
3.025
3,451
2.781
5,513
3.031
4.555
ISONET
X
3.850
1.780
3.507
2.906
5.865
2.771
4.861
68.732
11.095
78.300
26.057
34.354
20.667
60.652
GREED
78.878
12.774
78.837
26.188
32.318
23.478
55,985
1.981
12.767
3.377
2.057
1,581
7,809
2.341
ERIC
X
1.912
12.391
2.588
2.220
1.536
11.186
2.161
4.747
5.212
4.145
3,465
4.316
5.369
4.496
SimGNN
2.991
8.923
4.062
3.397
3.470
6.623
4.289
3,413
9.435
3.782
3,396
3.105
5.848
3.678
H2MN X
3.287
14.892
3.611
3.377
3.064
5,576
3,776
5,370
7.405
6.643
3.928
5.266
6.815
6.907
GraphSim
X
4.886
10.257
6.394
3,921
5.538
6.439
6.033
1.758
3.957
2.371
2.1.3
1.693
5,503
2.157
EGSC
X
1.769
4.395
2.510
2.217
1.432
4.664
2.305
GRAPHEDX
X
1.134
1,478
1.804
1.677
1.252
0.914
1.603
Table 12: Comparison of performance (MSE) methods for the non-uniform cost setting when
nodes are initialized with costs as features versus without. For each method, the better performance between with and without cost-feature initialization highlighted in bold for both uniform and non-uniform cost settings. In each column, Green (yellow) numbers report the best (second best) performers.
27

---

D.4 Comparison of GRAPHEDX with baselines with node substitution cost
In Tables 13 and 14, compare the performance of GRAPHEDX with baselines under node substitution cost b The cost setting is 1 = 1 = b = a = の = 1. This experiment includes
only five datasets where node labels present. We observe that GRAPHEDX outperforms all other baselines. There is no clear second- model, but ERIC, EGSC, and ISONET perform better than the others.
Mutag
Code2
Molhiv
Molpeba
AIDS
GMN-Match
1,057 + 0.011
5.224 + 0,404
1.388 + 0.018
1,432 1.52-0..011 0.017
0.868 + 0.007
GMN-Embed
2.159 + 0.026
4.070 + 0.318
3.523 - 0.040
4.657 0.054
1.818 1 0,014
ISONET
0.876 1 0.008
1.129 0.084
1.617 0.020
1.332 0.014
1.142 0.010
GREED
2.876 1 0.032
4,983 0.531
2.923 1 0.033
3,902 1 0.044
2.175
0.016
ERIC
0.886 1 0.009
6.323 0.683
1.537 + 0.018
1.278 0.014
1.602 0.036
SimGNN
1.160 0.013
5.909 0,490
1.888 = 0.031
2.172 = 0.050
+
H2MN
1.277 0.014
6.783 0.587
1.891 0.024
1.666 0.021
1.290 +
GraphSim
1.043 = 0.010
4,708 0.425
1.817 = 0.021
1.748 = 0.021
1,561 = 0.021
EGSC
0.776 + 0.008
8.742 + 0.831
1.273 = 0.016
1,426 = 0.018
1.270 + 0.028
GRAPHEDX
0.441 + 0.004
0.820 0.092
0.792 1 0.009
0.846 1 0.009
0.538 0.003
Table 13:
Comparison with baselines in terms of MSE including standard error, presence of the
node substitution cost, which set to one in uniform cost setting: 8 b = b a a
Green (yellow) numbers report the best (second best) performers.
Mutag
Code2
Molhiv
Molpcba
AIDS
GMN-Match
0.895
0.811
0.881
0,809
01839
Embed
0.847
0.845
0.796
0.684
0.767
ISONET
0.906
0.925
0.868
0.815
0.812
GREED
0.827
0.829
0.822
0.710
0.746
ERIC
0.905
0.847
0,872
0.818
0.815
SimGNN
0.891
0.836
0,864
0.797
0.810
H2MN
0.886
0.818
0.858
0.789
0.802
GraphSim
0.896
0.846
0.860
0.782
0.795
FGSC
0.912
0.802
0.885
0.821
0.832
GRAPHEDX
0.936
0.945
0.913
0.856
0.874
Table 14:
Comparison with baselines in terms of KTTau, in presence of the node substitution cost,
which set to one uniform cost setting: 1 report the best (second best) performers.
b-" a
a
Green (yellow) numbers
D.5 Performance evaluation for edge-only vs. all-node-pair representations
In this section, we compare the performance of using graph representation with two variants of our method. (i) Edge-only (edge - edge): Here, R, R' E ma R) = are computed using only the embeddings of node-pairs that are edges, and excluding non-edges. This means that S' becomes an edge-to-edge alignment matrix instead of full node-pair alignment matrix. (ii) Edge-only (pair -> pair): In this variant, S remains a node-pair alignment matrix, but the embeddings of the non-edges in R, R' E R ((N-)) D are explicitly set to zero. Tables 15 and 16 contain extended results from Table across seven datasets. The results are similar to those discussed the main paper: (1) both these sparse representations perform significantly worse compared to our method using non-trivial representations for both edges and non-edges, and (2) Edge-only (edge - edge) performs better than Edge-only (pair -> pair). This underscores the importance of explicitly modeling trainable non-edge embeddings to capture the sensitivity of GED to global graph structure.
Molag
Codk2
Mollas
Molpeha
AIDS
Linux
Yeas
Edge-only (edge edge)
0.560
0.008
0.791
0,007
Edge-only (psir - puir)
0.596
0.008
0.760
0.058
0.862 1 0.099 0.811 0.008
0.606
0.006
0.44
1 0.056
0.761 0.008
GRAPHEDX
0.492
0.007
0.429
0.088
0.781 4 0.08
0.764 2 0007
0.565
0006
0.354
+ 0.043
0,717 = 0.007
Table 15: Comparison of using all-ooee-pirrs against edge-only representations using MSE for
uniform cost setting. Green (yellow) numbers report the best (second best) performers.
28

---

Muiae
Code2
Molar
Malpcha
AIDS
Linux
Yeast
Edge-only (edge edge)
1.24=
1817 0.341
1.57 1 0009
1,793 0.017
1318 1 00011
0,977 1 0.129
1 0.016
Edge-only (pair pair)
1.276= 0,017
1,79 = 0.136
1.865 + 0.000
1.779
0.017
1.422
0.015
0.992 + 0.114
1.94= 00017
GRAPHEuX
1.134
0.166
0.118
0019
1.77 0016
1252
0.014
0.110
0.016
Table 16: Comparison of using -ll-o-ddddisss against edge-only representations using MSE for
non-uniform cost setting. Green (yellow) numbers report the best (second best) performers.
D.6 Effect of using cost-guided scoring function on baselines
In Tables 17 and 18, we report the impact of replacing the baselines' scoring function with our proposed cost-guided scoring function three baselines across seven datasets for uniform and non-uniform cost settings, respectively. We notice that similar to the results reported in Section 5.2, the cost-guided scoring function helps the baselines perform significantly better in both the cost settings.
Mutag
Code2
Molbiv
Melpeha
Linux
Yeast
GMN-Maathh
0.797 = 0.013
1
1,318 = 0.020
1,073 0:011
0.821
0.010
0.687
= =00088
1.175 = 0:013
GMN-Match
0.684
0.011
0.960
0.092
1.008
0.011
0.858
0.009
0.601
0.007
0.590
0.084
0.849
0.009
Embee
1,022 00016
1,358
0.104
1,859
0.020
1,951 1 0.020
1044
0.013
0.736
0.102
1.767
1 0.021
GMN-Embeed
1011 0.077
1.179
0.098
1.409 +: 0.015
1.881 + 0.019
0,849
0.010
0.577
0.094
1,000
0.017
GREED
1,398 0.033
1,099
0.140
1,708 = 0.019
1,550 + 0.017
1,004
0.012
1.331
0.169
1.433
0.015
GREED
2.133 0.037
1,850
0.156
1.644 - 0.019
1.623 1: 0.017
1,143 1: 0.015
1.297 1 0.151
1.440
= 0.016
GRAPREDX
0,492
0.036
0.781 0.008
0.764
0.006
0.043
0.007
Table 17: Impact of cost-guided distance on MSE in uniform cost setting (6
= 6 = a
a 1).
* represents the variant of the baseline with cost-guided distance. Green shows the best performing model. Bold font indicates the best variant of the baseline.
Mulag
Code2
Mollai
Molpcha
AIDS
Linux
Yeast
GMN-Match
69.210
0.88.
13,472
0.920
76.923 = 0.862
23,985 + 0.224
=1.522=0.55
21.519:22:256
63.179
1.127
GMN-Match
1.592
0.027
2,906 + 0.285
2.162 = 0.024
1,986 + 0.021
1.434 0.017
1.596 0.211
2,056
0.022
GMN-Fimhed
72,495
000++00000 0.915
13,425 + 1,035
78.254 + 0.861
28.437 + 0.268
33,221
+ 0.523
20.591 + 2.136
60.949
0.663
GMN-Bmbedd
0.039
0,289
3,413 0.037
4.286
2,046
1,495
3,800
0.042
GREED
68.722
0.867
11,095 + 0.773
78 900
+ 0.798
26.087
+ 0.238
34.354
0.357
211667
+ 2.14
66652
0.704
GREED
2456 = 0.040
5,429
0.517
3,877
= 0.043
3,807
+ 0.040
2,282
0.028
2,894 : 0.394
3,506
0,038
GRAPREDX
1134 0.016
0.I18
0.19
1,677
0.06
1,252
0314
1.003
0.016
Table 18: Impact of cost-guided distance on MSE in non-uniform cost setting (b = 3,6
1, 1
2, a = 1). * represents the variant of the baseline with cost-guided distance. Green shows the best
performing model. Bold font indicates the best variant of the baseline.
D.7 Results on performance of the alternate surrogates for GED
In Table 19, we present the performance of the alternate surrogates scoring function for GED discussed in B under non-uniform cost settings (b = 3, 1 = 1, و = 2, a = 1). From the results, we can infer that the alternate surrogates have comparable performance to GRAPHEDX however GRAPHEDX outperforms it by a small margin on six out of the seven datasets.
Muing
Code2
Mollay
Molpehs
AIDS
Linux
Yeus!
MAX-OR
L194 : 0.016
1,112 1 0.084
1.987
= 11022
L808 + 0.017
1.347 1 0.014
1.009 : 0.132
1.686 4 0,018
MAX
1,351
1.772
0.122
1.922
L.64 0.017
1.346
0.015
1.435
0.169
1.748
0.018
GRAPHEDX
1.34 = 0.016
1.478 0.118
1804
= 0.019
1677 = 0.016
1,252 + 0.014
0.914
0.110
1.603 = 0.016
Table 19: Comparison of MSE between GRAPHEDX MAX-OR, and MAX. Green (yellow) numbers
report the best (second best) performers.
D.8 Comparison of zero-shot performance on other datasets
In Table 20, compare all baselines with GRAPHEDX zero-shot GED prediction on new dataset. For each method, we select the best-performing models for (AIDS, Yeast, Mutag, Molhiv ). and test each one on the AIDS dataset under non-uniform cost setting.
Train data
GRAPHEDX
Match
Embed
ISONET
GREED
ERIC
SimGiNN
H2MN
GraphSim
EGSC
AIDS
1,252
31.522
33.221
5,513
34.354
1,581
4,316
3.105
5,266
1,693
Yeast
1.746
35.24
38.542
7.631
40.838
2,774
4,851
3.805
8.404
2.061
Motag
2.462
33.918
38.624
7,311
34.936
4.100
5.68
5.117
7.292
4.305
Molhiv 2.127
35.138
38.482
14,806
38,705
2.936
4.525
4.274
6.201
2.444
Table 20:
Comparison of MSE between GRAPHEDX and baselines on zero-shot GED prediction
on the AIDS test dataset under non-uniform cost setting. Green (yellow) numbers report the best (second best) performers.
29

---

D.9 Importance of node-edge consistency
GRAPHEDX enforces consistency between node and edge alignments by design. However, one might choose to enforce node-edge consistency through alignment regularization between independently learnt soft node and edge alignment. However, shown in Figure 21, notice that such non- constrained learning might lead to under-predictte or incorrect alignments. We demonstrate the importance constraining the node-pair alignment 5 with the node alignment P by showing the mapping of nodes and edges between two graphs. The required edit operations for subfigure a) with the constrained S are two node additions {e, f), one edge deletion (d. a), and three edge additions {(a. f), (e, d), (e. f) Assuming that each edit costs one, the true GED is 6. However, in subplot b), S is not constrained, and the edit operations with the lowest cost are two node additions {e. f] and two edge additions {(a, f), (e, f)}. This erroneously results in GED of 4.
G
G¹
G
G
a
a
b
b
C
(a) Constrained
(h) Unconstrained
Figure 21: Node and edge alignment with constrained and unconstrained alignment S. A dashed edge represents the deleted edge. Grey edges represent added edges.
Further, in Table 22, we compare the performance enforcing node-edge consistency through design (GRAPHEdX), and through alignment regularization (REG). Following the discussion in Section 4.2, such a model also exhibits variant with XOR, called REG-xor. We notice that GRAPHEDX even outperforms such the described model in 4 out of 6 cases. We also notice that REG-xor outperforms GRAPHEDX in the other two cases. However, the above example shows tendency to learn wrong alignments which in turn gives wrong optimal edit paths.
GED with uniform cost
GED with non-uniform cost
Mutag
Mutag
Molhiv
REG
0.536
0.576
0.848
1.162
1,488
1.877
REG-xor
0.513
0.587
0.826
1.309
1.400
1.711
GRAPHEDX
0.492
0.429
0.781
1.134
1.488
1.804
Table 22: Comparison of alignment regularizer usage versus no alignment regularizer usage on
uniform cost GED, Measured by MSE. Green (yellow) numbers report the best (second best) performers.
30

---

D.10 Comparison of nine possible combinations our proposed set distances
In Tables 23 and 24, compare the performance of nine possible combinations our proposed set distances for uniform and non-uniform cost settings respectively. Results follow the observations in Table 2, where the variant with XOR-DIFFALIGN outperforms those without it.
Edge eăit
Node edit
Muiag
Cose2
Melhiv
Mojpela
AIDS
Lines
Yeart
DIRFALIGN
DIFF ALIN
0.579 + 0.007%
0.740 =000585
0.800 + +.0088
0.778 + 0.0075
0.601 : 00.0063
0.494
0.0575
0.728
0.0071
DIEFALION
0,557 1 0.0073
0,742 1: 0.6122
0.506 1 000088
0.779 1: 0.0076
0.597 1. 0.0063
0.452
0,0614
0.747 1: 0.0078
DUVALIUN
XOR
0,538
0.0072
0.719 0.0561
0.794 + 0.0883
0.777 + 0.0075
01550
0,0000
0.356
0.0512
0.750
0.0075
ALIoNDaY
AuvALION
0.0072
0.13 030867
00005
000024
0.0073
ALONDDPR
0.929
000886
0.0075
+00033
0.605
ALIONDIFF
0.507
XOR
0.492 00006
0.429
01084
0.0074
0.466 039494
0.730 0.0072
XOR
DIRALIGN
0.510
0.0067
0.634
0.0522
0.781
0.0044
0.0073
0.574
0.0000
0.332
0.0430
0.717
0.0072
XOR
XOR
0,530
0.0074
1,588 0.1299
0.807
2. 00004
0.764 1 0.0003
0.564
0.0089
0.354 0,0427
0.721
0.0076
GRAPFEDX
0.492 000I6
0.42 + C033S
0.781
+ 00084
0.764
00003
U.SGS
0.002
0,35 03427
0.717 = 00072
Table 23: Comparison of MSE for nine combinations of our neural set distance surrogates under
uniform cost settings. The GRAPHEDX model was selected based on the best MSE the validation set, while the reported results represent MSE on the test set. Green (yellow) numbers report the best (second best) performers.
Edge
Molpotu
DIFF
DIEATIGN
2 0015
1:41
1235 00099
0.0188
1.4122000 0.0146
0.988
0.1.0
1:630=
DIFFALION
AIFGNDDFF
1,211 0.0064
2.116 1. 0.1588
1,887 0.0199
1.811 1. 0.0174
1.319 0.0140
1,078
0.1168
1,791 0.01RS
DEVALIEN
XDR
1146 00.154
19966 +014877
1800 + 00188888
1,822
+ 0.0176
1.381 + 0.0014
1,049
0.1182
1,737 0.0172
ALIGNDIFF
DIFFALION
1,85 0.0159
1689 1.0.2100
1874 1 0.0000
1.758 1 0.0169
1.391 1 0.0114
0.914
0,1099
1,633 1: 0.0163
ALIGNDIFF
ALIGNDur
1,338 2 0.0178
1488
2 0.1222
1903 4: 040264
1,899 4: 0.0179
1.326 2 0,0141
0.1335 1,258
1,731 0.017
ALIGNDUR
XOR
1.196 0.0164
1.741 +01115)
1,570 0.019
1.815 + 0.0144
1.374 0.0146
1,128
0.1330
1.802 + 0.0194
XOR
ALIGNDIFF
L134 0.0158
1.478 0.11178
1.722 0.0002
1,742 1 0.0168
1,252 0.0136
1,073 0.1211
1.639 0.0162
XOR
DIVALIGN
1,148
1.004 0.0912
1,603 0.0160
XOR
1,55 001995
0OT5S
1478
1X04 00002
0.10P9
1.605 0.000
Table 24: Comparison of MSE for nine combinations under non-uniform cost settings. The
GRAPHEDX model was selected based on the best MSE on the validation set, while the reported re-
sults represent MSE on the test set. Green (yellow) numbers report the best (second best) performers.
31

---

D.11 Comparison of performance of our model with baselines using scatter plot
In Figure 25, illustrate the performance of model compared the second-best performing model, under both uniform and non-uniform cost settings, by visualizing the distribution of outputs of the predicted GEDs by both models. We observe that predictions from model consistently align closer to the = z line across various datasets showcasing lower output variance as compared the next best-performing model.
20
1 1.
Prodicted
20
GmohBaXX
Prodicted
50
GraphEalX
Proflcted
GraphBix
Prodicted
GraphEax
10-
20
10
20
30
Ground Truth
Ground Truth
Ground Truth
Ground Truth
(a) Mutag uniform cost
(h) Mutag non-uniform
(c) Code2 uniform cost
(d)
Code2 non-uniform
cost
cost
40
EGSC
T
ERIC Bale ao Reeder
ERIC
Prodicted
GraphBBXX
Predicted
Glophitx
Predicted
Preficted
20
50
-0
20
50
10
20
20
40
Ground Truth +
Ground Truth
Ground Truth
Ground Truth
Molhiv uniform
(f) Molhiv non-uniform cost (g) Molpcha uniform (h) Molpcha non-uniform
cost
Figure 25: Scatter plot comparing the distribution of the predicted GED of our model with the next best best-performing model across various datasets under both uniform and non-uniform cost settings.
D.12 Comparison of performance of our model with baselines using error distribution
In Figure 26, we plot the distribution of error (MSE) of our model against the second-bes performing model, under both uniform and non-uniform cost settings. We observe that our model performs better, exhibiting higher probability density for lower MSE values and a lower probability density for higher MSE values.
1..4
GrephaiXX
0.6
BIKET Griandx
Gouplaiax
1SONRT
Probabainyy
0.3
Probability
Probabiiitty
0.4
Probability
0.4
0.2
0.2
0.8
0.00
20
Squared Error
Squared Ervor
Squared Error
Squared Error
(a) Mutag uniform cost
Mutag
non-uniform
(c) Code2 uniform cost
(d)
Code2
non-uniform
cost
cost
To.1-
Gnjares
Frzsn
0.4
Griaati
0.6
GripntxX
Bkin
0.4
Griptbck
Probathti
0.5
Probubilite
0.3
Probsbilits
0.8-
Probabillit
0.3
0.2
0.2
0.2
82
0.00
0.5
1.0
1.5
2.0
0.00
2.5
5.0
7.5
0.0
0.5
1.0
0.00
Squared Error
Squared Eeror
Squared
Error
Squared Error
(e) Molhiv uniform cost
(f) Molhiv non-uniform
(g) Molpeha uniform cost
(h) Molpcha non-uniform
cost
cost
Figure 26: Error distribution of our model compared to the next best-performing model across various datasets under both uniform and non con-uniform cost settings.
32

---

D.13 Comparison of combinatorial optimisation gadgets for GED prediction
IPFP
F2
Branch
Anchor-aware
GED
Bipartite
GraphEdX
Branch-tight
100
100
100
MSS
10
MSE
MSE
10
MS
10-1
10-3 10 10"
10-1
10-110-1
10-1
10
10-2 10
Time Limit (sne)
Time Limit (sec)
Time Limit (sne)
Time Limit (sec)
(a) Mutag uniform cost
(b)
Mutag non-uniform
(c) Code2 uniform cost
(d)
Code2
non-uniform
cost
cost
100
100
100
MSB
10
MSB
MSE
MSB
10
10
10
10
10-
10"
10 100
Time Limit (sec)
Time Limit (sec) +
Time Limit (sec) +
Time Limit (sec) +
(c) AIDS uniform cost
(f) AIDS non-uniform cost
(g) Linux uniform cost
(h) Linux non-uniform cost
Figure 27: Performance of combinatorial optimization algorithms on various datasets under both uniform and non-uniform cost settings is evaluated. We plot MSE against the time limit allocated to the combinatorial algorithms. Additionally, we include the amortized time of our model and its MSE
We compare the runtime performance of six combinatorial optimization algorithms described in Appendix C (ipfp [11]. anchor-aware GED [15], branch tight [8], F2 [29]. bipartite [41] and branch [8]. We note that combinatorial algorithms are slow to approximate the GED between two graphs Specifically, GRAPHEDX often predicts the GED in ~ 10 seconds per graph, however, the performance of the combinatorial baselines are extremely poor under such time constraint. Hence, execute the combinatorial algorithms with four different time limits per graph: ranging from 10-2 seconds (100x our method) to 10 seconds (10xx x our method).
In Figure 27, we depict the MSE versus time limit for the aforementioned combinatorial algorithms under both uniform and non-uniform cost settings. We also showcase the inference time per graph of our method in the figure. It is evident that even with time limit scaled by 10"x, most combinatorial algorithms struggle achieve a satisfactory approximation for the GED.
33

---

D.14 Prediction timing analysis
In Figure 28 illustrates the inference time per graph of model versus under uniform cost settings, averaged over ten runs. From the figure, we observe the following (1) GRAPHEDX outperforms four of the baselines in terms of inference time, and comparable ISONET's inference time (2) GMN-Embed, GREED, ERIC, and EGSC run faster compared to all other methods due to lack of interaction between graphs, which results in poorer performance predicting the GED.
Matag
10
Mothiv
Molpcha
Figure 28: GED inference time comparison between our model and baselines. We notice that GRAPHEDX is consistently the third-fastest amongst all baselines. Although GREED have the lowest inference time, GRAPHEDX has much lower MSE consistently.
and
D.15 Visualization (optimal edit path) + Pseudocode
In Algorithm 1, we present the pseudocode to generate the optimal edit path given the learnt node and edge alignments from GRAPHEDX. Figure 29 demonstrates how the operations in the edit path can be utilized to convert G to G".
AddEdgr(a. O AddEdge(e, d) AddEdgefe, O
AddNodele) AddNadeis.
DeleteEdge(a,
Figure 29; An example the sequence edit operations performed to convert one graph into another.
Algorithm 1 Generation of Edit Path
1: function GETEDITPATH(G, G', mG.
2:
P. S.S4 + GRAPHEDX(G, G', GGG,G,,,GGG.. .mG. ne')
3:
P. + HUNGARIAN(P), HUNGARIAN(S)
4:
o = NewList()
5:
for (u, [N] x [N] do
6:
if P(u, = and 7o [d] 0 and nor [v] then
7:
Addltem((,,DDNoDDEEI
8:
for (u, (w,,') .²) E [[N] [N] [[N] x [N]] do
9:
if S", v), (u', v') [0]]= and A Ju, r| = and A'(u', v'] = then
10:
AddItem(o.ADDEDGrr (T,, v), (u', (
v)))
11:
and A lu, o] and A A'lu,, fuf,e v'] = then
12:
Andltem(o.DELEDGGEE
v))
13:
for (u, U) E [ x [ do
14:
if P(u, v] = and 7G [z] and no [b] 0 then
15:
Ad
16:
return
34

---

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: In Section 5, we present experiments and results support the claims made in the abstract and introduction.
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 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. is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer:
[Yes]
Justification:
In Conclusions, discuss the limitations of our work.
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 on 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 to 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 faimess..
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 't acknowledged in 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
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In Appendix B, we provide proof for the theoretical results mentioned in the paper.
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.
35

---

All assumptions should be clearly stated or referenced in 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 to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proofs provided in appendix or 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 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: We provide code and dataset in the supplementary material with instructions to reproduce the results.
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 be 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 or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS 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 new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.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 (c.g.. with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to 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 to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: In the supplementary material, we provide code for our model, baselines, and experimental datasets, well instructions for reproducing the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not
36

---

reproducible, they including code, unless this is central to the contribution (e.g., for new open-souree benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ /nips. cc/ cctpublic/ /ellicc//uiis///ee Suuee/umm ssiion wwsssssoosllli 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. If only subset of experiments 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 much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: In Appendix C, we provide training details, such as hyperparameters and optimizer used.
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 a 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, 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: [Yes]
Justification: Along with Mean Squared Error also provide Standard deviation report the statistical significance of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
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 the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. 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 reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question: 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?
Answer: [Yes]
37

---

Justification: In Appendix C we provide information on hardware used for running experi-
ments.
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, or 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 in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: attpps:/neuuigg: /twuurrurpp.../ httpp.....e/ee cc/ccc///////. http//uulc//tttct/ttee ines?
Answer: [Yes]
Justification: Yes, the research conducted in the paper conforms, in every aspect, with Neurips Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction). 10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In Appendix A we have discuss broader impact of our work. Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeen 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 partieular 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 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification: We do not any such dataset/method.
Guidelines:
The answer NA means that the paper poses no such risks.
38

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to 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 (e.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: We cite and provide URLs for datasets and codes that for the experi- ments.
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 or dataset.
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 are 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 license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide our code and dataset with README file having instructions on how run the experiments.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/model 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
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 sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve such research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing 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 the main paper.
39

---

According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve such research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Depending 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 we 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.
40


Reviews:
[{"review_id": "Otdqcikzbe", "reviewer": "Reviewer_eEwY", "summary": "This paper proposes GRAPHEDX, a neural model that learns to estimate the graph edit distace among a pair of graphs, not only in the case of equal and symmetric costs for edit operations, but in the case of unequal costs specified for the four edit operations. The core of the proposal represents each graph as a set of node & edge embeddings, designs neural set divergence surrogates based on those embeddings, and replaces the QAP term corresponding to each operation with its surrogate. The method learns alignments to compute surrogates via a Gumbel-Sinkhorn permutation generator while also ensuring consistency between the node and edge alignments and rendering them sensitive to the presence and absence of edges between node-pairs.", "questions": "Q: What is the cost of training and estimation?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "S1. Addresses a gap in the field that previous works have left open.\nS2. Outpeforms previous effort in both equal-cost and unequal-cost settings.", "weaknesses": "W1. The cost of training and estimating is not shown.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> *What is the cost of training and estimation?*\n\nIn Appendices F.11 and F.12, we discuss the computational cost of GED estimation. The following table presents the total training time and the amortized per-graph pair inference time (in milliseconds) for different methods on all dataset. The training time includes variations due to different numbers of training epochs for each method, under the same early stopping criteria. The inference time is averaged across all graph pairs and does not include data preprocessing times, which may vary across methods. In the global PDF, we provide the histogram of per-graph pair inference time (Figure E).\n\n||Dataset| GRAPHEDX | GMN-Match | GMN-Embed | ISONET | GREED | ERIC  | SimGNN | H2MN  | GraphSim | EGSC  |\n|------|----|----------|-----------|-----------|--------|-------|-------|--------|-------|----------|-------|\n| Training Time (min) | Mutag | 422      | 465       | 44        | 238    | 50    | 1185  | 556    | 2268  | 415      | 166   |\n|                     | Code2   | 38       | 41        | 5         | 8      | 6     | 37    | 102    | 60    | 28       | 25    |\n|                     | Molhiv  | 479      | 877       | 58        | 379    | 95    | 1480  | 1058   | 1546  | 780      | 401   |\n|                     | Molpcba | 847      | 986       | 97        | 489    | 112   | 1605  | 1358   | 1125  | 1135     | 325   |\n|                     | AIDS         | 388      | 748       | 70        | 107    | 63    | 1179  | 1343   | 3123  | 705      | 426   |\n|                     | Linux        | 39       | 11        | 2         | 4      | 2     | 26    | 10     | 24    | 7        | 4     |\n|                     | Yeast        | 390      | 936       | 90        | 228    | 115   | 2801  | 642    | 1449  | 464      | 827   |\n| Inference Time (ms) | Mutag | 0.127    | 1.945     | 0.011     | 0.105  | 0.007 | 0.008 | 0.869  | 0.763 | 0.423    | 0.008 |\n|                     | Code2   | 0.257    | 1.638     | 0.16      | 0.28   | 0.169 | 0.205 | 0.862  | 0.449 | 0.465    | 0.189 |\n|                     | Molhiv  | 0.088    | 2.78      | 0.009     | 0.092  | 0.005 | 0.006 | 1.18   | 0.376 | 0.304    | 0.005 |\n|                     | Molpcba | 0.089    | 1.975     | 0.011     | 0.094  | 0.006 | 0.006 | 0.831  | 0.488 | 0.297    | 0.005 |\n|                     | AIDS         | 0.071    | 1.512     | 0.009     | 0.072  | 0.007 | 0.007 | 0.672  | 0.289 | 0.263    | 0.006 |\n|                     | Linux        | 0.51     | 1.782     | 0.357     | 0.471  | 0.349 | 0.477 | 1.275  | 0.627 | 0.705    | 0.374 |\n|                     | Yeast        | 0.073    | 1.537     | 0.012     | 0.076  | 0.008 | 0.008 | 0.65   | 0.297 | 0.266    | 0.007 |\n\nWe observe that GraphEDX is generally faster in training than GMN-Match, ERIC, and H2MN, and is comparable to SimGNN and GraphSIM. In terms of inference, GraphEDX is significantly faster than GMN-Match with cost-guided distance, which outperforms all other baselines in terms of accuracy (see Table 3 vs. Table 2 in the main paper), but is slower than ERIC and EGSC. However, the efficiency of ERIC and EGSC comes at the cost of lower accuracy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ap27zgTspZ", "reviewer": "Reviewer_htic", "summary": "This paper proposes GRAPHEDX, an innovative neural model that deftly handles Graph Edit Distance (GED) calculations with customizable edit costs. By representing graphs as rich sets of node and edge embeddings and using a Gumbel-Sinkhorn permutation generator, GRAPHEDX captures the subtle nuances of graph structure that influence edit distances. Experiments across diverse datasets demonstrate GRAPHEDX's superiority, with the model consistently outperforming state-of-the-art baselines by significant margins, especially in scenarios with unequal edit costs.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The handling of GED metric with unequal cost is a timely and under-explored topic. In real world, many use cases involving GED need to consider such unequal cost scenario.\n2. Rigorous evaluation on both the accuracy and efficiency (runnign time) is performed, showing that the proposed method achieves high accuracy while maintaining efficiency.\n3. The current model may not fully address richly attributed graphs with complex node and edge features.\nTo show the transfer learning ability, I encourage the authors to try training on one dataset and testing on another. This would reduce concern on overfitting to one particular dataset\nThe paper is well-written.", "weaknesses": "1. The current model may not fully address richly attributed graphs with complex node and edge features.\n2. To show the transfer learning ability, I encourage the authors to try training on one dataset and testing on another. This would reduce concern on overfitting to one particular dataset", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">  *The current model may not fully address richly attributed graphs with complex node and edge features.*\n\nWe did not perform any experiments on node and edge features, but we can encode node feature and edge features in our models. Specifically, node features can be encoded during feature initialization and edge features can be encoded in the message passing step Eq. 24, page 22 as $LRL _{\\theta} (x _k(u), x _k(v), \\text{EdgeFeature} _{uv})$ instead of $LRL _{\\theta} (x _k(u), x _k(v))$.\n\n\n>  *To show the transfer learning ability, I encourage the authors to try training on one dataset and testing on another. This would reduce concern on overfitting to one particular dataset.*\n\nIn the following, we show the inference MSE of different models trained on the AIDS, Yeast, Mutag, and Molhiv datasets, when tested on the AIDS dataset. Analyzing the table column-wise, we observe the expected drop in performance across all methods when using models trained on datasets other than AIDS. Additionally, within each individual row, GraphEDX consistently outperforms all baselines, regardless of the training dataset. In Table C of the global pdf, we present comparison with all baselines.\n| Test  Dataset | Train Dataset | GraphEDX | ERIC  | SimGNN | H2MN  | EGSC  |\n|---------------|---------------|----------|-------|--------|-------|-------|\n| AIDS          | AIDS          | 1.252    | 1.581 | 4.316  | 3.105 | 1.693 |\n| AIDS          | Yeast         | 1.746    | 2.774 | 4.581  | 3.805 | 2.061 |\n| AIDS          | Mutag         | 2.462    | 4.1   | 5.68   | 5.117 | 4.305 |\n| AIDS          | Molhiv        | 2.127    | 2.936 | 4.525  | 4.274 | 2.444 |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gW1ZTChLjJ", "reviewer": "Reviewer_81fW", "summary": "This paper studies the approximation of non-uniform Graph Edit Distance (GED) using graph neural networks. It considers four types of edit operations with different costs: edge deletion, edge addition, node deletion, and node addition. The paper proposes explicitly accounting for the costs assigned to each type of edit operation to adapt to both uniform and non-uniform cost settings. Moreover, it introduces node-pair embeddings for connected and disconnected node pairs within graphs as edge and non-edge embeddings. It computes the node and node-pair alignments through three types of distance functions to approximate the considered operations. Experiments on real-world datasets under a variety of edit cost settings show that the proposed method outperforms selected baselines on chosen metrics.", "questions": "* To what extent does the performance of the proposed model rely on the number of refinement iterations of the Gumbel-Sinkhorn network? Can the authors provide an analysis in this respect?\n* To incorporate non-uniform edit costs into baselines, the author include the edit costs as initial features in the graphs. However, most baselines such as Eric [1] and SimGNN [2] only rely on the supervision signal during training. I wonder whether such an initialization is necessary and beneficial.\n* The results regarding the inference time in Figure 26 seem illogical to me. Given that the complexity of Eric [1] is $\\mathcal{O}(m + d_{ms}d^{′}T )$ in the inference stage (see the original paper), while the proposed method is at least $\\mathcal{O}(k \\cdot N^2)$, where $k$ is the number of refinement iterations, $N$ is the number of nodes. Can the authors provide the complexity analysis of the propose method?\n\n\nReferences\n\n[1] Wei Zhuo and Guang Tan. 2022. Efficient Graph Similarity Computation with Alignment Regularization. In Advances in Neural Information Processing Systems, Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.). https://openreview.net/forum?id=lblv6NGI7un\n\n[2] Yunsheng Bai, Haoyang Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (2019).", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* This paper studies an important task with many real-world applications.\n* The authors propose generating learnable embeddings for disconnected node pairs, which is new to me.\n* Extensive experiments have been conducted.", "weaknesses": "* The clarity of the paper should be improved. For example:\n  * What are the differences between the pad indicator $q$ and  $η$? Are they inconsistent notation?\n  * The paper is not self-contained. The related work should be in the main paper rather than in the appendix. Additionally, some related work, such as [1], which clearly highly influences this paper, is missing.\n* The technical contribution of this paper is somewhat limited, as it directly uses MPNNs for representing nodes and the Gumbel-Sinkhorn network to establish alignment.\n* The size of the graphs used in the experiments is relatively small (with at most 20 nodes) compared with the graphs used in other neural approaches.\n* Restricting the model parameters for the baselines does not seem fair to me, since the proposed model heavily relies on the iterative non-parameterized Gumbel-Sinkhorn refinement.\n* The size of the graphs used in the experiments is relatively small, so it is unclear if the proposed model can scale to graphs with, say, one or two hundred nodes. Moreover, since obtaining training data for GED is nontrivial, it is also unclear how the proposed model performs when the supervision signal is not the optimal GED value. I suggest that the authors conduct experiments on commonly used GED datasets with larger graphs, such as the IMDB dataset provided in [2], or use large synthetic graphs following [3].\n\n\nMinors:\n\n* There are some typos (Line 278 Additiional -> Additional). Some sentences are missing periods, for example, in Lines 273, 551.\n* The caption of tables should be above the tables.\n\nReference\n\n[1] Piao C, Xu T, Sun X, et al. Computing Graph Edit Distance via Neural Graph Matching[J]. Proceedings of the VLDB Endowment, 2023, 16(8): 1817-1829.\n\n[2] Yunsheng Bai, Haoyang Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (2019).\n\n[3] Roy, Indradyumna et al. “Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks.  NeurIPS 2022.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">  *differences between  𝑞 and 𝜂*\n\nYes, we apologize for the mistake, $q$ = 1-$\\eta$. The notation was redundant; only one is needed -- we will correct it.\n>  *some related work [1] is missing.*\n\nSince NeurIPS allowed including the Appendix with the main paper, we placed the related work there. If accepted, we will use the extra page to move the related work into the main paper.\nWe also evaluate our method against GEDGNN [1] in both equal and unequal cost setups, below.\n\n\n|MSE||Mutag|Code2|Molhiv|Molpcba|Aids|Linux|Yeast|\n|:-|:-|:-|:-|:-|:-|:-|:-|:-|\n|Equal Cost|GEDGNN|33.281|31.124|39.163|12.419|20.006|10.521|32.128|\n|Equal Cost|GRAPHEDX|0.492|0.429|0.781|0.764|0.656|0.354|0.717|\n|Unequal Cost|GEDGNN|152.299|107.62|163.377|73.872|65.646|27.611|163.26|\n|Unequal Cost|GRAPHEDX|1.134|1.478|1.804|1.677|1.252|0.914|1.603|\n\nWe observe that GraphEDX outperforms GEDGNN across all datasets. GEDGNN relies on node-level alignment supervision, which is unavailable in our setup, thereby degrading its performance. Additionally, as expected, GEDGNN, which is not designed to handle unequal cost setups, performs better at minimizing MSE in equal cost setups.  \n\n>  *technical contribution.*\n\nGraphEdX is eventually simple and intuitive to describe, yet the judicious combination of MPNN and Sinkhorn networks significantly improves inductive bias. Our work is the first neural GED model that accounts for generic costs, requiring a deep understanding of GED costs and careful design of surrogate functions. Our experiments show that our method performs particularly well in non-uniform edit cost settings, highlighting the effectiveness of our set divergence guided scoring. Additionally, our method provides clear guidance on combining embeddings and alignments (DiffAlign, AlignDiff, XOR-DiffAlign) and uniquely enforces consistency between node and edge permutations, which is a significant contribution to the community.\n\n>  *The size of the graphs  is small.*\n \n Please refer to global response.\n>  *#parameters for the baselines*\n\nIn the table below, we compare the model performances on the Mutagenicity dataset under equal cost, across the original number of parameters and our reduced parameter setting. Performance is evaluated in terms of MSE, with the numbers in parentheses indicating the number of parameters. We observe that GraphEDX outperforms all baseline models across both parameter settings. Additionally, in most cases, the baselines perform comparably across both settings, except for GREED in the equal cost setting, where there is approximately a 40% reduction in error, albeit at the cost of a 44x increase in the number of parameters. Table (B) in the global PDF provides comparisons on other baselines, for both equal and unequal costs.  \n|Mutagenicity|GraphEDX|GMN-Match|GREED|ERIC|H2MN|EGSC|\n|-|-|-|-|-|-|-|\n|Our|**0.492** (3030)|0.797 (2270)|1.398 (2434)|**0.719** (5902)|1.278 (2974)|0.765 (4248)|\n|Original|**0.492** (3030)|**0.686** (19936)|**0.807** (107776)|0.975 (45509)|**1.147** (18103)|**0.760** (54753)|\n\n\nBenchmarking across different baselines is challenging due to the large variation in the number of parameters (e.g., GREED has 2x more parameters than ERIC). Performance can vary with changes in the depth and width of different layers, making it difficult to create a standardized comparison platform without keeping the embedding dimensions and the number of GNN layers the same across all baselines. For example, in the restricted parameter setting, ERIC has a lower MSE than GREED, while in the original parameter setting, where GREED uses 2x the parameters of ERIC, it has a lower MSE than ERIC. This could be due to capturing spurious correlations rather than improving inductive bias. \n\n\n>  *analysis on Sinkhorn iterations*\n\nThe following table shows the effect of varying the number of Sinkhorn iterations, under the equal cost setting on the Mutag dataset.\n\n|#Sinkhorn Iterations|1|2|3|4|8|12|16|20|\n|:-:|-|-|-|:-:|:-:|:-:|:-:|:-:|\n|MSE|13.531|7.889|2.42|1.422|0.684|0.529|0.498|0.492|\n\nWe observe that within 12 iterations, it reaches 93% of the optimal MSE reported at 20 iterations.\n\n>  *edit costs as initial features*\n\nIn order to ensure high-quality benchmarking, we allowed all baselines to leverage the knowledge of edit costs as much as possible, as they were not primarily designed for non-uniform edit costs. We had believed that this improves their inductive bias.\nAs suggested by the reviewer, we performed an ablation study on the initialization of different baselines. The following table shows the results for Mutag and code2 (Fig D in global-pdf shows the rest). We observed that there is no consistent winner among different type of initializations. For ERIC and SIMGNN, in majority of cases, the setting without cost initialization is very marginally better than cost based initialization. GraphEdX outperforms all baselines.\nIn the final draft, we will take the best performance across both settings for each baseline.\n\n||Mutag|Code2|\n|-|-|-|\n|ERIC (init)|1.981|12.767|\n|ERIC (no-init)|**1.912**|**12.391**|\n|SimGNN (init)|4.747|**5.212**|\n|SimGNN (no-init)|**2.991**|8.923|\n|EGSC (init)|**1.758**|**3.957**|\n|EGSC (no-init)|1.769|4.395|\n|GraphEDX|1.134|1.478|\n\n>  *inference time in Figure 26 seem illogical*\n\nWe are thankful to the reviewer for spotting this.  Upon closer inspection, we found that the inference times reported in Figure 26 included data batching time. Methods like GMN-Match, EMN-Embed, ISONET, and GraphEDX use numpy-CPU-based batching, while others use the PyTorch Geometric Data batching API, which is slower for our datasets. This was unfair to ERIC and possibly other baselines. To ensure a fair evaluation, we removed the data batching time and tracked only the forward pass times for each model. The updated histograms in Figure E of the global PDF show that ERIC is one of the fastest baselines. Additionally, GraphEDX is significantly faster than GMN-Match and H2MN, and comparable to ISONET.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
> *Evaluation on larger graphs*

As has been correctly pointed out, obtaining training data for GED is nontrivial for larger graphs, and baselines have often used noisy GED values for supervision. Since our work addresses asymmetric cost-sensitive GED for the first time, we preferred to use exact optimal GED values to better evaluate our proposal and the baselines. However, we agree that our proposal should also be evaluated with larger graphs.

We generate large graphs by randomly selecting graphs of size 60-80 from the AIDS dataset and appending them to graph pairs in our dataset. This results in graphs averaging 80 nodes, with a maximum of 100 nodes, introducing some noise to the unequal cost GED values.

The following table shows the results for our methods and the baselines, where we use the number of parameters originally specified by each baseline. We observe that GraphEDX has the lowest MSE, followed by ISONET, H2MN and ERIC. Table A in the global pdf reports numbers on all methods in this setting.
|                 | GraphEDX | GMN-Match | ISONET | ERIC   | H2MN   | EGSC   |
|-----------------|----------|-----------|--------|--------|--------|--------|
| MSE:  | 3.986    | 52.156    | 8.324  | 24.584 | 6.695 | 43.467 |


Moreover, as suggested by the reviewer, we evaluate the scalability on large graphs with more than 20 nodes. The following table presents the amortized inference time (in milliseconds) per graph pair, demonstrating that our method can easily scale to large graphs.
|Inference Time (ms)| \|V\|=20 | \|V\|=30 | \|V\|=50 | \|V\|=70 | \|V\|=100 | \|V\|=150 | \|V\|=200 |
|:-|:-|:-|:-|:--|:-|:-|:-|
|GRAPHEDX|0.165|0.165|0.200|0.290|0.768|4.616|10.485|


To further evaluate performance on larger graphs, we used a pretrained model on Ogbg-Code2 dataset graphs with fewer than $|V| = 20$ nodes and tested it on graphs with nodes  $|V| \in (20, 50]$  from the same dataset, with an average size of 30. The following table shows the results in terms of MSE under the unequal cost setup:
| | GraphEDX | GMN-Match | ISONET | SimGNN | H2MN  |
|-|-|-|-|-|--|
| Code2-(20,50] | 6.302 | 53.297 | 7.052  | 48.072 | 9.486 |

We observe that our method outperforms all the baselines, with ISONET and H2MN being the second and third best performers respectively. Table A in the gobal pdf reports numbers on the remaining baselines.

Meta-review: The paper proposes a neural-based graph edit distance (GED) estimator that can work with general costs specified for the four edit operations (edge deletion, edge addition, node deletion, and node addition). The method is evaluated on different combinations of datasets and edit cost settings, showing consistent improvement with respect to existing GED estimation heuristics.

This paper provides an ingenuous method to a NP-hard problem, which seems to work in practical applications. Furthermore, the authors positively reply to each (valid) concern raised by the reviewers during the rebuttal. I recommend acceptance.
Decision: Accept (poster)