Scalability. As traditional GNN architectures perform computations on the neighborhood of each node, their computational complexity depends on the number of nodes in the graph and the maximum degree.
To enable GNN processing of large graphs [1]} and [2]} propose randomly sub-sampling neighbors every batch or every layer.
To better preserve local neighborhoods [3]} and [4]} use graph clustering, to construct small subgraphs for each batch.
Alternatively, [5]} quantize node embeddings and use a small number of quantized vectors to approximate messages from out-of-batch nodes. In contrast to our approach, these methods focus on node-level tasks and might not be straightforward to extend to graph-level tasks, because they rely on considering only a predetermined subset of nodes from a graph in a given batch.
