Graph Summarization with Quality Guarantees

This post introduces polynomial-time approximation algorithms for graph summarization, specifically for creating supernode-based summaries. It quantifies dissimilarity using reconstruction error and cut-norm error, and demonstrates how these summaries can be used for efficient approximate query answering on large graphs.