Graph neural networks

Each node aggregates transformed messages from its neighbors using a permutation-invariant function (e.g., sum/mean/max), then combines the aggregate with its own representation via an update function (often an MLP plus nonlinearity). This 'aggregate-then-update' step is repeated across layers so that after k layers each node encodes information from its k-hop neighborhood.

A graph has no canonical ordering of a node's neighbors, so the output must not change if neighbors are relabeled or reordered. Using a permutation-invariant aggregator (sum, mean, max) guarantees the same node embedding regardless of how the neighbor set is enumerated, making the network well-defined on graphs.

Over-smoothing is the phenomenon where node representations converge to similar (nearly indistinguishable) values as depth increases, destroying discriminative information. It arises because repeated neighborhood averaging acts like repeated application of a low-pass graph filter, pushing features toward the dominant eigenvector / a smooth signal across connected components.

GraphSAGE learns aggregator functions that generate embeddings by sampling and aggregating a fixed-size neighborhood, so it can produce embeddings for nodes unseen during training (inductive). Classic GCN learns a full-graph propagation tied to the specific adjacency/Laplacian used in training, making it transductive and unable to natively embed new nodes without retraining.

GAT computes an unnormalized attention score for each edge from a learnable function (typically a single-layer feedforward applied to concatenated transformed endpoint features, followed by LeakyReLU), then normalizes scores across each node's neighborhood with softmax. Aggregation is a weighted sum of neighbor features using these learned, data-dependent coefficients, usually with multiple heads.

GCN uses D̃^(-1/2) à D̃^(-1/2), where à = A + I (adjacency with self-loops) and D̃ is its degree matrix. This symmetric normalization scales each edge by 1/sqrt(d_i d_j), keeping the propagation operator's eigenvalues bounded and preventing high-degree nodes from dominating the aggregation.

# H' = sigma( D̃^-1/2 (A+I) D̃^-1/2 H W )

Message-passing GNNs are at most as powerful as the 1-dimensional Weisfeiler-Lehman (1-WL) graph isomorphism test at distinguishing graphs. They cannot distinguish two graphs that 1-WL deems equivalent; GIN achieves this maximal power by using a sum aggregator plus an injective MLP update.

Sum aggregation can preserve the full multiset of neighbor features (counts and identities), whereas mean loses information about multiset cardinality (it captures distribution but not counts) and max captures only the set of distinct elements. Combined with an injective update (MLP over sum), sum lets GIN distinguish neighborhoods that mean/max would conflate, matching 1-WL power.

Neighbor explosion is the exponential growth of the receptive field: a k-layer GNN on a dense graph requires aggregating O(d^k) nodes per target, making full-batch training infeasible at scale. GraphSAGE caps this by sampling a fixed number of neighbors per layer, bounding per-node computation and memory regardless of true degree.

GraphSAGE samples a fixed number of neighbors per node recursively, so the sampled set can still grow across layers. FastGCN instead samples a fixed number of nodes per layer (independent of how many target nodes reference them), interpreting propagation as an integral and using importance sampling to control variance, giving constant cost per layer.

Spectral methods define convolution via the graph Fourier transform using the Laplacian eigenbasis (filters are functions of eigenvalues), which is principled but ties the model to a fixed graph and is costly. Spatial methods define convolution directly as localized message aggregation over neighbors in the vertex domain, which is more scalable, inductive, and generalizes across graphs.

ChebNet approximates the spectral filter with a truncated Chebyshev polynomial of the scaled Laplacian, so the filter is expressed as a sum of T_k(L̃) terms computed via the polynomial recurrence. This makes filters K-localized (touching only K-hop neighbors) and avoids the O(n^3) eigendecomposition, since only sparse matrix-vector products with L are needed.

A readout aggregates all node embeddings into a single fixed-size graph representation (via permutation-invariant operations like sum/mean/max or learned hierarchical pooling). It is required for graph-level prediction (e.g., molecule classification) because per-node embeddings must be summarized into one vector regardless of graph size or node ordering.

DiffPool learns a soft cluster-assignment matrix S at each layer that maps nodes to a smaller set of clusters; it then coarsens the graph by computing pooled node features (S^T X) and a coarsened adjacency (S^T A S). Stacking these layers yields a differentiable hierarchy, trained end-to-end with auxiliary link-prediction and entropy regularization to keep assignments meaningful.

R-GCN uses relation-specific weight matrices so that messages are transformed differently per edge type (and direction), summing normalized contributions across relations. To avoid parameter explosion with many relations, it employs basis or block-diagonal decomposition to share/regularize the per-relation weights.

Because message passing is bounded by the 1-WL test, two non-isomorphic graphs that are regular (every node has identical degree and locally identical neighborhoods) produce identical color refinements, so all nodes get the same embeddings and the graphs are indistinguishable. Adding positional/structural encodings or unique node IDs (random features) can break this symmetry.

Positional encodings inject information about a node's location/role in the graph that message passing alone cannot capture, improving expressivity beyond 1-WL. A common choice is Laplacian eigenvector encodings (using the smallest non-trivial eigenvectors of the graph Laplacian), as well as random-walk-based encodings (e.g., diagonals of powers of the random-walk matrix).

Over-squashing is the compression of an exponentially growing amount of long-range information into fixed-size node vectors, causing distant-node signals to be distorted as they pass through graph bottlenecks. It is governed by topology, particularly negative graph curvature / low effective resistance bottleneck edges; remedies include graph rewiring and curvature-based edge additions.

Skip connections (residual or initial/jumping-knowledge connections) let each layer retain access to earlier, less-smoothed representations, mitigating over-smoothing and vanishing gradients. Designs like JKNet aggregate representations from all layers, and APPNP/GCNII use initial-residual + identity mapping to preserve node-specific information across depth.

edge_index is a [2, num_edges] LongTensor in COO format where the first row holds source node indices and the second row holds destination node indices for each directed edge. Message passing reads it to gather source features (index 0) and scatter aggregated messages to destinations (index 1).

# x: [N, F], edge_index: [2, E]
out = conv(x, edge_index)  # PyG GCNConv

Multiple graphs are merged into one large disconnected graph by block-diagonally stacking their adjacency/edge_index (with offset node indices) and concatenating node features. A batch vector maps each node to its originating graph so that readout/pooling can be done per graph; this preserves correctness since the graphs share no edges.

APPNP decouples feature transformation from propagation: an MLP first produces per-node predictions, then these are propagated using a personalized PageRank scheme that, at each step, mixes neighbor aggregation with a teleport probability back to the original predictions. This allows large propagation depth (wide receptive field) without over-smoothing, since the teleport term preserves the node's own signal.

Mean aggregation is degree-normalized, so it is robust to large variation in node degree and to graphs of different sizes/densities, producing more stable and comparable embeddings. Sum can produce magnitudes that scale with degree, which may dominate features and hurt generalization across graphs with heterogeneous degree distributions.

A heterogeneous GNN operates on graphs with multiple node and/or edge types (e.g., users, items, reviews) and uses type-specific transformations and aggregation, often along defined metapaths or via per-relation parameters. A homogeneous GNN assumes a single node type and single edge type with shared weights everywhere.

The GNN encodes nodes into embeddings, then a decoder scores candidate node pairs (e.g., dot product, bilinear, or an MLP on concatenated embeddings) to predict edge existence. Training uses observed edges as positives and sampled non-edges as negatives, optimizing a binary cross-entropy / ranking loss; evaluation often uses AUC or Hits@k.

# score = (z_u * z_v).sum(-1)  # dot-product decoder

Negative sampling supplies non-existent (or unobserved) node pairs as negatives so the model learns to separate true edges from false ones; without negatives the model could trivially score all pairs high. Sampling a small number of negatives per positive makes training tractable on huge graphs, and harder negatives (e.g., popularity- or structure-based) often improve discrimination.

In the transductive setting, all nodes (including test nodes, but not their labels) are present in the graph during training, so the model can leverage their features and connectivity. In the inductive setting, test nodes (or entirely new graphs) are unseen during training, requiring the model to generalize its learned aggregators to novel structure.

Cluster-GCN partitions the graph into dense subgraphs using a graph-clustering algorithm (e.g., METIS), then trains on mini-batches consisting of one or a few clusters, restricting message passing to within-cluster edges. This bounds neighborhood size and memory per batch while keeping most useful edges, dramatically reducing the neighbor-explosion overhead.

Edge features (e.g., bond type, distance) modulate the messages passed along that edge. The general MPNN framework computes messages as a function M(h_u, h_v, e_uv) of both endpoint states and the edge feature, often using the edge feature to parameterize the transformation (edge-conditioned convolution), so structurally identical neighbors with different edge attributes send different messages.

Without self-loops, the aggregation of node i would exclude its own current representation, so a node's features could be lost or overwritten by neighbors each layer. Adding the identity ensures each node retains and combines its own signal with neighbor information, and it also keeps the normalized operator well-conditioned (avoiding zero rows for isolated nodes).

A Graph Transformer applies (full or sparse) self-attention so every node can attend to many or all others in one layer, with graph structure injected via positional/structural encodings and optional attention biases. Because information no longer must traverse many message-passing hops, it sidesteps the topological bottlenecks that cause over-squashing for long-range dependencies.

DropEdge randomly removes a fraction of edges from the adjacency at each training iteration, acting like data augmentation that reduces over-fitting and slows over-smoothing by lowering the connectivity/message volume per epoch. At inference the full graph is used; it is the graph analogue of dropout applied to edges rather than units.

Because nodes are connected, random splits cause information leakage: a test node's neighbors may be in the training set, and message passing propagates their features/labels, inflating performance and breaking the i.i.d. assumption of standard CV. Proper evaluation needs structure-aware splits (e.g., inductive splits, or removing test-node edges) and fixed public splits for comparability.