acceptodds
Under review as a conference paper at ICLR 2027

Polarized Community Detection in Signed Networks via Quasi-Arithmetic Means

Abstract

The 2-POLARIZED-COMMUNITIES (2PC) problem seeks two disjoint polarized communities such that most edges within each community are positive, and most edges between communities are negative. The 2PC objective encodes these requirements as the arithmetic mean of the per-node net degree balance. While effective, this captures only an average-driven notion of polarized structure, and may overlook other notions such as tight cores, where all selected nodes are strongly polarized, and hub-driven formations, dominated by a few high-balance nodes. We introduce a novel one-parameter family of polarized-community objectives, where the parameter controls a quasi-arithmetic exponential mean of net degree balances. Our objective captures the standard 2PC problem as a special case (), and interpolates between core-like () and hub-driven () notions of polarized structure. We study the complexity of the resulting problems, showing NP-hardness in general and at the core-like extreme, a polynomial-time exact algorithm for the hub-driven extreme, and identifying tractable cases on balanced signed graphs. Algorithmically, we show that the standard 2PC peeling rule does not extend to , and design a generalized peeling algorithm that removes nodes according to the exact marginal change in the finite- objective. Experiments on real-world datasets show that interpolates between small, dense, highly polarized cores and larger hub-driven structures; on synthetic graphs, our methods robustly identify the ground-truth communities.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
polarized community detection, signed graphs, quasi-arithmetic means

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_UJEDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the 2-Polarized-Communities (2PC) problem. The 2PC problem aims to group the nodes of a signed graph into two clusters, with large similarity inside each cluster and small similarity between ecah cluster, while allowing some objects to remain neutral (i.e. not assigned to any cluster). This implies the subgraph induced by the nodes in the two clusters should be as dense as possible. Existing work on 2PC primarily targets the polarity objective. This paper indentifies that this objective optimizes the average contribution of each node to the objective. However, in some cases, it may be of interest to also put emphasis on objects with the smallest or largest contribution to the objective. For example, putting emphasis on nodes with the smallest contribution can encourage solutions where all objects are aligned with the polarization structure. They propose an objective that captures this, and it generalizes polarity. They then analyze the computational complexity of this objective and generalize an algorithm for polarity to their objective (peeling).

Critical strengths
  • The proposed objective is a novel and interesting generalization of polarity for the 2PC problem. It makes it possible to find clustering structures that are (possibly) meaningfully different compared to optimization of the polarity objective. This may be of interest for a number of use cases.

  • The derivation of the generalized peeling algorithm is interesting and provides a way to optimize their generalized objective.

Critical weaknesses
  • You show that varying pp leads to changes in community size, density, node balance etc. However, you do not establish that these resulting structures are more informative for any concrete application. The results shown in Table 1 essentially just confirm what one would expect given the role that pp has. Also, it seems that the p=∞p=\infty case is not interesting and finding the solution is trivial in this case. This makes me wonder if the p>0p > 0 is actually useful. I would appreciate clarification about this. Moreover, on the synthetic experiments it does not seem that a non-zero value of pp improves discovery of ground-truth communities.

  • To my understanding, the generalized peeling rule is O(n(n+m))O(n(n+m)), whereas the standard peeling rule is O(n+m)O(n+m). This is a significant difference, and essentially means that your method will not scale to large graphs. Even for sparse graphs it would be O(n2)O(n^2), which is not scalable in general. In addition, the experiments do not evaluate the scalability of your method.

To summarize, the experiments do not convince me that the generalized objective provides a meaningful benefit over standard polarity, in particular given that it is also much slower.

Questions for authors

See list of weaknesses above.

2 comments

We thank the reviewer for the careful review and for raising concerns about the usefulness of pp, the algorithmic complexity, and scalability.

All section, table, and theorem numbers below refer to the revised PDF, where new and modified text is highlighted in blue; a summary of all revisions is posted in the general comment.

W1. Usefulness of the parameter pp

Our contribution is primarily theoretical and methodological. The parameter pp is a modeling choice specifying which notion of polarized community is sought, and evaluating a range of values supports exploratory analysis. We agree that Table 1 mainly confirms the predicted behavior; the experiments further show that different values return structurally distinct communities: p→−∞p \to -\infty favors cohesive and selective communities, whereas p>0p > 0 can restructure the solution and reveal two-sided communities when the p=0p = 0 solution is one-sided. Since real signed networks generally lack ground-truth polarized communities, we follow prior 2PC work (Bonchi et al., 2019; Tzeng et al., 2020; Gullo et al., 2026) in evaluating through structural criteria and recovery on planted instances, rather than tailoring the evaluation to a specific application; application-driven validation is an important direction for future work.

On p→+∞p \to +\infty. We agree that Max-2PC is solved by a direct construction (Theorem 2): a vertex of maximum unsigned degree, with its positive and negative neighbors in the two communities. As also noted by Reviewer jz7x and Reviewer rHKK (Strength 2), we regard this as an informative complexity result, especially given the NP-hardness of the opposite, core-oriented extreme (Theorem 3). The hub solution is also useful algorithmically: for finite p>0p > 0, taking the better of Max-2PC-Exact and GenPeel-pp-2PC inherits the additive guarantee of Proposition 5.

Usefulness of finite p>0p > 0. Finite p>0p > 0 can return structures that differ from both p=0p = 0 and p→+∞p \to +\infty: on WikiPol, p=0p = 0 yields a highly one-sided solution (546/2), whereas p=0.01p = 0.01 returns two larger communities (8061/2330), with agreement 0.914 vs. 0.832 at p→+∞p \to +\infty (Table 1). Moreover, the hub solution does not dominate GenPeel-pp-2PC: at p=0.01p = 0.01, GenPeel-pp-2PC obtains higher EpE_p on all four small and medium-sized networks below.

EpE_p at p=0.01p = 0.01CloisterCongressHTribesWord
GenPeel-pp-2PC7.476.776.1925.54
Hub (Max-2PC-Exact)5.773.284.7513.70

The hub solution wins only on large graphs with very high-degree hubs, where even a small p>0p > 0 makes the objective nearly hub-driven (see our reply to Reviewer rHKK, W1(b)).

Synthetic graphs. We agree that finite pp does not improve F1 over p=0p = 0 in the planted M-SSBM setting. This is expected: the ground-truth communities planted by M-SSBM are of the kind targeted by the p=0p = 0 objective (standard 2PC). Finite pp preserves this recovery (F1 = 1 for η≤0.3\eta \le 0.3, F1 ≥0.947\ge 0.947 at η=0.5\eta = 0.5). The two extremes reveal trade-offs not captured by p=0p = 0, e.g., p→−∞p \to -\infty achieves precision 1 up to η=0.5\eta = 0.5, at lower recall.

W2. Complexity and scalability

The O(∣V∣∣E∣)O(|V||E|) bound in the submission was coarse. Accounting for the incremental maintenance of marginal values and the priority queue used in the implementation, the revised bound is O(∣V∣+(∑v∈Vd(v)2)log⁡∣V∣)O\big(|V| + \big(\sum_{v \in V} d(v)^2\big) \log |V|\big) (Section 5 and Appendix E). This is close to linear on sparse graphs with bounded or light-tailed degree distributions. On dense or hub-dominated graphs, however, ∑v∈Vd(v)2\sum_{v \in V} d(v)^2 can approach ∣V∣∣E∣|V||E|; the revision now acknowledges this limitation.

We also added scalability experiments (Figure 13), injecting ∣V∣/2|V|/2 to 8∣V∣8|V| dummy vertices into Epinions and WikiConflict. The largest instances have about 1.2M vertices and 12.3M edges (Epinions) and 1.05M vertices and 34.7M edges (WikiConflict). GenPeel-pp-2PC completes on all instances and values of pp; runtime grows steadily with size, staying under 14 hours on the largest graph. It remains slower than Greedy-2PC, as expected from the exact marginal rule, which depends on two-hop information.

Overall, the benefit of the generalized objective over standard polarity lies in the structures that polarity misses. For instance, Core-2PC-Peel (p→−∞p \to -\infty), faster than Greedy-2PC, attains the best minimum net degree balance on 11/11 networks (Table 7) and, on Word, isolates a clean antonym core of 23 size adjectives (big/huge vs. tiny/little), whereas p=0p = 0 returns 110 words mixing unrelated antonym pairs, e.g., primary/secondary and superior/inferior (Figure 3). The extra runtime concerns only finite p≠0p \neq 0, where GenPeel-pp-2PC improves EpE_p over net-degree peeling by up to 747.9% (Table 6; see our reply to Reviewer rHKK, W1(a)).

We hope this addresses your concerns and would be glad to clarify further.

Thank you for the response. It addresses my concerns and I have updated my score.

Reviewer_jz7xOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a general framework, P-MEAN-2PC, for detecting polarized communities in signed networks. Instead of using the arithmetic mean of net degree balances, this framework employs a quasi-arithmetic exponential mean, regulated by a parameter p. By adjusting the value of p, the framework enables a smooth transition between two extreme structural configurations. The paper proves that the general problem and the CORE-2PC variant are NP-hard, while the MAX-2PC variant can be solved in polynomial time. To address these problems, the authors develop the GenPeel-p-2PC algorithm, which generalizes the traditional peeling method by precisely calculating the marginal changes resulting from the removal of nodes. Through experiments on both real-world and synthetic signed networks, the paper demonstrates how the parameter p influences the detected community structures and evaluates the effectiveness of the proposed algorithm in comparison to existing methods.

Critical strengths

1.This paper introduces a novel model for detecting polarized communities. By incorporating parameterized quasi-arithmetic means, the model extends the traditional 2PC objective function, allowing it to encompass a diverse range of polarization structures. 2.The study derives several theoretical insights concerning different parameter ranges and investigates the computational complexity of the problem, revealing significant distinctions between its various special cases. Specifically, it is shown that the CORE-2PC problem is NP-hard, whereas the MAX-2PC problem can be solved in polynomial time. 3.The paper proposes a generalized peeling strategy and provides a comprehensive empirical evaluation. The evaluation encompasses a variety of real-world networks, synthetic graphs with predefined community structures, comparisons with existing methods, and small-scale instances for which optimal solutions are known.

Critical weaknesses
  1. The overall technical contribution of this study appears somewhat incremental. While the P-MEAN-2PC formulation proposed in the paper offers a unified perspective for understanding various concepts of polarized communities, its core ideas have already been explored in existing literature on dense subgraphs. The study’s primary algorithmic contribution, GenPeel-p-2PC, largely adopts the established peeling framework, merely replacing the traditional node-removal criterion with an exact marginal change derived from the new objective function. This extension is quite straightforward, and does not introduce novel search strategies, provides no superior approximation guarantees, or a more efficient algorithm.
  2. Compared to traditional peeling strategies, GenPeel-p-2PC offers only marginal improvements while incurring a significantly higher computational cost. As shown in Table 6, GenPeel-p-2PC achieves 98.7%–99.9% of the optimal solution, whereas Greedy-2PC reaches 98.2%–98.6%. However, the runtime of GenPeel-p-2PC is substantially higher. For instance, on the WikiCon dataset, GenPeel-p-2PC requires approximately 7000 seconds, compared to just 124 seconds for Greedy-2PC.
  3. The proposed peeling algorithm is highly dependent on the initial spectral partition. Both GenPeel-p-2PC and Core-2PC-Peel utilize Eigen-Bipartition to initialize the two communities. Subsequently, as nodes are removed, their community assignments are never re-evaluated. Consequently, if a node is incorrectly assigned to a community during the initialization phase, it cannot be reassigned to the other, which may limit the quality of the final solution. The paper does not adequately explore how different initialization strategies might affect the results, nor does it investigate whether allowing for node reassignment could improve the objective function value.
  4. The experimental evaluation fails to sufficiently demonstrate the practical advantages of various parameter choices. While the authors show that varying the parameter p yields communities with distinct structural properties, most evaluations on real-world data rely on structural metrics such as polarity, density, and the agreement ratio. Although these metrics are closely related to the intended optimization objectives, they do not necessarily prove that the identified communities are more meaningful in a practical context. Further evaluation using real-world community data with external labels or downstream tasks would provide stronger evidence for the algorithm's practical utility.
Questions for authors
  1. Given that Table 6 shows Greedy-2PC already achieves objective function values ​​close to the optimum, could the authors provide additional experimental cases that demonstrate scenarios where the exact marginal-change rule yields significant improvements?
  2. How sensitive are the proposed peeling algorithms to the initial bipartition? Have the authors explored alternative initialization strategies, or perhaps local reallocation operations that allow vertices to move between the two communities during the optimization process?
3 comments
AuthorsOpenReview ↗

Response to Reviewer jz7x 1/2

We thank the reviewer for the careful review. We address the concerns about the contribution, computational cost, initialization, and practical relevance of pp below, together with the two questions.

All section, table, and theorem numbers below refer to the revised PDF, where new and modified text is highlighted in blue; a summary of all revisions is posted in the general comment.

W1. Novelty and incremental contribution

We acknowledge the connection with generalized-mean dense-subgraph objectives (Veldt et al., 2021) and with the established peeling paradigm. However, we believe that the technical contribution of the paper lies in several complementary aspects beyond the removal rule:

  • Problem formulation: to the best of our knowledge, P-Mean-2PC is the first theoretically grounded, single-parameter family of polarization objectives for signed graphs, using an exponential quasi-arithmetic mean to handle signed node balances.
  • Complexity: unlike the unsigned generalized-mean densest-subgraph setting, Core-2PC is NP-hard (Theorem 3), whereas Max-2PC is polynomial-time solvable (Theorem 2). On balanced graphs, polynomial-time solvability holds for p→−∞p \to -\infty and p=0p = 0 (Theorem 4), and the revision additionally establishes it for every finite p>0p > 0 (Theorem 5).
  • Algorithms and evaluation: we show that the ordinary 2PC peeling rule does not extend to p≠0p \neq 0 (Example 1), derive the exact marginal-removal rule (Equation 6), and evaluate it on real and synthetic networks. On real networks, the gains over net-degree peeling reach 747.9%. For p>0p > 0, the better of GenPeel-pp-2PC and Max-2PC-Exact also inherits the additive guarantee in Proposition 5.

We therefore view the paper as introducing and computationally characterizing a new family of polarized-community objectives, supported by algorithmic development and an extensive empirical evaluation.

W2 / Q1. Cases with significant improvement and computational cost

The comparison in Table 8 (old Table 6 in the submitted version), i.e., 98.2% versus 98.7–99.9% of the optimum, concerns 16-node graphs, where Greedy-2PC is already close to optimal and leaves limited room for improvement. Prompted by Reviewer rHKK, we added the same comparison on real-world networks (new Table 6 in the revised paper): using the same seed and the same EpE_p-based selection criterion, GenPeel-pp-2PC is never worse than net-degree peeling and is strictly better in 76 of 88 settings. Its gain exceeds 10% in 18 settings. Table 6 also reports the additional running time of GenPeel-pp-2PC for each setting. The largest gains include (complete results in Table 6 of the revised paper):

Datasetpprelative EpE_p gain over net-degree peelingExtra time (s)
WikiPol+0.001+0.001+747.9%+804
Bitcoin+0.01+0.01+234.1%+4.9
WikiEle+0.01+0.01+108.0%+23
Word+0.1+0.1+106.1%+4.4
TwitterRef−0.1-0.1+37.2%+197
Slashdot−0.1-0.1+30.1%+260

For negative pp values close to zero, gains are small (median approximately 0.2%), consistently with Proposition 3; the revised manuscript now makes this explicit. On all small and medium networks, the extra time is below 36 s in every setting; it grows to hours only on WikiConflict, where it still yields gains of up to 27.8%. Since polarized-community detection is typically an offline, exploratory analysis, this cost is affordable in exchange for substantially better solutions. GenPeel-pp-2PC also scales to much larger graphs: on augmented networks with up to 1.05M nodes and 34.7M edges, it completes for every tested pp in under 14 hours (Fig. 13; see also our reply to Reviewer UJED, W2).

AuthorsOpenReview ↗

Response to Reviewer jz7x 2/2

W3 / Q2. Initialization and vertex reassignment

We have added the seed-sensitivity study described in our response to Reviewer Kxt5 (W1), covering perturbed spectral seeds, random bipartitions, and the hub seed. The results show that solution quality degrades with seed perturbation: flipping 5% of the vertices retains approximately 96% of the EpE_p value. A random seed retains only 38–56%. For p≤0p \le 0, Eigen-Bipartition is the best or within 0.3% of the best tested seed in every setting. For p>0p > 0, the hub seed is better in nine of the 66 tested settings, all on the largest graphs.

GenPeel-pp-2PC can remove vertices into the neutral set, but it cannot move a vertex directly to the opposite community or reconsider a previous removal. During early development of our work, we tested a greedy local-search post-processing step that allowed such moves (node to the opposite community or to the neutral set) whenever they improved EpE_p. It produced no improvement in most configurations and relative gains below 1% in the remaining cases. Given these limited gains, we retained the current algorithm and did not include this experiment in the paper.

W4. Practical value of different values of pp

To our knowledge, real signed networks generally do not provide ground-truth polarized communities or external labels against which such communities can be evaluated directly. Prior work on 2PC (Bonchi et al., 2019; Tzeng et al., 2020; Gullo et al., 2026) therefore uses structural criteria and recovery on planted synthetic instances; we follow the same evaluation protocol.

Our contribution is primarily theoretical and methodological. The parameter pp specifies which notion of polarized structure is sought, and a sweep over pp can support exploratory analysis by revealing different structures in the same network. In the opinion-network example in the Introduction, p→−∞p \to -\infty favors opposing groups whose members are all consistently embedded in the support–dissent structure; p=0p = 0 identifies broader camps polarized on average, potentially including peripheral participants; and p→+∞p \to +\infty emphasizes highly polarized hubs or figures supported by one side and opposed by the other.

The Word network, whose edges encode synonym and antonym relations, lets us check the meaning of the returned communities directly (Figure 3 in Appendix). There, p→−∞p \to -\infty isolates two tight groups of 23 size adjectives, synonyms within each group and antonyms across them (big/huge vs. tiny/little), whereas p=0p = 0 returns 110 words that mix unrelated antonym pairs (e.g., primary/secondary and superior/inferior). Hence, pp changes not only structural metrics but also what the communities mean.

We hope these responses address the reviewer's concerns and would be glad to provide further clarification if needed.

Thank you for your clarifications and supplementary experiments, which have addressed some of my previous concerns. While these responses and results have strengthened the paper, I still consider its technical contribution to be relatively incremental, with substantial performance improvements demonstrated only in a small subset of experimental settings. Therefore, I will maintain my original rating.

Reviewer_rHKKOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper provides a generalization of the 2 Polarized Communities problem on signed graphs. Each selected vertex receives a net degree balance: the difference between the number of edges consistent with its community assignment and the number of inconsistent edges. The standard objective averages these balances. The proposed objective replaces this average with an exponential quasi-arithmetic mean controlled by a parameter pp.

The objective recovers the arithmetic mean as p→0p\to0, the minimum balance as p→−∞p\to-\infty, and the maximum balance as p→+∞p\to+\infty. This gives a common formulation for communities with uniformly strong membership, high average balance, or a few high-balance hubs.

The paper proves hardness for the minimum-balance problem and gives an exact algorithm for the maximum-balance problem. It also proposes GenPeel, an approach that removes vertices using their exact contribution to the change in the finite-pp objective. Experiments cover networks where the optimum can be computed exactly.

Critical strengths
  1. Communities can have the same average balance but very different distributions of vertex balances. The exponential mean captures this distinction, handles negative balances, and connects the minimum, average, and maximum objectives. Removing a vertex affects both its own contribution and the balances of its neighbors. Equation (6) includes these effects and gives a reasonable extension of ordinary peeling.

  2. The contrast between the NP-hard minimum-balance problem and the simple maximum-balance problem is interesting.

Critical weaknesses
  1. Can the authors provide a comparison with ordinary net-balance peeling, with the best intermediate solution selected using the same objective, EpE_p, as GenPeel?

The paper reports this comparison only on small synthetic graphs, where GenPeel’s improvement is modest. The comparison is missing on real networks. The authors should show whether this additional computation produces better solutions on these networks.

The paper’s own analysis also suggests another competitive simple baseline: select the highest-degree vertex and its neighbors, assigning the neighbors to communities according to their edge signs. Lemma 4 gives a guaranteed lower bound on this solution’s EpE_p score. On real networks, GenPeel’s reported score falls below this bound (Tables 1 and 4). For example, on WikiEle at p=0.01p=0.01, GenPeel achieves 243.7, while the hub construction is guaranteed to achieve at least 367.8. Thus, a direct construction outperforms GenPeel under the same objective, without iterative peeling.

Since the authors already compute the hub solution using Max-2PC-Exact, they should evaluate it under each finite positive pp and compare its score with GenPeel’s.

  1. Proposition 1 needs a more precise statement and a corrected proof.

As written, Proposition 1 only asks for some bipartition of VV containing the two selected communities. Under the paper’s convention allowing empty parts, any two disjoint sets can be extended this way. The literal statement is therefore trivial.

However, the sentence after the proposition and its proof clearly intends a balanced bipartition of the whole graph. The claim that every optimal assignment extends to such a bipartition is false.

For a counterexample, take two all-positive 4-cliques joined by a positive path of three edges. Select the two cliques as opposite communities and leave the two internal path vertices neutral. Every selected vertex has balance 3. This is optimal at p=0p=0, because no subgraph of this graph has average degree above 3. However, the graph is connected and all-positive, so every balanced bipartition puts all vertices on the same side. The two opposite community assignments cannot extend to it.

The gap in the proof is that it treats the components of the selected subgraph as independently orientable, while paths through neutral vertices can constrain their relative orientation.

A sufficient corrected statement is:

For any fixed balanced bipartition, there exists an optimal solution consistent with it.

This follows from the paper’s own argument: reassigning selected vertices according to a fixed balanced bipartition does not reduce any vertex’s net degree balance. This statement is also sufficient for Theorem 4.

Questions for authors
  1. Please refer to weakness section.

  2. The balanced case with p>0p > 0 appears to admit a polynomial oracle algorithm.

Appendix C leaves this case open because binary search over thresholds may not terminate efficiently. Dinkelbach’s method avoids this binary-search issue. After fixing a balanced bipartition, the task is to maximize N(U)/∣U∣N(U)/|U|, where

$ N(U)=\sum_{u\in U}e^{p d_U(u)} $ is supermodular by Lemma 5.

Starting from λ=0\lambda=0, Dinkelbach’s method repeatedly maximizes N(U)−λ∣U∣N(U)-\lambda|U|. Each such problem can be solved by minimizing the submodular function λ∣U∣−N(U)\lambda|U|-N(U). Whenever the maximum is positive, the method updates λ\lambda to the returned ratio N(U)/∣U∣N(U)/|U|. Taking N(∅)=0N(\emptyset)=0, it stops when the maximum is zero.

The cardinalities of successive improving solutions strictly decrease, so at most ∣V∣+1|V|+1 oracle calls are needed, including the final termination check. This gives a polynomial algorithm in the exact real-valued oracle model, consistent with known results on densest supermodular sets (Chekuri, Quanrud, and Torres, 2022; Harb, Yassin, and Chekuri, 2025). Please state the computational model and revise the claim that this case is open if this holds.

I encourage the authors to submit a rebuttal. I am willing to update my score provided the authors satisfactorily address my concerns.

2 comments

We thank the reviewer for the precise and constructive review. We have adopted the suggestions and revised the manuscript accordingly.

All section, table, and theorem numbers below refer to the revised PDF, where new and modified text is highlighted in blue; a summary of all revisions is posted in the general comment.

W1(a). Net-balance peeling with EpE_p-based selection

We added a comparison on all 11 real-world networks (Table 6 and Appendix K). Both algorithms start from the same seed and return the best intermediate solution according to EpE_p; they differ only in the removal rule. The following table summarizes the results across the 11 networks; the detailed gains for each dataset and all 88 configurations are reported in Table 6.

pp−0.1-0.1−0.05-0.05−0.01-0.01−0.001-0.001+0.001+0.001+0.01+0.01+0.05+0.05+0.1+0.1
GenPeel strictly better (out of 11)1011859111111
Median gain (%)6.490.170.070.000.037.486.214.93
Maximum gain (%)37.216.43.83.4747.9234.145.6106.1

Overall, GenPeel-pp-2PC is never worse: it is strictly better in 76 of 88 settings, with ties in the remaining 12. Gains exceed 10% in 18 settings and 100% in four. Ties are concentrated near p=0p = 0, consistently with Proposition 3, since the generalized removal rule converges to the ordinary net-balance rule as pp approaches zero.

W1(b). Hub-based solution

We agree that the hub-based solution should be evaluated under each finite-pp objective. We now report the value of Max-2PC-Exact evaluated under every finite pp considered (Table 5). This solution can outperform GenPeel-pp-2PC; for example, on WikiEle at p=0.01p = 0.01, it obtains 371.4 compared with 243.7 for GenPeel-pp-2PC, exceeding the lower bound of 367.8 established by Lemma 4.

pp−0.01-0.01−0.001-0.001+0.001+0.001+0.01+0.01
GenPeel-pp-2PC better (out of 11)111194
Hub solution better (out of 11)0027

All nine cases in which the hub solution is better occur on the seven largest networks. Lemma 4 certifies six of these cases. On small and medium-sized networks, GenPeel-pp-2PC is better for every tested pp; for example, on Word at p=0.01p = 0.01 it obtains 25.54, compared with 13.70 for the hub solution.

This difference is explained by the initialization: peeling never reassigns vertices, so the hub's neighbors retain the sides assigned by Eigen-Bipartition rather than being assigned according to their edge signs with the hub. Consistently, when GenPeel-pp-2PC is initialized with the hub seed, it returns exactly the hub value in these nine settings (Table 9). Following the reviewer's suggestion, we now recommend taking the better of the GenPeel-pp-2PC and Max-2PC-Exact solutions for p>0p > 0. This adds at most 13.2 seconds on our datasets and inherits the additive guarantee of Proposition 5.

W2. Proposition 1

We thank the reviewer for identifying the issue and for providing a counterexample. The statement in the submission was indeed trivial as written, while the stronger statement intended by the proof was false. As suggested by the reviewer, we replaced it with the following: for any fixed balanced bipartition (V1,V2)(V_1, V_2), there exists an optimal solution of the form {U∩V1, U∩V2}\lbrace U \cap V_1,\, U \cap V_2 \rbrace for some nonempty U⊆VU \subseteq V. The revised proof uses only the fact that assigning the selected vertices according to the fixed balanced bipartition does not decrease any vertex's net degree balance (Appendix B). Theorems 4 and 5 apply this proposition to the bipartition used in their respective reductions.

Q2. Balanced graphs for finite p>0p > 0

We adopted the reviewer's argument and added Theorem 5 (Section 4 and Appendix C), establishing polynomial-time solvability for every finite p>0p > 0 on balanced signed graphs. The result is proved in the exact real-arithmetic oracle model, which is now stated explicitly; the bit complexity remains open. The case of finite p<0p < 0 remains open because the relevant objective does not retain the required supermodularity or submodularity properties.

We would like to thank the reviewer once again for the very helpful comments; we hope to have addressed their concerns and remain available for any further clarification.

Thank you for the rebuttal. My concerns are sufficiently addressed. Updated the score.

Reviewer_Kxt5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies polarized community detection in signed networks. Specifically, it address the challenge of identifying different polarized structures that cannot be distinguished by average polarity alone. They introduce an exponential quasi-arithmetic mean of node-level net degree balances, with parameter (pp) controlling the emphasis on minimum, average, or maximum balance. This allows the objective to capture core-like polarized structures, communities polarized on average, and hub-driven structures. They present the study on computational complexity of the proposed problem and develop a generalized peeling algorithm for optimizing the finite-(pp) objective.

Critical strengths

The paper clearly motivates why high average polarity need not imply that all community members are strongly polarized.

The NP-hardness result for Core-2PC problem is useful.

The developed peeling algorithm considers the problem of selecting nodes for removal while accounting for changes in their neighbour balances.

Critical weaknesses

The algorithm first constructs a spectral partition and then applies peeling. Its performance depends on the quality of this initial partition, since peeling can remove nodes but cannot change their community assignments.

Experiments on synthetic data use equally sized communities. Performance when communities differ in size remains unclear.

The generalized peeling algorithm incurs substantial runtime overhead, while its improvement over ordinary peeling is relatively less certain cases.

The paper motivates polarization through agreement within two groups and disagreement between them, but in results there are cases with empty communities. Can authors clarify on its interpretations.

Questions for authors

Check weakness

4 comments
AuthorsOpenReview ↗

Response to Reviewer Kxt5 1/2

We sincerely thank the reviewer for the thoughtful and constructive comments. The revised manuscript addresses the concerns raised, as detailed below.

All section, table, and theorem numbers below refer to the revised PDF, where new and modified text is highlighted in blue; a summary of all revisions is posted in the general comment.

W1. Dependence on the spectral initialization

We agree that the peeling procedure only removes vertices; it does not change their community assignments. To quantify the effect of this limitation, we added a seed-sensitivity study (new RQ2, Table 2, and per-dataset results in Table 9). We evaluate three alternative initialization strategies: (i) perturbed Eigen-Bipartitions, obtained by independently flipping each vertex with probability ε\varepsilon; (ii) uniformly random bipartitions, with 30 trials per configuration; and (iii) the hub-based solution returned by Max-2PC-Exact. Table 2 reports EpE_p as a percentage of the value obtained from Eigen-Bipartition, averaged over the 11 real-world networks.

Initializationp→−∞p \to -\inftyp=−0.01p = -0.01p=0p = 0p=+0.001p = +0.001p=+0.01p = +0.01
ε=0.05\varepsilon = 0.0596.296.295.893.793.4
ε=0.2\varepsilon = 0.282.482.881.675.171.4
Random55.951.753.846.038.0
Hub (Max-2PC-Exact)62.864.163.169.599.3

The results show a gradual decline in solution quality as the initialization becomes less accurate. For p≤0p \le 0, flipping 5% of the vertices retains approximately 96% of the Eigen-Bipartition score, whereas a random seed retains approximately 52–56%. For p>0p > 0, the degradation can be more pronounced. Eigen-Bipartition is the best or is within 0.3% of the best tested seed in every setting with p≤0p \le 0. A better result is obtained with the hub seed in 9 of the 66 tested (dataset, pp) configurations; all nine cases occur for p>0p > 0 and on the seven largest graphs. In these cases, the returned value coincides with the hub solution, as discussed in our response to Reviewer rHKK (W1(b)).

During the development of the work, we also tested a greedy local-search post-processing step that allows vertices to move to the other community or to the neutral set. It produced no improvement in most configurations and relative gains below 1% in the remaining cases (see our response to Reviewer jz7x, W3).

W2. Communities of unequal sizes

The findings of the equal-size case do not change with unbalanced communities: finite pp still recovers both communities, including the smaller one, and the extremes show the same precision/size trade-offs. We have added an experiment with planted communities of unequal sizes, following the protocol of Aronsson and Chehreghani (2025) (Section 6, Figures 10–12, and Appendix K). The two planted communities contain 200 vertices in total, and their size ratio is varied as ρ=∣C2∣/∣C1∣∈{1,…,8}\rho = |C_2|/|C_1| \in \lbrace 1,\dots,8 \rbrace, from (100, 100) to (22, 178). We set the noise parameter to 0.4 and generate 10 graphs for each value of ρ\rho.

  • For every finite pp, the F1 score remains ≥0.985\ge 0.985 across all tested community-size ratios. The smaller community is recovered with recall ≥0.991\ge 0.991, and the imbalance factor of the output matches the planted one within 0.015, i.e., our methods do not favor balanced partitions.
  • For p→−∞p \to -\infty, precision is exactly 1 for every tested ratio, at the cost of lower recall.
  • For p→+∞p \to +\infty, the method over-expands and returns nearly balanced solutions (imbalance factor ≥0.975\ge 0.975), largely independently of the planted ratio.

These results show that recovery does not rely on the assumption of equally sized communities: for finite pp, the method remains robust as the size imbalance increases and recovers both communities, including the smaller one.

AuthorsOpenReview ↗

Response to Reviewer Kxt5 2/2

W3. Runtime versus improvement over ordinary peeling

Following the suggestion of Reviewer rHKK, we compared GenPeel-pp-2PC with ordinary net-degree peeling (the Greedy-2PC removal rule) on all 11 real-world networks and for all eight tested values of pp. Both algorithms start from the same seed and return the best intermediate solution according to EpE_p. Thus, the comparison isolates the effect of the vertex-removal rule (Table 6 and Appendix K).

GenPeel-pp-2PC is never worse than ordinary net-degree peeling: it is strictly better in 76 of the 88 settings, while the remaining 12 are ties. The improvement exceeds 10% in 18 settings. Examples include +747.9% on WikiPol (p=0.001p = 0.001), +234.1% on Bitcoin (p=0.01p = 0.01), +108.0% on WikiEle (p=0.01p = 0.01), and +37.2% on TwitterRef (p=−0.1p = -0.1). The comparison previously reported in the submission concerned only 16-node instances, where both methods are close to optimal.

We acknowledge that GenPeel-pp-2PC is computationally more expensive than ordinary peeling. The revised manuscript now provides a tighter analysis and new experiments showing that the algorithm scales to large graphs with up to approximately 1.2 million vertices and 34.7 million edges (see our response to Reviewer UJED, W2).

W4. Empty or highly unbalanced communities

As in the original 2PC formulation (Bonchi et al., 2019), feasibility requires only S1∪S2≠∅S_1 \cup S_2 \neq \emptyset; the objective imposes no lower bound on either community's size (Section 3). Consequently, an optimal solution may be highly unbalanced or one-sided, as already observed by Bonchi et al. (2019) and Gullo et al. (2026). A solution with S1=∅S_1 = \emptyset or S2=∅S_2 = \emptyset should be interpreted as identifying a single cohesive group for which the network does not provide a sufficiently strong opposing group under the objective.

This behavior is a property of the objective, rather than an artifact of our algorithms. The RH baseline returns community-size ratios of 202/1 on Slashdot, 270/1 on Epinions, 750/2 on WikiEle, and 572/2 on WikiPol (Table 7), closely matching Greedy-2PC at p=0p = 0. Varying pp can reveal a two-sided structure when one exists; for example, at p→+∞p \to +\infty we obtain 2518/31 on Slashdot and 8075/2641 on WikiPol, with agreement ratios of 0.910 and 0.832, respectively (Section 6).

We hope these additions address your concerns and would be glad to clarify further.

I thank the authors for the response. It address only some of my previous concerns. However, two key concerns remain largely unresolved. First, as acknowledged by the authors, performance degrades under noisy initial assignments, which may limit the robustness and practical applicability of the proposed method. Second, as also highlighted by reviewer jz7x, the method can incur substantially higher computational costs in certain scenarios. While the authors provide results from 88 additional experiments, the corresponding runtime values are not reported, making it difficult to assess the computational trade-off associated with these results. In particular, the reported runtime difference of approximately 7,000 seconds versus 124 seconds, representing roughly a 56× increase, is substantial and could be restrictive in practice. Given these remaining concerns, I will maintain my current score.

AuthorsOpenReview ↗

Follow-up response to Reviewer Kxt5

We sincerely thank the reviewer for taking the time to engage with our rebuttal. We are glad that our additional responses and experiments have addressed some of your concerns (W2 and W4). We address the remaining concerns below.

Seed initialization (W1). We respectfully clarify that noisy initial assignments do not arise when our method is used in practice. The seed is not a parameter of our method: our proposed GenPeel-pp-2PC (Algorithm 1) always starts from the seed provided by the Eigen-Bipartition algorithm (Algorithm 2), which is deterministic and computed from the graph (a discretization of the exact solution of the continuous relaxation of 2PC). A user therefore never runs it on noisy assignments. The perturbed and random seeds in RQ2 are stress tests to check whether Eigen-Bipartition is a good choice, and the provided results confirm it: perturbing it lowers the objective on average, and a random seed retains only 38–56% of its value (Table 2).

Running time (W3). We agree that the running times of these experiments should be reported. Table 6 in the revised PDF now reports, for each of the 88 settings, the additional running time of GenPeel-pp-2PC over net-degree peeling with EpE_p selection, next to the EpE_p gain, and App. K discusses the trade-off. The gain of GenPeel-pp-2PC exceeds 10% in 18 settings. The largest gains include (complete results in Table 6 of the revised paper):

DatasetppEpE_p gain over net-degree peelingExtra time (s)
WikiPol+0.001+747.9%+804
Bitcoin+0.01+234.1%+4.9
WikiEle+0.01+108.0%+23
Word+0.1+106.1%+4.4
TwitterRef−0.1+37.2%+197
Slashdot−0.1+30.1%+260

On all small and medium networks, the extra time is below 36 s in every setting. It grows to hours only on WikiConflict, where it still yields gains of up to 27.8%.

Finally, we note that polarized-community detection is typically an offline, exploratory analysis, where an additional running time of seconds to a few hours is affordable in exchange for substantially better solutions. GenPeel-pp-2PC also scales to much larger graphs: on augmented networks with up to 1.05M nodes and 34.7M edges, it completes for every tested pp in under 14 hours (Fig. 13 in the revised paper).

We hope this addresses the remaining concerns and would be glad to discuss further.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revisions and Responses to Reviewers

We sincerely thank the reviewers for their careful reading of our paper and for their constructive comments. These comments led to new experiments, refined analyses, and a theoretical result that settles a case left open in the submission; we believe these changes have substantially improved the paper. The revised PDF uploaded to OpenReview highlights new and modified text in blue. Below, we summarize the main changes; our point-by-point responses are posted under each review. Section, figure, table, theorem, proposition, and appendix numbers refer to the revised manuscript.

Summary of the main revisions

Experiments

  • Comparison of GenPeel-pp-2PC with ordinary net-degree peeling on all 11 real-world networks and for all eight tested values of pp. Both methods use the same initial seed and select the best intermediate solution according to EpE_p (Table 6 and Appendix K). This shows that the proposed exact marginal rule provides improvements on real networks: GenPeel-pp-2PC is never worse in terms of the objective EpE_p, is strictly better in 76 of 88 settings, and gains up to 747.9%. [Reviewer rHKK, Reviewer jz7x, Reviewer Kxt5]
  • Evaluation of the Max-2PC-Exact hub-based solution under each finite value of pp considered in the experiments (Table 5 and Appendix K). [Reviewer rHKK]
  • New sensitivity analysis of GenPeel-pp-2PC to its initialization, considering perturbed spectral bipartitions, random bipartitions, and the hub-based seed (new RQ2, Table 2, and per-dataset results in Table 9). This supports our choice of Eigen-Bipartition as the seed: perturbing it lowers the objective function value EpE_p on average, and a random seed retains only 38–56% of its value. [Reviewer Kxt5, Reviewer jz7x]
  • New scalability experiments on augmented Epinions and WikiConflict networks, reaching approximately 1.2 million vertices and 34.7 million edges across the two instances (Figure 13 and Appendix K). These show that GenPeel-pp-2PC completes on all instances and values of pp, up to 1.05M vertices and 34.7M edges, in under 14 hours, with runtime growing steadily with graph size. [Reviewer UJED]
  • New experiments with ground-truth communities of unequal sizes (Figures 10–12 and Appendix K). This shows that our methods effectively recover the ground-truth communities without relying on equal community sizes. [Reviewer Kxt5]

Theory and algorithms

  • Corrected the statement and proof of Proposition 1 (Section 4 and Appendix B). [Reviewer rHKK]
  • Added Theorem 5, establishing polynomial-time solvability on balanced signed graphs for every finite p>0p > 0, via Dinkelbach's method and Densest Supermodular Set; the case p<0p < 0 remains open (Section 4 and Appendix C). [Reviewer rHKK]
  • Provided a tighter running-time analysis of the proposed GenPeel-pp-2PC matching the implementation used in the experiments (Section 5 and Appendix E). [Reviewer UJED]
  • Clarified that, for p>0p > 0, choosing the better of the GenPeel-pp-2PC and Max-2PC-Exact solutions retains the additive guarantee of Proposition 5 (Section 5). [Reviewer rHKK, Reviewer jz7x]

Discussion

  • Expanded the discussion of one-sided and highly unbalanced solutions, including the interpretation of solutions in which one community is empty (Section 6). [Reviewer Kxt5]

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.