- 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 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 has. Also, it seems that the case is not interesting and finding the solution is trivial in this case. This makes me wonder if the is actually useful. I would appreciate clarification about this. Moreover, on the synthetic experiments it does not seem that a non-zero value of improves discovery of ground-truth communities.
-
To my understanding, the generalized peeling rule is , whereas the standard peeling rule is . This is a significant difference, and essentially means that your method will not scale to large graphs. Even for sparse graphs it would be , 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
Thank you for the response. It addresses my concerns and I have updated my score.
We thank the reviewer for the careful review and for raising concerns about the usefulness of p, 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 p
Our contribution is primarily theoretical and methodological. The parameter p 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→−∞ favors cohesive and selective communities, whereas p>0 can restructure the solution and reveal two-sided communities when the p=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→+∞. 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>0, taking the better of Max-2PC-Exact and GenPeel-p-2PC inherits the additive guarantee of Proposition 5.
Usefulness of finite p>0. Finite p>0 can return structures that differ from both p=0 and p→+∞: on WikiPol, p=0 yields a highly one-sided solution (546/2), whereas p=0.01 returns two larger communities (8061/2330), with agreement 0.914 vs. 0.832 at p→+∞ (Table 1). Moreover, the hub solution does not dominate GenPeel-p-2PC: at p=0.01, GenPeel-p-2PC obtains higher Ep on all four small and medium-sized networks below.
The hub solution wins only on large graphs with very high-degree hubs, where even a small p>0 makes the objective nearly hub-driven (see our reply to Reviewer rHKK, W1(b)).
Synthetic graphs. We agree that finite p does not improve F1 over p=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=0 objective (standard 2PC). Finite p preserves this recovery (F1 = 1 for η≤0.3, F1 ≥0.947 at η=0.5). The two extremes reveal trade-offs not captured by p=0, e.g., p→−∞ achieves precision 1 up to η=0.5, at lower recall.
W2. Complexity and scalability
The 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∣) (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 can approach ∣V∣∣E∣; the revision now acknowledges this limitation.
We also added scalability experiments (Figure 13), injecting ∣V∣/2 to 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-p-2PC completes on all instances and values of p; 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→−∞), 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=0 returns 110 words mixing unrelated antonym pairs, e.g., primary/secondary and superior/inferior (Figure 3). The extra runtime concerns only finite p=0, where GenPeel-p-2PC improves Ep 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.