Message-passing graph persistence
Abstract
Message-passing graph neural networks (GNNs) are limited in expressive power by the one-dimensional Weisfeiler-Leman test. Persistent homology (PH) provides topological descriptors that can complement GNN representations, but existing approaches typically compute persistence separately from the representation learning process. In this paper, we introduce Message-Passing Graph Persistence (MGP), a family of topological descriptors that incorporates message passing into graph filtrations. At each filtration step, node embeddings are updated using the current subgraph and associated with persistence events. These embeddings also determine the representatives of connected components during persistence computation. We prove that MGP is invariant under graph isomorphism and that it is strictly more expressive than the PH-based descriptors it extends. We evaluate MGP on an expressivity benchmark and on several graph classification and regression datasets. Experiments show that MGP outperforms other PH-based descriptors on most of these datasets.
Related
- Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
- Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks
- From Mixing to Tearing: Graph Decomposition in Decentralized Optimization via Message Passing
- Geometry-Aware Simplicial Message Passing
- Learned Score-Based Turbo Message Passing for Channel Recovery From Spatially Compressed Measurements
BibTeX
@misc{franco2026messagepassing,
title = {{Message-passing graph persistence}},
author = {Jorge Luiz Franco and Arthur Queiroz Moura and Moacir Ponti and Amauri Souza},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06801},
eprint = {2611.06801},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06801},
}
RIS
TY - UNPB
TI - Message-passing graph persistence
AU - Jorge Luiz Franco
AU - Arthur Queiroz Moura
AU - Moacir Ponti
AU - Amauri Souza
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06801
UR - https://arxiv.org/abs/2611.06801
AB - Message-passing graph neural networks (GNNs) are limited in expressive power by the one-dimensional Weisfeiler-Leman test. Persistent homology (PH) provides topological descriptors that can complement GNN representations, but existing approaches typically compute persistence separately from the representation learning process. In this paper, we introduce Message-Passing Graph Persistence (MGP), a family of topological descriptors that incorporates message passing into graph filtrations. At each filtration step, node embeddings are updated using the current subgraph and associated with persistence events. These embeddings also determine the representatives of connected components during persistence computation. We prove that MGP is invariant under graph isomorphism and that it is strictly more expressive than the PH-based descriptors it extends. We evaluate MGP on an expressivity benchmark and on several graph classification and regression datasets. Experiments show that MGP outperforms other PH-based descriptors on most of these datasets.
ER -