Learning Steady-States of Iterative Algorithms over Graphs

Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alex Smola, Le Song
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1106-1114, 2018.

Abstract

Many graph analytics problems can be solved via iterative algorithms where the solutions are often characterized by a set of steady-state conditions. Different algorithms respect to different set of fixed point constraints, so instead of using these traditional algorithms, can we learn an algorithm which can obtain the same steady-state solutions automatically from examples, in an effective and scalable way? How to represent the meta learner for such algorithm and how to carry out the learning? In this paper, we propose an embedding representation for iterative algorithms over graphs, and design a learning method which alternates between updating the embeddings and projecting them onto the steady-state constraints. We demonstrate the effectiveness of our framework using a few commonly used graph algorithms, and show that in some cases, the learned algorithm can handle graphs with more than 100,000,000 nodes in a single machine.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-dai18a, title = {Learning Steady-States of Iterative Algorithms over Graphs}, author = {Dai, Hanjun and Kozareva, Zornitsa and Dai, Bo and Smola, Alex and Song, Le}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1106--1114}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/dai18a/dai18a.pdf}, url = {https://proceedings.mlr.press/v80/dai18a.html}, abstract = {Many graph analytics problems can be solved via iterative algorithms where the solutions are often characterized by a set of steady-state conditions. Different algorithms respect to different set of fixed point constraints, so instead of using these traditional algorithms, can we learn an algorithm which can obtain the same steady-state solutions automatically from examples, in an effective and scalable way? How to represent the meta learner for such algorithm and how to carry out the learning? In this paper, we propose an embedding representation for iterative algorithms over graphs, and design a learning method which alternates between updating the embeddings and projecting them onto the steady-state constraints. We demonstrate the effectiveness of our framework using a few commonly used graph algorithms, and show that in some cases, the learned algorithm can handle graphs with more than 100,000,000 nodes in a single machine.} }
Endnote
%0 Conference Paper %T Learning Steady-States of Iterative Algorithms over Graphs %A Hanjun Dai %A Zornitsa Kozareva %A Bo Dai %A Alex Smola %A Le Song %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-dai18a %I PMLR %P 1106--1114 %U https://proceedings.mlr.press/v80/dai18a.html %V 80 %X Many graph analytics problems can be solved via iterative algorithms where the solutions are often characterized by a set of steady-state conditions. Different algorithms respect to different set of fixed point constraints, so instead of using these traditional algorithms, can we learn an algorithm which can obtain the same steady-state solutions automatically from examples, in an effective and scalable way? How to represent the meta learner for such algorithm and how to carry out the learning? In this paper, we propose an embedding representation for iterative algorithms over graphs, and design a learning method which alternates between updating the embeddings and projecting them onto the steady-state constraints. We demonstrate the effectiveness of our framework using a few commonly used graph algorithms, and show that in some cases, the learned algorithm can handle graphs with more than 100,000,000 nodes in a single machine.
APA
Dai, H., Kozareva, Z., Dai, B., Smola, A. & Song, L.. (2018). Learning Steady-States of Iterative Algorithms over Graphs. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1106-1114 Available from https://proceedings.mlr.press/v80/dai18a.html.

Related Material