GraphOpt: Learning Optimization Models of Graph Formation

Rakshit Trivedi, Jiachen Yang, Hongyuan Zha
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:9603-9613, 2020.

Abstract

Formation mechanisms are fundamental to the study of complex networks, but learning them from observations is challenging. In real-world domains, one often has access only to the final constructed graph, instead of the full construction process, and observed graphs exhibit complex structural properties. In this work, we propose GraphOpt, an end-to-end framework that jointly learns an implicit model of graph structure formation and discovers an underlying optimization mechanism in the form of a latent objective function. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm. Further, it employs a novel continuous latent action space that aids scalability. Empirically, we demonstrate that GraphOpt discovers a latent objective transferable across graphs with different characteristics. GraphOpt also learns a robust stochastic policy that achieves competitive link prediction performance without being explicitly trained on this task and further enables construction of graphs with properties similar to those of the observed graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-trivedi20a, title = {{G}raph{O}pt: Learning Optimization Models of Graph Formation}, author = {Trivedi, Rakshit and Yang, Jiachen and Zha, Hongyuan}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {9603--9613}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/trivedi20a/trivedi20a.pdf}, url = {https://proceedings.mlr.press/v119/trivedi20a.html}, abstract = {Formation mechanisms are fundamental to the study of complex networks, but learning them from observations is challenging. In real-world domains, one often has access only to the final constructed graph, instead of the full construction process, and observed graphs exhibit complex structural properties. In this work, we propose GraphOpt, an end-to-end framework that jointly learns an implicit model of graph structure formation and discovers an underlying optimization mechanism in the form of a latent objective function. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm. Further, it employs a novel continuous latent action space that aids scalability. Empirically, we demonstrate that GraphOpt discovers a latent objective transferable across graphs with different characteristics. GraphOpt also learns a robust stochastic policy that achieves competitive link prediction performance without being explicitly trained on this task and further enables construction of graphs with properties similar to those of the observed graph.} }
Endnote
%0 Conference Paper %T GraphOpt: Learning Optimization Models of Graph Formation %A Rakshit Trivedi %A Jiachen Yang %A Hongyuan Zha %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-trivedi20a %I PMLR %P 9603--9613 %U https://proceedings.mlr.press/v119/trivedi20a.html %V 119 %X Formation mechanisms are fundamental to the study of complex networks, but learning them from observations is challenging. In real-world domains, one often has access only to the final constructed graph, instead of the full construction process, and observed graphs exhibit complex structural properties. In this work, we propose GraphOpt, an end-to-end framework that jointly learns an implicit model of graph structure formation and discovers an underlying optimization mechanism in the form of a latent objective function. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm. Further, it employs a novel continuous latent action space that aids scalability. Empirically, we demonstrate that GraphOpt discovers a latent objective transferable across graphs with different characteristics. GraphOpt also learns a robust stochastic policy that achieves competitive link prediction performance without being explicitly trained on this task and further enables construction of graphs with properties similar to those of the observed graph.
APA
Trivedi, R., Yang, J. & Zha, H.. (2020). GraphOpt: Learning Optimization Models of Graph Formation. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:9603-9613 Available from https://proceedings.mlr.press/v119/trivedi20a.html.

Related Material