Techniques for Reducing the Computational Complexity of Large-Scale Graph Neural Networks

The talk introduces graph neural networks (GNNs), describing the types of graphs used—global graphs, instance graphs, dense and sparse graphs—and how GNNs relate to traditional neural networks such as BERT.

It outlines the standard GNN computation pipeline: initialization of node, edge, and global states; iterative message‑passing steps that compute messages, attention scores, aggregate messages, and update states.

Complexity analysis covers both space (model parameters, intermediate tensors) and time (dependence on batch size B, iteration count T, number of vertices |V|, edges |E|, and feature dimensions D). The discussion highlights that large dense graphs can cause O(|V|²) costs.

To reduce these costs, ten practical ideas are presented:

Avoid edge‑wise computation by using destination‑independent messages, lowering complexity from O(|E|) to O(|V|).

Reduce feature dimension D, especially in multi‑head attention, to shrink per‑message cost.

Selective iteration: update only a subset of nodes or use hard gates, sparse attention, or learned criteria to cut the number of message‑passing steps T.

“Baking” – cache intermediate results in a memory module and skip gradient back‑propagation for non‑critical nodes.

Distillation – train a smaller GNN to mimic a larger one using hidden‑based or attention‑based loss.

Graph partition or clustering – split a huge graph into groups, perform intra‑group message passing and inter‑group pooling.

Sparse graph computation – maintain index lists and use operations such as gather, scatter, segment_sum in TensorFlow or PyTorch.

Sparse routing – dynamically construct local sub‑graphs with top‑K outgoing edges, akin to a push‑style attention.

Cross‑sample shared features – compute input‑agnostic node embeddings once and reuse them across batches.

Combine any subset of the above methods to suit specific workloads.

The article concludes with a reminder to apply the appropriate combination of techniques to achieve efficient large‑scale GNN training and inference.