cs.LGNov 4, 2026

Message-passing graph persistence

Authors: Jorge Luiz Franco, Arthur Queiroz Moura, Moacir Ponti, Amauri Souza

Organizations: Institute of Mathematics and Computer Sciences (ICMC), University of S˜ao Paulo, S˜ao Carlos, Brazil · Avra · Mercado Libre · Federal Institute of Cear´a (IFCE), Fortaleza, Brazil

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.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Contraction and Hourglass Persistence for Learning on Graphs, Simplices, and Cells

    Apr 19, 2026Mattie Ji, Indradyumna Roy, Vikas GargGraph Neural NetworksGraph Representation Learning

  2. Repurposing Unified Topological Signatures for Graph Representation Learning

    Sep 15, 2026Sanyam Sanjay Jain, Anshika Krishnatray, Aditya Sharma +1Graph Representation LearningGNN Expressivity