The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation

Sven Kurras, Ulrike Luxburg, Gilles Blanchard
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1530-1538, 2014.

Abstract

Consider a neighborhood graph, for example a k-nearest neighbor graph, that is constructed on sample points drawn according to some density p. Our goal is to re-weight the graph’s edges such that all cuts and volumes behave as if the graph was built on a different sample drawn from an alternative density q. We introduce the f-adjusted graph and prove that it provides the correct cuts and volumes as the sample size tends to infinity. From an algebraic perspective, we show that its normalized Laplacian, denoted as the f-adjusted Laplacian, represents a natural family of diagonal perturbations of the original normalized Laplacian. Our technique allows to apply any cut and volume based algorithm to the f-adjusted graph, for example spectral clustering, in order to study the given graph as if it were built on an unaccessible sample from a different density. We point out applications in sample bias correction, data uniformization, and multi-scale analysis of graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-kurras14, title = {The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation}, author = {Kurras, Sven and Luxburg, Ulrike and Blanchard, Gilles}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1530--1538}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/kurras14.pdf}, url = {https://proceedings.mlr.press/v32/kurras14.html}, abstract = {Consider a neighborhood graph, for example a k-nearest neighbor graph, that is constructed on sample points drawn according to some density p. Our goal is to re-weight the graph’s edges such that all cuts and volumes behave as if the graph was built on a different sample drawn from an alternative density q. We introduce the f-adjusted graph and prove that it provides the correct cuts and volumes as the sample size tends to infinity. From an algebraic perspective, we show that its normalized Laplacian, denoted as the f-adjusted Laplacian, represents a natural family of diagonal perturbations of the original normalized Laplacian. Our technique allows to apply any cut and volume based algorithm to the f-adjusted graph, for example spectral clustering, in order to study the given graph as if it were built on an unaccessible sample from a different density. We point out applications in sample bias correction, data uniformization, and multi-scale analysis of graphs.} }
Endnote
%0 Conference Paper %T The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation %A Sven Kurras %A Ulrike Luxburg %A Gilles Blanchard %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-kurras14 %I PMLR %P 1530--1538 %U https://proceedings.mlr.press/v32/kurras14.html %V 32 %N 2 %X Consider a neighborhood graph, for example a k-nearest neighbor graph, that is constructed on sample points drawn according to some density p. Our goal is to re-weight the graph’s edges such that all cuts and volumes behave as if the graph was built on a different sample drawn from an alternative density q. We introduce the f-adjusted graph and prove that it provides the correct cuts and volumes as the sample size tends to infinity. From an algebraic perspective, we show that its normalized Laplacian, denoted as the f-adjusted Laplacian, represents a natural family of diagonal perturbations of the original normalized Laplacian. Our technique allows to apply any cut and volume based algorithm to the f-adjusted graph, for example spectral clustering, in order to study the given graph as if it were built on an unaccessible sample from a different density. We point out applications in sample bias correction, data uniformization, and multi-scale analysis of graphs.
RIS
TY - CPAPER TI - The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation AU - Sven Kurras AU - Ulrike Luxburg AU - Gilles Blanchard BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-kurras14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1530 EP - 1538 L1 - http://proceedings.mlr.press/v32/kurras14.pdf UR - https://proceedings.mlr.press/v32/kurras14.html AB - Consider a neighborhood graph, for example a k-nearest neighbor graph, that is constructed on sample points drawn according to some density p. Our goal is to re-weight the graph’s edges such that all cuts and volumes behave as if the graph was built on a different sample drawn from an alternative density q. We introduce the f-adjusted graph and prove that it provides the correct cuts and volumes as the sample size tends to infinity. From an algebraic perspective, we show that its normalized Laplacian, denoted as the f-adjusted Laplacian, represents a natural family of diagonal perturbations of the original normalized Laplacian. Our technique allows to apply any cut and volume based algorithm to the f-adjusted graph, for example spectral clustering, in order to study the given graph as if it were built on an unaccessible sample from a different density. We point out applications in sample bias correction, data uniformization, and multi-scale analysis of graphs. ER -
APA
Kurras, S., Luxburg, U. & Blanchard, G.. (2014). The f-Adjusted Graph Laplacian: a Diagonal Modification with a Geometric Interpretation. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1530-1538 Available from https://proceedings.mlr.press/v32/kurras14.html.

Related Material