Faster Graph Embeddings via Coarsening
Faster Graph Embeddings via Coarsening
复制标题
DOI：
--
复制
发表时间：
2020-07
期刊：
影响因子：
--
通讯作者：
Matthew Fahrbach;Gramoz Goranci;Richard Peng;Sushant Sachdeva;Chi Wang-
中科院分区：
文献类型：
--
作者：
Matthew Fahrbach;Gramoz Goranci;Richard Peng;Sushant Sachdeva;Chi Wang-
图嵌入是机器学习任务的普遍工具，例如图结构数据上的节点分类和链接预测。然而，即使我们只对相关顶点的一小部分感兴趣，计算大规模图的嵌入也是非常低效的。为了解决这个问题，我们提出了一个有效的图粗化方法，基于舒尔补，用于计算相关顶点的嵌入。我们证明了这些嵌入是完全保留的Schur补图，通过高斯消除的非相关顶点。由于计算Schur补是昂贵的，我们给出了一个近似线性的时间算法，生成一个粗化图的相关顶点，可证明匹配的Schur补的期望。我们涉及图上预测任务的实验表明，在粗化图而不是整个图上计算嵌入，可以在不牺牲准确性的情况下节省大量时间。
Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for large-scale graphs is prohibitively inefficient even if we are interested only in a small subset of relevant vertices. To address this, we present an efficient graph coarsening approach, based on Schur complements, for computing the embedding of the relevant vertices. We prove that these embeddings are preserved exactly by the Schur complement graph that is obtained via Gaussian elimination on the non-relevant vertices. As computing Schur complements is expensive, we give a nearly-linear time algorithm that generates a coarsened graph on the relevant vertices that provably matches the Schur complement in expectation. Our experiments involving prediction tasks on graphs demonstrate that computing embeddings on the coarsened graph, rather than the entire graph, leads to significant time savings without sacrificing accuracy.