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 es- pecially for high dimensional data. Although it achieves compelling performance, the sparse graph generated by $\ell$1-Graph ignores the geo- metric information of the data by sparse rep- resentation for each datum separately. To ob- tain a sparse graph that is aligned to the un- derlying 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 neigh- borhood 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 so- lution in each step of the coordinate descent, which is essential for the overall optimiza- tion of NR$\ell$1-Graph. Its provable acceler- ated version, NR$\ell$1-Graph by Random Projec- tion (NR$\ell$1-Graph-RP) that employs random- ized data matrix decomposition, is also pre- sented to improve the efficiency of the opti- mization of NR$\ell$1-Graph. Experimental re- sults 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 Of- fice 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 es- pecially for high dimensional data. Although it achieves compelling performance, the sparse graph generated by $\ell$1-Graph ignores the geo- metric information of the data by sparse rep- resentation for each datum separately. To ob- tain a sparse graph that is aligned to the un- derlying 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 neigh- borhood 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 so- lution in each step of the coordinate descent, which is essential for the overall optimiza- tion of NR$\ell$1-Graph. Its provable acceler- ated version, NR$\ell$1-Graph by Random Projec- tion (NR$\ell$1-Graph-RP) that employs random- ized data matrix decomposition, is also pre- sented to improve the efficiency of the opti- mization of NR$\ell$1-Graph. Experimental re- sults 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 Of- fice 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 es- pecially for high dimensional data. Although it achieves compelling performance, the sparse graph generated by $\ell$1-Graph ignores the geo- metric information of the data by sparse rep- resentation for each datum separately. To ob- tain a sparse graph that is aligned to the un- derlying 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 neigh- borhood 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 so- lution in each step of the coordinate descent, which is essential for the overall optimiza- tion of NR$\ell$1-Graph. Its provable acceler- ated version, NR$\ell$1-Graph by Random Projec- tion (NR$\ell$1-Graph-RP) that employs random- ized data matrix decomposition, is also pre- sented to improve the efficiency of the opti- mization of NR$\ell$1-Graph. Experimental re- sults 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 Of- fice 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