Improved large-scale graph learning through ridge spectral sparsification

Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces…

• NS
  National Science Foundation

  Awards: CAREER, 1149048
• AN
  Agence Nationale de la Recherche

  Awards: ANR-16-CE23-0003, ANR-14-CE24-0010, CE23-0003
• MD
  Ministère de l'Education Nationale, de l'Enseignement Superieur et de la Recherche
• CN
  Centre National de la Recherche Scientifique
• OV
  Otto von Guericke University Magdeburg
• C
  CHIST-ERA