TL;DR
This paper introduces a highly scalable local search algorithm (LSPCD) for discovering polarized communities in signed networks. By incorporating a novel quadratic regularization term to prevent size-imbalanced clusters and mapping the algorithm to block-coordinate Frank-Wolfe optimization, the authors achieve a provable linear convergence rate and state-of-the-art performance on large-scale networks.
What Problem Does This Paper Address?
Signed networks use positive edges to represent friendly interactions and negative edges to represent antagonistic ones, making them ideal for studying social polarization, political divisions, and online conflict. Polarized Community Discovery (PCD) aims to identify $k$ dense communities that are internally cohesive (mostly positive edges) and externally hostile (mostly negative edges), while allowing unaligned or ambiguous vertices to remain in a "neutral" set.
A major limitation of existing PCD methods is their tendency to produce highly size-imbalanced solutions. When maximizing standard "polarity" metrics, algorithms frequently collapse into trivial solutions where one or two massive clusters swallow the network, leaving the remaining clusters completely empty. This paper tackles the challenge of finding meaningful, size-balanced polarized communities without sacrificing computational efficiency.
Methods
To resolve the cluster imbalance issue, the authors propose a new objective function that introduces an additive regularization term: subtracting the sum of squared cluster sizes ($-\beta \sum |S_m|^2$). This mathematically penalizes both oversized and highly unequal clusters, naturally driving the algorithm toward balanced solutions.
Building on this objective, they develop LSPCD (Local Search for Polarized Community Discovery). While local search algorithms are highly effective for standard network partitioning, extending them to handle an explicit neutral set efficiently is difficult. The authors show that their discrete local search is mathematically equivalent to a continuous relaxation optimized via block-coordinate Frank-Wolfe. This theoretical bridge allows them to prove a linear convergence rate of $O(1/t)$, which is remarkably fast for a non-convex objective.
To make the algorithm scale to massive networks, the authors avoid recomputing the full objective at each step—a naive approach that costs $O(Tk^2n^2)$ time. Instead, they precompute a sparse matrix product ($M = 2AX$) and dynamically update it after each node reassignment, reducing the per-iteration complexity to just $O(n+k)$.
Datasets
The authors evaluated their approach using both synthetic and real-world datasets:
- Synthetic Datasets: Generated using a modified signed stochastic block model (m-SSBM), which plants ground-truth communities to test how well algorithms handle varying levels of noise and structural cluster imbalance.
- Real-World Datasets: Eight widely used signed network benchmarks spanning online trust, voting, and political discourse: Bitcoin (BTC), WikiVot (WikiV), Referendum (REF), Slashdot (SD), WikiCon (WikiC), Epinions (EP), WikiPol (WikiP), and WoW-EP8 (W8).
Key Insights and Ideas
- Additive vs. Fractional Regularization: Instead of fractionally normalizing the objective function (which destroys the mathematical structure needed for fast local search), using an additive squared penalty successfully enforces cluster balance while keeping the optimization problem tractable.
- The Frank-Wolfe Equivalence: Demonstrating that a discrete local search step is equivalent to a continuous Frank-Wolfe step provides a rigorous theoretical foundation for an algorithm that might otherwise be viewed as a simple heuristic.
- Natural Neutrality Filtering: The gradient formulation reveals that a node is automatically assigned to the neutral set if its total contribution to all active non-neutral clusters is negative, providing an elegant, parameter-driven safety valve for low-degree or highly ambiguous nodes.
Key Results
- Superior Ground-Truth Recovery: On synthetic datasets, LSPCD significantly outperformed spectral and graph neural network (GNN) baselines. It was the only method capable of accurately recovering planted communities under high noise conditions ($\eta > 0.2$).
- Realistic Real-World Clustering: On real-world networks, baseline methods often achieved high polarity scores deceptively by creating empty or single-node clusters. LSPCD consistently found high-polarity solutions while maintaining realistic, well-balanced community sizes.
- Substantial Speedups: The matrix precomputation strategy yielded massive practical performance gains. LSPCD completes in seconds or minutes on large graphs where a naive local search implementation would take hours or days.
Limitations and Future Work
- Hyperparameter Sensitivity: The objective function relies on two hyperparameters: $\alpha$ (balancing internal cohesion vs. external hostility) and $\beta$ (controlling cluster size balance). While the authors demonstrate that the algorithm is robust within reasonable ranges, finding the absolute optimal parameters for a completely unsupervised real-world dataset still requires some empirical tuning.
- Memory Constraints: The optimized algorithm requires storing the pairwise relations matrix in memory. While highly efficient due to sparse matrix operations, scaling to web-scale graphs with billions of edges may eventually require distributed-memory parallelization.
Summary updated