This results in very efficient batches and an up to 130x speedup over the baseline.

These plots show the accuracy vs. speed trade-off for 3 datasets, 3 GNNs, and multiple mini-batching methods when varying their hyperparameters. Note the log. x-axis.
4/8

IBMB uses influence scores to select the most important neighbors, instead of a random set.

It works in 2 steps:
1. Partition the output nodes (for which we want predictions) into batches.
2. For each mini-batch, select the auxiliary nodes that help most with predictions.
2/8

Luckily, the influence scores simplify to personalized PageRank (PPR) if we make some assumptions.

Step 2 then becomes an application of PPR or topic-sensitive PageRank.

Step 1 is more tricky and requires falling back to heuristics like PPR or graph partitioning.
3/8