Research map / Learning theory and algorithms / Combinatorial and search optimization
Theoretical Bounds on the Network Community Profile from Low-rank Semi-definite Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the low-rank SDP instead of direct SDP solvers | μ-conductance optimization · Synthetic graphs (85 and 537 nodes) | objective value: LRSDP objective values are nearly identical to SCS and MOSEK across the tested μ values | No clear effect |
| Use the low-rank SDP solver rather than SCS | μ-conductance optimization · Synthetic graphs (85 and 537 nodes) | running time: 0.7s vs 16.7s; 17.8s vs 1.6 hrs | Helped |
| Increase μ | Low-rank SDP solver · HepPh and DBLP | running time: HepPh, k=3: 1.7 min -> 1.8 hrs; DBLP, k=3: 21.8 hrs -> 1.6 days | Hurt |
| Increase rank parameter k | Low-rank SDP solver · HepPh and DBLP | running time: HepPh, μ=0.001: 1.7 min -> 6.2 min; DBLP, μ=0.001: 21.8 hrs -> 2.6 days | Hurt |
| Vary rank parameter k (ablation) | Low-rank SDP lower bound · AstroPh and HepPh | lower-bound quality | No clear effect |
| Use extremely small k (ablation) | Low-rank SDP lower bound · AstroPh and HepPh | lower-bound quality | Hurt |
| Increase the number of sampled seeded-PageRank sets | HepPh NCP estimate · HepPh | gap to lower bound: about 1/3 off | Helped |
| Analyze progressively higher k-cores | Email-Enron NCP analysis · Email-Enron | preservation of NCP structure | Mixed |
| Use the μ-conductance lower bound across varying μ | NCP characterization · AstroPh and HepPh | coverage of size-resolved lower bounds | Helped |
Closest papers by meaning
- An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks (NeurIPS 2025 · similarity 0.85)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.85)
- Optimal community detection in dense bipartite graphs (NeurIPS 2025 · similarity 0.84)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.84)
- Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering (ICML 2024 · similarity 0.84)
- Information Loss and Disparate Effects in Network Embeddings (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.