Graph Summarization Algorithms

Two Sigma is developing capabilities in graph summarization, focusing on creating concise, lossy representations of large graphs. These summaries enable faster approximate query answering for metrics like adjacency, degree, eigenvector centrality, and triangle/subgraph counting. The work involves developing polynomial-time approximation algorithms based on connections to geometric clustering (k-means, k-median) and exploring techniques for compressed graph representation. This post introduces ABRA, a suite of algorithms to compute and maintain probabilistically guaranteed, high-quality approximations of the betweenness centrality of all nodes (or edges) on both static and fully dynamic graphs, using progressive random sampling and analyses relying on Rademacher averages and pseudodimension. ABRA is much faster than exact methods and outperforms state-of-the-art algorithms with the same quality guarantees.