Course contentsShow
← Machine Learning and Deep Learning
Lesson 2513 of 3,53854. Graph Neural NetworksFree lesson

GIN: Graph Isomorphism Networks

Sum aggregation and injective functions for maximizing expressive power based on the WL test.

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.