General Tensor Spectral Co-clustering for Higher-Order Data
Spectral clustering and co-clustering are well-known techniques in data analysis, and recent work has extended spectral clustering to square, symmetric tensors and hypermatrices derived from a network. We develop a new tensor spectral co-clustering method that simultaneously clusters the rows, columns, and slices of a nonnegative three-mode tensor and generalizes to tensors with any number of modes. The algorithm is based on a new random walk model which we call the super-spacey random surfer. We show that our method out-performs state-of-the-art co-clustering methods on several synthetic datasets with ground truth clusters and then use the algorithm to analyze several real-world datasets.
This paper propose a new variant of the super-spacey random walk - a variant of higher-order Markov chain model that has been introduced in previous work for co-clustering tensor data. Experimental results show that the algorithm outperforms several previous works on synthetic dataset. The algorithm is then evaluated on several realistic datasets.
I'm not an expert in the problem of clustering but I have read the proofs in some detail including the supplementary material and did not notice significant errors. Overall, I find the paper well-written and understandable. The supplement is well-prepared and contains more details about experimental results which I appreciate. In terms of technical contributions, the problem of undefined transitions in the probability tensor has been tackled already in previous work [4]. Here the authors consider a different way to solve it. However, since the two models share striking similarities, I think the new model should be justified more in terms of both theoretical motivation and analytical results (see below) so that one can clearly see the advantages/drawbacks of the model compared to previous work. As I'm not an expert in this problem, I would consider most of my comments below as suggestions for improving the paper if it is accepted.  1. Please check carefully the notations & variable's indices between lines 44-45 in the supplement as I believe there are some mistakes.  2. Is there any equivalence form of the newly introduced biased conductance like the standard one as shown in Observation 1. At this point, paper [4] has proposed similar conductance functions - "higher-order conductance" and "higher-order expansion". Please comment on this.  3. The biased conductance has been introduced in the paper as a new quality metric for partitioning data. However, it is never used in the experiments to analyze the algorithm, but instead other evaluation metrics (ARI,FMI,F1) were used to compare all algorithms. Some figures showing the values of different higher-order conductance as functions of |S_k| for different methods (at least GTSC,TSC,SC) could be helpful to readers.  4. It seems that the comparison with previous work is done only on synthetic datasets with quantitative results, while it is rather qualitative on other real-world datasets. In this way, I cannot see why one should use the proposed algorithm in favour of other methods for practical clustering. Moreover, on the synthetic dataset, only 5 trials that has been used to estimate the standard deviations for algorithms might be too small so that one cannot say much about standard deviations.