Charting the Design Space of Neural Graph Representations for Subgraph Matching
Authors: Vaibhav Raj
Indradyumna Roy
Ashwin Ramachandran
Soumen Chakrabarti
Abir De
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Retrieval
Graph Neural Networks
Subgraph Matching
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a unified framework for graph matching networks and experiment with various alternatives for each design axis to obtain state-of-the-art results on the subgraph isomorphism task.

Abstract: Subgraph matching is vital in knowledge graph (KG) question answering, molecule design, scene graph, code and circuit search, etc.
Neural methods have shown promising results for subgraph matching.
Our study of recent systems suggests refactoring them into a unified design space for graph matching networks.
Existing methods occupy only a few isolated patches in this space, which remains largely uncharted.
We undertake the first comprehensive exploration of this space, featuring such axes as attention-based vs. soft permutation-based interaction between query and corpus graphs, aligning nodes vs. edges, and the form of the final scoring network that integrates neural representations of the graphs.
Our extensive experiments reveal that judicious and hitherto-unexplored combinations of choices in this space lead to large performance benefits.
Beyond better performance, our study uncovers valuable insights and establishes general design principles for neural graph representation and interaction, which may be of wider interest.

Published as a conference paper at ICLR 2025
CHARTING THE DESIGN SPACE OF NEURAL GRAPH REPRESENTATIONS FOR SUBGRAPH MATCHING
Vaibhay Raj', Indradyumna Roy", Ashwin Ramachandran, Soumen Chakrabarti, Abir De
Department of Computer Science and Engineering. IIT Bombay (vaibhavraj,, indraroy15, soumen, abir)@css..itb.acc ashwinramg @ucsd. edu
ABSTRACT
Subgraph matching is vital in knowledge graph (KG) question answering, molecule design, scene graph, code and circuit search, etc. Neural methods have shown promising results for subgraph matching. Our study of recent systems suggests refactoring them into a unified design space for graph matching networks. Existing methods occupy only few isolated patches in this space, which remains largely un- charted. We undertake the first comprehensive exploration of this space, featuring such axes attention- basodd vs. soft permutation brasde interaction between query and corpus graphs, aligning nodes vs. edges, and the form of the final scoring net- work that integrates neural representations of the graphs. Our extensive experiments reveal that judicious and hitherto-unexploeed combinations of choices in this space lead large performance benefits. Beyond better performance, our study uncovers valuable insights and establishes general design principles for neural graph repre- sentation and interaction, which may be of wider interest. Our code and datasets are publicly available at https::/github... http://hhbbbbb.ooo///uu//omnnnne subm-uuueeeeeee floo-ddeiggn-saee
INTRODUCTION
Subgraph matching-basee retrieval is essential in tasks like querying knowledge graphs (Liang et al., 2024), biological graphs (Tian et al., 2007), chemical substructure search (Willett et al., 1998), etc. In all these applications, given a query graph, the goal is to score-ane and thereby
graphs by how close they come to containing the query graph as a subgraph. Since exact subgraph matching is NP-Complete (Conte al., 2004), there has been a growing focus on tractable neural methods, with the added benefit of learning the relevance scoring function in a differentiable framework.
Prior work and complexity of their design choices Neural architectures for estimating distance between graphs have been extensively studied in recent years (Bai et al., 2019; 2020; Doan al., 2021; Li et al., 2019; Lou et al., 2020; Roy et al., 2022; Qin et al., 2021; Zhuo and Tan, 2022; Ranjan et al., 2022). These methods use graph neural networks (GNNs) to embed each graph, and then compute distance between query and corpus graphs' representations. Among them, IsoNet (Roy et al., 2022), IsoNet++ (Ramachandran et al., 2025) and NeuroMatch (Lou al., 2020) focus specifically subgraph matching based graph retrieval, by introducing an asymmetric order embeddings (Vendrov et al., 2015) to characterize subgraph containment. In addition, IsoNet has two key design features: it trains an injective alignment map between query and corpus graphs; and uses this map to compute relevance distance based on sel alignment, in contrast to distance between whole graph representations. The design space of such retrieval models is cluttered with various choices whose subtle interactions with each other are scarcely studied in prior work. We present two examples.
(1) GMN (Li et al., 2019) uses early interaction GNN, integrating cross-graph signals during message passing. In contrast, IsoNet and NeuroMatch are late interaction models, which do not per- form any cross-graph interaction while computing their representations. Challenging the widely held expectation that early interaction is more powerful, IsoNet's 's late interaction approach outperforms GMN. This raises important questions: Is IsoNet's advantage attributable to its use of set align- ment vs. GMN's whole-graphe graph representations, or its injective alignment over GMN's non-injective cross-attention? Can GMN improve with similar set alignment or injective mapping?
(2) Although IsoNet and NeuroMatch both use asymmetric hinge distances, NeuroMatch relies on whole-graph representations, while IsoNet uses set alignment at the node or edge level. Other
Vaibhay and Indradyumna contributed equally. Ashwin Ramachandran did this work while at IIT Bombay.

---

Published as a conference paper at ICLR 2025
works (Bai al., 2019; Zhuo and Tan, 2022; Qin et al., 2021) use neural distance layers that do not enforce either symmetry or asymmetry. This distinction raises an important question: IsoNet's 's set alignment-bris based distance more effective than other neural or non-neural methods in capturing the nuances of subgraph matching?
1.1 OUR CONTRIBUTIONS
Recent system presents aggregate performance comparisons against prior systems. However, such aggregate views miss the opportunity to factor out key design choices involving the representation of and interaction between graph representations, and then systematically explore subtle interplay between these design choices.
Set alignment vs. aggregated embedding In knowledge graph (KG) align- ment, Euclidean distance or cosine similarity between single-vector graph representations (often via aggregating node embeddings) is often less effective than earth mover distance (EMD) between sets of neighbor embeddings (Tang et al., 2020). IsoNet adopts a similar set alignment approach to compare node edge embeddings across query and corpus graphs. In contrast, GMN collapses node embeddings into a single graph-level representation and uses Euclidean distance between these aggregates. Neural scoring layers (MIP neural tensor network), where aggregated embeddings fed into a trainable layer, also remain popular (Qin et al., 2021; Bai et al., 2019).
Relevance distance:
Interaction stage: Early vs. late Interaction across graphs may be arranged early or late in the comparison network. Early interaction models like GMN (Li al., 2019) and ERIC (Zhuo and Tan, 2022) use information from the query graph to compute the representation of the corpus graph, and vice-versa, which renders their embeddings strongly dependent on each other. In contrast, a late interaction model like IsoNet (Roy et al., 2022) computes the representation of one graph independent of any other graph, and combine these embeddings at the very last stage during score computation. Early interaction models are expected to be able to compare query and corpus graph neighborhoods directly, while late interaction models have the potential for fast approximate nearest neighbor (ANN) retrieval (Simhadri et al., 2023).
Interaction structure: Non-injective vs. injective GMN models cross-graph interactions using attention which induces a non-injective -uppiig nodes in the corpus graph may map to one node in the query graph (or vice versa). In contrast, IsoNet uses soft permutation (doubly stochastic) matrix to approximate injective alignments. We investigate whether replacing attention- based interaction with a doubly stochastic alignment (even in systems other than IsoNet) leads to improved performance.
Interaction non-linearity: Trainable vs. fixed GMN and IsoNet take divergent approaches to modeling graph-pair interactions. GMN relies dot-product similarity, while IsoNet applies feedforward layers to both query and corpus embeddings and feed them into an interaction module. The relative merits of these approaches are not fully understood. Additionally, we introduce a natural alternative: incorporating an asymmetric ordering between graph components into the cost matrix.
Interaction granularity: Nodes vs. edges IsoNet introduces the idea of aligning edges instead of nodes, based on the intuition that larger units might provide more reliable signal for detecting isomorphism. This idea parallels the principle that joint distributions are better approximated when accounting for larger cliques (Koller and Friedman, 2009). It remains unclear how well edge-based alignment can integrate with different cross- gaass interaction methods and scoring layers, warranting further investigation.
Key takeaways and design tips Our systematic navigation of the design space resolves hitherto- unexplained observations and provides reliable guidelines for future methods. (1) We conclusively ex- plain (late-interaction) IsoNet's earlier-observed superiority over (early-interaction) GMN. If GMN's early interaction is supplemented with any of set alignment, injective structure, hinge nonlinearity, or edge-based interaction, it can readily outperform IsoNet. (2) These five design principles are vital, and their combination unveils a novel graph retrieval model that surpasses all existing methods. (3) Shifting from late to early interaction may increase computational cost, but compensates for the limitations of relevance distance defined using aggregated dingle-vector embeddings.
2 PRELIMINARIES
Notation We denote the set of query graphs Q = {G,) } and the set of corpus graphs C' (G where G3 (V,, F.y) and G. = (Ve, F..) denote query and corpus graph. Having padded with
2

---

Published as a conference paper at ICLR 2025
Signal from Go
H or M
Gr- GNN
W 7
H M
G GNN
0
dist()
Relevance distance
H or M
dial
Relevance distance
Ge GNN
w- n
M
Ge GNN
Signal from Gy
Early Interaction
Late Interaction
Neural
Non-injective
Set Alignment
Set Alignment
Neural
Dot-Product
Hinge
Agg Hinge
Dot-Product
Non-injective
Non lionaiine
Hinge
Structure w
Injective
Agg NTN
Aug-MLP
Passing
lnteraction)
Agg MLLP
Agp-NTN
Monilmnarity N
Hinge
Structure W
Injective
Relevance
Relevance Distance
Message Passing
(Early Interaction)
Cross graph interactions occur during embedding computation layers, with both Green signals from Ge and blue signals from Gg feeding into both graphs. Late interaction: No cross-graph signal transfer occurs. Green signals from Ge and blue signals from Gg are restricted
Figure 1: Early interaction:
to their respective graphs. Final layer embeddings. H (g) used to compute relevance distance. Axes of the design space: Subgraph matching models work in two stages: message passing and relevance distance. Relevance distance dist(.;.) can be set alignment, aggregated-hinge, aggregated-MLP or aggregated-NTNN w represents the interaction structure (injective vs. non-injective), and 1) defines the interaction non-linearity (Neural, dot product, or hinge). For early interaction (bottom left panel), message passing involves obtaining embeddings via cross- cross-graph alignment, which is used for dist(-,)) .) if set alignment is used for relevance distance (shown by thick arrow). In late interaction (bottom right panel), and w are absent during message set alignment approximate dist.Gyy: Ge)-
(g) K H (node) or M K K (edge), are
passing, but become active if
suitable number of nodes to obtain the same number of nodes across G, and Ges we obtain A, and A. as the 0/1 adjacency matrices of size N x N. We write the neighbors of as nbr(u). l denotes both node and edge alignment matrices, which are used during cross cross-graph graph interaction or relevance computation using set alignment. a denotes an attention matrix, where a a(u, u'] is the attention weight from u to u', with En a a(u, w'] = 1. Similarly, we use b for an edge attention
matrix with Ee ble, e'] 1. Given the nodes E Vg and u' Ve, we write h (4) (u) Rdimm and (e)
h (u') E RRdium to denote their embeddings, obtained after k-layer message passing using GNN.
The last layer is numbered K. We collect these embeddings into matrices H())) H!(
E R Nxdims,
H+ max {0, J is the ReLU or hinge function, [N] denotes the set {1, N). and || Il denotes
Σn, [i,]]. PN and By indicate the set of N x N permutation matrices and doubly stochastic matrices respectively. We generally use 'permutation' and 'alignment" interchangeably.
Subgraph search and (asymmetric) relevance score In the context of subgraph matching, we define the relevance label rel otherwise. Given G we define Cg = {G. rel(G G.) ===1 =1} as the set of relevant corpus graphs and Cax = C Cgt as the irrelevant corpus subset. (Gg G.) denotes a relevance distance, which is inversely related to rel(G, q, 9c). In general, GG C GG + G. C Gay so relevance labels are inherently asymmetric: gG,, Ge) * rel Gg). This necessitates an asymmetric distance dist(;,) :) with dist Ge) a dist dist(Ge, Gg)) in most cases (Roy et al., 2022; Ranjan et al., 2022; Lou et al., 2he goal is to rank Cgs/ above Cgx, given query Gg.
1, when Gg S G. (Gg, is subgraph of G.) and
3 DESIGN SPACE OF GRAPH REPRESENTATIONS FOR SUBGRAPH MATCHING
From existing methods (Bai et al., 2019; Zhuo and Tan, 2022; Qin et al., 2021; Zhang et al., 2021; Roy et al., 2022: Li et al., 2019; Ranjan et al., 2022), we catalogue the salient design axes: (1) relevance distance, (2) interaction stage (late vs. early), (3) interaction structure (4) interaction non-linearity and (5) interaction granularity (node vs. edge). We first present a unified view of these design axes. divide our analysis by interaction granularity, first
Then, to control the complexity of exposition, analyzing the various options for node interactions, followed by a discussion for edge interactions. Figure illustrates framework.
3

---

Published as a conference paper at ICLR 2025
3.1 UNIFIED FRAMEWORK (INTERACTION GRANULARITY: NODE)
Given a query graph Gg and a corpus graph Go. existing work computes the relevance distance in two steps. The first step applies GNN to perform iterative message passing across edges for K propagation layers. At the end of each layer, we obtain the embeddings H()) and H& with approximate
1 S k S K, for Gg and Go. respectively. The second step compares H/ and H le) K dist H H = dist(Gg; Gc). We now present generalized view of these two steps.
(9)
Generalized message passing Given a task on single graph, e.g. link prediction or node classifi- cation, GNN updates the node embeddings by collecting messages only from its neighbors, within that graph. If the task involves two graphs, we can adopt either late interaction after all K layers of the GNN are computed, or early interaction between corresponding layers of the GNNs. E.g., Li et al. (2019) modified the GNN on Gg. so that it can incorporate signals from Ge and vice-versa. To capture this interaction, we compute two node alignment matrices 22% E R x and 12 V
after each propagation layer l E [O,.., K - 1), based on the embeddings H and (c) Each of these matrices computed in two layers: in the first layer, we apply non-linear map 1) to compute the similarity between H (()) and H(()) and then use another function w to obtain the alignment scores across different node pairs.
(1) As we shall discuss later, 17 and w represent the interaction structure and interaction non-linearity, which are described in Items (3) and (4) in the design space. Here, 2 [u, u']. 2. E [o, 1]. Both of them estimate the alignment score that u' V. match with E Vy. However, they are not necessarily cqual except for certain design choices. Next, we use 22 to update the query embeddings h (u) - h++ (u). To make this update for E Vg, we multiply 12% H(()) to extract signals from the other graph Gei aggregate messages from the neighbors nbr(u) in its own graph Gg-
2 = w (H ))),
H)
(4)
obtained through a neural network msggg and combine these signals as follows:
(w) updateg
(4) h
(u); DEnbr(a))
Σ
msgo (h (w), ME (v));
Σ MEE(N]
2 u w'th (u')
(2)
Neighbors own graph
Nodes in other graph
Likewise, we update h (u') h k++ (u'). For h: = O, the embeddings (u)( are computed using node features. Having updated the embedding at layer k + 1, we assemble them into the the matrices H and H (o) and then use them to compute fresh alignment matrices 52%
k++1
Computation of the relevance distance dist(:;-) As discussed in Section 2, the relevance distance asymmetric, because the relevance label rel is asymmetric, owing to the asymmetric nature of the subgraph matching task (Roy et al., 2022; Ranjan et al., 2022; Lou et al., 2020). We briefly justify such asymmetric constructions. If G, S Go. then there exist some row-column permutation of A which will cover all ones in Ag. Le., there will exist permutation matrix P of size N x N such that, whenever Ay(u, u']= we have (P) [u, u'] also present in E., leading to G2 C G.. This implies that, for subgraph isomorphism, we will have Ag < PA.P TT, elementwise. This suggests the natural definition
1, which indicates any edge (u, u/) Eg is
dist G.) = minpPew ||[A, PA. 11..
Existing works (Roy et al., 2022; Ranjan et al., 2022; Lou et al., 2020) use a surrogate of clist (Gg. Go). by applying hinge distance across elements of the set of node embeddings H( and H or the whole graph representations g and g g()). Note that rel(Ggg G.) = 1 (i.e., G, Ge). we have di Go) 0. The above distance also draws parallel from the problem of graph isomorphism, where we have symmetric distance minpepw ||[A, PA.PT]
"1,,, instead of asymmetric dis- 1|],,,,
tance (3). Because of the PA.PT term, Eq. (3) aims to solve a quadratic assignment problem (QAP) which is HarH (Conte et al., 2004). Hence, existing works approximate dist GG. G.) using an (9) and ((() By overloading
asymmetric distance or trainable distance on the node embeddings H(()
the notation, we write such a distance as dist (g) of the design space, beginning with the relevance distance.
K ( In the following, we describe each axis
4

---

Published as a conference paper at ICLR 2025
3.2 RELEVANCE DISTANCE: SET ALIGNMENT VS. AGGREGATED- VS. AGGREGATED- MMLP vs. AGGREGATED-NTN
The relevance distance dist H K K can take four forms, based on (1) Set alignment, (2) Aggre-
gated-hinge: Comparing aggregated graph representations g g g( derived from H& . H and subsequently using hinge distance, (3) Aggregated-MLPP multi-layer perceptron (MLP) to compare g( and g g( and (4) Ng a neural tensor network (NTN) comparing g()) and g()
Set alignment Here, we relax the quadratic assignment problem (QAP) (3) to linear assignment problem (LAP), where we first represent the graphs G2 and G. as sety of node embeddings H H and H( and then quantify the alignment between these sets using the earth mover distance (EMD); (q) ( dist H K K = minpePx || (g) K - PH K 1
K
(4) Note that the EMD is induced by hinge distance rather than symmetric Lp distances; therefore, is not a metric, unlike symmetric EMD. In the context of graph retrieval, solving such an LAP for large number of graph pairs is daunting, even though for one graph pair, LAP is more tractable than QAP. To get past the blocker of this explicit optimization for each graph pair, we replace P with the alignment matrix k2% which end-to-end trained under the distant supervision of rel(G,,: Go) (Section 2). Therefore, we compute dist (H (0), (9) as:
dist (H H [| 2 14l1,,1
(5) The above distance provides a natural alternative to Eq. (4). Here, we fix the ordering of the query nodes and align the corpus nodes using 2 Similarly, one can also fix the order of the corpus nodes and apply Si on H They do not provide significant difference in retrieval accuracy.
Aggregated-hings Here, instead of representing graph as variable-sized set of node embeddings, we represent whole graphs Gg and Ge as single fixed-length vectors g()) E Ridim and g E Rdim, using neural network comb,, Then, in Eq. (3), we replace A, and P PA.PP PT with the corresponding whole graph representations (1)) and g(()) and compute dist H (0) H
())) follows:
dist H (0)) = (l - - where g(s) combo H g. combo H
(6)
K
Aggregated-MLP Here we feed gla) and g(e) defined in Eq. (6) into a trainable neural network "ee to compute the distance, where "i is an MLP, which is free to implement an asymmetric function:
dist H(() HH())) re(g (1) (())())))))) (c).
ANNN SimGNN (Bai et al., 2019) proposed the usage of Neural Tensor Net- works (Socher et al., 2013) to combine graph-level embeddings, as shown in Eq. (8) below. Here, I, represents the latent dimension of the score, Will Rdim, x dim, xL is a weight tensor, VNTN E Lx2dim, is a weight matrix applied on the concatenation of the two embedding sets, bNTN E R- is bias vector, and aa is an MLP that outputs the scalar distance.
(c)) dist(H (2) K K 70 (g(n) GolTwi::L wiL-- (() + VNTN[g("); [0) bNTN)
(8)
Time complexity In set alignment (4), computation of & (() takes O(N2) time, where N is the number of nodes and (e) E IR x For all other choices, the complexity is O(N).
H
Variants in existing works Among existing works, GotSim (Doan et al., 2021) uses set alignment based distance of the form in Eq. (4) and optimizes for P using the Hungarian algorithm (Edmonds and Karp. 1972). In contrast, IsoNet (Roy et al., 2022) uses set alignment distance of the form in Eq. (5). GMN (Li et al., 2019). GREED (Ranjan et al.. 2022), Neuromatch (Lou et al., 2020) use aggregated embedding based distance. SimGNN (Bai et al., 2019), ERIC (Zhuo and Tan, 2022), EGSC (Qin et al., 2021), and GraphSim (Bai et al., 2020) use neural distances. SimGNN (Bai et al., 2019) and ERIC (Zhuo and Tan, 2022) leverage distances in the form of Eq. (8), while EGSC (Qin et al., 2021) and GraphSim (Bai et al., 2020) use Eq. (7)
Takeaways and design tips Compressing the entire graph into a low dimensional vector can result in information loss. Therefore, comparing the node embeddings in the set-level granularity results in better performance than their single vector representations. Similar experience has been reported from other domains. In knowledge graph alignment, encoding the neighborhood of an entity as a set, and then aligning two such sets, has been found better than comparing compressed single- vector representations of each entity (Tang al., 2020). In textual entailment (Lai and Hockenmaier,
5

---

Published as a conference paper at ICLR 2025
2017; Chen et al., 2020; Bevan et al., 2023), allowing cross-interaction between all tokens of the two sentences is generally better than compressing each sentence to a single vector and comparing them. Our work reconfirms this intuition also for subgraph retrieval.
3.3 INTERACTION STAGE: EARLY VS. LATE
Early interaction If fig used during computation of the node embedding in Eq. (2) is non-zero, then H and H ()) become dependent each other through the third term in the RHS of (2). This leads to early interaction GNN architecture.
Late interaction In late interaction, no cross-graph interaction occurs during the message- paassigg steps, as shown in Figure 1. Such models are obtained by setting 22 0 in Eq. (2) (and similarly in h 1.))) ). Here, the embedding update step becomes the same as a standard GNN. E.g., for Gg. we (i) have k (w) = update, (h (u); Evente(w)) msg, (h& (u), h (u))), separating the computation of query and corpus graph embeddings. However, even if $2% is not used in the message passing interaction, it can still be used during relevance distance computation based on set alignment (5).
Time complexity For early interaction, we have the following computation costs: (1) Computation of h takes O(N) time. (2) For each layer & E [K - 1], computation of 52 takes O(N²) time. (3) For each layer k; message passing in embedding update step takes O(EE,) and O(EEa) time for Gg and Ge computation of EVEN S2% [u, u"| fgg (w') takes ((N2) time. Hence, the overall time complexity is O(K For late interaction model, the overall complexity is O(K Egg + K K(E))).
Variants in existing works GMN (Li et al., 2019) and H2MN (Zhang al., 2021) use early interaction models, whereas SimGNN (Bai et al., 2019), IsoNet (Roy et al., 2022), ERIC (Zhuo and Tan, 2022), GREED (Ranjan et al., 2022), GOTSim (Doan et al., 2021), EGSC (Qin et al., 2021) and Neuromatch (Lou et al., 2020) use late interaction models.
Takeaways and design tips Although late interaction potentially enables fast nearest neighbor search, early interaction generally known to superior in text retrieval (Khattah and Zaharia, 2020, Figure 1). The comparison between IsoNet (Roy et al., 2022) vs GMN (Li et al., 2019) apparently contradicts this general trend. Therefore, it is important to resolve this issue using carefully controlled experiments.
3.4 INTERACTION STRUCTURE: NON-INJECTIVE VS. INJECTIVE
The interaction structure computes the alignment scores 52 in Eq. (1), by normalizing across different dimensions of n (H(() ((()). Depending on the nature of normalization, we obtain approximate non-injective or injective mappings for node node alignment.
Non-injective Here, the function w performs softmax-style normalization across different columns for each row, which makes the entries of 52% similar to "attention weights" or "probabilty parameters in a multinomial distribution". Given a temperature т, we write the values of the alignment matrices: (u) (a/))r
en (u)) (a'))/
22 [u, u']
2 (u',
EUTELN (n(h (1),
EUTEIN en A
The above form of 52 enables a unique mapping from Gy to Ge but not vice-versa. Le., the mapping, even if 0-1, could be many-to-one We note that Σn. S22."lu, u'] = 1. Hence, for any fixed node u E Gg, the matrix Ω distributes a unit score across all nodes u' E G.. If 0, u will be matched to only one node u'. However, such allocation is performed independently for different nodes in the query graph. Therefore, given u' E Go. both 12 u'I and Ω29 u'] can be high for u # U E Gg. Therefore, as r + O, we have two different matched nodes in Gy. resulting in an approximate non-injective interaction structure.
Injective Injectivity seeks to mitigate the above limitation. Specifically, in addition to Gg + Ga- an approximate unique mapping is also enforced from G, + G₁- L.e., for each node u' é G., as + 0, there will exist exactly one u for which 0 [u, u'] 1 and vice-versa. These constraints naturally ensure that, as T + 0, 52% approaches a permutation matrix. Similar to the relaxation of argmax operation using softmax function, the permutation matrix is approximated with doubly stochastic matrix using Sinkhorn iterations (Sinkhorn and Knopp, 1967; Cuturi, 2013; Mena et al., 2018). Instead of only row normalization, it excutes iterative row-column normalization for T steps,

---

Published as a conference paper at ICLR 2025
starting with initialization: Zo e (
at 1= Ze Z/ u']
Zit1 [u, u'] Z (M, u'] EVENN] u'] where Z u¹] EVE(N] Ze(u, w²) for all (u,4²) (10)
As T' grows, ZT approaches doubly stochastic matrix, satisfying EWENNN] Zr(u, and EnE(N] Zr(u, u'] = 1. After I' iterations, we set $ = ZT and $ = Z7-
Time complexity Computation of 2% and 2 requires O(N2) time for a non-injective mapping, where N is the number of nodes. For injective mapping, T iterations of row-column normalization raise the complexity to O
Variants in existing work GMN (Li et al., 2019) and H2MN (Zhang et al., 2021) use non-injective mapping during early interaction, whereas GotSim (Doan et al., 2021) uses injective mapping. However, as mentioned earlier, GotSim (Doan et al., 2021) optimizes the alignment using the Hungarian method. IsoNet (Roy et al., 2022) uses trainable Sinkhorn iterations (10).
Takeaways and design tips The combinatorial definition of graph matching includes finding an injective mapping between pairs of nodes from the two graphs. The mapping is also an interpretable artifact. Attention from one node to all nodes in the other graph, even if maintained from each graph separately, cannot achieve consistent 1-1 mapping. Our experiments suggest that injective mapping (or its continuous relaxation - doubly stochastic matrices) performs better.
3.5 INTERACTION NON-LINEARITY: NEURAL VS. DOT PRODUCT VS. HINGE
Alignment computation involves three possible choices of nf:
Neural: ((H) (q) H k. [u, w'] LRL (h (4) (w)) [ (h (c)
(c)
(w')), where LRLg is a Linear-ReLUs
Linear network with parameter
Dot product: Here, 17( (H)()) H [u, u²) (h (T))TTE (w').
Hinge: Here, (H)
(9) ( [u, w| --||-1 1|
(4) (u)
h (0) (w))
Time complexity All methods require (N2) complexity, since we compute one scalar for each node pair and computations along the embedding dimension are considered ((1).
Variants in existing works GMN (Li al.,, 2019). H2MN (Zhang al., 2021) perform dot-product operations, and IsoNet (Roy et al., 2022) and GOTSim (Doan et al., 2021) use a neural model. In this paper, we also investigate hinge-based similarity as an alternative, with justification provided in Appendix D.I.
Comparison between different design choices Prior experimental work lacks systematic analysis of this issue, which we address here.
3.6 GENERALIZING ALIGNMENTS FROM NODES TO EDGES
We complete our design space by altering the interaction and alignment granularity from nodes to edges, which is largely unexplored. While IsoNet (Roy et al., 2022) proposed edge based interaction, this was explored with specific choices of other design axes: set alignment, late interaction, injective interaction structure and neural interaction non-linearity. More details are in Appendix D.
Unified framework Instead of node alignment (I), here we compute edge alignment matrices 22 and 2 These matrices computed using edge embeddings M( im (a) (e)
(e)le (e)
[N']]
N "ddm and M = [m (e') E [N]] E xdiim, where N' is the total number of edges after padding. After suitable padding with edges, we have: 229- (M)(M(9))) (4)
M(()))
2
&
( (()))) Edge embeddings
(4) obtained as m (1 (1, v) = no (hk (u), h (t)) and
m (9) (u', =00==(hhh" (h (u'), h
(c) h (o')), where μg is neural network. To compute m we use the
alignment matrix 12% applied on the edge embeddings in Ge for cross graph signals (m k+1 (u) is
(c)
computed likewise):
bo+ (w) = updates
(4)
(h! (4) (u): (u)::u))bbe Evenbr(w) msgg (n), h (6),, m (e))))
(u),
(11)
(g) m k+1 (e) = joing
(h k+1 (u), h 2 (v), (9) (e) E.EE. 2 28 el) m
msge
(12)
Query graph
Corpus graph
7

---

Published as a conference paper at ICLR 2025
Relevance distance: We compute alignment between edge embedding
[[
22 M 19) 1+11ll1 similar to Eq. (5) used in node interactions. Set aggregate based distances or neural distances are computed similar to Eqs. (6) and (7).
Interaction stage: Eq. (12) results in early interaction for non-zero 22 whereas setting $2 to zero leads late interaction model (with joing becoming dormant).
Interaction structure: Similar to section (3.4) w can be injective or non-injective. For injective w. we perform iterative Sinkhorn iterations on () (e), m (e')) for different edge pairs e Gg.e' e' E Ge. whereas for non-injective w. we use attention. Interaction non-linearity Similar to section (3.5), we use neural, dot product and hinge.
Set-Alignment
Agg-Hiuge
Agg- MLP
Aga-NTN
0.A8
0.90
0.75
0.AI-
0.92
DATT
0.99
0.772
0.73
0.12
0.68
0.50
0.03
0,50
Node Bile
Node Bdge
Node Bdge
Nuck: Edle
Node Edge
Soale Blge
Node Bige
Node Eilas
Node Edge
Nodi Bilge
Non-Injecte Injective
Non-
Injective 0.72
0.86
0.58
0.00
6.75
0.77
0,50
0.92
0.87-
0.00
MAPP
0.09
0.72
0.75
0.81
6.62
0:00
0.83
0.55
0.56
0.50
0.50
Node
Edge
Node
Nodie
Filge
Node
Edge
Node
Bdg
Node
BMgge
Nodo
Edge
Node
Frlge
Node
Edg
Node
Filgn
Neural
Dot Product
TTnge
0.80
0.58
0.72
0.75
p 0.77
0.50
0L82
0UST
0.10
MAP
0.77
0.75
0.51-
0.62
0.00
0.40-
0.08
0.50-
0.50
051
0.56
0.00
0.50
Ferb. Edae
0,50
Eaclo Eueoo
Node
Edly
Node
Edle
Nadh:
Edae
Node
Edge
Node
Edae
Node
Edee
Node
Blge
Nodk:
Node
Edge
Node
Blae
AIDS
MUTAG
PTC-FM
NCI-H2SH
MOLT-4H
Figure 2: MAP for various choices of design axes. Each column corresponds data set. Each chart has four bar groups, corresponding to interaction stage (late, early) x granularity (node, edge). In the top row, each color represents relevance distance (set alignment vs. aggregated hinge, MLP, and NTN). In the middle row, colors correspond to non-injective and injective interactions. In the bottom row, each color represents a different form of interaction non-linearity (neural, dot product, and hinge). Each bar shows the test MAP after choosing all other axes, policies hyperparameters to maximize validation MAP. Individually, set alignment (first row), early interaction (third and fourth groups of bars in each row), injective mapping (sccond row), hinge nonlinearity (third row) and edge based interaction (second and fourth groups of bars) are the best choices in their corresponding axes.
4 EXPERIMENTS
In this section, we systematically evaluate different configurations across the five salient design axes on ten real datasets with diverse graph sizes. Appendix F contains additional experiments.
4.1 EXPERIMENTAL. SETUP
Datasets We select ten real-world datasets from the TUDatasets repository (Morris et al., 2020), viz., AIDS, Mutag, PTC-FM (FM), NCI, MOLT, PTC-FR (FR), PTC-MM (MM), PTC-MR (MR), MCF and MSRC. Detailed descriptions of these datasets are provided in Appendix E. Here, we present results the first five datasets, relegating others to Appendix F.
Training and Evaluation We split query graphs Q {Gy} into training, validation and test folds in the ratio 60:15:25, Given Cgv,i.e, i.e., the set of all corpus graphs that are supergraphs of a query graph Go we estimate model parameters by minimizing ranking loss EqeTrain set Ees ECgr gC,,
dist (9))) (((())) - dist (9) H (((e))) where is the margin hyperparameter, following the approach in (Roy et al., 2022; Li al., 2019). For each test query g, we rank corpus graphs by ascending order dist (H H We evaluate performance using mean average precision (MAP).
K
(Additional settings, hyperparameters reported in Appendix E).
8

---

Published as a conference paper at ICLR 2025
4.2 RESULTS
Optimal choice for each design axis The problem of selecting the best design choices entails exploring five design axes with 66 configurations. To keep the exploration manageable in Figure 2. each column corresponds to one data set. Within each chart, we vary (what we found as) the two most influential axes: interaction stage (late, early) x granularity (node, edge). The top row explores the effect of the choice of relevance distance. (Therefore, each color corresponds one choice of relevance distance.) The middle row explores the effect of non-injective vs. injective interactions. The bottom row explores the effect of the choice of interaction non-linearity. This covers the five major design axes. Each chart shows the best MAP over all choices of axes not involved.
AIDS
NCI
AIDS
NCT
(A)
Agg
Agg
SA
(B)
Agg
SA. (Node)
Agg
SA
(Late -> Early)
(Late)
(Late-
-> Early)
(Late)
(Node + Edge)
(Node + -dgee)
(Node)
Node
0.557 - 0.726
0.664
0.529
0.624
0.625
0.557
0.635
0.664
0.529
0.369
0.625
Edge
0.635 -> 0.763
0.712
0.569
- 0.666
0.643
Early
0.726
0.763
0.734
0.624 + 0.660
0.654
AIDS
NCI
AIDS
NCI
(C)
Node
Edge
Node
Edge
(D)
Late
Early
Late
Early
(Agg
SA)
(Agg)
(Agg
SA)
(Agg)
(Agg + SA)
(Agg)
(Agg +
(Aga)
Late
0.557
0.004
0.635
0.529
0.625
0.309
Node
0.557 0.064
0.726
0.529 + 0.625
0.024
Early
0,726
0.734
0.763
0.624
+ 0.654
0.006
Edge
0.635 + 0.712
0.763
0.569 0.643
0.666
Table 1: Does transition from worse to better choice in one design axis improve the performance of the worse choice in another axis? Highlighted numbers show the best performer.
Figure 2 shows the results, which reveals the following observations. (1) Early interaction performs
better than late interaction (groups vs. 3, 2 vs. 4 in each chart) across almost all datasets. While this is consistent with the observations from other domains (Lai and Hockenmaier, 2017; Chen et al., 2020; Wang et al., 2021; Khattab and Zaharia, 2020), this trend is opposite to what IsoNet (Roy et al., 2022) reports - we dig deeper into this by comparing IsoNet against careful modifications GMN, later in this section. For AIDS and Mutag, we observe that the closest cousin of GMN outperforms the closest cousin of IsoNet. We attribute this to upgrading GMN's default non-injective mapping to IsoNet's 's injective mapping. (2) In terms of alignment granularity, edge is better than node (groups 1 vs. 2,3 3 vs. 4). (3) Set alignment the best relevance distance (top row). (4) Injective mapping is better than non-injective (middle row). (5) Hinge is the best nonlinearity (third row).
Performance sensitivity to design choices To enhance clarity, we present numerical summaries in Table for the AIDS and NCI datasets, providing a quick reference to support our key arguments alongside the detailed bar plots in Figure 2. In panel (A) of Table I, replacing late interaction with early, while keeping either edge or node granularity fixed, allows aggregated-hinge to outperform set alignment in three out of four cases, with a near tie in the fourth. This demonstrates that shifting from late to early interaction can offset some limitations of relevance distance. In contrast, Panel (B) shows that transitioning from node to edge granularity with aggregated-hingg and set alignment has less predictable effect, with set alignment retaining its lead in late-stage interaction. Panel (C) shows that the performance gain from switching to set alignment is more pronounced in late interaction than early interaction. Panel (D) reveals that while early interaction is generally superior, switching to set alignment in the NCI dataset boosts performance, consistent with observations in IsoNet.
Design guideline to maximize accuracy through change of only one axis: From these insights, we propose the following design guidelines.
(1) Shifting from late to early interaction can overcome scoring layer limitations, (2) In late interaction, switching from aggregated-hing is highly effective, accounting for IsoNet's superiority over GMN; and, (3) In the absence of any other design constraints, early edge interaction with set alignment with injective structure and hinge nonlinearity is the optimal configuration.
to set alignment
Best design choices for accuracy-time trade off We investigate how to optimize design choices while considering time constraints, by analyzing the trade-off between MAP and inference time. Figure 3 presents the scatter plot for AIDS dataset, where each point represents a unique design combination. Each subplot replicates the same set of points but colors them according to different choices along the design axes. Here are the key takeaways.
Design guideline to optimize accuracy-time trade off: (1) Set alignment consistently performs best across both reduced-time late interaction models and high-MAP, slower early interaction setups. In the mid-range accuracy-time trade-off, NTN and MLP occasionally perform better. (2) Early interaction models generally achieve higher MAP, though even the fastest early variant is slower than the slowest late interaction one. Some late interaction designs provide better MAP, making them an effective choice if time is scarce. (3) Injective mappings consistently outperform non-injective ones

---

Published as a conference paper at ICLR 2025
Age- Hinge AEE-NTN
AsP-MPP Set- Aligiment
Early Late
Nou-iajective
Hiuge Dot Product
Edge
Enjeetive
Noda
Noumaa
0.3-
0.5
0.5
0.8-
0.8-
0.7
0.7
0.7
0.6
0.6
75
25
75
25
25
50
75
50
75
Time (mu))
Inf. Time (aus)
Inf. (ins)
Inf. Time (mus)
Time (mu))
Figure 3: Scatter plot of MAP versus inference time for different design choices on the AIDS dataset. Each point represents a unique combination of design axes, with colors indicating variations in relevance distance, interaction structure, stage, non-linearity and granularity.
in both high-MAP, high- high-inference-ine time scenarios and low-MAP, -ie-ininneee-iinne setups. Their better performance comes with only a slight time increase in low-time settings. But, in high-MAP, in high-inference-ting regimes, injective mappings result in significant increases in computational cost, due to iterative Sinkhorn normalization, which makes makes non-injective mappings a viable alternative in that regime. (4) Hinge and dot product perform best in high-MAP, slower setups, while hinge and neural options excel in faster, lower-MAP configurations. Hinge offers balanced performance and inference time. (5) Edge-level interaction consistently yields higher MAP than node-level interaction, but mostly at the cost of slower query execution.
Comparison against baselines We now highlight the optimal combinations of the design space, selected through the best validation MAP across all possible design choices, against existing state-of- the-art (SOTA) methods. Table 2 shows the results, along with the underlying design choices. As evident from the table, recent models occupy only a few isolated areas within the broader design space, leaving many potential configurations unexplored. We make the following observations: (1) Our best combination from early interaction models (Our-Farly-Best) is the winner across all datasets, whereas the best possible late interaction model (Our-Late-Bil -ar--ate-Best) shows the second best performance across four out of five datasets. (2) Models using set alignment, viz., IsoNet, Bur-Early-Bees
Our-Late-
consistently outperform those employing aggregated heuristics. GOTSim finds alignment by using a Hungarian solver, which prevents end-to-end differentiability. resulting in poor performance. Other methods which use aggregated embeddings perform poorly, (3) While Our-Early- -eett leverages set alignment and injective structure, GMN uses aggregated embeddings and non-injective interaction structure, showing lower performance. H2MN, despite using edge granularity, under-performs significantly, suggesting that its other design choices made in carly interactions might not effectively leverage the structural advantages.
Rel. Dist.
Structure Noa-lin. Granularity AIDS
Mutag
FM
NCI
MOLT
SimGNN (Bai 2019)
Agg-NTN
NA
NA
Node
0.326
0.303
0.416
0.39
0.421
GraphSim (Bui et al., 2020)
Agg-MLP
NA
NA
Node
0.173
0.182
0.231
0.468
0.499
GOTSii (Doan et al., 2021)
Set align.
Injective
Neural
Node
0.336
0.387
0.459
0.382
0.462
ERIC (Zhuo and Tan, 2022)
Agg-NTN
NA
NA
Node
0.512
0.558
0.624
0.356
0.549
Late
EGSC (Qin et al.. 2021)
Agg-MLP
NA
NA
Node
0.5
0.416
0.613
0.528
0.555
GREED (Ranjan et al., 2022)
Agg-hinge
NA
NA
Node
0.502
0.551
0.545
0.478
0.507
GEN et al., 2019)
Agg Agnne
Non-inj
Dot-Prod
Node
0.537
0.594
0.636
0.529
0.537
Neuromatch (Lou et al.. 2020)
Agg-binge
NA
NA
Node
0.451
0.583
0.622
0.513
0.552
IsoNet (Roy et al., 2022)
Set align.
Inj
Neural
Edge
0.704
0.733
0.782
0.615
0.649
Our-Late-Best
Set align.
Inj
Hinge
Edge
0.712
0.721
0.793
0.643
0.662
Early
HHMN (Zhang et al., 2021)
Agg-Mi.P
Non-inj
Prod
Edge
0.267
0,282
0.364
0.381
014055
GMN-Match (Li al., 2019)
Agg-hinge
Non-inj
Dot-Prod
Node
0.609
0.693
0.686
0.588
0.603
Our-Early-
Set align.
Inj
Hinge
Edge
0.817
0.837
0.887
0.677
0.71
Table 2: Comparison of MAP between our best combination of choices across different design axes, for both early (Our-Early-Best and late (Our-Late-Best) interaction and the state-of-the-arr subgraph matching methods. Green, Blue and Yellow cells indicate best early, best late and second- best late interaction methods.
5 CONCLUSION
In this work, we have methodically charted the design space of neural subgraph matching models, which has been sparsely explored by previous models that proposed variants using a limited subset of design choices. Our investigation into hitherto uncharted design regions gives new insights and uncovers design combinations that significantly boost performance. We proposed set of guidelines to inform future work, helping researchers make optimal design choices based on accuracy requirements and query time constraints.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
Indradyumna acknowledges Google PhD fellowship; Abir acknowledges SERB CRG grant; and, Soumen acknowledges SERB and IBM grants.
REFERENCES
Y. Bai, H. Ding, S. Bian, T. Chen, Y. Sun, and W. Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference Web Search and Data Mining, pages 384-392, 2019.
Y. Bai, H. Ding, K. Gu, Sun, and W. Wang. Learning bassing-basedd efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings the AAAI Conference on Artificial Intelligence, volume 34, pages 3219-3226, 2020.
H. Bast, B. Buchhold, and E. Haussmann. Semantic search on text and knowledge bases. Found. Trends Inf. Retr, 10:119-271, 2016. URL pottps://appe semanticscholar..org
CorpusID: I 64 374591.
R. Bevan, O. Turbitt, and M. Aboshokor. Mdc at semeval-2023 task 7: Fine-tuning transformers for textual entailment prediction and evidence retrieval in clinical trials. In International Workshop on Semantic Evaluation, 2023. URL https:/ /tpp. semant ccscholar org/ Carp/orrpsss.. 259376630.
G. Bhalotia, A. Hulgeri, C. Nakhe, S. Chakrabarti, and S. Sudarshan. Keyword searching and browsing in databases using BANKS. In ICDE. IEEE, 2002.
Chakrabarti, H. Singh, S. Lohiya, P. Jain, and M. Joint completion and alignment of multilingual knowledge graphs. In EMNLP Conference, pages 1 1922-11938, Dec. 2022. doi: 10.18653/v1/ 2022.emnlp-main.811 URL wwtpttttt////o
anthol ogy- org/2022. emn p-ma i 8177.
Chen, Z. Jiang, A. Poliak, K. Sakaguchi, and B. Van Durme. Uncertain natural language inference. In D. Jurafsky, Chai, N. Schluter, and Tetreault, editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 8772-8779, Online, July 2020. URL https:
Association for Computational Linguistics. doi: 10. 1001866511122022aallmmmmi org/ 2zgg20200 2020. acl maalmmain...m 774.
D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. International journal of pattern recognition and artificial intelligence. 18(03):265-295 2004.
L. P. Cordella, P. Foggia, C. Sansone, and M. Vento. A (sub) graph isomorphism algorithm for matching large graphs. IEEE transactions on pattern analysis and machine intelligence, 26(10): 1367-1372, 2004.
M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2300, 2013.
A. Deutsch, M. F. Fernández, D. Florescu, A. Y. Halevy, D. Maier, and D. Suciu. Querying xml data. IEEE Data Eng. Bull., 22:10-18, 1999. URL https: //api. semanti org/
Corpus CorpusID:3330 :3:389933..
K. D. Doan, S. Manchanda, S. Mahapatra, and C. K. Reddy. Interpretable graph similarity computation via differentiable optimal alignment of node embeddings. pages 665-674, 2021.
J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248-26) Apr. 1972. ISSN 0004-5411. doi: 00.1445/21694.3311699 URL http::ttp://... /ww. /10 1145/124222 694 321699.
A. Hagberg, P. Swart, and D. S Chult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National (Lb.(L.,..), Los Alamos, NM (United States), 2008.
G. Kasneci, M. Ramanath, F. M. Suchanck, and G. Weikum. The yago-naga approach to knowledge discovery. SIGMOD Rec., 37:41-47, 2009. URL https: / api, semanticschoi org/ CorpusTD:530731
11

---

Published as a conference paper at ICLR 2025
O. Khattab and M. Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pages 49-48, 2020.
D. Koller and N. Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
A. Lai and J. Hockenmaier. Learning to predict denotational probabilities for modeling entailment. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 721-730, 2017. URL https: /ww. aclweb.
org/ a/t/olothoogyyy/o / 1e//EE1111111 1068 pdf.
L. C. Gu, T. Dullien, O. Vinyals, and Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pages 3835-3845.
PMLR, 2019. URL https: aariiv.vvvv. org/ waargg/bbs/00 abs/1904 12787.
K. Liang. L. Meng, M. Liu, Y. Liu, W. Tu, S. Wang, S. Zhou, X. Liu, F. Sun, and K. He. A survey of knowledge graph reasoning on graph types: Static, dynamic, and multi-modal. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024. URL https: attps://ieeeee htttp::/ieeexploee.cee ieee.
org/abste abs/taatttcc/cca/a///aa////..ctt document/ 10577554.
X. Ling, L. Wu, S. gang Wang, G. Pan, T. Ma, F. Xu, A. X. Liu, C. Wu, and and Deep graph matching and searching for semantic code retrieval. ACM Transactions on Knowledge Discovery from Data (TKDD), 15:1 - 21, 2020. URL httss::::/ /api. cemanticscholas. org/ perg/CorpusDD: 225067851.
Z. Liu and Chen. Reasoning and identifying relevant matches for xml keyword search. Proc. VLDB Endow. 1:921-932, 2008 URL https:/ /app.ap.../// semant icscholaar 6100135.
Z. Lou, J. You, C. Wen, A. Canedo, J. Leskovee, et al. Neural subgraph matching. arXiv preprint arXiv:2007.03092, 2020.
G. Mena, D. Belanger, S. Linderman, and J. Snoek. Learning latent permutations with gumbel- sinkhorn networks. arXiv preprint 802.0:/882.008655, 2018. URL pdf/1802, w0w.5.666......
B. Mitra and N. Craswell. An introduction to neural information retrieval. Foundations and Trends@ in Information Retrieval, 13(1):1-12,, 2018. ISSN 1554-0669. doi: 10.1561/150000061. URL http: / /xx. doi. org/10.......o......... 61 01151/1110000000 15000000611
C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. 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.ggaaahaiinggg....gggee io.
L. Piccolboni, A. Menon, and G. Pravadelli. Efficient control-foww subgraph matching for detecting hardware trojans in rtl models. ACM Transactions on Embedded Computing Systems (TECS), 16 (5s):1-19, 2017.
C. Qin, H. Zhao, L. Wang, H. Wang, Y. Zhang, and Y. Fu. Slow learning and fast inference: Efficient graph similarity computation via knowledge distillation. In Thirty-Fifih Conference on Neural Information Processing Systems, 2021.
S. A. Rahman, M. Bashton, G. L. Holliday, R. Schrader, and J. M. Thornton. Small molecule subgraph detector (smsd) toolkit. Journal of cheminformatics, 1:1-13, 2009.
A. Ramachandran, V. Raj, I. Roy, S. Chakrabarti, and A. De. Iteratively refined early interaction alignment for subgraph matching based graph retrieval. Advances in Neural Information Processing Systems, 37:77593-77633 2025.
R. Ranjan, S. Grover, S. Medya, V. Chakaravarthy, Y. Sabharwal, and S. Ranu. Greed: A neural framework for learning graph distance functions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, November 29-Decemer 2022, 2022.
12

---

Published as a conference paper at ICLR 2025
R. G. Reddy, J. Doo, Y. Xu, M. A. Sultan, D. Swain, A. Sil, and H. Ji. FIRST: Faster improved listwise reranking with single token decoding, 2024. URL https: httppp/:///xxxx/.////a.ao /400.. 15657.
I. Roy, S. Velugoti, Chakrabarti, and De. Interpretable neural subgraph matching for graph retrieval. In AAAI Conference, 2022. URL http:: htt::///nnddddddaieee hammma..ittttttt IsoNet_ma in, pdf.
T. Saxena, P. Tu, and R. Hartley. Recognizing objects in cluttered images using subgraph isomorphism. In Proceedings of the IU Workshop, Monterey, 1998.
V. Shankar, J. Zhang, J. Chen, C. Dinh, M. Clements, and A. Zakhor. Approximate subgraph isomorphism for image localization. Electronic Imaging, 28:1-9, 2016.
H. V. Simhadri, R. Krishnaswamy, G. Srinivasa, S. J. Subramanya, A. Antonijevic, D. Pryce, D. Kaczynski, S. Williams, S. Gollapudi, V. Sivashankar, N. Karia, A. Singh, S. Jaiswal, N. Mahapatro, P. Adams, B. Tower, and Y. Patel. DiskANN: Graph-structured indices for scalable, fast, fresh and filtered approximate nearest neighbor search, 2023. URL https: //github. www..om/////o.//o Mi crosoft /teff///iiiieeeee /DiskANN.
R. Sinkhorn and P. Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21(2):343-34,, 1967.
R. Socher, D. Chen, C. D. Manning, and A. Ng. Reasoning with neural tensor networks for knowledge base completion. In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Wein- berger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013. URL https: http://ttweeeeenncceeeeeccccesst neurips. ce hwwpppapp...... ffiles/papes / /33 0003:/Llee2331186446622222222283
pdf.
F. M. Suchanek, G. Kasneci, and G. Weikum. YAGO: A core of semantic knowledge unifying WordNet and Wikipedia. WWW Conference, pages 697-706. ACM Press, 2007. URL http:
//www2007. www.///pgrrre.... pttpss//ppppp91..ppppp
Y. Suh, K. Adamezewski, and K. Mu Lee. Subgraph matching using compactness prior for robust feature correspondence. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5070-5078, 2015.
Z. Sun, J. Huang, W. Hu, M. Chen, L. Guo, and Y. Qu. Transedge: Translating relation--comtexxuullzed embeddings for knowledge graphs. CoRR, abs/2004.13579, 2020. URL htthttss://axxxv.ooo abs abs/2004 13579.
X. Tang, J. Zhang, B. Chen, Y. Yang, H. Chen, and C. Li. Bert-int: A bert-based interaction model for knowledge graph alignment. interactions, 100:e1, 2020.
Y. Tian, R. C. Mceachin, C. Santos, D. J. States, and J. M. Patel. Saga: a subgraph matching tool for biological graphs. Bioinformatics, (112::22-239 2007.
Vendrov, R. Kiros, Fidler, and R. Urtasun. Order-embeddiins of images and language. arXiv preprint 1rXiv:/511.0636 2015. URL
S. Wang. H. Fang, M. Khabsa, H. Mao, and H. Ma. Entailment few-shot learner. arXiv preprint 20X4v22004.14690, 2021.
Y. Wang, Y. Xia, J. Yan, Y. Yuan, H.-B. Shen, and X. Pan. Zerobind: protein-specific zero-shot predictor with subgraph matching for drug-target interactions. Nature Communications, 14(1): 7861, 2023.
Willett, J. M. Barnard, and M. Downs. Chemical similarity searching. Journal of chemical information and computer sciences, 38(6):983-996, 1998.
Y. Wu, X. Liu, Y. Feng, Z. Wang, R. Yan, and D. Zhao. Relation- entity alignment for heterogeneous knowledge graphs. CoRR, htw/1908.08220 2019. URL http: // /rxiivorrg/ abs 908. 08210.
13

---

Published as a conference paper at ICLR 2025
Z. Zhang, J. Bu, M. Ester, Z. Li, C. Yao, Z. Yu, and C. Wang. H2mm: Graph similarity learning with hierarchical hypergraph matching networks. Proceedings of the 27th ACM SIGKDD Conference Knowledge Discovery & Data Mining, pages 2274-2284, 2021.
Z. Zhang, X. Wang, C. Guan, Z. Zhang, H. Li, and W. Zhu. AutoGT: Automated graph transformer architecture search. In The Eleventh International Conference on Learning Representations, 2023a.
URL https: opppreveeeeeeeeeeeeeeeeeeee net. peet/forrue forum? id=GcM7qf152Y.
Zhang, X. Wang. Zhang, G. Shen, Shen, and W. Zhu. Unsupervised graph neural architecture search with disentangled self-supervision. In Thirty-seventh Conference Neural Information Processing Systems, 2023b. URL httptttttt:p/peeee/ee/e///e
www.:/ntttooouuue d=UAF a2hR85.
R. Zhu, M. Ma, and Wang. RAGA: relation-aware graph attention networks for global entity alignment. PKDD, abs/2103.00791, 2021. httptttss///xx...ooott
00791.
Y. Zhu, H. Liu, Wu, and Y. Du. neiationn matching model model for entity alignment. CoRR, abs/2012.08128, 2020. URL
W. Zhuo and G. Tan. Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, 35:30181-30193, 2022.
14

---

Published as a conference paper at ICLR 2025
Charting the Design Space of Neural Graph Representations for Subgraph Matching (Appendix)
A LIMITATIONS
We present a thorough investigation into the design space of interaction models, with our best model significantly outperforming existing variants, and provide valuable insights into accuracy and time trade-offs. However, there could be potential limitations as follows:
(1) Many real-world applications, such as ligand-based screening in chemical compound libraries, rely on 3D graph topology orient subgraphs for maximizing binding affinity with target graphs. Our approach does not account for such characteristics, which could potentially be encoded as features. However, experimental verification of this encoding is necessary establish its effectiveness.
(2) The robustness of the models within outlined design space against noise remains uncertain. There may be instances of missing or noisy ground truth information, as well as inaccuracies in node or edge information caused by adversarial attacks or perturbations. Further investigation is required to assess the impact of these factors on model performance.
(3) In scenarios where out-of-distribution (OOD) performance is essential, it is unclear which design choices exhibit greater robustness. Some models may effectively leverage distributional characteristics for subgraph matching in in-distribution datasets but may not perform as reliably when faced with OOD data. This aspect warrants further exploration to determine the models' adaptability varying data distributions.
B BROADER IMPACT
In recent years, there has been a surge of interest in this area, leading numerous publications that explore different facets of subgraph matching. However, the multitude of design choices available has not been thoroughly investigated, often steering research efforts in suboptimal directions. By carefully navigating this complex design space, we have provided a benchmark that outlines promising axes for future exploration. Our findings offer a foundational framework upon which subsequent research can build, guiding efforts toward more effective and efficient models. Additionally, our insights into the intricacies of subgraph matching and scoring mechanisms could inspire further analyses of failure cases and potential avenues for improvement, fostering advancements that could benefit wide array of applications.
In terms of practical applications, the broader impact of this work is significant across various real-world graph similarity scoring and retrieval tasks.
(1) In-silico drug discovery (Rahman et al., 2009; Wang et al., 2023; Willett et al., 1998). Subgraph matching based retrieval is critical component of ligand-based virtual screening for in- silico drug discovery, enabling the identification of potential drug candidates by comparing molecular structures to known ligands. This is crucial for quickly searching for potential drug candidates from large chemical compound libraries.
(2) Querying pathway fragments in biological graph databases (Tian et al., 2007). In bioinfor- matics, subgraph matching assists in querying pathway fragments, allowing researchers retrieve and analyze biological pathways efficiently, thereby facilitating understanding of complex biological interactions and mechanisms.
(3) Image localization (Shankar et al., 2016). Subgraph matching techniques are useful in improving the accuracy of computer vision systems in real-world navigation scenarios, by identifying and matching features between images and reference maps.
(4) Feature correspondence in computer vision (Saxena et al., 1998; Suh et al., 2015). Fur- thermore, computer vision tasks, subgraph matching enables effective feature correspondence, improving object recognition and scene understanding by identifying similar structures across differ- ent images.
(5) Hardware Trojan detection (Piccolboni al., 2017). Subgraph matching is useful in hardware security for detecting hardware Trojans in integrated circuits, by identifying malicious modifications.
While our work presents numerous practical applications across various domains, we do not anticipate any ethical concerns inherent in investigations as part of this paper. Our focus has been
15

---

Published as a conference paper at ICLR 2025
advancing the understanding and effectiveness of subgraph matching techniques, and we believe that our findings will contribute positively to the relevant fields without raising ethical issues.
C RELATED WORK
Parts of the design space we explore have been latent in various applied set and graph analysis communities in recent years.
Interaction modeling in graphs across different domains Knowledge graphs (KGs) provide well-motivated graph search and alignment applications. E.g., one may want partial alignments between KGs with nodes (entities) and edges (relations) labeled in multiple languages. Representing nodes u, v as bags of embeddings of their respective neighborhoods, and featurizing the Cartesian space of their member embeddings, has been found superior to comparing single vectors representing and (Tang al., 2020; Chakrabarti et al., 2022). Others exploit duality between edge and node embeddings (Wu et al., 2019; Sun et al., 2020; Zhu et al., 2020; 2021).
Set based relevance distance models In dense text retrieval (Mitra and Craswell, 2018), query and a corpus document are each represented by a single vector, obtained by encoding each of them separately through a suitable contextual embedding transformer network, and these vectors are compared with a similarity function (commonly cosine). The late interaction enables use of approximate nearest neighbor indexes (Simhadri et al., 2023). Today's 's large language models (LLM) beat such "single-vector" probes. Typically, the query and shortlisted passages, together with a tuned instruction "prompt' all concatenated into the input context of LLM, which is then asked to output passage IDs in decreasing order of relevance (as it deems) (Reddy et al., 2024). However, this early interaction comes with steep price of slower execution. ColBERT (Khattab and Zaharia, 2020) strikes an effective compromise related to set alignment: compute contextual embeddings of all query and corpus words, and then, for each query word embedding, find the best-matching 'partner' from candidate passage to score it.
Subgraph matching in other domains Searching knowledge graphs like Wikidata or YAGO present strong motivation for graph matching (Bhalotia et al., 2002; Suchanek et al., 2007; Kasneci et al., 2009; Bast et al., 2016). In such applications, the query is usually connected small graph with wildcard features on nodes or edges, e.g., (2m, mother-of, Barack Obama), (?m, attended-school. ?s), natural language question ("where did Barack Obama's 's mother go school?") that is 'compiled' to such a small query graph Gg. This graph must then be 'overlaid' on to a large corpus graph (the knowledge graph) with low distortion with regard node and edge features. XML search (Deutsch et al., 1999; Liu and Chen, 2008) and code search (Ling et al., 2020) have many of the same characteristics.
Automated network structure search Within specific families of graph encoder networks, such as GNNs/GATTs (Zhang et al., 2023b) or graph transformers (Zhang et al., 2023a), researchers have proposed super-networks to explore the parametric space of encoder networks, using bi-level optimization framework. We do not yet NAS as automating the combination of design spaces described in our paper. But would be of future interest to investigate if NAS methods can be extended subgraph search and other combinatorial graph problems, to automatically explore network design spaces.
16

---

Published as a conference paper at ICLR 2025
D ADDITIONAL DETAILS ABOUT THE UNIFIED FRAMEWORKS AND DIFFERENT DESIGN COMPONENTS
D.1 JUSTIFICATION BEHIND THE HINGE NON-LINEARITY
The neural surrogate of the optimization problem for the subgraph isomorphism problem can be written as follows:
min QuPEPy
|H S2
(2..5HH 11,11
(13)
We manipulate the optimization target follows:
| - 52 1+11
H [u, il]+ S2 v]
TTacee( !2:0))
Differentiable optimization of S2 is carried out by adding entropic regularizer (Cuturi, 2013; Sinkhorn and Knopp, 1967; Mena al., 2018).
min Trace (TT Q
Σ
12 (u, v) log (u, v]
(14)
Hence, the iterative row-column normalization described in Eq. (10) is reduced to Zo exp(CCTT
(15)
Z [u, u']
Zi (u, u'] EeE[N] Ze(u, w/) for all (u,u')
Z++1 u'] = EV'EI Zi v"]: where Zi(u, u']
(16)
Clearly, here C = (HH, (())). Hence, such initialization leads to solve optimization of the problem described in Eq. (13), leading to a high inductive bias.
D.2 UNIFIED FRAMEWORK FOR ADGE-GRANULARITY MODELS
The message passing framework requires modification to conform to edge-level granularity. The query graph equations are shown in Eqs. (11), (12) in the main text. The equations for corpus graphs are shown below, with edge e' = =(u'v')
(e) hi+ (w') updates (nl ((():
msge (n (c)
(w'),
(0) (v)). m (e))))
(17)
E'Enb((u
m (e') = joing msgo (n(e) (1'), (c)
(v)), m (9) (d)).
Σ
Te' e) (2)
(18)
eEE,
Corpus graph
Query graph
For late interaction model, Eqs. (12) and (18) respectively transform into the following: (q)
m (e)
msge
(n (9) ( (u), (v). m
m() (e()
(19)
k++ msga
(c) 6+1 ( (u'), h (v') m (c) (c'))
(20)
D.3 END-TO-END FRAMEWORK OUR BEST MODEL
In this section, describe the components of our best-performing model Our-Early-Bes which ranks first on nine out of ten datasets with respect to MAP.
Relevance distance: Set Alignment
Interaction stage: Early
Interaction structure: Injective
Interaction non-linearity Hinge
Interaction granularity: Edge
The following equations represent message passing within the GNN which emits M and M (
h (g)
h (u) update, (n (w);
Σ
(g) msgo (n( (u), h (v). m (4) (e))
(21)
(e)
17

---

Published as a conference paper at ICLR 2025
(4) m (e) = joing
(9) msgg ( h (0)) me
(2) (c)):
E d'E
aa e'I m m (e')
(c)
(22)
Query graph
Corpus graph
At each layer of message passing, the edge representations are used to compute the injective alignment matrices 12 and f2 using the following equations. represents the number of edges.
Zo = exp(n((M /
(23)
e, ele
Ze(e,ed
where Zi(e,e'|
for all (e,
(24)
E1eee Zile, M']
Σ]E[E) Zelf,e"]
2
ZT
2 = 27
(25)
The Hinge non-linearity is used to compute the initial alignment estimate Zo in Eq. (23) as such:
m (9)
[e,e)"
(m, m m (c')+
m
(26)
Finally, the relevance distance Set align. is used to compute the score between the query and corpus graphs. It utilizes the computation of 12 and $2 shown above.
(Gst G.) [
22% 2 1
(27)
D.4 DIFFERENCE BETWEEN GMN AND GMN*
Li et al. (2019) proposed GMN for the graph isomorphism task, which matches the query and corpus nodes as is. This leads to an unbalanced Optimal Transport (OT) problem the query and corpus graphs differ in size, which is the case for subgraph isomorphism. Roy et al. (2022) introduced padding nodes to have equi-sized graphs, thus converting it into a balanced OT problem.
Suppose we have two graphs G3 = (Vg Eg) and G, = (V e E.) and we pad the query graph with V.l VVg disconnected nodes to obtain G (V, Vpad, F.g. Two different non-injective
alternatives are described below. As a shorthand, represent sim(a, b) ny(h (a), ((((())
(b)) here.
Including the padding nodes Vpad to compute the alignment. The following equations hold for all u E Vg U Vpad and u' E Ve.
cim(uu,"))/
cim(unn))//
22 uu u/]
Eutev. esim(w,ut)/7" 22 [u', u]
(28)
E EuteV,uV,.. esim(ut,wr)/T
Mask out the padding nodes from the attention computation. For u E Vg. u' E Ve. the following equations hold. Note the difference in the denominator for computation of N0.9
(slm(,,w))/ 1/7
esim(u,')//
(u uu' =
Entev. esim(uat)/+ 22 [ul, = Ewlev, eslm(ut,w/)/r
(29)
For u E Vpad, w' E Ve, we simply set 2 u/] "
[u/, 0.
The first alternative induces the total mass on the query nodes and that on the corpus nodes to be identical, as should be the case with perfect alignment and hence, we choose it improve the inductive bias.
18

---

Published as a conference paper at ICLR 2025
E ADDITIONAL DETAILS ABOUT EXPERIMENTS
E.1 DATASETS
Ten datasets are chosen from the TUDatasets repository (Morris et al., 2020), six of which were earlier used by (Roy et al., 2022). Key statisties about these datasets shown in Table 3. count(y) represents the number of pairs (Gg: Ge) such that rel(Gg. G.) = y.
Observe that the final four datasets NCI, MOLT, MSRC and MCF have significantly higher query and corpus graph sizes than the remaining six. These datasets were added to the analysis to study the generalizability of our methods to large input graph sizes.
Since these are real-world datasets not readily available in format suitable for the subgraph matching task, we adopt the technique proposed by Lou al. (2020) to sample query and corpus graphs from these datasets. A graph size [V] is randomly sampled from range (maximum specified in Table 3) and Breadth First Search (BFS) is commenced from an arbitrary node till [V] number of nodes are traversed. We perform this operation independently to obtain 300 query graphs and 800 query graphs, and their pairwise subgraph isomorphism relationship (rel, the ground truth) is computed using the VF2 algorithm (Cordella et al., 2004) from the NetworkX library (Hagberg et al., 2008).
Avg. [Vgl
Max [Vll
Avg. |Eg]
Avg. [Vol
Max [V.|
Avg. |Eel co count(()
counc;
count:
AIDS
11.61
15
11.25
18.50
20
18.87
41001
198999
0.2118
Mutag
12.91
15
13.27
18.41
20
19.89
42495
197505
0.2209
FM
11.73
15
11.35
18.30
20
18.81
40516
199484
0.2085
FR
11.81
15
11.39
18.32
20
18.79
39829
200171
0.2043
MM
11.80
15
11.37
18.36
20
18.79
40069
199931
0.2056
MR
11.87
15
11.49
18.32
20
18.78
40982
199018
0.2119
MSRC
14.01
20
20.28
45,41
50
93.58
41374
198626
0.2140
MCF
22.03
21.60
44.79
50
46.50
35951
204049
0.1805
NCI
19.02
25
18.70
44.89
50
46.55
40548
199452
0.2094
MOLT
19.04
25
18.69
44.94
50
46.56
40177
199823
0.2058
Table 3: Statistics for the 10 datasets selected from the TUDatasets collection (Morris et al., 2020)
E.2 METRICS
For query graph Gg. sort the set of corpus graphs C {Ge} in increasing order of dist dist(Gg. Ge) to obtain the ranked list Cg.soet. As noted in the main text, Cgpl refers to the set supergraphs of Gg. and is subset of C.
Average Precision (AP) is defined the ratio of the rank (according so of relevant item in Cyp to its rank in C, averaged over all relevant corpus items. Note that rel Gy. Ge) 1 E Cyrl.
rel(G, (q.soc((pss) x Eee rel(Gyg Cy.son
Ag =
|Cay
pos=1
Mean Average Precision is the mean of AP(g) over all query items & E Q.
Σgeq AP(g)
MAP
Q
19

---

Published as a conference paper at ICLR 2025
E.3 IMPLEMENTATION DETAILS ABOUT GNN, MLPs
We list all the hyperparameters and details for different network components here. we use Linear(a, b) to denote linear layer with input dimension and output dimension b. Composition of Linear (a, b), ReLU and Linear(b, e) networks is denoted by MLP (a, c) (similarly for > 3 arguments).
Node features are set to [1] following (Roy et al., 2022), since the goal is to ensure feature agnostric subgraph matching. Such identical fcaturization ensures that two structurally isomorphic graphs have exact same embeddings.
The node and edge embedding sizes are respectively set to dim,, = 10 and dim... 20. Below, we use dim to refer to one of these based on the granularity of the network involved. the concatenation of the embeddings of the nodes that form the edge and optionally the edge's embeddings, as shown in Eq. (2). To ensure that the undirected nature of graphs is respected, msg, is applied to both ordered pairs (u, v) and (v, u) and their sum is returned. For mode-granularity models, the edge embedding is a fixed one-sized vector and thus, the msgg is a Linear(21. 20) network. For dige-graaularity models, the edge embedding is of size 20, resulting in a Linear (40, 20) network.
msga computes messages by operating
update, is modeled as GRU where the initial hidden state is the node representation (the first argument) of size 10, as shown in Eqs. (2) and (11). Exactly one GRU update is performed on top of this base vector. However, the update vector varies based on the stage and granularity of the network. For early interaction networks with edge granularity and late interaction networks, the update vector is simply an aggregation (sum) of all message vectors corresponding to this node, of dimension 20, For node- granularity early interaction networks, the update vector is the concatenation of the aggregated message vector and the difference between the node representation and the signal from the other graph:
(1) (u), K (v)): 1 (u) - Σ Tu u' I' (u') msgo (h
(u')
(Enbe(u)
[EE[N]
The dimension of this vector is 30 (20 from the first term, 10 from the second term).
joing operates on the concatenation of messages from the same graph and alignment-based signal from the other graph. It is modeled as an MLP(400 40, 20) network.
comby inputs the node/edge embeddings and outputs whole graph embeddings, as shown in Eq. (6). For each individual node/edge, We first apply Linear dim, 2 dim) network on its embedding, split into two dim-sized vectors and use the first as a gate (by applying added and passed
sigmoid) for the second vector, sigmoid("1)
92. Individual vectors through a stnear(dim, dim) layer to obtain the dim-sized whole graph vector.
The MLP in Eq. (7) operates on the concatenation of whole graph embeddings, and is modeled as an MLP(2- dim, dim, 1) network.
Neural Tensor Network We use a latent dimension of L = 16. The MLP in Eq. (8), 7o is an MLP(16, 8, 4, 1) network, resulting in a scalar score for every graph pair. LRLL,, used for Neural non-linearity in Section 3.5, is an MT.((dim, dim, 16) network.
E.4 TRAINING DETAILS
We adopt common training procedure for all models. The Adam optimizer is used perform gradient descent on the ranking loss with a learning rate of 10-3 and a weight decay parameter of 5 x 10-4, We use batch size of 128, a margin of 0.5 for the ranking loss, and cap the number of training epochs to 1000. To prevent overfitting on the training dataset, we adopt early stopping with respect the MAP score on the validation split, with a patience of 50 epochs & a tolerance of 10-4
Seed Selection We select three integers uniformly at random from the range [o. 104] to obtain our seed set (1704, 4929, 7762). We train each model on all three seeds for 10 epochs, choose the best seed per model per dataset based on the MAP score for the validation split and train this selected seed till completion.
Software & Hardware Details All models were implemented with Py 2.1.2 in Python 3.....3. Experiments were run on Nvidia RTX A6000 (48 GB) GPUs.
20

---

Published as a conference paper at ICLR 2025
F ADDITIONAL EXPERIMENTS
F.1 SELECTION THE BEST CHOICE OTHER DATASETS
Figure 4 is an extension Figure 2 to ten datasets. We observe similar trends overall across all ten datasets. (1) -raanrraallrrtty models dominate those with node granularity and early interaction usu- ally outperforms late interaction. (2) Injective mapping allows for significantly greater performance, compared to non-injective. (3) Hinge non-linearity remains the best among the three options.
Set-Alignment
Agg- -lnge
Agg MIP
Agg-NTN
staehe
Late, Lace,
farry, Karbs
Lade: Lote.
Karty, knchs
Late, Late, Locty, laarg.
Lass, Loce
Karbs Karty,
Lote:
Late,
Kneby, loety.
Non-Injentive
Tnjective
1.00 Todls
Karly.
Tade
Late, Karty, Earty
Labe,
Barry.
Tadn
Fontly. Early
Laton
Karly. Forty
Neural
Dot Product
Hinge
0.75
1.:2:
0.77
Loce,
Karb,
Lacts
Karty
Earty, Node
Earrty
Node
Nodia
Node
Nidde
Node
Nada
Nade:
Node
Lidgo
Noda
AIDS
MUTAG
PTC-FM
NCI-H23H
MOLT-4H
(a) MAP for various choices of design axes for AIDS, Mutag, FM, NCI and MOLT datasets.
Sct- A lignment
Agg-Hinge
Agg- MLP
Agg-NTN
0.58
0.45
T
0.75
0.s
B.54-
8.57
0.00
0.20
0.00
Late, Lark
Parry. Karbs
Lade Loin Fdly
Karly, Farly Falge
Late, Late, Forly, Banry. Ediee
Larn. Lorn Korts Karly; Fvlge
Tate. Tato,
Foely, Torly.
Non-Injective
Injective
0.60
0.38
0.60
0.20
0.54-
Lode.
Latn,
Lacty,
Barby
Late, Lake, Karry, Eacts
Labe,
Lotes
Karby Loarty.
Lode.
Labo, Baerly
Earty.
Labe
Lac.,
Karby
Laety
Neural
Product
Hinge
T 0.77
0.30
0.00
0.30
D.51
Earn
Karly Karty,
Fantyy
Late,
Karly
Tarls;
Late,
Taviy
Node
Nodi
Nidle
Node
Nadio
Nadi
Node
Nodi
Nadio
PTC-FR
PTC-MM
PTC-R
MSRC-21
MCF-7H
(b) MAP for various choices of design axes for FR, MM. MR. MSRC and MCF datasets.
Figure 4: Each column corresponds to a dataset. Each chart has four bar groups, corresponding to interaction stage (late, early) x granularity (node, edge). In the top row, each color represents relevance distance (set alignment vs. aggregated hinge, ML., and NTN). In the middle row, colors correspond to non-injective and injective interactions. In the bottom row, each color represents different form interaction non- oonearieyy (neural, dot product, and hinge). Each bar shows the maximize validation MAP.
test MAP after choosing all other axes, policies or hyperparameters Individually, set alignment (first row), early interaction (third and fourth groups of bars in each row), injective mapping (second row), hinge nonlinearity (third row) and edge based interaction (second and fourth groups of bars) are the best choices in their corresponding design axes.
21

---

Published as a conference paper at ICLR 2025
F.2 COMPARISON BETWEEN GMN* ON OTHER DATASETS
Here, we expand Table ?? include all datasets. We observe that the trends noted in the main text remain largely consistent:
(1) Modifying the non- non-linearity 1 in Eq. (I) from dot product to hinge significantly improves GMN*, outperforming IsoNet seven out of ten datasets.
(2) Changing interaction granularity from Node to Edge, or interaction structure from non-injective to injective offers moderate benefits, improving GMN' over IsoNet in five and four datasets respectively.
alignment does not help, as IsoNet continues to outperform GMN" in eight out of ten datasets. This is likely due to the sensitivity of relevance distance in late interaction models, whereas GMN* uses early interaction.
(3) Altering the relevance distance dist. from aggregated-
(4) Combining set alignment and injective mapping, allows GMN* to surpass IsoNet's performance.
(5) While Hinge non-linearts uinliinerity alone helps GMN* outperform IsoNet, combining with set alignment reduces performance. This is perhaps due to the incompatibility of GMN*'s non-injective mapping with hinge non-linearity.
(6) Combining hinge non-linearity with injective structure affords moderate benefits, allowing GMN to outperformlsoNet in three out of ten cases.
(7) Transitioning edge-level models and adjusting any single design axis consistently improves GMN over IsoNet across all datasets, underscoring the critical role of edge granularity in enhancing subgraph matching performance.
Prior art
Change one design axis in GMN'
Change two design axes in GMN'
Agg-Hinge Set-Align.
Non-Inj
DP
Node
align..
Set align..
Set alignn..
Hinge.
Dataset
IsoNet
GMN
++ Inj
+ Hinge
++ Edge
Inj.
Hinge
Hinge
Edge
Edge
Edge
AIDS
0.704
0.608
0.726
0.676
0.715
0.763
Mutag
0.733
0.693
0.754
0.75
0.723
0.734
0.779
0.669
0.734
0.779
0.763
0,753
0.782
0.686
0.759
0.79
0.79
0.78
0.8
0.772
0.785
0.812
0.826
NCI
0.615
0.588
0.603
0.619
0.618
0.625
0.632
0.599
0.624
0.635
0.656
0.666
MOLT
0.649
0.603
0.62
0.63
0.651
0.653
0.652
0.637
0.635
0.659
0.67
0.686
FR
0,734
0.667
0.706
0.73
0.75
0.727
0.774
0.678
0.733
0.799
0.8
0,772
MM
0.758
0.627
0.691
0.699
0.723
0.706
0.736
0.711
0.713
0.789
0.777
0.799
MR
0.764
0.683
0.715
0.736
0.787
0.746
0.803
0.768
0.752
0.81
0.803
0.815
MSRC
0,411
0,416
0.423
0.423
0.414
0.421
0.436
0.419
0.403
0.421
0.415
0.423
MCF
0.553
0.574
0.601
0.593
Table 4: Changing one or design axes in GMN outperforms IsoNet's default design.
22

---

Published as a conference paper at ICLR 2025
F.3 MAP-TIME TRADE OFF ON OTHER DATASETS (CORRESPONDING FIGURES ARE NEXT TWO PAGES)
In the main paper, we presented MAP vs. inference time scatter plots for the AIDS dataset. Here, we extend this analysis to all ten datasets to validate whether the initial conclusions still hold. Our key observations are:
(1) The trade-off' between early and late-stage interaction remains consistent across all datasets. While early interaction models yield significantly higher MAP scores, they come with a notable increase in inference time. In contrast, late interaction models are much faster, and although they lag behind the top-performing early models, they still outperform a significant portion of the early variants. This makes late interaction viable compromise when inference time is critical factor.
(2) Set alignment continues be the best choice in both early and late interaction setups, offering the highest MAP scores without a significant increase in inference time compared to other relevance distance measures.
(3) Injective interaction structures consistently outperform non-injective variants across most datasets. However, there are exceptions, such as in MSRC, where some non-injective variants come close to matching the best-performing injective models.
(4) Interestingly, several datasets, including MM, FR, MOLT, and Mutag, hinge non-linearity significantly boosts MAP scores compared to other variants. This reinforces recommendation that hinge non-linearity an optimal choice for subgraph matching tasks.
(5) Edge-level interaction continues to outperform node-level granularity. This supports our guideline that, in graphs with similar number of nodes and edges, edge granularity is the superior design choice.
23

---

Published as a conference paper at ICLR 2025
Aus-Hinge Age- VTN
Asx-MLP Set- Algumeent
Early Late
Non-tajettive Fnjerzivo
Hinge Product Nouraa
Edge
Node
0.8-
0.8
0.8
0.8-
0.8-
MAP
0.7
0.7
0.7
0.7
0.7
0.6
0.6
25
50
75
25
50
75
25
50
75
25
50
75
25
50
75
Inf. Time (ms)
->
Inf. Time (ms)
Time (ms)
Inf. Time (ms)
Time (ms)
(a) AIDS
Hinge NTN
Amp-MPP Segmmnig
Nun-tajeetive Injective
Edge Node
Late
Product
Neurall
0.8
0.8
MAP
0.7
0.7
0.7
0.7
0.7
25
50
50 Tnf. Time (ms)
50 Tnf. Time (ms)
25
50 Inf. Timo (ms)
25
50
Tnf. Time (ms)
Inf. Time (ms)
(b) Mutag
Aug-Hinge
App-MLP Alggmmigne
Nun-Enjeettvv Injective
Hinge
NTN
Late
Product Nusura
Node
MAP
0.8
0.8
0.8
0.7
0.7
0.7
25
50
75
25
50
25
50
75
25
50
25
50
75
Inf. Time (ms)
Inf. Time (ms)
Inf.
Time (ms)
Inf. Time (ms)
Inf. Time (ms)
(c) FM
Agg-Einge Ago-NIN
AgR-MIP Set- Aligammett
Early Tate
Injectivee Injective
Doe Product
Node
Neurll
0.675
0.675
0.675
0.075
0.675
f. 0.650
0.650
0.65O
0.660
0.650
MAP
0.62G
0.625
0.025
0.025
0.025
0.600
0.600
0.000
0,800
0.600
25
50
75
25
50
75
25
50
75
25
50
75
25
50
75
Time
(ms)
Time (ms)
Time (ms)
Time (ms)
Time (ms))
(d) NCT
Asx: Hinge Agg-NTN
Agx MLP Aligumannt
Early Late
Noo- Injective Injuctive
Hinge Product Neural
Edge
0.70
0.70-
0.70-
0.70-
0.70-
MAP
0.6G
0.65
0.60
0_60-
0.00-
0.60-
0.00-
255
75
50
25
50
7h
25
50
7h
25
50
Inf.
Time (ms))
Inf. Time (ms)
Inf. Time (ms)
Inf. Time
(ms)
Inf. Time (mss)
(c) MOLT
Figure Scatter plot of MAP versus inference time for different design choices. Each point represents a unique combination of design axes, with colors indicating variations in relevance distance, interaction structure, stage, non-linearity, and granularity.
24

---

Published as a conference paper at ICLR 2025
Aus-Hiuge AST-NIN
App-MLP Scc-Aligmmeet
Early
Nun-Tajjetivve Injective
Hings Product
Edge
Node
0.8
0.8
0.8
MAP
0.7
0.7
0.7
0.7
0.7
25
50
25
50
25
50
25
50
25
50
Inf. Time
(ms)
Inf. Time (ms)
Inf.
Time (ms)
Inf. Time (ms)
Inf. Time (ms)
(a) FR
Ass-Hius
ALP ligument
Earl
Nun-tsjertive Tujertioo
Hinge Produuct Naural
Agc- NTN
Nodi
0.8
0.8
0.8
0.8
0.8
MAP
0.7
0.7-
0.7-
0.7
25
50
50 Inf. Time (ms)
25
50
50
25
6o
Inf. Time
(ms)
Inf.
Time (ms)
Inf. Time (ms)
Inf.
Time (ms)
(b) MM
Agg-Hiisg
Asy-MLP Alggmeett
Early
Non-Tajective Injective
Hingo Neural
Edge
Procluct
0.8
0.8
0.8
0.8
0.8
MAP
0.7
0.7
0.7
25
25
25
75
25
Inf:
Time
(ins)
Inf. Time (mus) +
Inf.
Tine (mus)
Inf.
Time (mus)
Inf. Time (ms) +
(c) MR
Aua-
MLP Sul- Aliggment
Early Latt
Non Injective Injectivo
Edge
Ase-NTN
Dot Produuc Neural
Node
0.42
0.42
0.12
0.12
0.42
MAP
0.40
0.40
0.40
0.40
0.40
2i5
75
50
25
7/s
25
74
2/s
50
75
Inf.
Time (ms)
+
Inf. Time (ms)
Inf.
Time (ms)
Inf.
Time (ms)
Inf. Time (ms)
(d) MSRC
Aug- Hinge Auge- NTN
Agg-MIPP Set- Aligument
Early Late
Now- Injective Injective
Hinge Dot Producct Neural
Kidge
Node
MAP
0.60
0.60-
0.60-
0.60-
0.60
0.55
0.55
0.55
0.55
0.55
225
50
70
225
30
225
50
70
25
50
75
25
50
76
Time (ms)
Time (ms))
Inf.
(ms)
Inf.
(ms)
Time (ms)
(e) MCF
Figure 6: Scatter plot of MAP versus inference time for different design choices. Each point represents unique combination of design axes, with colors indicating variations in relevance distance, interaction structure, stage, non-linearity, and granularity.
25

---

Published as a conference paper at ICLR 2025
F.4 COMPARISON WITH BASELINES ON OTHER DATASETS
In Table 2 of the main paper, we compared the optimal configuration from our design space exploration against state-of- tf-the--rt baselines across five datasets. Here, we extend these comparisons to all 10 datasets. Table 5 details the design choices made by each baseline according to our specified design axes, highlighting that they occupy only sparse regions of the design space. Table 6 presents the full performance results, reaffirming our previous observations. Specifically, (1) our best early interaction model Early-Beett)) consistently outperforms all other methods across datasets, and (2) models utilizing set alignment consistently surpass those relying on aggregated heuristics. (3) Despite using an Injective structure with Set align. relevance distance, GOTSim performs poorly because it uses Hungarian solver (instead of Sinkhorn iterations) which doesn't t allow end-to-end differentiability.
Model
Rel. Dist.
Structure
Non- Non-linearity Granularity
SimGNN (Bai et al., 2019)
Agg-NTN
NA
NA
Node
GraphSim (Bai ct al., 2020)
Agg-MLP
NA
NA
Node
GOTSim (Doan et al., 2021)
Set align.
Injective
Neural
Node
ERIC (Zhuo and Tan, 2022)
Agg-NTN
NA
NA
Node
Late
EGSC (Qin et al., 2021)
Agg-MLP
NA
NA
Node
GREED (Ranjan et al., 2022)
Agg-hinge
NA
NA
Node
GEN (Li ct al., 2019)
Agg-hinge
Non-injective NA
Dot Product
Node
NeuroMatch (Lou al., 2020)
Agg-hinge
NA
Node
IsoNet (Roy et al., 2022)
Set align.
Injective Injective
Neural
Edge
Our-Late-Best
align.
Hinge
Edge
Early
H2MN (Zhang et al., 2021)
Agg-MLP
Non-injective Non-injective
Dot Product
Edge
GMN- (Li et al., 2019)
Agg-hinge
Dot Product
Node
Our-Early-Best
Set align.
Injective
Hinge
Edge
Table 5: Choices corresponding to different design axes for state-of-the-art subgraph matching methods.
Model
AIDS
Mutag
FM
NCI
MOLT
SimGNN
0.326 + 0.019
0.303 0.012
0.005
0.39 + 0.018
0.421 + 0.015
GraphSim
0.173 : 0.007
0.182 2: 0.008
0.468 0.201
0.016
0.499 -
GOT'S
0.336 + 0.017
0.387 + 0.018
+0018
0.382 0.017
0.462 + 0.015
ERIC
0.512 0.022
0.558 + 0.027
0.019
0.006
0.549 0.016
0.016
Late
EGSC
0.5:2.0022
0.446 - 0.021
0.018
0.019
0.555 = 0.016
GREED
0.502 = 0.022
0.551 = 0.026
0.019
0.019
0.507 = 0.017
GEN
0.557 = 0.023
0.591 + 0.03
1.022
0.529 0.019
0.537 0.018
NeuroMatch
0.454 + 0.025
0.583 0..27
0.622
+
0.552
0.017
IsoNet
0.704 0.021
0.733 1 0.023
0.782 + 0.017
0.615 = 0.019
0.649 1 0.016
Late-Best
0.712 0.018
0.721 + 0.025
0.793 + 0.016
0.643 + 0.02
0.662 + 0.016
Early
H2MN
0.267 + 0.014
0.282 + 0.012
0.364 + 0.016
0.381 + 0.015
0.405 + 0.013
GMN-Mateh
0.609 + 0.02
0.693 + 0.026
0.686
+ 0.018
0.588 + 0.019
0.603 = 0.018
Early-Best
0.817 + 0.017
0.837 + 0.02
0.887 + 0.012
0.677 + 0.02
0.71 + 0.018
Model
FR
MM
MR
MSRC
MCF
SimGNN
0.355 = 0.015
0.358 0.015
0.308 4 0.017
0.237 1 0.008
0.141 = 0.006
GraphSim
0.165 = 0.007
0.2 0.009
0.006
0.348 + 0.011
0.43 143=0000 0.016
GOTSim
0.361 = 0.013
0
0.210 0.001
0.352 0 0.016
ERIC
0.572 0.021
0.573 = 0.02
0.639
0.364
0.502 0 0.017
Late
HGSC
()6022 + 0.02
0.583 1 00009
0.576
0.358
0.47 + 0.019
GREED
0.549 + 0.022
+
0.561 +002
0.35
0.33 + 0.019
GEN
0.577 = 0.022
0.579 = 0.02
0.019
0.385
0.011
0.492 0.018
NeuroMatch
0.572 + 0.023
0.522 0.019
0.565
0.359
0.011
0.463 0.019
IsoNet
0.734 - 0.02
0.758 + 0.016
0.764 + 0.015
0.411 = 0.012
0.587 1 0.019
Our-Late-Bess
0.744 0.019
0.758 + 0.015
0.782 + 0.014
0.397
0.013
0.572 0.02
Early
H22MN
0.285 = 0.011
0.308 = 0.015
0.371
0.265
+ 0.009
01273 = 0.016
GMN-Match
0.667 + 0.021
0.627 + 0.02
0.683 + 0.017
0.416 1 0.012
0.549 - 0.018
Our-Early-Best
0.854 + 0.013
0.849 + 0.012
0.864 + 0.011
0.424 0.012
0.64 + 0.018
Table 6: Comparison of MAP between our best combination of choices across different design axes, for both early (Our-Early-Best) and late (Our-Late-Best) interaction and state-of of-te-of-the-ar subgraph matching methods. Green, Blue and Yellow cells indicate best early, best late and second- becond-best late interaction methods.
26

---

Published as a conference paper at ICLR 2025
F.5 EXPLORATION THROUGH ALL POSSIBLE COMBINATIONS IN DESIGN SPACE
In this section, we present the detailed numerical data used to generate the bar plots in Figure 2. Fol- lowing the analytical framework established in Figure 2, we categorize the runs into four components: Late Node, Late Edge. Early Node, and Early Edge. Within each component, we provide separate tables that group the runs along the three design axes: relevance distance, interaction structure, and interaction nonlinearity. We will analyze each of these tables in turn.
Analysis of Late Node Interaction along Relevance Distance Design Choices In Table 28, we observe: (1) For eight datasets, one of the networks using the Set align. distance emerges the best performer indicating its compatibility with late interaction. (2) Agg-NTNN distance is the second best alternative, winning two datasets and demonstrating competitive performance across others. (3) Agg-hinge& & Agg-MLP distances consistently fail to match the performance of the previously mentioned relevance distances in any of the datasets.
Rel. Dist.
Structure
Non-linearity
AIDS
Mutag
NCI
MOLT
Agg-hinge
NA
NA
0.537 0. 023
0.591 0.03
0,636 0.022
0.329 0.019
0.537 0.018
Agg-MLP
NA
NA
0.548 :: 0.022
0.64 = 0.028
0.674 0.019
0.566 1: 0.019
0.575 + 0.018
Agg NTN
NA
0.576 0.023
0.708
0.027
0.744 4: 0.019
0.612 0.019
0.627 0.018
Set align.
Non-injective
Dot Product
0.0:2.002.
0.652 + 0.027
0.702 0.021
0.598 0.02
0.617 = 0.017
Set align.
Non injective
Hinge
0.636 1: 0.022
0.647
0.027
0.694
0.022
0.617 = 0.019
0.616 1 0.017
Set align.
Non-injective
Neural
0.635 0.022
0.681 0.026
0.736
+ 0.017
0.605-00009
0.609 0.017
Set align.
Injective Injective
Dot Product
0.631 0.002
0.66 = 0.026
0.722 + 0.019
0.608
2 0.019
0.612 0.016
align.
Hinge
0.633
0.647
0.72 0.019
0.625
0.019
0.622 = 0.017
Set align.
Injective
Neural
0. 0.6641 + 0.021
0.69 + 0.026
0.758 + 0.017
0.612 0.019
0.621 = 0.017
Rel. Dist.
Structure
Noa-lincarity
FR
MM
MR
MSRC
MCF
Agg hinge
NA
NA
0.577 0.022
0.579 + 0.02
0.618 0.019
0.385 + 0.011 1
0.492 + 0.018
Agg-MLP
NA
NA
0.608 0.023
0.577 + 0.02
0.605 0.018
0.368 + 0.011
0.528 0.02
Agg NTN
NA
NA
0.674 1: 0.022
0.663 0.023
0.707 1: 0.018
0.409 1: 0.011
0.552 -: 0.02
Set align.
Non-injective Non-injective
Dot Product
0.621 4.62140.024
0.019
0.681 0.02
0.403 0.012
0.56 + 0.021
Set align.
Hinge
0.63
0.701 = 0.02
0.392
0.012
0.577 = 0.019
Set align.
Non-injective Injective Injective
Neural
0.689 0.021
0.705
0.741 + 0.017
0.399 1:99:000 0.012
0.58 = 0,019
Set align.
Dot Product
0.62 1: 0.023
0.664 0.019
0.643 1:6431100 0.019
0.415 = 0.012
0.57 1 0.019
Set align.
Hinge
0.652 = 0.024
0.72
0 + 0.018
0,399 + 0.012
0.574 = 0.019
Set align.
Injective
Neural
0.683 1: 0.022 0.711::0.00
0.738 1: 0.017
0.41 1 0.012
0.576 0.019
Table 7: Comparison of different relevance distances for late interaction models with node-level granularity across ten datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
Analysis of Late Edge Interaction along Relevance Distance Design Choices In Table 8, we observe: (1) Similar to node- granulataularttt networks in Table 28, Set align. distance the best per- forming alternative, followed by Agg-NTN. (2) Ainghinge&& & Agg distances again demonstrate significantly weaker performance compared to the other alternatives.
Rel. Dist.
Structure
Non- -ineaiiaaitty
AIDS
Mulag
FM
NCI
MOLT
Agg. Agg-hinge
NA
0.635 0.024
0.684 + 0.028
0.712 0.018
0.560 0.02
0.571 0.019
Agg-MLP
NA
NA
0.607 0.024
0.63 = 0.029
0.727 = 0.02
0.601
+603100011
Agg-NTN
NA
NA
0.66 + 0.026
0.718 0.0277
0.759 0.019
0.627
0.019
0.653 + 0.019
Set align.
Non-injective Non-injective
Dot Product
0.681 0.022
0.681
0.719
0.019
0.017
Set align.
Hinge
0.702 0.001
0.687:10.02
0,771 0.016
0.631 0.021
0.638
- 0.017
Set align.
Non-injective Injective Injective Injective
Neural
0.7
0.713 0.025
0.77 1: 0.017
0.02
0.618
0.017
Set align.
Dot Product
0.68 + 0.021
0.712 0.006
0.755 + 0.016
0.623
0.02
0.631 = 0.018
Set align.
Hinge
0.712 0.018
0.721
1 0.025
0.793
1: 0.016
0.643 0.02
0.662 1 0.016
Set align.
Neural
0.704 1 0.021
0.733
1 0.023
0.782 1: 0.017
0.615
0.019
0.649 1 0.016
Rel. Dist.
Structure
Non- -ineaiicyr
FR
MM
MR
MSRC
MCF
Agg-hinge
NA
NA
0.086 0.022
0.685
0,709 0.019
0.389 +: 0.012
0.51 + 0.019
Agg-MLP
NA
0.66020.022
0.609 +: 0.02
0.669 - 0.02
0.368 0.011
0.561 = 0.019
Agg-NIN
NA
NA
0.716 0.021
0.671200001
0.721 0.02
0.414 0.012
0.581
Set align.
Non-in injective
Dot Product
0.693 :: 0.022
0.702 0.019
0.723 0.019
0.411 1 0.012
0.571 0.02
Set align.
Non-injective
Hinge
0.731 0.018
0.735
+ 0.017
0.776 + 0.017
0.412
0.012
0.609 + 0.018
Set align.
Non-injective Injective Injective
Neural
0.716 0.02
0.721 17211:00 0.016
0.707
0.403
1: 0.011
0.572 1 0.019
Set align.
Product
0.719 +: 0.02
0.018
0.735
0.018
0.404
0.012
0.58 + 0.019
Set align.
Hinge
0.744
0.758
+ 0.015
0.782 + 0.014
0.397
+ 0.013
0.672 0.02
Set align.
Injective
Neural
0.00
0.758 + 0.016
0.761 0.015
0.411 + 0.012
0.587 = 0.019
Table 8: Comparison of different relevance distances for late interaction models with edge-level granularity across ten datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
27

---

Published as a conference paper at ICLR 2025
Analysis of Early Node Interaction along Relevance Distance Design Choices In Table 9 and Table 10, we observe: (1) The Set align. and Agg-NTN distances dominate in the presence of injective and non-injective networks, respectively. (2) The Agg- hinge distance generally performs the worst among the alternatives. (3) The Agg-MI.P method demonstrates mediocre performance, falling between the former two and the latter across datasets and base networks.
Relevance Distance 1
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Stage Early; Structure
Injective; Non-linearity Dot Product: Gramularity Node
Agg-hinge
0.64 + 0.019
0.75 + 0.023
0.79 + 0.016
0.619 = 0.019
0.63 + 0.018
Agg-MLP
0.658 + 0.019
0.768 +: 0.023
0.806 + 0.016
0.641 + 0.019
0.649 + 0.017
Agg-NTN
0.721 = 0.019
0.772 0.022
0.812 = 0.016
0.626 = 0.019
0.636 + 0.018
Set align.
0.71 + 0.019
0.779 0.022
0.8 + 0.017
0.632 + 0.02
0.652 0.017
Fixed axes: Stage Early; Structure Injective:
Non-linearity
Hinge; Granularity
Node
Agg-hinge
0.662 1 0.019
1.744:0.022
0.785 0.017
0.624
0.635 1 0.018
Agg-MLP
0.683 + 0.019
0.757 = 0.023
0.785 + 0.016
0.629
0.627 = 0.018
Agg-NTN
0.743 0.018
0.773
0.805 0.016
0.615 = 0.019
0.629 0.017
Set align.
0.774
0.834 0.016
0.64
0.647 + 0.018
Fixed axes:
-laly; Structure -Injectte-,jecvivee;; Injective;
Non-linearity - Neural; Granularity
Node
Agg- Singeinge
0.614 0.021
0.736 + 0,025
0.779 0.017
0.613
0.637 0.019
Agg-MI.P
0.629 + 0.021
0.764 + 0.024 0.024
0.777 + 0.016
0.626 0.02
0.641 1 0.017
Agg-NTN
0.667 + 0.02
0.791 + 0.021
0.828 + 0.015
0.629
0.651 + 0.018
Set align.
0.69 - 0.02
0.783 0.023
0.827 0.015
0.654
0.659 +:59:00 0.018
Fixed axes: Stage
Early; Structure
Non-injective; Non-linearity
Dot Product: Granularity Node
Agg-hinge
0.609 =
0.693 + 0.026
0.686 = 0.018
0.588
0.603 0.018
Agg-MLP
0.63 = 0.022
0.713 + 0.025
0.765 0.016
0.593 0.019
0.619 - 0.017
Agg-NTN
0.669 0.022
0.742 0.025
0.05
0.602 0.019
0.628 1 0.017
Set align.
0.608 + 0.022
0.754 :: 0.024
0.759 - 0.017
0.603 - 0.019
0.62 + 0.017
Fixed axes: Stage
Early; Structure
Non-injective:
Con-liiearity
Hinge; Granularity
Node
Agg-hinge
0.726 + 0.02
0.723 + 0.026
0.79 + 0.016
0.618 1618+000011 0.019
0.651 + 0.018
Agg-MLP
0.637 + 0.021
0.725 + 0.024
0.808 + 0.015
0.63 0.02
0.636 + 0.017
Agg-NTN
0.686 0.019
0.758 0.022
0.818 0.015
0.641 = 0.02
0.664 0.017
Set align.
0.676 + 0.022
0.669 + 0.024 0.772 + 0.018
0.599 + 0.02
0.637 = 0.018
Fixed axes: Stage
Early; Structure
Non-injective;
Iin-aine
Neural: Granulanty
Node
Node
Agg-hinge
0.598 + 0.021
0.694 + 0.025
0.712 + 0.019
0.591 = 0.019
0.629 - 0.018
Agg-MLP
0.629 + 0.023
0.715 + 0.025
0.769 - 0.017
0.623 + 0.018
0.627 - 0.018
Agg-NTN
0.635 + 0.025
0.755 + 0.025
0.796 + 0.016
0.633 + 0.019
0.641 + 0.017
Set align.
0.593 + 0.021
0.748 + 0.025
0.772 + 0.016 0.614 0.019
0.646 + 0.017
Table 9: Comparison of different relevance distances for early interaction models with node-level granularity across first five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset..
28

---

Published as a conference paper at ICLR 2025
Relevance Distance |
FR
MM
MR
MSRC
MCF
Fixed axes: Stage
Early; Structure
Injective; Non -ineaiinerr Dot Product; Granularity
Node
Agg- -inng
0.73 + 0.019
0.699 + 0.019
0.736 +: 0.016
0.423 = 0.012
0.674
Agg-MLP
0.751 + 0.018
0.741 -: 0.017
0.809 - 0.014
0,431 + 0.012
0.577 2 0.019
Agg-NTN
0.764 = 0.019
0.748 + 0.017
0.796 - 0.015
0.426 = 0.012
0.583 + 0.019
Set align.
0.774 + 0.017
0.736 + 0.017
0.803
0.014
0.436 0.012
0.593 0.019
Fixed axes: Stage Early; Structure Injective:
Non-linaarity
Hinge; Granularity
Node
Agg-hinge
0.733 + 0.021
0.713
0.018
0.752 0.018
0.403 0.011
0.575 + 0.02
Agg-MLP
0.75 0.75 0.019
0.017
0.781 + 0.016
0.42 0.011
0.603
0.019
Agg-NTN
0.768 0.019
0.755 + 0.017
0.798
0.015
0.422 0.012
0.571 0.019
Set align.
0.774 0.017
0.759 + 0.016
0.806 0.013
0.426 0.012
0.584 0.019 Node
Fixed axes: Stage -Farly; Structure Injective; Non-linearity - Neural; Granularity
Agg-hinge
0.73 0.02
0.018 0.712 + 0.018
0.733 = 0.017
0.417 1 0.011
0.579 0.019
Agg-MLP
0.772 = 0.017
0.707 + 0.018
0.785 = 0.015
0.416 = 0.011
Agg-NTN
0.766 0.019
0.748
0.8 0.015
0.409 = 0.011
0.584 + 0.019
Set align.
0.746 + 0.019
0.764 0.016
0.776 + 0.015
0.433 + 0.012
0.613 0.019
Fixed axes: Stage-
Early; Structure-
Non-injective; Non-linearity Dot Product; Gramularity Node
Agg-hinge
0.667 + 0.021
0.627 + 0.02
0.683 0.017
0.416 0.012
Agg-MI.P
0.687 + 0.00
0.678 + 0.018
0.741 0.017
0.42 + 0.011
0.562 0.019
Agg-NTN
0.715 + 0.021
0.711
0.762 - 0.017
0.415 = 0.011
0.571 + 0.019
Set align.
0.706 + 0.02
0.691 =
0.715
0.423 0.012
0.553 = 0.019
Fixed axes: Stage
Early; Structure
Non-injective; Non-lineariyy
Hinge; Granularity - Node
Agg-hinge
0.75
0.018
0.787 0.015
0.414 0.012
0.584 = 0.02
Agg-MLP
0.744 0.02
0.773 0.018
0.41 0.011
0.586 +: 0.02
Agg-NTN
0.765 0.019
0.766 0.016
0.014
0.409 - 0.012
0.572 + 0.02
Set align.
0.678 + 0.022
0.711 + 0.018
0.768 + 0.017
0.419 + 0.012
0.601 0.02
Fixed axes: Stage
Early; Structure
Nonn:ijeetvee.NNonnneeiiiy
Neural: Gramularity
Node
Agg-hinge
0.674 t 0.022
0.643 + 0.02
0.662 + 0.02
0.401 = 0.011
0.554 = 0.019
Agg-MLP
0.698 + 0.021
0.698 + 0.018
0.739 - 0.018
0.415 0.012
0.575 + 0.019
Agg-NTN
0.707 = 0.021
0.701 + 0.019
0.408 = 0.011
0.586 + 0.018
Set align.
0.719 + 0.02
0.703 + 0.019
0.742 + 0.016
0.416 + 0.012
0.579 + 0.018
Table 10: Comparison of different relevance distances for early interaction models with node-level granularity across last five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset..
29

---

Published as a conference paper at ICLR 2025
Analysis of Early Edge Interaction along Relevance Distance Design Choices In Table 11 and Table 12, we observe: (1) Set align. consistently outperforms Agg-NTN, regardless of the interaction structure. The only exception is found in non-injective networks utilizing Hinge non-linearity, where their performances are comparable. (2) Notably, the top-performing early interaction network identified in our study, which surpasses all others across nine datasets, employs Set align. as its relevance distance in conjunction with Hinge non-linearity.
Relevance Distance
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Stage
Early: Structure
Injective; Non linearity Dot Product; Granularity Edge
Agg-hinge
0.755 + 0.019
0.763 + 0.025
0.826 + 0.014
0.636 + 0.02
0.67 + 0.019
Agg-MI.P
0.758 + 0.019
0.773 + 0.023
0.853 + 0.014
0.662 + 0.02
0.683 + 0.017
Agg-NTN
0.74 + 0.02
0.783 0.023
0.833 + 0.015
0.655 : 0.02
0.672 = 0.018
Set align.
0.798 0.019
0.789 0.023
0.862 0.015
0.674 0.019
0.688 0.018
Fixed axes: Stage - Early; Structure - Injective;
Non-linearity
Hinge; Granularity
Edge
Agg-hinge
0.758 + 0.019
0.78 + 0.023
0.83 1:83:000 0.015
0.661 + 0.02
0.681 + 0.019
Agg-MLP
0.789 + 0.017
0.807 + 0.023
0.871 =: 0.013
0.663 =.02 0.02
0.678 - 0.018
Agg-NTN
0.76 0.019
0.766 + 0.025
0.855 + 0.013
0.653 + 0.021
0.679 + 0.018
Set align.
0.817 0.017
0.837 + 0.02
01887 + 0.012
0.677 + 0.02
0.71 + 0.018
Fixed axes: Stage
Early; Structure Injective:
Non-lineurity Neural; Gramularity
Edge
Agg-hinge
0.68 + 0.022
0.755 + 0.024
0.807 0.016
0.625 + 0.02
0.656 + 0.019
Agg-MLP
0.703 = 0.021
0.738 + 0.026
0
0.643 0.021
0.644 0.019
Agg-NTN
0.689 + 0.022
0.749 + 0.027
0.831 0.015
0.651
0.021
0.661 + 0.019
Set align.
0.725 0.021
0.784 0.023
0.837 = 0.015
0.649 0.019
0.664 1 0.018
Fixed axes: Stage
Farly; Structure
Non-injjctive;
Non-linearity - Dot Product; Granularity Edge
Agg-hinge
0.02
0.734 0.025
0.78 0.018
0.625 + 0.02
0.633 1 0.018
Agg-MI.P
0.677 + 0.022
0.766 + 0.023
0.792 + 0.016
0.638 + 0.019
0.65 + 0.018
Agg-NTN
= 0.71 0.022
0.751 + 0.024
0.815 + 0.016
0.653 - 0.02
0.644 + 0.017
Set align.
0.715 +: 0.021
0.779 + 0.023
0.812 - 0.017
0.635 = 0.019
0.659 + 0.017
Fixed axes: Stage
Early; Structure
Non-injective;
Non-lineyrity
Hinge: Granularity
Edge
Agg-hinge
U.763 + 0.018
0.753 # 0.025
0.831
0.666 = 0.02
0.686 0.017
Age-MLP
0.748 + 0.019
0.778
0.023
0.847 : 0.014
0.658
0.021
0.684 0.018
Agg-NTN
0.091
0.785
0.023
0.835
0.014
0.661
0.683 + 0.018
Set ulign.
0.783 0.017
0.785 0.024
0.807 + 0.015
0.657
0.021 0.696 + 0.018
Fixed axes: Stage
Early; Structure - Nonniijective; Non- Non-linearity-
Neural; Gramularity - Edge
Agg-hinge
0.677 + 0.022
0.729 + 0.025
0.747 + 0.019
0.618 = 0.019
0.633 + 0.018
Agg-MLP
0.662 + 0.024
0.735 + 0.024
0.745 + 0.019
0.629 = 0.02
0.65 + 0.018
Agg-NTN
0.701 0.023
0.734 + 0.028
0.811 = 0.016
0.625 + 0.02
0.648 + 0.019
Set align.
0.708 + 0.022
0.763 + 0.024
0.807 + 0.016
0.648 + 0.019
0.655 + 0.018
Table II: Comparison of different relevance distances for early interaction models with edge-level granularity across first five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
30

---

Published as a conference paper at ICLR 2025
Relevance Distance |
FR
MM
MR
MSRC
MCF
Fixed axes: Stage
Early: Structure
Injective; Non-
- Dot Product; Granularity
Edge
Agg-hin -inneing
0.8 + 0.018
0.777 + 0.018
0.803 + 0.015
0.415 = 0.011
Agg-MLP
0.786 + 0.017
0.791 + 0.016
0.827 = 0.014
0.404 0.011
0.614
Agg-NTN
0.771 + 0.018
0.81 + 0.014
0.858 = 0.012
0.425 - 0.012
0.617 0.018
Set align.
0.817 0.016
0.791 + 0.016
+ 0.014
0.435 0.012
0.63 + 0.018
Fixed axes: Stage Strutue
Structure Injective:
Non-hinarity
Hinge; Granulanity
Edge
Agg-hinge
0.798 + 0.019
0.785 +: 0.016 0.817
0.019 0.012
Agg-MLP
0.815 + 0.016
0.833 0.014
0.851 = 0.011
0.423 = 0.012
0.599 0.018
Agg-NTN
0.824 0.016
0.821 + 0.014
0.811 0.013
0.426 0.012
0.635 0.019
Set align.
0.854 0.013
+.499+00012
0.864
0.011
0.424
0.012
0.64 + 0.018
Fixed axes: Stage Harly; Structure - Injective; Non-linearity
Neural; Granularity
Eddge
Agg-hinge
0.749 + 0.022
0.705 - 0.019
0.766 + 0.016
0.406 = 0.012
0.018 0.018
Agg-MLP
0.771 = 0.019
0.717 0.018
0.795 = 0.016
0.401 = 0.011
0.601 + 0.018
Agg-NTN
0.762 0.02
0.767 0.018
0.802 0.016
0.411 0.012
0.593 + 0.018
Set align.
0.752 = 0.02
0.773
:: 0.016
0.788 + 0.015
0.433 + 0.012
0.609 0.02
Fixed axes: Stage-
Early; Structure-
Non-injective;
Non-lincarity Dot Product; Granularity Edge
Agg-hinge
U.727 0.019
0.706 + 0.02
0.746 +
0.421 0.012
0.601 0.018
Agg-MI.P
U.751 + 0.019
0.723 +.03+000033
0.788 0.016
0.416 + 0.011
0.596 + 0.02
Agg-NTN
0.754 0.019
0.719 1 0.021
0,777
0.016
0.418 1 0.012
0.614 + 0.018
Set align.
0.799 + 0.017
0.789
0.81 0.016
0.421 + 0.012
0.609 + 0.02
Fixed axes: Stage
Early; Structure
Non-injective;
Non-linearity
Hinge; Granularity
Edge
Agg-hinge
0.772 + 0.018
0.799 + 0.015
0.815 0.014
0.423 + 0.012
0.612 + 0.019 0.019
Agg-MLP
0.756 + 0.019
0.787 + 0.015
0.786 0.015
0.416 = 0.012
0.628 + 0.019
Agg-NTN
0.791 0.017
0.8 0.016
0.833 - 0.014
0.421 - 0.011
0.608 + 0.02
Set align.
0.773 0.019
0.814
0.795 + 0.016
0.435 0.012
0.626 + 0.02
Fixed axes: Stage - Early; Structure- - Non-injective;
Non-linearity
Neural: Gramularity - Edge
Agg-hinge
0.704 + 0.022
0.691 + 0.02
0.722 + 0.02
0.422 + 0.011
0.589 + 0.019
Agg-MLP
0.74 : 0.02
0.687 + 0.021
0.732 + 0.02
0.416 = 0.011
0.603 + 0.018
Agg-NTN
0.723 + 0.022
0.704 0.02
0.753 = 0.018
0.419 = 0.012
0.584 + 0.02
Set align.
0.733 + 0.02
0.75 + 0.018
0.782 + 0.017
0.421 + 0.011
0.607 + 0.018
Table 12: Comparison of different relevance distances for early interaction models with edge-level granularity across last five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
31

---

Published as a conference paper at ICLR 2025
Analysis of Late Node Interaction along Interaction Structure Design Choices In Table 13, we observe: (1)The Injective structure is the preferred option across all con-lincarities, achieving victories in more than five datasets in each instance. (2)The Non-injective structure is also highly competitive and, in some cases, significantly outperforms Injective, particularly evident in the MR under the Dot Product non-linearity.
Interaction Structure 1
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist. Set align.; Stage Late; Non-lincarity - Dot Product; Granularity Node
Non-injective
0.6 0.023
0.652 + 0.027 0.702 0.021
0.598 + 0.02
0.617 1 0.017
Injective
0.631 + 0.022
0.66 0.026
0.722 + 0.019
0.608 + 0.019
0.612 0.016
Fixed axes: Rel. Dist. Set align.; Stage - Late; Non-linearity Hinge; Granularity
Node
Non-injective
0.636 + 0.022
0.647 + 0.027
0.694 + 0.022
0.617 = 0.019
0.616 + 0.017
Injective
0.633 + 0.021
0.647 + 0.028
0.72 = 0.019
0.625 + 0.019
0.622 + 0.017
Fixed axes: Rel. Dist. Set align.: Stage Late; Non- linearity Neural: Granularity
Node 0.609 0.017
Non-injective
0.635 + 0.022
0.681 + 0.026
0.736 + 0.017 0.605 0.019
Injective
0.664 + 0.021
0.69 + 0.026 0.758 = 0.017 0.612 + 0.019
0.621 + 0.017
Interuction Structure 1
FR
MM
MR
MSRC
MCF Node
Fixed axes: Rel. Dist. Set align.; Stage Late; Non-lincarity Dot Product; Granularity
Mooniinecctive
0.621 + 0.024
0.671 : 0.019 0.681 0.02
0.403 0.012
0.56 1 0.021
Injective
0.62 + 0.023
0.664 0.019 0.643 1 0.019
0.415 + 0.012
0.57 = 0.019
Fixed axes: Rel. Dist. Set align.; Stage - Late; Non-linearity Hinge; Granularity
Node
Non-injective
0.645 1 0.024
0.634 + 0.021
0.701 + 0.02
0.392 = 0.012
0.577 16771100011
Injective
0.652 + 0.024
0.72 + 0.017
0.694 + 0.018
0.399 + 0.012
Fixed axes: Rel. Dist. Set align.; Stage Late; Non- linearity Neural, Granularity
Node
Non-injective 0.689 + 0.021
0.705 + 0.019
0.741 = 0.017 0.399 0.012
0.58 = 0.019
Injective
0.683 + 0.022
0.711 + 0.017 0.738 + 0.017
0.41 + 0.012
0.576 + 0.019
Table 13: Comparison of different interaction structures for late interaction models with node-level granularity across ten datasets, using mean average precision (MAP). Green cells indicate the best methods respectively for the corresponding datasets.
Analysis of Late Edge Interaction along Interaction Structure Design Choices In Table 14, we observe: (1) The Injective structure continues to demonstrate superior performance, with one of its models utilizing Hinge non-linearity emerging as the best-performing late interaction network in our study. (2) While the Non-injective structure remains competitive, its effectiveness relative to Injective diminishes as we transition from Dot Product to Hinge and finally to Neural, ultimately resulting in no datasets won.
Interaction Structure ||
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist.
Set align.; Stage Late; Non-lineante Dot Product; Granularity
Edge
Non-injective
0.681 + 0.022
0.681 + 0.026 0.759 + 0.019 0.611 0.019 0.621
0.017
Injective
0.68 + 0.021
0.712 + 0.026 0.755
0.016
0.623 0.02
0.634 + 0.018
Fixed axes: Rel. Dist. Set align.: Stage Late; Non-linearity - Hinge: Gramularity
Edge
Non-injective
0.702 + 0.021
0.687 + 0.027 0.774 + 0.0T6
0.631 + 0.021
0.638 t 0.017
Injective
0.712 + 0.018
0.721 + 0.025
0.793 + 0.016 0.643 0.02
0.662 + 0.016
Fixed axes: Rel. Dist. Set align.; Stage Late; Non-linearin
Neural; Granularity
Edge
Non-injective
0.7 + 0.022
0.713 + 0.025
0.77 # 0.017 0.609 + 0.02
0.618 0.017
Injective
0.704 + 0.021
0.733 + 0.023
0.782 + 0.017 0.615 + 0.019 0.649 + 0.016
Interaction Structure 1
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist. Set align.; Stage Late; Non-linearity Dot Product; Granularity
Edge
Non-injective
0.693 + 0.022
0.702 = 0.019 0.723 0.019 0.111
0.571 = 0.02
Injective
0.719 + 0.02
0.676 0.018 0.735 = 0.018 0.404 0.012
0.58 = 0.019
Fixed axes: Rel. Dist. Set align.: Stage Late; Mon-linearity - Hinge; Gramularity
Edge
Non-injective
0.731 + 0.018
0.735 + 0.017 0.776 + 0.017
0.412 + 0.012
0.609 + 0.018
Injective
0.744 + 0.019
0.758 + 0.015 0.782 + 0.014
0.397 + 0.013
0.572 + 0.02
Fixed uxes: Rel. Dist. Set align.; Stage Late: Non- linearity Neural; Granularity
Edge
Non-injective 0.716 0.02
0.721 + 0.016 0.757 1 0.017 0.403 0.011
0.572 0.019
Injective
0.734 + 0.02
0.758 + 0.016 0.764 # 0.015 0.411 + 0.012 0.587 + 0.019
Table 14: Comparison of different interaction structures for late interaction models with edge-level granularity across ten datasets, using mean average precision (MAP). Green cells indicate the best methods respectively for the corresponding datasets.
32

---

Published as a conference paper at ICLR 2025
Analysis of Early Node Interaction along Interaction Structure Design Choices In Tables 15 and 16, we observe: Networks with injective structures consistently outperform those with non- injective structures, with few notable exceptions.
(1) The relevance distance using Agg-hinge with (2) The relevance distance using Agg-NTNN with non- linearity Hinge wins in six datasets. (3) The relevance distance using Agg-MLP with non-linearity Hinge wins in three datasets. These observations lead us to conclude that non-injective structures tend to perform well when paired with Hinge non-linearity.
non-linearity Hinge wins in eight datasets.
Interaction Structure |
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist. - Agg-hinge: Stage Early; Non-linearity Dot Product: Granularity Node
Non-injective
0.609 0.02
0.693 + 0.026 0.686 + 0.018
0.588 0.019
0.603 0.018
Injective
0.64 0.64+0.019 0.019
0.75 + 0.023
0.79 + 0.016
0.619 + 0.019 0.63 + 0.018
Fixed axes: Rel. Dist. Agg-hinge;
Stage Early; Non-limearity Hinge; Gramulanity
Node
Non-injective
0.726 + 0.02
0.723 + 0.026
0.79 + 0.016
0.618 + 0.019 0.651 + 0.018
Injective
0.662 + 0.019
0.734 + 0.025
0.785 + 0.017
0.624 0.02 0.635 + 0.018
Fixed axes: Rel.
Dist, Agg-hinge;
Stuge Early; Non-linearity Neural: Granularity
Node
Non-injective
0.598 1: 0.021
0.694 + 0.025
0.712 0.019 0.591 = 0.019 0.629 0.018
Injective
0.614 + 0.021
0.736 1 0.025
0.779 + 0.017
0.613 = 0.02 0.637 + 0.019
Fixed axes: Rel. Dist. Agg--LMM Stage Early; Non-lineariyy Dot Product: Gramularity Node
Non-injective
0.63 + 0.022
0.713 0.025 0.765 + 0.016 0.593 0.019 0.619 0.017
Injective
0.658 + 0.019
0.768 + 0.023 0.806 + 0.016 0.641 + 0.019 0.649 + 0.017
Fixed axes: Rel. Dist. ALL Stage - Early: Non-lincarty Hinge; Granularity Node
Non- Non-injective
0.637 + 0.021
0.725 + 0.024 0.808 + 0.015 0.63 + 0.02 0.636 + 0.017
Injective
0.683 +: 0.019
0.757 + 0.023 0.785 + 0.016 0.629 + 0.019 0.627 + 0.018
Fixed axes: Rel. Dist. Agg-MLP:
Stage Early; Non-lincarity Neural; Gramularity
Node
Non-injective
0.629 + 0.023
0.715 - 0.025 0.769 0.017 0.623 0.018 0.627 0.018
Injective
0.629 + 0.021
0.764 1 0.024 0.777 = 0.016
0.626 0.02 0.641 + 0.017
Fixed axes: Rel. Dist. Set align.:
Stage - Early; Non-linearty- Dot Product: Granularity Node
Non-injective
0.608 + 0.022
0.754 0.024 0.759 + 0.017 0.603 0.019 0.62 E 0.017
Injective
0.71 0.019
0.779 + 0.022
0.8 0.017
0.632 = 0.02 0.652 + 0.017
Fixed axes: Rel. Dist. - Set align.; Stage Early; Non-linearity - Hinge; Granularity
Node
Non-injective
0.676 1 0.022
0.669 + 0.024 0.772 + 0.018
0.599 + 0.02 0.637 + 0.018
Injective
0.734 + 0.019
0.774 + 0.023 0.834 = 0.016
0.64 + 0.019 0.647 + 0.018
Fixed axes: Rei. Dist. Set align.: Stage Farly; Non-lineariyy Neural; Gramularity
Node
Non-mnjective
0.593 1:200 0.021
0.748 + 0.025 0.772 0.016
0.614 0.019 0.646 0.017
Injective
0.69 + 0.02
0.783 + 0.023 0.827 = 0.015
0.654 1 0.019 0.659 + 0.018
Fixed axes: Rel. Dist. - Agg-NTNN Stage Early; Non-lineariyy Dot Product; Granularity Node
Non- Non-injective
0.669 + 0.022
0.742 : 0.025 0.75 + 0.016 0.602 0.019 0.628 0.017
Injective
0.721 = 0.019
0.772 - 0.022
0.812 - 0.016 0.626 1 0.019 0.636 1 0.018
Fixed axes: Rei. Dist. Agg-NTN; Stage - Early; Non-lincarity Hinge; Gramularity - Node
Non- Non-injective
0.686 1 0.019 0.758 + 0.022 0.818 + 0.015
0.641 = 0.02 0.664 0.017
Injective
0.743 + 0.018
0.773 + 0.024 0.805 + 0.016
0.615 0.019 0.629 + 0.017
Fixed axes: Rel. Dist. Agg-NTN; Stage Early; Non-lincarity Neural; Granularity
Node
Non-injective
0.635 = 0.025
0.755
0.025
0.796 0.016 0.633 = 0.019 0.641 0.017
Injective
0.667 + 0.02 0.791 0.021 0.828 = 0.015 0.629 0.019 0.651 # 0.018
Table 15: Comparison of different interaction structures for early interaction models with node- level granularity across first five datasets, using mean average precision (MAP). Green cells indicate the best method for the corresponding datasets.
33

---

Published as a conference paper at ICLR 2025
Interaction Structure
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist. Agg-hinge: Stage Early; Non- Non-linearity Dot Product; Granularity Node
Non-injective
0.667 + 01.21
0.627 + 0.02 0.683 + 0.017 0.416 + 0.012 0.549 + 01.118
Injective
0.73 0.019
0.699 + 0.019 0.736 + 0.016 0.423 + 0.012 0.574 0.018
Fixed axes: Rel. Dist. Agg- hinge: Stage Early; Non-linearity
Hinge; Granularity
Node
Non-injective
0.75 0.018
0.723 + 0.018 0.787 + 0.015 0.414 + 0.012 0.584 t 0.02
Injective
0.733 + 0.021
0.713 + 0.018 0.752 + 0.018 0.403 0.011 0.575 = 0.02
Fixed axes: Rel. Dist. Agg-hinge;
Stuge Early; Non-linearity Neural, Gramularity
Node
Non-injective
0.674 1: 0.022
0.643 0.02 0.662 1 0.02 0.401 0.011 0.534 0.019
Injective
0.73 + 0.02
0.712 + 0.018 0.733 + 0.017 0.417 1 0.011 0.579 1 0.019
Fixed axes: Rel. Dist. - Age-MLP: Stage Early; Non- Von-linearity Dot Product; Granularity Node
Non-injective
0.687 + 0.02
0.678 + 0.018 0.741 + 0.017 0.42 + 0.011 0.562 + 0.019
Injective
0.751 + 0.018 0.741 + 0.017 0.809 + 0.014
0.431 + 0.012 0.577 + 0.019
Fixed axes: Rel. Dist. Agg-MLPP Stage Early: Non-linerrin
Hinge; Granularity Node
Non-injective
0.744 + 0.02
0.71 + 0.018 0.773 + 0.016 0.41 = 0.011 0.586 = 0.02
Injective
0.75 0.019
0.774 0.017
0.781 = 0.016 0.42 + 0.011 0.603
Fixed axes: Rei. Dist. Agg-MLP:
Stage- Early Non-lincarity Neural; Granularity
Node
Non-injective
0.698 1. 0.021
0.608 1 0.018 0.730 0.018 0.415 0.012 0.575 0.019
Injective
0.772 = 0.017
0.707 = 0.018 0.785 + 0.015 0.416 + 0.011 1.0911
Fixed axes: Rel. Dist. Set align.: Stage - Early; Non-lineantyy Dot Product: Granularity - Node
Non-injective
0.706 +: 0.02
0.691 + 0.017 0.715 + 0.019 0.423 + 0.012 0.553 + 0.019
Injective
0.774 +: 0.017 0.736 + 0.017 0.803 + 0.014
0.436 + 0.012 0.593 + 0.019
Fixed axes: Rel. Dist. - Set align.; Stage Early; Non-linearity Hinge; Granularity
Node
Non-injective
0.678 + 0.022
0.711 0.018 0.768 + 0.017 0.419 0.012 0.601 0.02
Injective
0.774 + 0.017
0.759 + 0.016 0.806 + 0.013 0.426 1 0.012 0,584 + 0.019
Fixed axes: Rel. Dist. Set -iet align.; Stage Early; Non-lineariyy Neural; Granularity
Node
Non-injective
0.719 00002 0.703 0.019 0.742
0.016 0.416 0.012 0.579 0.018
Injective
0.746 = 0.019
0.764
0.016 0.776 + 0.015 0.433 + 0.012 0.613
Fixed axes: Rel. Dist. Agg-NTN; Stage Early; Non-lineartyy Dot Product; Granularity Node
Non Mojninneettive
0.715 + 0.021 0.711 0.019 0.762 + 0.017 0.415 + 0.011 0.571 + 0.019
Injective
0.764 + 0.019
0.748 + 0.017 0.796 + 0.015
0,426 1 0.012 0,583 + 0.019
Fixed axes: Rel.
Dist. Agg-NTN; Stage - Farly; Non-linearity Hinge; Granularity
Node
Non-injective
0.765 1: 0.019 0.766 + 0.016
0.8 0.014
0.409 0.012 0.572 0.02
Injective
0.768 + 0.019
0.755 - 0.017 0.798 + 0.015 0.422 + 0.012 0.571 0.019
Fixed axes: Rel.
Dist. Agg-NTN; Stage Early; Non-linearity Neural; Granularity
Node
Non-injective
0.707 + 0.021
0.701 1.0019 0.69 + 0.019 0.408 0.011 0.586 + 0.018
Injective
0.766 = 0.019
0.748 = 0.018 0.015 0.409 + 0.011 0.584 0.019
Table 16: Comparison of different interaction structures for early interaction models with node- level granularity across last five datasets, using mean average precision (MAP). Green cells indicate the best method for the corresponding datasets.
34

---

Published as a conference paper at ICLR 2025
Analysis of Early Edge Interaction along Interaction Structure Design Choices In Tables 17 and 18, we observe: (1) Similar to node granularity, several non-injective networks either match or surpass the performance of their injective counterparts, primarily due to the Hinge non-linearity For instance, with relevance distance Agg-hinge and non-linearity Hinge, this configuration wins in six datasets. (2) Additionally, with relevance distance Agg-NTN and non-linearity Hinge, this combination wins in four datasets.
Interaction Structure 1
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist. Agg-hinge; Stage Early; Non- Non-linearity Dot Product; Granularity Edge
Non-injective
0.7 0.022
0.734 0.025
0.78 + 0.018
0.625 + 0.02
0.018
Injective
0.755 0.019
0.763 : 0.025
0.826 + 0.014
0.656 0.02
0.67 0.019
Fixed axes: Rel. Dist. Aig-hinge; Stage Early; Non-lincarity - Hinge; Gramularity
Edge
Non-injective
0.763 + 0.018
0.753 + 0.025
0.831 + 0.015
0.666 = 0.02 0.686 + 0.017
Injective
0.758 +: 0.019
0.78 + 0.023
0.83 + 0.015
0.661 + 0.02 0.681 + 0.019
Fixed axes: Rel. Dist. - Agg-hinge; Stage - Farly; Non-linearity Neural; Granularity
Edge
Non-injective
0.677 + 0.022
0.729 + 0.025
0.747 + 0.019
0.618 = 0.019 0.633 + 0.018
Injective
0.68 = 0.022
0.755 + 0.024 0.807 = 0.016
0.625 = 0.02 0.656 0.019
Fixed axes: Rel. Dist. Agg-MLP, Stage Early; Non-linearity Dot Product, Granularity Edge
Non-injective
0.677 + 0.022
0.766 + 0.023 0.792 + 0.016
0.638 0.019 0.65 0.018
Injective
0.758 +: 0.019
0.773 0.023 0.853 - 0.014
0.662 = 0.02 0.683 0.017
Fixed axes: Rel. Dist. Agg-MLP, Stage Early; Non-linearity Hinge; Granularity
Edge
Non-injective
0.748 1 0.019 0.778 + 0.023 0.847 0.014
0.658 - 0.021
0.018
Injective
0.789 + 0.017 0,807 + 0.023
0.871 = 0.013
0.663 = 0.02
0,678 + 0.018
Fixed axes: Rel.
Dist. Agg-MLP; Stage Early; Non-linearity Neural; Granularity Edge
Non-injective
0.662 + 0.024
0.735 = 0.024 0.745 + 0.019 0.629 + 0.02 0.65 = 0.088
Injective
0.703 + 0.021
0.738 # 0.026
0.815 = 0.015
0.643 = 0.021
0.019
Fixed axes: Rel. Dist. Set align.;
Stage Early; Non-lnerty Dot Product: Granularity Edge
Non-injective
0.715 + 0.021
0.779 0.023 0.812 + 0.017 0.635 0.019 0.659 0.017
Injective
0.798 +: 0.019
0.789 + 0.023 0.862 : 0.015 0.674 0.019 0.688 0.018
Fixed axes: Rel. Dist. Set align.; Stage Farly; Non-linearity - Hinge; Granularity
Edge
Non-injective
0.783 + 0.017
0.785 0.022 0.807 + 0.015
0.657 = 0.021 0.696 0.018
Injective
0.817 + 0.017 0.837 + 0.02 0.887 + 0.012
0.677 = 0.02
0.71 0.018
Fixed axes: Rei. Dist. Set align.; Stage Early; Non linearity Neural; Granularity Edge
Non-injective
0.708 + 0.022
0.763 = 0.021 0.807 + 0.016 0.618 = 0.019 0.655 + 0.018
Injective
0.725 + 0.021
0.784 + 0.023 0.837 + 0.015
0.649 + 01019 0.664 0.018
Fixed axes: Rel. Dist. AAg.-NNNN Stage Early: Non-linearty Dot Product; Granularity Edge
Non-injective
0.71 + 0.022
0.751 0.024 0.815 + 0.016
0.653 + 0.02 0.644 0.017
Injective
0.74 = 0.02
0.783 + 0.023 0.833 + 0.015
0.655 0.02 0.672 0.018
Fixed axes: Rel. Dist. Agg-NTN; Stage - Early; Non-linearity
Hinge; Gramularity
Edge
Non-injective
0.79 = 0.017 0.785 + 0.023 0.835 + 0.014
0.661 0.02 0.683 0.018
Injective
0.76 + 0.019 0.766 + 0.025 0.855 + 0.013
0.653 = 0.021 0.679 + 0.018
Fixed axes: Rel. Dist. Agg- NTN; Stage Early; Non- Non-linearity- Neural; Granularity
Edge
Non-injective
0.701 + 0.023
0.734 + 0.028
0.811 + 0.016 0.625 + 0.02 0.648 0.01
Injective
0.689 + 0.022
0.749 + 0.027
0.831 + 0.015 0.651 + 0.021 +
Table 17: Comparison of different interaction structures for early interaction models with edge- level granularity across first five datasets, using mean average precision (MAP). Green cells indicate the best method for the corresponding datasets.
35

---

Published as a conference paper at ICLR 2025
Interaction Structure |
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist. Agg hinge; Stage Early; Non- Mon-liinerity Dot Product; Granularity Edge
Non-injective
0.727 + 0.019 0.706 + 0.02 0.746 + 0.019
0,421 + 0.002 0.601 + 0.018
Injective
0.8 + 0.018 0.777 + 0.018
0.803 + 0.015
0.415 + 0.011 0.616 0.018
Fixed axes: Rel. Dist. Agg-hinge: Stage Early; Non-linearitg
Hinge; Granularity
Edge
Non-injective
0.772 +: 0.018 0.799 + 0.015 0.815 + 0.014
0.423 + 0.012 0.612
0.019
Injective
0.798 +: 0.019
0.785 + 0.016
0.817 = 0,014
0.421 = 0.012 0.619
Fixed axes: Rel. Dist. Agg-hinge, Stage Early; Non-hineurity - Granularity
Edge
Non-injective
0.704 1: 0.022
0.691 0.02
0.722
0.422 1 0.011 0.589 0.019
Injective
0.749 + 0.022
0.705 + 0.019 0.766 + 0.016 0.406 0.012 0.595 0.018
Fixed axes: Rel. Dist. Aeg-MLPP Stage Early; Non- lineariyy Dot Product; Granularity Edge
Non-injective
0.751 + 0.019 0.723 + 0.019 0.788 + 0.016 0.416 + 0.011 0.596 + 0.02
Injective
0.786 + 0.017 0.791 + 0.016 0.827 + 0.014 0.404 + 0.011
0.014
Fixed axes: Rei. Dist. Agg-MLP; Stage - Early; Non-lincurity Hinge; Gramularity
Edge
Non-injective
0.756 +: 0.019
0.787 + 0.015 0.786 + 0.015 0.416 0.012 0.011
Injective
0.815 +: 0.016
0,833 + 0.014 0.851 = 0.011 0.423 1 0.012 0.599
Fixed axes: Rel.
Dist. -igg--A
Stage- Early; Non-linearity Neurall; Granularity
Non-injective
0.74 0.02
1.68710.021
0.732 0.02 0.416 1 0.011 0.603
0.018
Injective
0.771 = 0.019
0.717 0.018 0.795 + 0.016
0.401 0.011 0.601
Fixed axes: Rel. Dist. - Set align.:
Stage - Early; Non-line Dot Product: Granularity Edge
Non-injective
0.799 + 0.017
0.789 + 0.016 0.81 + 0.016 0.421 + 0.012 0.609 + 0.02
Injective
0.817 + 0.016 0.791 + 0.016 0.819 + 0.014
0.435 + 0.012
0.63 = 0.018
Fixed axes: Rel. Dist. - Set align.: Stage Early; Non-lincarity Hinge; Gramularity
Bdge
Non-injective
0.773 +: 0.019
1.01 0.795 + 0.016
0.435 1 0.012
0.626 0.02
Injective
0.854 0.013 0,849 + 0.012 0.864 0.011
0.424 0.012
0.64
Fixed axes: Rel. Dist. -iet align.; Stage Farly; Non-linearity Neural; Granularity
Edge
Non-injective
0.733 = 0.00
0.75 4 0.782 0.017 0.421 0.011 0.607 0.018
Injective
0.752 + 0.02
0.773
0.788 + 0.015 0.433 + 0.012 0.609 +.00000.000 0.02
Fixed axes: Rel. Dist. Agg-NTN; Stage Early; Non-lineartyy Dot Product; Granularity Edge
Non- iojeiinee
0.754 : 0.019
0.719 + 0.021 0.777 + 0.016 0.418 + 0.012 0.614 0.018
Injective
0.771 + 0.018 0,81 + 0.014 0.858 + 0.012
0.425 1 0.012 0,617 0.018
Fixed axes: Rel. Dist. Agg-NTN: Stage - Early; Non-lincarity
Hinge: Gramularity
Edge
Non-injective
0.791 1: 0.017
0.016 0.833 1 0.014 0.421 0.011 0.608 =
Injective
0.824 + 0.016
0,821 1 0.014 0.844 0.013
0.426 + 0.012
0.635
Fixed axes: Rel.
Dist. Agg-NTN; Stage Early; Non-linearity Neural; Granularity
Edge
Non-injective
0.723 + 0.022
0.704
0.02
0.753 0.018 0.419 + 0.012
0.584 = 0.02
Injective
0.762 + 0.02 0.767 = 0.018 0.802 = 0.016 0.411 0.012 0.593 0.018
Table 18: Comparison of different interaction structures for early interaction models with edge- level granularity across last five datasets, using mean average precision (MAP). Green cells indicate the best method for the corresponding datasets.
36

---

Published as a conference paper at ICLR 2025
Analysis of Late Node Interaction along Interaction Non-Linearity Design Choices In Table 19, we observe: (1) The Neural non-linearity wins in six datasets for both Injective and Non-injective structures, making it the preferred alternative in this context. (2) Both Hinge and Dot Product exhibit competitive performance; however, the preferred option between these two varies depending on the
dataset.
Interaction Non- Non-linearity 11
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist. Set align:; Stage Late; Structure Injective; Granularity Node
Dot Product
0.631 1 0.022
0.66 1 0.026
0.722 0.019
0.608 0.019
0.612 0.016
Hinge
0.633 0.021
0.647 0.028
0.72 + 0.019
0.625 + 0.019
0.622 0.017
Neural
0.664 0.021
0.69 + 0.026
0.758 0.017
0.612 + 0.019
0.621 = 0.017
Fixed axes: Rel. Dist. Set align.;
Stuge- Late; Structure -Non-ijjectiee;
Granularity Node
Dot Product
0.6 = 0.023
0.652 0.027
0.702 = 0.021
0.598 = 0.02
0.617 = 0.017
Hinge
0,636 0.022
0.647 = 0.027
0.694 0.022
0.617 1 0.019
0.616 0.017
Neural
0.635 0.022
0.681 + 0.026 0.736 + 0.017
0.605 + 0.019 0.609 + 0.017
Interaction Non-lincarity +
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist. Set align.; Stage Late; Structure Injective; Granularity Node
Dot Product
0.62 0.023
0.664 = 0.019 0.643 + 0.019
0.415 1 0.012
0.57 0.019
Hinge
0.652 + 0.024
0.72 + 0.017 0.694 +: 0.018
0.399 = 0.012
0.574 = 0.019
Neural
0.683 + 0.022
0.711
0.738 = 0.017
0.41 = 0.012
0.019
Fixed axes: Rel. Dist. Set align.; Stage- Late; Structure- - Non-injective; Granularity
Node
Dot Product
0.621 + 0.024
0.671
0.001
0.681 + 0.02
0.403 + 0.012
0.56 + 0.021
Hinge
0.645 + 0.024
0.634 = 0.021
0.701 + 0.02
0.392 = 0.012
0.577 = 0.019
Neural
0.689 1 0.021
0.705 1 0.019 0.741 1 0.017
0.399 1 0.012
0.58 1 0.019
Table 19: Comparison of different interaction non-linearities for late interaction models with node-level granularity across ten datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
Analysis of Late Edge Interaction along Interaction Non-Linearity Design Choices In Table 20, we observe: (1) Hinge non-linearity clearly outperforms other options for both Injective and Non- injective structures. Notably, the Injective variant stands out as the best-performing late interaction model in our study. (2) Neural non-linearity, while not good as Hinge, outperforms Dot Product for most datasets.
Interaction Non-linearity 11
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist.
Set align.: Stage - Late; Structure Injective: Granularity Edge
Dot Product
0.68 + 0.021
0.712 = 0.026
0.755 + 0.016
0.623 = 0.02
0.634 0.018
Hinge
0.712 1 0.018
0.721 1 0.025
0.793 1 0.016
0.643 0.02
0.662 - 0.016
Neural
0.704 0.021
0.733 0.023
0.782
0.017
0.615
0.019
0.649 0.016
Fixed axes: Rel. Dist. - Set align.; Stage - Late; Structure- Non-injective; Granularity
Edge
Dot Product
0.681 + 0.022
0.681 = 0.026
0.759 + 0.019
0.611 + 0.019
0.621 = 0.017
Hinge
0,702 0.021
0.687 1 0.027
0.774 0.016
0.631 1 0.021
0.638 0.017
Neural
0.7 = 0.022
0.713 0.025
0.77 = 0.017
0.609 + 0.02
0.618 + 0.017
Interaction Non-linearins
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist. Sct align.; Stage Late; Structure Injective; Granularity Edge
Dot Product
0.719
0.02
0.676
0.018 0.735 0.018
0.404 + 0.012
0.019
Hinge
0.744 0.019
0.758 0.015
0.782 0.014
0.397 0.013
0.572
Neural
0.734 + 0.02
0.758 + 0.016
0.764 :: 0.015
0.411 + 0.012
0.587 =: 0.019
Fixed axes: Rel. Dist. Set align.;
Stage Late; Structure Non-injective;
Granularity
Edge
Dot Product
0.693 + 0.022
0.702 = 0.019
0.723 + 0.019
0.411 # 0.012
0.571 0.02
Hinge
0.731 4: 0.018
0.735 0.017
0.776 1 0.017
0.412 1 0.012
0.609
0.018
Neural
0.716 + 0.02
0.721 + 0.016 0.757 + 0.017 0.403 + 0.011
0.572 0.019
Table 20: Comparison of different interaction non-linearities for late interaction models with edge-level granularity across ten datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
37

---

Published as a conference paper at ICLR 2025
Analysis of Early Node Interaction along Interaction Non-Linearity Design Choices In Ta- bles 21 and 22, we observe: (1) Hinge non-linearity is typically the best choice for non-injective structures. (2) For injective networks, altermative clearly stands out; however, both Neural and Dot Product non-linearities demonstrate comparable performance to Hinge. (3) Notably, Dot Product emerges as the best option in six datasets when used with Agg-MI.P relevance distance in injective network.
Interaction Non-linearity.
AIDS
Mutag
FM
NCI
MOLT
Fixed axes: Rel. Dist. Agg-hinge
Stage - Early: Structure Injective; Granularity Node
Dot Product
0.64 = 0.019
0.75 = 0.023
0.79 = 0.016
0.619 = 0.019
0.63 0.018
Hinge
0.662 = 0.019
0.734 0.025
0.785 0.017
0.624 0.02
0.635 = 0.018
Neural
0,614 0.021
0.736 = 0.025
0.779 + 0.017
0,613 + 0.02
0.637 = 0.019
Fixed axes: Rel.
Dist. Agg MLP: Stage Early: Structure Injective: Granularity
Node
Dot Product
0.658 = 0.019
0.768 0.023
0.806 0.016
0.641 = 0.019
0.649 = 0.017
Hinge
0.683 = 0.019
0.757 + 0.023
0.785 0.016 0.629 = 0.019
0.627 + 0.018
Neural
0.629 1 0.021
0.764 = 0.024
0.777 1 0.016
0.626 + 0.02
0.641 = 0.017
Fixed axes: Rel. Dist, Set align.: Stage Larly; Structure Injective: Granularity Node
Dot Product
0.71 = 0.019
0.779 = 0.022
0.8 = 0.017
0.632 = 0.02
0.652 = 0.017
Hinge
0.734 = 0.019
0.774 + 0.023
0.834 0.016
0.64 = 0.019
0.647 + 0.018
Neural
0.69 1 0.02
0.783 1 0.023
0.827 0.015
0.654 1 0.019
0.659 1 0.018
Fixed axes: Rel. Dist. Big--NNN; Stage Early; Structure Injective; Granularity Node
Dot Product
0.721 = 0.019
0.772 1 0.022 0.812
0.016
0.626 = 0.019
0.636 = 0.018
Hinge
0.743 = 0.018
0.773 = 0.024
0.805 + 0.016 0.615 + 0.019
0.629 + 0.017
Neural
0.667 1 0.02
0.791 1: 0.021
0.828
0.015
0.629 1 0.019
0.651 1 0.018
Fixed axes: Rel. Dist. Agg hinge; Stage Early; Structure- Non-injective; Granularity
Node
Dot Product
0.609 + 0.02
0.693 1 0.026 0.686 + 0.018
0.588 1 0.019 0.603 1 0.018
Hinge
0.726 + 0.02
0.723 = 0.026 0.79 = 0.016
0.618 = 0.019
0.651 = 0.018
Neural
0.598 1 0.021
0.694 + 0.025
0.712
0.019 0.591 + 0.019
0.629 : 0.018
Fixed axes: Rel. Dist,
Agg-MMPP:
Stage Early; Structure- Non- Granularity
Node
Dot Product
0.63 1 0.022
0.713 1 0.025 0.765 1 0.016 0.593 1 0.019 0.619 0.077
Hinge
0.637 + 0.021
0.725 = 0.024 0.808 0.015
0.63 - 0.02
0.636 = 0.017
Neural
0.629 0.023
0.715 + 0.025
0.769
0.017
0.623 + 0.018
0.627 + 0.018
Fixed axes: Rel. Dist, - Set align.; Stage - Early; Structure Non-injective; Gramularity Node
Dot Product
0.608 1: 0.022
0.754 = 0.024
0.759 0.017 0.603 1 0.019
0.62 1 0.017
Hinge
0.676 + 0.022
0.669 1 0.024
0.772 = 0.018 0.599 1 0.02
0.637 + 0.018
Neural
0.593 0.021
0.748 + 0.025
0.772 - 0.016
0.614 + 0.019
0.646 + 0.017
Fixed axes: Rel. Dist. Agg-NTN; Stage Farly; Structure- - Non-injective; Granularity
Node
Dot Product
0.669 1 0.022
0.742 1 0.025
0.75 - 0.016
0.602 1 0.019 0.628 E 0.017
Hinge
0.686 1 0.019
0.758 1 0.022
0.818 0.015
0.641 1 0.02
0.664 1 0.017
Neural
0.635 + 0.025
0.755 = 0.025 0.796 0.016 0.633 + 0.019 0.641 + 0.017
Table 21: Comparison of different interaction non-linearities for early interaction models with node-level granularity across first five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
38

---

Published as a conference paper at ICLR 2025
Interaction Non-linearity.
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist.
Stage
Early; Structure Injective; Granularity Node
Dot Product
0.73 0.019
0.699 1 0.019 0.736 = U.016
0.423 0.012
0.374
Hinge
0.733 = 0.021
0.713 = 0.018
0.752 0.018
0.403
0.011
0.575
Neural
0.73 1 0.02
0.712
0.018
0.733
0.017
0.417
0.011
0.579
Fixed axes: Rel. Dist. Aag-AgggM
Stage Early; Structure Injective; Granularity Node
Dot Product
0.751 - 0.018
0.741
0.017
0.800
0.014
0.431
0.012
0.577
Hinge
0.75 0.019
0.774
0.017
0.781 +: 0.016
0.42 = 0.011
0.603 = 0.019
Neural
0.772 0.017
0.707
0.018
0.785
0.015
0.416
0.011
0.597 0.019
Fixed axes:
Dist, -Stt alignn; Stage Earye-Early; Structure Injoective Injective; Granularity Node
Dot Product
0.074
0.736
0.803
0.014
0.436
0.012
0.593 1 0.019
Hinge
0.774 = 0.017
0.759
0.806 0.013
0.426
0.012
0.584 0.019
Neural
0.746 0.019
0.764
0.776
0.015
0.433
0.012
0.613
0.019
Fixed axes: Rel.
- Agg-NTN, Stage
Earye- Structure Injective; Granularity
Node
Dot Product
0.764
0.748
0.017
0.796
11796110000
0.426
0.012
0.583 1 0.019
Hinge
0.768 1: 0.019
0.755
-
0.798 0.015
0.422
0.012
0.571 0.019
Neural
0.766 + 0.019
0.748
0.018
0.015
0.409 0.011
0.584+ 0.019
Fixed axes: Rel. Dist.
Agg-hinge;
Farge-Farly, Structure Non-injective;
Granularity
Node
Dot Product
0.667 0.021
0.627
0.02
0.683
0.017
0.416 0.012
0.549 0.018
Hinge
0.75
0.723
0.018
0.787 0.015
0.414
0.012 0.584
Neural
0.674 0.022
0.643
0.02
1.662+0.00
0.401
0.011
0.554
Fixed Rel. Dist.
Agg-MI.P; Stage Farly; Structure Non-injective; Granularity
Node
Dot Product
0.687 0.02
0.678 + 0.018 0.741 0.017
0.011
0.562 0.019
Hinge
0.744
0.71 0.018 0.773 0.016
0.41::0001
0.586 0.02
Neural
0.698 = 0.021
0
0.739 +
0.415
0.012
= +
Fixed axes: Rel. Dist Sct aliggn Stage Early; Structure Non-injective; Gramularity
Node
Dot Product
+.706++0.022
0.691
0.017 0.715
0.423
0.553 + 0.019
Hinge
0.678 +: 0.022
0.711 0.018 0.768 0.017
0.419 0.012
0.601 0.02
Neural
0.01
0.003:00019
0.016
0.416 0.012
Fixed axes: Rel. Dist.
Agg-NTN;
Early Structure Non-injective; Granularity
Node
Dot Product
0.715 + 0.021
0.019 0.762
0.017
0.415 0.011
0.571 + 0.019
Hinge
0.765 + 0.019
0.766
0.016
0.014
0.409 0.012
0.572 0.02
Neural
0.707 0.021
0.701 # 0.019
0.69 0.019
0.408 0.011 0.586 0.018
Table 22: Comparison of different interaction non-linearities for early interaction models with node-level granularity across last five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
39

---

Published as a conference paper at ICLR 2025
Analysis of Early Edge Interaction along Interaction Non-Linearity Design Choices In Ta- bles 23 and 24, we observe: (1). Hinge non-linearity is the best performer across all datasets, regardless of the interaction structure, (2), Dot Product method ranks second in most cases, although
occasionally outperforms Hinge., (3) Neural method is consistently the lowest performer among
the three.
Interaction Non-linearity//
AIDS
Mutag
FM
NCT
MOLT
Fixed axes: Rel. Dist. Agg-hinge: Stage Early; Structure- Injective; Granularity
Edge
Dot Product
0.755 = 0.019
0.763 = 0.025
0.826 0.014
0.656 0.02
0.67 0.019
Hinge
0.758 + 0.019
0.78 :: 0.023
0.83 + 0.015
0.661 0.02
0.681 + 0.019
Neural
0.68 + 0.022
0.755 + 0.024
0.807 + 0.016
0.625 + 0.02
0.656 0.019
Fixed axes: Rel. Dist. Agg.
Stage Early; Structure Injective; Granularity
Edge
Dot Product
0.758 = 0.019
0.773 0 0.023
0.853 0.014
0.682 0.02
0.683 = 0.017
Hinge
0.789 1 0.017
0.807 0.023
0.871 0.013
0.663 0.02
0.678 + 0.018
Neural
0.703 0.021
0.738 + 0.026
0.815 + 0.015
0.643 0.021
0.644 0.019
Fixed axes: Rel. Dist, Set align.;
Structure Injective; Granularity
Edge
Dot Product
0.798 = 0.019
0.789 = 0.023
0.862 0.015
0.674
0.019
0.688 = 0.018
Hinge
0.817 1: 0.017
0.837 0.02
0.887 0.012
0.677 1 0.02
0
Neural
0.725 0.021
0.784
0.023
0.837 + 0.015
0.649
0.019
0.664 0.018
Fixed axes: Rel. Dist. - Agg-NTN; Stage Early; Structure Injective; Granularity
Edge
Dot Product
0.74 0.02
0.783 = 0.023
0.833 0.015
0.655 0.02
0.672 = 0.018
Hinge
0.019
0.766
0.025
0.855
0.013
0.653 0.021
0.679 : 0.018
Neural
0.689 0.022
0.749 + 0.027
0.831 + 0.015
0.651 0.021
0.664 0.019
Fixed axes: Rel. Dist.
Ainghinge; Stage Early; Structure Non-injective: Granularity
Edge
Dot Product
0.7 0.022
0.734 = 0.025
0.78 1 0.018
0.625 0.02
0.653 + 0.018
Hinge
0.763 + 0.018
0.753 0.025
0.831
0.015
0.606 0.02
0.686 + 0.017
Neural
0.677 0.022
0.729 + 0.025
0.747 + 0.019
0.618
0.019
0.633 0.018
Fixed axes: Rel. Dist. -Ag--Mi
Stage Early; Structure Non-injective; Granularity
Edge
Dot Product
0.677 1 0.022
0.766
0.023
0.792 0.016
0.638 1 0.019
0.65 0.01S
Hinge
0.748 0.019
0.778 0.023
0.847 0.014
0.658 0.021
0.684 + 0.018
Neural
0.662 + 0.024 0.735 + 0.024 0.745
0.019
0.629 + 0.02
0.65 +
Fixed axes: Rel. - Set align.; Stage Eady; Structure Non-injective; Granularity
Edge
Dot Product
0.715 1 0.021 0.779 0.023
0.812
0.017
0.635 0.019
0.659
0.017
Hinge
0.783 + 0.017 0.785 0.024
0.807 0.015
0.657 0.021
0.696 + 0.018
Neural
0.708 + 0.022
0.763 + 0.024
0.807
0.016
0.648
0.019
0.655 0.018
Fixed axes: Rel. Dist. - ATg,NTN, Stage Early; Structure- Non-injective; Granularity
Edgee
Dot Product
0.71 0.022
0.751
0.024
0.815 0.016
0.653 1 0.02
0.644 0.017
Hinge
0.79 = 0.017
0.785 0.023
0.835
0.014
0.661 0.02
0.683 = 0.018
Neural
0.701 0.023 0.734 0.028 0.811 0.016 0.625 + 0.02 0.648 = 0.019
Table 23: Comparison of different interaction non-lincarities for early interaction models with edge-level granularity across first five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
40

---

Published as a conference paper at ICLR 2025
Interaction Non-linearity.)
FR
MM
MR
MSRC
MCF
Fixed axes: Rel. Dist. Agg-hinge: Stage
Early; Structure Injective; Cranularity
Edge
Dot Product
0.018
0.777 0.018 0.803 0.015
0.415 0.011
0.616
Hinge
0.798 = 0.019
0.785 = 0.016
0.817 0.014
0.421 = 0.012
0.619 = 0.019
Neural
0.749 0.022
1: 0.019
0.766
0.016
0.406
0.012
0.595
Fixed axes: Rel. Dist. Agg-MLP. Stage Early; Structure Injective; Granularity Edge
Dot Product
0.786 + 0.017 0.791
0.016 0.827
0.014
0.404
0.011
0.614 + 0.018
Hinge
0.815 = 0.016 0.833 = 0.014 0.851
0.011
0.423 = 0.012
0.599
0.018
Neural
0.771 0.019 0.017
0.795
0.016 0.401
0.011
0.601 + 0.018
Fixed axes:
Dist. - Set alignn; Stage Eary; Structure Injective; Granularity Edge
Dot Product
0.817 0.016 0.791 0.016
0.819
0.014
0.435
0.012
0.63 1.00S
Hinge
0.854 +: 0.013 0.849
0.012
0.864
0.011
0.424
0.012
0.018
Neural
0.752 0.02 0.773
0.016
0.788
0.015
0.433
0.012
0.609
+
Fixed axes: Rel.
Dist. -ost.-Age Agg-NTN; Stage Early; Structure Injective; Granularity
Edge
Dot Product
0.771 0.018
0.81
0.0144
0.858
0.012
0.425
0.012
0.617 0.018
Hinge
0.824 1: 0.016 0.821
0.014
0.844 = 0.013
0.426 0.012
0.635 1
Neural
0.762 0.02 0.767 + 0.018
0.802
0.016
0.411 0.012
0
Fixed axes: Rel. Dist. Agg-hinge; Stage Early; Structure Non-injective; Granularity
Edge
Dot Product
1: 0.019
0.706
1: 0.02
0.746 0.019
0.421
0.601 0.018
Hinge
0.772 1: 0.018
0.799
0
0.423
0.012 0.612
Neural
0.02
0.691
0.02
0.02
0.422
0.011
0
Fixed axes: Rel. Dist. MLP-
Farly Structure Non-injective; Granularity
Edge
Dot Product
0.751 0.019
0.723
0.019
0.788 0.016
0.416 0.011
0.396
Hinge
0.756 1: 0.019 0.787
0.015
0.786 0.015
0.416
0.012
0.628 0.019
Neural
0.04
0.687
0.021
0.732
0.416 0.011
0.603 0.018
Fixed axes: Rel. Dist. -et alignn; Stage Early; Structre Non-injective; Granularity
Edge
Dot Product
0.799 0.017
0.789+0.011
0.016
0.421 + 0.012
+
Hinge
0.773 + 0.019
0.015
0.795 0.016
0.435 0.012
0.626 0.02
Neural
0.02
0.018
0.717
0.421 0.011
0.607
Fixed axes: Rel. Dist. Agg-NTN, Eaage- Structure Non-injective; Granularity
Edge
Dot Product
0.754 + 0.019
0.719
0.777 0.016
0.418 + 0.012
0.61400.015
Hinge
0.791 + 0.017
0.8 0.016
0.833
0.014
0.421 0.011
0.608 0.02
Neural
0.723 0.022
0.704 0.02 0.753 0.018 0.419 0.012 0.584
Table 24: Comparison of different interaction non-linearities for early interaction models with edge-level granularity across last five datasets, using mean average precision (MAP). Green and yellow cells indicate the best and second best methods respectively for the corresponding dataset.
41

---

Published as a conference paper at ICLR 2025
G REAL-WORLD LARGE DATASETS
Recent work such as Greed (Ranjan et al., 2022) proposes heuristic for adapting small-scale fast neural graph solvers to the problem of subgraph localization within large-scale graphs. Inspired by this approach, we extended our experiments include three large-scale graphs drawn from the SNAP repository:
1. com-Amazon: Represents an Amazon product co-purchasing network. with nodes prod- ucts and edges denoting co-purchasing relationships. consists of 334,863 nodes and 925,872 edges.
2. email-Enron, Represents an email communication network, with nodes as individuals and edges email exchanges. It consists of 36,692 nodes and 183,831 edges.
3. roadnet-CA: Represents the road network of California, with nodes as road intersections and edges as connecting roads. It consists of 1, 1,965,200 nodes and 2,766,607 edges.
To integrate these datasets into our study, we followed the same preprocessing and subgraph extraction methodology outlined in the paper and ran all the designed experiments to further explore the design space of the subgraph matching methods.
Rel. Dist.
Structure
Non- Non-linearity
Amazon
Email
Roadnet
Agg-hinge
NA
NA
0.616
0.723
0.556
Agg-MLP
NA
NA
0.544
0.631
0.616
Agg-NTN
NA
NA
0.656
0.778
0.499
Set align.
Non-injective Non-injective
Dot Product
0.66
0.798
0.618
Set align.
Hinge
0.739
0,826
0,609
Set align.
Non-injective Injective Injective Injective
Neural
0.752
0.805
0.585
Set align.
Dot Product
0.739
0.852
0.637
Set align.
Hinge
0.772
0.864
0.576
Set align.
Neural
0.771
0.852
0.605
Table 25: MAP for late interaction models with node-level granularity across three large and diverse datasets.
Rel. Dist.
Structure
Non-linearity
Amazon
Email
Roadnet
Agg-hinge
NA
NA
0.692
0.847
0.744
Agg-MLP
NA
NA
0.652
0.783
0.682
Agg-NTNN
NA
NA
0.678
0.851
0.706
Set align.
Non-injective Non-injective
Dot Product
0.737
0.834
0.621
Set align.
Hinge
0.776
0,865
0.741
Set align.
Non-injective Injective Injective Injective
Neural
0.771
0.838
0.72
Set align.
Dot Product
0.749
0.852
0.668
Set align.
Hinge
0.8
0.849
0.708
Set align.
Neural
0.788
0.871
0.724
Table 26: MAP late interaction models with edge-level granularity across three large and diverse datasets.
42

---

Published as a conference paper at ICLR 2025
Rel. Dist.
Structure
Non-linearity
Amazon
Email
Roadnet
Agg-MLP
Injective
Hinge
0.805
0.902
0.68
Agg-MLP
Injective
Dot Product
0.725
0.911
0.643
Agg-MLP
Injective
Neural
0.798
0.895
0,668
Agg-MLP
Non-Inge -ojeInjeetive
Hinge 0.77
0.869
0.646
Agg-MLP
Non-Injed non-Injective
Dot Product
0.72
0.817
0.648
Agg-MLP
Non-Injee -njeetneeevve
Neural
0.748
0.834
0.586
Agg-NTN
Injective
Hinge 0.798
0.906
0.699
Agg-NTN
Injective
Dot Product
0.789
0.902
0.669
Agg-NTN
Injective
Neural
0.787
0.92
0.732
Agg-NTN
Non-
Non-Injective
Hinge 0.768
0,855
0.668
Agg-NTN
Non-Injective
Dot Product
0.668
0.829
0.612
Agg-NTN
Non-Injective
Neural
0.695
0.839
0.645
gg-hinge
Injective
Hinge 0.756
0.866
0.659
Agg gg-hinge
Injective
Dot Product
0.748
0.861
0.682
A Ag--iigg
Injective
Neural
0.743
0.862
0.66
gg-hinge
Non-Injective Non- MojeInjective
Hinge
0.799
0.878
0.662
Agg-hinge
Dot Product
0.657
0.764
0.61
Agg-hinge
Non-Injective Injective Injective Injective
Neural
0.676
0.759
0.592
Set align
Hinge
0.849
0.935
0.745
Set align
Dot Product
0.816
0.905
0.706
Set align
Neural
0.823
0.905
0.723
Set align
Non-Injedd Injeinjective
Hinge 0.768
0.86
0.652
Set align
Non- Non-Injective
Dot Product
0.729
0.827
0.648
Set align
Non-Injective
Neural
0.747
0.842
0.648
Table 27: MAP for early interaction models with node-level granularity across three large and diverse datasets.
Rel. Dist.
Structure
Non-linearity
Amazon
Email
Roadnet
Agg-MLP
Injective
Hinge
0.84
0.926
0.773
Agg-MLP
Injective
Dot Product
0.799
0.934
0.76
Agg-MLP
Injective
Neural
0.72
0.91
0.74
Agg-MLP
Non-
Moj-Injective
Hinge
0.801
0.886
0.671
Agg-MLP
Non- Mon-Injective
Dot Product
0.74
0.837
0.745
Agg-MLP
Non-Injective
Neural
0.703
0.869
0.613
Agg-NTN
Injective
Hinge 0.791
0.922
0.731
Agg-NTN
Injective
Dot Product
0.783
0,916
0.76
Agg-NTN
Injective
Neural
0.789
0.908
0.737
Agg-NTN
Non-Injective
Hinge
0.795
0.868
0,816
Agg-NTN
Non-Injective
Dot Product
0.765
0.874
0.77
Agg-NTN
Non- Injective
Neural
0.701
0,853
0,708
Agg-hinge
Injective Injective Injective
Hinge
0.827
0.939
0.801
Agg-hinge
Dot Product
0.77
0.915
0.805
agg-hinge
Neural
0.753
0.911
0.768
ggg agghhinee
Non- Non-Injective Non-Inie onjeInjective
Hinge
0.797
0.874
0.73
Age gg-hinge
Dot Product
0.736
0.845
0.607
Agg-hinge
Inj-Injective
Neural
0.69
0.842
0.698
Set align
Injective Injective Injective
Hinge
0.863
0.944
0.834
Set align
Dot Product
0.827
0.921
0.828
Set align
Neural
0.826
0.909
0.752
Set align
Non-Injective Non-Injective Non-Injective
Hinge 0.783
0.875
0.832
Set align
Dot Product
0.802
0.872
0.802
Set align
Neural
0.769
0.858
0.74
Table 28: MAP for early interaction models with edge-level granularity across three large and
diverse datasets.
43

---

Published as a conference paper at ICLR 2025
H TRANSFER ABILITY ACROSS DATASETS
In this section, we test our models in -iitti--ittiittiionn transfer setting by evaluating models on datasets other than the one they were originally trained on. We first fix AIDS as the target dataset and iterate over Mutag, FR and MOLT as source datasets.
Analysis of transfer abilities Early Node Interaction models Tables 29 and 30, we observe: (1) The strongest transfer abilities are displayed by models trained the FR dataset, followed by the Mutag dataset, while models trained on the MOLT dataset show severe degradation in performance compared to the baseline model trained
AIDS itself. This pattern can be explained by the extent of relative dissimilarity between the source datasets and AIDS, which is maximum for MOLT (doubly- sized graphs AIDS), followed by Mutag (mean node/edge counts off by one/two) and finally FR. (2) Hinge non-linearity is consistently the best performer even in the transfer setting, similar to the default setting of training and testing the same dataset.
Rel. Dist.
Structure
Non-linearity
AIDS - AIDS Mutag -> AIDS FR - AIDS
MOLT - AIDS
Agg-hinge
Non-injective Non-injective
Dot Product
0.609
0.330
0.520
0.253
Agg-hinge
Hinge
0.726
0,360
0.626
0.369
Agg-hinge
Non-injective
Ncural
0.598
0.331
0.510
0.238
Agg-hinge
Injective Injective Injective
Dot Product
0.64
0.394
0.581
01.22
Agg-hinge
Hinge
0,662
0.422
0.595
0.346
Agg-hinge
Neural
0.614
0.403
0.598
0.322
Agg-MLP
Non-injective Non-injective Non-injective
Dot Product
0.63
0.323
0.569
0.363
Agg-MIP
Hinge
0.637
0.378
0.624
0.437
Agg-MLP
Neural
0.629
0.363
0.552
0.337
Age-MLP
Injective Injective Injective
Dot Product
0.658
0.486
0.612
0.427
Ag-MMLP
Hinge
0.683
0.457
0.611
0.455
Agg-MI.P
Neural
0.629
0.464
0.625
0.414
Agg-NTN
Non-injective Non-ing ion-injective
Dot Product
0.609
0.450
0.557
0.407
Agg-NTN
Hinge
0.686
0.442
0.623
0.405
Agg-NTN
Non-injective
Neural
0.635
0.367
0.549
0.268
Agg-NTN Injective Injective Injective
Dot Product
0.721
0.487
0.635
0.420
Agg-NTN
Hinge
0.743
0.478
0.626
0.356
Agg-NTN
Neural
0.667
0.499
0.617
0.395
Set align.
Non-injective Non-injective Non-injective
Product
0.608
0.377
0.574
0.419
Set align.
Hinge
0.676
0.394
0.600
0.451
Set align.
Neural
0.593
0.450
0.599
0.363
Set align.
Injective Injective Injective
Dot Product
0.71
0,510
0.663
0.448
Set align.
Hinge
0.734
0.505
0.684
0.480
Set align.
Neural
0.69
0.507
0.641
0.494
Table 29: Comparison of different network configurations for early interaction models with node- level granularity, using mean average precision (MAP). Green and yellow cells indicate the best and second best transfer methods respectively for the corresponding network. Cells in boldface represent the best non-linearity individually for each transfer combination.
44

---

Published as a conference paper at ICLR 2025
Rel. Dist.
Structure
Von-linearity
AIDS - AIDS Mutag + AIDS
FR - AIDS
MOLT AIDS
Agg-hinge
Non-injective Non-injective Non-injective
Dot Product
0.7
0.400
0.560
0.290
Agg-hinge
Hinge
0.763
0.445
0.640
0.447
Agg-hinge
Neural
0.677
0.414
0.541
0.219
Agg-hinge
Injective Injective Injective
Dot Product
0.755
0.454
0.657
0.305
Agg-hinge
Hinge
0.758
0.477
0.664
0.274
Agg-hinge
Ncural
0.68
0.422
0.578
0.278
Agg-MLP
Non-injective Non-injective
Dot Product
0.677
0.451
0.589
0.341
Agg-MLP
Hinge
0.748
0.423
0.619
0.337
Agg
Agg-MLP
Non-injective
Neural
0.662
0.396
0.563
0.351
Age-MLP Injective
Product
0.758
0.662
0.373
Agg-MLP
Injective
Hinge
0.789
0.491
0.718
0.425
Agg-MLP
Injective
Neural
0.703
0.620
0.312
Age-NTN
Non-injective Non-injective
Dot Product
0.71
0.444
0.603
0.399
Age-NTN
Hinge
0.79
0.489
0.658
0.241
Age-NTN
Non-injective
Neural
0.701
0.419
0.572
0.361
Agg-NTN Injective Injective Injective
Dot Product
0.74
0.466
0.623
0.367
Agg-NTN
Hinge
0.76
0,518
0.714
0.431
Agg-NTN
Neural
0.689
0.409
0.599
0.320
Set align.
Non-injective Non-injective Non-injective
Dot Product
0.715
0.474
0.668
0.374
Set align.
Hinge
0.783
0.483
0.687
0.497
Set align.
Neural
0.708
0.429
0.594
0.412
align.
Injective Injective Injective
Product
0.798
0.505
0.695
0.447
Set align.
Hinge
0.817
0,599
0.773
0.538
Set align.
Neural
0.725
0.599
0.428
Table 30: Comparison of different network configurations for early interaction models with edge-level granularity, using mean average precision (MAP). Green and yellow cells indicate the best and second best transfer methods respectively for the corresponding network. Cells in boldface represent the best non- non-linennn linearity individually for each transfer combination.
45

---

Published as a conference paper at ICLR 2025
I VARIATION IN PERFORMANCE WITH INTRINSIC DATASET CHARACTERISTICS
In this section, we study how different characteristics of the dataset affect the performance of our models. In particular, we choose metric (like edge count in a graph), split the corpus set into 4 cqual-sized buckets based on this metric, and compute the MAP score over all test query graphs on each of these splits independently, using the model trained on the entire corpus. Three metrics are considered (1) Node count (representative of graph size) (2) Edge count (representative of graph size) (3) Standard deviation of degrees of all nodes in the graph (representative of the regularity of graphs). We tackle each of these metrics individually in the subsections below. Subset represents the split of the dataset with the lowest value for that metric, while subset 3 is the other extreme, with the highest values for the metric. For instance, subset for the Standard deviation of node degrees metric represents the set of graphs with the least variation in node degrees i.e. the most regularity.
46

---

Published as a conference paper at ICLR 2025
1.1 EDGE COUNT
In Tables 31 and 32, we observe: (1) With non-injective interaction structure, we observe that graphs with more edges see better performance on average. (2) Under the injective interaction structure, the difference in scores across subsets is more subtle, which indicates that injective mapping might not be affected significantly by edge count.
Rel. Dist.
Structure
Non-linearity
AIDS
Subset O
Subset
Subset 2
Subset 3
Agg-hinge Agg-hinge
Non-injective Non-injective
Dot Product
0.609
0.535
0.574
0.617
0.665
Hinge
0.726
0.763
0.703
0.738
0.739
Agg-hinge
Non-injective
Neural
0.598
0,519
0.5417
0.606
0.659
Agg-hinge
Injective Injective Injective
Dot Product
0.64
0.635
0.627
0.658
0.672
Agg-hinge
Hinge
0.662
0,663
0.643
0.661
0.693
Agg-hinge
Neural
0.614
0,535
0.566
0.623
0.673
Age-MLP
Non-injective Non-injon non-injective
Dot Product
0.63
0.562
0.580
0.611
0.686
Agg-MLP
Hinge
0.637
0.624
0.613
0.651
0,671
Agg-MLP
Non-injective
Neural
0.629
0,564
0.584
0.616
0.671
Agg-MLP Injective
Dot Product
0.658
0.687
0.650
0.670
0.677
Agg-Mi Agg-MIP
Injective
Hinge
0.683
0.722
0.685
0.688
0.698
Agg-MLP
Injective
Neural
0.629
0.612
0.599
0.642
0.667
Agg-NTN
Non injective
Dot Product
0.669
0.613
0.630
0.672
0.715
Agg-NTN
Non-injective
Hinge
0.686
0.681
0.641
0.690
0.726
Agg-NIT NNNNNT
Non injective
Neural
0.635
0.572
0.579
0.628
0.698
Agg-NTN
Injective
Dot Product
0.721
0.736
0.697
0.728
0.745
Agg-NTN
Injective
Hinge
0.743
0.773
0.736
0,756
0.750
Agg-NTN
Injective
Neural
0.667
0.643
0.619
0.675
0.713
Set align.
Non-injective Non-injectivn
Dot Product
0.608
0.574
0.592
0.614
0.650
Set align.
Hinge
0.676
0.706
0.671
0.693
0.703
Set align.
Non-injective
Neural
0.593
0.566
0.566
0.616
0.637
Set align.
Injective Injective
Dot Product
0.71
0.767
0.698
0.713
0.721
Set align.
Hinge
0.734
0.821
0.735
0.740
0.724
align.
Injective
Neural
0.69
0.735
0.680
0.705
0.704
Table 31: Comparison of different network configurations for early interaction models with node-
level granularity across splits of the AIDS dataset with increasing edge count, using mean average precision (MAP). Green and yellow cells indicate the subsets where the model trained on the full dataset performs best and second best respectively.
Rel. Dist.
Structure
Non-lineurity
AIDS
Subset 0
Subset
Subset
Subset
Agg-hinge
Non-injective Non- injectieetie
Dot Product
0.7
0.667
0.662
0.708
0.742
Agg- hinge
Hinge
0.763
0.784
0.754
0.773
0.774
Agg-hinge
Non-injective
Neural
0.677
0.612
0.617
0.693
0.723
Agg hinge
Injective Injoctive Injective
Dot Product
0.755
0.763
0.742
0.770
0.765
Agg-hinge
Hinge
0.758
0.781
0.742
0.769
0.775
Agg hinge
Neural
0.68
0.628
0.645
0.689
0.724
Agg-MLP
Non-injective Non-injective
Dot Product
0.677
0.619
0.617
0.670
0.721
Agg-MLP
Hinge
0.748
0.767
0.731
0.751
0.770
Agg-MI.P
Non-injective
Neural
0.662
0.592
0.619
0.665
0.715
Agg-MLP Injective
Det Product
0.758
0.778
0.737
0.762
0.773
Agg-MLP
Injective
Hinge
0.789
0.837
0.78G
0.797
0.784
Agg-MLP
Injoctive
Neural
0.703
0.685
0.676
0.710
0.736
Agg-NTN
Non- injective
Det Product
0.71
0.713
0.678
0.714
0.741
Agg-NTN
Non-injective
Hinge
0.79
0.842
0.786
0.791
0.791
Agg-NTN
Non-injo non-injecttvee
Neural
0.701
0.063
0.671
0.711
0.744
Agg-
Injective
Product
0.74
0.718
0.725
0.749
0.762
Agg-NTN
Injective
Hinge
0.76
0.785
0.747
0.759
0.781
Agg NTN
Injective
Neural
0.689
0.609
0.642
0.695
0.731
Set align.
Non-injective
Dot Product
0.715
0.656
0.664
0.695
0.755
Set align.
Non injective
Hinge
0.783
0.805
0.750
0.790
0.786
Set align.
Non-injective
Neural
0.708
0.661
0.670
0.709
0.749
Set align.
Injective Injoctive
Dot Product
0.795
0.829
0.782
0.796
0.805
Set align.
Hinge
0.817
0.879
0.812
0.827
0.801
Set align.
Neural
0.725
0.716
0.677
0.716
0.749
Table 32: Comparison of different network configurations for early interaction models with edge-
level granularity across splits of the AIDS dataset with increasing edge count, using mean average precision (MAP). Green and yellow cells indicate the subsets where the model trained the full dataset performs best and second best respectively.
47

---

Published as a conference paper at ICLR 2025
1.2 NODE COUNT
In Tables 33 and 34, we observe: (1) Across splits with increasing node count, performance consis- tently improves for all network configurations. This can be explained by the presence of padding nodes in the injective/ / non-injective maps
Rel. Dist.
Structure
Non-linearity
AIDS
Subset O
Suhset
Suhset 2
Subset
Agg-hinge
Non-injective Non injective
Dot Product
0.609
0,531
0.58G
0.623
0.670
Agg hinge
Hinge
0.726
0.687
0.714
0.724
0.758
Agg-hinge
Non-injective
Neural
0.598
0.511
0.577
0.603
0.660
Agg hinge
Injective Injoctive
Dot Product
0.64
0.594
0.629
0.652
0.687
Agg-hinge
Hinge
0.662
0.596
0.680
0.671
0.701
Agg hinge
Injective
Neural
0.614
0.526
0.580
0.638
0.674
Agg-MLP
Non-injective
Dot Product
0.63
0.543
0.616
0.637
0.691
Agg. ML.
Non injective
Hinge
0.637
0.567
0.620
0.653
0.685
Agg-MLP
Non-injective
Neural
0.629
0.540
0.603
0.634
0.689
Agg-MLP
Injective Injective
Det Product
0.658
0.614
0,658
0.674
0.693
Agg-MLP
Hinge
0.683
0.660
0.688
0.685
0.711
Agg-MLP
Injective
Neural
0.629
0.566
0.607
0.631
0.683
Agg-NTN
Non injective
Product
0.669
0.579
0.643
0.683
0.721
Agg-NIN
Non-injective
Hinge
0.686
0.611
0.6:1
0.692
0.745
Agg-NVI
Non- injective
Neural
0.635
0.543
0.603
0.642
0.707
Agg-NTN
Injective
Dot Product
0.721
0.665
0.714
0.726
0.757
Agg Agg-NTX
Injective Injective
Hinge
0.743
0,684
0.749
0.757
0.767
Agg-NTN
Neural
0.667
0.593
0.639
0.675
0.721
Set align.
Non-injective Non-injective Non-injective
Dot Product
0.608
0.533
0.594
0.623
0,662
Set align.
Hinge
0.676
0.633
0.672
0.697
0.727
Set align.
Neural
0.593
0,536
0.576
0.608
0.614
Set align.
Injective Injective
Dot Product
0.71
0.678
0.704
0.709
0.744
Set align.
Hinge
0.731
0.723
0.746
0.732
0.747
Set align.
Neural
0.69
0,652
0.676
0.703
0.723
Table 33: Comparison of different network configurations for early interaction models with node-
level granularity across splits of the AIDS dataset with increasing node count, using mean average precision (MAP). Green and yellow cells indicate the subsets where the model trained on the full dataset performs best and second best respectively.
Rel. Dist.
Structure
Non- linearity
AIDS
Subset
Subset
Suhset
Subset
Agg-hinge Non-injecti iojeeineetivve
Dot Product
0.7
0.633
0.666
0.706
0.751
Agg-hinge Non-injective
Hinge
0.763
0.736
0.759
0.771
0,790
Agg-hinge
Non-injective
Neural
0.677
0.604
0.643
0.686
0.730
Agg-hinge
Injective Injective
Dot Product
0.755
0.706
0.751
0.758
0.781
Agg-hinge
Hinge
0.758
0.716
0.753
0.765
0.791
Agg-hinge
Neural
0.68
0.602
0.660
0.688
0.731
Agg-MLP
Non-injon Non-injective
Dot Product
0.677
0,584
0.649
0.683
0.732
Agg MLP
Non injective
Hinge
0.748
0.699
0.736
0.759
0.786
Agg-MLP
Mon-injective
Neural
0.602
0.565
0.636
0.676
0.721
Agg- MI.P
Injective Injoctive
Dot Product
0.758
0.695
0.742
0.765
0.793
Age-MLP
Hinge
0.789
0.754
0.791
0.790
0.813
Agg ML.
Injective
Neural
0.703
0.635
0.687
0.714
0.742
Agg-NTN
Non-injective
Dot Product
0.71
0.660
0.696
0.704
0.752
Agg NTN
Non injective
Hinge
0.79
0.765
0.783
0.796
0.814
Agg-NTN
Non-injective
Neural
0.701
0.630
0.677
0.704
0.755
Agg-NIN Injective Injective
Det Product
0.74
0.676
0.726
0.744
0.777
Agg-NTN
Hinge
0.76
0.715
0.750
0.762
0.794
Agg-NIN
Injective
Neural
0.689
0.615
0.606
0.69-
0.741
Set align.
Non injective
Product
0.715
0.612
0.698
0.710
0.767
Set align.
Non-injective Non-in Non-injective
Hinge
0.783
0.725
0.761
0.786
0.816
Set align.
Neural
0.708
0.615
0.680
0.722
0.755
Set align.
Injective Injective Injoctive
Dot Product
0.798
0.760
0.781
0.807
0.820
Set align.
Hinge
0.817
0.798
0.813
0.822
0.830
Set align.
Neural
0.725
0.653
0.696
0.731
0.756
Table 34: Comparison of different network configurations for early interaction models with edge-level
granularity across splits of the AIDS dataset with increasing node count, using mean average precision (MAP). Green and yellow cells indicate the subsets where the model trained on the full dataset performs best and second best respectively.
48


Reviews:
[{"review_id": "Ulj4rNTo6E", "reviewer": "Reviewer_6vg7", "summary": "This paper presents a unified design space for existing neural subgraph matching methods over various dimensions. By carefully controlling the design option for each dimension, it effectively reveals the optimal design option combination for neural subgraph matching with substantial improvement, providing new insights on the previous methods and reported results.", "questions": "**Q1.** Does the use of hinge distance make sense for set alignment and aggregated-hinge (L216-236)? In particular, the authors justify the use of hinge distance for adjacency matrices, but the adjacency matrices are binary while node/aggregated node embeddings are just real-valued.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**S1.** The charting of the design space is convincing and well-articulated.\n\n**S2.** Empirical studies demonstrate the effectiveness of the design space in characterizing existing methods and devising superior new methods for the experiments considered.\n\n**S3.** The presentation is quite neat and clear overall.", "weaknesses": "**W1.** Most datasets considered are for small molecules despite the various applications of subgraph matching mentioned in the introduction.\n\n**W2.** There is a lack of understanding in subgraph matching performance with respect to the intrinsic challenge of the setting, e.g., highly regular graphs, different graph sizes, different feature distributions, out-of-distribution settings. Such study may be best achieved with synthetic datasets.\n\n**minor**\n- The use of notations $\\omega$ and $\\eta$ are not consistent between L124 and Figure 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "0Z4fuX45EC", "reviewer": "Reviewer_SvpM", "summary": "The paper presents an exploration of the design space for neural subgraph matching, where subcomponents have been presented in existing research. The authors observe that prior methods for neural graph matching have been narrowly focused, with most methods falling into limited design categories. To address this, the authors organize a comprehensive framework including key architectural choices: relevance distance, interaction stages, interactions structures, interaction non-linearity, and interaction granularity. Extensive experiments demonstrate that unexplored combinations within this design space can lead to performance improvement.", "questions": ".", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The authors show a detailed and thorough literature survey on neural subgraph matching and introduce general subcomponents for subgraph matching models.\n- The authors conduct extensive experiments on all possible combinations within design spaces.\n- The authors discover a new combination of subcomponents that outperforms the existing state-of-the-art model.", "weaknesses": "-  While the paper does a thorough job of exploring the design space or structured ablation studies, it does not provide a principled explanation of why certain configurations (or subcomponents) yield performance improvements. Adding a more in-depth empirical and theoretical analysis can address this issue. This can not only strengthen the contributions but also offer a more principled foundation for future research in this area.\n- Although the best combination shows performance benefits, its novelty is limited. The only differences between the best model and the existing state-of-the-art (IsoNet) are the interaction stage and non-linearity (which have been proposed in existing studies). Without providing principled rationales (as the first bullet), this could make the contributions appear incremental.\n- The dense presentation makes it challenging for readers to immediately see the paper’s structure and key subcomponents. I think the authors should present a clearer organization and structured outline. In particular, Figure 1 is hard to interpret. I think that the authors can provide more human-readable visualization. Plus, please put some margin to the bottom of Figure 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}, {"review_id": "6AuXUgmf5P", "reviewer": "Reviewer_VJh8", "summary": "This paper studies the problem of neural network based subgraph matching, focusing on several model/system design choices, e.g. early vs late interaction, trainable vs fixed non-linearity, etc. A set of guidelines and best practices are outlined which are the key contributions of this work.", "questions": "1. How is this work related to neural architecture search (NAS)? It might be worth comparing/surveting works in NAS, e.g. https://arxiv.org/pdf/2403.05064v1, https://openreview.net/pdf?id=GcM7qfl5zY, etc. Referencing such works can position this work better within the broader literature and bring out further discussion.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 3, "strengths": "1. The overall problem formulation is interesting and timely considering the various design choices in subgraph matching literature.\n2. Ample experimental study is performed adding credibility and rigorousity to the findings and guidelines.\n3. Error bar is shown for the results, e.g. in Figure 2.", "weaknesses": "1. It seems all the 10 datasets are relatively small, e.g. up to 50 nodes. I wonder if there is a reason for not choosing much larger graphs, e.g. graphs up to 1M nodes as the target graph to be searched for (while using a small query graph of ~50 nodes).\n2. Some of the paper writing can be made more clearer. E.g. “Challenging the widely\nheld expectation that early interaction is more powerful, IsoNet’s late interaction approach outperforms GMN, even when GMN’s final score computation is made asymmetric” – It is a bit unclear what it means by “asymmetric”, especially due to the fact this is written at the beginning of intro and the audience may not be familiar with this area of research. \n3. It may be useful to introduce/outline the summarized findings at the end of the introduction section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)