Research map / Learning theory and algorithms / Combinatorial and search optimization
An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a size-balanced objective for polarized community discovery in signed networks with neutral vertices, and a scalable local search algorithm (LSPCD) that is shown to be a block-coordinate Frank-Wolfe method with O(1/t) convergence.
Problem
Finding k polarized (internally positive, externally negative) communities in signed networks while allowing neutral vertices; existing objectives (polarity) tend to yield highly size-imbalanced or empty clusters.
Approach
Replace polarity normalization with an additive objective that subtracts beta times the sum of squared cluster sizes (shifting intra-cluster similarities by -beta), which enables a local search procedure with neutral objects allowed and a provable linear convergence rate via block-coordinate Frank-Wolfe analysis.
Key results
- On synthetic m-SSBM graphs with k=4,6,10, LSPCD is reported as the only method recovering ground-truth clusters for noise eta > 0.2.
- On real-world datasets, LSPCD attains high polarity (e.g., 146.1 on REF with k=2) while keeping imbalance factor well above baselines that reach near-zero IF (e.g., SCG-MA 172.2 with IF 0.01 on REF).
- Theory: block-coordinate FW analysis gives an O(1/t) convergence rate for the non-concave, non-multilinear objective, versus O(1/sqrt(t)) for standard FW on general non-concave functions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed size-regularized local search objective instead of polarity-based methods | LSPCD · Real-world PCD datasets | polarity: 23.3 vs 25.3; 52.6 vs 53.1; 139.2 vs 116.2 | Mixed |
| Use the proposed size-regularized local search objective instead of polarity-based methods | LSPCD · Real-world PCD datasets | imbalance factor: 0.47 vs 0.93; 0.52 vs 0.99; 0.41 vs 0.87 | Mixed |
Surprising findings
- Optimizing polarity (SCG, N2PC with gamma=1) yields very low imbalance factors, often with empty clusters, suggesting polarity alone gives unsatisfactory solutions.
- Maximizing polarity-based objectives can produce solutions with multiple empty clusters.
Limitations
- Results for k=2 are the only setting where N2PC is compared, and it is limited to two clusters.
- Requires choosing beta (the best beta is selected per dataset by maximizing polarity on real data), so tuning is needed.
Experimental setup
Datasets: BTC WikiV REF SD WikiC EP WikiP m-SSBM synthetic graphs
Benchmarks: BTC WikiV REF SD WikiC EP WikiP m-SSBM synthetic graphs
Metrics: polarity imbalance factor F1-score runtime
Baselines: SCG-MA SCG-MO SCG-B SCG-R KOCG-top-1 KOCG-top-r BNC SPONGE N2PC
Builds on: correlation clustering block-coordinate Frank-Wolfe polarity objective (SCG) gamma-polarity (N2PC)
Closest papers by meaning
- Discovering conflicting groups in signed networks (NeurIPS 2020 · similarity 0.93)
- Sublinear-Time Clustering Oracle for Signed Graphs (ICML 2022 · similarity 0.89)
- Discovering Opinion Intervals from Conflicts in Signed Graphs (NeurIPS 2025 · similarity 0.88)
- Optimal Quasi-clique: Hardness, Equivalence with Densest-k-Subgraph, and Quasi-partitioned Community Mining (AAAI 2024 · similarity 0.85)
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better (ICML 2024 · similarity 0.84)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · 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.