GIN: Graph Isomorphism Networks
What you'll learn: How GIN uses sum aggregation and injective functions to achieve maximum expressive power for distinguishing graph structures.
The Core Problem
Remember from earlier lessons that graph neural networks need to distinguish between different graph structures (graph isomorphism). Most GNN architectures can't tell apart certain non-isomorphic graphs because their aggregation functions lose information. GIN was designed specifically to be as powerful as the Weisfeiler-Lehman (WL) test—the theoretical gold standard for graph discrimination.
Why Sum Aggregation?
Sum aggregation is provably the most expressive aggregation function when combined with an injective transformation. Here's why:
Think of sum as a "lossless counter" for multisets. If you have different collections of neighbor features, their sums will differ (unlike max or mean, which can produce identical outputs for different inputs). This property is called injectivity—different inputs always produce different outputs.
The GIN Formula
GIN updates node representations using:
h_v^(k+1) = MLP((1 + ε) · h_v^(k) + Σ h_u^(k))
where the sum is over neighbors u of node v, and ε is a learnable parameter (often initialized to 0). The MLP (Multi-Layer Perceptron) must be injective to preserve expressive power—this is guaranteed when it has sufficient capacity.
The (1 + ε) term ensures the node's own features are distinguishable from its aggregated neighborhood.
The Power
By combining sum aggregation with an injective MLP, GIN can distinguish any graphs that the WL test can distinguish—making it maximally expressive among message-passing GNNs.
Key Takeaway: GIN achieves maximum expressive power by using sum aggregation (which preserves multiset information) combined with injective MLPs, making it as discriminative as the Weisfeiler-Lehman graph isomorphism test.