Article Source

• Pragmatic Ridge Spectral Sparsification for Large-Scale Graph Learning

Pragmatic Ridge Spectral Sparsification for Large-Scale Graph Learning

• Ioannis Koutis, New Jersey Institute of Technology

Ioannis Koutis presents a talk entitled “Pragmatic Ridge Spectral Sparsification for Large-Scale Graph Learning” at the Workshop on Randomized Numerical Linear Algebra, Statistics, and Optimization held at DIMACS on September 16-18, 2019.

Abstract

The representation and benefits of learning methods based on graph Laplacians, such as Laplacian smoothing or harmonic function solution for semi-supervised learning, are empirically and theoretically well supported. There is an increasing number of very large real-world graphs with a number of edges which is sufficiently large for sparsification algorithms to become practically applicable. Motivated by learning algorithms that employ regularization, we discuss the design and properties of a distributed algorithm for ridge spectral sparsification with demonstrable practical gains. The talk represents joint work with Daniele Calandriello, Alesandro Lazaric, and Michal Valko.