Basu, S. (CSE) – Decomposition Techniques for Web-Scale Networks: Bridging Theory and Practice

Decompositions of large-scale networks are central to many applications in graph mining, network science, and algorithm design. Over several decades, a rich body of work has developed techniques to partition networks with various different objectives. However, a noticeable gap persists between methods with strong theoretical guarantees, and those that perform well in practice. Practical algorithms often lack provable guarantees, while theoretically sound methods are rarely straightforward to implement, and scale poorly. This thesis presents a suite of techniques that aim to close this gap, presenting decomposition methods that are both theoretically grounded and practically efficient.

The first part of the thesis focuses on dense subgraph decomposition, a fundamental problem with numerous real-world applications and a close relation to the problem of community detection studied in the complex networks literature. Specifically, we focus on decompositions that produce a large number of small components; a variant that existing techniques struggle with. We propose a novel shift in perspective: rather than approximate the optimum closely using traditional optimization approaches, we develop fast algorithms with provable lower bounds on output quality. We introduce some new objectives and metrics to achieve these, and introduce a new theoretical framework that captures structural properties of real-world networks. We compare our perspective with the common approach taken in the community detection literature, and demonstrate algorithms that significantly outperform prior methods across a broad range of datasets.

The second part of the thesis explores how network decompositions can enable sublinear-time algorithms: ones that produce approximate solutions without needing to inspect the entire input. We study two somewhat distinct problems. The first is a property testing problem in bounded-degree planar graphs, where we show that hyperfinite decompositions allow for efficient testing of even the most complex properties. The second examines shortest-path computation in real-world networks. By observing that shortest paths often traverse a dense core, we design the first sublinear algorithm that exploits this structure to approximate shortest paths. Our method competes with exact algorithms in speed, while scaling to larger networks that such algorithms cannot handle.

We leave some open problems and discuss ongoing and future work, and provide pointers on how our insights can be leveraged to study a larger class of problems in graph algorithms.

Event Host: Sabyasachi Basu, PhD Candidate, Computer Science & Engineering

Advisor: C. Seshadhri