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

• 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)
• Discovering the Representation Bottleneck of Graph Neural Networks from Multi-order Interactions [51.597480162777074]
  Graph neural networks (GNNs) rely on the message passing paradigm to propagate node features and build interactions. Recent works point out that different graph learning tasks require different ranges of interactions between nodes. We study two common graph construction methods in scientific domains, i.e., emphK-nearest neighbor (KNN) graphs and emphfully-connected (FC) graphs.
  arXiv  Detail & Related papers  (2022-05-15T11:38:14Z)
• 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)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Topological Regularization for Graph Neural Networks Augmentation [12.190045459064413]
  We propose a feature augmentation method for graph nodes based on topological regularization. We have carried out extensive experiments on a large number of datasets to prove the effectiveness of our model.
  arXiv  Detail & Related papers  (2021-04-03T01:37:44Z)
• 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.