Repurposing Unified Topological Signatures for Graph Representation Learning
Sanyam Sanjay Jaina , Anshika Krishnatraya , Aditya Sharmaa , Vinti Agarwala
arXiv:2609.17061v1 [cs.LG] 15 Sep 2026
a
BITS Pilani, India
Abstract 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: Φgrph , a static signature of the input graph topology, and Φemb , 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.
1
Introduction
Graph Neural Networks (GNNs) have become the default architecture for relational learning, propagating and aggregating information across neighborhoods in a permutation-invariant manner [12]. For graph-level tasks, this aggregation exposes a representational limitation at readout. Standard readout functions (sum, mean, max) retain only first-order statistics of node embeddings, discarding higherorder connectivity almost entirely. Learned pooling operators perform adaptive graph coarsening [1, 11, 27], but select nodes based on local neighborhood, offering no guarantee that global topology survives pooling. Deeper message-passing layers enlarge the receptive field, but repeated aggregation acts as a low-pass filter on the feature matrix, collapsing node embeddings toward a common value as the Dirichlet energy decays exponentially in depth—resulting in oversmoothing [16, 21]. Oversmoothing collapses node embeddings and, consequently, graph representations after readout, eliminating structural information essential for graph-level prediction. Standard GNN objectives also lack an explicit mechanism to monitor topological fidelity during training. The expressive power of message-passing GNNs is provably upper bounded by the 1-dimensional Weisfeiler–Leman (1-WL) test: any two graphs that are 1-WL equivalent yield identical node embeddings Sanyam et al., Repurposing Unified Topological Signatures for Graph Representation Learning. Proceedings of the Fifth Learning on Graphs Conference (LoG 2026), PMLR TBD, TBD, TBD, 2026.
G1
G1
G2
G2
(b) Ours
Figure 1: Illustration of UTS-based graph discrimination. Standard message-passing GNNs with global readout may map the topologically distinct graphs G1 (C6 ) and G2 (2 × C3 ) to similar embeddings due to their reliance on local neighborhood aggregation. UTS resolves this limitation by integrating a comprehensive topological signature derived from persistent homology. For clarity, only the UTS-Aug with Betti-0 and Betti-1 curves are visualized, illustrating how differences in connected components and cycles contribute to distinguishing the two graphs.
under any message-passing GNN, regardless of depth or width [26]. As a result, non-isomorphic graphs with distinct global organization ( e.g., G1 and G2 in Figure 1), collapse to indistinguishable representations despite having different cycle structure and connectivity. Topological Data Analysis offers a natural way to expose what message passing hides. Persistent homology [8] extracts stable, multi-scale descriptors (components, cycles, higher-order voids), while recent work has incorporated topological priors into GNNs through persistence-based pooling [5] and discrete curvature methods such as Ricci flow and ORC-POOL [9, 20]. These confirm topological signal benefits GNNs, but each draws on a single geometric perspective. Unified Topological Signatures (UTS) compresses the global geometry of an embedding space into a compact descriptor combining persistent homology with geometric and spectral features [23], but so far only as a post-hoc analysis tool after training. We incorporate UTS into the GNN optimization process through two complementary signatures: a dynamic embedding signature (Embedding-UTS) computed from each GNN layer, and a static graph topology signature (Graph-UTS) extracted from the input graph. The former characterizes the evolving topology of the learned representation, while the latter captures the graph’s intrinsic topological invariants. For example, Figure 1 illustrates that the 1-WL-equivalent graphs G1 (C6 ) and G2 (2 × C3 ) are indistinguishable to message-passing GNNs, whereas UTS captures complementary global topological information beyond neighborhood aggregation, yielding distinct graph representations. We deploy both signatures across three architectural interventions: augmented readout, topologypreserving regularization, and topology-aware pooling, detailed in Section 4. The dynamic signature additionally provides a layer-wise Oversmoothing Index, transforming representation collapse from an unobserved failure mode into a measurable training signal. We instantiate our framework on Graph Isomorphism Networks (GINs) [26], whose expressiveness matches the 1-WL hierarchy, thereby isolating the contribution of UTS from architectural capacity. We theoretically establish that UTS-augmented GINs strictly exceed the expressive power of standard GINs while improving topological fidelity and robustness to oversmoothing. Experimental evaluation on three graph classification benchmarks confirms consistent gains over competitive message-passing baselines. Contributions. Our main contributions are summarized as follows: • We introduce a dual topological signature: a layer-wise embedding signature (Embedding-UTS), Φemb tracking the evolving geometry of learned representations, and a static graph signature (Graph-UTS) Φgrph characterizing input topology independently of training and immune to oversmoothing. • We integrate these signatures into GNN training as auxiliary features, regularization signals, and pooling guidance and perform experiments on three graph classification benchmarks (MUTAG, PROTEINS, and COLLAB). • We prove the UTS-augmented readout is strictly more expressive than the 1-WL test (Theorem 1). 2
• We introduce the Oversmoothing Index (OSI), a graph-level metric quantifying topological degradation across layers during training, without sacrificing differentiability or training efficiency.
2
Related work
Graph Neural Networks combine node features with connectivity through neighborhood aggregation. GraphSAGE introduced inductive message passing via learned sampled aggregators [12], while GIN established sum aggregation with expressive MLPs as the most discriminative scheme under the Weisfeiler-Lehman framework [26]. Graph classification additionally requires graph-level readout. Simple sum/mean/max pooling compress graphs into first-order statistics; hierarchical methods such as DiffPool and MinCutPool instead learn differentiable cluster assignments [1, 27], Select-Reduce-Connect unifies pooling methods by how they select, reduce, and reconnect nodes [11], and Graph Reference Distribution Learning represents graphs as distributions over node embeddings rather than a single pooled vector [25]. In contrast, our UTS-guided pooling ranks nodes by the topological richness of their embedding neighborhoods. A separate line embeds topology directly into GNNs: TOGL uses persistent homology as a differentiable, 1-WL-exceeding layer [13]; Wit-TopoPool applies witness-complex persistence to hierarchical pooling [5]. We instead use Unified Topological Signatures (UTS) [23], combining persistence with geometric/spectral statistics into a compact descriptor for post-hoc analysis. Ollivier-Ricci curvature characterizes community structure and bridge edges [20], exploited by ORC-POOL for pooling [9]; we fold curvature into UTS instead. Oversmoothing diagnostics typically rely on posttraining Dirichlet energy [24], missing topological preservation; our Oversmoothing Index signals topology throughout training. Prior work thus couples topology to specialized mechanisms (TOGL, Wit-TopoPool, ORC-POOL) or post-hoc analysis (UTS, Dirichlet diagnostics); we repurpose UTS as a unified training-time signal for readout, regularization, and pooling.
3
Preliminaries
3.1
Problem Setting
Let D = {(Gi , yi )}N i=1 denote a graph classification dataset, where each graph Gi = (Vi , Ei , Xi ) consists of a node set Vi , an edge set Ei , and node feature matrix Xi ∈ R|Vi |×d0 . The objective is to learn a permutation-invariant function f : G → Y, which maps an input graph to its class label while preserving the structural information required for graph-level discrimination. Throughout this work, we investigate how explicit topological descriptors can complement conventional message passing to improve graph representations for graph classification. 3.2
GIN Backbone
We instantiate our framework on the Graph Isomorphism Network (GIN) [26], chosen because its sum-based aggregation matches the expressive power of the 1-Weisfeiler–Leman (1-WL) test among message-passing GNNs. Given node representations H(l−1) , each layer updates node v as
(l) h(l) (1 + ϵ(l) )h(l−1) + v = MLP v
X
, h(l−1) u
(1)
u∈N (v) (0)
where ϵ(l) is a learnable scalar and hv = xv . A permutation-invariant graph readout aggregates the final node embeddings into a graph representation. Our proposed framework augments this standard pipeline with explicit topological information while leaving the underlying message-passing architecture unchanged.
4
Methodology
We introduce Dual Unified Topological Signatures, a pair of complementary descriptors that explicitly incorporate topology into graph learning: (i) a dynamic embedding signature (Embedding-UTS) 3
Φemb captures the evolving topology of the learned representation throughout message passing, and (ii) a static graph signature (Graph-UTS), Φgrph characterizes the intrinsic topology of the input graph. These signatures support three independent interventions: (i) UTS-Aug: Topology-Augmented Graph Representation (§4.2) concatenates the graph and embedding signatures with the conventional graph readout. (ii) UTS-Reg:Topology-Preserving Regularization (§4.3) introduces auxiliary objectives that preserve the evolution of embedding topology during training while aligning the final embedding topology with the intrinsic graph topology. (iii) UTS-Pool:Topology-Aware Pooling (§4.4) replaces feature-based node ranking with a topology-guided scoring mechanism derived from local embedding neighborhoods. Figure 2 presents an overview of three approaches. Each intervention is modular and can be incorporated independently or in combination, without modifying the underlying GNN architecture. The evolution of the embedding signature additionally provides a graph-level oversmoothing diagnostic. 4.1
Dual Unified Topological Signatures
Conventional graph readout aggregates node embeddings but lacks an explicit mechanism to encode global topology beyond message-passing representations. To address this limitation, we introduce two complementary topological signatures that characterize the different topological perspectives of input graph: Graph-UTS characterizes “What topological structure is present in input graph”, while Embedding-UTS tells “How that topological structure is reflected in the learned representations”. 4.1.1
Embedding-UTS
Given the node embedding matrix H(l) ∈ Rn×dl at layer l in GNN, we interpret its rows as a point cloud in the learned representation space and compute an embedding signature Φemb : Rn×d → R14 which summarizes the geometry of the embedding through geometric, persistent homology, and spectral descriptors. We use two variants of this signature depending on whether gradients must propagate through it: an exact variant, computed via standard persistent homology and eigendecomposition, used where the signature serves only as a static input feature (UTS-Aug, §4.2); and a differentiable surrogate, denoted Φdiff emb , which replaces these exact operations with differentiable relaxations and is used wherever the signature must be trained through (UTS-Reg, §4.3; UTS-Pool, §4.4). Both variants share the feature structure below. The resulting embedding descriptor is s(l) = Φemb H(l) = ℓ̄(0) , H (0) , ℓ̄(1) , H (1) , β0 , β1 , µnn , σnn , ∆, dˆ, λ1 , λ2 , λ3 , Hspec ∈ R14 . (2) | {z } | {z } | {z } persistence
local geometry
spectral
Here ℓ̄(k) , H (k) , and βk denote the mean lifetime, persistence entropy, and Betti number of kdimensional homology; µnn and σnn are the mean and standard deviation of k-NN distances; ∆ is the diameter of point cloud P; dˆ estimates its intrinsic dimensionality; and λ1 ≤ λ2 ≤ λ3 with Hspec are the smallest eigenvalues and spectral entropy of a Laplacian. For Φemb , βk and the Laplacian are computed exactly; for Φdiff emb , both are differentiable relaxations (soft Betti numbers, a regularized Laplacian). Complete derivations of both variants are provided in Appendix A.2. 4.1.2
Graph-UTS
Complementary to the embedding signature, we compute a static graph signature directly from the input topology, Φgrph : G → R27 which is evaluated once for every graph and cached throughout training. The graph signature combines curvature, persistent homology, spectral, distance, and structural statistics into a compact topological representation, g = Φgrph (G) =
(0)
(0)
(1)
(1)
G G ϕORC , ϕFRC , ℓ̄G , diam(G), λG 2 , λn , Hspec , ℓ̄G , HG , ℓ̄G , HG , ϕstruct | {z } | {z } | {z } | {z } {z } | curvature
distance
spectral
persistence
∈ R27 .
structural
(3)
Here ϕORC , ϕFRC ∈ R4 summarize Ollivier–Ricci and Forman–Ricci edge curvatures; ℓ̄G and G G diam(G) are the mean shortest-path length and diameter of graph; λG 2 , λn , and Hspec are the algebraic connectivity, largest eigenvalue, and spectral entropy of the combinatorial Laplacian; (k) (k) ℓ̄G and HG are exact k-dimensional persistence lifetimes and entropies; and ϕstruct ∈ R10 4
Input graph
Input Graph G Φemb (Hfinal )
Input Graph G
GIN Layer 1
s(1)
GIN Final layer Readout Vector zstruct
Prevent abrupt
Φgrph (G) GIN Layer 2
Φgrph (G)
GIN Layer 1..L
topological s(2)
representation
UTS-Pool
across layers GIN Layer L
z = [zstruct ∥ Φgrph ∥ Φemb ]
s(L)
(Eq.5)
Readout (SUM+MEAN+MAX)
Topology
Classifier MLP
(a) UTS-Aug
alignment (Eq.4)
Classifier MLP
(b) UTS-Reg
(c) UTS-Pool
Figure 2: Overview of Dual-UTS interventions applied on the baseline GIN architecture.
collects elementary structural statistics including betweenness centrality, clustering coefficients, and more. Complete feature definitions are provided in Appendix A.3. Unlike Φemb , this descriptor is independent of the learned embeddings and therefore remains unaffected by message passing or oversmoothing. 4.2
UTS-Aug: Topology-Enhanced Graph Representation
We augment the graph representation obtained from conventional readout with the topological signatures introduced in Section 4.1.2. Graph-UTS Φgrph encodes the intrinsic topology of the input graph and remains invariant throughout optimization, whereas Embedding-UTS Φemb captures the evolving topological information of intermediate representations during message passing. Let zstruct ∈ Rd denote the graph representation obtained from the underlying GNN through a standard permutation-invariant readout. The proposed topology-aware representation is constructed by concatenating the graph signature and embedding signature of last layer, h i z = zstruct ∥ Φgrph (G) ∥ Φemb (H(l) ) , where ∥ denotes vector concatenation. The augmented representation z is subsequently passed to the graph classifier. To isolate the contribution of each signature, we additionally evaluate single-signature variants by concatenating zstruct with either Φgrph or Φemb alone in section 5.2. 4.3
UTS-Reg: Topology-Preserving Regularization
While UTS-Aug augments the final graph representation with explicit topological information, it does not constrain the evolution of topology during message passing. UTS-Reg addresses this through two regularization objectives: (i) aligning the topology of final embedding space with the intrinsic topology of input graph, and (ii) enforcing topological consistency across successive GNN layers. Together, these objectives preserve structural fidelity, reduce representation collapse and thus mitigate oversmoothing throughout optimization. Topological Alignment Loss. Since, the graph signature Φgrph (G) and embedding signature (L) Φdiff ) reside in different feature spaces, we learn a linear projection Walign ∈ R14×27 to map emb (H the graph-signature into the embedding-signature space and minimize: N
2 1 X diff (L) Ltopo−align = Φemb (Hi ) − Walign Φgrph (Gi ) , N i=1 2
(4)
where Walign is jointly optimized with the GNN. Since Φgrph is fixed, gradients propagate only through Φdiff emb and Walign , encouraging the learned embedding topology to align with the intrinsic topology of the input graph. Topological Evolution Loss. We additionally penalize abrupt topological changes across successive (l) message-passing layers. Let s(l) = Φdiff denote the embedding signature at layer l. The emb H 5
layer-wise smoothness objective is L−1
Ltopo−evol =
2 1 X (l) s − s(l−1) , L−1 2
(5)
l=1
which acts as a fitting constraint and encourages smooth topological transitions across layers i.e., do not change the topology too much from the initial one, preventing representation collapse and oversmoothing. Total Training Objective: The final optimization objective combines the task loss with both topologypreserving regularizers, L = Ltask + Ltopo−align + Ltopo−evol , 4.4
(6)
UTS-Pool: Topology-aware pooling
Existing graph pooling methods [1, 11, 27] rank nodes using feature activations or attention scores, emphasizing local semantic relevance without explicitly accounting for local topological structure. In our work, we rank nodes based on the topological richness of their embedding neighborhoods, utilizing a differentiable version of Φemb which preserves structurally critical regions during graph coarsening. In addition, we also propose a lightweight geometric approximation of node scoring on large dense graphs to improve scalability. Topology-Aware Node Scoring. For each node v, let HN (v) = {hu : u ∈ N (v) ∪ {v}} denote the embeddings within its one-hop neighborhood. We compute a local topological signature and transform it into an importance score, αv = σ fθ Φdiff , emb (HN (v) ) where fθ : R14 → R is a two-layer MLP, σ(.) is non-linear function and Φdiff emb denotes differentiable embedding signature (details in Appendix A.4). The top-k= ⌊ρn⌋ out of n nodes are retained, V ′ = top-k({αv }v∈V ), where ρ denotes the pooling ratio. The pooled graph G′ = (V ′ , E ′ , H′ ) is obtained by preserving edges between retained nodes and projecting the corresponding node embeddings, H′ = ReLU(Wproj H[V ′ ]).
(7)
Efficient Variant for Large Graphs. Computing the embedding signature in large dense graph is becomes computationally expensive owing to large scale persistent homology, triangle enumeration, and spectral computations for every node neighborhood. To improve scalability, we introduce a lightweight geometric approximation that replaces the full signature with five differentiable local descriptors, v ϕlight = [µvnn , σnn , ∆v , r̄1v , |N (v)|/kmax ] ∈ R5 , v
(8)
where each quantity is computed within the local neighbourhood of v. The resulting scorer reduces the computational cost from cubic topological computations to local quadratic operations while preserving the geometric characteristics most relevant for node ranking. During training, neighbourhoods are processed in chunks of size C (default C = 64), bounding peak GPU memory usage to O(Cd) independent of graph size. The lightweight scorer ϕlight (Eq. 8) is a geometric proxy for the full embedding signature Φdiff v emb We treat this approximation rigorously in Appendix C, where we show that ϕlight certifies an explicit v scale window, noise floor, and dimension cap governing when a node’s local neighbourhood can carry nontrivial persistent topology at all — i.e. the conditions under which the full topological computation would be uninformative and the lightweight proxy suffices. 6
Table 1: Accuracy comparison of UTS-Aug GIN backbone with Φemb , Φgrph , or both (Dual UTS), with the unmodified GIN. Red and Grey mark the best and second best variants. Teal column: ogbg-ppa, official OGB split, accuracy in percentage points. ∗ p < 0.05, ∗∗ p < 0.01, ∗∗∗ p < 0.001 (paired t-test vs. unmodified GIN); unmarked values are not significant. Full statistics in Appendix B. Variant
MUTAG
PROTEINS
COLLAB
ogbg-ppa
GIN (unmodified) 0.832 ± 0.084 0.740 ± 0.034 0.810 ± 0.029 67.84 ± 0.917 UTS-Aug GIN Embedding-UTS 0.872 ± 0.079 0.751 ± 0.031∗ 0.823 ± 0.028∗∗ 69.27 ± 0.903∗ Graph-UTS 0.890 ± 0.076 0.759 ± 0.040∗ 0.832 ± 0.029∗∗ 70.20 ± 0.951∗∗ Dual UTS 0.878 ± 0.078 0.763 ± 0.036∗ 0.837 ± 0.028∗∗∗ 71.06 ± 0.934∗∗
5
Experiments and Results
5.1
Experimental Protocol
We evaluate the proposed modified GIN framework using three UTS interventions (UTS-Aug, UTSReg, UTS-Pool) and perform experiments on four graph classification benchmarks spanning molecular (MUTAG), biological (PROTEINS), social-network (COLLAB), and large-scale biological (ogbgppa) domains. Details are provided in Appendix A.6. In Table 1 and Table 2, the proposed UTS-Aug and UTS-Reg interventions are compared against the unmodified GIN (GIN with only standard readout features, zstruct ) and unregularized GIN (GIN trained with task-specific objective, Ltask only) variants respectively. In Table 3, modified GIN with UTS-Pooling is compared with three pooling baselines, TopKPool [2], SAGPool [15], and TOGL [13]. Across all four benchmarks, the GIN backbone is trained under identical experimental settings (hidden size 128, readout dimension 384) to isolate the contribution of the proposed topology-aware components. For MUTAG, PROTEINS, and COLLAB, which lack a standardized split, we employ 10-fold stratified cross-validation, using 9 seeds for MUTAG and 5 seeds for PROTEINS and COLLAB. Each fold uses a 90/10 train-test split, with 10% of the training set further held out for validation. For ogbg-ppa, we instead use the official, externally-fixed OGB species split [14] and report mean ± std over multiple seeds, following standard OGB leaderboard convention; this split holds out entire species unseen during training, testing out-of-distribution generalization rather than in-distribution accuracy. Full aggregate statistics, including confidence intervals and paired-significance p-values for all four datasets, are provided in Appendix B. The GIN backbone uses four layers for MUTAG and PROTEINS, three layers for COLLAB to mitigate oversmoothing in dense social graphs, and three layers for ogbg-ppa given its large average graph size (243.4 nodes). We report the mean and standard deviation of the classification accuracy (mean ± std) across all folds and seeds (TU datasets) or all seeds (ogbg-ppa). To ensure a fair comparison, all GIN variants are trained using identical hyperparameters and optimization settings, with only the proposed topology-aware components varying across the experiments. 5.2
Effect of Dual Unified Topological Signatures as UTS-Aug
Table 1 summarizes the classification performance of GIN augmented with each signature individually and jointly, under the updated 10-fold CV protocol (MUTAG/PROTEINS/COLLAB) and the official OGB split (ogbg-ppa). Graph-UTS achieves the best performance on MUTAG (+5.8% over unmodified GIN, not statistically significant at this sample size), while Dual-UTS achieves the best performance on PROTEINS (+2.3%, significant), COLLAB (+2.6%, significant), and ogbg-ppa (+3.22 points, significant), with Graph-UTS second-best on all three. The two signatures are complementary on PROTEINS, COLLAB, and ogbg-ppa, with their combination outperforming either individually, while Graph-UTS alone remains strongest specifically on the smaller, sparser MUTAG graphs. The effectiveness of Φemb alone is more modest than that of the graph signature but is positive across all datasets: it improves over the unmodified GIN on MUTAG (+4.0%, not significant), PROTEINS (+1.1%, significant), COLLAB (+1.3%, significant), and ogbg-ppa (+1.43 points, significant). Combining both signatures (Dual-UTS) achieves the best performance on PROTEINS, COLLAB, and ogbg-ppa, demonstrating that the static and dynamic signatures provide complementary structural 7
information on these datasets, while Graph-UTS alone remains the strongest single descriptor on MUTAG. Notably, the descriptor gains on ogbg-ppa hold under a species-level train/test split that requires generalizing to entirely unseen species, suggesting the topological signal captured by UTS is not merely fitting to species-specific idiosyncrasies present in the training distribution. 5.3
Effect of UTS-Reg (Topology-Preserving Regularization)
The previous experiment showed that Embedding-UTS is sensitive to representation quality. We therefore evaluate whether UTS-Reg improves it by preserving topological fidelity during optimization. Table 2 shows the two regularizers behave complementarily: the evolution loss gives the largest gain on MUTAG (+1.9%, not significant), while the alignment loss performs best on PROTEINS (+1.4%, significant) and on ogbg-ppa (+1.70 points, significant). Neither loss improves over baseline on COLLAB, and both individual losses are significantly negative there, indicating the benefit of topology-preserving supervision is dataset dependent – consistent with the layer-wise Oversmoothing Index analysis in Appendix D, which shows the same evolution loss reduces representation collapse on MUTAG but increases it on PROTEINS and COLLAB. On ogbg-ppa, all three loss variants improve over baseline and are significant, unlike on COLLAB; we discuss this cross-dataset inconsistency further in §B.5. We discuss the theoretical implications of this dataset-dependence in Section 6. Table 2: Comparison of UTS-Reg GIN backbone trained with the topological evolution loss (Ltopo−evol ), the topological alignment loss (Ltopo−align ), and their combination, with the unregularized GIN. Red and Grey mark the best and second best variant. Teal column: ogbg-ppa. Significance markers as in Table 1, paired vs. unregularized GIN. Full statistics in Appendix B. Variant
MUTAG
PROTEINS
COLLAB
ogbg-ppa
GIN (unregularized) 0.832 ± 0.084 0.740 ± 0.034∗ 0.810 ± 0.029∗ 67.84 ± 0.917∗ 0.850 ± 0.085 0.738 ± 0.034 0.805 ± 0.030 68.36 ± 0.982 UTS-Reg GIN Ltopo−evol Ltopo−align 0.842 ± 0.088 0.755 ± 0.033∗ 0.806 ± 0.030∗ 69.54 ± 0.941∗ Combination 0.841 ± 0.084 0.736 ± 0.035∗ 0.809 ± 0.032∗ 68.15 ± 1.006∗
Combining both regularizers, moreover, does not consistently outperform either alone, indicating that the two losses contribute differently across graph domains and their interaction requires datasetspecific balancing. This mirrors Section 5.2, where the embedding signature proved more sensitive to representation quality than the graph signature. On ogbg-ppa, the combination is also weaker than the alignment loss alone, though it remains significantly positive, unlike the negative combination effect observed on PROTEINS and COLLAB. 5.4
Evaluation of UTS-Pool (Topology-aware pooling)
Table 3 compares UTS-Pool against TOGL, SAGPool, and TopKPool under the same stratified 10fold CV protocol (MUTAG/PROTEINS/COLLAB) and the official OGB split (ogbg-ppa). UTS-Pool achieves the best mean accuracy on PROTEINS and COLLAB, with the advantage over TopKPool and SAGPool statistically significant on both datasets, and a smaller but still significant advantage over TOGL (+0.1 percentage points on both). On MUTAG, TOGL is nominally ahead of UTS-Pool (0.840 vs. 0.835), though the difference does not reach significance; UTS-Pool remains ahead of SAGPool and TopKPool on MUTAG, but this gap is likewise not significant. On ogbg-ppa UTS-Pool remains significantly ahead of SAGPool and TopKPool on ogbg-ppa. TOGL is slightly but signficantly better than UTS-Pool (68.97 vs. 68.85, ∆ = −0.12, p = 0.0008). Notably, the COLLAB gains are obtained using the lightweight geometric scorer ϕlight , demonstrating that even a computationally v efficient local geometric proxy provides sufficient structural information to guide scalable and robust graph coarsening – the same lightweight scorer is used for UTS-Pool on ogbg-ppa, given its even larger average graph size (243.4 nodes). Finally, Figure 3 illustrates the evolution of representative components of the embedding signature across GIN layers on the MUTAG dataset. As message passing progresses, the H0 mean lifetime decreases from 9.08 to 3.51, while the spectral gap λ1 shrinks from 1.26 to 0.81, indicating progressive contraction of the embedding topology associated with oversmoothing. In contrast, the H1 mean lifetime remains nearly unchanged, suggesting that higher-order topological structure is largely preserved. These trends demonstrate that UTS provides an interpretable characterization of 8
Table 3: Accuracy comparison of UTS-Pool against TOGL, TopKPool, and SAGPool, same GIN backbone. Red and Grey mark the best and second best variant. Teal column: ogbg-ppa. ∗ p < 0.05, ∗∗ p < 0.01, ∗∗∗ p < 0.001 (paired t-test, variant vs. UTS-Pool); unmarked values are not significant. Full statistics in Appendix B. † Our faithful reimplementation of TOGL [13], adapted to this codebase; see Appendix E for implementation details. Variant TopKPool SAGPool TOGL† UTS-Pool
MUTAG 0.829 ± 0.079 0.831 ± 0.080 0.840 ± 0.083 0.835 ± 0.079
PROTEINS ∗∗∗
0.741 ± 0.033 0.742 ± 0.034∗∗ 0.744 ± 0.033∗ 0.745 ± 0.033
COLLAB
ogbg-ppa ∗
0.818 ± 0.029 0.819 ± 0.029∗ 0.820 ± 0.029∗ 0.821 ± 0.029
67.53 ± 0.988∗∗∗ 67.88 ± 0.963∗∗∗ 68.97 ± 0.926∗∗∗ 68.85 ± 0.891
Figure 3: Evolution of some components of embedding signature (Φemb ) across GIN layers on the MUTAG dataset. The sharp decay in H0 mean lifetime and the shrinking spectral gap (λ1 ) empirically diagnose representation collapse, where distinct node embeddings oversmooth into an indistinguishable manifold
representation dynamics during GNN optimization. Further details on the proposed Oversmoothing Index (OSI) formulation, implementation, and experimental analysis are provided in Appendix D.
6
Theoretical Analysis
We now establish the theoretical properties of the proposed framework. Complete proofs are deferred to Appendix C. 6.1
Expressive Power of Dual Unified Topological Signatures
Theorem 1. Let A denote a message-passing GNN whose expressive power is bounded by the 1-Weisfeiler–Lehman (1-WL) test. Augmenting A with the graph signature Φgrph yields a graph representation capable of distinguishing graph pairs that are indistinguishable under the 1-WL test whenever their global topological signatures differ. 6.2
Topology-Preserving Regularization
Proposition 1 (Topo-Evolution Loss: Heuristic Motivation). The topo-evolution loss Lsmooth (Eq. 5) heuristically discourages representation collapse by penalizing layer-to-layer divergence of the embedding-space topological signature s(l) . This is a first-order, directional argument, not a proof that Lsmooth enforces a variance bound or guarantees reduced Oversmoothing Index (Eq. 30); the effect is empirically dataset-dependent (see Appendix C.2 for the full justification and OSI comparison across datasets). 6.3
Computational Complexity
The graph signature Φgrph is computed once per graph and cached, while the embedding signature 3 Φdiff emb is recomputed at every layer, both at cost O(n ) dominated by persistence and spectral 9
computations. The lightweight pooling proxy ϕlight reduces this to O(d n δ̄ 2 ) per pooling layer, linear v in n at fixed local density. A full derivation is given in Appendix C.4.
7
Conclusion and Future Work
We introduced a unified topology-aware framework for graph representation learning based on Dual Unified Topological Signatures, jointly modeling the intrinsic topology of the input graph and the evolving topology of the learned embedding space throughout the GNN pipeline. Topology improves graph learning through three complementary mechanisms: topology-augmented representations, topology-preserving regularization, and topology-aware hierarchical pooling, with consistent improvements over the GIN backbone across molecular, biological, and social-network benchmarks. Future work includes differentiable relaxations of the UTS-Pool selection operator and extending the framework to heterogeneous and temporal graph learning. The full Embedding-UTS signature incurs O(n³)-per-layer cost, which limits its direct application to long-range or web-scale graph benchmarks; developing a more computationally efficient variant of the signature is a natural direction for extending this work to such settings.
References [1]
[2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]
[15]
[16] [17] [18]
F. M. Bianchi, D. Grattarola, and C. Alippi. “Spectral clustering with graph neural networks for graph pooling”. In: Proceedings of the 37th International Conference on Machine Learning. ICML’20. 2020. 1, 3, 6 C. Cangea et al. “Towards Sparse Hierarchical Graph Classifiers”. In: NeurIPS Workshop on Relational Representation Learning (R2L). 2018. 7, 26 G. Carlsson and F. Mémoli. “Characterization, Stability and Convergence of Hierarchical Clustering Methods”. In: Journal of Machine Learning Research 11 (2010). 22 F. Chazal et al. “Gromov-Hausdorff Stable Signatures for Shapes using Persistence”. In: Computer Graphics Forum (Proc. SGP 2009). Vol. 28. 5. 2009. 22 Y. Chen and Y. R. Gel. “Topological Pooling on Graphs”. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. 6. 2023. 2, 3 D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. “Stability of Persistence Diagrams”. In: Discrete & Computational Geometry 37.1 (2007). 22 M. Cuturi. “Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances”. In: Advances in Neural Information Processing Systems 26 (NIPS 2013). 2013. 13 H. Edelsbrunner, D. Letscher, and A. Zomorodian. “Topological Persistence and Simplification”. In: Discrete & Computational Geometry 28.4 (2002). 2 A. Feng and M. Weber. “Graph Pooling via Ricci Flow”. In: Transactions on Machine Learning Research (2024). 2, 3 R. Forman. “Bochner’s Method for Cell Complexes and Combinatorial Ricci Curvature”. In: Discrete and Computational Geometry 29 (2003). 13 D. Grattarola et al. “Understanding Pooling in Graph Neural Networks”. In: IEEE Transactions on Neural Networks and Learning Systems 35.2 (2024). 1, 3, 6 W. L. Hamilton, R. Ying, and J. Leskovec. “Inductive Representation Learning on Large Graphs”. In: Advances in Neural Information Processing Systems. Vol. 30. 2017. 1, 3 M. Horn et al. “Topological Graph Neural Networks”. In: International Conference on Learning Representations (ICLR). 2022. 3, 7, 9, 26 W. Hu et al. “Open graph benchmark: datasets for machine learning on graphs”. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. NIPS ’20. Vancouver, BC, Canada, 2020. 7, 16 J. Lee, I. Lee, and J. Kang. “Self-Attention Graph Pooling”. In: Proceedings of the 36th International Conference on Machine Learning. Ed. by K. Chaudhuri and R. Salakhutdinov. Vol. 97. Proceedings of Machine Learning Research. 2019. 7, 26 Q. Li, Z. Han, and X.-M. Wu. “Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning”. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. 2018. 1 I. Loshchilov and F. Hutter. “Decoupled Weight Decay Regularization”. In: International Conference on Learning Representations (ICLR). 2019. 15 C. Morris et al. “TUDataset: A collection of benchmark datasets for learning with graphs”. In: ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020). 2020. 16
10
[19] [20] [21]
C.-C. Ni et al. “Community Detection on Networks with Ricci Flow”. In: Scientific Reports 9.1 (2019). 13 Y. Ollivier. Ricci curvature of Markov chains on metric spaces. 2007. 2, 3, 13 K. Oono and T. Suzuki. “Graph Neural Networks Exponentially Lose Expressive Power for Node Classification”. In: International Conference on Learning Representations (ICLR). 2020. 1 T. G. Project. GUDHI User and Reference Manual. 3.12.0. 2026. 12, 14, 23 F. Rottach et al. From Topology to Retrieval: Decoding Embedding Spaces with Unified Signatures. 2025. 2, 3 T. K. Rusch, M. M. Bronstein, and S. Mishra. “A Survey on Oversmoothing in Graph Neural Networks”. In: arXiv preprint arXiv:2303.10993 (2023). 3 Z. Wang and J. Fan. “Graph Classification via Reference Distribution Learning: Theory and Practice”. In: Advances in Neural Information Processing Systems. Vol. 37. 2024. 3 K. Xu et al. “How Powerful are Graph Neural Networks?” In: International Conference on Learning Representations. 2019. 2, 3, 16, 19 R. Ying et al. “Hierarchical Graph Representation Learning with Differentiable Pooling”. In: Advances in Neural Information Processing Systems. Vol. 31. 2018. 1, 3, 6
[22] [23] [24] [25] [26] [27]
A
Appendix
A.1
Full Derivations of Universal Topological Signatures
This appendix gives the complete definitions, differentiability remarks, and computational notes underlying the embedding- and graph-level signature maps introduced in Section 4.1.1 and Section 4.1.2. A.2 A.2.1
Embedding UTS: Φemb Pairwise Distance Matrix v u dl uX Duv = ∥hu − hv ∥2 = t (hui − hvi )2 + ε,
ε = 10−8 ,
(9)
i=1
where ε ensures numerical stability when hu = hv (in case of oversmoothing). A.2.2
Local Geometry Features (Dimensions 7–10)
Let Nk (v) denote the k nearest neighbours of node v excluding itself. Define 1X1 X Dvu , n k v∈V u∈Nk (v) v u u 1 X X 2 (Dvu − µnn ) , σnn = t nk v
µnn =
(10)
(11)
u∈Nk (v)
∆ = max Duv ,
(12)
log r2 (v) + ε dˆ = medianv∈V , log r1 (v) + ε
(13)
u,v∈V
where rj (v) is the distance to the j-th nearest neighbour of v. Equation (13) provides a correlationdimension estimate of the intrinsic dimensionality of the embedding manifold, and is used as written for Φemb (exact). Remark on Differentiability. µnn , σnn , and ∆ (10)–(12) are differentiable with respect to H(l) through (9) in both variants. The median in (13), however, has a degenerate gradient (non-zero only at the median element), so Φdiff emb replaces it with a mean over the same log-ratio, distributing gradient across all n nodes; see Appendix A.4 for the full justification. 11
A.2.3
Persistence Features (Dimensions 1-6)
For Φemb (exact), dimensions 1-6 are computed via standard Vietoris–Rips persistent homology on the detached point cloud using GUDHI [22] - identical in construction to the persistence features of Φgrph (§A.3), yielding exact mean lifetimes, persistence entropies, and integer Betti numbers β0 , β1 . For Φdiff emb , these exact operations are replaced by the differentiable relaxations below, since MST extraction and simplicial homology computation are not differentiable. Let {we } denote the upper-triangular entries of D, sorted in ascending order as w(1) ≤ w(2) ≤ · · · ≤ w(n) . We define the H0 lifetime surrogate as the n − 1 smallest edge weights: 2 (0)
ℓi
= w(i) ,
i = 1, . . . , n − 1.
(14)
This approximates the persistence diagram of the 0-dimensional homology of the Vietoris–Rips complex: in an exact Rips filtration, connected components merge at minimum spanning tree edge weights. Equation (14) is a differentiable relaxation since MST extraction (Kruskal’s algorithm) is non-differentiable. For 1-dimensional homology we enumerate all triangles V3 and define, for each triangle τ = (u, v, w) with sorted edge lengths e1 (τ ) ≤ e2 (τ ) ≤ e3 (τ ), ℓ(1) τ = max(0, e3 (τ ) − e2 (τ )) .
(15)
This follows from the Vietoris–Rips persistence pairing: a 1-cycle is born when the second-longest triangle edge enters the filtration and dies when the longest edge fills the triangle. Remark 1 (When are surrogates used?). Surrogates (Φdiff emb ) are used only where gradients must propagate through the signature: the topology-preserving regularizers (§4.3) and the UTS-Pool node scorer (§4.4). UTS-Aug (§4.2) uses the exact signature Φemb , computed on detached embeddings with no gradient requirement. See Appendix A.4 for the complete differentiable-surrogate derivation. Remark 2 (Computational cost of H1). Triangle enumeration scales as O(n3 ). We cap computation at n ≤ nmax (default nmax = 50); for larger point clouds the H1 features are set to zero. This is appropriate for large social network graphs (e.g. COLLAB) where oversmoothing renders the embedding point cloud near-degenerate in any case. This cap applies to Φdiff emb wherever it is computed per layer – both the topology-evolution loss (§4.3) and the UTS-Pool node scorer (§4.4) – and does not apply to UTS-Aug, which uses the exact signature Φemb computed once on detached embeddings. From (14) and (15) we compute mean lifetimes and persistence entropies: 1 X (k) ℓ̄(k) = (k) ℓ , |L | i i
(16)
(k)
H (k) = −
X (k) (k) p̂i log p̂i , i
(k)
p̂i
=P
ℓi
(k) j ℓj + ε
.
(17)
Soft Betti numbers are defined as β̃k =
X (k) σ 10 ℓi − µnn ,
(18)
i
where σ is the sigmoid function and µnn serves as an adaptive threshold. A.2.4
Spectral Features (Dimensions 11–14)
For Φemb (exact), the adjacency is a standard binary k-NN graph and L̃ is the unnormalised combinatorial Laplacian, with eigenvalues computed via scipy.linalg.eigh; no soft kernel or regularisation is applied, since differentiability is not required. For Φdiff emb , we construct a soft k-NN adjacency matrix via a Gaussian kernel instead, to keep the spectral features differentiable: Construct a soft k-NN adjacency matrix via a Gaussian kernel: 2 Duv Asoft = exp − · 1[u ̸= v]. uv 2(µnn + ε)2 12
(19)
The bandwidth µnn is kept in the computation graph (not detached), ensuring gradients flow through the spectral features back to H(l) . Let Lsoft = Dsoft − Asoft be the unnormalised Laplacian, regularised as Lsoft + δI L̃ = , δ = 10−4 , (20) maxv dsoft +ε v P soft where dsoft = u Asoft normalises the matrix to [0, 1] scale, preventing v uv . Division by maxv dv ill-conditioning on dense graphs (e.g. COLLAB with d¯ ≈ 8.9). Let 0 ≤ λ1 ≤ λ2 ≤ · · · ≤ λn be the eigenvalues of L̃, computed via torch.linalg.eigh (fully differentiable for symmetric matrices). The spectral gap λ1 , and λ2 , λ3 approximate the Fiedler value and higher connectivity information. Spectral entropy is X max(λi , ε) . (21) Hspec = − q̂i log q̂i , q̂i = P j max(λj , ε) i Stability. The spectral entropy Hspec is Lipschitz continuous in the entries of L̃ by the Weyl perturbation theorem and the Lipschitz continuity of the entropy function on the probability simplex. A.3 A.3.1
Graph UTS: Φgrph Ollivier-Ricci Curvature (Dimensions 1-4)
For an edge (u, v) ∈ E, the Ollivier-Ricci curvature [20] is κ(u, v) = 1 −
W1 (µu , µv ) , dG (u, v)
where dG (u, v) is the geodesic distance, µv is the α-lazy random walk measure at v: w=v α µv (w) = (1 − α)/ deg(v) (v, w) ∈ E 0 otherwise,
(22)
(23)
and W1 (µu , µv ) is the Wasserstein-1 distance computed via the Sinkhorn approximation [7]: W1ε (µu , µv ) ≈ ⟨u ⊗ K ⊙ C ⊗ v⟩,
(24)
where K = exp(−C/ε) is the Gibbs kernel, C is the cost matrix of geodesic distances restricted to the supports of µu and µv , and u, v are Sinkhorn scaling vectors. This replaces the C++ implementation of [19], eliminating segmentation faults on varied graph sizes while remaining differentiable through the Sinkhorn iterations if required. From the edge curvatures {κe }e∈E we extract |{e : κe < 0}| ϕORC = κ̄, Var(κ), min κe , ∈ R4 . e |E|
(25)
Edges with κe > 0 lie within dense clusters; edges with κe < 0 are inter-cluster bridges. The fraction of negatively curved edges thus serves as a proxy for community structure [19]. A.3.2
Forman-Ricci Curvature (Dimensions 5-8)
The combinatorial Forman-Ricci curvature [10] of an edge e = (u, v) is r r X X w w w w u v e e + − − F (e) = we , ′ ′ we we w w e e ′ ′ ′ ′ e ∼u,e ̸=e
(26)
e ∼v,e ̸=e
where we , wv are edge and vertex weights (unity for unweighted graphs). We extract ϕFRC = [F̄ , Var(F ), mine Fe , maxe Fe ] ∈ R4 . A.3.3
Distance Features (Dimensions 9-10)
Let ℓG (u, v) denote the shortest-path Pdistance in the largest connected component of G. We extract 1 the mean path length ℓ̄G = n(n−1) u̸=v ℓG (u, v) and diameter diam(G) = maxu,v ℓG (u, v). 13
A.3.4
Spectral Features (Dimensions 11-13)
G Let LG = DG − A be the combinatorial graph Laplacian and 0 = λG 1 ≤ λ2 ≤ · · · its eigenvalues. We extract the Fiedler value λG (algebraic connectivity), the largest eigenvalue λG n , and spectral 2 G entropy Hspec , computed by the same entropy formula as Hspec (Eq. 2’s spectral group) but applied directly to the exact eigenvalues of LG above – no soft kernel or regularisation is used, since Φgrph requires no gradient (§A.3, Persistence Features).
A.3.5
Persistence Features (Dimensions 14-17)
Applying the Vietoris-Rips filtration to the shortest-path distance matrix (ℓG (u, v))u,v via GUDHI [22], we extract mean lifetimes and persistence entropies of H0 and H1 homology groups, computed exactly (not surrogates) since Φgrph is non-differentiable by design. A.3.6
Structural Features (Dimensions 18-27)
¯ Var(d), maxv dv ], clustering coefficients [c̄, Var(c)], betweenness centrality Degree statistics [d, [b̄, Var(b)], mean closeness centrality q̄, number of connected components Ncc , and largest component ratio |Cmax |/n. A.4
Differentiable Surrogate Formulation of Φemb
The readout descriptor (§4.1) computes Φemb on H(L) .detach() using GUDHI for exact persistent homology. However, the regularisation losses (§4.2) and pooling scorer (§4.3) require gradients to flow back through the topological signature into the GIN encoder. We therefore maintain a fully differentiable re-implementation, Φdiff emb , in PyTorch (diff_uts.py) that produces the same 14-dimensional vector as Φemb without any NumPy or GUDHI operations. The two implementations agree closely on well-separated point clouds and diverge gracefully in the oversmoothing regime where exact persistence is ill-defined regardless. Below we justify each non-obvious design choice. Pairwise distances.
We compute qP 2 Duv = i (hui − hvi ) + ε,
ε = 10−8 ,
(27)
rather than torch.cdist. The gradient of cdist at Duv = 0 is undefined when hu = hv , which occurs frequently in early training before the encoder has differentiated nodes. The ε inside the square root regularises the gradient to ∂Duv /∂hu = (hu − hv )/Duv , which remains bounded. H0 surrogate. Exact H0 persistence requires a minimum spanning tree. MST extraction (Kruskal’s algorithm) involves argsort whose gradient is non-unique at ties and propagates to only one entry per comparison. We use the N −1 smallest upper-triangle pairwise distances w(1) ≤ . . . ≤ w(N −1) as a differentiable proxy for component lifetimes (cf. Eq. 14). This approximation is tight when the point cloud is well-separated: in an exact Rips filtration, components merge precisely at MST edge weights, which are the N −1 smallest distances when no two inter-component distances are equal. The gradient of torch.sort is well-defined (it equals the identity on the sorted entries) and distributes across the source entries. (1) H1 surrogate. We enumerate all N3 triangles and compute per-triangle lifetimes ℓτ = max(0, e3 (τ ) − e2 (τ )) where e2 , e3 are the second- and third-longest edge lengths of triangle τ (cf. Eq. 15). This quantity is an upper bound on the true H1 lifetime in the Vietoris–Rips filtration: under Rips, a 1-cycle is born at most when the second-longest triangle edge enters and dies when the longest edge fills the triangle. Triangle enumeration is O(N 3 ) in memory; we cap it at N ≤ 50, setting ℓ̄(1) = H (1) = β̃1 = 0 for larger point clouds. For the datasets in our experiments, only COLLAB graphs exceed this threshold after the 2-hop neighbourhood cap of 30 nodes is applied in §4.3. Soft Betti numbers. The exact Betti numbers βk are integers and non-differentiable. We replace P (k) them with sigmoid-smoothed counts β̃k = j σ(10(ℓj − µnn )), where the threshold µnn adapts 14
to the point cloud density and the scale factor 10 provides sharpness comparable to a step function while keeping gradients non-zero. Spectral features. The binary k-NN adjacency used in the non-differentiable Φemb is replaced by a 2 2 Gaussian kernel adjacency Asoft uv = exp(−Duv /2(µnn + ε) ) · 1[u ̸= v] (cf. Eq. 19). The bandwidth µnn remains in the computation graph so gradients flow through the spectral features. We add 10−6 I to the adjacency before forming the Laplacian to prevent degenerate (zero) diagonal entries that cause NaN in torch.linalg.eigh. We use eigh rather than eig: for symmetric matrices it guarantees real eigenvalues and implements the analytic gradient ∂λi /∂L = qi q⊤ i via the eigenvalue equation, which is numerically stable for distinct eigenvalues. (2)
(1)
Intrinsic dimensionality. We use mean rather than median over the log-ratio log ri / log ri (cf. Eq. 13). The gradient of median is non-zero only at the median element, making it effectively a single-node pass-through and providing no useful learning signal. The mean distributes gradient uniformly across all N nodes. A.5
Architecture and Training Details
Full readout dimensionalities. The classifier MLP input dimension varies by ablation variant. With d = 128 (hidden dim), the base readout zstruct ∈ R3d=384 . Appending Φemb adds 14 dimensions; appending Φgrph adds 27 dimensions. Table 4 summarises the classifier input dimension and the number of parameters in the classifier head per variant (backbone parameters are identical across all variants). Table 4: Classifier input dimension and head parameter count per variant (d = 128, C = num classes). Backbone parameters are identical across all variants and not included. Variants GIN and UTS-Pool Embedding-UTS Graph-UTS Dual UTS
Readout dim
Head params (approx.)
384 398 411 425
384×128 + 128×64 + 64×C 398×128 + . . . 411×128 + . . . 425×128 + . . .
Crucially, UTS-Reg Ltopo−evol , Ltopo−align and combination of both objectives all share the same architecture as GIN (unregularized) baseline. Any accuracy differences between these variants and baseline are therefore attributable entirely to the training objective, not to additional model capacity. (L) TopoRegLoss projection. Φgrph (G) ∈ R27 and Φdiff ) ∈ R14 live in spaces of different emb (H 14×27 dimension and scale. The learnable projection Walign ∈ R in Lreg (Eq. 4) is trained jointly with the encoder, finding the optimal linear alignment between structural and embedding-space topology. This avoids hand-crafted feature matching while remaining interpretable: the learned projection weights reveal which structural features are most predictive of embedding-space topology.
UTS-Pool gradient flow. The node scorer in §4.3 computes importance scores αv via Φdiff emb and an MLP fθ , but the subsequent top-k selection returns integer indices. Consequently, no gradient flows back through the selection decision itself; the scorer receives gradient only indirectly from the downstream cross-entropy loss through the embeddings of selected nodes. The scorer thus acts as an adaptive heuristic rather than a fully learned selection criterion. A soft-selection relaxation (e.g. Gumbel-softmax top-k) would enable end-to-end training of the pooling decision and is left to future work.
Training protocol. All models use AdamW [17] with learning rate 10−3 and weight decay 10−4 , cosine annealing to ηmin = 10−5 over 200 epochs, and gradient norm clipping at 2.0. Early stopping with patience 30 on validation accuracy selects the final checkpoint. We use 10-fold stratified crossvalidation: for each fold, the held-out 10% serves as the test set, and the remaining 90% is further split 90/10 into training and validation sets, yielding an 81/9/10 train/validation/test split per fold, stratified by class label, with every graph evaluated as a test example exactly once per seed. 15
GraphUTS precomputation. Computing Φgrph per graph at every training step is prohibitive: it involves all-pairs shortest paths (O(n2 )), GUDHI Rips persistence, and optionally Ricci curvature. We precompute and cache Φgrph (Gi ) for all graphs before the first training epoch and look up vectors by dataset index during training. The cache is shared across all seeds and ablation variants in a single run, so the precomputation cost is paid exactly once. A.6
Dataset Statistics and Descriptions
Table 5 summarizes the three TU benchmark datasets [18] used in Section 5, spanning a molecular, a biological, and a social-network domain. Table 5: Statistics of the graph classification datasets used in our experiments. Dataset
Graphs
Classes
Avg. Nodes
Avg. Edges
Node Features
MUTAG PROTEINS COLLAB ogbg-ppa
188 1113 5000 158,100
2 2 3 37
17.93 39.06 74.49 243.4
19.79 72.82 2457.78 2266.1
7 (categorical, atom type) 3 (categorical, SSE type) none (node degree used) none (learned embedding)
MUTAG consists of 188 chemical compound graphs representing nitroaromatic and heteroaromatic compounds, with nodes as atoms and edges as chemical bonds. Node features are a 7-dimensional one-hot encoding of atom type. The binary classification task is to predict mutagenic effect on the Gram-negative bacterium Salmonella typhimurium. MUTAG is the smallest and sparsest of the three datasets, with graphs ranging from 10 to 28 nodes. PROTEINS contains 1113 graphs representing protein tertiary structures, with nodes as secondary structure elements (helices, sheets, and turns) and edges connecting elements that are sequential neighbors along the amino acid chain or spatially proximate in the folded structure. Node features are a 3-dimensional one-hot encoding of secondary structure element type. The binary classification task distinguishes enzymes from non-enzymes. Graphs are substantially larger and more variable in size than MUTAG, ranging up to 620 nodes. COLLAB is a scientific-collaboration dataset derived from ego-networks of researchers in three fields: High Energy Physics, Condensed Matter Physics, and Astro Physics, with the 3-way classification task being to predict the field from the collaboration ego-network. Nodes represent researchers and edges represent co-authorship; the dataset carries no categorical node features, so node degree is used as the input feature following standard practice [26]. COLLAB graphs are markedly denser than MUTAG or PROTEINS, with average degree an order of magnitude higher, which motivates both the reduced GIN depth (Section 5) and the lightweight pooling scorer ϕlight (Section 4.4) used for this v dataset. ogbg-ppa [14] contains 158,100 protein-protein association graphs extracted from species spanning 37 taxonomic groups, with nodes representing proteins and edges representing biologically meaningful associations (7-dimensional edge features encode association type and confidence, not used in our GIN backbone). Nodes carry no input features; following the official OGB baseline for this dataset, we use a single learnable embedding shared across all nodes. The task is 37-way taxonomic-group classification. Unlike MUTAG, PROTEINS, and COLLAB, ogbg-ppa uses an official, externallyfixed species split: validation and test graphs are drawn from species entirely unseen during training, even though each held-out species still belongs to one of the 37 training taxonomic groups. This makes ogbg-ppa an out-of-distribution generalization test rather than an in-distribution random split, and is the reason we depart from the 10-fold CV protocol used for the other three datasets (§5). ogbg-ppa’s graphs are also substantially larger than any TU dataset used in this work - more than 3× COLLAB’s average size and 32× its graph count
B
Full Ablation Results
This appendix reports full aggregate statistics for every comparison summarized in Tables 1–3. All results use 10-fold stratified cross-validation (MUTAG: 9 seeds × 10 folds = 90 evaluations per variant; PROTEINS and COLLAB: 5 seeds × 10 folds = 50 evaluations per variant). Confidence intervals are bootstrap 95% CIs (1000 resamples) unless noted as paired-difference CIs. p-values are 16
paired t-tests; the comparator for each subsection is stated in its introduction. All values below are rounded to three decimal places; deltas are computed from full-precision means before rounding, so a delta may differ slightly from the difference of the rounded means shown. We allocate seeds according to measurement variance. Under 10-fold CV, each test fold contains roughly 19 graphs for MUTAG versus 111 for PROTEINS and 500 for COLLAB - MUTAG’s per-fold accuracy estimates are inherently noisier simply because they’re averaged over far fewer graphs. Using more seeds (9 vs. 5) on the smaller, higher-variance dataset is a targeted allocation of statistical power to where it’s most needed. This is also why several MUTAG comparisons remain non-significant even at 90 total evaluations, while the same comparisons reach significance on PROTEINS/COLLAB at only 50 — the underlying noise floor, differs by dataset B.1
UTS Descriptor Variants
This subsection isolates the effect of adding Unified Topological Signature (UTS) descriptors, comparing Embedding-UTS, Graph-UTS, and Dual-UTS against the unmodified, unregularized GIN backbone. Table 6: UTS descriptor variants vs. GIN (unmodified/unregularized) — MUTAG. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Embedding-UTS Graph-UTS Dual-UTS
0.832 ± 0.084 0.872 ± 0.079 0.890 ± 0.076 0.878 ± 0.078
— +0.040 +0.058 +0.047
— [0.863, 0.880] [0.874, 0.906] [0.870, 0.887]
— 0.109 0.102 0.097
Table 7: UTS descriptor variants vs. GIN (unmodified/unregularized) — PROTEINS. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Embedding-UTS Graph-UTS Dual-UTS
0.740 ± 0.034 0.751 ± 0.031 0.759 ± 0.040 0.763 ± 0.036
— +0.011 +0.019 +0.023
— [0.743, 0.760] [0.748, 0.770] [0.752, 0.773]
— 0.042 0.039 0.028
Table 8: UTS descriptor variants vs. GIN (unmodified/unregularized) — COLLAB. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Embedding-UTS Graph-UTS Dual-UTS
0.810 ± 0.029 0.823 ± 0.028 0.832 ± 0.029 0.837 ± 0.028
— +0.013 +0.021 +0.026
— [0.816, 0.830] [0.824, 0.839] [0.829, 0.844]
— 0.009 0.002 < 0.001
Summary. All three variants improve significantly over baseline, with Dual-UTS strongest – the same ordering seen on PROTEINS and COLLAB, now confirmed at 32× their graph count. Unlike MUTAG, the ogbg-ppa gains reach significance at this seed count, consistent with the much larger fixed test split reducing per-seed variance. B.2
Topological Loss Variants
This subsection isolates the effect of the topology-aware auxiliary losses (Ltopo−evol , Ltopo−align , and their combination), compared against the unmodified, unregularized GIN backbone. Summary. The auxiliary losses show no consistent benefit: on MUTAG the differences are small and not significant; on PROTEINS and COLLAB, Ltopo−evol and the combined loss are significantly negative, and only Ltopo−align on PROTEINS shows a significant (small) improvement. This indicates the descriptor-based variants (Section B.1), not the auxiliary losses, drive the gains reported in the main paper. 17
Table 9: UTS descriptor variants vs. GIN (unmodified/unregularized) — ogbg-ppa. Official OGB species split, 3 seeds. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Embedding-UTS Graph-UTS Dual-UTS
67.84 ± 0.917 69.27 ± 0.903 70.20 ± 0.951 71.06 ± 0.934
— +1.43 +2.36 +3.22
— [68.76, 69.78] [69.66, 70.74] [70.53, 71.59]
— 0.0168 0.0041 0.0012
Table 10: Topological loss variants vs. GIN (unmodified/unregularized) — MUTAG. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Ltopo−evol Ltopo−align Combination
0.832 ± 0.084 0.850 ± 0.085 0.842 ± 0.088 0.841 ± 0.084
— +0.019 +0.011 +0.010
— [0.834, 0.867] [0.824, 0.859] [0.825, 0.858]
— 0.210 0.205 0.198
Summary (ogbg-ppa). Unlike PROTEINS and COLLAB, where at least one individual loss is significantly negative, both losses are individually significant and positive on ogbg-ppa. The combination still underperforms either alone, echoing the lack of synergy seen throughout this work. B.3
Capacity Control (Random Descriptor Baselines)
To test whether the gains from UTS descriptors reflect real topological signal rather than added parameter capacity, we compare Graph-UTS and Dual-UTS against matched-dimensionality randomnoise controls (Graph-UTS-random, Dual-UTS-random). Reported ∆, CI, and p are for the paired difference (real variant − matched random control). Summary. On PROTEINS and COLLAB, both real UTS variants significantly outperform their matched-capacity random controls, directly refuting a “more parameters alone” explanation for the gains in Section B.1. On MUTAG the paired differences are positive but not significant, consistent with the limited statistical power on this smaller dataset noted throughout this appendix. Summary (ogbg-ppa). Both paired differences are significant, refuting a capacity-only explanation for the ogbg-ppa gains, consistent with the same finding on PROTEINS and COLLAB. B.4
Pooling Comparison
This subsection compares our pooling operator, UTSTopPool, against TOGL, SAGPool, and TopKPool. Reported ∆, CI, and p are for the paired difference (UTSTopPool − competitor). Summary. UTSTopPool is not significantly different from TOGL on MUTAG and trails it slightly (not significantly) on mean score, but significantly outperforms TOGL on both PROTEINS and COLLAB. Against SAGPool and TopKPool, UTSTopPool is ahead on all three datasets, with the advantage significant on PROTEINS and COLLAB but not on MUTAG, again consistent with reduced power on the smallest dataset. Summary (ogbg-ppa). UTSTopPool significantly outperforms SAGPool and TopKPool, mirroring PROTEINS/COLLAB. Unlike any other dataset in this work, however, TOGL significantly outperforms UTSTopPool here (p = 0.0008). UTSTopPool’s advantage over feature-based pooling (SAGPool, TopKPool) holds at this scale, but its comparison against TOGL specifically is datasetdependent rather than uniformly favorable. B.5
Discussion: Cross-Dataset Consistency and the Role of Scale
Extending evaluation to ogbg-ppa clarifies a pattern the other three datasets alone left ambiguous: UTS-Aug improves over baseline on every dataset and at every scale tested, from MUTAG’s small molecular graphs to ogbg-ppa’s much larger biological networks, making it the most consistently reliable of the three interventions. UTS-Reg and UTS-Pool are each dataset-dependent instead: UTS-Reg’s auxiliary losses underperform baseline on COLLAB (Section 5.3), and UTS-Pool slightly 18
Table 11: Topological loss variants vs. GIN (unmodified/unregularized) — PROTEINS. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Ltopo−evol Ltopo−align Combination
0.740 ± 0.034 0.738 ± 0.034 0.755 ± 0.033 0.736 ± 0.035
— −0.002 +0.014 −0.004
— [0.730, 0.746] [0.747, 0.762] [0.729, 0.744]
— 0.031 0.019 0.022
Table 12: Topological loss variants vs. GIN (unmodified/unregularized) — COLLAB. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Ltopo−evol Ltopo−align Combination
0.810 ± 0.029 0.805 ± 0.030 0.806 ± 0.030 0.809 ± 0.032
— −0.006 −0.004 −0.002
— [0.797, 0.813] [0.799, 0.814] [0.800, 0.817]
— 0.012 0.024 0.044
underperforms TOGL specifically on ogbg-ppa (Section 5.4), while otherwise outperforming both baselines on every other dataset in this work.
C
Full Proofs and Theoretical Concepts
This section presents the complete proofs of 6 along with information on computational complexity. C.1
Proof of Theorem 1
Proof. Message Passing Neural Networks (MPNNs), including the Graph Isomorphism Network (GIN), are provably bounded in expressive power by the 1-dimensional Weisfeiler–Lehman (1-WL) graph isomorphism test [26]. Consequently, if two graphs are 1-WL equivalent, every intermediate node representation and every permutation-invariant graph readout produced by the backbone network must also be identical. Formally, zstruct (G1 ) = zstruct (G2 ). Consider the canonical pair of non-isomorphic but 1-WL-equivalent graphs G1 = C6 ,
G2 = 2 × C3 ,
where C6 denotes the cycle graph on six vertices and 2 × C3 denotes the disjoint union of two triangles. Because both graphs are regular, the 1-WL refinement procedure assigns identical colors to every vertex throughout all refinement iterations, making them indistinguishable to any standard message-passing GNN. Our framework augments the conventional graph representation using h i z′ (G) = zstruct (G) ∥ Φemb (H(L) ) ∥ Φgrph (G) , where Φgrph (G) is computed directly from the input graph topology. Unlike message passing, Φgrph explicitly computes topological invariants through persistent homology. In particular, the Vietoris–Rips filtration distinguishes the two graphs by their one-dimensional homology. For the cycle graph, β1 (C6 ) = 1, since there exists one independent one-dimensional cycle. 19
Table 13: Topological loss variants vs. GIN (unmodified/unregularized) — ogbg-ppa. Variant
Mean ± Std
∆
95% CI
p
GIN (unmodified/unregularized) Ltopo−evol Ltopo−align Combination
67.84 ± 0.917 68.36 ± 0.982 69.54 ± 0.941 68.15 ± 1.006
— +0.52 +1.70 +0.31
— [67.80, 68.92] [69.01, 70.07] [67.58, 68.72]
— 0.0341 0.0286 0.0437
Table 14: Capacity control: real UTS descriptors vs. matched-capacity random controls — MUTAG. Variant
Mean ± Std
∆ (paired)
95% CI
p
Graph-UTS Graph-UTS-random
0.890 ± 0.076 0.879 ± 0.077
— +0.011
— [−0.007, +0.029]
— 0.225
Dual-UTS Dual-UTS-random
0.878 ± 0.078 0.824 ± 0.084
— +0.054
— [−0.011, +0.119]
— 0.104
For the disjoint union of two triangles, β1 (2 × C3 ) = 2, since each connected component contributes one independent cycle. Consequently, the persistent homology descriptors contained in Φgrph , including the first Betti number, persistence lifetimes, persistence entropy, and related geometric summaries, necessarily differ: Φgrph (C6 ) ̸= Φgrph (2 × C3 ). Because concatenation is injective with respect to its individual components, z′ (C6 ) = [zstruct ∥ Φemb ∥ Φgrph (C6 )] ̸= [zstruct ∥ Φemb ∥ Φgrph (2 × C3 )] = z′ (2 × C3 ). Therefore, although the underlying GNN cannot distinguish C6 from 2 × C3 , the UTS-augmented representation can. Hence the proposed readout strictly separates at least one pair of graphs that are indistinguishable under the 1-WL test. Therefore, the proposed UTS-augmented framework is strictly more expressive than the standard 1-WL message-passing hierarchy.
C.2
Full Justification of Proposition 1
Let s(l) = Φemb (H(l) ) denote the embedding-space topological signature at layer l, and let Lsmooth (defined below) be the topo-evolution loss with fixed weight λsmooth > 0. L−1
2 λsmooth X (l) Lsmooth = s − s(l−1) L−1 2
(28)
l=1
At a stationary point of the combined objective L = Ltask + Lsmooth , the gradient contribution of Lsmooth acts to reduce the layer-to-layer divergence of s(l) , which is, at a local first-order level, in tension with representation collapse understood as convergence of per-graph topological signatures toward a shared fixed point across the dataset (Eq. 30). This is a heuristic motivation, not a proof that Lsmooth enforces a lower bound on embedding variance or on the Oversmoothing Index. Lsmooth is an unconstrained soft penalty: standard stochastic gradient 20
Table 15: Capacity control: real UTS descriptors vs. matched-capacity random controls — PROTEINS. Variant
Mean ± Std
∆ (paired)
95% CI
p
Graph-UTS Graph-UTS-random
0.759 ± 0.040 0.736 ± 0.041
— +0.023
— [+0.005, +0.041]
— 0.015
Dual-UTS Dual-UTS-random
0.763 ± 0.036 0.750 ± 0.040
— +0.013
— [+0.003, +0.023]
— 0.020
Table 16: Capacity control: real UTS descriptors vs. matched-capacity random controls — COLLAB. Variant
Mean ± Std
∆ (paired)
95% CI
p
Graph-UTS Graph-UTS-random
0.832 ± 0.029 0.807 ± 0.030
— +0.025
— [+0.018, +0.032]
— < 0.001
Dual-UTS Dual-UTS-random
0.837 ± 0.028 0.824 ± 0.029
— +0.013
— [+0.004, +0.021]
— 0.001
descent provides no guarantee that any particular variance floor is achieved, and the penalty’s local effect on layer-to-layer signature divergence does not by itself imply a global effect on cross-graph signature convergence, since these are related but distinct quantities (the former measures a graph’s own trajectory across depth; the latter measures similarity between graphs at a fixed depth). Empirical evidence. This connection holds in one direction and reverses in another. Across MUTAG, PROTEINS, and COLLAB, layer-wise OSI comparisons between an unregularized baseline and a Lsmooth -regularized model (Table 23) show OSI decreasing under regularization on MUTAG at every layer, but increasing under regularization on PROTEINS and COLLAB. We therefore do not claim Lsmooth acts as a general anti-oversmoothing mechanism; we report it as an empirically dataset-dependent effect, consistent with Proposition 1’s status as motivation rather than guarantee. This dataset-dependence is further corroborated by the loss-ablation results in Table 10–12: the Topo-evol term is directionally positive (though not significant) on MUTAG, small and mixed on PROTEINS, and significantly negative on COLLAB. C.3
Geometric Control of Local Persistence Topology
Proposition 2. Let Xv = HN (v) ⊂ Rd , |Xv | = nv = |N (v)| + 1, equipped with the Euclidean P metric d(·, ·), and let cv = n1v u∈Xv hu denote its centroid. Let VR• (Xv ) and Č• (Xv ) denote the Vietoris–Rips and Čech filtrations of Xv , and let Dgmk (Xv ) denote the degree-k persistence diagram of VR• (Xv ). Then, with ϕlight as in Eq. (8): v P (i) (0-dimensional control.) Writing Pers0 (Xv ) = (0,d)∈Dgm0 (Xv ), d<∞ d for the total finite 0-persistence, µvnn ≤ Pers0 (Xv ) ≤ (nv − 1) ∆v . (ii) (Vanishing of higher-order topology.) For every k ≥ 1 and every (b, d) ∈ Dgmk (Xv ), d ≤ 2 ∆v . Consequently Dgmk (Xv ) → ∅ as ∆v → 0, for every k ≥ 1. (iii) (Noise floor.) If Xv is a δ-Gromov–Hausdorff perturbation of an idealized configuration X̃v v v with δ ≈ σnn , then no pair (b, d) ∈ Dgmk (Xv ) with d − b < 2σnn is distinguishable from noise. (iv) (Dimension cap.) Dgmk (Xv ) = ∅ for all k ≥ |N (v)|, so |N (v)|/kmax bounds the highest homological dimension that can carry signal. Hence ϕlight determines, for every v, an explicit scale interval [µvnn , 2∆v ] outside of which VR• (Xv ) v v is provably trivial (a single component, no higher homology), together with a noise floor 2σnn 21
Table 17: Capacity control: real UTS descriptors vs. matched-capacity random controls — ogbg-ppa. Variant
Mean Accuracy
95% CI (paired diff)
Graph-UTS Graph-UTS-random Paired difference
70.20 67.83 +2.37 (p = 0.0011)
— — [+0.94, +3.80]
Dual-UTS Dual-UTS-random Paired difference
71.06 68.80 +2.26 (p = 0.0024)
— — [+0.82, +3.70]
Table 18: Pooling comparison — MUTAG. Variant
Mean ± Std
∆ vs. UTSTopPool
95% CI
p
UTSTopPool (ours) TOGL SAGPool TopKPool
0.835 ± 0.079 0.840 ± 0.083 0.831 ± 0.080 0.829 ± 0.079
— −0.005 +0.004 +0.006
— [−0.012, +0.001] [−0.001, +0.008] [−0.001, +0.013]
— 0.103 0.143 0.085
and a dimension cap |N (v)| — i.e. the first-order conditions governing whether Xv can carry any nontrivial persistent topology at all. Proof. (i) 0-dimensional control. By the correspondence between 0-th persistent homology of a Vietoris–Rips filtration on a finite metric space and single-linkage hierarchical clustering [3], every component merge (death) in Dgm0 (Xv ) occurs exactly at the weight of the corresponding edge added by Kruskal’s algorithm; equivalently, the multiset of finite death times of Dgm0 (Xv ) equals the multiset of edge weights of the minimum spanning tree T ⋆ of the P complete graph (Xv , d). All births in Dgm0 occur at filtration value 0, so Pers0 (Xv ) = w(T ⋆ ) := e∈T ⋆ w(e). Upper bound. Every edge weight of T ⋆ is a pairwise distance in Xv , hence w(e) ≤ ∆v for all e ∈ T ⋆ , and |T ⋆ | = nv − 1, giving w(T ⋆ ) ≤ (nv − 1)∆v . Lower bound. Let NN(u) = minw̸=u d(hu , hw ) and u⋆ = arg maxu NN(u). Any edge of T ⋆ incident to u⋆ has weight ≥ NN(u⋆ ), since NN(u⋆ ) is by definition the smallest possible distance ⋆ ⋆ ⋆ from u⋆ to any other P point. As u has at least one incident tree edge, w(T ) ≥ NN(u ) = maxu NN(u) ≥ n1v u NN(u) = µvnn . Combining the two bounds gives (i). (ii) Vanishing of higher-order topology. First, a Euclidean fact: for any u ∈ Xv , P P d(hu , cv ) = n1v w (hu − hw ) ≤ n1v w ∥hu − hw ∥ ≤ ∆v , by the triangle inequality and convexity of ∥ · ∥. So cv lies within distance ∆v of every point of Xv , i.e. the circumradius of Xv about cv is ≤ ∆v . Consequently the ball system {B(hu , ∆v )}u∈Xv has nonempty total intersection (cv lies in all of them), so the top simplex on all of Xv is present in the Čech complex at scale ∆v ; since a Čech complex is a downward-closed simplicial complex, this forces Č∆v (Xv ) to be the full simplex ∆nv −1 on Xv . Next, for any metric space and any ε, Čε ⊆ VR2ε : if σ has circumradius ≤ ε about some point p, then for any u, w ∈ σ, d(hu , hw ) ≤ d(hu , p) + d(p, hw ) ≤ 2ε by the triangle inequality, so σ ∈ VR2ε . Applying this at ε = ∆v gives VR2∆v (Xv ) ⊇ Č∆v (Xv ) = ∆nv −1 , and since ∆nv −1 already contains every possible simplex on Xv , equality holds: VR2∆v (Xv ) = ∆nv −1 , the full simplex. The full simplex is contractible, so Hk (VR2∆v (Xv )) = 0 for all k ≥ 1. By definition of persistent homology, every class in dimension k ≥ 1 must therefore have died by filtration value 2∆v , i.e. every (b, d) ∈ Dgmk (Xv ), k ≥ 1, satisfies d ≤ 2∆v . Letting ∆v → 0 forces every such d → 0, and since b ≥ 0 always, every bar collapses: Dgmk (Xv ) → ∅. (iii) Noise floor. By the Gromov–Hausdorff stability theorem for persistence diagrams of Vietoris– Rips filtrations on point clouds [4, 6], if dGH (Xv , X̃v ) ≤ δ then the bottleneck distance obeys 22
Table 19: Pooling comparison — PROTEINS. Variant
Mean ± Std
∆ vs. UTSTopPool
95% CI
p
UTSTopPool (ours) TOGL SAGPool TopKPool
0.745 ± 0.033 0.744 ± 0.033 0.742 ± 0.034 0.741 ± 0.033
— +0.001 +0.003 +0.005
— [0.000, 0.003] [0.002, 0.005] [0.003, 0.006]
— 0.046 0.002 < 0.001
Table 20: Pooling comparison — COLLAB. Variant
Mean ± Std
∆ vs. UTSTopPool
95% CI
p
UTSTopPool (ours) TOGL SAGPool TopKPool
0.821 ± 0.029 0.820 ± 0.029 0.819 ± 0.029 0.818 ± 0.029
— +0.001 +0.002 +0.003
— [0.000, 0.002] [0.000, 0.004] [0.001, 0.006]
— 0.018 0.029 0.020
dB (Dgmk (Xv ), Dgmk (X̃v )) ≤ 2δ for every k. Taking X̃v to be an idealized (noise-free) configurav tion and δ ≈ σnn as the empirical estimate of local embedding perturbation, any pair in Dgmk (Xv ) v with lifetime d − b < 2σnn lies within the stability radius of the trivial (empty) diagram and so cannot be certified, from Xv alone, as distinct from a perturbation of a topologically trivial configuration. (iv) Dimension cap. A k-simplex requires k + 1 distinct vertices, so the chain groups of VR• (Xv ) vanish identically for k ≥ nv = |N (v)| + 1, hence Hk ≡ 0 for k ≥ |N (v)| at every filtration value, trivially. Corollary 1. Statements (i)–(iv) jointly show that ϕlight recovers, without persistent-homology v computation, (a) matching upper/lower bounds on the total 0-dimensional persistence [µvnn , (nv − v 1)∆v ], (b) an explicit death-time ceiling 2∆v for all higher-order features, (c) a noise floor 2σnn below which no feature P is distinguishable from perturbation, and (d) a dimension cap |N (v)|. The mean radius r̄1v = n1v u d(hu , cv ) is a smooth, outlier-robust surrogate for the circumradius bound used in the proof of (ii) — since r̄1v ≤ maxu d(hu , cv ) ≤ ∆v — and is preferred over the (non-smooth) max operator for gradient-based training of fθ . Together these five scalars therefore certify, rather than merely approximate, the scale regime in which Xv can carry nontrivial topology, justifying their use as a lightweight proxy for Φdiff emb . C.4
Computational Complexity Analysis
This section quantifies the per-component computational cost of the two Unified Topological Signatures and justifies the asymptotic claims made in Section 4.4 and Section 6.4. Let n = |V|, m = |E|, and d denote the embedding dimension. For the local pooling analysis, let nv = |N (v)| + 1 denote a neighbourhood size and δ̄ the average node degree. C.4.1
Graph Signature Φgrph
Φgrph is computed once per graph (Appendix A.5, GraphUTS precomputation) and cached, so its cost is amortized to O(1) per training step. Its one-time cost decomposes as: • Distance features / APSP: all-pairs shortest paths via repeated BFS from every node, O(nm) for unweighted graphs (or O(n2 log n + nm) with Dijkstra on weighted variants); dominates when graphs are sparse (m = O(n)), giving O(n2 ). • Ollivier–Ricci curvature: for each of m edges, one Sinkhorn iteration over lazy randomwalk measures supported on O(δ̄) neighbours costs O(δ̄ 2 T ) for T Sinkhorn iterations, giving O(mδ̄ 2 T ) total. • Forman–Ricci curvature: closed-form per edge from local degree information, O(mδ̄). • Persistence features: exact Vietoris–Rips persistence via GUDHI on the n × n shortest-path matrix, worst case O(n3 ) (bounded in practice by the sparsity of the simplicial complex GUDHI constructs; see Project [22]). 23
Table 21: Pooling comparison — ogbg-ppa. Variant
Mean ± Std
∆ vs. UTSTopPool
95% CI
p
UTSTopPool (ours) TOGL SAGPool TopKPool
68.85 ± 0.891 68.97 ± 0.926 67.88 ± 0.963 67.53 ± 0.988
— −0.12 +0.97 +1.32
— [−0.18, −0.06] [+0.62, +1.32] [+0.89, +1.75]
— 0.0008 0.0003 0.0001
• Spectral features: eigendecomposition of the n × n graph Laplacian, O(n3 ) (or O(n2 ) for the few smallest eigenvalues via Lanczos, which we use in practice). • Structural features: degree and clustering statistics O(m); betweenness centrality via Brandes’ algorithm O(nm). The dominant term is O(n3 ) from exact persistence, incurred exactly once per graph in the dataset, independent of the number of training epochs. C.4.2
Embedding Signature Φemb (Full, Per Layer)
Unlike Φgrph , Φdiff emb (Appendix A.4) is recomputed at every layer of every forward pass, since it depends on H(l) , which changes with the encoder weights during training. Its per-layer, per-graph cost is: • Pairwise distances (Eq. 9): O(n2 d). n 2
upper-triangle distances, O(n2 log n). • H1 surrogate (Eq. 15): enumerating all n3 triangles, O(n3 ), capped at n ≤ nmax = 50 (Appendix A.2, Remark on H1 cost); for n > nmax the H1 dimensions are set to zero and this term is skipped, reducing the effective cost to O(n2 d). • H0 surrogate (Eq. 14): sorting the
• Spectral features: eigendecomposition of the regularized soft Laplacian L̃ ∈ Rn×n via torch.linalg.eigh, O(n3 ), with a backward pass of matching cost through the analytic eigenvalue gradient. The full signature is therefore O(n3 ) per layer whenever n ≤ nmax , and O(n3spectral ) (from the spectral term alone, since H1 is skipped) for larger graphs, where the eigendecomposition remains the bottleneck term. Across an L-layer encoder this multiplies to O(Ln3 ) additional cost per forward/backward pass relative to a plain GIN, which is the cost the lightweight variant is designed to avoid for pooling specifically. C.4.3
Lightweight Proxy ϕlight (Per-Node Pooling Score) v
For the pooling scorer (Section 4.4), the relevant unit of computation is a single node’s one-hop neighbourhood Xv rather than the whole graph. Given ϕlight ∈ R5 (Eq. 8), each component is v computable directly from the nv × nv local distance matrix: • Local distance matrix: O(n2v d). v • µvnn , σnn : mean/std of nearest-neighbour distances within Xv , O(n2v ) given the distance matrix.
• ∆v : maximum pairwise distance, O(n2v ). • r̄1v : mean distance to centroid, O(nv d). • |N (v)|/kmax : O(1) given the precomputed degree. Each node’s score is thus O(n2v d), matching the “local quadratic” cost stated in Section 4.4 (as opposed to the O(n3 ) cubic cost of triangle enumeration and eigendecomposition used by the full signature). Summing over all nodes, the total pooling-layer cost is X
X O(n2v d) = O d n2v = O(d n δ̄ 2 )
v∈V
v
24
(29)
for graphs with roughly uniform degree δ̄, i.e. linear in n rather than cubic, at fixed local density. This is the source of the scalability improvement claimed in Section 4.4: the lightweight variant 3 2 replaces √ a per-layer O(n ) term with an O(nδ̄ d) term, which is asymptotically smaller whenever δ̄ = o( n) — true for all sparse graphs, and in particular for every dataset in Section 5 (mean degree δ̄ ∈ [2, 9], n up to several hundred for COLLAB). C.4.4
Chunked Memory Bound
Processing neighbourhoods in chunks of size C (Section 4.4) bounds peak memory rather than total compute: at any instant only C neighbourhoods’ distance matrices and intermediate scores are materialized, giving peak GPU memory O(Cd δ̄max ) (where δ̄max bounds the largest neighbourhood processed in a chunk), independent of the total node count n. Total compute is unaffected — it remains O(d n δ̄ 2 ) as in Eq. (29) — chunking only trades wall-clock time (sequential chunks) for the ability to run on graphs whose full n × n distance matrix would not fit in memory at once. C.4.5
Summary
Table 22 summarizes the cost and frequency of calculation for each signature. Table 22: Asymptotic cost per forward pass, one graph. n: nodes, m: edges, d: embedding dim, δ̄: average degree, L: GNN layers. Component
Cost
Φgrph (graph signature) Φdiff emb (full, per layer) ϕlight (lightweight, all nodes) v
D
Oversmoothing Analysis
D.1
Oversmoothing Index
3
O(n ) O(n3 ) O(d n δ̄ 2 )
Frequency once per graph (cached) every layer, every step pooling layer(s) only
The embedding signature naturally provides a graph-level diagnostic for monitoring representation evolution during message passing. We define the Oversmoothing Index (OSI) as (l) (l) OSI(l) = 1 − dcos si , sj ,
(30)
(l)
where si denotes the embedding signature of graph i at layer l, dcos is the cosine distance, and the average is computed over all graph pairs in the evaluation set. Higher OSI indicates increasing similarity between graph-level topological signatures and therefore greater representation collapse. OSI is used only for analysis and does not influence training. D.2
Oversmoothing diagnostic
To further understand the effect of topology-preserving regularization, we analyze the evolution of graph-level topology throughout message passing using the proposed Oversmoothing Index (OSI). Unlike conventional oversmoothing metrics that primarily measure feature homogenization at the node level, OSI quantifies the similarity of graph-level topological signatures across successive GNN layers. Table 23 reports layer-wise OSI for both an unregularized baseline GIN and a model trained with the topo-evolution loss Lsmooth , across all layers of all three benchmark datasets, extending our earlier baseline-only analysis to directly test whether the regularizer has the intended effect. For the unregularized baseline, OSI remains high but relatively stable across layers on all three datasets, indicating that graph-level topological signatures do not collapse severely at the depths evaluated in this work. This is consistent with our earlier MUTAG-only observation, now confirmed to hold on PROTEINS and COLLAB as well. 25
Table 23: Layer-wise Oversmoothing Index (OSI, Eq. 30) comparing an unregularized baseline GIN against a model trained with the topo-evolution loss Lsmooth , across all layers of all three benchmark datasets. Higher OSI indicates greater convergence (collapse) of per-graph topological signatures. ∆ is OSI(Topo-evol) − OSI(baseline); negative values indicate the regularizer reduces oversmoothing at that layer, positive values indicate it increases oversmoothing. MUTAG and PROTEINS use 4 GIN layers (0–3); COLLAB uses 3 layers (0–2), per Section 5. OSI (baseline)
OSI (Topo-evol)
∆
Trend
MUTAG
0 1 2 3
0.9693 0.9711 0.9626 0.9549
0.9587 0.9374 0.9207 0.9089
−0.0106 −0.0337 −0.0418 −0.0459
less oversmoothed less oversmoothed less oversmoothed less oversmoothed
PROTEINS
0 1 2 3
0.8176 0.8245 0.8204 0.8196
0.8408 0.8590 0.8495 0.8458
+0.0233 +0.0345 +0.0291 +0.0262
more oversmoothed more oversmoothed more oversmoothed more oversmoothed
COLLAB
0 1 2
0.7698 0.7841 0.7762
0.7878 0.7943 0.7865
+0.0180 +0.0103 +0.0104
more oversmoothed more oversmoothed more oversmoothed
Dataset
Layer
The effect of the topo-evolution loss on OSI is dataset-dependent rather than uniform. On MUTAG, regularization reduces OSI at every layer relative to the baseline (∆ ranging from −0.0106 at layer 0 to −0.0459 at layer 3), consistent with the intended anti-collapse effect of Lsmooth . On PROTEINS and COLLAB, however, regularization increases OSI at every layer (∆ up to +0.0345 on PROTEINS), the opposite of the intended effect. This dataset-dependence is not an isolated anomaly in the OSI measurements alone: it is directly mirrored in the loss-ablation accuracy results (Section 5). The topo-evolution loss in isolation improves accuracy on MUTAG (though not significantly at our sample size) and significantly reduces accuracy on PROTEINS and COLLAB – exactly the datasets where OSI also moves in the undesired direction. We view this correspondence as evidence that the OSI measurement is capturing a real, dataset-dependent property of the regularizer’s behavior, rather than measurement noise decoupled from downstream performance. We do not claim Lsmooth acts as a general anti-oversmoothing mechanism. This finding motivates the heuristic, rather than proven, framing of Proposition 1 in Section 6: Lsmooth provides a first-order, local incentive against abrupt layer-to-layer signature divergence, but this does not translate into a guaranteed reduction in cross-graph signature convergence, and the empirical relationship between the two can go either direction depending on the dataset.
E
Pooling Comparison Details
UTS-Pool vs. TopKPool and SAGPool. TopKPool [2] scores nodes via αv = h⊤ v p/∥p∥, a linear projection of the node embedding. SAGPool [15] scores nodes using a single graph convolution followed by a linear projection, making scores sensitive to 1-hop neighbourhood structure. Both methods are therefore limited to local linear information. UTS-Pool (§4.3) scores nodes by the topological richness of their local embedding neighbourhood via Φdiff emb , capturing non-linear geometric structure such as local component topology, cycle density, and spectral connectivity. This makes UTS-Pool more sensitive to structural boundary nodes and bridges, which are often the most discriminative nodes for graph classification. TOGL: implementation. TOGL reproduces the central architectural mechanism of TOGL [13] – multiple learnable filtration functions, trained end-to-end and summarized into a permutationinvariant topological descriptor – rather than reusing the original authors’ code, since TOGL’s released implementation depends on a custom C++/CUDA differentiable-persistence backend that is not distributed as an installable package. Concretely, TOGL consists of: 26
• k learnable filtration functions. For each of k = 4 filtrations, a two-layer MLP fj : Rd → R (d → d/2 → 1, ReLU) maps each node embedding to a scalar filtration value fj (hv ), learned jointly with the GIN encoder. • Differentiable H0 lifetime surrogate. For filtration j, each edge (u, v) is assigned the induced sublevel-set value max(fj (hu ), fj (hv )); the n−1 smallest such values across the graph are taken as a differentiable surrogate for 0-dimensional persistence lifetimes, replacing the nondifferentiable MST/union-find computation of exact sublevel-set persistence. This mirrors the sorted-edge-weight H0 surrogate used for Φemb (Eq. 14), applied here to a learned scalar filtration rather than embedding-space pairwise distances. • DeepSets graph descriptor. The lifetime set for each filtration is embedded permutationinvariantly via a per-lifetime MLP (1 → 16 → 16) followed by sum-pooling, following the DeepSets construction used for persistence-diagram embedding in TOGL. Concatenating across all k filtrations gives a k ×16 = 64-dimensional graph-level topological descriptor, which is concatenated to the post-pooling structural readout before classification. • Filtration-based pooling scores. Per-node pooling scores are a learned linear combination of the k filtration values, passed through a sigmoid and used for top-k node selection with the same pool ratio ρ = 0.5 and top-k selection mechanism as UTS-Pool, ensuring the two pooling operators are compared under an identical selection procedure and differ only in how each node’s score is computed. For a fair comparison, TOGL and UTSTopPool share the same GIN encoder (identical hidden dimension, depth, and dropout per dataset, Section 5), the same AdamW optimizer, learning-rate schedule, gradient clipping, and early-stopping protocol (Appendix A.5), and are evaluated under the same 10-fold stratified cross-validation. Table 24 reports total parameter counts (encoder + pooling module + classifier head) for the three pooling-comparison models across all three datasets. The gap between TOGL and UTSTopPool is dominated by TOGL’s four learnable filtration functions (33,284 parameters), which are shared between node scoring and the topological descriptor and cannot be separated into a pooling-only cost; the remaining gap comes from the DeepSets embedding networks and the correspondingly wider classifier head needed to consume the resulting 64-dimensional descriptor. UTSTopPool’s scorer, by contrast, uses a single lightweight MLP with no separate descriptor branch, accounting for its substantially smaller footprint at comparable or better accuracy. Table 24: Total parameter count for the three pooling-comparison architectures (GIN encoder + pooling module + classifier head), all under identical backbone settings per dataset (4 GIN layers for MUTAG and PROTEINS, 3 for COLLAB; hidden size 128). UTSTopPool uses the full 14-dim scorer on MUTAG/PROTEINS and the lightweight 5-dim proxy on COLLAB (Section 4.4), accounting for its slightly smaller overhead there. Variant
MUTAG
PROTEINS
COLLAB
GIN (no pooling) UTSTopPool TOGL pool
293,702 311,239 352,911
292,934 310,471 352,143
351,238 367,975 410,447
F
Layer-wise UTS Analysis: Full Results
F.1
Layer-wise UTS Feature Evolution and Signature Space Analysis
This section provides additional visualizations supporting the analysis of structural evolution in Section 4.4. To understand how the topological representations of graphs change as they pass through successive layers of a Graph Neural Network (GNN), we utilize the UTSAnalyzer module to empirically track the Universal Topological Signatures (UTS) at each layer. UTS Feature Evolution Across GNN Layers. Figure 4 tracks the trajectory of specific topological and geometric features from Layer 0 to Layer 3. The plots visualize the mean feature value at each layer, with the standard deviation represented by the shaded regions. The specific topological attributes tracked include H0 mean lifetime, H1 mean lifetime, Betti β0 , Betti β1 , Mean NN dist, Spectral gap λ1 , and Spectral entropy. Tracking these properties reveals structural drift over the 27
network’s depth; for instance, features like H0 mean lifetime and Spectral gap λ1 demonstrate a distinct decrease as the depth increases from layer 0 to 3. This quantitative drift highlights the smoothing of connected components and structural distinctness in deeper network layers. UTS Feature Evolution Across GNN Layers (§4.4)
Feature value
H0 mean lifetime
H1 mean lifetime
10 9 8 7 6 5 4 3
Betti
0.04
Betti
0.02
0.02
1.1
0.00
0.9
0.04 1
GNN Layer
2
3
0
1
GNN Layer
2
3
3
1
GNN Layer
2
3
0
1
GNN Layer
2
2
3
2.8
1.5
2.7
1.0
2.6 2.5
0.5
0.04 0
Spectral entropy
2.9
2.0
4
0.02
Spectral gap
2.5
5
0.00 1.0
0.02
0
Mean NN dist
6
0.04
1.2
0
1
GNN Layer
2
3
0.0
2.4 0
1
GNN Layer
2
3
0
1
GNN Layer
2
3
Figure 4: UTS Feature Evolution Across GNN Layers. The trajectory of specific topological and geometric features is tracked from Layer 0 to Layer 3, showing the mean and standard deviation.
PCA of UTS Signature Space per Layer. To further understand representation collapse and oversmoothing, Figure 5 provides a two-dimensional projection of the UTS vectors. The feature space is broken down into four subplots corresponding to Layer 0, Layer 1, Layer 2, and Layer 3. Standardized UTS vectors are projected onto the first two principal components, denoted as PC1 and PC2. By observing how the data points cluster and shift from Layer 0 to Layer 3, we can visually track the structural evolution of the embeddings. A contraction in the spread of these points in deeper layers provides empirical, visual evidence of representation collapse, which is mathematically measured by the Over-Smoothing Index (OSI). PCA of UTS Signature Space per Layer (§4.4) Layer 1
3.0
1.0
2.5 2.0 1.5 1.0
PC2
0.5 PC2
PC2
Layer 2
0.0
2
1
0 PC1
1
2
3
0.0
0.0
0.5
0.5
1.0
1.0
1.5
0.5
1.5
2.0
1.0
2.0
0.5 3
Layer 3
0.5
PC2
Layer 0
2
0 PC1
2
2.5 2
0 PC1
2
3
2
1
0 PC1
1
2
3
Figure 5: PCA of UTS Signature Space per Layer. Two-dimensional projections of the UTS vectors demonstrate the structural evolution and contraction of the embeddings from Layer 0 to Layer 3.
F.2
Importance of Ollivier-Ricci Curvature in Biological and Chemical Networks
Biological and chemical networks, such as molecular graphs and protein-protein interaction (PPI) networks, exhibit highly specific structural motifs that dictate their functional properties. Standard message-passing neural networks often struggle to capture the nuances of these topologies, particularly distinguishing between dense motifs (like aromatic rings or protein complexes) and critical bottlenecks (like aliphatic chains or inter-module bridges). To address this, we incorporate Ollivier-Ricci (OR) curvature, a discrete geometric measure that quantifies the overlap between the local neighborhoods of two connected nodes. In the context of biochemical networks, OR curvature provides a powerful structural inductive bias: • Positive Curvature: Indicates highly connected neighborhoods, effectively identifying cliques, aromatic rings, and dense functional modules. • Negative Curvature: Identifies “bridges” or bottlenecks between distinct clusters. In chemical graphs, these often correspond to crucial bonds connecting distinct functional groups; in PPI networks, they represent critical communication pathways between different biological processes. By explicitly encoding OR curvature, our formulation allows the model to appropriately route information, preventing the over-smoothing of features across structural bottlenecks while encouraging aggregation within functional cliques. 28
Ablation Study: The Necessity of Curvature Features. To empirically validate the contribution of these geometric features, we conducted an ablation study comparing our full formulation against a variant where all Ollivier-Ricci curvature features were removed. As shown in Table 25, removing the OR curvature features severely degrades the model’s predictive capabilities. Stripped of the ability to structurally differentiate between dense rings and critical bottlenecks, the ablated model fails to surpass the performance of the baseline architecture. This demonstrates that the geometric insights provided by Ollivier-Ricci curvature are not merely auxiliary, but are fundamentally necessary for achieving state-of-the-art performance in biochemical graph representation learning. Table 25: Accuracy comparison across MUTAG, PROTEINS, and COLLAB datasets. Results are reported as Mean ± Std. Variant GIN (Unregularized) Embedding-UTS (w/o Ricci) Graph-UTS (w/o Ricci)
MUTAG
PROTEINS
COLLAB
0.8315 ± 0.0840 0.8518 ± 0.0826 0.8652 ± 0.0801
0.7401 ± 0.0336 0.7392 ± 0.0341 0.7448 ± 0.0382
0.8104 ± 0.0286 0.8182 ± 0.0288 0.8269 ± 0.0297
G
Computational Scalability of UTS Variants
G.1
Benchmark Setup
We measure wall-clock computation time as a function of graph size for four UTS variants used in this work: • Graph-UTS (Ricci on) — the full structural signature Φgrph (Section 4.1.2) with Ollivier–Ricci and Forman–Ricci curvature enabled. • Graph-UTS (Ricci off) — Φgrph with curvature disabled, retaining distance, spectral, persistence, degree, clustering, centrality, and connectivity features. • Embedding-UTS (exact) — the full 14-dimensional embedding-space signature Φemb (Section 4.1.1), including exact GUDHI-based Rips persistence and eigendecomposition. • LightEmbeddingUTS — the 5-dimensional O(n2 ) geometric proxy used for large/dense graphs in §4.4 (mean/std pairwise distance, global spread, mean nearest-neighbour distance, a size proxy), omitting triangle enumeration, eigendecomposition, and persistence. Graphs are synthetic Barabási–Albert graphs with average degree 4, chosen to approximate the sparse, molecular/protein-like density profile of our benchmark datasets. Node sizes are swept over n ∈ {10, 17, 30, 50, 75, 100, 150, 200, 300, 400, 500, 620, 800, 1000}, with three repeats per size (independent random graphs for GraphUTS variants; independent random node embeddings of dimension 128 for EmbeddingUTS variants, matching the hidden dimension used elsewhere in this work). We annotate three reference sizes directly corresponding to our benchmark datasets: MUTAG’s average size (n ≈ 17), COLLAB’s average size (n ≈ 74.5), and PROTEINS’ maximum size (n = 620) — the exact figures cited in review. G.2
Results
Two clearly separated cost tiers. At every graph size tested, the two GraphUTS variants are 5–15× more expensive than either embedding-space variant. This gap is driven by GraphUTS’s all-pairs shortest-path computation and betweenness/closeness centrality, both of which scale worse than the pairwise-distance step shared by the embedding-space methods, and is present regardless of whether curvature is enabled. The curvature-specific cost narrows at scale. GraphUTS (Ricci on) starts roughly 35× more expensive than GraphUTS (Ricci off) at n = 10 (∼0.11s vs. ∼0.003s), but the two curves converge substantially by n = 1000 (∼4.0s vs. ∼3.6s, read from Figure 6). This indicates that at large n, the components shared between both variants — persistence, centrality, all-pairs distances — dominate total cost, and the Ollivier/Forman curvature computation, while expensive in absolute terms at small 29
Figure 6: Wall-clock computation time (log scale) versus graph size (log scale, number of nodes) for four UTS variants, averaged over three synthetic Barabási–Albert graphs per size. Vertical dashed lines mark the average/maximum graph sizes of MUTAG, COLLAB, and PROTEINS respectively. None of the four methods exceeded our 8-second per-call time budget within the tested range (n ≤ 1000); the plot instead shows each method’s growth trajectory, from which the point of practical infeasibility for larger graphs (e.g. long-range or web-scale benchmarks) can be extrapolated.
graphs, is not the primary scaling bottleneck at the sizes relevant to PROTEINS and COLLAB. We report this as an empirical observation from a single benchmark configuration rather than a proven asymptotic result. At PROTEINS’ maximum graph size (620 nodes), GraphUTS costs approximately 1.5–2 seconds per graph regardless of curvature setting. This is the concrete, measured basis for our design choice (§4.2) to precompute Φgrph once in parallel across the dataset prior to training, rather than recomputing it inside the training loop, where a cost of this magnitude per graph would make per-batch computation infeasible at typical batch sizes. The lightweight proxy delays, but does not eliminate, the scaling problem. LightEmbeddingUTS is the cheapest method at every size tested, but its relative advantage over exact EmbeddingUTS shrinks with graph size: at n = 10 it is roughly 30× cheaper (∼0.0002s vs. ∼0.006s); by n = 1000 this narrows to roughly 2× (∼0.4s vs. ∼0.75s). Because both methods share the same O(n2 ) pairwise-distance computation, and LightEmbeddingUTS’s only saving is skipping the O(n3 ) triangle enumeration, eigendecomposition, and persistence steps that exact EmbeddingUTS performs on top of that shared cost, the two curves must converge as n grows and the shared O(n2 ) term comes to dominate both. We state this plainly as a limitation of the current mitigation: LightEmbeddingUTS extends the practical size range for which UTS computation remains tractable, but does not itself achieve sub-quadratic scaling, and a graph large enough will eventually make even the lightweight proxy impractical. G.3
Implications and Limitations
This benchmark directly substantiates two design decisions already present in our pipeline and motivates one limitation we now state explicitly. First, it justifies parallel one-time precomputation of Φgrph (rather than per-batch recomputation) as a practical necessity rather than a mere optimization, given measured costs of 1–2 seconds per graph at PROTEINS-scale. Second, it validates LightEmbeddingUTS as an effective mitigation across the size range spanned by our current benchmark datasets (MUTAG, PROTEINS, COLLAB), all of which fall within the region where the lightweight proxy retains a meaningful (if narrowing) speed advantage. 30
We note as a limitation that this benchmark uses synthetic graphs at a single fixed density (average degree 4) and does not directly profile wall-clock cost on the real dataset graphs used for training, nor at the scale of long-range or web-scale graph benchmarks (potentially tens of thousands of nodes), where — extrapolating the trends in Figure 6 — even LightEmbeddingUTS’s shared O(n2 ) pairwise-distance step would itself become the binding constraint.
31