Neighborhood Regularized $\ell_1$-Graph

Yingzhen Yang, Jiashi Feng, Jiahui Yu, Jianchao Yang, Pushmeet Kohli, Thomas S. Huang
Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, PMLR R15:581-590, 2017.

Abstract

$\ell_1$-Graph, which learns a sparse graph over the data by sparse representation, has been demonstrated to be effective in clustering especially for high dimensional data. Although it achieves compelling performance, the sparse graph generated by $\ell_1$-Graph ignores the geometric information of the data by sparse representation for each datum separately. To obtain a sparse graph that is aligned to the underlying manifold structure of the data, we propose the novel Neighborhood Regularized $\ell_1$-Graph (NR$\ell_1$-Graph). NR$\ell_1$-Graph learns sparse graph with locally consistent neighborhood by encouraging nearby data to have similar neighbors in the constructed sparse graph. We present the optimization algorithm of NR$\ell_1-Graph with theoretical guarantee on the convergence and the gap between the sub-optimal solution and the globally optimal solution in each step of the coordinate descent, which is essential for the overall optimization of NR$\ell_1$-Graph. Its provable accelerated version, NR$\ell_1$-Graph by Random Projection (NR$\ell_1$-Graph-RP) that employs randomized data matrix decomposition, is also presented to improve the efficiency of the optimization of NR$\ell_1$-Graph. Experimental results on various real data sets demonstrate the effectiveness of both NR$\ell_1$-Graph and NR$\ell_1$-Graph-RP. This work is supported in part by US Army Research Office grant W911NF-15-1-0317. The work of Jiashi Feng was supported by NUS startup R-263-000-C08-133, MOE R-263-000-C21-112 and IDS R-263-000-C67-646. Pushmeet Kohli was at Microsoft Research during this project.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR15-yang17b, title = {Neighborhood Regularized $\ell_1$-Graph}, author = {Yang, Yingzhen and Feng, Jiashi and Yu, Jiahui and Yang, Jianchao and Kohli, Pushmeet and Huang, Thomas S.}, booktitle = {Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence}, pages = {581--590}, year = {2017}, editor = {Elidan, Gal and Kersting, Kristian}, volume = {R15}, series = {Proceedings of Machine Learning Research}, month = {11--15 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r15/main/assets/yang17b/yang17b.pdf}, url = {https://proceedings.mlr.press/r15/yang17b.html}, abstract = {$\ell_1$-Graph, which learns a sparse graph over the data by sparse representation, has been demonstrated to be effective in clustering especially for high dimensional data. Although it achieves compelling performance, the sparse graph generated by $\ell_1$-Graph ignores the geometric information of the data by sparse representation for each datum separately. To obtain a sparse graph that is aligned to the underlying manifold structure of the data, we propose the novel Neighborhood Regularized $\ell_1$-Graph (NR$\ell_1$-Graph). NR$\ell_1$-Graph learns sparse graph with locally consistent neighborhood by encouraging nearby data to have similar neighbors in the constructed sparse graph. We present the optimization algorithm of NR$\ell_1-Graph with theoretical guarantee on the convergence and the gap between the sub-optimal solution and the globally optimal solution in each step of the coordinate descent, which is essential for the overall optimization of NR$\ell_1$-Graph. Its provable accelerated version, NR$\ell_1$-Graph by Random Projection (NR$\ell_1$-Graph-RP) that employs randomized data matrix decomposition, is also presented to improve the efficiency of the optimization of NR$\ell_1$-Graph. Experimental results on various real data sets demonstrate the effectiveness of both NR$\ell_1$-Graph and NR$\ell_1$-Graph-RP. This work is supported in part by US Army Research Office grant W911NF-15-1-0317. The work of Jiashi Feng was supported by NUS startup R-263-000-C08-133, MOE R-263-000-C21-112 and IDS R-263-000-C67-646. Pushmeet Kohli was at Microsoft Research during this project. }, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Neighborhood Regularized $\ell_1$-Graph %A Yingzhen Yang %A Jiashi Feng %A Jiahui Yu %A Jianchao Yang %A Pushmeet Kohli %A Thomas S. Huang %B Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2017 %E Gal Elidan %E Kristian Kersting %F pmlr-vR15-yang17b %I PMLR %P 581--590 %U https://proceedings.mlr.press/r15/yang17b.html %V R15 %X $\ell_1$-Graph, which learns a sparse graph over the data by sparse representation, has been demonstrated to be effective in clustering especially for high dimensional data. Although it achieves compelling performance, the sparse graph generated by $\ell_1$-Graph ignores the geometric information of the data by sparse representation for each datum separately. To obtain a sparse graph that is aligned to the underlying manifold structure of the data, we propose the novel Neighborhood Regularized $\ell_1$-Graph (NR$\ell_1$-Graph). NR$\ell_1$-Graph learns sparse graph with locally consistent neighborhood by encouraging nearby data to have similar neighbors in the constructed sparse graph. We present the optimization algorithm of NR$\ell_1-Graph with theoretical guarantee on the convergence and the gap between the sub-optimal solution and the globally optimal solution in each step of the coordinate descent, which is essential for the overall optimization of NR$\ell_1$-Graph. Its provable accelerated version, NR$\ell_1$-Graph by Random Projection (NR$\ell_1$-Graph-RP) that employs randomized data matrix decomposition, is also presented to improve the efficiency of the optimization of NR$\ell_1$-Graph. Experimental results on various real data sets demonstrate the effectiveness of both NR$\ell_1$-Graph and NR$\ell_1$-Graph-RP. This work is supported in part by US Army Research Office grant W911NF-15-1-0317. The work of Jiashi Feng was supported by NUS startup R-263-000-C08-133, MOE R-263-000-C21-112 and IDS R-263-000-C67-646. Pushmeet Kohli was at Microsoft Research during this project. %Z Reissued by PMLR on 04 October 2026.
APA
Yang, Y., Feng, J., Yu, J., Yang, J., Kohli, P. & Huang, T.S.. (2017). Neighborhood Regularized $\ell_1$-Graph. Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R15:581-590 Available from https://proceedings.mlr.press/r15/yang17b.html. Reissued by PMLR on 04 October 2026.

Related Material