Mixed-order spectral clustering for complex networks

Yan Ge, Pan Peng, Haiping Lu*

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review


Spectral clustering (SC) is a popular approach for gaining insights from complex networks. Conventional SC focuses on second-order structures (e.g. edges) without direct consideration of higher-order structures (e.g. triangles). This has motivated SC extensions that directly consider higher-order structures. However, both approaches are limited to considering a single order. To address this issue, this paper proposes a novel Mixed-Order Spectral Clustering (MOSC) framework to model both second-order and third-order structures simultaneously. To model mixed-order structures, we propose two new methods based on Graph Laplacian (GL) and Random Walks (RW). MOSC-GL combines edge and triangle adjacency matrices, with theoretical performance guarantee. MOSC-RW combines first-order and second-order random walks for a probabilistic interpretation. Moreover, we design mixed-order cut criteria to enable existing SC methods to preserve mixed-order structures, and develop new mixed-order evaluation metrics for structure-level evaluation. Experiments on community detection and superpixel segmentation show (1) the superior performance of the MOSC methods over existing SC methods, (2) enhanced performance of conventional SC due to mixed-order cut criteria, and (3) new insights of output clusters offered by the mixed-order evaluation metrics.

Original languageEnglish
Article number107964
JournalPattern Recognition
Publication statusPublished - Sep 2021

Bibliographical note

Publisher Copyright:
© 2021 Elsevier Ltd


  • Higher-order structures
  • Mixed-order structures
  • Spectral clustering


Dive into the research topics of 'Mixed-order spectral clustering for complex networks'. Together they form a unique fingerprint.

Cite this