Learning from Contagion (Without Timestamps)

Kareem Amin, Hoda Heidari, Michael Kearns
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1845-1853, 2014.

Abstract

We introduce and study new models for learning from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed infections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models differ from prior work in that detailed vertex-by-vertex timestamps for the spread of the contagion are not observed. The goal of learning is to infer the unknown network structure. Our main theoretical results are efficient and provably correct algorithms for exactly learning trees. We provide empirical evidence that our algorithm performs well more generally on realistic sparse graphs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-amin14, title = {Learning from Contagion (Without Timestamps)}, author = {Amin, Kareem and Heidari, Hoda and Kearns, Michael}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1845--1853}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/amin14.pdf}, url = {https://proceedings.mlr.press/v32/amin14.html}, abstract = {We introduce and study new models for learning from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed infections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models differ from prior work in that detailed vertex-by-vertex timestamps for the spread of the contagion are not observed. The goal of learning is to infer the unknown network structure. Our main theoretical results are efficient and provably correct algorithms for exactly learning trees. We provide empirical evidence that our algorithm performs well more generally on realistic sparse graphs.} }
Endnote
%0 Conference Paper %T Learning from Contagion (Without Timestamps) %A Kareem Amin %A Hoda Heidari %A Michael Kearns %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-amin14 %I PMLR %P 1845--1853 %U https://proceedings.mlr.press/v32/amin14.html %V 32 %N 2 %X We introduce and study new models for learning from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed infections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models differ from prior work in that detailed vertex-by-vertex timestamps for the spread of the contagion are not observed. The goal of learning is to infer the unknown network structure. Our main theoretical results are efficient and provably correct algorithms for exactly learning trees. We provide empirical evidence that our algorithm performs well more generally on realistic sparse graphs.
RIS
TY - CPAPER TI - Learning from Contagion (Without Timestamps) AU - Kareem Amin AU - Hoda Heidari AU - Michael Kearns BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-amin14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1845 EP - 1853 L1 - http://proceedings.mlr.press/v32/amin14.pdf UR - https://proceedings.mlr.press/v32/amin14.html AB - We introduce and study new models for learning from contagion processes in a network. A learning algorithm is allowed to either choose or passively observe an initial set of seed infections. This seed set then induces a final set of infections resulting from the underlying stochastic contagion dynamics. Our models differ from prior work in that detailed vertex-by-vertex timestamps for the spread of the contagion are not observed. The goal of learning is to infer the unknown network structure. Our main theoretical results are efficient and provably correct algorithms for exactly learning trees. We provide empirical evidence that our algorithm performs well more generally on realistic sparse graphs. ER -
APA
Amin, K., Heidari, H. & Kearns, M.. (2014). Learning from Contagion (Without Timestamps). Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1845-1853 Available from https://proceedings.mlr.press/v32/amin14.html.

Related Material