← Back to all news
arXiv Machine Learning

Advancing Local Clustering on Graphs via Compressive Sensing: Semi-supervised and Unsupervised Methods

arXiv:2504. 19419v3 Announce Type: replace Abstract: Local clustering aims to identify specific substructures within a large graph without any additional structural information of the graph.

Related stories

arXiv Machine Learning
5d ago

Robust Graph Clustering Network for Multiple Missing Data

The paper introduces the Robust Graph Clustering Network for Multiple Missing Data (RGCN), a method designed to cluster graphs with simultaneous missing node attributes and structural links. RGCN employs a view‑decoupled dual‑branch imputation to reduce cross‑view interference, a multi‑hyperspherical mixture prior to improve cluster compactness and separability on a directional latent manifold, and a boundary‑aware contrastive enhancement objective to counteract cluster blurring caused by imputation bias. Experiments on real‑world datasets show that RGCN consistently outperforms state‑of‑the‑art baselines across various missing data patterns.

By Keyuan Qiu, Renda Han, Zhen Tang, Qiang He, Xingwei Wang, Wenxin Zhang, Guangzhen Yao, Junxin Chen, Qingjian Ni
benchmarkssafety
More like this →
arXiv Machine Learning
Jul 13

Scalable Varied-Density Clustering via Graph Propagation

arXiv:2508. 02989v2 Announce Type: replace Abstract: We propose a novel perspective on varied-density clustering for high-dimensional data by framing it as a label propagation process in neighborhood graphs that adapt to local density variations.

By Ninh Pham, Yingtao Zheng, Hugo Phibbs
More like this →
arXiv Machine Learning
Aug 27

Towards Robust and Scalable Density-based Clustering via Graph Propagation

The paper introduces CluProp, a framework that treats varied‑density clustering in high‑dimensional spaces as a label propagation process over neighborhood graphs. By combining density‑based ideas with graph connectivity, it offers a deterministic propagation strategy that reduces parameter sensitivity and scales efficiently to millions of points. CluProp is agnostic to distance metrics and consistently outperforms existing baselines in accuracy while processing large datasets in minutes.

By Yingtao Zheng, Hugo Phibbs, Ninh Pham
More like this →
arXiv Machine Learning
Sep 17

Provable Guarantees for Spectral Structured Prediction

The paper presents provable guarantees for a spectral method that recovers binary node labels on signed graphs with edge‑flip noise. It provides graph‑structure‑agnostic bounds on approximate inference accuracy and maximum angle deviation, using matrix concentration and eigenvector perturbation techniques. The results connect to the Cheeger constant and are validated with synthetic experiments, marking the first theoretical analysis of this spectral approach.

By Violet Zheng, Jean Honorio
computer-visionnlp
More like this →
arXiv Machine Learning
Sep 24

Graph Learning with Spectral Connectivity Priors for Scarce Data

The paper introduces Spectral Connectivity-Regularized Graph Learning (SCoGL), a method for learning sparse graphs from limited data by incorporating Laplacian spectral priors that promote global connectivity. SCoGL extends the graphical lasso objective with a connectivity prior derived from Laplacian eigenvalues and uses projected gradient descent with Armijo backtracking for optimization. Experiments demonstrate that SCoGL improves graph recovery and enhances downstream tasks such as graph signal denoising when observations are scarce.

By Mingxiao Liu (Tsinghua University, China), Bahar Oveisgharan (York University, Canada), Bingyan Zou (Tsinghua University, China), Gene Cheung (York University, Canada), H. Vicky Zhao (Tsinghua University, China), Feifei Gao (Tsinghua University, China)
efficiency
More like this →