The Same Graph Topology, Three Different Results

TL;DR for operators

A graph classifier can use network structure in several ways: supplying structural measurements to the classifier, constraining how representations change during training, or using structure to decide which nodes to retain. These approaches should not be treated as interchangeable.

In Repurposing Unified Topological Signatures for Graph Representation Learning, Jain and colleagues¹ examine all three using a common Graph Isomorphism Network (GIN) backbone. Their strongest and most consistent results come from adding topological descriptors to graph-level representations. On the ogbg-ppa protein-network benchmark, classification accuracy increases from 67.84% to 71.06%.

The other interventions are less predictable. Structural regularization sometimes reduces accuracy, while topology-guided pooling improves on conventional feature-based methods but does not consistently outperform another topological alternative.

For teams building molecular, biological, or relational graph classifiers, the research supports testing structural augmentation before assuming that explicit topology-preservation constraints are beneficial. That preference remains conditional on computational feasibility and validation against the team’s own data.

Preserving more structure does not necessarily improve prediction

Consider a team developing a classifier for protein association networks. Each graph contains proteins and their relationships, and the model must assign the network to a category.

The team can describe the original network more comprehensively, discourage structural changes in learned representations, or retain nodes that appear structurally informative. All three approaches use additional knowledge about connectivity, but they change different parts of the learning process.

The experimental results make this choice consequential.

On ogbg-ppa, supplying both original-network and learned-representation descriptors raises accuracy from 67.84% to 71.06%, a 3.22-percentage-point improvement. A training penalty designed to discourage abrupt topological changes instead reaches 68.36%. A topology-guided pooling architecture achieves 68.85%, below the 68.97% of the competing TOGL method.

These are separate architectural comparisons, not a controlled head-to-head experiment establishing the best intervention in every setting. They nevertheless challenge an assumption: if structural information is predictive, enforcing structural preservation throughout training should also help.

The evidence suggests that making structural information available and restricting how representations evolve are different operations with different consequences.

Two signatures describe different forms of structure

Message-passing graph neural networks repeatedly aggregate information from neighboring nodes. This supports learning from connectivity but has a recognized limitation: certain structurally different graphs remain indistinguishable when local aggregation produces identical representations.

The studied framework supplements message passing with two kinds of numerical descriptions, called Unified Topological Signatures (UTS).

Graph-UTS is a fixed, 27-dimensional description of the input network. It combines curvature, shortest-path measurements, graph Laplacian spectral statistics, persistence features, and conventional structural measures. It is calculated independently of learned node representations and can be cached.

Embedding-UTS is a dynamic, 14-dimensional description of the geometry of learned node embeddings. It combines persistent-homology measurements, nearest-neighbor distances, intrinsic dimensionality, and spectral features. Because embeddings change during training, their signatures can also change between network layers.

The distinction allows structural information to serve different purposes:

For dual-signature augmentation, the final representation is:

The classifier receives its conventional learned graph representation alongside descriptors of the original graph and the final node-embedding geometry.

Crucially, augmentation does not require the message-passing backbone to preserve every measured structural characteristic. It supplies additional evidence that the classifier can learn to use.

Additional structural information produces consistent classification gains

The main augmentation experiments compare GIN against three descriptor configurations across four datasets.

Source: Section 5.2, Table 1. Gains are percentage-point differences calculated from the displayed means. MUTAG’s gain is not statistically significant (p = 0.102); the displayed improvements on the other three datasets are significant under the reported paired tests.

Every augmentation configuration improves mean accuracy relative to GIN across the four benchmarks. The combined static and dynamic descriptor performs best on three datasets, while the static descriptor alone leads on MUTAG.

The controlled comparisons offer more than an accuracy ranking. Adding descriptors also increases classifier input dimensionality, potentially increasing model capacity. The authors therefore compare real signatures with dimension-matched random descriptors.

These controls have a specific purpose: testing whether the improvements reflect structural information rather than merely a larger classifier input.

On ogbg-ppa, Dual-UTS exceeds its random-descriptor control by 2.26 percentage points, with a reported 95% confidence interval of +0.82 to +3.70 points. Similar statistically significant advantages appear for Graph-UTS and Dual-UTS on PROTEINS and COLLAB. MUTAG’s corresponding differences are not significant.

The controls strengthen the informational interpretation of augmentation, although they do not isolate the contribution of every signature component.

Structural regularization can constrain the wrong changes

The regularization experiments examine two additional training objectives.

Topology alignment encourages the geometry of final embeddings to correspond to a learned projection of the original graph’s structural signature. Topology evolution penalizes differences between embedding signatures at successive layers.

The second objective is motivated partly by oversmoothing, a phenomenon in which learned representations become insufficiently distinguishable.

If structural measurements change abruptly as information passes through network layers, discouraging those changes might appear to preserve information. But preserving a descriptor is not equivalent to preserving the distinctions needed for classification.

The results demonstrate the limitation.

On PROTEINS, topology-evolution regularization reduces accuracy from 74.0% to 73.8%. On COLLAB, it reduces accuracy from 81.0% to 80.5%. Both reported declines are statistically significant. Topology alignment performs better on PROTEINS and ogbg-ppa, but combining the two losses does not reliably improve results.

The paper also introduces an Oversmoothing Index (OSI), derived from the average cosine similarity of graph-level embedding signatures. Higher values indicate greater convergence among graph signatures, rather than necessarily measuring every form of node-level oversmoothing.

At layer three on MUTAG, topology-evolution regularization reduces OSI from 0.9549 to 0.9089. On PROTEINS, however, it increases OSI from 0.8196 to 0.8458. COLLAB likewise shows increased signature similarity at the reported layers.

These diagnostic results support a narrower conclusion than the regularizer’s motivation: discouraging signature changes can alter representation convergence, but it does not reliably prevent oversmoothing or improve prediction.

Topological pooling helps, but the strongest competitor still matters

Pooling reduces graph representations by retaining selected nodes. UTS-Pool uses learned scores derived from local embedding structure rather than relying exclusively on conventional node features.

On PROTEINS and COLLAB, UTS-Pool achieves the highest reported pooling accuracy: 74.5% and 82.1%, respectively. Its advantages over the authors’ TOGL reimplementation are only 0.1 percentage point on each dataset.

On ogbg-ppa, UTS-Pool achieves 68.85%, significantly above TopKPool’s 67.53% and SAGPool’s 67.88%. Yet TOGL reaches 68.97%, a statistically significant 0.12-point advantage over UTS-Pool (p = 0.0008).

The result supports structural node scoring as an alternative to feature-based pooling, without establishing superiority over existing topology-aware designs.

UTS-Pool also has a differentiability boundary: although its scoring descriptors can support gradient computation, hard top-k selection does not propagate gradients through the selection decision. The architecture therefore remains an adaptive selection heuristic rather than a fully differentiable pooling mechanism.

Greater expressivity does not remove computational limits

The paper’s theoretical result explains why external graph descriptors can extend discrimination beyond ordinary message passing.

A GNN bounded by the one-dimensional Weisfeiler-Leman (1-WL) procedure cannot distinguish certain graph pairs. Appending an independently calculated structural signature can distinguish such a pair when the chosen signatures differ.

The theorem establishes a conditional capability. It neither changes the underlying message-passing algorithm’s expressivity nor proves that the 27-dimensional signature distinguishes every pair of non-isomorphic graphs.

Computational feasibility introduces another boundary.

The full graph signature and differentiable embedding signature involve operations with stated cubic-time complexity, $O(n^3)$, where $n$ is the number of nodes. Static Graph-UTS can be computed once and cached; embedding signatures may require repeated computation across layers and training steps.

For pooling, the authors propose a five-dimensional local geometric proxy with stated complexity:

Here, $d$ is embedding dimension and $\bar{\delta}$ is average degree. The approximation becomes comparatively attractive when neighborhoods remain small. It does not reproduce complete persistent-homology information, and its near-linear dependence on node count does not hold when graph density grows substantially.

Synthetic scaling experiments examine graphs up to 1,000 nodes at approximately fixed average degree. They help characterize computational trade-offs but do not demonstrate production-scale efficiency.

Architecture selection should separate information, constraints, and selection

The practical implication for graph-classification teams is a staged evaluation strategy.

Where input graphs are stable enough for one-time preprocessing, static descriptor augmentation is a reasonable first candidate. Teams can compare unmodified message passing, Graph-UTS, Embedding-UTS, and Dual-UTS under matched evaluation protocols, including dimension-matched controls.

Regularization should then be tested independently, with classification accuracy and representation diagnostics considered together. Reduced layer-to-layer signature variation is not sufficient evidence that a model has become more discriminative.

Pooling requires its own comparison against feature-based and existing topological methods. The benchmark evidence does not support automatically selecting UTS-Pool over TOGL.

These implications apply most directly to graph-classification research involving molecular, biological, and relational networks. The four benchmarks do not establish performance on heterogeneous temporal graphs, substantially larger networks, or commercial workloads. Comparability with TOGL is also qualified by the authors’ independent reimplementation.

The central finding is therefore architectural rather than universal: topological information has different effects depending on whether a model receives it as evidence, obeys it as a constraint, or uses it to discard nodes.

For the studied benchmarks, making structure available to the classifier is the most consistently supported intervention. Whether that advantage survives deployment depends on predictive gains relative to preprocessing cost, training overhead, and the specific structural distinctions a workload requires.

Cognaptus: Automate the Present, Incubate the Future.