PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Representation via Elements of Discrete Morse and Cobordism Theories

Jennifer Rozenblit, Chenguang Yang, Yuxin Liu, Yuzhou Chen, Yulia Gel

arXiv:2610.01937v1cs.LGmath.GN

TL;DR

Graph diffusion work has largely treated generation as local denoising, while topology in machine learning has focused mainly on topological data analysis. MG-Diff conditions graph diffusion on a discrete Morse skeleton, reports competitive forecasting and regeneration performance, and shows relative CRPS gains of 6%-16% on all but one dataset.

  • Problem

    Topology in machine learning remains largely focused on topological data analysis, while graph diffusion often treats generation as local denoising without explicitly modeling how global structure emerges, merges, or dissipates.

    Source: §1 · pp. 1–2

  • Method

    MG-Diff conditions graph diffusion on a discrete Morse skeleton of the graph’s clique complex, using critical cells and a filtration-compatible representative path to guide structural changes.

    Source: §1 · p. 3, §3 · p. 5

  • Results

    MG-Diff shows competitive forecasting and regeneration performance, with relative CRPS gains of 6%-16% on all but one dataset.

    Source: §1 · p. 4

  • Takeaways & Limitations

    MG-Diff guides graph generation toward preserving global structures while allowing local substructures to be randomized, with competitive gains in forecasting and uncertainty quantification.

    Source: §5 · p. 12

    Existing higher-order guidance can remain heuristic and under-specify which cycles become higher-dimensional cells and how their attaching maps are chosen.

    Source: §1 · p. 2, §3 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

Topology in machine learning remains largely focused on topological data analysis, while cobordism and discrete Morse theory offer a complementary perspective for graph diffusion. MG-Diff conditions diffusion on a discrete Morse skeleton, with the paper reporting forecasting and uncertainty-quantification gains.

1 Introduction

  • Graph diffusion can struggle to preserve global structure such as cycles and higher-order motifs, which convey information about latent organization and system function.The introduction cites transportation cycles as describing alternative traffic loops or robustness against disruptions.Source: §1 · p. 1
  • Cobordism-aware structure captures event connectivity that persistence records do not: distinct gradient fields can share persistence diagrams yet have different descending manifolds.The paper uses this distinction to motivate an intermediate representation of both event timing and connectivity.Source: §1 · p. 2
  • MG-Diff extracts a discrete Morse skeleton from each graph and conditions diffusion on it, providing a sparse guide that encodes critical cells and gradient-respecting paths.The skeleton represents both topological events and how gradient flow connects them.Source: §1 · p. 2
  • Diffusion trajectories need not be monotone in a topological invariant; the skeleton instead guides which points within and between changing topologies should remain stable.Each perturbation can be viewed as an elementary cobordism that preserves or changes graph topology.Source: §1 · p. 3
  • A finite-comparison deterministic extractor is reported to have a local stability result when relevant decision gaps are separated.The supplied introduction passage does not state the separation threshold or full conditions.Source: §1 · p. 3
  • 6%-16% relative CRPS gains are reported for MG-Diff on all but one dataset, alongside competitive spatio-temporal forecasting performance.The authors also report that MG-Diff illustrates the utility of discrete Morse and cobordism theory for graph forecasting and regeneration.Source: §1 · p. 4

2 Elements of the Discrete Morse Theory

Discrete Morse theory gives a combinatorial analogue of classical Morse theory for cell and simplicial complexes. The section motivates Morse-guided filtrations for network topology and describes how critical simplices represent topological events.

2 Elements of the Discrete Morse Theory

  • A discrete Morse function is a combinatorial analogue of a smooth Morse function, and a critical simplex has no paired face or coface under the function.Critical simplices encode irreducible topological features and form a basis for Morse reductions and topology-aware filtrations.Source: §2 · pp. 4–5
  • Morse matchings can simplify complexes while preserving homology, often reducing computation for persistent homology on dense or large-scale complexes.Morse-guided filtrations also provide theoretical lower bounds on critical-cell counts for representing homology and achieve near-optimal reductions in practice.Source: §2 · p. 4
  • Naive network filtrations can obscure higher-order clique organization, so the paper adopts a Morse filtration whose critical simplices govern topological events.The cited discussion notes that dimension-only filtrations may reproduce heavy-tailed degree distributions while missing heterogeneity in higher-order clique organization.Source: §2 · p. 4

3 Methodology: Morse-Guided Diffusion

MG-Diff uses a discrete Morse skeleton to guide graph diffusion, representing critical topological events and gradient-respecting paths. The section specifies how the skeleton is constructed, proves conditions for its stability and informational refinement over persistence diagrams, and describes the model that uses it.

3 Methodology: Morse-Guided Diffusion

  • Existing higher-order guidance can omit intra-topological shifts, under-specify cell attachments, or become unstable on sparse and near-tree graphs.The paper identifies these limitations as motivation for a Morse-theoretic intermediate representation.Source: §3 · p. 5

3.1 Morse Skeleton Representation of Graphs

  • The Morse skeleton S(G) = (C, D) pairs critical cells with a representative gradient-respecting descending path, encoding topological-event locations and combinatorial flow.The extractor is deterministic and returns a finite skeleton for the graph’s clique complex.Source: §3.1 · p. 6

3.2 Construction of the Discrete Morse Function

  • A deterministic edge-assignment routine pairs incident cells while enforcing the discrete Morse inequalities, yielding a valid discrete Morse function and gradient vector field.The construction uses average and raise branches, with a small edge-noise term in the latter.Source: §3.2 · p. 6
  • The degree-based score directs gradient flow toward high-degree vertices, while the choice of scoring function determines which cells are treated as critical.The paper motivates degree-based scoring for sparse sensor networks and contrasts it with betweenness- and eigenvector-based choices for other tasks.Source: §3.2 · pp. 6–7
  • For each critical cell, MG-Diff selects a deterministic representative path rather than retaining the full descending manifold.In the 1-skeleton setting, the path follows a unique finite V-path under the specified greedy rule.Source: §3.2 · p. 7

3.3 Theoretical Guarantees of Morse Skeleton Guidance

  • The skeleton strictly refines the persistence diagram: it determines the diagram, but equal diagrams can correspond to different skeletons and descending-manifold structures.Under a positive decision margin and Lipschitz decision gaps, sufficiently small feature perturbations leave the extracted skeleton unchanged.Source: §3.3 · p. 8

3.4 Morse-Guided Diffusion Model

  • MoMoE separates critical and non-critical graph parts and routes representational capacity between their experts; the denoiser uses the resulting Morse-aware condition with diffusion inputs.The critical/non-critical split is based on the Morse-derived partition, and the reverse process is conditioned on both graph structures and the MoMoE condition.Source: §3.4 · pp. 9–10

4 Experiments

Across the reported spatio-temporal forecasting scenarios, MG-Diff achieves the strongest performance, and graph-generation results also favor it on the reported distributional and topology measures. The experiments further relate uncertainty gains to structural guidance and report ablations of model components and skeleton choices.

Results

  • MG-Diff yields the strongest forecasting performance across the reported scenarios, including lower MAE, RMSE, and CRPS than the runner-up on PEMS-03.On PEMS-03, it improves over USTD by 3.6% in MAE, 3.2% in RMSE, and 6.1% in CRPS; on AIR-GZ, its CRPS is second to USTD.Source: §4 · p. 10
  • Compared with SwinGNN and GDSS, MG-Diff shows up to 46.98% relative gain on Degree, maintains competitive clustering structure, and yields substantially lower W2 and smaller Betti β0/β1 discrepancies.Source: §4 · pp. 10–11

Topological Uncertainty Quantification

  • The paper attributes CRPS gains of 6.1%–15.7% to skeleton conditioning that anchors denoising to global cyclic context, with the skeleton most influential during early high-noise reverse steps.The gains are largest on AIR-BJ, intermediate on PEMS, and smallest on AIR-GZ; on tree-like graphs with β1 ≈ 0, MG-Diff reduces to standard conditional diffusion.Source: §4 · p. 11

Ablation Studies

  • Ablations report degradation of up to 20% when MoMoE or MDDN is removed, and replacing the Morse skeleton with a matched-size random skeleton worsens all four reported AIR-GZ metrics.The matched-size random-skeleton comparison reports Morse-skeleton wins of 6.0% in MAE, 3.5% in RMSE, 7.2% in MAPE, and 8.4% in CRPS.Source: §4 · p. 11

5 Conclusion

The conclusion presents MG-Diff as a mathematically grounded way to guide graph diffusion using discrete Morse and cobordism theory. The paper also positions its skeleton as information beyond persistence and states future directions for extending the approach.

5 Conclusion

  • MG-Diff guides graph diffusion on which global structures remain intact and which local substructures can be randomized, with reported competitive gains in forecasting and uncertainty quantification.The conclusion identifies diffusion on manifolds, probabilistic object alignment, and dynamic graphs as future directions.Source: §5 · p. 12

A Mathematical Background

  • The paper supplies mathematical background on smooth Morse theory, cobordisms, discrete Morse theory, and their applications to graph diffusion to make its constructions precise.It refers readers to classical texts for deeper theory.Source: A Mathematical Background · p. 18

A.1 Positioning

  • The paper gives explicit counterexamples showing that persistence diagrams do not determine descending-manifold structures.It states that no well-defined map from persistence diagrams to descending-manifold structures exists.Source: §A.1 · p. 19

A.2 Topology in Modern Machine Learning

This section develops the smooth, cobordism, and discrete Morse concepts used to describe critical events, descending flow, and graph-specific structure, positioning MG-Diff as integrating discrete Morse structure into graph diffusion conditioning rather than introducing the theory itself. It then specializes to graphs, where acyclicity supports a sink-based anchor map, while the main MoMoE split uses paired and critical edges without requiring anchors.

A.2 Topology in Modern Machine Learning

  • MG-Diff conditions graph diffusion on a persistence-free Morse skeleton whose descending paths are not recoverable from persistence diagrams, unlike prior deterministic reconstruction or segmentation methods.The method operates on abstract graphs using a degree score by default, and uses the skeleton as a generative diffusion condition; prior DMT methods use ambient scalar fields and persistence to prune the Morse complex.Source: §A.2 · pp. 19–20

A.3 Graphs as Clique Complexes

  • A graph’s clique complex is the downward-closed simplicial complex whose simplices are the vertex sets of its cliques, including vertices, edges, and triangles as 0-, 1-, and 2-simplices.A p-simplex contains p+1 mutually adjacent vertices.Source: §A.3 · p. 20

B Smooth Morse Theory on Manifolds

  • On a smooth compact manifold, non-degenerate critical points of a Morse function are isolated, and their indices count the independent directions in which the function decreases.The manifold admits a CW decomposition with one cell of index ind(p) for each critical point p.Source: B Smooth Morse Theory on Manifolds · p. 21

C Cobordisms and Morse Functions

  • A Morse function on a cobordism describes transformation between boundary manifolds through handle attachments, with each critical point corresponding to a handle whose index equals the point’s Morse index.Topology changes precisely at critical points.Source: C Cobordisms and Morse Functions · p. 22

D Discrete Morse Theory

  • Discrete Morse theory replaces smooth manifolds with cell complexes, where critical cells encode essential topological features and determine a homotopy-equivalent CW model.The model has exactly one p-cell for each critical p-cell.Source: D Discrete Morse Theory · p. 22, §D.1 · p. 24

D.1 Discrete Morse Functions and Critical Simplices

  • A single descending path compactly represents a critical cell’s location and gradient-flow direction for fixed-size diffusion guidance, while preserving event semantics despite variation in non-critical regions.The full descending manifold can be large and unstable under benign changes to non-critical structure.Source: §D.1 · p. 23

E Discrete Flow and Descending Sets

  • The Morse skeleton combines critical cells with their induced descending sets, which encode the parts of a complex that flow out of each critical cell and guide diffusion.A descending set is a combinatorial reachability object defined by V-paths, rather than a smooth submanifold.Source: E Discrete Flow and Descending Sets · p. 25

F Specialization to Graphs: Acyclicity and Paired-Edge Orientation

G H0-Faithfulness and Semantic Guarantees for the MoMoE Split

Under H0-faithfulness and forestedness, the paired-edge subgraph preserves components and critical edges encode cycle rank. The stability analysis shows when perturbations leave the Morse skeleton—and therefore its diffusion guidance—unchanged.

G H0-Faithfulness and Semantic Guarantees for the MoMoE Split

  • Under H0-faithfulness and forestedness, paired edges form a spanning forest and critical edges account exactly for the graph’s cycle rank.H0-faithfulness alone does not imply forestedness; both conditions are needed for this interpretation.Source: G H0-Faithfulness and Semantic… · pp. 26–27

H Proofs and Additional Details on Stability of Morse-Skeleton Guidance

  • The stability guarantees concern invariance of skeleton-based guidance, not global stability of discrete Morse theory.The setup assumes a deterministic skeleton extractor, fixed historical input, and a reverse-step kernel whose covariance is independent of the state.Source: H Proofs and Additional Details on… · p. 27, §H.1 · pp. 27–28

H.1 Abstract Setup

  • If a perturbation preserves the extracted skeleton, the guidance and reverse-step conditional distribution remain unchanged.This follows from deterministic guidance computed from the skeleton and fixed historical input.Source: §H.1 · p. 28

H.1.1 Interpretation and implications

  • The skeleton is a sufficient characteristic for guidance: state information that does not change it is invisible to the reverse diffusion process.Perturbations to edge weights, node features, or auxiliary scores that leave the skeleton unchanged therefore leave the generative distribution unchanged.Source: §H.1.1 · p. 28

H.2 A sufficient condition for skeleton preservation: margin stability

  • A positive decision margin and Lipschitz decision gaps provide a sufficient condition for skeleton preservation under small perturbations.The guarantee addresses perturbations relative to a computable margin; it does not characterize preservation when the skeleton changes.Source: §H.1.1 · p. 28, §H.2 · p. 29, §H.2.2 · p. 31

H.2.1 Decision representation

  • The extractor’s output is determined by finitely many comparison signs; MG-Diff’s degree-score pairing meets this condition with deterministic tie-breaking.The comparison-based representation does not cover extractors using continuous optimization or soft differentiable relaxations.Source: §H.2.1 · pp. 29–30

H.2.2 Decision margin and Lipschitz regularity

  • The decision margin is the smallest comparison gap, and MG-Diff’s degree-based score differences have Lipschitz constant at most 2.Near-ties weaken the margin certificate; the minimum score gap across edges provides a concrete local stability measure.Source: §H.2.2 · pp. 30–31

H.2.3 Proof of Theorem 6: the margin stability guarantee

  • When perturbations are smaller than the margin divided by the Lipschitz constant, comparison signs stay fixed and the skeleton is unchanged.The proof preserves every decision sign, so the deterministic extractor returns the same output.Source: §H.2.3 · p. 31

H.2.4 Interpretation and practical implications

The margin defines a state-specific radius within which the skeleton is guaranteed unchanged, yielding invariant guidance. Its practical strength depends on the margin and the extractor’s Lipschitz constant.

H.2.4 Interpretation and practical implications

  • Within radius r(s) = m(s)/L∆, the skeleton is guaranteed unchanged, so the generative distribution remains invariant to such local perturbations.The radius is defined around each state using its decision margin and the Lipschitz constant.Source: §H.2.4 · pp. 31–32
  • For MG-Diff, L∆ ≤ 2, so vertex-score perturbations smaller than δ/2 preserve the skeleton when the minimum adjacent-vertex score gap is δ > 0.The stability radius is at least m(s)/2.Source: §H.2.4 · p. 32
  • Near-ties, including repeated degrees in regular or near-regular graphs, shrink the margin and weaken the guarantee; larger Lipschitz constants also shrink the radius.Degree-based MG-Diff has L∆ ≤ 2, while more complex nonlinear scoring functions can have larger constants.Source: §H.2.4 · p. 32
  • The extractor’s decision gaps yield a computable robustness certificate from the minimum absolute score difference over edges, obtained in linear time.This enables post-hoc robustness verification for individual inputs.Source: §H.2.4 · p. 32

I.1 Worked Example: Discrete Morse Flow on a Two-Cycle Graph

The worked example shows how a discrete gradient field identifies critical cells and descending paths; counterexamples establish that persistence alone cannot determine descending-manifold structure.

I.1 Worked Example: Discrete Morse Flow on a Two-Cycle Graph

  • The upper-link rule pairs each edge with an unpaired higher-valued endpoint, leaving vertex 5 and cycle-closing edges (2, 3) and (6, 7) critical.The unique critical vertex is the global minimum; the two critical edges cannot be paired without violating acyclicity.Source: §I.1 · pp. 33–34
  • From each critical edge, descending paths follow unpaired incidences and matched pairs until they reach a critical vertex.In the example, both endpoints of each critical edge have anchor 5.Source: §I.1 · p. 34

J Counterexamples: Persistence Does Not Determine Descending Manifolds

  • Identical persistence diagrams can correspond to distinct descending-manifold structures, so no well-defined reconstruction map from persistence alone exists.The counterexamples include filtration-compatible gradient fields with genuine finite birth–death intervals.Source: J Counterexamples: Persistence Does… · p. 35

J.1 A Minimal Counterexample: Path Graph on Four Vertices

  • On the four-vertex path, the same filtration has D0={(0, ∞), (0, 3)} while e12 has different descending manifolds under V1 and V2.The two fields are valid filtration-compatible discrete gradient vector fields on the tree.Source: §J.1 · pp. 36–37, Conclusion · p. 38

Conclusion.

  • The conclusion rules out any well-defined rule that outputs a unique descending-manifold structure from a persistence diagram alone.Source: Conclusion · p. 38

J.3 J.2. Robustness under stricter compatibility: maximal entry-time matchings

Even under maximal entry-time-compatible matchings, identical persistence can accompany different descending-manifold connectivity. The related-work discussion situates this result within topology-aware graph diffusion and motivates cobordism theory as a generative modeling framework.

J.3 J.2. Robustness under stricter compatibility: maximal entry-time matchings

  • Entry-time compatibility requires each matched pair to appear at the same first filtration index, and maximality means no larger compatible matching exists.Source: §J.3 · p. 38
  • Two maximal entry-time-compatible matchings can have identical persistence yet route descending-manifold connectivity differently from the merge edge toward b or c.At t = 2, the new edges share u; matching u to one prevents pairing the other under the matching and entry-time constraints.Source: §J.3 · p. 39

L Overview of the Related Work

  • Graph diffusion often learns local denoising rules without explicitly representing when global events such as fundamental cycles occur.The discussion notes that these cycles can convey information about latent organization and functionality.Source: L Overview of the Related Work · p. 40
  • The paper introduces cobordism theory to spatio-temporal graph diffusion, drawing on its account of topology-changing trajectories and variation across diffusion trajectories.The related-work discussion presents handle decompositions and Cerf theory as relevant structures for generative modeling.Source: L Overview of the Related Work · p. 41

M Datasets, baselines and experimental setup

The experiments use four real-world air-quality and traffic datasets, a 60-minute history window, and comparisons with eight forecasting baselines.

M Datasets, baselines and experimental setup

  • The evaluation uses PEMS-03, PEMS-BAY, AIR-BJ, and AIR-GZ, covering traffic-speed and PM2.5 measurements from California, Beijing, and Guangzhou.PEMS-03 measurements are recorded every five minutes; PEMS-BAY contains six months of data from 325 Bay Area sensors, while AIR-BJ and AIR-GZ each span one year.Source: M Datasets, baselines and experimental… · p. 42
  • All tests use a 60-minute history window, and MG-Diff is compared with eight baselines, including TimeGrad, CSDI, DiffSTG, PriSTI, USTD, DSTD, and ZS-DM.The passage lists MC Dropout as the eighth baseline alongside the seven named here.Source: M Datasets, baselines and experimental… · p. 42
  • Training uses Adam with batch size 32 and learning rate 1e−3; hidden dimensions are selected by grid search over 8 to 256.The learning-rate search considers {1e−4, 3e−4, 3e−3, 1e−2}.Source: M Datasets, baselines and experimental… · p. 42

N Ablation Studies and More Details on Computational Costs

A matched-size random-skeleton comparison isolates the benefit of Morse-based conditioning, while additional tests examine scoring-function robustness and computational costs.

N Ablation Studies and More Details on Computational Costs

O Additional Experiments

Additional experiments report graph-generation performance on tree data, robustness to missing observations, and one-time construction costs. The discussion relates the value of Morse guidance to cycles, bottlenecks, and changing topology.

O Additional Experiments

  • Clustering MMD is nondiscriminative on tree data because trees contain no triangles, making the clustering coefficient zero for valid tree outputs.The reported similarity across models on this metric is therefore an artifact of the data topology, not evidence of equal model quality.Source: O Additional Experiments · p. 45
  • On tree graphs, MG-Diff achieves the lowest MMDs for degree, wavelet, spectrum, and orbits, with relative gains from 3.2% to 49%.The authors attribute the degree and orbit results to conditioning that encodes the tree’s branching hierarchy.Source: O Additional Experiments · pp. 44–45, Table 12 · p. 45
  • Morse construction on the 169k-node ogbn-arxiv graph requires about 2.2 seconds and 25MB, and the cached structure adds no per-iteration optimization cost.The construction is performed once during model initialization.Source: O Additional Experiments · p. 45, Table 13 · p. 46
  • At 20% missingness, MG-Diff’s MAE, RMSE, and CRPS degradations are 18.3%, 11.5%, and 20.5%, versus USTD’s 27.1%, 15.0%, and 35.2%.MG-Diff is reported to outperform USTD across tested corruption levels on MAE, RMSE, and CRPS.Source: Table 14 · p. 46, O Additional Experiments · p. 46

O.1 Morse guidance, a discussion.

  • Forecasting gains are largest on AIR-BJ with ring roads and high β1, smallest on AIR-GZ with a dense, opaque skeleton, and intermediate on PEMS.The discussion connects forecasting value to cycles and bottlenecks that shape signal flow and uncertainty.Source: §O.1 · p. 47
  • For graph regeneration, the Morse structure marks cycle births and deaths and component merges or splits; guidance is useful when valid samples depend on these events.The discussion cites molecular rings, meshes, and utility networks as examples.Source: §O.1 · p. 47
  • Tree-like forecasting is a weak case: with β1 ≈ 0, Ecrit is empty and MoMoE collapses to one expert, reducing MG-Diff to standard conditional diffusion.The discussion says hierarchy is weakest when it occurs without cycles, and gains appear when hierarchy coexists with cycles.Source: §O.1 · p. 47

P Limitations

The limitations section identifies the lack of formal statistical inference as a current limitation and leaves it for future research. The paper also describes anticipated broader impacts and its limited use of language models.

P Limitations

  • A main current limitation is the lack of formal statistical inference, which the authors leave as a standalone future research direction.They frame this as a question at the interface of low-dimensional topology and mathematical statistics.Source: P Limitations · p. 47

Q Broader Impacts

  • The authors anticipate topological uncertainty quantification could benefit risk-assessment applications and state that they envision no negative societal impacts.These are presented as the authors’ expectations about broader impacts.Source: Q Broader Impacts · p. 47

R Usage of LLM

  • LLMs were used only to rephrase sentences and correct grammar, not to design experiments, generate results, or contribute scientific content.Source: R Usage of LLM · pp. 47–48
Loading 2610.01937v1…