🥍

How Powerful Are Graph Neural Networks (GIN)

Read the paper

Key Points

Framework for analyzing expressiveness and discriminative power of GNNs.
The Weisfeiler-Lehman (WL) Isomorphism test is NP-complete. We need to iteratively update a node's feature vector by aggregating the neighborhood's feature vectors.
Set of node's neighborhood feature vectors: multiset with possibly repeating elements.
GNNs proven to be at most as powerful as the WL-test in distinguishing graph structures.
Conditions for the above established in the paper.
GIN: Graph Isomorphism Network shows representative power is equal to the WL-test.

Building Powerful GNNs

Diagram showing the WL-test iterative relabeling process for graph isomorphism detection.

To study the representational power of a GNN, we analyze when a GNN maps two nodes to the same location in the embedding space.
- Intuitively, a maximally powerful GNN maps two nodes to the same location only if they have identical subtree structures with identical features on the corresponding nodes.
A maximally powerful GNN would never map two different neighborhoods to the same representation!

Illustration of how different neighborhood structures must map to different embeddings in a maximally powerful GNN.

GIN (Graph Isomorphism Network)

UPDATE step:

GIN update rule: $h_v^{(k)} = \text{MLP}^{(k)}\left((1+\epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in N(v)} h_u^{(k-1)}\right)$

Analysis of Different Aggregators

Comparison of sum, mean, and max aggregators: sum captures the full multiset, mean captures the proportion/distribution of elements, and max ignores multiplicities.

Notice sum captures the full multiset, mean captures the proportion/distribution of elements of a given type, and the max aggregator ignores multiplicities.

Venn diagram showing the hierarchy of distinguishing power: sum > mean > max for multiset discrimination.

Hence the GIN is maximally powerful when it can distinguish multisets, using "SUM" as the READOUT step in the previous equation.