Graph Representation via Elements of Discrete Morse and Cobordism Theories
Authors: Jennifer Rozenblit, Chenguang Yang, Yuxin Liu, Yuzhou Chen, Yulia Gel
Organizations: Department of Mathematics; University of Texas, Austin · Department of Statistics; University of California, Riverside · Department of Statistics; Virginia Tech
Topology is, by its nature and design, suited to structure that is nonlinear, multiscale, and nonstationary - however, within machine learning, its use remains largely confined to topological data analysis. We advocate that tools from low-dimensional topology which have remained almost exclusively contained within the domain of pure mathematics (such as Morse theory) offer a strong, complementary, and yet virtually unexplored perspective on the hidden structure of data-generating processes and learning tasks built upon them. Here we introduce concepts from cobordism theory and harness tools from discrete Morse theory to improve the performance of graph diffusion models through our pipeline MG-Diff. Further, we derive theoretical guarantees and sufficient conditions so that under a positive decision-gap, the Morse-theoretic tools and their application for induced diffusion guidance are stable under small perturbations. Finally, we illustrate the utility of discrete Morse theory in application to graph diffusion models for spatio-temporal graph forecasting and graph regeneration, and argue that these applications are only a small window into the part of what low-dimensional topology can offer to the field of machine learning.
Figures & tables
Figure 1
Figure 2 : MG-Diff (left) vs. higher-order guided diffusion (right). MG-Diff identifies critical cells (red), computes descending manifolds (dotted), and perturbs outside these regions (blue). Higher-order diffusion preserves only 2-cell boundaries (teal triangles), missing critical 1-cells that govern topological connectivity.
Method
Data
PEMS-03
PEMS-BAY
AIR-BJ
AIR-GZ
Metric
MAE
RMSE
CRPS
MAE
RMSE
CRPS
MAE
RMSE
CRPS
MAE
RMSE
CRPS
TimeGrad
21.55
36.57
0.101
2.62
5.30
0.034
33.40
54.93
0.363
15.45
21.93
0.376
MC Dropout
18.87
29.81
0.093
3.50
5.43
0.040
37.92
55.49
0.391
13.10
19.26
0.290
CSDI
23.46
39.60
0.098
2.67
4.10
0.031
38.94
57.81
0.417
14.78
22.24
0.361
DiffSTG
17.58
28.75
0.095
2.03
4.22
0.025
38.03
56.87
0.373
13.06
18.25
0.319
PriSTI
22.30
37.58
0.092
2.51
3.99
0.026
36.81
54.34
0.388
14.04
21.03
0.352
Table 1 : Prediction comparison over spatio-temporal graphs based on PEMS-03 [ 13 ] , PEMS-BAY [ 42 ] , AIR-BJ [ 75 ] , and AIR-GZ [ 75 ] .
Method
Degree ↓
Clus. ↓
GDSS
0.0373
0.0723
DiGress
0.0899
0.1920
GraphVAE-MM
0.0587
0.3560
HOG-Diff
0.4700
0.3650
CoPHo
0.0523
0.0911
SwinGNN
0.00366
0.0862
Table 2 : Graph generation performance on community-small data in MMD along with the average Wasserstein distance W2 and mean absolute error in Betti β0 and β1 numbers between the observed and generated graphs.
Appendix figures & tables20 assets
Supplementary material from the paper’s appendix.
Appendix
Symbol
Meaning
Graphs and complexes
G=(V,E,X)
Simple graph: vertices V , edges E , node features X
N=∣V∣,M=∣E∣
Number of vertices and edges
deg(v)
Degree of vertex v ; degmax=maxu∈Vdeg(u)
Λ
Finite simplicial / regular CW complex
Cl(G)
Clique complex of G (simplices = cliques of G )
Appendix
Table 3 : Table of Notations
Method
Topological signal
DMT
Persistence
Domain
Task
TAGG [ 53 ]
PH (diagram-matching loss, βi attention)
No
full
abstract graph
graph generation (diffusion)
TopoDiffusionNet [ 26 ]
PH (Betti number)
No
full
image/cubical
image generation (diffusion)
Prob. Topo. Rep. [ 34 ]
DMT+PH
Yes
prunes Morse complex
image likelihood field
segmentation (reconstruction)
Dey–Wang–Wang [ 19 ]
DMT+PH
Yes
prunes Morse complex
density field ρ
graph/curve reconstruction
TOGL [ 31 ]
PH (learned filtration)
No
full
abstract graph
classification
PDGNN [ 73 ]
PH (EPD surrogate)
No
full
abstract graph
classification
Appendix
Table 4 : Positioning of MG-Diff among topology-aware diffusion and discrete-Morse (DMT) methods in ML.
Figure 3 : Side-by-side comparison of the Morse-guided graph evolution (left) and the corresponding human motion phases (right).
Figure 4 : The torus viewed as a cobordism between two empty sets. The green marks indicate the gradient flow lines that constitute the connections between critical points along the gradient vector field.
Figure 5 : Example graph with two 4-cycles connected by a bridge. Top: the input graph. Middle: critical cells in red. Bottom: descending paths in green, flowing from critical edges to the critical vertex.
Edge e
f(e)
Pairing (v,e)∈V
(4,5)
0.078
(4,(4,5))
(2,4)
0.222
(2,(2,4))
(1,2)
0.421
(1,(1,2))
(5,6)
0.554
(6,(5,6))
(4,7)
0.756
(7,(4,7))
(0,1)
0.831
(0,(0,1))
Appendix
Table 5 : Vertex–edge pairings in the discrete gradient vector field. Each paired edge e is matched with its higher-valued endpoint. Unpaired cells are critical.
Figure 6 : Same persistence, different gradient routing. Both panels show the same filtered hexagon-fan complex with identical H1 persistence [1,2) . The critical 2-cell Δ0=(c,0,1) (darkly shaded) is identical in both matchings. However, V-path reachability differs: in V1 , gradient paths reach Δ0 counterclockwise (support excludes s5 ); in V2 , clockwise (support excludes s2 ). This directed incidence information-invisible to persistence-determines which edges are downstream of a cycle-filling event in topology-guided generation.
Figure 7 : A filtration on Λ : the path graph enters in stages, with the final edge e12 merging two components at time t=3 .
Figure 8 : Two distinct gradient vector fields V1 (left) and V2 (right) on the path graph.
Figure 9 : A filtration on the star graph T : three leaves appear at t=0 , the center and one edge at t=1 , and two more edges simultaneously at t=2 .
Dataset
# Node
# Time Step
Granularity
Attribute
PEMS-03
358
26,208
5 min
Flow
PEMS-BAY
325
52,116
5 min
Speed
AIR-BJ
36
8,760
1 hour
PM2.5
AIR-GZ
42
8,760
1 hour
PM2.5
Appendix
Table 6 : Summary statistics of the datasets.
Architecture
MAE
CRPS
PEMS-03
AIR-BJ
PEMS-03
AIR-BJ
MG-Diff
15.67
29.91
0.077
0.290
MG-Diff W/o MoMoE
16.20
30.22
0.082
0.348
MG-Diff W/o MDDN
16.56
30.83
0.234
0.534
Appendix
Table 7 : Ablation studies on MG-Diff variants.
Method
PEMS-03
AIR-BJ
MG-Diff
15.67
29.91
MG-Diff w. deg.
16.20
30.22
MG-Diff w. bet.
16.56
30.83
Appendix
Table 8 : Ablation studies with different Morse function values on PEMS-03 and AIR-BJ.
Method
Clean AIR-GZ
Noisy AIR-GZ
MAE
RMSE
MAE
RMSE
USTD
9.99
15.41
10.72
15.71
MG-Diff (Ours)
9.80
15.07
10.25
15.26
Appendix
Table 9 : Robustness analysis (noise ratio =5% ) on AIR-GZ.
PEMS-03
PEMS-BAY
AIR-BJ
AIR-GZ
MG-Diff
136
67.5
1
1
Appendix
Table 10 : Running time in seconds (s) (average per epoch).
Conditioning skeleton
MAE
RMSE
MAPE
CRPS
Random skeleton (matched size)
10.19767 ± 0.00002
15.46738 ± 0.00003
0.41979 ± 0.00000
0.25223 ± 0.00105
Morse, g(v)=deg(v)+εv
9.72684 ± 0.00000
15.20191 ± 0.00003
0.38107 ± 0.00000
0.23853 ± 0.00084
Morse, g(v)=degmed+deg(v)+εv
10.44039 ± 0.00004
15.30176 ± 0.00003
0.46580 ± 0.00000
0.24502 ± 0.00112
Morse, g(v)=degmax−deg(v)+εv (Ours)
9.58643 ± 0.00001
14.92188 ± 0.00002
0.38942 ± 0.00000
0.23099 ± 0.00108
Appendix
Table 11 : Isolating the Morse skeleton on AIR-GZ (mean ± std over 5 seeds): a random skeleton of matched size vs. Morse skeletons under different vertex scoring rules g , with identical architecture, training configuration, and checkpoint.
Method ↓
Degree ↓
Wavelet ↓
Spec. ↓
Clus.
Orbit ↓
DiGress
0.000374
0.00567
0.0175
0
0.000611
DeFoG
0.000349
0.00517
0.0149
0
0.000335
BWFlow
0.003180
0.01920
0.0300
0
0.000840
MG-Diff (Ours)
0.000204
0.00500
0.0112
0
0.000175
Appendix
Table 12 : Graph generation performance on tree data
#Nodes
#Edges
Construction time (s)
Start memory (MB)
End memory (MB)
1,000
1,333
0.0049
666.00
666.00
5,000
13,530
0.0333
666.64
666.64
10,000
44,175
0.0912
666.89
666.89
25,000
353,582
0.6185
666.90
666.90
50,000
669,889
1.1644
670.53
680.37
169,343
1,157,799
2.2019
681.35
706.65
Appendix
Table 13 : Runtime and memory consumption of the one-time Morse construction on BFS-induced subgraphs of ogbn-arxiv. Memory is the process RSS before and after construction.
Corruption
Rate
MG-Diff (Ours)
USTD
MAE
RMSE
CRPS
MAE
RMSE
CRPS
Clean
0%
10.259
15.201
0.2452
10.725
15.713
0.2750
Missing events
5%
10.449
15.458
0.2508
11.271
16.196
0.2938
Missing events
10%
10.815
15.837
0.2612
11.936
16.725
0.3174
Missing events
20%
12.132
16.945
0.2953
13.628
18.073
0.3718
Degradation at 5%
−1.85%
−1.69%
−2.28%
−5.09%
−3.07%
−6.84%
Appendix
Table 14 : Robustness to missing events on AIR-GZ. Top: absolute performance under increasing missing-event rates. Bottom: relative degradation with respect to the clean setting.
Method ↓
Degree ↓
Wavelet ↓
Spec. ↓
Clus.
Orbit ↓
DiGress
0.000374
0.00567
0.0175
0
0.000611
DeFoG
0.000349
0.00517
0.0149
0
0.000335
BWFlow
0.003180
0.01920
0.0300
0
0.000840
MG-Diff (Ours)
0.000204
0.00500
0.0112
0
0.000175
Appendix
Table 15 : Graph generation performance on tree data
After a somewhat rocky start, geometry and topology have established a foothold in machine learning. Message passing, either on graphs or higher-order complexes, is one of the main drivers of geometric deep learning, and paradigms that were once considered to be firmly in the realm of the abstract-like sheaves-have been "tamed" to serve as novel inductive biases for model architectures in topological deep learning. The veritable diversity of models, however, is in stark contrast to the scarcity of suitable benchmark datasets. As a result, researchers often resort to lifting existing graph datasets to include higher-order information. In this opinion paper, I want to encourage the community to also source new datasets, which may be used to prop up the foundations of our research field.
Bastian Rieck
AIDOS Lab, University of Fribourg, Switzerland · Institute of AI for Health, Helmholtz Munich, Germany
Despite an ever-increasing interest in topological deep learning models that target higher-order datasets, there is no consensus on how to evaluate such models. This is exacerbated by the fact that topological objects permit operations, such as structural refinements, that are not appropriate for graph data. In this work, we extend MANTRA, a benchmark dataset containing manifold triangulations, to a larger class of manifolds with more diverse homeomorphism types. We show that, unlike prior claims, both graph neural networks (GNNs) and higher-order message passing (HOMP) methods can saturate the benchmark. However, we find that this is contingent on the right representation and feature assignment, emphasizing their importance in baseline models. We thus provide a novel evaluation protocol based on representational diversity and triangulation refinement. Surprisingly, we find no indication that existing models are capable of generalizing beyond the combinatorial structure of the data. This points towards a research gap in developing models that understand topological structure independent of scale. Our work thus provides the necessary scaffolding to evaluate future models and enable the development of topology-aware inductive biases.
Johannes S. Schmidt, Martin Carrasco, Ernst Röell +3
Dept. of Math. & Statistics University of Montréal Montréal, Canada · Dept. of Informatics University of Fribourg Fribourg, Switzerland
We introduce Topoformer, a lightweight and scalable framework for graph representation learning that encodes topological structure into attention-friendly sequences. At the core of our method is Topo-Scan, a novel module that decomposes a graph into a short, ordered sequence of topological tokens by slicing over node or edge filtrations. These sequences capture multi-scale structural patterns, from local motifs to global organization, and are processed by a Transformer to produce expressive graph-level embeddings. Unlike traditional persistent homology pipelines, Topo-Scan is parallelizable, avoids costly diagram computations, and integrates seamlessly with standard deep learning architectures. We provide theoretical guarantees on the stability of our topological encodings and demonstrate state-of-the-art performance across graph classification and molecular property prediction benchmarks. Our results show that Topoformer matches or exceeds strong GNN and topology-based baselines while offering predictable and efficient compute. This work opens a new path for parallelizable and unifying approaches to graph representation learning that integrate topological inductive biases into attention frameworks.
Department of Mathematical Science The University of Texas at Dallas Richardson, TX 75080, USA · Department of Mathematics Florida State University Tallahassee, FL 32306, USA · AI Initiative University of Central Florida Orlando, FL 32816, USA