Consistency of Spectral Partitioning of Uniform Hypergraphs under Planted Partition Model
Spectral graph partitioning methods have received significant attention from both practitioners and theorists in computer science. Some notable studies have been carried out regarding the behavior of these methods for infinitely large sample size (von Luxburg et al., 2008;Rohe et al., 2011), which provide sufficient confidence to practitioners about the effectiveness of these methods. On the other hand, recent developments in computer vision have led to a plethora of applications, where the model deals with multi-way affinity relations and can be posed as uniform hypergraphs. In this paper, we view these models as random m-uniform hypergraphs and establish the consistency of spectral algorithm in this general setting. We develop a planted partition model or stochastic blockmodel for such problems using higher order tensors, present a spectral technique suited for the purpose and study its large sample behavior. The analysis reveals that the algorithm is consistent for m-uniform hypergraphs for larger values of m, and also the rate of convergence improves for increasing m. Our result provides the first theoretical evidence that establishes the importance of m-way affinities.
In this paper the authors present theoretical guarantees for the accuracy of a spectral partitioning algorithm on uniform hypergraphs as well as experiments which support their claims. The proofs substantially build on prior work [5] regarding estimating misclustering.This is an interesting paper and quite clearly written. The spectral clustering method presented and the theoretical guarantees appear novel. However, there are some questions in the minds of this reviewer which prevents declearing it a very good paper. Hopefully a revision that answers these issues and improves the presentation will follow.1. Spectral partitioning for regular graphs that use eigenvectors of a Laplacian matrix formed from the adjacency matrix is well established. Applying a spectral technique for (uniform) hypergraphs got less attention, but there is prior art as also cited in the paper (especially [8]); these seem to all come from image processing backgrounds. There exists prior work from other areas that similarly forms a Laplacian (like) matrix derived from the hypergraph and uses eigenvectors of this matrix to perform partitioning or clustering. (Two examples from different fields: Multilevel Spectral Hypergraph Partitioning with Arbitrary Vertex Sizes J. Y. Zien, M. D. F. Schlag, and P. K. Chan in IEEE trans. on computer aided design of integrated circuits and systems vol 8, no 9 or Laplacian eigenvalues and partition problems in hypergraphs J. A. Rodriguez in Applied Mathematics Letters, volume 22, issue 6). One wonders how the proposed/discussed method differs from those other approaches.The authors could properly place their work in the context of spectral techniques for hypergraphs in general and not just geometric groupings. It seems to this reviewer that the use of the flattened adjacency tensor is fairly new and therefore improvements to it and theoretical results might be novel. The authors could make it more clear what is novel and what is reproduced from [8] regarding the algorithm in their discussion.2. The algorithm described in [2] slightly differs from algorithm 1 in that a normalization step is missing prior to the k-means clustering of the rows of X_n.This reviewer asks the authors to discuss (in the paper and outside) what is the source of the difference between Algorithm 1 and that of [2]. Do normalization take place in the implementation? 3. In [5] on page 15 it is noted that the eigenvectors belonging to the largest absolute eigenvalues of L are (and should be) used in their framework. Since the proofs rely on [5], this reviewer asks the authors to discuss the form of the Lagrangian used and the subsequent eigenvector selection and how the misclustering estimates are affected. (See theorem 3.1 of [5] as well.)4. Also in [5] on page 18 it is noted that their theorem 3.1 "depends on the true optimum of the k-means function", or more precisely a certain inequality holding. The authors of [5] repeated the k-means step with various random initializations as part of their simulations until the inequality did hold. This aspect should be addressed by the authors regarding their theoretical guarantees and experiments.Some additional comments:While the paper presents a spectral clustering algorithm it could be still beneficial to mention other state of the art hypergraph clustering approaches, for example Metis.Throughout in the paper the nottaion is using n as subscript to remind the problem size. This only seems to make the nottaions slightly more complicated and this reviewer feels that the n subscript could be safely dropped. The notation can even be confusing, for example C_n is a kxk matrix and it is not denoting an nth iterate.Line 104: "expected quantities of entries of A" - this does not sound right, this reviewer cannot parse "quantities of entries"Throughout the paper there are mismatched articles like: "an hyperedge", "a m-uniform" etc.Line 192: It seems that C_n is positive semidefinite and that could be mentioned.Line 200: Some intuition could be given as to the various conditions.Line 206: The statement |M| = O(T) almost surely may be confusing a bit at first for some readers. (It was for this reviewer.) This is interpreted as there exist a k such that |M| <= kT with probability 1. Is that correct?Line 382: should be: "number of problems" AFTER AUTHOR FEEDBACK:I mentioned above the issue of the selection of the k eigenvectors of the Laplacian. I understand and thank the author's response regarding the Laplacian formulation. I am still a bit confused what formulation is used.To elaborate: In [5] (on which this paper and the results build) the authors emphasize that the eigenvalues need to be ordered by absolute values. Now the standard definition of the Laplacian implies that it is positive semidefinite and so taking the abolute values appears unnecessary. However the authors of [5] are adamant; a quote from [5]:"The above theorem suggests that before finding the largesteigenvalues, you should first order them by absolute value. This allows forlarge and negative eigenvalues. In fact, eigenvectors of L corresponding toeigenvalues close to negative one (all eigenvalues of L are in [−1, 1]) discover“heterophilic” structure in the network that can be useful for clustering."(see page 16 in the discussion of theorem 3.1)I repeat: this is mostly concerning since the submitted paper builds on and cites [5] heavily so this reviewer is puzzled: Did the authors of [5] make a mistake regarding the absolute value? Or did they use a different Laplacian than the submitted paper?I do not generally hold the authors of the submitted paper responsible for the correctness of a cited work, but to the extent that no errors are propagated.