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 $ınfty$, 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 $\mathitL^\dagger$, which remains finite in this
limit. Motivated by this insight, we provide a probabilistic algorithm that
reduces graphs while preserving $\mathitL^\dagger$, 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.
Users
Please
log in to take part in the discussion (add own reviews or comments).