Message Passing

Each node collects feature vectors from its immediate neighbors using a permutation-invariant aggregation function. Common aggregators include:

• Sum: Preserves total neighborhood magnitude
• Mean: Normalizes for varying node degrees
• Max: Captures the most salient neighbor features

The choice of aggregator directly impacts the model's representational capacity and inductive bias.

Message passing operates over multiple layers or hops, with each iteration expanding the node's receptive field. After k layers, a node's representation incorporates information from its k-hop neighborhood. This mirrors the Weisfeiler-Lehman isomorphism test, where deeper iterations capture increasingly global graph structure.

The message function computes the information transmitted along each edge. It typically transforms the source node's features, often conditioned on edge attributes. In a Graph Convolutional Network (GCN), the message is simply the neighbor's feature vector. In a Graph Attention Network (GAT), the message is weighted by a learned attention coefficient.

After aggregation, an update function combines the aggregated neighborhood message with the node's previous state to produce its new representation. This is often implemented as a learnable transformation:

• Concatenation followed by a linear layer
• Gated Recurrent Unit (GRU) for sequential updates
• Residual connections to mitigate over-smoothing in deep architectures

The aggregation step must be invariant to the order of neighboring nodes, as graphs lack a canonical node ordering. This property ensures the model produces identical outputs regardless of how the adjacency list is indexed. Violating this constraint would make predictions dependent on arbitrary data formatting rather than graph structure.

A critical failure mode where node representations become indistinguishable after too many message-passing layers. As the receptive field grows to encompass the entire graph, node-specific information is washed out. Mitigation strategies include skip connections, graph normalization, and architectures like Graph Isomorphism Networks (GIN) that preserve discriminative power.

A foundational message-passing architecture that normalizes neighbor features using the symmetric Laplacian. GCNs compute a weighted average of adjacent node representations, applying a shared linear transformation and non-linearity. This spectral-based approach is highly effective on homophilous graphs but can suffer from over-smoothing when stacked too deeply.

A message-passing variant that introduces self-attention to the aggregation step. Instead of treating all neighbors equally, GATs compute dynamic, learnable importance coefficients for each edge. This allows nodes to selectively focus on the most relevant neighbors, making the architecture robust to noisy graph structures and effective on heterophilous graphs.

An inductive message-passing framework designed for large, evolving graphs. GraphSAGE learns a set of aggregator functions—mean, LSTM, or pooling—to generate embeddings by sampling a fixed-size neighborhood. This avoids the need to retrain on the full graph Laplacian, enabling generalization to entirely unseen nodes, a critical requirement for dynamic supply chain networks.

A theoretically maximal message-passing architecture designed to match the discriminative power of the Weisfeiler-Lehman (WL) test. GIN uses a multi-layer perceptron on the sum of a node's features and its neighbors' features. This 'sum' aggregation is injective, meaning GIN can distinguish a wider variety of graph substructures than mean or max-pooling GNNs.

A fundamental limitation of deep message-passing networks where node representations become indistinguishable after too many iterations. As the number of layers increases, repeated averaging causes all node embeddings to converge to the same vector, destroying local information. Mitigation strategies include skip connections, graph normalization, and Graph Transformers with global attention.

The learnable transformation applied to a source node's features before transmission along an edge. A message function can be as simple as a linear projection or as complex as an edge-conditioned MLP that incorporates edge attributes like distance, capacity, or lead time. In supply chain graphs, edge features encoding transportation cost are critical inputs to the message computation.