Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks
Authors: Indradyumna Roy
Soumen Chakrabarti
Abir De
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph neural networks
graph retrieval

Abstract: The graph retrieval problem is to search in a large corpus of graphs for ones that are most similar to a query graph.  A common consideration for scoring similarity is the maximum common subgraph (MCS) between the query and corpus graphs, usually counting the number of common edges (i.e., MCES).  In some applications, it is also desirable that the common subgraph be connected, i.e., the maximum common connected subgraph (MCCS). Finding exact MCES and MCCS is intractable, but may be unnecessary if ranking corpus graphs by relevance is the goal.  We design fast and trainable neural functions that approximate MCES and MCCS well.  Late interaction methods compute dense representations for the query and corpus graph separately, and compare these representations using simple similarity functions at the last stage, leading to highly scalable systems.  Early interaction methods combine information from both graphs right from the input stages, are usually considerably more accurate, but slower.  We propose both late and early interaction neural MCES and MCCS formulations.  They are both based on a continuous relaxation of a node alignment matrix between query and corpus nodes.  For MCCS, we propose a novel differentiable network for estimating the size of the largest connected common subgraph.  Extensive experiments with seven data sets show that our proposals are superior among late interaction models in terms of both accuracy and speed.  Our early interaction models provide accuracy competitive with the state of the art, at substantially greater speeds.

Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks
Indradyumna Roy Soumen Chakrabarti Abir De
Indian Institute of Technology Bombay (indraroy 15, soumen, abir) @cse.ittbac.in
Abstract
The graph retrieval problem is to search in large corpus of graphs for ones that are most similar to a query graph. A common consideration for scoring similarity is the maximum common subgraph (MCS) between the query and corpus graphs, usually counting the number common edges (i.e., MCES). In some applications, it is also desirable that the common subgraph be connected, i.e., the maximum common connected subgraph (MCCS), Finding exact MCES and MCCS is intractable, but may be unnecessary if ranking corpus graphs by relevance is the goal. We design fast and trainable neural functions that approximate MCES and MCCS well. Late interaction methods compute representations for the query and corpus graphs separately, and compare these representations using simple similarity functions at the last stage, leading highly scalable systems. Early interaction methods combine information from both graphs right from the input stages, are usually considerably more accurate, but slower. We propose both late and early interaction neural MCES and MCCS formulations. They are both based on continuous relaxation of a node alignment matrix between query and corpus nodes. For MCCS, we propose novel differentiable 'gossip' network for estimating the size of the largest connected common subgraph. Extensive experiments with seven data sets show that our proposals accuracy and speed. Our carly interaction models provide accuracy competitive with the state of the art, at substantially greater speeds.
superior among late interaction models in terms of both
Introduction
Given query graph, the graph retrieval problem is to search for relevant or similar response 3 4
graphs from a corpus of graphs 2
g 10 Depending on the application, the size of the maximum
notion of relevance may involve graph edit distance (GED) 12 13.
common subgraph (MCS) [5] 6, 7 8 9). full graph or subgraph isomorphism [5] [O] [T] etc. In this work, focus on two variations of MCS-based relevance measures: (i) maximum common
edge subgraph (MCES) 15] which has applications in distributed computing [16] [3] and molecule
search [17 18
19 20 and (ii) maximum common connected subgraph (MCCS) 21). which has
applications in keyword search over knowledge graphs [22]2]] software development
26).
image analysis 227 28 29 etc.
In recent years, there has been an increasing interest designing neural graph retrieval models [5] 6 9 10]. However, most of them learn black box relevance models which provide suboptimal performance the context of MCS based retrieval (Section 4b. Moreover, they not provide intermediate matching evidence to justify their scores and therefore, they lack interpretability. In this context, Li et al. [5] proposed graph matching network (GMN) [5] based on a cross-grapp attention mechanism, which works extremely well in practice (Section Nevertheless, it suffers from three key limitations, leaving considerable scope for the design of enhanced retrieval models. (i) Similar to other graph retrieval models, it uses a general- purpose scoring layer, which renders it suboptimal in the context MCS based graph retrieval. (ii) As acknowledged by the authors, GMN is slow in both
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

training and inference, due to the presence of the expensive xross-attentie mechanism. (iii) MCS or any graph similarity function entails an injective mapping between nodes and edges across the graph pairs. In contrast, cross-attention induces potentially inconsistent and non-injective mappings, where a given query node can mapped to multiple corpus nodes and vice-versa.
1.1 Our contributions
We begin by writing down (the combinatorial forms of) MCES and MCCS objectives in specific ways that facilitate subsequent adaptation to neural optimization using both late and early interaction networks. Notably, these networks are trained end-to-end, using only the distant supervision by MCES or MCCS values of query-corpus graph pairs, without explicit annotation of the structural mappings identifying the underlying common subgraph.
Late interaction models. We use a graph neural network (GNN) to first compute the node embed- dings of the query and corpus graphs independently of each other and then deploy an interaction network for computing the relevance scores. This decoupling between embedding computation and interaction steps leads to efficient training and inference. We introduce LMCES and LMCCS, two late interaction neural architectures for MCES and MCCS based graph retrieval respectively. The interaction model is a differentiable graph alignment planner. It learns a Gumbel-Sinkhne network to provide an approximate alignment plan between the query and corpus graphs. In contrast to GMN [5]. it induces an approximately injective mapping between the nodes and edges of the query and corpus graphs. The MCES objective is then computed as differentiable network applied to this mapping. For MCCS, we further develop novel differentiable gossip network that computes the size of the largest connected component in the common subgraph estimated from the above mapping. These neural gadgets may be of independent interest.
(GS)
Early interaction model. In the early interaction model, perform the interaction step during the node embedding computation phase, which makes the query and corpus embeddings dependent on each other. This improves predictive power, at the cost of additional training and inference time. Here, we propose XMCS (cross-MCS), an early interaction model that works well for both MCES and MCCS based graph retrieval. At each propagation layer of the GNN, we first refine the alignment plan using the embeddings computed in the previous layer, then update the underlying coverage objective using the refined alignment and finally use these signals to compute the node embeddings of the current layer.
Comprehensive evaluation. We experiment with seven diverse datasets, which show that: (i) our late and early interaction models outperform the corresponding state-of-the-an methods in terms of both accuracy and inference time; (ii) in many cases, LMCES and LMCCS outperform the early interaction model of GMN [5]; and (iii) GMN's accuracy can be significantly improved by substituting its final layer with our MCS- neural surrogate.
1.2 Related work
Combinatorial algorithms for MCS. Both MCES and MCCS are NP-complete
15 Several works Bahiense et al.
designed heuristics for computing MCES for specific types of graphs [18 17 30
formulated MCES as an integer programming problem, provided a polyhedral analysis of the underlying formulation, and finally designed a branch and cut algorithm to solve it. Such polyhedral study for MCES was also performed by others [2). Combinatorial methods for different variants of MCCS have also been thoroughly studied. Some of them provide exact MCCS
15]
33 34 35
McCreesh et al. [33] proposed McSplit, a branch and bound algorithm for maximum common induced and connected graph, which is efficient in terms of time and memory. Other works provide effective hcuristics to find approximate MCCS [36] 37). However, these methods are not differentiable and therefore not suitable for data-driven MCS estimation.
Learning models for MCS. There are some recent efforts to design machine learning models for graph similarity and search (38 77 Among them, Bai et al. 38 GL.seacch compute MCS between two graphs using a reinforcement learning setup. In contrast, we consider a supervised learning setting for graph retrieval. Although Bai et al. 77 GraphSim] focus on the supervised learning scenario, their relevance scoring model performs poorly for MCS based retrieval.
Graph matching for computer vision. Neural models for graph matching are used in applications of computer vision for computing image similarity, object detection, etc. However, these applications
permit explicit supervision of the underlying node alignments [39] 40 4] 42 43
45 46 47 48)

---

They adopt different types of losses which include permutation loss [4] 42 43 44
Hungarian
loss [46]. and displacement loss [40] In our problem. we only use distant supervision in the form of size of the underlying MCS. Moreover, these work mostly consider graph matching problems, superttsueeeiiii
whereas we consider maximum common subgraph detection using distant supervision from MCS
score alone.
Graph representation learning. Representation learning on graphs has been widely researched in 53
the last decade [49, [50] 51 52
54]. Among them, graph neural networks (GNN) are the most
55 56]- Given a node u, a GNN collects information from K K-hopp neighbors of the node and applies a symmetric aggregator on top of it to obtain the representation vector of the nodes. the context of graph retrieval, the node embeddings are used in two ways. In the first approach, they are further aggregated into graph embeddings, which are then used to compute the similarity between query and corpus graphs, by comparing the embeddings in the vector space TO [5. The second approach consists of SimGNN [6). GOTSim [8] GraphSim [7], GEN (5) and GMN (5], which compare the node embeddings and find suitable alignments between them. Here, GMN applies cross attention based mechanism on the node embeddings given graph neural network [49]. Recently, Chen et al. [57] designed a structure aware transformer architecture, which can represent subgraph around a node more effectively than several other representation models.
popular node embedding models 44
50
51
52
Differentiable solvers for combinatorial algorithms. Our work attempts to find neural surrogate for the combinatorial challenge of maximizing objective scores over a permutation space. In effect, we are attempting to solve an Optimal Transport problem, where the central challenge is to present a neural gadget which is differentiable and backpropagable. thus enabling end-to-end training. Cuturi [58] utilized iterative row and column normalization, earlier proposed by Sinkhorn [59] to
approximately solve the transportation problem subject to marginal constraints. In another approach, Vlastelica al. (0) attempted to solve combinatorial problems exactly using available black-box solvers, by proposing to use the derivative of an affine surrogate of the piece-wise constant function in the backward pass. Rolínek al. [61] leverage this to perform deep graph matching based on explicit supervision of the ground truth node alignments. In another approach, Berthet et al. (62) perturb the inputs the discrete solvers with random noise, so as make them differentiable. Karalias and
Loukas [63] design probabilistic loss functions for tackling the combinatorial objective of selecting a subset of nodes adhering to some given property. Finally, Kotary et al. (64] present a detailed survey of the existing neural approaches for solving constrained optimization problems on graphs
2 Late interaction models for MCES and MCCS
In this section, we first write down the exact objectives for MCES and MCCS. These expressions are partly based upon a pairing of nodes between query and corpus graphs, and partly on typical graph algorithms. They lead naturally to our subsequent development of two late interaction models, LMCES and LMCCS. We begin with formal definitions of MCES and MCCS.
Definition 1 (MCES and MCCS) Given query and corpus graphs G Gv=(Vy, Eg) and G.= Ec).
(1) The maximum common edge subgraph MCES(G Ge) is the common (not necessarily induced nor connected) subgraph between Gg and Ge. having the maximum number of edges KT5Y. (2) The maximum common connected subgraph MCCS(G G.) is the common connected subgraph with the maximum number of nodes (2T
2.1 Combinatorial formulations for MCES and MCCS
combinatorial algorithms for MCES and MCCS abound in the litera- However, it is difficult to design neural surrogates for these algorithms. Therefore, we come up with the new optimization objectives for MCES and MCCS, which allow us to design neural surrogates by gradually replacing its different components with differentiable parameterized components.
As mentioned in Section 1.2
ture [34] 15
18
17
30
Exact MCES. Given a query graph G,= -V,, E.) and corpus graph G. Ec), we pad the graph having fewer vertices (typically, Gj), with [|Val - [V, disconnected nodes. This ensures that the padded graphs have an equal number of nodes N. Let us denote the adjacency matrices of G2 and Ge (after padding) as A, E {0, [0,1)Nxx NxN and A. E {0, NxN, To find MCES(G,, G.) from the
3

---

adjacency matrices Ag and Ac, we first obtain the candidate common subgraph under some proposed node alignment given by permutations of A., which can be characterized by the adjacency matrix min( Aq. P P²). This matrix shows the overlapping edges under the proposed node alignment. Subsequently, we choose the permutation which maximizes the total number of edges in this subgraph. Formally, we compute the MCES score by solving a coverage maximization problem, as follows:
maxpEP Σng min (Ag: PA.PT) i.
(1)
where P is the set of permutation matrices of size N N and the min operator is applied elementwise. Exact MCCS. MCES does not require the common subgraph to connected, which may be desirable in some applications. For example, in keyword search and question answering over knowledge graphs (KGs) [22 65 23]. one may wish to have the entity nodes, forming the response, to be connected to each other. In molecule search, one may require connected functional group to be present in both query and corpus graphs [9]. In such situations, MCCS may be more appropriate.
Given a query graph Gg and a corpus graph Ge and their adjacency matrices Ag and Ac after padding, we first apply a row-column permutation on A. using the permutation matrix P and obtain the candidate common subgraph with adjacency matrix min( A,, P P..P")). Then we apply Tarjan's s algorithm (66) to return the size of the largest connected component, which we maximize w.r.t. P:
maxpEp TARJANSCC (min (Ag. PA.PP)
Here TARJANSCC takes the adjacency matrix as input and returns the size of the largest connected component of corresponding graph.
One way of avoiding the intractability of searching through P. to replace the hard permutation matrix with a differentiable soft surrogate via the Gumbel-Sinkhon (GS) network 667 also see Section B However, such a relaxation is not adequate on its own.
Bottleneck of approximating the optimization problems 11 and 2
1. Most elements of min( (Ag. P..PT) are binary, which deprives the learner of gradient signals. 2. In practice, the nodes edges may have associated (noisy) features, which play an important role in determining similarity between nodes or edges across query and corpus graphs. For example, in scene graph based image retrieval, "panther" may be deemed similar to "1 eeopard' rd". The objectives in Eqs. (1 and ( do not capture such phenomenon.
3. Tarjan's 's algorithm first applies DFS on graph to find the connected components and then computes the size of the largest among them, in terms of the number of nodes. Therefore, even for a fixed P, it is not differentiable.
Next, we address the above bottlenecks by replacing the objectives and ( with two neural surrogates, which are summarized in Figure
2.2 Design of LMCES
We design the neural surrogate of Eq. by replacing the adjacency matrices with the corresponding continuous node embeddings computed by a GNN, and the hard permutation matrix with a soft surrogate-a a doubly stochastic embeddings allow us to compute non-zero gradients and approximate similarity between nodes and their local neighborhood in the continuous domain. Specifically, we compute this neural surrogate in the following two steps.
setrii--enerrtedd by the Gumbel-Sikhor network (67). These node
Step 1: Computing node embeddings. We message passing graph neural network 449 68 GNN, with R propagation layers and trainable parameters 6, to compute the node embeddings (1). (1).....] h. (R) IRd, for each node in the query and corpus graphs, to which GNN, is applied N for [R] by stacking the node
separately. Finally, we build two matrices H (r...HH
embedding vectors for query and corpus graphs. Formally, we have
(1 (R) GNNo
H.(1)...., H.(R) = GNNo(G.))
(3)
Step 2: Interaction between (r) and (r).). In principle, the embeddings h (1)...... hr (R) of node u capture information about the neighborhood of Thus, we can view the set of embedding matrices (r₂(r) r E }R] and (H) r E [R]} as a reasonable representation of the query and corpus graphs, respectively. To compute smooth surrogate of the adjacency matrix of the common subgraph, i.e., min (A,. PA.PT), ), we seek to find the corresponding alignment between H (r) and (r) using soft- noft-permutation (doubly stochastic) matrices p(r) generated through Gumbel-Sikhorn

---

network GS Here, we feed Hg (r) and Ho(r) into GSş and obtain doubly stochastic matrix P(r); p!r) GS (H, H.(r)) vr [R]]
(4)
Finally, we replace the true relevance scoring function in Eq. T with the following smooth surrogate:
s(G G.) = Σ W min (H (r),), Hc()))
(5)
rE(
Here {w, 2 0:re [ trainable parameters, balancing the quality of signals over all message rounds r. Note that the R message rounds execute on the query and corpus graphs separately. The interaction between corresponding rounds, happens at the very end.
2.3 Design of LMCCS
In case of MCES, our key modification was to replace the adjacency matrices with node embeddings and design a differentiable network to generate ooft-permutation matrix. In the case of MCCS, we have to also replace the non-differentiable step of finding the size of the largest connected component of the common subgraph with neural surrogate, for which we design novel gossip protocol.
Differentiable gossip protocol to compute the largest connected component. Given any graph G = (V, E') with the adjacency matrix B, we can find its largest connected component (LCC) by using a gossip protocol. At iteration / = 0, we start with assigning each node a message vector an (0) E RA, which is the one-hot encoding of the node i.e., T. (0){) = 11 for u u and 0 otherwise. In iteration & > 0, we update the message vectors (t + 1) as (t,(t + 1) = Enenbr(w)) (t).
Here, (br(w) is the set of neighbors of u. Initially we start with sparse vector w,, with exactly one non-zero entry. As we increase the number of iterations, would gradually collect messages from the distant nodes which are reachable from u. This would in- crease the number of non-zero entries of xy. For sufficiently large value of iterations I' (diameter of G), we will attain x. (T) o O whenever u and lie in the same connected component and T. (T) O, otherwise. Once this stage is reached, one can easily compute the number of nodes in the largest connected component of G as max, [| (T) i.e., the maximum number of non-zero entries a message vector. Algorithm shows the gossip protocol, with the adjacency matrix B as input and the size of the largest connected component as output. Exact MCCS computation using the gossip protocol. Given the query and corpus graphs Gg and Ge with their adjacency matrices Ag and Ac, we can rewrite Eqn. (2) in the equivalent form
Algorithm 1 GOSSIP(B)
1: X(0) =I # ddntity
2: for fort=1,...7 do
3: X(++1) + X(t) I)
4: Return maxuey X(T))o, (e)))( uillo
max GossIp(min( Ag. PA.PT) PEP
Recall that the set permutation matrices of size N x N.
Neural surrogate. One can use a GS network to obtain a permutation matrix P, which in principle. can support backpropagation of min(A,p PT). However, as mentioned in Section 2.1 (items] and A. is 0/1, and P often saturates, losing gradient signal for training. In response, we will design neural surrogate for the true MCCS size given in Eq. (2). using three steps.
Step 1: Computation of edge embeddings. To tackle the above challenge, we introduce a parallel pockppropagttion path, in order to allow the GNNs to learn which edges more important than others. To this end, we first use the GNNs to compute edge embedding vectors m. (r) E Rd for edges E E, in addition to node embeddings at each propagation layer E [R]. Then, we gather the edge embeddings from the final layer R, into the matrices M, M.(R) REExxd for query and corpus pairs. Next, we feed each separately into a neural network I. with trainable parameters a, which predicts the importance of edges based on each edge embedding. Thus, we obtain two matrices S, E R XN and S. E R N which are composed of the edge scores between the corresponding node pairs. Formally, we have:
(R) M2 = GG,), (R),), (R) = GN.)
S, L,, (M,(R)) S. = L,, (R)
(8)
In our implementation, L. consists of one linear layer, ReLU layer and another linear layer. Step 2: Continuous approximation of MCCS. MCES, we approximated the MCES score in Eq. (1) directly, using the neural coverage function defined in Eq. (5) in terms of the node embeddings. Note that, here, we did not attempt to develop any continuous approximation of min (Ag, PA.PT) the adjacency matrix of the candidate common subgraph. However, in order to apply proposed
5

---

GNN,
H,,)),...
(R)
G
GNN
M.UR Ho(R)
8,(R)
pD
LMCES
G55
P(R)
[
LMCCS
GS
min (A, S,, PA, S.P)
G
GNN.
H H2(l) (
GOSSIP(-)
GNN
> oh D mine (r), Hallia
M.(R
(R)
mIR (X "I]l
HI(I)
Hr(r)
MESSAGEEASSINGG,
(r)
(r
H Ho(R)
Hy(r) min( Hefr), PITALED min (H)) PTOR BRO
XMCS
GS
UPDATE EMBEDDINGS
mint min( (R), plo H. H.
H Ho(l)
H. (r(r)
MESSAGEPASSING;
M
(.(R)
Figure 1: Proposed late (top row) and early (bottom row) interaction models. Top Left: LM- CES encodes the given query-corpus graphs separately, using R layers of GNN, to compute node embedding matrices (r), Hr(r) with
{l..... R}. For each layer r. the Gumbel- Sinkhorn network G computes the optimal alignment p(r) between (r) and Ha(r), which is finally used compute the relevance score in Eq. ( Top Right: LMCCS uses GNN to encode the Rt-hop node and edge embeddings, H. (R) and M. The edge embeddings M. (It) are fed into La, to predict edge score matrix S. (R) whose valid edge entries are encoded in A @ S. As before, (H, HR)R)) generates alignment ((R) which is used to compute candidate MCS graph min(A, A, @ Sq. P(A, C ST) which is then fed into the neural GOSSIP mod- ule, to predict the final MCCS score. Bottom: At each layer r, XMCS uses the alignment ma- trix p(r) factor the cross graph influences using (r) min(H, p(r) (r)r) for query. and H.(r) min( (r)) p(r)" (r)) for corpus. This is used update the node embeddings (r) + (r 1). Embeddings from the final layer are used to compute the final relevance score.
gossip protocol (or its neural approximation), we need an estimate of the adjacency matrix of the common subgraph. Therefore, we compute the noisy estimator as follows:
p= (H, (R), Ho)),,
= min (A, + Sq P(Ac C S..PP)
(9)
In the above expression, we replace all the non-zero entries of A, and A with the corresponding edge importance scores of S, and S.. This facilitates backpropagation more effectively, as opposed to the original 0/1 adjacency representation of the common subgraph (item iin Section 1. Here, we generate the permutation matrix using Gumbel-Sinkhon here we generate only one permutation matrix based on the embeddings on the final layer, whereas in MCES, we generated permutations p(r) for each layer r.
network similar to MCES, except that
Step 3: Neural implementation of gossip. Our gossip protocol in Algorithm I already differen- tiable. However, by the virtue of the way it is designed, it would give accurate results only if the input matrix consists of 0/1 values. However, our neural estimate B contains mostly non-zero continuous values and many of them can go beyond +1. As a result, the resultant matrix X(t) X (B) + II) in Algorithm [ may suffer from extremely poor conditioning. To tackle this problem, we use a noise filter network at the final step T' We first estimate a dynamic threshold T E [0, oc) and then set the values of (T) below that threshold zero. Finally, we scale the non-zero entries between (0, 1) using a sigmoid activation a a.). Formally, we define:
(10) where À is temperature hyperparameter. THRESH, consists of linear, ReLU, then another linear layer. Note that X(T) E (0, 1] by design, which lets us replace the Log norm in the final score (Algorithm T line 4) with the more benign T. norm, followed by a maxpool over nodes:
T THRESH (XEEESHHH((())))))
À(T) = 2o (ReLU[X(T) - - 1,
s(Gy G.) = max wEV
X w|]
(11)
Note that the interaction steps 2 and above are completely decoupled from step and do not have any contribution in computing embeddings.
3 Early/cross interaction model: XMCS
Although late interaction models offer efficient training and fast inference, prior work (5] suggests that early interaction models, while slower, may offer better accuracy. Motivated by such successes,

---

we propose a unified early interaction model, called XMCS, which works for both MCES and MCCS. XMCS is slower than LMCES and LMCCS, but provides significant accuracy gains (Section (
Moreover, it is significantly faster than GMN [ As before, the relevance score s(Gg Ge) is computed using a graph neural network (GNN) with R propagation layers, but each graph influences
embeddings of the other graph in each layer.
Initialization of node embeddings. We start with the raw node features 2n for each node u E VgUV and use them to initialize the node embeddings hu-
(0) FEATUREENCODERR((Z.))
(12)
Embedding computation via interaction between Gg and G.. Given the node embeddings (r) for some propagation layer < R. we first encode the intra-graph influences across all edges in both query and corpus graphs. Accordingly, we obtaín directed message vectors, for each pair of nodes (u, v)) E Fig U Pes which are then aggregated using simple sum aggregator.
mu (T) MESSAGEPASSINGA
hr),,,(r)) V (u, E Eg E. m. (r) = Σ w Muv(r) Yu E U.V.
(13)
(14)
Next, we perform the interaction step across the query and corpus graphs G3 and Ge. using a graph alignment network, which is modeled using GS similar to the late interaction models in Eq. $ We build embedding matrices (r) and Ho(r) by stacking (r) from Gg and G. respectively. Then, we feed them into GS to generate an alignment matrix, and finally compute the difference of the query and the corpus graphs from the underlying MCS in the continuous embedding space:
p(r) = GS
Hc(r);
(r( = Hr)r) - min (r). p(r) Hc(r));
(r( H Hr(r) - (in(Ha(r)...............)))m)ii) POT Hr))..
(15)
Note that A (r) in the above can also be written (eL
Hr(r)] (because min(a, b)
a Rea - b)) and thus (r(r) (similarly, (r))) captures the representation of a subgraph present in Gg (Ge). which is not present in Ge (G₂). Here, P provides injective mapping from V. GMN [5]. which is non-injective- assigns one corpus node to
to Vg. in contrast to attention- one query node but one query node to possibly multiple corpus nodes.
Next, the node embeddings h, are updated using aggregated intra- and cross-graph influences.
(r + 1) = UPDATEEMBEDDING (hw m.. (r): Σ, (r) V u E V2 UV. (16)
The node embeddings of G2 explicitly depend G. via the alignment p(+) and vice-versa. Relevance score computation. Finally, we compute the relevance score using the neural surrogate:
(GG Go) = Σ min( (H,(HH ((R) (R)))
(17)
Clearly, the above scoring function directly approximates the MCES objective I similar to the score given by LMCES in Eq. ( except that here we use the embeddings the last layer to compute the score. Although one can subsequently a combine gossip network with the above model, we found that it does not improve accuracy significantly and moreover, results in extreme slowdown.
Experiments
In this section, we provide comprehensive evaluation of our models across seven datasets and show that they outperform several competitors 66 Xmes
7
8 10
5. Our code is in https://tinyuul.co/mmmcss
4.1 Experimental setup
Datasets. We experiment with seven datasets, viz., MSRC-21 (MSRC), PTC-MM (MM), PTC-FR (FR), PTC-MR (MR), PTC-FM (FM), COX2 (COX) and DD. The details about them are described in Appendix C Among these datasets, we report the results of the first six datasets in the main paper and the DD dataset in Appendix D For every dataset, we have a corpus graph database with 800 graphs and a set of 500 query graphs, leading to 400000 query-corpus pair of graphs.
State-of-the-art methods compared. We compare our method against six state-of-the-arr late interaction models, viz. (i) SimGNN (6) (ii) GraphSim 77. (iii) GOTSim (8) (iv) NeuroMatch (10) (v) IsoNet [ and (vi) Graph embedding network (GEN) [5]; and one carly interaction model, viz.,
7

---

MSE (lower is better)
KTau (higher is better)
MCES
MSRC
MM
FR
MR
FM
COX
MSRC
MM
FR
MR
FM
COX
SimGNN
0.910
0.302
0.355
0.337
0.331
0
0.232
0.3G8
0.358
0.354
0.372
0.394
GiaphSim
0.629
0.274
0.282
0.274
0.261
0.249
0.461
0.432
0.458
0.454
0.500
0.403
Late
GOTSim
0.496
0.343
0.326
0.320
0.359
0.328
0.564
0,464
0.448
0.516
0.496
0.374
NeuroMatch
0.582
0.308
0,282
0.795
0.604
0.269
0,632
0,488
0.516
0,548
0,535
0.514
IsoNet
0.276
0.225
0.220
0.2019
0.253
0.182
0.669
0.506
0.504
0.537
0.532
0.522
GEN
0.426
0.311
0.273
0.284
0.324
0.277
0.627
0.416
0.468
0.456
0.456
0,466
LMCES
0.232
0.167
0.170
0.162
0.163
0.140
0.691
0.577
0.588
0.598
0.610
0.574
Early
GMN
0.269
0.184
0.181
0.178
0,189
0.155
0.670
0.544
0,567
0.568
0.569
0.555
XMCS
0.226
0.154
0.162
0.154
0.160
0.132
0.699
0.582
0.594
0.612
0.606
0.580
MSE (lower
better)
KTau (higher better)
MCCS
MSRC
MM
FR
MR
FM
COX
MSRC
MM
FR
MR
FM
COX
SimGNNN
0.100
0.360
0.137
0.233
0.316
0.289
0.125
0.281
0.308
0.313
0.299
0.366
GraphSim
0.088
0.283
0.290
0.221
0.255
0.325
0.153
0.336
0.337
0.315
0.366
0.292
Late
GOTSim
0.165
0.416
0.340
0.330
0.321
0.318
-0.088
0.320
0.327
0.307
0.380
0.416
NeuroMatch
0.352
0.376
0.326
0.351
0.295
0,984
0.125
0.376
0.365
0.370
0.406
01.40
IsoNet
0.086
0.237
0.244
0.191
0.218
0.253
0.185
0,381
0.388
0.351
0.402
0.406
GEN
0.171
0,366
0.344
0.290
0.356
0.309
0.111
0.325
0.332
0.305
0.326
0.391
LMCCS
0.068
0.174
0.179
0.134
0.173
0.177
0.248
0,451
0.438
0.406
0.457
0.487
Eart
GMN
0.101
0.200
0.216
0.156
0.193
0.176
0.174
0,416
0,405
0.379
0,431
0,479
XMCS
0.071
0.168
0.163
0.131
0.168
0.153
0.198
0.452
0.451
0.412
0.453
01501
Table I: Performance measured using mean square error (MSE) (left half) and Kendall-Tau Rank Correlation (Ktau) (right half) of our models and of-te-of-the-art baselines, viz., SimGNN (6), GraphSim 77. GOTSim (8), Neuromatch [10], IsoNet [T. GEN [5], GMN [5] on 20% test set. Top-half and bottom- half report results for MCES and MCCS respectively. Except GMN, all SOTA methods are late interaction models. Numbers in green (blue) indicate the best performers among early (late) interaction models. Numbers in yellow indicate second best performers for late interaction models.
(vii) Graph Matching Network (GMN) [S. All methods use a general purpose scoring layer, except for MeuroMatch and IsoNet, which are specifcially designed for subgraph isomorphism.
Training and evaluation. Given corpus graphs C= {Ge), query graphs Q= {G₂} and their gold MCES and MCCS values {UMCESS (Gg. G.)} and {yMces G... Ge)}. for Gg E Q Ge E C, we partition the query set into 60% training. 20% validation and 20% test folds. We train all methods by minimizing mean square error (MSE) loss between the predicted output and gold MCS (MCES or MCCS) values on the training split.
mina EG,Eq,G.C((A(GGG G.) -VGG,
(18)
Here y can be either /MCES or jMCCS and A is the set of trainable parameters for the relevance scoring function S (G, G.). In the context of our models, A {6, Φ WIR) for LMCES, A {8, Φ, a, [}} for LMCCS and A- = {0, o} for XMCS model. We use the validation split to tune various hyperparameters. Subsequently, we use the trained models to predict MCS scores between the test query graphs and the corpus graphs. For each of the query graphs in the test split, we use the predicted outputs to compute the MSE and Kendall- Tau rank correlation (KTau) values. Finally, we report the average MSE and mean KTau values across all the test query graphs
4.2 Results
Comparison with state-of-the-art methods. In Table we compare the performance of LMCES and XMCS (LMCCS and XMCS) against the sfate-of-the-al methods on both MCES (MCCS) based retrieval tasks. We observe: (1) For MCES and MCCS tasks, LMCES and LMCCS outperform all late interaction models by substantial margin in terms of MSE and KTauu across all datasets. (2) XMCS consistently outperforms GMN, the only early interaction baseline model. Suprisingly, GMN is also outperformed by our late interaction models, except in COX for the MCCS task. The likely reason is that GMN uses a general purpose scoring function and a cross attention mechanism that induces non-injective mapping between the nodes and edges of the query corpus pairs. (3) XMCS outperforms both LMCES and LMCCS, as expected. (4) For both MCES and MCCS tasks, IsoNet is consistently second- best with respect to MSE. IsoNet is a subgraph isomrrphism based retrieval model and its scoring function is proportional to Σe, (RI,
P( (R)).... which can be re- ne-written&a as [M, [R) - min(M, (R), p ( Mc (since min(a, b) = a - ReLU(a b)). Thus, the second term captures MCES score. During training, IsoNet is also able to shift and scale the above score to offset the additional term involving M, which likely allows it to outperform other
8

---

MCES
MSRC
MM
FR
MR
MCCS
MSRC
MM
FR
MR
GEN
0.426
0.311
0.273
0.284
GEN
0.171
0.366
0.344
0.290
Late
GEN (MCS)
0.284
0.181
0.179
0.169
Early Late
GEN (MCS)
0.076
0.226
0.195
0,161
IsoNet
0.276
0.225
0.220
0.209
IsoNet
0,086
0.237
0.244
0.191
IsoNet (MCS)
0.260
0.187
0.178
0.173
IsoNet (MCS)
0.088
0.230
0.225
0.161
LMCES
0.232
0.167
0.170
0.162
LMCCS
0.068
0.174
0.179
0.134
Early
GMI
0.269
0.184
0,181
0.178
GMN
0.101
0,200
0.216
0.136
GMN (MCS)
0.228
0.155
0.158
0.157
GEN (MCS)
0.070
0.178
0.173
0.125
XMCS
0.226
0.154
0.162
0.154
XMCS
0.071
0.168
0.163
0.131
Table 2: Effect of replacing the general- scoring layers with new layers customized to MCS on most competitive basclines, viz, GEN and IsoNet (late interaction models) and GMN, across first four datasets (MSE). Numbers in green (red) indicate the best (second best) performers for early interaction models. Numbers in blue (yellow) indicate the best (second best) performers for late interaction models. The proposed modification improves performance of all baselines. However our models outperform them, even after modifying their layers, in most cases.
baselines. (5) Neuromatch is excellent with respect KTau, where it is the second best performer in six out of twelve settings. This is due to NeuroMatch's 's order-embedding training objective, which translates well to the KTTau rank correlation scores.
Effect of replacing general purpose scoring layers with MCS customized layer. The state- of-the-art methods use a general purpose scoring functions, whereas those of our models are tailored to MCS based retrieval. In order to probe the effect of such custom MCS scoring layers, we modify the three most competitive baselines, viz., IsoNet, GEN, GMN, where we replace their scoring layers with a layer tailored for MCS. Specifically, for IsoNet, we set s(G,, Go) = Eis min( M, (R), p( Mc())) and for GEN and GMN, we use s(G,,, Go) = E, min(h, (R), (R)), Table 2 summarizes the results, which show that: (1) All three baselines enjoy a significant accuracy boost from the MCS-tailored scoring layer. (2) LMCES and LMCCS continue to outperform MCS-tailored variants of late interaction baselines. XMCS outperforms MCS-tailored GMN in a majority of cases.
Ablation study. We consider four additional variants: (i) LMCES (final layer) where the relevance score computed using only the embeddings of the 18th layer, (ii) LMCCS (no gossip), where we remove the gossip network and compute s(G,, Go)
MCES
MSRC
MM
FR
Early Late
LMCES (linal layer)
0.237
0.175
0.170
Eis min(A, Ag Mg. ((R) Ag @ M.P(B)) (iii)
C
LMCES
0.232
0.167
0.170
XMCS (all layers)
0.224
0.154
0.165
LMCCS (no NOISE FILTER) where
XMCS
0.226
0.154
0.162
MCCS
MSRC
MM
FR
we set Tr = 0 in Eq. (T0) and (iv)
LMCCS (no gossip)
0.166
0.241
0,240
XMCS (all layers) where we compute
Late
LMCCS (no NOISE FILTER)
0.068
0.194
0.206
the relevance score in Eq. (17) using embeddings from all R layers. Table
LMCCS
0.068
0,174
0.179
Early
XMCS (all Tayers)
0.069
0.181
0.171
summarizes the results where the num- bers in green (red) for early interaction models, and blue (yellow) for late interaction models, indicate the best (second best) performers. We observe: (1) The scoring function of LMCES computed using Eq. (5) improves the performance for MSRC and MM datasets. (2) The gossip component is the most critical part of LMCCS. Upon removal of this component, the MSE of LMCCS significantly increases-for for MSRC, more than doubles. (3) The noise filter unit described in Eq. (TO) is also an important component of LMCCS. Removal of this unit renders noticeable rise in MSE MM and FR datasets. (4) Given an already high modeling power of XMCS, we do not observe any clear advantage if we use embeddings (r) (r),r E [R]] from all R layers to compute the final score in Eq. (T).
XMCS
0.071
0.168
0.163
Table 3: Ablation study (MSE).
Recovering latent linear combinations of MCES and MCCS scores. In some applications. the ground truth relevance scores may be unknown or equal noisy latent function MCCS and MCES size. To simulate this scenario, here, we evaluate the performance when the ground truth relevance label is a convex combination of MCCS and MCES scores, i.e., a -MCS--iie (1 (1-a)- a). MCES- We experiment with our late (LMCES and LMCCS) and early (XMCS) interaction models, as well as the baseline late (GEN) and early(GMN) interaction models equipped with our custom MCS layer. Additionally, we implement new model COMBO, whose relevance score sGG, G.) = Σ EU (G G.) + #281,MES (G,, G.). Here, (w, 2 0 r E [2]] are trainable parameters, which attempt to balance the signals from the LMCCS and LMCES scoring functions, in order to

---

Combined
MSE (lower is better)
K KTan (higher is better)
MSRC
MM
MSRC
MM
8 0.3
8= 0.7
a= 0.3
a= 0.7
4 0.3
a= 0.7
a= 113
0.7
GEN (MCS)
0.150+0.004
0.071=0008
0.146=00005
0.165=0.012
0.064:00004
0.64:00004
0.567=0.00
0.549:00.05
Late
LMCES
0.125+0.004
L044.10.099 00006
0.143-0.006
0.17740.013
0.692+0.004
0.675++0.004
0.587+0.005
0.565+00.05
LMCCS
0.16610.001
0.55110.010
0.528-0.011
0.55411.006
COMBO
D. 0.130+0.004 0.068+00008
0.145-0.06
0.140-0.012
0.68740.004
0.665+000044
0.580=00005
0.578+0.005
(MCS
0.12410.005
0.129 0.06010:007
0.130:10009
0.69210.004
0.677:10.004
0.087
0.57410.005
XMCS
0.12110.003
0.06311.008
0.124
0.129:0.009
0.69510.004
0.671190.06
0.593
0.57240.005
Table Performance when the ground truth is the convex combination of MCES and MCCS sizes, ie., a- MCCS-size + (1 aa) MCES-size, for two values of viz. a E (0.3, 0.7). Performance measured using mean square error (MSE) (left half) and Kendall-Tau Rank Correlation (Ktau) (right half) with standard error, of our models and the baselines GEN and GMN, for two datasets. Numbers in green (red) indicate the best (second best) performers for early interaction models. Numbers in blue (yellow) indicate the best (second best) performers for late interaction models.
predict any given combination of ground truths. In Table we report the performance terms of MSE and KTauu with standard error, for two latent (hidden from the learner) values of a, viz. 0.3 and a = 0.7. We make the following observations:
1. GEN (MCS) is consistently outperformed in all cases, by one of our late interaction variants LMCES, LMCCS, or COMBO.
2. LMCCS is seen to be very susceptible to noise. It does not perform well even for = 0.7 (30% MCES noise). In fact, its performance deteriorates rapidly for MCES dataset, due to the noisy MCES signals, with the performance for 0.3 being significantly worse than 0.7.
LMCES is seen to be more robust to noise, and is the best performer six out of eight cases. 4. COMBO is overall seen to be the most well-balanced in terms of performance. Although it is the best performer in two out of eight cases, it is the second best close behind LMCES, for the remaining cases.
5. XMCS is seen to be able to adapt well to this noisy setup, and performs better than GMN (MCS)
in five out of eight cases.
encouraging to see that XMCS does not need customization based on connectedness of the MCS, but we remind the reader that late interaction methods are substantially faster and may still have utility.
Inference times. Tables D and suggest that GMN is the most competitive baseline. Here, we compare the inference time, on our entire test fold, taken by GMN against our late and
early interaction models. Table 5 shows the results. We observe: (1) XMCS is 3x faster
than GMN. This because GMN's ' cross interaction demands processing one query-corpus pair
at time to account for variable graph sizes. In contrast, our Gumbel- Sinkhorn permutation network allows us to pad the adjacency matrices for batched processing, which results in significant speedup along with accuracy improvements. (2) LM- CES is 2x slower than LMCCS (no gossip), as it has to compute the permutation matrices for all R layers. Furthermore, LMCCS and LMCCS (no gossip) require comparable inference times.
LMCCSS LMCCS (no gossip)
LMCES
XMCS
GMN
13.78
13.96
28.13
31.10
99.54
Table 5: Inference time (s), increasing from left to right.
5 Conclusion
We proposed late (LMCES, LMCCS) and early (XMCS) interaction networks for scoring corpus graphs with respect to query graphs under maximum common (connected) subgraph consideration. Our formulations depend on the relaxation of a node alignment matrix between the two graphs, and a neural 'gossip' protocol to measure the size of connected components. LMCES and LMCCS are superior with respect to both speed and accuracy among late interaction models. XMCS is comparable to the best early interaction models, while being much faster. Our work opens up interesting avenues for future research. It would be interesting to design neural MCS models which can also factor in similarity between attributes of nodes and edges. Another interesting direction is to design neural models for MCS detection across multiple graphs
Acknowledgement. Indradyumna acknowledges PMRF fellowship and Qualcomm Innovation Fellowship. Soumen Chakrabarti and Abir De acknowledge IBM AI Horizon grant. Abir De also acknowledges DST Inspire grant.
10

---

References
[1] Adrià Cereto- Mareto-Massagué, María José Ojeda, Cristina Valls, Miquel Mulero, Santiago Gareia- Vallvé, and Gerard Pujadas. Molecular fingerprint similarity search in virtual screening. Methods, 71:58-63, 03,88-6,2220 2015.
[2] Miles Ohirich, Carl Ebeling, Eka Ginting, and Lisa Sather. Subgemini: Identifying subcireuits using a fast subgraph isomorphism algorithm. In Proceedings of the 30th International Design
Automation Conference, pages 31-37, 1993.
[3] Edward K Wong. Model matching in robot vision by subgraph isomorphism. Pattern Recogni- tion, 25(3):287-303, 1992.
[4] Justin Johnson, Ranjay Krishna, Michael Stark, Li-Jia Li, David Shamma, Michael Bernstein, and Li Fei-Fei. Image retrieval using scene graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages (668-3678, 2015.
[5] Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference machine learning, pages 3835-3845, PMLR, 2019.
[6] Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. pages 384-392, 2019.
[7] Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning- based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3219-3226, 2020.
[8] Khoa D Doan, Saurav Manchanda, Suchismit Mahapatra, and Chandan K Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. pages 665-674, 2021.
[9] Yun Peng, Byron Choi, and Jianliang Xu. Graph edit distance learning via modeling optimum matchings with constraints. 2021.
[10] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprini Stt::2007.030992 2020.
[1I] Indradyumna Roy, Venkata Sai Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. AAAI, 2022.
[12] Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25-36, 2009.
[13] Richard Myers, RC Wison, and Edwin R Hancock. Bayesian graph edit distance. IEEE Transactions on Pallern Analysis and Machine Intelligence, 22(())628-66 6358,6636222 2000.
[14] Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and upplications, 13(1):11-1129 2010.
[15] Laura Bahiense, Gordana Manić, Breno Piva, and Cid C De Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160(18): 2523 2523-2541, 2012.
[16] Shahid H. Bokhari. On the mapping problem. IEEE Trans. Computers, 30(3))207 1981.
[17] John W Raymond, Eleanor J Gardiner, and Peter Willett. Rascal: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45(6)6311-444, 2002.
[18] John W Raymond, Eleanor Gardiner, and Peter Willett. Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm. Journal of chemical information and computer sciences, 42(2):305-33 2002.
[19] John W Raymond and Peter Willett. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of computer-aided molecular design. 16(7):
521-533, 2002.
[20] Hans-Christtin Ehrlich and Matthias Rarey. Maximum common subgraph isomorphism algo- rithms and their applications molecular science: a review. Wiley Interdisciplinary Reviews: Computational Molecular Science, 1(1):68-79, 2011.

---

[21] Philippe Vismara and Benoît Valery. Finding maximum common connected subgraphs using clique detection or constraint satisfaction algorithms. International Conference on Modelling. Computation and Optimization in Information Systems and Management Sciences, pages 358- 368. Springer, 2008
[22] Spencer Bryson, Heidar Davoudi, Lukasz Golab, Mehdi Kargar, Yuliya Lytvyn, Piotr Micrze- jewski, Jaroslaw Szlichta, and Morteza Zihayat. Robust keyword search in large attributed graphs. Information Retrieval Journal, pages 1-23, 2020. URL /tttpp:://oi..g///////
LC07/S10791002--00 09379
[23] Yuanyuan Zhu, Qian Zhang. Lu Qin, Lijun Chang, and Jeffrey Xu Yu. Cohesive subgraph search using keywords in large networks. IEEE Transactions on Knowledge and Data Engineering,
34:178-191, 2022. URL http: httt::://eeexpplooc
ieee. . org/ stamp/ stamp. jsp?tp=
karnumber= 9028268
[24] Péter Englert and Péter Kovács. Efficient heuristics for maximum common substructure search. Journal of chemical information and modeling, 55(5):941-955, 2015.
[25] Gabriel Hjort Blindell, Roberto Castañeda Lozano, Mats Carlsson, and Christian Schulte. Modeling universal instruction selection. In Principles and Practice of Constraint Programming 2st International Conference, CP 2015, pages 609-626, 2015.
[26] Michele Sevegnani and Muffy Calder. Bigraphs with sharing. Theoretical Computer Science, 577:43-73, 2015,
[27] Hui Jiang and Chong-Wai Wah Ngo. Image mining using inexact maximal common subgraph of multiple args. In International conference on visual information system, volume 2, page 3, 2003.
[28] Avik Hati, Subhasis Chaudhuri, and Rajbabu Velmurugan. Image co-segmentation using maximum common subgraph matching and region co ro-growing.... In Computer Vision ECCV 2016 14th European Conference, pages 736-752, 2016.
[29] Kim Shearer, Horst Bunke, and Svetha Venkatesh. Video indexing and similarity retrieval by largest common subgraph detection using decision trees. Pattern Recognition, 1475) 2001.
[30] Fikret Ercal, J Ramanujam, and P Sadayappan. Task allocation onto a hypercube by recursive mincut bipartitioning. Journal of Parallel and Distributed Computing, 10(1):35-44, 1990.
[31] Javier Marenco. A generalization of independent set inequalities for the mapping polytope. Proceedings of CLAIO, 2002.
[32] Javier Marenco. New facets of the mapping polytope. Proceedings of CLAIO, 2006.
[33] Ciaran McCreesh, Patrick Prosser, and James Trimble. A partitioning algorithm for maximum common subgraph problems. In The Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pages 712-719, 2017
[34] Ciaran McCreesh, Samba Ndojh Ndiaye, Patrick Prosser, and Christine Solnon. Clique and constraint models for maximum common (connected) subgraph problems. In International Conference Principles and Practice of Constraint Programming, pages 350-368. Springer, 2016.
[35] Ruth Hoffmann, Ciaran McCreesh, and Craig Reilly, Between subgraph isomorphism and maximum common subgraph. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
[36] Vincenzo Bonnici, Rosalba Giugno, Alfredo Pulvirenti, Dennis Shasha, and Alfredo Ferro. A subgraph isomrrphism algorithm and its application to biochemical data. BMC bioinformatics, 14(7):1-13, 2013.
[37] Edmund Duesbury, John D Holliday, and Peter Willett. Maximum common subgraph isomor- phism algorithms. MATCH Communications in Mathematical and in Computer Chemistry, 77 (2):213-255) 12123222,2141 2017.
[38] Yunsheng Bai, Derek Xu, Yizhou Sun, and Wei Wang. Glsearch: Maximum common subgraph detection via learning to search. The 38th International Conference on Machine Learning, ICML 2021, pages 588-598, 2021.
12

---

[39] Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. Revised note on learning quadratic assignment with graph neural networks. In 2018 IEEE Data Science Workshop (DSW). pages 1-5. IEFE, 2018. 8.
[40] Andrei Zanfir and Cristian Sminchisescu. Deep learning of graph matching- In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2684-2693, 2018.
[41] Runzhong Wang. Junchi Yan, and Xiaokang Yang. Learning combinatorial embedding networks for deep graph matching. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 3056-3065, 2019.
[42] Hao-Ru Tan, Chuang Wang, Si-Tong Wu, Tie-Qiang Wang, Yu-Yao Zhang, and Cheng-Lin Lin Liu. Proxy graph matching with proximal matching networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 9808-9815, 2021.
[43] Kaixuan Zhao, Shikui Tu, and Lei Xu. la-gm: A deep bidirectional learning method for graph matching. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 3474-3482, 2021.
[44] Matthias Fey, Jan E Lenssen, Christopher Morris, Jonathan Masci, and Nils M Kriege. Deep graph matching consensus. arXiv preprini urXiv:2001.0962 2020.
[45] Tianshu Yu, Runzhong Wang, Junchi Yan, and Baoxin Li. Learning deep graph matching with chamnel-independent embedding and hungarian attention. In International conference on learning representations. 2019.
[46] Tianshu Yu, Runzhong Wang. Junehi Yan, and Baoxin Li. Deep latent graph matching. In International Conference on Machine Learning, pages 12187-12197. PMLR, 2021.
[47] Linfeng Liu, Michael C Hughes, Soha Hassoun, and Li-Ping Liu. Stochastic iterative graph matching. arXiv preprint arXiv:2 02200000002222.00 2021.
[48] Jingwei Qu, Haibin Ling, Chenrui Zhang, Xiaoqing Lyu, and Zhi Tang. Adaptive edge attention for graph matching with outliers. 2021.
[49] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning, pages 1263-1272. PMLR, 2017.
[50] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31 International Conference on Neural Information Processing Systems, pages 1035-1035, 2017.
[51] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
[52] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
[53] Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In KDD,, pages 701-710, 2014.
[54] Aditya Grover and Jure Leskovec. SIGKDD, 2016
node2vec: Scalable feature learning for networks. In
[55] Tathagat Verma, Abir De, Yateesh Agrawal, Vishwa Vinay, and Soumen Chakrabarti. Varscene:
A deep generative model for realistic scene graph synthesis. In International Conference on Machine Learning, pages 22168-22183. PMLR, 2022.
[56] Bidisha Samanta, Abir De, Gourhari Jana, Vicenę Gómez, Pratim Kumar Chattaraj, Niloy Ganguly, and Manuel Gomez Hommez-Rodriguez Nevae: A deep generative model for molecular graphs. Journal of machine learning research. 2020 Apr: 21 (114): 1-33, 2020.
[57] Dexiong Chen, Leslie O' Bray, and Karsten Borgwardt. Structure-awart transformer for graph representation learning. ICML., 2022.
[58] Marco Cuturi. Sinkhorn distances: neural information processing systems, 26:2292-2300, 2013.
Lightspeed computation of optimal transport. Advances in
[59] Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-348, 1967.
13

---

[60] Marin Vlastelica, Anselm Paulus, Vit Musil, Georg Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. arXiv preprint veXiv:1912.021177 2019.
[61] Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vit Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers. In European Conference on Computer Vision, pages 407-424. Springer, 2020.
[62] Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean- SannPPhllippe Vert, and Francis Bach. Learning with differentiable pertubed optimizers. Advances in neural information processing systems, 33:9508 991889999,,-1111 2020.
[63] Nikolaos Karalias and Andreas Loukas. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. Advances Neural Information Processing Systems, 2020.
[64] James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:2103. 16378, 2021.
[65] Soumajit Pramanik, Jesujoba Oluwadara Alabi, Rishiraj Saha Roy, and Gerhard Weikum. Uniqorn: Unified question answering over rdf knowledge graphs and natural language text. ArXiv, abs/21 08.00814, 2021. URL htt.t/ttts///aattte http://wwwwwoppp////////ee/
08614.
[66] Thomas H. Cormen, Charles E. Leiserson, Ronald I.. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. 2009.
[67] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snock. Learning latent per- mutations with gumbel-sinkhone networks. arXiv preprint arXiv:1802.08665 2018. URL
https: //apxi//axvvvio wttp
08665. pdf]
[68] Yanli Liu, Chu-Min Li, Hua Jiang, and Kun He. learning based branch and bound for maximum common subgraph related problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2392-2399, 2020.
[69] Ramesh Hariharan, Anand Janakiraman, Ramaswamy Nilakantan, Bhupender Singh, Sajith Varghese, Gregory Landrum, and Ansgar Schuffenhauer. Multimes: a fast algorithm for the maximum common substructure problem multiple molecules. Journal of chemical information and modeling, 51(():788-80) 806, 2011.
[70] Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprini arXiv:
2015.
[71] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion
Neumann. Tudataset: A collection of benchmark datasets for learning with graphs In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. www.graaphleerning..t
[72] Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprini urXiv:2007.03000 2020.
[73] Aric Hagberg, Pieter Swart, and Daniel Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Lab. (LANL), Los Alamos, NM (United States), 2008
[74]
Maurice G Kendall, new measure of rank correlation. Biometrika, 30(1/2):81-9 1938.
14

---

Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Appendix A
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms
them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yess] Code, data, and instructioncan be accessed
htttp::/tinyull.co//meec -mess
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Appendix and Supplemental material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix and Supplemental material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [Yes]
See Appendix ans Supplemental material.
(d) Did you discuss whether and how consent obtained from people whose data you'ne
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A] No such information present in the data used in this paper.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "ioInBa0uxFW", "reviewer": "Reviewer_pKLh", "summary": "This paper studies the neural graph retrieval problem. Specifically, it focuses on two similarilty scores, MCCS and MCES. Since exact computation is intractable, thus this paper designs neural functions to approximate MCES and MCCS. This paper proposes both early and late fusion of neural graph retriever, and experiments overs seven datasets show that the proposed approaches outperform baselines on both accuracy and speed. ", "questions": "1. Does different GNN architecture affect the results? \n2. Maybe add an experiment on hybrid interaction (start with late interaction, then interaction), and experiment on both accuracy and time. (see details in strengths/weaknesses).\n3. Maybe add a few related works on neural information retrieval (e.g., dense retrieval)", "limitations": "Not addressed, but I do not think of any potential negative social impact. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n\n1. Although several research work has focused on neural information retrieval, few works on graph neural retrieval, an important but relatively underexplored problem. This paper fills in the gap. \n2. This paper proposed a simple neural graph retrieval method and works well on both accuracy and efficiency (significantly outperforms baselines) \n3. The paper is well-written, it's enjoyable reading it.\n\nWeakness (more like suggestions, not really a weak point)\n\nSince this paper proposes both early and late interaction approaches, a natural idea is to combine both approaches (e.g., hybrid approach). \nA straightforward approach is to start with late interaction to find some relevant graphs, then use early interaction to re-rank these graphs. The expectation is to find the optimal trade-off between accuracy and efficiency. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RDK1n2uHl2", "reviewer": "Reviewer_UMf5", "summary": "The paper proposes new neural network architectures for the task of graph retrieval (computing a score between a query graph and a corpus graph) tailored for the Maximum Common Subgraph (MCS) metrics. Two late interaction models and an early interaction model are proposed with trade-off in efficiency and accuracy. Experiments on seven real-world datasets show the superiority of the proposed models.", "questions": "Please see above for questions.", "limitations": "The authors do not explicitly mention societal impact in details.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The proposed method is relatively novel, albeit heavily relying on the Gumbel-Sinkhorn (GS) network. \n2. Two variants in MCS definition are discussed (MCES and MCCS), which reflect the different needs of real-world applications.\n3. The paper is well-written with enough details as well as code provided for reproducing the experimental results.\n\nWeaknesses:\n1. It is unclear how scalable the proposed methods are. First of all, the theoretical time and space complexity are not explicitly discussed, and thus the speedup compared with GMN is not explained from a theoretical point of well. Second, the statistics of the number of nodes and edges of the graphs in the seven datasets are not shown. Instead, the authors give a relatively vague description of how the graph pairs are generated in Section D, “Subsequently, we augment the seed query graph G′q , with randomly connected nodes and edges, which gives us the final query graph Gq for MCS computation.” How many nodes and edges are randomly added to the seed? What is the final size of the graph? This concern is of particular relevance given that exact MCS is NP-hard to compute, but the authors can generate the ground-truth MCS values “using the combinatorial formulations for exact MCCS and MCES,” raising the concern that whether the graph sizes are quite small so that even exact MCS computation is affordable. Figures 2 and 3 also show quite small graph pairs with ~20 nodes. Why would people use such approximate methods for MCS scores if the input graphs are small and the exact solvers can already handle them reasonably well? Without large graph experiments, the exact solver may be used as a baseline too, which is missing in the current experiments.\n2. A minor concern is the applicability of the proposed models, since the models are specifically designed for MCS metrics, more specifically, MCCS and MCES. I agree that MCS metrics are already important and worth specific models designed for them, but it would be interesting to discuss the potential issues if the proposed methods are used for other metrics, e.g. GED, or domain-specific similarity scores. This would make the contribution and the scope of usage clearer.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5yN5v4RbMI8", "reviewer": "Reviewer_Q3Ju", "summary": "In this work, the authors propose LMCES and LMCCS, which are late interaction neural architectures for MCES (counting the number of common edges) and MCCS (the maximum common connected subgraph) based graph retrieval respectively. Additionally the authors propose XMCS (cross-MCS) which is an early interaction model that works well for both MCES and MCCS based graph retrieval. The authors demonstrate the efficacy of their approach via empirical results.", "questions": "q1) why did you not include results related to to the training/inference times for the different baseline models along with the proposed approaches ? ", "limitations": "The authors share multiple limitations of their work.", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Here are the main strengths of the current work :\n1) The authors focus on graph similarity measurement which is a very important problem in the graph ML community.\n2) The authors propose both early and late interaction models for determining the MCES and MCCS, via introducing a relaxation to the node alignment matrix between query and corpus graphs.\n3) The authors demonstrate the efficacy of their approach via exhaustive empirical study using seven diverse datasets and six state-of-the-art late interaction baseline models.\n\nHere are the main weaknesses of the current work :\n1) The novelty factor of the proposed approaches is somewhat limited. \n2) The authors should have included more results, including those related to the training/inference times for the different baseline models. Currently it is hard to compare whether the gain in performance is matched by the potential training/inference latency issues.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept