Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation

Saeed Amizadeh, Bo Thiesson, Milos Hauskrecht
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:61-70, 2012.

Abstract

In recent years, non-parametric methods utilizing random walks on graphs have been used to solve a wide range of machine learning problems, but in their simplest form they do not scale well due to the quadratic complexity. In this paper, a new dual-tree based variational approach for approximating the transition matrix and efficiently performing the random walk is proposed. The approach exploits a connection between kernel density estimation, mixture modeling, and random walk on graphs in an optimization of the transition matrix for the data graph that ties together edge transitions probabilities that are similar. Compared to the de facto standard approximation method based on k-nearestneighbors, we demonstrate order of magnitudes speedup without sacrificing accuracy for Label Propagation tasks on benchmark data sets in semi-supervised learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-amizadeh12a, title = {Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation}, author = {Amizadeh, Saeed and Thiesson, Bo and Hauskrecht, Milos}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {61--70}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/amizadeh12a/amizadeh12a.pdf}, url = {https://proceedings.mlr.press/r10/amizadeh12a.html}, abstract = {In recent years, non-parametric methods utilizing random walks on graphs have been used to solve a wide range of machine learning problems, but in their simplest form they do not scale well due to the quadratic complexity. In this paper, a new dual-tree based variational approach for approximating the transition matrix and efficiently performing the random walk is proposed. The approach exploits a connection between kernel density estimation, mixture modeling, and random walk on graphs in an optimization of the transition matrix for the data graph that ties together edge transitions probabilities that are similar. Compared to the de facto standard approximation method based on k-nearestneighbors, we demonstrate order of magnitudes speedup without sacrificing accuracy for Label Propagation tasks on benchmark data sets in semi-supervised learning.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation %A Saeed Amizadeh %A Bo Thiesson %A Milos Hauskrecht %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-amizadeh12a %I PMLR %P 61--70 %U https://proceedings.mlr.press/r10/amizadeh12a.html %V R10 %X In recent years, non-parametric methods utilizing random walks on graphs have been used to solve a wide range of machine learning problems, but in their simplest form they do not scale well due to the quadratic complexity. In this paper, a new dual-tree based variational approach for approximating the transition matrix and efficiently performing the random walk is proposed. The approach exploits a connection between kernel density estimation, mixture modeling, and random walk on graphs in an optimization of the transition matrix for the data graph that ties together edge transitions probabilities that are similar. Compared to the de facto standard approximation method based on k-nearestneighbors, we demonstrate order of magnitudes speedup without sacrificing accuracy for Label Propagation tasks on benchmark data sets in semi-supervised learning. %Z Reissued by PMLR on 04 October 2026.
APA
Amizadeh, S., Thiesson, B. & Hauskrecht, M.. (2012). Variational Dual-Tree Framework for Large-Scale Transition Matrix Approximation. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:61-70 Available from https://proceedings.mlr.press/r10/amizadeh12a.html. Reissued by PMLR on 04 October 2026.

Related Material