Abstract: We study the problem of graph summarization. Given a large graph we aim at producing a concise lossy representation (a summary) that can be stored in main memory and used to approximately answer queries about the original graph much faster than by using the exact representation. To quantify the dissimilarity between the original graph and a summary, we adopt the reconstruction error and the cut-norm error, inspired by the Frieze-Kannan variant of Szemeredi’s regularity Lemma. By exposing a connection between graph summarization and geometric clustering problems (i.e., k-means and k-median), we develop the first polynomial-time approximation algorithms to compute the best possible summary of a certain size under both measures. Using the summary to answer queries is very efficient as the running time to compute the answer depends on the number of supernodes in the summary, rather than the number of nodes in the original graph. This is joint work with Francesco Bonchi and David Garcia-Soriano, published in the Data Mining and Knowledge Discovery journal.