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
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
Figure 1: Worked computation of the MGP diagram. Vertices are born according to the structure-aware edge filtration, and their embeddings are updated by message passing on each filtration subgraph. Zero-dimensional tuples record birth, death, and the corresponding death-step embedding, while cycle-creating edges contribute one-dimensional tuples. In this example, we use the order gray<red<orange on the terminal embeddings.
Figure 2: A monochromatic four-vertex star G and path H . They are indistinguishable by every element of DRePHINE , whereas every element of DMGP distinguishes them.
MUTAG
PTC_MR
PROTEINS
NCI109
NCI1
ZINC
GNN
73.68 ± 12.34
56.00 ± 2.56
72.86 ± 1.20
79.90 ± 2.03
75.47 ± 3.33
0.162 ± 0.006
PH
91.58 ± 2.88
59.43 ± 4.69
70.36 ± 1.32
78.69 ± 1.67
77.23 ± 2.88
0.160 ± 0.021
RePHINE
86.32 ± 2.88
60.00 ± 7.28
70.71 ± 2.22
77.68 ± 1.97
81.75 ± 3.09
0.142 ± 0.013
SpectRe
89.47 ± 3.72
57.71 ± 2.39
70.71 ± 2.48
79.61 ± 2.55
79.51 ± 1.87
0.157 ± 0.018
MGP
88.42 ± 7.81
61.71 ± 5.19
73.04 ± 3.91
82.23 ± 1.66
81.36 ± 0.47
0.110 ± 0.011
Table 1: Test accuracy (%) on five TU datasets and mean absolute error on ZINC (lower is better) at the epoch of best validation score, mean ± std over five seeds. All methods share the backbone of each dataset; best mean per column in bold.
Deg.
Betw.
Clos.
PR
PHV
0.03
0.49
0.21
0.04
PHE
0.41
0.41
0.41
0.41
RePHINE
0.41
0.52
0.50
0.41
MGP
0.41
0.53
0.49
0.41
Table 2: Total accuracy on BREC under the reliability check, by vertex filtration function: degree, betweenness, closeness and PageRank (PR). MGP: mean over three seeds.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
Graphs of
Graphs
nˉ
eˉ
Task
Majority
MUTAG
nitro compounds, mutagenicity
188
17.93
19.79
2 classes
0.6649
PTC_MR
compounds, carcinogenicity (male rats)
344
14.29
14.69
2 classes
0.5581
PROTEINS
proteins, enzyme or not
1,113
39.06
72.82
2 classes
0.5957
NCI1
compounds, lung-cancer screen
4,110
29.87
32.30
2 classes
0.5005
NCI109
compounds, ovarian-cancer screen
4,127
29.68
32.13
2 classes
0.5038
ZINC (12k)
molecules, constrained solubility
12,000
23.2
24.9
regression, MAE
–
Appendix
Table 3: Datasets: number of graphs, mean numbers of vertices and undirected edges, task and majority-class rate (classification). Graphs without node features receive one-hot encoded degrees.
Dataset
Backbone
MGP
F
k
MUTAG
5 layers, 256, JK
GINE- ε , R=3
16
64
PTC_MR
5 layers, 256, JK
GINE- ε , R=3
16
64
PROTEINS
5 layers, 128, JK, RWSE
GatedGCN + attention
8
64
NCI109
5 layers, 256, RWSE
GINE- ε , R=2
16
32
NCI1
3 layers, 256, JK
GatedGCN + attention, R=2
8
32
ZINC
3 layers, 128, JK, RWSE
GatedGCN
16
128
Appendix
Table 4: Selected configurations for Table 1 . Backbone (all methods): GINE layers, width, jumping knowledge (JK), RWSE. MGP: aggregation (Appendix E ), rounds per step R , F and k ; T=4 and T=16 run in parallel.
Filtration
Diagram
CFI
Regular
Extension
Basic
Total
Degree
PHV
0.03
0.00
0.07
0.03
0.03
PHE
0.03
0.34
0.55
0.98
0.41
RePHINE
0.03
0.34
0.55
0.98
0.41
MGP
0.03
0.34
0.54
0.98
0.41
Betweenness
PHV
0.10
0.34
0.82
0.95
0.49
PHE
0.03
0.34
0.55
0.98
0.41
Appendix
Table 5: Accuracy on the BREC categories by vertex filtration function and diagram type, under the reliability check. Regular: all 140 regular pairs; every distinguished one is simple regular (strongly, 4-vertex condition and distance regular: 0.00 for all). MGP: mean over three seeds.
Persistent homology (PH) encodes global information, such as cycles, and is thus increasingly integrated into graph neural networks (GNNs). PH methods in GNNs typically traverse an increasing sequence of subgraphs. In this work, we first expose limitations of this inclusion procedure. To remedy these shortcomings, we analyze contractions as a principled topological operation, in particular, for graph representation learning. We study the persistence of contraction sequences, which we call Contraction Homology (CH). We establish that forward PH and CH differ in expressivity. We then introduce Hourglass Persistence, a class of topological descriptors that interleave a sequence of inclusions and contractions to boost expressivity, learnability, and stability. We also study related families parametrized by two paradigms. We also discuss how our framework extends to simplicial and cellular networks. We further design efficient algorithms that are pluggable into end-to-end differentiable GNN pipelines, enabling consistent empirical improvements over many PH methods across standard real-world graph datasets. Code is available at this https URL.
Mattie Ji, Indradyumna Roy, Vikas Garg
University of Pennsylvania · Aalto University · Indian Institute of Technology Bombay +1
We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2 iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous studies state that sum-aggregation MP-GNNs match full CR however they consider a weak, 'non-uniform', notion of distinguishing-power where each graph size may require a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.
Message-passing Graph Neural Networks (GNNs) iteratively propagate and aggregate local neighborhood information followed by global readout to learn graph representations. However, their discriminative power is upper-bounded by the Weisfeiler--Lehman (1-WL) graph isomorphism test. This prevents GNNs from distinguishing certain non-isomorphic graphs with identical local neighborhood structures, often leading to similar graph representations. Unified Topological Signatures (UTS) capture compact, multi-scale representation of global graph topology derived from persistent homology. We introduce two complementary UTS signatures: Graph_UTS- a static signature of the input graph topology, and Embedding_UTS- a dynamic signature of the evolving embedding topology. They encode structural information inaccessible to 1-WL-based message-passing GNNs, yet their capabilities are explored solely for post-hoc embedding-space analysis. We integrate UTS into GNN training across three architectural interventions: (i) UTS-Aug: augmenting with standard readout feature that encodes graph's true topology; (ii) UTS-Reg: topological regularizer that constrains representation collapse; (iii) UTS-Pool: topology-guided pooling that retains structurally critical nodes. We further leverage UTS as a layer-wise diagnostic to quantify oversmoothing during GNN training. Theoretically, we show that integrating UTS into GNN optimization strictly extends GNN expressivity beyond the 1-WL hierarchy. Experiments on three graph classification benchmarks show consistent benefits: Graph-UTS, Dual-UTS, and UTS-Pool improve accuracy across all three datasets, Embedding-UTS provides smaller but similarly consistent gains, and UTS-Reg's benefit varies across graph domains. Accuracy improves by up to 5.8% with Graph-UTS augmentation, by up to 1.9% with UTS-Reg, and achieves comparable performance to TOGL with UTS-Pool.