# discovering_conflicting_groups_in_signed_networks__93a56e54.pdf

Discovering conflicting groups in signed networks

Ruo-Chun Tzeng KTH Royal Institute of Technology rctzeng@kth.se

Bruno Ordozgoiti Aalto University bruno.ordozgoiti@aalto.fi

Aristides Gionis KTH Royal Institute of Technology argioni@kth.se

Signed networks are graphs where edges are annotated with a positive or negative sign, indicating whether an edge interaction is friendly or antagonistic. Signed networks can be used to study a variety of social phenomena, such as mining polarized discussions in social media, or modeling relations of trust and distrust in online review platforms. In this paper we study the problem of detecting k conflicting groups in a signed network. Our premise is that each group is positively connected internally and negatively connected with the other k 1 groups. A distinguishing aspect of our formulation is that we are not searching for a complete partition of the signed network; instead, we allow a subset of nodes to be neutral with respect to the conflict structure we are searching. As a result, the problem we tackle differs from previously-studied problems, such as correlation clustering and k-way partitioning. To solve the conflicting-group discovery problem, we derive a novel formulation in which each conflicting group is naturally characterized by the solution to the maximum discrete Rayleigh s quotient (MAX-DRQ) problem. We present two spectral methods for finding approximate solutions to the MAX-DRQ problem, which we analyze theoretically. Our experimental evaluation shows that, compared to state-of-the-art baselines, our methods find solutions of higher quality, are faster, and recover ground-truth conflicting groups with higher accuracy.

1 Introduction

Signed networks are graphs where each edge is labeled either positive or negative. The introduction of edge signs, which goes back to the 50 s, was motivated by the study of friendly and antagonistic social relationships [22]. The representation power of signed networks comes at the cost of significant differences in fundamental graph properties, and thus, algorithmic techniques employed to analyze unsigned networks are usually not directly applicable to their signed counterparts. These differences have spurred significant interest in a variety of analysis tasks in signed networks [20, 36] such as signed network embeddings [7, 24, 25, 39], signed clustering [8, 14, 27, 32], and signed link prediction [9, 28, 38, 41] in recent years.

In this paper we study the problem of detecting k conflicting groups in signed networks. In more detail, we are interested in finding a collection of k vertex subsets, each of which is positively connected internally, and negatively connected to the other k 1 subsets. In social networks where edge signs indicate positive or negative interactions, identifying conflicting groups may help in the study of polarization [1, 31, 40, 43], echo chambers [17, 19] and the spread of fake news [12, 35, 42].

Detecting k conflicting groups is challenging due to various reasons. First, conflicting groups are not simply dense subgraphs, so community-detection techniques for unsigned graphs are not effective. Second, in real applications we can expect a majority of the network nodes to be neutral with respect

34th Conference on Neural Information Processing Systems (Neur IPS 2020), Vancouver, Canada.

to the conflicting structure. As an example, consider a social network where a heated discussion is taking place between different political factions. Most users might not get involved in the quarrel, and thus their interactions are not necessarily consistent with this division. For this reason, methods for signed networks like correlation clustering and k-way partitioning may not be effective.

Our approach for detecting k-conflicting groups in signed networks extends the formulation of Bonchi et al. [4], to arbitrary values of k, addressing an open problem left in that work, which studied only the case k = 2. We argue that simply rounding the principal eigenvectors of the adjacency matrix might yield unsatisfactory results. Instead, we show that the proposed objective can be interpreted in terms of the Laplacian of a complete graph, and rely on the spectral properties of this matrix to derive a novel optimization framework, spectral conflicting group detection (SCG). By carefully examining the invariant subspaces of the aforementioned Laplacian, we reformulate the problem as a maximum discrete Rayleigh quotient (MAX-DRQ) objective, which is an APX-hard problem. We propose two algorithms, one deterministic, and one randomized with approximation guarantees. We show that the obtained approximation is essentially the best possible, when using the largest eigenvalue as an upper bound.

We perform an extensive set of experiments to compare the performance of our approach to that of multiple alternatives from the literature, on a variety of synthetic and real datasets. Our algorithms generally run faster, yield solutions of higher quality, and exhibit a better ability to find ground-truth groups than competing methods. In addition, we discuss how to select the number of groups k in practical scenarios.

2 Related work

Signed graph partition. Typical formulations partition the nodes of the signed graph into k sets so that intra-edges are mostly positive and inter-edges are mostly negative. This is a special case of k conflicting group detection with no neutral nodes. Spectral methods are competitive and we review several representatives here. The signed Laplacian has been used for clustering [27], but resulting clusters tend to behave like in unsigned spectral clustering [37]. k-way balanced normalized cut (BNC) was proposed to address the issue [8]. Signed Laplacians [8, 27] were recently generalized through matrix power means [32]. The state of the art method SPONGE [14] is based on a generalized eigenvalue problem for constrained clustering [13] and works well on sparse graphs and large k. All these methods partition the network and are ineffective in the presence of many neutral nodes.

Correlation clustering methods partition the entire network, but allow k to be unspecified. The standard objective [2, 5, 16, 6] counts the number of edges that agree (disagree) with the partition, i.e., positive (negative) intra-group edges and negative (positive) inter-group edges, and aims to maximize (minimize) agreement (disagreement). The problem is APX-hard for general graphs and has many variants. Giotis et al. [21] consider the case of fixed k and Puleo et al. [33] measure per-node error. Our work is inspired by a recent variant [4], which formulates the discrete eigenvector problem by maximizing the gap between agreement and disagreement with respect to the total size of two conflicting groups. They propose a randomized O( n)-approximation algorithm. However, their approach does not extend to k > 2, as the two groups are identified by the sign of the optimal vector. In fact, the discrete eigenvector problem is APX-hard and the best known result achieves an approximation guarantee of O(n1/3) using an SDP-based approach [3]. The latter SDP formulation cannot be extended to k > 2 as well. In this paper, we generalize the problem as MAX-DRQ and present two algorithms for k 2.

Antagonistic group mining focuses on the setting with two groups. These works can be divided into direct or indirect. Direct methods [18, 29, 30] search for structures such as bi-cliques or balanced triads. Indirect methods [45, 46] find frequent conflicting patterns in database transactions. These approaches cannot be easily extended to finding k > 2 conflicting groups.

To our knowledge, our only direct competitor is the KOCG method [11]. They formulate the problem as trace-maximization, where each group is represented as a simplex with nonzero entries indicating the participation of the nodes in the groups. However, their method finds conflicting groups only within local regions and is sensitive to initialization, often converging to local maxima. Our approach is fundamentally different and experimentally is shown to consistently outperform this baseline.

3 Preliminaries

We focus on simple undirected signed graphs. We denote G = (V, E) to be a signed graph, with E = E+ E consisting of the sets of positive edges E+ and negative edges E . The signed adjacency matrix of G is denoted by A { 1, 0, 1}n n with Ai,j being +1 if (i, j) E+, 1 if (i, j) E and 0 otherwise. We use n = |V | and m = |E| to indicate the number of nodes and edges of the signed graph G. We use E(V1, V2) to denote the set of edges between two subsets V1, V2 V , where V1, V2 are not required to be disjoint. We define E(V1) to be E(V1, V1), for any V1 V .

We consider the eigenvalues λ1(M) . . . λn(M) of a symmetric matrix M Rn n, arranged in non-increasing order and listed with multiplicities. We denote the corresponding eigenvectors v1(M), . . . , vn(M), with vi(M) associated with eigenvalue λi(M). By convention, v1(M) is the leading eigenvector and {v1(M), . . . , vi(M)} are the i principal eigenvectors.

We denote by In the identity matrix of size n n, and by Jn the n n matrix with all elements being 1. For a matrix M Rn n, we use Mi,: to indicate its i-th row, and M:,j to refer to its j-th column. We also use Mi:,j: to indicate the submatrix of M that consists of rows i to n, and columns j to n. We use tr( ) to denote the trace of a matrix, , F to denote the Frobenius product between two matrices, and , to denote the dot product between two vectors. We use θ(u, v) = arccos( u, v /( u 2 v 2)) [0, π] to indicate the angle between two nonzero vectors u, v Rn. Finally, we write [n] to denote the set {1, . . . , n}.

Note. All omitted proofs can be found in the supplementary material.

4 Problem formulation

Given a signed graph G = (V, E) and an integer k, our goal is to find k mutually-disjoint node sets S1, . . . , Sk V that have the following informally-stated properties:

Property 1 For all i, j [k], with i = j, the edges in E(Si) are mostly positive, whereas the edges in E(Si, Sj) are mostly negative.

Property 2 There should be a large number of interactions among the nodes of S1, . . . , Sk relative to the total number of nodes in these groups. In other words, the subgraph induced by S1, . . . , Sk should be as dense as possible.

Inspired by the formulation of Bonchi et al. [4], our objective function is also a variant of the correlation-clustering problem [2], but with certain differences that we discuss below. For a set of groups S1, . . . , Sk as a candidate solution, we quantify Property 1 by using the objective

f(S1, . . . , Sk) = X

(i,j) E(Sh) Ai,j + 1 k 1

h,ℓ [k] h =ℓ

(i,j) E(Sh,Sℓ) ( Ai,j). (1)

Compared to the standard objective of correlation clustering [2], which treats all edges equally, our objective in Equation (1) weighs an intra-group edge k 1 times more heavily than an inter-group edge. The rationale is as follows: suppose the group sizes and edge densities stay fixed as k increases. Since the number of inter-group edges grows quadratically with k and the number of intra-group edges grows linearly with k, the weighting in Equation (1) prevents the inter-group edges from dominating the objective. The value of (k 1) in the denominator is chosen so that our objective reduces to the standard case, i.e., the formulation of Bonchi et al. [4], when k = 2.

By introducing an indicator matrix X {0, 1}n k with Xi,j = 1 if node i Sj and 0 otherwise, our objective in Equation (1) can be rewritten as

f(S1, . . . , Sk) = A, XXT F A, XJk XT F A, XXT F

k 1 = A, XLk XT F

where Lk = k Ik Jk. The term XLk XT in Equation (2) captures explicitly the relationship between the k groups as (XLk XT )i,j is positive (negative) whenever nodes i and j are in the same (different) groups. Also, (XLk XT )i,j = 0 if either node i or node j does not belong to any of the groups.

Hence, the value of the Frobenius product A, XLk XT F quantifies Property (1) for the groups S1, . . . , Sk (which are encoded in matrix X).

Next, we analyze the matrix Lk, which is a fixed matrix not depending on the input signed graph. Let Lk = UDU T be the eigendecomposition of Lk, where D = diag([0, k, . . . , k]) Rk k, and U Rk k is a real-valued orthogonal matrix. As the geometric multiplicity of eigenvalue k is k 1, the matrix U is not unique. For the rest of the paper, we restrict our choice of U to be the following

(U:,1)T = 1/

k [1, . . . , 1], (U:,2)T = c1 [k 1, 1, . . . , 1], (U:,3)T = c2 [0, k 2, 1, . . . , 1], . . . (U:,k)T = ck 1 [0, . . . , 0, 1, 1], (3)

where ci = 1/ p

(k i + 1)(k i), for i = 1, . . . , k 1.

By the change of variables Y = XU, we can rewrite our objective in Equation (2) as A, XLk XT F = A, Y diag([0, k, . . . , k])Y T F = k tr((Y:,2:)T A(Y:,2:)). (4) To account for Property (2) we normalize our objective with the total number of nodes in the groups S1, . . . , Sk, which can be written as X

i [k] |Si| = tr(Y T Y ) = k (Y:,1)T (Y:,1) = k k 1 tr((Y:,2:)T (Y:,2:)). (5)

Finally we replace the constraints on the indicator matrix X with the constraint that the rows of Y should take values in the set {0, U1,:, . . . , Uk,:}. The equivalence holds since Xi,: picks the j-th row of U if i Sj. Putting all this together, we can now give the final formulation of our problem:

max Y Rn k\{0} tr((Y:,2:)T A(Y:,2:))

tr((Y:,2:)T (Y:,2:)) , (6)

subject to Yi,: {0, U1,:, . . . , Uk,:}, for all i = 1, . . . , n.

Intuitively, our objective aims to find small-size conflicting groups with many edges satisfying Property (1). Note that if we ignore the weighting between the inter-group and intra-group edges, Equation (6) can be expressed as (#{edges satisfying Property (1)} #{edges violating Property (1)}) divided by | h [k] Sh|.

Also, note that our optimization problem, as formulated above, is different from the tracemaximization problem [26], which given two n n matrices M and A, seeks to find an n d matrix Z to maximize the form tr(ZT AZ), subject to the constraint ZT MZ = Id. The reason is that since we have no constraint on the group sizes, there is no predefined matrix M to require XT MX = Ik.

5 Proposed spectral approach

The problem we study has been shown to be APX-hard for the special case of k = 2 [3]. Here we consider a generalization for any k 2. In this section we present an efficient spectral algorithm by leveraging the problem formulation (6).

Our starting point is that matrix U, as seen in Equations (3), is almost lower-triangular. We can use this observation to partition Y:,2: column-wise, and reformulate the constraints in problem formulation (6) as follows:

Y:,2 {0, c1, c1(k 1)}n implies Yi,2 = c1(k 1) if i S1, c1 if i k h=2Sh,

Y:,3 {0, c2, c2(k 2)}n implies Yi,3 =

0 if i S1, c2(k 2) if i S2, c2 if i k h=3Sh,

Y:,k {0, ck 1, ck 1}n implies Yi,k =

0 if i k 2 h=1Sh, ck 1 if i Sk 1, ck 1 if i Sk.

Algorithm 1: SCG (A, k) Spectral Conflicting Group detection Input :A is the adjacency matrix of the signed network; k is the number of groups. Output :Groups S1, . . . , Sk. A(0) A; for t = 1, . . . , k 1 do

r(t) Solve-Max-DRQ (A(t 1), k t) ; // See Algorithm 2 if t < k 1 then

St {i / t 1 j=1Sj : |r(t) i | = (k t)}; A(t) A(t 1); A(t) i,: 01 n and A(t) :,i 0n 1 for all i St ; // Remove edges E(St, V )

else Sk 1 {i / t 1 j=1Sj : r(t) i = 1} and Sk {i / t 1 j=1Sj : r(t) i = 1} ; end return S1, . . . , Sk;

Notice that Yi,j = 0 for all i j 2 h=1Sh and Yi,j = cj 1 for all i k h=j Sh. We let A(0) = A, and we define A(t) to be the adjacency matrix that results after removing from A(t 1) all entries that correspond to edges incident to nodes in St. Then, the objective function (6) is equivalent to

tr((Y:,2:)T A(Y:,2:))

tr((Y:,2:)T (Y:,2:)) =

t=1 wt (Y:,t+1)T A(Y:,t+1)

(Y:,t+1)T (Y:,t+1) =

t=1 wt (Y:,t+1)T A(t 1)(Y:,t+1)

(Y:,t+1)T (Y:,t+1) , (7)

where wt = (Y:,t+1)T (Y:,t+1)/tr((Y:,2:)T (Y:,2:)) [0, 1] and Pk 1 t=1 wt = 1. In other words, Equation (7) shows that the objective function (6) is a convex combination of k 1 discrete Rayleigh quotients. Moreover, Equation (7) also suggests that the solution Y:,t+1 characterizes the group St that conflicts the most with the (not yet decided) rest of groups Sh for h > t. Based on this observation, we propose a scheme SCG (spectral conflicting groups), shown as Algorithm 1.

SCG executes k 1 iterations. At the t-th iteration, for each t [k 1], we find the vector Y:,t+1 that maximizes the discrete Rayleigh quotient of A(t 1), while satisfying the constraints set on matrix Y . We refer to this problem as MAX-DRQ:

r(t) = argmax x {0, 1,k t}n\{0}

x T A(t 1)x

x T x . (8)

The vector Y:,t+1 is then given by Y:,t+1 = ct r(t). We note that our scheme works with any method that solves the MAX-DRQ problem. In Algorithm 1 (SCG) we refer to such a general method as Solve-Max-DRQ. Strategies to solve MAX-DRQ are presented in Section 6. Once the MAX-DRQ problem is solved in the t-th iteration, the vector r(t) is obtained. If t < k 1, the t-th group is recovered by St = {i / t 1 j=1Sj : |r(t) i | = (k t)}, and if t = k 1 (last iteration), the last two groups

are recovered by Sk 1 = {i / t 1 j=1Sj : r(t) i = 1} and Sk = {i / t 1 j=1Sj : r(t) i = 1}.

Note that Equation (7) justifies why it is not a good idea to use the k 1 principal vectors of A to identify the conflicting groups: the reason is that the coefficients [wt] are not fixed values.

6 Solving the maximum discrete Rayleigh quotient problem

In this section we present two solutions for MAX-DRQ. Our first solution is a deterministic algorithm presented in Section 6.1. The second solution is a randomized algorithm presented in Section 6.2. Both solutions first compute the leading eigenvector v1 of the input matrix A(t 1), and then round v1 to the appropriate discrete form. The difference is the rounding method. We refer to this generic algorithm as Solve-Max-DRQ, and it is the procedure used in the iterative step of SCG. Pseudocode for Solve-Max-DRQ is given as Algorithm 2.

Algorithm 2: Solve-Max-DRQ (A, q) Find maximum discrete Rayleigh quotient Input :Square and symmetric matrix A, and positive integer q. Output :The rounded vector r {0, 1, q}n. v the leading eigenvector of A; (d1, r1) Round(v, q) ; // d1 = sin θ(v, r1) (d2, r2) Round( v, q) ; // d2 = sin θ( v, r2) if d1 d2 then r r1; else r r2; return r;

Algorithm 3: Min Angle Round (v, q) Deterministic rounding by minimum-angle heuristic Input :Vector v Rn and positive integer q. Output :Vector u {0, 1, q}n with min angle to v. {ik}n k=1 Sort v and return the indexes such that vi1 . . . vin; (d, u ) ( , 0); (k1, k2) (0, n + 1); while k1 < k2 do

u1 set the ik1+1-th element of u to q; u2 set the ik2 1-th element of u to 1; if min{sin θ(v, u1), sin θ(v, u2)} d then break; if sin θ(v, u1) < sin θ(v, u2) then (k1, d, u ) (k1 + 1, sin θ(v, u1), u1); else (k2, d, u ) (k2 1, sin θ(v, u2), u2); end return (d, u );

6.1 Deterministic rounding

Our goal is to find a discrete vector v {0, 1, q}n that maximizes the quotient x T A(t 1)x/(x T x). Let v be the leading eigenvector of A(t 1), i.e., the real-valued maximizer of x T A(t 1)x/(x T x). The idea is to round v to a discrete vector u {0, 1, q}n that minimizes sin θ(v, u), among all vectors u {0, 1, q}n. It can be shown that such u can be found by restricting the search over O(n2) thresholded candidate vectors obtained by v. We formalize this below.

Definition 1 Let v Rn, q [k 1] and a, b R be given. Define a threshold function σa,b : Rn Rn that maps v to a new vector σa,b(v), whose i-th coordinate is

q if vi a > 0, 1 if vi b < 0, 0 otherwise,

and denote T = {ti}n+1 i=0 the sequence of all possible thresholds over the coordinates of v, that is, t0 = , tn+1 = and ti is the i-th largest coordinate of v, for i [n]. Then, the set of all possible thresholded vectors of v is denoted by Γ(v) = {σa,b(v) : for all a, b T }.

Given a vector v, the discrete vector u {0, 1, q}n that minimizes sin θ(v, u) can be computed by using the following result.

Lemma 1 Let v Rn and q [k 1] be given. The minimizer of sin θ(v, u) over all u {0, 1, q}n is equal to the minimizer of sin θ(v, u) over all u Γ(v) Γ( v).

Since the size of the set Γ(v) Γ( v) is O(n2), enumerating all vectors to find the optimal u is not efficient for large datasets. To make our method scalable, we propose a linear-time rounding heuristic in Algorithm 3, which finds a local optimum.

This heuristic works by initializing two indexes k1, k2, the indexes of the two thresholds, which are initially set to 0 and n + 1, respectively. At each iteration, we move only 1 threshold, we either increase k1 by 1 or decrease k2 by 1. This is determined by comparing sin θ(v, σtk1+1,tk2(v)) and sin θ(v, σtk1,tk2 1(v)) and choosing the smaller option.

Algorithm 4: Random Round (v, q) Randomized rounding Input :Vector v Rn and positive integer q. Output :Vector u {0, 1, q}n, a randomized rounded vector of v. u 0; for i = 1, . . . , n do

if vi > 0 then ui q Bernoulli(|vi|/q) ; else if vi < 0 then ui ( 1) Bernoulli(|vi|) ; end d sin θ(v, u); return (d, u);

6.2 Randomized rounding

Our second algorithm for maximizing x T A(t 1)x/(x T x) in {0, 1, q}n is a randomized-rounding scheme starting with the eigenvector v of A(t 1). Pseudocode is shown in Algorithm 4.

In more detail, we round v onto {0, 1, q}n by drawing Bernoulli trials. For each positive coordinate vi we set ui q Bernoulli(|vi|/q), for each negative coordinate vi we set ui ( 1) Bernoulli(|vi|), and if vi = 0 we set ui = 0. In this way, we have E[u] = v. By applying similar arguments to the ones presented by Bonchi et al. [4], we can show that the randomized-rounding algorithm provides a O(q n)-approximation guarantee to the MAX-DRQ problem. We present this result as Theorem 1. Furthermore, Corollary 1 states that this result is tight for k = 2.

Theorem 1 Let v be the leading eigenvector of the adjacency matrix A of a signed graph, and let q 1 be a positive integer. Then, the Random Round algorithm with (v, q) as input is a (q n)- approximation to the optimum of the corresponding MAX-DRQ problem.

Lemma 2 Let OPT be the optimum solution to the MAX-DRQ problem. There exists a problem instance such that λ1(A) OPT Ω( n).

Corollary 1 The integrality gap of algorithm Random Round is Ω( n), and thus, the approximation result of Theorem 1 is asymptotically tight up to a factor of q.

7 Experimental evaluation

In this section, we evaluate our framework with both synthetic and real-world graphs. All the experiments are executed on a machine with Intel Core i5 at 1.8 GHz with 8 GB RAM. All methods have been implemented in Python 3.1 The datasets we have used are all publicly available and the detailed information can be found in Supplementary D.1. Beyond the experiments discussed here, we present more results in Supplementary D, including execution times, and a discussion on deciding the number of groups k.

Proposed methods. Our approach (SCG) is a framework that admits different methods to solve MAX-DRQ. We have instantiated our framework with the following routines. Minimum angle: the deterministic rounding algorithm presented in Section 6.1; Randomized rounding: the randomized rounding algorithm presented in Section 6.2; Maximum objective: a generalization of Eigen Sign [4], that rounds v1(A) by finding an optimal threshold to maximize the objective; Bansal: motivated by the pivot for correlation clustering [2], which finds two conflicting groups by considering the neighborhood of a single node, and using the node that results in the maximum value of the objective. These instantiations are denoted by SCG-MA, SCG-R, SCG-MO, and SCG-B, respectively.

Baselines. We use the following baselines: KOCG [11] is a method designed for a similar formulation to ours. We use the authors implementation [10] with default hyperparameters α = 1/(k 1), β = 50, and ℓ= 5000. As KOCG returns a ranked list of disjoint subgraphs, each containing k conflicting groups, we pick the k groups contained in their top-1 and top-r subgraphs. We choose r so that the total group size equals the one returned by SCG-MA. We use two spectral algorithms: BNC [8], which optimizes balanced normalized cut; and SPONGE [14], a method particularly suitable

1https://github.com/rutzeng/SCG-Neur IPS2020.

Table 1: Polarity objective (Equation (6)) achieved by the proposed methods and the baselines on real-world signed graphs, for two different values of k: the number of conflicting groups to be detected. Dashes indicate that a method exceeded the memory limit.

Wo W-EP8 Bitcoin Wiki Vot Referendum Slashdot Wiki Con Epinions Wiki Pol

|V | 790 5 881 7 115 10 884 82 140 116 717 131 580 138 587 |E| 116 009 21 492 100 693 251 406 500 481 2 026 646 711 210 715 883 |E |/|E| 0.2 0.2 0.2 0.1 0.2 0.6 0.2 0.1

k = 2 SCG-MA 236.6 28.8 71.5 172.2 77.5 155.2 128.3 82.8 SCG-MO 236.6 29.5 71.7 174.1 79.7 175.7 128.7 88.4 SCG-B 200.6 21.7 37.6 116.3 61.0 129.3 156.4 46.5 SCG-R 218.3 14.9 55.7 119.6 29.9 100.2 70.9 36.0 KOCG-top-1 9.0 3.6 4.0 4.3 1.0 6.2 4.2 1.0 KOCG-top-r 18.2 3.8 2.5 14.0 3.7 2.4 6.2 0.9 BNC-k 184.6 5.3 15.8 41.5 BNC-(k + 1) -0.7 -10.8 -1.0 -1.0 SPONGE-k 191.4 5.1 15.8 41.5 SPONGE-(k + 1) 88.0 1.0 1.0 1.0

k = 6 SCG-MA 207.3 14.6 45.5 84.9 37.8 102.6 88.8 57.5 SCG-MO 226.9 15.2 47.0 55.6 34.6 111.6 129.2 41.8 SCG-B 211.6 9.3 23.3 116.2 47.7 46.1 94.5 46.0 SCG-R 198.1 5.0 9.7 39.8 7.3 16.2 39.4 5.5 KOCG-top-1 7.0 4.4 5.5 8.8 2.6 4.5 8.7 4.8 KOCG-top-r 8.5 2.9 2.9 5.0 3.6 4.0 6.5 3.0 BNC-k 185.2 5.2 15.8 41.5 BNC-(k + 1) -0.2 -4.2 -1.1 -0.8 SPONGE-k 58.5 5.0 15.8 41.5 SPONGE-(k + 1) 48.1 0.8 1.0 1.0

for sparse graphs and large k. To detect k conflicting groups using the spectral clustering algorithms, we compare with two approaches. The first approach is to directly apply BNC and SPONGE to detect k clusters and return all the detected clusters as conflicting groups. The second approach is to detect (k + 1) clusters, then heuristically treat the largest cluster as the non-conflicting cluster, and return the k smallest clusters as the detected conflicting groups. Let BNC-k and SPONGE-k denote SPONGE and BNC with the first approach and let BNC-(k + 1) and SPONGE-(k + 1) denote the two with the second approach. We use a publicly-available implementation [15] for BNC and SPONGE.

Results on real-world networks. We first measure the quality of the proposed methods and baselines with respect to the polarity objective, i.e., Equation (6), on real-world signed graphs. The results are shown in Table 1. The running times of all methods are listed in Supplementary D.2. We observe that mostly, SCG-MA and SCG-MO achieve the best polarity scores. They are also the fastest, and usually find larger groups. An example of the sizes of the groups found by all methods is given in Supplementary D.3. The SCG-B algorithm identifies conflicting groups by exploring local neighborhoods, and its detected groups tend to be located around high-degree nodes. Although SCG-B achieves the largest polarity on Referendum for k = 6, it only detects 2 groups, already covered by SCG-MA and SCG-MO. As the groups are not necessarily the high-degree nodes, SCG-B performs less competitive on Wiki Vot and Wiki Con for k = 6. Finally, SCG-R is not as competitive as SCG-MA or SCG-MO and is slower due to random sampling.

With respect to our direct competitor KOCG, the KOCG-top-1 variant performs slightly better than KOCG-top-r when k = 6. As KOCG finds groups in local regions, KOCG-top-1 returns much smaller groups than the other methods. On the contrary, KOCG-top-r intersects several local groups in different graph regions but remains ineffective compared to SCG-MA under the same total group size. All KOCG settings perform worse than BNC and SPONGE on the first 4 datasets.

Finally, the spectral-clustering methods BNC and SPONGE exceed the memory limit (caused by k-means) on large datasets. The k groups returned by BNC-k and SPONGE-k usually consist of one large group with many non-conflicting nodes and k 1 very small groups. Since BNC-(k + 1) and SPONGE-(k + 1) can use the spare cluster to put the non-conflicting nodes, we expect they perform better than BNC-k and SPONGE-k but it turns out to be worse on all 4 real-world networks. Despite of the unexpected results, both versions of BNC and SPONGE are less effective than SCG-MA and SCG-MO at finding conflicting groups in real-world graphs.

Results on synthetic graphs. In our second experiment, we use synthetic graphs to measure how well the methods recover ground-truth conflicting groups. We use the modified signed stochastic

0.0 0.1 0.2 0.3 0.4 0.5 0.6

(a) F1-Score vs

0.0 0.1 0.2 0.3 0.4 0.5 0.6

(b) Polarity vs

SCG-MA SCG-MO SCG-B SCG-R KOCG-top-1 KOCG-top-r BNC-k BNC-(k+1) SPONGE-(k+1) SPONGE-k Ground Truth

Figure 1: F1-score (left) and polarity score (right) as a function of the parameter η. The input signed graphs are generated by the m-SSBM model, for a graph of size n = 2 000, with k = 6 ground-truth groups, each having size ℓ= 100.

block model (m-SSBM) [4], which has 4 parameters; n: the graph size; k: the number of conflicting groups; ℓ: the size of each of the conflicting groups (all have the same size); and η [0, 1]: a parameter that controls the edge probabilities. Edges in the same group are positive with probability 1 η and negative or absent with probability η/2. Edges between distinct groups are negative with probability 1 η and positive or absent with probability η/2. All other edges have equal probability of min(η, 1/2) of being positive or negative. Hence, the smaller the value of η, the denser the conflicting groups and the lower the noise level. Note that the conflicting groups only emerge when η 2/3, since m-SSBM is expected to have more negative edges in the groups and more positive edge between groups if η > 2/3.

In this experiment we measure the recovery rate of the ground-truth groups using the F1 score, with precision and recall averaged over all groups. In Figure 1 we report the results of the m-SSBM model with parameters n = 2 000, k = 6, ℓ= 100, and η = 0 : 0.1 : 0.6. Each setting is repeated 20 times, and we report the average F1 score and polarity scores.

As seen in Figure 1, the recovery rate (F1 score) for all methods declines with η, since the graph becomes sparser and more noisy. It is clear that SCG-MA and SCG-MO are robust methods, handling very well the increasing noise level. It is worth noting that SPONGE-(k + 1) performs the best in this experiment with respect to both F1 and polarity. We also see that SCG-B is less competitive here, as in this data the conflicting groups are not concentrated around high-degree nodes. In summary, under the m-SSBM model, our polarity score is consistent with the F1 score, and our proposed methods SCG-MA and SCG-MO are effective in detecting the ground-truth conflicting groups.

8 Conclusions and future work

We propose an efficient method for detecting k conflicting groups in a signed network. Our approach relies on interpreting the problem objective in terms of the Laplacian of a complete graph, characterizing the spectral properties of this matrix, and deriving a novel formulation in which each conflicting group is characterized by the solution to the maximum discrete Rayleigh quotient problem.

Our work opens several exciting directions for future work. First, it remains open whether we can improve the O( n)-approximation for the maximum discrete Rayleigh quotient problem, using an approach that does not rely on rounding the leading eigenvector, such as by extending the SDP-based algorithm in [3]. Second, it would be interesting to explore the applicability of our approach to unsigned graphs for the task of detecting dense subgraphs. Third, the modified Stochastic Block Model (m-SSBM) is actually a special case of Label Stochastic Block Model (LSBM) [23]. It would be relevant to analyze the recovery guarantee of our proposed method in m-SSBM with respect to the fundamental limit results [44] and the interplay with the Bethe-Hessian operator [34] in the sparse regime. Finally, the difference in the empirical performance of our two rounding techniques and the spectral clustering baseline SPONGE [14] in the real-world networks and the synthetic network is somewhat striking. It is possible that some properties or structures exist in the real-world networks but not in the synthetic networks. An interesting question is to explain this behavior analytically, in particular with respect to properties of real-world networks.

Acknowledgments

We thank the anonymous reviewers for their insightful feedback. We thank Stefan Neumann for pointing to us the work of Bhaskara et al. [3]. This research is supported by the Academy of Finland projects AIDA (317085) and MLDB (325117), the ERC Advanced Grant REBOUND (834862), the EC H2020 RIA project So Big Data (871042), and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

Broader Impact

As the task we tackle in this paper belongs to the broad category of data mining, and as our study is mainly of theoretical nature, the impact of our work to the society is indirect. With respect to positive consequences, we name two possible applications that could impact the modern society. First, the rise of polarization and fake news is related to the existence of conflicting groups. Thus, having an efficient characterization tool is the first step to mitigate the situation. Second, both collaboration and competition exist in a diverse environment and detecting conflicting groups helps to understand the interplay of the two. With respect to negative consequences, we do not foresee specific issues when applying our method.

[1] Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: divided they blog. In Proc. of Link discovery workshop, 2005.

[2] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 2004.

[3] Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, and Aravindan Vijayaraghavan. On quadratic programming with a ratio objective. In Proc. of ICALP. Springer, 2012.

[4] Francesco Bonchi, Edoardo Galimberti, Aristides Gionis, Bruno Ordozgoiti, and Giancarlo Ruffo. Discovering polarized communities in signed networks. In Proc. of CIKM, 2019.

[5] Moses Charikar and Anthony Wirth. Maximizing quadratic programs: Extending grothendieck s inequality. In Proc. of FOCS, 2004.

[6] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. Journal of Computer and System Sciences, 2005.

[7] Yiqi Chen, Tieyun Qian, Huan Liu, and Ke Sun. " bridge" enhanced signed directed network embedding. In Proc. of CIKM, 2018.

[8] Kai-Yang Chiang, Joyce Jiyoung Whang, and Inderjit S Dhillon. Scalable clustering of signed networks using balance normalized cut. In Proc. of CIKM, 2012.

[9] Kai-Yang Chiang, Cho-Jui Hsieh, Nagarajan Natarajan, Inderjit S Dhillon, and Ambuj Tewari. Prediction and clustering in signed networks: a local to global perspective. JMLR, 2014.

[10] Lingyang Chu. Source code: Finding gangs in war from signed networks. https://github. com/lingyangchu/KOCG.SIGKDD2016, 2016.

[11] Lingyang Chu, Zhefeng Wang, Jian Pei, Jiannan Wang, Zijin Zhao, and Enhong Chen. Finding gangs in war from signed networks. In Proc. of KDD, 2016.

[12] Nicole A Cooke. Fake news and alternative facts: Information literacy in a post-truth era. American Library Association, 2018.

[13] Mihai Cucuringu, Ioannis Koutis, Sanjay Chawla, Gary Miller, and Richard Peng. Simple and scalable constrained clustering: a generalized spectral method. In Proc. of AISTATS, 2016.

[14] Mihai Cucuringu, Peter Davies, Aldo Glielmo, and Hemant Tyagi. Sponge: A generalized eigenproblem for clustering signed networks. In Proc. of AISTATS, 2019.

[15] Peter Davies and Aldo Glielmo. Signet: A package for clustering of signed networks. https: //github.com/alan-turing-institute/signet, 2019.

[16] Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica. Correlation clustering in general weighted graphs. Proc. of STOC, 2006.

[17] Seth Flaxman, Sharad Goel, and Justin M Rao. Filter bubbles, echo chambers, and online news consumption. Public opinion quarterly, 2016.

[18] Ming Gao, Ee-Peng Lim, David Lo, and Philips Kokoh Prasetyo. On detecting maximal quasi antagonistic communities in signed graphs. Data mining and knowledge discovery, 2016.

[19] R Kelly Garrett. Echo chambers online?: Politically motivated selective exposure among internet news users. Journal of Computer-Mediated Communication, 2009.

[20] Aristides Gionis, Antonis Matakos, Bruno Ordozgoiti, and Han Xiao. Mining signed networks: Theory and applications: Tutorial proposal for the web conference 2020. In Companion Proceedings of the Web Conference 2020, WWW 20, 2020.

[21] Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. Proc. of STOC, 2006.

[22] Frank Harary et al. On the notion of balance of a signed graph. The Michigan Mathematical Journal, 1953.

[23] Simon Heimlicher, Marc Lelarge, and Laurent Massoulié. Community detection in the labelled stochastic block model. Proc. of NIPS Workshop, 2012.

[24] Amin Javari, Tyler Derr, Pouya Esmailian, Jiliang Tang, and Kevin Chen-Chuan Chang. Rose: Role-based signed network embedding. In Proc. of The Web Conference, 2020.

[25] Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang. Side: representation learning in signed directed networks. In Proc. of WWW, 2018.

[26] Effrosini Kokiopoulou, Jie Chen, and Yousef Saad. Trace optimization and eigenproblems in dimension reduction methods. Numerical Linear Algebra with Applications, 2011.

[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. In Proc. of ICDM, 2010.

[28] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In Proc. of SIGCHI, 2010.

[29] David Lo, Didi Surian, Kuan Zhang, and Ee-Peng Lim. Mining direct antagonistic communities in explicit trust networks. In Proc. of CIKM, 2011.

[30] David Lo, Didi Surian, Philips Kokoh Prasetyo, Kuan Zhang, and Ee-Peng Lim. Mining direct antagonistic communities in signed social networks. Information processing & management, 2013.

[31] Michael Mc Cluskey and Young Mie Kim. Moderatism or polarization? representation of advocacy groups ideology in newspapers. Journalism & Mass Communication Quarterly, 2012.

[32] Pedro Mercado, Francesco Tudisco, and Matthias Hein. Spectral clustering of signed graphs via matrix power means. In Proc. of ICML, 2019.

[33] Gregory J Puleo and Olgica Milenkovic. Correlation clustering and biclustering with locally bounded errors. In Proc. of ICML, 2016.

[34] Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. In Proc. of NIPS, 2014.

[35] Kai Shu, Amy Sliva, Suhang Wang, Jiliang Tang, and Huan Liu. Fake news detection on social media: A data mining perspective. Proc. of SIGKDD, 2017.

[36] Jiliang Tang, Yi Chang, Charu Aggarwal, and Huan Liu. A survey of signed network mining in social media. ACM Computing Surveys (CSUR), 49(3):1 37, 2016.

[37] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 2007.

[38] Jing Wang, Jie Shen, Ping Li, and Huan Xu. Online matrix completion for signed link prediction. In Proc. of WSDM, 2017.

[39] Suhang Wang, Charu Aggarwal, Jiliang Tang, and Huan Liu. Attributed signed network embedding. In Proc. of CIKM, 2017.

[40] Han Xiao, Bruno Ordozgoiti, and Aristides Gionis. Searching for polarization in signed graphs: a local spectral approach. In Proc. of The Web Conference, 2020.

[41] Pinghua Xu, Wenbin Hu, Jia Wu, and Bo Du. Link prediction with signed latent factors in signed social networks. In Proc. of KDD, 2019.

[42] Shuo Yang, Kai Shu, Suhang Wang, Renjie Gu, Fan Wu, and Huan Liu. Unsupervised fake news detection on social media: A generative approach. In Proc. of AAAI, 2019.

[43] Sarita Yardi and Danah Boyd. Dynamic debates: An analysis of group polarization over time on twitter. Bulletin of science, technology & society, 2010.

[44] Se-Young Yun and Alexandre Proutiere. Optimal cluster recovery in the labeled stochastic block model. In Proc. of NIPS, 2016.

[45] Kuan Zhang, David Lo, and Ee-Peng Lim. Mining antagonistic communities from social networks. In Proc. of PAKDD, pages 68 80, 2010.

[46] Kuan Zhang, David Lo, Ee-Peng Lim, and Philips Kokoh Prasetyo. Mining indirect antagonistic communities from social interactions. Knowledge and information systems, 2013.