Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness (2023-08-16T00:00:00.000000Z)

TL;DR

This work develops efficient adversarial attacks for subgraph counting and shows that more powerful GNNs fail to generalize even to small perturbations to the graph's structure, and that such architectures also fail to count substructures on out-of-distribution graphs.

Abstract

We perform the first adversarial robustness study into Graph Neural Networks (GNNs) that are provably more powerful than traditional Message Passing Neural Networks (MPNNs). In particular, we use adversarial robustness as a tool to uncover a significant gap between their theoretically possible and empirically achieved expressive power. To do so, we focus on the ability of GNNs to count specific subgraph patterns, which is an established measure of expressivity, and extend the concept of adversarial robustness to this task. Based on this, we develop efficient adversarial attacks for subgraph counting and show that more powerful GNNs fail to generalize even to small perturbations to the graph's structure. Expanding on this, we show that such architectures also fail to count substructures on out-of-distribution graphs.

Authors

Stephan Günnemann

9 papers

Francesco Campi

1 papers

Lukas Gosch

1 papers

TL;DR

Abstract

Authors

References28 items

Adversarial Training for Graph Neural Networks

Revisiting Robustness in Graph Machine Learning

Learning to Count Isomorphisms with Graph Neural Networks

Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs

Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries

How Powerful are K-hop Message Passing Graph Neural Networks

Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness

Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results

Faster Motif Counting via Succinct Color Coding and Adaptive Sampling

Directional Message Passing for Molecular Graphs

Can graph neural networks count substructures?

Multi-Objective Molecule Generation using Interpretable Substructures

An Analysis of Adversarial Attacks and Defenses on Autonomous Driving Models

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Provably Powerful Graph Networks

Graph Neural Networks for Social Recommendation

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

How Powerful are Graph Neural Networks?

Invariant and Equivariant Graph Networks

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

Adversarial Attack on Graph Structured Data

Adversarial Attacks on Neural Networks for Graph Data

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

Neural Message Passing for Quantum Chemistry

Explaining and Harnessing Adversarial Examples

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

Efficient graphlet kernels for large graph comparison

A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names