Stephen Pasteris
email: s.pasteris@cs.ucl.ac.uk

Fabio Vitale
email: fabio.vitale@inria.fr

Claudio Gentile
email: cla.gentile@gmail.com

Mark Herbster
email: m.herbster@cs.ucl.ac.uk

On Similarity Prediction and Pairwise Clustering

Keywords: Online clustering, similarity, clustering distance, interactive clustering

We consider the problem of clustering a finite set of items from pairwise similarity information. Unlike what is done in the literature on this subject, we do so in a passive learning setting, and with no specific constraints on the cluster shapes other than their size. We investigate the problem in different settings: i. an online setting, where we provide a tight characterization of the prediction complexity in the mistake bound model, and ii. a standard stochastic batch setting, where we give tight upper and lower bounds on the achievable generalization error. Prediction performance is measured both in terms of the ability to recover the similarity function encoding the hidden clustering and in terms of how well we classify each item within the set. The proposed algorithms are time efficient.

Introduction

In the problem of clustering through pairwise similarity, we have a finite set V of items that have to be suitably clustered into groups by means of information about the similarity/dissimilarity between pairs of such items. This information may come from diverse sources, depending on the specific application. For instance, in the well-known Entity Resolution problem, the goal is to identify and group together records, possibly from different data sources, that refer to the same entity and/or individual, e.g., different pictures of the same person, different ways of addressing the same author of a scientific paper, different names of the same organization, different accounts of the same user of a recommendation service, etc. In these and many other examples of Entity Resolution, one often leverages attributes associated with these entities and, by comparing these attributes, determine very likely matches and mismatches between pairs of entities.

Another related application is community detection in Social Networks, where we naturally view V as the nodes of an edge-signed graph, and we are allowed to observe the sign of some edges carrying information about whether some pairs of nodes/individuals belong to the same community (i.e., they are "similar") or not (they are "dissimilar"). Coarsely speaking, the problem is then trying to reconstruct the communities based on the observed relationships and, as a byproduct, inferring the sign of new pairwise relationships. Yet, this inference process is clearly prone to errors, for we do not observe all possible pairwise relationships over V . Moreover, small-world phenomena have to be taken into duly account, since this is a typical scenario where the clusters are strongly unbalanced in size, and we would like to be able to take advantage of this pattern as well.

In this paper, we consider the task of building a clustering of a finite set of items V from pairwise similarity/dissimilarity information. This information is assumed to be consistent with an unknown clustering D = {D 1 , . . . , D k } that we want to reconstruct. We measure the reconstruction error in different ways, depending on whether our algorithms output after training a clustering C or merely similarity relationship Y (which need not be transitive). In the former case, our metric will be the misclassification error between C and D, which is essentially the number of items in the learner's output clustering C that are misclassified, as compared to the ground truth D. In the latter case, our reconstruction error will be the Hamming (distance) error between Y and D (D being viewed as a transitive similarity relationship over V ), which is essentially the number of item pairs labeled by ground truth D that are misclassified by C. We investigate two learning settings, an online setting in the mistake bound model [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF], and a batch stochastic setting with train/test split. In the online setting, we deliver a tight characterization of the predictive complexity of the problem when we have no specific constraints on the cluster shapes other than their size and their number. We give upper and lower mistake bounds, the upper bound being achieved by a novel and efficient algorithm whose predictive bias is towards the existence of a few large clusters and many small ones (just as in the above mentioned community detection scenario). By means of standard online-to-batch conversions, these upper bounds can immediately be turned to generalization error bounds holding in a batch stochastic setting w.r.t. the Hamming error. Yet, our focus in batch stochastic settings is on misclassification error, rather than Hamming error. Assuming randomly drawn training pairs, we prove tight upper and lower bounds on the achievable misclassification error on unseen pairs, the bridge between the two settings being established by a novel reduction turning small Hamming error into small misclassification error. Related work. The problem we are considering here can be seen as an instance of matrix & metric learning through noise-free labels. The field includes a fair amount of work, hence we can hardly do it justice here. We now outline some of the main contributions in matrix & metric learning, with an emphasis on those we believe are mostly related to the current paper. Relevant work in matrix learning, specifically in online settings, includes [START_REF] Tsuda | Matrix exponentiated gradient updates for on-line learning and bregman projections[END_REF]; [START_REF] Warmuth | Winnowing subspaces[END_REF]; [START_REF] Cavallanti | Linear algorithms for online multitask classification[END_REF]; [START_REF] Kakade | Regularization techniques for learning with matrices[END_REF]; [START_REF] Hazan | Near-optimal algorithms for online matrix prediction[END_REF]; [START_REF] Gentile | Online similarity prediction of networked data from known and unknown graphs[END_REF]; Herbster et al. (2016). In all these works, a major effort is devoted to designing appropriate regularization methods to drive the online optimization process and/or to incorporate available side information, spectral sparseness being of special concern. Yet, the resulting algorithms appear to be too general to deliver tight bounds for the special problem we are considering here and, moreover, their scaling properties make them unfit to practical usage for large problem instances. Early work in the mistake bound setting considered the problem of learning a binary relation over a finite set Goldman et al. (1993); [START_REF] Goldman | Learning binary relations using weighted majority voting[END_REF]. This setting generalizes online similarity prediction, but however leads to weaker bounds for similarity prediction. Metric learning is the special case of matrix learning where the matrix to be learned is positive semi-definite.

Representative works include [START_REF] Xing | Distance metric learning with application to clustering with side-information[END_REF][START_REF] Shalev-Shwartz | Online and batch learning of pseudo-metrics[END_REF]; [START_REF] Maurer | Learning similarity with operator-valued large-margin classifiers[END_REF]; [START_REF] Cao | Generalization bounds for metric and similarity learning[END_REF]. In particular, [START_REF] Cao | Generalization bounds for metric and similarity learning[END_REF] work out generalization bounds based on a Rademacher complexity analysis which is again too general to deliver tight bounds for our specific problem; besides, they essentially consider only a Hamming distance-like error.

In short, what distinguishes our work from the above previous work is that we produce not just similarity functions, but instead construct clusterings with an associated tight misclassification error analysis.

The so-called matrix completion task is also related to our work (see, e.g., [START_REF] Koltchinskii | Nuclear norm penalization and optimal rates for noisy matrix completion[END_REF] for a representative work, as well as references therein). Yet, the typical goal there is to come up with matrix recovery methods whose error rates are again measured through a Hamming distance-like error (i.e., the Frobenious norm distance), with no specific concerns in clustering.

Closer in spirit to our work is the general line of research on semi-supervised clustering/clustering with side information, where the must-link/cannot-link constraints can be seen as similarity feedback. Known references, mostly application-oriented, include [START_REF] Ben-Dor | Clustering gene expression patterns[END_REF]; [START_REF] Demiriz | Semi-supervised clustering using genetic algorithms[END_REF]; [START_REF] Basu | A probabilistic framework for semi-supervised clustering[END_REF]; [START_REF] Kulis | Semi-supervised graph clustering: a kernel approach[END_REF], the formal statements therein being fairly different from ours. Somewhat closer to our paper from the formal standpoint within semi-supervised clustering is the thread on interactive clustering/clustering with queries. Here, the learner is allowed to interactively ask for feedback in the form of suitable queries, e.g., split and merge queries [START_REF] Balcan | Clustering with interactive feedback[END_REF][START_REF] Awasthi | Local algorithms for interactive clustering[END_REF], and similarity/same-cluster queries [START_REF] Davidson | Top-k and clustering with noisy comparisons[END_REF][START_REF] Ashtiani | Clustering with same-cluster queries[END_REF]Mazumdar and Saha, 2017a,b). Unlike our paper, in many of these works, the goal is to achieve exact, rather than approximate, reconstruction of the ground-truth clustering by asking as few queries as possible. As a sample of the available results in this literature, in the interactive feedback paper of [START_REF] Balcan | Clustering with interactive feedback[END_REF], the authors focus on clusters having specific shapes, that is, coming from a specific collection B of subsets of V . They show that the number of queries that suffice is either constant or logarithmic in n, but is also dependent on the "descriptional" complexity of B, e.g., if V is a set of n points on the real line and B is the set of intervals, then k log n queries suffice; more generally, O(k 3 log |B|) queries are enough when computationally inefficient algorithms are also considered. Yet, generalizing their argument to clusters of arbitrary shapes (i.e., B = 2 V ), as we have them here, easily leads in general to the trivial bound of O(n) queries. [START_REF] Davidson | Top-k and clustering with noisy comparisons[END_REF] show that Θ(k n) similarity queries are both necessary and sufficient to achieve exact reconstruction, the lower bound holding specifically in the case of (almost) equally-sized clusters. Yet, unlike our paper, they work in an active learning setting. Still in the active setting, Mazumdar and Saha (2017a,b) consider ways to sharpen the above bound by means of further side information available to the learner beyond queries. Their results are generally incomparable to ours, for besides dealing with active learning and exact reconstruction, they also allow for similarity labels to be noisy.

Finally, correlation clustering [START_REF] Bansal | Correlation clustering[END_REF] is also similar in flavor to some of our results. In correlation clustering, a similarity relationship Y on item pairs is given, and the goal is to find a clustering C which minimizes the Hamming error between Y and C. The problem, as stated, is NP-hard, and a number of approximation algorithms exist (e.g., [START_REF] Bansal | Correlation clustering[END_REF]; [START_REF] Demaine | Correlation clustering in general weighted graphs[END_REF]). Although inspired by these results as well, our focus here is slightly different: we seek to provide efficient algorithms that compute a clustering with associated predictive performance guarantees.

Preliminaries and Notation

We now introduce our main notation along with basic preliminaries. Given a finite set V = {1, . . . , n}, a clustering D over V is a partition of V into sets D = {D 1 , . . . , D k }. Each D j is called a cluster. A similarity graph G = (V, P) over V is an undirected (but not necessarily connected) graph where, for each pairing (v, w) ∈ V 2 , v and w are similar if (v, w) ∈ P, and dissimilar, otherwise. Notice that the similarity relationship so defined need not be transitive. We shall interchangeably represent a similarity graph over V through a binary n × n similarity matrix Y = [y v,w ] n×n v,w=1 whose entry y v,w is 1 if items v and w are similar, and y v,w = 0, otherwise. A clustering D over V can be naturally associated with a similarity graph G = (V, P D ) whose edge set P D is defined as follows: given v, w ∈ V , then (v, w) ∈ P D if and only if there exists a cluster D ∈ D with v, w ∈ D. In words, G is made up of k disjoint cliques. It is only in this case that the similarity relationship defined through G is transitive. Matrix Y represents a clustering if, after permutation of rows and columns, it ends up being block-diagonal, where the i-th block is a d i × d i matrix of ones, d i being the size of the i-th cluster. Given clustering D, we find it convenient to define a map µ D : V → {1, . . . , k} in such a way that for all v ∈ V we have v ∈ D µ D (v) . In words, µ D is a class assignment mapping, so that v and w are similar w.r.t. D if and only if µ D (v) = µ D (w).

Given two similarity graphs G = (V, P) and G = (V, P ), the Hamming (distance) error between G and G , denoted here as HA(P, P ), is defined as

HA(P, P ) = {(v, w) ∈ V 2 : (v, w) ∈ P ∧ (v, w) / ∈ P ∨ (v, w) / ∈ P ∧ (v, w) ∈ P } ,
where |A| is the cardinality of set A. The same definition applies in particular to the case when either G or G (or both) represent clusterings over V . By abuse of notation, if D is a clustering and G = (V, P) is a similarity graph, we will often write HA(D, P) to denote HA(P D , P), where (V, P D ) is the similarity graph associated with D, so that HA(P D , D) = 0. Moreover, if the similarity graphs G and G are represented by similarity matrices, we may equivalently write HA(Y, Y ), HA(Y, D), and so on. The quantity HA(, ) is very closely related to the so-called Mirkin metric [START_REF] Mirkin | Mathematical classification and clustering[END_REF] over clusterings, as well as to the (complement of the) Rand index [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF], see, e.g., [START_REF] Meila | Local equivalences of distances between clusterings-a geometric perspective[END_REF].

Another "distance" that applies specifically to clusterings is the misclassification error distance, denoted here as ER(, ), and defined as follows. Given two clusterings C = {C 1 , . . . , C } and D = {D 1 , . . . , D k } over V , repeatedly add the empty set to the smaller of the two so as to obtain = k. Then ER(C, D) = min e.g., in Meila (2007). An illustrative example to gain intuition on the ER metric is the following: Suppose V = {1, 2, 3, 4, 5, 6}, and we have clusterings C = {{1, 2, 3}, {4, 5}, {6}} and D = {{1, 2}, {3, 4}, {5}, {6}}. In order to turn C into D, we operate on C by moving item 3 from the first cluster {1, 2, 3} to the second cluster {4, 5}, and item 5 from the second cluster {4, 5} to a new cluster. Since this is the minimal number of moves we need to make, we have ER(C, D) = 2. Finally, the (Jaccard) distance dist(A, B) between sets A and B, with A, B ⊆ V is defined as

dist(A, B) = |A \ B| + |B \ A| |A ∪ B| .
Recall that dist(, ) is a proper metric on the collection of all finite sets. Moreover, observe that dist(A, B) = 1 if and only if A and B are disjoint.

Learning settings

We are interested in predicting similarities and/or computing clusterings over V = {1, . . . , n} based on binary similarity/dissimilarity information contained in a similarity matrix Y , whose entries are only partially observed. In particular, we are given a training set S of m binary-labeled pairs (v, w), y v,w ∈ V 2 × {0, 1}, drawn uniformly at random1 from V 2 , and our goal is to either build a clustering C over V so as to achieve small misclassification error ER(C, Y ), or a similarity prediction model (that is, an estimated similarity matrix) Ŷ so as to achieve small Hamming error HA( Ŷ , Y ). In both cases, the error is computed on the whole matrix Y (clearly enough, this is sensible only when m is significantly smaller than n 2 ). The similarity matrix Y will always be consistent with a given unknown clustering D over V . Notice that the number of clusters k will also be unknown to the prediction/clustering algorithms. Hence, if the goal is to simply predict similarities over V , the error of our inference procedures will be measured through HA. On the other hand, if our final goal is not to merely predict similarities, but to produce a clustering over V then our error will be measured through ER. In fact, we shall do the above in different ways, corresponding to the content of the next three sections:

1. By investigating the problem of online prediction of pairwise similarities in the standard mistake bound model of online learning [START_REF] Littlestone | Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm[END_REF]. Using a simple online-tobatch conversion, we will make the online algorithm compute a similarity prediction model Ŷ for the unseen entries of Y . Since Ŷ itself is not guaranteed to be a clustering over V , error in this case will be measured through HA( Ŷ , Y ).

2. By an indirect approach that exhibits a (tight) reduction from similarity prediction methods measured through HA (like those coming from Item 1 above) to clustering methods measured through ER. The machinery developed in Item 1 may thus be a possible input to this reduction.

3. Through a direct approach, by presenting a specific baseline algorithm whose goal is to build a clustering C over V based on a training set S drawn at random, and the discrepancy between C and D will be measured through ER(C, D).

Online Similarity Prediction

In this section, we consider similarity prediction in the online mistake bound model, where an example sequence S = (v 1 , w 1 ), y v 1 ,w 1 , . . . , (v m , w m ), y vm,wm is revealed incrementally in rounds. In the t-th round the algorithm is compelled to predict the similarity label y vt,wt ∈ {0, 1}, given the previous t -1 examples (v 1 , w 1 ), y v 1 ,w 1 , . . . , (v t-1 , w t-1 ), y v t-1 ,w t-1 , and (v t , w t ). Denote by ŷt ∈ {0, 1} the prediction issued by the algorithm in round t. After prediction, the true label y t = y vt,wt is revealed, and we say that the algorithm has made a prediction mistake if ŷt = y t . The aim is to minimize the number of mistaken predictions on any example sequence S. Sequence S can be generated by an adaptive adversary, but the labels y vt,wt are assumed to be consistent with an underlying clustering

D = {D 1 , D 2 , . . . , D k } over V , with cluster sizes d 1 , d 2 , . . . , d k . Throughout, we assume w.l.o.g. that d 1 ≤ d 2 ≤ . . . ≤ d k .
This problem has been studied before, and can be cast as a special case of online matrix/metric learning (e.g., Shalev-Shwartz et al. ( 2004 (2013)). Yet, a direct application of techniques available from those papers would give rise to suboptimal results in terms of both mistake bound and running time. For instance, we may use the adaptation of the Matrix Winnow algorithm [START_REF] Warmuth | Winnowing subspaces[END_REF] from [START_REF] Gentile | Online similarity prediction of networked data from known and unknown graphs[END_REF], that provides a mistake bound of the form

|Φ G | max v,w∈V R G v,w log n, where |Φ G | is the cutsize determined by a graph G over V , and the R G v,w are the corresponding effective resistance factors. If G therein is the complete graph 2 then it is easy to see that |Φ G | = k i=1 d i (n -d i ) = n 2 -k i=1 d 2 i
, and all effective resistance factors R G v,w are 2/n. Up to multiplicative constants, this results in a mistake bound of the form

n - 1 n k i=1 d 2 i log n . (1)
Moreover, the running time per round of this algorithm is O(n 3 ), since it requires to maintain and update at every round the SVD of a n × n matrix. An even simpler baseline (belonging to folklore) -see pseudocode in Algorithm 1 -is one where the algorithm maintains on the fly a spanning forest over V (i.e., a collection of disjoint trees covering V , each tree being a cluster), and at round t the algorithm predicts 1-"similar" on (v t , w t ) if v t and w t belong to the same tree, and 0-"dissimilar", otherwise. If the actual label y vt,wt is 1 and the algorithm is mistaken, then the two nodes v t and w t get connected by an edge, thereby merging two trees of the current forest into a bigger tree. It is easy to argue that if we start off from the degenerate forest made up of n singletons (as in Algorithm 1), this algorithm makes at most n -k mistakes. Thus this algorithm has a predictive bias towards many "small" clusters.

Given the above state of affairs, a natural question is what is the optimal mistake bound for the problem of online learning k clusters of sizes d 1 ≤ d 2 ≤ . . . ≤ d k over V = {1, . . . , n} through pairwise similarity labels. In the rest of this section, we describe and analyze the time-efficient algorithm Oppa (Online Pairwise Prediction Algorithm) which incorporates a different predictive bias than the folklore algorithm mentioned above. We then complement Algorithm 1 Folk online clustering algorithm. Input: Item set V = {1, . . . , n}. Initialization:

• C = {{v} : v ∈ V }; // Let C v denote the cluster containing v.
For t = 1, . . . , m:

1. Get pair (v t , w t ) ∈ V 2 ; 2. If C vt = C wt then ŷt = 1, else ŷt = 0: 3. Observe y t := y vt,wt ; if ŷt = y t then C ← C \ C w and C v ← C v ∪ C w ; Output: Clustering C .
our analysis by showing through a lower bounding argument that no online algorithm can do better in terms of mistake bounds up to constant factors, thereby showing that Oppa is essentially optimal.

Oppa is described in Algorithm 2. Whereas the folklore algorithm is predictively biased to the case of many small clusters (large k). Oppa is predictively biased to the case of few large "majority" clusters (implying a large d k ). Thus the algorithms incorporate distinct predictive biases which are indirectly in opposition. In common with the folklore algorithm we maintain a clustering C, and we predict consistently so that when two points are known to be in the same cluster we predict "similar." However, unlike the folklore algorithm if we do not know the two points to be "similar" we do not necessarily predict "dissimilar", in fact if it is the first time we have encountered both points we predict "similar." Intuitively this follows from the different predictive biases, as e.g., if we make a mistake on two novel points we now know the cardinality d k of the majority cluster is reduced by one. Oppa maintains both a clustering C and a tag in {∅, A, B} for each cluster C ∈ C, the tags controlling both prediction and updates, as seen in Algorithm 2. The tagging through an amortized analysis (see proof of Theorem 1) enables one to prove that the potential cardinality of the majority cluster is reduced by one every five mistakes. Both the folklore algorithm and Oppa can be implemented with a standard disjoint set data-structure ensuring a cumulative time complexity for m predictions of O((n + m) log * n) for both algorithms.

We have the following result.

3 1) is weaker than Theorem 1 by at least a logarithmic factor. On the other hand, the latter is again generally incomparable to the folklore bound n -k. By constrast, the following (almost matching) lower bound holds.

Theorem 1 Let D = {D 1 , . . . , D k } be any clustering of V = {1, . . . , n}, with d i = |D i |, i = 1, . . . ,
Algorithm 2 The Online Pairwise Prediction Algorithm ( Oppa ). Input: Set V = {1, . . . , n}. Initialization:

• C = {{v} : v ∈ V }; // Let C v denote the cluster containing v. • For any v ∈ V , set tag ω(C v ) ← ∅.
For t = 1, . . . , m: Theorems 1 and 2 combined together provide a reasonably tight characterization of the complexity of online learning clusterings through pairwise similarity labels.

1. Get pair (v t , w t ) ∈ V 2 ; 2. If C vt = C wt then ŷt = 1; //predict "
(∅, ∅) Similar (ŷ t = 1) ζ ← (A, A) (∅, A) Similar (ŷ t = 1) ζ ← (A, B) (A, ∅) Similar (ŷ t = 1) ζ ← (B, A) (∅, B) Dissimilar (ŷ t = 0) C ← MERGE A (C, C vt , C wt ) (B, ∅) Dissimilar (ŷ t = 0) C ← MERGE A (C, C vt , C wt ) (A, B) Dissimilar (ŷ t = 0) C ← MERGE A (C, C vt , C wt ) (B, A) Dissimilar (ŷ t = 0) C ← MERGE A (C, C vt , C wt ) (A, A) Dissimilar (ŷ t = 0) C ← MERGE A (C, C vt , C wt ) (B, B) Dissimilar (ŷ t = 0) C ← MERGE B (C, C vt , C wt ) Algorithm 3 The MERGE A (, , )/MERGE B (, , ) subroutine. Input: Clustering C, clusters C, C ∈ C. 1. Set C * ← C ∪ C ; 2. Set C ← (C \ {C, C }) ∪ {C * }; 3. If operation is MERGE A (C, C, C ) set ω(C * ) ← A; 4. If operation is MERGE B (C, C, C ) set ω(C * ) ← B; Output: Clustering C, tagging ω(•).
Randomly drawn sequences. Suppose now that the training sequence S is drawn uniformly at random. According to a standard online-to-batch conversion [START_REF] Helmbold | On weak learning[END_REF], one can pick at random one of the m similarity prediction models4 produced by Oppa during its online functioning, call this model ŶS , and have a guarantee that the probability of making a mistake on an unseen pair (v, w) drawn again uniformly at random is O( n-d k m ). The probability also takes into account the random draw of S and the random draw of the model within the sequence of m models. Then, recalling the definition of HA(, ) from Section 2, the upper bound in Theorem 1 immediately entails the following.

Corollary 3 Let D = {D 1 , . . . , D k } be any clustering of V = {1, . . . , n}, with d i = |D i |, i = 1, . . . , k, and d 1 ≤ d 2 ≤ . . . d k . Let S = (v 1 , w 1 ), y v 1 ,w 1 , .
. . , (v m , w m ), y vm,wm be labeled according to D, and be such that (v t , w t ) are drawn uniformly at random from V 2 . Moreover, let Ŷt be the similarity prediction model produced by Oppa at the beginning of round t, for t = 1, . . . , m. If ŶS is drawn uniformly at random from the sequence Ŷ1 , . . . , Ŷm , then

E HA( ŶS , Y ) = O n 2 m (n -d k ) . (2)
In the above, the expectation is over the random draw of S and the random draw of ŶS from the sequence Ŷ1 , . . . , Ŷm .

From HA to ER

This section exhibits a clustering algorithm that takes as input a similarity graph (V, P) (like one produced after a training phase as in Corollary 3 of Section 3) and gives in output a clustering C over V . The primary goal here is to show that for any other clustering D over V , ER(C, D) is tightly related to HA(P, D). This algorithm will be a building block for later results, but it can also be of independent interest. Our algorithm, called Robust Greedy Clustering Algorithm (rgca, for brevity), is displayed in Algorithm 4. The algorithm has two stages. The first stage is a robustifying stage where the similarity graph (V, P) is converted into a (more robust) similarity graph (V, Q) as follows: Given two distinct vertices v, w ∈ V , we have (v, w) ∈ Q if and only if the Jaccard distance of their neighbourhoods (in (V, P)) is not bigger than 1 -a, for some distance parameter a ∈ [0, 1]. The second stage uses a greedy method to convert the graph (V, Q) into a clustering C. This stage proceeds in "rounds". At each round t we have a set A t of all vertices which have not yet been assigned to any clusters. We then choose α t to be the vertex in A t which has the maximum number of neighbours (under the graph (V, Q)) in A t , and take this set of neighbours (including α t ) to be the next cluster.

From a computational standpoint, the second stage of rgca runs in O(n 2 log n) time, since on every round t we single out α t (which can be determined in log n time by maintaining a suitable heap data-structure), and erase all edges emanating from α t in the similarity Algorithm 4 The Robust Greedy Clustering Algorithm Input: Similarity graph (V, P); distance parameter a ∈ [0, 1].

For all

v ∈ V , set Γ(v) ← {v} ∪ {w ∈ V : (v, w) ∈ P}; 2. Construction of graph (V, Q): //First stage For all v, w ∈ V with v = w: If dist (Γ(v), Γ(w)) ≤ 1 -a then (i, j) ∈ Q, otherwise (i, j) / ∈ Q; 3. Set A 1 ← V , and t ← 1; //Second stage 4. While A t = ∅: • For every v ∈ A t set N t (v) ← {v} ∪ {w ∈ A t : (v, w) ∈ Q}, • Set α t ← argmax v∈At |N t (v)|, • Set C t ← N t (α t ), • Set A t+1 ← A t \ C t ,
• t ← t + 1;

Output: C 1 , C 2 , ..., C , where = t -1.
graph (V, Q). On the other hand, the first stage of rgca runs in O(n 3 ) time, in the worst case, though standard techniques exist that avoid the all-pairs comparison, like a Locality Sensitive Hashing scheme applied to the Jaccard distance (e.g., (Rajaraman and Ullman, 2010, Ch.3)). We have the following result. Hence, if the chosen D is the best approximation to P w.r.t. HA(, ), and we interpret (V, P) as a noisy version of D, then small HA(P, D) implies small ER(C, D). In particular, HA(P, D) = 0 implies ER(C, D) = 0 (simply pick j = 1 in the minimum). Notice that this result only applies to the case when the similarity graph (V, P) is fully observed by our clustering algorithm. As we already said, (V, P) may in turn be the result of a similarity learning process when the similarity labels are provided by an unknown clustering D. In this sense, Theorem 4 will help us delivering generalization bounds (as measured by ER(C, D)), as a function of the generalization ability of this similarity learning process (as measured by HA(P, D)).

The problem faced by rgca is also related to the standard correlation clustering problem [START_REF] Bansal | Correlation clustering[END_REF]). Yet, the goal here is somewhat different, since a correlation clustering algorithm takes as input (V, P), but is aimed at producing a clustering C such that HA(P, C) is as small as possible.

In passing, we next show that the construction provided by rgca is essentially optimal (up to multiplicative constants). Let G D = (V, E D ) be the similarity graph associated with clustering D. We say that a clustering algorithm that takes as input a similarity graph over V and gives in output a clustering over V is consistent if and only if for every clustering D over V the algorithm outputs D when receiving as input G D . Observe that rgca is an example of a consistent algorithm. We have the following lower bound.

Theorem 5 For any finite set V , any clustering D = {D 1 , D 2 , . . . , D k } over V , any positive constant σ, and any consistent clustering algorithm, there exists a similarity graph (V, P) such that HA(P, D) ≤ σ, while

ER(C, D) ≥ min j=1,...,k 1 2d j σ -1 + 1 4 j-1 i=1 d i , (3)
or ER(C, D) ≥ n 2 , where C is the output produced by the algorithm when given (V, P) as input, and

d i = |D i |, i = 1, . . . , k, with d 1 ≤ d 2 ≤ . . . d k .
From the proof given in the appendix, one can see that the similarity graph (V, P) used here is indeed a clustering over V so that, as the algorithm is consistent, the output C must be such a clustering. This result can therefore be contrasted to the results contained, e.g., in [START_REF] Meila | Local equivalences of distances between clusterings-a geometric perspective[END_REF] about the equivalence between clustering distances, specifically Theorem 26 therein. Translated into our notation, that result reads as follows: ER(C, D) ≥ HA(P,D) 16d k . Our Theorem 5 is thus sharper but, unlike the one in [START_REF] Meila | Local equivalences of distances between clusterings-a geometric perspective[END_REF], it does not apply to any possible pairs of clusterings C and D, for in our case C is selected as a function of D.

We finally tie things together. The similarity graph (V, P) in input to rgca may for instance be the predictor learned by a similarity learning algorithm, like Matrix Winnow [START_REF] Warmuth | Winnowing subspaces[END_REF] or Oppa (Section 3). Since none of the two algorithms output a clustering over V (despite the training labels are indeed consistent with a ground truth clustering D), this is where our reduction rgca comes into play. For the sake of concreteness, suppose that (V, P) is the model ŶS generated by the online-to-batch conversion of Corollary 3 applied to Oppa after seeing m-many randomly drawn pairs (v t , w t ) labeled according to D, and let C be the corresponding clustering output by rgca . Then, combining Theorem 4 with Corollary 3, we conclude that C satisfies

E ER(C, D) ≤ E min j=1,...,k 12 d j HA(P, D) + j-1 i=1 d i ≤ min j=1,...,k 12 d j E HA(P, D) + j-1 i=1 d i = O min j=1,...,k 1 d j n 2 m (n -d k ) + j-1 i=1 d i , (4)
which is our generalization bound in the ER metric. As an example, if d i = n/k for all i, then we can pick j = 1 in Eq. ( 4) to achieve

E ER(C, D) = O k n 2 m . (5)
On the other hand, if D has few big clusters and many small ones the resulting bound looks significantly different. As an extreme situation, let for concreteness

d 1 = d 2 = . . . d k-h = 1, and d k-h+1 = d k-h+2 = . . . d k = n-k+h h
, for some small h such that 2 ≤ h < k. Then picking

j = k -h + 1 in (4) yields E ER(C, D) = O h n-k+h n 3
m + k , and if, say, h = 3 and k is either a constant ≥ 3 or k = o(n), then we have

E ER(C, D) = O n 2 m + k , (6)
as n grows large. Notice that ( 6) is typically smaller than (5), take for instance k = √ n, and m = n 3/2 : whereas Eq. ( 5) gives O(n) (which is vacuous, up to multiplicative constants, for this size of m), Eq. ( 6) yields a bound of O( √ n). Next, we take a more direct route to obtain alternative ER-based statistical guarantees.

A direct approach to bounding ER and a lower bound

In the previous section, we showed an indirect route to prove ER bounds. This route specifically applies to algorithms that do not output a clustering after training, but only a similarity model. Yet, there are algorithms, like the folk online clustering algorithm of Section 3 (Algorithm 1), that do indeed produce a clustering at the end of each online round. Hence, one is wondering whether a direct analysis in the ER metric for such algorithms can be carried out. In the next theorem, we show a simple generalization bound achieved by Algorithm 1 after training with m randomly drawn examples. Unlike the one in Eq. ( 4), we have been unable to obtain a meaningful dependence on the cluster sizes d i .

Theorem 6 Let D = {D 1 , . . . , D k } be any clustering of V = {1, . . . , n}, with d i = |D i |, i = 1, . . . , k, and d 1 ≤ d 2 ≤ . . . d k . Let S = (v 1 , w 1 ), y v 1 ,w 1 , . . . , (v m , w m ), y vm,wm be labeled according to D, and be such that (v t , w t ) are drawn uniformly at random from V 2 . Then Algorithm 1 returns a clustering C such that ER(C, D) is bounded as follows:

E ER(C, D) = O k n 2 m log n 2 m ,
the expectation with respect to a random draw of S.

It is instructive to compare the upper bounds contained in Theorem 6 to the one in Eq. ( 4), as specialized in ( 5) and ( 6). The bound in Theorem 6 tends to be weaker (by at least a log factor -compare to the equal-size case in ( 5)). Moreover, it does not show an explicit dependence on the cluster sizes d i , making it unable to leverage cluster unbalancedness, like in (6). On the other hand, the folk algorithm is definitely much faster to run than the combination rgca + Oppa.

To close this section, we complement our upper bounds in Eqs. ( 4)-( 6), and Theorem 6 by the following lower bound result, showing that the dependence of ER(, ) on k and n 2 cannot in general be eliminated.

Theorem 7 Given any k > 2 and any m < n 2 4 , there exists a clustering D of at most k clusters such that, for any algorithm having as input a randomly drawn training sequence of length m labeled according to D and giving in output clustering C, we have that E ER(C, D) = Ω min k n 2 m , n , the expectation with respect to a random draw of the training sequence.

Conclusions and Ongoing Research

We have investigated the general problem of learning a clustering over a finite set from pairwise similarity labels, with no specific constraints on the cluster shapes, other than their size. We did so in two settings:

1. An online setting, where we exhibited a novel characterization of the complexity of learning the clustering in the mistake bound model of online learning;

2. In a batch stochastic setting, where we took either an indirect route that steps through a reduction, called rgca, establishing a tight bridge between the two clustering metrics HA and ER, or a direct route, where we have shown as a yardstick the kind of misclassification error bounds a standard baseline may achieve for this problem.

Finally, we complemented the above results with an almost matching lower bound that applies to the ER metric when the training sequence is randomly drawn. Two extensions we are currently exploring are: i. extending the underlying statistical assumptions on data (e.g., sampling distribution-free guarantees) while retaining running time efficiency, and ii. studying other learning regimes, like active learning, under similar or broader statistical assumptions as those currently in this paper, possibly with sideinformation, as in, e.g., Mazumdar and Saha (2017a,b).

Appendix A. Proofs

A.1. Proof of Theorem 1

Proof Recall that D k = argmax D∈D |D|, and define for brevity V \k := V \ D k . The rounds where Oppa can make mistakes is one of the cases contained in the following table.

Case (v t , w t ) in: Value of ζ After: Round type a D k × V \k (∅, ∅) ζ ← (A, A) τ 2 b V \k × D k (∅, ∅) ζ ← (A, A) τ 2 c D k × V \k (∅, A) ζ ← (A, B) τ 6 d V \k × D k (A, ∅) ζ ← (B, A) τ 6 e D k × V \k (A, ∅) ζ ← (B, A) τ 3 f V \k × D k (∅, A) ζ ← (A, B) τ 3 g D k × D k (∅, B) C ← MERGE A (C, C v , C w ) τ 4 h D k × D k (B, ∅) C ← MERGE A (C, C v , C w ) τ 4 i D k × D k (A, B) C ← MERGE A (C, C v , C w ) τ 7 j D k × D k (B, A) C ← MERGE A (C, C v , C w ) τ 7 k D k × D k (A, A) C ← MERGE A (C, C v , C w ) τ 7 l D k × D k (B, B) C ← MERGE A (C, C v , C w ) τ 7 m V \k × V \k (∅, B) C ← MERGE A (C, C v , C w ) τ 8 n V \k × V \k (B, ∅) C ← MERGE A (C, C v , C w ) τ 8 o V \k × V \k (A, B) C ← MERGE A (C, C v , C w ) τ 8 p V \k × V \k (B, A) C ← MERGE A (C, C v , C w ) τ 8 q V \k × V \k (A, A) C ← MERGE A (C, C v , C w ) τ 8 r V \k × V \k (B, B) C ← MERGE A (C, C v , C w ) τ 8
In what follows, we define suitable quantities. Notice that these quantities are dynamic, in that they change from round to round. First, let ω(v) be a shorthand for ω(C v ). Let X := {v ∈ V \k : ω(v) = ∅}. Let τ 1 be the set of rounds on which an item v enters X . Note that once an item has entered X it cannot leave, and hence |τ 1 | ≤ |V \k |. Let τ 2 be the set of mistaken rounds of cases a and b, and τ 3 be the set of mistaken rounds of cases e and f . Observe that τ 2 ∩ τ 3 = ∅ and that both τ 2 and τ 3 are subsets of τ 1 . Hence

|τ 2 | + |τ 3 | ≤ |τ 1 | ≤ |V \k | . Let δ = {C ∈ C : C ⊆ V \k } and Y = {C ∈ δ : ω(C) = B}.
Note that the cardinality of δ \ Y never increases over time, and is initially |V \k |, so it can only decrease |V \k | times. Let τ 6 be the set of mistaken rounds of cases c and d. Since, for every round in τ 6 we have that the cardinality of δ \ Y decreases, we must have

|τ 6 | ≤ |V \k |. Next, let = {C ∈ C : C ⊆ D k }, and W = {C ∈ : ω(C) = B}.
Observe that W only increases on rounds in τ 3 . Let τ 4 be the set of mistaken rounds with mistakes of cases g and h. Note that for a round in τ 4 the cardinality of W decreases by one. Coupled with the fact that W only increases on rounds in τ 3 , and only by one each time, we have that

|τ 4 | ≤ |τ 3 | . Let U = {C ∈ : ω(C) = ∅}.
Notice first that U is initially empty, and increases in cardinality on mistaken rounds in τ 2 (cases a and b) or τ 6 (cases c and d), where it only increases by one each time. Let τ 7 be the set of mistaken rounds of cases i to l, and observe that in such rounds U decreases in cardinality, hence directly from above we have

|τ 7 | ≤ |τ 2 | + |τ 6 | .
Finally, let τ 8 be the set of mistaken rounds of cases m to r. Note that, for every round in τ 8 , we have that |δ| deceases, so that since |δ| never increases, and is initially equal to |V \k |, we conclude that

|τ 8 | ≤ |V \k | .
Now, because every mistaken round is either in τ 2 , τ 3 , τ 6 , τ 4 , τ 7 or τ 8 , from the above displayed inequalities we have that the total number of mistakes

|τ 2 | + |τ 3 | + |τ 6 | + |τ 4 | + |τ 7 | + |τ 8 |
made by Oppa is bounded from above as follow:

|τ 2 | + |τ 3 | + |τ 6 | + |τ 4 | + |τ 7 | + |τ 8 | ≤ |V \k | + |τ 6 | + |τ 4 | + |τ 7 | + |τ 8 | ≤ 2|V \k | + |τ 4 | + |τ 7 | + |τ 8 | ≤ 2|V \k | + |τ 3 | + |τ 7 | + |τ 8 | ≤ 2|V \k | + |τ 3 | + |τ 2 | + |τ 6 | + |τ 8 | ≤ 3|V \k | + |τ 6 | + |τ 8 | ≤ 4|V \k | + |τ 8 | ≤ 5|V \k | ,
thereby concluding the proof.

A.2. Proof of Theorem 2

Proof We describe an adversarial strategy forcing any algorithm to achieve the lower bound of Theorem 2. This strategy is described in Algorithm 5. Notice that the strategy only focuses on the first n -1 rounds of a potentially longer training sequence S. In fact, any learning algorithm is forced by this strategy to make at least n -k -

d k mistakes over the first n -1 examples (v 1 , w 1 ), y v 1 ,w 1 , . . . , (v n-1 , w n-1 ), y v n-1 ,w n-1 of S.
These examples are such that v t ≡ w t-1 and v t ≡ v t-1 for all t > 1. In other words, the sequence of pairs (v t , w t ) corresponding to the first n -1 examples of S is a line graph spanning the whole vertex set V . The first vertex v 1 is assigned to a cluster D i selected arbitrarily. At each round t, a new vertex w t is assigned to a cluster selected according to the learner's prediction. This Algorithm 5 Adversarial strategy for the online similarity prediction problem. Input: Vertex set V = {1, . . . , n}; sequence of cluster sizes d 1 , d 2 , . . . , d k . Initialization:

• For each j = 1, . . . , k: Set d j ← d j and D j ← ∅; • Select arbitrarily i ∈ [k]; D i ← {v 1 }; V ← {v 1 }; d i ← d i -1; For t = 1, . . . , n -1: 1. Select arbitrarily w t ∈ V \ V ; V ← V ∪ {w t }; 2. Ask for label y t ; 3. If (ŷ t = 1 ∨ d i = 0) ∧ (∃j = i : d j = 0), then
Set i to an arbitrarily selected cluster index j = i such that d j = 0;

4. D i ← D i ∪ {w t }; d i ← d i -1;
selection is accomplished in order to force a mistake whenever possible. The number of items that can be assigned to each cluster D j for all j ∈ [k], is initially equal to d j , and decreases over time. At any time t, for all j ∈ [k], let d j be the difference between d j and the number of items assigned to D j in the first t -1 rounds. In other words, for each j ∈ [k], d j is the number of items that can be assigned to D j during the remaining rounds t, t + 1, . . . , n -1.

The core of the adversarial strategy is simple. Given any round t ∈ [n -1], let D t be the set of all clusters D j such that, at time t, d j = 0 and j = µ D (v t ). We then have the following cases:

• If the learner predicts 1 (similar) and D t ≡ ∅, then item w t is assigned to a cluster D j selected arbitrarily in D t . This assignment thus forces one mistake.

• If the learner predicts 0 (dissimilar) and D t ≡ ∅, then we have two sub-cases:

-If d µ D (vt) = 0, then item w t is assigned to cluster D µ D (vt) , hence forcing one mistake.

-If d µ D (vt) = 0, then w t cannot be assigned to D µ D (vt) , because d µ D (vt) items have already been assigned to this cluster. In this case, w t is added to a cluster D j selected arbitrarily in D t , such as when the learner predicts 1 and D t ≡ ∅. However, since now the learner predicts 0, no mistake can be forced.

• Finally, if D t ≡ ∅, according to the definition of D t , the only cluster D j such that d j = 0 is D µ D (vt) . Hence w t must be assigned to D µ D (vt) . Note that, in this case, no mistake can be forced if the learner predicts 1.

In order to quantify the effectiveness of this strategy, observe that, at each round t ∈ [n -1] we have in the pseudocode of Algorithm 5 that i = µ D (v t ). Line 3 and 4 of the pseudocode ensure that one mistake is forced at any round such that both the following conditions are satisfied: (a) d i = 0, and (b) ∃j = i : d j = 0. In fact, if both these conditions hold, then we have either (i) µ D (v t ) = µ D (w t ) if ŷt = 0, which implies y t = 1, or (ii) µ D (v t ) = µ D (w t ) if ŷt = 1, which implies y t = 0.

The number of rounds t ∈ [n -1] such that condition (a) is violated cannot be larger than k -1. In fact, since t ≤ n -1, we must always have at least one cluster index j such that d j = 0. On the other hand, the number of rounds t ∈ [n -1] such that condition (b) is violated cannot be larger than max j d j = d k . Hence, the number of mistakes so forced is lower bounded by the difference between n -1 and k -1 + d k , i.e., n -k -d k , as claimed.

A.3. Proof of Theorem 4

The following two lemmas are an immediate consequence of the triangle inequality for dist.

Lemma 8 Let a, b ∈ [0, 1] be such that a + b ≥ 3/2, and sets U, W, X, Y, Z satisfy

1. dist(U, W ) ≤ 1 -a; 2. dist(W, X) ≤ 1 -b; 3. dist(U, Y ) ≤ 1 -a; 4. dist(Z, X) = 1. Then dist(Y, Z) ≥ 1 -b. Proof We can write 1 = dist(Z, X) ≤ dist(Z, Y ) + dist(Y, U ) + dist(U, W ) + dist(W, X) ≤ dist(Z, Y ) + 1 -a + 1 -a + 1 -b , so that dist(Z, Y ) ≥ 2a + b -2 ≥ 1 -b,
the last inequality using the assumption a + b ≥ 3/2. This concludes the proof.

Lemma 9 Let a, b ∈ [0, 1] be such that 2b ≥ 1 + a, and sets X, Y, Z satisfy Putting the two cases together gives us

1. dist(X, Y ) ≤ 1 -b: 2. dist(Y, Z) ≥ 1 -a . Then dist(X, Z) ≥ 1 -b. Proof We can write 1 -a ≤ dist(Y, Z) ≤ dist(Y, X) + dist(X, Z) ≤ 1 -b + dist(X, Z), so that dist(X, Z) ≥ b -a ≥ 1 -b, (A ψ(i)+1 ∩ D γ(ψ(i)) ) \ Λ b .
|D i \ C ψ(i) | ≤ |D i ∩ Λ b | + |C ψ(i) ∩ Λ b |, as required.
Having established the main building blocks of the behavior of rgca, we now turn to quantifying the resulting connection between ER and HA. To this effect, we start off by defining a natural map Υ associated with the clustering {C 1 , . . . , C } generated by rgca, along with a corresponding accuracy measure.

Definition 20 The map Υ : {D 1 , . . . , D k } → {C 1 , . . . , C } is defined as follows:

Υ(D i ) = C ψ(i) if i ∈ ∆ b ∅ if i / ∈ ∆ b Moreover, let M(Υ) := k i=1 |D i \ Υ(D i )|.
We have the following lemma.

Lemma 21 M(Υ) ≤ 2|Λ b |. Proof For i / ∈ ∆ b we have D i ⊆ Λ b and Υ(D i ) = ∅ so that |D i \ Υ(D i )| = |D i | = |D i ∩ Λ b | = |D i ∩ Λ b | + |∅| = |D i ∩ Λ b | + |Υ(D i ) ∩ Λ b |.
On the other hand, for i ∈ ∆ b we have Υ(D i ) = C ψ(i) so that, by Lemma 19, we can write

|D i \ Υ(D i )| ≤ |D i ∩ Λ b | + |Υ(D i ) ∩ Λ b | .
Hence, in both cases, for all i ∈ {1, . . . , k} we have

|D i \ Υ(D i )| ≤ |D i ∩ Λ b | + |Υ(D i ) ∩ Λ b | , implying M(Υ) ≤ k i=1 |D i ∩ Λ b | + |Υ(D i ) ∩ Λ b | . (9)
Now, both {D 1 , . . . , D k } and {Υ(D 1 ), . . . , Υ(D k )} are a partition of V , implying

|Λ b | = k i=1 |D i ∩ Λ b | = k i=1 |Υ(D i ) ∩ Λ b | .
Plugging back into (9) yields the claimed result.

Next, observe that, by its very definition, HA(P, D) can be rewritten as

HA(P, D) = v∈V |(D µ D (v) \ Γ(v)) ∪ (Γ(v) \ D µ D (v) )| . ( 10
) Lemma 22 We have HA(P, D) ≥ (1 -b) k i=1 d i |D i ∩ Λ b | . Proof Fix class i ∈ {1, . . . , k} and vertex v ∈ D i ∩ Λ b . Then v ∈ Λ b implies dist(D µ D (v) , Γ(v)) ≥ 1 -b, which in turn yields |(D µ D (v) \ Γ(v)) ∪ (Γ(v) \ D µ D (v) )| ≥ (1 -b)d i ,
thereby concluding that for all fixed i

v∈D i ∩Λ b |(D µ D (v) \ Γ(v)) ∪ (Γ(v) \ D µ D (v) )| ≥ (1 -b) |D i ∩ Λ b | d i . Since Λ b = k i=1 (D i ∩ Λ b ), being the sets D i ∩ Λ b , i = 1, . . . , k, pairwise disjoint, we can write v∈Λ b |(D µ D (v) \ Γ(v)) ∪ (Γ(v) \ D µ D (v) )| = k i=1 v∈D i ∩Λ b |(D µ D (v) \ Γ(v)) ∪ (Γ(v) \ D µ D (v) )| ≥ (1 -b) k i=1 |D i ∩ Λ b | d i .
Thus, from (10), and the fact that Λ b ⊆ V the result immediately follows.

Lemma 23 The number |Λ b | of b-anomalies can be upper bounded as

|Λ b | ≤ min j=1,...,k 1 d j (1 -b) HA(P, D) + j-1 i=1 d i .
Proof For any j = 1, . . . , k we can write

|Λ b | = k i=1 |D i ∩ Λ b | = j-1 i=1 |D i ∩ Λ b | + k i=j |D i ∩ Λ b | ≤ j-1 i=1 d i + k i=j |D i ∩ Λ b |
so all that is left to prove is that the last sum in the right-hand side is at most

1 d j (1-b) HA(P, D).
Since, for all classes i such that i ≥ j, we have d i ≥ d j , we can write

k i=j |D i ∩ Λ b | ≤ k i=j d i d j |D i ∩ Λ b | ≤ 1 d j k i=1 d i |D i ∩ Λ b | ≤ 1 d j (1 -b) HA(P, D) ,
where the last inequality derives from Lemma 22. This concludes the proof.

We are now ready to combine to above lemmas into the proof of Theorem 4. Proof (Theorem 4) Direct from Lemmas 21 and 23 we have

M(Υ) ≤ min j=1,...,k 2 d j (1 -b) HA(P, D) + j-1 i=1 d i .
We then optimize for b by selecting b = 1+a 2 , and then for a by setting a = 2/3, so as to fulfil conditions (7). The result follows by the fact that ER(C, D) ≤ M(Υ), for ER(C, D) is a minimum over all possible cluster maps D → C, while Υ is just the one in Definition 20.

|D j o \ f (D j o )| ≥ c. This allows us to conclude that ER(C, D) = k j=1 |D j \ f (D j )| ≥ c + 1 2 j o -1 j=1 d j = ω/2d j o + 1 2 j o -1 j=1 d j ≥ ω 2d j o -1 + 1 2 j o -1 j=1 d j = σ 2d j o -1 - 1 4d o j j o -1 j=1 d 2 j + 1 2 j o -1 j=1 d j = σ 2d j o -1 + 1 2 j o -1 j=1 d j 1 - d j 2d j o ≥ σ 2d j o -1 + 1 4 j o -1 j=1 d j .
Finally, notice that the only incorrect similarity/dissimilarity predictions of P with respect to D are those between P + j and P - j , for every j < j o , and those between X and Y , which gives us 2|P + j | • |P - j | = d 2 j /2 incorrect predictions for every j < j o , and an additional 2|X| • |Y | = 2c(d j o -c) ≤ 2cd j o ≤ ω incorrect predictions between X and Y . This implies that

HA(P, D) ≤ ω + j o -1 j=1 d 2 j /8
which is in turn bounded from above by σ. This completes the proof for the second case.

A.5. Proof of Theorem 6

The following simple lemma is of preliminary importance.

Lemma 24 Let H = (V, E) be an Erdos-Renyi G(n, p) graph. For each subgraph H (V , E ) ⊆ H with n = |V | nodes, when p = λ log n n the following separation property holds: As n approaches infinity, the expected number z of isolated vertices in G equals (n ) 1-λ . Furthermore, in the special case when n = 1 p , we always have z ≥ 1 pe .

Proof In order to prove this property, it suffices to observe that, given any node in V , the probability that it is isolated in G is equal to (1 -p) n -1 , which in turn is equal to e -λ log n = (n ) -λ as n approaches infinity. Hence we have z = (n ) 1-λ . By a similar argument, it is immediate to verify that in the case when n = 1 p we have z =

1 p (1 -p) 1 p -1
which is never smaller than 1 ep .

Proof (Theorem 6) Let G = (V, E ) denote the undirected graph whose edge set E is made up of all pairs of vertices drawn in S. Since S is drawn uniformly at random, G turns out to be an Erdos-Renyi graph G(n, p), with p = m/n 2 . Setting λ = 2 in Lemma 24, we have that for all clusters C ∈ C such that 2 log |C| |C| ≤ p, cluster C can be completely detected by Algorithm 1 (line 3 therein) with probability at least 1 |C| . Hence, the expected number of misclassification errors made when detecting such clusters is upper bounded by 1 per cluster. In order to satisfy the assumption 2 log |C| |C| ≤ p, the size of these clusters must be equal to a value τ = Ω (ρ log ρ), where we set ρ = 1 p . Finally, we can conclude the proof observing that the total number of misclassification errors is bounded in expectation by the sum of the following two quantities: (i) the number of clusters larger than τ , which in turn is bounded by k, and (ii) the total number of nodes belonging to the clusters smaller or equal to τ , which in turn is bounded by kτ :

E [ER(C, D)] = O (k(1 + τ )) = O (kρ log ρ) , (11)
thereby concluding the proof.

A.6. Proof of Theorem 7

Proof As in the proof of Theorem 6, we denote by G = (V, E ) the undirected graph whose edge set E is made up of all pairs of vertices drawn in the training set S. Since S is drawn uniformly at random, G turns out to be an Erdos-Renyi graph.

The basic idea of this proof is to construct a collection H of z disjoint subsets of V , call them H 1 , H 2 . . . , H z , and, for all j ∈ {1, . . . , z}, to randomly label all nodes of each subset H j using only a pair of classes of {1, . . . , k}. These z pairs of classes must be distinct and disjoint. The random labeling is accomplished in such a way that no algorithm can exploit the training set to guess how each H j is labeled. More specifically, H is created so as to satisfy the following two properties:

Property (i) For all j = 1, . . . , z, no pair of nodes in H j are connected by an edge in the training graph representation G , i.e. for each pair of nodes u, v ∈ H j , we have (u, v) ∈ S.

Property (ii) For all j = 1, . . . , z, we have that the expected size of H j (over the random draw of the training set S) is larger than n 2 2m e , if m > n 2 , where e is the base of natural logarithms, while it is Θ(n) if m ≤ n 2 . Figure 1 provides a pictorial explanation of the randomized labeling strategy we are going to describe.

We now describe in detail the randomized labeling strategy (a randomized clustering D representing a clustering with k clusters), and derive a lower bound for E S,D [ER(C, D)] when H satisfies both the above properties.

Let z ≤ k-1 2 . Once we constructed such a collection H of clusters, we associate a distinct pair of classes in {1, . . . , k} with each H j in such a way that all these class pairs are distinct and disjoint. This allows us to always leave one class out (say, class k) for labeling The grey area includes all the nodes of V . In this example, we set z = 3 and k = 7.

In this case we thus have k-1 2 = 3. G is the collection of the 3 vertex-disjoint subgraphs G 1 , G 2 and G 3 . The node set size of each of these subgraphs is equal to

n 2
2m . The subsets of isolated vertices in these 3 subgraphs are H 1 , H 2 , and H 3 , which are depicted in this figure by the bicoloured circles. Each color represents a class. For each j, the expected size of H j must be linear in the size of the node set of G j . For j = 1, 2, 3, set H j is labeled by selecting uniformly at random a class between the two classes (or colors) 2j -1 and 2j. All the remaining nodes in the grey area of this picture are given the same class 7. Hence, for each pair of nodes u and v both belonging to H j for some j, we must have (u, v) ∈ S. On the contrary, for each pair u and v with u ∈ H j , for some j, and v ∈ H j , we must have y u,v = 0. The information of the training set cannot be used to predict how the nodes in H 1 , H 2 , and H 3 , are labeled. In fact, any algorithm will make 1 2 mistakes in expectation over the randomized labeling on each node contained in these subsets. all remaining vertices in V . In particular, we associate with H j the class pair (2j -1, 2j), and then adopt the following randomized strategy:

For all j = 1, . . . , z, set H j is split uniformly at random into two subsets H j and H j , and we label H j by class 2j -1 and H i by class 2j. All remaining nodes in V \ ∪ z j=1 H j are labeled with class k.

This randomized labeling strategy ensures that, in order to guess the true clustering D, no learning algorithm can exploit the information provided by S, since for all node pairs (v, w) with v ∈ H j , for some j ∈ {1, . . . , z}, one of two cases hold:

Case (a): w ∈ H j , which implies that (v, w) ∈ S, because of Property (i). We have therefore no training set information related to the similarity of nodes laying in the same set H j .

  c 2018 S. Pasteris, F. Vitale, C. Gentile & M. Herbster.

  over all bijections from D to C. In words, ER(C, D) measures the smallest number of classification mistakes over all class assignments of clusters in D w.r.t. clusters in C. This is basically an unnormalized version of the classification error (distance) considered,

  ); Tsuda et al. (2005); Warmuth (2007); Cavallanti et al. (2010); Kakade et al. (2012); Hazan et al. (2012); Gentile et al.

Theorem 2

 2 Let D = {D 1 , . . . , D k } be any clustering of V = {1, . . . , n}, with d i = |D i |, i = 1, . . . , k, and d 1 ≤ d 2 ≤ . . . d k . Then, for any online similarity prediction algorithm A, a sequence of examples S exists which is labeled according to D, and such that the number of mistakes made by A on S is at least n -k -d k .

Theorem 4

 4 Let C = {C 1 , . . . , C k } be the clustering produced in output by rgca when receiving as input similarity graph (V, P), and distance parameter a = 2/3. Then for any clustering D = {D 1 , . . . , D k }, with d i = |D i |, i = 1, . . . , k, and d 1 ≤ d 2 ≤ . . . d k we have ER(C, D) ≤ min

Figure 1 :

 1 Figure 1: Illustration of the randomized labeling that achieves the lower bound in Theorem 7.The grey area includes all the nodes of V . In this example, we set z = 3 and k = 7.In this case we thus have k-1

  k, and d 1 ≤ d 2 ≤ . . . d k . Then for any sequence of examples S labeled according to D, the number of mistakes made by Oppa on S is upper bounded by 5(n -d k ) .

	It is useful to contrast the upper bound for Oppa in Theorem 1 to the bound for Matrix
	Winnow in (1). Since k i=1 d 2 i ≤

k i=1 d i (max i=1...k d i ) = nd k , one can readily see that (

  similar" 3. Else define ζ as the pair of tags (ω(C vt ), ω(C wt )); then predict as in the table (second column) and, upon observing y t , if ŷt = y t update as in the table (third column):

	Value of ζ	Prediction	On mistake execute:

  By Lemma 15 the number of such vertices v is hence upper bounded by |C ψ(i) ∩ Λ b |.Case (ii). In this case, we simply have that v ∈ D i ∩ Λ b , so the number of such vertices v is upper bounded by |D i ∩ Λ b |.

For simplicity of presentation, we will assume throughout that, when drawn at random from V , the samples in S are drawn with replacement.

This choice of G seems best in the absence of further information.

All proofs are given in the appendix.

Unlike the folklore algorithm, Oppa is not guaranteed to deliver after training a prediction function which is itself a clustering over V .

Acknowledgments SP and MH have been supported in part by the U.S. Army Research Laboratory and the U.K. Defence Science and Technology Laboratory. This work was accomplished under Agreement Number W911NF-16-3-0001. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, ether expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Defence Science and Technology Laboratory or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. FV was supported by the ERC Starting Grant DMAP 680153. CG was partially supported by a Criteo Faculty Research Award.

the last inequality deriving from 2b ≥ 1 + a. This concludes the proof.

With these two simple lemmas handy, we are now ready to analyze rgca. The reader is compelled to refer to Algorithm 4 for notation. In what follows, a ∈ [0, 1] is rgca's distance parameter, and b ∈ [0, 1] is a constant such that the two conditions on a and b required by Lemmas 8 and 9 simultaneously hold. It is easy to see that these conditions are equivalent to 5 a ≥

The following definition will be useful.

Definition 10 A b-anomaly in the similarity graph (V, P) is a vertex v ∈ V for which dist(D µ D (v) , Γ(v)) ≥ 1 -b, for some constant b ∈ [0, 1] satisfying (7). We denote by Λ b the set of all anomalies. A centered round of rgca is any t ≤ in which N t (α t ) ⊆ Λ b . We denote by Ω b the set of all centered rounds. A centered label is any class i ∈ {1, . . . , k} such that D i ⊆ Λ b . We denote by ∆ b the set of all centered labels.

Lemma 11 For any round t ≤ , there exists a class j ∈ {1, . . . , k} such that for every

Proof Suppose, for the sake of contradiction, that we have v, w

We are therefore in a position to apply Lemma 8 verbatim, from which we have dist(Y, Z) ≥ 1 -b, i.e., w ∈ Λ b . This is a contradiction, which implies the claimed result.

Lemma 11 allows us to make the following definition.

Definition 12 Given a centered round t ∈ Ω b , we define γ(t) to be the unique class j such that for every vertex v ∈ N t (α t ) \ Λ b we have µ D (v) = j.

Lemma 13 For any round t ≤ and vertices v, w

Lemma 14 For any centered round t ∈ Ω b , any vertex v ∈ N t (α t ) \ Λ b , and any vertex w ∈ N t (α t ) \ N t (v), we have w ∈ Λ b .

5. For instance, we may set a = 2/3 and b = 5/6.

Proof If µ D (w) = µ D (v) then by Lemma 11 we must have w ∈ Λ b , so we are done. On the other hand, if

∈ Λ b , so let us consider such a v. Note that by the way the algorithm works, we have

Now suppose we have some vertex w

For the sake of contradiction, let us assume that w / ∈ N t (v). Then w ∈ A t+1 implies w ∈ A t which, combined with Lemma 13 together with the fact that µ D (v) = γ(t) = µ D (w), implies that w ∈ Λ b , which is a contradiction. Hence we must have w ∈ N t (v). Moreover, since w ∈ A t+1 we must have w / ∈ N t (α t ). We have hence shown that w

Combining with (8) concludes the proof.

We now turn to considering centered labels.

Lemma 16 For any centered label i ∈ ∆ b there exists some round t ≤ such that γ(t) = i.

Lemma 16 allows us to make the following definition.

Definition 17 Given a centered label i ∈ ∆ b , we define ψ(i) := min{t : γ(t) = i}.

Lemma 18 For any centered label i ∈ ∆ b , we have

Proof Suppose, for contradiction, that there exists some v

Then, by definition of A ψ(i) there exists some round

Proof Suppose we have some v ∈ D i \ C ψ(i) , and let us separate the two cases:

Proof For ease of proof, we assume that d j is even for all j (adapting the proof to the general case is trivial). We consider two cases:

For the first case we choose, for every j = 1, . . . , k, sets P + j and P - j such that |P + j | = |P - j | = d j /2 and P + j ∪ P - j = D j . We then construct the similarity graph (V, E P ), where clustering P is made up of the 2k clusters {P + j : j = 1, . . . , k} ∪ {P - j : j = 1, . . . , k}. Since the algorithm is consistent, we must have C = P. Now, let f be an injection from D to C, and consider any j = 1, . . . , k. If f (D j ) ∈ {P + j , P - j } then we have

Since f is arbitrary, this shows that ER(C, D) ≥ n 2 . Moreover, we observe that the only incorrect similarity/dissimilarity predictions of P with respect to D are those between P + j and P - j , for every j, which gives us 2|P + j | • |P - j | = d 2 j /2 incorrect predictions for every j. This implies that HA(P, D) = k j=1 d 2 j /2, which is no greater than σ, thereby completing the proof for the first case.

We now turn to the second case. Let j o ∈ {1, . . . , k} be such that 1 2

and

We choose, for every j < j o , sets P + j and

We construct the similarity graph (V, E P ), where clustering P is made up of the k + j o clusters

Again, since the algorithm is consistent, we must have C = P. As before, let f be an arbitrary injection from D to C, and consider any j

In any case, since c < d j o /2, we have Case (b): w / ∈ H j . In this case, whenever (v, w) ∈ S, we always have y v,w = 0, and this information cannot be exploited to guess the randomized labeling of H j .

In short, no training information can be exploited to guess how each set H j is split into the two subsets H j and H j . This entails that any clustering algorithm will incur an expected number of misclassification errors proportional to

the latter equality deriving from Property (ii).

We now turn to describing the detailed construction of H. We will explain how to select the z subsets satisfying Property (i), and show that their size is bounded from below as required by Property (ii). This will lead to the claimed lower bound.

Definition of z. Let

Satisfaction of Property (i).

Let H be a collection of disjoint subsets of V created as follows. H is generated by selecting uniformly at random z disjoint subsets of V such that each node subset contains n 2 2m nodes. The collection of subsets H = {H 1 , . . . , H z } is constructed as described next. Let G ≡ {G 1 , G 2 , . . . , G z }, where G j is the subgraph of G induced by the nodes in the j-th set of H . We create z-many disjoint subsets H 1 , H 2 , . . . , H z by selecting all vertices that are isolated in each graph of G, and set H ≡ {H 1 , H 2 , . . . , H z }. Property (i) is therefore satisfied.

Satisfaction of property (ii). By definition of H , each graph of the collection G has n 2 2m nodes in expectation. Using the second part of Lemma 24, we conclude that the expected size of each set in H is not smaller than n 2 /2m e .

Hence the collection of sets S so generated fulfils at the same time both Properties (i) and (ii).

In order to conclude the proof, we compute our lower bound based on the definition of z and Property (ii). As anticipated, because of the randomized labeling strategy, the expected number of misclassification errors made by any algorithm is proportional to