Recent work on eigenvalues of hypermatrices and tensors has generated an algebraic analogue of the stationary distribution vector for a Markov chain. We show that this tensor eigenvector corresponds to the stationary distribution of a new stochastic process called a spacey random walk; it is a hybrid of a higher-order Markov chain and a vertex-reinforced random walk. Our insight provides a solid probabilistic foundation for these tensor eigenvectors, their interpretation, and their application to data problems with higher-order structure.

Austin Benson is a Ph.D. student at Stanford University working with Jure Leskovec. His research focuses on network science, matrix computations, and data mining. He is the recipient of a Stanford Graduate Fellowship and has interned at Google and Sandia National Labs.