How Powerful are Graph Neural Networks? (Graph Isomorphism Network - GIN)

Theoretically characterized GNN expressive power through the Weisfeiler-Lehman (1-WL) graph isomorphism test, proving injective sum aggregation is optimal.

The theoretical standard for whole-graph classification in molecular property prediction, drug discovery, and biochemical graphs.

Assumptions

• Representing multiset neighborhood features via sum aggregation followed by MLPs models injective functions over multiset inputs

Limitations

• Bounded by the 1-WL test: cannot detect simple non-isomorphic substructures like distinguishing 6-cycles from pairs of triangles