OpenNovelty.org

Exchangeability of GNN Representations with Applications to Graph Retrieval

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 6.0Download Report PDF
GNNLocality sensitive hashing
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.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Taxonomy

Core-task Taxonomy Papers
8
3
Claimed Contributions
30
Contribution Candidate Papers Compared
1
Refutable Paper

Research Landscape Overview

Core task: Locality-sensitive hashing for graph retrieval using transportation-based similarity measures. The field structure reflects a convergence of optimal transport theory, graph neural networks, and scalable retrieval systems. The taxonomy organizes work into four main branches: Optimal Transport Approximation Methods focus on efficient computation of Wasserstein and related distances, often trading exactness for speed (e.g., Scalable optimal transport in[3], Warpspeed Computation of Optimal[8]); Graph Neural Network Architectures with Transport-Based Distances explore how to embed graphs in ways that respect or approximate transport metrics; Neural Graph Retrieval Systems address end-to-end pipelines for indexing and querying large graph databases (e.g., Scalable Neural Graph Retrieval[6], Scalable and Multi-modal Neural[7]); and Domain-Specific Applications of Transport-Based Retrieval demonstrate these techniques in areas like molecular search or shape matching (e.g., Fast contour matching using[4]). Together, these branches illustrate a progression from foundational distance computation to learned representations and practical retrieval architectures. A particularly active theme concerns the interplay between approximation quality and computational scalability: many studies seek hashing schemes or neural embeddings that preserve transport-based distances while enabling sublinear query times. Within this landscape, Exchangeability of GNN Representations[0] sits squarely in the Graph Neural Network Architectures branch, emphasizing the theoretical property of exchangeability to ensure that learned node or graph embeddings remain compatible with locality-sensitive hashing under permutation-invariant transport metrics. This contrasts with works like SLoSH[1] or HIGH-PERFORMANCE SEMANTIC SIMILARITY ANALYSIS[2], which may prioritize empirical speedups or domain-specific tuning over formal invariance guarantees. Meanwhile, Template based Graph Neural[5] explores structured message-passing that could complement exchangeable representations. The central tension across these lines is whether to rely on hand-crafted transport approximations, end-to-end learned hashing, or hybrid approaches that blend neural architectures with classical LSH theory.

Claimed Contributions

Exchangeability of GNN node embeddings

The authors establish that node embeddings produced by trained GNNs exhibit exchangeability across embedding dimensions, meaning the joint probability density of embedding elements remains invariant under permutations of the dimension axis. This property holds for a broad class of GNN architectures, loss functions, and optimizers.

10 retrieved papers
Approximation of transportation-based graph similarity using Euclidean similarity

The authors leverage exchangeability to approximate computationally expensive transportation-based graph similarities with simpler Euclidean similarities computed over sorted embedding elements in individual dimensions, reducing complexity from O(n³) to dimension-wise operations.

10 retrieved papers
Unified locality-sensitive hashing framework for graph retrieval

The authors develop GRAPH HASH, a unified LSH framework that supports multiple asymmetric graph relevance measures including subgraph matching and graph edit distance by combining their exchangeability-based approximation with Fourier-based hashing techniques.

10 retrieved papers
Can Refute

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Within the taxonomy built over the current TopK core-task papers, the original paper is assigned to a leaf with no direct siblings and no cousin branches under the same grandparent topic. In this retrieved landscape, it appears structurally isolated, which is one partial signal of novelty, but still constrained by search coverage and taxonomy granularity.

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

Exchangeability of GNN node embeddings

The authors establish that node embeddings produced by trained GNNs exhibit exchangeability across embedding dimensions, meaning the joint probability density of embedding elements remains invariant under permutations of the dimension axis. This property holds for a broad class of GNN architectures, loss functions, and optimizers.

Contribution

Approximation of transportation-based graph similarity using Euclidean similarity

The authors leverage exchangeability to approximate computationally expensive transportation-based graph similarities with simpler Euclidean similarities computed over sorted embedding elements in individual dimensions, reducing complexity from O(n³) to dimension-wise operations.

Contribution

Unified locality-sensitive hashing framework for graph retrieval

The authors develop GRAPH HASH, a unified LSH framework that supports multiple asymmetric graph relevance measures including subgraph matching and graph edit distance by combining their exchangeability-based approximation with Fourier-based hashing techniques.

Table of Contents