AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Scalable Algorithm for Higher-Order Co-Clustering via Random Sampling
Daisuke Hatano, Takuro Fukunaga, Takanori Maehara, Ken-ichi Kawarabayashi

Last modified: 2017-02-13


We propose a scalable and efficient algorithm for coclustering a higher-order tensor. Viewing tensors with hypergraphs, we propose formulating the co-clustering of a tensor as a problem of partitioning the corresponding hypergraph. Our algorithm is based on the random sampling technique, which has been successfully applied to graph cut problems. We extend a random sampling algorithm for the graph multiwaycut problem to hypergraphs, and design a co-clustering algorithm based on it. Each iteration of our algorithm runs in polynomial on the size of hypergraphs, and thus it performs well even for higher-order tensors, which are difficult to deal with for state-of-the-art algorithm.


Co-clustering; Graph partitionning; Karger and Stein's algorithm

Full Text: PDF