Discovering Balance-Aware Polarized Communities in Signed Networks with Graph Neural Networks

Abstract

Signed graphs model interactions among users, where nodes represent individuals and edges are labeled as positive for friendly relationships and negative for antagonistic ones. The 2-Polarized-Communities (2pc) problem aims to identify two disjoint polarized communities in a signed network so as to satisfy three conditions: the majority of intra-community edges should be positive, the majority of intercommunity edges should be negative, and the ratio of edges satisfying these conditions to the number of nodes in the communities should be maximized. Existing 2pc methods sufer from two key limitations: () they rely on a single optimal solution to a continuous relaxation of the problem, later rounded to obtain the final pair of polarized communities, and ( ) the standard 2pc objective function does not impose any constraints on the balance between community sizes. In this paper, we discuss a method that addresses both limitations and introduce two key contributions: (i) a Graph Neural Network-based approach that systematically explores multiple suboptimal solutions to the relaxed 2pc problem, selecting the one that yields the best 2pc solution after rounding; and (ii) a generalization of the 2pc objective function which explicitly encourages size-balanced communities. Extensive experiments on real-world and synthetic signed graphs have shown the high accuracy of our approach, its superiority over existing methods, and the efectiveness of -polarity in producing high-quality, well-balanced polarized communities.

Keywords

• eol>polarization
• signed graphs
• graph neural networks

1. Introduction

The widespread use of modern social media has created a huge amount of online social interactions, fostered the formation of communities [ 1, 2, 3, 4 ] and facilitating discussions about a variety of topics. Users establish positive relationships such as friendships, agreements, and trust, as well as negative relationships such as foes, disagreements, and distrusts. The existence of such mixed interactions has led to an ever-growing polarization phenomenon, i.e., a division of the set of users into groups with opposite view on controversial topics (e.g., politics, religion).

Signed graphs are graphs whose edges are assigned either a positive or a negative label, denoting whether the interaction depicted by an edge is friendly or antagonistic, respectively [ 5 ]. Signed graphs are used to model a variety of data and study numerous (social) phenomena, such as emergence of polarized discussions in social media, or analysis of trust/distrust in review platforms [ 6, 7, 8, 9, 10 ]. Bonchi et al. [ 11 ] defined the 2-Polarized-Communities (for short, 2pc) problem on signed graphs, aiming to find two subsets of nodes, generally referred to as communities, such that there are (R1) mostly positive edges within each community and (R2) mostly negative edges between the two communities, and (R3) the subgraph induced by these two communities is as much dense as possible. Also, the two communities are required to be non-overlapping, but they do not necessarily need to cover the entire node set. The rationale of the latter is to comply the most with real-world situations, where polarized communities are concealed within a body of other graph nodes which do not (yet) have a strongly formed opinion, and, as such, they are neutral in terms of polarization.

Motivation. The above R1–R3 requirements for the 2pc problem are jointly pursued by maximizing a single objective function, termed polarity. Maximizing polarity is NP-hard [ 11 ], but a continuous relaxation of that problem is solvable in polynomial time. Existing methods rely on rounding (i.e., discretizing) the optimal solution of the relaxed problem, but this approach has two key limitations. First, deriving a solution to 2pc starting from the optimal solution of the relaxed problem may be limiting in terms of polarity as suboptimal solutions to the relaxed problem can lead to better solutions to 2pc after rounding. Second, polarity maximization does not require or foster size-balanced communities, often leading to one dominant and one nearly empty group, even when naturally balanced polarized communities exist. Identifying such balanced groups is crucial across various domains, from social media and politics to market research, as it fosters constructive debates, reduces echo chambers, and identifies harmful situations. Thus, methods that can detect balanced polarized communities are needed. Contributions. In this paper, we discuss our recent advancement [ 12 ] in the 2pc problem that properly addresses the above limitations. Our contributions are twofold. First, to address the first limitation and leveraging the recent success of Graph Neural Networks (GNNs) in graph learning tasks [ 13, 14, 15 ], we propose a novel GNN-based approach, dubbed Neural2PC, that systematically explores multiple suboptimal solutions to the relaxed problem, ultimately selecting the one that yields the best discrete 2pc solution after rounding. Second, to overcome the second limitation, we define a generalization of the polarity function, named -polarity that is designed to produce polarized communities that, depending on the setting of , can be either more balanced or larger than those yielded by standard polarity.

2. Preliminaries

Let = (, +, − ) be an undirected signed graph, where is a set of nodes, and +, − ⊆ × , + ∩− = ∅, are sets of positive and negative edges, respectively. We assign each node in a unique integer ID in 1, . . . , | | and use ∈ interchangeably for the node and its position, simplifying matrix/vector notation. A ∈ {−1, 0, 1} | |×| | is the signed adjacency matrix of , defined as A[, ] = 1 if (, ) ∈ +, A[, ] = −1 if (, ) ∈ − , and A[, ] = 0 otherwise.

Given a signed graph = (, +, − ), the 2-Polarized-Communities [ 11 ] problem (for short, 2pc) finds two disjoint subsets 1, 2 ⊆ of nodes such that (R1) there are as many positive edges and as few negative edges as possible within 1 and within 2; (R2) there are as many negative edges and as few positive edges as possible across 1 and 2; and (R3) there should be a large number of edges complying with (R1) and (R2) within 1 and 2 relative to the total number of nodes in these groups.

1 and 2 are regarded as polarized communities, i.e., groups of nodes which are cohesive in terms of both intra-group positive relationships (edges) and inter-group negative relationships. Nodes included into neither 1 nor 2, denoted as 0, form the set of neutral nodes. A partition {0, 1, 2} of can alternatively be represented by a (column) vector x ∈ {−1, 0, 1} | |, whose -th coordinate is x = 0 if ∈ 0, x = 1 if ∈ 1, and x = −1 if ∈ 2.

The above R1–R3 requirements are altogether encoded into a single function, termed polarity: Definition 1 (Polarity [ 11 ]). Given a vector x ∈ {−1, 0, 1} | | and a matrix A {−1, 0, 1} | |×| | , the polarity (x, A) of x with respect to A is defined as: ∈ (1) (x, A) = x⊤A x x⊤x .

The numerator of (·, ·) accounts for R1 and R2, while numerator and denominator altogether model R3. In this regard, note that x⊤x = |1 ∪ 2|. The 2pc problem is formulated as follows: Problem 1 (2pc [ 11 ]). Given a signed graph = (, +, − ) with signed adjacency matrix A, find x* =

arg max x∈{−1,0,1} | | (x, A).

Relaxing node-to-community assignments to be in [ −1, 1 ] results in the following problem: Problem 2 (2PC-relaxed [ 11 ]). Given a signed graph = (, +, − ) with signed adjacency matrix A, find z* = arg max (z, A),

z∈[ −1,1 ] | | where polarity (z, A) = z⊤A z/z⊤z of a vector z ∈ [ −1, 1 ] | | is defined as in Definition 1. State of the art in 2pc. 2pc is shown to be NP-hard, while 2PC-relaxed can be solved in polynomial time by finding the eigenvector of the signed adjacency matrix corresponding to the largest eigenvalue [ 11 ]. Bonchi et al. [ 11 ] exploit the latter to devise two approximation algorithms for 2pc. The first (deterministic) algorithm simply rounds the optimal solution z* to 2PC-relaxed as x* = sgn(z*), for all ∈ , where sgn(·) is the sign function. The second (randomized) algorithm sets, for all ∈ , x* = sgn(z*) if a Bernoulli experiment with success probability |z*| succeeds, otherwise x* = 0.

3. Related Work

Representation learning for signed graphs. Graph representation learning is the problem of assigning elements of a graph (e.g., nodes, edges, subgraphs) to numerical vectors (embeddings) such that the similarity between those elements in the graph is preserved in the embedding space. This field spans shallow methods, which optimize specific criteria (e.g., -hop reachability, random-walk co-occurrence) and deep approaches based on graph neural networks (GNNs) [ 16, 14 ]. Representation learning has been studied for signed graphs as well, both undirected [ 17, 18, 19, 20, 21 ] and directed [ 22, 23 ]. In this work, we regard signed graph representation learning as a building block of the proposed framework. Note that our approach is versatile w.r.t. the choice of graph representation learning model.

Clustering signed graphs has also received attention in the literature [ 24, 25, 26, 27, 28 ]. However, those methods require every node to be part of an output cluster, hence they are not designed to detect neutral nodes and left them out of evaluation, unlike our approach. Also, signed graph clustering methods optimize criteria other than polarity.

4. The Neural2PC approach

Overview. Unlike existing methods [ 11 ] which find the optimal solution z* to 2PC-relaxed (Problem 2) directly, we let a neural-network model – with parameters – produce a set {z | = 1, . . . , } of feasible solutions to 2PC-relaxed during multiple epochs 1, . . . , of training. All the various z are rounded in order to yield feasible discrete solutions x to 2pc. The best (in terms of polarity, Definition 1) of such x solutions is the definitive output.

The rationale of our approach is that it allows for exploring a variety of suboptimal solutions to 2PC-relaxed. This favors obtaining ultimate discrete solutions (after rounding) which exhibit higher polarity than the one derived by rounding the optimal solution to 2PC-relaxed. The goal is to find the model parameters that maximize the polarity of the (relaxed) solutions computed via (or, equivalently, minimize a loss defined based on the negative polarity). As parameter learning goes on, it is expected to get a deeper exploration of the space of relaxed solutions, and hence a higher likelihood of getting an efective discrete solution after rounding.

The proposed neural approach is named Neural2PC. A graphical illustration of its main components is shown in Figure 1. Next, we delve into its technical details.

Neural model. Our model takes as input a signed graph = (, +, − ), and a matrix H0 ∈ R| |× containing a -dimensional (real-valued) vector of features for every node. If such features are not available, H0 can be initialized by considering structural information derived from [ 17 ]. The first block of is a (-layer) signed GNN [ 17, 18, 19, 20, 21 ] sgnn(· ), with parameters sgnn. sgnn(· ) properly processes ’s topology and (possibly) node features H0, and outputs a matrix H ∈ R| |× = [h ∈ R ]∈ containing a hidden vector representation h of every node ∈ . This operation can be described as H = sgnn(, H0). Then, vector representations produced by sgnn(· ) feed into fully-connected neural-network linear layers nn(· ), with parameters nn. Ultimately, a tanh activation function is used to cast the (node-to-community assignment) scores for every node to the desired [ −1, 1 ] range (cf. Problem 2). This operation can be written as z = tanh(nn(H)). As a result, the overall model, with parameters = { sgnn, nn}, is as follows: (, H0) = tanh(nn(sgnn(, H0))), (2) Loss function. To optimize model parameters , we employ a loss function ℒ2PC defined as a combination of (the negative of) polarity (·, ·) and a regularization term. The latter enforces the model produce continuous scores that are as close as possible to the ultimately desired discrete {−1, 0, 1} scores. Specifically, we denfie the regularization term as the || · || 2 L2-norm of a vector ∈ R | |, whose entries [] , for all ∈ , are set to the diference min{|z[]|, 1 − |z[]|} between z[] and the closest valid discrete score. The intuition is that minimizing the norm of (together with the other loss component) is expected to produce the desired efect of yielding output continuous z scores not too far from the valid discrete ones.

Given z = (, H0), the signed adjacency matrix A of , and a hyperparameter ∈ R which weighs the importance of the regularization term, the ℒ2PC loss function is defined as: ℒ2PC(z, A, ) = −(z, A) + |||| Rounding. To round a continuous solution z ∈ [ −1, 1 ] | | onto a valid discrete x ∈ {−1, 0, 1} | | solution to 2pc, we borrow the procedure adopted by Bonchi et al. [ 11 ]. Specifically, given a threshold ∈ [ 0, 1 ] , for all ∈ , x[] = sgn(z[]) if |[]| ≥ , x[] = 0 otherwise. Let = {⌈z[]⌋ | ∈ } be a set of candidate thresholds, where ⌈·⌋ denotes approximating a real number at the -th decimal digit (we use = 3). In order to avoid sticking to a single , we follow [ 11 ], and try all the thresholds ∈ . Given a threshold ∈ , we yield a discrete solution x as follows: ∀ ∈ , x [] = sgn(z[]) if |z[]| ≥ ; 0 otherwise. The final solution corresponds to the discrete solution with highest polarity: round(z) = arg max x ∈ {x | ∈ } (x, A).

Algorithm. The algorithm we employ to produce a solution to 2pc simply consists in optimizing the = { sgnn, nn} parameters of the neural model end-to-end, via standard gradient descent, for a number of training epochs. Specifically, the algorithm alternates a forward phase, which produces a continuous solution z given the current parameters, and a backward phase, where parameters are updated via gradient descent, using the ℒ2PC loss function, with a certain learning rate . The continuous solution z yielded in every epoch is rounded according to the round(· ) procedure described above. The discrete rounded solution with the highest polarity score out of all the ones produced in the various epochs is ultimately output. Rounding and evaluating polarity in every epoch is necessary because the best discrete solution’s epoch is hard to predict in advance.

5. Balancing the size of the communities

A known issue with the polarity measure (Definition 1) is its bias toward size-imbalanced communities, sometimes leading to one dominant community and the other empty [ 11 ]. To address this, we propose -polarity, a generalized measure that promotes more balanced polarized (3) (4) communities by adjusting the parameter . We define -polarity by modifying the denominator of the polarity measure while keeping the numerator unchanged. Given a node-to-community assignment vector x ∈ {−1, 0, 1} | |, let 1 = ∑︀∈,x[]<0 |x[]| and 2 = ∑︀∈,x[]>0 x[] be the size of the two communities, with = max{1, 2}, = min{1, 2}. The denominator of the polarity measure is x⊤x = + , which can be rewritten as ( − ) + 2. The key idea behind -polarity is to weight the size imbalance term ( − ) by a factor > 0, leading to the following definition: Definition 2 (-polarity). Given a vector x ∈ {−1, 0, 1} | |, a matrix A ∈ {−1, 0, 1} | |×| | , and a real number > 0, the -polarity (x, A) of x with respect to A is defined as: (x, A) =

x⊤A x ( − ) + 2 .

(5)

For > 1 , the size-diference ( − ) term is amplified: maximizing enforces such a term to be small, encouraging balanced communities. For ∈ (0, 1) , the efect is reversed, while = 1 recovers standard polarity.

The relaxed version of -polarity replaces x with a continuous vector z ∈ [ −1, 1 ] | | in Equation (5). It can be integrated into Neural2PC by substituting (z, A) with (z, A) in the ℒ2PC loss (Equation (3)).

6. Experimental Methodology

Evaluation goals. We evaluated Neural2PC and competitors/baselines on (1) real datasets, and (2) synthetic datasets; (3) impact of diferent signed GNNs in Neural2PC; (4) runtimes of the considered methods; (5) an ablation study on the Neural2PC components; (6) efectiveness of the -polarity measure in yielding communities that are both size-balanced and high-quality. Real datasets. We selected publicly-available real-world signed graphs of varying sizes and types. Bitcoin [ 29 ] (5.9k nodes, 21.5k edges), Epinions [ 29 ] (131.6k nodes, 711.2k edges) are trust-distrust networks. Cloister [ 30 ] (18 nodes, 125 edges), Congress [ 30 ] (219 nodes, 521 edges), and HTribes [ 30 ] (16 nodes, 58 edges) are social networks. Larger networks include Slashdot [ 29 ] (82.1k nodes, 500.5k edges), a friend-foe network, TwitterRef [ 31 ] (10.9k nodes, 251.4k edges), a stance network, WikiCon [ 29 ] (116.7k nodes, 2.03M edges), an edit-conflict network, WikiEle [ 30 ] (7.1k nodes, 100.7k edges), a voting network, and WikiPol [ 31 ] (138.6k nodes, 715.9k edges), a political discussion network.

Synthetic datasets. We used synthetic signed graphs to test methods in recovering groundtruth polarized communities, generated by the modified signed stochastic block model (mSSBM) [ 32 ]. The model has three parameters: the total number of nodes , the size = |1| = |2| of the polarized communities, and a noise parameter ∈ [ 0, 1 ] , with polarized communities emerging when ≤ 2/3.

We used diferent synthetic graphs by varying number of nodes ( ), community size , and ∈ {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6}. For each configuration, we generated 10 diferent graphs. Competing methods. We compared our Neural2PC against state-of-the-art methods for polarized community detection and relevant baselines from related problems. Our primary competitors are Eigen and its randomized variant R-Eigen [ 11 ], as they address the same 2pc optimization problem.

We included Pivot, a baseline inspired by a correlation clustering algorithm [ 33, 34, 35 ] and Greedy [ 11 ], a method based on a 2-approximation algorithm for densest subgraph [ 36 ]. We also considered the signed graph clustering algorithms BNC [ 24 ], SPONGE [ 25 ], and SSSNet [ 26 ]. Experimental setting. We used SGDNET [ 18 ], SNEA [ 19 ] and SGNN [ 17 ] as GNN models for our Neural2PC. All signed GNN models were trained on CPUs with uniform settings: node embeddings size = 64, = 2 layers, the final embedding of a signed spectral embedding model [ 27 ] as the input feature matrix ( = 64) and default values for other parameters. Model training was carried out with the Adam optimizer for = 300 epochs, using grid search for the learning rate ∈ {0.01, 0.005, 0.001} and regularization factor ∈ {0.1, 0.01, 0.001} . Results are averaged over 30 runs.

7. Results

Results on real datasets. Table 1 reports the polarity values, along with the sizes of the two resulting polarized communities. Concerning Neural2PC, we only report the results obtained by the best-performing (in terms of polarity) graph representation learning method.

Neural2PC is generally the most competitive in polarity. The exceptions (Slashdot, WikiEle, WikiPol) occur when Greedy selects an overly dense subgraph as one polarized community, leaving the other empty—an undesirable outcome. In contrast, our method returns both nonempty communities with high polarity in WikiEle and WikiPol. Among competitors, Eigen and R-Eigen, achieve strong polarity, with Eigen outperforming R-Eigen. Pivot as well as BNC and SPONGE performs poorly, with the latter two often producing very imbalanced communities. SSSNet performs slightly better but still lags behind.

Results on synthetic datasets. We analyzed the average 1-scores and polarity scores over 10 synthetic graphs for each noise level , considering varying network sizes ( ∈ 250, 500, 1000, 2000) and community sizes ( ∈ 25, 50, 100, 200). Our experiments (results not shown) revealed that Neural2PC remains robust to increasing noise, consistently outperforming competitors in both 1-score and polarity.

Impact of diferent signed GNNs. We analyzed polarity and community size values yielded by Neural2PC using diferent signed GNN models (results not shown). Our experiments revealed that the polarity of the solutions provided by Neural2PC does not significantly change across the various GNNs, which indicates robustness of the approach in terms of this main component. Execution times. The average runtime performance of the methods was measured across the diferent runs (results not shown). The learning-based methods, SSSNet and Neural2PC, have the highest runtimes, primarily due to the number of training epochs (max = 300). Nonetheless, Neural2PC ’s per-epoch time is comparable to the fastest methods. Among the other methods, SPONGE performs best, followed by BNC and Eigen. R-Eigen is slightly slower than Eigen due to its randomized nature, while Pivot and Greedy are ineficient.

Ablation study. To assess the impact of Neural2PC components, we conducted an ablation study on two simplified versions of Neural2PC: (i) NN, which removes the sgnn (·) block, retaining only nn(·) , and (ii) Direct, which optimizes the z assignments by minimizing the ℒ2PC loss via projected gradient descent. For each variant, we measured (results not shown) polarity, solution size, and execution time. The full Neural2PC is crucial for optimal polarity across all datasets or at least matching Direct (TwitterRef, WikiEle). However, Direct is less eficient, requiring significantly more epochs (at least twice as many) than Neural2PC (and NN, too), as the latter leverages sgnn(·) to assigns more similar scores within communities, reducing the number of thresholds tested in rounding and improving eficiency. Also, Neural2PC and Direct yield larger communities than NN. Overall, the outcomes of this ablation study justify the need for all components of the Neural2PC framework. -polarity results. We analyzed the impact of on the size and quality of solutions found by Neural2PC using the -polarity loss. We tested multiple values above 1 (up to 20) and their reciprocals to explore a symmetric range below 1. Neural2PC consistently achieves (results not shown) the best -polarity. Higher leads to more balanced communities, while lower creates imbalance, sometimes leaving one community empty. Competing methods often yield highly unbalanced solutions. Overall, -polarity proves useful, allowing users to inspect and select the most suitable communities for their needs.

8. Conclusion

We discussed a recent advancement in 2pc [ 12 ], which relies on a GNN-based neural approach and introduces the notion of -polarity to improve the balance in the size of the polarized communities. Future work includes detecting more than two communities [ 32 ], leveraging clustering ensemble techniques [ 37, 38 ] and improving the training eficiency [39]. Acknowledgements: D. Mandaglio and A. Tagarelli are partly supported by the PNRR Future AI Research (FAIR) project (H23C22000860006, M4C21.3 spoke 9).

Declaration on Generative AI

The authors have not employed any Generative AI tools. 452–511. doi:10.1007/S10618-012-0266-X. [39] F. Scala, S. Flesca, L. Pontieri, Play it straight: An intelligent data pruning technique for green-ai, in: Proc. DS Conf., volume 15243, 2024, pp. 69–85. doi:10.1007/ 978-3-031-78977-9\_5.

References

[1] D. Mandaglio , A. Tagarelli , F. Gullo, In and out: Optimizing overall interaction in probabilistic graphs under clustering constraints , in: Proc. KDD Conf ., 2020 , pp. 1371 - 1381 . doi: 10 .1145/3394486.3403190.

[2] A. K. Ghoshal , N. Das , S. Das , Disjoint and overlapping community detection in small-world networks leveraging mean path length , TCSS 9 ( 2021 ) 406 - 418 .

[3] D. Mandaglio , A. Tagarelli , Dynamic consensus community detection and combinatorial multi-armed bandit , in: Proc. ASONAM Conf ., 2019 , pp. 184 - 187 . doi: 10 .1145/3341161. 3342910.

[4] D. Mandaglio , A. Tagarelli , A combinatorial multi-armed bandit based method for dynamic consensus community detection in temporal networks , in: Proc. DS Conf ., 2019 , pp. 412 - 427 . doi: 10 .1007/978-3- 030 -33778-0\_ 31 .

[5] F. Harary , On the notion of balance of a signed graph , Michigan Mathematical Journal 2 ( 1953 ) 143 - 146 .

[6] G. Beigi , J. Tang , H. Liu, Signed link analysis in social media networks , in: Proc. ICWSM Conf ., 2016 , pp. 539 - 542 .

[7] T. Derr , C. C. Aggarwal , J. Tang , Signed network modeling based on structural balance theory , in: Proc. CIKM Conf ., 2018 , pp. 557 - 566 .

[8] K. Yao , L. Chang , L. Qin , Computing maximum structural balanced cliques in signed graphs , in: Proc. ICDE Conf ., 2022 , pp. 1004 - 1016 .

[9] X. Zheng , D. D. Zeng , F. Wang , Social balance in signed networks , Inf. Syst. Frontiers 17 ( 2015 ) 1077 - 1095 .

[10] L. L. Cava , D. Mandaglio , A. Tagarelli , Polarization in decentralized online social networks , in: Proc. WebSci Conf ., 2024 . doi: 10 .1145/3614419.3644013.

[11] F. Bonchi , E. Galimberti , A. Gionis , B. Ordozgoiti , G. Rufo, Discovering polarized communities in signed networks , in: Proc. CIKM Conf ., 2019 , pp. 961 - 970 .

[12] F. Gullo , D. Mandaglio , A. Tagarelli , Neural discovery of balance-aware polarized communities , Mach. Learn . 113 ( 2024 ) 6611 - 6644 . doi: 10 .1007/S10994-024-06581-4.

[13] A. Tsitsulin , J. Palowitch , B. Perozzi , E. Müller, Graph clustering with graph neural networks , JMLR 24 ( 2023 ) 1 - 21 .

[14] L. Wu , P. Cui , J. Pei , L. Zhao , Graph Neural Networks: Foundations, Frontiers, and Applications , Springer Singapore, Singapore, 2022 .

[15] L. Zangari , D. Mandaglio , A. Tagarelli , Link prediction on multilayer networks through learning of within-layer and across-layer node-pair structural features and node embedding similarity , in: Proc. WWW Conf ., 2024 , pp. 924 - 935 . doi: 10 .1145/3589334.3645646.

[16] H. Cai , V. W. Zheng , K. C. Chang , A comprehensive survey of graph embedding: Problems, techniques, and applications , TKDE 30 ( 2018 ) 1616 - 1637 .

[17] T. Derr , Y. Ma , J. Tang, Signed graph convolutional networks , in: Proc. ICDM Conf ., 2018 , pp. 929 - 934 .

[18] H. Liu , Z. Zhang , P. Cui, Y. Zhang , Q. Cui , J. Liu, W. Zhu, Signed graph neural network with latent groups , in: Proc. KDD Conf ., 2021 , pp. 1066 - 1075 .

[19] Y. Li , Y. Tian , J. Zhang , Y. Chang , Learning signed network embedding via graph attention , in: Proc. AAAI Conf. , 2020 , pp. 4772 - 4779 .

[20] S. Wang , J. Tang , C. Aggarwal , Y. Chang , H. Liu, Signed network embedding in social media , in: Proc. SDM Conf ., 2017 , pp. 327 - 335 .

[21] J. Kim , H. Park , J.-E. Lee , U. Kang , Side: representation learning in signed directed networks , in: Proc. WWW Conf ., 2018 , pp. 509 - 518 .

[22] J. Huang , H. Shen , L. Hou , X. Cheng, SDGNN: learning node representation for signed directed networks , in: Proc. AAAI Conf. , 2021 , pp. 196 - 203 .

[23] J. Huang , H. Shen , L. Hou , X. Cheng, Signed graph attention networks , in: Proc. ICANN Work ., 2019 , pp. 566 - 577 .

[24] K.-Y. Chiang , J. J. Whang , I. S. Dhillon , Scalable clustering of signed networks using balance normalized cut , in: Proc. CIKM Conf ., 2012 , pp. 615 - 624 .

[25] M. Cucuringu , P. Davies , A. Glielmo , H. Tyagi , SPONGE: A generalized eigenproblem for clustering signed networks , in: Proc. AISTATS Conf ., 2019 , pp. 1088 - 1098 .

[26] Y. He , G. Reinert , S. Wang , M. Cucuringu, SSSNET: semi-supervised signed network clustering , in: Proc. SDM Conf ., 2022 , pp. 244 - 252 .

[27] J. Kunegis , S. Schmidt , A. Lommatzsch , J. Lerner , E. W. D. Luca , S. Albayrak , Spectral analysis of signed graphs for clustering, prediction and visualization , in: Proc. SDM Conf ., 2010 , pp. 559 - 570 .

[28] P. Mercado , F. Tudisco , M. Hein , Clustering signed networks with the geometric mean of laplacians , in: Proc. NIPS Conf ., 2016 , pp. 4421 - 4429 .

[29] J. Leskovec , A. Krevl , SNAP Datasets: Stanford large network dataset collection , http: //snap.stanford.edu/data, 2014 .

[30] J. Kunegis , KONECT - The Koblenz Network Collection, in: Proc. WWW Conf ., 2013 , pp. 1343 - 1350 . http://konect.cc.

[31] M. Lai , V. Patti , G. Rufo, P. Rosso , Stance evolution and twitter interactions in an Italian political debate , in: Proc. NLDB Conf ., 2018 , pp. 15 - 27 .

[32] R.-C. Tzeng , B. Ordozgoiti , A. Gionis , Discovering conflicting groups in signed networks , Proc. NIPS Conf . 33 ( 2020 ) 10974 - 10985 .

[33] N. Bansal , A. Blum , S. Chawla , Correlation clustering, Machine Learning 56 ( 2004 ) 89 - 113 .

[34] D. Mandaglio , A. Tagarelli , F. Gullo , Correlation clustering with global weight bounds , in: Proc. ECML PKDD Conf. , volume 12976 , 2021 , pp. 499 - 515 . doi: 10 .1007/ 978-3- 030 -86520-7\_ 31 .

[35] F. Gullo , D. Mandaglio , A. Tagarelli , A combinatorial multi-armed bandit approach to correlation clustering , DAMI 37 ( 2023 ) 1630 - 1691 . doi: 10 .1007/S10618-023-00937-5.

[36] M. Charikar , Greedy approximation algorithms for finding dense components in a graph , in: Proc. APPROX Work ., 2003 , pp. 84 - 95 .

[37] F. Gullo , A. Tagarelli , S. Greco , Diversity-based weighting schemes for clustering ensembles , in: Proc. SDM Conf., SIAM , 2009 , pp. 437 - 448 . doi: 10 .1137/1.9781611972795.38.

[38] F. Gullo , C. Domeniconi , A. Tagarelli , Projective clustering ensembles , DAMI 26 ( 2013 )