# Tensor Spectral Clustering for Partitioning Higher-order Network Structures

arXiv: https://arxiv.org/abs/1502.05058 · HTML: https://mlsanity.com/paper/1502.05058/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2015.

## Built on by (most cited first, 15 of 15)

- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations](https://mlsanity.com/paper/2101.07730/) (2021)
- [Hypergraph Artificial Benchmark for Community Detection (h-ABCD)](https://mlsanity.com/paper/2210.15009/) (2022)
- [Local Algorithms for Finding Densely Connected Clusters](https://mlsanity.com/paper/2106.05245/) (2021)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Scalable Motif Counting for Large-scale Temporal Graphs](https://mlsanity.com/paper/2204.09236/) (2022)
- [Modularity Based Community Detection in Hypergraphs](https://mlsanity.com/paper/2406.17556/) (2024)
- [Clustering with Simplicial Complexes](https://mlsanity.com/paper/2303.07646/) (2023)
- [Higher-order Graph Attention Network for Stock Selection with Joint Analysis](https://mlsanity.com/paper/2306.15526/) (2023)
- [Scalable tensor methods for nonuniform hypergraphs](https://mlsanity.com/paper/2306.17825/) (2023)
- [DynACPD Embedding Algorithm for Prediction Tasks in Dynamic Networks](https://mlsanity.com/paper/2103.07080/) (2021)
- [Bayesian Detection of Mesoscale Structures in Pathway Data on Graphs](https://mlsanity.com/paper/2301.11120/) (2023)
- [An Accelerated Newton-GMRES Method for Multilinear PageRank](https://mlsanity.com/paper/2509.23374/) (2025)
- [Data Understanding Survey: Pursuing Improved Dataset Characterization Via Tensor-based Methods](https://mlsanity.com/paper/2510.14161/) (2025)
- [Provable Guarantees for Spectral Structured Prediction](https://mlsanity.com/paper/2609.18527/) (2026)

## Abstract (arXiv)

Spectral graph theory-based methods represent an important class of tools for studying the structure of networks. Spectral methods are based on a first-order Markov chain derived from a random walk on the graph and thus they cannot take advantage of important higher-order network substructures such as triangles, cycles, and feed-forward loops. Here we propose a Tensor Spectral Clustering (TSC) algorithm that allows for modeling higher-order network structures in a graph partitioning framework. Our TSC algorithm allows the user to specify which higher-order network structures (cycles, feed-forward loops, etc.) should be preserved by the network clustering. Higher-order network structures of interest are represented using a tensor, which we then partition by developing a multilinear spectral method. Our framework can be applied to discovering layered flows in networks as well as graph anomaly detection, which we illustrate on synthetic networks. In directed networks, a higher-order structure of particular interest is the directed 3-cycle, which captures feedback loops in networks. We demonstrate that our TSC algorithm produces large partitions that cut fewer directed 3-cycles than standard spectral clustering algorithms.