A Unifying Framework for Spectrum-Preserving
Graph Sparsification and Coarsening
Gecia Bravo-Hermsdorff*
Princeton Neuroscience Institute
Princeton University
Princeton, NJ, 08544, USA
geciah@princeton.edu
Lee M. Gunderson*
Department of Astrophysical Sciences
Princeton University
Princeton, NJ, 08544, USA
leeg@princeton.edu
Abstract
How might one “reduce” a graph? That is, generate a smaller graph that preserves
the global structure at the expense of discarding local details? There has been
extensive work on both graph sparsification (removing edges) and graph coarsening
(merging nodes, often by edge contraction); however, these operations are currently
treated separately. Interestingly, for a planar graph, edge deletion corresponds to
edge contraction in its planar dual (and more generally, for a graphical matroid
and its dual). Moreover, with respect to the dynamics induced by the graph
Laplacian (e.g., diffusion), deletion and contraction are physical manifestations
of two reciprocal limits: edge weights of
0
and
∞
, respectively. In this work, we
provide a unifying framework that captures both of these operations, allowing one
to simultaneously sparsify and coarsen a graph while preserving its large-scale
structure. The limit of infinite edge weight is rarely considered, as many classical
notions of graph similarity diverge. However, its algebraic, geometric, and physical
interpretations are reflected in the Laplacian pseudoinverse
L
†
, which remains finite
in this limit. Motivated by this insight, we provide a probabilistic algorithm that
reduces graphs while preserving
L
†
, using an unbiased procedure that minimizes
its variance. We compare our algorithm with several existing sparsification and
coarsening algorithms using real-world datasets, and demonstrate that it more
accurately preserves the large-scale structure.
1 Motivation
Many complex structures and phenomena are naturally described as graphs (eg,
1
brains, social
networks, the internet, etc). Indeed, graph-structured data are becoming increasingly relevant to
the field of machine learning [
2
,
3
,
4
]. These graphs are frequently massive, easily surpassing our
working memory, and often the computer’s relevant cache [
5
]. It is therefore essential to obtain
smaller approximate graphs to allow for more efficient computation.
Graphs are defined by a set of nodes
V
and a set of edges
E ⊆ V × V
between them, and are often
represented as an adjacency matrix
A
with size
|V | × |V |
and density
∝ |E|
. Reducing either of
these quantities is advantageous: graph “coarsening” focuses on the former, aggregating nodes while
respecting the overall structure, and graph “sparsification” on the latter, preferentially retaining the
important edges.
∗
Both authors contributed equally to this work.
1
The authors agree with the sentiment of the footnote on page
xv
of [
1
], viz, omitting superfluous full stops
to obtain a more efficient compression of, eg: videlicet, exempli gratia, etc.
Preprint. Under review.
arXiv:1902.09702v4 [cs.DM] 23 Aug 2019
