Reproduce “A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening” on OpenResearch

About this paper

Gecia Bravo-Hermsdorff, Lee M. Gunderson

The authors unify graph sparsification, which deletes edges, and coarsening, which merges nodes, in a probabilistic framework that targets the graph Laplacian pseudoinverse. The method balances expected reduction against squared error while keeping the pseudoinverse unbiased in expectation. In separate comparisons, it more accurately preserved global structure than competing methods; this finding is limited to the metrics and graphs tested.

Key insights

• The Laplacian pseudoinverse (L†) remains finite and well-behaved in the limit of infinite edge weights, enabling it to serve as a robust, unifying cost function for both edge deletion (sparsification) and edge contraction (coarsening).
• An empirical observation shows that the expected squared Frobenius error from simultaneous graph perturbations is approximately additive, allowing the decomposition of the global optimization problem into a sequence of single-edge optimizations.
• A novel hyperbolic distance derived from the Poincaré half-plane model offers a more sensitive and geometrically intuitive measure of graph similarity, capturing both relative change in quadratic forms and angular differences in output vectors.

Summary by alphaXiv.