Graph Neural Network (GNN)

The foundational computation paradigm where nodes iteratively aggregate feature information from their local neighborhood. A node's state is updated based on 'messages' passed along connecting edges.

• Aggregation Function: A permutation-invariant operator (e.g., SUM, MEAN, MAX) that combines incoming neighbor messages.
• Update Function: A learnable neural network (e.g., MLP or GRU) that computes the new node state from its previous state and the aggregated message.
• K-Hop Receptive Field: Stacking k message-passing layers allows a node to incorporate information from neighbors up to k hops away, analogous to the receptive field in CNNs.

GNNs respect the fact that graph data has no inherent node ordering. The output must be independent of the arbitrary indexing of input nodes.

• Invariance: A function f is permutation invariant if f(PX, PAP^T) = f(X, A) for any permutation matrix P. Graph-level prediction tasks (e.g., molecular toxicity) require invariant outputs.
• Equivariance: A function f is permutation equivariant if f(PX, PAP^T) = Pf(X, A). Node-level tasks (e.g., node classification) require equivariant outputs, meaning the output order permutes identically to the input order.
• This property is enforced by using aggregation functions that are commutative and associative.

Unlike transductive methods like shallow node embeddings (e.g., DeepWalk, node2vec) that require retraining to generate embeddings for unseen nodes, GNNs are inherently inductive.

• Shared Parameters: The learnable aggregation and update functions are shared across all nodes in the graph, not memorized per-node.
• Generalization to Unseen Graphs: A trained GNN model can be applied directly to entirely new graphs or nodes without retraining, as long as the feature dimensionality matches.
• Dynamic Graph Support: This property is critical for evolving graphs in production systems, such as new users joining a social network or new products being added to a catalog.

Real-world data often involves multiple types of nodes and edges. Heterogeneous GNNs (HGNNs) extend the message-passing framework to handle this complexity.

• Type-Specific Projections: Each node type and edge type can have its own learnable linear projection matrix to map features into a shared or type-specific latent space.
• Relation-Specific Aggregation: Messages are aggregated separately for each relation type before being combined, often using attention mechanisms to weigh the importance of different relations.
• Metapath-Based Sampling: Sampling strategies can be guided by predefined metapaths (e.g., User-Item-User) to capture specific semantic relationships in the graph.

Graph Attention Networks (GATs) introduce a self-attention mechanism to the aggregation step, allowing the model to implicitly weigh the importance of different neighbors during message passing.

• Dynamic Weighting: Instead of treating all neighbors equally, an attention coefficient α_{ij} is computed for each edge, indicating the relevance of node j's features to node i.
• Multi-Head Attention: Multiple independent attention mechanisms are executed in parallel, and their outputs are concatenated or averaged to stabilize the learning process and capture different facets of a neighborhood.
• Computational Complexity: The self-attentional layer is highly efficient, as the computation of attention coefficients can be parallelized across all edges.

GNNs can be broadly categorized by their theoretical foundation for defining the convolution operation on graphs.

• Spectral Methods: Define convolution via the graph Laplacian's eigendecomposition and the Fourier transform. ChebNet approximates this using Chebyshev polynomials to avoid the costly eigendecomposition, making filters strictly localized in the K-hop neighborhood.
• Spatial Methods: Define convolution directly on the graph's topology by aggregating features from a node's spatial neighbors. This is the dominant paradigm in modern architectures like GraphSAGE and GAT due to its flexibility and scalability.
• Bridging the Gap: Many spatial methods can be interpreted as approximations of spectral convolutions, providing a unifying theoretical link.

The fundamental computational paradigm of GNNs where nodes iteratively update their hidden states by aggregating feature information from their local neighborhood. In each layer, a node receives messages from its neighbors, applies an aggregation function (mean, sum, or max pooling), and combines the result with its own representation via an update function (typically a neural network layer). This process allows information to propagate across the graph, with a k-layer GNN enabling information flow across k-hop neighborhoods. The choice of aggregation function significantly impacts representational power—sum aggregation is injective and maximally expressive, while mean pooling can fail to distinguish certain graph structures.

A seminal GNN variant that applies a spectral convolution operation on graph-structured data, using a first-order approximation of localized spectral filters. The layer-wise propagation rule normalizes the adjacency matrix with self-loops and applies a shared weight transformation: H^(l+1) = σ(D̃^(-1/2) Ã D̃^(-1/2) H^(l) W^(l)). This symmetric normalization prevents numerical instability from exploding activations in high-degree nodes. GCNs are transductive by design, requiring the full graph structure at training time, which limits their application to dynamic graphs with evolving node sets compared to inductive frameworks like GraphSAGE.

An inductive framework that generates embeddings by sampling and aggregating features from a node's local neighborhood, enabling inference on unseen nodes without retraining. Unlike transductive GCNs, GraphSAGE learns aggregation functions (mean, LSTM, or pooling) that generalize to new graph structures. The algorithm samples a fixed-size neighborhood at each depth to maintain computational efficiency on high-degree nodes. This makes it particularly suitable for dynamic recommendation graphs where new users and items continuously enter the system, as embeddings can be generated on-the-fly without full graph recomputation.

A GNN architecture that introduces self-attention to the aggregation process, allowing nodes to assign different importance weights to each neighbor rather than treating all connections equally. The attention coefficients are computed as: α_ij = softmax(LeakyReLU(a^T [W h_i || W h_j])), where a is a learnable attention vector. Multi-head attention stabilizes learning by running multiple attention mechanisms in parallel and concatenating or averaging their outputs. GATs excel in heterophilic graphs where connected nodes have dissimilar features, as the attention mechanism can learn to down-weight uninformative neighbors.

A production-scale GNN developed by Pinterest for web-scale recommendation, combining random walks with graph convolutions to generate embeddings for billions of nodes. PinSAGE constructs importance-weighted neighborhoods by simulating random walks from each node and selecting the top-k most frequently visited neighbors, prioritizing structurally relevant connections over uniform sampling. The architecture uses a MapReduce pipeline to parallelize minibatch construction across massive item-item graphs, enabling efficient training on graphs with trillions of edges. This demonstrated the viability of GNNs for industrial recommender systems.

A GNN variant designed for graphs containing multiple node and edge types, such as user-item bipartite graphs with additional product attributes or social connections. Heterogeneous GNNs maintain type-specific transformation matrices and aggregation functions, recognizing that the semantics of a 'purchased' edge differ fundamentally from a 'viewed' edge. The Relational Graph Convolutional Network (R-GCN) is a foundational architecture that applies distinct weight matrices per relation type. In recommender systems, this enables the model to separately encode collaborative signals, content similarity, and knowledge graph relationships within a unified framework.