On the equivale… (2019-05-29T00:00:00.000000Z)

TL;DR

It is proved that order-2 Graph G-invariant networks fail to distinguish non-isomorphic regular graphs with the same degree, and is extended to a new architecture, Ring-GNNs, which succeeds on distinguishing these graphs and provides improvements on real-world social network datasets.

Abstract

Graph neural networks (GNNs) have achieved lots of success on graph-structured data. In the light of this, there has been increasing interest in studying their representation power. One line of work focuses on the universal approximation of permutation-invariant functions by certain classes of GNNs, and another demonstrates the limitation of GNNs via graph isomorphism tests. Our work connects these two perspectives and proves their equivalence. We further develop a framework of the representation power of GNNs with the language of sigma-algebra, which incorporates both viewpoints. Using this framework, we compare the expressive power of different classes of GNNs as well as other methods on graphs. In particular, we prove that order-2 Graph G-invariant networks fail to distinguish non-isomorphic regular graphs with the same degree. We then extend them to a new architecture, Ring-GNNs, which succeeds on distinguishing these graphs and provides improvements on real-world social network datasets.

Authors

Joan Bruna

9 papers

Zhengdao Chen

4 papers

Lei Chen

3 papers

References55 items

The expressive power of kth-order invariant graph networks

Can graph neural networks count substructures?

Stability of Graph Scattering Transforms

Provably Powerful Graph Networks

Position-aware Graph Neural Networks

TL;DR

Abstract

Authors

Joan Bruna

9 papers

Zhengdao Chen

4 papers

Lei Chen

3 papers

TL;DR

Abstract

Authors

References55 items

The expressive power of kth-order invariant graph networks

Can graph neural networks count substructures?

Stability of Graph Scattering Transforms

Provably Powerful Graph Networks

Position-aware Graph Neural Networks

TL;DR

Abstract

Authors

References55 items

The expressive power of kth-order invariant graph networks

Can graph neural networks count substructures?

Stability of Graph Scattering Transforms

Provably Powerful Graph Networks

Position-aware Graph Neural Networks

Universal Invariant and Equivariant Graph Neural Networks

Relational Pooling for Graph Representations

On the Universality of Invariant Networks

LanczosNet: Multi-Scale Deep Graph Convolutional Networks

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

How Powerful are Graph Neural Networks?

Invariant and Equivariant Graph Networks

Representation Learning on Graphs with Jumping Knowledge Networks

REVISED NOTE ON LEARNING QUADRATIC ASSIGNMENT WITH GRAPH NEURAL NETWORKS

Universal Approximations of Invariant Maps by Neural Networks

Mapping Images to Scene Graphs with Permutation-Invariant Structured Prediction

Covariant Compositional Networks For Learning Graphs

Graph Attention Networks

Representation Learning on Graphs: Methods and Applications

Weisfeiler-Lehman Neural Machine for Link Prediction

A Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks

Inductive Representation Learning on Large Graphs

Supervised Community Detection with Line Graph Neural Networks

Neural Message Passing for Quantum Chemistry

Equivariance Through Parameter-Sharing

Geometric Deep Learning: Going beyond Euclidean data

Semi-Supervised Classification with Graph Convolutional Networks

Convolutional Networks on Graphs for Learning Molecular Fingerprints

Deep Graph Kernels

Adam: A Method for Stochastic Optimization

Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs

Spectral redemption in clustering sparse networks

On the power of combinatorial and spectral invariants

A tutorial on spectral clustering

Semidefinite Programming Relaxations for the Quadratic Assignment Problem

The elements of integration and Lebesgue measure

Fractional isomorphism of graphs

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

Approximation capabilities of multilayer feedforward networks

A note on compact graphs

Approximation by superpositions of a sigmoidal function

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

Matrix multiplication via arithmetic progressions

Graph isomorphism and theorems of Birkhoff type

Random Graph Isomorphism

Probabilistic Symmetries and Invariant Neural Networks

A Comprehensive Survey on Graph Neural Networks

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

The Graph Neural Network Model

Special Issue devoted to Selected Papers presented at the Workshop on Spectral Graph Theory with Applications on Computer Science, Combinatorial Optimization and Chemistry

Graph Isomorphism Network combined with Relational pooling by

• Order-2 Graph G-invariant Networks: G-invariant networks based on

Graph Isomorphism Network by [30]. We took their performance results on the IMDB datasets reported in [30], and their performance results on the Circular Skip Link graphs experiments reported in

Weisfeiler-Leman and Graph Spectra

Line Graph Neural Networks proposed by [5]. In our experiments, the sGN N models have 5 layers and hidden layer dimension (i.e. d k ) 64

Field of Study

Venue Information

Name

Type

URL

Alternate Names