Exchangeability of GNN Representations  with Applications to Graph Retrieval
Authors: Kartik Nair
Indradyumna Roy
Soumen Chakrabarti
Anirban Dasgupta
Abir De
Venue: ICLR 2026 Oral (2026)
Keywords: GNN
Locality sensitive hashing
Primary area: learning on graphs and other geometries & topologies
TL;DR: It shows that graph representations are exchangeable random variables which can help in LSH in graphs

Abstract: In this work, we discover a probabilistic symmetry, called as exchangeability in graph neural networks (GNNs). Specifically, we show that the trained node embedding computed using a large family of graph neural networks, learned under standard optimization tools,  are exchangeable random variables. This implies that the probability density of the node embeddings remains invariant with respect to a permutation applied on their dimension axis. This results in identical distribution across the elements of the graph representations.  Such a property enables approximation of transportation-based graph similarities by Euclidean similarities between order statistics. Leveraging this reduction, we propose a unified locality-sensitive hashing (LSH) framework that supports diverse relevance measures, including subgraph matching and graph edit distance. Experiments show that our method helps to do LSH more effectively than baselines.

Published as a conference paper at ICLR 2026
EXCHANGEABILITY OF GNN REPRESENTATIONS WITH APPLICATIONS TO GRAPH RETRIEVAL
Kartik Nair*
Indradyumnna Roy IT Bombay nd Anndrroy 10csey wit...c.bb.iiiii...
Soumen Chakrabarti IIT Bombay
Carnegie Mellon University ksnai rêcs. cmu. edu
soumen@cse. iitb.ac.
Anirban Dasgupta
Abir De IIT Bombay abirêcse. iitb.ac.in
ITT Gandhinagar ani anirbandge siirranndeiiggg.cco ac.in
ABSTRACT
We discover a probabilistic symmetry, called exchangeability, graph neural networks (GNNs). Specifically, we show that the trained node embedding computed using large family of graph neural networks, learned under standard optimization tools, are exchangeable random variables. This implies that the probability density of the node embeddings remains invariant with respect to a permutation applied on their dimension axis. This results in identical distribution across the elements of the graph representations. Such property enables approximation of transportation- based graph similarities by Euclidean similarities between the sorted embedding elements in fixed dimension. This allows to propose unified locality-sensitive sensitive hashing (LSH) framework that supports diverse relevance measures for graphs. Experiments show that method provides more effective LSH than baselines. Code can be found at ht /tttts://rebrandd....
INTRODUCTION
In their seminal work, Hecht- Nicht-Nielsen (1990) first demonstrated that the output of multi-layer per- ceptrons (MLPs) remains invariant under suitable permutations of the weight matrices across layers. Since then, such weight-space symmetries have been widely recognized, and have resurfaced with the advent of deep learning (Neyshabur et al., 2015b; Freeman al., 2016; Brea et al., 2019). Recent works (Bui Thi Mai et al., 2020; Godfrey et al., 2022) characterized such symmetries for different activation functions. Beyond academic interest, weight space symmetries underpin several practical advances: for example, they enhance model training (Neyshabur et al., 2015b), equivariant architec- ture design (Cohen et al., 2016; Maron et al., 2019; Navon et al., 2023), enable model merging (Peña et al., 2022; Ainsworth et al., 2022), motivate data augmentation (Schürholt et al., 2021), etc. They also yield deeper characterizations of geometry and loss landscapes (Brea et al., 2019; Simsek et al., 2021; Entezari al., 2021). These works focus algebraic symmetry, and treat them in isolation from training. This leaves unaddressed the probabilistic symmetry structures in GNNs that emerge naturally during standard training, starting with random model initialization.
Our contributions We aspire for broad understanding of exchangeability in a wide variety of message passing graph neural network (GNN) topologies. This of particular interest to us hashing, indexing, and scalable graph retrieval using such neural representations (Roy al., 2022; Chakraborty et al., 2025). Some specific cases of exchangeability in multi-layer perceptrons and CNNs have been reported independently in contemporaneous work (Yi et al., 2025a), but without connections to hashing and search.
because of the recent research focus on locality
- -Characterization of exchangeabiliy: conditions, the elements of node embeddings computed by a trained GNN are exchangeable random variables, where the randomness is induced by the initialization of model parameters. Let x(u) R denote the embedding of node u, produced by a trained GNN. Then, the joint distribution of its components x <1u)[1], ... <=)) [D] is invariant under any permutation of the embedding dimensions E [D]. This has a significant consequence: the components (1))[]].- x()) [D) are identically distributed random variables. Therefore, when averaged across multiple random seeds, the expected embedding matrix [[ (u)]uev] collapses to a rank one matrix.
We establish new property of GNNs:
under standard
Work done while IIT Bombay

---

Published as a conference paper at ICLR 2026
We would like to highlight that, we show such exchangeability holds for wide spectrum of GNNs and graph transformers; and several optimizers, e.g. SGD, Adam. In view of GNNs' known propensity for spatial oversmoothing (Roth et al., 2024) and recent discoveries of output rank collapse of transformers (Dong et al., 2023; Naderi et al., 2025), and sequential state space models (Joseph et al., 2025), this result is of independent interest.
-Applications to graph retrieval: In neural graph retrieval, the goal is to find corpus graphs C= (.) most relevant query graph Gg. Recent studies (Jain al., 2024; Zhuo al., 2022: Fey et al.. 2020) make it clear that transportation-basee relevance distance between node embeddings performs significantly better than single-vector veettrr aggregation and graph kernels (Roy et al., 2022; Zhuo et al., 2022). Exchangeability enables efficient graph retrieval in two steps:
Consider embeddings in one dimension (D = 1). In this case, the transportation distance between two sets can be solved exactly by sorting the points in each set and matching them in order. For example, suppose we use GNN to produce one-dimensional embeddings sru)) E IR. Then, given two graphs Gg and Ge. each with n nodes, the transportation distance between their embedding sets is Transport ( (w))())) (w)))
(1) Approximating transportation similarity with 1-D Euclidean approximations:
I|- In higher dimensions (D > 1), however, computing transportation- based distance (or transportation -baeed similarity) is substantially more complex, with exact algorithms scaling for n nodes as O(n") and often requiring O(n²) approximations such as Sinkhorn iterations. Exchangeability provides a way around this: since embedding coordinates are identically distributed, each dimension yields a concentrated estimate of the underlying transportation- based similarity. Instead of solving the full high-dimensiona. transportation-Be based similarity, we approximate it by aggregating D simple Euclidean similarities across dimensions, thereby reducing "transportation distance between high dimensional vector sets" to an estimate based on per-dimension sorted orders, which is more amenable to indexing.
()SOR((((0)) (u))) SORT((2(()) (4)) (u)
(2) Locality sensitive hashing (LSH)) for graphs: LSH enables sublinear-time retrieval by hashing similar objects into the same bucket (Gionis al.; Indyk et al., 1998; Charikar, 2002). Exchangeabilityy lets us approximate costly transportation-bast based similarity with simple Euclidean similarity across embedding dimensions, making existing LSH schemes directly applicable. Notably, LSH for asymmetric transportation based similarity has remained unexplored; our approximation provides the first principled approach, leveraging Roy et al. (2023). This yields unified LSH framework that supports diverse graph relevance measures, from subgraph matching to graph edit distance with general costs.
2 PRELIMINARIES
Notation
For a graph G = EV, E). we denote A as its n x n adjacency matrix. We write [++ m - 0} as the hinge ReLU function, P,, as the set of n x n permutation matrices and [n] = (,,,.. n for any integer n. We denote P and π to indicate n and 7) dimensional permutation matrices, respectively, which are applied on the nodes and their embedding vectors respectively. [+] E {0.1] is indicator function. In the context of graph retrieval, we denote query graph Gg., corpus graph as G. with VVg1 = |Val
after padding with suitable number of nodes; and, the set of corpus graphs as C. We also use Ay and A. to denote their n x n adjacency matrices. We use p(.) to denote the density of any random variable. Given group G. function f is G-equivariant (G-invariant) if [ggx) = (xx) (resp.. /(ga) = (ar) for all g E G.
Node embedding computation using GNN Given the number of message passing steps (or layers) K and the dimension of node embeddings D, a graph neural network (GNNg) computes node embeddings (u) GNNo(G)
IR" for u V using K message passing steps. For brevity, we drop K to write æuw) = æx (u). We compute the embedding matrices X e Rx as
X ==x(u)) [==(u] X d] E RR denotes the d-th column of X. The operator SORT(.) sorts input vector in decreasing order. In the context of graph retrieval, we denote (49) (u) and (e())
(u') to denote embeddings of node u E [n] and u' E [n] in the query and corpus graphs G. and Gos respectively. Similarly, we use ( [x=()) (u)]we(n) R D and (e) = (z(()((')) (u'))e'(w) E R denote
the embedding matrices.
The parameters& 0 of the GNN are learned by minimizing task specific loss function, which denote as loss( We assume that weights in are initialized via iid sampling from popular distributions, and then some popular gradient-based update recipes used for training.
2

---

Published as a conference paper at ICLR 2026
Exchangeability Exchangeabilityy implies that the joint density of the elements within vector is permutation invariant with respect to the ordering of the elements.
Definition 1 (Exchangeability (Aldous, 1985)). Let Ya E Rn be random vectors E [D] We say Yı,..., YD are exchangeable, if for all permutations тI [D] + [D], the probability densiry functions of the sequence of vectors {Y,,.., Yn} is the same as that of (Yx())-- .... (D(D)), i.e.,
Pv.....M. (y1,...D)) = (((D))) (.)....D) for all realizations: Ya yd ya d E [D].
Order statisties For a vector a, we denote its order statisties by SORT(a). obtained by sorting its entries in decreasing order. For the node embedding matrix X, we will frequently use SORT(X) [: d) the order statistics of the d-thh embedding dimension across all nodes.
Overview of our analysis (1) Distinct from algebraic symmetry, we characterize a new type of probabilistic symmetry in the node embeddings X of graph G, which is computed using X(; DJ trained GNN starting with random model initialization. Specifically, we show that [
are exchangeable random variables, where the randomness induced by the initialization of the model. (2) Given a query-corpus graph pair (Gg. Ge), we exploit this property to approximate the vransportation-basee similarity between X and X using Euclidean similarity between the order statistics SORT(* X [+) d)) and So
d)) for d E [D]] (3) Building upon the proposal of Roy et al. (2023), we develop unified LSH (Charikar, 2002) method for several graph relevance measures using the Fourier transform on the order statistics vectors. We further show that the resulting algorithm is valid LSH for the original transportation-basee graph similarity.
3 EXCHANGEABILITY OF GNN REPRESENTATIONS
In this section, we characterize the probabilistic symmetry of node representations, explicitly incorporating the effect of model training. Specifically, given the node representation matrix [ D) are exchangeable random
X x [=<x(\)]ue[a) E RaXD = GNN, we show that variables (Definition 1) across the axis of the embedding dimension, where X|: d] = [=x(u) [d]] [e]]] We first describe the setting for our analysis, followed by a high level explanation on why exchange- ability will hold. Finally, we present the formal characterization.
3.1 SETTING
We provide the four components of our settings. We emphasize that they are presented primarily for technical completeness. They are not restrictive and, in fact, capture broad class of settings.
(1) Broad class of GNN architectures We consider the wide variety of GNN architectures, which are listed in Appendix F. This list includes gated GNN (Gilmer et al., 2017), GIN (Xu al., 2019), GAT (Veličković et al., 2018), GCN (Kipf et al., 2017). Our analysis is likely extend beyond these cases, and also applies to graph transformers (Appendix F).
(2) IID initialization of the parameters within a layer The entries of the parameter matrix within each layer are initialized in an i.idd manner. This covers standard model initialization schemes, including Kaiming (He et al., 2015) and Xavier initialization (Glorot et al., 2010).
(3) Permutation invariance of loss function We consider loss functions that are invariant to permutations of elements in the node embedding vectors. This condition holds naturally in several settings, including graph retrieval. Here, the loss, whether binary cross-entropy or pairwise ranking, depends on the similarity between (Gg: G.) via the transportation plan between X (1) and X Since this similarity is invariant under permutations of embedding elements, the loss is likewise cermutationninvaiian
This also applies to link prediction, when the similarity hetween nodes u and is computed as the dot product a=) x<(),, which is permutation invariant w.r.t. elements of æ. (4) Broad class of optimizers Our results hold for a broad class of gradient-based optimizers, viz. SGD (Zhang, 2004), Adam (Kingma et al., 2015), etc.
3.2 WHY EXCHANGEABILITY HOLDS: A HIGH LEVEL EXPLANATION
Exchangeability among initialized model parameters Training begins with i.i.d. initialization of the parameter matrices. Formally, consider a weight matrix θ whose entries are drawn i.i.d. from a common distribution. Its joint distribution is invariant to column permutations: for any permutation matrix π, p(@) = p(OT). When θ is applied to an input row vector x, the output x' = z is equivariant to column permutations of θ: C θT x' + a I... Although permuting O
3

---

Published as a conference paper at ICLR 2026
changes the values of x', an i..d. initialization ensures that all permutations equally likely, the distribution of x' is invariant: p(a') = p(æ'T). This statistical symmetry is precisely what we mean by exchangeability of hidden units at initialization. Nonlinear activations 0, such as sigmoid tanh, being identical and applied pointwise, preserve this symmetry.
Exchangeability in MLP Training Consider two-layer MLP with weights v O and nonlinear activations o, which maps an input row feature vector feat to an output representation æ via (fe(at ) ))). ). As discussed, at initialization = 0), exchangeability holds by construction: the entries of O (θ at = 0) are i.i.d., so p p(Oo) = p( OO ) and consequently p(x) = p(æTT) As noted in Section 3.1 (3), the loss function invariant permutations of the embedding dimensions. With all other randomness fixed by seeding, permuting the columns of Oo yields identical losses and hence equivariant gradients. Consequently, the training trajectories are permutation permutation-equiiaaiantt
for any π, O + 0π = + θ, for all epochs t. Combining p (Qa) p' (,x)) at initialization, with permutation-equivaree training dynamics, we obtain p(O,) = p(O,T) and hence p(æ) p(æT) for all t 0.
3.3 FORMAL CHARACTERIZATION OF EXCHANGEABILITY
Overview Here, we seek to establish the afore-mentioned arguments for GNN to prove the ex- changeability of the elements of the node embeddings. We prove this using four steps:
(1) Permutation induced parameter transformation on GNN (Lemma 2): Given GNN₃ with parame- ter set consider any permutation π Pp. We show that there exists bijective transformation T on 0 such that, for 0' = x (f), the elements of the node embeddings are permuted by π, i.e. X H XT. We refer to 7 as a permutation-inducing transformation corresponding to π.
(2) Gradient equivariance (Lemma 3): We show that the gradient of loss is equivariant with respect
to permutation inducing transformation TT.
(3) Invariance of the probability density of model parameters (Lemma 4): We show that any stage of training, the model parameters are exchangeable- the probability density of the parameters 0 remains invariant to the transformation 7r.
(4) Result on exchangeability (Theorem 5): Using (1-3), we show that X|: [|, D) are exchangeable.
Warmup: Constructing In for 2-layer MLP We are given an MLP of the form æ (fefet O)). If we want to reorder by given permutation æ,, we will transform θ - Or which will result in æ + æτ. Equivalently, suppose we write 0 = [ T θ), then, we can introduce a bijection Fx by F (0) := Diag(Il, T), which will result in output equivariance + æπ..
Permutation induced parameter transformation on GNN Constructing a similar transformation H is more involved for GNNs. The difficulty stems from the iterative message passing protocol: permutations of parameters in one layer propagate through neighborhood aggregations, which can entangle the symmetry across layers and makes it hard to identify Tx for popular GNNs, e-g., gated GNN (Li et al., 2016), (Gilmer et al., 2017) which is widely used in graph retrieval (Li et al., 2019; Roy et al., 2022; Jain al., 2024). Nevertheless, in the following, we formally establish that such transformations can indeed be derived for GNNs (proven in Appendix E).
Lemma 2. Given a graph G and a GNN architecture GNN, described in Appendix F, let the node embedding matrix of G be X = GNN,(G') E RaxD Then, for any permutation matrix т E PD. there exists a bijective transformation I with [Det (Ør, (0)/80)] such that X GNN (G) We call i a model transformation induced by permutation π.
Given this characterization, we seek to reduce the problem of establishing exchangeability to estab- lishing probabilistic symmetries in the model parameters 0 with respect the transformation Fz.
Equivariance of gradient under permutation induced parameter transformation Since the loss function invariant to any permutation π of the node embeddings, it is also invariant to the transformation F on 0 (Lemma 2). As a result, the corresponding loss landscape exhibits symmetry under Fx. This symmetry, in turn, implies an equivariance property for the gradient, as formalized below (proven in Appendix E).
Lemma 3 (Gradient equivariance). Given the setting described in Section 3.1. Let I be the transforattinn the GNN parameters 0, induced by permutation n, introduced in Lemma 2. We denote the loss function as loss((), Then the gradient of the loss V Voloss(f) is equivariant under transformation Tx of the parameters 0.
4

---

Published as a conference paper at ICLR 2026
Invariance of probability density of model parameters under the transformation I Suppose we shuffle the initial parameters within a layer. Then, from the gradient equivariance property (Lemma 3) the resultant trajectory {&e It 0} of 9 at different epochs t, will undergo an equivariant transformation with respect to permutation-induueed bijection 1'x. Since p(0b) = pL (0o)), the observation will lead to invariance of the probability density of 0g for 2 too, as stated below (proven in Appendix E).
Lemma (Invariance of density of (0)). Given the setting described Section 3.1. Let f0r 0} be the trajectory of the parameter of GNN across different training epochs 2 0. Then, we have: p(0+)= = (0))) for all t 2
Key results on exchangeability Using Lemmas 2-4, we can show our key exchangeability results, stated as follows (proven Appendix E).
Theorem 5 (Exchangeability of embedding elements). Given the setting described in Section 3.1. Then, X = GNN, are exchangeable random variables, where the randomness is induced by the model initialization prior to training. That is, pl X) p xt).
Note that the above theorem can also be generalized for a joint distribution over multiple graphs. For example, in graph retrieval, is necessary to compute the joint distribution of the embeddings of the query and corpus graph pairs (G,, G.). In such cases, we have the following result (proven in Appendix E).
Proposition 6. Given two graphs Gg. Go. let the settings in Section 3. hold true. Specifically, let us assume that the loss function be invariant to simultaneous permutations of the embeddings (4) GNNo(Ga) and X (c) GNNo(G.)) Then, Y [x(9), X(0) E R22nDD satisfies p(Y) p TT).
Scope of the result We imposed few simplifying assumptions only for brevity. In fact, our exchangeability results continue to hold even when these conditions are not explicitly met, including architectures that incorporate more complex operations such as normalization layers. Moreover, our results remain valid even when the loss itself is not permutation-invariee losses may still exhibit invariance under a joint transformation consisting of (i) a permutation of intermediate representations; and, (ii) corresponding parameters in the subsequent layer (Appendix F.1.6).
This is because such
ietiuutttiooinnnuuee transformation of the
APPLICATIONS TO GRAPH RETRIEVAL
Graph retrieval In graph retrieval, we are given large number of corpus graphs C= {Ge) and the goal is to efficiently find out top-b graphs that are relevant to a given query Gg. In typical real-world application, the corpus database contains large number of graphs, necessitating efficient indexing and retrieval mechanisms, akin to other retrieval tasks. In this section, we exploit exchangeability to design a locality-sensitive hashing (LSH) method (Gionis et al.; Indyk et al., 1998; Charikar, 2002) that accommodates a wide variety of transportation--asse graph distance measures in unified framework. This would allow us to return the set of relevant items in a query time that is sublinear in the number of corpus items |C|.
We proceed in two steps: (1) We leverage our results on exchangeability (Theorem 5 and Proposition 6) to approximate the transportation-bast for LSH. (2) We build upon the proposal of (Roy et al., 2023) to design LSH for such approximate Euclidean similarity, which is also valid LSH for the true transportation-base
graph similarity using Euclidean similarity, which is suited
Euclidean similarity.
4.1 USE OF EXCHANGEABILITE TO DERIVE SIMILARITY OF GRAPHS IN EUCLIDEAN SPACE
Transportation-basee relevance distance between graphs It is well established in the literature (Roy et al., 2022: Zhuo et al., 2022; Fey et al., 2020; Jain et al., 2024; Bommakanti et al., 2024) that transport distance between sets of node embeddings across query and corpus graphs results in better accuracy than graph kernels or pooled single-vector representation. These works have proposed different notions of transportation distances, e.g., hinge distance for subgraph matching (Roy et al., 2022), graph edit distance (Jain et al., 2024; Zhuo et al., 2022, GED), etc. We unify these distances under common relevance distance, computed using function p convex, potentially asymmetric
5

---

Published as a conference paper at ICLR 2026
and decomposable between dimensions, i.e. p(x) = EdelD p(z|d)).
AGGo: Ga)
min Σ
Σ
p(x x (u))dd Plu, u']
(1)
PEP, a
a.a' de(D)
If p()) [o],, then A (Ge, Ggy) captures the hinge distance for subgraph isomorphism (Roy et al., 2022); if p()) Bgg [ + eg x [-+]+ for some egy Eg > O. then A(Ge, Gg) captures GED, where Bgy and egg denote the costs of edge deletion and addition, respectively (Jain et al., 2024).
Distance to similarity Suppose the elements of the node embeddings are bounded by mmax. Given cost function p. we compute Pmax = - p(x - x²). We define a score function s(x) - Pmax p(x), which converts the transportation-based distance in Eq. (1) to the following transportation-basedd similarity measure.
sim GT))
max PEP
E
E
sax - (v)) Plu,u', u').
15,00 dE(D)
Approximation of transportation-based similarity into Euclidean similarity Owing to the random initialization of the parameters 0, (9( and (1')) are random variables, which makes (im Gg)) random scalar. Now, sim(Ge. Gg) is not amenable to indexing and search. To tackle this, we approximate this similarity using a simpler Euclidean similarity sim Gg), focusing on a single dimension d. This approximate similarity is also a random variable, due to the parameter initialization, but more amenable to approximate nearest neighbor search. As we will see shortly, sima Gg) serves scaled approximation of sim, Gg) with high probability.
Proposition 6 suggests that the node embedding pairs of Gg and Ge are exchangeable across dimen- sions i.e., if Y [x;;; x then we have: pYY = p(YT) for any permutation π. This means that the elements of the embeddings have an identical distribution across different dimensions. This also yields an identical distribution in the output of the score function s(.) across different embedding dimensions. This, in turn, allows us approximate the score by evaluating it in any one dimension d:
Sima Gg) = max PEP
Σ 2L.
(z (w)ld ( (d'Id) Plu, n']
(3)
By restricting Eq. (3) to a single dimension d E [D], the problem reduces to transportation cost between scalars. This together with the property that s(-) is concave (as p is convex) allows us to simplify Eq. (3) (Appendix E) into a similarity function between the order statistics or the sorted vector of the node embedding elements in a fixed dimension. Specifically, we compute the order statistics: SORT(X ( [:, d)) and SORT (X ( [:: d)) and express the similarity function for dimension d in Eq. (3) as the similarity between these order statistics:
sima(Ge. G3)) = (SORTT (x (4) [:,d)) SORT (x d))
(4)
As the distance function p is decomposable p(xr) Ea p(=]d)) the score function satisfies: s(xr
Ea s (æzdd) Hence, we overload 8 as a function on scalars in Eq. (3), as well as vectors in Eq. (4).
As exchangeability results in identical distribution of the above similarity across the dimension d, we will have the following concentrations (Proven in Appendix E):
Proposition 7. For any > 0,6 > 0, setting D दमz ensures that, for some 30 = OD()), we have:
Pr [sim(Ger Gg)/D (i., Gg) sc) 2 1 - 1-08
(5)
4.2 LOCALITY SENSITIVE HASHING OF GRAPHS
Locality sensitive hashing Locality Sensitive Hashing (LSH) maps queries and corpus items to the same bucket with high probability when they are similar, and with low probability otherwise (Gionis et al.; Indyk et al., 1998; Charikar, 2002; Neyshabur et al., 2015a). This enables retrieving relevant graphs from {G.} by searching only within the bucket where G, gets hashed.
Why will existing approaches not work? If s-) in Eq. (4) were a symmetric Euclidean distance, we could directly apply existing LSH methods, such as grid-based projections for L1 (Andoni et al., 2006) or line projections for L2 (Datar al., 2004). However, various common graph similarities inherently asymmetric (refer to the examples below Eq. (1)). To address this limitation, we propose a new framework for LSH of graphs, starting with the definition of asymmetric-LSH for graphs under a general similarity measure (Neyshabur et al., 2015a).

---

Published as a conference paper at ICLR 2026
Definition 8. Given Q, C, the domain of query and corpus graphs and similarity measure sim
C' C R. A distribution over mappings F Q + N and H. - N is called a (So. 7 p. p/)-
asymmetric LSH (ALSH) if. with p pl and r (0, 1). the following conditions are satisfied.
(1) Pr f-r N (f(Gg) ([(Gg)))(GG)))) 2 p, if sim(G.: G4) 2 So.
(6)
(2) PT h(G.) s p', if sim Gg) S 7:50
Intuition behind our approach Suppose we estimate two vectors Tq.d and Te,d. such that the Euclidean similarity for dimension d in Eq. (4) can be expressed as sima(Ga (Gg, Go) xx cos (T ga d, Te,a). Then, the random hyperplane projections f(Gg) sign( w T Tq.d) and h( sign(w (w Tea) with w (0, 1), will be valid LSH for sima (Charikar, 2002; Neyshabur al., 2015a). Since this Euclidean similarity is only scaled approximation of the transportation-base (Proposition 7), the same random hyperplane projection is valid LSH for sim sim G²). Hence, we now focus on obtaining such vectors T and Te.d whose inner product approximates sima-
similarity sim Gq)
GRAPHHASHE ASH: Our approach for LSH for graphs In their seminal work, Rahimi et al. (2007) showed that kernels of the form <( -x') can be approximated using a product of finite-dimensional
Fourier features. Our approximate similarity sima(G Gg)
(XXORT(((0) [;, d]) SORT X [
.d)) has similar structure. However, 8(-) is generally not a kernel, because the underlying distance measure can involve complex asymmetric structure (see examples following Eq. (1)). Hence, their method cannot be directly applied. Roy et al. (2023) extended the approach to hinge-based similarities. We build on their idea and generalize it to arbitrary graph similarity functions. Specifically, express sim, Ge, Gg) as an integral over dot products of two real vectors.
Proposition 9. For each u E [n], there exist vectors Fu,a(weu) Fod(usu) E R with different Fourier frequency wn for each node u, such that: simalGes Gg) (Eq. (4)) can be expressed as:
sima (g) = EE/
F Fg,a(wsu) ME(N) W.ER
(F Fe,a(ws)) duu
To approximate the above integral into finite terms, we design the frequency sampling distribution as p(w.) x [S(wa)]. where 5(w)) is the Fourier transform of the scoring function s(o) when
applied on scalars. Given w = [wi,.., Wn], we use (ww) = [Fe,((ww)) /p(Ww)luem) to obtain an equivalent expression for Eq. (7), as follows:
sima(Ge, Gg)) = E pp()) (T (w))((w) T [e)a(w]]
(8)
We prove it in Appendix E. One can show that 1IT q.a (w))2 (w)dd for all G2 and G.. Next, sid p(w) to compute To.d (E RR R44M) A (w))) IeEM, which will give: we draw (w(m))
(im Gg) cos(T q.d: Te,dl
Overall routine (GRAPHHASH) Finally, we use the random hyperplane method to compute hash codes f f(G)) and h h(G)). Given dimy, the dimension of Ta and dima, the hashcode size, we first draw W E Iedima xdimr with W [r. t] iid ~ (0. 1) and then set (G.) sign( sign(Wf. c..) (Algorithm 1). During query execution, we return top-b corpus graphs {G.} from the hash bucket f(() (G₂) sign( WT ... (Algorithm 2). The family of these hash functions gives a valid LSH. We call our method as GRAPHHASH. We provide LSH guarantees for GRAPHHASH Appendix
Algorithm 1 Indexing phase of GRAPIHASSI
Algorithm 2 Query phase of GRAPIHAASII
Require: Corpus {C.), score function s(e)
Require: Query Gg. stored hyperplanes W, frequency samples (w (m) 1
frequency samples (m)).
1: [i. jl NO 1), E [dima].j E [dimr].
1: R 4- 0
2: for all G. and E [D] do
2: for d [D] do
3: Use s(-) to compute (o.(( from
3: Given s(-), compute F Fg.a(wo from SORT(X ()) d)) for all d, m
SORT(X (to) d)) for all d,
4: Compute Te from (F=ra(ew(")) ("))) and (px(w(")))
4: Compute L,n from
{Fe,a (m))) and (px(w(m)
5: 1((4) (G.) = sign(WT...))
5: f(a0 (G.) sign(WTT,.))
6: Store G. in the bucket indexed by A (G.)
6: R R+RUIC RUIG.
G. E Bucket (4) (G,))} 7: Return Top-b graphs from R
7: Store W for use in the query phase

---

Published as a conference paper at ICLR 2026
I Sonn oxs uas
Dousity L.
0.s0
Deasity
0.5
0
0
x [e
x [
(a) Ge, v
(b) Initialization
(c) Epoch
(d) Epoch 20
Figure 1: Empirical probability density of X [v. dl the highlighted node v in the example corpus graph Ge in cox2, obtained using 5000 independently trained instances of the GNN model for
Subgraph Matching based graph retrieval. Panels (b)-(d) show the density of X (0) [v) d] after model initialization and different stages of training.
5 EXPERIMENTS
We organize our experiments in two parts: first, empirically validate the exchangeability property of GNN-based graph embeddings (Theorem 5); second, we evaluate the retrieval effectiveness of GRAPUHASII across multiple datasets. Appendix H shows additional experiments.
5.1 EMPIRICAL VALIDATION OF EMBEDDING EXCHANGEABILITY
Validation using marginal distribution We verify a necessary condition of exchangeability; identical marginal distribution of the embedding elements for a fixed node across independently initialized and trained models. We train 5,000 independently initialized GNN models on small subset of the cox2 dataset, consisting of 1,024 query-corpus graph pairs. Each model is trained for 20 epochs using the Adam optimizer with an embedding size D = 10, by minimizing a ranking loss for subgraph matching based graph retrieval task. For each trained model, we extract the embedding vector for a fixed, node v from one graph G. and record the scalar values ( [v, for [D].
This yields an empirical distribution of X [v, d] across model instances for each d [D].
Figure shows the empirical probability density of ( [v. d] for three representative dimensions 1,5, 10, at three points in training: initialization, epoch 8, and epoch 20. We observe that the distributions remain identical across the embedding dimensions throughout training. This validates the necessary condition of our result that the embedding dimensions are exchangeable under random initialization and remain so despite backpropagation, non-convex losses.
Direct test for exchangeability The marginal distributions do not capture more complex de- pendencies between dimensions, which is why we make use of the maximum mean discrepancy to quantify the gap between the distribution of
cox2 (GED) 3388 10-5 + 2.69 10-5 Cox2 (SM) 1.18 x 10-6 6
+ 3.28 x 10-5
Table 2: Estimator for unbiased MMD for px and pxw for cox2 dataset
X and X XT. We sample 100 different permutations and compute the estimator of MMD for each permutation, and report the average over these 100 observations. Note that estimator of MMD can be negative. Table 2 shows that the MMD values are extremely small for cox2dataset for both GED and subgraph matching (SM). These results strongly support that px and pxn close.
Rank of E[X] Another conse- quence of exchangeability is that the expectation of the graph embedding matrix E[X] is rank one. Conse- quently, we expect the leading singu- lar value of the sample mean graph embedding matrix to be significantly larger than the rest. Figure! shows multi- ple runs, where T1, .,,,, are the singu- lar values of E sorted in decreas-
1.00
0.94
0.95
"6" 0.92-
0.90
0.90
10'
10a
10a Initializations
10'
# Initializations
a?
how the ratio Σ. o?
varies
(a) Graph from ccx2 (SM) Figure The relative size of the top singular value of the mean (trained) embedding across model initializations.
(b) Graph from cox2 (GED)
ing order. We observe that this frac-
tion converges to one, which indicates that the rank of the embedding matrix is 1.
8

---

Published as a conference paper at ICLR 2026
5.2 EVALUATION OF GRAPHHASH's RETRIEVAL PERFORMANCE
We evaluate GRAPHHASH against existing baselines on four datasets to assess retrieval accuracy- efficiency trade-off's across indexing strategies.
Setup We construct retrieval datasets using four real-world benchmarks from the TUDatasets (Mor- ris et al., 2020): ptc-fr, ptc-fm, cox2, and ptc-mr. Each dataset consists of 500 query graphs and a corpus of 100,000 graphs, following related work (Roy et al., 2022: Lou et al., 2020). We generate binary relevance labels under two asymmetric graph similarity signals: (1) Subgraph Matching (SM): Relevance is determined using the VF2 subgraph matching algorithm (Hagberg al., 2020). Here, we set binary relevance eel
c: Gg) = [Gg C. Gel. where [+] is the indicator function. (2) GED: We use the GEDLIB toolkit (Blumenthal et al., 2019) to compute edit distances with asymmetric costs og
(insertion) and cg (deletion). followed by thresholding to obtain binary relevance. Here, we set rel G₂)) = [GE G₂)) I T], where 7 is threshold. For each supervision type, we train a separate transport-based scoring model using the relevance distances for Subgraph Matching and for GED. The model is trained using pairwise ranking loss (Roy et al., 2022; Jain et al., 2024) of the form Eg Gecrl((G..,,==I..''vlv
)=0= (G,, G₂) A(G Gg) + 7]+ where y is fixed margin, and (:;:)) denotes the transport-based relevance distance (Eq. (1)). We evaluate retrieval performance using both MAP and NDCG. The analysis presented below focuses on MAP, while NDCG results and additional experiments are in Appendix H.
We benchmark GRAPHHASH against five competitive ANN methods adapted to graph retrieval. These include single-vector and multi- indexing paradigms. (I) FourierHash (Roy et al., 2023): It implements an LSH tailored for initriinvariant asymmetric distances by projecting graph emnbeddings into the Fourier space. Each graph G. is represented as single vector
V. Evev, =(u).
where X = [a (e(w))uetwg (II) Random Hyperplanes (RH) (Charikar, 2002; Indyk et al., 1997): It serves a classic LSH baseline, where we directly hash mean pooled graph representations using random linear projections. (III) IVF (Douze et al., 2024): It follows the FAISS-based ColBERT- style approach, constructing dense inverted index over the collection of corpus node embeddings, and probes with individual query node vectors, followed by aggregating the hits at the graph level. (IV) DisKANN (Simhadri et al., 2023) follows similar multi-vector setup but leverages an HNSW index over corDus node embeddines. Lastly. we include a Random baseline that retrieves a uniformly
GraphHash
Hot
(Subeampled)
DisKANN
IVE
Random
0.4
0.4
0.4
0.4
MAP
MAP
MAP
MAP
0.2
0.0
0.0
0.0
0.0
25K 50K 75K 100K # Retrieved Graphs
25K 50K 75k 100K Retrieved Graphs
25K 50k 75K 100K # Retrieved Graphs
25K 50K 75K 100K
# Retrieved Graphs
ptc- fm (SM)
(b) cox2 (SM)
(c) ptc-fr (SM)
(d) ptc-mr (SM)
0.4
0.4
0.2
0.3
0.5
MAP
0.2
MAP
0.2
0.2
0.1
0.1
0 25k 50K 75K 100K # Retrieved Graphs
0 25K 50K 75K 100K
25K 50K 75k 100K
D 25k 50K 76K 100k # Retrieved Graphs
#
Retrieved Graphs
# Retrieved Graphs
(e) ptpt--fie fm (GED) Figure 4: Trade-off between mean average precision (MAP) and number of retrieved graphs, for GRAPHHASH, FourierHashhNet (Roy et al., 2023), Random Hyperplane (RH) (Charikar, 2002; Indyk et al., 1997), IVF (Douze et al., 2isAAND (Simhadrí al., 2023) and Random, across all datascts. Top row: Retrieval based on Subgraph Matching (SM); Bottom row: Retrieval based on GED. Horizontal red line denotes 50% of exhaustive MAP. Our method shows a better trade-off than others in majority of the cases.
(l) cox2 (GED)
(g) pt (GED)
(h) ptc-mrr (GED)

---

Published as a conference paper at ICLR 2026
Results We vary hyperparameters in each method to produce different retrieval set sizes, yielding MAP vs. # retrieved graphs trade-offs shown in Figure 4. The key observations are as follows. (1) GRAPHHASH consistently outperforms all baselines across both Subgraph Matching (SM) and Graph Edit Distance (GED), with FourierHashNet emerging as the next-best method overall. (2) FourierHashNet fails to span the full selectivity spectrum, particularly on SM tasks most notably on ptc-fx fr and pt ptc-mr, where its MAP plateaus below 50% of the exhaustive MAP. (3) RH hashing performs reasonably well on GED, occasionally matching GRAPHHASH in MAP. However, it exhibits high variance at fixed selectivity levels, complicating hyperparameter tuning. On SM tasks, RH performs worse than random, which is expected since cosine similarity over pooled vectors is ill-suited to the asymmetric nature of containment queries. (4) DiskANN and IVF, despite using multi-vector indexing, perform poorly due to their reliance on symmetric similarity metrics like L2 and cosine, which are incompatible with the asymmetric transport- based supervision. (5) Random sampling yields substantially lower MAP compared to both GRAPHHASH and FourierHashNet, highlighting the non-trivial structure captured by learned or LSH-based methods.
Next, we vary dim, (number hash bits) and obtain different trade-off curve between MAP and #no of retrieved graphs. We plot the variation of AUC against dim which shows at around dim,, 10, we obtain an optimal trade-off.
0.3
0.3
0.3
0.3
0.2
0.2
0.2
AUC
AUC
0.1
0.1
0.1
0.1
26
50
25
50
25
50
26
50
dim,
dim:
dim,
dima
(a) ptc- fm (SM)
(b) cox2 (SM)
(c) ptc fr (SM)
(d) ptc mr (SM)
0.30
0.3
0.3
0.25
0.20
0.20
0.15
0.2
0.2
0.15
AUC
ACC
0.30
0.10
0.1
0.1
0.05
25
50
25
25 dim,,
50
25
50
dim,
dim,
dima
(e) pm (GED)
(1) cox2 (GED)
(g) pto-fr (GED)
(h) ptc-mr (GED)
Figure 5: Performance of GRAPHHASH across different choices for dim,, the size of the hasheode.
We summarize the trade-off plot between MAP and the number of retrieved graphs by computing the area under the curve after normalizing the x-axis. We observe that the optimal size is around dim,- 10 across datasets and tasks.
6 CONCLUSIONS
Taking a step beyond existing notions of algebraic symmetries in neural architectures and losses, we introduce the property of exchangeability over neural graph embeddings. We show that this property exhibited by a broad class of graph neural networks across a broad class of loss functions and optimizers. We utilize this property to obtain concentration bound for reducing transport problems on node embeddings, culminating in GRAPHHASH, a unified and theoretically grounded framework for approximate graph retrieval using general transport- based distances. We experimentally validate exchangeability, and GRAPHHASH consistently outperforms strong baselines in retrieval performance under both subgraph matching and edit distance supervision. Future work might explore other consequences of the phenomenon on learning and training dynamics. It may be worthwhile to extend the framework similarities over richer class of similarity functions between three dimensional molecular structures, 3D objects, etc.
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This work makes an algorithmic contribution and uses only publicly available, non-proprietary graph datasets under their original licenses. No human subjects or sensitive data are involved. We believe our results advance understanding graph retrieval without raising additional ethical concerns.
REPRODUCIBILITY STATEMENT
We provide code link in abstract, configuration files, and dataset splits to fully reproduce all experi- ments. Hyperparameters, training settings, and evaluation protocols are documented, and scripts are included regenerate the reported figures and tables. In addition, all theorems are stated formally with accompanying proofs in the appendix to allow independent verification of our theoretical claims.
REFERENCES
Samuel Ainsworth, Jonathan Hayase, and Siddhartha Srinivasa. Git re-basin: Merging models modulo permutation symmetries. arXiv preprint arXiv:2209.0453 2022.
David J. Aldous. Exchangeability and related topics, pp. 1-198. Springer Berlin Heidelberg, 1985.
ISBN 9783540393160, doi: 10. 10.10077b160099421.
Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS '2006), pp. 459-468, 2006.
Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high-dimensional spaces. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA '2008), pp. 343-352, 2008.
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David Woodruff. Efficient sketches for earth-mover distance, with applications. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '2009), 2009.
Yunsheng Bai, Hao Ding, Song Bian, Ting Chen, Yizhou Sun, and Wei Wang. Simgnn: A neural network approach to fast graph similarity computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 384-392, 2019.
Benjamin floem-Reddy. Yee Whye, et al. Probabilistic symmetries and invariant neural networks. Journal of Machine Learning Research, 21(90):1-61, 2020.
David B. Blumenthal, Sébastien Bougleux, Johann Gamper, and Luc Brun. Gedlib: A c++ library for graph edit distance computation. In Donatello Conte, Jean-Y Yve Ramel, and Pasquale Foggia (eds.), Graph-Based Based Representations in Pattern Recognition, pp. 14-24, Cham, 2019. Springer International Publishing. ISBN 978-3-030-20081-7
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. 2023.
Salomon Bochner and Komaravolu Chandrasekharan. Fourier transforms. (AM-19), volume 19. Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, July 1949.
Aditya Bommakanti, Harshith R Vonteri, Konstantinos Skitsas, Sayan Ranu, Davide Mottin, and Panagiotis Karras. Fugal: Teature-fortiffie unrestricted graph alignment. Advances in Neural Information Processing Systems, 37: 17:19933-19446 2024.
Johanni Brea, Berfin Simsek, Bernd Illing, and Wulfram Gerstner. Weight-space symmetry in deep networks gives rise to permutation saddles, connected by equal-loss valleys across the loss landscape. arXiv preprint 1rXiv:1907.02911 2019.
Xavier Bresson and Thomas Laurent. Residual gated graph convnets. arXiv preprint, 2017.
Phuong Bui Thi Mai and Christoph Lampert. Functional vs. parametric equivalence of relu networks. In 8th International Conference on Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2026
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chure Chang. A comprehensive survey of graph embedding: Problems, techniques, and upplications. IEEE transactions on knowledge and data (egiheerinng.3(0)1166666666
2018.
Pritish Chakraborty, Indradyumna Roy, Soumen Chakrabarti, and Abir De. Contextual tokenization for graph inverted indices. arXiv preprint arXiv:2510.22479, 2025.
Moses S. Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC '02, pp. 380-388. Association for Computing Machinery, 2002. ISBN 1581 1581134959, doi: 10.1 04455509907.509998
Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. An improved analysis of the quadtree for high-dimensional emd. 2020.
Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. New streaming algorithms for high dimensional emd and mst. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 222-22222222222222222 223233,222 2022.
Taco Cohen and Max Welling. Group equivariant convolutional networks. In International Internattioaalcofffreneee on machine learning, pp. 2990-2999. PMLR, 2016.
John M. Danskin. The Theory of Max-Min and its Application to Weapons Allocation Problems. Springer Berlin Heidelberg, 1967. ISBN 9783642460920. doi: 10.1007997-33642-46099-00
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the 20th ACM Symposium Compula- fional Geometry (SoCG '2004), pp. 253-262, 2004.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing. Generative modeling using the sliced wasserstein distance. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3483-3491, 2018.
Yihe Dong, Jean-Ban Sannttat Cordonnier, and Andreas Loukas. Attention is not all you need: Pure attention loses rank doubly exponentially with depth, 2023.
Matthijs Douze, Alexandr Guzhva, Chengqi Deng. Jeff Johnson, Gergely Szilvasy,
Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. arXiv preprint arXiv:2401.0828/ 2024.
Jian Du, Shanghang Zhang, Guanhang Wu, José MF Moura, and Soummya Kar. Topology adaptive graph convolutional networks. arXiv preprint arXiv:1710. 10370, 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Chi Thang Duong. Graph Embedding for Retrieval. PhD thesis, EPFL, 2022.
David Duvenaud, Dougal Maclaurin, Jorge gguilera-Iparragurre. Rafacl othy Hirzel, Alán Aspuru-Guzik, and Ryan P. Adams. Convolutional networks on graphs for learning molecular fingerprints. 2015.
Tim-
Rahim Entezari, Hanie Sedghi, Olga Saukh, and Behnam Neyshabur. The role of permutation invariance linear mode connectivity of neural networks. arXiv preprint 1rXiv:2110.06244 2021.
Matthias Fey, Jan Eric Lenssen, Christopher Morris, Jonathan Masci, and Nils M. Kriege. Deep graph matching consensus. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: /6/ 1.15400 2016.
12

---

Published as a conference paper at ICLR 2026
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
Emma J Gerritse, Faegheh Hasibi, and Arjen P de Vries. Graph-embedding empowered entity retrieval. In Advances Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14-17, 2020, Proceedings, Part I 42, pp. 90- Springer, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Similarity search in high dimensions via hashing. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB '1999).
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings, 2010.
Charles Godfrey, Davis Brown, Tegan Emerson, and Henry Kvinge. On the symmetries of deep learning models and their internal representations. arXiv preprint arXiv: 14258, 2022.
Aric Hagberg and Drew Conway. Networkx: Network analysis with python. URL: https://networkk. github. io, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Robert Hecht-Nielsen. On the algebraic structure of feedforward network weight spaces. In Advanced Neural Computers, pp. 129-135. Elsevier, 1990.
Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In Proceedings of the 36th ACM Symposium on the Theory of Computing (STOC '2004), pp. 373-380, 2004.
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the 30th ACM Symposium on the Theory of Computing (STOC '1998), pp. 604-613, 1998.
Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, and Santosh Vempala. Docality-preserving hashing in multidimensional spaces. In Proceedings of the twetty-ninth annual ACM symposium Theory of computing, pp. 618-625 1997.
Eeshaan Jain, Indradyumna Roy, Saswat Meher, Soumen Chakrabarti, and Abir De. Graph edit distance with general costs using neural set divergence. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Rajesh Jayaram, Erik Waingarten, and Tian Zhang. Data-dependent Ish for the earth mover's distance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 800-811, 2024. 2024
Federico Arangath Joseph, Jerome Sieber, Melanie Zeilinger, and Carmen Amo Alonso. Lambda- skip connections: the architectural component that prevents rank collapse. In The Thirteenth International Conference Learning Representations, 2025.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, abs/1442.69900, 2014.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
13

---

Published as a conference paper at ICLR 2026
Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized sliced wasserstein distances. Advances in neural information processing systems, 32, 2019.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 14:21618-21666 2021.
Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based commutation-nnvaiiann neural networks. In International Conference on Machine Learning (ICML), 2019.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning, pp. 3835-3845. PMLR, 2019.
Zihao Li, Yuyi Ao, and Jingrui He. Sphere: Expressive and interpretable knowledge graph embedding for set retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Reirieval, pp. 2629 (639-26334, 2024.
Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec, et al. Neural subgraph matching. arXiv preprint urXiv:2007.03092 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In 7th International Conference Learning Representations, ICLR, 2019.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs, 2020.
Alireza Naderi, Thiziri Nait Saada, and Jared Tanner. Mind the gap: spectral analysis of rank collapse and signal propagation in attention layers, 2025.
Aviv Navon, Aviv Shamsian, Idan Achituve, Ethan Fetaya, Gal Chechik, and Haggai Maron. Equiv- ariant architectures for learning in deep weight spaces. In International Conference Machine Learning, pp. 25790-22 25816. 16. PMLR, 2023.
Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric Ishs for inner product search. In International Conference on Machine Learning, pp. 1926-1934. PMLR, 2015a.
Behnam Neyshabur, Russ R Salakhutdinov, and Nati Srebro. Path-sgd: Path-normalized optimization in deep neural networks. Advances in neural information processing systems, 28, 2015b.
Hamid Palangi, Li Deng, Yelong Shen, Jianfeng Gao, Xiaodong He, Jianshu Chen, Xinying Song, and Rabab Ward. Deep sentence embedding using long short-term memory networks: Analysis and application to information retrieval. IEEE/ACM Transactions Audio, Speech, and Language Processing, 24(4):694-707, 2016.
Fidel A Guerrero Peña, Heitor Rapela Medeiros, Thomas Dubail, Masih Aminbcidokhti, Eric Granger, and Marco Pedersoli. Re-basin via implicit sinkhor differentiation. arXiv preprint 12 /2042, 2022.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in neural information processing systems, 20, 2007.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 14541-145555 2022.
Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan 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, NeurlPS 2022, November 29-Decemer 2022, 2022.
14

---

Published as a conference paper at ICLR 2026
Andreas Roth and Thomas Liebig. Rank collapse over-smoothing and over-correlation in graph neural networks, 2024.
Indradyumna Roy, Venkata Sai Baba Reddy Velugoti, Soumen Chakrabarti, and Abir De. Interpretable neural subgraph matching for graph retrieval. In Proceedings of the AAAI conference artificial intelligence, volume 36, pp. 8115-8, 2022.
Indradyumna Roy, Rishi Agarwal, Soumen Chakrabarti, Anirban Dasgupta, and Abir De. Locality sensitive hashing in fourier frequency domain for soft containment search. Advances in Neural Information Processing Systems, 36:56352-56383, 2023.
Yuki Saito, Takuma Nakamura, Hirotaka Hachiya, and Kenji Fukumizu. Exchangeable deep neural networks for set-to-set matching and learning. In European Conference on Computer Vision, pp. 626-646. Springer, 2020.
Filippo Santambrogio. Optimal transport for applied mathematicians, volume 87. Springer, 2015.
Konstantin Schürholt, Dimche Kostadinov, and Damian Borth. Self-supervised representation learning on neural network weights for model characteristic prediction. Advances in Neural Information Processing Systems, 34: 34:16481-16493, 2021.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning. pp. 32-3113-13633.. PMLR, 2023.
Harsha Vardhan Simhadri, Ravishankar Krishnaswamy, Gopal Srinivasa, Suhas Jayaram Subramanya, Andrija Antonijevic, Dax Pryce, David Kaczynski, Shane Williams, Siddarth Gollapudi, Varun Sivashankar, Neel Karia, Aditi Singh, Shikhar Jaiswal, Neelam Mahapatro, Philip Adams, Bryan Tower, and Yash Patel. DiskANN: Graph-structured indices for scalable, fast, fresh and filtered approximate nearest neighbor search, 2023. URL https://gitans thu................ com/ hac.//icoooof//////ooo DiskANN.
Berfin Simsek, François Ged, Arthur Jacot, Francesco Spadaro, Clément Hongler, Wulfram Gerstner, and Johanni Brea. Geometry of the loss landscape overparameterized neural networks: Symme- tries and invariances. In International Conference Machine Learning, pp. 9722-9732. PMLR, 2021.
Kiran K. Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for semi-supervised learning, 2018. URL https: /ates://arxiie /tt///axiiv//./////////ee///aavl wttp:/wwww/////////aee 03735.
Tijmen Tieleman and Geoffrey Hinton. Neural networks for machine learning, lecture 6.5 6.5-rmsp 2012. Coursera lecture slides.
Titouan Vayer, Rémi Flamary, Romain Tavenard, Laetitia Chapel, and Nicolas Courty. Sliced gromov-wasserstein. arXiv preprint arXiv:1905 10/24, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
Quan Wang, Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE transactions on knowledge and data engineering. 29(12): 2724-2743. 2017.
Chai Wah Wu. On rearrangement inequalities for multiple sequences. Mathematical Inequalities & Applications, (2):511-534, 2022. ISSN 1331-4343. doi: 10.7153/mia-2022-25-22
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. arXiv preprint, 2019.
Qitian WU, Wentao Zhao, Zenan Li, David Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification, 2023, URL https: /arxiv.iivv orw.org//aoo abs// 2306. 08385.
15

---

Published as a conference paper at ICLR 2026
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Pu Yi, Tianlang Chen, Yifan Yang, and Sara Achour. Exchangeability in neural network and its application to dynamic pruning. arXiv-preprint: 2506.02210, 2025a.
Pu Luke Yi, Yifan Yang, Chae Young Lee, and Sara Achour. Early termination for hyperdimensional computing using inferential statistics. In ASPLOS, 2025b.
Chengxuan Ying. Tianle Cai, Shengjie Luo,, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yat Yan Liu. Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34:28877-28888, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algorithms. In Proceedings of the Twenty-Firas International Conference Machine Learning (ICML), 2004.
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yanfang Ye. Gophormer: Ego-graph transformer for node classification. 2021.
Xixi Zhou, Yang Gao, Xin Jie, Xiaoxu Cai, Jiajun Bu, and Haishuai Wang. Ease-dr: Enhanced sentence embeddings for dense retrieval. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 2374-2378, 2024.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In ICLR, 2021.
Wei Zhuo and Guang Tan. Efficient graph similarity computation with alignment regularization. Advances in Neural Information Processing Systems, 35:30181 2022.
16

---

Published as a conference paper at ICLR 2026
Exchangeability of GNN Representations with Applications to Graph Retrieval (Appendix)
CONTENTS
A Broader Impact
18
Limitations
18
LLM Usage
18
Related work
18
E Proofs and other technical details
20
E.1
Proofs of the results of exchangeability presented in Section
20
E.1.1
Proof of Lemma 2
21
E.1.2
Proof of Lemma 3
23
E.1.3
Proof of Lemma 4
24
E.1.4
Proof of Theorem and Proposition 6
25
E.1.5
Equivariance of the Update Step Additional Results on Exchangeability
27
E.1.6
31
E.2
Proofs of the technical results in Section 4
33
E.2.1
Proof of Proposition
33
E.2.2
Proof of the fact that Eq, (3) and Eq. (4) are equivalent
35
E.2.3
Auxiliary Results used to prove Lemmas in Appendix E.2
36
E.2.4
Proofs LSH results
38
E.2.5
Auxiliary results used to prove results this subsection E.2.4
43
List of GNNs
45
F.1
Graph Neural Network
45
F.2
Graph Transformers.
47
G Additional details about experiments
50
G.I Datasets
50
G.2 Embedding model architecture
50
G.3 Fourier-map and hashcode training
51
G.4 Baselines
51
G.5 Evaluation Metrics
52
G.6 Hardware and Licenses
53
H Additional Experiments
54
H.1
Additional Exchangeability Results
54
H.2
Further Evaluation of GRAPIHAASI'S Retrieval Performance
55
H.2.1
MAP on Equal-Cost GED
55
H.2.2
Evaluation using NDCG
56
H.2.3
Clarification on RH (Subsampled)
57
H.2.4
Evaluation on Larger Graphs
59
H.2.5
Evaluation on larger corpus
59
H.2.6
Ablation Studies
60
H.2.7
Comparison of sim and sim
63
H.2.8
Evaluation of LSH Methods under Aligned Scoring Functions
64
17

---

Published as a conference paper at ICLR 2026
A BROADER IMPACT
Our work is the first of its kind within the space of distributional symmetries in neural architectures, as it moves the focus towards the distribution of embeddings over randomness in initialization. Our work may also be adapted to other classes of neural networks. Probabilistic symmetries may have other consequences to training and learning dynamics, like our concentration bound.
GRAPHHASE also offers an efficient way to retrieve graphs from large database of graphs. It can help in identifying a subset molecules which similar to some other molecule, from large corpus. It can also help in video or image retrieval by specifically focusing on scene graphs. Thus, our work has the potential to reduce computational cost and carbon footprint of large search systems.
B LIMITATIONS
(1) We only restrict ourselves exchangeability as probabilistic symmetry of GNN, which is symmetry induced by permutations in the weight space. In this work, we do not consider how other types of symmetry can affect the probability density function of the embeddings. However, our work can be seen as a stepping stone to characterize such cases. (2) It is well known that the exchangeable sequence (Y1,..., YD) tends become i.i.d, sequence as + oo. However, this does not apply to our setting because the values of the embedding elements also depend on D. It would be interesting to discover asymptotic characterization of embedding values. (3) Exact graph distance involves solving quadratic assignment problem, whereas its surrogate used in Eq. (1) approximates graphs using sets. This gives a first order approximation, which allows us to leverage exchangeability to approximate transportation distance between two embedding sets using Euclidean distance. One can provide more accurate approximation using distance between edge embeddings. We did not provide this formulation in our paper. However, our work be easily extended such setting, by considering joint distribution between node pairs.
C LLM USAGE
We used an LLM primarily for correction of grammar and polishing text. Very occasionally, used it to supplement bibliographic search. No LLM was used to generate ideas, design experiments, analyze data, implement algorithms,, produce results. We carefully reviewed and revised any response provided by L.M..
D RELATED WORK
Representation learning Representation using dense embeddings of structured objects has been much-studied area of research, e.g. for, sets (Lee et al., 2019; Zaheer et al., 2017), sequences (Palangi et al., 2016; Zhou et al., 2024), and graphs (Cai et al., 2018: Wang et al., 2017). Relatively fewer results focus the question of retrieval using these embeddings (Li et al., 2024; Duong, 2022; Gerritse et al., 2020). Prior works on graph retrieval predominantly aggregate node embeddings from each graph into single, pre-computable embedding vector (Li al., 2019; Bai al., 2019; Ranjan et al., 2022). This allows for the use of standard indexing methods for vector similarity search. However, this reduces accuracy due compressing the entire graph into one embedding. Yi al. (2025b) discuss exchangeability in the context of hyperdimensional vectors.
Transportation distance in graphs More recent techniques for graph embedding employ node- based vectors and then define relevance scores of the corpus graphs with respect to the query by using transportation distance between the two sets of vectors (Roy al., 2022; Zhuo et al., 2022; Fey et al., 2020). The cost within the transportation framework models various notions of relevance measure, including asymmetric measures for subgraph matching, graph edit distance with non-uniform costs, etc., which results in enhanced accuracy, as compared to aggregation to single vectors.
Locality sensitive hashing After obtaining the embedding (or set of embeddings), there still remains the question of finding out the most relevant object using this representation. For traditional vector databases, locality sensitive hashing (LSH), Indyk et al. (1998) pioneered a celebrated method for approximate near neighbor search. The benefit of LSH over comparable techniques, e.g., IVF, and graph-base based techniques, c.g., HNSW, is the faster indexing time while giving comparable or slightly worse recall times.
18

---

Published as a conference paper at ICLR 2026
LSH for transportation distance A key contribution of the current work is to propose LSH for transportation distance, in context of GNN. Nearest neighbor methods has been studied extensively in the theory community (Andoni et al., 2009; Chen et al., 2022; 2020; Indyk, 2004; Andoni et al., 2008; Jayaram et al., 2024). They first embed a set similarity into Fuclidean space with some distortion factor, and then this reduction design an L.H.. However, the similarity measure in these existing works is always symmetric, whereas in graph retrieval, it is often asymmetric, such as in subgraph matching Graph Edit Distance (GED) with non-uniform costs.
Sliced Wasserstein distance While transportation distance is computationally expensive, recent studies have explored approximations that are cheaper (Kolouri al., 2019; Deshpande al., 2018; Vayer et al., 2019). The most well-known one, perhaps, is the sliced Wasserstein (SW) distance, which is the average of the Wasserstein distance over multiple 1D random projections. Deshpande al. (2018) show the efficacy of the SW distance for GAN training. Kolouri et al. (2019) demonstrate the connection of SW distance to the Radon transform, and Vayer et al. (2019) propose sliced Gromov Wasserstein, similar approximation for the Gromov- caatoov--sssrttein distance, also used for optimal transport. However, none of them study the question of efficient retrieval under such distances, or the connection with dimension exchangeability of representations produced by common neural networks.
Transportation distance has also been studied in the average case: Jayaram et al. (2024) give a Olog n) approximate data-dependent LSH in the distributional case. In our setting. this problem is tackled by showing the exchangeability of embedding dimensions of GNNS. Our result is incom- parable (Jayaram al., 2024), since their posited distribution is not exchangeable, and our set of exchangeable distributions is broader than what (Jayaram et al., 2024) assumed. The notion of exchangeability has been studied before for neural networks, but in different contexts and toward different goals. Set transformers famously utilized permutation invariance to give set embeddings, exchangeable networks for set-to-set matching were described by Saito et (2020), while Bloem- Reddy et al. (2020) characterized invariant network architectures for particular symmetry property, including exchangeability, of the input. However, none of these results have characterized the ex- changeability property of the embedding dimensions, is done in our work. In Introduction, we have already mentioned works that recognized various symmetries of loss surfaces with respect to hidden units of some standard networks. In those works, such symmetry is usually impediment fast optimization, remedied by advanced optimization techniques. In contrast, we use such symmetries to establish exchangeability, in the service of efficient LSH indexes.
19

---

dimensions O which has the corresponding gradients. As set by earlier convention, grad 21 ( Published as a conference paper at ICLR 2026
E PROOFS AND OTHER TECHNICAL DETAILS
In this section, we present the proofs of the technical results presented in Section 3 and Section 4.
E. PROOFS OF THE RESULTS OF EXCHANGEABILITY PRESENTED IN SECTION
Here, prove Lemma 2, Lemma 3, Lemma 4, Theorem 5 and Proposition 6. To achieve this goal, we first restate the setting:
(1) Broad class of GNN architectures We consider the wide variety of GNN architectures, which are enlisted in Appendix F. This list encompasses a wide range of GNN architectures, including gated GNN (Gilmer al., 2017), GIN (Xu et al., 2019), GAT (Veličković et al., 2018), GCN (Kipf et al., 2017). Note that, our analysis is likely to extend beyond these cases, and can also be applied in Graph transformers, as shown in Appendix
(2) IID intialization of the parameters within a layer The entries of the parameter matrix ( in each layer of are initialized in an i.i.d manner. Parameters across different layers are initialized independently, but not necessarily identically. This covers standard model initialization schemes, such as Kaiming initialization (He et al., 2015) and Xavier initialization (Glorot et al., 2010), both of which yield i.i.d. initialization of the parameters within a layer.
(3) Permutation invariance of loss function We consider the loss function is invariant to the permutations of elements in the node embeddings. This holds naturally in several settings including our graph retrieval. Here, the loss, whether binary cross-entropy or pairwise ranking, depends on the similarity between (G,, Go) via the transportation plan between X (9) and X(e) (Roy et al., 2022: Zhuo et al., 2022). Since this similarity is invariant under permutations of embedding elements, the loss is likewise permutation invaariant. In link prediction, the similarity between two nodes and is often computed as the dot product x æ(u) (v)), which is invariant to permutations of the elements of a.. Consequently, the associated loss is also permutation-invarian.
(4) Broad class of optimizers The optimizer for training can be SGD (Zhang, 2004), Adam (Kingma et al., 2015), etc. This pertains to standard optimizers, which are routinely em- ployed across learning settings.
Additional Notation
We further introduce supplementary notation.
(1) We use ((0)) denote the parameter matrix of the b-th layer the th update step. We shall index our weights using the set [emax] = {0, 1, Lmax] }, which shall implicitly cover each of the components (embedding initialization, message passing and update step). We will typically use to denote the layer index.
(2) o <t denotes the collection of parameters O jeor for iter
(E)
(3) Aer denotes the collection of all parameters fuer for iter 0, 1
(4) (( is a transformation on the parameters of the 4-th layer. F- is a global transformation on all parameters. We take pn to be separable across layers (this holds for the permutation-
transformations considered by us). That is, Tr may be written Tx +ce(tmax) T This means
that Tx (0) = (T (0(9) & E (fmax))
(5) Ie refers to the domain of the parameters, which is R2 where p is the number of parameters in the network.
(6) We refer to the loss function at the hh update step as loss,, which a function of the parameters of the network, i.e., loss,(0) (0): thus the index encodes the batching/data used for that update step. When it is clear from context, we may write loss, (0.) simply as loss
(7) 8A.(k.t) is defined as the matrix of appropriate dimensions with all zeros except for a A at the (k, 1)-th position. Note that this is different from Dirac delta function 5( we will alert the reader we use as Dirac delta function.
(8) We denote the gradient of the loss function with respect to the parameters O, the collection (grad( I E [Emax]). where l is the layer index. Here, grad,") is a matrix of the same grad, A
(e) for iter = 0, 1 1, and grad denotes the denotes the collection of gradients grad iter collection of all gradients grad for iter 0, 1,...., 1.
20

---

Published as a conference paper at ICLR 2026
E.1.1 PROOF OF LEMMA 2
Lemma Given a graph G and a GNN architecture GNN, enlisted in Appendix F, let the node embedding matrix of G be X GNN&(G) E RTXD. Then, for any permutation matrix E PD. there exists a bijective transformation 1'x with |Det (ōi (0) = 1 such that X (oNr, We call x permutation induced transformation, for π.
Overview: In this section, we focus two architectures, which covers the intricacy involved in designing the permutation inducing transformation. For other GNN architectures, we provide the reader with building blocks for transformations involving other common GNN layers in Appendix F.
Proof:
In this proof, we consider the GNN in the form of gated GNN used by Li et al. (2016); Gilmer et al. (2017).
Architecture, Given integers K and D, a graph neural network (GNNg) computes node embeddings a& (w) E RD for u E V using K message passing steps. Here, we initialize mo(u) using node features feat(u) and keep updating æy using two neural networks upd and msgg having parameters 0.
xo (o(u) inito (feat(u))
(10)
#++1 (u) upd (zx Eeturnee msga (mx( xg ())))
for k < K.
(11)
In the above: initø, msgg are multilayer perceptron (MLP) networks of the form of Linear (fmas)
a (fmax-11) .... (1) Li)ear( where Linear(() is linear layer and (()) is activation function
that applies pointwise. upd8 can be (a) an MLP network or, (b) one layer of GRU (Gilmer et al.,
2017). In the current analysis, we omit step index t, since we are focusing on only one step.
Gated GNN with MLP based updg: Proof Sketch. In particular, we assume that each of
xy(u)
xx(u)
[ag(()) x001
feat(
xo(1))
xx())
O(1) - @
- ( (
(1)
(eat(s))
ko(w)
x(()
(x,(t)) x[O]]
x2-)
π
x 0x'
π
msga
xx(l))x πT xx(i) (x(()) x((v)
x241 (1))
feativ
featti))
10)
x (v)
(V) π--
x
@
e - 0
(v)) (x+)
(eattw)
inita
x (w) (x((V) π (x))r
upd
initg, msgg, upd8 is simple MLP with 1, 2. and 2 layers, respectively. The figure shows initialization
and recursive propagation from layer to k 1.11 1. To induce the transformation Ø (u) +> x x (u)TT, I, we modify the final layer of upd, as ((4) + (4)) æ, which also changes all intermediate outputs of updg: æ ==( + 2z (u) This change affects msg, inputs. We undo the "side-effect" by transforming (1)) to Diag(T
10(1), Finally, we update (0) + (()), π ensure that the initial input msgg, namely pp (2) ा. aligns with the transformed flow. Since the rest of the network remains unchanged, this transformation is agnostic to the depths of init, msg, and upd, affecting only the last layers of init and upd and the first layer of insg.
Detailed Proof. Firstly, we re-index the network weights for readability, as - (I) init: Let the last weight of init be ((6)) (II) msg: Given (u, v) E, and the propagation layer let x (0) o (u), x (v) be the input to the message propagation layer after the node embeddings are concatenated according to the edges in the graph. The weight matrix in the first propagation layer
of msg is (41), Let x (f1) be the output of ((1), i.e., x = x (0) (()) (III) upd: Let the final
layer of upd be θ (+2), The transformation is defined as follows:
2 (e (ft))
θ (fo)
(12)
(e(()) = π 0
((1)
(13)
0 π
r
(e)
O (f2) π
(14)
21

---

Published as a conference paper at ICLR 2026
While the remaining transformations identity, i.e., 1 I d for all & {lo, E1, (2). We shall show that the output of the network is permuted in columns by æ, by tracing the effect of the trans- formation from the imput the output. We show this inductively on the number propagation steps.
Base case. For k = O. As (6) + θ ((o n,, we have: Xo + XOT.
Inductive Step. Suppose that Xx X&T for some k. Then X (0)
[x]( 2 (b)]
X
(0)
0
under 0 - (0).
0
π
Since transform (5)
(G) and X (0)
X
(0)
π 0 the quantity X (f1)
x
0
π
X
(0)
0 π
0
+ (41)
X (0) θ (f1) remains unchanged π I.
π
(Fx) remains invariant to 1 Until the final layer of updates, all transformations rx()) are identity and therefore, the resultant intermediate embeddings also remain invariant. At the final layer, we have ((a) ((2)) (from Eq. (14)). This will give: X + X4+1
Due to this, X k
Gated GNN with GRU based updg: (I) Let ((()), ( x (-((1) bear the same meaning as before.
(II) updg: We introduce the hidden state encoding of the GRU:
(reset) (update) (hidden)) The corresponding weights are indexed by limp, or Enid, Here, X X X
the update steps considered in the GRU at the 1tth round of propagation are:
X (reset)
Xx (fip.1) + X (61) (fmd.1))
X
(15)
X (update) k
(finn.2) (1mo)))))))
(61) (Pmid.2)
(16)
X (hidden)
= tanh
X (4mp.a)
+ (X (f1)
C x (updase)
e (Eaid,3)
(17)
X (1 X (reset))
1 Xx + X
(reset)
@ X (hidden)
(18)
&
We define our transformation as
r (e)to)) = ((((t))==+++
(fa)
π
π (4))
0 T
(19)
n
I (lip ( ( (Fup..)) = (Fun..)))
1
(fmd.
( fiid.e)
(
(fnia. π
(20)
While the remaining transformations are identity.
Like the previous proof, we trace the computations in the network inductively over the propagation rounds.
Base case. For k = 0, this is true just like the previous case. X + Xox as e (fo) + θ (80) π.
Inductive Step. Suppose X + X& for a value of k. Then X (0)
a (u), 2 (v)
X (0)
0
under 0 + Tx (0). Since, we transform (
π
(E)) and X (0)
0
π
X (0)
0
the quantity x((6) (0)
π
π
(ti)
x (0) (fi) remains un-
0 π
0
0
changed as πम
T T
Due the transformations in Eq. (20). have: (1) ((iuni) X T (4mp..) n
X O (fmp.e) for each i 1,2, 3; and, (2) (((uaa)) (10 a for each 1,2.
22

---

Published as a conference paper at ICLR 2026
Consequently X (reset)
X (update)
X (hidden)
X (ressat) n,, X (update)
n, X (hidden)
n, resulting in
Xx+1 + X 1I+I T as follows:
x (resett)
O (mp..)
π + ((1) (Enid.)
(21)
(4ng.1
X (6) (
π = X (reseet)
π
(22)
X (updato)
+ X (2mp.2
π + X (11) (Riid.2) π
(23)
=0 [ (4mpp)))
+ X (6) ) (
π = X (update)
π
(24)
X (hidden)
b tanh X (4ip..))
π (81)
X (update)
π (f1ia.2)
(25)
= tanh
X O (1pp.3) +(X (f1) X (update)
(aidd,))
X (hidden),
π
(26)
Therefore we will have:
X (1 X (reset)
T) 3 X + X (reset)
π X (hiddon))
(27)
(1 X (resct)
① Xx X (reset)
x (hidden)
Xx+1
(28)
E.1.2 PROOF OF LEMMA 3
Lemma 3. Given the setting described in Section 3.1. Let T be the transformation on the GNN parameters 0, induced by a permutation π E TRD, introduced in Lemma 2. Then the gradient of the loss is equivariant under transformation T of the parameters.
Proof: Outline. We assume that the loss is differentiable with respect to each parameter. We shall work with a finite difference of as a proxy for the gradient. We show that that equivariance holds for this setup. Thus, the equivariance holds in the limiting case A + 0, hence in the case of gradients.
We shall make the following observation in order to prove the lemma: For every layer, the transfor- mation consists of permutation of its entries. This also makes T linear.
Additional Notation to Facilitate the Proof. Corresponding to each layer l and each scalar parameter e J, k), we shall consider a perturbation of the parameter by A E R {0}. Within this proof, A a perturbation and not relevance distance. Finally, &a.(k.0) is defined as the matrix of appropriate dimensions with all zeros except for at the (k,,))th position.
( (t') ( =1) ['[(faa)] This indicates the perturbation only
We write 0g te dA.U,.)
at (j, k)-th entry of ()()) at El = f. We define the matrix of discrete differences as CiA as
(()
r.a [i
(2)
[loss, (0g +e )A.()A)) - loss;
(29)
A
First, we show that when 02 + Ix()),, the transformation C, + I (Cx) will hold true. To show this, we derive that for general E [[maax] (0 r(() (c(2)) Let characterize the permutation on the entries of the parameter corresponding to _ by introducing a permutation map [m] [m] -
[m]] x [n)]. For any ()()) there exists â defined as above, such that:
A)] ( [j, k).
Here, के depends on However, we omit this for the sake of readability.
Proof. Note the following identities that hold as consequence:
For all j, k. we have:
r (0))) - k)]
(30)
Consider the (a, 6)th entry of the following matrix: (((() (..0),),a 6] = 85.0.1/ (a, 6)], which
is A if b= 7(j k) and O, otherwise. Then, by definition of 83.(0.0)- we have:
T(0 8 8A,()(AA))
(31)
23

---

Published as a conference paper at ICLR 2026
The transformation T is linear, which implies that Tx +e )A.(0)) (0) 1+ (6s,
Consider the (a, b)-th entry of 2 = C.A (o-T(((
which is the loss:
(9)
(a, 6]
[osss (Tx) +- (a.()) - loss, (Ix (0:))
(32)
A
1
losss (T>(())) +z ! o 1
"م,(a,))) (100'((((.))))
Loss (I=r(
(33)
A
1
[osss (Ii (0, +e r (o,,(a)))))) (oss:((+
(34)
A
1
[ooss (0, + (1)
(dم, loss, (0.)
(as the loss is invariant of Tx)
(35)
A
|loss; (0. +e 63 ((a,b))) - loss; (0:)
from Eq. (31)
(36)
A
2 [ ((a b)] = - ( 2. la, b] bj from Eq. (30)
(37)
Thus, 200 = (1) (c).)) Now, lim A +0 c grad Hence, we have:
lim 2.1 lim ( (c()))
(38)
A00 A-0
= =I
lim c(2))
(T() is smooth map)
(39)
A
- (grad))
(40)
Therefore ( + 10 (01), we have grad +
((0) (grad)). Hence, grad, = [grad
[T+] (grad])]= = Pr Tx (grad = T (grad,).
E.1. PROOF OF LEMMA 4
Lemma 4. Given the setting described in Section 3.1. Let {0: 2 0} be the trajectory of the parameter 0 of a GNN across different training epochs 2 0. Then, we have: p(0.) = ((.)) for all t 2 0.
For iter 0, we have p(0,) (fo)) by the ii.d. initialization of parameters. For iter > O, we use two key conditions: (1) The loss function is invariant under In (which holds, as our loss permutation invariant in the GNN output). (2) The gradient and update steps are equivariant
Proof:
under T.. We first note that:
p(0)) S T
xX...X
II p(Otter ( d8 iter=1
(41)
First, to build up intuition, consider a simpler setup which, instead of using an advanced optimizer like Adam/SGD, uses simple full batch gradient descent. Assuming the learning rate is 1, we will have:
(E)
grad (-
(42)
iter
iter-1
iter-1
Hence, p(Ottor (citer) given by:
p(O (ftter (citer)) = 5(Biter Oiter-1 + grad
(43)
Since (2) a linear homeomorphism, we have
r
(C)
r (010 ((r-1) (()) (ggaad 00 1o
(44)
iter
(O!0 -grad
(Lemma 3)
(45)
Given (0) + T (
(!)))
Fx (ftte)) = I (0 grad
(46)
9=1, g=r,(Oma-1)) (0rar-1)
This allows us to write:
pT (f
I (flcterr) = (Biter)
Ix ((teer-)) + (grad
(47)
24

---

Published as a conference paper at ICLR 2026
Now, since Eq. (42) and Eq. (46) equivalent, we have pl (Oter (iito)) = pp (0 T (f<cier))
(48)
The above relationship suggests Eq. (41) is equivalent to p(O.) x.... x J itr=1
J3x...x
II (Oiter) Tx (0 (Q<iter)) d0icer
(49)
= oL+ ittr=
00
II p(I (Oneer) ITx (0 ((( (((TT(((0 Det
(50)
OI (0iter)
(O,)
(51)
because F consists only of permutation matrices. Here, proved that Eq. (42) and Eq. (46) are equivalent for full batch gradient descent. This relationship also holds for other standard optimizers (such as listed in E.1.5), which is shown below. We may abstract the update step as follows-
Det 86 (Pase)
(E) iter
Updater,iter (!!!
(0) < iter) (grad,
iter)
(52)
This gives: ptrr 0 <iter) = II
1@0
( iter
Updateg,iter (@) | b< iter) (grad!
< iter)
)))
(53)
According to Lemma 10, Eq. (52) is equivalent to:
r(e) (
Updates,tter
(( (0) ((T=((0))))
iter). ( (grad! <
iter)
(54)
iter
as long as x is a permutation matrix (which is the case according to Lemma 2). This implies that p(Otee (iter) (53) is the same
p(Tx (Qter) Ix (fciter)
III
[ (8) )
Updator,ite (TT!) iter). (I+ (grad,!)) iter) )terr)
(55)
E.1.4 PROOF OF THEOREM AND PROPOSITION
We state both the results.
Theorem 5. Given the setting described in Section 3.1. Then, X = GNN) exchangeable random variables, where the randomness is induced by the model initialization prior to training. That is, x(X)= p(X T.).
Proposition 6. Given two graphs Gy. Go let the settings in Section 3.1 hold true. Specifically, let us assume that the loss function be invariant to simultaneous permutations of the embeddings (()) GNN,(Gg) and (c) GNNo(G.). Then, Y == (x X(e) E R satisfies p(Y) pl Y TT).
We shall prove both of these in one go, as the latter implies the former.
(x)
(x)
Proof:
Let Y denote the concatenation of the query and corpus embeddings, i.c., Y
X
where ()) E D. We need to show that:
p pY
(56)
25

---

have Published as a conference paper at ICLR 2026
This is precisely the condition for exchangeability as stated in Definition 1. We first observe that:
p(X)= =
p P p(0)) d0,
(marginalization)
(57)
PY π 7 ((.))) (using PY (1)) = p (T
(58)
1 p ( T (O.))) (using ((0.) - ((TT((0)))
(59)
00,
p(T [L))
(0,)
(Random variable transform 8 ++ T₂)))
(60)
-f p( (T
pYY) (marginalization)
(61)
Justifications of Eqs (57), (61) are trivial. We now provide justifications for the claims in Eq. (58) and Eq. (59) are as follows.
Justification for p(Y (0, = p(Y क (0.)) used Eq. (58): the network output is determin-
istic, p(||0,) can be written in terms of the network output GNN, and the Dirac delta function as follows:
GNN,, (G.)
P(Y 0.) = 8
(62)
GNN,, (G.)
0c if = 0
Here (()) is the Diract delta functional. 5())
otherwise and Jo o(Z)dZ =.
GNN,, (Gg)
GNNT, (0.) (G.)) GNNI, (G.)
Since the following relation holds: Y
iff Y
GNNo, (G.)
P 02) y (0:)). Justification for p(O.) = p(T T (0+) in Eq. (59) occurs due to Lemma 4.
Here, we note that our result holds even in the presence of additional sources of randomness in the training process, such as data shuffling or batching. Since these sources are independent of parameter initialization, the proof extends by conditioning on the training randomness and then marginalizing, yielding the same conclusion.
26

---

Published as a conference paper at ICLR 2026
E.1.5 EQUIVARIANCE OF THE UPDATE STEP
We shall present general lemma that states the precise update step equivariance property. Later, we will prove it for optimizers such as Adam, SGD, AdaGrad, RMSProp, followed by a more general general formulation.
Lemma 10 (Equivariance of update step). The update steps of the aptinizerfollow form and equivariance property. Specifically Eq. (63) holds true isf Eq. (64) holds true.
follow the functional
- Updater.
((0
(t) iter
iter <t): (grrad (1)
iter <1)
(63)
(4) T θ 22 Updateg.
+ [
T2
(2)
T2
T2 iter < <t) (rig iter iter <1)
(64)
Note that this means that the update step is equivariant with respect to transformation that permutes the rows and columns of each parameter matrix. The transformation क permutes the rows of the parameter matrix, while 2 permutes the columns.
Proof for Adam (Kingma et al., 2015) We first describe the Adam update steps - For layer l at time t. refer to the momentum of the gradients mf, and the squared gradients vf- The corresponding birs-corrected terms which used by Adam are denoted by mi and of respectively.
The hyperparameters for Adam are defined as follows: 31 and B2 are scalar coefficients that control the exponential moving averages of the gradient and its square. a denotes the learning rate. is a small positive constant added for numerical stability. À is the weight decay parameter.
The Adam optimizer (Kingma et al., 2014) updates each parameter as follows:
!
8 = ( a
m
(65)
V
+E
91 grad
(8)
(8)
+ x0
(8)
(66)
1-1
m m. 1- n
(67)
m = 3 fmmm1
+ (1 (1- 31)9 (0)
(68)
8/ 1- BJ
(69)
of = 320 + -2)((g) .g
(70)
Where m = v/ = 0.
Eq (63) can represented by simply inductively writing out the update steps in terms of the previous steps using (f) <t and grad ( et. Similarly for Eq. (64), we can show that each vfeer and m are
-! permutation equivariant with respect to the gradients, and consequently even mit and of We shall work this out here-
Consider the transformation
(P) <t + π. T2.
grad + ग. grad (1)
(assumption, shown in Lemma 3)
(71)
We show equivariance for of and m by induction-
9i + π (gi (8) )
(72)
of = (1 (1-5)) (8)
g0
1 + (1 (2) gb
(8)
n2 2 ग. 9b T
(6)
(73)
π (1 32)
(0)
90
(8)
m
(74)
of B20 + - (1-33))g)
① g:
+ 32 T oi_ हे + T (g) (8)
g
(P)
m
(75)
π 0.712
(76)
27

---

Published as a conference paper at ICLR 2026
mg = (1- B:)(gb ) + (1 B:)(TT go T2)
(77)
= T 32)(90 (1)
T )
π m
(78)
m = 8im + (1- - ()) + 3 m + ক (1 (3)) (0) )T2
(79)
π miT²
(80)
i T 0\
6f
T 8/
(81)
1
32
m
T1 m
m;
m. T2
(82)
3
1
3
Finally, from (65), ( is permutation equivariant with respect to (0) and the gradients.
1-1
Cx
m
1
1-1
(E)
TT2
T
m.
T2
(83)
e
V |
0 T +
0
1-1
(8)
a
m,
T82
-T: O π
(84)
+e
Proof for SGD SGD has hyperparameters for learning rate a, and weight decay A. For layer at time t, the update step of SGD with weight decay is given by:
@ o ag. (0)
(85)
(2) grad (2) g:
!0
(86)
Where the weight decay term and a is the learning rate.
Here, the gradient is computed over point/mini -atch of points sampled at time t. We can fix the randomness of the sampling by conditioning on the "trajectory" sampled points(or mini- hami-bathee)..
Thus, we can treat grad! (") as a deterministic function of (
<t.
Furthermore, this gradient also follows the gradient equivariance property from Lemma 3.
Consider the transformation (0, + πH (2(2) T2 and grad! (f) + क. ( TZ. Then:
g. π (grad) TT2 + ATT (t) (2)
(E)
TT g: (8)
r-1 7
π3
(87)
O ( + π 0 n22 aTT i g.
(f)
n
(88)
= - [ ogg TT2
π
(89)
Thus, the SGD update is equivariant with respect the transformation. By conditioning the trajectory, we actually show a stronger result for equivariance. We may show the equivariance without conditioning on the trajectory, by considering the expectation of the above result over the randomness of the sampling.
Proof for AdaGrad (Duchi et al., 2011) AdaGrad has hyperparameters for (time dependent) learning rate a₁, weight decay X, and a small constant for stability, For layer & at time t, we refer to the accumulated squared gradients as G( (which is defined below). The update steps for AdaGrad
28

---

Published as a conference paper at ICLR 2026
given by:
Qt
① 9i (2)
(90)
V VG +
9: grad (6) =00
(-1
(4)
(91)
G G + (gi gt (0)
(2)
(92)
Where Go = O.
Consider the transformation O
(
(0 <t T2 and grad (6) + x/ (grad <e T2. We show that
TT)
G. is equivariant by induction:
9 म. [gg
(g: 222
(8)
(93)
G 0 π
OTT 0 = .. G n2
(94)
G G --1 + (g) @ 9: (8)
(
(95)
H म T 1- n2 + [
(4)
T2 ① π 9: T2)
(96)
n G2 (0)
2 π g
gt T
(97)
x [ 9t 9t
(
n2 π
G T
(98)
Finally, for the weight update:
θ (
a2
① g:
(4)
(99)
Va
(
+
(P)
04
①
T
9:
π2
(100)
T
G
T2
+
T
(8)
2
T
gt
(f)
π
(101)
(1)
+
gi
(8)
T22
0
(102)
G 1
+
Thus, the AdaGrad update is equivariant with respect to the transformation.
Proof for RMSProp (Tieleman et al., 2012) RMSProp has hyperparameters for learning rate weight decay X, momentum 3, and small constant e for stability, and an additional mode the square averages are centered. For layer at time f, we refer to the moving average of squared gradients as of. the "average" gradient as gr ave(E) (which required if the square averages are centered), and the buffer 6/", which are all defined below. The update steps for RMSProp are given by:
(
(e) ab
(103)
6 1
(0)
(104)
o +e
9 ( grad
(
+ XO (8)
(105)
i-1
of Buf
+ (1 (g (9) ② ( (if not centered)
(106)
1 Buf é
+ (1 () o gt (8) g.
avo(e)
gr
ave(E)
(if centered)
(107)
(t)(
fg.1 me(()
+ (1 9) (t) (if centered)
9:
(108)
ave(f) = 0, of 0, 0 = 0. Note that in the absense of momentum (p = 0), the buffer b. Where 90
is not required, and the update step will simplify to e (
(2)
29

---

Published as a conference paper at ICLR 2026
Consider the transformation O (0) + T (0 xe and grad (6) + T "grgadd 2e/T2. We show that the other variables are equivariant by induction:
( 9r + J (gi 2
T (2)
(109)
" 0 π 0T = 0 प 16/T
(110)
1 of = B + (1- - (g. (2) O 9.
(111)
+ Bπ T 0/ + (1 - (T) 9: 12 0 t 9: T2)
(2)
(112)
o/ + (1 - 3) (9) 3 gt T
(113)
I [BoBf 1 + - (g) (8) (6)
9i To
(114)
(e = 0 + π 2T = 0 = क 9u
ave(()
90
22
(115)
91 (N)(E) = 39:-1 + (1- - 3)g (8)
ave(E)
(116)
| T -t-1 T2 + (1 | 1 9: π22
ave(t)
T (2)
(117)
. (3g (t)
+ (1 - 8)gt TT2 1 T ave(E)
gt
(118)
2 = B + (1- ()) (8) @ 9: (0) 9t
(ve(E)
ave(E)
gt
(if centered)
(119)
+ BT _ 0/ + (1 ( 9:
(1)
122
1 9:
(8)
T2))
- 1 gt
(ve
n2
O T gt
ave(E)
T
(120)
| 0 T2 + (1-8) (g) gi
n22
I (g)
(v)(e)
@ gt
ave(e)
722
(121)
. (Bof + (1 - () (8) (0)
9:
a)o(()
3 gr
ave(e)
TTT .. 1 π22
(122)
6 = 0 + ग 0T = 0 = म. by n2
(123)
6, = pa (0)
+ gi
(124)
1 +e
+ p T b
1 222 +
1 9: T22
(125)
VT oj T2 +e
9t (1)
= μ 6-117 T22 + π
π22
(126)
Ve + c
gi (2)
ub
(1)
+
T22 = 1
(1)
π
(127)
V +
Finally, for the weight update:
9 8
0
(1)
1-1 a
(128)
1 +e
(8)
π.
T (1)
T 9:
(129)
U
π2
+ c
gt
= 222
1-1
π
n22
(130)
+
gt (0)
=
(
a
T22
=
0 π
(131)
+
Thus, the RMSProp update is equivariant with respect to the transformation.
Proof for a general case We can show that a general optimizer leads to equivariance under the transformation if the update step can be separated for each scalar entry of the parameters.
30

---

Published as a conference paper at ICLR 2026
Lemma 11 (Update Equivariance of separable optimizer). Let the parameters be updated by the function f. such that for any step t,
0c+1 f( : iter & t), {Srerr iter S t), Ttt Ze)
(132)
where, Iver based on the optimizer may be the gradient (which may also be clipped and/or normalized gradient) w.E.t the parameters Ueer which is equivariant under TT
Let be the set of hyperparameterss of the optinizer (this may include learning rate, momentum, etc.) at update step i, and Ze be a latent random variable representing any stochasticity in the update step (such as data selection for HiDDmini-batchy
We call f to be separable over each scalar, if we can write for any parameter θ ( for all of its entries entries j.
++1 bi = (( iter b..j: iter S (), [. iter S (1, Thi
(t)
11, Ze)
(133)
where f() is an appropriate function which may be different for each layer & E
Then, the update step is equivariant (conditioned on (Ze : S t)) any transformation 7x applied jointly to each of (Otter, Piter } for iter S I.
Note that this functional form is quite general despite the separability condition, as it subsumes commonly used optimizers GD,SGD, Momentum, RMSProp, Adam, AdamW, Adagrad, etc. The conditioning on the latent random variables implies that the equivariance also holds in expectation over the randomness.
Proof:
The proof follows from the fact that the transformation F is composed of permutations in each of the weights. Consider a layer é with parameters ((0), of size di d2. We may find a permutation
#: [di] x [d2] + [di] x [d2] such that for any entry (i. of matrix A, r (i) = A [)],
To reiterate, under the transformation Tx VtV(i, [d,] x [d2). [ θ 2 (+(1,))))) and
( + ( [ (i]
Then, for any step t, under the action of F on {ftter: Piter for iter S t,
iter & 1), (ol [..j] iter & 1, Mr, 7e) iter [ (10 (0)
((0) (i. iter S {t), t [+( iter S tt,, nr. Zt)
Htrl
(134)
22 (i. = r (i.
(135)
Thus e [ (1) Finally, since this holds for all layers L, we have 0.+1 + Ix (0(+1).
1 ( (i..). Since this holds for all entries (i,j), we have e 0 H
1. ADDITIONAL RESULTS ON EXCHANGEARILITY
Loss functions without permutation equivariance In this paper, we take the loss to be direct function of the embeddings, which necessitates that the loss function be permutation invariant.
When we consider settings where the loss is not permutation invariant, for example classification task, the 'representations' exist within the middle of the network rather than at the end. Moreover, such representations can be shown to be exchangeable.
For this analysis, we may partition the network into two, which could be referred to as the 'embedding' network and the 'classifier head', may write X = NN(G) where refer to X as the embeddings and ý = (X) where ý is the prediction label vector across nodes. We can characterize and prove the exchangeability of X for this setting.
Let the parameters of the entire network at timesteps be represented by 0 (0NN. fCır), corespond- ing to the parameters of either network. Let us also define the permutation inducing transformation as F = INN, & I T. i.e. (0) = (UNN,==ONN)) cir, (Ocns)).
Given the dataset, may reparameterise the loss function L(X, CIf), or equivalently, L(X, 0cr)).
31

---

Published as a conference paper at ICLR 2026
The new condition for the transformation boils down
+ X under I'
. the loss is invariant under (ST, a. i..
C(X, 0c1)) C(Xi, L'n,
(136)
Under these conditions, exchangeability follows with the same steps exchangeability at initialisation, equivariance of gradient, equivariance of update step.
To illustrate this, consider three class classification task with a single layer for both NN and Clf. Let the input feature be feat. Let us focus on one channel/node of X denoted x X|: o] and y|-] = y. We have: x Nf((ae)) = (feattONN) Hence, we will have: Softmax (I(x w1), (x W2), (x W3)]).
The transformation I can then represented as, NN H ①NNT and [W1, W2, Wal H [T T W1, π W2, π wa]. Under this transformation x + xX but 9 remains invariant-theree the loss is invariant.
Effect of normalization Batch norm, layer norm, etc. do not break exchangeability condition. If the network without the norm layers can be shown give exchangeable embeddings, the same will hold for the embeddings for the network with batch norm or layer norm.
We denote normalization layer NL,, where y and B3 parameters. Such layers allow to extend permutation inducing transformation "n to 7 For simplicity, assume that the normalization layer N L is applied one layer ε. Suppose, (0))) gives Z Zr in that layer (where Z R=xdsm=).. Then will also give Z + Zi..
7
obtain transformation 7/4 such that J (7, Y (0 (),
Let the batch of inputs be GI, G2, .................. .G and single batch norm layer, with the cor- responding inputs Y1, Y,, YB to the layer. Then, we have: Zi, Z2. ZB BatchNorm((1, Y2,..., Y,),,3). Suppose: Y YY,. YY)) where Y the batch VarlYY.. (2.,...Y......))++
mean. Then, we have: Z1, Z2, ZB = V @ y + 3. Now, suppose - +m( gives + Yo. This would give Y Ya. Suppose, we now transform - 7T and 3 + BT. Then, Zi, Zz, ZB + Ya @ (YT) BT Y y B) ZIT, Z ZBT.
Consider layer norm. Assume the corresponding input is y and output in one channel is y-y1 where y the feature mean. Then, we have: LayerNormly;;,,90 B) Suppose: y VVrrly)+
2 y ④ now transform y 7T and B - Br. Then, + ÿ ④ (yT)) + Bi 2π.
B. Now, suppose 0 + Yr (0) gives y + YT. This would give ý ÿT. Suppose, we
Hence, > (0 U (), (7 (0), 7T. BT.. Therefore, Lemma 2 holds true even when we apply Batch norm or Layer norm on each layer/feature. Since Lemma is used to prove Lemma 3, 4 and these lemmas are used to prove the final result in Theorem 5, our results of exchangeability remain the same, regardless of normalization layer.
32

---

Published as a conference paper at ICLR 2026
E.2 PROOFS OF THE TECHNICAL RESULTS IN SECTION
Here, we first prove Proposition and then derive the equivalence of Eqs. (3) and (4).
E.2. PROOF OF PROPOSITION? 7
Proposition 7. For any > 0, > O, setting D >> 2/B ensures that, for some 8o = Op(1), we have:
Pr 1 Siim(Ge Gg) simalG.; Ga) se) 5$) Boo
(137)
Proof:
For the purposes of the proof, we introduce a new similarity measure sim Ges Gg),
Sim Gg) = max
Σ
[[s(x(() (w)[d - x (x)))
(l) u'].
(138)
PEP
a. E/En)//]
We use the above to prove two results:
Pr (
Sim Ggy) (G. Gg) S 2 - -8
(139)
Pr (Isima(Ges G₂) sim (Gm Gg) S E) 2 - 38
(140)
where B = OD().. Finally, we will use the union bound to get the desired result. In addition to
sim Ge: Gq), we also introduce additional notation to facilitate the proofs:
(1) Z is a matrix indexed by the pair of nodes, and the embedding dimension. particular,
Z ((u, u'), d] s(xx()) [u)[d] - fx (x)))()
(141)
(2) We define the vector Za by fixing the value dimension d.
((u, u²), d](a,,'),d
(142)
Za
Z [u, u²), dl((n.)))
(143)
(3) Z is the expectation value of Za with respect the initialization of the embedding model. As it follows from the exchangeability of the dimensions in Theorem 15, we have: E|Zi] = [2[ E[..
Z = Z[Za]
(144)
(4) Our estimator denoted by the vector 2.
D Σ
2 A
Za
(145)
D i=1
Thus, similarity can be written as
1
sim (Ge, (i,, Ggy = max PEP
Σ
[1,, u')) Plu, n'1
(146)
D
[[m]
Suppose R is any matrix in Rax", Then, we define the following quantities:
A(R,
Σ
R((u, u')
(147)
U.a' [
(" arg max A(R, P)
(148)
PEP.
(R) max PEP,
A P) A(R, PZ))))
(149)
Thus we have: GG Gτ) (² and sima GG) AZa)).. Therefore, we first establish that if D 28. then
Pr Pr ( - (Z 2 < 36.
(150)
We begin by showing that A is -i-isschit Convexity of A* follows from the convexity of A(, P) and Danskin's 's Theorem (Theorem 13). By Danskin's 's theorem, the semi-derivative A" with respect to R in the direction of v is given by
0,A ( P.P-P((R)
A(R, P) (v)
(151)
33

---

Published as a conference paper at ICLR 2026
From Eq. (147), we have: (R) |vec P) 1)122 vn. This gives us:
(R) A (R)) - vn R: Rell2
(152)
Note that this is the vector norom not the matrix n-ro.. This proves that A is Lipschitz, from which it follows that for any 6. [A*(R)) - (R2)) 2 = vn R R2ll2 2 c. This gives us: We now use this fact in proving Eq. (139).
Pr - AZ))
2
S Pr 1 Z
(Eq. (152))
(153)
vni
E
[(, Var( (u,, u')l)
(Chebyshev's Inequality)
(vA)
Σ u,u'E|n]x[n]
Var
Σ dE(D)
Zal(u, u')]
(154)
D2
(155)
De
Here. 3 is computed using the variance bound computed by Lemma 16: 3 n 4L2 n²2 To
prove Eq. (140), we directly invoke the Lipschitz condition for A from Eq. (152).
Pr (Z, A (Z) 2 Pr
Z 2 Vn.
(Eq. (152))
(156)
Σ
[/W'E() Var( Zi(u, [u, w'l)
(Chebyshev's Inequality)
4T2
(From variance bound, Lemma 17)
D
u,w'E[n] x(n]
(157)
B
where 3
4L2 n²
(158)
De
Using the results in Eqs. (139) and (140), prove the main result (5), using the union bound Pr(Isim(Gee, Gg) sima G,) 2 e)
S Pr([sim(Ger Gg) fim(Gen Gg)l 2 2
+ Pr(Isima(Ger Gyy) - sim G,) 2 5
(159)
43
48
83
<
+
De
De
De
3u
(160)
De
34

---

Published as a conference paper at ICLR 2026
E.2.2 PROOF OF THE FACT THAT EQ. (3) AND EQ. (4) ARE EQUIVALENT
Here, we will show that if have:
sima(Ge: Gg)
max
Σ
-/
P(u,,,
(161)
PEP
then sima can also be written as:
sima(Ge, G,) = (0)))=((SR()))))) (SSOR((X ([, SORT X (1 d)))
(162)
In the following, provide this result, in terms of any vectors and y.
Theorem 12 (Rearrangement for s). Given a convex function p .R - [0. oo), which is not
necessarily symmetric and satisfies p(x) = >, [(x((). and a score function s that is of the form s(.) = Pmax - p(()), for all æ, y with [0]|oo: |///|oo S Tmax, we have:
E max PEP
s (xful) - y/u')) Plu, u'] = s (SORT(()) SORT(Y))
(163)
This is well known result for L, metric. For optimal transport between distributions, such result exists for convex distances (Santambrogio, 2015, Proposition 2.17). We still provide the proof for self containment. Here, we will apply Lemma 14. But that requires some conditions on s( (stated as y therein). We will prove that as long as p is convex, s satisfies those conditions required to apply Lemma 14.
Proof
Those conditions requires us to show the following: For a1, 02 b, b2 with aj 2 0z, bj 2 b2. p p(a1 - b2) + p (a2 b1) 2 (a1 b1) + p - b2) To show this, invoke the convexity of p p-). For any 2,, v. z with x 2 y and z 2 0, consider y + y. Convexity of gives us:
(164)
the case 2 y, then x + 2 2 x 2
(x - y)p(x + =) + + 2 pzz)
(165)
I x y
zp(x 2) + (a y)p(y) 2 p(y +)
(166)
x x 2 y
Summing both inequalities, we have: p(x + 2) + p(y) 2 p(x) + ply + 2). W.l.o.g. consider a1, 22 b1, 62 R with a1 a2, bi 2 b2. of the following form:
bi +
02 bj + y
b2 bi
This gives us Eq. (164).
To finish proving the theorem, we notice that: due to maxpep. Ens (axfu] - y(ur) Plu, u'] maxpeP, a Enw s ((P'x)[u] y(u')) Plu, uf) for any permutation P', we have:
3 (x|u] y)u')) P (u, u'] max Σ (SORT( ylu'l) P w'| PEP.
(167)
PEP,
Now, thanks to Eq. (164), s( satisfies the conditions in Lemma 14 with p(x, y) in that Lemma
satisfies μ(x y) s(x y). This gives us: maxpeP, En (x[u] 3 (u'))) Plu, u²] s (SORT(()) SORT(y))
as designed before introducing Eq. 2.
35

---

Published as a conference paper at ICLR 2026
E.2.3 AUXILIARY RESULTS USED TO PROVE LEMMAS APPENDIX E.2
Lemma 13 (Danskin's Theorem (Danskin, 1967)). Let g: R Z E. be continuous function of Two arguments where Z C R!. is compuct set. Let fzz max (0,, 2). then
f is convex if g( 2) is convex for any 2 E
f is differentiable at x if the arg max; is a single possible element.
The semi-differential of I in the direction of v is given by
d.f(x) = max g' (x, 2/v) =E
(168)
where (2 is the derivative of in the direction v, and Z the set of maximising
points of g(:
If f is differentiable at x, then the gradient of f is given by (x) = Vag(x, =
Vig(æ, =²) (gradient in the first argument).
Lemma 14 (Rearrangement Inequality). (Wu, 2022, Theorem 7) Let p be real-valued function of variables defined on La x Ib. If
p( U2) p1(22, u1) ((21,32) + ((x1,81)) 2
for all S D2 in La and 11 I y2 in 1b. then
Σ p(a;, bn bn- S Σ
plar. ba(t)) Σ pla;, b.)
(169)
ie|m
sE(m]
sE(ml
for all sequences 01 S 02 .... On in Las b1 S S... in Ia, and all permutatiions [n].
Theorem 15. If the columns of X are distrbuted exchangeably, then for any d, d' E [D] and u, [n]
Em,(d [d] (xa[d) [x] _dd" [d.). (x.,dd) xx(d"))
(170)
Proof As columns of X are distributed exchangeably. the joint distribution of (z x.)) is also exchangeable. Thus the marginals are also the same, Pæ.[d]]au.dd P=._d"],...d'") Therefore,
E m. (df (x [d] a.((d)
s (ax, y) Pauld]aa.ld (xc, y) dx dy
(171)
(xx, y) Pa.,ld',,a, a.. [dr] (x) 4) dx dy JRa
(172)
Em (am (x - (d](d
(173)
Lemma 16 (Variance Bound for EdE Za). Let Za be defined as in Eq. (143). Given that (u))le,. (
(u)ll2 S B, then we can bound
Var
Σ
Zal(u, ALZ
(174)
dE(Di
Proof We write the variance follows:
Var
Σ Zal(u, w'))
dE(D)
Cov(Zal(u, 2')], [(,
(175)
Σ (s(a000 x (v'(t)) EIs( x0 (v)(ti)
(s(z(() (w)bi (s)li) (v'b)) - E|s( ( (c)bi)))
(176)
36

---

Published as a conference paper at ICLR 2026
We refer to x (u)li] - (u'(l as & so that Eq. (176) can be rewritten as
Σ
[((((á)) ((s())))(ss(ár) B[s(6x))))
(177)
d,d' {
Σ
(((((a)) - =(0) - - -00)(()))) =(0) - B[s(dr) - s(O]
(178)
d. (
Σ
((()( =(0))(((0x) s(o)]] -[(((()) -()))][((((](])))) - =(0))] (179)
d,d' (Dxx((
E
[(()( (00))(())))((0))) -
Σ [((((d)) s(O)]]
(180)
ddd'=(D|x(D]
dE(D)
We write (s(da) s(0)
De [dal Lg loal- Thus Eq. (180) can be reduced to
max 228
Σ
[[(((6a) (()))s(( s(0))]
Σ ([(s(d,) - =(0]
ddd'E(D)x(D]
dEIDi
Σ
[[(s(5a) -(0))(((xx) x())]
(181)
d,d' DIx(D
L
Σ
E 1160118211
(182)
< 1 [ < 4T. D DB²
(183)
Where the final bound in Eq. (183) uses the bound on (u).
Lemma 17 (Variance Bound for Za). Let Za be defined as in Eg. (143).
Given that
||al9) (u')l2, (x (u)lla S B, then we can bound
Var( Bar(Za(u,,"))) u'))) S BL
(184)
Proof for the Variance Bound We follow similar steps as the proof for Lemma 16.
Var Zal(u, uf d')])= s E [(s(5a) ((s(6))))(((()) - E[s(5a)])]
(185)
< E [<s(5)) - =0)))] - B(s(5a) - -0))?
(186)
< E [(s(5a) - =()))
(187)
- 131131 = L3
Σ B[S
as B = [809 -...= =...=1188]]
(188)
D
dE(D)
1
L2
= 3
- D
4B2.
(189)
D
Here, the final bound in Eq. (189) uses the bound on (z()(()) (u).
37

---

Published as a conference paper at ICLR 2026
E.2.4 PROOFS OF LSH RESULTS
We show that our random hyperplane hashing on T. and T used in Eq. (9) gives us produce a valid LSH for the similarity measure sim,(Ges Gy) and sim Gy). We first establish some key details of our procedure.
Augmentation of Low Pass Filter with scoring function s(.) Since s(-) is bounded and absolutely convergent, its Fourier transform S((w) = 2 Seen s(2r) exp(-wwr)dz is finite. This allows us to write s(x) = Lwea S(ww) exp(wx)ddw. However, for simple scoring functions, S(w)) imparts significant amount of high frequency signals, which leads to divergence of the integral of [S(w))] To tackle this problem, we multiply smooth low pass filter (w) 2n A+ow with S(ww to obtain SA (ww) LPFx (ww) which absolutely integrable, i.e, SWER [Sx(w))ldw oo.
A
We first demonstrate that the integral JWER [Re(S(w))) ( du may diverge in the absence of smoothing. Consider p as the hinge function, p(x) = [x]],- Applying the construction, we obtain s( and 5()) similar to the formulation in (Roy et al., 2023).
mmax
Tmxx 5050
s(x)
max
0 S Tmax
(190)
0
otherwise
sin wax
sin? Wilfmaxx
sin wāxax
Imax COS Wil max
S(w) =
Fmax
+
(191)
2nw
2T
2mw2
2mw
In order to show that the integral diverges, it suffices to show that the tail diverges-
/
000
[Re(S(w))) + Im( (Sww)) dw 2 (Re(S(ww) + Im(S(ww)) di
using la + 6] s |a|
+ |b]
40
(192)
sin WXmmax
sin 2 Wilmans
sin W.Fmax
Tmax COS walEmmx
Fmax
+ 2
dw
(193)
2Tw
2TT2
2mwwa
2T
000
sin W.Taax
Tmax WTTamxx
sin 2 Wirgins
sin W.T
Fmax
2
dw
(194)
2mw
2nw
2Tw2
2Tw
sin WXmax
Fmax COS Wax
sin
sin WT Waxmx dw
Fmax
dw
(195)
2mw
2nTw
2mw2
2mw2
400
uno
The second term is finite; hence we focus on the first term. number ng. This allows us to write
Choose wa 2nTo + 4 for a natural
sin WTmax
Fmax
COS max dw
000 f Fmax v2
sin(w 4) dw (196)
Fmax
2TT
2Tw
2Tw
000
sin(t - 7 dt substituting 1 = W.Tmax
(197)
2mnot
2TT
1
27 (1++1++ T
22
sin 7) dt
(198)
2mww
an++ 4 2=2
2
[sin(1 - b dl
(199)
2T 2 (n 1) 7)
Jntt
n=2
2
V2 2 (n 2) = 00
2>
(200)
2m20 2T( + 1) 7)
2n
Finally, we show that that after the low pass filter is applied, the resultant integral is JueR [Re(S)(w)) [[mmSS(ww) du < integrable for the general function considered in
38

---

Published as a conference paper at ICLR 2026
this paper.
[e((S) [Im(SX(w))) - v2)5 Modulus of the complex number
(201)
/2|S (w=) [LPFx(W)]
(202)
As s( (() is measurable, bounded, absolutely integrable function, we know that lim [.((w)) =
by the Riemann-Lebesgue Lemma (Bochner et al., 1949).
Thus, [S(w)) is o(1). [LPFx(w)] 2x V S (sx dw < oc.
1
Iwl Thus, [Sx(ww] = ol (() and thus,
/ [Re(S)(wW)) + [m (Ix()( dw S / v2]Sx(w))ldu 00 WER
(203)
WER
39

---

Published as a conference paper at ICLR 2026
Proof that RH on the approximate Fourier vectors Tq.d and Te.d give LSH Finally, we show our results which shows that the above Algorithms result in valid LSH.
Theorem 18. Let sim and sima o) be defined as in Eq. (2) and Eg. (3) respectively.
compute h h( (G.) = sign( w Tq.a) with w E (0) Then we have the following results:
1. (LSH for simal )) For e O, there exist p. p.p', A,nnmmmnn (e) 0 and Mmin (e) such that the above random hyperplane hashing will give a (Su, ySu. P. JALSH for simal when
À > Amin (c), M Muin(().
2. (LSH for sim ()))) ) For c, > O, there exists P. F. Amii (c, c') > 0 and M (ainnce, > O such that the above random hyperplane hashing will give a 1S,, 7. )-A.
-ALSH for
sim( when X )mia(e,''), M >> Mmin (5, and D >> 1/22e'.
Proof of (1) Assume L, is the Lipschitz constant for s()) and Leos is Lipschitz constant for cos- max - maxe,q ())R((x(9)) (O and Tmax = max X { | X (o,,,0) Our random projection hashing is finally based on the similarity measure sim, from Section 4, which is the Monte Carlo estimate of sim Eq. (7).:
LPF which is the low-pass filtered version of sima, defined in
(Ge Gg)
T Te.
(204)
M
In the following proofs, we shall trace back the approximations from sim leading up to sima. and appropriately bound the differences. Let Ix - Snx [Re(Sx(w))) + [m(Sx(e)))ddo. Then,
(Rw(S)(W)) + [Tm(Sx(W)) IX
T. (1)
(205)
We also observe that [ nīx and ||T.all3 MnIa. From drop d from f(a) (G₂) and h(d) (Ge).
fT Fead
SA (f(Gg) = h(Go)(w) = =1 COS
(206)
[Tq.allz (e.all
COS -
[Tg.dll I1
1
sim 1PP (Gor Gg)
(207)
JR (Tq.(w)))12 (Ted (2)))))) (w)dw
π
1
sim
LPF (Go, Gg)
C0S
-1
T (q.a(w)]12
(Te. w 1|PA (epP((W))
(2px)(w)d (w)dw
(208)
1
(Ge Gg)
ssmm
LPP
(Ges Gq)
cos
+ cos
π
nTx
In
1
LPF (sim (imm GT)
1
(Sima(Ges Gg)
cos
+
cos
π
nly
π
nil
Iz
1
(G Gq)
cos
(209)
π
nIx
Note that the argument (G,, nnIx, in the final term must reside within the domain of cos ! Since TA is monotonically increasing in X, suffices to require À > infx Tx >> fmax/n).
40

---

Published as a conference paper at ICLR 2026
We shall now bound each of the terms in Eq. (209)
1 Leus
1
I
sima Gg) sim (G Gq)
(210)
π
nIx
Leos
Ew
[Zi
simalGos Gg) - simd (G Ga)
(211)
Leus
(Lemma 19)
(212)
anIa
Leos
nl3
Leos
(213)
mnIy
T MVMn
As cos is monotonically decreasing, and Lipschitz in our context, we can use the bound in Lemma 20, i.e.
Leoos
Lia
Smax
Leos Le
< Is S
(214)
T
A
mmx
òmax
Tyx À
Thus,
simalGes Gq)
Leos
Loos La
P = $
COS
+
(215)
nIy simma(Go Ga)
Mn
xIλ X
Leos
PrEM(((G,) = -MG.) 2
COS
(216)
nTx
TVMn
Leas
Iig + Smax 2xmax
(217)
TAI
Smax
Using Lagrange's mean value theorem, we have:
(750 cos -1
Su nlv
( ()=)))
[[cos- 1)50))
y So nlx nly
cos 1
=
te
ndl
nla
(218)
(1 7)
2
as (cos (cos- < -1
(219)
Andn
From the bounds obtained in Eq. (215) and Eq. (217), we have
1
750
Leos
Leos L. TI
p' = 1 --
cos
+
(220)
π
nI,x
TVMn
1
So
Lros
Leos
p 1
C08
-1
Toy Smax 2x 8max
(221)
π
nIy
x TvMn
TdI
We have p > pppin if
So
2
Lecos
Co8
cos
2T. + Smax mx Emax
(222)
nTA
nIx
My
TAJ
Using Eq. (219), the sufficient conditions for the above equation are:
2 (1 7) 2Leos
(223)
3 anla
TVMn.
1 (1 -)
Lens
TdI (2 + Smna 2x 8max
(224)
3 xnI^
We obtain
3 Toooo (2l,, + 8max 2x Imax
7L2 9L2 nI13
A
M
(225)
(1-7)80
(1 2
This is sufficient condition for the LSH to hold that denotes the existence of appropriate Rmmin Amin such that the LSH holds. We can also choose other bounds on M and À such that the above conditions satisfied, and the LSH is valid. We now show the second part of the theorem.
Proof for (2) Now that we have shown that we have a %S. p. p/ALSSLLSSHH for sim,, we show that it is hash for sim. We shall use the concentration result in Proposition 7. Given 1 (G.,, Ggy)
41

---

Published as a conference paper at ICLR 2026
sim,(Ge: Gg)l with probability 1 Buó, can express this as:
-6 (im, Gg)) sima(Ge, Gg) S
(226)
D
with probability 1 Sgd. Here, the randomness arises from simg. This can be rewritten as: 1 -e - D sim(Ges Gy) (im Gg) Se
(227)
simaa Gg) S (is Gg) +e (condition 1),
(228)
sima Gg) 2 D (im Gg) - (condition 2).
Both condition 1 and condition 2 have probability 2 1 - Puó. Here, and p' are computed in the proof of (1).
1. Condition 1 implies that if Jsim(Ge,,r, G.) S 7S0 6, then sima Gg) S ySo with probability 2 1 - Ago. Therefore, when s Gg) S 7S0
Pr f. (f((G)) h(Ge)) =Pr(f(Gg) = h(Ge) siima Gg) S S Pr(sima(Gee Gg) S 750)
+ +Pr(f(Gg) h(Ga) sima Gg) > 7)) Pr(simm Gg) > S)))
(229)
5 - -1
(230)
2. Condition 2 implies that if sim Gq) 2 So + e, then sima(Ges Gg) 2 So with probability 2 1 - 306. Therefore, when J (Ge, GT) 2 S +e
Pr frf,)()) h(G.))
=Pr(S(Gg) h(G))) ( (Ge: Ggy 2 5o) Pr(sim Gg) 2 So)
+P[(J(G,) = l(G.)) (G, G₂) < Sn) Pr(sima Gg) < So)
(231)
2 Pr(f(G,) = -)(G.) (Gem G₂) 2 So) Pr(simm Gg) 2 So)
(232)
2 p (96)
(233)
Then, have (D(S) + e), D(vS0 - -), 306), p/ Bod) + B66)-ALSH
p(1 B08) p1(1 BBd) + Bgd
(234)
Bod
p p¹
(235)
305
We shall find a sufficient condition for Eq. (235) to hold. We use the expressions in the previous
results. Finally, we reparameterize the problem with S A ((S +)), S1 D(ySo-6 with 7/
5o 7 < 1, 5- = p(1 - F05) and f/ = p' (1(1 00o) + 0
For (ww) x [Re(S()))) + [S (w))), the above criteria can be achieved by taking
2 Looos
M > n
(236)
(1-9)88 21
1-906
2Leenen 22,, + Bmas Trmus Smax
for x
Reparameterizing with S1, 71, we obtain
(1-7)50
2Loos (2L + Smax 2.maa - Imax
2Tecos (1-7))
M > n
D
de2 A
2
(1 (1-7)) (1-1)S1/DD 2c
21x
1
300
(237)
As before, we pick Muin- Amin such that the above conditions are satisfied. We can also choose other bounds on M and À such that the above conditions are satisfied, and the LSH is valid. Note that here we have considered the randomness of model initialization be part of the randomness of the hashing routine.
42

---

Published as a conference paper at ICLR 2026
E.2.5
AUXILIARY RESULTS USED TO PROVE RESULTS THIS SUBSECTION E.2.4
Lemma 19. Suppose sima is defined as Eq. (7) and simy is defined as Eq. (9). Then, we have the
following concentration bound:
E
simma Gg) sima (G,, Gg) S
R M
nh
(Traluu) T TT Teul(uu))
(238)
Proof We observe that:
sima Gq) - simalGe. Gg)
(ima Gy) (Gea Gy)
2
Var
( (imma(Ges GG)
(239)
Var
Σ Σ Tgia(wru) T Tadd(aa) [M]] mE(n)
(240)
M
Var (T (Tg.)(w))) TT,aa(uu)) V M
E (Taalwwr) Te.al (w))
(241)
M
Here, Eq. (241) follows from the i.d sampling of wu-
Lemma 20. Suppose sima is defined as Eq. (7) and sima defined as Eq. (3). Then, we have the following concentration bound:
-(nte nTss
78maax
sima(Ger Gτ) sima(Ge: Gτ) S nIe
(242)
Tmax Ómax
X
where Ly is the Lipschitz constant for 8; 8max
A maxeq [|0ORT(0(()) SORT(a! and
max max[I] (0X(91100,,0)) || (x)()]]]a [00,000 < Tmax
Proof. Let sx denote the fourier inverse Sx
/ Sx (ww) (aa
sima(Gos GT) =
(243)
"E(m)
Σ
- x (0) (w)ld)
(244)
ME(M]
We shall bound the deviation of the smoothed score function 8\ from the original score function
(x(x)= / s(x -)) [P)))(t)dt using F-glf F FF' F [g]
(245)
= [ 5(x - ((xx=))de* (( I s(x - t)
(246)
(where (-) is the Heaviside step function)
s(x + x le-''e substitution with 1 + At
(247)
Tom s(x)) de + S pc
(s(x - -=(())) tdt
(248)
s(x) + 1 (s(x 2) s(x)))-=al
(249)
We shall use the fact that is clipped to outside the domain [- 2xxxmx 2% 20max] We have the following possible cases:
Case x + 1 2rnax t> X(2xmaxx z)
Case 2 2xrmax $ 2Tmax
X(20mmax - xx) 2 1> 0 X( 2xmax x)
43

---

Published as a conference paper at ICLR 2026
This lets split the integral in I into two in order to bound the term.
J (0(x + 5) s(x))e =
A(2zmax
(s(x + )) s(x))e
(0 s(x))e dd
(250)
A A222max m.
1228max 2)
(s(x + 2) s(x))e
-)s(())]e dt -s(x)e A[2mmax
(251)
now bound |J| as follows:
a2a 2)
t e
| $
Lg
't
(s is Lipschitz with constant L,)
(252)
L
A [-(1+ + 1)e 1)e 112 A(2mmax La [1 1)e 1)e A(20max max =1=11
(253)
1==
Lg
(1 (1- e1 e- 3-122mmax
X(2xmax + δmax)e A(2iraan + mmax)
(254)
X
$ [-(t+ 1)e 1= I.s
L.
(255)
X
The bound in (253) relies on integrating over larger interval. This yields the bound Eq. (254).
However, for purposes of this proof, we use the looser bound Eq. (255) by integrating over (0, oo).
Using the fact that 0 S s(-) < mmax in Eq (251)
T Smaxe -A22mmax 3) <I |
(256)
L
5maxe A1227max x) <IS L, )
(257)
L
Smaxe SI Isg A(2
(258)
mmax
X
Eq. (258) blows up near (2rmax Smaxx 2s O as is a much looser bound than Eq. (257). However keep leads to simpler closed form expression for X.
44

---

Published as a conference paper at ICLR 2026
F LIST OF GNNS
We collect the following list from Pytorch Geometric.
1. GNN
(1) Gated GNN (Li et al.. 2016; Gilmer et al., 2017) (Already showed)
(2) GCN (Kipf et al., 2017)
(3) ChebConv (Defferrard al., 2016)
(4) SAGE (Hamilton et al., 2017)
(5) ResGatedGrrphhonn (Bresson et al., 2017)
(6) GAT (Veličković et al., 2018)
(7) AGNNConv (Thekumparampil al., 2018)
(8) GIN (Xu et al., 2019)
(9) SGConv (Wu et al., 2019)
(10) TAGCony (Du et al., 2017)
(11) APPNP (Gasteiger al., 2018)
(12) SSGConv (Zhu et al., 2021)
(13) MFConv (Duvenaud et al., 2015)
2. Graph Transformers
(1) Graph Transformer (GraphGPS-stylee (Rampášek al., 2022)
(2) Graphormer (Ying et al., 2021)
(3) Spectral Attention Network (SAN) (Kreuzer al., 2021)
(4) Exphormer (Shirzad et al., 2023)
(5) NodeFormer (Wu et al., 2023)
Here, we will take node embeddings to be column vectors, but the graph embedding X to have along rows. As such we will use @ for the parameters right multiplied and W for left multiplied. D, A, refer to the degree, adjacency and Laplacian matrices respectively. Similarly, D, A, refer to the normalized degree, adjacency and Laplacian matrices respectively.
We demonstrate transformations for various graph layers that can be used to maintain/induce permu- tations in the output, which would be required for showing exchangeability applicable, we may take arbitrary permutation T2 on the input and a corresponding π in the output. For some cases the permutations are more restrictive (such as π TT2).
certain layer. Where
These transformations can then be composed to generate the permutation inducing transformation for the entire network.
We have shown transformation for architectures such as the MLP (FF) and GRU (GRU). For a given permutation (where is clear from context), we define the transformed versions follows:
GRU*(X TT, H GRU(X, H)w
FF (XT) FF(X), T
or if the input and output permutations are different:
F = FF(X)
F.1 GRAPH NEURAL NETWORK
Based on the original formulation, can be row or column vector and therefore æ is pre-multiplied or post-multiplied
(1) GCN (Kipf et al., 2017):
X' = -TD--1AAD-1/X
(259)
X'T = D-1/2 1/2 ((T))
(260)
X'm = D-122A -
θm))
(261)
(2) ChebConv (Defferrard et al., 2016): It uses Chebyshev polynomial filters the rescaled Laplacian. The Chebyshev polynomials are defined as (=) = 1, Ti (x) = x and T, (x) 2rTh-1 (x)) Tx-2(x) for 2.
45

---

Published as a conference paper at ICLR 2026
( Σ Te(T.) (1-
(262)
K
X T1 =
Σ T(( (x (k-
T22 (T)
(263)
SAGEConv (Hamilton al., 2017): We take the aggregate function be permutation equivari- ant (eg. mean/sum).
x (R) W a
(k-1) W2 (G ())
(264)
πæ: (R) a (( Wi ) (k-1) + (#W2= AGGREGATE((Ts; ())
(265)
or, there may be a layer before the aggregation (allowing for more flexibility in the transforma- tion):
a (k) a ( (k-1) W2 AGGREGATE ())
(266)
T a (k) = o (( W a (k-1) + ( W2 AGGREGATE (T22a (k- (k }})
(267)
(4) ResGatedGraphCon (Bresson al., 2017): Adds residual connection gated convolu- tion mechanism.
(k)
(k-1)
Σ
W2a (k-1) (Wa
(k-1) Warsh-11)
(268)
JEN()
(T W T2 ? (--11)
+ Σ
( W2TT (TT20)) 11-1))
o @ Wa (TZar
(EN(()
+ ( W (T2 (k 1)
(269)
(5) GAT (Veličković et al., 2018): The attention score can be made invariant.
x (K)
Σ
w 20 (R-1)
(270)
JEN())
Σ jEN(()
(T, W(())) vt T DTTA (k-1)
(271)
exp (LeakyReLU (a" [ x; W x wxll)
0aj Σ ΣkEAtoURa exp (LeakyRel.U (a W Wæ, Wxx)))
(272)
exp (LeakyReLU (a W nZ; W π Tx;
aij ExEN(OU(S)) exp (LeakyReLU aa [ π πे; W πœι)))
(273)
If the aggregation is concatenation instead of sum, the output will not be exchangeable for all dimensions. rather, each block of dimensions corresponding to a head will be exchangeable. (6) AGNNConV (Thekumparampil et al., 2018):
X'=PX
(274)
Where,
(me):
may moz
exp(B cos(os (x, x,))
exp
Ta.
Ptj EvEN(OOO)) exp(B cos(2;; xkk)
(275)
Σ EXEN(OU(() exp
B
So this layer is equivarient to any permutation (7) GIN (Xu et al., 2019):
X' =F ((1 X X
(276)
X'm FF ((1 + (X A(Xa2)
(277)
A powerful injective update via MLP which combines self-feature (with learnable epsilon) plus neighbor sum.
46

---

Published as a conference paper at ICLR 2026
(8) SGConv (Wu et al., 2019): A K-step precomputed propagation that simplifies convolution.
X'
D D-2 1/2
AD
AD11/22 K
XO, A+
(278)
1-2 À 1/2) K
X' . =
[xT2)(TT]m)
(279)
(280)
(9) TAGConv (Du et al., 2017):
K
D 1/2 A D 1/- *
X'
Σ
XO:
(281)
k=0
K
X'T
D 1/2 AD AD-1/2 (x
(282)
km0
(10) APPNP (Gasteiger al., 2018):
x X
(283)
X (k) (1
(k-1) 4xx
(284)
X' =x(K)
(285)
This layer is equivariant to any permutation π.
x π = X
(286)
( π (1 -a)D a)D-1/2
1/2 AD 1-A--/2/-00 1/2 (1-1), π + +xx(0
(287)
X'T X(K)
(288)
(11) SSGConv (Zhu et al., 2021):
X' =1 a)
D D-12 À D 11/2)
X6, + a X
(289)
X'm (1 - a)) (D- 1/2 ÀD AD-1/2 XT Oi + a X n. θ2
(290)
Skip-connection version of SGConv with initial-feature mixing via a.
(12) MFConv (Duvenaud et al., 2015): This has distinct weight matrix for nodes of each degree.
2 (1) 3i +
Σ JEN(()
Waeg(s) æz
(291)
T [
W deggtt) 22 (T2211) +
Σ JEN(1)
(T W (ieg(t))T) (TzHz
(292)
F.2 GRAPH TRANSFORMERS
Multi-Head Attention (MHA) Before examining specific Graph Transformer architectures, we first establish the standard Multi-Head Attention (MHA) mechanism that forms the foundation of most transformer-bes based models. The MHA operation transforms input representations H E Raxd through learned query (Q), key (K), and value (V) projections:
Q(h)_ = H
(h)) = (() (()) V(h) = ( w
(293)
Q
Q
(M)
(K) (N)
(N) softmax,
+ Bij
(294)
Vds
( a (M) (M)
(295)
MHA (H (0) Concat( Z
Z Z Wo
(296)
where each attention head h E f1....,f) f} computes scaled dot dot-product attention independently, and Wo projects the concatenated multi-head output. Given the input H + H we can transform (h) (h) and (K(h) V as (h)) + n. Whh), And the output of MHA can be transformed by π
Q by Wo + WOT.
Using the above, define MHA, such that MHA B (xx) MHA B (X)T.
47

---

Published as a conference paper at ICLR 2026
Note that in general, different attention mechanisms dealt with similarly the attention parameters can be used to undo the effect of a preceding permutation, hence the attention score computation remains unchanged.
Transformer layers also typically include Layer Normalization, that we will largely omit here, as is straightforward that it permutation equivariant.
(1) Graph Transformer (Rampášek et al., 2022):
Q (h) = H w(()
K H K V WH
(297)
Q (h) (K + Bss)
(h) 0i soflmax,
(298)
dd
(h) = (1) (h)
(299)
H = H - MHAB(H
(300)
H ((+1) (F(
(301)
We observe that the following transformations are sufficient,
H π (0(0 T MHA (HH
(302)
H (++1) = (++1)) +F (F
(303)
(2) Graphormer (Ying et al., 2021); Firstly, the graphormer adds centrality encodings to the node embedding (0)) Hence these encoding require the same permutation as that of the input node features. The graphormer adds spatial and edge encodings as attention biases Biy. As transformation does not affect the Q-K dot product, it does not affect the attention scores.
Q (k) = H0
khh) (
((()) K
Vhk (+(
(304)
Q (h) (K)
aij softmax,
(h)
enc
(SPD(i.)) + iedeo (edge-path(i,, (i.
(305)
Vdk
(h) (1))
(306)
(++1) FF (H (H)(HH())
(307)
(h) Hence, the same transformations as the graph transformer follow, as o remains unchanged.
(3) Spectral Attention Network (SAN) (Kreuzer al., 2021):
H ( H (6) S
(308)
Q (h) A (0 (()))
(N) (h)
(0) (h)) K
V(A = (0
(309)
(K!
!T)
(h)
softmax,
(310)
Vdl
z (h) = (1) ((+1) (F(H (HH (0))
(311)
(312)
Given the Laplacian cigendecomposition L = UAUT, the LPE Transformer processes concate- nated eigenvalue-eigenvvetor pairs [^;; u. to produce learned positional encodings E Raxd If H is permuted, we require the encodings of the LPE Transformer to also be transformed to permute S. The remaining steps the transformation can proceed as in the previous cases.
(313) Exphormer (Shirzad al., 2023): The changes here pertain to the expander graph and the global virtual nodes. As these can be regarded as structural changes to the graph before applying the graph transformer, we can take the same transformations as the graph transformer. (5) NodeFormer (Wu et al., 2023): Notably, the modification over the base graph transformer is related to the computation of the attention, which uses kernelized attention to speed up the otherwise quadratic self-attention. The above outlined transformation are again sufficient as the kernelized operations preserve the transformation to WQ. WK so that the attention still invariant.
H π (0)) S
(6) Gophormer (Zhao et al., 2021): The proximity score term in the attention can be seen as a structural bias that is not affected by the permutations along the embedding dimension. Once
48

---

Published as a conference paper at ICLR 2026
again. by transforming the Wo. WK. Wy matrices accordingly, ensure that the same transformations as the graph transformer follow.
Qth) H (6)
(M) @
K H (R) K v(N (K!
W
(314)
Qu (b)
( softmax.es,
bom (u.
(315)
Vdz
((h)
Σ
(10 uv
(A)
(316)
VES.
(7) SpecFormer (Bo al., 2023): S. + MHA(H ())
H
(E+1) FF(HS)
(317)
SpecFormer computes spectral filter g from eigenvalues via Transformer. Since the eigenvalues X; are independent the feature dimension, the filter compu- tation is unaffected by feature permutations
The spectral convolution X UDiag(9) X is naturally equivariant: input X π yields output X'n. π. For different input/output permutations, transform any subsequent linear layer W n2 W 1.
49

---

Published as a conference paper at ICLR 2026
G ADDITIONAL DETAILS ABOUT EXPERIMENTS
G.1 DATASETS
We build retrieval datasets from four benchmarks in the TU Graph Dataset collection (Morris et al., 2020): ptc-fr, ptc- fm, cox2, and ptc-mr. Each dataset contains 500 queries and corpus of 100,000 graphs. following the setup in (Roy et al., 2022; Lou et al., 2020). To sample graphs, we adopt the BFS-based extraction strategy introduced in (Lou et al., 2020): starting from randomly chosen node, a BFS traversal is performed until the induced subgraph spans between 5 and 25 nodes. This method is applied independently to construct both query and corpus graphs.
For subgraph matching (SM), binary relevance labels are generated using the VF2 subgraph isomorphism algorithm (Hagberg et al., 2020). A corpus graph G, is marked relevant to a query G, if Gg is a subgraph of G., i.e., rel(G G₂) = [G, C GeI, where [-]] denotes the indicator function.
For graph edit distance (GED), we use the GEDLIB solver (Blumenthal al., 2019), setting insertion cost esp = 1 and deletion cost ég 2. Relevance is determined by thresholding the computed GED: (G,, G,) = [GED[G,; Gg) < Thrs], for a fixed threshold Thrs. Results under symmetric cost setting (Eq. cost GED) with cg cg are also reported in Appendix.
For all datasets, we partition the 500 queries into 60% train, 20% validation, and 20% test splits. Dataset statistics for the subgraph matching and GED tasks are summarized in Table 6 and Table 7, respectively.
Table 6: Graph statistics for each dataset generated for Subgraph Matching (SM).
Dataset
Query Graphs
Corpus Graphs
B 1 b
Nodes
Edges
Nodes
Edges
Label Ratio
(min/ / max / avg)
(min / max avg)
(min / max / avg))
(min / max / avg)
PTC-FR
(6/ 15 / 12.65)
(6/ 15 12.41)
(16 / 25 18.68)
(15/ / 10.17)
0.13
PTC-FM
(7 / 15 12.58)
(7 / 15 12.35)
(16/ 25 18.70)
(15/28/ / 20.14)
0.12
COX2 PTC-MR
(5/15/ 15 / 13.21)
(6/ 16/ 12.82)
(16/ 25 19.65)
(15 / 26 / 20.24)
0.12
(6/ 15 12.66)
/5/ 12.41)
(16/ 25 18.72)
(15 / /8 / 20.18)
0.12
Table 7: Graph statisties for each dataset generated for GED,
Dataset
Query Graphs
Corpus Graphs
y=1 y=
Nodes
Edges (min / max avg))
Nodes
Edges
Label Ratio
(min/ / max avg)
(min / max lvg))
(min / max / avg)
PTC-FR
(9/ 14 11.14)
(8 / 16/ 12.25)
(6 20 / 14.66)
(5 24 15.77)
0.07
PTC-FM
(9/ 14 11.09)
(8 15 12.08)
(6 / 20 14.64)
(5/24/ 15.73)
0.07
COX2
(9 19/15/11.5 11.61)
(8 17 12.90)
(7 / 20 15.48)
(6/20 20/ 15.79)
0.04
PTC-MR
(9 14/ 10.90)
(8 /5 11.71)
(6/ 20/20/ 14.67)
(5/ / 15.80)
0.08
G.2
EMBEDDING MODEL ARCHITECTURE
To supervise retrieval with transport-based distances, we train a neural scoring model composed of a GNN encoder and a
aligner, optimized using pairwise ranking loss (Roy et al., 2022; Jain et al., 2024). Here, init, is an LRL implemented as a single-layer MLP that maps node features to 10-dimensional embedding space. msgg is a message passing block consisting of two linear message functions (forward and reverse), each mapping concatenated node-edge features to a 20-dimensional hidden state, followed by GRU with hidden size 10 to aggregate incoming messages. upd, is a two-layer aggregation MLP: the first layer expands the node embedding to 20 dimensions, and the second reduces it back to 10 dimensions to produce the final node representation. To compute the permutation matrix P. we solve a linear assignment problem via 10 Sinkhorn iterations at a temperature of 0.1.
Separate models are trained for each supervision Distance (GED)-based on their respective distance formulations using Eq. (1). The model is trained
Matching (SM) and Graph Edit
50

---

Published as a conference paper at ICLR 2026
to assign lower distance scores to relevant corpus graphs compared irrelevant ones, using the following hinge-bann based loss:
Σ E
[A G,) A(Go, ((G,,GG)))). + 7|+,
G..GG. (..GG
where y E (0.1,0.5) fixed margin, and A(.,) :) the transport- baaee distance (Eq. (I)). We set the node embedding dimensionality to D 10 in all experiments.
G.3 FOURIER-MAP AND HASHICOEE TRAINING
We adopt the training framework proposed by Roy et al. (2023) to improve the quality of Fourier- based representations and optimize the hashcodes derived from them. Specifically, we apply two neural networks Vr, and V. that take as input the Fourier representations F, and Pe.d of query and corpus graphs respectively, and output transformed feature vectors:
24 (T
Zc (TT.)..).
(318)
These transformed vectors are trained using a binary cross-entropy loss that promotes high cosine similarity between relevant query-corpus pairs:
min Pgite
Σ
-rel(G Gg) log(1 cos(2g: zc))
rel(G Gg)) log(1 cos( zg. zz))- (319)
G..
To generate binary hashcodes from the transformed fourier feature vectors, we use learned projection matrix W E gddm,, x diiu and apply the random hyperplane method:
(G,) sign W 2q):
h ( (G..) sign [ z.).
(320)
for each d E [D] [10]. In practice dimr 10, dim, = 64. We set the number of w samples M = 10, We use the frequency cutoff À in the low pass filter as 100. During training, we use
tanh(W's ( 2) differentiable approximation to sign( W 2), and optimize W using the following
composite loss:
Dash = A111 + A2f12 + A3H3.
(321)
where:
A1: Collision Minimizer Encourages higher hashcode overlap between G and its most relevant corpus graphs compared to irrelevant ones.
Ag: Fence-Sitting Penalty- Penalizes intermediate values of tanh W 2) to enforce hash
bits near 1.1.
A3: Bit Balance Promotes equal usage of +1 and -1 bits across all corpus hashcodes.
We use the default hyperparameters and network configurations proposed in FourierHashNet (Roy al., 2023) for , Ve., and the loss weights μ4.
This training process improves both retrieval relevance and the discriminability of learned hashcodes. Algorithm and 2 summarize the index construction and query retrieval procedures based these learned hashcodes.
G.4 BASELINES
We compare GRAPHHASH against range of methods that fall into three broad categories: LSH-based methods operating on single-vector graph embeddings, inverted index-based multi-vector vector retrieval using FAISS, and graph-based ANN using DiskANN. We also include naive random sampling baseline for reference.
Hyperplane based hashing These methods rely on locality-sensitive hashing (LSH) applied to single-vector embedding for each graph, typically obtained via mean pooling over node representa- tions.
Hoshier (Roy et al., 2023): A learned LSH scheme that approximates banee-based dominance distances through Fourier transformation. It encodes asymmetric containment-style similarities in a form suitable for efficient hash- based retrieval using random hyperplanes in the frequency domain. We use the default hyperparameters and network configurations proposed in FourierHashNet (Roy et al., 2023). Specifically, we use w = 10 samples for the Fourier features, trainable Fourier map optimized using the BCE loss with embedding dimension 10, and
51

---

Published as a conference paper at ICLR 2026
hashcodes of length 64. We train using the loss function defined in Eq. (321), sweeping across all combinations of and other hyperparameters as described in their original paper. To evaluate tradeoffs, vary the number of hash table buckets from 2' to 2 during
retrieval.
Random Hyperplane (RH) Hashing: A classical LSH method that applies cosine similarity hashing to mean-pooled graph vectors. Since it uses symmetric cosine distance, it does not capture subgraph asymmetry or node-level structure. We train the baseline using the same loss function as in FourierHashNet (Eq. (321)), sweeping over all hyperparameter combinations reported in their work. The hashcode dimension is to 64, and we vary the number of selected hyperplanes (i.e.. the subset size) from 2' to 2 to generate the tradeoff curves.
Inverted Index (IVF) We implement the inverted file index from FAISS (Douze et al., 2024) in multi-vector setup, where each corpus graph is decomposed into its node embeddings. These are indexed independently, and during retrieval, each query node probes the index. Retrieved nodes are then aggregated by graph ID to form the candidate set. This simulates node-level matching using learned dense vectors.
For the FAISS baseline, we use the IVF-Flat indexing scheme with nlist = 128 clusters. The index is built over node-level embeddings extracted from the corpus graphs. Depending on the specified distance metric (cos in or 12), cosine similarity, all corpus embeddings are L2-normalized prior to indexing.
either inner product similarity Euclidean distance. For
Graph-Based ANN (DiskANN) DiskANN (Simhadri et al., 2023) builds compact HNSW-style proximity graphs for approximate nearest neighbor retrieval at scale. In our setting, each node embedding from the corpus is indexed independently, and the query node embeddings probe this graph. Retrieved node hits are aggregated to rank corpus graphs. DisKANN offers scalability and fast retrieval, but operates with symmetric distances (e.g., L2, cosine) which may not align well with asymmetric retrieval objectives.
We employ the StaticMemoryIndex implementation with cosine or Euclidean distance as the retrieval metric. The wemory-based index is built using graph degree of 16, build-time complexity of 32, and a search-time initial complexity of 222. We disable product quantization (PQ) and OPQ refinements by setting use_pq_bbillee build-aaFee and opp==alse,,,, respectively, opting for full-precision vectors. During index construction, we set alpha=1.2 2 and filter_ titer_comllextt=32. with multi multi-threading enabled using 16 threads. We vary the top-K K parameter during querying generate the efficiency- accurrac tradeoff plots.
Random Sampling This baseline selects fixed number of graphs uniformly at random from the corpus, without using any learned embeddings or indexing structure. serves as a lower-bound reference contextualize retrieval performance. Here, we simulate retrieval by uniformly sampling fixed number of corpus items for each query. We sweep over the number of retrieved items using the set: {10, 100, 1000, 2000] (5000, 10000, ... 95000], generate efficiency-aceureg tradcoff' curves.
G.5 EVALUATION METRICS
MAP To assess the trade-off between retrieval accuracy and candidate set size, we compute the Mean Average Precision (MAP). For a query graph Gg E Q, let Cye S C denote the set of relevant corpus graphs. Given a retrieved ranking II over retrieved candidate set Rg. the average precision (AP) is computed as:
|mm
AP(G.)
Precur (r)l, E Cyel.
Cya
where Prec@r is the precision rank r. and [[-1] the indicator function. We compute MAP by averaging AP across all test queries in Ques:
1
MAP
AP(G,)
Qrest
GGE
This formulation penalizes high precision with low recall, ensuring models are rewarded only when most number of relevant items retrieved with high retrieval accuracy.
AUC To summarize the trade-off between accuracy and candidate set size, we convert the MAP vs. candidate set size curve into single scalar metric by computing the area under the trade-curve.
52

---

Published as a conference paper at ICLR 2026
We normalize the candidate set size by the total corpus size [C], and numerically integrate the MAP values over the normalized x-axis.
Normalized Discounted Cumulative Gain (NDCG) We also report NDCG to evaluate the quality of ranked lists. For each query Gy. let rel, (r) E {0, 13 denote the relevance label the item ranked position in ql. The DCG rank & is given by:
(r)
DCG
Σ
1r +1)
==1
and the corresponding ideal DCG (IDCG) is computed from perfect ranking. The NDCG is then:
DCG@k
NDCG@k We average NDCG over all test queries to obtain a corpus-level evaluation. This metric does not penalize high precision with low recall. We set 1000.
IDCG@A
G.6 HARDWARE AND LICENSES
All experiments were run local NAS server configured with seven NVIDIA RTX A6000 GPUs (48GB each), a 96-core processor, and 20TB storage, operating under Debian 6.1. All model components, including GNN encoders and hash function training, were executed on GPU memory without resource bottlenecks.
Regarding licensing, GMN (Li et al., 2019) is distributed under the MIT license. The implementations of Isonet (Roy et al., 2022) and FourierHashNet (Roy et al., 2023) are open source and have been cited appropriately in our work. Our full codebase and datasets will be released for public use upon publication.
53

---

Published as a conference paper at ICLR 2026
H ADDITIONAL EXPERIMENTS
We present supplementary experimental results support the findings in the main paper. These include validations of embedding exchangeability on additional datasets and evaluation of retrieval performance under alternate metrics and supervision settings. Our goal is to assess whether the trends observed in the main experiments persist across diverse configurations.
H.1 ADDITIONAL. EXCHANGFABILITT RESULTS
The following experiments reuse the same setup as before: 5,000 GNNs are trained independently on subset of 1,024 query-corpus graph pairs, each with D 10 embedding dimensions, and trained for 20 epochs using a pairwise ranking loss. For a fixed node in one corpus graph, we collect the scalar embedding values across dimensions d E [D] from all models.
Covariance of Node embeddings Another consequence of exchangeability is the symmetry of higher order moments of the embedding. Specifically, we expect the covariance between two dimensions to remain constant across all pairs of dimensions, which is stronger demonstration of symmetry in the joint distribution.
0.20
0.06
0.15
0.04
0.10
0000
0.00
(a) cox2 (SM)
(b) cox2 (GED)
Figure 8: Sample covariance matrix for the ( [u, for the highlighted nodes in Figures 1,9. The
figure shows that the off- off-diagonal covariances are roughly, which strongly indicates that the coupling between dimensions symmetric.
Figure 8 shows the covariance matrices for two nodes from different graphs. The [i,j]h entry of each matrix matrix represents the estimate for (ov(X())) i]. (u,j). We observe that all the off diagonal elements are close to one another, and similarly, all diagonal elements too are close to one another, which indicates that there is symmetry in the coupling between dimensions.
Dousty 0.m8
Donily 0.76
Dumilty 0.75
9,50
0.50
a.50
0.25
025
e.
0.00
0.00
0.00
[
[ 4
X of
(a) Ge,
(b) Initialization
(c) Epoch 8
(d) Epoch 20
Figure 9: Empirical probability density of X [v, d] for the highlighted node in the example corpus graph G. in ptc-fr, obtained using 5,000 independently trained instances of the GNN model under GED-based supervision. Panels (b)-(d) show the density of X X [v, d] at initialization and at intermediate stages of training. The observed similarity of distributions across embedding dimensions reaffirms the exchangeability result (Theorem 5) in a different dataset and task setting.
Marginal distributions on a different dataset In Section 1. we validated the exchangeability of embedding dimensions by examining the marginal distributions of node embeddings across different
dimensions, under repeated training runs. Here, we present additional experiment dataset (PTC-FR) and a different supervision signal (GED with asymmetric costs), to confirm the generality of our claims. Figure shows the distribution of X ( (,, d] for three representative dimensions (d = 5, 10) at three points during training. Similar to the findings cox2(main paper), the distributions remain near-identical across dimensions and throughout training. This supports the robustness of Theorem 5, even under varied datasets and training objectives.
Remark. For the distribution plots of node embeddings (Figure and Figure 9), we use histograms with 25 bins and apply kernel density estimation for smoothing. These visualizations are generated using the built-in functionality of the seaborn library.
54

---

Published as a conference paper at ICLR 2026
H.2 FURTHER EVALUATION OF GRAPHHASH'S RETRIEVAL PERFORMANCE
In the main paper (Section 5.2), evaluated GRAPIHASI under two supervision signals-Subgraph Matching (SM) and asymmetric GED-using conservative MAP as the primary evaluation metric. Here, we extend that analysis along two axes.
First, we report additional results on more commonly used GED variant, where both insertion and deletion costs are set to eg eg 1. This equal-cost GED setting alters the notion of relevance and allows us to assess the generality of our approach under different supervision signal.
Second, we evaluate retrieval performance using NDCG, position position-sensitive ranking metric that complements MAP. These additional results evaluate whether the trends observed in the main paper persist under both metric and supervision signal variations.
H.2.1 MAP ON EQUAL-COST GED
In the main paper. we evaluated retrieval performance under asymmetric GED costs (eg 1, 1, = 2)). Here, we assess whether the key trends persist under the equal-cost variant where eg eg 1, widely used formulation in the literature.
Figure 10 shows the MAP vs. retrieved graphs trade-off curves for all baselines under equal-cost GED supervision. We summarize our observations below:
1. GRAPHHASH and FourierHashNet remain the strongest performers across all datasets. Even under equal-cost supervision, both methods consistently outperform other baselines MAP across retrieval budgets.
Hashier shows marginal improvement in this regime, particularly on ptc-fr, where it slightly surpasses GRAPUHASH, and on cox2 and ptc-mr, where its MAP approaches that of GRAPIHAAS at lower candidate counts. However, FourierHashNet often fails to span the full selectivity spectrum, unlike GRAPHHASH, which yields smoother and more complete accuracy-efficiency trade-off.
3. RH Hashing remains unstable. While it occasionally matches GRAPHHASH on cox2 and ptc-mr, its high variance limits its practical utility.
4. DiskANN, IVE, and Random sampling continue to underperform. As in the asymmetric setting, these methods yield substantially lower MAP, highlighting the advantage of trainable indexing strategies like GRAPHHASH and FourierHashNet.
These trends are consistent with our findings from the main paper and further validate the generality of GRAPHHASH across different supervision regimes.
GraphHash
FourieetHashNet
RH (Subsampled)
DisKANN
IVE
Random
0.8
be
0.8
0.8
[ 0.6
0.6
0.6
MAP
0.4
MAP
0.4
MAP
0.4
0.2
0 25K 50K 70K 100K # Retrieved Graphs -
0 25K 50K 75k 100K
25K 50k 75k 100K # Retrieved Graphs
0 25k 50k 70k 100K
# Retrieved Graphs
#
Retrieved Graphs
(a) ptc-fm (Eq. cost GED) (b) cox2 (Eq, cost GED) (c) ptc-trr fr (Eq, cost GED)d) ptc-mr (Eq, cost GED)
Figure 10: Trade-off between mean average precision (MAP) and number of retrieved graphs, for all the methods, viz., GRAPHHASH, FourierHashNet (Roy et al., 2023), Random Hyperplane (RH) (Charikar, 2002; Indyk et al., 1997), IVF (Douze al., 2024),DiskAN
(Simhadri al., 2023) and Random, across all datasets. Retrieval based on Equal cost GED (c. = 1). Horizontal red line denotes 50% of exhaustive MAP, Our method shows better trade-off than others in majority of the cases.
55

---

Published as a conference paper at ICLR 2026
GraphIlash
FourierIlashNet
(Subsanpled)
DiskANN
Random
0.5
0.5
0..
0.75
NDCG & 1K
0.6
NDOG 8 1K
0.6
NDCG 91K
0.06
NDCG 1KK
0.50
0.2
0.26
0.0
100K
25K
# Retrieved Graphs
#
Retrieved Graphs
Retrieved Graphs
Retrieved Graphs
(a) ptc-im fm (SM)
(b) cox2 (SM)
(c) ptc-fr fr (SM)
(d) ptc-mr (SM)
0.5
NDCG 8 IK
NDCG a IK
NDCG a IK
0.6
NDCG a IK
0.8
0.4
82
0.2
0.2
25K 5ok 79K 100K # Retrieved Graphs
20k s0k 79K 100K
25k 50K 7SK 100K Retrieved Graphs
26k 50K 75k 100K
# Retrieved Graphs
#
#
Retrieved Graphs
(c) pCc-fm (GED)
(f) cox2 (GED)
(g) ptc-fr fr (GED)
(h) ptc-mr (GED)
1.00
1.00
1.00
1.00
NDOG 11
0.75
0.75
NDOG n IK
0.75
0.50
0.50
0.50
NDOG
0.25
NDD
25K 30K 75k 100K
25K Rettrieeed Graphs
25K
100K
26K
# Retrieved Graphs -!
RRetrieved Graphs
RRetrieved Graphs
(i) ptc-fm (Eq. cost GRD) (j) cox2 (Eq. cost GRD) (k) ptc- fr (Eq. cost(l) ptc-mr (Eq. cost GFD)
GED)
Figure 11: Trade-off between NDCG top 1000 and number of retrieved graphs, for all the methods, viz., GRAPHHASH, FourierHashNet (Roy et al., 2023), Random Hyperplane (RH) (Charikar, 2002; Indyk et al., 1997), IVF (Douze al., DiskANDN (Simhadri et al., 2023) and Random, across all datasets. Top row: Retrieval based on Subgraph Matching (SM); Middle row: Retrieval based on GED; Bottom row: Retrieval based on Equal cost GED (e. 1). Our method shows better trade-off than others in majority of the cases.
H.2.2 EVALUATION USING NDCG
To complement our MAP-based evaluation, assess ranking quality using NDCG across all datasets and relevance definitions. Figure 11 reports results for Subgraph Matching, unequal-cox GED, and equal-cost GED.
1. GRAPHHASH consistently achieves the highest or near-highest NDCG across all datasets and relevance settings. This confirms that GRAPHHASH not only retrieves more relevant graphs overall, but also ranks them effectively near the top of the candidate list. Relative gains over baselines are smaller compared to MAP. While GRAPIHASSII leads in most cases, RH hashing performs competitively under unequal-cost GED, and nearly all baselines exhibit similar performance under equal-cost GED. This suggests that some methods manage to prioritize a few relevant graphs early, even if overall recall is limited.
DiskANN and IVF show competitive NDCG despite low MAP. These methods often retrieve a handful of highly relevant graphs early in the ranking, which boosts NDCG but fails to capture the full relevant set.
4. Random sampling yields flat and significantly lower NDCG. This reinforces the importance of structured indexing and learning- based methods for meaningful ranked retrieval.
Overall, NDCG results validate our MAP findings and demonstrate that GRAPHHASH excels not just retrieving relevant graphs but also ranking them effectively within large candidate pools.
56

---

Published as a conference paper at ICLR 2026
H.2.3 CLARIFICATION ON RH (SUBSAMPLED)
In Figure of the main paper and Figures 10 and 11 in the appendix, we display retrieval performance as seatter plots, as described in Section 5.2. The label "RH (Subsampled)" in these figures refers to subsampling of the full of trade-off points obtained for the Random Hyperplane (RH) method. This subsampling was performed solely to prevent visual clutter and improve readability of the main figures.
To ensure full transparency, Figures 12 and 13 present the complete set of RH performance points generated via a comprehensive hyperparameter sweep. Specifically, we vary the hash table size and the loss weights in Eq. (321), following the experimental protocol recommended in the FourierHash- Net (Roy et al., 2023). These figures show retrieval performance for all datasets across all three supervision signals (Subgraph Matching, GED, and Equal-cost GED), evaluated using both MAP and NDCG at top 1000.
We make the following observations:
1. Consistency with main trends: Even with the full set of hyperparameter configurations, the qualitative findings from the earlier results remain Cariistent-GAAPPHHH... both MAP and NDCG for Subgraph Matching (SM), and also on MAP for GED. RH achieves comparable performance only NDCG for GED, but remains less reliable overall.
outperforms RH on
Pronounced variability: With more points shown, the performance of RH appears highly scattered, especially fixed retrieval sizes. This reinforces its sensitivity hyperparameter selection.
Practical tuning challenge:
The high variance observed for RH across sweeps suggests that achieving consistently strong performance would require extensive tuning, which may not be practical real-world deployments.
57

---

Published as a conference paper at ICLR 2026
GraphHash
RH
0.4
0.4
MAP
MAP
MAP
0.
# Retrieved Graphi
Retzieved Graphs
Retzieved Graphi
Retrieved Graphs
(a) pt.- fm (SM)
(b) cox2 (SM)
pto-fr (SM)
(d) pt ptc-mr (SM)
0.3
0.8
MAP
0.0
0.0
23K 10K F&K, 100K # Retrieved Grapha
0 28 40k TSK 100K
0 30K 5OK F&K 100k
288 60K TaK 100k
#
Rotrieved Grapha
Retzieved Graphs
Retrieved Graphs
(e) poo-fm (GED)
( cox2 (GED)
(g) pto-fr (GED)
(h) ptc-mr (GED)
0.5
0.8
0.6
aus
0.0
0.4
MAP
0.0
0.0
5IK
Retrieved Graphs
Graphs
Retrleved Graphs
Retrieved Craphs
(i ptppc--es Im (Eq. cost GED) ( cox2 (Eq. cost GED) (k) pte--ix fx (Eq, cost GED)() pte-mr (Eq. cost GED)
Figure 12: Trade-off between MAP and number of retrieved graphs taking all points. Top row: Subgraph Matching (SM); Middle row: GED; Bottom row: Equal cost GED (c. 1). Horizontal red line denotes 50% of exhaustive MAP.
GraphHash
R.H
0.8
0.4
8.0
NDCG IK
sppco 9 1K
0.6
NDOG
0.4
NDCC
0.3
0.2
26K BOK 708 100K
0.0
20K BOR FOR 100K
25k 30K T6K 100K
25K 50K F5K 100K Retrieved Graphs
Reteieved Graphs
#
Retrieved Graphs
Retrieved Graphs
(4) ptc-ttt Em (SM)
(b) cox2 (SM)
(c) pre-Ir (SM)
(d) ptc-mr (SM)
NDOC 8 11
NDCG il ui n.B
swwees i IK
NDCG u
2-
0.2
25K 75k
25K
75K
75K
Retrieved Graphs
Graphs
Graphs
Retrieved Graphu
(6) ppp--mm Em (GED)
( cox2 (GED)
( pic-Ir (GED)
(h) pre-mz (GED)
0.073
0.44
8,069
XDCG a IK
DDOC in IK
NDCG
0.81
8.000
0.92
#i Reszleved
#
Retrieved Graphs
Retrieved Graphs
Retrieved Graphs
p-pc---mm (Eq. GED)
ccx2 (Eq. GED) pL) (Eq. cost GEDXD) pic-mr (Eq, cost GED)
Figure 13: Trade-off between NDCG at 1000 and number of retrieved graphs taking all points. Top row: Subgraph Matching (SM); Middle row: GED; Bottom row: Equal cost GED (c. =1).
58

---

Published as a conference paper at ICLR 2026
H.2.4 EVALUATION ON LARGER GRAPHS
We synthetically generate larger versions of cox2 and ptc-fr datasets for the Subgraph Matching task. The gold relevance labels are approximated as the set of graphs made up of relevant items of the original data. We generate 10t corpus items for either dataset, and plot the tradeoff curves as in Figure 4. We observe that GRAPHHASH performs better than the baselines in high accuracy regime
fr by combining graphs in the original
GraphHash
Hoshier
RH
DisKANN
IVF
0.4
0.3
0.3
0.2
MAP
0.2
MAP
0.1
0.1
2.5K
7.5K 10K
2.5K 7.5K 10K
# Retrieved Graphs
#
Retrieved Graphs
(a) cox2 (SM)
(b) ptc-fr (SM)
Figure 14: Trade-off between mean average precision (MAP) and number of retrieved graphs, for GRAPHHASH, FourierHashNet (Roy et al., 2023), Random Hyperplane (RH) (Charikar, 2002; Indyk al., 1997), IVF (Douze et al., 2024) and DiskANN (Simhadri al., 2023), across two datasets with synthetically generated large graphs under Subgraph Matching supervision.
H.2.5 EVALUATION ON LARGER CORPUS
In this set of experiments, we evaluate GRAPHHASH on a larger corpus of 1 1M items.
GraphHash
FouriecHasbbNet
RH
DisKANN
IVF
0.4
0.4
MAP
MAP
0.2
27
MAP
0.2
0.2
0.2
0
250K 500K 750K IM
250K 500K 750K IM
250K 500K 750K IM
0. 250K 500K 750K IM
# Retrieved Graphs
Retrieved Graphs
#
Retrieved Graphs
#
Retrieved Graphs
(a) cox2 (SM)
(b) ptc-fr (SM)
(c) fm (SM)
(d) ptc-mr (SM)
Pogge Parg
0.2
0.3
0.3
MAP
MAP
0.2
MAP
0.2
0.1
0.1
0.0
0.0
0.0
0.0
250K 500K 750K 1M Retrieved Graphs
250K 500K 750K 1M Retrieved Graphs
250K 500K 750K IM
250K 500K 750K 1M Retrieved Graphs
#
Retrieved Graphs
#
cox2 (GED)
(f) ptc-fr (GED)
(g) pm (GED)
(h) ptc-mr (GED)
Figure 15: Trade-off between mean average precision (MAP) and number of retrieved graphs, for GRAPHHASE NourierHashNet (Roy et al., 2023), Random Hyperplane (RH) (Charikar, 2002; Indyk
al., 1997), IVF (Douze al., 2024), and DiskANN (Simhadri et al., 2023) across all datasets for million sized corpus. Top row: Retrieval based on Subgraph Matching (SM); Bottom row: Retrieval based GED
59

---

Published as a conference paper at ICLR 2026
H.2.6 ABLATION STUDIES
Ablation dim, Here, present the trade-off curves for MAP versus number of retrieved graphs for each choice of dimp, the size the hashcode. The below tradeoff has been summarised to Figure 5 in the main paper. Owing the larger number of values of dimp, use colorscale for the scatterplot.
dim,
dim, dim,
dim, 15
dim, =20
dim,
dim, 1
dim, dim, 11
dim, 16
dim, - 25
dim, 50
dim, 2
dim, dim, dim, 17
dim, 30
dim, 55
dim,
dim,-
dim,
dim, 18
dim,
dim,
dim, 4
dim, 9
dim, 14
dim, 19
dim, - 40
0.4
0.4
0.4
MAP
MAP
MAP
MAP
0.2
0.0
0.0
0.0
0.0
25K 50K 75K 100K
25K 50K 100K
b0k 75K 100K
25K Gok 70K 100K
# Retrieved Graphs
Retrieved Graphs
# Retrieved Graphs
Retrieved Graphs
ptc- fm (SM)
(b) cox2 (SM)
(c) (e)ttc-t fr (SM)
(d) ptc-pim (SM)
0.4
0.4
0.2
0.3
0.5
MAP
0.2
MAP
0.2
MAP
0.2
0.1
0.1
0 25K 50K 75K 100K
0 25K 50K 75K 100K
25K 50K 75K 100K
0 25K 50K 75K 100K Retrieved Graphs
# Retrieved Graphs
#
Retrieved Graphs
# Retrieved Graphs
#
(c) p-c (GED)
(f) cox2 (GED)
(g) pto-fr (GED)
(h) ptc-mr (GED)
Figure 16: Trade-off between mean average precision (MAP) and number of retrieved graphs, for GRAPIHASHI for different values of the hashcode size dimm.
Ablation with D Here, we perform experiments ablating the embedding dimension of the netowrk. and the number of hash tables used.
0.6
0.50
MAP
MAP
0.45
0.4
0.40
0.35
0.3
2
5
10
15
20
30
2
15
20
30
D
(a) cox2 (SM)
(b) p (SM)
Figure 17:
The exhaustive MAP achieved by an embedding model trained on the node aligned loss with respect to the embedding dimension of the model.
We see that MAP increases monotonically with D, as is expected as the higher dimension allows for richer feature representation without hitting the bottleneck in training requirements.
Ablation with number of hash tables We also perform ablation over the number of hash tables.
Note that for ASA the number of hash tables corresponds to the number of dimensions of
60

---

Published as a conference paper at ICLR 2026
the embedding utilised, which implies monotone behavior in the performance. We seek to find if the accuracy losses are comparatively low, which could help cut time and memory.
0.4
0.4
MAP
MAP
0.2
GrophHashh sall
0.2
GrophHishh
Ttalk
Stilks
D -5
0.0
0.5
1.0
0.0
0.5
1.0
# Retrieved Graphsx
# Retrieved Graphsx 10
(a) cox2 (SM)
(b) ptc-fmt fm (SM)
Figure 18: Trade of plot showing MAP the number of retrieved corpus items for different variants of GRAPHHASH that uses different number of hash tables for retrieving results.
We observe that the drop in performance is not too significant from 10 although it is noticeable for 5. Ultimately, this vindicates our decision to use all 10 hash tables
Stability of random hyperplane seeding Next, evaluate the stability of the random hyperplane hashing scheme over multiple random seeds. In this setting, we set 10 different random seeds for the hyperplanes, keeping the embeddings and fourier maps fixed. We then evaluate the retrieval performance on the best hyperparameters found from GRAPHHASH.
We report the mean and standard devation in AUC over these 10 runs.
Dataset (Task)
Mean AUC
Std
pt fm (SM)
0.342685
0.006966
cox2 (SM)
0.369972
0.009179
ptc- fm (GED)
0.289546
0,007598
Cox2 (GED)
0.238293
0.005878
Table 19: Mean and standard deviation of AUC over 10 different random seeds for RH seeding.
We also plot the tradeoff curves for the different random seeds, contrasting their performance with the final version of GRAPHHASH. Each color denotes different seed.
0.4
0.4
MAP
MAP
0.2
0.2
GroplyHosh
GrophiHush
0.0
0.5
1.0
0.0
0.5
1.0
# Retrieved Graphsx
# Retrieved Graphsx 10*
(a) cox2 (SM)
(b) pt (SM)
0.3
MAP
MAP
0.1
GrsphHush
CraphHuuh
0.0
0.0
0.5
1.0
0.5
1.0
# Retrieved Graphsx 10a
# Retrieved Graphsx 10
(c) cox2 (GED)
(d) ptppp---a fm (GED)
Figure 20: Tradcoff curves comparing GRAPHHASH (red) with different random seeds for Random Hyperplane hashing across both tasks cox2 and ptc-fm. Each color denotes different seed.
61

---

Published as a conference paper at ICLR 2026
We observe that the variation in performance between different seeds is very minimal, as the different values coincide with the tradcoff trajectory of the best performing hyperparameters of GRAPHHASH. Stability of fourier map dimension dimy We also ablate the size of the fourier representation dimy. In our formulation, we have reparameterized dimy = 4nM, where n is the size of the graphs. In our experiment ablate over M.
0.24
0.38
0.36
0.22
AUC
0.34
AUC
0.20
0.32
0.30
0.18
0.28
2
8
9 10
2
4
6
8
9
10
M
M
(a) cox2 (SM)
(b) ccx2 (GED)
0.300
0.34
0.275
0.32
AUC
0.30
AUC
0,250
0.28
0.225
0.26
0.200
2
8 9 10
2
4
6
10
M
M
(c) ptc-fm f' (SM)
(d) ptc-fn (GED)
Figure 21: Comparison of AUC of the MAP retrieval ratio curve for different values of the per-dimension-fourrer frequencies M, across two datasets on both tasks.
We compare the AUC generated by the tradeoff curve generated for each value of M. We observe sharp decline in the performance when going down from 10 fourier frequencies per dimension.
62

---

Published as a conference paper at ICLR 2026
H.2.7 COMPARISON OF sim AND simd
Direct comparison of sim vs. simd We compare the quality of the approximation by plotting the scatter plots of the scores obtained by sim and sima for all the datasets and tasks. Specifically, we
sim scaled by D- For each Ge Gg pair in the test set, we compute these two values and plot them.
compare the mean ID score, i.e. Ei= sim? (6) against the
Areage, pm 2000 2
Anarege, - 400.000.. 2.704
Averago, om 0.251 2632
m
(a) cox2 (SM) fnstoas 1890
(b) ppc-frr fr (SM)
(c) ptc-cc-f fm (SM)
(d) ptc-mr (SM) Antrago, pat) /0
Anstion 2-3 (000
(e) cox2 (GED)
(1 ptc-fr (GED)
(g) ptc-fmm (GED)
(h) ptc-mr (GED)
Figure 22: Scatter plots comparing the mean ID similarity scores (y-axis) with the true similarity scores (x-axis) computed with sinkhorn iterations, for the (top) Subgraph Matching and (bottom) Graph Edit Distance task across different datasets.
Decay of [sima(Ge, Gg) - sim(Ge, Gg) with increasing D Next, we empirically validate the concentration result from Proposition by plotting the average absolute error |sima(Ge Gg). sim(G G₂) over all pairs (Ge: G,) in the test set as a function of D. We note that the deviation decreases with increasing D, confirming the result.
I. (C,, 0, Ga
2.5
2.0
1.5
1.0
10.55
2
10
15
2
10
30
D
D
(a) cox2 (SM)
(b) ptc-ff (SM)
Figure 23: Boxplot of average absolute error 1 Σ sima G₂) sim Gg) as function of D for the Subgraph Matching task on different datasets.
63

---

Published as a conference paper at ICLR 2026
H.2.8 EVALUATION OF LSH METHODS UNDER ALIGNED SCORING FUNCTIONS
To ensure fair comparison across LSH-based retrieval strategies, we evaluate each method using graph embeddings specifically trained to align with its intended scoring function. That is, while GRAPHHASH is evaluated under transport- supervision, FourierHashNet and Random Hy- perplane (RH) methods are applied on embeddings trained for hinge and cosine- based scoring, respectively.
transport-Based Scoring with GNN Embeddings. For GRAPHHASH, we use node-level embeddings produced by GNN encoder, trained using a pairwise ranking loss (Eq. (G.2)) based on the transport distance (G.,, Gg) (Eq. (1)).
GRAPHHASH:
For the baselines that require single-vector representation of graphs, we adopt the GEN architecture from (Li et al., 2019), which aggregates node embeddings into global graph-level vector via mean pooling.
FourierHashNet: Hinge Distance over Aggregated Graph Embeddings (GEN FourierHash- Net). FourierHashNett is designed for asymmetric hinge-baser based distances over global graph em- beddings. We apply it on GEN representations trained using the ranking loss in Eq. (G.2), where (el(Ge, Gg) Ia acll. and ag ag denote the pooled graph embeddings. Here, [+]+ is the
ReLU function.
RH: Cosine Similarity-Basee Hashing (GEN + RH). To align with RH's reliance on cosine simi- larity, we again use GEN-pooled embeddings and train them with the ranking loss in Eq. (G.2), setting rel(Ge, Ga) = - cos( (a, a.). This setup ensures that the learned representations are optimized for RH's basee locality -ennitiveee hashing.
Summary. Each method is thus benchmarked under conditions it was designed for: transport distance with GRAPHHASH, hinge distance with FourierHashNet, and cosine similarity with RH. This isolates the performance of the retrieval mechanism from mismatches in training objectives or input embeddings.
Observations. Figures 24 and 25 present retrieval performance across all datasets and supervision types. Figure 24 reports MAP trade-offs, while Figure 25 reports NDCG. We observe that:
1. Exhaustive scores reveal superiority of transport- based supervision. Across all datasets and similarity signals, GRAPHHASH consistently achieves higher exhaustive MAP and NDCG compared to both GEN + FourierHashNet and GEN + RH. This confirms that transport- based supervision captures a more powerful and fine-graing mne-graieed notion of graph relevance.
2. RH shows significantly reduced variance when used with compatible supervision. Unlike earlier results where RH was applied to transport-trainet embeddings and exhibited high variability (Figure 4), the GEN + RH setup shows much smoother and more stable trade-offs. This emphasizes the importance of matching the embedding training signal to the retrieval method.
Fourier benefits from hinge-compatible embeddings. When used with GEN-trained embeddings under hinge distance supervision, FourierHashNet exhibits broader coverage of the selectivity spectrum. yielding smoother MAP and NDCG trade-off curves. This again reinforces the value of scoring-function alignment between embedding training and LSH mechanism.
Despite improvements, GRAPHHASH retains overall dominance. Even though GEN-based variants show improved performance over their misaligned counterparts, they still fall short of GRAPHHASH in nearly all retrieval settings. This underscores the strength of the transport scoring model in both relevance estimation and downstream index quality.
64

---

Published as a conference paper at ICLR 2026
GASPHHASH
GEN + FOURIERHASHNET
GEN + RH
0.4
0.4
0.4
MAP -
MAP
MAP
0.2
0.2
0.0
0.0
0.0
25K 50K 70K 100K
0
25K 50K 73K 100K
23K bok 75K 100K
25K Gok 70K 10nk
# Retrieved Graphs
Retrieved Graphs
# Retrieved Graphs
# Retrieved Graphs
ptc- Fm (SM)
(b) cox2 (SM)
(c) pt (SM)
(d) ptc-mr (SM)
0.3
0.2
0.3
MAP
0.2
MAP
0.2
0.2
0.1
0.1
0.1
0.0
25K 75K
75K # Retrieved Graphs
25K 75K
# Retrieved Graphs
#
Retrieved Graphs
#
Retricved Graphs
(e) ppt-cmmm fm (GED)
(1) cox2 (GED)
(g) pto-fr (GED)
(h) ptc-mr (GED)
0.8
0.8
0.6
0.6
0.6
MAP
0.4
MAP P
0.4
P
0.4
MAP.
0.2
0.2
0.2
0.2
0.0
0.0
0.0
0.0
25K 50K 75K 100K
25K 50K 73k 100K
25K 50k 75K 100K
25K 50k 75K 100K
# Retrieved Graphs
Retrieved Graphs
Retrieved Graphs
#
Retrieved Graphs
(i) ptc-fm (Eq. cost GED) cox2 (Eq. cost GED) ptc-fr (Eq, cost GED)() pto-mr (Bq. cost GED)
Figure 24: Trade-off between mean average precision (MAP) and number of retrieved graphs, for all the methods, viz. GRAPHHASH, FourierHashNet (Roy al., 2023) using GEN embeddings, Random Hyperplane (RH) (Charikar, 2002; Indyk et al., 1997) using GEN embeddings, across all datasets. Top row: Retrieval based on Subgraph Matching (SM): Middle row: Retrieval based on GED; Bottom row: Retrieval based on Equal cost GED (c. 1). Horizontal red line denotes 50% of exhaustive MAP. Our method shows a better trade-off than others majority of the cases.
65

---

Published as a conference paper at ICLR 2026
GRAPHHASH
GEN + FOURIERHASHNET
GEN + RH
0.8
0.88
0.8
NDCG 81 11
NDCG 8 1K
0.6
0.6
NDCG a 1K
0.6
0.4
NDCG
0.4
0.4
0.4
0.2
25K S0K 70K 100K
25K 50K 73K 100K
25K bOK 75K 100K # Retrieved Graphs
25K Gok 70K 100k
# Retrieved Graphs
Retrieved Graphs
#
Retrieved Graphs
(a) ptc- fm (SM)
(b) cox2 (SM)
(e) fr (SM)
(d) ptc-mr (SM)
0.8
0.8
NDCG a 111
0.6
NDCG a iK
0.4
0.6
NDCG 111K
0.6
amai
NDCG
0.4
0.4
0.2
25K 50K 75K 100K # Retrieved Graphs
25K 50K 75K 100K
25K 50K 75K 100k
25K 50K 75K 100K Retrieved Graphs
Retrieved Graphs
# Retrieved Graphs
#
(c) fm (GED)
(f) COX2 (GED)
(g) ptc-fr (GED)
(h) ptc-mr (GED)
1,00
1.00
1,00
adka
NDCG a 1K
0.75
NDCG a 1K
0.75
0.75
0.75
0.50
0.50
NDCG
NDCG
0.25
0.00
25K 50K 75K 100k
0 25K 50K 75k 100K Retrieved Graphs
2GK G0K 76K 100K
25k G0K 75K 100k Retrieved Graphs
# Retrieved Graphs -
#
Rotrieved Graphs
#
(i) ptc-fm (Eq. cost GED) (i) cox2 (Eq. cost GED) (k) fir (Eq. cost GED)() pto-mr (Eq. cost GED)
Figure 25: Trade-off between NDCG at top 10000 and number of retrieved graphs, for all the methods, viz., GRAPHHASH, Faurier (Roy et al., 2023) using GEN embeddings, Random Hyperplane (RH) (Charikar, 2002: Indyk et al., 1997) using GEN embeddings, across all datasets. Top row: Retrieval based on Subgraph Matching (SM); Middle row: Retrieval based on GED; Bottom row: Retrieval based on Equal cost GED (c. 1). Our method shows a better trade-off than others in majority of the cases.
66


Reviews:
[{"review_id": "1pB9N9RcHx", "reviewer": "Reviewer_nx4Q", "summary": "The paper introduces a novel approach, GraphHash, addressing the graph retrieval problem. It demonstrates that the node embedding dimensions for a wide class of GNN methods are invariant under permutation operations applied along the dimension axis. This property is referred to as exchangeability, and the authors design a locality-sensitive hashing (LSH) framework by leveraging this property in order to efficiently approximate transportation-based graph similarities. The proposed method is supported by theoretical analysis and evaluated on four benchmark datasets for the graph retrieval task.", "questions": "- Does the method require a fixed number of nodes per graph? Since the hash function depends on sorting node embeddings, how is hashing handled if graphs undergo updates that change the embedding order?\n- What is the computational and space complexity of the proposed method? and how does it scale with graph size and embedding dimensionality compared to existing approaches?\n- Based on Proposition 7, how does varying $D$ influence the performance? Similarly, what is the impact of $dim_h$ and $dim_T$ for different values?\n- Since the hashing relies on random Fourier features and random hyperplanes, how stable is the performance across different seeds? Could the authors report variance for different runs?\n- Could the authors elaborate on how sensitive the exchangeability property is to violations of the assumptions, such as non-i.i.d. initialization?\n- It would be helpful to include the exact (non-approximate) transportation-based similarity in the comparison to better quantify the accuracy loss.\n- In Figure 2, it is difficult to distinguish the performances clearly due to overlapping points. It would be better to summarize retrieval performance using a single aggregate score, such as area under the curve or a related metric.\n\n**Additional comments:**\n- In Line 163, it could be nice to mention that $\\Psi$ and $ \\Theta$ indicate the weight matrices in order to avoid the confusion that $\\Psi$ is an input feature. \n- Line 1034, “invovled” -> involved", "limitations": "", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-structured and clearly presented, so the technical content is easy to follow.\n- It provides a rigorous theoretical analysis supporting the proposed framework and its underlying assumptions.\n- It includes an experimental evaluation demonstrating the effectiveness of the method across multiple datasets.", "weaknesses": "- The experimental evaluation is limited to relatively small benchmark datasets and lacks large-scale or real-world scenarios.\n- The paper focuses primarily on retrieval performance but does not examine the memory and computational requirements.", "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": "4YXCjQy2Xt", "reviewer": "Reviewer_3FEM", "summary": "The paper formalizes *embedding-dimension exchangeability* for GNNs under specific conditions (i.i.d. initialization, permutation-invariant loss, and equivariant optimization) and leverages this property to approximate high-dimensional transport-based graph similarity via per-dimension sorted one-dimensional matching.  \n\nThis leads to the **GraphHash** framework, which applies Fourier feature mapping and LSH for efficient graph retrieval.  \n\nExperiments on small TU-style molecular datasets (PTC-FM/FR/MR, COX2) show favorable accuracy–efficiency trade-offs compared with several baselines.", "questions": "1. **Zero-padding and simplification of the matching process**  \n   The current approach simplifies node alignment by zero-padding smaller graphs before per-dimension sorting and matching. Could the authors provide more discussion or ablation on this choice? It seems that this step simplifies the transport computation considerably, but it is unclear how much accuracy or theoretical rigor is sacrificed as a result. A deeper justification or empirical analysis would make the approach more convincing.\n\n2. **Extension to other downstream tasks**  \n   While the paper focuses on graph retrieval, the proposed transport-based similarity measure appears more general. Would it be possible to show at least one additional downstream task (e.g., k-NN classification, clustering, or graph alignment) to demonstrate broader applicability and potential beyond retrieval?\n\n3. **Dataset scale and comparison completeness**  \n   The current datasets (PTC-FR/FM/MR, COX2) are relatively small in both node count and embedding dimensionality. Could the authors evaluate the method on larger or more complex datasets to test its scalability? In addition, many strong contemporary baselines (e.g., IsoNet++, CORGII, SLoSH, SWWL) are missing. Including such comparisons would help non-specialist reviewers better assess the actual competitiveness and validity of the proposed approach.\n\n4. **Optional clarifications related to weaknesses**  \n   Some of the weaknesses mentioned (e.g., idealized assumptions, limited statistical validation of exchangeability) might be addressed by additional experiments or discussion. The authors may selectively respond to these points if relevant.\n\n---\n\n**General comment:**  \nIf the authors can convincingly address these concerns—especially providing more insight into the zero-padding mechanism, exploring at least one additional task, and extending experiments to larger or more challenging datasets—I would be happy to raise my score. A simple but effective idea, if rigorously justified, can indeed make for a strong and impactful contribution.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. **Novel theoretical formulation — Exchangeability of GNN embeddings.**  \n   The paper introduces the concept of *embedding-dimension exchangeability* in GNNs, showing that under mild assumptions, different embedding dimensions can be treated as exchangeable random variables.  \n   This extends classical symmetry analyses (e.g., permutation invariance) into the probabilistic domain and provides a new theoretical lens for understanding GNN representations.\n\n2. **Principled link between theory and computational efficiency.**  \n   Using the exchangeability property, the authors reduce the high-dimensional optimal transport (OT) distance to a sum of one-dimensional sorted distances.  \n   This theoretically justified simplification avoids solving full OT, achieving a significant computational reduction.\n\n3. **Unified and efficient retrieval framework.**  \n   The proposed **GraphHash** system combines this OT-based distance with locality-sensitive hashing (LSH), providing a unified, efficient, and theoretically grounded approach to graph retrieval.\n\n4. **Strong empirical performance.**  \n   On four TU benchmark datasets (PTC-FR/FM/MR, COX2), GraphHash consistently outperforms several strong baselines (FourierHashNet, DiskANN, IVF) in both *Subgraph Matching (SM)* and *Graph Edit Distance (GED)* tasks, achieving higher MAP and NDCG scores.\n\n5. **Good scalability and trade-off behavior.**  \n   The method achieves a favorable accuracy–efficiency balance, maintaining more than 50% of exhaustive MAP performance with much lower retrieval cost.\n\n6. **Reproducibility and clarity.**  \n   The theoretical derivations are detailed, and the authors provide code, data splits, and reproducibility documentation.", "weaknesses": "## **Weaknesses and Limitations**\n\n1. **Idealized theoretical assumptions.**  \n   The exchangeability theorem relies on assumptions rarely satisfied in modern GNNs. Components such as normalization layers (BatchNorm, LayerNorm), multi-head attention, temperature scaling, dropout, and adaptive optimizers can break permutation equivariance. The paper does not analyze which architectural choices preserve or violate exchangeability, limiting the generality of the theorem.\n\n2. **Zero-padding heuristic lacks theoretical justification.**  \n   When graphs have different node counts, the smaller graph is zero-padded before per-dimension sorting and matching. This can distort the node-value distribution and create spurious matches, especially for graphs with large node-count disparities. No theoretical bound or comparison with **Unbalanced/Partial OT** is provided, leaving the robustness of this approximation unclear.\n\n3. **Weak statistical validation of exchangeability.**  \n   The empirical evidence mainly consists of qualitative plots. There are no formal statistical tests (e.g., KS, MMD, or energy distance) or analyses of inter-dimensional dependence (correlation, mutual information). It remains unclear whether dimensions are merely identically distributed or also weakly independent—an important distinction for the proposed matching approach.\n\n4. **Limited task scope despite a broadly applicable distance.**  \n   While related works also focus on retrieval, the proposed transport-based distance could naturally extend to other tasks (e.g., k-NN classification, clustering, or graph alignment). Evaluating at least one additional downstream task would strengthen claims of broader applicability.\n\n5. **Missing comparisons with the strongest recent methods.**  \n   The experiments lack comparisons with several contemporary state-of-the-art systems, such as **IsoNet++**, **CORGII**, and recent **sliced-Wasserstein/set-hashing** approaches like **SLoSH** and **SWWL**. Without these baselines, it is difficult to assess how GraphHash performs relative to the current best.\n\n6. **Small embedding dimensionality in the chosen datasets.**  \n   All experiments use low-dimensional (≈10D) node embeddings on small molecular graphs. The exchangeability assumption and 1D matching approximation may not hold as well in higher-dimensional spaces where inter-dimensional dependencies are richer. A sensitivity analysis with respect to embedding dimensionality would help assess generality.", "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": "BLK00lpoLS", "reviewer": "Reviewer_knCv", "summary": "The paper introduces and proves a probabilistic symmetry in trained GNN node embeddings: under standard i.i.d. layer-wise initializations and across a broad class of architectures, the embedding dimensions behave as exchangeable random variables. Experiments validate this claim by showing near-identical per-dimension marginals across massive independently trained models. Leveraging this insight, the authors propose new graph retrieval methods based on order-statistic features, achieving competitive performance compared to prior work.", "questions": "How do retrieval quality and the Proposition-7 approximation error scale with $D$? Can you report MAP vs $D$ and discuss the smallest $D$ where the 1-D surrogate is reliable?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper introduces an interesting perspective for understanding GNN representations and proposes a series of sensible applications that leverage this new finding.\n- The reduction from permutation-equivariant training dynamics to exchangeability of embeddings is clear and broadly applicable under the paper’s assumptions.\n-  The transition from transport similarity to Fourier features and ultimately to random-hyperplane LSH is elegant and well-justified, making the paper logically coherent throughout.\n- Training with many random seeds and demonstrating that per-dimension marginals remain stable provides direct and compelling empirical support for the theoretical claim.", "weaknesses": "- The guarantees rely on permutation-invariant losses. Common heads (e.g., linear classifiers, feature-wise norms) can break this unless parameters are aligned under permutations; the practical scope should be specified more sharply.\n\n- While the embedding dimensions are exchangeable, this does not imply independence—identical marginals do not preclude cross-coordinate dependencies. The proposed 1-D order-statistic surrogate could ignore the joint structure of the embeddings. Without quantifying inter-dimensional dependence (e.g., via covariance or effective rank) or demonstrating robustness to such dependencies, it remains unclear when this 1-D compression faithfully preserves information critical for retrieval.", "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": "U2mU9y5kE1", "reviewer": "Reviewer_UMLi", "summary": "This paper claims to uncover an exchangeability property in GNN embeddings, suggesting that node embedding dimensions are probabilistically symmetric and invariant under permutation. Based on this assumption, the authors approximate transportation-based graph similarities using Euclidean distances between order statistics and build a unified LSH framework supporting multiple graph similarity measures. While the idea is conceptually interesting, the theoretical justification and empirical validation of the claimed exchangeability remain questionable and insufficiently supported.", "questions": "- The introduction states that “the expected embedding matrix $\\mathbb{E}[[x(u)]_{u\\in V}]$ collapses to a rank-one matrix.” However, no empirical evidence (e.g., covariance analysis or SVD spectrum visualization) is provided to substantiate this claim.\n- Real-world graphs typically vary in size. How does the proposed GraphHash framework handle graphs with different numbers of nodes, especially when a query graph contains more nodes than any graph seen during training?\n- Do the padding nodes used to equalize graph sizes introduce additional noise or bias that may negatively affect retrieval performance?\n- The conditions described in Sec. 3.1 for achieving exchangeability seem too strong. Many standard graph learning losses are not permutation invariant, and the optimizer’s equivariance depends critically on this property of the loss function.\n- More SOTA works regarding graph match should be included, such as GNN-PE[1], IsoNet++[2]\n- No hyperparameter sensitivity analysis.\n\n\n- The proposed experiment for validating the exchangeability of embedding dimensions is conceptually flawed and cannot support the stated claim. The authors attempt to verify exchangeability by checking whether the marginal distributions of embedding elements are identical. However, this approach only measures the stability or randomness of parameter initialization and model convergence, not the permutation invariance or exchangeability of embedding dimensions within a single trained model.\nIn particular:\n\t- Exchangeability concerns the joint distribution of embedding dimensions within a model, not the marginal consistency of embeddings across independently trained models.\n\t- The observed similarity (or dissimilarity) of marginal distributions across models provides no evidence for or against permutation invariance in the learned representation space.\n\t- The experiment conflates stochastic training variation with structural symmetry in the embedding space.\n\t- No statistical test is performed on the joint dependency structure between embedding dimensions, which is essential for verifying exchangeability.\n\n\n[1] Ye Y, Lian X, Chen M. Efficient exact subgraph matching via gnn-based path dominance embedding[J]. Proceedings of the VLDB Endowment, 2024, 17(7): 1628-1641.\n\n[2] Ramachandran A, Raj V, Roy I, et al. Iteratively refined early interaction alignment for subgraph matching based graph retrieval[J]. Advances in Neural Information Processing Systems, 2024, 37: 77593-77629.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- The writing is good.\n- The quite novel angle is graph matching area.\n- The performance is superior.", "weaknesses": "- The assumptions required to achieve exchangeability are overly restrictive and may not hold in realistic training scenarios.\n- The experimental validation of exchangeability is weak.\n- The choice of baselines is limited.", "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 (Oral)