Improved Semi-Supervised Learning with Multiple Graphs

Krishnamurthy Viswanathan, Sushant Sachdeva, Andrew Tomkins, Sujith Ravi
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:3032-3041, 2019.

Abstract

We present a new approach for graph based semi-supervised learning based on a multi-component extension to the Gaussian MRF model. This approach models the observations on the vertices as jointly Gaussian with an inverse covariance matrix that is a weighted linear combination of multiple matrices. Building on randomized matrix trace estimation and fast Laplacian solvers, we develop fast and efficient algorithms for computing the best-fit (maximum likelihood) model and the predicted labels using gradient descent. Our model is considerably simpler, with just tens of parameters, and a single hyperparameter, in contrast with state-of-the-art approaches using deep learning techniques. Our experiments on benchmark citation networks show that the best-fit model estimated by our algorithm leads to significant improvements on all datasets compared to baseline models. Further, our performance compares favorably with several state-of-the-art methods on these datasets, and is comparable with the best performances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-viswanathan19a, title = {Improved Semi-Supervised Learning with Multiple Graphs}, author = {Viswanathan, Krishnamurthy and Sachdeva, Sushant and Tomkins, Andrew and Ravi, Sujith}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {3032--3041}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/viswanathan19a/viswanathan19a.pdf}, url = {https://proceedings.mlr.press/v89/viswanathan19a.html}, abstract = {We present a new approach for graph based semi-supervised learning based on a multi-component extension to the Gaussian MRF model. This approach models the observations on the vertices as jointly Gaussian with an inverse covariance matrix that is a weighted linear combination of multiple matrices. Building on randomized matrix trace estimation and fast Laplacian solvers, we develop fast and efficient algorithms for computing the best-fit (maximum likelihood) model and the predicted labels using gradient descent. Our model is considerably simpler, with just tens of parameters, and a single hyperparameter, in contrast with state-of-the-art approaches using deep learning techniques. Our experiments on benchmark citation networks show that the best-fit model estimated by our algorithm leads to significant improvements on all datasets compared to baseline models. Further, our performance compares favorably with several state-of-the-art methods on these datasets, and is comparable with the best performances.} }
Endnote
%0 Conference Paper %T Improved Semi-Supervised Learning with Multiple Graphs %A Krishnamurthy Viswanathan %A Sushant Sachdeva %A Andrew Tomkins %A Sujith Ravi %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-viswanathan19a %I PMLR %P 3032--3041 %U https://proceedings.mlr.press/v89/viswanathan19a.html %V 89 %X We present a new approach for graph based semi-supervised learning based on a multi-component extension to the Gaussian MRF model. This approach models the observations on the vertices as jointly Gaussian with an inverse covariance matrix that is a weighted linear combination of multiple matrices. Building on randomized matrix trace estimation and fast Laplacian solvers, we develop fast and efficient algorithms for computing the best-fit (maximum likelihood) model and the predicted labels using gradient descent. Our model is considerably simpler, with just tens of parameters, and a single hyperparameter, in contrast with state-of-the-art approaches using deep learning techniques. Our experiments on benchmark citation networks show that the best-fit model estimated by our algorithm leads to significant improvements on all datasets compared to baseline models. Further, our performance compares favorably with several state-of-the-art methods on these datasets, and is comparable with the best performances.
APA
Viswanathan, K., Sachdeva, S., Tomkins, A. & Ravi, S.. (2019). Improved Semi-Supervised Learning with Multiple Graphs. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:3032-3041 Available from https://proceedings.mlr.press/v89/viswanathan19a.html.

Related Material