Weisfeiler and … (2022-01-31T00:00:00.000000Z)

TL;DR

This work shows that one can increase the expressive power of the Weisfeiler-Leman (WL) test ad infinitum, and proposes an efficient pre-coloring based on spectral features that provably increase the expressiveness of the vanilla WL test.

Abstract

Graph isomorphism testing is usually approached via the comparison of graph invariants. Two popular alternatives that offer a good trade-off between expressive power and computational efficiency are combinatorial (i.e., obtained via the Weisfeiler-Leman (WL) test) and spectral invariants. While the exact power of the latter is still an open question, the former is regularly criticized for its limited power, when a standard configuration of uniform pre-coloring is used. This drawback hinders the applicability of Message Passing Graph Neural Networks (MPGNNs), whose expressive power is upper bounded by the WL test. Relaxing the assumption of uniform pre-coloring, we show that one can increase the expressive power of the WL test ad infinitum. Following that, we propose an efficient pre-coloring based on spectral features that provably increase the expressive power of the vanilla WL test. The above claims are accompanied by extensive synthetic and real data experiments. The code to reproduce our experiments is available at https://github.com/TPFI22/Spectral-and-Combinatorial

Authors

Chaim Baskin

5 papers

A. Mendelson

2 papers

Or Feldman

1 papers

References56 items

Understanding over-squashing and bottlenecks on graphs via curvature

Equivariant Subgraph Aggregation Networks

Weisfeiler and Lehman Go Cellular: CW Networks

Breaking the Limits of Message Passing Graph Neural Networks

Rethinking Graph Transformers with Spectral Attention

TL;DR

Abstract

Authors

Chaim Baskin

5 papers

A. Mendelson

2 papers

Or Feldman

1 papers

TL;DR

Abstract

Authors

References56 items

Understanding over-squashing and bottlenecks on graphs via curvature

Equivariant Subgraph Aggregation Networks

Weisfeiler and Lehman Go Cellular: CW Networks

Breaking the Limits of Message Passing Graph Neural Networks

Rethinking Graph Transformers with Spectral Attention

TL;DR

Abstract

Authors

References56 items

Understanding over-squashing and bottlenecks on graphs via curvature

Equivariant Subgraph Aggregation Networks

Weisfeiler and Lehman Go Cellular: CW Networks

Breaking the Limits of Message Passing Graph Neural Networks

Rethinking Graph Transformers with Spectral Attention

Weisfeiler-Leman, Graph Spectra, and Random Walks

Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks

A Generalization of Transformer Networks to Graphs

Directional Graph Networks

The Surprising Power of Graph Neural Networks with Random Node Initialization

GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

Wasserstein Embedding for Graph Learning

On the Bottleneck of Graph Neural Networks and its Practical Implications

A Deep Learning Approach to Antibiotic Discovery

A Survey on The Expressive Power of Graph Neural Networks

Random Features Strengthen Graph Neural Networks

On the Equivalence between Positional Node Embeddings and Structural Graph Representations

Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View

Provably Powerful Graph Networks

Fast Graph Representation Learning with PyTorch Geometric

Spectral graph theory

Fake News Detection on Social Media using Geometric Deep Learning

Graph Neural Networks: A Review of Methods and Applications

Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

How Powerful are Graph Neural Networks?

Graph Neural Networks for IceCube Signal Classification

Graph Convolutional Neural Networks for Web-Scale Recommender Systems

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

Graph Attention Networks

Representation Learning on Graphs: Methods and Applications

Predicting multicellular function through multi-layer tissue networks

The Weisfeiler-Leman dimension of planar graphs is at most 3

Inductive Representation Learning on Large Graphs

Deep Functional Maps: Structured Prediction for Dense Shape Correspondence

struc2vec: Learning Node Representations from Structural Identity

Neural Message Passing for Quantum Chemistry

Geometric Deep Learning: Going beyond Euclidean data

Semi-Supervised Classification with Graph Convolutional Networks

Revisiting Semi-Supervised Learning with Graph Embeddings

Convolutional Networks on Graphs for Learning Molecular Fingerprints

Deep Graph Kernels

Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors

On the power of combinatorial and spectral invariants

Partial differential equations with numerical methods

An optimal lower bound on the number of variables for graph identification

An optimal lower bound on the number of variables for graph identification

L G ] 3 M ay 2 01 9 A simple yet effective baseline for non-attributed graph classification

A Comprehensive Survey on Graph Neural Networks

Infinite: Spectral and Combinatorial Pre-Colorings A. Proofs In the following proofs we assume the definition of the kWL as defined in [Morris et

Fast Solvers for Solving Shape Matching by Time Integration

THE REDUCTION OF A GRAPH TO CANONICAL FORM AND THE ALGEBRA WHICH APPEARS THEREIN

Struc 2 vec : learning node representations from structural identity

GradientBased Learning Applied to Document Recognition

Gradient-based learning applied to document recognition

Describing Graphs: A First-Order Approach to Graph Canonization

Field of Study

Journal Information

Name

Volume