Simultaneous Partitioning of a Sequence of Graphs using a Spectral Tensor Method

Lars Eldén
Department of Mathematics
Linköping University
Linköping

Abstract:

Spectral graph partitioning is a method for clustering data organized as undirected graphs, and it has numerous applications in information sciences. The method is based on the computation of eigenvectors of the graph Laplacian. In many areas one wants to cluster data from a sequence of graphs. Such data can be organized as a large sparse tensor. A few attempts have been made to generalize spectral partitioning to the tensor case. Unfortunately there is no natural way to set up the Laplacian of a sparse tensor.

We will present a spectral method for tensor partitioning based on the computation of the best rank-(2,2,2) aproximation of the tensor. A few applications are briefly discussed.