  We propose quasi-stable coloring, an approximate version of stable coloring.
Stable coloring, also called color refinement, is a well-studied technique in
graph theory for classifying vertices, which can be used to build compact,
lossless representations of graphs. However, its usefulness is limited due to
its reliance on strict symmetries. Real data compresses very poorly using color
refinement. We propose the first, to our knowledge, approximate color
refinement scheme, which we call quasi-stable coloring. By using approximation,
we alleviate the need for strict symmetry, and allow for a tradeoff between the
degree of compression and the accuracy of the representation. We study three
applications: Linear Programming, Max-Flow, and Betweenness Centrality, and
provide theoretical evidence in each case that a quasi-stable coloring can lead
to good approximations on the reduced graph. Next, we consider how to compute a
maximal quasi-stable coloring: we prove that, in general, this problem is
NP-hard, and propose a simple, yet effective algorithm based on heuristics.
Finally, we evaluate experimentally the quasi-stable coloring technique on
several real graphs and applications, comparing with prior approximation
techniques.
  A reference implementation and the experiment code are available at
https://github.com/mkyl/QuasiStableColors.jl .
