Locality-preserving L1-graph and its application in clustering

Shuchu Han, Hao Huang, Hong Qin, Dantong Yu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations


Constructing a good graph to represent data structures is critical for many important machine learning tasks such as clustering and classification. Recently, a nonparameteric graph construction method called L1-graph is proposed with claimed advantages on sparsity, robustness to data noise and datum-adaptive neighborhood. However, it suffers a lot from the loss of locality and the instability of perfor- mance. In this paper, we propose a Locality-Preserving L1-graph (LOP-L1), which preserves higher local-connections and at the same time maintains sparsity. Besides, compared with L1-graph and the succeeding regularization-based tech- niques, our LOP-L1 requires less amount of running time in the scalability test. We evaluate the effectiveness of LOP-L1 by applying it to clustering application, which confirms that the proposed algorithm outperforms related methods.

Original languageEnglish (US)
Title of host publication2015 Symposium on Applied Computing, SAC 2015
EditorsDongwan Shin
PublisherAssociation for Computing Machinery
Number of pages6
ISBN (Electronic)9781450331968
StatePublished - Apr 13 2015
Externally publishedYes
Event30th Annual ACM Symposium on Applied Computing, SAC 2015 - Salamanca, Spain
Duration: Apr 13 2015Apr 17 2015

Publication series

NameProceedings of the ACM Symposium on Applied Computing


Other30th Annual ACM Symposium on Applied Computing, SAC 2015

All Science Journal Classification (ASJC) codes

  • Software


  • L-graph
  • Locality
  • Sparsity


Dive into the research topics of 'Locality-preserving L1-graph and its application in clustering'. Together they form a unique fingerprint.

Cite this