Can graph neura… (2020-02-10T00:00:00.000000Z)

TL;DR

A local relational pooling approach with inspirations from Murphy et al. (2019) is proposed and demonstrated that it is not only effective for substructure counting but also able to achieve competitive performance on real-world tasks.

Abstract

The ability to detect and count certain substructures in graphs is important for solving many tasks on graph-structured data, especially in the contexts of computational chemistry and biology as well as social network analysis. Inspired by this, we propose to study the expressive power of graph neural networks (GNNs) via their ability to count attributed graph substructures, extending recent works that examine their power in graph isomorphism testing and function approximation. We distinguish between two types of substructure counting: induced-subgraph-count and subgraph-count, and establish both positive and negative answers for popular GNN architectures. Specifically, we prove that Message Passing Neural Networks (MPNNs), 2-Weisfeiler-Lehman (2-WL) and 2-Invariant Graph Networks (2-IGNs) cannot perform induced-subgraph-count of substructures consisting of 3 or more nodes, while they can perform subgraph-count of star-shaped substructures. As an intermediary step, we prove that 2-WL and 2-IGNs are equivalent in distinguishing non-isomorphic graphs, partly answering an open problem raised in Maron et al. (2019). We also prove positive results for k-WL and k-IGNs as well as negative results for k-WL with a finite number of iterations. We then conduct experiments that support the theoretical results for MPNNs and 2-IGNs. Moreover, motivated by substructure counting, we propose a local relational pooling approach with inspirations from Murphy et al. (2019) and demonstrate that it is not only effective for substructure counting but also able to achieve competitive performance on real-world tasks.

Authors

Joan Bruna

9 papers

Zhengdao Chen

4 papers

Lei Chen

3 papers

References94 items

From Graph Low-Rank Global Attention to 2-FWL Approximation

Open Graph Benchmark: Datasets for Machine Learning on Graphs

A Deep Learning Approach to Antibiotic Discovery

A Survey on The Expressive Power of Graph Neural Networks

Graph neural network

Abstract

TL;DR

Abstract

Authors

References94 items

From Graph Low-Rank Global Attention to 2-FWL Approximation

Open Graph Benchmark: Datasets for Machine Learning on Graphs

A Deep Learning Approach to Antibiotic Discovery

A Survey on The Expressive Power of Graph Neural Networks

Graph neural network

TL;DR

Abstract

Authors

References94 items

From Graph Low-Rank Global Attention to 2-FWL Approximation

Open Graph Benchmark: Datasets for Machine Learning on Graphs

A Deep Learning Approach to Antibiotic Discovery

A Survey on The Expressive Power of Graph Neural Networks

Graph neural network

Generalization and Representational Limits of Graph Neural Networks

Composing Molecules with Multiple Property Constraints

Multi-Objective Molecule Generation using Interpretable Substructures

A Deep Learning Approach to Antibiotic Discovery

Neural Subgraph Isomorphism Counting

G2SAT: Learning to Generate SAT Formulas

Hierarchical Graph-to-Graph Translation for Molecules

Experimental performance of graph neural networks on random instances of max-cut

What graph neural networks cannot learn: depth vs width

Strategies for Pre-training Graph Neural Networks

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

Provably Powerful Graph Networks

Position-aware Graph Neural Networks

Cognitive Graph for Multi-Hop Reading Comprehension at Scale

Universal Invariant and Equivariant Graph Neural Networks

Approximation Ratios of Graph Neural Networks for Combinatorial Problems

GNN Explainer: A Tool for Post-hoc Explanation of Graph Neural Networks

GNNExplainer: Generating Explanations for Graph Neural Networks

Relational Pooling for Graph Representations

Fast Graph Representation Learning with PyTorch Geometric

On the Universality of Invariant Networks

Graph Neural Networks: A Review of Methods and Applications

Discovering Molecular Functional Groups Using Graph Convolutional Neural Networks

On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties

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

How Powerful are Graph Neural Networks?

Invariant and Equivariant Graph Networks

Graph Neural Networks for IceCube Signal Classification

N-Gram Graph: Simple Unsupervised Representation for Graphs, with Applications to Molecules

N-Gram Graph, A Novel Molecule Representation

Hierarchical Graph Representation Learning with Differentiable Pooling

Representation Learning on Graphs with Jumping Knowledge Networks

Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation

Link Prediction Based on Graph Neural Networks

GraphRNN: A Deep Generative Model for Graphs

GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models

Junction Tree Variational Autoencoder for Molecular Graph Generation

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

Graph Attention Networks

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

Learning Combinatorial Optimization Algorithms over Graphs

Neural Message Passing for Quantum Chemistry

On the Combinatorial Power of the Weisfeiler-Lehman Algorithm

Deep Sets

MoleculeNet: a benchmark for molecular machine learning

Geometric Deep Learning: Going beyond Euclidean data

Semi-Supervised Classification with Graph Convolutional Networks

Instance Normalization: The Missing Ingredient for Fast Stylization

Comparing structural fingerprints using a literature-based similarity benchmark

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

Deep Residual Learning for Image Recognition

Convolutional Networks on Graphs for Learning Molecular Fingerprints

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

Adam: A Method for Stochastic Optimization

Quantum chemistry structures and properties of 134 kilo molecules

Spectral Networks and Locally Connected Networks on Graphs

Structural Analysis of Viral Spreading Processes in Social and Communication Networks Using Egonets

ZINC: A Free Tool to Discover Chemistry for Biology

PEBBLE GAMES AND LINEAR EQUATIONS

Finding Frequent Subgraphs in Longitudinal Social Network Data Using a Weighted Graph Mining Approach