#71 - ZAK JOST (Graph Neural Networks + Geometric DL) [UNPLUGGED]

Foundations

Graph neural networks (GNNs) are revolutionizing the way we process data by leveraging message passing and neighborhood aggregation. Zach Jost explains that the aggregation step is crucial, as it determines the network's ability to distinguish between different graph structures. He highlights the importance of injective aggregation functions to achieve the upper bound of the Weisfeiler-Lehman test, a benchmark for graph isomorphism 1.

The only way you can achieve the upper bound of this one WL test is if you use an injective aggregation function.

--- Zach Jost

Tim Scarfe adds that message passing, akin to pairwise interactions, captures significant information about a system, though it has limitations in distinguishing certain structures like closed triangles 2.

   

Network Comparison

GNNs offer unique advantages over other neural networks, such as transformers, by focusing on sparse interactions. Zach Jost compares transformers to fully connected graphs, where every node interacts with every other node, resulting in a quadratic number of interactions 3. GNNs, on the other hand, are more efficient by considering only relevant connections, which can be advantageous when the graph encodes meaningful relationships.

If you have the computational power to consider the interactions of everything with everything else, I don't think we're going to beat that.

--- Zach Jost

Tim Scarfe notes that despite their differences, both GNNs and transformers perform information diffusion, albeit through different mechanisms 4.

   

Challenges

GNNs face challenges like over-squashing and over-smoothing, which can limit their expressive power. Zach Jost discusses graph rewiring as a solution, where edges are selectively removed or added to optimize information flow and reduce over-squashing 5. This technique involves updating the graph structure to better reflect the underlying data relationships.

There are certain edges that cause this over-squashing problem, because they will connect a node to a different disparate connect of densely connected things.

--- Zach Jost

Tim Scarfe highlights Zach Jost's work on breaking the bottleneck of GNNs by addressing these challenges, thereby enhancing their expressive capabilities 6.