Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes

• URL: http://arxiv.org/abs/2308.06838v6
• Date: Sun, 31 Mar 2024 22:55:11 GMT
• Title: Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexes
• Authors: Quang Truong, Peter Chin,
• Abstract summary: Graph Neural Networks (GNNs) are theoretically bounded by the 1-Weisfeiler-Lehman test. Our study presents a novel perspective by focusing on simple paths within graphs during the topological message-passing process.
• Score: 4.23480641508611
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph Neural Networks (GNNs), despite achieving remarkable performance across different tasks, are theoretically bounded by the 1-Weisfeiler-Lehman test, resulting in limitations in terms of graph expressivity. Even though prior works on topological higher-order GNNs overcome that boundary, these models often depend on assumptions about sub-structures of graphs. Specifically, topological GNNs leverage the prevalence of cliques, cycles, and rings to enhance the message-passing procedure. Our study presents a novel perspective by focusing on simple paths within graphs during the topological message-passing process, thus liberating the model from restrictive inductive biases. We prove that by lifting graphs to path complexes, our model can generalize the existing works on topology while inheriting several theoretical results on simplicial complexes and regular cell complexes. Without making prior assumptions about graph sub-structures, our method outperforms earlier works in other topological domains and achieves state-of-the-art results on various benchmarks.

Related papers

• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data. This paper explores the computational limitations of GNNs through the lens of circuit complexity. Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism.
  arXiv  Detail & Related papers  (2025-01-11T05:54:10Z)
• 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) This framework provides a standardized setting to evaluate GNNs across diverse datasets. We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• One Model for One Graph: A New Perspective for Pretraining with Cross-domain Graphs [61.9759512646523]
  Graph Neural Networks (GNNs) have emerged as a powerful tool to capture intricate network patterns. Existing GNNs require careful domain-specific architecture designs and training from scratch on each dataset. We propose a novel cross-domain pretraining framework, "one model for one graph"
  arXiv  Detail & Related papers  (2024-11-30T01:49:45Z)
• Generalization of Graph Neural Networks through the Lens of Homomorphism [7.223313563198697]
  We propose to study the generalization of Graph Neural Networks (GNNs) through a novel perspective - analyzing the entropy of graph homomorphism. By linking graph homomorphism with information-theoretic measures, we derive generalization bounds for both graph and node classifications. These bounds are capable of capturing subtleties inherent in various graph structures, including but not limited to paths, cycles and cliques.
  arXiv  Detail & Related papers  (2024-03-10T03:51:59Z)
• Homomorphism Counts for Graph Neural Networks: All About That Basis [8.25219440625445]
  We argue for a more fine-grained approach, which incorporates the homomorphism counts of all structures in the basis'' of the target pattern. This yields strictly more expressive architectures without incurring any additional overhead in terms of computational complexity.
  arXiv  Detail & Related papers  (2024-02-13T16:57:06Z)
• Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling [83.77955213766896]
  Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graphstructured data. To address its scalability issue, graph topology sampling has been proposed to reduce the memory and computational cost of training Gs. This paper provides first theoretical justification of graph topology sampling in training (up to) three-layer GCNs.
  arXiv  Detail & Related papers  (2022-07-07T21:25:55Z)
• Learning Connectivity with Graph Convolutional Networks for Skeleton-based Action Recognition [14.924672048447338]
  We introduce a novel framework for graph convolutional networks that learns the topological properties of graphs. The design principle of our method is based on the optimization of a constrained objective function. Experiments conducted on the challenging task of skeleton-based action recognition shows the superiority of the proposed method.
  arXiv  Detail & Related papers  (2021-12-06T19:43:26Z)
• Topological Relational Learning on Graphs [2.4692806302088868]
  Graph neural networks (GNNs) have emerged as a powerful tool for graph classification and representation learning. We propose a novel topological relational inference (TRI) which allows for integrating higher-order graph information to GNNs. We show that the new TRI-GNN outperforms all 14 state-of-the-art baselines on 6 out 7 graphs and exhibit higher robustness to perturbations.
  arXiv  Detail & Related papers  (2021-10-29T04:03:27Z)
• Learning the Implicit Semantic Representation on Graph-Structured Data [57.670106959061634]
  Existing representation learning methods in graph convolutional networks are mainly designed by describing the neighborhood of each node as a perceptual whole. We propose a Semantic Graph Convolutional Networks (SGCN) that explores the implicit semantics by learning latent semantic-paths in graphs.
  arXiv  Detail & Related papers  (2021-01-16T16:18:43Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• 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.