2018 SIAM International Conference on Data Mining (SDMձ8)

May 3-5, 2018      San Diego, California


Tutorial Title:  Problems with Partially Observed (Incomplete) Networks: Biases, Skewed Results, and Solutions


Abstract:  Networked representations of physical and social phenomena are ubiquitous. Examples include social and information networks, technological and communication networks, co-purchasing networks, etc. These networks are often incomplete because the phenomena are partially observed. Working with incomplete networks can skew analyses. Acquiring the full data is often unrealistic (e.g., obtaining the Twitter Firehose is not viable), but one may be able to collect data selectively to enrich the incomplete network. With a limited query budget, which parts of a partially observed network should be examined to give the best (i.e., most complete) view of the entire network? Suppose that one has obtained a sample of a Twitter retweet network from a Web site. The sample was collected for some other purpose (unbeknownst to us), and so may not contain the most useful structural information for one’s purposes. How should one best supplement this sampled data? This tutorial addresses the above questions. In particular, it we will focus on multi-armed bandit and reinforcement learning solutions



·      Tina Eliassi-Rad, Northeastern University, tina@eliassi.org

·      Sucheta Soundarajan, Syracuse University, susounda@syr.edu

·      Sahely Bhadra, Indian Institute of Technology, Palakkad, Kerala, India, sahely@iitpkd.ac.in


Schedule:  This two-hour tutorial will cover the following:

·      Complex networks and their properties

·      Partial observability, biases, and skewed results

·      The network completion problem

·      Multi-armed bandit solutions

·      Limits of learning in incomplete networks


Slides:  Available here.


Resources & code:  Will be uploaded soon. Stay tuned.


Target Audience and Prerequisites:  Our target audience includes researchers and practitioners in data mining and machine learning, with an interest in incomplete (a.k.a. partially observed) networks and graphs. We are targeting people who are concerned about the latent biases in the “real-world” data being used in research and industry. We expect the audience to come away with an overview of the state-of-art in enriching incomplete networks and have a better understanding of the challenges in this area. No assumption is made about familiarity with complex networks, graph mining, graph sampling, and incomplete data. A brief overview of them will be included in the tutorial.



[1]  K. Avrachenkov, N. Litvak, L. O. Prokhorenkova, and E. Sayargulova. Quick detection of high-degree entities in large directed networks. In ICDM, pages 54–65, 2014.

[2]  M. Bilgic, L. Mihalkova, and L. Getoor. Active learning for networked data. In ICML, pages 79–86, 2010.

[3]  S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, vol. 5, no. 1, pages 1–122, 2012.

[4]  S. Chen, A. Mira, and J.-P. Onnela. Flexible Model Selection for Mechanistic Network Models via Super Learner. CoRR, abs/1804.00237v1, April 2018.

[5]  J. Cho, H. Garcia-Molina, and L. Page. Efficient crawling through URL ordering. In WWW, pages 161–172, 1998.

[6]  R. Cohen, S. Havlin, and D. Ben-Avraham. Efficient immunization strategies for computer networks and populations. Phys. Rev. Lett., vol. 91, no. 24, p. 247901, 2003.

[7]  C. Cooper, T. Radzik, and Y. Siantos. Estimating network parameters using random walks. In CASoN, pages 33–40, 2012.

[8]  C. Dann, G. Neumann, and J. Peters. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research 15: 809–883 (2014).

[9]  A. Dasgupta, R. Kumar, and D. Sivakumar. Social sampling. In KDD, pages 235–243, 2012.

[10]    A. Dasgupta, R. Kumar, and T. Sarlós. On estimating the average degree. In WWW, pages 795–806, 2014.

[11]    I. Grondman, L. Busoniu, G.A.D. Lopes, and R. Babuska. A survey of actor-critic reinforcement learning: Standard and natural policy gradients. IEEE Trans. Systems, Man, and Cybernetics, Part C 42(6): 1291–1307 (2012).

[12]    S. Hanneke and E. P. Xing. Network completing and survey sampling. In AISTATS, pages 209–215, 2009.

[13]    M. Kim and J. Leskovec. The network completion problem: Inferring missing nodes and edges in networks. In SDM, pages 47–58, 2011.

[14]    T. LaRock, T. Sakharov, S. Bhadra, and T. Eliassi-Rad. Limits of Learning in Incomplete Networks, NetSci’18, Paris, France, June 2018.

[15]    J. Leskovec and C. Faloutsos. Sampling from large graphs. In KDD, pages 631–636, 2006.

[16]    S. A. Macskassy and F. Provost. Suspicion scoring based on guilt-by association, collective inference, and focused data access. In International Conference on Intelligence Analysis, 2005.

[17]    K. Madhawa and T. Murata. Exploring Partially Observed Networks with Nonparametric Bandits, CoRR, abs/1804.07059v1, April 2018.

[18]    A. S. Maiya and T. Berger-Wolf. Online sampling of high centrality individuals in social networks. In PAKDD, pages 91–98, 2010.

[19]    A. S. Maiya and T. Berger-Wolf. Sampling community structure. In WWW, pages 701–710, 2010.

[20]    A. S. Maiya and T. Y. Berger-Wolf. Benefits of bias: Towards better characterization of network sampling. In KDD, pages 105–113, 2011.

[21]    F. Murai, D. Rennó, B. Ribeiro, G.L. Pappa, D. Towsley and K. Gile. Selective harvesting over networks. CoRR, abs/1703.05082v1, March 2017.

[22]    L. Peel. Estimating network parameters for selecting community detection algorithms. In FUSION, pages 1–8, 2010.

[23]    J. J. Pfeiffer III, J. Neville, and P. N. Bennett. Active sampling of networks. In MLG Workshop, 2012.

[24]    J. J. Pfeiffer III, J. Neville, and P. N. Bennett. Active exploration in networks: Using probabilistic relationships for learning and inference. In CIKM, pages 639–648, 2014.

[25]    V. S. Sheng, F. Provost, and P. G. Ipeirotis. Get another label? Improving data quality and data mining using multiple, noisy labelers. In KDD, pages 614–622, 2008.

[26]    S. Soundarajan, T. Eliassi-Rad, B. Gallagher, and A. Pinar. MaxOutProbe: An algorithm for increasing the size of partially observed networks. In NIPS Workshop on Networks in the Social and Information Sciences, December 2015.

[27]    S. Soundarajan, T. Eliassi-Rad, B. Gallagher, and A. Pinar. MaxReach: Reducing network incompleteness through node probes. In ASONAM 2016: 152–157.

[28]    S. Soundarajan, T. Eliassi-Rad, B. Gallagher, and A. Pinar. e-WGX: Adaptive edge probing for enhancing incomplete networks. In WebSci, June 2017.

[29]    R.S. Sutton, H.R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesvári, and E. Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. In ICML 2009: 993–1000.

[30]    D. Thompson, J. Bennett, C. Seshadhri, and A. Pinar. A provably-robust sampling method for generating colormaps of large data. In LDAV, pages 77–84, 2013.

[31]    J. Vermorel and M. Mohri. Multi-armed bandit algorithms and empirical evaluation. In ECML, pages 437–448, 2005.