Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval
Authors: Ashwin Ramachandran
Vaibhav Raj
Indradyumna Roy
Soumen Chakrabarti
Abir De
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Neural Networks
Graph Retrieval
Primary area: graph_neural_networks
TL;DR: Improved neural interaction modelling of graph pairs for subgraph matching based retrieval.

Abstract: Graph retrieval based on subgraph isomorphism has several real-world applications such as scene graph retrieval, molecular fingerprint detection and circuit design. Roy et al. [35] proposed IsoNet, a late interaction model for subgraph matching, which first computes the node and edge embeddings of each graph independently of paired graph  and then computes a trainable alignment map. Here, we present $\texttt{IsoNet++}$, an early interaction graph neural network (GNN), based on several technical innovations. First, we compute embeddings of all nodes by passing messages within and across the two input graphs, guided by an *injective alignment* between their nodes. Second, we update this alignment in a lazy fashion over multiple *rounds*. Within each round, we run a layerwise GNN from scratch, based on the current state of the alignment. After the completion of one round of GNN, we use the last-layer embeddings to update the alignments, and proceed to the next round. Third, $\texttt{IsoNet++}$ incorporates a novel notion of node-pair partner interaction. Traditional early interaction computes attention between a node and its potential partners in the other graph, the attention then controlling messages passed across graphs. We consider *node pairs* (not single nodes) as potential partners. Existence of an edge between the nodes in one graph and non-existence in the other provide vital signals for refining the alignment. Our experiments on several datasets show that the alignments get progressively refined with successive rounds,
resulting in significantly better retrieval performance than existing methods. We demonstrate that all three innovations contribute to the enhanced accuracy. Our code and datasets are publicly available at https://github.com/structlearning/isonetpp.

Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval
Ashwin Ramachandran"
Vaibhav Raj²* Indrayumna Roy²
Soumen Chakrabarti Abir De
UC San Diego 2IT Bombay
ashwinramg@uedd.co
(vaibhavraj, indraroy15, soumen, abir)ecse. witb. ic.in
Abstract
Graph retrieval based on subgraph isomorphism has several real-world applications such as scene graph retrieval, molecular fingerprint detection and circuit design. Roy et al. 35 proposed IsoNet, late interaction model for subgraph matching, which first computes the node and edge embeddings of each graph independently of paired graph and then computes trainable alignment map. Here, present IsoNet++, an early interaction graph neural network (GNN), based on several technical innovations. First, we compute embeddings of all nodes by passing messages within and across the two input graphs, guided by an injective alignment between their nodes. Second, we update this alignment in a lazy fashion over multiple rounds. Within each round, we run a layerwise GNN from scratch, based the current state of the alignment. After the completion of round of GNN, we use the last-layer embeddings to update the alignments, and proceed to the next round. Third, IsoNet++ incorporates novel notion of node-pair partner interaction. Traditional early interaction computes attention between a node and its potential partners the other graph, the attention then controlling messages passed across graphs. In contrast, we consider node pairs (not single nodes) as potential partners. Existence of an edge between the nodes in one graph and non-existence in the other provide vital signals for refining the aligmment. Our experiments on several datasets show that the alignments get progressively refined with successive rounds, resulting in significantly better retrieval performance than existing methods. We demonstrate that all three innovations contribute to the enhanced accuracy. Our code and datasets are publicly available at htttts://githubb... com/ wwt.bb.co///utuaaeeeoeeeee wtr.ccteearmiingissonttyyy
Introduction
In graph retrieval based on subgraph isomorphism, the goal is to identify subset of graphs from a corpus, denoted [G.]. wherein each retrieved graph contains a subgraph isomorphic to given query graph GGp. Numerous real-life applications, e.g., molecular fingerprint detection [6]. scene graph retrieval [16]. circuit design [29] and frequent subgraph mining [43], can be formulated using subgraph isomorphism. Akin to other retrieval systems, the key challenge is to efficiently score corpus graphs against queries.
Recent work neural graph retrieval 1
22
23
35
31
has shown significant promise. IsoNet] focus specifically on subgraph
46
Among them, Lou et al. 2X Neuromatch] and Roy et al. 35 isomorphism. They employ graph neural networks (GNNs) to obtain embeddings of query and corpus graphs and compute the relevance score using form of order embedding [39]. In addition, IsoNet also approximates injective alignment between the query and corpus graphs. These two models operate in a late interaction paradigm, where the representations the query and corpus graphs are
Equall contribution. Ashwin Ramachandran did this work while at IIT Bombay.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

computed independent of each other. In contrast, GMN [22 is a powerful early interaction network for graph matching, where GNNs running on G2 and G2 interact with each other every layer.
Conventional wisdom suggests that early interaction is more accurate (even if slower) than late interaction, but GMN was outperformed by IsoNet. This is because of the following reasons. (1) GMN does not explicitly infer any alignment between G2 and Ge. The graphs are encoded by two GNNs that interact with each other at every layer, mediated by attentions from each node in one graph on nodes in the other. These attentions are functions of node embeddings, so they change from layer to layer. While these attentions may be interpreted as approximate alignments, they induce at best non-injective mappings between nodes. (2) In principle, one wishes to propose a consistent alignment across all layers. However, GMN's attention based 'alignment' is updated in every layer. (3) GMN uses standard GNN that is known to be an over over-smoother [36] 40]_ Due to this, the attention weights (which depend on the over-smoothed node representations) also suffer from oversmoothing. These limitations raise the possibilityy of third approach based on early interaction networks, enabled with explicit alignment structures, that have the potential to outperform both GMN and IsoNet.
1.1 Our contributions
We present IsoNet++, an early interaction network for subgraph matching that maintains chain of explicit, iteratively refined, injective, approximate alignments between the two graphs.
Early interaction GNNS with alignment refinement We design early interaction networks for scoring graph pairs, that ensure the node embeddings of one graph are influenced by both its paired graph and the alignment map between them. In contrast to existing works, we model alignments as an explicit "data structure". An alignment can be defined between either nodes or edges, thus leading to two variants of our model: IsoNet++ (Node) and IsoNet++ (Edge). Within IsoNet++, we maintain a sequence of such alignments and refine them using GNNs acting on the two graphs. These alignments mediate the interaction between the two GNNs. In our work, we realize the alignment as a doubly stochastic approximation to a permutation matrix, which an injective mapping by design.
Eager or lazy alignment updates In our work, we view the updates to the alignment maps as form of gradient-based updates in specific quadratic assignment problem or asymmetric Gromov- Wasserstein (GW) distance minimization [30 41] The general form of IsoNet++ allows updates that proceed lockstep with GNN layers (eager layer-wise updates), but it also allows lazy updates. Specifically, IsoNet++ can perform T rounds of updates to the alignment, each round including K layers of GNN message passing. During each round, the alignment is held fixed across all propagation layers in GNN. At the end of each round, we update the alignment by feeding the node embeddings into a neural -Sinhe-- soft permutation generator 10 26
Node-pair partner interaction between graphs The existing remedies to counter oversmoothing [ 33 40 entail extra computation: but they may be expensive an early-interaction setting. Existing early interaction models like (22) perform node partner interaction; interactions are constrained to occur between node and it's partner, the node in the paired graph aligned with it. Instead, we perform node-pair partner interaction; the interaction is expanded to include the node-pairs (or edges) in the paired graph that correspond to mode-pairs containing the node. Consequently, the embedding of a node not only depends on nodes in the paired graph that align with it, but also captures signals from nodes in the paired graph that are aligned with neighbors.
Experiments The design components of IsoNet++ and their implications are subtle - we report on extensive experiments that tease out their effects. Our experiments real world datasets show that, IsoNet++ outperforms several state-of-the-an methods for graph retrieval by substantial margin. Moreover, our results suggest that capturing information directly from node-pair partners can improve representation learning, as compared to taking information only from node partner.
2 Preliminaries
Notation Given graph G (V, E), we use nbr(u) denote the neighbors of a node u E V. We use u + v to indicate message flow from node u to node v. Given a set of corpus graphs C' = { and query graph Gg,, we denote y/G. G,,) as the binary relevance label of G. for G,. Motivated by several real life applications like substructure search in molecular graphs [1), object search in scene graphs [66] and text entailment (20), we consider subgraph isomorphism to significantly influence
the relevance label, similar to previous works 23 35). Specifically, v(G. Gg) when G, is

---

subgraph of Go. and 0 otherwise. We define C++ C as the set of corpus graphs that are relevant to G2 and set C.- C+ Mildly overloading notation, we use P to indicate 'hard' (0/1) permutation matrix or its 'soft' doubly-stochastii relaxation. B,, denotes the set of all n x n doubly stochastic matrices, and ,I, denotes the set of all n x n permutation matrices.
IsoNet (35] Given a graph G = (V, E), IsoNet uses GNN, which initializes node representations (ho(u): : } using node-local features. Then, messages are passed between neighboring nodes in K propagation layers. In the kth layer, a node receives messages from its neighbors, aggregates them, and then combines the result with its state after the (A: 1) layer:
(u) = combo (bx-1(u), Eveabr(u) {msg, 1 (x) hx)1()))))
Here, msga() (-) and combo (:,-) are suitable networks with parameters collectively called 0. Edges may also be featurized and influence the messages that are aggregated [24] The node representations
at the final propagation layer K can be collected into the matrix H ( u E V). Given node u E G, and a node u' E G.. we denote the embeddings of u and u' after the propagation layer
k as h (4) (u) and h ( (u') respectively, H (2) and (c denote the Kth-layer node embeddings of Gg and Ge, collected into matrices. Note that, here the set of vectors H99) and (c) do not dependent
on Ge and Gg- In the end, IsoNet compares these embeddings to compute the distance A Gg). which is inversely related to (Gee Gg).
A Ggy) = E.. ReLU|H - [u,
(2)
Since subgraph isomorphism entails asymmetric relevance, we have: A(G, + A(G, G.). IsoNet also proposed another design of A, where it replaces the node embeddings with edge embed- dings and node alignment matrix with edge alignment matrix in Eq.
In an early interaction network, (1) depends on G. and (e) depends on Gg for any given (Gg. Ge) pair. Formally, one should write H ()) and (cl instead of H( and (c) respectively for an early interaction network, but for simplicity, we will continue using (1v) and H())
Our goal Given set of corpus graphs C = {Go c E [[CI]], our high-level goal is to build graph retrieval model so that, given a query Gg, it can return the corpus graphs {G.}] which are relevant to Gg. To that end, we seek to develop (1) a GNN-based early interaction model, and (2) an appropriate distance measure ((- so that (c) H()))
is an accurate predictor of ((Ge Gg), at least to the extent that (-)..) is effective for ranking candidate corpus graphs in response to query graph.
3 Proposed early-interaction GNN with multi-round alignment refinement
In this section, we first write down the subgraph isomorphism task as an instance of the quadratic assignment problem (QAP) or the Gromov-Wassersees (GW) distance optimization task. Then, we design IsoNet++, by building upon this formulation.
3.1 Subgraph isomorphism as Gromov-Wasserster distance optimization
QAP GW formulation with asymmetric cost We given a graph pair Gg and Ge padded with appropriate number of nodes to ensure IVgl = |Va| = n (say). Let their adjacency matrices be Ag. A E (0. 1) jax" Consider the family of hard permutation matrices P E II, where P(u, u'] = 1 indicates u. E Vg is "matched" to w' E V.. Then, Gg is subgraph of G., if for some permutation matrix P. the matrix Ay is covered by P PT. i.e., for each pair (u, v), whenever we have A,lu, A, rj 1, we will also have PA,P" [u, u] = 1. This condition can be written as A, I PA.P.. We can regard deficit in coverage as cost or distance:
cost (P: Ag. Ac) = Eus [n].e[]]] (A,, - PA.PTT)
(A,-PA.PT) ),,] [u, w]
(3)
= Emveenn Ew.yeem (A,(u, v] (.lu,,o') Plu, v') P(c,o"]
(4)
Here, []+ max { 0} is the ReLU function, applied elementwise. The function cost (P; Ay, Ad)
can be driven down to zero using a suitable choice of P iff G, is subgraph of G.- This naturally suggests the relevance distance
AGG. Gg) = min cost (P; A,,
(5)
Pell.
Xu et al. 41 demonstrate that this QAP realization of the Maanov-Wastterstein distance minimization in graph setting.
3

---

Pals. Pila,
Pifso,
to M
Ge
Maniuna (+))
comby
Aligrnmet
Pr.8;
Prece Sine
Retted aligmment
Pp.
(2) Node pair partner Interaction in IsoNet++ (Node)
Bil0,,0) (s", (s),
Bi Ar
oi (w.,
layers
R GNN myere round
[+1
A (t)) cumbby
FallyinlaadionGNM.p (combn mage Interg)
(1) Pipeline of IsoNet++
Node pair partner interaction in IsoNet+* (Edge)
Figure 1: Overview of IsoNet++. Panel (a) shows the pipeline of IsoNet++. Given a graph pair
(G Ge), we execute T rounds, each consisting of K GNN layer propagations. After round t, we use the node embeddings to update the node alignment P = P. from its previous estimate P= P-Pp-1- Within each round t [T]. we compute the node embeddings of G2 by gathering signals from Ge and vice-versa, using GNN embeddings in the previous round and the node-alignment map Pt. The alignment P. remains consistent across all propagation layers k E [K] and is updated at the end of round f. Panel (b) shows our proposed node pair partner interaction in IsoNet++ (Node). When computing the message value of the node pair (u, v), we also feed the node embeddings the partners u' and v' in addition to the embeddings of the pairs (u, v), where u' and o' is approximately aligned with and v, respectively (when converted to soft alignment, u', of need not be neighbors).
Panel (c) shows the node pair partner interaction in IsoNet++ (Edge). In contrast to IsoNet++ (Node), here we feed the information from the message value of the partner pair (u', v²) instead their node embeddings into the message passing network misg..
Updating P with projected gradient descent As shown Benamou et al. 3 Peyré et al. 30, Xu al. [41], one approach is to first relax P into doubly stochastic matrix, which serves continuous approximation of the discrete permutation, and then update it using projected gradient descent (PGD).
Here, the soft permutation P.- is updated to P. at time-step by solving the following linear optimal transport (OT) problem, regularized with the entropy of (Plu, o] u, v E [m]] with a temperature т.
P. + arg min Trace [ pcost( P; Aq, Ae) P=PP..) + Elu, u] log Plu, v].
(6)
PEB..
Similar to other combinatorial optimization problems on graphs, QAP (4) does not capture the coverage cost in the presence of dense node edge features, where nodes edges may exhibit graded degrees of similarity represented by continuous values. Furthermore, the binary values of the adjacency matrices result in inadequate gradient signals in V p.ost(.). Additionally, the computational bottleneck of solving fresh OT problem in each PGD step introduces a significant overhead, especially given the large number of pairwise evaluations required in typical leariin-tto-ren setups.
Such an OT problem is solved using the iterative Sinkhorn- Sinkhorn-Knopp algorithm [00 37 26
3.2 Design of IsoNet+ (Node)
Building upon the insights from the above GW minimization 3 and the successive refinement step (6. we build IsoNet++ (Node), the first variant of our proposed early interaction model.
Node-pair partner interactions between graphs For simpler exposition, we begin by describing synthetic scenario, where P is a hard node permutation matrix, which induces the aligmment map as a bijection Vg + Ve, so that (Ta)) = b if P(a, b] 1. We first initialize layer & = 0 embeddings as (1))) (u) = Inita (feature(u)) using a neural network Initg. (Throughout, h (u) are treated likewise.) Under the given alignment map æ, a simple early interaction model would update the node embeddings as follows:
(g) # (u) combo (n(0) (u), Evenbr(w) msga (h (u), 1e (v)). h (T(2))
(7)
In the above expression, the update layer uses representation of the partner node w' E V. during the message passing step, compute (0()) (u). the embedding of node
Vg. Li al. [22 use
similar update protocol, by approximating f (π(u) = Ewev, ow-n the kth layer attention from Vg to potential partner u' e Vo, with Ewev au = L. Instead
(K) 1 (((())), where (k)
a is
(k)

---

h
h
interg
msg0
msga
Σ
msgA
comba
comba
comba
(a) No Interaction (IsoNet)
(b) Node Pair Interaction (GMN)
(c) Node Pair Partner
Interaction (IsoNet++)
Figure 2: Illustration of the three interaction modes. IsoNet has no/late interaction between h and h() IsoNet++ and GMN allow interaction between the representations of the query and corpus nodes. Under node pair interaction, the individual node embeddings (9) are used for message passing directly, thereby exposing them only to their neighbors. In the corresponding comba step, nodes interact only with their respective partners, therefore missing out on information from the partners of its neighbors. However, under node pair partner interaction, the representation of node is combined with that of its partner(s) first, using the inter, block to obtain z (I2). which is used for message passing. Thus, when interacting with neighbors, a node also gets information from the partners of its neighbors.
of regarding only nodes as potential partners, IsoNet++ will regard node pairs as partners. Given (u, v)) Eg. the partners (r(u), (T)) E, should then greatly influence the intensity of assimilation of h (e(( into h h (u). The first key innovation in IsoNet++ is to replace to recognize and
implement this insight:
K+t (u) combs (hh (9) (u), (. (T(1)),
Evenbr(u) msgo (Ih (u), h (T(())) ( n ( (+(1))))
(8)
Embeddings ( for nodes u' E V. are updated likewise in a symmetric manner. The network msg, provided embeddings from partners TT)). TT() of u, E Vg this allows h (u) to capture information from all nodes in the paired graph, that match with the + 1)-hop neighbors of u. We schematically illustrate the interaction between the paired graphs in IsoNet, GMN and IsoNet+ in Figure
Multi-round lazy refinement of node alignment In reality, we are not given any alignment map This motivates second key innovation beyond prior models ① 22 23 35 where we decouple GNN layer propagation from updates to P. To achieve this, IsoNet+ (Node) executes T rounds, each consisting of K layer propagations in both GNNs. At the end of each round
refine the earlier alignment P:-1 to the next estimate Pt, which will be used in the next round. Henceforth, we will use the double subscript & instead of the single subscript
in traditional GNNs. We denote the node embeddings at layer k and round & by h (u), A (u') E Rdima for E V, and u' E Va. which are (re-) jnntialzzel with node features h for each round I. We gather these into matrices
t [h, (u) u E V,J E mnndimm,, and t.6 [ (0) (w') u' E Vol E Ruddima.
(9)
P no longer remains an oracular hard permutation matrix, but becomes a doubly stochastic matrix indexed by rounds, written P.. At the end of round t, differentiable aligner module takes H (g) and H (c)
t.k inputs and outputs doubly stochastic node alignment (relaxed permutation) matrix Pa
as follows:
P. = Nodeellinne
H (.k
(10)
LK
GumbelSinkhoru (LRL (H L (H)))
(c) e B,
(11)
In the above expression, GumbelSinkhhrn performs iterative Sinkhorn normalization on the input matrix added with Gumbel noise (26): : LRL,, is neural module consisting of two linear layers with a ReLU activation after the first layer. As we shall see next, P. is used to gate messages flowing across from one graph the other during round t + i.e., while computing H41111K and H((e) H The soft alignment P, kept frozen for the duration of all layers in round L + Pe(u, u') may be interpreted as the probability that is assigned to u', which naturally requires that P. should be
5

---

row-equivariant (column equivariant) to the shuffling of the node indices of Gg (G.). As shown in Appendix D the above design choice (TT) ensures this property.
Updating node representation using early-interaction GNN Here, we describe the early in- teraction GNN for the query graph Gg. The GNN the corpus graph G. follows the exact same design and is deferred to Appendix E.1 In the initial round (t = 1), since there is no prior alignment estimate Pt= we employ the traditional late interaction GNN to compute all layers H 1,1:K and
(c) 1,1:K separately. These embeddings are then used estimate Pa- using Eq. (T)). For subsequent
rounds (1 1), given embeddings H f,1:K> and the alignment estimate matrix Pt, we run early interaction GNN from scratch. We start with fresh initialization of the node embeddings before; ie., h+ ()) = Inity (fatturfear For each subsequent propagation layer + 1 (A E [0, K 1)),
we approximate { as follows. We read previous-round, same-layer embeddings h. (u') of nodes u' from the other graph Ge, incorporate the alignment strength P. [u, w'), and aggregate these to get an intermediate representation of that is sensitive to P. and Ge.
I A (u) = interg 11 (u), Ewev.
(0) t. (u' (
(u))
(12)
Here, interp is neural network that computes interaction between the graph pairs; zt- (u) provides soft alignment guided representation of [h(])
(4)
(h)))) (u), h (x(2)) Eq.
( which can be relaxed as:
h (1) bi+Lk+1 (u) combè (x(() (21+1,x(2), Eventr(()) msgo (2++1 (w), (1))
(c)
(13)
In the above expression, we explicitly feed (4) (v), u E nbr(u) in the msg, network, capturing embeddings of nodes in the corpus G, aligned with the neighbors of node u E Vg in h 1141,84111 ( This allows the model to perform node-pair partner interaction. Instead, we were to feed only (g) 1. & (u) into the msgg network, then it would only perform node partner interaction. In this case, the computed embedding for u would be based solely signals from nodes in the paired graph that directly correspond u, therefore missing additional context from other neighbourhood nodes.
Distant supervision of alignment Finally, at the end of T rounds, we express the relevance
distance AGGel Gq) soft distance between the set H (a) [h Iu Vgl and H H..
T.K
(e) [h K (w') w' V.l, measured
(P. (u,d) d)
(14)
Our focus is on graph retrieval applications. It is unrealistic to assume direct supervision from a gold alignment map P Instead, training query instances are associated with pairwise preferences between two corpus graphs, in the form (G,, Got, Go-), meaning that, ideally, we want As.o (G.- G.y) > y + A s (Go (G)), where 7 > is margin hyperparameter. This suggests a minimization of the standard hinge loss as follows:
ming. Φ Egeq Ectec h A0. (G&+ |G,) (Ge G2)l+
(15)
This loss is propppapeee to train model weights 0 in comba, intere, msgg and weights o in the Gumbel-Sinkhorn network.
Multi-layer eager alignment variant Having set up the general multi-round framework of IsoNet++, we introduce structurally simpler variant that updates eagerly after every layer, eliminating the need to re-initialize node embeddings every time we update P. The eager variant retains the benefits of node-pair partner interactions, while ablating IsoNet++ toward GMN. Updating P via Sinkhorn iterations is expensive compared to a single GNN layer. In practice, we see non-trin non-trivial tradeoff between computation cost, end task accuracy, and the quality of our injective alignments, depending on the value of K for eager updates, and the values (T, for lazy updates. Formally, P& is updated across layers as follows:
Pt = Node Aligner Refttemmet,,,nenn,, (H H()))
(16)
= GumbelSinkhorn (L.L, (H I (H(
(17)

---

We update the GNN embeddings, layerwise, as follows:
(9) 2 (u) inters (A
(4) (u). hi (u') (x))
(18)
(1) 1++1 (u) = combo (2)- (0)
Evenbo(.)) msgo (w). (u), (u), (1))
(19)
Analysis of computational complexity Here, will compare the performance of IsoNet (Node) [35] with multi-layer IsoNet++ (Node) and multi-round IsoNet++ (Node) for graphs with [V] nodes. For multi-layer IsoNet++ (Node) and IsoNet (Node), we assume K propagation steps and for multi-round IsoNet++ (Node), T rounds, each with K propagation steps.
IsoNet (Node): The total complexity is O + K|E)), computed as follows: (1) Initialization of layer embeddings at layer & = 0 takes ((V)) time. (2) The node representation computation incurs a complexity of O((E)) for each message passing step since it aggregates node embeddings across all neighbors. (3) The computation of P takes O(V))) time.
Multi-layer eager IsoNer++ (Node): The total complexity O K|E + KVP)=
O(K]V computed as follows: (1) Initialization (layer k = 0) takes O(IVI) time. (2) The computation of intermediate embeddings 2²() (Eq. 18 involves the evaluation of the expression Evev. h (u')P((u,, u'] and hence admits complexity of O(VVl) for each node per layer. The total complexity for K steps and [V] nodes is thus (²). (3) Next, for each node in every layer, we compute h (Eq. 19) which gathers messages (x() from all its neighbors, contributing total complexity of O(K El) (4) Finally, we update Ps for each layer which has complexity of (KK]V)2).
-Mutti- coali--rounddde IsoNer++ (Node): Here, the key difference from the multi-layer version above is that the doubly stochastic matrix P. from round is used to compute and the K K-step-GNN runs in each of the T rounds. This multiplies the complexity of steps 2 and 3 with T, raising it to V + ET) Matrix P. is updated a total of T times, which changes the complexity of step 4 to (TT)V))) Hence, the total complexity is O(KTIV/ - T + KT B = 0 O(KT)V)??
Hence, the complexity of IsoNet is O(IV + K F)),), multi-layer IsoNet++ is O O(K|V (22 and multi- round IsoNet++ is (KT)VV))). This increased complexity of the latter comes with the benefit of a significant performance boost, as our experiments suggest.
3.3 Extension of IsoNet++ (Node) to IsoNet++ (Edge)
We now extend IsoNet++ (Node) to IsoNet++ (Edge) which uses explicit edge alignment for interac- tion across GNN and relevance distance surrogate.
Multi-round refinement of edge alignment
IsoNet++ (Edge), we maintain a soft edge permuta- tion matrix S which is frozen at S = S within each round /. E [T] and gets refined after every round as S + S. Similar to IsoNet++ (Node), within each round t, GNN runs from scratch: propagates messages across layers & E [K] and S, assists it to capture tross-graph signals. Here, in addition to node embeddings h we also use edge embeddings m (e), (e') E Rdimm at each layer and each round f, which capture the information about the subgraph k S K hop away from the edges and e'. Similar to Eq. we define M = [m (7) (e)]ee and M (n) (m
( are initialized using the features of the nodes connected by the edges, and possibly local edge features. Given the embeddings M(9)) and M(d) computed at the end of round an edge aligner module BeeigeeAliiurRReieeeennnt (o)) takes these embedding matrices as input and outputs a soft edge permutation matrix S,, similar to the update of P. in Eq. I1].
S. = EdgeAlignor
(M
(9)
(20)
KK T.
= GumbbelSnnkhom((RRR...
(g) 1.K)
LRR. T
(21)
Here, M are appropriately padded to ensure that they have the same number of rows.
Edge alignment-induced early interaction GNN For
start with late interaction model using vanilla GNN (1) and obtain S,=1 using Eq. (2 Having computed the edge embeddings
(*) m m.ikK and node embeddings h,, upto round t, we compute S, and use it to build fresh
carly interaction GNN for round + 1. To this end, adapt the GNN guided by P. in Eqs. I22
7

---

13)tt the GNN guided by S.. We overload the notations for neural modules and different embedding vectors from IsoNet++ (Node), whenever their roles are similar.
Starting with the same initialization as in IsoNet++ (Node), we perform the cross-graph interaction guided by the soft edge permutation matrix St, similar Eq. (12) Specifically,
the embed- dings of edges {e' = v')} E Ec, computed at layer & at round t, which share soft alignments
with edge (u, v) E Eag compute 2(4) 2+1,1 and 2(() 1-1, (e)))((e))
follows:
(2) 1 (e) = intera (M++1A (e), EeEE, m 10 (e(e))lle
(22)
Finally, we update the node embeddings h 111144 for propagation layer l: + as
h (g)
P1+14+1 (1) combo (e41,e(u); Eaenbr(u) (u): msgee (1++1, (u), h
(a)
(1)
(7) 1 (a), 2/4 ((x,())))
(23)
In this case, we perform the cross -raph interaction at the edge level rather than the node level. Hence,
msge acquires cross-edge signals separately as x(4) z(+1, Finally, we use h 1 and 2(4) *++1.+1 to
(o) update m as follows:
(0) 1+ ((u, v)) msgo (1411,44(1)) ( (v), 2141,6 ((u,
(g)
(1)
(24)
(c) Likewise, we develop m 141.4+1 for corpus graph Ge. Note that m 1+1,+1 (u,, u)) captures signals not only from the matched pair (u', v"), but also signals from the nodes in Ge which share corre-
(4)
spondences with the neighbor nodes of and v. Finally, we pad zero vectors to [ml?. (e),
(c) and [m (eeeee"eeee to build the matrices M and M7,K with same number of rows, which are finally used compute the relevance distance
(G Gq) = En, Ea ReLU M (0)
T.K (S T.Kk
(25)
4 Experiments
We report on a comprehensive evaluation of IsoNet++ on six real datasets and analyze the efficacy of the key novel design choices. In Appendix G we provide results of additional experiments.
4.1 Experimental setup
Datasets We use six real world datasets in our experiments, viz, AIDS, Mutag, PTC-FM (FM), PTC-FR (FR), PTC-MM (MM) and PTC-MR (MR), which were also used in (2 35 Appendix provides the details about dataset generation and their statistics.
State-of-the-art baselines We compare our method against eleven state-of-the-art methods, viz., (6) Neuro-
(1) GraphSim 22 (2) GOTSim III (3) SimGNN [. (4) EGSC (II, (5) H2MN 45
match 23) (7) GREED B2). (8) GEN 22 (9) GMN 22 (10) IsoNet (Node) 35 and (11) IsoNet
(Edge) 33 Among them, Neuromatch, GREED, IsoNet (Node) and IsoNet (Edge) apply asymmetric
hinge distances between query and corpus embeddings for AG Gg), specifically catered towards subgraph matching, similar to our method in Eqs. [4p and (25). GMN and GEN use symmetric Euclidean distance between their (whole-) graph embeddings g ( (for query) and ((*) (for corpus) as (l) [I in their paper [22], which is not suitable for subgraph matching and therefore, results poor performance. Hence, we change it to AGG, | = [g ()) g J+. The other methods first compute the graph embeddings, then fuse them using neural network and finally apply a nonlinear function on the fused embeddings to obtain the relevance score.
Training and evaluation protocol Given a fixed corpus set C, we split the query set Q into 60% training. 15% validation and 25% test set. We train all the models on the training set by minimizing ranking loss (1).. During the training of each model, we use five random seeds. Given a test query g'. we rank the corpus graphs in the decreasing order of Ag.s Gz²) computed using the trained model. We evaluate the quality of the ranking by measuring Average Precision (AP) and HITS @20, 20, described in Appendix [F] Finally, we report mean average precision (MAP) and mean HITS 20, across all the test queries. By default, we set the number of rounds 7 = 3, the number of propagation layers GNN K 5. In Appendix F we discuss the baselines, hyperparameter setup and the evaluation metries in more detail.
8

---

Metrics
Meun Average Precision (MAP)
HITS @
20
AIDS
Mutag
FM
FR
MM
MR
AIDS
Mutag
FM
FR
MM
MR
GraphSim
2
0.356
0.472
0.477
0.423
0.415
0.453
0.145
0.257
0.261
0.227
0.212
0.23
GOTSim 11
0.324
0.272
0.355
0.373
0.323
0.317
0.112
0.088
0.147
0.166
0.119
0.116
SimGNN
0.341
0.283
0.473
0.341
0.298
0.379
0.138
0.087
0.235
0.155
0.111
0.160
EGSC 31
0.505
0.476
0.609
0.607
0.586
0.58
0.267
0.243
0.364
0.382
0.348
0.325
H2MN 15
0,267
0.276
0.436
0.412
0.312
0.243
0.076
0.084
0.200
0.189
0.119
0.069
Neuromatch 23
0.489
0.576
0.615
0.559
0.519
0.606
0.262
0.376
0.389
0,350
0.282
0.385
GREED 32
0.472
0.567
0.558
0.512
0.546
0.528
0.245
0.371
0,316
0.287
0.311
0.277
GEN 22
0.557
0.605
0.661
0.575
0.539
0.631
0.321
0.429
0.448
0.368
0.292
0,391
GMN 22
0.622
0.710
0.730
0.662
0.655
0.708
0.397
0,544
0.537
0.45
0,423
0.49
IsoNet (Node) 35
0.659
0.697
0.729
0.68
0.708
0.738
0.438
0.509
0.525
0.475
0.493
0,532
IsoNet (Edge) 35
0.690
0.706
0.783
0.722
0.753
0.774
0,479
0.529
0.613
0.538
0.571
0.601
TsoNec++ (Node)
01825
0.851
0.888
0.855
0.838
0.874
0.672
0.732
0.797
0.737
0.702
0.755
IsoNec++ (Edge)
0.847
0.858
0.902
0.875
0.902
0.902
0.705
0.749
0.813
0.769
0.809
0.803
Table 3: Comparison of the two variants of IsoNet++ (IsoNet++ (Node) and IsoNet++ (Bdge)) against all the state-of-the- art graph retrieval methods, across all six datasets. Performance measured in terms average precision (MAP) and mean HITS@20 In all cases, we used 60% training. 15% validation and 25% test sets. The numbers highlighted with green and yellow indicate the best, second best method respectively, whereas the numbers with blue indicate the best method among the baselines. (MAP values for IsoNet++ (Edge) across FM, MM and MR were verified to be not exactly the same, but they match up to the third decimal place.)
AIDS
Murag
FM
FR
MM
MR
AIDS
Malag
FM
FR
MM
MR
Rdge Node
Eager
0.756
0.81
0.859
0,802
0.827
0.841
Node partner
0.776
0,829
0.851
0.819
0.844
0.84
Lazy
0.825
0.851
0.888
0.855
0838
0.874
IsoNet++ (Node)
0,255
08811
0.888
0.855
0.888
0.74
Eager
0.795
0.855
0,883
0812
0.862
0.886
Node partner
0.668
0.783
0.821
0.752
0.753
0.794
Lazy
0.847
0,858
0,902
0.875
0.902
0,902
IsoNet++ (Node)
0,756
0.81
0.859
0.802
0.827
0.841
Table 4: Lazy multi-round vs. eager multi-layer. First (Last) two rows report MAP for IsoNet++ + (Node)
Table 5: Node partner vs. node pair partner interaction. First (Last) two rows report MAP for multi-round (multi- layer) update. Green shows the best method.
(IsoNet++ (Edge)). Green shows the best method.
4.2 Results
Comparison with baselines First, we compare IsoNet++ (Node) and IsoNet++ (Edge) against all the baselines, across all datasets. In Table 3 we report the results. The key observations are as follows: (1) IsoNet++ (Node) and IsoNet++ (Edge) outperform all the baselines by significant margins across all datasets. IsoNet++ (Edge) consistently outperforms IsoNet++ (Node). This is because edge aligmment allows us to compare the graph pairs more effectively than node alignment. similar effect was seen for IsoNet (Edge) vs. IsoNet (Node) 35 (2) Among all state-of-the-arr competitors, IsoNet (Edge) performs the best followed by IsoNer (Node). Similar to us, they also use edge and node alignments respectively, However, IsoNet does not perform any interaction between the graph pairs and the alignment is computed once only during the computation of A (Gy) This results in modest performance compared to IsoNet++. (3) GMN uses "attention" to estimate the alignment between graph pairs, which induces non-injective mapping. Therefore, despite being an early interaction model, it is mostly outperformed by IsoNet, which uses injective alignments.
Lazy vs. eager updates In lazy multi-round updates, the alignment matrices remain unchanged across all propagation layers and are updated only after the GNN completes its K K-layer message propagations. To evaluate its effectiveness, we compare it against the eager multi-layer update (described at the end of Section 3.2). where the GNN executes its K-layer message propagations only once; the alignment map is updated across K layers; and, the alignment at kth layer is used to compute the embeddings (k: + 1)th layer. In Table 4 we compare the performance in terms MAP, which shows that lazy multi-round updates significantly outperform multi-layer updates.
Node partner ys. node-pair partner interaction To understand the benefits of node-pair partner interaction, we contrast IsoNet++ (Node) against another variant of our method, which performs node partner interaction rather than node pair partner interaction, similar to Eq. 77.. For lazy multi-round updates, we compute the embeddings as follows:
h (9)
h+ (u) combo (h(9) (1, (u), Eventr()) msga (h1. (1) (v)), Ewev. Pilu, v' (
For eager multi-layer updates, we compute the embeddings as:
(9) 1++1 (w) = comba(h (9) (u), Ev (
(h (u), h (4) (w)). Ewev. Pa(u,u(Th (c) (ud))
9

---

0.20
0.12-
Multi- Rouid
AIDS
-1
0.12-
0.16-
Multi Layer
-k
-k
-k
P[Tr(S] 5
0.05
Multi- Round
AIDS
P(T(88T (")
0.12
0.08
AIDS Multi Layer
-k
-k
-k
-k
P(T((
0.08
P(Tr
-k
0.04
0.06
0.04
10
10
Tr P*)
Tr(PP PT)
Tr 5*)
Tr(S
Figure 6: Empirical probability density of similarity between the estimated alignments and the true aligmments P for both multi-round and multi-layer update strategies across different stages of updates (t for multi-round and k for multi-layer), for AIDS. Similarity is measured using P(Tr(P, P'))),((T(SS) 5))) for multi-round lazy updates and p(Tr(P, P*)), S*)) for multi-layer eager updates.
S
Table 5 summarizes the results, which shows that IsoNet++ (Node) (node partner pair) performs significantly better than Node partner for both multi-round lazy updates (top-two rows) and multi-layer eager updates (bottom tow rows).
Quality of injective alignments Next we compare between multi-round and multi-layer update strategies in terms of their ability to refine the alignment matrices, as the number of updates of these matrices increases. For multi- (layer) updates, we instrument the alignments P. and S, (Pk and Sp) for different rounds t E [T' (layers k E [.). Specifically. we look into the distribution of the similarity between the learned alignments P,, and the correct alignments P S (using combinatorial routine), measured using the inner products Tr( P, P*) and Tr(S, S*) for different t. Similarly, we compute Tr(P, k PP) and Tr.S. S*) for different A E [K]. Figure 6 summarizes increases, the learned alignments become closer to the
the results, which shows that (1) gold alignments; (2) multi-round updates refine the alignments
the multi-layer variant. The distribution of Tr(P, P') at approximately twice as faster than in multi-round strategy almost always close Tr( Tr(P. P*) for & 2. Note that, our aligner networks learn refine the P, and S, through end-to-end training, without using any form of supervision from true alignments or the gradient computed in Eq. (6).
Accuracy-inference time trade-off Here, we an- alyze the accuracy and inference time trade-off. We vary T and K for IsoNet++'s 's lazy multi-round vari- ant, and vary K for IsoNet++'s eager multi-layer variant and for GMN. Figure 7 summarizes the re- sults. Notably, the eager multi-layer variant achieves the highest accuracy for K = 8 on the AIDS dataset, despite the known issue of oversmoothing in GNNs for large K. This unexpected result may be due to our message passing components, which involve terms like Σ. Plu, w' d'()) effectively acting as a convolution between alignment scores and embedding vectors. This likely enables P function as a filter, countering the oversmoothing effect.
1.0 Lazy
Eager
GMN
1.0 Lazy
Eager GMN
MAP
MAP
0.8
0.0
50
SO
110
0.6
50
80
110
140
Inference time ms)
Inference time ms)
(a) Node, AIDS
(b) Edge, AIDS
Figure 7: Trade-off between MAP and inference time (batch size=128).
Conclusion
We introduce IsoNet++ as an early-interaction network for estimating subgraph isomorphism. IsoNet++ learns to identify explicit alignments between query and corpus graphs despite having access to only pairwise preferences and not explicit alignments during training. We design graph neural network (GNN) that uses an alignment estimate to propagate messages, then uses the GNN's output representations to refine the alignment. Experiments across several datasets confirm that alignment refinement is achieved over several rounds. Design choices such as using node-pair partner interaction (instead of node partner) and lazy updates (over eager) boost the performance of our architecture, making it the of-te-of-the-aee art in subgraph isomorphism based subgraph retrieval. We also demonstrate the accuracy v/s inference time trade offs for IsoNet++, which show how different knobs can be tuned to utilize our models under regimes with varied time constraints.
This study can be extended to graph retrieval problems which use different graph similarity measures, such as maximum common subgraph or graph edit distance. Extracting information from node-pairs is effective and can be widely used to improve GNNs working on multiple graphs once.
10

---

Acknowledgements
Indradyumna acknowledges Qualcomm Innovation Fellowship, Abir and Soumen acknowledge grants from Amazon, Google, IBM and SERB.
References
[1] Y. Bai, H. Ding, S. Bian, T. Chen, Y. Sun, and W. Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings the Twelfth ACM International Conference on Web Search and Data Mining, pages 384-392, 2019.
[2] Y. Bai, H. Ding, K. Gu, Y. Sun, and W. Wang. Learning computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2219-3228 2020.
Learning-based based efficient graph similarity
[3] J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyré. Iterative bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2):1111- A1138, 2015.
[4] Q. Berthet, M. Blondel, O. Teboul, M. Cuturi, J.-P. Vert, and F. Bach. Learning with differen- tiable pertubed optimizers. Advances in neural information processing systems, 33:9508 9519, 2020.
[5] L. Biewald. Experiment tracking with weights and biases, 2020. URL wttph:ttt//rtt wandb com/ Software available from wandb.com.
[6] A. Cereto-Massagué, M. Ojeda, C. Valls, M. Mulero, S. Garcia-Vallye and G. Pujadas. Molecular fingerprint similarity search in virtual screening. Methods, 71:58-63, 2015.
[7] D. Chen, L. O'Bray, and K. Borgwardt. Structure-aware transformer for graph representation learning. ICML, 2022.
[8] E. Cohen-Karlik, A. B. David, and A. Gloherson. Regularizing towards permutation invariance in recurrent models. In NeurIPS. Curran Associates Inc., 2020. ISBN 9781713829546, URL
https://arxix: org/ abs/2010. 13055
[9] L. P. Cordella, Foggia. Sansone, and M. Vento. (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence, 26(10); 1367-1372, 2004.
[10] M. Cuturi. Sinkhorn distances: neural information processing systems, 22002002 2013.
Lightspeed computation of optimal transport. Advances in
[11] K. D. Doan, S. Manchanda, S. Mahapatra, and C. K. Reddy, Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. pages 665-674, 2021.
[12] H.-C. Ehrlich and M. Rarey. Systematic benchmark substructure search in molecular graphs- from ullmann to vf2. Journal of Cheminformatics, 4:1-17, 2012.
[13] X. Gao, B. Xiao, Tao, and X. Li. A survey of graph edit distance. Pattern Analysis and applications, 13(1):113-12, 2010.
[14] Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017.
[15] A. Hagberg, Swart, and D. Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab,(LNN)), Los Alamos, NM (United States), 2008.
[16] J. Johnson, R. Krishna, M. Stark, L.-J. Li, D. Shamma, M. Bernstein, and L. Fei-Fei. Image retrieval using scene graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3668-3678, 2015.

---

[17] N. Karalias and A. Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances in Neural Information Processing Systems, 33: 6659-6672, 2020.
[18] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (609.02907, 2016.
[19] J. Kotary, F. Fioretto, P. Van Hentenryck, and B. Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:2/03.16378 2021.
[20] A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling en- tailment. In Proceedings of the 15th Conference of the European Chapter of the Associa- tion for Computational Linguistics: Volume 1, Long Papers, pages 721-730, 2017. URL https:///ww/ www.eb.clwb..oo org/
10t...006.ppppp .dff
[21] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel. Gated graph sequence neural networks. arXiv preprint arXiv: 2015.
[22] 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 on machine learning, pages PMLR, 2019. URL http:ttsss//ii..oooo
aba/a/as//19. 12787
[23] Z. Lou, You, C. Wen, A. Canedo, J. Leskovec, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03092, 2020.
[24] D. Marcheggiani and I. Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In M. Palmer, R. Hwa, and S. Riedel, editors, Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1506-1515, Copenhagen, Denmark, Sept. 2017. Association for Computational Linguistics. doi: 10.18653/ v1/D17-1159. URL httttt::/aclaantolloo"
wttp:hhoooogyyg//111111 www/ooo- 1159
[25] B. McFee and G. R. G. Lanckriet. Partial order embedding with multiple kernels. In Interna- tional Conference on Machine Learning, 2009. URL httpss:/app...... www.eeeeieaneolaeeeeeee...etetee org/
CorpusID:660 199299
[26] G. Mena, D. Belanger. S. Linderman, and Snock. Learning latent permutations with gumbel- sinkhorn networks. arXiv preprint 180iv: 18860,1800.00665, 2018. BtL/hhtps://ara org/pdf/ 1802.08665 pdf
[27] C. Morris, N. M. Kriege, Bause, K. Kersting, P. Mutzel, and Neumann. Tudataset: collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www wwwphhearaing........ io
[28] R. Myers, R. Wison, and R. Hancock. Bayesian graph edit distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(6):628-633 2000.
[29] M. Ohlrich, C. Ebeling, E. Ginting, and L. Sather. Subgemini: Identifying subcircuits using a fast subgraph isomorphism algorithm. In Proceedings of the 30th International Design Automation Conference, pages 31-37, 1993.
[30] G. Peyré, M. Cuturi, and J. Solomon. Kromov-wassersteie averaging of kernel and distance matrices. In International conference on machine learning, pages 2664-2672. PMLR, 2016.
[31] 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.
[32] R. Ranjan, S. Grover, S. Medya, V. Chakaravarthy, Y. Sabharwal, and S. Ranu. Greed: A neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, November 29-Decemer 1, 2022, 2022.
[33] I. Roy, A. De, and S. Chakrabarti, Adversarial permutatioo guided node representations for link prediction. In AAAI Conference, 2021. URL httpss/////a org/abb//012..8977
12

---

[34] I. Roy, S. Chakrabarti, and A. De. Maximum common subgraph guided graph retrieval: Late and early interaction networks. In NeurlPS, 2022. /ttps://ppeeeeeeriiii wtw.eeerrriiieennnffoorur net/forum? id=COAcbu3 k4U.
[35] I. Roy, V. S. Velugoti, S. Chakrabarti, and A. De. Interpretable neural subgraph matching for graph retrieval. In AAAI Conference, 2022. URL hRKLittts//indddyuuaaaa github. / IsoNeet_maie maint_mmann.. pdf
[36] T. K. Rusch, M. M. Bronstein, and S. Mishra. A survey on oversmoothing in graph neural networks. Preprint, 2023.
10993
[37] R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-348, 1967.
[38] Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
[39] I. Vendrov, R. Kiros, S. Fidler, and R. Urtasun. Order-embeddinngs of images and language. arXiv preprint arXiv: 151.666,, 2015. URL
[40] Wenkel, Y. Min, M. Hir,, M. Perlmutter, and G. Wolf. Overcoming oversmoothness in graph convolutional networks via hybrid scattering networks, 2022. URL httpss//aaxii..rrrr abs/22001.885
[41] H. Xu, D. Luo, H. Zha, and L. C. Duke. node embedding. In International conference on machine learning, pages 6932-6941. PMLR, 2019.
learning for graph matching and
[42] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, How powerful are graph neural networks? arXiv preprint arXiv: Xiv::180.000826, 2018
[43] X. Yan, P. S. Yu, and J. Han. Graph indexing: A frequent structure-basce approach. In Proceedings of the 2004 ACM SIGMOD international conference Management of data, pages 335-34--0 335,346,77 2004.
[44] 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-36, 2009.
[45] Z. Zhang, Bu, M. Ester, Li, 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, pages 2284-2284, 2021.
[46] W. Zhuo and G. Tan. Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, 55:30181-30199 2022.
13

---

Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval (Appendix)
A Limitations
We find two limitations of our method each which could form the basis of detailed future studies.
1. Retrieval systems greatly benefit from the similarity function being hashable. This can improve the inference time multi-fold while losing very little, if at all any, performance, making the approach ready for production environments working under tight time constraints. The design of a hash function for an early interaction network like ours unknown and seemingly difficult. In fact, such a hashing procedure is not known even for predecessors like IsoNet (Bdge) or GMN, and this is exciting future direction.
2. Our approach does not explicitly differentiate between nodes or edges that may belong to different classes. This can be counterproductive when there exist constraints that prevent the alignment of two nodes or edges with different labels. While the network is designed to process node and edge features, it might not be enough to rule out alignments that violate the said constraint. Such constraints could also exist for node-pains such as in knowledge graphs with hierarchical relationships between entity types, and are not taken into account by our model. Extending our work to handle such restrictions is an interesting problem to consider.
B Related work
In this section, we discuss different streams of work that are related and have influenced the study.
B.1 Graph Representation Learning
Graph neural networks (GNN) [4, [2 21
18 42 38 have emerged as a widely applicable approach for graph representation learning. A graph neural network computes the embedding of a node by aggregating the representations of its neighbors across K steps of message passing, effectively combining information from K K-hop neighbors. GNNs were first used for graph similarity computation by Li et al. [22], who enriched the architecture with attention to predict isomorphism between two graphs. Attention acts as mechanism transfer information from the representation of one graph to that of the other, thus boosting the performance of the approach. Chen et al. 7 enriched the representation of graphs by capturing the subgraph around node effectively through structure aware transformer architecture.
B.2 Differentiable combinatorial solvers
We utilize differentiable gadget to compute an injective alignment, which is a doubly stochastic matrix. The differentiability crucial to the training procedure as enables us to backpropagate through the alignments. The GumbelSinkhorn operator, which performs alternating normalizations across rows and columns, was first proposed by Sinkhorn and Knopp (37) and later used for the Optimal Transport problem by Cuturi [IO]. Other methods to achieve differentiability include adding random noise to the inputs to discrete solvers 4 and designing probabilistic loss functions [17]. A compilation of such approaches towards constrained optimization graphs through neural techniques is presented in
B.3
Graph Similarity Computation and Retrieval
Several different underlying measures have been proposed for graph similarity computation, including
full graph isomorphism (22) subgraph isomorphism 23
35
graph edit distance (GED) [ 13
28
and maximum common subgraph (MCS) 2 34 Bai et al. 2 proposed GraphSim
towards the GED and MCS problems, using convolutional neural network based scoring on top of graph similarity matrices. GOTSim [II explicitly computes the alignment between the two graphs by studying the optimal transformation cost. GraphSim 2 utilizes both graph-level and node-level signals to compute graph similarity score. NeuroMatch 23 evaluates, for each node pair across the two graphs, if the neighborhood of one node is contained in the neighborhood of another using order
embeddings 225 GREED [32 proposed Siamese graph isomorphism network, late interaction
14

---

model to tackle the GED problem and provided supporting theoretical guarantees. Zhang et al. 445 propose an early interaction model, using hypergraphs to learn higher order node similarity. Each hypergraph convolution contains a subgraph matching module to learn cross graph similarity. Qin al. [31 trained a slower attention-based network on multi-level features from GNN and distilled its knowledge into faster student model. Roy et al. [35] used the GumbelSinkhorn operator as a differentiable gadget to compute alignments
fashion and also demonstrated the utility of computing alignments for edges instead of nodes.
backpropagation-friiee
C Broader Impact
This work can be directly applied to numerous practical upplications, such as drug discovery and circuit design. which are enormously beneficial for the society and continue garner interest from researchers and practitioners worldwide. The ideas introduced in this paper have benefitted from and can benefit the information retrieval community as well, beyond the domain of graphs. However, malicious parties could use this technology for deceitful purposes, such identifying and targeting specific social circles on online social networks (which can be represented as graphs). Such pros and cons are characteristic of every scientific study and the authors consider the positives to far outweigh the negatives.
D Network architecture of different components of IsoNet++
IsoNet++ models consist of three components an encoder, a message-passing network and node/edge aligner. We provide details about each of these components below. For convenience, we represent a linear layer with input dimension a and output dimension b as Linear(a, b) and a Jinear-ReLL-linne ReLU--inear network with Lincar(a, b), Lincar(b, c) layers with ReLU activation in the middle LRI(a,
D.1 Encoder
The encoder transforms input node/edge features before they are fed into the message- saaaaagg-pssinggggge network. For models centred around node alignment like IsoNet++ (Node), the encoder refers to Init, and is implemented as a Linear(1, 10) layer. The edge vectors are not encoded and passed as-is down to the mnessage-passingg network. For edge-based models like IsoNet++ (Edge), the encoder refers to both Inite, node and Inita edge. which are implemented Linear(1, 10) and Linear(1, 20) layers respectively.
D.2 GNN
Within the message-passingg framework, use node embeddings of size dim,, 10 and edge embeddings of size dim,, = 20. We specify each component of the GNN below.
interp combines the representation of the current node/edge (h,) with that from the other graph, which are together fed the network by concatenation. For node-based and edge- based models, it is implemented as LRT 20, 10) and LRI,(40, 40, 20) networks respec- tively. In particular, we ensure that the input dimension twice the size the output dimension, which in turn equals the intermediate embedding dimension dim(z).
msga is used to compute messages by combining intermediate embeddings z. nodes across an edge with the representation of that edge. For node-based models, the edge vector is fixed vector of size 1 while the intermediate node embeddings z. are vectors of dimension 10, resulting in the network being Linear (21, 20) layer. For adge-bases models, the edge embedding is the m vector of size 20 which requires msg, to be a Linear (40, 20) layer. Note that the message-passing network is applied twice, once to the ordered pair (u, v) and then to (u, u) and the outputs thus obtained are added up. This is to ensure node order invariance for undirected edges by design.
comba combines the representation of a node 2. with aggregated messages received by it GRU where the node representation (of size 10) is the initial hidden state and the aggregated message vector (of size 20) is the only element of an input sequence which updates the hidden state to give the final node embedding h.
from all its neighbors. It modelled
15

---

D.3 Node aligner
The node aligner takes as input two sets of node vectors H R and H() E R representing Gg and G. respectively. n refers to the number of nodes in the corpus graph (the query graph is padded to meet this node count). We use LRLg LRL(10, 16, 16) network (refer Eq. 11
D.4
Edge aligner
The design of the edge aligner is similar to the node aligner described above in Section D.3 except that its inputs are sets of edge vectors M(a) e R and M E Rex200 refers to the number of edges in the corpus graph (the query graph padded to meet this edge count). We use LRLg as LRL(200 16, 16) network (refer Eq. 21..
D.5
GumbelSinkhorn operator
The GumbelSinkhorn operator consists of the following operations
Du = exp(Dma/7)
(26)
D++1 RowNorm (ColumnNorr((D.)
(27)
D Dout lim D:
(28)
f-000
The matrix Den obtained after this set of operations will be a doubly-stochastic matrix. The input
Din in our case is the matrix containing the dot product of the node/edge embeddings of the query and corpus graphs respectively. 7 represents the temperature and is fixed to 0.1 in all our experiments.
Theorem Equation I1 results in a permutation matrix that is row-equivariant (column-) to the shuffling of nodes in Gg (Go).
Proof To prove the equivariance of Eq. 11 we need to show that given a shuffling (permutation) of
query nodes Z II, which modifies the node embedding matrix to 2 ZH t.K' the resulting output of (9)))
(4)
said equation would change to P... Below, we consider any matrices with Z in the suffix as being an intermediate expression in the computation of NoddeAligeeRRefeeeeenn, (ZH,,
(4) H.(kk
It is easy to observe that the operators LRLg (a linear- ReLU-linear network applied to matrix), RowNorm, ColumnNorm and element-wise exponentiation (exp), division are all permutation- equivariant since shuffling of the vectors fed into these will trivially result in the output vectors getting shuffled in the same order. Thus, we get the following sequence operations
D LRL (ZH (o) LRL (H)
Z LRLg ( (0) (, (H D = ZDn (29)
Do.z equals exp( Din. Dinz/T), which according to above equation would lead to Do.z = 2Dn We can then inductively show using Eq. the following holds till E, that
24 and the equivariance of row/column normalization, assuming
D++1, RowNorm (ColumnNorm( Dr,z)) RowNorm (ColumnNormm (7D:))
(30)
= RowNorm (Z- ColumnNorm( (D))) = Z RowNorm (ColumnNorm(( (.)) = 2D (31)
The above equivariance would also hold in the limit, resulting in the doubly stochastic matrix
D 7 ZD which concludes the proof.
similar proof can be followed show column equivariance for a shuffling in the corpus nodes.
E Variants of our models and GMN, used in the experiments
E.1 Multi-round refinement of IsoNet++ (Node) for the corpus graph
Initialize:
h = Initg(feature(("))
(32)
Update the GNN embeddings as follows: (c) (c) (x') = inters (n')), (1)), EvEv, L (. (T) (u'
(2)
(33)
[o) h441,44111 (u') combo (c) (1')) (n') Entraay msgo (2 (2(1) (1²), (c)
(34)
16

---

E.2
Eager update for IsoNef++ (Edge)
Initialize:
hg (u) mode (featurc(u)),
(g)
(35)
(4) (e) Inite, edge (feature(e)).
mg
(36)
The edge alignment is updated across layers. So is set to matrix of zeros. For k > 0, the following equation is used:
S EdgeelliguerRefinene
(M² ,
(37)
GumbelSinkhorn (M (
(38)
We update the GNN node and edge embeddings as follows:
k (e) = interø (m (g) (c), Ee'EE m (0) (d')S(le,)))
(39)
h k+ (u) = comby (1% (u), Enenbr(w) msga (h (u), h (a), 2 ((u,a)))
(40)
(4) m k++1 (u, o)) msgo (h
(a) k+1 (u), h F (e), 2 (4)
((,v))))
(41)
E.3 Node partner (with additional MLP) variant of IsoNet++ (Node)
Here, we update node embeddings as follows:
h (4) 1,41441 (u) combo
(9) 1, (u), (u), E Eennr(()) msgo (h, (9)
1+1. (1), h ④ 141. (T))
(42)
* is replaced with h
Here, 2())
1,+1,& (u) is computed as Eq. 12). where interg is an MLP network. contrast to Eq.
1. (v) are not fed into the message passing layer. Hence, in the message passing layer, we do not capture the signals from the partners of u and u G.- Only signals from partners of
(4) here, 1,+ (w). (g)
are captured through = (u) in the first argument.
E.4
Node pair partner (msg only) variant of IsoNet++ (Node)
We change the GNN update equation as follows:
h (g) 1+1kk 1 (w) comba
h
h E En msgo (w), 2 (g)
(())
(43)
replaced with
Node pair partner interaction takes place because, we feed from Eq. (12) into the message passing layer. However, use h in the first argument, instead of
17

---

Additional details about experimental setup
F11
Datasets
We use six datasets from the TUDatasets collection [27 for benchmarking our methods with respect existing baselines. Lou al. [23 devised method sample query and corpus graphs from the graphs present in these datasets to create their training data. We adopt it for the task of subgraph as the center of a Breadth First Search (BFS) and run the algorithm till [V] nodes are traversed, where the range of V is listed in Table 8 (refer to the Min and Max columns for [V,l and [V.). This process independently performed for the query and corpus splits (with different ranges for graph size) to obtain 300 query graphs and 800 corpus graphs. The set query graphs split into train, validation and test splits 180 (60%), 45 (15%) and 75 (25%) graphs respectively. Ground truth labels are computed for each query-corpus graph pair using the VF2 algorithm 99] [5 23 implemented in the Networkx library. Various statistics about the datasets are listed in Table 8 pairs (y) denotes the number of pairs in the dataset with gold
matching. partieular, we choose a node
label y, where y E {0,1] 1}.
Mean Vg Min |V,l Max [V,1 Mean Egl Mean [Vl
[V.]
Max VV
Mean |E
pairs(1)
pains(0)
pairs
ATDS
11.61
11.25
18.50
17
18.87
41001
198999
0.2118
Mutag
12.91
13.27
19.89
42495
197505
0.2209
FM
11.73
15
11.35
18.30
17
18.81
40516
199484
0.2085
FR
11.11
15
11.39
18.32
17
20
18.79
39829
200171
0.2043
MM
11.80
15
11.37
18.36
17
20
18.79
40069
199931
0.2056
MR
11.87
15
11.49
18.32
17
20
18.78
40982
199018
0.2119
Table 8: Statistics for the 6 datasets borrowed from the TUDatasets collection
27
F22 Baselines
GraphSim, GOTSim, SimGNN, Neuromatch, GEN,
GMN, IsoNet (Node), IsoNet (Edge): We Some for loops were vectorized to improve
utilized the code from official implementation of 335 the running time of GMN.
EGSC: The official implementation is refactored and integrated into code.
H2MN: We use the official code from
GREED: We use the official code from The model is adapted from the graph edit distance (GED)
task to the subgraph isomorphism task, using a hinge scoring layer.
The number of parameters involved in all models (our methods and baselines) are reported in Table 9
Number of parameters
GraphSim GOTSim
3909
304
SimGNN
1671
EGSC 31
3948
H2MN 45
2974
Neuromatch 23
3463
GREED 332
1840
GEN 22
1750
GMN 22
2050
IsoNet (Node)
35
1868
IsoNet (Edge) 35
2028
IsoNet++ (Node)
2498
IsoNet++ (Edge)
4908
Table 9: Number of parameters for all models used in comparison
httep///iccabb.ooo//mmmmp///1f1f Grwph__iimlaarittee Computationnn
httpg://ggthab..co/ddddeeddddddd
18

---

F.3
Calculation of Metrics: Mean Average Precision (MAP), HITS @K, Precision @ K and Mean Reciprocal Rank (MRR)
Given ranked list of corpus graphs = {Ge} for a test query Gg. sorted in the decreasing order of Ao (G, let assume that the dhth relevant graph is placed at position pos(c4) ) {1;,. |C] in the ranked list. Then Average Precision (AP) is computed as:
AP
(44)
10o+1 c4E(1C+
pos(c+)
Mean average precision is defined as ΣneQ AP(1)/1Q).
# relevant graphs corresponding to Gg till rank K. Finally we report the mean of Precision @ K K(() across queries.
Precision @ (q)
Reciprocal rank or (R(g) (g) is the inverse the rank the topmost relevant corpus graph corresponding to Gg in the ranked list. Mean reciprocal rank (MRR) is average of RR(g) across queries.
HITS@ K for a query Gg defined as the fraction of positively labeled corpus graphs that appear before the th negatively labeled corpus graph. Finally, we report the average of HITS@ K across queries.
Note that HITS K is a significantly aggressive metric compared to Precision @ and MRR, can be seen in Tables 12 and
F44 Details about hyperparameters
All models were trained using early stopping with MAP score on the validation split as stopping criterion. For early stopping, we used patience of 50 with a tolerance of 10-4. We used the Adam optimizer with the learning rate as 10-3 and the weight decay parameter as 5 10-4, We set batch size to 128 and maximum number of epochs to 1000.
Seed Selection and Reproducibility Five integer seeds were chosen uniformly at random from the range [0, 10a] resulting in the set {1704, 4929, 7366, 7474, 7762). IsoNet+ (Node), GMN and IsoNet (Edge) were trained on each of these seeds for all 6 datasets. Note that these seeds do not control the training- dev-test splits but only control the initialization. Since the overall problem non-convex, in principle, one should choose the best initial conditions leading local minima. Hence, for all models, we choose the best seed, based on validation MAP score, is shown in Table I0
AIDS
Mutag
FM
FR
MM
MR
GraphSim GOTSim
2
7762
4929
7762
7366
4929
7474
7762
7366
1704
7762
1704
7366
SimGNN
7762
7474
1704
4929
4929
7762
EGSC 31
4929
1704
7762
4929
4929
7366
H2MN 45
7762
4929
7366
1704
4929
7474
Neuromatch
23
7366
4929
7762
7762
1704
7366
GREED 32
7762
1704
1704
7474
1704
1704
GEN 22
1704
4929
7474
7762
1704
1704
GMN 22
7366
4929
7366
7474
7474
7366
IsoNet (Node) 35
7474
7474
7474
1704
4929
1704
IsoNet (Edge) 335
7474
7474
7474
1704
4929
1704
GMN
2
7366
4929
7366
7474
7474
7366
IsoNet++ (Node)
7762
7762
7474
7762
7762
7366
Table 10: Best seeds for all models. For IsoNet (Edge), GMN and IsoNet+ (Node), these are computed based on MAP score on the validation split at convergence. For other models, the identification occurs after 10 epochs of training.
IsoNet++ (Edge) and all ablations on top of IsoNet++ (Node) were trained using the best seeds for IsoNet+ (Node) (as in Tables and Ablations of GMN were trained with the best GMN seeds.
For baselines excluding IsoNet (Edge), models were trained on all 5 seeds for 10 epochs and the MAP scores the validation split were considered. Full training with early stopping was resumed only for
19

---

the best seed per dataset. This approach was adopted to reduce the computational requirements for benchmarking.
Margin Selection For GraphSim, GOTSim, SimGNN, Neuromatch, GEN, GMN and IsoNet (Edge), the margins determined by Roy et al. [35] for each dataset. For IsoNet (Node), the margins prescribed for IsoNet (Edge) were used for standardization. For IsoNet++ (Node), IsoNet++ (Edge) and ablations, fixed margin of 0.5 is used.
Procedure for baselines EGSC, GREED, H2MN: They are trained on five seeds with a margin 0.5 for 10 epochs and the best seed is chosen using the validation MAP score this point. This seed is also used to train a model with margin of 0.1 for 10 epochs. The better of these models, again using MAP score the validation split, is identified and retrained till completion using early stopping.
AIDS
Mutag
FM
FR
MM
MR
GraphSim
2
0.5
0.5
0.5
0.5
0.5
0.5
GOTSim
0.1
0.1
0.1
0.1
0.1
0.1
SimGNN
0.5
0.1
0.5
0.1
0.5
0.5
EGSC B1
0.1
0.5
0.1
0.5
0.1
0.5
H2MN 45
0.5
0.5
0.5
0.5
0.5
0.1
Neuromatch 24
0.5
0.5
0.5
0.5
0.5
0.5
GREED 32
0.5
0.5
0.5
0.5
0.5
0.5
GEN 122
0.5
0.5
0.5
0.5
0.5
0.5
GMN [22
0.5
0.5
0.5
0.5
0.5
0.5
IsoNet (Node) 35
0.5
0.5
0.5
0.5
0.5
0.5
IsoNet (Edge)
[35
0.5
0.5
0.5
0.5
0.5
0.5
Table 11: Best margin for baselines used in comparison.
F.5 Software and Hardware
All experiments were run with Python 3.10.13 and PyTorch 2.1.2. IsoNet++ (Node), IsoNet+ (Edge), GMN, IsoNet (Edge) and ablations on top of these were trained on Nvidia RTX A6000 (48 GB) GPUs while other baselines like GraphSim, GOTSim etc. were trained on Nvidia A100 (80 GB) GPUs.
As estimate of training time, typically spawn 3 training of IsoNet++ (Node) IsoNet+ (Edge) on one Nvidia RTX A6000 GPU, each of which takes 300 epochs to conclude on average, with average of 6-12 minutes per epoch. This amounts GPUs by spawning 6 training runs per GPU increases the training time marginally to 2.5 days.
days of training. Overloading the
Additionally,
wandb to manage and monitor the experiments.
License
GEN, GMN, GOTSim, GREED and EGSC are available under the MIT license, while SimGNN is public under the GNU license. The licenses for GraphSim, H2MN, IsoNet (Node), IsoNet (Edge), Neuromatch could be identified. The authors were unable identify the license of the TUDatasets repository (27), which was used to compile the datasets used in this paper.
20

---

G Additional experiments
G.1 Comparison against baselines
In Tables 12 and 13 we report the Mean Average Precision (MAP), HITS@20, MRR and Preci- sion@ @20 scores for several baselines as well as the four approaches discussed our paper- - multi-layer and multi-round variants of IsoNet++ (Node) and IsoNet++ (Edge). Multi-round IsoNet++ (Edge) outperforms all other models with respect to all metrics, closely followed by multi-round +soNet++ (Node) and multi-layer IsoNet++ (Edge) respectively. Among the baselines, IsoNet (Edge) is the best-performing model, closely followed by IsoNet (Node) and GMN.
For MRR, Precision @ 20, the comparisons are less indicative of the significant boost in performance obtained by IsoNet++, since these are not aggressive metries from the point of view of information retrieval.
Meam Average Precision (MAP)
AIDS
Mutag
FM
FR
MM
MR
GraphSim X
0.356 0.016
0.472 0.027
0.477 = 0,016
0.423 + 0.019
0.415 = 0.017
0.453 + 0.018
GOTSim
0.324
0.272
0.355
0.373
0.323 0.015
0.013
SimGNN 1
0,341 = 0.019
0,283 = 0.012
0.473 # 0.016
0,341 + 0.015
0,298 = 0.012
0.379 + 0.015
EGSC 31
0.505 4: 0.02
0.476 0.022
0.609 1: 0.018
0.607 1: 0.019
0.586 a 0.019
0.58 i 0.018
H2MN 55
0.267 0.014
0.276 = 0.012
0,436 + 0.015
0,422 + 0.016
0.312 = 0.014
0.243 + 0.008
Neuromatch
0,489 1 0.024
0,576 a: 0.029
(.615 1 0.019
0.559 1 0.024
0.319 1 0.02
0.606 1 0.021
GREED
0.472 0.021
0,567 0.027
0.558 0.02
0.512 + 0.021
0.546 +: 0.021
0.528 0.019
GEN 22
0.557 0.021
0.605
0.028
0.661 1: 0.021
0.575 0.02
0.539 0.02
0.631 1 0.018
GMN 27
0.622 + 0.02
0,710 = 0.025
0.730 + 0,018
0,662 0.02
0,655 0.02
0.708 + 0.017
IsoNet (Node)
35
0.659 0.022
0.697 0.026
0.729 : 0.018
0.68 0.022
0.708 = 0.016
0.738 + 0.017
IsoNet (Edge)
35
0.690 0.02
0.706 à 0.026
0.783 1: 0.017
0.722 0.02
0.753 4 0.015
0.774 1. 0.016
Layer LooNet+ (Node)
0.756 0.019
0.81 L 0.021
0,839 1 0.015
0.802 1 0.018
0.827 1 0.015
0.841 1 0.013
multi-layer IsoNet++ (Edge)
0.795 0.018
0.805 = 0.022
0.883
0.013
0.812 + 0.016
0.862 + 0.013
0.886 0.011
multi round IsaNet++ (Node)
0.825 1: 0.016
0.851 1: 0.018
0.888 1 0.012
0.855 1 0.015
0.838 1: 0.015
0.874 1 0.011
multi-round IsoNcct+ (Edge)
0.847 0.016
0.858
0.019
0.902 + 0.012
0.875 0.014
0.902 + 0.01
0.902 # 0.01
HITS@ 20
AIDS
Mutag
PM
MM
MR
GraphSim
0.145 = 0.011
0.257
0.027
0.261 0.015
0.227
0.015
0.212 0.014
0.23 =: 0.015
GOTSim
1
0,112 + 0.011
0.088 + 0.009
0.147 + 0.011
0,166 + 0.014
0.011
0,116 0.011
SimGNN
0.016
0.087 0.008
0.235 0.015
0.155
0.111
0.160
BGSC 11
0.267 +0.023
0.243 +0.02
0,364 =0.02
0.382 +00024
0.348 +0.023
0.325 =0.021
H2MN 45
0.076 + 0.009
0.084 + 0.007
0 0.200 + 0.012
0,189 +: 0.013
0.1 0.111
0.069 + 0.004
Neuromatch 231
0.025
0.034
0.389
0.350 0.025
0.282 0.019
0,385
GREED 32
0.245 = 0.025
0.371 = 0.034
0,316 1: 0.027
0,287 1: 0.019
0,311 1: 0.024
0,277 =: 0.023
GEN 23
0.321 0.026
0.429
0.035
0.448 0.03
0.368 0.026
0.292 0.024
0,391 0.025
GMN
0.029
0.544 0.035
0.027
0.45 0.027
0.423
0.49 0.026
IsoNet (Nede)
351
0.138 = 0.028
0.509 : 0.034
0.525 4: 0.026
0.475 = 0.03
0.493 1 0.023
0.532 = 0.025
IsoNet (Edge)
0,479 0.029
0.529
0.035
0.613
0.026
0.538 0.029
0:571 + 0.023
0.601 0.027
muln-layer IsnNets (Node)
0.37 + 0.029
0.672 0.033
0.744 + 0.027
0.657 + 0.031
0.68 + 0.025
0.707 + 0.024
multi-lnyer IsoNet (Fdge)
0.636 + 0.029
0.671 + 0.035
0.775
0.026
0.67 - 0.028
0.743 + 0.024
0.776 + 0.021
muli-round IsnNete (Node)
0.672 0.027
+
0.797
0.737
0.026
0.702
0.025
0.755
mult-rrundd IsoNete+ (Edge)
0.705 = 0.028
0.749 1 0.032
0.813 = 0.023
0.769 = 0.026
0.809 1 0.019
0.803 : 0.02
Table 12: Replication of Table 3 with standard error. Comparison of the two variants of IsoNet++ (IsoNet++ (Node) and IsoNet++ (Edge)) against all the state-of-the-art graph retrieval methods, across all six datasets. Performance is measured in terms average precision MAP and HITS @ 20. In all cases, we used 60% training, 15% validation and 25% test sets. The first five methods apply neural network on the fused graph-pair representations. The next six methods apply asymmetric hinge distance between the query and corpus embeddings similar to our method. The numbers with green and yellow indicate the best, second best method respectively, whereas the numbers with blue indicate the best method among the baselines. (MAP values for IsoNet++ (Edge) across FM, MM and MR are verified to be not exactly same, but they take the same value until the third decimal).
21

---

Mean Reciprocal Rank (MRR)
AIDS
Murag
FM
FR
MM
MR
GraphSim 2
0.71 =0.039
0.795
#0.037
0.885 #0.029
=0032
0.818 =0.334
0.789 -0.07
GOTSim
0.568 +0.038
0.584
#0.037
0.775 #0.037
0.716
0.459 #0.05
0.525 =0.047
SimGNN
0.533 10.038
0.644 10.04
0.866 10.031
0.753 10.038
0.669 10.04
0.638 0.046
EGSC
10.026
10.041
10.021
10.02
10.025
-0,02
H2MN +5
0.46 =0.047
0.565 +0.042
0.822 #0.035
0.817 =0.034
0.386 +0.099
0.62 #0.041
Neuromatch
10.035
0.855 10.035
00028
0.929 00022
0:87 10:027
00006
GREED 01
0.789 +0.035
0.805 +0.034
0.834 +0.033
0.834 =0.032
0.894 0.0028
0,759 =0.039
GEN 22
0.865 +0.028
0.895 +0.029
0.889 +00026
0.878 =0.028
0.814 +00034
0.878 =0.026
GMN 22
0.877 1:0027
0.923 10.023
0.949 10.019
0.947 00.199
0.928 10.023
0.922 00.022
IsoNet (Node)
35
0.916 100024
0.887 +0.029
0.977 10.013
0.954 00.088
0.956 10.018
0.954 20.018
IsoNet (Edge) 35
0.949 10.02
0.926 #00026
0.973 #0.013
0.956 #0,018
0.98 20.011
0.948 00.019
multi-layer IsoNet++ (Node)
0.956 10.018
0,954 #0.018
1.0 #0.0
0.978 =0.033
0.98 #0.011
1.0 =0.0
multi-layer IsaNet+ (Fdge)
+0.011
0.976
0.991 +00.009
+0.009
+00009
0.993 000007
multi-round IsoNet++ (Node)
0.993 #0.007
0
#0.014
1.0 #0.0
0.993 #0.007
0.993 =0.007
0.993 =0.007
round IsoNet++ (Edge)
0.983
0.991
1.0
1.0 10.00
1.0 000
Precision
AIDS
Mutag
FM
FR
MM
MR
GraphSim 2
0.474 10.025
0.577
10.033
0.679 100023
0.617 10,028
0.604 10.028
0.638 10.026
GOTSim
11
0,386 10.024
0.325 10.021
0.479 10.027
0.519 10.03
0.409 10.027
0,421 10003
SimGNN I
0.44 +0.026
0,33 +0.022
0.626 +0.026
0.471 +0,029
0,414 +0.026
0.512 +0.032
EGSC X
+0.023
0.608 +0.034
0.79 +0.022
0.766 +0.021
0.739 +0.023
0.74 +0.021
H2MN 45
0.28 10.026
0.34 10.023
0.587 10.024
0.563 10.026
0.399 10.028
0.308 10.017
0.615 +0.03
0.689 +0.032
0.809 40.022
0.725 +0.027
0.694 +0.027
0.751 +0.023
GREED 32
0.591 =0.024
0.661 10.03
0.689 20.026
0.642 20.028
0.699 10.028
0.624 10.029
GEN 22
0.674 =0.024
0.721 =0.03
0.783 10.023
0.678 #0.022
0.64 00.02
0.759 10.021
GMN 22
0.751 +00022
0.82 +0.023
0,852 +0.02
0,809 40.019
0.783 +0.022
0.832 +0.018
IsoNet (Node)
35
0.791 :00022
0,803 +00029
0,866 10.018
0,803 10.022
0.844 10.015
0.863 10.016
IsoNet (Fidge)
35
0.822 10.022
0.812 10.028
0.896 10.016
0851 10.017
0.877 10.014
0.875 10.017
mulli layer booei++ (Node)
0.873 10.088
0.897
10.018
0.935
10.022
0.917
10.022
0.93 10.13
0.931 10.012
multi-layer IsoNot++ (Edge)
0.905 =0.015
0.883
+0.021
0.958 =0.01
0.93 +0.01
0.953 #0.01
0.976
malli round IonNet+ (Node)
0.932 20012
0,943
10.011
0.977 10.01
0,981 10.008
0.949 10.011
0.963 10.008
multi-round IsoNet++ (Edgo)
0.946
=0.012
0.931
=0.014
0.973
=0.007
0.963
+00008
0.98 +0.005
0.987 +0.003
Table 13: MRR and Precision @2 20 of corresponding models from Table with standard error. Comparison of the two variants of IsoNet++ (IsoNet++ (Node) and IsoNet++ (Edge)) against all the state-of-the-art graph retrieval methods, across all six datasets. Performance is measured in terms MRR and Precision @00. In all cases, we used 60% training. 15% validation and 25% test sets. The first five methods apply neural network the fused graph-pair representations. The next six methods apply asymmetric hinge distance between the query and corpus embeddings similar to our method. The numbers with green and yellow indicate the best, second best method respectively, whereas the numbers with blue indicate the best method among the baselines.
G.2 HITS@ 20, MRR and Precision @ 20 for multi-round IsoNet++ and multi-layer IsoNet++
Table 14 compares multi-round and lulti-layer IsoNet++ with respect to different metrics. We observe that multi-round IsoNet++ outperforms multi-layer IsoNet++ by a significant margin when it comes to all metrics, both when the models are node-based or edge-based. This reinforces the observations from MAP scores noted earlier Table Note that a minor exception occurs for MRR but the scores are already so close to that this particular metric can be discounted and our key observation above still stands.
G.3 Refinement of alignment matrix across rounds and layers in multi-round IsoNet++ and multi-layer IsoNet++
The node (edge) alignment calculated after round is denoted as P. (S,). We accumulate such alignments across multiple rounds. This also includes Pr (Sr) which used to compute the relevance distance in Eq. 14 (Eq. 25 We wish to compare the predicted alignments with ground
22

---

HITS@20 20
AIDS
Mutag
MM
MR
Edge Node
Multi-layer
0.57
0.672
0.744
0.657
0.68
0.707
Multi-round
0.672
0.732
0.797
0.737
0.702
0.755
Multi-layer
0.626
0.671
0.775
0.67
0.743
0.776
Multi-round
0.705
0.749
0.813
0.769
0.809
0.803
Mean Reciprocal Rank (MRR)
AIDS
Mutag
FM
FR
MM
MR
Node
Multi-layer
0.956
0.954
1.0
0.978
0.98
1.0
Multi-round
0.993
0.971
1.0
0.993
0.993
0.993
Edge
Multi-layer
0.984
0.976
0.991
0.987
0.987
0.993
Multi-round
1.0
0.983
0.991
1.0
1.0
1.0
Precision @
AIDS
Mutag
FM
FR
MM
MR
Edge Node
Multi-layer
0.873
0.897
0.935
0.917
0.93
0.931
Multi-round
0.932
0.943
0.957
0.961
0.949
0.963
Multi-layer
0.905
0.883
0.958
0.93
0.953
0.976
Multi-round 0.946
0.931
0.973
0.963
0.98
0.987
Table 14: Multi-round multi-layer refinement. First and the last two rows of each table report HITS @ 20, IsoNet++ (Node) and IsoNet++ (Edge) respectively. Rows colored green and yellow indicate the best and second best methods respectively.
MRR and Precision@
truth alignments. We expect final aligmment matrix P. (St) to be one of them. We determine the closest ground truth matrices P and S" by computing maxp Tr Tr P) and maxş Tr(S, S) for the closest ground-truth alignment
IsoNet++ (Node) and IsoNet++ (Edge) respectively. We now P to compute Tr(P, P*) for I. E (T). For each I, we plot a histogram with bin width 0. that denotes the density estimate P(Tr(P, P))). The same procedure adopted for edges, with S used instead of P The histograms are depicted in Figure 15 We observe that the plots shift rightward with increasing The frequency of graph pairs with misaligned P. (S,) decreases with rounds while that with well-aligned P. (S,) increases.
Here, we also study aligmments obtained through multi multi-layer refinement. We adopt the same procedure as in Section G.3 One key difference is that the node/edge alignments are computed after every layer and are accumulated across layers [K. In Figure we observe that the plots, in general, shift rightward with increasing k. The frequency of graph pairs with misaligned P. (S,) decreases with rounds & while that with well-aligned Pş (S²) increases.
G.4
Comparison across alternatives of multi-layer IsoNet++ (Node) and multi-round IsoNet+ (Node)
In Table 16
compare different alternatives the multi-round and multi-layer variants of IsoNet+ (Node). In particular, we consider four alternatives Node partner (equation shown in Section 4 Node partner (with additional MLP) [Appendix
E.3 Node pair partner (ınsg only) [Appendix E.4 and IsoNet++ (Node). We observe that for all metrics, IsoNet++ (Node) and Node pair partner (msg only) dominate the other alternatives most cases. This highlights the importance of node pair partner interaction for determining the subgraph isomorphism relationship between two graphs. For the multi-round variant, IsoNet++ (Node) outperforms Node pair partner (msg only) four of the datasets and is comparable slightly worse in the other two. Once again, comparisons based on MRR break down because it does not cause a strong differentiation between the approaches.
23

---

T
-1
P(Tr pt)
0.16
-1=2
P[Tr(P P))
0.16
-k
P(Tr(S] 5*)
0.12
((T((S 8Y)
0.12
-k
0.12
Multi Round
-1
0.12
Multi- Layer
-k
-k
0.05
Multi- Round
0.d8
Multi-Lape
-k
-A
0.08
-k
-k
10
10
Tr( P*)
Tr(P2 PT)
Tr(S 5*)
Tr(8)
p(TxPP
0.12
0.10
Multi- Round
MUTAG
P(Ti(P P))
0.12
Multi- Layer
=
P(TT(S))))
MUTAG Multi- Round
P[TRSS S')) ()))
0.12
Multi-Layer
-k
-k=0
-k
-
-k
0.04
0.04
0.04
10
10
10
Tr(P PT)
Tr(P P*)
S*)
Tr(S S*)
0.40
TT<P P))
0.16
0.08
0.12
0.20
Multi Round
PTC-FM
-f
P( P))
0.0s-
0.20
0.16
0.12
Multi Layer
PTC-FM
-k
-k
-k=4
-k
0.13
0.24
0.56
0.33
0.20
Multi Round
-1
-1
Tr ST
0.12
0.21
0.32
0.20
PTC-FM Multi-Layer
-k-
-K
-k=4
0.04
0.04
0.06
0.01
10
5
10
16
5
10
Tr(P, P*)
Tr P*)
Tr(S 5*)
Tr(S
P(TT(P PT)
0.16
PTC.FR
[(T(PP) P')
036-
PTC-FR
-k
-k
0.28
0.21
PTC.FR
0.25
PTC-FR
-k
-k
Multi- Round
Multi- Layer
Multi- Round -2
Multi-Layer
-k
0.08
0.08
-k=5
-k
10
10
10
5
10
T PT)
Tr(P. P*)
Tr(S S*)
Tr(S, 8*)
+
0.16
0.3
0.24
1
0.24
P(Tr(P pt)
0.12-
PTC-MM
P( P")
0.12-
PTC.MM
PTC-MM
-
p(T((S) (")) ( 5')
PTC.MM -k
Layer
0.16
-1
P(Tr(S)
0.36-
Multi Layer
0.0s
PT
0.12-
0.08
0.06
0.91
0.04
0.11
10
10
TT(P P*)
Tr(P. P*)
TT(S 8*)
Tr(S 8*)
P[Tr(P pm)
PTC-MR -1
PTC-MR
pTT (*))
PTC-MR
PTC-MR
0.12
Multi-Round
-1
Multi- Layer
matii-oound-e -t
0.k
Multi- Layer
0.08
0.08
0.04
0.04
0.1-
10
10
10
10 Tr(S S*)
TT(P P*)
Tr P*)
Tr(S S*)
Figure 15: Similar to Figure
6 we plot empirical probability density of P(Tr(P,TTP'' P*)) and
ST S*)) for different values of lazy multi round updates and p(Trp P*)) and ((T S*)) for different values for eager multi layer updates. The first (last) two plots the left (right) of each row are for multi-round IsoNet++ (Node) (multi-round IsoNet++ (Edge)).
24

---

Mean Average Precision (MAP)
AIDS
Mutag
MM
MR
Multi-Round Multi- Layer
Node partner (with additional MLP)
0.692
0.782
0.822
0.776
0.777
0.803
Node pair partner (msg only)
0.765
0.792
0.876
0.823
0.843
0.848
Node partner
0.668
0.783
0.821
0.752
0.753
0.794
IsoNet++ (Node)
0.756
0.81
0.859
0.802
0.827
0.841
Node partner (with additional MLP)
0.815
0.844
0.868
0.852
0.818
0.858
Node pair partner (msg only)
0.818
0.833
0.897
0.831
0.852
0.871
Node partner
0.776
0.829
0.851
0.819
0.844
0.84
IsoNet++ (Node)
0.825
0.851
0.888
0.855
0.838
0.874
HITS@
AIDS
Mutag
FM
FR
MM
MR
Multi- Layer
Node partner (with additional MLP)
0.479
0.634
0.677
0.611
0.608
0.64
Node pair partner (msg only)
0.577
0.651
0.775
0.682
0.719
0.703
Node partner
0.433
0.639
0.678
0.58
0.571
0.624
IsoNet+-+ (Node)
0.57
0.672
0.744
0.657
0.68
0.707
Multi-Round
Node partner (with additional MI.P)
0.658
0.727
0.756
0.738
0.667
0.743
Node pair partner (msg only)
0.671
0.717
0.807
0.696
0.728
0.753
Node partner
0.603
0.702
0.736
0.686
0.721
0.695
IsoNet++ (Node)
0.672
0.732
0.797
0.737
0.702
0.755
Mean Reciprocal Rank (MRR)
AIDS
Mutag
FM
FR
MM
MR
Multi- Layer
Node partner (with additional MLP)
0.909
0.941
0.965
0.964
0.966
0.984
Node pair partner (msg only)
0.97
0.956
0.964
0.993
0.978
1.0
Node partner
0.917
0.945
0.964
0.987
0.958
0.969
IsoNet++ (Node)
0.956
0.954
1.0
0.978
0.98
1.0
Multi-Round
Node partner (with additional MLP)
0.987
0.944
0,993
0.987
0.963
0.983
Node pair partner (msg only)
0.984
0.958
0.993
0.98
0.984
0.984
Node partner
0.984
0.949
0.993
0.978
0.978
0.97
IsoNet++ (Node)
0.993
0.971
1.0
0.993
0.993
0.993
Precision @ 20
AIDS
Mutag
FM
FR
MM
MR
Multi-Round Multi-L Layer
Node partner (with additional MLP)
0.817
0.867
0.913
0.913
0.883
0.914
Node pair partner (msg only)
0.871
0.886
0.957
0.937
0.927
0.937
Node partner
0.799
0.866
0,919
0.877
0.873
0.885
IsoNet++ (Node)
0.873
0.897
0.935
0.917
0.93
0.931
Node partner (with additional MLP)
0.921
0.917
0.936
0.951
0.921
0.945
Node pair partner (msg only)
0.923
0.913
0.969
0.951
0.957
0.957
Node partner
0.875
0.921
0.933
0.942
0.939
0.941
IsoNet++ (Node)
0.932
0.943
0.957
0.961
0.949
0.963
Table 16: Effect of node pair partner interaction in IsoNet++ (Node). Table shows the comparison of IsoNet++ (Node) with three different alternatives. The first table reports MAP values. second reports HITS@20, third reports MRR and fourth reports Precision @ 20. In each table, the first rows report metrics for multi-layer refinement and the second two rows report metrics for multi-round refinement. Rows colored green and yellow indicate the best and second best methods in their respective sections.
25

---

G.5 Comparison of GMN with IsoNet++ alternative for multi-layer and multi-round
Table 17 we modify the GMN architecture to include node pair partner interaction the message- passing layer. Based the reported metries, observe that there is substantial improvement upon including information from node pairs in GMN, which driven by a non-injective mapping (attention). This indicates that injectivity of the doubly stochastic matrix in formulation is crucial towards the boost in performance obtained from node pair partner interaction as well.
Mcan Average Precision (MAP)
AIDS
Mutag
FM
MM
MR
GMN
0.622
0.71
0.73
0.662
0.655
0.708
Multi-Layer
Node pair partner
0.579
0.732
0.74
0.677
0.641
0.713
GMN
0.629
0.699
0.757
0.697
0.653
0.714
Multi-Round
Node pair partner
0.579
0.693
0.729
0.69
0.665
0.705
HITS @ 20
AIDS
Mutag
FM
MM
MR
GMN
0,397
0.544
0.537
0.45
0.423
0.49
Multi-Layer
Node pair partner
0.346
0.567
0.551
0.476
0.411
0.5
GMN
0.403
0.533
0.562
0.494
0.431
0.502
Multi-Round
Node pair partner
0.344
0.528
0.54
0.502
0,462
0.506
Mean Reciprocal Rank (MRR)
AIDS
Mutag
FM
MM
GMN
0.877
0.923
0.949
0.947
0.928
0.922
Multi-Layer
Node pair partner
0.827
0.897
0.958
0.877
0.918
0.92
GMN
0.905
0.862
0.958
0.956
0.906
0.921
Multi-Round
Node pair partner
0.811
0.901
0.907
0.908
0.964
0.92
Precision @ 20
AIDS
Mutag
GMN
0.751
0.82
0.852
0.809
0.783
0.832
Multi-Layer
Node pair partner
0.7
0.833
0.861
0.797
0.792
0.846
GMN
0.753
0.795
0.885
0.829
0.792
0.842
Multi- Multi-Round
Node pair partner
0.694
0.794
0.847
0.835
0.802
0.825
Table 17: Effect of node pair partner interaction GMN. The tables compare GMN with its IsoNet++ alternative. The table reports
values, second table reports HITS@20 values, third table reports MRR values and the fourth table reports Precision 20. In cach table, the first two rows report metrics for multi-layer refinement and the second two rows report metrics for multi-round refinement. Rows colored green and yellow indicate the best and second best methods according the respective metrics.
26

---

G.6 Variation of IsoNet++ (Node) and IsoNet++ (Edge) with different T and K
In this section, we analyze the accuracy and inference time trade-off of multi-round lazy and multi- layer eager variants of IsoNet++ (Node) and IsoNet++ (Edge). In the following tables, show the MAP and inference time. Additionally, we also analyze the trade-off of GMN and IsoNet (Edge). The T, K parameters for different models are so chosen that they be compared against each other while fixing the inference time to be roughly similar. For instance, multi-round lazy IsoNet++ (Node) with T = 5, K 5 maps multi-layer eager IsoNet++ (Node) with K 8, allowing for direct comparison of performance without caring much about different compute. Note that in below tables, models are listed in order of increasing inference time (i.e. increasing K or T)).
In tables and 20 we show variations for multi-round lazy IsoNet++ (Node) for fixed T and fixed K respectively. We observe that with fixed T', increasing K from 5 to 10 doesn't t improve the model significantly. For fixed K, performance (in terms of MAP) improves notably when increasing T from
3 to 5.
In table 21 we show variations for multi-layer eager IsoNet++ (Node) for varying We observe that except for drop K 7, the performance of the model improves as we increase K. In fact, at K = 8, the performance surprisingly good, even outperforming the similarly timed T 5, K variant of lazy multi-round IsoNet++ (Node) on both AIDS and Mutag.
In tables 22 and 23 we compare variants of multi-round lazy IsoNet++ (Edge) with fixed T and fixed K respectively. We observe that when I' is fixed and K is increased, the gain is marginal. We observe a significant gain When K is fixed and T is increased from 4.
In table 24 we study the trade-off for multi-layer eager IsoNet++ (Edge) for varying K. We observe that with increasing K, the performance continues improve and peaks K = 8. Note that even at this K, the performance of multi-layer eager IsoNet++ (Edge) is worse than a similarly timed variant (T 55 K 5) of multi-round IsoNet++ (Edge).
In table 25
we show variations for GMN for varying K. We observe marginal gains while increasing 10 to K 12, the performance drops.
K. From K
In table 26 show how performance varies for IsoNet (Edge) for varying K. We observe that the model does not improve with increasing K.
1.0
Lazy e Eager
GMN
1.0
Lazy e Eager
GMN
MAP
MAP
0.8
0.8-
50
80
110
140
50
80
110
140
Inference time ms)
Inference time ms)
(a) Node, AIDS
(b) Edge, AIDS
1.0
Lazy
Eager GMN
1.0
Lazy
Eager GMN
MAP
MAP
0.8
0.8
0.6
50
80
1i0
140
0.6
50
80
110
140
Inference time (in ms)
Inference time (in ms)
(c) Node, Mutag
(d) Edge, Mutag
Figure 18: Trade off between MAP and inference time (batch size= 128).
27

---

Mean Average Precision (MAP)
AIDS
Mutag
FM
FR
MM
MR
T.3,K= =
0.825
0.851
0.888
0.855
0.838
0.874
= 10
0.774
0.855
0.898
0.811
0.855
0.882
Inference time (in ms)
AIDS
Mutag
FM
FR
MM
MR
T 5
80.11
80.99
81.01
81.24
80.94
80.25
-= 10
99.11
99.31
99.28
99.48
99.37
99.36
Table 19: MAP and inference time trade-off of variants of multi-round lazy IsoNet++ (Node) with fixed T.
Rows colored green indicate the best K according to the MAP score.
Mean Average Precision (MAP)
AIDS
Mutag
FM
FR
MM
MR
= =5 5
0.825
0.851
0.888
0,855
0.838
0.874
T 4,K =
0.799
0.833
0.892
0.858
0.867
0.891
T 5, 55
0.845
0.875
0.919
0.883
0.894
0.897
Inference time (in ms)
AIDS
Mutag
FM
FR
MM
MR
T 3, 5 80.11
80.99
81.01
81.24
80.94
80.25
T 4, 4,4
101.33
100.99
100.95
100.46
100.59
100.87
= 5, K 5
123.18
124.19
123.61
122.79
123.33
122.74
Table 20: MAP and inference time trade-off of variants of multi-round lazy IsoNet++ (Node) with fixed K.
Rows colored green and yellow indicate the best and second best T according to the MAP score.
Mean Average Precision (MAP)
Inference time (in ms)
AIDS
Mutag
AIDS
Mutag
0.756
0.81
79.02
79.15
K =
0,813
0.821
= 94.99
95.33
K = 7
0.808
0.842
K = 110.78
111.09
K 0.883
0.874
K 126.48
126.6
Table 21: MAP and inference time trade-off of variants of multi-layer eager IsoNet++ (Node) with increasing
K. Rows colored green and yellow indicate the best and second best K according to the MAP score.
Mean Average Precision (MAP)
Inference time (in ms)
AIDS
Mutag
AIDS
Mutag
3 K
0.847
0.858
T 3, K =5
64.39
66.03
= 10
0.865
0.871
T 3, K = 10
88.59
90.76
Table 22: MAP and inference time trade-off variants multi-round lazy IsoNet++ (Edge) with fixed
Rows colored green indicate the best K according to the MAP score.
Mean Average Precision (MAP)
Interence time (in ms)
AIDS
Mutag
AIDS
Mutag
T 3, 5
0.847
0.858
T K,
64.39
66.03
T -=
0.881
0.887
T T=1,K=
85.02
87.33
T 5,
0.886
0.909
106.24
109.1
Table 23: MAP and inference time trade-off of variants of multi-round lazy IsoNet++ (Edge) with fixed K. Rows colored green and yellow indicate the best and second best 7 according to the MAP score.
28

---

Mean Average Precision (MAP)
Inference time (in ms)
AIDS
Mutag
AIDS
Mutag
0.795
0.805
72.63
73.46
K =
0.828
0.837
K =
86.03
87.77
K 0.852
0.848
K 100.26
102.6
K 0.862
0.851
K 114.33
115.01
Table 24: MAP and inference time trade-off of variants of multi-layer cager IsoNet++ (Edge) with increasing
K. Rows colored green and yellow indicate the best and second best K according to the MAP score.
Mean Average Precision (MAP)
AIDS
Mutag
FM
FR
MM
MR
K
5 5
0.622
0.710
0.730
0.662
0.655
0.708
K 8
0.641
0.731
0.745
0.701
0.658
0.711
K 10
0.679
0.736
0.741
0.712
0.691
0.74
K
0.651
0.728
0.743
0.697
0.687
0.699
Inference time (in ms)
AIDS
Mutag
FM
MM
MR
K
52.94
53.16
53.23
53.12
53.32
53.34
K = 8
83.97
84.47
84.64
84.38
85.41
84.51
K 10
104.87
105.21
105.72
105.33
105.66
105.73
K 12
125.99
126.33
126.53
126.39
126.79
126.59
Table 25: MAP and inference time trade-off of variants of GMN with increasing K. Rows colored green and yellow indicate the best and second best K according to the MAP score.
AIDS
Inference time (in ms)
K
0.69
19.77
0.717
20.83
0.697
21.96
K =
0.709
23.02
Table 26: MAP and inference time trade-off of variants IsoNet (Edge) with increasing Rows colored green and yellow indicate the best and second best 7 according to the MAP score.
29

---

G.7 Contribution of refining alignment matrix in inference time
GMN, computing the embeddings of nodes after the message passing step at each layer dominates the inference time. However, in the case of IsoNet++ models, observe the refinement of the alignment matrix at each layer or round to also be time-intensive. In table [27] we show the contribution of embedding computation and matrix updates to the total inference time. The updates to P constitute the largest share of inference time for multi-layer variants. This can be attributed to the refinement of P after every message passing step, equaling the frequency of embedding computation. In the case of multi-round variants, both embedding computation and updates to contribute almost equally since P refined only the end of each round, after several layers of message passing alongwith embedding computation.
Models
Embedding Computation
Matrix Updates
multi-layer IsoNet++ (Node)
13.7
68.3
multi-layer IsoNet++ (Edge)
19.7
76.3
multi-round IsoNet++ (Node)
34.1
47.8
multi-round IsoNet++ (Edge)
54.9
39,9
Table 27: Inference contribution of embedding computation and matrix updates by multi-layer and multi-round + (Node) and IsoNet++ (Edge) models.
30

---

G.8 Transfer ability of learned models
In this section, we evaluate the transfer ability of each trained model across datasets. In table 28 report the Mean Average Precision (MAP) scores for models trained using the AIDS and Mutag datasets respectively evaluated on all six datasets. We observe that despite a zero-shot transfer from one of the datasets all others, variants of IsoNet++ show the best accuracy.
Test other datasets when trained AIDS
AIDS
Mulag
FM
FR
MM
MR
GraphSim
0.356
0.225
0.192
0.198
0.210
0.215
GOTSim
0.324
0.275
0.370
0.339
0.314
0.361
SimGNN
0.341
0.264
0.374
0.344
0.331
0.383
EGSC
505
0.255
0.473
0.451
0.447
0.499
H2MN 45
0.267
0.272
0.319
0.281
0.262
0.297
Neuromatch 23
0.489
0.287
0.442
0.403
0.386
0.431
GREED 32
0.472
0.307
0.477
0.452
0.436
0.490
GEN 22
0.557
0.291
0.445
0.427
0.437
0.496
GMN 22
0.622
0.342
0.569
0.544
0.532
0.588
IsoNet (Node)
0.659
0.459
0.612
0.562
0.640
IsoNet (Edge)
0.690
0.468
0.620
0.568
0.624
0.627
multi-layer IsaNet++ (Node)
0.756
0.685
0.825
0.767
0.781
0.794
multi-layer IsoNet++ (Edge)
0.795
0.683
0.800
0.751
0.792
0.785
multi-round IsoNet++ (Node)
0.825
0.702
0.828
0.777
0,800
0.825
multi-round IsoNet++ (Edge)
0.847
0.741
0.846
0.799
0.833
0.836
Test across other dutasets when trained on Mutag
AIDS
Mutag
FM
FR
MM
MR
GraphSim
0.188
0.472
0.190
0.193
0.205
0.198
GOTSim
0.194
0.272
0.185
0.192
0.202
0.182
SimGNN
0.206
0.283
0.203
0.209
0.220
0.195
RGSC 3T
0.296
0.476
0.391
0.333
0.309
0.355
H2MN
0.209
0.276
0.204
0.207
0.223
0.197
Neuromatch 23
0.275
0,576
0.368
0,304
0.304
0.325
GREED 32
0.328
0,567
0.388
0.335
0.356
0.370
GEN 22
0.278
0.605
0.359
0.308
0.312
0.330
GMN 22
0.299
0.710
0.434
0.361
0.389
0.394
IsoNet (Node)
35
0.458
0.697
0.503
0.456
0.446
0.486
IsoNet (Edge)
35
0.472
0.706
0.499
0.438
0.467
0.489
multi-layer IsoNet++ (Node)
0.601
0.810
0.695
0.611
0.628
0.614
multi-layer IsoNet++ (Edge)
0.527
0.805
0.558
0.507
0.560
0.563
multi-round IsoNer++ (Node)
0.645
0.851
0.679
0.626
0.652
0.655
multi-round IsoNet++ (Edge)
0.625
0.858
0.639
0.598
0.634
0.650
Table 28: Test MAP of all graph retrieval methods on different datasets, when they were trained on AIDS (top half) and Mutag (bottom half) dataset. The numbers with green and yellow indicate the best, second best method respectively.
31

---

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: Section 1.1 discusses the paper's contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors? Answer: [Yes]
Justification: Appendix A discusses the limitations of our work. Details about computational efficiency are included in the main paper well as in Appendix G.6 expressed explicitly as the running time each approach.
Guidelines:
The answer NA means that the paper has no 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 a 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 soll-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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be 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 low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails to 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 fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The paper includes one theorem, which is noted and proved in Appendix D.5
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.
32

---

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 of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper introduces new architectures and the designs of each of these
discussed in the main paper under Sections 3.2 3.3 and Appendices D E] Hyperparameters.
training procedure, hardware and random seeds for all experiments noted in Appendix [ 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 to 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, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it 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 (c.g.. in the case of large language model), releasing of a model checkpoint, or other means that 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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a 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 (e.g.. with an open-souree dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should 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: Uploaded in github.
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
33

---

reproducible, they including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
httpssccccpbccccccceceeceecccccc wetccc/giiiee htdp:////u.deee/eeeuubbbbsssi CodeSubmissss wwwiebbmmsssiiioi ssinssiiccyyyyyy 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: Important parameters that are required to understand and appreciate the results are noted as and when required. Hyperparaaetters training procedure, hardware and random seeds for all experiments are noted in Appendix Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail
that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Appendix G. includes standard error for the metrics reported in the paper, which includes Mean Average Precision (MAP) and HITS @ 20, computed across each query graph in the test split. The section also reports the method of calculation of the standard error.
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, 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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2- 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 are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
34

---

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 experiment??
Question:
Answer: [Yes]
Justification: Types of GPUs and inference time are reported in Appendices F.5 and G.6
respectively. Other details about the training setting are mentioned point-wise in Appendix 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 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 Answer: [Yes]
Justification: The authors have studied the ethics guidelines and find the work to conform well them.
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 socictal impacts of the work performed? Answer: [Yes]
Justification: Broader societal impacts (both positive and negative) discussed in Ap- pendix C
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended
(e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g.. deploymennt 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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
35

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The datasets used in the paper are derived from public graph datasets widely used by researchers and the authors are not aware of any risks for misuse posed by them.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (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: The related work and datasets applicable to this work have been cited in Appendices B and [.I respectciyy. Best effort was made by the authors to determine the
licenses the datasets and existing architectures, and are included in Appendix F.6
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwprspppesataeee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Details of the models and datasets are discussed Appendices D and respectively. Datasets used in the paper are publicly accessible. The code is submitted with the paper as a supplementary item and anonymized & well-documented.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
36

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The experiments performed in this paper do not involve human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The experiments performed in this paper do not involve human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 expect authors to adhere to 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.
37


Reviews:
[{"review_id": "I6Jn5TTcWv", "reviewer": "Reviewer_sihU", "summary": "The paper proposes EinsMatch, a neural approach for graph retrieval, i.e. the problem of finding  the best candidates of a corpus of graphs that contain a subgraph isomorphic to a given query graph. EinsMatch is based on a Graph Neural Network architecture and introduces technical improvements over existing methods: (i) message-passing iterations across query and candidate graphs which are guided by an injective alignment; (ii) the iterations are lazy in the sense that multiple of them are computed with a fixed alignment before refining it; (iii) node pairs are considered as potential partners instead of single nodes in the message-passing steps. In addition, the authors propose a variant which works at the level of edges and natively leverages edge matchings. This variant seems to be the most competitive one in the experiments the authors run. In general, EinsMatch significantly outperforms a variety of other methods. The authors also report insightful ablation studies on the number of alignment rounds and message passing layers.", "questions": "Please see Weaknesses. Also:\n\n- The readers refer oversmoothing problems in some of the previous methods. Can they expand on how their approach side-steps this?\n\n- Can the authors better explain lines 333 — 336? I found them hard to understand.\n\n- How does the computational complexity compare with that of IsoNet?", "limitations": "The authors do not seem to explicitly discuss them in the main corpus, but mention two aspects in Appendix A.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed architecture nicely interpolates between late and early aggregation approaches, whilst ensuring injectiveness of the candidate mapping. In this sense, it appears as a sensible generalisation of other approaches.\n\n- The proposed model is highly performant if compared with other methods, and, in particular offers a competitive accuracy-inference time tradeoff if compared with other approaches as GMNs.\n\n- The reported ablation studies are insightful in that they shed light on the impact of important hyperparameters, namely the number of layers and rounds.", "weaknesses": "- I found the paper somewhat hard to follow. The contributions are rather technical and only one single figure in the manuscript illustrate the approach. I think it would be particularly helpful if the authors improved on this aspect.\n\n- Still on the presentation side, I found it hard to clearly understand the specific contributions w.r.t. previous works. I believe the paper would increase in quality if the authors would state these more clearly in the main corpus.\n\n- The authors only provide a high-level intuition behind some specific technical contributions, e.g. the choice of working with node-pair partners. Would it be possible to refer to more formal arguments around those?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and insightful review. \n\n> *paper hard to follow...only one single figure*\n\nIn the global rebuttal PDF, we include another diagram (Figure A) to distinguish between node-pair interaction (earlier work) vs node-pair partner interaction, and also contrast them with IsoNet. If our paper gets accepted, we will include this diagram in the paper.\n\n> *contributions w.r.t. previous works.*\n\nEarly interaction models are conventionally more powerful in other domains [a,b], yet in the context of subgraph retrieval, GMN (early interaction) is outperformed by IsoNet (late interaction).\n\n[a] A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling entailment.\n\n[b] Entailment as Few-Shot Learner.  S Wang, H Fang, M Khabsa, H Mao, Hao Ma. arXiv:2104.14690v1\n\nIn this work, we build a new early interaction model, which addresses the limitations of prior work, also using lessons from IsoNet and GMN. Here, we further elaborate on our contributions. \n\n1. GMN does not use any explicit alignment structure. They use a non-injective attention mechanism, which changes from layer to layer. In our work, we model inter-graph alignments as relaxed bijective permutation maps that are *proposed*, then $K$ layers of GNN *score* the proposal, leading to a *refined* proposal. Thus, the node embeddings of one graph become dependent on the paired graph, implementing early interaction. To the best of our knowledge, this is the first early interaction model for subgraph matching where proposed alignments and GNN layers help refine each other.\n1. When we compute the message of  node-pair $(u,v)$ in $G _q$, we also use $(u',v')$ in $G _c$ which match with $(u,v)$. Therefore, for $u\\in G  _q$, the node embedding $\\mathbf{h} ^{(q)}  _u$ not only depends on nodes in $G _c$ that align with $u$, but also on those nodes in $G _c$, which are aligned with the $\\text{Nbr}(u)$ neighbors of $u$. In terms of a formal argument, we have:\n$$\\mathbf{h} ^{(q)}  _u = f(\\mathbf{h} ^{(q)}  _u, \\\\{ \\mathbf{h} ^{(q)}  _v: v\\in  \\text{Nbr}(u) \\\\}, \\\\{\\mathbf{h} ^{(c)}  _ {v'} : v' \\in G _c \\text{  aligns with some  } v \\in \\text{Nbr}(u)\\\\})\\ \\ \\ (1)$$\nExisting early interaction models like GMN  do not capture signals from $\\\\{v' \\in G _c \\text{  aligns with some  } v \\in \\text{Nbr}(u)\\\\}$, they only capture signal from $u' \\in G _c$ that matches with $u$.  Hence, in GMN,  we have:\n$$\\mathbf{h} ^{(q)}  _u = f(\\mathbf{h} ^{(q)}  _u, \\\\{\\mathbf{h} ^{(q)}  _v: v\\in  \\text{Nbr}(u)\\\\}, \\\\{\\mathbf{h} ^{(c)}  _ {u'} : u' \\in G _c \\text{  aligns with } u\\\\})\\ \\ \\ (2)$$\nAs our experiments suggest, approach (1) gives better performance than (2).  We provide a more detailed description of this in lines 146-161 in the main paper.\n1. We propose two protocols for updating node embeddings and alignments (Lazy and Eager). In Lazy update, we first perform $K$ GNN runs followed by then one single alignment update and in Eager, we update the alignment in each of the $K$ message passing steps.\n\nWe will include these elaborations in the additional page, if our paper gets accepted. \n\n\n>  how their approach side-steps oversmoothing? explain lines 333 — 336.\n\nThe usually symmetric and parameter-free aggregation of messages from a node’s neighbors is known to weaken graph representations computed by GNNs [c]. L334 points out that scaling $h(u’)$ with a relaxed (evolving) permutation $P[u,u’]$ breaks the symmetry and conjectures that this reduces the oversmoothing effect, through task-driven cross-attention between two graphs (as against self-attention in GAT [d]).\n\n[c] A Survey on Oversmoothing in Graph Neural Networks; T. K. Rusch, M. M. Bronstein, S Mishra.\n\n[d] Graph attention networks, P Veličković, G Cucurull, A Casanova, A Romero, P Liò, Y Bengio.\n\n\n> How does the computational complexity compare with that of IsoNet?\n\nLet's consider three node models — IsoNet (Node), Eager EinsMatch (Node) and Lazy EinsMatch (Node) with $T$ rounds, each with $K$ propagation steps. \n\n**IsoNet (Node)**\n\nInitial node featurization takes $O(N)$ time. Node representation computation aggregates node embeddings over all neighbors, leading to complexity of $O(E)$ for each message passing step and computation of $P$ takes $O(N^2)$ time. The overall complexity for all the steps becomes $O(N^2+KE)$ where $K$ is the number of message passing steps.\n\n**Eager Multi-layer EinsMatch (Node)**\n\n1. Initial Node featurization takes $O(N)$ time\n1. EinsMatch first computes intermediate embeddings $z$ (Eq. 33, Page 16), which admits complexity of $O(N)$ for each layer per node, since it computes $\\sum _{u'\\in V _c} h^{(c)} _{k}(u') \\textbf{P} _{k}[u,u']$ for each node in each layer. The total complexity for $K$ steps is $O(KN^2)$.\n1. Next we  compute (Eq. 34) $h _{k+1}$ which gathers messages $z$ from all neighbors per node per layer. The total complexity contributed by this equation is $O(KE)$.\n1. Next we update $P _k$  for each layer which has complexity of $O(KN^2)$.\n\nHence, the total complexity is $O(KN^2+KE+KN^2)=O(KN^2)$.\n\n**Lazy Multi-round EinsMatch (Node)**\n\nHere, the key difference from Eager version is that the doubly stochastic matrix $P _t$ from round $t$ is used to compute $z$ and the $K$-step-GNN runs in $T$ rounds. This increases the complexity of step 2 and 3 to $O(KTN^2+KTE)$. Matrix $P _t$ is updated a total of $T$ times, which changes the complexity of step 4 to $O(TN^2)$. Hence, the total complexity is $O(KTN^2+TN^2+KTE) = O(KTN^2)$.\n\nHence, complexity of IsoNet is $O(N^2+KE)$. EinsMatch-Eager has complexity $O(KN^2)$ and EinsMatch-Lazy has complexity $O(KTN^2)$. However, this increased complexity comes with the benefit of significant acuracy boost, as our experiments suggest.", "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": "NzQSJ1dmei", "reviewer": "Reviewer_1Kfh", "summary": "This paper proposes an early interaction network for subgraph matching. The proposed method enables (1) early interaction GNNs with alignment refinement at both node and edge levels, where the alignments are refined by GNNs; (2) eager or lazy alignment updates,  and (3) node-pair partner interaction, instead of node partner interaction, which improves the model efficiency and embedding quality. The paper includes extensive experiments on real-world datasets, demonstrating the superiority and effectiveness of the proposed approach.", "questions": "- What is the motivation and intuition behind lazy updates? In my understanding, \"lazy\" means updating the alignment map after every K GNN layers, and \"eager\" means updating the alignment map and letting the map affect the embedding at each layer. Is there any explanation for the consistently better performance of \"lazy\" updates?\n- What do the multiple points with the same color in Figure 6 represent? Do they indicate variants with different hyperparameters?", "limitations": "Yes. This paper discussed the limitations in terms of efficiency and", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and easy to understand. The notations are clearly clarified and explained.\n2. The idea of iteratively early interaction between graphs for more accurate subgraph retrieval is novel and reasonable to me, which is also verified by the experimental results.\n3. The performance superiority of the proposed method against other baselines is significant and promising.", "weaknesses": "1. Considering the high complexity of the proposed method, an ablation study (or a hyperparameter sensitivity study) would be beneficial to provide a clearer understanding of the success of the proposed method. In addition, how did the authors tune hyperparameters (apart from T and K) for their approach and the competitors?\n2. Experiments are only conducted on small graph datasets (with an average of 11 nodes). It would be beneficial to discuss or evaluate the applicability of the proposed approach to larger graph datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback. The questions raised in the review are addressed below.\n\n>*ablation study (or a hyperparameter sensitivity study).. how did the authors tune hyperparameters?*\n\nWe used hyperparameters from the code of IsoNet, which, thanks to the authors, also made the baseline implementations public. In IsoNet's code, the authors suggest that they already tuned the margin in the ranking loss and other hyperparameters for all the baselines. Hence, we used them as-is. We did tune the margin in the ranking loss of three baselines (EGSC, GREED, H2MN) which are not included in IsoNet codebase. More details are in line 703 onwards in Appendix F.4. We run all methods for an unlimited number of epochs, with the patience parameter 50, i.e., training is stopped only if the performance on the validation set does not improve for 50 epochs.\n\nWe would like to highlight that, for EinsMatch, we did not tune any hyperparameters beyond IsoNet. We performed a hyperparameter sensitivity study (not tuning) for $T$ and $K$, which shows that for wide ranges of $T$ and $K$, EinsMatch performs better than baselines. We report results for $T=3, K=5$ in the main table, because its running time is comparable to most baselines. Increasing $T$ and $K$ improves accuracy at more computation cost.\n\nWe did perform ablations on the node pair partner interaction component in Table 4 and the effect of lazy updates in Table 3 in the main paper. We write the results here.\n\nThe following table compares the performance of node partner interaction with EinsMatch, which involves node pair partner interaction. Node pair partner interaction consistently outperforms node partner interaction for both eager and lazy variants of EinsMatch (Node).\n\n|Model|AIDS|Mutag|FM|FR|MM|MR|\n|-----|----|-----|--|--|--|--|\n|Node partner (Lazy)|0.776|0.829|0.851|0.819|**0.844**|0.840|\n|Node pair partner (Lazy)|**0.825**|**0.851**|**0.888**|**0.855**|0.838|**0.874**|\n|Node Partner (Eager)|0.668|0.783|0.821|0.752|0.753|0.794|\n|Node pair partner (Eager)|**0.756**|**0.810**|**0.859**|**0.802**|**0.827**|**0.841**|\n\nThe following table compares the performance of the eager and lazy variants of EinsMatch (Node) and EinsMatch (Edge). Lazy multi-round updates consistently outperform eager multi-layer updates across all datasets, for both Node and Edge models.\n\n|Model|AIDS|Mutag|FM|FR|MM|MR|\n|-----|----|-----|--|--|--|--|\n|EinsM. (Node, Eager)|0.756|0.810|0.859|0.802|0.827|0.841|\n|EinsM. (Node, Lazy)|**0.825**|**0.851**|**0.888**|**0.855**|**0.838**|**0.874**|\n|EinsM. (Edge, Eager)|0.795|0.805|0.883|0.812|0.862|0.886|\n|EinsM. (Edge, Eager)|**0.847**|**0.858**|**0.902**|**0.875**|**0.902**|**0.902**|\n\nWe observe that our method, in the presence of the node pair partner interaction component, performs better and lazy update generally outperforms eager update.\n\n> applicability of the proposed approach to larger graph datasets.\n\nIn early experiments, we found relatively small size of query graphs to actually present more challenge to the learner. Given our distant supervision, there are a larger number of promising alignments between query and corpus graphs that may lead to the relevant supervision.\n\nDuring the rebuttal, we performed experiments with graph pairs generated from the Cox2 dataset.  Here, we considered 100 query graphs with $|V|\\in[25,35]$, and 500 corpus graphs with $|V|\\in[40,50]$. The following table shows the results.\n\n| Models                   | Test mAP score on Cox2 |\n|--------------------------|-------|\n| NeuroMatch | 0.5036 |\n| EGSC | 0.4727 |\n| GREED | 0.1874 |\n| GEN | 0.6590 |\n| GMN | 0.6818 |\n| IsoNet (Node) | 0.7641 |\n| IsoNet (Edge) | 0.7356 |\n| EinsM. (Node) Lazy | 0.7291 |\n| EinsM. (Node) Eager | 0.7393 |\n| EinsM. (Edge) Lazy | **0.8302** |\n| EinsM. (Edge) Eager | 0.7949 |\n\nWe observe that our method EinsMatch (Edge) Lazy outperforms the baselines significantly. The node variant of our model is marginally outperformed by IsoNet (Node).\n\n>  motivation and intuition behind lazy updates?\n\nPlease refer to the global response.\n\n> What do the multiple points with the same color in Figure 6 represent? \n\n We vary rounds \\(T\\) and layers \\(K\\). Each point corresponds to a $(T,K)$ combination.  The color, as the legend shows, corresponds to an algorithm family. The goal is to study the tradeoff between inference speed and ranking accuracy (MAP).", "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": "LLDQa7bv3R", "reviewer": "Reviewer_65Ze", "summary": "This work proposes a GNN architecture for graph matching problem. The innovations in the work mainly lie in the early interaction between the query graph and the corpus graph, and the node-pair matching setting, as well as the lazy update technique in each round. Empirical results show that this work significantly outperforms the baselines on all the datasets.", "questions": "- Any related work indicating early interaction is good? As mentioned in line 36.\n- In line 124 the notation $A_q \\leq PA_c P^T$ is a bit confusing. \n- In equation 5, what is the sign of $\\tau$? If it's positive then you're encouraging the entropy to be higher, which means the entries of P are more uniform? That is a bit counter-intuitive. \n- What is the complexity of Sinkhorn Knopp algorithm and Gumbel Sinkhorn?\n- Is the K-layer GNN in each round t shared?\n- Any intuition why lazy updates works better? Is it easier to optimize or other aspects?\n- I don't quite understand why the work is not differentiable on nodes with different classes, as mentioned in appendix A. \n- Is there other measure between the $P$ and $P^*$? I feel $Tr(P^TP^*)$ does not capture all the information of the matrices.", "limitations": "As mentioned by the authors, the quality of the matching relies on the distance function, which is a general problem for graph matching works. Also I am a little dubious about the time complexity of the P matrix update, in the experiments it is more expensive than the baseline GMN.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The writing of the paper is clear and good. \n- The methodology is solid, and the illustration is informative. \n- The results are very promising, both in predictive performance and runtime. And the ablation experiments are well-designed.", "weaknesses": "- Some background part is not well explained, for example the graph matching problem, and the optimal transport problem. Readers may need external resources to understand them. Of course it is hard to explain everything in detail in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback. The questions raised in the review are addressed below.\n> Any related work indicating early interaction is good?\n\nThe GMN paper itself provides some evidence: GMN-match (early cross-graph interaction) is slower but convincingly superior in terms of accuracy to GMN-embed (late interaction between whole-graph representations). Other domains provide strong supporting evidence [a,b]. E.g., in textual entailment (NLI) tasks [b], where we need to classify if sentence s1 implies sentence s2, late comparison of (say) transformer-based embeddings of the two sentences, computed separately, is convincingly beaten by injecting s1 concat s2 into a comparable transformer and fine-tuning a classification head for the NLI task.\n\n[a] A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling entailment.\n\n[b] Entailment as Few-Shot Learner.  Sinong Wang, Han Fang, Madian Khabsa, Hanzi Mao, Hao Ma. arXiv:2104.14690v1\n\n>  In line 124  $A _q\\le PA _c P^{\\top}$ is a bit confusing.\n\n\nBy $A _q\\le PA _c P^{\\top}$, we mean the constraint holds true for each entry, i.e.,\n$A _q[u,v]\\le (PA _c P^{\\top})[u,v]$ for all u,v. \n\nSuppose  $A  _q$ is the node-node adjacency matrix of the query graph and   $A  _c$ is the node-node adjacency matrix of the corpus graph. Suppose, we could find a permutation $P$ of the node numbering (i.e., rows and columns) of $A  _c$, which is easily verified as $P A  _c P^T$, then $G _q\\subseteq G _c$ implies that every edge in $A  _q$ will also be present in $P A _c P^T$.  In other words, if $A _q[u,v]=1$ then  $(P A _c P^T)[u,v]$ must also be 1. This leads to the stated inequality.\n\n\n> Eq 5: the sign of $\\tau$\n\n Yes, we indeed want to make the entropy of $P$ a bit higher as this allows us to convert the hard permutation matrix into a smooth doubly stochastic matrix. To gain basic intuition into this, consider the argmax to softmax conversion. The selection $\\max _i a _i$, given a vector of real numbers $\\vec{a}$, is rewritten as $\\max _{\\vec{z}\\in \\Delta} \\vec{z} \\cdot \\vec{a}$, where $\\Delta$ is the unit simplex ($\\sum _i z _i =1$). Adding a maximizer of the entropy of $z$ readily yields the softmax function. Just like adding an entropy maximizer turns a vector of logits into a softmax distribution, adding an entropy maximizer turns a matrix of logits into a doubly stochastic soft permutation.  For technical details, see Cuturi’s classic paper and related works [10, 26].\n \n[10] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292–2300, 2013.\n\n[26]  G. Mena, D. Belanger, S. Linderman, and J. Snoek. Learning latent permutations with gumbel-sinkhorn networks. arXiv preprint arXiv:1802.08665, 2018.\n\n> What is the complexity of Sinkhorn Knopp algorithm and Gumbel Sinkhorn?\n\nAs mentioned in Appendix D.5, both these algorithms consist of some number of alternating row and column scalings. If the input matrix is $N\\times  N$, then each scaling takes $O(N^2)$ time. The number of scaling iterations is usually a small fixed constant (20 in our experiments).\n\n> Is the K-layer GNN in each round t shared?\n\nYes.  We regard the same GNN as being trained after each refinement applied to the proposed (soft) permutation.\n\n> Any intuition why lazy updates works better?\n\n Please refer to the global response.\n\n>why the work is not differentiable on nodes with different classes.\n\nWe meant that, at present, EinsMatch is not coded to account for node or edge labels. Our matching process is purely structural. If there are hard constraints that red nodes in the query graph can match only red nodes in the corpus graph, or there is an additional cost in the form of the difference in their degree of redness, we need to investigate if Sinkhorn-style updates will survive zeroing out parts of $P$. The problem seems complicated enough for a separate piece of work. \n\n\n> Is there other measure between the P and P*?  I feel $Tr(P^\\top P^*)$ does not capture all the information of the matrices.\n\nIndeed, other measures like Frobenius distance $\\Vert P-P^*\\Vert _F$ may be used. In Figure B in global-rebuttal-pdf, we updated the histograms, which reveal similar observations as with the Trace metric. Note that $\\Vert P-P^*\\Vert _F ^2 = 2|V| - 2\\, Tr(P^TP^*)$ if P and P* are both hard permutation matrices, but not necessarily the same if they are soft permutation matrices.\n\n> Also I am a little dubious about the time complexity of the P matrix update, in the experiments it is more expensive than the baseline GMN.\n\nL716–L720 give an idea of the clock time needed to train EinsMatch variants. Appendix G.6 gives an idea of the inference times involved, particularly, contrasted against IsoNet (edge) — we find these times within the same order of magnitude (usually within 10% and 40% of each other). Figures 6 and 17 show that, at any fixed level of inference time investment, EinsMatch (lazy) has the most favorable MAP envelope.\n\nFollowing table shows the time splits between GNN embedding computation and matrix P updates, in percentage of time spent performing that step.\n\n| Models  | % Embedding Computation  | % Matrix $\\textbf{P}$ updates |\n|--|--|--|\n| EinsMatch (Node) Multi Round | 34.1 | 47.8 |\n| EinsMatch (Node) Multi Layer | 13.7 | 68.3 |\n| EinsMatch (Edge) Multi Round | 54.9 | 39.9 |\n| EinsMatch (Edge) Multi Layer | 19.7 | 76.3 |\n\nThese percentages don't add up to 100% because of contributions from other steps like node encoding and score computation.  The summary is that yes, updating  $P$ has a non-negligible but non-overwhelming cost, with the benefit of better accuracy.\n \n> As mentioned by the authors, the quality of the matching relies on the distance function.\n\nWe absolutely agree with you. The same is the case for matching passages, images, video and audio. Good distance function design, mirroring human judgment, is critical to applications.", "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": "93YARElb4R", "reviewer": "Reviewer_WLV9", "summary": "The paper introduces EINSMATCH, an early interaction graph neural network for subgraph matching and retrieval that maintains and refines explicit alignments between query and corpus graphs. EINSMATCH has several novelties: computing embeddings guided by injective alignments between graphs, updating alignments lazily over multiple rounds, and using node-pair partner interactions. The model learns to identify alignments between graphs despite only having access to pairwise preferences during training, without explicit alignments. Experiments on several datasets show that EINSMATCH significantly outperforms existing methods.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The analysis of GMN’s worse performance compared to IsoNet (in Section 1) is intriguing.\n2. Extensive experimental results are presented with ample baselines and std errors included as well for most numbers reported.\n3. Source code with data splits is released for ease of reproducing the results.\n4. A large amount of ablation and parameter sensitivity studies are performed.", "weaknesses": "1. The datasets used in the experiments are relatively small, with at most ~20 nodes. \n2. It would be interesting to see the transfer ability of the learned model across datasets, e.g. training on PTC and testing on AIDS, to see how the proposed model would handle such challenging but realistic scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful review. The weaknesses raised in the review are addressed below.\n\n> The datasets used in the experiments are relatively small, with at most ~20 nodes.\n\nIn early experiments, we found relatively small size of query graphs to actually present more challenge to the learner. Given our distant supervision, there are a larger number of promising alignments between query and corpus graphs that may lead to the relevant supervision.\n\nDuring the rebuttal, we performed experiments with graph pairs generated from the Cox2 dataset.  Here, we considered 100 query graphs with $|V|\\in[25,35]$, and 500 corpus graphs with $|V|\\in[40,50]$. The following table shows the results.\n\n| Models                   | Test mAP score on Cox2 |\n|--------------------------|-------|\n| NeuroMatch | 0.5036 |\n| EGSC | 0.4727 |\n| GREED | 0.1874 |\n| GEN | 0.6590 |\n| GMN | 0.6818 |\n| IsoNet (Node) | 0.7641 |\n| IsoNet (Edge) | 0.7356 |\n| EinsM. (Node) Lazy | 0.7291 |\n| EinsM. (Node) Eager | 0.7393 |\n| EinsM. (Edge) Lazy | **0.8302** |\n| EinsM. (Edge) Eager | 0.7949 |\n\nWe observe that our method EinsMatch (Edge) Lazy outperforms the baselines significantly. The node variant of our model is marginally outperformed by IsoNet (Node).\n\n> It would be interesting to see the transfer ability of the learned model across datasets, e.g. training on PTC and testing on AIDS, to see how the proposed model would handle such challenging but realistic scenarios.\n\nDuring the rebuttal period, we performed experiments evaluating the transfer ability of the learned models across datasets. In particular, we chose the weights for each model trained using the AIDS and Mutag datasets respectively and evaluated them on all six datasets. The results are shown below. We observe that despite a zero-shot transfer from one of the datasets to all others, variants of EinsMatch show the best accuracy.\n\n**Models Trained on AIDS**\n\n| Test Datasets $\\to$                   | AIDS  | Mutag |   FM   |   FR   |   MM   |   MR   | \n|--------------------------|-------|-------|--------|--------|--------|--------|\n| GraphSim                 | 0.356 | 0.225 | 0.192  | 0.198  | 0.210  | 0.215  |\n| GOTSim                   | 0.324 | 0.275 | 0.370  | 0.339  | 0.314  | 0.361  |\n| SimGNN                   | 0.341 | 0.264 | 0.374  | 0.344  | 0.331  | 0.383  |\n| EGSC                     | 0.505 | 0.255 | 0.473  | 0.451  | 0.447  | 0.499  |\n| H2MN                     | 0.267 | 0.272 | 0.319  | 0.281  | 0.262  | 0.297  |\n| NeuroMatch               | 0.489 | 0.287 | 0.442  | 0.403  | 0.386  | 0.431  |\n| GREED                    | 0.472 | 0.307 | 0.477  | 0.452  | 0.436  | 0.49   |\n| GEN                      | 0.557 | 0.291 | 0.445  | 0.427  | 0.437  | 0.496  |\n| GMN                      | 0.622 | 0.342 | 0.569  | 0.544  | 0.532  | 0.588  |\n| IsoNet (Node)            | 0.659 | 0.459 | 0.612  | 0.562  | 0.588  | 0.640  |\n| IsoNet (Edge)            | 0.690 | 0.468 | 0.620  | 0.568  | 0.624  | 0.627  |\n| EinsM. (Node) Multi Layer| 0.756 | 0.685 | 0.825  | 0.767  | 0.781  | 0.794  |\n| EinsM. (Edge) Multi Layer| 0.795 | 0.683 | 0.800  | 0.751  | 0.792  | 0.785  |\n| EinsM. (Node) Multi Round| 0.825 | 0.702 | 0.828  | 0.777  | 0.800  | 0.825  |\n| EinsM. (Edge) Multi Round| **0.847** | **0.741** | **0.846**  | **0.799**  | **0.833**  | **0.836** |\n\n**Models Trained on Mutag**\n\n|  Test Datasets $\\to$                   | AIDS  | Mutag |   FM   |   FR   |   MM   |   MR   |\n|--------------------------|-------|-------|--------|--------|--------|--------|\n| GraphSim                 | 0.188 | 0.472 | 0.190  | 0.193  | 0.205  | 0.198  |\n| GOTSim                   | 0.194 | 0.272 | 0.185  | 0.192  | 0.202  | 0.182  |\n| SimGNN                   | 0.206 | 0.283 | 0.203  | 0.209  | 0.220  | 0.195  |\n| EGSC                     | 0.296 | 0.476 | 0.391  | 0.333  | 0.309  | 0.355  |\n| H2MN                     | 0.209 | 0.276 | 0.204  | 0.207  | 0.223  | 0.197  |\n| NeuroMatch               | 0.275 | 0.576 | 0.368  | 0.304  | 0.304  | 0.325  |\n| GREED                    | 0.328 | 0.567 | 0.388  | 0.335  | 0.356  | 0.37   |\n| GEN                      | 0.278 | 0.605 | 0.359  | 0.308  | 0.312  | 0.33   |\n| GMN                      | 0.299 | 0.71  | 0.434  | 0.361  | 0.389  | 0.394  |\n| IsoNet (Node)            | 0.458 | 0.697 | 0.503  | 0.456  | 0.446  | 0.486  |\n| IsoNet (Edge)            | 0.472 | 0.706 | 0.499  | 0.438  | 0.467  | 0.489  |\n| EinsM. (Node) Multi Layer| 0.601 | 0.810 | **0.695**  | 0.611  | 0.628  | 0.614  |\n| EinsM. (Edge) Multi Layer| 0.527 | 0.805 | 0.558  | 0.507  | 0.560  | 0.563  |\n| EinsM. (Node) Multi Round| **0.645** | 0.851 | 0.679  | **0.626**  | **0.652**  | **0.655**  |\n| EinsM. (Edge) Multi Round| 0.625 | **0.858** | 0.639  | 0.598  | 0.634  | 0.650  |", "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:
We are thankful to all the reviewers for taking out time to provide us with detailed reviews. Through this rebuttal, we aim to address questions that came up across multiple reviews. Figures have also been shared through the rebuttal PDF attached herewith.

> Why is Lazy update better? (Reviewers 1Kfh, 65Ze)

In L125-142 and L164-L167, we provide justification for lazy updates.
The underlying optimal alignment between the graphs remains the same for each of $K$ steps (layers) of message passing of GNN. Hence, when GNN performs its operation, the alignment proposal (matrix $P$) should be fixed. In eager update, this matrix keeps changing across the message passing steps, whereas in lazy update, $P$ is updated (and improved) only after $K$ layers of GNN, which enhances the inductive bias.

Elaborating, as we discussed in L125-142, we start with a combinatorial formulation and its solution. Define,
$$\text{cost}(P; A _q, A _c)   = 
\sum _{u\in [n],v\in[n]}  [\big(A _q-P A _c P^{\top}\big) _+] [u,v]$$

This cost is minimized through Gromov Wasserstein (GW) approach, where P is updated as
$$    P _{t} \leftarrow  \text{argmin} _{P} \textrm{Trace}\left(P^T\nabla _{P}\ \text{cost}(P;A _q,A _c) \big| _{P = P _{t-1}}\right) + \tau \sum _{u,v}P[u,v] \cdot \log P[u,v] .
$$

One can view each GW update step as a lazy update step. In the above, $P _{t-1}$ is used to compute the cost and in our method, we use it to compute the GNN embeddings and effectively those embeddings can approximate the $P _{t-1}$  dependent cost. Then, $P _t$ is updated by solving an entropy-regularized OT problem and we update $P _{t}$ using Sinkhorn iterations, which effectively optimizes entropy-regularized GNN guided cost.

Meta-review: The paper proposes a GNN-based neural architecture for graph retrieval, i.e., finding the best candidates for a set of graphs containing a subgraph isomorphic to a given query graph. The architecture proposes several innovations, i.e., message-passing iterations are guided by an injective alignment; a lazy update technique is used in each round by computing with a fixed alignment before refining it; and pairs of vertices are considered instead of single vertices in the message-passing steps. Moreover, the authors propose an extension to edge-level matching. The paper is complemented with a rather extensive empirical study, suggesting that the proposed architecture outperforms competing approaches. 

After an extensive rebuttal by the authors, all reviewers vote to accept the present paper. I follow this assessment.
Decision: Accept (poster)