Reproduce “FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling” on OpenResearch

About this paper

Jie Chen, Tengfei Ma, Cao Xiao

FastGCN enables Graph Convolutional Networks (GCNs) to operate efficiently on large-scale graphs in an inductive setting, overcoming the scalability and transductivity limitations of prior GCN models. It achieves this by reinterpreting graph convolutions as integral transforms and using Monte Carlo importance sampling for batched training, yielding training speeds one to two orders of magnitude faster than existing methods with comparable accuracy.

Key insights

• Reframing graph convolutions as integral transforms allows for a principled, probabilistic approach to sampling, enabling inductive learning and scalability.
• Monte Carlo sampling converts computationally intractable summations over large neighborhoods into manageable sample averages, fixing the computational cost per batch.
• Importance sampling, even with a pre-computed sub-optimal distribution, significantly reduces the variance of gradients, leading to more stable and accurate training compared to uniform sampling.

Summary by alphaXiv.