NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:4192
Title:A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening

Graph sparsification has a well developed literature with strong theoretical guarantees. In contrast, the literature on graph reductions (coarsening) is much more ad-hoc, even though from a practical point of view coarsening could be very useful. The present paper introduces an imaginative way to combine these two tasks. While there are no theoretical guarantees (which is what Reviewer 1 complains about) and some of the details like the computational complexity or a detailed explanation of the rational behind the loss function/algorithmic details are not fully fleshed out, there are plenty of interesting mathematical insights here that are worth sharing with the community. I am also a bit mystified by the reason for the hyperbolic distance that the authors introduce and wonder if one could construct a bottom up version of the algorithm, because that would be very important for large problems. Overall, I think this is a valuable contribution because it might help the field of graph coarsening get "unstuck".