Going beyond persistent homology using persistent homology

• URL: http://arxiv.org/abs/2311.06152v1
• Date: Fri, 10 Nov 2023 16:12:35 GMT
• Title: Going beyond persistent homology using persistent homology
• Authors: Johanna Immonen, Amauri H. Souza, Vikas Garg
• Abstract summary: We introduce a novel concept of color-separating sets to provide a complete resolution to this important problem. We propose RePHINE for learning topological features on graphs.
• Score: 5.724311218570011
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Representational limits of message-passing graph neural networks (MP-GNNs), e.g., in terms of the Weisfeiler-Leman (WL) test for isomorphism, are well understood. Augmenting these graph models with topological features via persistent homology (PH) has gained prominence, but identifying the class of attributed graphs that PH can recognize remains open. We introduce a novel concept of color-separating sets to provide a complete resolution to this important problem. Specifically, we establish the necessary and sufficient conditions for distinguishing graphs based on the persistence of their connected components, obtained from filter functions on vertex and edge colors. Our constructions expose the limits of vertex- and edge-level PH, proving that neither category subsumes the other. Leveraging these theoretical insights, we propose RePHINE for learning topological features on graphs. RePHINE efficiently combines vertex- and edge-level PH, achieving a scheme that is provably more powerful than both. Integrating RePHINE into MP-GNNs boosts their expressive power, resulting in gains over standard PH on several benchmarks for graph classification.

Related papers

• Tensor-Fused Multi-View Graph Contrastive Learning [12.412040359604163]
  Graph contrastive learning (GCL) has emerged as a promising approach to enhance graph neural networks' (GNNs) ability to learn rich representations from unlabeled graph-structured data. Current GCL models face challenges with computational demands and limited feature utilization. We propose TensorMV-GCL, a novel framework that integrates extended persistent homology with GCL representations and facilitates multi-scale feature extraction.
  arXiv  Detail & Related papers  (2024-10-20T01:40:12Z)
• PHLP: Sole Persistent Homology for Link Prediction -- Interpretable Feature Extraction [2.8413459430736396]
  Link prediction (LP) is a significant research area in graph data. Although graph neural network (GNN)-based models have achieved high performance in LP, understanding why they perform well is challenging. We propose a novel method that employs PH for LP (PHLP) focusing on how the presence or absence of target links influences the overall topology.
  arXiv  Detail & Related papers  (2024-04-23T16:54:56Z)
• Boosting Graph Pooling with Persistent Homology [8.477383770884508]
  naively plugging PH features into GNN layers always results in marginal improvement with low interpretability. We investigate a novel mechanism for injecting global topological invariance into pooling layers using PH, motivated by the observation that filtration operation in PH naturally aligns graph pooling in a cut-off manner. Experimentally, we apply our mechanism to a collection of graph pooling methods and observe consistent and substantial performance gain over several popular datasets.
  arXiv  Detail & Related papers  (2024-02-26T07:00:24Z)
• Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes [5.838832985156104]
  We present a higher-order Flower-Petals (FP) model, incorporating FP Laplacians into simplicial complexes (SCs) We also introduce a Higher-order Graph Convolutional Network (HiGCN) grounded in FP Laplacians, capable of discerning intrinsic features across varying topological scales. HiGCN accomplishes state-of-the-art performance on a range of graph tasks and provides a scalable and flexible solution to explore higher-order interactions in graphs.
  arXiv  Detail & Related papers  (2023-09-22T16:11:17Z)
• Learnable Filters for Geometric Scattering Modules [64.03877398967282]
  We propose a new graph neural network (GNN) module based on relaxations of recently proposed geometric scattering transforms. Our learnable geometric scattering (LEGS) module enables adaptive tuning of the wavelets to encourage band-pass features to emerge in learned representations.
  arXiv  Detail & Related papers  (2022-08-15T22:30:07Z)
• Is Homophily a Necessity for Graph Neural Networks? [50.959340355849896]
  Graph neural networks (GNNs) have shown great prowess in learning representations suitable for numerous graph-based machine learning tasks. GNNs are widely believed to work well due to the homophily assumption ("like attracts like"), and fail to generalize to heterophilous graphs where dissimilar nodes connect. Recent works design new architectures to overcome such heterophily-related limitations, citing poor baseline performance and new architecture improvements on a few heterophilous graph benchmark datasets as evidence for this notion. In our experiments, we empirically find that standard graph convolutional networks (GCNs) can actually achieve better performance than
  arXiv  Detail & Related papers  (2021-06-11T02:44:00Z)
• Optimisation of Spectral Wavelets for Persistence-based Graph Classification [0.0]
  We propose a framework that optimises the choice of wavelet for a dataset of graphs. Our framework encodes geometric properties of graphs in their associated persistence diagrams. We apply our framework to graph classification problems and obtain performances competitive with other persistence-based architectures.
  arXiv  Detail & Related papers  (2021-01-10T18:34:27Z)
• Hierarchical Graph Capsule Network [78.4325268572233]
  We propose hierarchical graph capsule network (HGCN) that can jointly learn node embeddings and extract graph hierarchies. To learn the hierarchical representation, HGCN characterizes the part-whole relationship between lower-level capsules (part) and higher-level capsules (whole)
  arXiv  Detail & Related papers  (2020-12-16T04:13:26Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs) first augments node features with certain multi-hop operators on the graph. We prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth.
  arXiv  Detail & Related papers  (2020-10-28T17:59:59Z)
• Data-Driven Learning of Geometric Scattering Networks [74.3283600072357]
  We propose a new graph neural network (GNN) module based on relaxations of recently proposed geometric scattering transforms. Our learnable geometric scattering (LEGS) module enables adaptive tuning of the wavelets to encourage band-pass features to emerge in learned representations.
  arXiv  Detail & Related papers  (2020-10-06T01:20:27Z)
• 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.