Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem

Manuel Gomez-Rodriguez, Le Song, Bernhard Schoelkopf
Proceedings of The 27th Conference on Learning Theory, PMLR 35:1276-1279, 2014.

Abstract

Information spreads across social and technological networks, but often the network structures are hidden and we only observe the traces left by the diffusion processes, called cascades. It is known that, under a popular continuous-time diffusion model, as long as the model parameters satisfy a natural incoherence condition, it is possible to recover the correct network structure with high probability if we observe O(d^3 \log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. However, the incoherence condition depends, in a non-trivial way, on the source (node) distribution of the cascades, which is typically unknown. Our open problem is whether it is possible to design an active algorithm which samples the source locations in a sequential manner and achieves the same or even better sample complexity, e.g., o(d_i^3 \log N), than previous work.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-gomezrodriguez14, title = {Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem}, author = {Gomez-Rodriguez, Manuel and Song, Le and Schoelkopf, Bernhard}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {1276--1279}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/gomezrodriguez14.pdf}, url = {https://proceedings.mlr.press/v35/gomezrodriguez14.html}, abstract = {Information spreads across social and technological networks, but often the network structures are hidden and we only observe the traces left by the diffusion processes, called cascades. It is known that, under a popular continuous-time diffusion model, as long as the model parameters satisfy a natural incoherence condition, it is possible to recover the correct network structure with high probability if we observe O(d^3 \log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. However, the incoherence condition depends, in a non-trivial way, on the source (node) distribution of the cascades, which is typically unknown. Our open problem is whether it is possible to design an active algorithm which samples the source locations in a sequential manner and achieves the same or even better sample complexity, e.g., o(d_i^3 \log N), than previous work.} }
Endnote
%0 Conference Paper %T Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem %A Manuel Gomez-Rodriguez %A Le Song %A Bernhard Schoelkopf %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-gomezrodriguez14 %I PMLR %P 1276--1279 %U https://proceedings.mlr.press/v35/gomezrodriguez14.html %V 35 %X Information spreads across social and technological networks, but often the network structures are hidden and we only observe the traces left by the diffusion processes, called cascades. It is known that, under a popular continuous-time diffusion model, as long as the model parameters satisfy a natural incoherence condition, it is possible to recover the correct network structure with high probability if we observe O(d^3 \log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. However, the incoherence condition depends, in a non-trivial way, on the source (node) distribution of the cascades, which is typically unknown. Our open problem is whether it is possible to design an active algorithm which samples the source locations in a sequential manner and achieves the same or even better sample complexity, e.g., o(d_i^3 \log N), than previous work.
RIS
TY - CPAPER TI - Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem AU - Manuel Gomez-Rodriguez AU - Le Song AU - Bernhard Schoelkopf BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-gomezrodriguez14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 1276 EP - 1279 L1 - http://proceedings.mlr.press/v35/gomezrodriguez14.pdf UR - https://proceedings.mlr.press/v35/gomezrodriguez14.html AB - Information spreads across social and technological networks, but often the network structures are hidden and we only observe the traces left by the diffusion processes, called cascades. It is known that, under a popular continuous-time diffusion model, as long as the model parameters satisfy a natural incoherence condition, it is possible to recover the correct network structure with high probability if we observe O(d^3 \log N) cascades, where d is the maximum number of parents of a node and N is the total number of nodes. However, the incoherence condition depends, in a non-trivial way, on the source (node) distribution of the cascades, which is typically unknown. Our open problem is whether it is possible to design an active algorithm which samples the source locations in a sequential manner and achieves the same or even better sample complexity, e.g., o(d_i^3 \log N), than previous work. ER -
APA
Gomez-Rodriguez, M., Song, L. & Schoelkopf, B.. (2014). Open Problem: Finding Good Cascade Sampling Processes for the Network Inference Problem. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:1276-1279 Available from https://proceedings.mlr.press/v35/gomezrodriguez14.html.

Related Material