Topological Graph Neural Networks

• Message-passing GNNs cannot necessarily capture structures such as cycles, which are relevant to applications requiring connectivity information, including molecular graph analysis.Source: §1 · p. 1
• TOGL integrates into GNNs, learns contrasting topological representations, and increases expressivity; it improves predictive performance when topology matters for the task.The layer is differentiable and incorporates multi-scale topological information.Source: §1 · p. 1
• Figure 1 contrasts a data set classifiable by topology-based methods with one that requires learnable topological features.The figure compares GCN, GCN-TOGL, the Weisfeiler–Lehman graph kernel, and static topological features.Source: Figure 1 · p. 2

• A graph’s Betti numbers count its connected components (β0) and cycles (β1), and are invariant under graph isomorphism.Source: §2 · p. 2
• A filtration is a sequence of nested subgraphs that tracks when topological features appear and disappear, with persistence recording their relevance across the sequence.Persistent homology represents a feature by its appearance and disappearance indices, or by filtration-function values.Source: §2 · p. 2
• The notation ph(G, f) returns dimension-0 diagrams for connected components and dimension-1 diagrams for cycles, associating tuples with the vertices or edges that create them.Unpaired edges receive a dummy tuple value; other cycle-forming edges are paired with the maximum filtration value.Source: §2 · p. 2

• Graph kernels embed graphs in reproducing kernel Hilbert spaces but cannot capture partial neighborhood similarities, which GNNs learn through message passing.Source: §3 · pp. 2–3
• Related GNN work incorporates additional substructures, higher-order message passing, or generalized message passing.Source: §3 · p. 3
• Unlike GFL’s single-filtration readout and Zhao et al. (2020)’s local scalar-weight approach, TOGL learns multiple filtrations and exposes topology to downstream layers.The paper describes TOGL as applicable to arbitrary GNN architectures and topological features at all scales, including graph-level features.Source: §3 · p. 3

4 TOGL: A TOPOLOGICAL GRAPH LAYER

• TOGL maps node attributes through learned filtrations to persistence-diagram embeddings, which are combined with the original attributes to augment GNN representations.The filtration functions are projections of a single-hidden-layer MLP; the implementation fixes l = 1, capturing connected components and cycles.Source: §4 · pp. 3–4
• Dimension-0 embeddings augment individual node representations, while dimension-1 embeddings are pooled into a graph-level representation.The paper gives graph-level pooling for dimension 1 because cycles map to edges rather than bijectively to vertices, and cites stability reasons for this choice.Source: §4 · p. 4
• For dimensions 0 and 1, persistent-homology computation is dominated by edge sorting at O(m log m); higher-dimensional calculations scale poorly, so TOGL restricts its implementation to components and cycles.The scalar-valued filtrations also cannot assess topological feature interactions; the authors leave multifiltrations for future work.Source: §4 · p. 4
• The filtration-to-diagram embedding is differentiable when the filtration assigns distinct values to vertices, enabling end-to-end training of the views.The authors consider DeepSets and several point transformations; they report no significant advantage among the embedding functions and treat the choice as a hyperparameter.Source: §4.2 · p. 5, §4.1 · p. 5

4.2 DIFFERENTIABILITY & EXPRESSIVE POWER

• This expressivity result does not guarantee better predictive performance; gains depend on whether task-relevant features are captured by the learned filtration.The authors state that WL[1]-based filtrations are not necessarily optimal for a specific task and TOGL may learn other filtrations.Source: §4.2 · pp. 5–6
• Persistent homology is at least as expressive as WL[1], and TOGL can distinguish graphs that WL[1] cannot, including two triangles versus a hexagon.The example differs in Betti numbers: the two triangles have β0 = β1 = 2, while the hexagon has β0 = β1 = 1.Source: §4.2 · pp. 5–6

5.1 EXPERIMENTAL SETUP

• The experiments use consistent training and limited parameter budgets, benchmark-matched folds and hyperparameters, and replace a GNN's second layer with TOGL as a parameter-matched compromise placement.The embedding function Ψ is treated as a hyperparameter.Source: §5.1 · pp. 6–7

5.2 PERFORMANCE ON SYNTHETIC DATA SETS

• On synthetic CYCLES and NECKLACES tasks, TOGL performs well even without GCN layers, while standard GCNs need at least four layers for CYCLES and more for NECKLACES to approach it.Degree-based static PH works on CYCLES, whose classes differ in Betti numbers, but NECKLACES require a task-learned filtration to distinguish their connectivity.Source: §5.2 · p. 7

5.3 STRUCTURE-BASED GRAPH AND NODE CLASSIFICATION PERFORMANCE

• On structure-only graph and node tasks, TOGL improves performance in virtually all comparisons, with gains exceeding 8% for GCN-3-TOGL-1 over GCN-4 on MNIST.For structural MNIST, TOGL also reaches high performance with fewer layers, a pattern observed on other datasets and associated with reduced oversmoothing risk.Source: §5.3 · pp. 7–8, Table 1 · p. 8, Figure 3 · p. 8

5.4 PERFORMANCE ON BENCHMARK DATA SETS

• TOGL outperforms comparison partners on most benchmark datasets, although ENZYMES overfits and GAT training has high variance, including on REDDIT-B.The benchmark comparison also reports that adding TOGL seems to address the GAT training issue on REDDIT-B.Source: §5.4 · pp. 8–9, Table 2 · p. 8

5.5 COMPARISON TO OTHER TOPOLOGY-BASED ALGORITHMS

• Against topology-based methods, learned filtrations outperform fixed ones, while TOGL compares well with a topology readout whose large standard deviations prevent assessing significant differences.Different TOGL placements can also lead to significantly different performance; the comparison uses a simplified GNN with one GCN message-passing layer.Source: §5.5 · p. 9, Table 3 · p. 9

6 CONCLUSION

• TOGL incorporates topological information into GNN architectures, and its learnable filtration functions make it more expressive than WL.The paper states that this also increases GNN expressivity.Source: §6 · p. 9
• On datasets with pronounced topological structures, TOGL helps GNNs achieve substantial predictive-performance gains and performs favorably against the literature on benchmarks.Source: §6 · p. 9
• Embedding functions that capture interactions between individual topological features typically perform better than functions that do not.Source: §6 · p. 9
• Topological information may lead to overfitting on smaller datasets; investigating additional regularization strategies remains future work.Source: §6 · p. 9
• The authors hypothesize that different filtration types and advanced persistent-homology algorithms, including extended persistence, could benefit predictive performance.Source: §6 · p. 9

REPRODUCIBILITY STATEMENT

• Experiments used single GPUs and released code and training seeds; tracked parameters and performance metrics were to be made publicly available.The code is released under a BSD-3-Clause License.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 SIMPLICIAL HOMOLOGY

• Simplicial homology quantifies connectivity through chains, boundaries, and homology groups; quotienting boundaries removes filled triangles from the count of holes.Graphs are treated as one-dimensional complexes, so their cycles are not filled by 2-simplices.Source: §A.1 · p. 14

A.2 PERSISTENT HOMOLOGY

• Persistent homology extends simplicial homology by tracking topological features across nested complexes, retaining scale information that coarse Betti numbers miss.Features are represented by creation and destruction values; the paper focuses on ordinary persistence for lower computational complexity.Source: §A.2 · p. 15, §A.1 · p. 15

A.3 EXAMPLES OF GRAPH FILTRATIONS

• A filtration function assigns values to vertices and edges, producing nested subgraphs whose persistence diagrams reflect the chosen ordering.For an edge, the filtration value is the maximum of its endpoint values; degree and heat-kernel structural role are examples of vertex features used to define filtrations.Source: §A.3 · p. 16
• Changing vertex filtration values changes when components appear and merge, while the example retains one cycle in its dimension-1 diagram.With unique vertex values, the example's dimension-0 diagram includes the tuple (2, 4), representing a component that merges at step 4.Source: §A.3 · p. 16

A.4 COMPUTATIONAL DETAILS

• The implementation pairs dimension-0 persistence tuples with vertices and dimension-1 tuples with cycle-creating edges, using dummy tuples for unpaired edges across filtrations.The resulting diagram matrices can be concatenated for processing.Source: §A.4 · pp. 16–17

Constructing a separating filtration

• A filtration built by assigning values to WL[1] labels yields distinct diagrams when the label counts differ.Each vertex contributes one pair, so a differing label count produces a tuple multiplicity difference.Source: B THEORETICAL EXPRESSIVITY OF TOGL:… · p. 17

Injective-filtration argument

• Injectivity matters because the paper's differentiability result applies to injective filtration functions.The initial separating filtration may be non-injective, motivating the perturbation step.Source: B THEORETICAL EXPRESSIVITY OF TOGL:… · pp. 17–18
• Any filtration can be approximated arbitrarily closely by an injective one, and the proof argues that this perturbation preserves distinct persistence diagrams.The approximation is obtained by resolving non-injective vertex pairs with new values within an arbitrarily small radius.Source: B THEORETICAL EXPRESSIVITY OF TOGL:… · pp. 17–18

Expressivity theorem

• Persistent homology is at least as expressive as WL[1]: diverging WL[1] label sequences imply the existence of distinct 0-dimensional persistence diagrams.The strong result uses an injective filtration.Source: B THEORETICAL EXPRESSIVITY OF TOGL:… · p. 18

Empirical expressivity

• Only 14%–22% of tested graph pairs remain indistinguished by the fixed degree-filtration scheme; for the specified strongly regular graphs, the figure is about 1.2%.The latter result covers 8236 of 7424731 pairs among 3854 strongly regular graphs on 35 vertices with λ = μ = 9.Source: C EMPIRICAL EXPRESSIVITY: ANALYSIS OF… · p. 18
• The experiment uses a standard degree filtration, includes higher-order cliques, and assigns each graph a feature vector from total persistence.The filtration is fixed rather than learned.Source: C EMPIRICAL EXPRESSIVITY: ANALYSIS OF… · p. 18

Computational complexity

• Arbitrary-dimensional persistent homology can become infeasible on larger datasets because the approach performs clique counting.Approximations may alleviate this constraint to some extent, but their practical benefits are unclear.Source: C EMPIRICAL EXPRESSIVITY: ANALYSIS OF… · p. 18

D EXPERIMENTAL SETUP & COMPUTATIONAL RESOURCES

• Table S4 reports persistent-homology error rates for pairs of k-regular graphs under a degree filtration, as an illustrative rather than exhaustive set of cases.The setup also records compute resources and reports reproducibility materials, including code and training logs.Source: Table S4 · p. 19, D EXPERIMENTAL SETUP & COMPUTATIONAL… · pp. 19–20
• Training follows validation-loss scheduling: the learning rate is halved after a patience period without improvement, and runs stop when it falls below lrmin.Dataset-specific schedule parameters are listed in Table S5.Source: D EXPERIMENTAL SETUP & COMPUTATIONAL… · pp. 18–19, Table S5 · p. 19

E HYPERPARAMETERS

• The experiments use graph-learning datasets available in PyTorch Geometric, with benchmark origins including Morris et al. (2020) and Dwivedi et al. (2020).TOGL hyperparameters are listed in Table S6; the Weisfeiler–Lehman subtree-kernel SVM uses a linear kernel and repeated 5-fold cross-validation to obtain standard deviations.Source: D EXPERIMENTAL SETUP & COMPUTATIONAL… · p. 19, Table S6 · p. 20, E HYPERPARAMETERS · p. 20

D EXPERIMENTAL SETUP & COMPUTATIONAL RESOURCES

• The static ablation replaces persistent-homology mappings with static vertex mappings and random edge selection, thereby learning graph-level information not strictly based on topology.Without tuple interactions it reduces to a per-vertex MLP; with interactions it uses a DeepSet.Source: D EXPERIMENTAL SETUP & COMPUTATIONAL… · p. 19

F EXTENDED RESULTS FOR THE SYNTHETIC DATA SETS

• Both cycles and connected components are crucial for high predictive performance, while the static variant beats standard GCN slightly but remains well below TOGL.The static variant has limited access to topological information.Source: F EXTENDED RESULTS FOR THE SYNTHETIC… · p. 20

G VISUALISATION OF THE LEARNT FILTRATIONS

• Three learned filtrations on a DD graph show one correlated with node degree and others apparently focused on different local graph properties.Node width represents degree and color saturation represents filtration value.Source: G VISUALISATION OF THE LEARNT… · p. 20

H EXPERIMENTS ON LAYER PLACEMENT

• Placing non-static TOGL before the final GNN layer gives the best performance on the investigated dataset, whereas readout-only access to topology would perform worst there.Position 0 instead passes topological information to downstream layers, limited to what can be gleaned from graph nodes.Source: H EXPERIMENTS ON LAYER PLACEMENT · pp. 20, 23, Table S7 · p. 23
• Figure S4 compares synthetic-data performance across GCN depth or Weisfeiler–Lehman iterations and varies the dimensionality of TOGL's topological features.Standard deviations are omitted because they are negligible.Source: Figure S4 · p. 21
• The supplementary examples contrast molecular benchmark graphs with complex topological structures and social-network graphs described by clique connectivity, where a single hub does not imply exploitable topology.Figure S7 encodes node degree as dot width and learned filtration value as color saturation.Source: Figure S5 · p. 21, Figure S6 · p. 22, Figure S7 · p. 22
• The placement assessment also tests IMDB-Binary, Reddit-Binary, Proteins, and DD, with results listed in Table S8.The caption describes position 0 as informing downstream layers and last-position TOGL as a multi-filtration readout.Source: H EXPERIMENTS ON LAYER PLACEMENT · p. 23, Table S8 · p. 23

I EXTENDED EXPERIMENTS FOR STRUCTURED-BASED GRAPH CLASSIFICATION

• The ablations compare DeepSets, which models interactions among persistence-diagram tuples, with coordinate-function embeddings that do not model those interactions, and include static variants.Figure S8 compares embedding types and the static variant across datasets while varying network depth.Source: I EXTENDED EXPERIMENTS FOR… · p. 24, Figure S8 · p. 24
• On CLUSTER and PATTERN node classification, GCN-3-TOGL-1 or its static variant performs best among the comparison partners.The authors interpret benchmark results as evidence that labels or features often leak structural information, despite salient topology in some graphs.Source: I EXTENDED EXPERIMENTS FOR… · p. 24, Table S10 · p. 25
• The static variant's performance indicates that benchmark prediction is not generally driven by access to topological information, and the authors characterize existing datasets as often leaking structural information through labels or features.Table S10 covers structure-only graph and node classification results.Source: I EXTENDED EXPERIMENTS FOR… · p. 24, Table S10 · p. 25
• GCN-4 results on CLUSTER and PATTERN differ slightly because Dwivedi et al.'s implementation is misaligned with the original GCN architecture.The authors flag this as an implementation caveat for those datasets.Source: I EXTENDED EXPERIMENTS FOR… · p. 24

J GEOMETRIC DATASET

• Replacing a GNN layer with TOGL yields nearly perfect accuracy on the synthetic Spheres-versus-Torus classification task.The graphs are fully connected and use points sampled from spheres or tori; Table S12 compares GCN-4 and GIN-4 with corresponding TOGL variants.Source: J GEOMETRIC DATASET · p. 26, Table S12 · p. 26

K LARGER NUMBER OF LAYERS IN THE GNN ARCHITECTURE

• With larger GNN depth, the advantage of including TOGL is generally conserved, similar to the four-layer case.Tables S13 and S14 report classification accuracy for structural and benchmark setups; Table S14 separates graph and node classification results.Source: K LARGER NUMBER OF LAYERS IN THE GNN… · p. 26, Table S14 · p. 27
• For structural data, increasing depth raises DD performance for both baseline and TOGL models but lowers PROTEINS performance; benchmark performance tends to rise on all three datasets.The benchmark setup includes node features.Source: K LARGER NUMBER OF LAYERS IN THE GNN… · p. 26
• The larger-layer analysis covers DD, PROTEINS, and CIFAR-10 for computational reasons and reuses the Section 5.1 experimental setup.Source: K LARGER NUMBER OF LAYERS IN THE GNN… · p. 26