Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval

Authors: ashwin  ramachandran
vaibhav  raj
indrayumna  roy
soumen  chakrabarti
abir  de
u c san
iit  bombay
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:10:20

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.

Main paper: 
 introduction: 
 In graph retrieval based on subgraph isomorphism, the goal is to identify a subset of graphs from a corpus, denoted {G c }, wherein each retrieved graph contains a subgraph isomorphic to a given query graph G q . 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. computed independent of each other. In contrast, GMN [22] is a powerful early interaction network for graph matching, where GNNs running on G q and G c interact with each other at 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 G q and G c . 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 a standard GNN that is known to be an 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 possibility of a third approach based on early interaction networks, enabled with explicit alignment structures, that have the potential to outperform both GMN and IsoNet.We present IsoNet++, an early interaction network for subgraph matching that maintains a 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 is an injective mapping by design.Eager or lazy alignment updates In our work, we view the updates to the alignment maps as a form of gradient-based updates in a 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 Gumbel-Sinkhorn soft permutation generator [10, 26, 37] .Node-pair partner interaction between graphs The existing remedies to counter oversmoothing [8, 33, 40] entail extra computation; but they may be expensive in an early-interaction setting. Existing early interaction models like [22] perform node partner interaction; interactions are constrained to occur between a 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 node-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 its neighbors.Experiments The design components of IsoNet++ and their implications are subtle -we report on extensive experiments that tease out their effects. Our experiments on real world datasets show that, IsoNet++ outperforms several state-of-the-art methods for graph retrieval by a 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. 
preliminaries: 
 Notation Given graph G = (V, E), we use nbr(u) to denote the neighbors of a node u ∈ V . We use u → v to indicate a message flow from node u to node v. Given a set of corpus graphs C = {G c } and a query graph G q , we denote y(G c | G q ) as the binary relevance label of G c for G q . Motivated by several real life applications like substructure search in molecular graphs [12] , object search in scene graphs [16] , and text entailment [20] , we consider subgraph isomorphism to significantly influence the relevance label, similar to previous works [23, 35] . Specifically, y(G c | G q ) = 1 when G q is a subgraph of G c , and 0 otherwise. We define C q+ ⊆ C as the set of corpus graphs that are relevant to G q and set C q-= C\C q+ . Mildly overloading notation, we use P to indicate a 'hard' (0/1) permutation matrix or its 'soft' doubly-stochastic relaxation. B n denotes the set of all n × n doubly stochastic matrices, and Π n denotes the set of all n × n permutation matrices.IsoNet [35] Given a graph G = (V, E), IsoNet uses a GNN, which initializes node representations {h 0 (u) : u ∈ V } using node-local features. Then, messages are passed between neighboring nodes in K propagation layers. In the kth layer, a node u receives messages from its neighbors, aggregates them, and then combines the result with its state after the (k -1)th layer:EQUATIONHere, msg θ (•) and comb θ (•, •) are suitable networks with parameters collectively called θ. 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 = {h K (u) | u ∈ V }. Given a node u ∈ G q and a node u ′ ∈ G c , we denote the embeddings of u and u ′ after the propagation layer k as h (q) k (u) and h(c)k (u ′ ) respectively. H (q) and H (c) denote the Kth-layer node embeddings of G q and G c , collected into matrices. Note that, here the set of vectors H (q) and H (c) do not dependent on G c and G q . In the end, IsoNet compares these embeddings to compute the distanceEQUATIONSince subgraph isomorphism entails an asymmetric relevance, we have:∆(G c | G q ) ̸ = ∆(G q | G c ).IsoNet also proposed another design of ∆, where it replaces the node embeddings with edge embeddings and node alignment matrix with edge alignment matrix in Eq. (2) .In an early interaction network, H (q) depends on G c and H (c) depends on G q for any given (G q , G c ) pair. Formally, one should write H (q | c) and H (c | q) instead of H (q) and H (c) respectively for an early interaction network, but for simplicity, we will continue using H (q) and H (c) .Our goal Given a set of corpus graphs C = {G c | c ∈ [|C|]}, our high-level goal is to build a graph retrieval model so that, given a query G q , it can return the corpus graphs {G c } which are relevant to G q . To that end, we seek to develop (1) a GNN-based early interaction model, and (2) an appropriate distance measure ∆(• | •), so that ∆(H (c) | H (q) ) is an accurate predictor of y(G c | G q ), at least to the extent that ∆(•|•) is effective for ranking candidate corpus graphs in response to a query graph.3 Proposed early-interaction GNN with multi-round alignment refinementIn this section, we first write down the subgraph isomorphism task as an instance of the quadratic assignment problem (QAP) or the Gromov-Wasserstein (GW) distance optimization task. Then, we design IsoNet++, by building upon this formulation. 
subgraph isomorphism as gromov-wasserstein distance optimization: 
 QAP or GW formulation with asymmetric cost We are given a graph pair G q and G c padded with appropriate number of nodes to ensure |V q | = |V c | = n (say). Let their adjacency matrices be A q , A c ∈ {0, 1} n×n . Consider the family of hard permutation matrices P ∈ Π n where P [u, u ′ ] = 1 indicates u ∈ V q is "matched" to u ′ ∈ V c . Then, G q is a subgraph of G c , if for some permutation matrix P , the matrix A q is covered by P A c P ⊤ , i.e., for each pair (u, v), whenever we have A q [u, v] = 1, we will also have P A c P ⊤ [u, v] = 1. This condition can be written as A q ≤ P A c P ⊤ . We can regard a deficit in coverage as a cost or distance:EQUATIONEQUATIONHere, [•] + = max {•, 0} is the ReLU function, applied elementwise. The function cost(P ; A q , A c ) can be driven down to zero using a suitable choice of P iff G q is a subgraph of G c . This naturally suggests the relevance distance ∆(G c | G q ) = min P ∈Πn cost(P ; A q , A c )Xu et al. [41] demonstrate that this QAP is a realization of the Gromov-Wassterstein distance minimization in a graph setting. Given a graph pair (G q , G c ), we execute T rounds, each consisting of K GNN layer propagations. After a round t, we use the node embeddings to update the node alignment P = P t from its previous estimateP = P t-1 . Within each round t ∈ [T ],we compute the node embeddings of G q by gathering signals from G c and vice-versa, using GNN embeddings in the previous round and the node-alignment map P t . The alignment P t remains consistent across all propagation layers k ∈ [K] and is updated at the end of round t. 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 of the partners u ′ and v ′ in addition to the embeddings of the pairs (u, v), where u ′ and v ′ is approximately aligned with u and v, respectively (when converted to soft alignment, u ′ , v ′ 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 of their node embeddings into the message passing network msg θ .Updating P with projected gradient descent As shown in Benamou et al. [3] , Peyré et al. [30] , Xu et al. [41] , one approach is to first relax P into a doubly stochastic matrix, which serves as a continuous approximation of the discrete permutation, and then update it using projected gradient descent (PGD).Here, the soft permutation P t-1 is updated to P t at time-step t by solving the following linear optimal transport (OT) problem, regularized with the entropy of {P [u, v] | u, v ∈ [n]} with a temperature τ .Trace P ⊤ ∇ P cost(P ; A q , A cEQUATIONSuch an OT problem is solved using the iterative Sinkhorn-Knopp algorithm [10, 37, 26] . Similar to other combinatorial optimization problems on graphs, a QAP (4) does not capture the coverage cost in the presence of dense node or edge features, where two nodes or 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 ∇ P cost(•). Additionally, the computational bottleneck of solving a fresh OT problem in each PGD step introduces a significant overhead, especially given the large number of pairwise evaluations required in typical learning-to-rank setups.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.For simpler exposition, we begin by describing a synthetic scenario, where P is a hard node permutation matrix, which induces the alignment map as a bijection π :EQUATIONk (u) are treated likewise.) Under the given alignment map π, a simple early interaction model would update the node embeddings as follows:EQUATIONIn the above expression, the update layer uses representation of the partner node u ′ ∈ V c during the message passing step, to compute h (q) k+1 (u), the embedding of node u ∈ V q . Li et al. [22] use a similar update protocol, by approximating h(c) k (π(u)) = u ′ ∈Vc a (k) u ′ →u h (c) k (u ′ ), where a (k) u ′ →u is the kth layer attention from u ∈ V q to potential partner u ′ ∈ V c , with u ′ ∈Vc a (k) u ′ →u = 1. Instead < l a t e x i t s h a 1 _ b a s e 6 4 = " / q d j g 2 S Q N o t L g V M l n p J J h t o L q D A = " > A A A B + X i c b V B N S 8 N A E J 3 4 W e t X 1 K O X x S L U S 0 l E 0 W P R i 8 c K 9 g P a G D b b T b t 0 s 4 m 7 m 0 I J + S d e P C j i 1 X / i z X / j t s 1 B W x 8 M P N 6 b Y W Z e k H C m t O N 8 W y u r a + s b m 6 W t 8 v b O 7 t 6 + f X D Y U n E q C W 2 S m M e y E 2 B F O R O 0 q Z n m t J N I i q O A 0 3 Y w u p 3 6 7 T G V i s X i Q U 8 S 6 k V 4 I F j I C N Z G 8 m 2 7 l 0 R B N s w f s + r T W Y 7 8 k W 9 X n J o z A 1 o m b k E q U K D h 2 1 + 9 f k z S i A p N O F a q 6 z q J 9 j I s N S O c 5 u V e q m i C y Q g P a N d Q g S O q v G x 2 e Y 5 O j d J H Y S x N C Y 1 m 6 u + J D E d K T a L A d E Z Y D 9 W i N x X / 8 7 q p D q + 9 j I k k 1 V S Q + a I w 5 U j H a B o D 6 j N J i e Y T Q z C R z N y K y B B L T L Q J q 2 x C c B d f X i a t 8 5 p 7 W X P u L y r 1 m y K O E h z D C V T B h S u o w x 0 0 o A k E x v A M r / B m Z d a L 9 W 5 9 z F t X r G L m C P 7 A + v w B F 2 S T T A = = < / l a t e x i t > h h h (q) k < l a t e x i t s h a 1 _ b a s e 6 4 = " d 3 z O l X e Y X K v n e A I 5 y G L C W Z N N K / o = " > A A A B + X i c b V B N S 8 N A E J 3 U r 1 q / o h 6 9 L B a h X k o i i h 6 L X j x W s B / Q x r D Z b t q l m 0 3 Y 3 R R K y D / x 4 k E R r / 4 T b / 4 b t 2 0 O 2 v p g 4 P H e D D P z g o Q z p R 3 n 2 y q t r W 9 s b p W 3 K z u 7 e / s H 9 u F R W 8 W p J L R F Y h 7 L b o A V 5 U z Q l m a a 0 2 4 i K Y 4 C T j v B + G 7 m d y Z U K h a L R z 1 N q B f h o W A h I 1 g b y b f t f h I F 2 S h / y m r k P E f + 2 L e r T t 2 Z A 6 0 S t y B V K N D 0 7 a / + I C Z p R I U m H C v V c 5 1 E e x m W m h F O 8 0 o / V T T B Z I y H t G e o w B F V X j a / P E d n R h m g M J a m h E Z z 9 f d E h i O l p l F g O i O s R 2 r Z m 4 n / e b 1 U h z d e x k S S a i r I Y l G Y c q R j N I s B D Z i k R P O p I Z h I Z m 5 F Z I Q l J t q E V T E h u M s v r 5 L 2 R d 2 9 q j s P l 9 X G b R F H G U 7 g F G r g w j U 0 4 B 6 a 0 A I C E 3 i G V 3 i z M u v F er c + F q 0 l q 5 g 5 h j + w P n 8 A A e a T P g = = < / l a t e x i t > h h h (c) k < l a t e x i t s h a 1 _ b a s e 6 4 = " h x 6 M j U m 8 k D D p n / h j 6 y P R E z I x 5 C w = " > A A A B / X i c b V D L S g M x F M 3 4 r P U 1 P n Z u g q X g q s y I o s u i G 5 c V 7 A P a U j L p b R u a m Q z J H b E O x V 9 x 4 0 I R t / 6 H O / / G t J 2 F t h 6 4 c D j n X n J y g l g K g 5 7 3 7 S w t r 6 y u r e c 2 8 p t b 2 z u 7 7 t 5 + z a h E c 6 h y J ZV u B M y A F B F U U a C E R q y B h Y G E e j C 8 n v j 1 e 9 B G q O g O R z G 0 Q 9 a P R E 9 w h l b q u I c t h A d M u Q q D c S d t 4 Q C Q j T t u w S t 5 U 9 B F 4 m e k Q D J U O u 5 X q 6 t 4 E k K E X D J j m r 4 X Y z t l G g W X M M 6 3 E g M x 4 0 P W h 6 a l E Q v B t N N p + j E t W q V L e 0 r b i Z B O 1 d 8 X K Q u N G d l 8 t B g y H J h 5 b y L + 5 z U T 7 F 2 2 U x H F C U L E Z w / 1 E k l R 0 U k V t C s 0 c J Q j S x j X w m a l f M A 0 4 2 g L y 9 s S / P k v L 5 L a a c k / L 3 m 3 Z 4 X y V V Z H j h y R Y 3 J C f H J B y u S G V E i V c P J I n s k r e X O e n B f n 3 f m Y r S 4 5 2 c 0 B + Q P n 8 w e g b J X 6 < / l a t e x i t > comb ✓ < l a t e x i t s h a 1 _ b a s e 6 4 = " + 4 4 g y Q C l u Y W d / y a P a W b l g K f e Y / 4 = " > A A A B / H i c b V B N S 8 N A E N 3 4 W e t X t E c v w S J 4 K o k o e i x 6 8 V j B f k A b w m Y 7 a Z d u P t i d i C H E v + L F g y J e / S H e / D d u 2 x y 0 9 c H A 4 7 0 Z Z u b 5 i e A K b f v b W F l d W 9 / Y r G x V t 3 d 2 9 / b N g 8 O O i l P J o M 1 i E c u e T x U I H k E b O Q r o J R J o 6 A v o + p O b q d 9 9 A K l 4 H N 1 j l o A b 0 l H E A 8 4 o a s k z a w O E R 8 x D N S q 8 f I B j Q F p 4 Z t 1 u 2 D N Y y 8 Q p S Z 2 U a H n m 1 2 A Y s z S E C J m g S v U d O 0 E 3 p x I 5 E 1 B U B 6 m C h L I J H U F f 0 4 i G o N x 8 d n x h n W h l a A W x 1 B W h N V N / T + Q 0 V C o L f d 0 Z U h y r R W 8 q / u f 1 U w y u 3 J x H S Y o Q s f m i I B U W x t Y 0 C W v I J T A U m S a U S a 5 v t d i Y S s p Q 5 1 X V I T i L L y + T z l n D u W j Y d + f 1 5 n U Z R 4 U c k W N y S h x y S Z r k l r R I m z C S k W fy S t 6 M J + P F e D c + 5 q 0 r R j l T I 3 9 g f P 4 A 6 4 e V l g = = < / l a t e x i t > msg ✓ < l a t e x i t s h a 1 _ b a s e 6 4 = " q S 2 M + g g/ 3 m d B / G B b + l a d Z H P g u G I = " > A A A B 6 3 i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K o s e g F 4 8 R z A O S J c x O Z p M h M 7 P L P I S w 5 B e 8 e F D E q z / k z b 9 x N t m D J h Y 0 F F X d d H d F K W f a + P 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t n V h F a I s k P F H d C G v K m a Q t w w y n 3 V R R L C J O O 9 H k L v c 7 T 1 R p l s h H M 0 1 p K P B I s p g R b H K p r 6 0 Y V G t + 3 Z 8 D r Z K g I D U o 0 B x U v / r D h F h B p S E c a 9 0 L / N S E G V a G E U 5 n l b 7 V N M V k g k e 0 5 6 j E g u o w m 9 8 6 Q 2 d O G a I 4 U a 6 k Q X P 1 9 0 S G h d Z T E b l O g c 1 Y L 3 u 5 + J / X s y a + C T M m U 2 u o J I t F s e X I J C h / H A 2 Z o s T w q S O Y K O Z u R W S M F S b G x V N x I Q T L L 6 + S 9 k U 9 u K r 7 D 5 e 1 x m 0 R R x l O 4 B T O I Y B r a M A 9 N K E F B M b w D K / w 5 g n v x X v 3 P h a t J a + Y O Y Y / 8 D 5 / A D M 9 j l c = < / l a t e x i t > X (a) No Interaction (IsoNet)< l a t e x i t s h a 1 _ b a s e 6 4 = " / q d j g2 S Q N o t L g V M l n p J J h t o L q D A = " > A A A B + X i c b V B N S 8 N A E J 3 4 W e t X 1 K O X x S L U S 0 l E 0 W P R i 8 c K 9 g P a G D b b T b t 0 s 4 m 7 m 0 I J + S d e P C j i 1 X / i z X / j t s 1 B W x 8 M P N 6 b Y W Z e k H C m t O N 8 W y u r a + s b m 6 W t 8 v b O 7 t 6 + f X D Y U n E q C W 2 S m M e y E 2 B F O R O 0 q Z n m t J N I i q O A 0 3 Y w u p 3 6 7 T G V i s X i Q U 8 S 6 k V 4 I F j I C N Z G 8 m 2 7 l 0 R B N s w f s + r T W Y 7 8 k W 9 X n J o z A 1 o m b k E q U K D h 2 1 + 9 f k z S i A p N O F a q 6 z q J 9 j I s N S O c 5 u V e q m i C y Q g P a N d Q g S O q v G x 2 e Y 5 O j d J H Y S x N C Y 1 m 6 u + J D E d K T a L A d E Z Y D 9 W i N x X / 8 7 q p D q + 9 j I k k 1 V S Q + a I w 5 U j H a B o D 6 j N J i e Y T Q z C R z N y K y B B L T L Q J q 2 x C c B d f X i a t 8 5 p 7 W X P u L y r 1 m y K O E h z D C V T B h S u o w x 0 0 o A k E x v A M r / B m Z d a L 9 W 5 9 z F t X r G L m C P 7 A + v w B F 2 S T T A = = < / l a t e x i t > h h h (q) k < l a t e x i t s h a 1 _ b a s e 6 4 = " d 3 z O l X e Y X K v n e A I 5 y G L C W Z N N K / o = " > A A A B + X i c b V B N S 8 N A E J 3 U r 1 q / o h 6 9 L B a h X k o i i h 6 L X j x W s B / Q x r D Z b t q l m 0 3 Y 3 R R K y D / x 4 k E R r / 4 T b / 4 b t 2 0 O 2 v p g 4 P H e D D P z g o Q z p R 3 n 2 y q t r W 9 s b p W 3 K z u 7 e / s H 9 u F R W 8 W p J L R F Y h 7 L b o A V 5 U z Q l m a a 0 2 4 i K Y 4 C T j v B + G 7 m d y Z U K h a L R z 1 N q B f h o W A h I 1 g b y b f t f h I F 2 S h / y m r k P E f + 2 L e r T t 2 Z A 6 0 S t y B V K N D 0 7 a / + I C Z p R I U m H C v V c 5 1 E e x m W m h F O 8 0 o / V T T B Z I y H t G e o w B F V X j a / P E d n R h m g M J a m h E Z z 9 f d E h i O l p l F g O i O s R 2 r Z m 4 n / e b 1 U h z d e x k S S a i r I Y l G Y c q R j N I s B D Z i k R P O p I Z h I Z m 5 F Z I Q l J t q E V T E h u M s v r 5 L 2 R d 2 9 q j s P l 9 X G b R F H G U 7 g F G r g w j U 0 4 B 6 a 0 A I C E 3 i G V 3 i z M u v F er c + F q 0 l q 5 g 5 h j + w P n 8 A A e a T P g = = < / l a t e x i t > h h h (c) k < l a t e x i t s h a 1 _ b a s e 6 4 = " h x 6 M j U m 8 k D D p n / h j 6 y P R E z I x 5 C w = " > A A A B / X i c b V D L S g M x F M 3 4 r P U 1 P n Z u g q X g q s y I o s u i G 5 c V 7 A P a U j L p b R u a m Q z J H b E O x V 9 x 4 0 I R t / 6 H O / / G t J 2 F t h 6 4 c D j n X n J y g l g K g 5 7 3 7 S w t r 6 y u r e c 2 8 p t b 2 z u 7 7 t 5 + z a h E c 6 h y J Z V u B M y A F B F U U a C E R q y B h Y G E e j C 8 n v j 1 e 9 B G q O g O R z G 0 Q 9 a P R E 9 w h l b q u I c t h A d M u Q q D c S d t 4 Q C Q j T t u w S t 5 U 9 B F 4 m e k Q D J U O u 5 X q 6 t 4 E k K E X D J j m r 4 X Y z t l G g W X M M 6 3 E g M x 4 0 P W h 6 a l E Q v B t N N p + j E t W q V L e 0 r b i Z B O 1 d 8 X K Q u N G d l 8 t B g y H J h 5 b y L + 5 z U T 7 F 2 2 U x H F C U L E Z w / 1 E k l R 0 U k V t C s 0 c J Q j S x j X w m a l f M A 0 4 2 g L y 9 s S / P k v L 5 L a a c k / L 3 m 3 Z 4 X y V V Z H j h y R Y 3 J C f H J B y u S G V E i V c P J I n s kW F l d W 9 / Y r G x V t 3 d 2 9 / b N g 8 O O i l P J o M 1 i E c u e T x U I H k E b O Q r o J R J o 6 A v o + p O b q d 9 9 A K l 4 H N 1 j l o A b 0 l H E A 8 4 o a s k z a w O E R 8 x D N S q 8 f I B j Q F p 4 Z t 1 u 2 D N Y y 8 Q p S Z 2 U a H n m 1 2 A Y s z S E C J m g S v U d O 0 E 3 p x I 5 E 1 B U B 6 m C h L I J H U F f 0 4 i G o N x 8 d n x h n W h l a A W x 1 B W h N V N / T + Q 0 V C o L f d 0 Z U h y r R W 8 q / u f 1 U w y u 3 J x H S Y o Q s f m i I B U W x t Y 0 C W v I J T A U m S a U S a 5 v t d i Y S s p Q 5 1 X V I T i L L y + T z l n D u W j Y d + f 1 5 n U Z R 4 U c k W N y S hx y S Z r k l r R I m z C S k W f y S t 6 M J + P F e D c + 5 q 0 r R j l T I 3 9 g f P 4 A 6 4 e V l g = = < / l a t e x i t > < l a t e x i t s h a 1 _ b a s e 6 4 = " / q d j gz / k z b 9 x N t m D J h Y 0 F F X d d H d F K W f a + P 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t n V h F a I s k P F H d C G v K m a Q t w w y n 3 V R R L C J O O 9 H k L v c 7 T 1 R p l s h H M 0 1 p K P B I s p g R b H K p r 6 0 Y V G t + 3 Z 8 D r Z K g I D U o 0 B x U v / r D h F h B p S E c a 9 0 L / N S E G V a G E U 5 n l b 7 V N M V k g k e 0 5 6 j E g u o w m 9 8 6 Q 2 d O G a I 4 U a 6 k Q X P 1 9 0 S G h d Z T E b l O g c 1 Y L 3 u 5 + J / X s y a + C T M m U 2 u o J I t F s e X I J C h / H A 2 Z o s T w q S O Y K O Z u R W S M F S b G x V N x I Q T L L 6 + S 9 k U 9 u K2 S Q N o t L g V M l n p J J h t o L q D A = " > A A A B + X i c b V B N S 8 N A E J 3 4 W e t X 1 K O X x S L U S 0 l E 0 W P R i 8 c K 9 g P a G D b b T b t 0 s 4 m 7 m 0 I J + S d e P C j i 1 X / i z X / j t s 1 B W x 8 M P N 6 b Y W Z e k H C m t O N 8 W y u r a + s b m 6 W t 8 v b O 7 t 6 + f X D Y U n E q C W 2 S m M e y E 2 B F O R O 0 q Z n m t J N I i q O A 0 3 Y w u p 3 6 7 T G V i s X i Q U 8 S 6 k V 4 I F j I C N Z G 8 m 2 7 l 0 R B N s w f s + r T W Y 7 8 k W 9 X n J o z A 1 o m b k E q U K D h 2 1 + 9 f k z S i A p N O F a q 6 z q J 9 j I s N S O c 5 u V e q m i C y Q g P a N d Q g S O q v G x 2 e Y 5 O j d J H Y S x N C Y 1 m 6 u + J D E d K T a L A d E Z Y D 9 W i N x X / 8 7 q p D q + 9 j I k k 1 V S Q + a I w 5 U j H a B o D 6 j N J i e Y T Q z C R z N y K y B B L T L Q J q 2 x C c B d f X i a t 8 5 p 7 W X P u L y r 1 m y K O E h z D C V T B h S u o w x 0 0 o A k E x v A M r / B m Z d a L 9 W 5 9 z F t X r G L m C P 7 A + v w B F 2 S T T A = = < / l a t e x i t > h h h (q) k < l a t e x i t s h a 1 _ b a s e 6 4 = " d 3 z O l X e Y X K v n e A I 5 y G L C W Z N N K / o = " > A A A B + X i c b V B N S 8 N A E J 3 U r 1 q / o h 6 9 L B a h X k o i i h 6 L X j x W s B / Q x r D Z b t q l m 0 3 Y 3 R R K y D / x 4 k E R r / 4 T b / 4 b t 2 0 O 2 v p g 4 P H e D D P z g o Q z p R 3 n 2 y q t r W 9 s b p W 3 K z u 7 e / s H 9 u F R W 8 W p J L R F Y h 7 L b o A V 5 U z Q l m a a 0 2 4 i K Y 4 C T j v B + G 7 m d y Z U K h a L R z 1 N q B f h o W A h I 1 g b y b f t f h I F 2 S h / y m r k P E f + 2 L e r T t 2 Z A 6 0 S t y B V K N D 0 7 a / + I C Z p R I U m H C v V c 5 1 E e x m W m h F O 8 0 o / V T T B Z I y H t G e o w B F V X j a / P E d n R h m g M J a m h E Z z 9 f d E h i O l p l F g O i O s R 2 r Z m 4 n / e b 1 U h z d e x k S S a i r I Y l G Y c q R j N I s B D Z i k R P O p I Z h I Z m 5 F Z I Q l J t q E V T E h u M s v r 5 L 2 R d 2 9 q j s P l 9 X G b R F H G U 7 g F G r g w j U 0 4 B 6 a 0 A I C E 3 i G V 3 i z M u v F er c + F q 0 l q 5 g 5 h j + w P n 8 A A e a T P g = = < / l a t e x i t > h h h (c) k < l a t e x i t s h a 1 _ b a s e 6 4 = " h x 6 M j U m 8 k D D p n / h j 6 y P R E z I x 5 C w = " > A A A B / X i c b V D L S g M x F M 3 4 r P U 1 P n Z u g q X g q s y I o s u i G 5 c V 7 A P a U j L p b R u a m Q z J H b E O x V 9 x 4 0 I R t / 6 H O / / G t J 2 F t h 6 4 c D j n X n J y g l g K g 5 7 3 7 S w t r 6 y u r e c 2 8 p t b 2 z u 7 7 t 5 + z a h E c 6 h y J Z V u B M y A F B F U U a C E R q y B h Y G E e j C 8 n v j 1 e 9 B G q O g O R z G 0 Q 9 a P R E 9 w h l b q u I c t h A d M u Q q D c S d t 4 Q C Q j T t u w S t 5 U 9 B F 4 m e k Q D J U O u 5 X q 6 t 4 E k K E X D J j m r 4 X Y z t l G g W X M M 6 3 E g M x 4 0 P W h 6 a l E Q v B t N N p + j E t W q V L e 0 r b i Z B O 1 d 8 X K Q u N G d l 8 t B g y H J h 5 b y L + 5 z U T 7 F 2 2 U x H F C U L E Z w / 1 E k l R 0 U k V t C s 0 c J Q j S x j X w m a l f M A 0 4 2 g L y 9 s S / P k v L 5 L a a c k / L 3 m 3 Z 4 X y V V Z H j h y R Y 3 J C f H J B y u S G V E i V c P J I n s kW F l d W 9 / Y r G x V t 3 d 2 9 / b N g 8 O O i l P J o M 1 i E c u e T x U I H k E b O Q r o J R J o 6 A v o + p O b q d 9 9 A K l 4 H N 1 j l o A b 0 l H E A 8 4 o a s k z a w O E R 8 x D N S q 8 f I B j Q F p 4 Z t 1 u 2 D N Y y 8 Q p S Z 2 U a H n m 1 2 A Y s z S E C J m g S v U d O 0 E 3 p x I 5 E 1 B U B 6 m C h L I J H U F f 0 4 i G o N x 8 d n x h n W h l a A W x 1 B W h N V N / T + Q 0 V C o L f d 0 Z U h y r R W 8 q / u f 1 U w y u 3 J x H S Y o Q s f m i I B U W x t Y 0 C W v I J T A U m S a U S a 5 v t d i Y S s p Q 5 1 X V I T i L L y + T z l n D u W j Y d + f 1 5 n U Z R 4 U c k W N y S hx y S Z r k l r R I m z C S k W f y S t 6 M J + P F e D c + 5 q 0 r R j l T I 3 9 g f P 4 A 6 4 e V l g = = < / l a t e x i t > z / k z b 9 x N t m D J h Y 0 F F X d d H d F K W f a + P 6 3 V 1 p b 3 9 j c K m 9 X d n b 3 9 g + q h 0 d t n V h F a I s k P F H d C G v K m a Q t w w y n 3 V R R L C J O O 9 H k L v c 7 T 1 R p l s h H M 0 1 p K P B I s p g R b H K p r 6 0 Y V G t + 3 Z 8 D r Z K g I D U o 0 B x U v / r D h F h B p S E c a 9 0 L / N S E G V a G E U 5 n l b 7 V N M V k g k e 0 5 6 j E g u o w m 9 8 6 Q 2 d O G a I 4 U a 6 k Q X P 1 9 0 S G h d Z T E b l O g c 1 Y L 3 u 5 + J / X s y a + C T M m U 2 u o J I t F s e X I J C h / H A 2 Z o s T w q S O Y K O Z u R W S M F S b G x V N x I Q T L L 6 + S 9 k U 9 u K r 7 D 5 e 1 x m 0 R R x l O 4 B T O I Y B r a M A 9 N K E F B M b w D K / w 5 g n v x X v 3 P h a t J a + Y O Y Y / 8 D 5 / A D M 9 j l c = < / l a t e x i t > X < l a t e x i t s h a 1 _ b a s e 6 4 = " L W a m V b / B k L 0 6 i j R G Z D I 2 0 n 1 v 6 t A = " > A A A B / n i c b V B N S 8 N A E N 3 U r 1 q / o u L J S 7 A I n k o i i h 6 L X j x W s L X Q h L D Z T t q l m w 9 2 J 2 I J A f + K F w + K e P V 3 e P P f u G 1 z 0 N Y H A 4 / 3 Z p i Z F 6 S C K 7 T t b 6 O y t L y y u l Z d r 2 1 s b m 3 v m L t 7 H Z V k k k G b J S K R 3 Y A q E D y G N n I U 0 E 0 l 0 C g Q c B + M r i f + / Q N I x Z P 4 D s c p e B E d x D z k j K K W f P P A R X j E n M c I s v B z F 4 e A t P D N u t 2 w p 7 A W i V O S O i n R 8 s 0 v t 5 + w L I I Y m a B K 9 R w 7 R S + n E j k T U N T c T E F K 2 Y g O o K d p T C N Q X j 4 9 v 7 C O t d K 3 w k T q i t G a q r 8 n c h o p N Y 4 C 3 R l R H K p 5 b y L + 5 / U y D C 8 9 / V u a I c R s t i j M h I W J N c n C 6 n M J D M V Y E 8 o k 1 7 d a b E g l Z T o M V d M h O P M v L 5 L O a c M 5 b 9 i 3 Z / X m V R l H l R y S I 3 J C H H J B m u S G t E i b M J K T Z / J K 3 o w n 4 8 V 4 N z 5 m r R W j n N k n f 2 B 8 / g C S l Z a F < / l a t e x i t > inter ✓ (c) Node Pair Partner Interaction (IsoNet++)Figure 2 : Illustration of the three interaction modes. IsoNet has no/late interaction between h (q) and h (c) . IsoNet++ and GMN allow interaction between the representations of the query and corpus nodes. Under node pair interaction, the individual node embeddings h (q) are used for message passing directly, thereby exposing them only to their neighbors. In the corresponding comb θ 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 a node is combined with that of its partner(s) first, using the inter θ block to obtain z (q) (12), which is used for message passing. Thus, when interacting with its 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) ∈ E q , the partners (π(u), π(v)) ∈ E c should then greatly influence the intensity of assimilation of h(c) k (u ′ ) into h (c)k+1 (u). The first key innovation in IsoNet++ is to replace (7) to recognize and implement this insight:EQUATIONk+1 (u ′ ) for nodes u ′ ∈ V c are updated likewise in a symmetric manner. The network msg θ is provided embeddings from partners π(u), π(v) of u, v ∈ V q -this allows h (•)k+1 (u) to capture information from all nodes in the paired graph, that match with the (k + 1)-hop neighbors of u. We schematically illustrate the interaction between the paired graphs in IsoNet, GMN and IsoNet++ in Figure 2 .Multi-round lazy refinement of node alignment In reality, we are not given any alignment map π. This motivates our second key innovation beyond prior models [1, 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 t, we refine the earlier alignment P t-1 to the next estimate P t , which will be used in the next round. Henceforth, we will use the double subscript t, k instead of the single subscript k as in traditional GNNs. We denote the node embeddings at layer k and round t by h(q) t,k (u), h (c) t,k (u ′ ) ∈ R dim h for u ∈ V q and u ′ ∈ V c ,which are (re-)initialized with node features h • t,0 for each round t. We gather these into matricesH (q) t,k = [h (q) t,k (u) | u ∈ V q ] ∈ R n×dim h and H (c) t,k = [h (c) t,k (u ′ ) | u ′ ∈ V c ] ∈ R n×dim h . (9)P no longer remains an oracular hard permutation matrix, but becomes a doubly stochastic matrix indexed by rounds, written as P t . At the end of round t, a differentiable aligner module takes H (q) t,K and H (c) t,K as inputs and outputs a doubly stochastic node alignment (relaxed permutation) matrix P t as follows:EQUATION= GumbelSinkhorn LRL ϕ (HEQUATIONIn the above expression, GumbelSinkhorn(•) performs iterative Sinkhorn normalization on the input matrix added with Gumbel noise [26] ; LRL ϕ is a neural module consisting of two linear layers with a ReLU activation after the first layer. As we shall see next, P t is used to gate messages flowing across from one graph to the other during round t + 1, i.e., while computing H (q) t+1,1:K and H (c) t+1,1:K . The soft alignment P t is kept frozen for the duration of all layers in round t + 1. P t [u, u ′ ] may be interpreted as the probability that u is assigned to u ′ , which naturally requires that P t should be row-equivariant (column equivariant) to the shuffling of the node indices of G q (G c ). As shown in Appendix D, the above design choice (11) ensures this property.Updating node representation using early-interaction GNN Here, we describe the early interaction GNN for the query graph G q . The GNN on the corpus graph G c 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 P t=0 , we employ the traditional late interaction GNN (1) to compute all layers H (q) 1,1:K and H (c) 1,1:K separately. These embeddings are then used to estimate P t=1 using Eq. (11) . For subsequent rounds (t > 1), given embeddings H (q) t,1:K , and the alignment estimate matrix P t , we run an early interaction GNN from scratch. We start with a fresh initialization of the node embeddings as before; i.e., h(q) t+1,0 (u) = Init θ (feature(u)). For each subsequent propagation layer k + 1 (k ∈ [0, K -1]),we approximate (8) as follows. We read previous-round, same-layer embeddings h(c) t,k (u ′ ) of nodes u ′ from the other graph G c , incorporate the alignment strength P t [u, u ′ ],and aggregate these to get an intermediate representation of u that is sensitive to P t and G c .EQUATIONHere, inter θ is a neural network that computes interaction between the graph pairs; z 8), which can be relaxed as:(q) t+1,k (u) provides a soft alignment guided representation of [h (q) k (u), h (c) k (π(u))] in Eq. (EQUATIONIn the above expression, we explicitly feed z(q) t+1,k (v), v ∈ nbr(u) in the msg θ network, capturing embeddings of nodes in the corpus G c aligned with the neighbors of node u ∈ V q in h (q)t+1,k+1 (u). This allows the model to perform node-pair partner interaction. Instead, if we were to feed only h (q) t+1,k (u) into the msg θ network, then it would only perform node partner interaction. In this case, the computed embedding for u would be based solely on signals from nodes in the paired graph that directly correspond to 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 ∆(G c | G q ) as a soft distance between the set H (q)EQUATIONOur 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 q , G c+ , G c-⟩, meaning that, ideally, we want∆ θ,ϕ (G c-|G q ) ≥ γ + ∆ θ,ϕ (G c+ |G q ), where γ > 0 is a margin hyperparameter. This suggests a minimization of the standard hinge loss as follows:EQUATION)This loss is back-propagated to train model weights θ in comb θ , inter θ , msg θ and weights ϕ in the Gumbel-Sinkhorn network.Having set up the general multi-round framework of IsoNet++, we introduce a structurally simpler variant that updates P 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 a 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, K) for lazy updates. Formally, P k is updated across layers as follows:EQUATION)We update the GNN embeddings, layerwise, as follows:EQUATIONEQUATIONAnalysis 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.- -Multi-layer eager IsoNet++ (Node):The total complexity is O(K|V | 2 + K|E| + K|V | 2 ) = O(K|V | 2 ), computed as follows: (1) Initialization (layer k = 0) takes O(|V |) time. (2)The computation of intermediate embeddings z (•) (Eq. 18) involves the evaluation of the expression -Multi-round IsoNet++ (Node): Here, the key difference from the multi-layer version above is that the doubly stochastic matrix P t from round t is used to compute z and the K-step-GNN runs in each of the T rounds. This multiplies the complexity of steps 2 and 3 with T , raising it tou ′ ∈Vc h (•) k (u ′ )P k [u, u ′ ]O(KT |V | 2 + KT |E|). Matrix P t is updated a total of T times, which changes the complexity of step 4 to O(T |V | 2 ). Hence, the total complexity is O(KT |V | 2 + T |V | 2 + KT |E|) = O(KT |V | 2 ). Hence, the complexity of IsoNet is O(|V | 2 + K|E|), multi-layer IsoNet++ is O(K|V | 2 ) and multi- round IsoNet++ is O(KT |V | 2 ). This increased complexity of the latter comes with the benefit of a significant performance boost, as our experiments suggest.We now extend IsoNet++ (Node) to IsoNet++ (Edge) which uses explicit edge alignment for interaction across GNN and relevance distance surrogate.Multi-round refinement of edge alignment In IsoNet++ (Edge), we maintain a soft edge permutation matrix S which is frozen at S = S t-1 within each round t ∈ [T ] and gets refined after every round t as S t-1 → S t . Similar to IsoNet++ (Node), within each round t, GNN runs from scratch: it propagates messages across layers k ∈ [K] and S t-1 assists it to capture cross-graph signals. Here, in addition to node embeddings hEQUATIONt,k (e ′ ) ∈ R dimm at each layer k and each round t, which capture the information about the subgraph k ≤ K hop away from the edges e and e ′ . Similar to Eq. ( 9), we defineM (q) t,k = [m (q) t,k (e)] e∈Eq , and M (c) t,k = [m (c) t,k (e ′ )] e ′ ∈Ec . M (•)t,0 are initialized using the features of the nodes connected by the edges, and possibly local edge features. Given the embeddings M (q) t,K and M (c) t,K computed at the end of round t, an edge aligner module (EdgeAlignerRefinement ϕ (•)) takes these embedding matrices as input and outputs a soft edge permutation matrix S t , similar to the update of P t in Eq. (11) .EQUATION= GumbelSinkhorn(LRL ϕ (MEQUATIONHere, M (•) t,K are appropriately padded to ensure that they have the same number of rows. Edge alignment-induced early interaction GNN For t = 1, we start with a late interaction model using vanilla GNN (1) and obtain S t=1 using Eq. (21) . Having computed the edge embeddings m (•) t,1:K (•) and node embeddings h (•) t,1:K (•) upto round t, we compute S t and use it to build a fresh early interaction GNN for round t + 1. To this end, we adapt the GNN guided by P t in Eqs. ( 12)- (13) ,to the GNN guided by S t . 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 S t , similar to Eq. (12) . Specifically, we use the embeddings of edges {e ′ = (u ′ , v ′ )} ∈ E c , computed at layer k at round t, which share soft alignments with an edge e = (u, v) ∈ E q , to compute z (q) t+1,k (e) and z (q) t+1,k (e ′ ) as follows:EQUATIONFinally, we update the node embeddings h(•)t+1,k+1 for propagation layer k + 1 asEQUATIONIn this case, we perform the cross-graph interaction at the edge level rather than the node level. Hence, msg θ acquires cross-edge signals separately as z(•) t+1,k . Finally, we use h (•)t+1,k+1 and z(•) t+1,k+1 to update m (•)t+1,k+1 as follows:EQUATIONLikewise, we develop m(c) t+1,k+1 for corpus graph G c . Note that m (q)t+1,k+1 ((u, v)) captures signals not only from the matched pair (u ′ , v ′ ), but also signals from the nodes in G c which share correspondences with the neighbor nodes of u and v. Finally, we pad zero vectors to [m(q) T,K (e)] e∈Eq and [m (c) T,K (e ′ )] e ′ ∈Ec to build the matrices M (q) T,K and M (c)T,K with same number of rows, which are finally used to compute the relevance distanceEQUATION 
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.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 [27, 35] . Appendix F 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., (1) GraphSim [2] (2) GOTSim [11] , (3) SimGNN [1] , (4) EGSC [31] , (5) H2MN [45] , (6) Neuromatch [23] , (7) GREED [32] , (8) GEN [22] , (9) GMN [22] (10) IsoNet (Node) [35] , and ( 11) IsoNet (Edge) [35] . Among them, Neuromatch, GREED, IsoNet (Node) and IsoNet (Edge) apply asymmetric hinge distances between query and corpus embeddings for ∆(G c | G q ), specifically catered towards subgraph matching, similar to our method in Eqs. ( 14) and (25) . GMN and GEN use symmetric Euclidean distance between their (whole-) graph embeddings g (q) (for query) and g (c) (for corpus) as ||g (q) -g (c) || in their paper [22] , which is not suitable for subgraph matching and therefore, results in poor performance. Hence, we change it to∆(G c | G q ) = [g (q) -g (c) ] + .The other methods first compute the graph embeddings, then fuse them using a 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 a ranking loss (15) . During the training of each model, we use five random seeds. Given a test query q ′ , we rank the corpus graphs C in the decreasing order of ∆ θ,ϕ (G c | G q ′ ) computed using the trained model. We evaluate the quality of the ranking by measuring Average Precision (AP) and HITS@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 T = 3, the number of propagation layers in GNN K = 5. In Appendix F, we discuss the baselines, hyperparameter setup and the evaluation metrics in more detail. First (Last) two rows report MAP for multi-round (multilayer) update. Green shows the best method.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 alignment allows us to compare the graph pairs more effectively than node alignment.A similar effect was seen for IsoNet (Edge) vs. IsoNet (Node) [35] .(2) Among all state-of-the-art competitors, IsoNet (Edge) performs the best followed by IsoNet (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 ∆(G c | G q ). This results in modest performance compared to IsoNet++. (3) GMN uses "attention" to estimate the alignment between graph pairs, which induces a 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-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 at (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.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. (7) . For lazy multi-round updates, we compute the embeddings as follows:h (q) t+1,k+1 (u) = comb θ (h (q)t+1,k (u), v∈nbr(u) msg θ (h(q) t,k (u), h (q) t,k (v)), u ′ ∈Vc P t [u, u ′ ]h (c)t,k (u ′ )) For eager multi-layer updates, we compute the embeddings as: h (q) k+1 (u) = comb θ (h (q) k (u), v∈nbr(u) msg θ (h (q) k (u), h (q) k (v)), u ′ ∈Vc P k [u, u ′ ]h (c) k (u ′ ))→ AIDS Multi-Layer k = 1 k = 2 k = 3 k = 4 k = 5Figure 6 : Empirical probability density of similarity between the estimated alignments and the true alignments P * , S * 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 ⊤ t P * )), p(Tr(S ⊤ t S * )) for multi-round lazy updates and p(Tr(P ⊤ k P * )), p(Tr(S ⊤ k S * )) for multi-layer eager updates.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).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-round (layer) updates, we instrument the alignments P t and S t (P k and S k ) for different rounds t ∈ [T ] (layers k ∈ [K]). Specifically, we look into the distribution of the similarity between the learned alignments P t , S t and the correct alignments P * , S * (using combinatorial routine), measured using the inner products Tr(P ⊤ t P * ) and Tr(S ⊤ t S * ) for different t. Similarly, we compute Tr(P ⊤ k P * ) and Tr(S ⊤ k S * ) for different k ∈ [K]. Figure 6 summarizes the results, which shows that (1) as t or k increases, the learned alignments become closer to the gold alignments; (2) multi-round updates refine the alignments approximately twice as faster than the multi-layer variant. The distribution of Tr(P ⊤ t P * ) at t = 1 in multi-round strategy is almost always close to Tr(P ⊤ k P * ) for k = 2. Note that, our aligner networks learn to refine the P t and S t 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 analyze the accuracy and inference time trade-off. We vary T and K for IsoNet++'s lazy multi-round variant, and vary K for IsoNet++'s eager multi-layer variant and for GMN. Figure 7 summarizes the results. 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 u ′ P [u, u ′ ]h(u ′ ), effectively acting as a convolution between alignment scores and embedding vectors. This likely enables P to function as a filter, countering the oversmoothing effect. 
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 a 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 state-of-the-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 at once. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Appendix G.1 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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? 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 F. 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? Answer: [Yes] Justification: The authors have studied the ethics guidelines and find the work to conform well to 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: Broader societal impacts (both positive and negative) are discussed in Appendix C. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 11. Safeguards 
 
 Appendix: We find two limitations of our method each of 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 is unknown and seemingly difficult. In fact, such a hashing procedure is not known even for predecessors like IsoNet (Edge) or GMN, and this is an 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-pairs, 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.In this section, we discuss different streams of work that are related to and have influenced the study.Graph neural networks (GNN) [14, 22, 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-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 a mechanism to 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 a node effectively through a structure aware transformer architecture.We utilize a differentiable gadget to compute an injective alignment, which is a doubly stochastic matrix. The differentiability is crucial to the training procedure as it 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 [10] . 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 on graphs through neural techniques is presented in [19] .Several different underlying measures have been proposed for graph similarity computation, including full graph isomorphism [22] , subgraph isomorphism [23, 35] , graph edit distance (GED) [2, 11, 13, 28, 44] and maximum common subgraph (MCS) [2, 11, 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 [11] 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 a 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 [25] . GREED [32] proposed a Siamese graph isomorphism network, a late interaction model to tackle the GED problem and provided supporting theoretical guarantees. Zhang et al. [45] 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 et al. [31] trained a slower attention-based network on multi-level features from a GNN and distilled its knowledge into a faster student model. Roy et al. [35] used the GumbelSinkhorn operator as a differentiable gadget to compute alignments in a backpropagation-friendly fashion and also demonstrated the utility of computing alignments for edges instead of nodes.This work can be directly applied to numerous practical applications, such as drug discovery and circuit design, which are enormously beneficial for the society and continue to 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 as 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.IsoNet++ models consist of three components -an encoder, a message-passing network and a 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 linear-ReLU-linear network with Linear(a, b), Linear(b, c) layers with ReLU activation in the middle as LRL(a, b, c).The encoder transforms input node/edge features before they are fed into the message-passing 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 message-passing network. For edge-based models like IsoNet++ (Edge), the encoder refers to both Init θ,node and Init θ,edge , which are implemented as Linear(1, 10) and Linear(1, 20) layers respectively.Within the message-passing framework, we use node embeddings of size dim h = 10 and edge embeddings of size dim m = 20. We specify each component of the GNN below.• inter θ combines the representation of the current node/edge (h • ) with that from the other graph, which are together fed to the network by concatenation. For node-based and edgebased models, it is implemented as LRL (20, 20, 10) and LRL (40, 40, 20) networks respectively. In particular, we ensure that the input dimension is twice the size of the output dimension, which in turn equals the intermediate embedding dimension dim(z). • msg θ is used to compute messages by combining intermediate embeddings z • of nodes across an edge with the representation of that edge. For node-based models, the edge vector is a fixed vector of size 1 while the intermediate node embeddings z • are vectors of dimension 10, resulting in the network being a Linear(21, 20) layer. For edge-based 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 (v, u) and the outputs thus obtained are added up. This is to ensure node order invariance for undirected edges by design. • comb θ combines the representation of a node z • with aggregated messages received by it from all its neighbors. It is modelled as a 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 us the final node embedding h • .The node aligner takes as input two sets of node vectors H (q) ∈ R n×10 and H (c) ∈ R n×10 representing G q and G c respectively. n refers to the number of nodes in the corpus graph (the query graph is padded to meet this node count). We use LRL ϕ as a LRL (10, 16, 16 ) network (refer Eq. 11).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 (q) ∈ R e×20 and M (c) ∈ R e×20 . e refers to the number of edges in the corpus graph (the query graph is padded to meet this edge count). We use LRL ϕ as a LRL (20, 16, 16 ) network (refer Eq. 21).The GumbelSinkhorn operator consists of the following operations -EQUATIONThe matrix D out obtained after this set of operations will be a doubly-stochastic matrix. The input D in in our case is the matrix containing the dot product of the node/edge embeddings of the query and corpus graphs respectively. τ represents the temperature and is fixed to 0.1 in all our experiments.Theorem Equation 11 results in a permutation matrix that is row-equivariant (column-) to the shuffling of nodes in G q (G c ).Proof To prove the equivariance of Eq. 11, we need to show that given a shuffling (permutation) of query nodes Z ∈ Π n which modifies the node embedding matrix to Z Ḣ(q) t,K , the resulting output of said equation would change to ZP t . Below, we consider any matrices with Z in the suffix as being an intermediate expression in the computation of NodeAlignerRefinement ϕ (ZH(q) t,K , H (c) t,K ).It is easy to observe that the operators LRL ϕ (a linear-ReLU-linear network applied to a matrix), RowNorm, ColumnNorm and element-wise exponentiation (exp), division are all permutationequivariant since a 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 of operations (29) D 0,Z equals exp(D in,Z /τ ), which according to above equation would lead to D 0,Z = ZD 0 . We can then inductively show using Eq. 27 and the equivariance of row/column normalization, assuming the following holds till t, thatD in,Z = LRL ϕ (ZH (q) t,K ) LRL ϕ (H (c) t,K ) ⊤ = Z • LRL ϕ (H (q) t,K ) LRL ϕ (H (c) t,K ) ⊤ D in = ZD inD t+1,Z = RowNorm (ColumnNorm(D t,Z )) = RowNorm (ColumnNorm(ZD t )) (30) = RowNorm (Z • ColumnNorm(D t )) = Z • RowNorm (ColumnNorm(D t )) = ZD t+1 (31)The above equivariance would also hold in the limit, resulting in the doubly stochastic matrix D out,Z = ZD out , which concludes the proof. ■ A similar proof can be followed to show column equivariance for a shuffling in the corpus nodes.E.1 Multi-round refinement of IsoNet++ (Node) for the corpus graphEQUATION• Update the GNN embeddings as follows:EQUATIONEQUATIONE.2 Eager update for IsoNet++ (Edge)• Initialize:EQUATION0 (e) = Init θ,edge (feature(e)), (36) • The edge alignment is updated across layers. S 0 is set to a matrix of zeros. For k > 0, the following equation is used:EQUATION• We update the GNN node and edge embeddings as follows:EQUATIONEQUATIONEQUATIONE.3 Node partner (with additional MLP) variant of IsoNet++ (Node)Here, we update node embeddings as follows:h (q) t+1,k+1 (u) = comb θ z (q) t+1,k (u), v∈nbr(u) msg θ (h (q) t+1,k (u), h (q) t+1,k (v)) z is replaced with h (42)Here, zt+1,k (u) is computed as Eq. ( 12), where inter θ is an MLP network. In contrast to Eq. ( 13), here, z(q) t+1,k (u), z (q)t+1,k (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 v in G c . Only signals from partners of u are captured through z (q) t+1,k (u) in the first argument.We change the GNN update equation as follows:h (q) t+1,k+1 (u) = comb θ h (q) t+1,k (u)z is replaced with h , v∈nbr(u) msg θ (zEQUATIONNode pair partner interaction takes place because, we feed z from Eq. ( 12) into the message passing layer. However, we use h in the first argument, instead of z.We use six datasets from the TUDatasets collection [27] for benchmarking our methods with respect to existing baselines. Lou et al. [23] devised a method to 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 matching. In particular, we choose a node u ∈ G 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 q | and |V c ). This process is 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 of query graphs is split into train, validation and test splits of 180 (60%), 45 (15%) and 75 (25%) graphs respectively. Ground truth labels are computed for each query-corpus graph pair using the VF2 algorithm [9, 15, 23] GraphSim, GOTSim, SimGNN, Neuromatch, GEN, GMN, IsoNet (Node), IsoNet (Edge): We utilized the code from official implementation of [35] 1 . Some for loops were vectorized to improve the running time of GMN. EGSC: The official implementation2 is refactored and integrated into our code. H2MN: We use the official code from 3 . GREED: We use the official code from 4 . 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 .GraphSim [2] 3909 GOTSim [11] 304 SimGNN [1] 1671 EGSC [31] 3948 H2MN [45] 2974 Neuromatch [23] 3463 GREED [32] 1840 GEN [22] 1750 GMN [22] 2050 IsoNet (Node) [35] 1868 IsoNet (Edge) [35] 2028 IsoNet++ (Node) 2498 IsoNet++ (Edge) 4908 Given a ranked list of corpus graphs C = {G c } for a test query G q , sorted in the decreasing order of ∆ θ,ϕ (G c |G q ), let us assume that the c th + relevant graph is placed at position pos(c + ) ∈ {1, ..., |C|} in the ranked list. Then Average Precision (AP) is computed as:EQUATIONMean average precision is defined as q∈Q AP(q)/|Q|.Precision@K(q) = 1 K # relevant graphs corresponding to G q till rank K. Finally we report the mean of Precision@K(q) across queries.Reciprocal rank or RR(q) is the inverse of the rank of the topmost relevant corpus graph corresponding to G q in the ranked list. Mean reciprocal rank (MRR) is average of RR(q) across queries.HITS@K for a query G q is defined as the fraction of positively labeled corpus graphs that appear before the K 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@K and MRR, as can be seen in Tables 12 and 13 .All models were trained using early stopping with MAP score on the validation split as a stopping criterion. For early stopping, we used a 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, 10 4 ] resulting in the set {1704, 4929, 7366, 7474, 7762}. IsoNet++ (Node), GMN and IsoNet (Edge) were trained on each of these 5 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 is non-convex, in principle, one should choose the best initial conditions leading to local minima. Hence, for all models, we choose the best seed, based on validation MAP score, is shown in Table 10 .GraphSim [2] 7762 4929 7762 7366 4929 7474 GOTSim [11] 7762 7366 1704 7762 1704 7366 SimGNN [1] 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) [35] 7474 7474 7474 1704 4929 1704 GMN [22] 7366 4929 7366 7474 7474 7366 IsoNet++ (Node) 7762 7762 7474 7762 7762 7366Table 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 4, 5 and 16). 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 on the validation split were considered. Full training with early stopping was resumed only for 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), we use 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, a fixed margin of 0.5 is used.Procedure for baselines EGSC, GREED, H2MN: They are trained on five seeds with a margin of 0.5 for 10 epochs and the best seed is chosen using the validation MAP score at this point. This seed is also used to train a model with a margin of 0.1 for 10 epochs. The better of these models, again using MAP score on the validation split, is identified and retrained till completion using early stopping.GraphSim [2] 0.5 0.5 0.5 0.5 0.5 0.5 GOTSim [11] 0.1 0.1 0.1 0.1 0.1 0.1 SimGNN [1] 0.5 0.1 0.5 0.1 0.5 0.5 EGSC [31] 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 [23] 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 [22] 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 Additionally, we use wandb [5] to manage and monitor the experiments.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 not be identified. The authors were unable to identify the license of the TUDatasets repository [27] , which was used to compile the 6 datasets used in this paper.In Tables 12 and 13 , we report the Mean Average Precision (MAP), HITS@20, MRR and Precision@20 scores for several baselines as well as the four approaches discussed in 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 IsoNet++ (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 metrics from the point of view of information retrieval. Table 13 : MRR and Precision@20 of corresponding models from 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 MRR and Precision@20. In all cases, we used 60% training, 15% validation and 25% test sets. The first five methods apply a 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.G.2 HITS@20, MRR and Precision@20 for multi-round IsoNet++ and multi-layer IsoNet++ Table 14 compares multi-round and multi-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 in Table 4 . Note that a minor exception occurs for MRR but the scores are already so close to 1 that this particular metric can be discounted and our key observation above still stands.The node (edge) alignment calculated after round t is denoted as P t (S t ). We accumulate such alignments across multiple rounds. This also includes P T (S T ) which is used to compute the relevance distance in Eq. 14 (Eq. 25). We wish to compare the predicted alignments with ground truth alignments. We expect our final alignment matrix P t (S t ) to be one of them. We determine the closest ground truth matrices P * and S * by computing max P Tr(P ⊤ T P ) and max S Tr(S ⊤ T S) for IsoNet++ (Node) and IsoNet++ (Edge) respectively. We now use the closest ground-truth alignment P * , to compute Tr(P ⊤ t P * ) for t ∈ [T ]. For each t, we plot a histogram with bin width 0.1 that denotes the density estimate p(Tr(P ⊤ t P * )). The same procedure is 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 t. The frequency of graph pairs with misaligned P t (S t ) decreases with rounds t while that with well-aligned P t (S t ) increases.Here, we also study alignments obtained through 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 k and are accumulated across layers k ∈ [K]. In Figure 15 , we observe that the plots, in general, shift rightward with increasing k. The frequency of graph pairs with misaligned P t (S t ) decreases with rounds k while that with well-aligned P k (S k ) increases.IsoNet++ (Node)In Table 16 , we compare different alternatives to 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 (msg 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 in 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) in 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. → PTC-FM Multi-Layer k = 1 k = 2 k = 3 k = 4 k = 5→ PTC-MR Multi-Layer k = 1 k = 2 k = 3 k = 4 k = 5In Table 17 , we modify the GMN architecture to include node pair partner interaction in the messagepassing layer. Based on the reported metrics, we observe that there is no substantial improvement upon including information from node pairs in GMN, which is driven by a non-injective mapping (attention). This indicates that injectivity of the doubly stochastic matrix in our formulation is crucial towards the boost in performance obtained from node pair partner interaction as well. G.6 Variation of IsoNet++ (Node) and IsoNet++ (Edge) with different T and KIn this section, we analyze the accuracy and inference time trade-off of multi-round lazy and multilayer eager variants of IsoNet++ (Node) and IsoNet++ (Edge). In the following tables, we 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 can 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 to multi-layer eager IsoNet++ (Node) with K = 8, allowing for a 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 19 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 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 K. We observe that except for a drop at K = 7, the performance of the model improves as we increase K. In fact, at K = 8, the performance is surprisingly good, even outperforming the similarly timed T = 5, K = 5 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 T is fixed and K is increased, the gain is marginal. We observe a significant gain When K is fixed and T is increased from 3 to 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 to improve and peaks at K = 8. Note that even at this K, the performance of multi-layer eager IsoNet++ (Edge) is worse than a similarly timed variant (T = 5, K = 5) of multi-round IsoNet++ (Edge).In table 25, we show variations for GMN for varying K. We observe marginal gains while increasing K. From K = 10 to K = 12, the performance drops.In table 26, we show how performance varies for IsoNet (Edge) for varying K. We observe that the model does not improve with increasing K. In 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, we 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 P contribute almost equally since P is refined only at the end of each round, after several layers of message passing alongwith embedding computation. In this section, we evaluate the transfer ability of each trained model across datasets. In table 28 , we 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 to all others, variants of IsoNet++ show the best accuracy. • The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material.https://github.com/Indradyumna/ISONET/https://github.com/canqin001/Efficient_Graph_Similarity_Computationhttps://github.com/cszhangzhen/H2MNhttps://github.com/idea-iitd/greedMean Average Precision (MAP) 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.

- 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?
questions: questions: Please see Weaknesses. Also:

- The readers refer oversmoothing problems in some of the previous methods. Can they expand on how their approach side-steps this?

- Can the authors better explain lines 333 — 336? I found them hard to understand.

- How does the computational complexity compare with that of IsoNet?
limitations: limitations: The authors do not seem to explicitly discuss them in the main corpus, but mention two aspects in Appendix A.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
2. 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.
questions: 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?
- What do the multiple points with the same color in Figure 6 represent? Do they indicate variants with different hyperparameters?
limitations: limitations: Yes. This paper discussed the limitations in terms of efficiency and
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: - Any related work indicating early interaction is good? As mentioned in line 36.
- In line 124 the notation $A_q \leq PA_c P^T$ is a bit confusing. 
- 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. 
- What is the complexity of Sinkhorn Knopp algorithm and Gumbel Sinkhorn?
- Is the K-layer GNN in each round t shared?
- Any intuition why lazy updates works better? Is it easier to optimize or other aspects?
- I don't quite understand why the work is not differentiable on nodes with different classes, as mentioned in appendix A. 
- Is there other measure between the $P$ and $P^*$? I feel $Tr(P^TP^*)$ does not capture all the information of the matrices.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The datasets used in the experiments are relatively small, with at most ~20 nodes. 
2. 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.
questions: questions: N/A
limitations: limitations: N/A

Comments: title: Thanks for your reply.
comment: Thanks for your response, which addressed my questions. I will maintain current score.
I acknowledge reading the authors' rebuttal, which I indeed found very helpful in better appreciating their contributions.

I strongly believe that the additional figures they proposed, the point-by-point discussion of contributions wrt previous works, as well as the complexity analyses should be included in the next revision of the manuscript.

I also appreciate the clarification on oversmoothing. I believe that, should the authors have space, they could also make these passages less cryptic in the paper. After all, they are mostly (interesting) conjectures.
Thank you for the detailed reply and your effort. I would like to raise my score to 6.
Thank you for your rebuttal.