How Expressive are Graph Neural Networks?

Idea : Aggregate Neighbors

Local Neighborhood Structures

• To generate a node embedding , GNNs use a computational graph corresponding to a subtree rooted around each node.

Design the most powerfull GNNs

Expressive Power of GNNs

• Key observation: Expressive power of GNNs can be characterized by that of neighbor aggregation functions they use.

Injective multi-set function

Full model of GIN

MLP

Relation to WL Graph Kernel

Recall : Color refinement algorithm in WL kernel