Permutation Invariance and Equivariance

A defining characteristic of a graph is that, unlike the pixels in an image or the words in a sentence, its nodes do not have a natural order. If you ask for the neighbors of a node, the set you receive, {u_1, u_2, u_3}, is identical to the set {u_3, u_1, u_2}. This lack of canonical ordering poses a significant challenge for standard neural networks like Multi-Layer Perceptrons (MLPs), which expect their input features to be in a fixed, ordered vector. If you were to feed the features of neighboring nodes to an MLP, the output would change depending on the arbitrary order you chose, leading to inconsistent and meaningless results.

To operate effectively on graphs, a neural network layer must respect this fundamental property. This is achieved through two related principles: permutation invariance and permutation equivariance.

Permutation Invariance in Aggregation

Let's first consider the AGGREGATE function in our message passing formula. Its job is to take the set of feature vectors from a node's neighbors, { \mathbf{h}_u^{(l)} : u \in \mathcal{N}(v) \}, and combine them into a single message vector, $\mathbf{m}_{\mathcal{N}(v)}$.

For the network to produce a consistent output regardless of how we order the neighbors, the aggregation function must be permutation invariant. A function $f$ is permutation invariant if its output remains the same even when the order of its inputs is shuffled.

$$f(x_1, x_2, \dots, x_n) = f(x_{\pi(1)}, x_{\pi(2)}, \dots, x_{\pi(n)})$$

Here, $\pi$ is any permutation of the indices $\{1, 2, \dots, n\}$.

The aggregation functions we discussed in the previous section, such as sum, mean, and max, all have this property. For example, summing the feature vectors of neighbors will produce the same result no matter which neighbor you start with.

• Sum: $\sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(l)}$
• Mean: $\frac{1}{|\mathcal{N}(v)|} \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(l)}$
• Max: $\max_{u \in \mathcal{N}(v)} (\mathbf{h}_u^{(l)})$ (element-wise max)

By using a permutation-invariant function for aggregation, we guarantee that the message generated from a node's neighborhood is based only on the set of neighbors, not on any artificial ordering we might impose.

Permutation Equivariance in GNN Layers

While the aggregation step is invariant to the order of a single node's neighbors, the entire GNN layer exhibits a slightly different property when considering all nodes in the graph: permutation equivariance.

A function is permutation equivariant if permuting its inputs results in an identically permuted output. Let's say we have a function $F$ that takes a set of node features $\mathbf{H}$ (a matrix where each row is a node's feature vector) and outputs a new set of features $\mathbf{H}'$. If we permute the nodes in the input graph (which corresponds to permuting the rows of $\mathbf{H}$ and the rows/columns of the adjacency matrix), the output features $\mathbf{H}'$ will be permuted in the exact same way.

Formally, if $\mathbf{P}$ is any permutation matrix that reorders the nodes, then a function $F$ is equivariant if:

$$F(\mathbf{P} \mathbf{A} \mathbf{P}^T, \mathbf{P} \mathbf{H}) = \mathbf{P} F(\mathbf{A}, \mathbf{H})$$

Here, $\mathbf{A}$ is the adjacency matrix. The operation $\mathbf{P} \mathbf{A} \mathbf{P}^T$ reorders the adjacency matrix according to the permutation, and $\mathbf{P} \mathbf{H}$ reorders the feature matrix. The equation states that permuting the graph's inputs and then applying the GNN layer is the same as applying the GNN layer first and then permuting its outputs.

The message passing mechanism naturally achieves this. Each node's new representation $\mathbf{h}_v^{(l+1)}$ is computed based on its own state and an aggregated message from its neighbors. Since this computation is performed for every node in parallel, if we re-index the nodes of the graph, the output embeddings will be re-indexed in the same way. The embedding for node A will still be the embedding for node A, even if we now call it node B.

Diagram illustrating invariance and equivariance. For invariance, different orderings of neighbor features fed into the AGGREGATE function produce the same output message. For equivariance, permuting the order of all nodes in the graph before the GNN Layer results in an identically permuted set of output node representations.

Why These Properties Are Important

Permutation invariance and equivariance are not just theoretical properties. They are the reason GNNs can learn functions that depend on the graph's underlying structure, or topology, rather than on an arbitrary node ordering. A model that is not permutation equivariant might learn that "the first node in the list is important," which is a meaningless and non-generalizable pattern.

By adhering to these principles, GNNs can:

1. Handle graphs of arbitrary structure and size: The message passing operation is defined locally for each node, making it independent of the total number of nodes or their specific arrangement.
2. Learn generalizable patterns: The model learns features based on neighborhood structures (e.g., a node's role as a "hub" or being on a "bridge" between communities), which are consistent even if the node labels or their storage order changes.

In essence, these properties ensure that the GNN is learning about the graph itself, not about the way we chose to write it down in memory. This is fundamental to building powerful and reliable models for graph-structured data.