Inferring Graphs from Cascades: A Sparse Recovery Framework

Jean Pouget-Abadie, Thibaut Horel
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:977-986, 2015.

Abstract

In the Graph Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascade model, for which we provide the first algorithm which recovers the graph’s edges with high probability and O(s log m) measurements where s is the maximum degree of the graph and m is the number of nodes. Furthermore, we show that our algorithm also recovers the edge weights (the parameters of the diffusion process) and is robust in the context of approximate sparsity. Finally we prove an almost matching lower bound of Ω(s \log m/s) and validate our approach empirically on synthetic graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-pouget-abadie15, title = {Inferring Graphs from Cascades: A Sparse Recovery Framework}, author = {Pouget-Abadie, Jean and Horel, Thibaut}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {977--986}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/pouget-abadie15.pdf}, url = {https://proceedings.mlr.press/v37/pouget-abadie15.html}, abstract = {In the Graph Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascade model, for which we provide the first algorithm which recovers the graph’s edges with high probability and O(s log m) measurements where s is the maximum degree of the graph and m is the number of nodes. Furthermore, we show that our algorithm also recovers the edge weights (the parameters of the diffusion process) and is robust in the context of approximate sparsity. Finally we prove an almost matching lower bound of Ω(s \log m/s) and validate our approach empirically on synthetic graphs.} }
Endnote
%0 Conference Paper %T Inferring Graphs from Cascades: A Sparse Recovery Framework %A Jean Pouget-Abadie %A Thibaut Horel %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-pouget-abadie15 %I PMLR %P 977--986 %U https://proceedings.mlr.press/v37/pouget-abadie15.html %V 37 %X In the Graph Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascade model, for which we provide the first algorithm which recovers the graph’s edges with high probability and O(s log m) measurements where s is the maximum degree of the graph and m is the number of nodes. Furthermore, we show that our algorithm also recovers the edge weights (the parameters of the diffusion process) and is robust in the context of approximate sparsity. Finally we prove an almost matching lower bound of Ω(s \log m/s) and validate our approach empirically on synthetic graphs.
RIS
TY - CPAPER TI - Inferring Graphs from Cascades: A Sparse Recovery Framework AU - Jean Pouget-Abadie AU - Thibaut Horel BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-pouget-abadie15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 977 EP - 986 L1 - http://proceedings.mlr.press/v37/pouget-abadie15.pdf UR - https://proceedings.mlr.press/v37/pouget-abadie15.html AB - In the Graph Inference problem, one seeks to recover the edges of an unknown graph from the observations of cascades propagating over this graph. In this paper, we approach this problem from the sparse recovery perspective. We introduce a general model of cascades, including the voter model and the independent cascade model, for which we provide the first algorithm which recovers the graph’s edges with high probability and O(s log m) measurements where s is the maximum degree of the graph and m is the number of nodes. Furthermore, we show that our algorithm also recovers the edge weights (the parameters of the diffusion process) and is robust in the context of approximate sparsity. Finally we prove an almost matching lower bound of Ω(s \log m/s) and validate our approach empirically on synthetic graphs. ER -
APA
Pouget-Abadie, J. & Horel, T.. (2015). Inferring Graphs from Cascades: A Sparse Recovery Framework. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:977-986 Available from https://proceedings.mlr.press/v37/pouget-abadie15.html.

Related Material