Skip to content

Improving Scalability

Many real-world/industrial graphs are billions of nodes and edges, perhaps 100s of billions - E.g., E-commerce products, reviews, transactions, sign-in events - You may not even be able to fit this into memory In small-world graphs like social networks, ~6 GNN layers means every node in the graph is needed to calculate each node embedding.

Sampling⚓︎

We don’t need the full graph to compute useful embeddings - In fact, having this source of randomness may make your model generalize betterto new, slightly different neighborhoods

We can sample at different levels: - Subset of neighbors of each node during message passing - A set of nodes for each GNN layer - A subset of the graph for the full GNN

Node-level Sampling⚓︎

  • Random neighbor sampling: for each node, only choose a subset of neighbors for message passing (e.g., GraphSage).
    • Still suffers from exponential growth with layers, but controllable
  • Importance sampling: try to improve the variance of your estimate by smarter sampling
    • FastGCN and LADIES use importance sampling at the layer-level to reduce exponential growth to linear growth

Subgraph sampling⚓︎

  • Cluster-GCN: Find densely connected clusters and only sample neighbors in the same cluster
  • GraphSAINT : Create random subgraphs for each minibatch and model with a GCN as if it were the full graph

Pre-computation⚓︎

  • Idea: instead of doing message passing before each MLP layer, do graph-based processing once
  • Assumes that the non-linearity between GNN layers is not important, so the model fitting phase is ~ logistic regression
  • Can be done in one big batch-processing job, not during training process
  • Simple Graph Convolution (SGC): \(H=softmax(A^KX\theta)\)
  • Scalable Inception Graph Neural Networks (SIGN): Similar to SGC, but also consider general operators, not just powers of A (e.g., counting triangles, diffusion operators like Personalized Page Rank,..., etc) and concatenate results as features

Resource management⚓︎

  • There are optimizations that can be made to improve resource utilization
  • GNNAutoScale caches historical embeddings from previous minibatches to avoid re-computing them
  • ROC and DistGNN enable fast/scalable distributed training via memory and graph partitioning optimizations