Network Completion and Survey Sampling

Steve Hanneke, Eric P. Xing
Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, PMLR 5:209-215, 2009.

Abstract

We study the problem of learning the topology of an undirected network by observing a random subsample. Specifically, the sample is chosen by randomly selecting a fixed number of vertices, and for each we are allowed to observe all edges it is incident with. We analyze a general formalization of learning from such samples, and derive confidence bounds on the number of differences between the true and learned topologies, as a function of the number of observed mistakes and the algorithm’s bias. In addition to this general analysis, we also analyze a variant of the problem under a stochastic block model assumption.

Cite this Paper

BibTeX
@InProceedings{pmlr-v5-hanneke09a, title = {Network Completion and Survey Sampling}, author = {Hanneke, Steve and Xing, Eric P.}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {209--215}, year = {2009}, editor = {van Dyk, David and Welling, Max}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/hanneke09a/hanneke09a.pdf}, url = {https://proceedings.mlr.press/v5/hanneke09a.html}, abstract = {We study the problem of learning the topology of an undirected network by observing a random subsample. Specifically, the sample is chosen by randomly selecting a fixed number of vertices, and for each we are allowed to observe all edges it is incident with. We analyze a general formalization of learning from such samples, and derive confidence bounds on the number of differences between the true and learned topologies, as a function of the number of observed mistakes and the algorithm’s bias. In addition to this general analysis, we also analyze a variant of the problem under a stochastic block model assumption.} }
Endnote
%0 Conference Paper %T Network Completion and Survey Sampling %A Steve Hanneke %A Eric P. Xing %B Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-hanneke09a %I PMLR %P 209--215 %U https://proceedings.mlr.press/v5/hanneke09a.html %V 5 %X We study the problem of learning the topology of an undirected network by observing a random subsample. Specifically, the sample is chosen by randomly selecting a fixed number of vertices, and for each we are allowed to observe all edges it is incident with. We analyze a general formalization of learning from such samples, and derive confidence bounds on the number of differences between the true and learned topologies, as a function of the number of observed mistakes and the algorithm’s bias. In addition to this general analysis, we also analyze a variant of the problem under a stochastic block model assumption.
RIS
TY - CPAPER TI - Network Completion and Survey Sampling AU - Steve Hanneke AU - Eric P. Xing BT - Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-hanneke09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 209 EP - 215 L1 - http://proceedings.mlr.press/v5/hanneke09a/hanneke09a.pdf UR - https://proceedings.mlr.press/v5/hanneke09a.html AB - We study the problem of learning the topology of an undirected network by observing a random subsample. Specifically, the sample is chosen by randomly selecting a fixed number of vertices, and for each we are allowed to observe all edges it is incident with. We analyze a general formalization of learning from such samples, and derive confidence bounds on the number of differences between the true and learned topologies, as a function of the number of observed mistakes and the algorithm’s bias. In addition to this general analysis, we also analyze a variant of the problem under a stochastic block model assumption. ER -
APA
Hanneke, S. & Xing, E.P.. (2009). Network Completion and Survey Sampling. Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:209-215 Available from https://proceedings.mlr.press/v5/hanneke09a.html.

Related Material