![Algorithmic Spectral Graph Theory_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Algorithmic%20Spectral%20Graph%20Theory_hi-res.jpg?h=bc58dfd7&itok=8NAdfoPF)
Abstract
We study a variety of spectral-based information diffusion problems that occur in the literature as relaxations of min-cut objectives. This allows us to describe two methods to make these diffusion-based algorithms more robust to the details of graph constructions, errors in node labeling, degree variability, and a variety of other real-world heterogeneities. The two methods are solidly grounded in the theory of spectral graph methods and include a rank-based label assignment strategy and a scalable-approximation algorithm for the basic diffusion algorithm that implicitly has sparsity-based regularization properties. In addition to describing the framework, we provide an empirical study these methods on a digit prediction problem as well as a variety of other pedagogical examples.