  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.
