An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
Authors: Linus Aronsson
Morteza Haghir Chehreghani
Venue: NeurIPS 2025 poster ()
Keywords: Local search
clustering
correlation clustering
polarized community discovery
polarized community detection
signed networks
graph partitioning
Primary area: general_machine_learning
TL;DR: This paper proposes a scalable local search method for detecting balanced polarized communities in signed networks, including neutral nodes, using a new objective that avoids size imbalance and achieves superior quality and efficiency.

Abstract: Signed networks, where edges are labeled as positive or negative to represent friendly or antagonistic interactions, offer a natural framework for analyzing polarization, trust, and conflict in social systems. Detecting meaningful group structures in such networks is crucial for understanding online discourse, political divisions, and trust dynamics. A key challenge is to identify communities that are internally cohesive and externally antagonistic, while allowing for neutral or unaligned vertices. In this paper, we propose a method for identifying $k$ polarized communities that addresses a major limitation of prior methods: their tendency to produce highly size-imbalanced solutions. We introduce a novel optimization objective that avoids such imbalance. In addition, it is well known that approximation algorithms based on *local search* are highly effective for clustering signed networks when neutral vertices are not allowed. We build on this idea and design the first local search algorithm that extends to the setting with neutral vertices while scaling to large networks. By connecting our approach to block-coordinate Frank-Wolfe optimization, we prove a linear convergence rate, enabled by the structure of our objective. Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-art baselines in solution quality, while remaining competitive in computational efficiency.

An Efficient Local Search Approach for Polarized Community Discovery in Signed Networks
Linus Aronsson Department of Computer Science and Engineering Chalmers University of Technology & University of Gothenburg Gothenburg. Sweden 1 inaro@chalmers.cc
Morteza Haghir Chehreghani
Department of Computer Science and
Engineering
Chalmers University of Technology University of Gothenburg Gothenburg, Sweden
mor norteza. chehreghann @chalmers.
Abstract
Signed networks, where edges are labeled as positive negative to represent friendly or antagonistic interactions, provide natural framework for analyzing polarization, trust, and conflict in social systems. Detecting meaningful group structures such networks is crucial for understanding online discourse, political divisions, and trust dynamics. A key challenge is to identify communities that are internally cohesive and externally antagonistic, while allowing for neutral or unaligned vertices. In this paper, propose a method for identifying & polarized communities that addresses a major limitation of prior methods: their tendency to produce highly size-imbalanced solutions. We introduce novel optimization ob- jective that avoids such imbalance. In addition, it well known that approximation algorithms based on local search are highly effective for clustering signed networks when neutral vertices are not allowed. We build on this idea and design the first local search algorithm that extends to the setting with neutral vertices while scaling to large networks. By connecting our approach to block-coordinate Frank- Wolfe optimization, we prove linear convergence rate, enabled by the structure of our objective. Experiments on real-world and synthetic datasets demonstrate that our method consistently outperforms state-of-the-at baselines in solution quality, while remaining competitive in computational efficiency.
Introduction
Signed networks extend traditional graph representations by associating each edge with positive or negative number, indicating friendly antagonistic relationships. Originating from studies social dynamics in the 1950s [22], signed networks introduce fundamental differences graph structure that make many algorithms designed for unsigned networks inapplicable [42, 6, 44). These challenges have fueled extensive research in recent years, leading to advances in signed network embeddings, signed clustering, and signed link prediction. We refer the survey by [42] for a comprehensive review of these methods. Most relevant to this paper is the problem of signed clustering, which split into two categories: (i) signed network partitioning (SNP), and (ii) polarized community discovery (PCD). The latter is the problem studied in this paper.
The goal of signed clustering is to identify k clusters where intra-cluster similarity is maximized (predominantly positive) and inter-cluster similarity minimized (predominantly negative). This problem has numerous real-world applications [42], particularly in social networks, where vertices represent individuals and edges capture friendly or antagonistic relationships (e.g., shared or opposing political views). Detecting conflicting groups in such networks is crucial for analyzing polarization [1, 47, 45), echo chambers [19, 17], and the spread of misinformation [41, 13, 46].
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In the SNP problem, the k groups must form a partition of the vertices, meaning every vertex must be included. Spectral methods based on the signed Laplacian have been widely used to tackle this problem [27, 11, 34, 14]. Alternatively, formulating SNP explicitly as an optimization problem leads to the well-studied correlation clustering (CC) problem [5], which is known to APX-hard. Consequently, numerous approximation algorithms have been developed [5, 8, 15, 2], with local search methods standing out for their strong performance in both clustering quality and computational efficiency [43, 10, 3, 4].
The problem formulation of PCD is identical to that of SNP, except that the k clusters are not required to form a partition of the vertices, allowing some vertices to remain mmassigned. The goal is therefore to only find the dense subgraphs of polarized communities. This accounts for cases where certain vertices are neutral w.r.t. the underlying conflicting group structure. For example, in social network with heated political debate, many users may not engage in the dispute, and their interactions might not align with any specific faction. There is a substantial body of work addressing this problem, but most approaches focus on identifying only two communities [6, 45, 36, 16, 35, 21]. As a result, they do not easily generalize to arbitrary k. To our knowledge, only two works specifically tackle PCD for arbitrary k. [12] formulated the task as a constrained quadratic optimization problem and proposes an efficient algorithm that iteratively refines small subgraphs, avoiding the costly computation of the full adjacency matrix. [44] introduced a spectral method based on maximizing a discrete Rayleigh quottent, which extends the seminal work of [6] to accommodate arbitrary k. These methods are known to produce highly imbalanced communities in terms of size [21].
The main contributions of this paper are as follows:
(i) We propose a novel formulation for the PCD problem that encourages more balanced com- munities, addressing key limitation of previous work that typically optimize polarity [44] (see Eq. 2). As demonstrated in our experiments, optimizing polarity often leads to clustering solutions with multiple empty clusters. The importance of promoting balanced communities (to avoid trivial solutions where all objects are placed in one or few clusters) is well established in the graph clustering literature [11]. In Appendix E, we expand on this, and provide some examples of practical scenarios where (reasonably) balanced communities are favorable in our context. We note that [21] also proposes an objective for PCD called y-polarity aimed at addressing cluster imbalance; however, it is restricted to the case of A 2 clusters. In contrast, our objective supports an arbitrary number of clusters k. Nonetheless, we compare to their method experimentally for k 2, and explain how it differs conceptually in Appendix F.
iii Motivated by the effectiveness of local search-basee approximation algorithms for CC (and many other machine learning models), propose the first scalable local search algorithm for PCD, which explicitly allows for neutral objects.
(iii) We establish a linear convergence rate of our local search algorithm by connecting it to block- coordinate Frank-Wolfe optimization [18, 29]. This connection is made possible utilizing the specific structure of our proposed optimization objective and extending the analysis in [43].
(iv) We propose techniques that allow the local search method to scale large networks.
(v) Finally, through extensive experiments on commonly used real-world and synthetic datasets in previous work on PCD, we show that our approach consistently outperforms state-of-th art baselines in terms of (a) recovering ground-truth solutions and (b) finding high quality solutions of reasonable cluster size balance.
2 Problem Formulation
We start by introducing the relevant notation, followed by an introduction to CC, which is connected to our problem. Finally, we describe PCD, including our novel formulation of the problem.
Notation. Consider a signed network G (V, E), where V is the set of objects and E the set of edges. The weight of an edge (i.g) E E represented by the element As,; E {-1,0, 0,10,,+1 of an adjacency matrix A. The matrix A is symmetric with zeros on the diagonal, which means Arj = A₁. and A = O. We use A,, and A., to denote row and column j of A, respectively. While we restrict all similarities to be in {-1.0,+1] (for clarity), all methods presented in the paper extend to arbitrary similarities in RR. We can decompose the adjacency matrix as A = At - A where At max(A, A, 0) and A max(- 0). A clustering with & clusters is denoted
2

---

Sin = {S1..... Sky, where each Sm S V is the set of objects assigned to cluster m E [k] {1. (1.....,R) .k). Let Nat.s EmeR Eijesm. At, and Ninia E Eijes, A7, be the sum of positive and absolute negative intra-cluster similarities, respectively. Furthermore, let N inter = Eme(h) Ene())mm) (m)) Eies.. Ejes, A. and Ninter = Emeek [pe(k)) Eies Zjes, Aig be the sum of positive and absolute negative inter-cluster similarities, respectively.
2.1 Correlation Clustering
We begin by noting that for CC, unlike PCD to be discussed in the next subsection, clustering Sjy is a partition of V. meaning V = UmE(k) Sm and each S. is disjoint. A notable feature of CC is its ability to automatically determine the number of clusters [7]. but here we we focus on the k-constrained variant of CC [20] as it is most relevant our problem. The k-CC problem can be defined as shown below.
Problem (k-CC), Find a clustering Sig that maximizes
N -N Niua
+ N inter
N inter
In other words, the goal is to find a clustering that (i) maximizes intra-cluster similarities and (ii) minimizes inter-cluster similarities. In the CC literature, it is known that maximizing certain subsets of terms in Eq. 1, such as the total number of agreements intra - N Nimter is equivalent to maximizing the full objective [9]. However, this equivalence does not hold for PCD when neutral objects are allowed, as each of the four terms in Eq. 1 contributes uniquely to the decision of whether an object left neutral. We formally show this in Appendix A, and thus focus on the full
should be clustered objective in the next section when we introduce PCD, CC is known to be NP-hard [5]. and many approximation algorithms have been proposed [5, 15, 2], with local search methods standing out for their strong performance in both clustering quality and computational efficiency [43, 10, 3].
2.2 Polarized Community Discovery
For PCD, we introduce a neutral set Sg. As a result, each object in V is either assigned to one of the non-neutral clusters Si..... S2 or designated as neutral by placing it in Sp. Consequently, clustering S1k) no longer partition of V and have S.- V Umera S,, (although all clusters are still disjoint). Given this, the goal of PCD is to identify non-neutral clusters Syy such that (i) a large value of the objective in Eq. 1 is obtained (consistent with CC), and (ii) the graph induced by the non-neutral objects as dense as possible (i.e., most edge weights are +1 or - 1). Any object that hinders either of these goals should be assigned to the neutral set Sg. This includes ambiguous objects, such as those with significant similarity to multiple clusters or those with inherently weak associations (e.g., low-degree nodes). Importantly, there exists natural trade-off between the size and density of the non-neutral clusters: small clusters can trivially achieve high density. As we will demonstrate, our objective allows for flexible balance of this trade-off.
In prior work, it is common to encourage the presence of neutral objects by penalizing large/sparse neu-nll clusters. This is typically done by normalizing Eq. by the number of non-neutral objects, i.e.,
(N intra
Nimira) + aNN N+ Viteer
Eme(k) |Sml
where a E R is used to balance (i) maximization of intra-cluster similarities and (ii) minimization of inter-cluster similarities. If = 1/(A- - 1). Eq. 2 is commonly referred to as polarity in prior work and is well-established objective for PCD [6, 44]. This choice of a was proposed in [44], based on the observation that the number of intra-similarities scale linearly with k while the number of inter-similarities grow quadratically. This choice prevents inter-similarities from dominating the objective. We use this value a throughout the paper unless otherwise stated.
However, as highlighted in [21] (and in our experiments), maximizing polarity often results in highly imbalanced clustering solutions (often with multiple empty clusters). In particular, clustering solutions with the same polarity can differ significuntly in terms of cluster size bulance. A concrete example illustrating this issue provided Appendix D. [21] proposes a new objective called --polarity that addresses this issue for the special case of k = 2. Our proposed objective is different
3

---

from 7-polarity and is applicable with any arbitrary k. In Appendix F, we compare 1-polarity with our proposed objective, defined in Eq. We also compare to [21] our experiments.
In this paper, we propose an alternative objective that, instead of normalizing by the number of non-neutral objects, incorporates regularization term by subtracting the sum of squared sizes of the non-neutral clusters.
(N intra -Mirra) + aN inter
N innter
3
> mE(k]
SSm 12
The third term in Eq. has been previously applied the minimum cut objective for unsigned networks [10]. In our context (i.e., for the PCD problem), the objective in Eq. 3 achieves two goals simultaneously: it penalizes the formation of (i) large/sparse and (ii) highly imbalanced non-neutral clusters. The second property is easy to see, as for clustering with & clusters and objects, the term Eme(N] |Sm] 2 is minimized when each cluster is assigned x objects (i.e., the clusters are perfectly balanced). Notably, the squaring of cluster sizes is what encourages cluster size balance.
We introduce regularization as an additive term rather than a normalization for two key reasons: (i) It allows flexible trade-off between the number of non-neutral objects and the density of the graph induced by them (controlled by the parameter 3 E R). which is a desirable property in this context as discussed the beginning of this section. This possibility absent in the existing methods that are based on Eq. 2 (polarity). (ii) It enables the development of an efficient optimization procedure based on local search with strong convergence guarantees. In the context of CC, local search- approximation algorithms are known to significantly outperform other methods [43, 10].
In this paper, develop the first scalable local search algorithm specifically tailored to the PCD setting. In Section 4, we demonstrate across a range of real-world and synthetic datasets that the advantages local search optimization (c.g.. for CC) carry over to PCD as well. We are now ready to formally state our problem, and we subsequently highlight its computational complexity in Thm. 1.
Problem (k-PCD). Find clustering Six) with neutral objects So V V'UUE!))) Sm. that maximizes Eg. 3.
Theorem 1. Problem 2 (i.e., k--CD) Na-hard.
All proofs can be found in Appendix B.
3 Algorithms
Thm. I underscores the necessity of approximate methods to solve Problem 2. In this section, we demonstrate how it can be solved using Frank- Wolfe (FW) optimization [18]. Specifically, we consider a variant called block- coordinae FW, which we begin by describing the next subsection. After this, we establish its equivalence to straightforward and provably efficient local search procedure. Next, we analyze the convergence rate of this approach. Following that, we propose practical enhancements to improve scalability, enabling the method to handle large problems. A detailed discussion of the impact of a and (3 is deferred to Appendix C.
3.1 Block-Coordinate Frank- Optimization
The Frank-Wolfe (FW) algorithm is one of the earliest methods for nonlinear constrained optimization [18]. In recent years, it has regained popularity, particularly in machine learning, due its scalability
[24]. In this paper, we use a variant of this method called block-coordinate FW [29]. This method yields a significantly faster optimization procedure while enjoying similar theoretical guarantees. Block-coordinate FW is applied to problems where the feasible domain can be split into blocks
D D D(1 x ... x D(n) C Rdd where each D(G) S Rd., is convex and compact and we have d= Σ d, Let zin) denote the concatenation of the variables x, E D(i) from all blocks i e [m]. The optimization problem is then
max D X Dis)) f(x))
where / differentiable function with an I.-Lipschitz continuous gradient. This approach particularly effective when optimizing w.r.t the variables in single block (while keeping other

---

Algorithm Block-coordinate Woole
Algorithm Local Search for PCD
[n| E (D(1) x .... DD"), 2: for t= 0, o,..., T do
1: Initialize (0)
1: Randomly assign each object E [n] to a cluster in Siyj. or the neutral set So
3: Select random block E [r]]
2: while not converged do
3: Select object E [nx] randomly Assign object to a cluster in Sjaj. or to the neutral set So, which maximally in- creases our objective in Eq. 3 end while
4: an := arg max 2.E
(m
4:
5: Let = 2n or optimize by line-search
c+2n
6: (t+1) = - 7) + +
7: end for
blocks fixed) simple and efficient. This turns out to the case for our problem, as will be discussed in the remainder of this section. The method is outlined in Alg. 1, where (=f(z(n) represents the gradient of / (a)))) with respect to block æ;, When the problem involves only single block (n = 1), Alg. 1 reduces the standard FW algorithm. We now show how our problem can be turned into an instance of Eq. 4. Below, we show an alternative way of writing our objective in Eq. 3.
Proposition Our objective in Eq. 3 can be written as
ΣΣ6 (Ai. mE/A/ JJESm
Σ E
EE Ar--
ME(M) (m) iESm JESp
We observe that the regularization term in Eq. 3 equivalent to shifting the intra-cluster similarities by -3. This reformulation proves highly useful for the remainder of this section. In context, each object i E [n] defines a block. We represent the cluster membership of object using æ; E (eo...., ex where em (for
{O..... k}) are the standard basis vectors. Each æ; is vector of dimension & 1, with index zero indicating membership in the neutral set Sp. Specifically, if Tz 1, object is assigned to So. Using this notation, we can now define our objective as follows.
f(x)))
Σ Σ
Jim B) a Σ Σ (KJ)) (E(M (m)
E
ip
(6)
(KJ) mE
Note that we do not include any terms involving Tio. thereby excluding contributions from neutral objects, as intended. The objective in Eq. 6 remains discrete and is therefore unsuitable for FW optimization. To address this, we relax the problem to make it continuous by allowing soft cluster memberships. Specifically, each x, E A K+1,, where A 6+1 = {x k++1 2 0, E m==o Im = 1} represents the simplex of dimension h. With this relaxation, we can now reformulate the optimization problem as follows.
max 2,EA
(x/p))
ViE[M]
Eq. 7 is a specific instance of the blockacoordinate FW formulation described Eq. 4 (where f is non-concave). Consequently, we can apply Alg. I to solve this problem.
3.2 Equivalence to Local Search Approach
We now show that optimizing Eq. 7 using Alg. 1 is equivalent to the local search procedure in Alg.
2. Let matrix G E [R+((,+), where element Gi,m = (x)))= (1)] ] is the gradient of fx]()) w.r.t.
variable m of block evaluated [")]- Given this, present the following theorem.
Theorem 2. If 2jn) in Alg I is discrete, the following hold. (a) For our problem (Eq. 7), the solution x; (line 4 of Alg. 1) is the basis vector ep. where p arg max (O.....) Gi, and the optimal value of the step size on line 6 is = 1. (b) Our objective function in Eq. 6 satisfies (x)) xz (.))) G f3*%)) (() where zim) is = with block modified to x:
From part (a) of Thm. 2, the current solution, x (4)
[n] remains discrete (i.e., hard cluster assignments) at every step of Alg. 1 for all i e [n]. Moreover, each step of Alg. 1 consists of placing object in
5

---

the cluster m E {o....,Ke }} with maximal gradient Gim- By part (b) of Thm. 2, this is equivalent
to placing object in the cluster that maximally improves our objective Eq. 3. Based on this, we conclude the following corollary.
(0) discrete, solving the optimization problem in Eq. 7 using Alg. I Corollary From Thm. 2, if [n)
is equivalent to executing the local search procedure described in Alg. 2.
3.3 Convergence Analysis
Given Corollary 1, we now present results for the convergence rate of Alg. 2. Following the prior work on the analysis of general FW algorithms [24, 29], we begin by providing the following definitions.
Definition (FW duality gap). The FW duality gap defined as [24]
g ma) = max (8)) Tma) V
(8)
which is zero and only if [in] is a stationary point. Furthermore, let ğt. = mimmminonnn-ee g( be the smallest duality gap observed in Alg. I up until step t.
(1)
Definition 2 (Convergence rate). We say the convergence rate of Alg. at least ((1/r)) if K[ōd] S O(1/re), where rz is some expression involving only and the expectation is w.r.t the random selection of blocks on line 3. n 1 the bound is deterministic.
The FW algorithm has been shown converge to a stationary point of ff under various settings, with well-established convergence rates. We summarize few known results below. The standard FW algorithm (n = 1) achieves deterministic convergence rate of O(1/t) for concave f [18] and O(1/vt) for non-concave f [28, 39]. For the block variant, [29] proves convergence rate of ((1/t) for concave f in expectation. For non-concave f. [43] proves a convergence rate of O(1/t) in expectation, under the assumption that f (x) is multilinear in each block æ; including correlation clustering. We here extend the analysis of [43] to Problem 2 (k-PCD) using Alg. 2, described in
Thm. 3. Note that their analysis cannot be applied directly to our objective function in Eq. 6 this objective does not satisfy the multilinearity property.
Theorem The convergence rate of Alg. at least nho/t = O1//t), where ho = =E(ine |
The (1/tt) convergence rate presented in Thm. should be compared with the deterministic convergence rate of O(1vv)) for general non-concave functions f under the standard FW method (n 1) [28, 39].
3.4 Improving the Computational Complexity
In the previous section, we demonstrated that Alg. 2 is guaranteed to converge at the linear rate O(1(t), making it highly efficient. In this section, we propose an alternative version of Alg. 2, designed to enhance the efficiency of each step t while maintaining full equivalence in functionality. This ensures that the convergence analysis from the previous section still remains valid. Firstly, naive implementation of Alg. has a complexity of Ó(Tk2n²) as each iteration requires (1???? compute the full objective in Eq. 6 for every candidate cluster in order to determine the best cluster for the current object i. Since the number of iterations T until convergence is typically larger than n, this approach can become computationally expensive. Part (b) of Thm. 2 offers an alternative: instead of evaluating the full objective, we can compute the gradient Gi,, which involves only terms related object i. Based this, we present the following theorem.
Theorem 4. Let Sig be the current clustering of our local search procedure, with neutral objects
So = VV UmE{A)) Sm- The gradient can then be expressed as follows.
Gi.m- 2(1 a)
Σ JESm..
Als 2a Σ Σ JES,
Ans - 23155m + 281 Sm)] 8
(9)
for all m E [R]] and G = O.
naive calculation of the full gradient G.,, for block is Okk2)). However, the specific structure of the gradient in Eq. 9 reduces the complexity to O(k)), since the term Σpe(M) Ejes, A is

---

Algorithm 3 Local Search for PCD (efficient)
1: Randomly assign each object i [r]] to one of the clusters in Sizj. or to the neutral set Sp-
2: Initialize X {0, 1]n*k with Xim if object belongs cluster [k:], and Xim otherwise. Neutral objects i E So have rows X;; of zeros.
3: M ;= 2AX
4: while not converged do
5: Select object i [n] uniformly at random
6:
D = current cluster of
7:
M, = Σ, Mi
8:
G.p = (1+ a) aM; 2.1Sp1 + 281 Spl - 8, vp [k] (See Eq.
9:
Gz =
10:
D = arg maxpe (O......... Gip
if p" P then skip to next iteration
12:
Assign object to cluster Sp.
if p [k:] then M. M.F p- 2A.
14:
if pr of 0 then M.
M. + 2.1.i
end while
100
125
Runtime (secands)
500
Runtime (seconds)
Runtime (seconds)
80
400
75-
300
200
50
100
0.0K
5.0K
10,0K
15.0K
20.0K
0.0K
5.0K
10.0K
15.0K
20.0K
20
40
80
100
Number of objects (n)
Number of objects
Number of clusters (k)
LSPCD: Olkn² T(n
Improved: O(Tkn)
LS Naive: O(TK*n²)
Figure 1: Comparison of runtime for the three implementations of Alg. 2 (local search) introduced in
Section 3.4 by varying the graph size and the number of non-neutral clusters k, using data generated from the m-SSBM model. See Section 4 for a description of this dataset. The noise level is fixed at r 0.4. When varying n. we fix & 4; when varying k, we fix n 5000. LSPCD corresponds to Alg. 3 and is used in all subsequent experiments because of its superior computational efficiency.
independent of the cluster and can therefore be precomputed (see Alg. 3). See the proof of Thm. for further insight on this. From Thm. 2, the gradient Gi,m represents the impact on the full objective in Eq. 6 if object is placed in cluster m. Thus, because G.,0 = O, we observe that an object is made neutral if its contribution all non-neutral clusters currently negative. Moreover, the total complexity is now reduced to O(Tkn), which is significant improvement over the naive approach with complexity n
We present third approach, shown in Alg. 3. We define matrix X {0, 1 with X 1 object belongs to cluster m E [K], and zero otherwise. Neutral objects i E Sy have rows X,,- of zeros. The procedure precomputes the matrix M 2AX, where Mtm is the total similarity of object to cluster Precomputing M is O(ka²), but allows gradient computation in O(k) (line 8). then have to update M accordingly (lines 13 and 14), which is Om)), reducing the per-iteration complexity O + k). The total complexity is O +T + k)), which improves on the OTTnk) approach because, (i) computing M involves a sparse matrix product, which is highly efficient in reducing per-iteration cost leads to significant practical gains.
practice, and (ii) since T
On the largest datasets in our experiments, Alg. 3 completes in seconds or minutes, while the naive version would take hours or days. Figure 1 presents runtime comparison of the three approaches discussed above. The method in Alg. 3 (LSPCD) achieves the best computational efficiency, significantly outperforming the naive approach in Alg. 2. Consequently, Alg. 3 is used in all subsequent experiments. Appendix G.5, we further demonstrate the scalability of Alg. 3 to large-scale graphs.
7

---

4 Experiments
In this section, we present our experimental evaluation. Additional results are provided in Appendix G. We use eight publicly available real-world datasets commonly adopted in prior work on PCD [44], with dataset details included in Appendix G.1. Notably, no real-world datasets with ground-truth solutions for PCD (i.e., where neutral objects are allowed) currently exist, Consequently, prior work has relied on polarity (Eq. 2) as a proxy for evaluating solution quality [6. 44]. For consistency, we also report polarity scores for these datasets. Additionally, following previous work [44], we include experiments on synthetic datasets where ground-truthe solutions are available. Throughout this section, we fix a and / (as specified below). In Appendix C. we provide a detailed discussion on the impact of these parameters (and we investigate experimentally our local search algorithm for PCD, named LSPCD (see Alg. 3), to several baseline methods, which we introduce below. The complete source code for all experiments is publicly available'.
Appendix G.8). We compare
Baselines. (i) SCG [44] is a spectral method that identifies & non-neutral clusters by maximizing polarity (Eq. 2) with a 1/(k- 1)). It solves a continuous relaxation and applies one of four rounding techniques, resulting in SCG-MA, SCG-R, SCG-MO, and SCG-B. We refer to [44] for details. (ii) KOCG [12] optimizes similar objective and formulates
constrained quadratic optimization problem (this optimization approach is very different from ours). It outputs a set of local minima. For comparison, we select KOCG-top-1 (the best local minimum) and KOCG-top-r. where r is chosen such that the number of non-neutral objects is closest to SCG-MA, following [44]. (ii) BNC [11] and SPONGE [14] are spectral methods designed for SNP that do not explicitly handle neutral objects. As in [44], we apply two heuristics with these methods: (a) we treat all & clusters as non-neutral, and (b) we run the methods with :: + clusters and then designate the largest cluster as neutral. These variants are denoted BNC-k / SPONGE-k and BNC-(K + 1) SPONGE-(K: + 1), respectively. (iv) N2PC [21] introduces a framework that employs graph neural network (GNN) to predict cluster memberships in the PCD setting. They propose "-polarity, a generalization of polarity designed to encourage balanced clusters. Higher values of 7 impose stricter balance constraints, with y recovering the standard polarity definition (Eq. 2). Since their method supports only k 2 clusters, results are reported exclusively for this setting. See details about baselines in Appendix G.2.
Metries (i) Following prior work, we use polarity to evaluate the quality of different methods [6, 44], defined as in Eq. 2 with a 1/(k- - 1). (ii) For datasets with available ground-truth, we measure the recovery-rate of ground-truth clusters using the Fi-score, which is the precision and recall averaged over all clusters (as in [6. 44]). (iii) To evaluate the balance of a clustering solution Sinj. we use the imbalance factor from [38]. Let p. = |Sel/ EmE())
|5ml be the proportion of objects in cluster S...
The imbalance factor (IF) is defined as
1 IP(I.....,. = -- loga
Σ
p logg (b) E 10,
(10)
where 1 indicates perfect balance and 0 indicates maximal imbalance (i.e., all objects in one cluster). For & = 1, the numerator reduces to Shannon entropy; we use & = 3 to penalize highly imbalanced solutions more strongly. The conclusions of our results are robust to changes in & around our chosen value. Results for other values of are provided in Appendix G.6. In addition, Appendix G.9 presents a detailed summary of the solutions found by each method, including the number of non-neutral objects, the number of non-empty clusters, runtime, and more.
Synthetic datasets. In our first experiment, we evaluate how well the methods recover ground-truth clusters using synthetic networks. Following [6, 44], we employ the modified signed stochastic block model (m-SSBM), which was specifically designed generate synthetic graphs with planted ground fround-truth communities for PCD. The m-SSBM model is parameterized by four variables: (i) n. the total number of nodes; (ii) k. the number of nen-neutral clusters: (iii) f, the size of each nen-neutral cluster, and (iv) E [0, 1]. which controls the edge probabilities. Smaller values of 17 correspond to denser neu-rll clusters and lower levels of noise (see Appendix G.3 for detailed description). Here, we assume balanced ground-truth clusters of size f. In Appendix G.4, we show that our method remains robust when increasing cluster imbalance on synthetic data.
In Figure 2, we present the Fi-score and polarity of various methods on different synthetic graphs generated using the m-SSBM model, across different noise levels v). For clarity, we include the
ltttps://githbb.coo http::://gtaab.oo//////sssssss/s http://tww.......oo.o/////////ea
8

---

100,
1.0
1.0
0.8
51.rc
0.8
F1-Score
0.8
F1-5core
0.8
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.2
0.0
0
200
200
200
200
150
150
150
Polarity
Palarity
Poiarty
Polarit
100
100
100
100
50
50
50
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
0.0
0.2
0.4
0.6
Ground Truth BNC-K
LSPCD (ours)
SCG-MA
SCG-MO
SCG-R
BNC- +
SPONGE-
SPONGE
N2PC
Figure Fi-score and polarity of different methods on synthetic graphs generated using the m-SSBM model, as the noise level 1y varies. See main text below for details. See Appendix G.4 for more results.
best performing baselines (KOCG peforms poorly here). Each setting is repeated 10 times, and we report the average. We fix B = 0.4 for LSPCD (it is robust to the choice of ()) and y for N2PC. We see that the recovery rate of all methods decreases as 1) increases, since the sparsity and noise level of the graph increases. For baseline methods, being the only method capable of recovering the ground-truth solutions for 1/ > 0.2. For k 2, we observe that our method, SCG-MA, and N2PC perform the best. However, for k 2 (which N2PC is limited to), the problem is significantly more simple. Finally, we see that the ground-trutt truth solution correlates with large polarity, justifying the use of polarity to measure solution quality for the real-world data.
4, 6, 10, we observe that our method significantly outperforms
Real-world datasets. Table present results for different methods and datasets with & 2, 4, 6 (we use the same values of & as SCG [44]). |E] denotes the number of edges with non-zero edge weight. Only seven of the eight datasets are shown (due space limit); see Appendix G.9 for complete results. The spectral clustering methods, BNC and SPONGE, exceeded memory limits on large datasets (caused by k-means), indicated by dashes.
report the mean over five runs, with standard deviations included in Appendix G.9. For our method, we select the value that maximizes polarity, testing 10 values per dataset, while we a 1/(k: - 1) for methods. For each method and dataset, we report the polarity (POL) and the imbalance factor (IF).
The results show that our method is highly competitive, often the best, in polarity across all datasets. In particular, our method consistently finds solutions with large polarity, while maintaining good cluster size balance (large imbalance factor). Additionally, our method does not impose strict balance constraints, which is beneficial since real-world clusterings are rarely perfectly balanced. Instead, it identifies high-polarity solutions with reasonable balance, making more practical for real-world applications. Notably, in cases where baseline methods attain higher polarity, it is usually at the cost of a very low imbalance factor (which often implies one or more empty clusters). Moreover, baseline methods with imbalance factor near generally exhibit very low polarity. This observation highlights the inherent trade-off between polarity and cluster balance, which our approach balances very well.
Results for N2PC are only included for 2, it does not support 2. We observe that increasing 7 results in more balanced clusters, which consistently leads to lower polarity. When N2PC optimizes standard polarity (? = 1), the polarity is usually highest, but the imbalance factor is consistently very low (often near zero). This suggests that optimizing polarity alone (as SCG does) is not ideal; encouraging the algorithm to produce more balanced solutions (even at the cost of reduced polarity) generally yields solutions that align better with user expectations in practice (see Appendix E for a detailed discussion on this). This a well-known observation in previous work on clustering of signed and unsigned graphs (beyond PCD, without neutral objects) []]]. While N2PC

---

Table 1: Polarity (POL) and imbalance factor (IF) for different methods and real-world datasets. denotes the number of edges with non-zero edge weight.
BTC
MiXIV
REF
Niw.C
EF
VIKIP
6K
[B]
214K
IM
251K
500K
2M
711K
715K
POL. IP
POL. TP
POL. TP
POL TP
POL TP
POL TP
SCG-MA
28.8 0.16
71.5
0.01
172.2
0.01
77.5
0.01
155.2
0.53
128.3
0.04
82.8
0.01
SCG-MO
29.5 00.03
71.7
0.01
174.
0.01
79.7
0.01
175.7
0.43
128.7
0.04
88.4
0.01
SCG-B
21.6 0..9
37.6
0.04
116.3
0.03
61.0
0.05
129.3
0.64
156.4
0.04
46.5
0.04
SCG-R
14.2 0.25
54.7
0.17
120.9
29.7
0.08
101.1
0.57
72.3
0.19
36.1
0.17
KOOG-FOP-
0.99
0.96
0.98
14.0
0.94
BNCC-A4+11
10.8 0.13
-1.1 0.79
-1.0 1.00
BNC-
5.3 0.02
15.8
0,00
41.5
0.00
MOONGE-Ck+11
0.79
1.0
0.47
0,79
SPONGE-K
29.6
172.8
N2PC (4 1.22)
30.1 0.46
71.7
0,01
173.6
0.02
81.1
0,00
175.7
0.77
169.8
0.00
87.1
0,00
N2PC (9 = 1.5)
24.4 1.00
70.0
0,10
130.3
0.94
81.8
0.00
158.2
0.99
169.9
0.00
86.6
0.02
N2PC 1.7)
23.9 1,00
59.1
0,56
119.4
1,00
55.0
1.00
155.5
0.99
124.3 0.29
75.2 0.39
N2PC
LSPCD (OURS)
23.3 0.41
52.6
0.52
139.2
00.11
61.1
0.54
113.6
0,56
111.5
0.58
71.6
0.27
SCG-MO
25,3 0.22
53.1
0.70
38.5
117.9
129.0
39.7
SCG-B
12.4 0.23
24.8
0,60
116.2
0.00
48.3
0.38
49.8 0.86
94.1
0.54
45.7
0.21
SCG-R
8.0 0.52
19.5
0.44
118.7
0.02
10.7
0.76
41.1 0.66
65.1 0.20
35.7
0.14
KO0G-TOP-1
8.4 0.90
4.5
0.81
15.0
0.65
2.6 0.80
4.5 0.23
8.9 0.91
3.1 0.71
KOCG-TOP-
3.7
0.79
3.8
11.0
(ACC-(4+1)
0.23
1.00
BNC
5.2 0.01
15.8
0.00
41.5 0.00
SPONGR-(K+11
0.10
1.0
0.71
1.0 0.79
SPONGE-K
0.00
0.00
15.8
0.00
41.5
0.00
LSPCD (OURS)
20.0 0.49
00.99
46.2
0.56
137.6
10.33
57.1
00.43
96.1
0.53
103.4
00.47
58.7
0.54
SCG-MA
14.6 0.46
45.5
0.42
84.9
0.62
17.8
0.17
102.6
0.07
88.8
0.52
57.5
0.42
SCG-MO
15.2 0.45
47.0
0.41
0.72
34.6
0.29
111.6
0,22
0.26
0.24
47.7
0.32
SCG-R
6.9 0.41
10.4
0.79
50.3
0.36
7.9
0.46
18.3 0.74
43.3 0.30
0.42
KOCG-TOP-1
0.92
0.92
4.5 0.96
8.6 0.93
0.90
4.9 0.53
6.0 0.94
10.1 0.86
KOCG-TOP-r
0.87
3.1 0.96
4.0
3.3 0.91
1.5 0.99
6.8 0.89
3.6 0.77
BNC- ())
-4.2 0.25
-0.8
SPONGE-(K+1)
0.15
0.86
1.0 0.92
SPONGE-K
3.1 0.00
15.8 0.00
41.5 0.00
is competitive with our method, it is limited to k 2, requires tuning 7, and is significantly more complex (it requires training graph neural network, leading to higher runtime, see Appendix G.9).
Conclusion
We proposed novel formulation of the polarized community discovery (PCD) problem that empha- sizes (reasonably) balanced communities in terms of size, addressing key limitation of prior work, which typically optimizes polarity (Eq. 2) and often produces highly imbalanced clusterings. To tackle this, developed the first efficient and scalable local search method for PCD and established a connection to block-coordinate Frank-Wolf (FW) optimization. While the standard FW algorithm known to achieve convergence rate of ((1 (1/VI)) for general non-concave objectives [28, 39), we showed that, due to the specific structure of our objective in Eq. 6, our method achieves significantly faster linear convergence rate of (1//t), despite the function being both non-concave and mulliiiiline.r. Extensive experiments demonstrated that method (LSPCD) consistently produces high-quality clusterings with reasonable cluster size balance, better aligning with practical expectations. Furthermore, observed that the strong performance of local search algorithms correlation clustering carried over to the PCD setting as well. Overall, our approach offers compelling alternative in the PCD literature, both in terms of performance and simplicity (see Alg, 2). Altemative methods in the literature are significantly more complex.
Acknowledgments
This work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
10

---

References
[1] Lada A. Adamic and Natalic Glance. The political blogosphere and the 2004 u.s. election: divided they blog. In Proceedings of the 3rd International Workshop Link Discovery, page 36-43, 2005.
[2] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55(5), 2008.
[3] Linus Aronsson and Morteza Haghir Chehreghani. Correlation clustering with active learning of pairwise similarities. Transactions on Machine Learning Research, 2024.
[4] Linus Aronsson and Morteza Haghir Chehreghani. Information-thheortiic active correlation clustering. In IEEE International Conference on Data Mining, ICDM, 2025.
[5] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering, Mach. Learn., 56(1- 31389-113, 2004.
[6] Francesco Bonchi, Edoardo Galimberti, Aristides Gionis, Bruno Ordozgoiti, and Giancarlo Ruffo. Discovering polarized communities signed networks. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, page 961-970, 2019.
[7] Francesco Bonchi, David Carcia-Soriano, and Edo Liberty. Correlation clustering: from theory to practice. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014.
[8] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. Comput. Syst. Sci., 71(3))360--38 2005.
[9] Morteza Haghir Chehreghani. Information-theoret validation of clustering algorithms. PhD) thesis, ETH Zurich, 2013.
[10] Morteza Haghir Chehreghani. Shift of pairwise similarities for data clustering. Mach. Learn., 11(66):2025-2051, 2023.
[11] Kai- Yang Chiang, Joyce Jiyoung Whang, and Inderjit S. Dhillon. Scalable clustering of signed networks using balance normalized cut. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, page
2012.
[12] Lingyang Chu, Zhefeng Wang, Jian Pei, Jiannan Wang, Zijin Zhao, and Enhong Chen. Finding gangs in war from signed networks. Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, page 1505-1514, 2016.
[13] Nicole A. Cooke. Fake News and Alternative Facts: Information Literacy in Post-Truth Era. ALA Editions, 2018.
[14] Mihai Cucuringu, Peter Davies, Aldo Glielmo, and Hemant Tyagi. Sponge: A generalized cigenproblem for clustering signed networks. In Proceedings of the SirentySeccome International Conference on Artificial Intelligence and Statistics, pages 1088-1098, 2019.
[15] Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Theor. Comput. Sci., 361 (2-3) 2006.
[16] Adriano Fazzone, Tommaso Lanciano, Riccardo Denni, Charalampos E. Tsourakakis, and Francesco Bonchi. Discovering polarization niches via dense subgraphs with attractors and repulsers. Proc. VLDB Endow., 15(13):3883-33
2022.
[17] Seth Flaxman, Sharad Goel, and Justin M. Rao. Filter bubbles, echo chambers, and online news consumption. Public Opinion Quarterly, 80(S1):298-38) -20, 2016.
[18] Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming. Naval Research Logisties Quarterly, 3(1-2):95-110, 1956.
[19] R. Kelly Garrett. Echo chambers online?: Politically motivated selective exposure among
internet news l.ersl. Journal of Computer-Mediatee Communication, 14(2):265-288 2009.

---

[20] Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clus- ters. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. page 1167-1176, 2006.
[21] Francesco Gullo, Domenico Mandaglio, and Andrea Tagarelli. Neural discovery of balance- aware polarized communities. Mach. Learn., 113(9);661 1-6444 2024.
[22] Frank Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143 146, 1953.
[23] Yixuan He, Gesine Reinert, Songchao Wang, and Mihai Cucuringu. Sssnet: Semi-supervised signed network clustering. In Proceedings of the SIAM International Conference on Data Mining (SDM), pages 244-252, 2022.
[24] Martin Jaggi. Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In Proceed- ings of the 30th International Conference on Machine Learning, 2013.
[25] Victor Kristof, Matthias Grossglauser, and Patrick Thiran. War of words: The competitive dynamics of legislative processes. In Proceedings The Web Conference, pages 2803-2809, 2020.
[26] Jérôme Kunegis. Konect: the koblenz network collection. In Proceedings of the 22nd Interna- tional Conference on World Wide Web, page 1343-1350, 2013.
[27] Jérôme Kunegis, Stephan Schmidt, Andreas Lommatzsch, Jürgen Lerner, Ernesto W. De Luca, and Sahin Albayrak. Spectral Analysis of Signed Graphs for Clustering, Prediction and Visualization. pages 559-570. 2010.
[28] Simon Lacoste-Julien. Convergence rate of frank-wolfe for non-convex objectives, 2016.
[29] Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate Frank-Wolf optimization for structural SVMs. In Proceedings of the 30th International Conference on Machine Learning, 2013.
[30] Mirko Lai, Viviana Patti, Giancarlo Ruffo, and Paolo Rosso. Stance evolution and twitter interactions in an italian political debate. In Natural Language Processing and Information Systems, pages 15-27, 2018
[31] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. 2014.
[32] Lingyang Chu. Source code: Finding gangs in war from signed networks. https://githut com/ hom//inggangcchu//nn SWW.DDD2I...DDI... 2016.
[33] Silviu Maniu, Talel Abdessalem, and Bogdan Cautis. Casting a web of trust over wikipedia: an interaction-based approach. In Proceedings of the 20th International Conference Companion on World Wide Web, page 87-88, 2011.
[34] Pedro Mercado, Francesco Tudisco, and Matthias Hein. Spectral clustering of signed graphs via matrix power means. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 4526-4536, 2019.
[35] Jason Niu and Ahmet Erdem Sariyüce. On cohesively polarized communities in signed networks. In Proceedings of The Web Conference, pages 1339 1349, 2023.
[36] Bruno Ordozgoiti, Antonis Matakos, and Aristides Gionis. Finding large balanced subgraphs in signed networks. In Proceedings of The Web Conference, page 1378-1383 13888, 2020.
[37] Peter Davies and Aldo Glielmo. Signet: A package for clustering of signed networks. https:
/ //githur gigthuu.cc. com/ alan turing- instintttteettt signet, 2019.
[38] Mohsen Pirizadeh, Hadi Farahani, and Saeed Reza Kheradpisheh. Imbalance factor: simple new scale for measuring inter-class imbalance extent classification problems. Knowl. Inf. Syst., 65(10):115-44183 2023.
12

---

[39] Sashank J. Reddi, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic frank-wolfe methods for nonconvex optimization. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), page 1244-1251, 2016.
[40] Ruo-Chun Tzeng. Source code: Discovering conflicting groups in signed networks. https: 2020.
/ //github. cttp:///ccttteegeeeee///0000---0
[41] Kai Shu, Amy Sliva, Suhang Wang. Jiliang Tang, and Huan Liu. Fake news detection on social media: A data mining perspective. SIGKDD Explor. Newsl., 19(1), 2017.
[42] Jiliang Tang, Yi Chang, Charu Aggarwal, and Huan Liu, A survey of signed network mining in social media. ACM Comput. Surv., 49(3), 2016.
[43] Erik Thiel, Morteza Haghir Chehreghani, and Devdatt Dubhashi. A non-convex optimiza- tion approach correlation clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 5159-5166, 2019.
[44] Ruo-Chun Tzeng, Bruno Ordozgoiti, and Aristides Gionis. Discovering conflicting groups in signed networks. In Advances in Neural Information Processing Systems, volume 33, pages 10974-10985, 2020.
[45] Han Xiao, Bruno Ordozgoiti, and Aristides Gionis. Searching for polarization in signed graphs: a local spectral approach. In Proceedings The Web Conference, pages 362-372, 2020.
[46] Shuo Yang, Kai Shu, Suhang Wang, Renjie Gu, Fan Wu, and Huan Liu. Unsupervised fake news detection on social media: A generative approach. Proceedings of the AAAI Conference on Artificial Intelligence 33(01):5644 5651, 2019.
[47] Sarita Yardi and Danah Boyd. Dynamic debates: An analysis of group polarization over time on twitter. Bulletin of Science, Technology & Society, 3065):316-327, 2010.
13

---

A Comparing CC and PCD
The following proposition presents alternative objectives equivalent maximizing Eq. 1 (i.e., solving the k-CC problem, see Problem 1). While this is known in the CC literature [9], we include complete summary here better motivate our problem formulation of PCD.
Proposition 2. Problem is equivalent to finding clustering Sig that maximizes any one of the four objectives in Eqs. 11-14 (ie., they share all local maxima).
Not
nama"
N
mntr
(11)
Niina
N inter
(12)
N innrra
(13)
N
inter
Not
inter
(14)
Furthermore, maximizing any other combination of the four terms is not equivalent Problem
All proofs can be found in Appendix B. The four formulations of CC shown in Prop. 2 respectively
correspond to (i) maximizing agreements (Eq. 11), (ii) minimizing disagreements (Eq. 12). (iii) maximizing intra-cluster similarities (Eq. 13), and (iv) minimizing inter-cluster similarities (Eq. 14).
Finally, we can combine all these notions into one single objective (i.e., Eq. 1). CC an NP-hard problem, leading to the development of numerous approximation algorithms. Existing approximation algorithms maximize one of the five expressions discussed above [7]. leading to differences in clustering performance, computational complexity and theoretical performance guarantees.
We now explain why Eq. I, which incorporates all relevant terms, must be considered when neutral objects are allowed. Much prior work on PCD also optimize all terms, but often without providing detailed justification for this choice. The next proposition provides such an intuition.
Proposition 3. clustering STk) with neutral objects So V Ume(N) Sm that maximizes one of the objectives in Eq. or Eqs. 11-14 is not guaranteed to maximize any of the other objectives".
From Prop. 3. we conclude that each term Eq. provides unique information when neutral objects are allowed, unlike the standard CC problem, where the different objectives are equivalent, as outlined by Prop. 2. This makes Eq. 1 the most reasonable objective for optimization in this context, as effectively balances all contributing terms. Moreover, since each term captures unique aspects of the PCD problem, may be beneficial to weight them differently to achieve an optimal trade-off.
B Proofs
Theorem 1. Problem 2 (i.e., k-PCD) is NP-hard.
Proof. Fix a, 3 e R to any values. Assume that we know which objects in V should be assigned to the neutral set So in the optimal solution to the k-PCD problem. Then, let V = V So and let E be the set of edges between objects V'. Since no object to finding partition of V that maximizes Eq. 3. We rewrite objective in Eq. as
should be neutral, the problem reduces
(N+ intra
(inira) + a(N Miteer
N+ Nitter)
Σ
Smm!
mE(R]
Σ
Σ
As.j a Σ Σ
Σ
Ar. - 3 Σ
Smm
mc(k] i.ESS
mE{K PE(A) (m)
iE
mE(M
(15)
JES,
Σ
Σ
B)
Σ
Σ
Σ
A..i
mE|k
i.ES
mE(k]
(m)
iES
JESp
The second equality follows from Prop. 1. Defining Caim EO.DE Arj. obtain:
Unless &s = 2. in which case Eq. 11 and Eq. are equivalent established in [6].
14

---

EED
Σ
A.j
Csim
E
E
Arj.
(16)
mE(M) (m))
V JESy
mc(k] t.jESm
Substituting this into Eq. 15 and simplifying:
Σ
Σ
(Ai. - - Σ E
Σ
A
mE(k] 1.688
mE DE (E(
ic
JESp
Σ
Σ
(Ais - 3) - aa(Csim
Σ
Σ
Ai.))
(17)
mE[k IJES
mE f.ES
(1 + 0
E
Σ (Ats - (3) -.Csim-
ME 6JES
Defining A/, (1 +0) (A B), we observe that since Csim is a constant across clustering solutions, the problem reduces to finding partition of V that maximizes Eme Eijesm. A/.3- This is equivalent to the max correlation objective (Eq. 13) applied the transformed adjacency matrix A'. By Prop. 2, this objective is equivalent to the k-CC problem (Problem 1). Thus, solving the k-PCD problem requires solving the k-CC problem on the instance = (V', meaning
k-PCD is least hard k-CC. Since correlation clustering is NP-hard [5, 20], conclude that k-PCD is also NP-hard.
Proposition 1. Our objective in Eq. 3 can be writlen as
Σ Σ
(Ar. - B) a Σ
Σ
Σ
Σ
Aig.
(5)
mE| J.ES
me [M] (m)) iESm.. JESy
Proof. We have
(N intra
Ninrra + ae QQNNinsrr
N
inter) 3
Σ
S5m 2
me [k]
Σ
Σ
Aij Σ
Ai, - 3 Σ
|
mE(k] iJE8m
me(k) pc [m))
iES
mE(k)
JES,
= Σ
Σ
Arj a Σ
Σ
Σ
Ar, 3 Σ
mETk WEE5
mE[k] pE[k]]fm iES
mE[ki ijESm
(18)
JES,
Σ
Σ
Aij Σ
Σ
Σ
Aij
Σ
Σ
B
mE(R) [ i.ES8
mE(M) Pe [R] (m)
E 1.jES
jES,
Σ META IJES...
Σ
-)
Σ
Σ
Σ
Ar.j
mEll (m)
EES JESP
The second equality (line 3) holds because the number of pairs of objects inside cluster m |mm 2 A similar regularization is established in [10] for the minimum cut objective, where it is shown that optimizing this minimum cut objective regularized with -3 > |Sm is equivalent to optimizing the max correlation objective (Eq. 13) with similarities shifted by B. However, their result specifically considers the full network partitioning of unsigned networks, where the initial pairwise similarities are assumed non non-nvgative. Moreover, they use a different regularization in practice: they shift the pairwise similarities so that the sum of the rows and columns of the similarity matrix becomes zero.
Li
(0) Theorem 2. If Zin) in Alg is discrete, the following hold. (a) For our problem (Eq. 7), the solution x; (line 4 of Alg. 1) is the basis vector ep, where optimal value of the step size on line is y = 1. (b) Our objective function in Eq. 6 satisfies (m) -
arg max.me(0.... Gim and the
-m. ..))) Ge.: = saa%)) [a)(())
(t) where ait) is a with block modified to wi.
15

---

Proof. We begin by writing our objective function f()))) in Eq. 6 as follows.
((m(m))
Σ
Σ
Tim
(
- 8) a 3 E
Dim jp
(JJE mE]A]
(LJ)EB mE(k) (
Σ
Σ
m +
Σ
Σ
Tim jm (Ais 3)
Σ
Σ
jp Ap
iE|n] mE(k]
(b,))E melk] if$
(1,))E mE|k pE(M)(m)
Σ
Σ
Fim
B +
Σ
Zim jm (Ais
-
Σ
E
Zim Pip
mE]
(iJ)) mE(K pE(M)(()
171
(19)
In the second equality, we separate out the terms for jj and use that A,, = 0. In the third equality. we consider that [i] is discrete solution. This makes the first term linear instead of being quadratic w.r.t. Tim, which is crucial step in proving the theorem. Let (xx) denote (()))) when treating all blocks other than æ; as constants. Then,
f(x;)
Σ mE[k]
TimB 3+mB+2 +2
Σ jE(n|M() mE(k)
Σ
I'm jm fm (Ais- -B) - 22 Σ E
Tim +
jEIm/MO mE(k) pE[k/Mm}
Σ Tim (-B+ + 2
Σ
(zim(Ais - 33--00
Σ
Asp +C,
ME(M
jE(m]((
Com
(20)
where C' denotes terms independent of æ;. Define E RR++1 with elements
Cim +
Σ
(Ijm(AL) - 3) - Σ AppAis), for E [k], Go 0. (21)
jE(n]M(
pm)
Then, obtain
f(x:)
Σ
Tim Cim + C C'= - + C.
(22)
mE ))
Eq. 22 clearly illustrates that the contribution of the neutral component (index zero) of each Tim is not included total objective (since Gan = 0). From Eq. 22, the gradient of (() w.r.t. æ; is
V v.f(z C..
(23)
Let (t) (=f()(()) be the gradient of (())) evaluated at the current solution a (defined as in Eq. 21). The optimization problem on line 4 of Algorithm 1 is
T C; arg max E,EA
(24)
Since Eq. 24 is linear program over the simplex A 1+ the optimal solution is obtained by setting -i = for m = arg maxma ci and x for all p A m. This proves the first statement of part (a) of the theorem.
Next, we note that the difference (wfj)) - f( (x) simplifies to f(x;) f(x(()) (where f(x,) is defined in Eq. 20), since only the terms involving the variables in block change between 2ij)) and (8) [n] Therefore, we can derive the following.
16

---

f(x(n) f(((/))
f(x,) )(x
((x))' o + C) - (1x)))) (9) +C)
((x))) c. +0) (To)"))ee +
(25)
((x))) - (a ())
(m) (0 V (a)(
Here, of is defined as in Eq. 21 w.r.t T.... Since कi, and (1)
|/j differ only in block i, and neither ct (t) depend on the variables in block i, follows that c = = (t)
justifying the third equality. In Eq. 19, we assume that [in] is discrete. To ensure this property holds throughout, require that both min] and a remain discrete for all (O.....7).
nor 6
First, by assumption in the theorem, (0)
[in] is discrete. From part (a), we know that x is discrete, (t)
implying कं. is discrete as long as [nn discrete. Furthermore, from Eq. 25, the optimal solution 2 in line of Algorithm maximally increases the objective, which ensures the optimal step size in line 6 is 7 (proving the second statement of part (a)). Consequently, .x! (++1) remains discrete. By induction, this guarantees that [n] is discrete for all f, ensuring Eq. 25 holds for all E =o,,...,T T). This completes the proof of part (b) of the theorem.
Theorem 3.
The convergence rate of Alg. 2 is at least nho/t = O(1/(), where ho = Eosie |Aisl-
Proof. From Definition I, we have that, in our case, the FW duality gap is defined as
(())))) =
max s.EARtiMielo
($(n) x(m)) V (Z(m))
(26)
Then, recall that
min g( (n)
(27)
0sist-1
the smallest duality gap observed in Alg. up until step As established by [29] for general domains, the FW duality gap can be decomposed as follows.
g( =
max
(8(n) T(()) (
E. ViE(n)
max s.E k+ ViElm
(8: x;) v.f(
(E(n)
(28)
Σ ie(n
max (s. - x.) V (x
Let gi (3)))) == max nax,,e x.) (Zr()) be the duality gap related block i. We have that the FW duality gap is the sum of the gaps from each block: g(X(x)) Σie (x
From Definition 2 (convergence rate), in order to prove the stated convergence rate, we need to show that Elğe] < n/g/tt. The structure of our proof is similar to the proof of Theorem 2 in [43]. However, here adapt it to our problem and make the proof more rigorous (including correction of mistake in the proof by [43]). A key difference that our objective Eq. 6 is not multilinear in the blocks i. Then, shown in Eq. 19 of Thm. 2, the first quadratic term be transformed into linear by assuming a discrete solution (which we showed holds at every step t).
In Alg. 1, block E [n] is chosen uniformly at random (on line 3). Therefore, we have
17

---

E Egg.(
( |n|
||اا
Σ
P(i is selected) gi (x(x) (n))
[m]
Σ
9r
(x (n)
Em(m]
(29)
Σ
max (s; (s.-);()) (a)(
n
o.
Ea++1
kE(m]
g [m]
(t) [mn) both sides and obtain
We now take expectation w.n.t
1 (a 1 (m))
B|Elg (2 (mn 12 [1]]
(30)
where the last equality follows from the Law of Total Expectation (i.e., that Ey [Ex [X]]] = Ex Ex[X],
where X and Y are random variables). We therefore have that i [ [x] Elg (0) [n] }] where the
n expectation is w.r.t. all randomly chosen blocks i before step t. Now, from Thm. we have that our objective satisfies
[ax - ((x(()) = (x( (0)
max (s x0)) (a
(31)
" E4++1
Then, we have
Big(x
E[g. (a: (t) [1]
1=0
Σ [a [m]
(++1)) f(a
(32)
(7) || f(zz (0) [f
s OPP f(z)))
where the third equality is due to the telescoping rule and OPT is the objective value of the optimal clustering solution to Problem (A-PCD). On the other hand, we have
Σ t=
Elg(
I ElGr]
(33)
where ze is defined as in Eq. 27 (the smallest gap observed until step f). Therefore,
T
Bigrl <
((x
(34)
Egrrl < nOPP f(x(0)))
T
The value of OPT depends on the particular instance. In order to obtain an instance-independent bound, we use that OPT - (0) ) < EoieE |A, resulting in
n E(BNEE |An
1 <
(35)
T
18

---

which we aimed to show since it holds for any T.
Corollary 1. From Thm. 2, if (m) is discrete, solving the optimization problem in Eq. 7 using Alg. 1 is equivalent to executing the local search procedure described in Alg. 2.
(0)
Proof. From part (a) of Thm. 2, the current solution, [n] remains discrete (i.e., hard cluster assignments) at every step of Alg. for all i [n]. Moreover, each step of Alg. 1 consists of placing object the cluster m E {0....,k] k} with maximal gradient G.m-- By part (b) of Thm. 2, this is equivalent to placing object in the cluster that maximally improves our objective in Eq. 3. O
Theorem 4. Let Siq be the current clustering of our local search procedure, with neutral objects
So = V. UmE(k) Sm- The gradient can then be expressed as follows.
Gi, = 2( +
ALs
ALj
20 Σ Σ
Av,j -03/mmlml + 281 Sm)] -
(9)
jESm
PEIN
for all m E [k] and Gi = O.
Proof. From Thm. 2, we recall that since the current solution æ (1) objective can written as
[n] always remains discrete, our
f( iE
T 2n 3+ Σ
Σ
Fim jm
A
Σ Σ
I I'm jp Ar.j.
mEik]
(.IEE me[k] iff
(K,)e E me [k] (m(
(36)
We let f(z denote (()
(0) [n]
when treating all blocks other than x
constants. Then,
f(x!")) = Σ
Fim
(1)
+
Σ
x (4) (Ais - 3) 2xx
Σ
Σ
S And +
mk[k]
JE mR]
jEin] (t) pm(k)
(37)
Therefore, we have
(1) Gi. = (V 1m
Cims
for m E [k].
(38)
This holds because neither Cim nor C depend on im Furthermore, since æ.o does show up in Eq. 37, everything in Eq. 37 is a constant w.r.t. Tzo. We therefore have
G.,0 = V (x 0.
(39)
By noting that (t) is discrete, we can rewrite Cim for m E [k] as follows.
Cim = -
Σ
Fijm (Ai.j - B) 2x
(t)
Σ
Σ
Jip
(2)
Aig
(x)
jE(m]M{ (m)
-3 2
Σ
a jm
(0)
A 2 Σ
B 2x
Σ
Σ
ip
Ais
(E
jE(m][(
jE(m) pe (M(m)
(40)
=-3+2 2
Σ
Aij - Σ
3 2a
Σ
Σ
Aij
jESM (0)
JES (()
[m) (e)
= -
Σ
Ar, - 2m + 2,31 j E Sm)
20
Σ
Σ
Aij-
jES
(M( jESPM()
19

---

In the last equality we use -2 jem -2 3 m2 + 281 E Sm]. We note that com- puting the final expression in Eq. 40 n(k²n), due to the last term. However, by noting that Epe EjESp\(1 At,- = Ees Ais 2j (113 Aij we can derive the following.
Gi = + Σ
As, - 2/5m/ + 2/ E Sm]
20:
Σ
Σ
Ais
JESm ((i)
pé
pe|k|MMm |
JESpi
-
Σ
Arj 2/5m| +211 Sm] 2
Σ
A
Σ
Ais)
JESm ((3)
$45
JESM
(41)
- Σ
(As, + a...)) 25 + 201 E 5ml - 2a Ai,
Σ
JESm 163)
3480
-
Σ
Ars 2/ 231 Sm) -2a Σ
At,5
ME
Then, we note that 2 2Eees Ar, = 3.,=2Epp: Ejes, Ar, = =pE|1 Mi.p (sum of all similarities from object to all non-neutral objects) and that Ar, = 0 (by assumption). This proves the statement of the theorem. The expression in Eq. can be computed in (kn) since Epe(k) Ejes, Ac, is a constant w.r.t. different clusters m E [k], and can therefore be precomputed (see Alg. 3). may appear reasonable remove the term ΣpE[K] Ejes, Ai,-- since it is constant with respect to the cluster m E [k]. However, this invalid because neutral objects are allowed. Specifically, Cim < O for all m E [k), assigning object i to the neutral set is optimal, Go 0. The term Epe(a] Zjes, A must therefore be retained, as it affects whether an object is assigned to the neutral set.
Proposition Problem is equivalent to finding a clustering Syy that maximizes any one of the four objectives in Eqs. 1 11-14 (i.e., they share all local maxima).
N Intra
N
inter
(11)
-Nuua
N+ inter
(12)
N
intra
N mnrr
(13)
N Vinter
N
(14)
inter
Furthermore, maximizing any other combination of the four terms is not equivalent to Problem I.
Proof. We begin by defining the following quantities, which are constants w.r.t. different clustering solutions for the k-CC problem.
Csim =
Σ As.j.
(42)
(i,))
Cabs Σ
|Ai
(43)
(iJ)EE
The five objectives can be written as follows.
20

---

pfull = N
N
N
Not
Σ
E
Arj Σ
E
Ai
intra
intra
inter
inter
mE[k] KJESm
mElki pe p S JESP
MaxAggee
Nit + N inter
= Σ
Σ
A
Σ
E
Σ
An
mE [N] S.JESm
mET PE (m)))
icSm JESp
Σ
Σ
(AA A A
E
E
((4 A
mE(M] 1.jE8m
m mE/k] Pa MMm iESm JESp
Minniisugre
intra N
inter
Σ
Σ
Σ
4
AT,
Σ
Σ
A
mE(K) SJE....
mE(k PE (1)) iEs
jESp
2 Σ
Σ
(|Aisl
Ats) +
Σ
Σ
Σ
(1Aia) + At.))
2 m i.E8
2
mE (b] PE [m] im
JE8P
MaxCor
N Intra
Mirra
ΣΣ
Anj
mE/k/ A.ES
MinCC
N
N
Σ Σ
Σ
ArJ
inter
inter
mE/M
IES JESP
(44)
Given this, we observe the following connection between the objectives.
MaxAgree
Σ
Σ (|Ais) + A..)) - Σ Σ
Σ (IAr,5 - Ais)
mE({) i.jESm
mE(M
PE [m] iES
JE
1
الull
Cabs
2
MinDissgree
+ Cabs
(45)
MMaxCorr
1
MMinCur + Cabs
2
MaxxCorr
Csim + Cabs
2
2
1
--
+ 2
Csim
+ Cabs
2
The above establishes that they are equal up to constants. We prove the last statement of the proposition by counterexample. We consider the graph V = (1, with edge weights A1,2 +1, A2,3 +1, A1,3 = 11. The possible clustering solutions (partitions) are:
5(1) ((1,2,3)}
5(2) = [11,2), (3)).
5(3) ((1.3), (2)}. 5(4) = ((2,3), (1)). (( = {{1), (2). (3)).
In Table 2, we list all linear combinations of the terms N mura N mura? N - of the five clustering solutions. Expectedly (from the first part of the proposition), the five objectives pfill f fMaxAgree, /MinDisagree f Maaxorr MMnnCuu all produce the same ranking of these solutions. In contrast, every other combination of the terms ranks least solution differently compared to these five. This proves the last statement of the proposition.
inter evaluated on each
21

---

Table 2: All sums of Nitra: N
inrra inter N and their values on the five partitions 5(m), In parentheses we indicate the known name when the combination corresponds to one of the five standard correlation curctation-clustering objectives (or its negative).
inter
TDX
COMBINATION
S(1)
S(2)
S(3)
$
S
NIvTra
2
NINIHA
-1
0
-1
0
0
NINTER
4
NINTER
0
-1
-2
-1
-2
NIVIRA NINIRA (MMAXCORR)
0
6
NIVTRA + NINTA (f (MAAAGGEE)
2
2
0
2
1
NIVTRA NNTTA
-2
-2
8
NINTRA + NIVTER
-1
-1
1
1
NINTRA- N NINTER MINDISAGRIER
-3
-2
10
NIVTUR NuxTuu (-1 (MINCUT)
0
0
-2
0
-1
11
NITTRA NINIIA N NiNTIR
2
12 NETIA NINIAA NIvIu
0
-3
0
-2
13
NIVIAA + N MINN INTIE
-2
1
-1
14
NINIRA + NINTER NINTEE
-3
0
-1
15
NISTAA NINTRA NINTER
NETTER (FRLL)
1
-3
1
-1
Proposition 3. A clustering Spa) with neutral objects Su V UmETa) Sm that maximizes one of the objectives in Eq. Eqs. 11-14 not guaranteed to maximize any of the other objectives).
Proof. If an object transitions from neutral non-neutral, may introduce agreements (positive intra-cluster or negative inter-cluster similarities) and/or disagreements (negative intra-cluster or positive inter-cluster similarities). An exception objects with zero degree (zero similarity to all others), which can be assigned as neutral non-neutral without affecting any of the five objectives. Thus, we only consider non-zero degree objects in the remainder of the proof.
The max agreement objective (Fq. 11) considers only agreements. Making an object non-neutral either increases or maintains the objective but never decreases ensuring all objects become non- neutral. Conversely, the min disagreement objective (Eq. 12) considers only disagreements. Making an object non-neutral either decreases maintains the objective but never improves it, ensuring all objects remain neutral.
Now, consider clustering with i non-nonueee neutral clusters, where all intra-cluster similarities are +1 and all inter-cluster similarities are -1. If an unassigned object i V has similarity +1 to all others, the max correlation objective (Eq. 13) assigns it to the largest non-neutral cluster, while the minimum cut objective (Fq. 14) keeps it neutral. For >> 2, the full objective (Fq. 1) places i the largest non-neutral cluster if its size exceeds the of all others; otherwise, it remains neutral. Conversely, if object has similarity -1 to all others, max correlation keeps it neutral, whereas minimum cut assigns the smallest non-neutral cluster. For 2, the full objective may assign as neutral or non-neutral depending on cluster sizes.
Therefore, conclude that agreement and min disagreement differ fundamentally. always assigning all objects as non-neutral or neutral, respectively. Furthermore, from the two counterexam- ples above, max correlation, minimum cut, and the full objective not equivalent and none of them guarantee that all objects are either neutral or non-neutral in all cases (meaning they are all different from max agreement and min disagreement in general).
For & = 2. the full objective always increases (or remains constant) when an object is made non- neutral, aligning it with max agreement. To this, consider clustering with non-neutral clusters, and let Mim. = Ejes.. A be the total similarity of object to cluster m. The impact on the objective when assigning to m is Msm Mrps where the other cluster. Since this difference is always positive when is placed in its most similar cluster, assigning as non-neutral
Unless & = 2, in which case Eq. and Eq. are equivalent established [6].
22

---

always improves the objective. Then, since all objects are non-neutral, the problem is equivalent to the k-CC problem where we know max agreement and the full objective are equivalent (from Prop. 2). For k: >> 2, this reasoning no longer holds, as contributions from other clusters can outweigh the within-cluster similarity to the most similar cluster (i.e., making the total contribution negative), potentially making neutrality optimal. However, we note that in our final objective (Eq. 3), when and B are involved, all terms will contribute with unique information even for k = 2.
C Impact of a and B
In this section, we analyze the impact of a and /3 in Eq. 3. In Appendix G.8 we investigate their impact experimentally. We begin by stating the following proposition.
Proposition 4. (a) There exists a & < O such that for any 3 S E1, there is a clustering solution assigned to single non-neutral cluster. (b) Conversely,
maximizing Eq. 3 where all the objects
there exists a &2 > O such that for any B 2 Ez, there is a clustering solution maximizing Eq. 3 where all the objects neutral.
Proof. By examining the gradient in Eq. 9, we observe that the dominant term involving / is -35mm Consequently, making 3 large and negative increases the incentive to assign objects non-neutral clusters. Moreover, since Sm. scales with cluster size, the local search procedure will favor placing an object in the largest non-neutral cluster. If [ is sufficiently large and negative, this term will completely dominate the objective, ensuring that no object is assigned to the neutral set (as the contribution to all non-neutral clusters remains positive). Ultimately, all objects will be placed in the largest non neutral cluster.
Similarly, if / is made very large and positive, - Sm will eventually dominate the objective, making the contribution to every non-neutral cluster negative for all objects. As a result, all objects will be assigned to the neutral set.
From Prop. 4, we understand the extreme cases of 3: (a) a small negative 3 results in a maximally imbalanced non-neutral clustering (i.e., all objects in one non-neutral cluster), while (b) a large positive 3 makes all objects neutral. For intermediate 3 E E2), we analyze the gradient in Eq. each cluster term -23] scales with cluster size, larger clusters become less favorable, promoting balance. If 3 is large enough, it forces Gt.m < for all m [k]. making neutrality optimal for object i. Note that this is more likely for low-degree objects, implying that high-degree objects (with clear cluster assignment) are more likely to remain nen-ral, resulting dense non-neutral clusters. Consequently, increasing 3 leads to smaller (i.e., more neutral objects) and denser non-neutral clusters, while maintaining balanced, as desired.
9. Increasing 3 strictly reduces the contribution of object
[K]. but since the
The parameter a has been studied in prior work [12, 44). From Eq. 3, a balances maximizing intra- similarities and minimizing inter-similarities, which translates to trade-off between cohesion within clusters and separation between them. A heuristic choice of a = 1/(A: 1) was proposed in [44], based on the observation that the number of intra-similarities scale linearly with k, while the number of inter-similarities grow quadratically. This choice prevents inter-similarities from dominating the objective. Finally, the term -ad; indicates that a influences whether object becomes neutral, underscoring the need to account for inter similaiiilssssies in the objective (as suggested in Section 2.2).
D Limitations of Polarity
To illustrate the limitation of polarity (Eq 2), we refer to Example 2 from [21], which considers signed graph with 12 objects: (A, B, D, E, F, G, H, I, J, L,K. The sign of each similarity can be found in Figure 3 of [21]. The study evaluates the following three clustering solutions:
-() = { B, C. D). (E,
S() = {[A, B. C. F.,F, H, LJ]
.
8(3) = (0, (E.F. G.
23

---

The polarity values for these solutions are: Polarity(S(1) = (20 + 10)/8 = 3.75, Polarity(S(3)) (38 + 6)/12 = 3.67, and Polarity ( )- = (30 + 08/8- 3.75.
Although ((1) and 5K3) achieve the same polarity score, s(1) is significantly more balanced, making it the more reasonable choice. In contrast, evaluating our objective (Eq. 3) for the same solutions,
we obtain ((1) (20 + 10) (42 + 42) 2, ((2) (38 6) (4 + 82) -36, and S(3)
(30 + 0) - 8 34.
Our objective function still identifies 5(2) the worst solution (consistent with polarity), but strongly favors 5(1) over 5(3) due its better balance. Here, assume 1/(k- 1) (which is 1 since k = 2) for consistency with polarity, and B ==
E Motivation for Discovering Balanced Communities
From an optimization perspective, the graph-clustering literature recognizes that objectives that simply maximize intra-cluster similarity or minimize inter-cluster similarity often degenerate into trivial solutions in which all objects are assigned to a single (or very few) clusters. A classic instance the minimum cut, which minimizes inter-cluster similarity yet exhibits this pathology on both signed and unsigned graphs. The usual remedy is to normalize the objective by quantity that reflects cluster size or degree, giving rise to alternative measures such as the (signed) ratio cut and the normalized cut [11, 10]. Crucially, such normalization can yield solutions whose value with respect to the unnormalized criterion is worse, while better coinciding with the true underlying clusters. In this work tackle analogous limitation in the context of PCD, where neutral objects are permitted.
We next motivate- motovate-throughh few illustrative examples- why clusterings that are more balanced in size are frequently better aligned with ground-truth clusterings observed in real-world settings.
As discussed in [21], many social environments- online forums and political systems to scientific institutions-cal benefit from balanced community structures in signed networks. Such balance helps ensure that diverse viewpoints or specializations are sufficiently represented and reduces the chance that one perspective overwhelmingly dominates. This, in turn, promotes constructive debate, encourages critical thinking, and helps broaden individuals' perspectives-ulimaatee limiting echo chambers and mitigating the spread of misinformation. Below, we provide few concrete examples.
In market research and product development, balanced communities can provide deeper insights into consumer preferences. By identifying groups of comparable size (rather than one massive consumer segment overshadowing niche but meaningful ones), organizations can more effectively tailor products or marketing strategies each community, thereby predicting market trends more accurately.
Academic Research Networks can also profit from balanced structures. Imagine a signed network in a university, where positive edges link researchers working on similar topics (e.g.. physics, computer science, mathematics), and negative edge edges indicate differing research domains. Because universities aim to cover a broad range of subjects each with enough faculty to maintain healthy research output-a balanced partition of the signed network (i.e., each discipline having a solid, negligibee presence) offers better representation of the university's diverse pursuits. In such a setting, neutral nodes might be faculty primarily engaged in administrative roles or other staff members not actively involved in research.
Another example is social networks where communities are formed around specific interests or activities (c.g., online book clubs, gaming groups). These communities grow naturally to a size where interaction remains high, and members can still engage meaningfully with each other, without the network becoming too large or fragmented, i.e., the size of the group grows until it reaches a point where communication remains efficient and personal connections preserved. As the group grows beyond a certain size, it may split into smaller subgroups, keeping the communities balanced in size.
In all these scenarios, balanced community detection ensures that no single faction's 's needs or views go unnoticed. This inclusivity promotes more representative outcomes, strengthens consensus- -uillingg. and leads to more robust decisions or insights.
24

---

F Comparison with y-polarity Objective from [21]
The 7-polarity objective introduced in [21] is defined specifically for the case of clusters. In this setting, we have only two non-neutral groups: S1 and S2. Let Sma = max([S1), [S2)] and
Smin (i. The y-polarity is then defined as
N intra
N intra
+ Vinter N
inter
(46)
(8mxx
Smin) > + 28min
This formulation is similar to the polarity objective in Eq. 2, which instead uses the denominator [So] + |S Like polarity, ?-polarity penalizes large or imbalanced clusters through a normalization term related to cluster sizes. However, the specific form of the denominator in Eq. 46 additionally enforces balance between S1 and S2.
In contrast, objective promotes balanced clustering through additive regularization term which supports an arbitrary number of clusters A key advantage of additive regularization is its simplicity: it effectively corresponds to shifting intra-cluster similarities by -3 (see Prop. 1). This straightforward modification enables us to establish a linear convergence rate (Thm. 3) and significantly improves computational efficiency (see Section 3.4). In comparison, obtaining similar theoretical guarantees and efficiency via local search on polarity-based objectives, including 7-polarity, is likely infeasible substantially more complex.
In summary, our objective facilitates the derivation of local search algorithm for the PCD problem that scales efficiently to large graphs.
G Experiments: More Details and Further Results
All experiments were conducted locally on a single machine with an Intel Core i9- 10850k CPU and 64 GB of RAM.
G.1 Datasets
Following [44], we consider the following widely studied real-world signed networks. WoW-EPS (W8) [25] represents interactions among authors in the 8th EU Parliament legislature, where edge signs indicate collaboration or competition. Bitcoin (BTC) [31] is trust-distrust network of users trading on the Bitcoin OTC platform. WikiVot (WikiV) [31] records positive and negative votes for Wikipedia admin elections. Referendum (REF) [30] captures tweets about the 2016 Italian constitutional referendum, with edge signs indicating whether users share the same stance. Slashdot (SD) [31] friend-foe network from the Slashdot Zoo feature. WikiCon (WikiC) [26] tracks positive and negative interactions between users editing English Wikipedia. Epinions (EP) [31] represents the trust-distrust relationships in the Epinions online social network. WikiPol (WikiP) [33] captures interactions among users editing Wikipedia pages political topics.
G.2 Baselines
For SCG, we use the public implementation from [40]. For KOCG, we use the public implementation from [32] with default hyperparameters:
1/(k - 1), 3 50 (note that the purpose of this B differs from the one used our paper), and 5000. For the spectral methods SPONGE and BNC,
we use the public implementations from [37]. Following [44], for SPONGE, we evaluate both the unnormalized and symmetric normalized versions and report results for the best-performing method. For N2PC [21], we default parameters for training their framework (based GNN). We use the public implementation provided by the authors.
G.3 Description of Synthetic Datasets
We employ the modified signed stochastic block model (m-SSBM), which was specifically designed to generated synthetic graphs with planted ground-truth communities for PCD. The m-SSBM model is parameterized by four variables: (i) the total number of nodes; (ii) k the number of nen-rrutral clusters; (iii) E, the size of each non-neutral cluster; and (iv) 1) E [0, 1]. which controls the edge probabilities. Edges within the same cluster are positive with probability 1 7, and negative absent
25

---

km2.1- 1- 100, 0 1000
A=4.1- 100,
2000
6m - 100,
2000
K
10, 1 10000000000 /1 4000
1.0
1.0
1.0
1.0
0.8
F1 21.Scor
0.8
S.crrre
Scaare
0.8
Scare
0.6
0.6
0.6
0.6
0.4
0.2
Imbalance
Imbalance
Imbalance
Imbalance
60
80
80
Polarty
40-
P0anty
60
Polanty
Polanity
60
60
20
40
20
20
20
Imbalance P
Imbalance
Imbalance
Imbalance P
Ground Truth BNC-K
(ours)
SCG-MA
SCG-MO
BNC-(K
SPONGE-(K+3]
SPONGE-K
N2PC
Figure 3: Fl-score and polarity of different methods on synthetic graphs generated using the m- M-SSBM model, as the size ratio parameter p varies. A larger value of p means the ground tround-truth non-neutral clusters are more imbalanced. The noise level is fixed to 0.4.
with probability 2/2. Conversely, edges between different clusters are negative with probability 1 1), and positive absent with probability n/2. All other edges are positive negative with equal probability min(1, 1/2).
Smaller values of correspond to denser non-neutral clusters and lower levels of noise. In other words, y controls both sparsity of the graph and noise (i.e., flipping sign of edge weights).
G.4 Results on Synthetic Datasets with Imbalanced Clusters
We now evaluate the performance of different methods on synthetic data with imbalanced cluster sizes. We use the same m- SSBM model described in the main text (and previous subsection). To control the degree of imbalance among the k planted groups, we follow the approach of [23] and introduce a group size ratio parameter p 1. When p = 1, each group has the same size f, resulting in balanced partition. For p > 1, the group sizes follow geometric progression: the smallest group has size the next has size s p 1/(k-1), and so on, such that the largest group is s p. This construction ensures that the ratio between the largest and smallest group sizes exactly p. while the total number of non-neute non-neutral nodes remains approximately kê. Any remaining nodes (i.e., when i= (C,)) are assigned neutral nodes, and their edges sampled from neutral distribution. In short, a larger value of means more imbalanced ground-trui truth non-neutral clusters.
The results are presented in Figure 3. The noise level is fixed to r = 0.4. We observe that our method remains robust as the cluster size imbalance increases, while the performance of baseline methods deteriorates more rapidly. This suggests that our approach does not rely on strict balance assumptions and is capable of effectively recovering imbalanced ground-truth clusterings.
G.5 Runtime Comparison on Large Scale Synthetic Data
To further highlight the scalability of our approach, we present additional experiments on large synthetic datasets generated using the m-SSBM model described in the paper, containing up to 250,000 objects and 150 million edges with non-zero edge weight. Our method is capable of handling even larger datasets; the only constraint was the memory required to store the matrix of pairwise relations on the machine used for our experiments, limitation that could be easily overcome by using machines with larger memory capacities. We compare LSPCD with the strongest baseline, SCG with min-angle rounding (SCG-MA), and report the F1 F1-score (ground-truth cluster recovery) and runtime in seconds. Other baselines yield lower Fl FI-scores, and most are also slower in runtime. We fix 7 0.45, k 6 and 500.
26

---

Number of edge weights ([E))
Number of non-zero edge weights ([E))
9M
17M
28M
42M
6OM
100M
150M
9M
17M
28M
42M
60M
100M
150M
2000
Runtime (seconds)
1500
F1-Score
1000
0.90
0.85
0
125K 150K
50K
75K
150K Number of objects (n)
Number of objects (n)
LSPCD (ours)
SCG-MA
Figure 4: Runtime comparison large-scale synthetic datasets generated using the m-SSBM model. LSPCD consistently achieves higher Fl-scores than SCG-MA while requiring less runtime, demonstrating superior scalability and efficiency. We fixed rj 0.45, k and & 500.
Table 3: The imbalance factor (IF) for three different values of { 1, 1,3,4 4.
REP
SD
WikiC
EP
Wiki1
Method
C=1
<=3
<=4
[=1
<=3
<=
[=1
C=3
<=
{=1
<=3
(=1
C=3
C=44
LSPCD (ours)
0.78
0.66
0.50
0.22
0.87
0.27
SCG-MA
0.05
0.02
0.01
0.06
0.02
0.01
0.77
0.62
0.48
0.13
0.05
0.04
0.06
0.02
0.01
SCG-MO
0.02
0.01
0.04
0.01
0.01
0.69
0.51
0.39
0.13
0.05
0.01
0.01
SCG-B
0.11
0.04
0.03
0.15
0.06
0.04
0.84
0.72
0.59
0.14
0.06
0.04
0.13
0.05
0.04
LSPCD (ours)
0.58
0.46
0.38
0.74
0.61
0.50
0.81
0.65
0.54
0.55
0.34
0.24
SCG-MA
0.75
0.71
0.66
0.51
0.31
0.22
0.18
0.08
0.05
0,50
0.36
0.27
0.64
0.55
0.49
SCG-MO
0.72
0.68
0.41
0,25
0.17
0.50
0.30
0.21
0.46
0.35
0.28
SCG-B
0.00
0.00
0.00
0.55
0.43
0.35
0.95
0.90
0.82
0.68
0.60
0.51
0.34
0,25
0.19
LSPCD (ours)
0.49
0.37
0.31
0.66
0.50
0.40
0.80
0.62
0.48
0.61
0.49
SCG-MA
0.71
0.66
0.60
0.35
0.21
0.15
0.22
0.09
0.06
0.63
0.55
0.50
0.53
0.45
0.40
SCG-MO
0.74
0.71
0.56
0.37
0.26
0.50
0.28
0.36
0.27
SCG-B
0.00
0.00
0.00
0.45
0.36
0.29
0.83
0.76
0.67
0.53
0.46
0.39
0.26
0.19
0.14
The results are shown in Figure 4. Our method consistently outperforms SCG terms of Fl score while also being more efficient, demonstrating its ability to scale to larger graphs.
G.6 Impact of & on Imbalance Factor
Evaluating unsupervised learning methods the absence of ground truth is inherently challenging. and there is often no universally or uniquely accepted metric or criterion. As a result, it is common practice to report multiple metrics, each reflecting different objective or perspective. for real-world datasets, we report both polarity and imbalance factor. As shown in our extensive experiments, our method is the only one that consistently performs well w.r.t. both metrics across various datasets.
this study,
Given the difficulty of evaluation in such settings, no single fixed value of & can be considered optimal. In the absence of prior preference, a reasonable approach is to examine multiple values of & and analyze how different methods perform under each. We experimented with a range of values and found that the conclusions remain stable. As mentioned in the main paper, we chose & = 3 since it provides a sharper distinction between solutions with different degrees of balance, compared to E == 1, which would have been the natural choice otherwise as it corresponds to Shannon entropy. To further demonstrate robustness, we now also report results for = 1,3, 4 for a subset of methods (see Table 3). Across all tested values, the relative ranking of methods remains consistent, and our conclusions are unchanged (again when SCG is more balanced, usually yields low polarity). Results consistent for even larger values of E.
27

---

G.7 Aspects to Assess Solution Quality
Below, we present 11 evaluation criteria used our experiments on on how the clustering solutions generated by each method differ. In the context of PCD (where ground-truti solutions are not available), evaluating clustering quality is inherently subjective: each aspect listed below highlights distinct facet of the solution. Generally, there is trade-off among these aspects, and the objective to achieve good balance between them. Below, we define the aspects used in our analysis. We have defined these aspects such that larger number is better (apart from runtime).
data shed light
Let N = Eme(y |Sml denote the number of non-neutral objects, and let Noz intra + N intra
Niner + N represent the number of non-zero similarities between non-neutral objects.
SIZE The total number of non-neutral objects.
IF: The imbalance factor introduced in the main text.
POL: Polarity, as defined in the main paper (Eq. 2).
K: The number of non-empty non-neutral clusters.
MAC: Mean Average Cohesion, quantifying the density of positive intra-cluster similarities, defined
MAC =
Σ mEi
Σ
At.
Sm K
LJES...
Its range is [0, 1], where higher values indicate stronger cohesion within clusters.
MAO: Mean Average Opposition, measuring the density of negative inter-cluster similarities, defined
MAO
E
AT.
l:k
MEI A
tESm
PE[A] [m))
JES,
Its range is [0, 1], where higher values indicate stronger opposition between clusters.
CC+: Measures the fraction of intra-cluster similarities that positive minus those that negative, defined as
N
CC+
intra
inrr
N
intra
N intra
Its range 11, where indicates that all non-zero intra-cluster similarities are negative, and +1 indicates that all are positive.
CC-: Measures the fraction of inter-cluster similarities that are negative minus those that are positive, defined as
N
N+
CC-
inter
inter
N
N
inter
inter
range [-1, where indicates that all non-zero inter-cluster similarities are positive, and +1 indicates that all are negative.
DENS: The proportion of non-zero similarities among non-neutral objects, defined as
N
DENS
N(N -1)
Its range is [0, 1], with higher values indicating denser connectivity.
ISO: Isolation, measuring the separation between non-neutral and neutral objects, defined as
N
ISO
N
Eies, Ejes, |
Its range is 10, 1). where ISD 1 means non-neutral objects are fully isolated from neutral ones, meaning non-zero edges exist between them (which is ideal).
TIME (s): Runtime of the corresponding method in seconds.
28

---

60
0.8
40
Polarity
Imbalance
30
0.4
10
0.2
B
LSPCD
SCG-MA
SCG-MO KOCG-top-r
SCG-B
SCG-R
KOCG-top-1
Figure 5: Impact of on the WikiPol dataset with = 6.
0.25
0.35
0.30
0.20
0.25
0.35
0.20
0.15
0.05
0.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00
3.05
0.10
0.20
0.25
0.30
3.40
B
proportion
MAO 1522 MAI
Size S.SPCD)
proportion (SC2
(LSPCD)
Balance 1SC0 HAL
(a) Epinions, k = 2, 8 -.1
(b) Wikipol, k = 6, a=
Figure 6: Investigation of the impact of a and B for I.SCDD (Alg. 3).
G.8
Varying a and B
Figure 5 shows the effect of varying B. Very small or large 3 values lead to poorer polarity, they produce clustering solutions with too many or too few non-neutral objects, respectively, contrast, intermediate 3 values consistently yields competitive polarity with the best performing methods, while being more balanced.
In Figure 6, we illustrate the impact of varying a and B. According to Figure 6a, increasing naturally balances intra-cluster cohesion and inter-cluster opposition. The size proportion, defined as the fraction of non-neutral objects in V, remains constant varies. Figure 6b shows that increasing monotonically reduces the number of non-neutral objects, leading denser clusters, as indicated by improved MAC and MAO scores. Notably, balance remains stable across different 8 values, unlike the baseline SCG-MA.
G.9 Results on Real- World Datasets
Tables 4-11 present detailed analyses for all datasets. See Appendix G.7 for description of the 11 aspects reported. Firstly, we observe that our method exhibits low standard deviation, indicating ro- bustness to the initial random solution. It consistently finds high-polarity solutions while maintaining better balance than its main competitor, SCG. Unlike some baselines such as KOCG and SPONGE, method does not enforce excessive balance, ensuring solutions remain both high in polarity and reasonably balanced.
In terms of runtime, our method is efficient and competitive with the baselines. It is also consistently ranked among the best both DENS and ISO. Unlike SCG, our method always identifies non-empty non-ncutral clusters, which we argue is significant limitation of SCG.

---

While SCG generally achieves higher MAC values, this is largely due to its tendency to produce highly imbalanced solutions, often with singleton clusters. Since small or singleton clusters trivially yield high average cohesion (values close to 1), they can disproportionately inflate the overall MAC score.
Finally, our method performs comparably or better than SCG in CC+ and significantly outperforms it in CC- in most cases. This highlights another limitation of SCG: often includes more positive similarities between clusters than negative ones, as reflected by negative CC- values. Some baselines produce either overly large or overly small non-neutral clusters (based on SIZE), whereas our method consistently finds solutions with reasonable number of non-neutral objects (which consequently leads a good balance of the other aspects), similar to SCG. However, we that we can easily adjust the number of non-neutral objects by adjusting B. as discussed in the paper.
Table 4: Detailed results for the WoW-EP8 dataset. LSPCD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
(x)
LSPCI
586
223.406
0.509
0.769
LSPCD (STD)
8.0
0.0
0.0
0.034
NYPC 1)
527
0.0
136.626
0.519
0.0
0.765
0.0
0.588
0.721
26.916
N2PC (v 1.2)
519
0.004
543
2
0.763
0.151
0.77
1.0
0.593
0.709
28.426
NYPC 1.7)
609
0.767
0.73
N2PC (7 2.0)
571
0,235
117.398
2
0.27
0.082
0.769
0. 0.48
0,504
0.726
26. 603
SCG-MA
527
0.0
236 55
0,52
0.762
0.0
0.59
0.725
1.225
SCG-MO
592
SCG-B
583
0.049
200.604
0.274
094
0.697
-0.369
0.514
0.767
4,657
SCG-R
513
0.03
114.616
0.272
0. 104
0.761
0.451
0.552
0.654
0.517
KOCG-TOP1
16
0.967
13.0
O 986
889
0.965
0.778
1.0
0.019
BNC-(R
-0.667
-1.0
0.333
BNC-À
790
0.005
184.63
2
0.152
0.049
0.628
1.0
0.372
1.0
0.537
SPONGE-(A
375
0.425
87,957
0.204
0.095
0.738
0.318
0.343
0.346
0,581
SPONGE-E
LSPCD
218.458
0.772
0.142
0.001
SCG-MA
599
0.138
205. 137
0.58
0.13
0.762
-0.32
0.527
0.822
1.198
SCG-MO
568
0,102
213.211
0.827
0.141
0.77
-0.349
0.55
0.776
1.176
211.561
056
0.762
KOCG-TOP-1
31
0.962
9.054
0.962
66668
0.944
0.339
0.978
0.039
KOCG-TOP-T
599
0.987
7,395
0.436
0. 099
0.692
-0.618
0.516
8.806
ANC-(K
SPONGE- (A-OBE---E
485
0.929
53.823
0.448
0.06
0.886
-0.53
0.33
0.433
0.593
SPONGE-E
790
0.869
71,162
0.383
0.08
0.803
-0.499
0.372
1.0
0.61
LSPCD (AVG)
591
0.075
217.344
0.142
0.071
0.761
0.414
0,505
0.773
0.269
LSPCD
0.142
0.006
0.001
SCG-MA
299
0.785
0.763
0.819
SCG-MO
591
0.112
205, 796
0.756
0.171
0.77
-0.321
0.534
0.811
1.378
SCG-B
615
1.O
211.661
0.421
0.0
0.693
0.0
0.498
0.822
7,512
SCG-R
744
0.978
42
7,905
KOCG-TOP-P
598
0.976
9.109
6
0.472
0.095
0.73
-0.637
0.523
0.812
BNC-(K-4
10
0.359
-0.2
0.5
0.0
-1.0
0.01
0.012
0.002
0.977
BNC-A
790
185.198
1.0
(RONGE
572
47.762
0.537
0.893
-0.511
0.536
SPONGE-K
790
0.878
$7.868
0.53
0.075
0.834
-0.539
0.372
1.0
0.599
30

---

Table 5: Detailed results for the Bitcoin dataset. LSPCD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
(e)
29.022
0.969
2,203
(SI)
0.003
8.001
NIPC (r 1)
134
0.016
29.642
0.617
0.195
0. 9.9
0.733
0.246
0.184
11.318
NIPC 1.2)
164
0.46
30.146
0.238
0.141
0.91
0.964
0.201
0.222
12.26
(T
N3PC ( 1.7)
23,857
0.255
0.452
0.876
0.136
N2PC (T 2.0)
68
1.0
24.147
0.258
0.478
0.871
0.993
0.38
0.139
12,834
SCG-ME
179
0,163
28.838
0.298
0,068
0.906
0.873
0.179
0.216
0.122
SCG-MD
0.184
0.201
SCG-R
842
0,249
14.24
0.022
0.009
0. 8.908
0.812
0.019
0.394
L.024
KOCG-T9P-1
1.0
1.0
1.0
1.0
0.0
1.0
1.0
0.004
KOCG-TOP-
BNC-IK +
-10.76
0.0
-0,316
0.0
0.425
0.581
0.341
BNC-E
5881
0.017
5.268
B 050
0.001
0.721
0.604
0.001
1.0
0.203
SPONGE
0,792
1.0
0.667
L.0
0.0
0.2
1.0
1.116
SPONGE-k
0.256
SCG-MA
176
0.225
25.121
D. 4R88
0.07
0.914
-0.44
0.1
0.2
0.302
SCG-MO
180
0.218
25,252
D 487
0.07
0.91
-0.411
169
0.205
0.348
SCG-R
8.033
0.92
627
0.033
0.238
KOCG-TOP-1
26
0.905
8.41
0.859
0.621
1.0
0.653
0.738
0.112
KOCG-RUPe
176
0.931
5.034
0.136
0.041
0.556
-0.246
0.113
0.157
BNC-IR
0.029
0.721
0.001
0.178
SPONGE-(K 1]
71
0.096
1.099
0.754
0.0
L.0
0.0
0.016
0.443
3.364
SPONGE-E
5881
0.001
5.092
0.75
0.0
0.697
0.0
0.001
1.0
2.797
LSPCD (ANG)
194
0.494
20.031
0.251
0.143
0.948
0.646
0.155
0.231
2.73
0.046
SCG-MD
412
0.464
15,165
0.571
0.028
0.929
-0.337
0.058
0.3
0.477
SCG-B
326
0.472
9.321
0.313
0.009
0.866
-0.421
0.053
0.222
10.509
0.006
0.367
XOCG-TOP-1
0.867
KOCG-TOP-T
430
0.867
3.601
0.077
0.013
0.88
.0.405
0.043
1126
BNC-(K +-1
224
0.255
.4.239
0.075
0.001
-0.622
0.958
0.033
0.394
0.286
BNC-A
SPONGE-
1.252
SPONGE-K
5881
0.00S
S.085
0. 0.563
0.0
0.696
-1.0
0.001
1.0
2,473
31

---

Table 6: Detailed results for the Wik dataset. LSPCD (avg) and L.PCCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
1278
0.428
62.322
0.038
0.015
2.457
(STD)
0.002
0.0
0.276
N2PC ( = 1)
712
0.0
71.63 635
0.11
0.0
0.852
0.0
0.118
3.999
24.313
N2PC ( 1.2)
759
0.006
71 663
0.052
0.093
0. 0.847
0.785
0.112
0.418
24.251
N2PC ( 1-7)
0.562
0.056
0.017
0.685
0.077
424
N2PC ( 2.0)
1190
1.0
509
0.064
0.012
0. 849
0.651
0.042
O. 395
$9.069
SCG-MA
0.008
71.476
0.048
0.079
0.671
0.104
0.436
1.537
1.432
57.589
0.776
7,501
SCG-R
1100
0. 1.4
$4,693
0.032
0.013
0.83
0,618
0.061
0.644
0,781
KOCG-TOP-
10
0.717
7.6
0.905
0.857
1.0
1.0
0.844
0.012
0.022
BNC- 1)
0.792
-1.111
0.0
-1.0
0.0
0.139
1.0
0.721
RNC-E
7115
0.003
15.794
0.002
0.0
0.558
0.0
0.004
1.0
0.49
SPONGE-(R
0.472
1.0
0,571
0.0
1.0
0.111
1.602
0,977
0.519
0.073
-0.045
4,381
(STD)
0.229
1.69
SCG-MA
1142
0.361
$2.945
0.08
0.018
0. 8-49
-0.618
0.069
506
2.042
SCG-MO
1050
0.374
$3.07
0.089
0.022
0.858
-0.692
0.073
0.474
1.986
SCG-8
0.437
0.031
0.008
0.813
-0.68
0.043
0.549
3.074
KOCG-TO8-1
0.811
4.525
0.845
0.086
0.933
-0.609
0.576
0.03
KOCG-IDI-
1142
0.99
3.288
0.055
0.011
0.719
-0.618
0.059
0.44
BNC-(R
0.001
0.0
0.558
0.533
SPONGE-(K + 1)
12
0:712
1.0
0.8
0.0
L.0
0.0
0.091
1.0
2.327
SPONGE-K
7115
0.003
15.794
0.156
0.0
0.558
0.0
0.004
1.0
1,522
6
LSPCD (AVG)
534
0.563
46.179
0.143
0.029
0.896
-0.314
0.133
0. 2828
5.292
LSPCD
0.002
0.421
2:24
SCG-MO
1226
0.409
47.013
0.073
0.024
859
-0.683
0.063
0.526
2.178
SCG-B
941
D.605
23.332
0.121
0.018
0:78
-0.735
0.D65
0.369
29.072
SCG-R
3.475
KOCG-IDI-1
0.963
0.227
KOCG--DP--
1355
0.962
3.132
0.051
0.009
0.73
-0.62
0.05
0.506
BNC-(R +
13
0.974
-1,077
0.0
0.0
-1.0
0.0
0.09
1.0
0.966
BNC-K
0.546
SPONGE-
0.859
1.0
SPONGE-k
7115
0.003
15. 794
0.434
0.0
0.558
0.0
0.004
1.0
1.66
32

---

Table 7: Detailed results for the Referendum dataset. LSPCD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
MAC
CC
190
(s)
LSPCD (AYG)
915
0.71
146. 109
0.279
0.014
1.0
0.114
0.17
0.353
3,376
L.SPDD
0.001
(Y 1)
173.604
0.297
0.573
N2PC (7 1.2)
651
0.02
173.654
0.401
0.254
1.0
0.571
0.27
0.343
665
N2PC 1.5)
918
0,944
130.261
0.253
0.011
1.0
0.24
0.149
0.331
304
(2 = 2.0)
992
1,0
118.099 099
0.236
0.009
1.0
0.169
0.126
0.327
SCG-MA
824
0.015
172.206
0.455
0.247
1.0
0.558
0.211
0.409
1,863
ECG-MO
673
0.013
174.083
0.546
0.3
1.0
0.571
0.261
0.352
1,108
1550
1.0
0.579
0.079
0.492
KOCG 1
15
0.637
11.6
0.973
0.659
1.0
1.0
0.829
0.007
KOCG-TOP-r
824
0,961
15.425
0.057
0.018
0.705
-0.317
0.065
169
BNC-(R
0.286
BNC-
10884
0.0
41,495
0.002
0.0
0,898
-1.0
0.004
L.0
1.114
SPONGE-(K (k++
0.792
1.0
0.667
0.0
1.0
0.0
0.2
L.0
6.754
SPONGE-K
10884
41.495
0.502
0.898
0.004
1.0
6.889
LSPCD (AVE)
1065
0,412
139,163
0.196
0.043
1.0
0.056
0.145
0.394
3,734
SOG-MA
1713
0.048
1.0
0.081
SCG-MO
1658
0.69%
$2.139
0.142
0.054
1.0
-0.767
D.084
D. 0.502
3,863
SCG-B
1142
116.233
0.102
0.0
1.0
0.0
102
39399
60.02
0.174
0.479
KOCG-TOP-1
0.648
14,956
0.83
0.297
1.0
-0.363
0.615
0.024
KOCG-TOP-P
1713
0.87
3,711
0.065
0.003
O 188
862
0.052
363
BNC-(R
1.0
-1.0
0.0
0.0
-1.0
0.0
0.143
0.25
1,125
(PONGE
0.792
0.0
1.0
0.0
0.059
1.0
SPONGE-E
10884
0.002
41.495
0.156
0.0
0.898
0.0
0.004
1.0
6.327
LSPCD (AVG)
1021
0.329
137.627
0.176
0.028
1.0
0.04
0.15
0.579
5,461
LSPCD (STD)
0.001
0,131
0.001
0.0
0,0
0.001
0.0
0.0
2,813
SOG-MA
1945
0.107
SOG-MO
0.629
SCG-B
1142
0.0
116:253
0.102
0.0
1.0
0.0
0.102
D. 398
98. 669
SCG-R
1660
0.359
50..58
0.08
0.038
0.986
-0,756
0.052
D. D.355
5.075
KOCG-TOP-1
1945
0.917
BNC-(R + 1)
12
0.938
-0.833
0.222
0.0
-0.714
0.0
0.106
0.25
1,923
BNC-
10884
0.001
41,495
0.056
0.0
0.898
-0.2
0.004
1.0
1,155
SPONGE-
11.664
0.501
0.898
1.0
Table 8: Detailed results for the Slashdot dataset. LSPCD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
S12E
POL
K
MAC
MAO
CC+
CC-
DINS
150
TIME
(e)
(AVG)
235
0.207
0.969
0.167
LSPCD (STD)
0
0.004
0.095
0
0.0
0.0011
0.0
0.003
0.001
0.0
3.151
NIPC 1)
205
$1.259
0.403
0.979
0.0
0.407
0.165
156.653
205
154.593
NIPC 1.5)
191
81.77
N2PC ( 1-7)
342
0.996
55.041
2
0:297
0.026
0.969
0.677
0.17L
D. 0.5
219.00 069
N3PC 2.0)
404
$2,069
0. 0.2488
0.019
0.97
0.64
0.137
0.18
3.4 945
SCG-MO
234
0.009
79,692
0.674
137
0.973
0.882
0.352
0.145
2.654
SCG-R
280
0.045
60 962
D. 0.145
0.055
0.9%
-0,005
0.221
0.205
287.233
SCG-R
3033
0.075
29,706
0.007
0.007
0.872
0.635
0,011
0.216
25.778
KOCG-TOP-1
KOCG-TOP-
307
0.028
0.159
0.037
(AVG)
0.212
0.087
0.966
0.189
37.751
L.SCCD (STD)
2
0.005
0.351
0
0.01
0.003
0.0
0.004
0.003
0.001
3.01.
SEG-MA
2552
0.246
35.53
1.9
0.012
0.862
-0.431
0.026
B.269
16.032
SCG-MO
410
48.306
0.287
0.973
-0,491
0.128
0.199
SCG-R
3853
0.762
10.749
0.01
0.002
0.877
-0.34
0.008
0:227
27. 27.254
KOCG-TTP-1
25
0.305
2.609
0.453
0.172
1.0
0.643
0.206
[.009
2552
L.PCD
272
0.306
0.982
0.423
0.251
0.156
64.95
(SID)
2.428
0.001
0.014
SCG-MA
2343
0.171
37.849
0.35
0.026
0.368
-0.701
0.028
0.256
32.081
SCG-MO
2504
0.293
34,649)
0.212
0.063
0.876
-0.421
0.026
B.265
26.278
SCG-B
420
0.254
1408,
0.433
KOCG-TOP-1
48
0.899
3.588
0.65
0.0779
0.978
-0.166
0.216
0.016
KOCG-TUP-2
2343
0.911
3.28
0.021
0.003
0.222
-0.54
0.014
0.164
33

---

Table 9: Detailed results for the WikiCon dataset. LSPCD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
S12E
IF
FCL
X
XAC
N60
CC+
0C
DENS
190
TIME (s)
LSPCD (AVG)
1876
0.825
190.8
2
0.055
0.128
0.871
0.997
0.108
0.242
72.368
LSPCD (STD)
0.0
0.019
0
0.0
0.0
0.0
0.0
0.0
0.0
17.051
1)
0.223
(2 1.2)
0.773
175.713
0.037
0.075
0.836
1.0
0.069
0.242
321.913
N2PC (7 1.5)
2788
0.986
158.235 235
0.044
067
0.857
0.999
0.061
0.238
493
N2PC 1.7)
2926
0.991
155.484
0.042
0.063
0.851
0.999
0.057
0.241
714.811
2.0)
0.057
SCG-MA
155.215
0.008
0.81
0.998
0.473
SCG SCG-MO
2442
0.431
175.654
0.036
0.094
0.839
0.999
0.08
0.22
19.316
SCG-B
502
0.638
129.335
0.117
0. 3636
0.816
0.926
0.295
0.142
1314.819
997
KOCG-TOP-1
0.842
5.857
0.803
0.289
0.85
0.368
0.648
0.002
KOCG-TOP-r
8903
0.986
3.417
0.007
0.007
0.0
0.056
0.014
0.327
L.SCD (AVG)
2288
0.556
113.637
0.013
0.051
0.869
0.936
0.086
0.23
88. 288
LSPCD (STD)
40
0.034
2,615
0.008
0.005
0.002
0.058
0.001
0.009
20..23
SCG-MA
SCG-MO
1.117
0.163
SCG-8
1700
0.356
49.824
0.12
0.032
0.768
0.268
0.07
0.174
3792. 395
SCG-R
7174
0.655
41.125
0.006
0.012
0.836
0.308
0.015
0.293
131,226
0.708
KOCG-TOP-r
4852
0.987
3.821
0.014
0.011
0.213
-0.075
0.024
0.199
(AVG)
0.049
L.PCD (STD)
207
0.091
4.757
0
0.025
0000
0.004
D.112
0.006
0.019
9.767
SEG-MA
4827
0.077
102.611
0.009
0.044
0.821
0.622
0.028
0.243
145. 295
SCG-MO
0.084
0.771
0.174
SCG-R
12909
0.739
18.278
0.011
0.004
0.788
0.135
0.009
0.463
175.294
KOCG-TOP-1
50
0.533
4,904
0.765
0 0.476
0.962
0.633
0.505
0.007
Table 10: Detailed results for the Epinions dataset. LSPCD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
8
S12E
IF
POL
MAC
MAO
CC-
OC-
DENS
1:0
TIME (s)
2 LSPCD (AVG)
2188
0.73
127.784
0.12
0.013
0.907
0.74
0.066
0.351
59.119
LSPCD (STD)
0.004
0,181
0.001
0.0
0.002
0.002
0.0
0.0
3,692
(y 1.2)
169.
0.0
0.999
N2PC (Y 1.5)
275
0.0
169, 859
D.625
0.01
0.999
0.0
0.625
0.595
238.315 3.5
N2PC 1.7)
1038
0,29
124.285
0.079
0.033
0.943
0.96
0.127
0.2 232
354.089 089
N2PC
2.181
0.114
0.739
SCG-MO
1017
0.039
722
0.099
0.138
0.91
0.713
0.14
0.22
25.471
SCG-B
253
0.043
156.179
0.419
0.205
0.999
1.0
0.621
0. 501
822.236
KOCG-TOP-1
0.596
8,167
0.708
0.815
1.0
0.833
0.007
KOCG-MMP-
1234
0.944
14.036
0.054
0.022
D.5
-0.245
0.064
0.16
4
LSPCD (AVG)
2120
0,582
111.544
0.124
0.016
0.952
0.408
0.065
0.341
65, 489
LSPCD (STD)
129
0.124
77.5
0.021
0.003
0.002
0.312
0.004
0.006
2.958
SCG-MA
0.297
D:001
SCG-B
868
0.544
96.43
0.405
0.0
0.926
-0.411
0.119
0.226
2169 558
SCG-R
1872
0.201
65.124
0.152
0.033
0.928
-0.801
0.044
0.23
49 49.068
KOUG-19P-1
XOCG-TOP-P
0.956
11.001
0.071
0.01
0.768
-0.63
0.06
(AVG)
0.473
0.929
107.579
LSPCD (STD)
155
0.051
3.637
0.009
0.004
0.002
0.142
0.004
0.007
20.806
SOG-MA
2564
0.52
$8.759
0.301
0.048
0.935
-0.213
0.05
0.34
57.185
SCG-MO
0.261
0.421
0.926
0.119
3696.279
SCG-R
1365
0.303
43,324
0.128
0.036
0.946
-0.998
0.054
0.203
$3.993
KDCG-10P-1
34
0.941
5.965
0.9
0.43
1.0
0..9%
0.576
0.012
KOLG-TOP-P
34

---

Table 11: Detailed results for the WikiPol dataset. L.PCDD (avg) and LSPCD (std) respectively indicate the mean and standard deviation across five runs of our method with different seeds.
k
S1ZE
1F
POL.
MAC
MAO
CC+
OC-
DENS
1:90
TIME (x)
2 LSPCD (AVG)
599
0.3
$1.985
D.093
0.034
0.917
0.87
0.15
0.109
$7.022
LSPCD (STD)
2
0.001
0.037
0.001
0.0
0.003
0.011
0.0
7,851
N2PC
472
(y
N2PC (4 = 1.5)
494
0.022
$6.579
0.092
0.05
0.932
0.984
0.188
0.102
162.75 781
N2PC (r 1.7)
562
0.39
15.167
0.098
0.023
0.918
0.994
0.145
0.099
154, 508
SCG-MA
1251
0.014
$2.822
0.035
0.054
0.924
0.928
0.072
0.172
11,484
SCG-MO
648
0.007
88. 441
0.071
0.079
0.928
1.0
0.147
0.121
4.041
SCG-B B
609
0.039
46.525
0.041
0.013
0.963
-0.238
773.37
KOCG-mP-1
0.792
0.625
KOCG-TOP TOP-
1251
0.988
1,258
0.024
0.012
0.322
-0.284
0.035
0.097
4 LSPCD (AVG)
450
0.27
71,628
0.147
0.068
0.938
0. 8.546
0.184
0.086
83.214
LSPCD (STD)
23
0.053
2.015
0.063
0.032
0.002
0.249
0.014
0.003
36.749
SCG-MA
2140
SCG-MO
2783
0.305
0.283
0.001
0.895
-0.775
0.026
0.242
SCG-B
727
0.208
45.661
0.203
0.001
0.967
-0.899
0.07
0.125
2225. 353
SCG-R
7740
0.144
53.723
0.002
0.001
0.916
0.599
0.005
0. 302
91.037
26
KOCG--MP--
2140
0.002
0.808
-0.609
(AVG)
LSPCD (STD)
72
0.07
1.348
0.023
0.014
0.005
0.183
0.011
0.008
192.894
SCG-MA
2176
0.415
$7.546
0.259
0.001
0.919
-0.73
0.037
0.22
$4,104
SUG-MO
0.236
0.001
727
3973.384
SCG-R
95033
0.423
3.329
0.006
0.01
0.854
-0.686
0.003
0.901
331.066
KDCG-1Ur-1
85
0.356
10.135
0.756
0.029
0.967
-0.658
0.268
0.015
2176
35

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and the list of contributions in the introduction enumerate the same five technical and empirical contributions later validated in Sections 3-4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: In Section 4, we note that no real-world ground-truth labels exist for PCD. We address this similar to previous work (by using polarity to evaluate solution quality and include synthetic data with ground-trute solutions).
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
36

---

Answer:
[Yes]
Justification: All theorems state the required assumptions and defer complete proofs to Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All details to reproduce the results are included. See Section 4. Also see Appendix G for details on datasets and hyperparameters.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
37

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The source code is available at NeurIPS2025-LSPCD.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
Polic)lly)yy)) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. http/uulic/ggeee www.c//ggge/eeeeeeee /elee///oodbbmiiec wwwaiiisssoooooiiiiiiiioooooioie
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Yes, all of it explaiend in detail in Section with more details in Appendix
G.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We include error bars in all plots involving synthetic data. For real-world data, show standard deviations of our method in Appendix G.9 (other methods deterministic).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
38

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See start of Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: / hww.rpsu....///
Answer: [Yes]
Justification: We have read the NeurIPS code of ethics and we confirm that our research conforms with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
39

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The work releases only an algorithm using atready-public graphs; no high-risk assets involved.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: See Appendix G.I.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
40

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //tprr//s.u...eeeee /ec//oonferenccee222/////// for what should or should be described.
42


Reviews:
[{"review_id": "8eRyCypLTE", "reviewer": "Reviewer_Tg7f", "summary": "The paper proposes a polarized community discovery method for signed graphs, aiming to address imbalanced clustering issues while maintaining good polarity of the discovered cohesive communities. Experiments on real and synthetic graphs were conducted to verify the performance of the method.", "questions": "Q1: The paper claims that scalability is one of the main contributions of the proposed method. However, the largest dataset used in the paper has only 2 million edges, which is not convincing to me. It would be better to include larger real datasets in the main paper to showcase the efficiency of the proposed method.\n\nQ2: It would be beneficial to demonstrate performance by comparing with related works using more sophisticated polarized community models, e.g., k-core, k-truss, and cliques. These methods can easily be extended to support top-k community retrieval. For example:\n\n[1] Effective and efficient core computation in signed networks, Information Sciences 2023\n\n[2] Maximum Balanced (k,ϵ)-Bitruss Detection in Signed Bipartite Graph, VLDB 2024\n\n[3] Clique Identification in Signed Graphs: A Balance Theory Based Model, TKDE 2023\n\n[4] Identifying Large Structural Balanced Cliques in Signed Graphs, TKDE 2024", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "S1: The problem studied in the paper is well-motivated and highly practical for real applications.\n\nS2: The paper is clearly written and easy to follow.\n\nS3: Detailed proofs and analyses are provided in the appendices.\n\nW1: It would be better to include performance comparisons with the most recent methods. Among all compared algorithms, only one was recently proposed (in 2024); all others were proposed before 2020.\n\nW2: The experiments could be enhanced by including larger datasets.\n\nW3: The related works are not comprehensively surveyed.", "was_revised": true, "final_justification": "Thank you for the rebuttal. I have read all the reviews, rebuttals, and the subsequent discussion. I will keep my current score.", "rebuttal": "Thank you for the thoughtful feedback.\n\n> ***Q1/W2:  The paper claims that scalability is one of the main contributions of the proposed method. However, the largest dataset used in the paper has only 2 million edges, which is not convincing to me. It would be better to include larger real datasets in the main paper to showcase the efficiency of the proposed method.***\n\nWe use the same datasets as the most relevant prior work on polarized community discovery (PCD), which we cite (e.g., [5,6,7,8]). These datasets vary widely in size, ranging from 6K nodes with 214K edges to 116K nodes with 2M edges. Across these datasets, our method remains competitive with baselines in terms of runtime (see Appendix G.8), demonstrating that our local search approach scales comparably to the best existing methods for PCD (while outperforming them in clustering quality). Furthermore, our proposed local search algorithm (Algorithm 3) is substantially faster than naive local search (see runtime comparison in Figure 3).\n\n> ***Q2/W1: It would be beneficial to demonstrate performance by comparing with related works using more sophisticated polarized community models, e.g., k-core, k-truss, and cliques. These methods can easily be extended to support top-k community retrieval.*** \n\nWe aim to find $k$ polarized communities in a signed graph, allowing for the presence of **neutral** objects (which we refer to as PCD). Among existing works on PCD, only [5,7] explicitly support an arbitrary number of clusters $k$, making them the only directly relevant prior work. We also include [7] in our comparisons, as it is the state-of-the-art for the special case of $k = 2$ clusters (there are a number of works for this special case, which we cite).\n\nFollowing [7], we additionally evaluate two state-of-the-art signed graph clustering methods (SPONGE and BNC). However, these methods do **not** explicitly account for neutral objects. To enable a fair comparison, we adapt them using heuristic extensions to allow neutral objects (as in [7]). Nonetheless, our experiments show that these heuristics result in poor performance. This supports our conclusion that signed clustering methods which do not explicitly model neutrality are not effective in settings where neutral objects are present.\n\nThe works cited by the reviewer (i.e., [1,2,3,4]) also do **not** explicitly handle neutral objects and would likely perform similarly poorly in our setting. Moreover, while some of the ideas presented in these papers can be used to detect clusters/communities, none of these works focus specifically on community or cluster detection. We now provide a detailed comparison of the four mentioned works:\n\n* [1]: The paper looks for a *single* maximal ($p$,$n$)-core, i.e., one subgraph in which every vertex has at least $p$ positive and fewer than $n$ negative intra‑edge, whereas PCD must *simultaneously* produce $k$ **disjoint communities plus a neutral set**. In our setting, the clusters/communities are detected automatically and do not need to set such possibly non-trivial hyper parameters. Since their objective is to *grow one cohesive subgraph*, not to partition the whole graph, there is no straightforward way to adapt their algorithms into a clustering baseline. It is not clear how one would extract exactly $k$ clusters, and neutral objects also are not explicitly handled.\n\n* [2]: Their algorithm looks for one (or several) dense balanced bitrusses in a **bipartite signed network**, defined by butterfly motifs and two disjoint node types, whereas PCD aims to partition a general (possibly **non‑bipartite**) signed graph into exactly $k$ communities plus a neutral set. It is not clear how one would extract exactly $k$ clusters from their method, and neutral objects are not explicitly handled. They mention **Community Search**, but this is about finding one community that contains a set of query nodes.\n\n* [3]: This work differs from ours, as it focuses on clique enumeration under the following assumptions: (i) each clique must contain at least $k$ nodes (note: this is a different $k$ compared to out paper, where $k$ denotes number of clusters), and (ii) cliques must not include any triangle with either two positive and one negative edge, or with all three edges negative. It is worth noting that triangles with two positive and one negative edge are particularly common in the presence of noisy edge weights (including all real-world and synthetic datasets in our experiments). Therefore, it is reasonable to allow them to be included in the discovered communities. Notably, our method is highly robust to such noise. Moreover, in our setting we do not impose any strict conditions on the size of the clusters.\n\n* [4]: This method also differs significantly from our setting: it aims to compute a maximal clique $C$ that includes $C_L$​ and $C_R$​, such that all negative edges lie between $C_L$​ and $C_R$​, and both $C_L$​ and $C_R$​ are larger than a predefined threshold $\\tau$. However, we are looking for coherent and positively well-connected clusters as well as a neutral set.\n\nIn short, none of the methods can be included as baselines for signed clustering with neutral objects without their methods being significantly re-designed.\n\n> ***W3: The related works are not comprehensively surveyed.***\n\nWe have included all works directly relevant to PCD in our discussion (see Section 1). As noted, the papers cited by the reviewer ([1,2,3,4]) are not directly related to our task. They also do not cite any literature on polarized community discovery with neutral objects, nor are they cited by any such works. For these reasons, we do not consider them relevant for direct comparison. However, we will include a brief discussion in the introduction (Section 1) about the connection to the suggested papers and the scope of our study in the camera-ready version.\n\n**References**\n\n[5] Chu et al. Finding gangs in war from signed networks. SIGKDD 2016.\n\n[6] Bonchi et al. Discovering polarized communities in signed networks. CIKM 2019.\n\n[7] Tzeng et al. Discovering conflicting groups in signed networks. NeurIPS 2020.\n\n[8] Gullo et al. Neural discovery of balance-aware polarized communities. *Mach. Learn.*, 113(9):6611–6644, 2024"}, {"review_id": "LEv8DqXh1p", "reviewer": "Reviewer_BDJW", "summary": "This paper addresses the Polarized Community Discovery Problem in Signed Networks, which consists of partitioning the network into k clusters with high (positive) similarity within clusters, low (negative) similarity across clusters and a possibly neutral subset of nodes. The paper proposes an alternative objective (with parameters alpha and beta) to a previously applied objective (polarity) and shows that the relaxation of the objective (originally NP-bard) can be formulated as a Block-coordinate Frank-Wolfe Optimization. The FW formulation is then shown to be equivalent to a local search algorithm that can be implemented e\"ciently. A theoretical analysis of the impact of the parameters alpha and beta is also provided. The experiments compare the proposed solution against four alternatives using eight datasets, showing that the baselines achieve worse results in terms of the proposed objective while the proposed solution is competitive with respect to polarity.\n\nI have to disclose that I have reviewed a previous submission and rebuttal of this paper earlier this year. Besides clarifications, the reviews and rebuttal focused on limitations in the evaluation of the proposed approach that have been partially addressed in this new version.", "questions": "Q1. How can the proposed formulation be justified based on real-world applications?\n\nQ2. Why is this paper a good match for NeurIPS?\n\nQ3. Is the optimization problem considered in this paper hard to approximate? If not, does the proposed algorithm provide any approximation guarantee?", "limitations": "Partially. The main paper could include a paragraph discussing these aspects.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n- The relationship between the FW formulation and the local search algorithm is interesting.\n- The paper presents many additional experiments and analysis in the appendix.\n- The proposed optimizations significantly decrease the complexity of the local search heuristic.\n\n**Weaknesses:**\n- The experimental section does not provide strong support for the proposed formulation.\n- The paper addresses a problem with limited interest within the ML community.\n- The proposed algorithm does not provide any approximation guarantees.\n\n**Detailed comments:**\n\nI find this to be an interesting paper, with some innovative ideas and a few limitations regarding its practical implications. I will provide some details on the weaknesses of the paper to help the authors to develop their rebuttal and possibly improve the paper.\n\n*Empirical support for the proposed formulation:* The formulation proposed in the paper (Equation 3) is motivated using theoretical arguments. Instead, it would be more interesting to use real-world ground-truth data to justify the proposed formulation. More specifically, how does the proposed formulation can potentially impact real-world applications in social or communication networks? Otherwise, it is hard to argue for one formulation versus another. In formulations for sparsest and normalized cuts, the balance appears as a ratio and not an additive form. Spectral graph theory supports interesting connections between these formulations and Laplacian eigenvectors. It is not clear when and why we should move to an additive balancing factor as proposed in this paper.\n\n*Problem:* Interest in polarization in social networks peaked about an eight years ago, together with misinformation and other topics. A lot of work has been done since but it is not clear where this line of research is moving towards. Looking at the NeurIPS topics of interest, this paper is closest to unsupervised machine learning and perhaps optimization. Other venues such as WetConf, WSDM, etc. seem to be more focused on this line of research.\n\n*Theoretical guarantees:* While the problem studied in this paper is np-hard, it is not clear if it can be approximated with any theoretical guarantee and whether the proposed algorithm achieves such a guarantee.", "was_revised": true, "final_justification": "This is an interesting paper that proposes an elegant solution for a problem that I believe have more theoretical than practical interest. The paper could be improved in some aspects (stronger empirical support for the proposed objective and theoretical guarantees for the proposed algorithm). However, I believe that its strengths overcome its weaknesses. The reviews are mostly positive and I would not argue against the acceptance of this paper.", "rebuttal": "We thank the reviewer for the detailed and constructive feedback.\n\n> ***Q1. How can the proposed formulation be justified based on real-world applications?***\n\nRegarding the following statement by the reviewer: “*Instead, it would be more interesting to use real-world ground-truth data to justify the proposed formulation*.”\n\nThis appears to imply that existing (signed) graph clustering objectives were derived from explicit analyses of patterns in real-world ground-truth data, rather than being motivated by good empirical clustering performance across datasets. However, it is not evident that this is the case. As the reviewer notes, many existing objectives, such as (signed) ratio cut, (signed) ratio association, and (signed) normalized cut, are connected to the spectral properties of various signed Laplacian matrices (as detailed in [1]). But it is not clear that spectral properties of a specific, arbitrarily chosen Laplacian matrix are inherently more aligned with real-world structure than alternative formulations.\n\nFor example, consider the seminal work on PCD by Bonchi et al. [2]. Their formulation is initially based on correlation clustering, which seeks to maximize intra-cluster similarity and minimize inter-cluster similarity. They observe that this objective does not naturally encourage the formation of neutral objects. To solve this, they propose a modified version which normalizes the objective by cluster size to promote neutral objects (as we discuss in detail in Section 2.2). Crucially, their formulation is not derived from real-world ground-truth data, but from a theoretical adjustment motivated by desired clustering behavior. The same is true for other PCD papers that we cite. \n\nIn our work, we adopt a similar high-level concept and approach, but propose to encourage balanced communities and neutral objects via an additive regularization term rather than a ratio-based adjustment. Our motivation is algorithmic: the additive formulation enables the development of the first (theoretically proven) efficient local search algorithm for PCD, **which would likely be infeasible with ratio-based objectives**. In addition, our experimental results demonstrate that this additive objective achieves strong performance compared to alternatives (*partially because we are able to employ an efficient local search based algorithm*). It is possible that our objective is connected to spectral properties of some Laplacian matrix, but we leave that analysis for future work.\n\n> ***Q2. Why is this paper a good match for NeurIPS?***\n\nPolarized Community Discovery (PCD) is a fundamental problem with numerous applications, particularly in the analysis of social networks, as discussed in Section 1 (see also the survey in [10]). Notably, two of our strongest competitors have been published in top-tier machine learning venues such as *Machine Learning Journal* (MLJ) and *NeurIPS* [3, 4].\n\nBeyond PCD, the broader task of clustering in signed networks (or signed graph mining more generally) has attracted considerable attention, with many contributions appearing in leading machine learning conferences and journals, see for example [5–10].\n\nOur approach can also be extended to deep learning settings, where pairwise similarities are derived from complex neural architectures, such as large language models. This direction has been explored, for instance, in the context of correlation clustering of signed networks [5, 11].\n\n> ***Q3. Is the optimization problem considered in this paper hard to approximate? If not, does the proposed algorithm provide any approximation guarantee?***\n\nCorrelation clustering, a problem closely related to Polarized Community Discovery (PCD), is known to be **APX-hard**, and therefore **hard to approximate** within arbitrary precision [13]. Given the structural similarity between the two problems, it is likely that PCD is also APX-hard. In our work, we prove that our problem (Problem 2 in the paper) is **NP-hard** by reducing from correlation clustering, and a similar reduction likely implies **APX-hardness** as well.\n\nWhile **constant-factor approximation algorithms** exist for correlation clustering — for example, using simple pivot-based methods \\[13] — these algorithms are often **outperformed in practice** by more sophisticated approaches based on **local search**, as shown in detail for example by [12]. However, these local search methods **lack known approximation guarantees** for the general case with arbitrary number of clusters $k$, in both correlation clustering and PCD.\n\nSimilarly, our local search-based approach does not come with theoretical approximation guarantees due to the algorithm's complexity. Instead, we focus on proving strong convergence guarantees and demonstrate that our method consistently outperforms standard baselines in empirical evaluations. In particular, as discussed in the paper, the standard Frank-Wolfe algorithm is known to achieve a convergence rate of $O(1/\\sqrt{t})$ for general non-concave objectives. In contrast, due to the specific structure of our objective, we prove that our method achieves a significantly faster linear convergence rate of $O(1/t)$, despite the function being both non-concave and non-multilinear. Given the prevalence and effectiveness of local search optimization methods in many learning models, including modern deep learning, our approach could even be perceived as having a higher impact and greater practicality than the methods with approximation guarantees.\n\n**References**\n\n[1] Chiang et al. Scalable Clustering of Signed Networks Using Balance Normalized Cut. CIKM 2012.\n\n[2] Bonchi et al. Discovering Polarized Communities in Signed Networks. CIKM 2019.\n\n[3] Tzeng et al. Discovering conflicting groups in signed networks. NeurIPS 2020.\n\n[4] Gullo et al. Neural discovery of balance-aware polarized communities. Mach. Learn., 113(9):6611–6644, 2024\n\n[5] Silwal et al. Kwikbucks: correlation clustering with cheap-weak and expensive-strong signals. ICLR 2023.\n\n[6] Kuroki et al. Query-Efficient Correlation Clustering with Noisy Oracle. NeurIPS 2024.\n\n[7] Bressan et al. Correlation Clustering with Adaptive Similarity Queries. NeurIPS 2019.\n\n[8] Mazumdar et al. Clustering with noisy queries. NeurIPS 2017.\n\n[9] Cucuringu et al. SPONGE: A generalized eigenproblem for clustering signed networks. AISTATS 2019.\n\n[10] Tang et al. A Survey of Signed Network Mining in Social Media. ACM Comput. Surv., 49(3):42:1–42:37, 2016.\n\n[11] Tipirneni et al. Context-Aware Clustering using Large Language Models. Preprint 2024.\n\n[12] Thiel et al. A non-convex optimization approach to correlation clustering. AAAI 2019.\n\n[13] Bansal et al. Correlation clustering. Mach. Learn., 56:89–113, 2004."}, {"review_id": "Bwn6ILyEbY", "reviewer": "Reviewer_hYDo", "summary": "The submission studies the question of identifying polarized communities in signed graphs. In this setting, each community consists of two opposing groups. The main point of the submission is that in previous works, the identified communities can have opposing groups of highly imbalanced sizes. Thus, the submission proposes a novel objective function, which obtains more balanced communities.\n\nFor the novel objective, an optimization algorithm based on the block-coordinate Frank-Wolfe method is proposed. It is then shown that this is equivalent to a local search approach, which is proven to converge to a stationary point and results on the convergence speed are provided. Further, a more efficient variant of this algorithm is provided.\n\nThe proposed algorithm is evaluated on synthetic and on real-world data, and it is compared against state-of-the-art competitors.", "questions": "1. Regarding the motivation of the submission, it is not fully clear to me why one should be aiming to find communities which are all roughly of the same size. I do agree that obtaining just very large or very small clusters is not ideal, but why should they all have the same size?\n2.  Continuing from the point above: In the experiments when defining the imbalance factor, why is the parameter $\\xi$ set to 3? It appears to be somewhat arbitrary, and I wonder whether this has been done in a principled way?", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. Identifying polarized communities in signed graphs is an interesting problem, especially as many existing methods can be quite fragile w.r.t. the solution quality they deliver. Thus, providing new methods in this area is interesting.\n2. The submission is overall well-written and easy to follow.\n3. Theoretical guarantees are presented, and the new method has strong mathematical foundations. In general, the submission provides good insights into the connections between continuous and discrete optimization.\n\nWeaknesses:\n1. Regarding the motivation of the submission, it is not fully clear to me why one should be aiming to find communities which are all roughly of the same size. I do agree that obtaining just very large or very small clusters is not ideal, but why should they all have the same size?\n2.  Continuing from the point above: In the experiments when defining the imbalance factor, why is the parameter $\\xi$ set to 3? It appears to be somewhat arbitrary, and I wonder whether this has been done in a principled way?\n3. It is not surprising that local search methods converge to stationary points. Also, the way that the new objective function is derived (by penalizing too many points in the non-neutral clusters) is quite standard.", "was_revised": true, "final_justification": "My impression is that this is a borderline paper. In general, the paper is well-executed, giving theoretical guarantees and interesting experimental results. \n\nOn the other hand, (also after the rebuttal) my impression is that the level of innovation is not exceedingly high (w.r.t. the new problem, as well as the theoretical results) and parameters such as $\\xi$ could be better explored.", "rebuttal": "Thank you for your insightful comments.\n\n> ***Regarding the motivation of the submission, it is not fully clear to me why one should be aiming to find communities which are all roughly of the same size. I do agree that obtaining just very large or very small clusters is not ideal, but why should they all have the same size?***\n\n**Important clarification:** We do **not** claim that all communities should be of equal size. The additive regularization term in our objective (Equation 3) is designed to discourage trivial solutions, such as those involving empty or near-empty clusters. However, it does **not** impose any strict balance constraint on cluster sizes.\n\nOur objective strikes a balance between three goals: maximizing intra-cluster similarity, minimizing inter-cluster similarity, and promoting reasonably balanced cluster sizes. As such, it may favor **unequal cluster sizes** when this leads to a better overall clustering solution according to the other criteria.\n\nThis behavior is evident in our experimental results. In Table 1, we report both Polarity and the Imbalance Factor, where a value of 1 for the imbalance factor indicates perfectly balanced clusters (i.e., all clusters are of equal size). Notably, our method (LSPCD) **never attains an imbalance factor of 1**, demonstrating that it does not enforce strict balance, but instead allows some variation in cluster sizes.\n\nAdditionally, Figure 2 in Appendix G.4 presents an experiment on synthetic data with **imbalanced ground-truth community sizes**. We observe that our method (LSPCD) successfully recovers the true communities in this setting. This further demonstrates that our objective does not enforce strict balance constraints and can effectively handle communities of varying sizes.\n\nFinally, Appendix E provides a detailed discussion of the benefits of discovering **reasonably balanced** communities, both from an optimization standpoint and in real-world applications. \n\n> ***Continuing from the point above: In the experiments when defining the imbalance factor, why is the parameter set to 3? It appears to be somewhat arbitrary, and I wonder whether this has been done in a principled way?***\n\nWe use the **imbalance factor** as defined in \\[1]. When the parameter $\\xi = 1$, the measure reduces to the Shannon entropy, as noted in the original paper. In our experiments, we set $\\xi = 3$ to **more strongly penalize highly imbalanced clusterings**.\n\nTo illustrate the effect of $\\xi$, consider the following examples:\n\n* For a perfectly balanced clustering with $k = 2$ clusters with cluster sizes $[1000, 1000]$, the imbalance factor is:\n\n  * $\\xi = 1$: 1.0\n  * $\\xi = 3$: 1.0\n\n* For a more imbalanced clustering with sizes $[1000, 300]$, the imbalance factor becomes:\n\n  * $\\xi = 1$: 0.779\n  * $\\xi = 3$: 0.548\n\nAs these values show, the imbalance factor is more **sensitive to deviations from perfect balance** when $\\xi = 3$, making it easier to distinguish between balanced and imbalanced solutions. This allows us to better capture and highlight differences in clustering behavior across methods.\n\nImportantly, we use the same value of $\\xi$ across all methods to ensure a fair comparison. While using $\\xi = 1$ leads to the **same overall conclusions**, choosing $\\xi = 3$ provides a sharper distinction between solutions with different degrees of balance. We illustrate this below by showing the imbalance factor of the solutions found by our method and our main competitor SCG on seven of the real-world datasets (as Table 1 in the main paper), for both $\\xi = 1$ and $\\xi = 3$.\n\nWe see that our method often finds more balanced solutions (larger imbalance factor), whereas our main competitor SCG finds highly imbalanced solutions (small imbalance factor). Note that in cases where their SCG achieves a larger imbalance factor, our method generally achieves a larger polarity. Please refer to Table 1 in the paper for complete results, where the trade-off between imbalance and polarity is highlighted. **The main point of the results below is that the relative ranking of the imbalance factor between the methods is consistent for** $\\xi = 1$ and $\\xi = 3$. We observe that the results and conclusions remain similar between $\\xi = 1$ and $\\xi = 3$. We will add this ablation study to the appendix of the camera-ready version.\n\nImbalance factors for $\\xi = 1$ (higher value means more balanced solution in terms of size):\n\n| k | Method       |  BTC | WikiV |  REF |   SD | WikiC |   EP | WikiP |\n| - | ------------ | ---: | ----: | ---: | ---: | ----: | ---: | ----: |\n| 2 | LSPCD (ours) | 0.84 |  0.69 | 0.88 | 0.50 |  0.93 | 0.89 |  0.56 |\n| 2 | SCG-MA       | 0.38 |  0.04 | 0.05 | 0.06 |  0.77 | 0.13 |  0.06 |\n| 2 | SCG-MO       | 0.11 |  0.04 | 0.05 | 0.04 |  0.69 | 0.13 |  0.03 |\n| 2 | SCG-B        | 1.00 |  0.12 | 0.11 | 0.15 |  0.84 | 0.14 |  0.13 |\n| 2 | SCG-R        | 0.50 |  0.39 | 0.12 | 0.22 |  0.79 | 0.41 |  0.39 |\n| 4 | LSPCD (ours) | 0.74 |  0.71 | 0.58 | 0.74 |  0.81 | 0.78 |  0.55 |\n| 4 | SCG-MA       | 0.45 |  0.60 | 0.75 | 0.51 |  0.18 | 0.50 |  0.64 |\n| 4 | SCG-MO       | 0.45 |  0.60 | 0.75 | 0.41 |  0.50 | 0.54 |  0.46 |\n| 4 | SCG-B        | 0.47 |  0.70 | 0.00 | 0.55 |  0.95 | 0.68 |  0.34 |\n| 4 | SCG-R        | 0.73 |  0.64 | 0.08 | 0.90 |  0.79 | 0.36 |  0.36 |\n| 6 | LSPCD (ours) | 0.75 |  0.70 | 0.49 | 0.66 |  0.80 | 0.71 |  0.76 |\n| 6 | SCG-MA       | 0.60 |  0.66 | 0.71 | 0.35 |  0.22 | 0.63 |  0.53 |\n| 6 | SCG-MO       | 0.61 |  0.64 | 0.78 | 0.56 |  0.50 | 0.42 |  0.36 |\n| 6 | SCG-B        | 0.64 |  0.75 | 0.00 | 0.45 |  0.83 | 0.53 |  0.26 |\n| 6 | SCG-R        | 0.58 |  0.84 | 0.44 | 0.72 |  0.87 | 0.47 |  0.51 |\n\nImbalance factors for $\\xi = 3$, used in Table 1 of main paper (higher value means more balanced solution in terms of size):\n\n| k | Method       |  BTC | WikiV |  REF |   SD | WikiC |   EP | WikiP |\n| - | ------------ | ---: | ----: | ---: | ---: | ----: | ---: | ----: |\n| 2 | LSPCD (ours) | 0.65 |  0.43 | 0.71 | 0.25 |  0.83 | 0.73 |  0.30 |\n| 2 | SCG-MA       | 0.16 |  0.01 | 0.01 | 0.01 |  0.53 | 0.04 |  0.01 |\n| 2 | SCG-MO       | 0.03 |  0.01 | 0.01 | 0.01 |  0.43 | 0.04 |  0.01 |\n| 2 | SCG-B        | 0.99 |  0.04 | 0.03 | 0.05 |  0.64 | 0.04 |  0.04 |\n| 2 | SCG-R        | 0.25 |  0.17 | 0.04 | 0.08 |  0.57 | 0.19 |  0.17 |\n| 4 | LSPCD (ours) | 0.47 |  0.52 | 0.41 | 0.54 |  0.56 | 0.58 |  0.27 |\n| 4 | SCG-MA       | 0.22 |  0.36 | 0.68 | 0.25 |  0.06 | 0.30 |  0.52 |\n| 4 | SCG-MO       | 0.22 |  0.37 | 0.70 | 0.20 |  0.24 | 0.34 |  0.30 |\n| 4 | SCG-B        | 0.23 |  0.60 | 0.00 | 0.38 |  0.86 | 0.54 |  0.21 |\n| 4 | SCG-R        | 0.52 |  0.44 | 0.02 | 0.76 |  0.66 | 0.20 |  0.14 |\n| 6 | LSPCD (ours) | 0.49 |  0.56 | 0.33 | 0.43 |  0.53 | 0.47 |  0.54 |\n| 6 | SCG-MA       | 0.46 |  0.42 | 0.62 | 0.17 |  0.07 | 0.52 |  0.42 |\n| 6 | SCG-MO       | 0.46 |  0.41 | 0.72 | 0.29 |  0.22 | 0.26 |  0.24 |\n| 6 | SCG-B        | 0.47 |  0.61 | 0.00 | 0.32 |  0.71 | 0.42 |  0.16 |\n| 6 | SCG-R        | 0.41 |  0.79 | 0.36 | 0.46 |  0.74 | 0.30 |  0.42 |\n\n> ***It is not surprising that local search methods converge to stationary points. Also, the way that the new objective function is derived (by penalizing too many points in the non-neutral clusters) is quite standard.***\n\nPenalizing large clusters to encourage the identification of neutral objects is indeed standard practice in PCD. However, we are the first to introduce this penalty via an additive regularization term (see Equation 3). This additive formulation is a key innovation that enables the development of the **first theoretically grounded and efficient local search algorithm for PCD**—a direction that would likely be infeasible under the **ratio-based objectives** used in all prior work. Our experimental results further demonstrate that this additive objective yields strong empirical performance, outperforming several baselines (*partially because we are able to employ an efficient local search based algorithm*).\n\nMoreover, our theoretical contributions go beyond standard convergence guarantees. We prove a **linear convergence rate**, making it highly efficient in practice. In particular, as discussed in the paper, the standard Frank-Wolfe algorithm is known to achieve a convergence rate of $O(1/\\sqrt{t})$ for general non-concave objectives. In contrast, due to the specific structure of our objective, we prove that our method achieves a significantly faster linear convergence rate of $O(1/t)$, despite the function being both non-concave and non-multilinear. \n\nGiven the prevalence and effectiveness of local search optimization methods in many learning models, including modern deep learning, our approach could even be perceived as having a higher impact and greater practicality than alternative methods.\n\n**References**\n\n[1] Pirizadeh et al. Imbalance factor: a simple new scale for measuring inter-class imbalance extent in classification problems. Knowl. Inf. Syst., 65(10):4157–4183, 2023."}, {"review_id": "Av4jph1AVS", "reviewer": "Reviewer_W8gu", "summary": "The paper presents an efficient local search method for detecting polarized communities in signed networks. The authors propose a novel formulation of the Polarized Community Discovery (PCD) problem, addressing issues of community balance. The approach leverages block-coordinate Frank-Wolfe optimization and translates it into a local search procedure with provable convergence guarantees. Through extensive experiments on real-world datasets, the proposed method demonstrates superior solution quality and computational efficiency compared to state-of-the-art baselines.", "questions": "Q1) Could the authors clarify why a comparison with N2PC (equipped with \\gamma-polarity) on synthetic networks with k = 2 and unbalanced ground-truth communities was omitted, given that both the proposed method and N2PC are specifically designed to account for community balance?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nS1) The paper is overall well-written\n\nS2) The proposed approach based on Frank-Wolfe optimization appears to be novel, to the best of my knowledge. To support the claim that “in Section 4, we demonstrate across a range of real-world and synthetic datasets that the advantages of local search optimization (e.g., for CC) carry over to PCD as well,” the authors could strengthen the connection to prior work by referencing related studies on correlation clustering (CC) where local search procedures have been successfully employed [n1, n2].\n\n[n1] An Efficient Local Search Algorithm for Correlation Clustering on Large Graphs. COCOA 2023.\n\n[n2] In and out: Optimizing overall interaction in probabilistic graphs under clustering constraints. KDD 2020.\n\nS3) The paper offers several valuable contributions across multiple aspects: theoretical (including a novel problem formulation and theoretical results), algorithmic (proposing algorithms to solve the introduced problem), and experimental (presenting extensive results in both the main paper and the appendix).\n\nS4) Convergence analysis of the proposed local search algorithm.\n\nS5) Experiments on both real-world and synthetic datasets. The selected datasets are consistent with those found in the relevant literature on PCD in signed graphs.\n\nS6) The results confirm the significance of the proposed method, as it yields solutions with high polarity while achieving better size balance.\n\nWeaknesses:\n\nW1) The paper fails to compare with N2PC (equipped with \\gamma-polarity) on synthetic networks with k = 2 and unbalanced ground-truth communities. Since the proposed method and N2PC are the only methods that account for community balance, such comparison seems needed. Also, I think Table 1 should report for k = 2 the results of N2PC.\n\nOverall, I believe this is a solid piece of work in which the strengths outweigh the weaknesses, and for this reason, I recommend acceptance.", "was_revised": true, "final_justification": "I was already positive about the paper before the author–reviewer interaction, as I found the contribution relevant, well-motivated, and clearly presented. The authors’ rebuttal effectively clarified the points I had raised in my review, and I found their explanations satisfactory. In addition, reading the authors’ responses to the other reviewers further reinforced my positive assessment. As no significant issues remain unresolved from my perspective, I remain convinced that the paper meets the quality standards for acceptance, given its sound methodology, clear presentation, and valuable contribution to the topic.", "rebuttal": "We thank the reviewer for the thoughtful feedback/comments.\n\n> ***Q1/W1: Could the authors clarify why a comparison with N2PC (equipped with \\gamma-polarity) on synthetic networks with k = 2 and unbalanced ground-truth communities was omitted, given that both the proposed method and N2PC are specifically designed to account for community balance?***\n\nThe reviewer is referring to Figure 2 in Appendix G.4. This case was omitted arbitrarily, as we found that the results for $k = 4$, $k = 6$, and $k = 10$ already illustrated our point effectively. The purpose of this experiment was to demonstrate that our method can recover the ground-truth communities even when they are imbalanced in size. This highlights that our proposed objective does not impose strict balance constraints and is capable of recovering communities that differ in size.\n\nNevertheless, we will include the results for $k = 2$ in the camera-ready version, along with the N2PC baseline, which is only applicable when $k = 2$. The results are consistent with those for $k = 4$, $k = 6$, and $k = 10$, with our method slightly outperforming N2PC.\n\nNote that we compare with N2PC in detail in the main paper, see e.g. Figure 1 and Table 2.\n\n> ***Also, I think Table 1 should report for k = 2 the results of N2PC.***\n\nThe results for $k = 2$ using N2PC are presented in Table 2. We included them as a separate table to emphasize the effect of varying $\\gamma$ for N2PC, and how it compares to our method. However, we can easily merge these results with Table 1 (e.g., by selecting a single representative value of $\\gamma$). We will add this to the camera-ready version.\n\n\n> ***To support the claim that “in Section 4, we demonstrate across a range of real-world and synthetic datasets that the advantages of local search optimization (e.g., for CC) carry over to PCD as well,” the authors could strengthen the connection to prior work by referencing related studies on correlation clustering (CC) where local search procedures have been successfully employed [n1, n2].***\n\nThank you for pointing this out. We will add these references as well to strengthen this claim."}]

Author rebuttal:

Meta-review: This paper addresses the problem of discovering polarized communities in signed graphs. The authors propose a novel objective function with additive regularization and solve it using a block-coordinate Frank-Wolfe optimization approach. The paper is clearly written, with strong theoretical contributions and extensive experimental evaluation. Although the reviewers concerned insufficient comparisons with recent methods and limited dataset sizes in the experiments, the proposed formulation and its connection to an efficient local search algorithm via Frank-Wolfe optimization are both interesting and valuable. Therefore, I recommend acceptance of this paper.
Decision: Accept (poster)