The Neighborhood Aggregation Idea

At the heart of any neural network is a simple question: how do we compute a useful feature representation for a given data point? For an image, a Convolutional Neural Network (CNN) slides a kernel across a fixed grid of pixels, aggregating local information to build up features like edges, textures, and shapes. For text, a Recurrent Neural Network (RNN) processes a sequence of words, updating its state at each step.

But what about graphs? A node in a graph doesn't have a fixed grid of neighbors like a pixel, nor does it have an ordered sequence like a sentence. A node can have one neighbor, or one thousand, and there is no canonical ordering to them. This is the central challenge that Graph Neural Networks are designed to solve.

The foundational idea behind GNNs is that a node's features can be enriched by incorporating information from its local neighborhood. Think about a social network. Your own interests and behaviors are often a reflection of your friends' interests. If you want to predict whether you'll enjoy a new movie, knowing whether your close friends liked it is probably a very strong signal. Similarly, in a citation network, the topic of a research paper is closely related to the topics of the papers it cites.

GNNs operationalize this intuition through a process called neighborhood aggregation or message passing. Instead of looking at a node in isolation, we create a new, more powerful representation for it by summarizing the features of its neighbors.

The Aggregation Process

The process is straightforward: for a target node, we gather the feature vectors of all its immediate neighbors and combine them into a single vector. This combined vector acts as a "message" that summarizes the entire neighborhood.

For example, consider a target node A connected to nodes B, C, and D. Each of these nodes has an associated feature vector, let's call them $\mathbf{h}_A$, $\mathbf{h}_B$, $\mathbf{h}_C$, and $\mathbf{h}_D$. The first step in a GNN layer is to aggregate the information from A's neighbors.

The feature vectors of neighboring nodes B, C, and D are collected and passed into an aggregation function. This function produces a single summary vector, or "message," which is then sent to the target node A.

This aggregation must handle the unordered, variable-size nature of a node's neighborhood. We can't simply concatenate the feature vectors, as that would depend on an arbitrary ordering of the neighbors. Instead, we need an operation that is permutation invariant, meaning it produces the same output regardless of the order of its inputs.

Common choices for this aggregation function include:

• Sum: Simply add all the neighbor vectors together.
• Mean: Take the element-wise average of the neighbor vectors.
• Max: Take the element-wise maximum across all neighbor vectors.

By applying an operation like mean, we compute a summary of the neighborhood that is independent of how many neighbors there are or in what order we process them. This aggregated vector represents the collective wisdom of the node's local environment. It's the first half of the general GNN layer formula we saw earlier:

$$\mathbf{m}_{\mathcal{N}(v)}^{(l)} = \text{AGGREGATE}^{(l)} \left( \{ \mathbf{h}_u^{(l)} : u \in \mathcal{N}(v) \} \right)$$

Here, $\mathbf{m}_{\mathcal{N}(v)}^{(l)}$ is the aggregated message for node $v$ at layer $l$, computed by applying the AGGREGATE function to the set of feature vectors ($\mathbf{h}_u^{(l)}$) from all neighboring nodes $u$.

Now that we have a concise summary of the neighborhood, the next step is to use this message to update the target node's own representation. This is the second part of the GNN layer, which we will explore in the next section.