Why I'm Lukewarm on Graph Neural Networks

Hello everyone…

I’ve been exploring Graph Neural Networks (GNNs) recently, but I find myself somewhat hesitant about fully embracing them.

Imagine storing information about connections in a big grid. For most real-world connections (like social networks), the grid is mostly empty spaces. That’s because most things aren’t connected to everything else. Because of all those empty spaces, it’s actually more efficient to focus on the connections that actually exist (the non-zero numbers). This makes analyzing these connections more like solving puzzles (discrete math) which can be tricky, rather than using smooth, flowing calculations (continuous math) which are easier for computers.

1 Like

hey!

Absolutely, that’s a great way to put it! This concept is particularly important in the field of graph theory, which is a fundamental part of discrete mathematics. In social networks, for example, each person can be thought of as a node, and each connection or relationship is an edge.

Given that most people aren’t connected to everyone else, the resulting matrix (or adjacency matrix) that represents these connections is sparse, meaning it contains many zeros.

Focusing on the non-zero elements, or the actual connections, can significantly reduce the complexity of the problem.

This approach is not only more efficient in terms of storage but also in terms of computational power. It allows algorithms to work faster because they don’t need to process the empty spaces.

This efficiency is why specialized data structures, like adjacency lists or sparse matrices, are often used instead of dense matrices.

These structures store only the existing connections, making operations like searching for a specific connection, adding a new connection, or finding all connections of a specific node much quicker.

Moreover, analyzing these sparse matrices involves techniques from combinatorics and graph theory.

These areas of discrete math are all about solving puzzles—understanding the structure and properties of graphs, finding patterns, and solving problems like finding the shortest path between nodes or detecting clusters of interconnected nodes.

In contrast, continuous math, such as calculus, deals with smoothly varying quantities and is often used in problems involving continuous change.

While continuous math is integral to fields like physics and engineering, discrete math is essential for computer science, network analysis, and many real-world applications where data is inherently discrete.

So, while it might seem tricky, understanding and working with discrete structures can provide powerful insights and solutions for analyzing complex networks and connections.

Graph Neural Networks (GNNs) offer advantages over simpler embedding methods but are overhyped. The field is crowded with incremental, often impractical advancements. Basic methods sometimes perform just as well and are more efficient. Improvements in GNNs should focus on practical, scalable solutions rather than theoretical innovations that don’t translate well to real-world applications.

1 Like

As someone who uses GNNs at a large scale, I have a few insights to share.

Firstly, the scale problem in the industry has largely been resolved. We train GNNs on billions of nodes and tens of billions of edges, and can scale horizontally without issues. It’s unlikely that anyone uses Networkx for large graphs. You’re correct that this often excludes techniques requiring global computation, except in special cases.

Most literature on the topic is unhelpful for the reasons you mentioned.

Regarding your Euclidean argument, it’s flawed because fitting a space into an adjacency matrix isn’t related to being Euclidean. Using the adjacency matrix as the distance norm isn’t useful or interesting. Points incan’t be placed in an adjacency matrix, yet it remains a Euclidean space. Your argument mainly relies on fully connected graphs, which are rare in real-world scenarios.