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.