Stanford CS224W: ML with Graphs | 2021 | Lecture 9.2 - Designing the Most Powerful GNNs

TL;DR

Graph Neural Networks (GNNs) can be characterized by their neighborhood aggregation functions. Mean pooling and maximum pooling, used in GCN and GraphSAGE respectively, are not injective and limit the expressive power of GNNs. The most expressive GNN is the Graph Isomorphism Neural Network (GIN), which uses summation pooling.

Transcript

so given the insight so far let's now go and design the most powerful graph neural network so let's go and design the most expressive graph neural network and let's develop the theory that will allow us to do that so the key observation so far is that the expressive power of a graph neural network can be characterized by the expressive power of the... Read More

Key Insights

• ✊ The expressive power of a GNN depends on the expressive power of its neighborhood aggregation function.
• 😫 Mean pooling fails to distinguish multisets with the same proportion of colors, while maximum pooling fails to distinguish multisets with the same set of distinct colors.
• ❓ GIN is the most expressive GNN, using summation pooling and MLPs to create injective aggregation functions.
• 🙈 GIN can be seen as a differentiable neural network version of the WL graph kernel.
• 🌍 GIN is able to capture fine-grained similarity and can distinguish most real-world graph structures.
• 🤑 The expressive power of GNNs can be improved by adding rich features to nodes.

Questions & Answers

Q: What is the key observation regarding the expressive power of GNNs?

The expressive power of a GNN can be characterized by the expressive power of its neighborhood aggregation function. The more expressive the neighborhood aggregation, the more expressive the GNN.

Q: How does mean pooling fail to distinguish multisets?

Mean pooling combines multisets that have the same proportion of colors into the same representation, resulting in lost information. For example, averaging one yellow and one blue message is the same as averaging two yellow and two blue messages.

Q: Why is maximum pooling not an injective operator?

Maximum pooling maps different inputs into the same output, causing collisions and loss of information. Even if the proportions of colors differ, the maximum pooling result will be the same as long as the set of distinct colors is the same.

Q: How does GIN achieve injectivity in its aggregation function?

GIN uses summation pooling to aggregate messages from neighbors and combines them with the node's own message transformed by an MLP. This aggregation is followed by another MLP transformation. The combination of MLPs ensures injectivity.

Summary & Key Takeaways

• Graph Neural Networks' expressive power depends on their neighborhood aggregation functions.

• Mean pooling fails to distinguish multisets with the same proportion of colors, while maximum pooling fails to distinguish multisets with the same set of distinct colors.

• The most expressive GNN is GIN, which uses summation pooling and transforms messages with MLPs to create injective aggregation functions.