Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming

Yufan Huang, C. Seshadhri, David F. Gleich

Introduction

Understanding the community structure of massive networks is a foundational challenge in network science. Typically, researchers measure how "well-defined" a community is using conductance—the ratio of edges leaving a group of nodes to the total edges within it. A lower conductance indicates a more isolated, tightly-knit community.

The Network Community Profile (NCP) plots the minimum conductance found for every possible community size. In geometric or planar graphs, conductance generally decreases as communities grow. However, real-world social and information networks exhibit a counter-intuitive phenomenon: as communities get larger, their conductance actually increases.

Until now, NCPs have been generated using heuristic search algorithms (like seeded PageRank). While these heuristics find good clusters, they only provide an upper bound on the minimum conductance. Because calculating the true minimum conductance is NP-hard, researchers lacked a theoretical lower bound to prove that this characteristic "upward-sloping" shape is a fundamental property of the graph, rather than a failure of the search algorithms.

This paper introduces the first theoretically sound and practically scalable method to compute these lower bounds, mathematically certifying the cluster structure of massive real-world networks.

Methodology: Bridging Theory and Scale

The authors solve this problem by bridging empirical network science and theoretical computer science through a multi-step mathematical relaxation process:

  1. The $\mu$-conductance Connection: The authors identify that the NCP is fundamentally a plot of $\mu$-conductance—a niche measure from Markov chain theory used to study the conductance of sets containing at least a $\mu$-fraction of a graph's total volume.
  2. Constrained Spectral Relaxation: Standard spectral methods (like the Fiedler vector) find the best global cut but tend to "localize" or collapse onto tiny sets of outlier nodes. To prevent this, the authors add entry-wise constraints to the spectral optimization problem, forcing the solution to spread across larger, specified volume scales.
  3. Semi-Definite Programming (SDP): The non-convex spectral problem is relaxed into a convex Semi-Definite Program (SDP). While theoretically robust, standard SDP solvers scale poorly and typically fail on graphs larger than a few thousand nodes.
  4. Low-Rank SDP (Burer-Monteiro): To scale the algorithm to hundreds of thousands of nodes, the authors utilize a low-rank formulation. Although this makes the problem non-convex again, they provide a crucial mathematical proof: the KKT points (local optima) of this low-rank problem can be used to derive a rigorous, global lower bound on the original convex SDP objective.

Datasets Evaluated

The algorithm was rigorously tested on both synthetic and real-world datasets:

  • Synthetic Graphs: Small networks (85 and 537 nodes) engineered with dense cores to validate the low-rank method against exact, traditional SDP solvers.
  • Real-World Networks: A diverse set of networks including AstroPh and HepPh (citation networks), Email-Enron (communications), Facebook-Page and Deezer (social networks), and DBLP (a co-authorship network). DBLP was the largest tested, featuring approximately 226,000 nodes and 716,000 edges.

Key Findings and Results

  • Unprecedented Scalability: The low-rank SDP algorithm successfully processed the DBLP graph (>200k nodes). This is a massive leap forward, as traditional SDP solvers typically max out at around 1,000 nodes.
  • Validating the Upward Trend: In almost all real-world cases, the computed lower bound closely followed the upward trend of the heuristic NCP. This provides the first mathematical confirmation of the "no large, deep communities" hypothesis in real-world networks.
  • Remarkable Tightness: On the HepPh dataset, the theoretical lower bound was within a factor of ~3 of the best-known empirical clusters. For an NP-hard problem that is generally computationally intractable, this bound is remarkably tight and informative.
  • Anomaly Detection: The tool successfully identified that the Deezer network possesses a "flat" NCP, correctly distinguishing its structural properties from the typical upward-sloping curves of other social networks.

Limitations and Future Directions

While a significant breakthrough, the method has limitations that pave the way for future research:

  • Computational Cost: Although vastly faster than standard SDPs, the method still requires hours to days to process the largest graphs. The authors suggest parallelization as an immediate next step to improve runtime.
  • Refining the Bounds: The current lower bounds are mathematically sound but "rough." There is room to refine the mathematical slack to bring the theoretical lower bounds even closer to the empirical upper bounds.
  • Random Walk Theory: The authors propose that $\mu$-conductance could lead to much tighter bounds on the mixing times of random walks in real-world graphs, as standard conductance-based bounds are often overly pessimistic.
  • Generalization: Extending these techniques to multivector or multiset generalizations could eventually allow researchers to study multiple communities simultaneously.

Summary updated

Abstract

We study a new connection between a technical measure called $\mu$-conductance that arises in the study of Markov chains for sampling convex bodies and the network community profile that characteri...
BibTeX
@inproceedings{huang2023theoretical,
  author = {Yufan Huang and C. Seshadhri and David F. Gleich},
  title = {{Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=6EUqA8VZ2O},
}
Figure