#85 Dr. Petar Veličković (Deepmind) - Categories, Graphs, Reasoning [NEURIPS22 UNPLUGGED]

Graph Learning

Graph representation learning is a pivotal aspect of neural networks, focusing on how graph structures influence data propagation and model efficacy. Petar Veličković highlights a common issue in this field, where edge messages are reused for both edge and node outputs, creating representational pressure that affects extrapolation performance 1. He explains that splitting the message function into two streams can significantly improve performance in edge-centric algorithms.

Just because you can implement it, doesn't mean that there's something not potentially a bit tricky going on in the sense that you're putting a bit of representational pressure on that edge message.

--- Petar Veličković

Additionally, Veličković addresses the over-squashing problem in graph neural networks, a challenge that arises from the topology of the graph rather than the model parameters 2. This issue requires exponential feature space for efficient node communication, particularly in tree structures, highlighting a fundamental problem in data propagation.

   

Expander Graphs

Expander graphs offer a solution to the over-squashing problem by enhancing global information propagation efficiency within graph neural networks. Petar Veličković explains that these graphs have low bottlenecks and a low diameter, allowing for efficient global data travel without the need for dense connections 3. This method supports scalable complexity and avoids the computational burden of preprocessing input graphs.

We propose to propagate information over these expander graphs, which are known constructs from graph theory.

--- Petar Veličković

By using sparse expander graphs, Veličković's approach maintains efficient communication properties while reducing computational costs, making it a promising direction for future research in graph neural networks 4.

   

Category Theory

Category theory provides a framework to innovate graph neural network designs, aligning network behavior more closely with target algorithms. Petar Veličković uses category theoretic tools to study how graph neural networks can emulate classical computer science algorithms, such as pathfinding, by encoding and processing data in high-dimensional spaces 5. This approach allows for the creation of commutative diagrams, which ensure that algorithmic steps and neural network processes lead to the same outcomes.

Category theory seems like a very nice language to study these kinds of interchangeable sequences of operations.

--- Petar Veličković

Moreover, Veličković's research demonstrates that alternating input graphs with expander graphs improves performance across datasets, offering a statistically significant advantage over baseline models 6. This integration of category theory and graph neural networks paves the way for more robust and efficient computational functions.