Repurposing Unified Topological Signatures for Graph Representation Learning

• URL: http://arxiv.org/abs/2609.17061v1
• Date: Tue, 15 Sep 2026 12:07:05 GMT
• Title: Repurposing Unified Topological Signatures for Graph Representation Learning
• Abstract summary: Unified Topological Signatures (UTS) capture compact, multi-scale representation of global graph topology.<n>UTS encode structural information inaccessible to 1-WL-based message-passing GNNs.<n>We show that integrating UTS into GNN optimization strictly extends GNN expressivity beyond the 1-WL hierarchy.
• Score: 1.9032628520534345
• License: http://creativecommons.org/licenses/by/4.0/
• 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: Graph_UTS- a static signature of the input graph topology, and Embedding_UTS- 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.

Related papers

• A Pure Transformer Pretraining Framework on Text-attributed Graphs [50.833130854272774]
  We introduce a feature-centric pretraining perspective by treating graph structure as a prior. Our framework, Graph Sequence Pretraining with Transformer (GSPT), samples node contexts through random walks. GSPT can be easily adapted to both node classification and link prediction, demonstrating promising empirical success on various datasets.
  arXiv  Detail & Related papers  (2024-06-19T22:30:08Z)
• Self-Attention Empowered Graph Convolutional Network for Structure Learning and Node Embedding [5.164875580197953]
  In representation learning on graph-structured data, many popular graph neural networks (GNNs) fail to capture long-range dependencies. This paper proposes a novel graph learning framework called the graph convolutional network with self-attention (GCN-SA) The proposed scheme exhibits an exceptional generalization capability in node-level representation learning.
  arXiv  Detail & Related papers  (2024-03-06T05:00:31Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. We propose Graph Sparse Training ( GST), which dynamically manipulates sparsity at the data level. GST produces a sparse graph with maximum topological integrity and no performance degradation.
  arXiv  Detail & Related papers  (2024-02-02T09:10:35Z)
• SGA: A Graph Augmentation Method for Signed Graph Neural Networks [14.441926210101316]
  Signed Graph Neural Networks (SGNNs) are vital for analyzing complex patterns in real-world signed graphs containing positive and negative links. We introduce the novel Signed Graph Augmentation framework (SGA), comprising three main components. Our method outperforms baselines by up to 22.2% in AUC for SGCN on Wiki-RfA, 33.3% in F1-binary, 48.8% in F1-micro, and 36.3% in F1-macro for GAT on Bitcoin-alpha in link sign prediction.
  arXiv  Detail & Related papers  (2023-10-15T02:19:07Z)
• Article Classification with Graph Neural Networks and Multigraphs [0.12499537119440243]
  We propose a method to enhance the performance of article classification by enriching simple Graph Neural Network (GNN) pipelines with multi-graph representations. fully supervised transductive node classification experiments are conducted on the Open Graph Benchmark OGBN-arXiv dataset and the PubMed diabetes dataset. Results demonstrate that multi-graphs consistently improve the performance of a variety of GNN models compared to the default graphs.
  arXiv  Detail & Related papers  (2023-09-20T14:18:04Z)
• Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity [2.5252594834159643]
  We propose Unified Graph Transformer Networks (UGT) that integrate local and global structural information into fixed-length vector representations. First, UGT learns local structure by identifying the local substructures and aggregating features of the $k$-hop neighborhoods of each node. Third, UGT learns unified representations through self-attention, encoding structural distance and $p$-step transition probability between node pairs.
  arXiv  Detail & Related papers  (2023-08-18T12:49:57Z)
• Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization [30.86182962089487]
  Graph Neural Networks (GNNs) have emerged as a powerful category of learning architecture for handling graph-structured data. We propose a dedicated plug-and-play normalization scheme, termed as SUbgraph-sPEcific FactoR Embedded Normalization (SuperNorm)
  arXiv  Detail & Related papers  (2023-05-31T14:37:31Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2022-05-07T04:11:23Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)
• Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks [183.97265247061847]
  We leverage graph signal processing to characterize the representation space of graph neural networks (GNNs) We discuss the role of graph convolutional filters in GNNs and show that any architecture built with such filters has the fundamental properties of permutation equivariance and stability to changes in the topology. We also study the use of GNNs in recommender systems and learning decentralized controllers for robot swarms.
  arXiv  Detail & Related papers  (2020-03-08T13:02:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.