How Powerful are Graph Neural Networks?

Inside the paper

The problem

Graph neural networks often combine information from neighbouring nodes, but different ways of combining it can erase different structural details. The paper asks which graph distinctions such models can represent, rather than judging them only by benchmark accuracy.

The idea

The authors compare neighbourhood aggregation with the Weisfeiler–Lehman graph test and characterize when aggregation preserves distinct neighbourhoods. They use that analysis to construct a graph isomorphism network, or GIN.

How it works

• Treat the features of a node’s neighbours as a multiset, where repeated features matter as well as their values.
• A sufficiently expressive sum-based aggregation can distinguish bounded multisets under the paper’s assumptions; mean and max operations can collapse some different multisets.
• GIN combines the node’s own representation with a sum of its neighbours’ representations and applies a multilayer perceptron.
• For whole-graph prediction, a readout combines node representations, including information from different network depths.

What it showed

The analysis bounds the graph-distinguishing ability of the studied aggregation networks by the Weisfeiler–Lehman test and gives conditions for matching it. On graph classification benchmarks, GIN fits training data better than several less expressive variants and performs well on test sets.

Read it for

Read Figure 1 and Sections 3–4 for the comparison and construction, then Figures 2–3 for concrete aggregation failures. Section 7 checks the ideas empirically; the appendix proofs can be saved for a deeper mathematical pass.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.