Faster Graph Embeddings via Coarsening

Graph embeddings are a ubiquitous tool for machine learning tasks on graph-structured data (e.g., node classification and link prediction). Computing embeddings for large-scale graphs, however, is often prohibitively inefficient, even if we are only interested in a small subset of relevant vertices. To address this, we present an efficient graph coarsening algorithm based on Schur complements that only computes the embeddings of the relevant vertices. We prove these embeddings are well approximated by the coarsened graph obtained via Gaussian elimination on the irrelevant vertices. As computing Schur complements can be expensive, we also give a nearly linear time algorithm to generate a coarsened graph on the relevant vertices that provably matches the Schur complement in expectation. In our experiments, we investigate various graph prediction tasks and demonstrate that computing embeddings of the coarsened graphs, rather than the entire graph, leads to significant time and space savings without sacrificing accuracy.

• Algorithms and Theory

• Machine Intelligence