Lune

ICML2023Top-tier venue

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

Yufan Huang, C. Seshadhri, David F. Gleich

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 characterizes size-resolved properties of clusters and communities in social and information networks. The idea of μ\mu-conductance is similar to the traditional graph conductance, but disregards sets with small volume. We derive a sequence of optimization problems including a low-rank semi-definite program from which we can derive a lower bound on the optimal μ\mu-conductance value. These ideas give the first theoretically sound bound on the behavior of the network community profile for a wide range of cluster sizes. The algorithm scales up to graphs with hundreds of thousands of nodes and we demonstrate how our framework validates the predicted structures of real-world graphs.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. Decoupling Variance and Scale-Invariant Updates in Adaptive Gradient Descent for Unified Vector and Matrix OptimizationZitao Song, Cedar Site Bai, Zhe Zhang, Brian Bullins et al.ICML 2026 · 4 citations

Related papers

  1. Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph ClusteringLorenzo Orecchia, Konstantinos Ameranis, Charalampos E. Tsourakakis, Kunal TalwarICML 2022 · 12 citations
  2. Hypergraph Clustering Based on PageRankYuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, Yuichi YoshidaKDD 2020 · 38 citations
  3. Local Algorithms for Finding Densely Connected ClustersPeter Macgregor, He SunICML 2021 · 10 citations
  4. p-Norm Flow Diffusion for Local Graph ClusteringKimon Fountoulakis, Di Wang, Shenghao YangICML 2020 · 30 citations
  5. Why the Metric Backbone Preserves Community StructureMaximilien Dreveton, Charbel Chucri, Matthias Grossglauser, Patrick ThiranNeurIPS 2024 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines