The Message Passing Framework Revisited

The principle of message passing is fundamental to most Graph Neural Networks. This mechanism allows nodes in a graph to iteratively aggregate information from their local neighborhoods, enabling the network to learn representations that capture both node features and the graph's topology. The generalized message passing framework will be formally examined, and its inherent limitations, particularly concerning expressive power, will be discussed.

The Generalized Message Passing Framework

Many popular GNN architectures can be unified under a common framework. In this framework, each node $v$ updates its hidden state $\mathbf{h}_v$ at layer $k$ based on its own state and the states of its neighboring nodes $\mathcal{N}(v)$ from the previous layer $k-1$. The update process for a single node $v$ at layer $k$ is typically defined by two functions: AGGREGATE and UPDATE:

$$\mathbf{h}_v^{(k)} = \text{UPDATE}^{(k)} \left( \mathbf{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)} \left( \{ \mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v) \} \right) \right)$$

Let's break down the components:

• $\mathbf{h}_v^{(k)} \in \mathbb{R}^{d_k}$: The feature vector (or hidden state) of node $v$ at layer $k$. $d_k$ is the dimensionality at this layer. $\mathbf{h}_v^{(0)}$ is usually the initial node feature vector.
• $\mathcal{N}(v)$: The set of neighbors of node $v$. Variations exist, such as including $v$ itself (adding self-loops).
• $\text{AGGREGATE}^{(k)}$: This function combines the feature vectors from the neighbors of $v$. A significant requirement for AGGREGATE is permutation invariance. Since nodes in a neighborhood do not have a natural order, the aggregation function must produce the same output regardless of the order in which neighbor features are processed. Common choices include element-wise sum, mean, or maximum operations.
  • SUM: $\text{AGGREGATE} = \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(k-1)}$
  • MEAN: $\text{AGGREGATE} = \frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(k-1)}$
  • MAX: $\text{AGGREGATE} = \max_{u \in \mathcal{N}(v)} \{ \mathbf{h}_u^{(k-1)} \}$ (element-wise max)
• $\text{UPDATE}^{(k)}$: This function takes the aggregated neighborhood information and the node's own previous state $\mathbf{h}_v^{(k-1)}$ to compute the node's new state $\mathbf{h}_v^{(k)}$. This function is often implemented using neural network layers, such as a simple linear transformation followed by a non-linearity, or more complex functions like Multi-Layer Perceptrons (MLPs) or Recurrent Neural Network (RNN) cells (like GRUs).

Different GNN models instantiate this framework with specific choices for AGGREGATE and UPDATE. For example:

• Graph Convolutional Network (GCN): Often uses a normalized sum (mean aggregation including self-loop) followed by a linear transformation and non-linearity.
• GraphSAGE: Explicitly samples neighbors and allows for various aggregators (mean, max-pooling, LSTM).
• Graph Isomorphism Network (GIN): Uses sum aggregation combined with an MLP for the update function, shown to be maximally expressive among simple aggregators (as we'll discuss next).

Expressive Power and its Limits

While flexible, this message passing framework has fundamental limitations in its ability to distinguish between different graph structures. The expressive power of a GNN refers to its capacity to map non-isomorphic graphs (graphs with different structures) to different representations or outputs. Ideally, a powerful GNN should be able to distinguish between any two graphs that are not structurally identical.

How can we measure this? A common benchmark is the Weisfeiler-Lehman (WL) test of graph isomorphism. Specifically, the 1-WL test (the simplest variant) provides an upper bound on the discriminative power of standard message-passing GNNs.

The 1-WL Test

The 1-WL test is an iterative algorithm that aims to determine if two graphs are non-isomorphic. It works by assigning an initial "color" (or label) to each node (often based on node degrees or initial features) and then iteratively refining these colors based on the colors of their neighbors:

1. Initialization: Assign an initial color $c_v^{(0)}$ to each node $v$.
2. Iteration ($k=1, 2, ...$): For each node $v$, collect the colors of its neighbors from the previous iteration into a multiset: $M_v^{(k-1)} = \{ \{ c_u^{(k-1)} : u \in \mathcal{N}(v) \} \}$.
3. Hashing: Assign a new color $c_v^{(k)}$ based on the node's previous color $c_v^{(k-1)}$ and the multiset of neighbor colors $M_v^{(k-1)}$. This is typically done using a hash function $H$ that maps unique pairs $(c_v^{(k-1)}, M_v^{(k-1)})$ to unique new colors: $c_v^{(k)} = H(c_v^{(k-1)}, M_v^{(k-1)})$.
4. Convergence: Repeat steps 2 and 3 until the set of colors across the graph converges (no new colors are generated).
5. Comparison: Two graphs G1 and G2 are deemed potentially isomorphic by the 1-WL test if the histograms (counts) of their final node colors are identical. If the histograms differ at any iteration, the graphs are definitely non-isomorphic.

The Connection: Message Passing as 1-WL

The connection between the message passing framework and the 1-WL test becomes apparent when comparing their update steps. The AGGREGATE function in a GNN effectively computes a representation of the multiset of neighbor features $\{\mathbf{h}_u^{(k-1)} : u \in \mathcal{N}(v)\}$. The UPDATE function then combines this aggregated information with the node's own previous state $\mathbf{h}_v^{(k-1)}$ to produce the new state $\mathbf{h}_v^{(k)}$.

This process directly parallels the 1-WL test's aggregation of neighbor colors (multiset $M_v^{(k-1)}$) and subsequent hashing with the node's current color $c_v^{(k-1)}$ to generate the new color $c_v^{(k)}$.

The critical insight, proven formally by Morris et al. (2019) and Xu et al. (2019), is that standard message-passing GNNs (using permutation-invariant aggregators like sum, mean, max) cannot be more powerful than the 1-WL test. If the AGGREGATE and UPDATE functions are injective (meaning they map distinct inputs to distinct outputs, like a perfect hash function in 1-WL), the GNN achieves the maximum expressive power equivalent to the 1-WL test (as GIN does). However, they cannot surpass it.

Implications of the 1-WL Limit

This theoretical upper bound means that any two graph structures that the 1-WL test cannot distinguish, a standard message-passing GNN also cannot distinguish. The 1-WL test is known to fail on certain classes of graphs, such as distinguishing some regular graphs (where all nodes have the same degree).

Example of two non-isomorphic graphs (a 6-cycle and two disjoint 3-cycles) that the 1-WL test, and thus standard message-passing GNNs, cannot distinguish if initial node features are uniform. Both are 2-regular graphs.

If all nodes start with the same initial feature vector $\mathbf{h}^{(0)}$, after one layer of message passing, all nodes in both graphs will have identical representations (since every node has two neighbors with feature $\mathbf{h}^{(0)}$). This identity persists through subsequent layers. Consequently, a GNN based purely on this framework cannot differentiate between these structures for tasks like graph classification.

Understanding this limitation is important. It motivates the development of more powerful GNN architectures, often referred to as "higher-order" GNNs or models incorporating subgraph information, which aim to overcome the constraints of the basic message passing and the 1-WL test. We will look at some of these advanced architectures and techniques in subsequent chapters. For now, recognizing the boundaries of the standard message passing framework provides a solid foundation for appreciating these more complex models.