Defining expressiveness

Neural networks are used to approximate functions. This is justified by the universal approximation theorem, which states that a feedforward neural network with only one layer can approximate any smooth function. But what about universal function approximation on graphs? This is a more complex problem that requires the ability to distinguish graph structures.

With GNNs, our goal is to produce the best node embeddings possible. This means that different nodes must have different embeddings, and similar nodes must have similar embeddings. But how do we know that two nodes are similar? Embeddings are computed using node features and connections. Therefore, we have to compare their features and neighbors to distinguish nodes.

In graph theory, this is referred to as the graph isomorphism problem. Two graphs are isomorphic (“the same”) if they have the same connections, and their only difference is a permutation of their nodes (see Figure 9.1)...