Flow-Based Clustering and Spectral Clustering: A Comparison

Y. Sarcheshmehpour*, Y. Tian, L. Zhang, A. Jung

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)
21 Downloads (Pure)


We propose and study a novel graph clustering method for data with an intrinsic network structure. Similar to spectral clustering, we exploit an intrinsic network structure of data to construct Euclidean feature vectors. These feature vectors can then be fed into basic clustering methods such as k-means or Gaussian mixture model (GMM) based soft clustering. What sets our approach apart from spectral clustering is that we do not use the eigenvectors of a graph Laplacian to construct the feature vectors. Instead, we use the solutions of total variation minimization problems to construct feature vectors that reflect connectivity between data points. Our motivation is that the solutions of total variation minimization are piece-wise constant around a given set of seed nodes. These seed nodes can be obtained from domain knowledge or by simple heuristics that are based on the network structure of data. Our results indicate that our clustering methods can cope with certain graph structures that are challenging for spectral clustering methods.

Original languageEnglish
Title of host publication55th Asilomar Conference on Signals, Systems and Computers, ACSSC 2021
EditorsMichael B. Matthews
Number of pages5
ISBN (Electronic)9781665458283
Publication statusPublished - 2021
MoE publication typeA4 Article in a conference publication
EventAsilomar Conference on Signals, Systems & Computers - Virtual, Pacific Grove, United States
Duration: 31 Oct 20213 Nov 2021
Conference number: 55

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393


ConferenceAsilomar Conference on Signals, Systems & Computers
Abbreviated titleACSSC
Country/TerritoryUnited States
CityPacific Grove


  • clustering
  • community detection
  • complex networks
  • machine learning
  • non-smooth optimization


Dive into the research topics of 'Flow-Based Clustering and Spectral Clustering: A Comparison'. Together they form a unique fingerprint.

Cite this