Graph Persistence goes Spectral

• URL: http://arxiv.org/abs/2506.06571v1
• Date: Fri, 06 Jun 2025 22:51:08 GMT
• Title: Graph Persistence goes Spectral
• Authors: Mattie Ji, Amauri H. Souza, Vikas Garg,
• Abstract summary: We propose SpectRe -- a new topological descriptor for graphs that integrates spectral information into PH diagrams.<n>We introduce notions of global and local stability to analyze existing descriptors and establish that SpectRe is locally stable.<n>Experiments on synthetic and real-world datasets demonstrate the effectiveness of SpectRe.
• Score: 5.093257685701887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Including intricate topological information (e.g., cycles) provably enhances the expressivity of message-passing graph neural networks (GNNs) beyond the Weisfeiler-Leman (WL) hierarchy. Consequently, Persistent Homology (PH) methods are increasingly employed for graph representation learning. In this context, recent works have proposed decorating classical PH diagrams with vertex and edge features for improved expressivity. However, due to their dependence on features, these methods still fail to capture basic graph structural information. In this paper, we propose SpectRe -- a new topological descriptor for graphs that integrates spectral information into PH diagrams. Notably, SpectRe is strictly more expressive than existing descriptors on graphs. We also introduce notions of global and local stability to analyze existing descriptors and establish that SpectRe is locally stable. Finally, experiments on synthetic and real-world datasets demonstrate the effectiveness of SpectRe and its potential to enhance the capabilities of graph models in relevant learning tasks.

Related papers

• Graph Self-Supervised Learning with Learnable Structural and Positional Encodings [39.20899720477907]
  We introduce emphGenHopNet, a GNN framework that integrates a $k$-hop message-passing scheme.<n>We also propose a structural- and positional-aware GSSL framework that incorporates topological information throughout the learning process.<n>Our work significantly advances GSSL's capability in distinguishing graphs with similar local structures but different global topologies.
  arXiv  Detail & Related papers  (2025-02-22T14:10:06Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning [3.6881508872690825]
  We introduce a novel edge filtration-based persistence diagram, named Topological Edge Diagram (TED)<n>TED is mathematically proven to preserve node embedding information as well as contain additional topological information.<n>We propose a neural network based algorithm, named Line Graph Vietoris-Rips (LGVR) Persistence Diagram, that extracts edge information by transforming a graph into its line graph.
  arXiv  Detail & Related papers  (2024-12-23T10:46:44Z)
• Greener GRASS: Enhancing GNNs with Encoding, Rewiring, and Attention [12.409982249220812]
  We introduce Graph Attention with Structures (GRASS), a novel GNN architecture, to enhance graph relative attention.<n>GRASS rewires the input graph by superimposing a random regular graph to achieve long-range information propagation.<n>It also employs a novel additive attention mechanism tailored for graph-structured data.
  arXiv  Detail & Related papers  (2024-07-08T06:21:56Z)
• SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
  Graph neural networks (GNNs) have revolutionized the field of machine learning on non-Euclidean data such as graphs and networks. We propose a concatenation-based graph convolution mechanism that injectively updates node representations. We also design a novel graph pooling module, called WL-SortPool, to learn important subgraph patterns in a deep-learning manner.
  arXiv  Detail & Related papers  (2024-04-21T13:11:59Z)
• Structure-Preserving Graph Representation Learning [43.43429108503634]
  We propose a novel Structure-Preserving Graph Representation Learning (SPGRL) method to fully capture the structure information of graphs. Specifically, to reduce the uncertainty and misinformation of the original graph, we construct a feature graph as a complementary view via k-Nearest Neighbor method. Our method has quite superior performance on semi-supervised node classification task and excellent robustness under noise perturbation on graph structure or node features.
  arXiv  Detail & Related papers  (2022-09-02T02:49:19Z)
• Quasi-Framelets: Robust Graph Neural Networks via Adaptive Framelet Convolution [28.474359021962346]
  We propose a multiscale framelet convolution for spectral graph neural networks (GNNs) The proposed design excels in filtering out unwanted spectral information and significantly reduces the adverse effects of noisy graph signals. It exhibits remarkable resilience to noisy data and adversarial attacks, highlighting its potential as a robust solution for real-world graph applications.
  arXiv  Detail & Related papers  (2022-01-11T00:10:28Z)
• Graph Structure Learning with Variational Information Bottleneck [70.62851953251253]
  We propose a novel Variational Information Bottleneck guided Graph Structure Learning framework, namely VIB-GSL. VIB-GSL learns an informative and compressive graph structure to distill the actionable information for specific downstream tasks.
  arXiv  Detail & Related papers  (2021-12-16T14:22:13Z)
• SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism [33.135006052347194]
  This paper presents a novel hierarchical subgraph-level selection and embedding based graph neural network for graph classification, namely SUGAR. SUGAR reconstructs a sketched graph by extracting striking subgraphs as the representative part of the original graph to reveal subgraph-level patterns. To differentiate subgraph representations among graphs, we present a self-supervised mutual information mechanism to encourage subgraph embedding.
  arXiv  Detail & Related papers  (2021-01-20T15:06:16Z)
• CommPOOL: An Interpretable Graph Pooling Framework for Hierarchical Graph Representation Learning [74.90535111881358]
  We propose a new interpretable graph pooling framework - CommPOOL. It can capture and preserve the hierarchical community structure of graphs in the graph representation learning process. CommPOOL is a general and flexible framework for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2020-12-10T21:14:18Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• 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)

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.