  A fundamental challenge in graph mining is the ever-increasing size of
datasets. Graph summarization aims to find a compact representation resulting
in faster algorithms and reduced storage needs. The flip side of graph
summarization is the loss of utility which diminishes its usability. The key
questions we address in this paper are: (1)How to summarize a graph without any
loss of utility? (2)How to summarize a graph with some loss of utility but
above a user-specified threshold? (3)How to query graph summaries without graph
reconstruction?} We also aim at making graph summarization available for the
masses by efficiently handling web-scale graphs using only a consumer-grade
machine. Previous works suffer from conceptual limitations and lack of
scalability. In this work, we make three key contributions. First, we present a
utility-driven graph summarization method, based on a clique and independent
set decomposition, that produces significant compression with zero loss of
utility. The compression provided is significantly better than state-of-the-art
in lossless graph summarization, while the runtime is two orders of magnitude
lower. Second, we present a highly scalable algorithm for the lossy case, which
foregoes the expensive iterative process that hampers previous work. Our
algorithm achieves this by combining a memory reduction technique and a novel
binary-search approach. In contrast to the competition, we are able to handle
web-scale graphs in a single machine without a performance impediment as the
utility threshold (and size of summary) decreases. Third, we show that our
graph summaries can be used as-is to answer several important classes of
queries, such as triangle enumeration, Pagerank, and shortest paths. This is in
contrast to other works that incrementally reconstruct the original graph for
answering queries, thus incurring additional time costs.
