Seshadhri Comandur

3Machine learning papers tracked by Lacuna
Is this you?

Research Overview

Seshadhri Comandur focuses on graph algorithms, network analysis, and online learning in dynamic environments. Early work addressed regret minimization and performance metrics for changing data streams, before shifting toward the structural properties of massive social networks. The most recent research in the evidence investigates sublinear algorithms for estimating degree distributions in heavy-tailed graphs.

Research Trajectory

The research trajectory of Seshadhri Comandur begins in the domain of online learning before transitioning into the structural analysis of massive networks and graph algorithms. In early work, Comandur explored dynamic data streams and the theoretical limits of regret minimization. As a co-author of Efficient learning algorithms for changing environments (2009), Comandur helped address the limitations of standard regret bounds in oblivious changing environments. Because traditional regret measures the difference between an online learner's cost and the best decision in hindsight, minimizing it often forces algorithms to converge to a static optimum—a suboptimal behavior when the underlying environment is dynamic. To resolve this, the research proposed a strengthened performance metric evaluated against a changing comparator, alongside data-streaming-based reductions designed to maintain algorithmic efficiency without sacrificing adaptability.

By 2012, Comandur's focus had shifted toward the topology of social networks, specifically examining how local structures relate to broader network properties. This work intersects with the research direction of Inferring Global Topology from Local Geometric Measurements. In Vertex neighborhoods, low conductance cuts, and good seeds for local community methods, Comandur and collaborators theoretically demonstrated that heavy-tailed degree distributions and large clustering coefficients—common features of real-world social networks—imply that vertex neighborhoods (or egonets) naturally form strong communities. Evaluating these neighborhood communities across a range of graphs, the study showed that they achieve conductance scores comparable to Fiedler cuts. Furthermore, the research established that the conductance of these local neighborhoods exhibits behavior similar to network community profiles computed via personalized PageRank, providing a localized, computationally viable method for understanding network structures.

In subsequent years, Comandur took on a senior research role focusing on sublinear algorithms for massive graph analysis. This phase of work addresses the computational challenges of estimating fundamental graph properties when the entire dataset cannot be processed efficiently. As the senior author of Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples (2018), Comandur led the development of SADDLES, a new algorithm designed to estimate the degree distribution of large graphs through small, random samples. Estimating these distributions in real-world graphs is notoriously difficult due to their heavy-tailed nature and the extreme variance in node degrees. By leveraging sublinear algorithmic techniques, this work provided provably accurate approximations for all values of the degree distribution. This advancement in graph sampling contributes to the broader area of structural analysis in complex datasets, a domain conceptually related to themes such as Scaling Topological Data Analysis for Deep Learning.

Current Directions

Based on the provided evidence, the most recent paper is from 2018. The latest visible directions of this research program center on the design of sublinear algorithms and sampling techniques for massive graphs. The primary focus is on developing provable, practical methods to estimate fundamental network properties—such as degree distributions—in heavy-tailed graphs where processing the entire dataset is computationally prohibitive. This involves leveraging random graph samples to accurately approximate global structural characteristics, ensuring that algorithmic solutions remain both efficient and theoretically grounded as network sizes scale.

Profile updated

See something wrong? Report a mistake