How Powerful Are Graph Neural Networks (GIN).md

How Powerful Are Graph Neural Networks?

Key points

• Framework for analyzing expresiveness and discriminative power of GNNs
• Weisfeiler-Lehman Isomorphism test is NP-complete. We need to iteratively update 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 WL-test in distinguishing graph structures
• Conditions for the above established in the paper\
• GIN: Graph Isomorphism Network shows representative power is equal to WL-test

Building powerful GNNs

• 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!

GIN (Graph Isomorphism Network)

• UPDATE step:

• 

• Analysis of different aggregators:

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

• 

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