# Testing properties of signed graphs

Florian Adriaens KTH, Sweden. Email<EMAIL_ADDRESS>Simon Apers CWI, the
Netherlands and ULB, Belgium. Email<EMAIL_ADDRESS>
###### Abstract

In graph property testing the task is to distinguish whether a graph satisfies
a given property or is “far” from having that property, preferably with a
sublinear query and time complexity. In this work we initiate the study of
property testing in signed graphs, where every edge has either a positive or a
negative sign. We show that there exist sublinear algorithms for testing three
key properties of signed graphs: _balance_ (or _2-clusterability_),
_clusterability_ and _signed triangle freeness_. We consider both the dense
graph model, where we can query the (signed) adjacency matrix of a signed
graph, and the bounded-degree model, where we can query for the neighbors of a
node and the sign of the connecting edge.

Our algorithms use a variety of tools from graph property testing, as well as
reductions from one setting to the other. Our main technical contribution is a
sublinear algorithm for testing clusterability in the bounded-degree model.
This contrasts with the property of $k$-clusterability which is not testable
with a sublinear number of queries. The tester builds on the seminal work of
Goldreich and Ron for testing bipartiteness.

##  1 Introduction

##### Signed Graphs

A _signed graph_ is a graph where every edge either has a positive or a
negative label. Formally it is denoted as $G=(V,E,\sigma)$ with node set
$V=[N]$, edge set $E\subseteq V\times V$ and edge labelling
$\sigma:E\to\\{+,-\\}$. Such graphs model a variety of different scientific
phenomena. The widely studied correlation clustering problem [BBC04, DEFI06]
was orginally motivated by a document classification problem, where one has
knowledge of pairwise similarities between documents, and the goal is to
cluster the documents into (an undefined number of) groups such that within a
group the documents are similar to each other, while across groups they are
less similar. Several authors [BGG+19, TOG20] have focused on the related
problem of finding large polarized communities. In physics, signed graphs and
their frustration index are utilized to model the ground-state energy of Ising
models [Kas63]. A third example are social networks, in which interactions
between individuals can often be categorized into binary categories: trust
versus distrust, friendly or antagonistic, etc. An important aspect in the
edge formation of social networks is the sign of triangles. According to
structural balance theory from social psychology [CH56], triangles with either
one or three positive edges are more plausible, and this prevalence has been
observed in real-life social networks [LHK10, TCAL16]. Many methods and
algorithms for link and sign prediction try to capitalize on this. Aside from
link prediction, the survey of [TCAL16] lists several other important data
mining tasks in signed social media networks.

Signed graphs generalize unsigned graphs, and as such they can have different
properties than unsigned graphs. One important example is the property of
_clusterability_ or _weak balance_ , this was first introduced in [Dav67] and
it is the subject of the correlation clustering problem [BBC04]. A signed
graph is clusterable if there exists a partitioning of the nodes into an a
priori unknown number of components such that (i) every positive edge connects
two nodes in the same component, and (ii) every negative edge connects two
nodes in different components. An equivalent characterization, in terms of
forbidden subgraphs, is that the signed graph contains no cycles with exactly
one negative edge [Dav67, DEFI06]. Clusterability does not appear to have a
meaningful interpretation in the case of unsigned graphs. For example, if one
views an unsigned graph as a signed graph with the restriction that all the
edges have the same sign, whether positive or negative, then clearly any such
graph is clusterable since it contains no cycles with exactly one negative
edge.

Other signed graph properties are closer related to unsigned graph properties.
For example, the property of _balance_ or _2-clusterability_ in signed graphs
[Kön36, Har53] in fact generalizes that of bipartiteness in unsigned graphs. A
signed graph is balanced if it is clusterable into exactly two components,
with only positive edges inside the components and negative edges between the
components. It follows that a signed graph with only negative edges is
balanced iff the underlying unsigned graph is bipartite. There is also a
reduction in the opposite direction, transforming a signed graph to an
unsigned graph by replacing each positive edge by a path of two negative
edges, and afterwards omitting all the signs of the edges [Zas18]. This
reduction preserves distances, in the sense that the minimum number of edges
that need to be deleted to make the signed graph balanced (the _signed
frustration index_) is equal to the minimum number of edges that need to be
deleted to make the transformed graph bipartite (the _unsigned frustration
index_) [Zas18, Proposition 2.2]. We will use this reduction to show that in
the bounded-degree model we can reduce the problem of testing balance to that
of testing bipartiteness.111This reduction does not work well in the dense
graph model, since the transformed graph will be typically sparse.

A final signed graph property that we investigate is that of _signed triangle
freeness_. For a given signed triangle we say that a signed graph is signed
triangle free if the given triangle does not occur in the graph. The
occurrence or absence of certain signed triangles is relevant in structural
balance theory [CH56] and it generalizes the notion of triangle freeness in
unsigned graphs.

##### Graph Property Testing

Graph property testing was formally introduced in the seminal work of
Goldreich, Goldwasser and Ron [GGR98]. As input we are given query access to
an (unsigned) graph $G=(V,E)$ with node set $V=[N]$ and edge set $E\subseteq
V\times V$. We would like to decide whether the graph obeys a certain property
$\mathcal{P}$, or whether it is “far” from any graph having that property.
This is a relaxed setting as compared to that of deciding $\mathcal{P}$ and it
often allows for algorithms that have sublinear query and/or time complexity.
Such sublinear algorithms have been proposed for a wide range of graph
properties such as bipartiteness [GGR98, GR99], $k$-colorability [GGR98,
AK02], cycle-freeness [GR04, CGR+14] and more generally monotone graph
properties [AS08] and minor-closed properties [KSS20, KSS19]. We refer the
interested reader to the survey by Goldreich [Gol10].

The precise definition of “far” however depends on the type of query access
that we have to the graph:

  1. 1.

In the _dense graph model_ [Gol17] we are able to query the adjacency matrix
entries. A query takes the form $(v,w)\in[N]\times[N]$ and the reply is $1$ if
there is an edge between $v$ and $w$, otherwise it is $0$. Two graphs
$G=(V,E)$ and $G^{\prime}=(V,E^{\prime})$ are said to be $\epsilon$-far from
each other if they differ in at least an $\epsilon$-fraction of the adjacency
matrix entries. Equivalently, at least $\epsilon N^{2}$ edges have to be added
or removed to turn $G$ into $G^{\prime}$.

  2. 2.

In the _bounded-degree graph model_ we are given an upper bound $d$ on the
degrees of the graph, and we are given access to the adjacency list of $G$. A
query takes the form $(v,i)$, with $v\in[N]$ and $i\in[d]$. If the degree of
$v$ is at least $i$, then the query is answered with the $i^{\text{th}}$
neighbor $u$ of node $v$ (in arbitrary order). If $v$ has degree smaller than
$i$, an error symbol is returned. Two graphs $G=(V,E)$ and
$G^{\prime}=(V,E^{\prime})$ are $\epsilon$-far from each other if at least
$\epsilon nd$ edges have to be modified (added or removed) to turn $G$ into
$G^{\prime}$.

Using these definitions, a graph is _$\epsilon$ -far from having property
$\mathcal{P}$_ if it is $\epsilon$-far from any graph having property
$\mathcal{P}$.

A property testing algorithm for $\mathcal{P}$ is a randomized algorithm that,
given query access to $G$ and an error parameter $\epsilon$, should behave as
follows: (i) if $G$ has property $\mathcal{P}$ then the algorithm should
accept with probability at least $2/3$, whereas (ii) if $G$ is $\epsilon$-far
from having property $\mathcal{P}$, then the algorithm should reject with
probability at least $2/3$. If $G$ satisfies neither condition than the
algorithm can behave arbitrarily. This is the main reason why testing
algorithms are often far more efficient than algorithms for effectively
deciding whether $G$ has property $\mathcal{P}$ or not. If a property tester
always accepts graphs having property $\mathcal{P}$ (i.e., it never falsely
rejects), then it is called a _one-sided_ property tester for $\mathcal{P}$.
Otherwise it is called a _two-sided_ property tester.

##### Testing in Signed Graphs

Given the utility of graph property testing, and the importance of signed
graphs in many applications, we believe that extending the framework of graph
property testing to signed graphs is worthwhile. The definitions of distance
and query access for unsigned graphs are easily extended to signed graphs:

  1. 1.

In the _dense signed graph model_ adjacency matrix queries are now answered by
an element from $\\{0,-,+\\}$. A signed graph is $\epsilon$-far from property
$\mathcal{P}$ if a least $\epsilon N^{2}$ edge modifications (addition,
removal or sign switch) have to be made to obtain a graph that satisfies
$\mathcal{P}$.

  2. 2.

In the _bounded-degree signed graph model_ a query $(v,i)\in[N]\times[d]$ is
now answered either by the $i$-th neighbor $w$ of $v$ and the sign
$\sigma(v,w)$ of the corresponding edge, or by an error symbol if $v$ has less
than $i$ neighbors. A signed graph is $\epsilon$-far from $\mathcal{P}$ if a
least $\epsilon nd$ edge modifications (addition, removal or sign switch) have
to be made to obtain a graph that satisfies $\mathcal{P}$.

Note that in both cases the edge modifications now consist of edge additions,
removals, as well as sign switches. However, the properties discussed in this
paper (signed triangle freeness, balance and clusterability) are all
monotonous, and hence one may restrict the attention to edge removals.

###  1.1 Results and Techniques

In this work we investigate property testing algorithms for the canonical
signed graph properties of signed triangle freeness, balance and
clusterability. Table 1 summarizes our results in terms of query complexity of
the proposed testers. The $\widetilde{O}(\cdot)$-notation hides
polylogarithmic factors in its argument and in $N$, in the bounded-degree
model it also hides a polynomial dependence on the degree bound $d$. The time
complexity for testing balance and clusterability in the bounded-degree model
is bounded by the query complexity
$\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$. In all other cases the time
complexity is at most exponential in the query complexity. In the rest of the
section we give a sketch of our techniques.

| Dense signed graph model | Bounded-degree signed graph model
---|---|---
Signed triangle freeness |  $\widetilde{O}(\mathrm{tower}(\log(1/\epsilon)))$ [Fox11] |  $\widetilde{O}(1/\epsilon)$ [Gol10]
Balance |  $\widetilde{O}(1/\epsilon)$ [Soh12] | $\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$
Clusterability | $\widetilde{O}(1/\epsilon^{7})$ | $\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$
Table 1: Query complexity of the different property testers. All testers are
one-sided except for the clusterability tester in the dense model. The
function $\mathrm{tower}(\log(1/\epsilon)))$ denotes a power tower of $2$’s of
height $O(\log(1/\epsilon))$.

##### Dense signed graph model

We first describe property testing algorithms in the dense signed graph model.
The property of _signed triangle freeness_ can be efficiently tested by
interpreting the signed graph as an edge-colored graph. We can then use Fox’s
edge-colored triangle removal lemma [Fox11], similar to the case of triangle
freeness in unsigned graphs. For the property of _balance_ or 2-clusterability
we can use a reduction to a constraint satisfaction problem (CSP): every node
corresponds to a Boolean variable (which indicates its cluster), a positive
edge imposes an equality constraint between its endpoints and a negative edge
imposes an inequality constraint. We can then test balance by using a property
testing algorithm for CSPs [AdKK03, Soh12, AE02]. The property of
_clusterability_ can also be cast as a CSP in which the node variables now
take arbitrary integer values in $[N]$ (indicating their cluster). However,
the aforementioned CSP testers [AdKK03, Soh12, AE02] are not efficient in such
a regime. We circumvent this problem by proving that a signed graphs that is
clusterable is necessarily $\epsilon/10$-close to being clusterable into
$O(1/\epsilon)$ clusters. Using this we reduce the problem of testing
clusterability to that of distinguishing graphs that are $\epsilon/10$-close
to being $O(1/\epsilon)$-clusterable from those that are $\epsilon$-far from
being $O(1/\epsilon)$-clusterable. This problem corresponds to _tolerantly_
testing a CSP where the variables now take values in $[O(1/\epsilon)]$, and
this can be done efficiently using an algorithm by Andersson and Engebretsen
[AE02].

##### Bounded-degree signed graph model

Now we turn to the bounded-degree model. Testing signed triangle freeness is
trivial in this model, similar to the unsigned case [Gol10]. Testing balance
requires more care. While we can again cast the problem as a CSP, we are not
aware of any appropriate property testing algorithms for CSPs in the bounded-
degree model. Rather we reduce the problem of testing balance for signed
graphs to that of testing bipartiteness for unsigned graphs, for which we can
use the algorithm of Goldreich and Ron [GR99]. The reduction is based on a
transformation described by Zaslavsky [Zas18], which maps balanced (resp.
unbalanced) signed graphs to bipartite (resp. nonbipartite) unsigned graphs.
The resulting algorithm’s query complexity has an optimal
$\sqrt{N}$-dependence, which follows from the $\Omega(\sqrt{N})$ lower bound
for testing bipartiteness.

Finally, and this is our main technical contribution, we describe a property
testing algorithm for clusterability. While we can again reduce the problem to
testing $O(1/\epsilon)$-clusterability, similar to the dense case, the problem
is that $k$-colorability (which is a special case of $k$-clusterability) is
not testable in the bounded-degree model [BT04]. Rather, we base our algorithm
on the forbidden subgraph characterization by Davis [Dav67], which states that
a signed graph is clusterable if and only if it has no cycles with exactly one
negative edge. We then use random walks to find such a cycle: first we pick a
random initial node and perform a large number of random walks _on the
positive edges_ of $G$, then we check for the existence of a negative edge
between any pair of nodes that were visited by a random walk. Such a negative
edge necessarily yields a bad cycle. The correctness of this algorithm is easy
to prove when the positive edges in $G$ induce an expander. For the general
case we build on the (unsigned) graph decomposition results of Goldreich and
Ron [GR99].

###  1.2 Conclusion and open questions

On the one hand, our work demonstrates that key properties of signed graphs
can be tested very efficiently. This seems to not have been studied before. On
the other hand, we introduce signed graphs as an interesting setting for
studying graph property testing. Our work leaves open a number of questions
and future directions:

  * •

A lot of effort has been put in characterizing the set of properties that are
testable (using $\widetilde{O}(\mathrm{poly}(1/\epsilon))$ queries) in the
dense graph model [AS08, AS05, GT01, AFNS09] and the bounded-degree graph
model [BSS10, CSS09, CGR+14, NS13]. It would be interesting to characterize
the set of signed graph properties that are testable.

  * •

In a very recent work by Kumar, Seshadhri and Stolman [KSS21] an efficient
_partition oracle_ was proposed. For minor-closed graph families such an
oracle gives local access to a certain global decomposition of the graph. The
study of such a decomposition and corresponding oracle for signed graphs seems
like an interesting future direction, especially given the connection between
signed graphs and social networks.

  * •

Finally, we did not succeed in proving a $\Omega(\sqrt{N})$ lower bound for
testing clusterability in the bounded-degree signed graph model, and hence we
leave this as an open question.

##  2 Property testing in the dense signed graph model

###  2.1 Signed Triangle Freeness

A signed triangle is any triangle with a fixed sign assignment of its edges.
As mentioned in the introduction, it is often interesting to check whether a
signed graph for instance contains any triangles with exactly one negative
edge. While it can be computationally expensive to effectively decide this,
especially for massive graphs such as social networks, it might be easier to
_test_ whether the graph is free of such triangles.

Testing triangle freeness for unsigned graphs has been well studied. It is a
direct application of the triangle removal lemma [RS78, Fox11]. For some
function $f$, the canonical one-sided tester simply picks $f(\epsilon)$ random
triples in $[N]$ and rejects the graph if any of the triples induces a
triangle. If the graph is triangle free, then we always accept the graph, so
that the tester is indeed one-sided. If the graph is $\epsilon$-far from being
triangle free, than the triangle removal lemma of Fox [Fox11] proves that the
graph contains at least $\delta(\epsilon)\,\binom{n}{3}$ triangles. Here
$\delta(\epsilon)$ is a function bounded by the inverse of the towering
function $\mathrm{tower}(\log(1/\epsilon))$, which corresponds to a tower of
$2$’s of height $O(\log(1/\epsilon))$ (i.e., $2$-to-the-$2$-to-the-…-to-
the-$2$, $O(\log(1/\epsilon)$ times). Hence if we sample
$f(\epsilon)\in\Theta(1/\delta(\epsilon))$ triples, then with high probability
one of them will induce a triangle and we will correctly reject the graph.
This yields a total query complexity of $O(1/\delta(\epsilon))$.

Testing signed triangle freeness in signed graphs can be analyzed in a very
similar way. By interpreting the edge signs of a graph as an edge-coloring, we
can use Fox’s _colored_ triangle removal lemma [Fox11]. This lemma states that
if an edge-colored graph is $\epsilon$-far from being free of a certain
colored triangle, then the graph contains at least
$\delta^{\prime}(\epsilon)\,\binom{n}{3}$ such induced triangles, where
$\delta^{\prime}(\epsilon)$ is again bounded by the inverse of
$\mathrm{tower}(\log(1/\epsilon))$. By the same argument as in the unsigned
case, this implies the existence of a one-sided tester for colored (or signed)
triangle freeness in the dense graph model with query complexity
$O(\mathrm{tower}(\log(1/\epsilon)))$. This proves the following theorem.

######  Theorem 1.

There exists a one-sided tester for signed triangle freeness in the dense
signed graph model with query complexity
$\widetilde{O}(\mathrm{tower}(\log(1/\epsilon)))$.

###  2.2 Balance

We can cast balance or 2-clusterability of a signed graph $G=(V,E,\sigma)$ as
a satisfiability problem. Associate with each node $v$ a variable
$x_{v}\in\\{0,1\\}$. With every edge $(u,v)\in E$ we associate a constraint on
$x_{u}$ and $x_{v}$: if $\sigma(e)=+$ (positive edge) the constraint is
satisfied iff $x_{u}=x_{v}$; if $\sigma(e)=-$ (negative edge) then the
constraint is satisfied iff $x_{u}\neq x_{v}$. The graph $G$ will be balanced
iff there exists an assignment of $x_{v}$’s such that all constraints are
satisfied. Even more, if $G$ is $\epsilon$-far from being balanced then we
similarly have to remove $\epsilon n^{2}$ constraints from the satisfiability
problem for it to satisfiable. As a consequence, the problem reduces to
testing whether the satisfiability problem is in fact satisfiable. For this we
can use the work by Sohler [Soh12] which describes a one-sided tester with
query complexity $\widetilde{O}(1/\epsilon)$. The algorithm is very simple:
sample $\widetilde{O}(1/\epsilon)$ variables and accept, if and only if the
induced set of constraints on those variables has a satisfying assignment.
Applying this algorithm to the problem of testing balance gives the following
algorithm: sample $\widetilde{O}(1/\epsilon)$ nodes, query the entire induced
subgraph, and accept if and only if the induced subgraph is balanced. From
[Soh12, Theorem 1] it then follows that this describes a one-sided property
tester for balance. This proves the following theorem.

######  Theorem 2.

There exists a one-sided tester for balance in the dense signed graph model
with query complexity $\widetilde{O}(1/\epsilon)$.

We note that testing $k$-clusterability can be reduced to satisfiability in
the very same manner, except that now the variables
$x_{v}\in\\{0,1,\dots,k-1\\}$. For constant $k$ we can again use [Soh12,
Theorem 1] to get a one-sided tester with query complexity
$\widetilde{O}(1/\epsilon)$.

###  2.3 Clusterability

A relaxation of $k$-clusterability for signed graphs is the notion of _weak
balance_ or _clusterability_ [Dav67, BBC04]. A signed graph is clusterable if
it is $k$-clusterable for some (a priori unknown) $k\in[N]$. Since there can
only be $N$ clusters, we could test clusterability by testing
$N$-clusterability. The satisfiability reduction from last section however
fails in such case, because typical satisfiability testers have a bad
dependence on the domain size of the variables.

Rather, we argue that testing clusterability can be reduced to tolerantly
testing $k$-clusterability for $k\in O(1/\epsilon)$. A tolerant tester [PRR06]
is required to accept inputs that are $\epsilon_{1}$-close to some property
$\mathcal{P}$, while rejecting inputs that are $\epsilon_{2}$-far from
$\mathcal{P}$, for some parameters $\epsilon_{1}<\epsilon_{2}$. Tolerant
testing is closely related to approximating the distance from an object to a
property (see [PRR06]). We use the following lemma.

######  Lemma 3.

If a signed graph is clusterable then it is $4\epsilon$-close to being
clusterable into at most $1/\epsilon$ clusters.

###### Proof.

Let the partition $V=P_{1}\cup P_{2}\cup\dots\cup P_{r}$ denote a valid
clustering of the graph. We define a new partition by merging different
components: keep all components $P_{i}$ of size $|P_{i}|\geq\epsilon N$, and
merge the remaining components into components of size between $\epsilon N$
and $2\epsilon N$ (which is always possible). This yields a new partition with
at most $1/\epsilon$ components. Between the components there are only
negative edges, and there are at most $(2\epsilon N)^{2}/\epsilon=4\epsilon
N^{2}$ edges within the components. Hence if we remove all the edges within
the new components, then we obtain a new graph for which the new partition
describes a clustering with at most $1/\epsilon$ clusters, and which is
$(4\epsilon)$-far from the original graph. ∎

Now if a signed graph is $\epsilon$-far from being clusterable, then clearly
it is also $\epsilon$-far from being say $(8/\epsilon)$-clusterable. On the
other hand, by this lemma, a graph that is $\epsilon/4$-close to being
clusterable will be $(\epsilon/4+\epsilon/2)=3\epsilon/4$-close to a graph
that is $(8/\epsilon)$-clusterable. Hence we can use a tolerant tester for
$O(1/\epsilon)$-clusterability to tolerantly test clusterability.
Equivalently, we can use an additive estimate (with error $\pm\epsilon N^{2}$)
on the number of edges that need to be removed in order to make a signed graph
$k$-clusterable, for $k\in O(1/\epsilon)$. Now we are in better shape to cast
the problem as a satisfiability problem, similar to last section. In Section
A.1 we detail how to use the algorithm of Andersson and Engebretsen [AE02] to
tolerantly test for $O(1/\epsilon)$-clusterability using
$\widetilde{O}(1/\epsilon^{7})$ queries. This yields the following theorem.

######  Theorem 4.

There exists a two-sided tolerant tester for clusterability in the dense
signed graph model with query complexity $\widetilde{O}(1/\epsilon^{7})$.

Since the tester is tolerant, this also gives an algorithm to estimate the
weak frustration index with additive error $\epsilon N^{2}$ using
$\widetilde{O}(1/\epsilon^{7})$ queries.

##  3 Property testing in the bounded-degree signed graph model

###  3.1 Signed triangle freeness

Testing triangle freeness in the bounded-degree (unsigned) graph model is
significantly easier to analyze than doing so for the dense model [Gol10]. In
fact, the exact same argument applies to signed graphs and we will describe it
here for completeness. Given query access to a signed graph, consider the
following testing algorithm: pick $\widetilde{O}(1/\epsilon)$ nodes and reject
if any of them is part of a signed triangle. We can check whether a node is
part of a signed triangle simply by querying for its neighbors, and the
neighbors of its neighbors. In the bounded-degree model this takes only
$\widetilde{O}(1)$ queries. If the graph is signed triangle free then we will
never reject. On the other hand, if at least $\epsilon dN$ edges have to
removed in order to make the graph signed triangle free, then at least
$\epsilon N$ nodes must be part of a signed triangle. With large probability
the algorithm will sample such a node and consequently reject the graph. This
yields the theorem below.

######  Theorem 5.

There exists a one-sided tester for signed triangle freeness in the bounded-
degree signed graph model with query complexity $O(1/\epsilon)$.

###  3.2 Balance

Our algorithm for testing balance of bounded-degree signed graphs reduces the
problem to testing bipartiteness in a related unsigned graph222The reduction
is reminiscent of the reduction from cycle-freeness testing to bipartiteness
testing in [CGR+14]. However, the reduction in [CGR+14] is randomized and
between unsigned graphs, whereas our reduction is deterministic and for signed
graphs.. Consider the following mapping from a signed graph $G$ to an unsigned
graph $G^{\prime}$: (i) for every positive edge $(u,v)$ create a new node
$w^{(u,v)}$ and replace the edge $(u,v)$ by two unsigned edges $(u,w^{(u,v)})$
and $(w^{(u,v)},v)$, and (ii) replace each of the remaining negative edges by
an unsigned edge. The unsigned graph $G^{\prime}$ has an odd cycle if and only
if $G$ has a cycle with an odd number of negative edges. As a consequence,
$G^{\prime}$ will be bipartite if and only if $G$ was balanced.

Figure 1: (a) Balanced signed graph $G$ (dotted lines are positive edges,
solid lines are negative edges). (b) Bipartite unsigned graph $G^{\prime}$
after mapping. (c) Bipartition of $G^{\prime}$.

In fact, an even stronger property holds [Zas18, Proposition 2.2]: the
(signed) frustration index of $G$ is equal to the (unsigned) frustration index
of $G^{\prime}$. This implies the following lemma.

######  Lemma 6.

If $G$ is $\epsilon$-far from balanced then $G^{\prime}$ is
$\epsilon/(d+1)$-far from bipartite.

###### Proof.

For the second fact, let $G$ be $\epsilon$-far from being balanced, so that it
has signed frustration index $k\geq\epsilon dN$. The unsigned graph
$G^{\prime}$ then has unsigned frustration index $k\geq\epsilon dN$. Now if
$G$ has $m^{+}$ positive edges, then $G^{\prime}$ has exactly
$N+m^{+}\leq(d+1)N$ vertices while keeping the same degree bound $d$. As a
consequence, we can bound its frustration index
$k\geq\frac{\epsilon}{d+1}(d+1)dN\geq\frac{\epsilon}{d+1}d(N+m^{+})$, so that
$G^{\prime}$ is indeed $\frac{\epsilon}{d+1}$-far from being bipartite. ∎

This lemma proves that we can test $\epsilon$-balancedness of $G$ by testing
$\epsilon/(d+1)$-bipartiteness of $G^{\prime}$. For this we can use the
following algorithm, which uses random walks to find odd cycles. It was proven
to be a one-sided bipartiteness tester in the bounded-degree model by
Goldreich and Ron [GR99].

Algorithm 1 Bipartiteness tester

1:for $O(1/\epsilon)$ times do

2: Pick a node $v$ uniformly at random.

3: Perform $\widetilde{O}(\sqrt{N}/\epsilon^{3})$ random walks333A single step
of the random walk from a node $v$ (with degree $d(v)$) corresponds to the
following process: with probability $d(v)/d$ move to a uniformly random
neighbor, and otherwise stay at $v$. starting from $v$, each of length
$\widetilde{O}(1/\epsilon^{8})$.

4: If some vertex $u$ is reached both after an even path and after an odd path
then reject.

It remains to prove that we can efficiently implement this tester on
$G^{\prime}$.

######  Lemma 7.

It is possible to implement Algorithm 1 on $G^{\prime}$ using
$\mathrm{poly}(\log(N)/\epsilon)\sqrt{N}$ adjacency list queries to $G$.

###### Proof.

We need to be able to select a uniformly random node from $G^{\prime}$, and
implement a random walk on $G^{\prime}$. The latter is easy:

  * •

If we are on an original node $u$ in $G^{\prime}$ then pick a random neighbor
$v$ of $u$ in $G$. If $(u,v)$ is negative, go to $v$, otherwise go to the new
node indexed $w^{(u,v)}$.

  * •

If we are on a new node $w^{(u,v)}$, go to either $u$ or $v$ with probability
$1/2$.

To select a uniformly random node from $G^{\prime}$, do the following:

  1. 1.

Pick $(u,i)\in[N]\times[d]$ uniformly at random and query for the $i$-th
neighbor $v$ of $u$ in $G$. If $u$ has less than $i$ neighbors we reject.

  2. 2.

If $\sigma(u,v)=-$, with probability $1/(4d(u))$ output a random endpoint of
$(u,v)$ and terminate. Otherwise, go to next step.

  3. 3.

If $\sigma(u,v)=+$, with probability $1/4$ output $w^{(u,v)}$ and terminate.
Otherwise, with probability $1/(3d(u))$ output a random endpoint of $(u,v)$.

With probability $\geq 1/(4d)$, this scheme returns a uniformly random node
from $G^{\prime}$ (and otherwise it rejects). To see this, first consider any
original node $u$ in $G^{\prime}$. Any of its $d(u)$ incident edges is picked
with an equal probability $1/(dN)$. If a negative incident edge is picked,
then $u$ is returned in step 2. with probability $1/(4d(u))$; if it is a
positive incident edge then $u$ is returned in step 3. with probability
$(1-1/4)/(3d(u))=1/(4d(u))$. Hence the total probability that $u$ is returned
is

$d(u)\frac{1}{4d(u)}\frac{1}{dN}=\frac{1}{4dN}.$

Now consider a new node $w^{(u,v)}$ in $G^{\prime}$. In step 1. the edge
$(u,v)$ is picked with probability $1/(dN)$, after which $w^{(u,v)}$ is
returned with probability $1/4$ in step 3., yielding a total probability
$1/(4dN)$. Since there are $N+m^{-}\geq N$ nodes in $G^{\prime}$, the total
probability of returning a node is $\geq N/(4dN)=1/(4d)$. The sampling scheme
only requires a single query, and so we can sample a uniformly random node
from $G^{\prime}$ using $4d\in O(1)$ queries in expectation. By Chebyshev’s
inequality the total number of queries will be close to its expection with
overwhelming probability. ∎

This proves the following theorem.

######  Theorem 8.

There exists a one-sided tester for balance in the bounded-degree signed graph
model with query complexity $\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$.

Since balancedness of signed graphs generalizes bipartiteness of unsigned
graphs, the $\widetilde{\Omega}(\sqrt{N})$ lower bound for testing
bipartiteness in the (unsigned) bounded-degree model [GR04, Theorem 7.1] also
applies to testing balancedness in the (signed) bounded-degree model. As a
consequence, the $\sqrt{N}$-dependency of our tester is optimal.

###  3.3 Clusterability

In this section we prove the existence of a one-sided property tester for
clusterability in the bounded-degree signed graph model. We first note that
similar to the dense case we can reduce the problem to testing
$O(1/\epsilon)$-clusterability. However, $k$-clusterability is a special case
of $k$-colorability for unsigned graphs, and this is known not to be testable
in the bounded-degree model [BOT02] (i.e., it requires $\Omega(N)$ queries).
Instead, we use the forbidden subgraph characterization of clusterability by
Davis [Dav67]:

######  Theorem 9 ([Dav67, Theorem 1]).

A signed graph $G$ is clusterable if and only if $G$ contains no cycle with
exactly one negative edge.

We will call such a cycle a _bad cycle_. This characterization is a crucial
distinction between clusterability and the untestable $k$-clusterability (or
its unsigned variant, $k$-colorability), which does not seem to have such a
simple characterization.

Similar to the bipartiteness tester of Goldreich and Ron [GR99] we will try to
find bad cycles by performing many random walks in $G$. Specifically, we
simulate random walks on the unsigned subgraph $G^{+}=(V,E^{+})$ induced by
the positive edges $E^{+}=\\{e\in E\mid\sigma(e)=+\\}$. Starting from a random
initial node, we perform many such random walks and we check for the existence
of a negative edge between distinct random walks. Such a negative edge will
necessarily yield a bad cycle, in which case we can safely reject the graph.

Algorithm 2 Tester for clusterability

1:for $O(1/\epsilon)$ times do

2: Pick a random node $s$ and run $\operatorname*{\texttt{bad-cycle}}(s)$.

3: If this returns a bad cycle, reject the graph.

$\operatorname*{\texttt{bad-cycle}}(s)$:

1:Perform $\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$ random walks of
length $\widetilde{O}(1/\mathrm{poly}(\epsilon))$ on $G^{+}$, starting from
$s$. Let $K$ denote the set of all the nodes that are visited.

2:If there is a negative edge between any pair of nodes in $K$, return the
corresponding bad cycle.

We prove the following claim.

######  Theorem 10.

Algorithm 2 is a one-sided tester for clusterability with query complexity

$\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon)).$

The claim about the query complexity is easy to check. The total number of
random walk steps is $\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$, and a
single random walk step can be implemented with $\widetilde{O}(1)$ queries. To
check whether there exists a negative edge between any pair of nodes in $K$,
it suffices to query the full (bounded) neighborhood of every node in $K$.
This takes $d|K|\in\widetilde{O}(\sqrt{N}/\mathrm{poly}(\epsilon))$ queries.
The remainder of this section is used to prove correctness of the tester
(which ultimately follows from 14).

####  3.3.1 Intuition: Expanding case

We will first describe the intuition behind the tester. To this end, assume
that there is a decomposition $V=V_{1}\cup\dots\cup V_{k}$ as in Fig. 2 such
that for each $i$ the following holds:

  1. 1.

$V_{i}$ has few positive outgoing edges:

$|E^{+}(V_{i},V_{i}^{c})|\leq\frac{\epsilon}{2}d|V_{i}|.$

  2. 2.

A random walk of length $\widetilde{O}(1/\mathrm{poly}(\epsilon))$ on $G^{+}$,
and starting from any $s\in V_{i}$, ends uniformly at random inside $V_{i}$.

While such a decomposition does not generally exist, the existence of a
closely related decomposition was proven by Goldreich and Ron [GR99].

Now assume that $G$ is $\epsilon$-far from being clusterable. Then we claim
that there must be at least $\frac{\epsilon}{2}dN$ negative edges inside the
partitions $V_{1},\dots,V_{k}$. Indeed, if this were not the case, then we
could find a valid clustering by removing these $\leq\frac{\epsilon}{2}dN$
negative edges together with the $\leq\frac{\epsilon}{2}dN$ positive edges
between the partitions. This contradicts the fact that $G$ is $\epsilon$-far
from being clusterable.

Now make the additional assumption that the number of negative edges
$|E^{-}(V_{i})|$ inside each partition $V_{i}$ is $\Omega(\epsilon|V_{i}|)$,
and consider an arbitrary node $s\in V_{i}$. The probability that a pair of
random walks on the positive edges, starting from $s$, results in a bad cycle
can be lower bounded by the probability that the random walk endpoints $u$ and
$v$ form a negative edge $(u,v)\in E^{-}$. Since $u$ and $v$ are distributed
uniformly, this probability is at least
$|E^{-}(V_{i})|/|V_{i}|^{2}\in\Omega(\epsilon/N)$. Taking $\sqrt{N/\epsilon}$
independent random walks (and ignoring correlations), the total probability of
finding a bad cycle then becomes
$\Omega\left(\binom{\sqrt{N/\epsilon}}{2}\frac{\epsilon}{N}\right)\in\Omega(1)$.

Figure 2: Bounded degree tester for clusterability. Positive edges $E^{+}$
depicted as solid lines, negative edges $E^{-}$ depicted as dashed lines. $G$
is $\epsilon$-close to clusterable if there are $\leq\frac{\epsilon}{2}dN$
positive edges between the partitions and $\leq\frac{\epsilon}{2}dN$ negative
edges inside the partitions.

####  3.3.2 General case: GR decomposition

While the former section correctly captures the intuition behind the tester,
the full proof of correctness is significantly more involved. Luckily, most of
the analysis runs similar to that of Goldreich and Ron [GR99] (regarding the
graph decomposition, but also regarding bounds on the correlation between
distinct random walks). We can make the above intuition rigorous. In the
following let $G^{+}=(V,E^{+})$ denote the (unsigned) subgraph induced by the
positive edges. The main idea of the decomposition is that for most of the
vertices $s$ in $G^{+}$, we can find a subset $S$ so that $S$ has few outgoing
edges and a short random walk from $s$ mixes approximately uniformly over $S$.
We can hence set the first partition $V_{1}=S$. Now we would like to repeat
the argument for the remaining graph $H^{+}=G^{+}[V-V_{1}]$, induced on the
node subset $V-V_{1}$. The problem is that the next subset
$S^{\prime}\subseteq V-V_{1}$ will be “good” for random walks in $H^{+}$, but
these can behave very differently from the original random walks in $G^{+}$.
This problem is dealt with by defining a Markov chain $M(H^{+})$ on the
unpartitioned subgraph $H^{+}$ such that (i) we can use $M(H^{+})$ to cut off
a new partition $S^{\prime}$ from $H^{+}$, but also (ii) that the behavior of
walks according to $M(H^{+})$ is related to the behavior of the original
random walks in $G^{+}$. Details of the Markov chain $M(H^{+})$ are given in
Section B.1. The following lemma is proven in [GR99], with $q_{s,v}(t)$
denoting the probability that $t$ steps of the Markov chain $M(H^{+})$,
starting from $s$, end in $v$.

######  Lemma 11 ([GR99, Corollary 3 and Lemma 4.3]).

Let $H^{+}$ be a subgraph of $G^{+}$ with at least $\epsilon N/4$ vertices.
Then for at least half of the vertices $s$ in $H^{+}$ there exists a subset of
vertices $S$ in $H^{+}$, a value $\beta\in\widetilde{\Omega}(\epsilon^{2})$
and an integer $t\in\widetilde{O}(1/\epsilon^{3})$ such that

  1. 1.

The number of edges between $S$ and the rest of $H^{+}$ is at most $\epsilon
d|S|/2$.

  2. 2.

For every $v\in S$ it holds that $\sqrt{\frac{\beta}{|S||H^{+}|}}\leq
q_{s,v}(t)\leq\frac{1}{\epsilon}\sqrt{\frac{\beta}{|S||H^{+}|}}$.

This is the key lemma that underlies the GR decomposition. Under these
conditions, we can prove that if the original signed graph $G$ has many
negative edges inside the subset $S$ then the modified Markov chain $M(H^{+})$
will find a bad cycle. This lemma is new, but its proof (which we defer to
Section B.2) runs along the lines of the proof of [GR99, Lemma 4.5].

######  Lemma 12.

Let $H^{+}$ be a subgraph of $G^{+}$, $s$ a vertex in $H^{+}$ and $S$ a subset
of vertices in $H^{+}$. Assume that there exist $\alpha>0$, $F\geq 1$, $t$
such that $\alpha\leq q_{s,v}(t)\leq F\alpha$ for every $v\in S$. If the
original graph $G$ has at least $\epsilon d|S|/2$ negative edges inside $S$
then $m\in\Omega\left(\frac{F}{\epsilon\alpha\sqrt{|S|}}\right)$ runs of
$M(H^{+})$ over $t$ steps and starting from $s$ will return a bad cycle with
probability at least $0.99$.

Ultimately we are ofcourse interested in the behavior of random walks in
$G^{+}$, rather than that of $M(H^{+})$. The following lemma (proven in
Section B.1) shows that both are closely related.

######  Claim 13.

Assume that there exists $s$ and $m$ such that $m$ walks of $M(H^{+})$ of
length $\widetilde{O}(1/\epsilon^{3})$ and starting from $s$ result in a bad
cycle with probability at least $0.99$. Then $m$ random walks in $G^{+}$ of
length $\widetilde{O}(1/\epsilon^{8})$ and starting from $s$ will also result
in a bad cycle with probability at least $0.99$.

####  3.3.3 Correctness

We can prove correctness of the tester (Algorithm 2) by combining the
ingredients from the previous section. Rather than proving that a graph $G$
that is $\epsilon$-far from clusterable will be rejected, we will prove that
if $G$ is accepted with large probability then $G$ must be close to being
clusterable. This is again similar to the proof of correctness in [GR99].

######  Claim 14.

If Algorithm 2 accepts a graph $G$ with probability greater than $1/3$, then
$G$ must be $2\epsilon$-close to being clusterable.

To prove this, let $G$ be a graph that is accepted with probability greater
than $1/3$. We say that a vertex $s$ is _good_ if $\operatorname*{\texttt{bad-
cycle}}(s)$ in Algorithm 2 returns a bad cycle with probability at most $0.1$.
Otherwise it is _bad_. Since we reject with probability less than $2/3$, and
we consider $\Omega(1/\epsilon)$ starting vertices, there can be only
$\epsilon N/16$ bad vertices (for the appropriate constant in the
$\Omega(\cdot)$ notation). We will show that under these circumstances we can
find a valid clustering by removing less than $2\epsilon dN$ edges. To this
end, we will iteratively separate a subset $S$ that has at most $\epsilon
d|S|/2$ positive outgoing edges and at most $\epsilon d|S|/2$ negative
internal edges. We call such a subset an _$\epsilon$ -good cluster_.

At a given step, let $H^{+}$ denote the unpartitioned graph. We wish to invoke
Lemma 11. Call a vertex $s$ for which the lemma holds a “useful” vertex with
respect to $H^{+}$. While $|H^{+}|\geq\epsilon N/4$, the lemma ensures that
there are $\geq\epsilon N/8$ useful vertices. Since there are at most
$\epsilon N/16$ bad vertices, this implies that there exists a vertex $s$ that
is both good and useful. By Lemma 11 there exists a subset $S$ in $H^{+}$ that
has at most $\frac{\epsilon}{2}d|S|$ (positive) edges to the rest of $H^{+}$.
Moreover, by Lemma LABEL:lem:bad-cycle and Claim 13, the set $S$ is such that
if the original signed graph $G$ has at least $\epsilon d|S|$ negative edges
inside $S$ then $\operatorname*{\texttt{bad-cycle}}(s)$ will return a bad
cycle with probability at least $0.99$. However, we assumed that $s$ is a good
vertex and so the latter probability can be at most $0.1$. This implies that
$G$ must have less than $\epsilon d|S|/2$ negative edges inside $S$, and hence
$S$ is an $\epsilon$-good cluster.

We repeat this process until $|H^{+}|<\epsilon N/4$. If $V_{1},\dots,V_{k}$
denote the $\epsilon$-good clusters that we have cut off, then we have a
partition $V=V_{1}\cup\dots\cup V_{k}\cup H$ such that the number of positive
edges between the partitions is at most

$d|H|+\sum_{i}|E^{+}(V_{i},V_{i}^{c})|\leq\frac{\epsilon}{4}dN+\sum_{i}\frac{\epsilon}{2}d|V_{i}|<\epsilon
dN,$

and the number of negative edges inside the partitions is at most

$d|H|+\sum_{i}|E^{-}(V_{i})|\leq\frac{\epsilon}{4}dN+\sum_{i}\frac{\epsilon}{2}d|V_{i}|<\epsilon
dN.$

Removing these less than $2\epsilon dN$ edges yields a valid clustering, so
that $G$ must be $2\epsilon$-close to clusterable. This proves 14.

##  4 Acknowledgements

This work has benefited from discussions with Jop Briët, Aristides Gionis,
Oded Goldreich and Christian Sohler. Florian Adriaens is supported by the ERC
Advanced Grant REBOUND (834862), the EC H2020 RIA project SoBigData (871042),
and the Wallenberg AI, Autonomous Systems andSoftware Program (WASP) funded by
the Knut and Alice Wallenberg Foundation. Simon Apers is supported in part by
the Dutch Research Council (NWO) through QuantERA ERA-NET Cofund project
QuantAlgo 680-91-034.

## References

  * [AdKK03] Noga Alon, W.Fernandez de la Vega, Ravi Kannan, and Marek Karpinski.  Random sampling and approximation of MAX-CSPs.  Journal of Computer and System Sciences, 67(2):212 – 243, 2003\.  Special Issue on STOC 2002.
  * [AE02] Gunnar Andersson and Lars Engebretsen.  Property testers for dense constraint satisfaction programs on finite domains.  Random Structures & Algorithms, 21(1):14–32, 2002.
  * [AFNS09] Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira.  A combinatorial characterization of the testable graph properties: It’s all about regularity.  SIAM Journal on Computing, 39(1):143–167, 2009.
  * [AK02] Noga Alon and Michael Krivelevich.  Testing k-colorability.  SIAM J. Discret. Math., 15(2):211–227, February 2002.
  * [AS04] Noga Alon and Joel H Spencer.  The probabilistic method.  John Wiley & Sons, 2004.
  * [AS05] N. Alon and A. Shapira.  A characterization of the (natural) graph properties testable with one-sided error.  In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 429–438, 2005.
  * [AS08] Noga Alon and Asaf Shapira.  Every monotone graph property is testable.  SIAM Journal on Computing, 38(2):505–522, 2008.
  * [BBC04] Nikhil Bansal, Avrim Blum, and Shuchi Chawla.  Correlation clustering.  Machine learning, 56(1):89–113, 2004.
  * [BGG+19] Francesco Bonchi, Edoardo Galimberti, Aristides Gionis, Bruno Ordozgoiti, and Giancarlo Ruffo.  Discovering polarized communities in signed networks.  In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM ’19, page 961–970, New York, NY, USA, 2019. Association for Computing Machinery.
  * [BOT02] Andrej Bogdanov, Kenji Obata, and Luca Trevisan.  A lower bound for testing 3-colorability in bounded-degree graphs.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 93–102. IEEE, 2002.
  * [BSS10] Itai Benjamini, Oded Schramm, and Asaf Shapira.  Every minor-closed property of sparse graphs is testable.  Advances in mathematics, 223(6):2200–2218, 2010.
  * [BT04] Andrej Bogdanov and Luca Trevisan.  Lower bounds for testing bipartiteness in dense graphs.  In 19th IEEE Annual Conference on Computational Complexity, pages 75–81. IEEE, 2004.
  * [CGR+14] Artur Czumaj, Oded Goldreich, Dana Ron, C Seshadhri, Asaf Shapira, and Christian Sohler.  Finding cycles and trees in sublinear time.  Random Structures & Algorithms, 45(2):139–184, 2014.
  * [CH56] D. Cartwright and F. Harary.  Structural balance: a generalization of Heider’s theory.  Psychological review, 63 5:277–293, 1956.
  * [CSS09] Artur Czumaj, Asaf Shapira, and Christian Sohler.  Testing hereditary properties of nonexpanding bounded-degree graphs.  SIAM Journal on Computing, 38(6):2499–2510, 2009.
  * [Dav67] James A Davis.  Clustering and structural balance in graphs.  Human relations, 20(2):181–187, 1967.
  * [DEFI06] Erik D Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica.  Correlation clustering in general weighted graphs.  Theoretical Computer Science, 361(2-3):172–187, 2006.
  * [Fox11] Jacob Fox.  A new proof of the graph removal lemma.  Annals of Mathematics, pages 561–579, 2011.
  * [GGR98] Oded Goldreich, Shari Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  J. ACM, 45(4):653–750, July 1998.
  * [Gol10] Oded Goldreich.  Introduction to testing graph properties.  In Property testing, pages 105–141. Springer, 2010.
  * [Gol17] Oded Goldreich.  Testing Graph Properties in the Dense Graph Model, page 162–212.  Cambridge University Press, 2017.
  * [GR99] Oded Goldreich and Dana Ron.  A sublinear bipartiteness tester for bounded degree graphs.  Combinatorica, 19(3):335–373, 1999.
  * [GR04] Oded Goldreich and Dana Ron.  Property testing in bounded degree graphs.  Algorithmica, 32, 01 2004.
  * [GT01] O. Goldreich and L. Trevisan.  Three theorems regarding testing graph properties.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, volume 1, pages 460–469, 2001.
  * [Har53] Frank Harary.  On the notion of balance of a signed graph.  Michigan Math. J., 2(2):143–146, 1953.
  * [Kas63] Pieter W Kasteleyn.  Dimer statistics and phase transitions.  Journal of Mathematical Physics, 4(2):287–293, 1963.
  * [Kön36] Dénes König.  Theorie der endlichen und unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe, volume 16.  Akademische Verlagsgesellschaft mbh, 1936.
  * [KSS19] Akash Kumar, C Seshadhri, and Andrew Stolman.  Random walks and forbidden minors II: a $\mathrm{poly}(d\varepsilon^{-1})$-query tester for minor-closed properties of bounded degree graphs.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 559–567, 2019.
  * [KSS20] Akash Kumar, C Seshadhri, and Andrew Stolman.  Random walks and forbidden minors I: An $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs.  SIAM Journal on Computing, 2020.
  * [KSS21] Akash Kumar, C Seshadhri, and Andrew Stolman.  Random walks and forbidden minors III: $\mathrm{poly}(d/\epsilon)$-time partition oracles for minor-free graph classes.  2021\.
  * [LHK10] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg.  Signed Networks in Social Media, page 1361–1370.  Association for Computing Machinery, New York, NY, USA, 2010.
  * [NS13] Ilan Newman and Christian Sohler.  Every property of hyperfinite graphs is testable.  SIAM Journal on Computing, 42(3):1095–1112, 2013.
  * [PRR06] Michal Parnas, Dana Ron, and Ronitt Rubinfeld.  Tolerant property testing and distance approximation.  Journal of Computer and System Sciences, 72(6):1012–1042, 2006\.
  * [RS78] Imre Z Ruzsa and Endre Szemerédi.  Triple systems with no six points carrying three triangles.  Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18:939–945, 1978.
  * [Soh12] Christian Sohler.  Almost optimal canonical property testers for satisfiability.  In IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 541–550. IEEE, 2012.
  * [TCAL16] 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.
  * [TOG20] Ruo-Chun Tzeng, Bruno Ordozgoiti, and Aristides Gionis.  Discovering conflicting groups in signed networks.  Advances in Neural Information Processing Systems, 33, 2020.
  * [Zas18] Thomas Zaslavsky.  Negative (and positive) circles in signed graphs: A problem collection.  AKCE International Journal of Graphs and Combinatorics, 15(1):31–48, 2018.

##  Appendix A Technical details for dense signed graph model

###  A.1 Clusterability

The following theorem is proven by Andersson and Engebretsen [AE02].

######  Theorem 15 ([AE02, Theorem 2]).

Consider a constraint family $\mathcal{F}=\\{f:D^{\ell}\to\\{0,1\\}\\}$ over
$\ell$ variables in domain $D$, and let $\Sigma$ denote the maximum number of
constraints that can be simultaneously satisfied. An $\ell$-CSP-$D$ instance
$\mathcal{I}$ over $n$ variables with constraint family $\mathcal{F}$ is
described by a collection of constraints
$\\{(f,x_{i_{1}},\dots,x_{i_{\ell}})\\}$ with $f\in\mathcal{F}$ and
$i_{1},\dots,i_{\ell}\in[n]$. It is possible to approximate the maximum number
of satisfiable constraints $\max(\mathcal{I})$ up to error $\epsilon n^{k}$
with probability at least $1-\delta$ using

$\widetilde{O}\left(\frac{|\mathcal{F}|\Sigma^{7}\ell^{2}}{\epsilon^{7}}\right)$

queries444A query to the instance $\mathcal{I}$ takes the form
$Q=(f,x_{i_{1}},\dots,x_{i_{\ell}})$ and returns 1 if $Q\in\mathcal{I}$ and 0
otherwise. and time
$\exp\big{(}\widetilde{O}\big{(}\frac{\Sigma^{3}\ell}{\epsilon^{3}}\big{)}\big{)}$.

The problem of $k$-clusterability is a special instance of this problem.
Define the family $\mathcal{F}=\\{f^{+},f^{-}:[k]^{2}\to\\{0,1\\}\\}$ by
$f^{+}(x,y)=1$ if $x=y$ and $0$ otherwise, and $f^{-}(x,y)=0$ if $x=y$ and $1$
otherwise. Now given a signed graph $G$, we can define a collection
$\mathcal{I}_{G}$ of constraints by adding constraint $(f^{+},x,y)$ if $(x,y)$
is a positive edge, and $(f^{-},x,y)$ if $(x,y)$ is a negative edge. We can
query $\mathcal{I}_{G}$ using a single query to the adjacency matrix of $G$.
Moreover, the $k$-frustration index of $G$ is given by

$|E(G)|-\max(\mathcal{I}_{G}),$

with $|E(G)|$ the number of edges in $G$. Using that $\Sigma=1$,
$|\mathcal{F}|=2$ and $\ell=2$ for the family $\mathcal{F}$, it follows from
Theorem 15 that we can find an $\epsilon N^{2}$ approximation of
$\max(\mathcal{I}_{G})$ using $\widetilde{O}(1/\epsilon^{7})$ queries and time
$\exp(\widetilde{O}(1/\epsilon^{3}))$. In addition we can easily approximate
$|E(G)|$ to additive error $\epsilon N^{2}$ by randomly sampling entries of
the adjacency matrix of $G$. Combining these gives an approximation algorithm
for the $k$-frustration index with additive error $\epsilon N^{2}$, and hence
a tolerant tester for $k$-clusterability.

##  Appendix B Technical details for clusterability testing in bounded-degree
model

###  B.1 Modified Markov chain

In this section we describe the technical details on the modified Markov chain
proposed by Goldreich and Ron [GR99]. Let $G=(V,E,\sigma)$ be a signed graph
and let $G^{+}=(V,E^{+})$ be the subgraph induced on the positive edge set.
Let $H^{+}$ be a subgraph of $G^{+}$, and let $\ell_{1},\ell_{2}$ be integers.
The boundary $B(H^{+})$ of $H^{+}$ consists of those vertices in $H^{+}$ that
have an edge in $G^{+}$ that leaves $H^{+}$. Let $\hat{H}^{+}$ be the graph
obtained by appending to every boundary node $v\in B(H^{+})$ an _auxiliary
path_ of length $\ell_{1}$ with node set $a_{v,1},\dots,a_{v,\ell_{1}}$.

We will define a surjective mapping $\phi$ from random walks $W$ in $G^{+}$ of
length $L=\ell_{1}\ell_{2}$ to walks $\phi(W)$ in $\hat{H}^{+}$ of length
$\ell_{1}$. If $W=v_{0},\dots,v_{L}$, let $i_{0},\dots,i_{k}$ be the timesteps
for which $v_{i_{j}}\in H^{+}$. The mapping is defined essentially by
contracting all length-$(<\ell_{2})$ walks outside of $H^{+}$, and routing any
length-$(\geq\ell_{2})$ walk outside of $H^{+}$ onto an auxiliary path. More
precisely:

  * •

_Contract:_ If $W$ does not perform $\ell_{2}$ or more consecutive steps
outside of $H^{+}$ before it made $\ell_{1}$ steps (in total) in $H^{+}$, then

$\phi(W)=v_{i_{0}},\dots,v_{i_{\ell_{1}}}.$

  * •

_Contract and route:_ In the other case, let $i_{r}$ be the first index that
precedes a walk of $\geq\ell_{2}$ consecutive steps outside of $H^{+}$. Then

$\phi(W)=v_{i_{0}},\dots,v_{i_{r}},a_{v_{i_{r}},1},\dots,a_{v_{i_{r}},\ell_{1}-i_{r}}.$

Figure 3: Illustration of mapping $\phi$ from walks of length
$L=\ell_{1}\ell_{2}$ on $G^{+}$ to walks of length $\ell_{1}$ on
$\hat{H}^{+}$.

The distribution $\Pr_{G}(W)$ over length-$L$ walks $W$ in $G^{+}$ induces a
distribution $\Pr_{M}(U)$ over length-$\ell_{1}$ walks $U$ in $\hat{H}^{+}$ by
setting

$\Pr_{M}(U)=\sum_{W:\phi(W)=U}\Pr_{G^{+}}(W).$

We now define a Markov chain $M(H^{+})$ on $\hat{H}^{+}$ such that
length-$\ell_{1}$ walks $U$ of $M(H^{+})$ have the same distribution
$\Pr_{M}(U)$. In the definition of $M(H^{+})$ we use the quantity
$p^{H}_{v,u}(t)$ for $v,u\in H^{+}$, which denotes the probability that a
random walk from $v$ will take $t-1$ steps outside of $H^{+}$ and end in $u$
at the $t$-th step. The Markov chain $M(H^{+})$ is defined as follows:

  * •

For every $v,u\in H^{+}$: $q_{v,u}=\sum_{t=1}^{\ell_{2}-1}p^{H}_{v,u}(t)$.

  * •

For every $v\in B(H^{+})$:

    * –

$q_{v,a_{v,1}}=\sum_{u\in H}\sum_{t\geq\ell_{1}}p^{H}_{v,u}(t)$,

    * –

for every $\ell$, $1\leq\ell<\ell_{1}$, $q_{a_{v,\ell},a_{v,\ell+1}}=1$,

    * –

for every $u\in H$,
$q_{a_{v,\ell_{1}},u}=q_{v,a_{v,1}}^{-1}\sum_{t\geq\ell_{2}}p^{H}_{v,u}(t)$.

The following claim states that if we find a bad cycle with the modified
Markov chain, then we will also find a bad cycle using the original random
walk. We say that a set of walks _results in a bad cycle_ if the original
graph $G$ has a negative edge between two distinct vertices of the walks.

######  Claim 16.

Assume that there exists $s$ and $m$ such that $m$ walks of $M(H^{+})$ of
length $\ell_{1}$ and starting from $s$ result in a bad cycle with probability
at least $0.99$. Then $m$ random walks in $G^{+}$ of length
$L=\ell_{1}\ell_{2}$ and starting from $s$ will also result in a bad cycle
with probability at least $0.99$.

###### Proof.

Let $U_{1}$ and $U_{2}$ denote length-$t$ walks of $M(H^{+})$ that result in a
bad cycle. If $W_{1}$ and $W_{2}$ are length-$L$ walks on $G^{+}$ with
$\phi(W_{1})=U_{1}$ and $\phi(W_{2})=U_{2}$, then $W_{1}$ and $W_{2}$ will
also result in a bad cycle. Now let $I_{\mathrm{bad}}(X_{1},\dots,X_{m})$
denote the indicator of whether the walks $X_{1},\dots,X_{m}$ (in $G^{+}$ or
$M(H^{+})$) form a bad cycle. By our former remark we know that
$I_{\mathrm{bad}}(W_{1},\dots,W_{m})\geq
I_{\mathrm{bad}}(\phi(W_{1}),\dots,\phi(W_{m}))$. We can lower bound the
probability that $m$ walks in $G^{+}$ form a bad cycle:

$\displaystyle\sum_{W_{1},\dots,W_{m}}$
$\displaystyle\Pr_{G^{+}}(W_{1})\dots\Pr_{G^{+}}(W_{m})I_{\mathrm{bad}}(W_{1},\dots,W_{m})$
$\displaystyle=\sum_{U_{1},\dots,U_{m}}\left(\sum_{W_{1}:\phi(W_{1})=U_{1}}\dots\sum_{W_{m}:\phi(W_{m})=U_{m}}\Pr_{G^{+}}(W_{1})\dots\Pr_{G^{+}}(W_{m})I_{\mathrm{bad}}(W_{1},\dots,W_{m})\right)$
$\displaystyle\geq\sum_{U_{1},\dots,U_{m}}\left(\sum_{W_{1}:\phi(W_{1})=U_{1}}\dots\sum_{W_{m}:\phi(W_{m})=U_{m}}\Pr_{G^{+}}(W_{1})\dots\Pr_{G^{+}}(W_{m})I_{\mathrm{bad}}(U_{1},\dots,U_{m})\right)$
$\displaystyle=\sum_{U_{1},\dots,U_{m}}\Pr_{M}(U_{1})\dots\Pr_{M}(U_{m})I_{\mathrm{bad}}(U_{1},\dots,U_{m})$
$\displaystyle\geq 0.99,$

which proves our claim. ∎

###  B.2 Sufficient condition for bad cycle

See 12

###### Proof.

For $1\leq i,j\leq m$, let $\eta_{i,j}$ be the random variable so that
$\eta_{i,j}=1$ if the $i$-th and $j$-th walk form a bad cycle and otherwise
$\eta_{i,j}=0$. We will bound the probability that we do not find a bad cycle,
which is $\Pr(\sum_{i<j}\eta_{i,j}=0)$. To this end we will use the bound

$\Pr\left[\sum_{i<j}\eta_{i,j}=0\right]\leq\frac{\mathrm{Var}\left[\sum_{i<j}\eta_{i,j}\right]}{\mathbb{E}[\sum_{i<j}\eta_{i,j}]^{2}}$
(1)

which can be derived from Chebyshev’s inequality [AS04, Theorem 4.3.1].

To bound $\mathrm{Var}\left[\sum_{i<j}\eta_{i,j}\right]$, we define
$\bar{\eta}_{i,j}=\eta_{i,j}-\mathbb{E}[\eta_{i,j}]$. By [GR99, Equation (20)]
we can then rewrite

$\mathrm{Var}\left[\sum_{i<j}\eta_{i,j}\right]=\mathbb{E}\left[\left(\sum_{i<j}\bar{\eta}_{i,j}\right)^{2}\right]=\binom{m}{2}\,\mathbb{E}\left[\bar{\eta}_{1,2}^{2}\right]+4\binom{m}{3}\,\mathbb{E}\left[\bar{\eta}_{1,2}\bar{\eta}_{2,3}\right].$

The first term is bounded by
$\mathbb{E}\left[\bar{\eta}_{1,2}^{2}\right]\leq\mathbb{E}\left[\eta_{1,2}^{2}\right]=\mathbb{E}\left[\eta_{1,2}\right]$.
Now we bound the second term, where we let $v_{i}$ denote the endpoint of the
$i$-th walk:

$\displaystyle\mathbb{E}\left[\bar{\eta}_{1,2}\bar{\eta}_{2,3}\right]\leq\mathbb{E}\left[\eta_{1,2}\eta_{2,3}\right]$
$\displaystyle=\Pr\left[\eta_{1,2}=1\text{ and }\eta_{2,3}=1\right]$
$\displaystyle=\Pr\left[\eta_{1,2}=1\text{ and }(v_{2},v_{3})\in E^{-}\right]$
$\displaystyle=\sum_{u}\Pr\left[\eta_{1,2}=1\text{ and }v_{2}=u\text{ and
}(u,v_{3})\in E^{-}\right]$ $\displaystyle=\sum_{u}\Pr\left[(u,v_{3})\in
E^{-}\right]\cdot\Pr\left[\eta_{1,2}=1\text{ and }v_{2}=u\right]$
$\displaystyle=\sum_{u}\Bigg{(}\sum_{w:(u,w)\in
E^{-}}\Pr\left[v_{3}=w\right]\Bigg{)}\cdot\Pr\left[\eta_{1,2}=1\text{ and
}v_{2}=u\right]$
$\displaystyle\leq\left(d\max_{w}\Pr[v_{3}=w]\right)\sum_{u}\Pr\left[\eta_{1,2}=1\text{
and }v_{2}=u\right]$
$\displaystyle=\left(d\max_{w}\Pr[v_{3}=w]\right)\mathbb{E}[\eta_{1,2}]$
$\displaystyle\leq dF\alpha\,\mathbb{E}[\eta_{1,2}].$

If we denote $\gamma=\mathbb{E}[\eta_{1,2}]$ then we get the bound
$\mathrm{Var}\left[\sum_{i<j}\eta_{i,j}\right]\in
O(m^{2}\gamma+m^{3}dF\alpha\gamma)$. Combined with (1) this gives the bound

$\Pr\left[\sum_{i<j}\eta_{i,j}=0\right]\in
O\left(\frac{m^{2}\gamma+m^{3}dF\alpha\gamma}{m^{4}\gamma^{2}}\right).$

If we let $E^{-}_{S}$ denote the set of negative edges with both endpoints
inside $S$ then we can lower bound

$\gamma=\sum_{(u,v)\in
E^{-}_{S}}q_{s,u}(t)q_{s,v}(t)\geq\alpha^{2}|E^{-}_{S}|.$

Combined with the fact that
$m\in\Omega\left(\frac{F}{\epsilon\alpha\sqrt{|S|}}\right)$ this gives the
bound $\Pr\left[\sum_{i<j}\eta_{i,j}=0\right]\in
O(\epsilon/(dF^{2})+1/\sqrt{|S|})$, which is $\leq 0.01$ for the right choice
of constants. ∎