Graph Clustering: Block-models and model free results
Clustering graphs under the Stochastic Block Model (SBM) and extensions are well studied. Guarantees of correctness exist under the assumption that the data is sampled from a model. In this paper, we propose a framework, in which we obtain "correctness" guarantees without assuming the data comes from a model. The guarantees we obtain depend instead on the statistics of the data that can be checked. We also show that this framework ties in with the existing model-based framework, and that we can exploit results in model-based recovery, as well as strengthen the results existing in that area of research.
extension, we define the degree matrix D and the Laplacian L associated to any matrix A ∈ R n×n , with A ij = A ji ≥ 0, in a similar way.
Let C be a partitioning (clustering) of the nodes of G into K clusters. We use the shorthand notation i ∈ k for "node i belongs to cluster k". We will represent C by its n × K indicator matrix Z, defined by Z ik = 1 if i ∈ k, 0 otherwise, for i = 1, . . . n, k = 1, . . . K.
Note that Z T Z = diag{n k } with n k counting the number of nodes in cluster k, and Z TÂ Z = [n kl ] K k,l=1 with n kl counting the edges in G between clusters k and l. Moreover, for two indicator matrices Z, Z � for clusterings C, C � , (Z T Z � ) kk � counts the number of points in the intersection of cluster k of C with cluster k � of C � , and (Z TD Z � ) kk � computes � i∈k∩k �di the volume of the same intersection.
"Block models" for random graphs (SBM, DC-SBM, PFM) This family of models contains Stochastic Block Models (SBM) [1,18], Degree-Corrected SBM (DC-SBM) [17] and Preference Frame Models (PFM) [20]. Under each of these model families, a graph G with adjacency matrixÂ over n nodes is generated by sampling its edges independently following the laŵ A ij ∼ Bernoulli(A ij ), for all i > j. The symmetric matrix A = [A ij ] describing the graph is the edge probability matrix. The three model families differ in the constraints they put on an acceptable A. Let C * be a clustering. The entries of A are defined w.r.t C * as follows (and we say that A is compatible with C * ).
SBM : A ij = B kl whenever i ∈ k, j ∈ l, with B = [B kl ] ∈ R K×K symmetric and nonnegative. DC-SBM : A ij = w i w j B kl whenever i ∈ k, j ∈ l, with B as above and w 1 , . . . w n non-negative weights associated with the graph nodes. PFM : A satisfies D = diag(A1), D −1 AZ = ZR where 1 denotes the vector of all ones, Z is the indicator matrix of C * , and R is a stochastic matrix (R1 = 1, R kl ≥ 0), the details are in [20] While perhaps not immediately obvious, the SBM is a subclass of the DC-SBM, and the latter a subclass of the PFM. Another common feature of block-models, that will be significant throughout this work is that for all three, Spectral Clustering algorithms [15] have been proved to work well estimating C * .
The paper presents a generic template for theoretical guarantee for the stability of a clustering C that fits the data well. The stability is measured in terms of the distance between C and any other C' that fit the same data well. The paper also provides specific example of using the template for two block models, PFM and SBM, and all the quantities involved in the guarantees can be computed explicitly from the data. Furthermore, it also uses the stability results thus obtained to show exact recovery guarantees for the models. However, the simulations suggest that either the goodness fit used or the conditions of the theorems provided render the results not too useful.
1) The paper considers the problem of providing generic template for theoretical guarantees for clustering without assuming that the data is from a specific model. The goal is to obtain such guarantees with quantities that can be computed from the data and the output of the clustering algorithms being compared. Providing such model free theoretical guarantees for clustering is of importance for both theoretical and practical purposes.  2) Given that PFM includes DC-SBM as a special class which in turn includes SBM, it is not clear why the two cases (PFM and SBM) are treated differently. Given that Spectral Clutering works well for all the models specified, why not use the same model estimator? In particular, it is not clear why the Laplacian is used for PFM while the adjacency matrix is used for the SBM. Also, the results for PFM is for weighted ME whereas for SBM it is in terms of ME. How do they compare with each other? Further, why are the results for DC-SBM not given?  3) In Proposition 10, what is the definition of < M', M >_F ?  4) In Assumption 5: Is it ||L^{hat}^2 - L^2||_F or ||L^{hat} - L||_F^2 ? If former, what is the intuition behind squaring the Laplacians?  5) The paper has focused mainly on disjoint clusters. Do the techniques/recipe used in this paper extend beyond block models to other models for which Spectral Clustering works? For example, Spectral clustering is known to work well for hierarchical clustering and there are theoretical guarantees available ( "Noise Thresholds for Spectral Clustering", S. Balakrishan et. al. 2011). How would the template work for this case?  6) The evaluation metric considered as well as the estimators considered both in the cases of PFM and SBM are limited to C and C' having the same number of clusters. Different clustering algorithms can potentially give different number of clusters. For example, let the eigenvalues of A might suggest K clusters for C and that of the Laplacian of A might suggest K' =  K + 1 clusters for C' such that all the clusters in C and C' are the same except for one cluster that splits into two.  C' is still "close" to C, but it cannot be captured by the given framework.  7) Related work section does not reflect a lot of model free results that exist: for example:  "Clustering with Spectral Norm and the k-means Algorithm", Kumar and Kannan, 2010. "Clustering under Perturbation Resilience", Balcan et. al. 2012. "Clustering under Approximation Stability", Balcan et. al. 2013. How does the notion of stability considered in this work related to those in these works? In particular, how is the stability in this paper related to the stability measured for perturbation of centers for two clusterings?  8) The perturbations tolerated by simulations for PFM are too small. Line 252-253 casually states "large eigengap makes PFM(G, C) differ from PFM(G, C_0) even for very small perturbations" without really qualifying the statement. It is unclear why it is so. On the other had, the political blog data is smoothed out by raising the power of A which would further exaggerate the gaps in eigenvalues, but in this case it seems to help stability?  Also, if such small perturbations can affect the model fit, then it renders the guarantee not of much use for practical purposes (which is one of the main selling points since the quantities can be actually calculated from the data). Lines 248-250 state that SBM guarantee conditions seem to be very hard to satisfy which is unfortunate.  9) Figure 1 caption mentions "For SBM, \delta is always greater than \delta_0". Which of the subplots is this referring to? If SBM is not plotted, then it should be made clear in the caption.  10) The guarantees in the theorems for PFM are for weighted ME, whereas in the experiment the perturbation is done for ME.     Minor Points: 1) Labels for axes in Figure 1 are missing.  2) (Line 44) For block models, A_{ij} for i > j are independent _given the cluster assignments_ for i and j.  3) B, C and Y have been used with _different_ definitions for PFM and later in 3.2 for SBM. This can be confusing in general. Given that the paper has a lot of notations, it is better to maintain consistency throughout. For example, may be use Y_{\orthogonal} and C_D respectively instead of B and C for PFM. Also, for the estimator of SBM, Y_Z is not required. It is better to use the expression of Y_Z directly in Proposition 8.  Similarly for \lambda in PFM and SBM, using \lamda^L an \lambda^B would clearly distinguish which eigenvalues are being talked about.  4) 4.4 is better suited to be a subsection in related work.