A compressed sensing based least squares approach to semi-supervised local cluster extraction

DOI10.1007/S10915-022-02052-XMaRDI QIDQ6158985zbMATH OpenOpenAlexFDO

Authors Ming-Jun Lai, Zhaiming Shen

Publication date 20 June 2023

Published in Journal of Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.02904

zbMATH Keywords

graph clusteringleast squarescompressed sensinggraph Laplaciansemi-supervised clusteringlocal clustering

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: A least squares semi-supervised local clustering algorithm based on the idea of compressed sensing is proposed to extract clusters from a graph with known adjacency matrix. The algorithm is based on a two-stage approach similar to the one in cite{LaiMckenzie2020}. However, under a weaker assumption and with less computational complexity than the one in cite{LaiMckenzie2020}, the algorithm is shown to be able to find a desired cluster with high probability. The ``one cluster at a time" feature of our method distinguishes it from other global clustering methods. Several numerical experiments are conducted on the synthetic data such as stochastic block model and real data such as MNIST, political blogs network, AT&T and YaleB human faces data sets to demonstrate the effectiveness and efficiency of our algorithm.

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 845714 (Why is no real title available?)
• scientific article; zbMATH DE number 7415091 (Why is no real title available?)
• scientific article; zbMATH DE number 6276186 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A proof of the block model threshold conjecture
• An effective region force for some variational models for learning and clustering
• Auction dynamics: a volume constrained MBO scheme
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Community detection and stochastic block models
• Complex graphs and networks
• Compressive sensing for cut improvement and local clustering
• Empirical Analysis of an Evolving Social Network
• Graph-based natural language processing and information retrieval.
• Linear Inversion of Band-Limited Reflection Seismograms
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Using PageRank to Locally Partition a Graph

Cited in

(1)

• K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

This page was built for publication: A compressed sensing based least squares approach to semi-supervised local cluster extraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158985)