Update Functions and Non-Linearities

Graph Neural Networks (GNNs) generate an updated representation for a node by integrating new information, often derived from messages gathered from its neighbors, with the node's current state. This integration is a two-part process: combining the gathered message with the node's current state and then transforming it. This update ensures that the node's new feature vector contains both its own prior information and the collective wisdom of its local neighborhood.

Let's denote the aggregated message vector for a node $v$ as $\mathbf{m}_{\mathcal{N}(v)}^{(l+1)}$ . This vector is the output of the AGGREGATE function we discussed previously. The update function's job is to combine this message with the node's own feature vector from the previous layer, $\mathbf{h}_v^{(l)}$ .

Combining Self-Features and Neighbor Messages

A common and effective strategy for combining these two vectors is to first concatenate them and then pass the result through a standard neural network layer. This layer consists of a linear transformation (a weight matrix) followed by a non-linear activation function.

Mathematically, this update operation can be written as:

\mathbf{h}_v^{(l+1)} = \sigma \left( \mathbf{W}^{(l)} \cdot \text{CONCAT}(\mathbf{h}_v^{(l)}, \mathbf{m}_{\mathcal{N}(v)}^{(l+1)}) \right)

Let's break this down:

$\text{CONCAT}(\mathbf{h}_v^{(l)}, \mathbf{m}_{\mathcal{N}(v)}^{(l+1)})$ : The node's own vector $\mathbf{h}_v^{(l)}$ is concatenated with the aggregated message vector $\mathbf{m}_{\mathcal{N}(v)}^{(l+1)}$ . If both are of dimension $d$ , the resulting vector has dimension $2d$ . This explicitly preserves the information from both sources without immediately mixing them.
$\mathbf{W}^{(l)}$ : This is a learnable weight matrix for layer $l$ . It acts as a linear transformation, mapping the concatenated vector from its current dimension (e.g., $2d$ ) to the desired output dimension for the next layer (e.g., $d'$ ). This is where the model learns to extract the most relevant signals from the combined information.
$\sigma$ : This is a non-linear activation function, which we will discuss next.

The diagram below illustrates this flow. The node's previous representation and the aggregated message are combined, processed by a linear layer, and passed through an activation function to produce the node's new representation.

The update step for a single node. The process combines the node's existing feature vector with the aggregated message, then transforms this combined vector to produce the new representation for the next layer.

An alternative approach, seen in architectures like Graph Convolutional Networks (GCNs), applies separate linear transformations to the self-vector and the aggregated message before combining them, typically with a sum. We will examine that specific formulation in the next chapter. For a general message passing network, the concatenation method is a powerful and intuitive starting point.

The Importance of Non-Linearities

The activation function, denoted by $\sigma$ , is an essential component of any neural network, and GNNs are no exception. Its purpose is to introduce non-linearity into the model.

If we were to omit the activation function, each GNN layer would simply be a sequence of linear operations (aggregation, which is often linear, followed by a linear transformation). Stacking multiple such layers would be pointless, as a sequence of linear transformations can always be mathematically reduced to a single, more complex linear transformation. The model's capacity would be severely limited, and it would fail to learn complex patterns in the data.

The most widely used activation function in modern deep learning, including GNNs, is the Rectified Linear Unit (ReLU). It is defined as:

\text{ReLU}(x) = \max(0, x)

ReLU is computationally efficient and works well in practice. It simply replaces any negative values in the feature vector with zero, allowing the network to model non-linear relationships by selectively "activating" certain features. While other functions like LeakyReLU, Sigmoid, or Tanh exist, ReLU is a strong default choice for hidden layers in a GNN.

By combining the aggregated neighborhood message with a node's own state and then applying a non-linear transformation, a GNN layer computes a richer, higher-level representation for each node. This new representation captures both the node's individual attributes and its structural role within its local environment.

Was this section helpful?

References

Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf and Max Welling, 2017 International Conference on Learning Representations (ICLR) DOI: 10.48550/arXiv.1609.02907 - This foundational paper introduces Graph Convolutional Networks (GCNs), which use a specific update function combining separate linear transformations and summation before a non-linearity. This approach is explicitly mentioned as an alternative in the section and illustrates how non-linearities are integrated into GNN updates.
Inductive Representation Learning on Large Graphs, William L. Hamilton, Rex Ying, and Jure Leskovec, 2017 Advances in Neural Information Processing Systems (NIPS) DOI: 10.48550/arXiv.1706.02216 - This paper introduces GraphSAGE, a prominent GNN architecture that employs update mechanisms similar to the general concatenation approach described in the section, often combining aggregated messages with self-features and applying non-linear transformations.
Graph Representation Learning, William L. Hamilton, 2020 Synthesis Lectures on Artificial Intelligence and Machine Learning, Vol. 14 (Morgan & Claypool Publishers) DOI: 10.2200/S01045ED1V01Y202009AIM046 - This textbook provides a comprehensive theoretical and practical treatment of GNNs, including detailed explanations of message passing paradigms, aggregation and update functions, and the role of non-linearities in different GNN architectures.
Graph Neural Networks: A Review of Methods and Applications, Jie Zhou, Ganqu Cui, Zhengyan Li, Mingxuan Wang, Lei Wang, 2021 AI Open, Vol. 2 (Elsevier) DOI: 10.1016/j.aiopen.2021.01.001 - This survey paper categorizes and reviews various GNN models, discussing their message passing mechanisms, including different aggregation and update function designs, and the importance of non-linear transformations in building expressive GNN layers.