Exchangeability of GNN Representations with Applications to Graph Retrieval
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.
Cite
Text
Nair et al. "Exchangeability of GNN Representations with Applications to Graph Retrieval." International Conference on Learning Representations, 2026.Markdown
[Nair et al. "Exchangeability of GNN Representations with Applications to Graph Retrieval." International Conference on Learning Representations, 2026.](https://mlanthology.org/iclr/2026/nair2026iclr-exchangeability/)BibTeX
@inproceedings{nair2026iclr-exchangeability,
title = {{Exchangeability of GNN Representations with Applications to Graph Retrieval}},
author = {Nair, Kartik and Roy, Indradyumna and Chakrabarti, Soumen and Dasgupta, Anirban and De, Abir},
booktitle = {International Conference on Learning Representations},
year = {2026},
url = {https://mlanthology.org/iclr/2026/nair2026iclr-exchangeability/}
}