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

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.

arXiv commentAAAI'24. Contains 17 pages, 4 figures

References in corpus (35)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Decoupled Weight Decay Regularization
• Semi-Supervised Classification with Graph Convolutional Networks
• Neural Message Passing for Quantum Chemistry
• Spectral Networks and Locally Connected Networks on Graphs
• Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
• Fast Graph Representation Learning with PyTorch Geometric
• Representation Learning on Graphs with Jumping Knowledge Networks
• DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
• Diffusion-Convolutional Neural Networks
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning
• TUDataset: A collection of benchmark datasets for learning with graphs
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting
• Residual Gated Graph ConvNets
• Principal Neighbourhood Aggregation for Graph Nets
• HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs
• Graph Neural Networks Exponentially Lose Expressive Power for Node Classification
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Simplicial Neural Networks
• Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks
• A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants
• Hierarchical Inter-Message Passing for Learning on Molecular Graphs
• Homologies of path complexes and digraphs
• Understanding over-squashing and bottlenecks on graphs via curvature
• Natural Graph Networks
• Topological Deep Learning: Going Beyond Graph Data
• Cell Attention Networks
• Architectures of Topological Deep Learning: A Survey of Message-Passing Topological Neural Networks
• DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks
• UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks
• Principled Simplicial Neural Networks for Trajectory Prediction
• pathGCN: Learning General Graph Spatial Operators from Paths
• Path Neural Networks: Expressive and Accurate Graph Neural Networks
• CIN++: Enhancing Topological Message Passing

Cited by in corpus (1)

• The Expressive Power of Graph Neural Networks: A Survey