On Graph Neural… (2020-10-28T00:00:00.000000Z)

TL;DR

This work compares multi-layer Graph Neural Networks with a simplified alternative that is called Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node features with certain multi-hop operators on the graph and then applies an MLP in a node-wise fashion.

Abstract

From the perspective of expressive power, this work compares multi-layer Graph Neural Networks (GNNs) with a simplified alternative that we call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node features with certain multi-hop operators on the graph and then applies an MLP in a node-wise fashion. From the perspective of graph isomorphism testing, we show both theoretically and numerically that GA-MLPs with suitable operators can distinguish almost all non-isomorphic graphs, just like the Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions and examining the equivalence classes they induce on rooted graphs, we prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count the number of attributed walks. We also demonstrate via community detection experiments that GA-MLPs can be limited by their choice of operator family, as compared to GNNs with higher flexibility in learning.

Authors

Zhengdao Chen

4 papers

Lei Chen

3 papers

Joan Bruna

1 papers

References57 items

Foundations of Machine Learning

Distance Encoding -- Design Provably More Powerful GNNs for Structural Representation Learning

Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

Simple and Deep Graph Convolutional Networks

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

TL;DR

Abstract

Authors

Zhengdao Chen

4 papers

Lei Chen

3 papers

Joan Bruna

1 papers

TL;DR

Abstract

Authors

References57 items

Foundations of Machine Learning

Distance Encoding -- Design Provably More Powerful GNNs for Structural Representation Learning

Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

Simple and Deep Graph Convolutional Networks

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

TL;DR

Abstract

Authors

References57 items

Foundations of Machine Learning

Distance Encoding -- Design Provably More Powerful GNNs for Structural Representation Learning

Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

Simple and Deep Graph Convolutional Networks

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

DeeperGCN: All You Need to Train Deeper GCNs

On the Bottleneck of Graph Neural Networks and its Practical Implications

SIGN: Scalable Inception Graph Neural Networks

Geometrically Principled Connections in Graph Neural Networks

A Survey on The Expressive Power of Graph Neural Networks

Neural Message Passing on High Order Paths

Generalization and Representational Limits of Graph Neural Networks

Can graph neural networks count substructures?

Random Features Strengthen Graph Neural Networks

Diffusion Improves Graph Learning

Understanding Isomorphism Bias in Graph Data Sets

What graph neural networks cannot learn: depth vs width

Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks

On the equivalence between graph isomorphism testing and function approximation with GNNs

Graph Neural Networks Exponentially Lose Expressive Power for Node Classification

Provably Powerful Graph Networks

Position-aware Graph Neural Networks

Revisiting Graph Neural Networks: All We Have is Low-Pass Filters

Universal Invariant and Equivariant Graph Neural Networks

Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

DeepGCNs: Can GCNs Go As Deep As CNNs?

Towards a practical k-dimensional Weisfeiler-Leman algorithm

Simplifying Graph Convolutional Networks

On the Universality of Invariant Networks

Personalized Embedding Propagation: Combining Neural Networks on Graphs with Personalized PageRank

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

How Powerful are Graph Neural Networks?

Predict then Propagate: Graph Neural Networks meet Personalized PageRank

Representation Learning on Graphs with Jumping Knowledge Networks

MOTIFNET: A MOTIF-BASED GRAPH CONVOLUTIONAL NETWORK FOR DIRECTED GRAPHS

Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning

Inductive Representation Learning on Large Graphs

Supervised Community Detection with Line Graph Neural Networks

Community detection and stochastic block models: recent developments

Deep Sets

Geometric Deep Learning: Going beyond Euclidean data

Semi-Supervised Classification with Graph Convolutional Networks

Instance Normalization: The Missing Ingredient for Fast Stylization

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Deep Residual Learning for Image Recognition

Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift

Adam: A Method for Stochastic Optimization

Spectral Clustering of graphs with the Bethe Hessian

Spectral Networks and Locally Connected Networks on Graphs

Spectral redemption in clustering sparse networks

From local measurements to network spectral properties: Beyond degree distributions

Random Graph Isomorphism

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

Advances in Neural Information Processing

Consider the space of graphs with n vertices

Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names