The 25TH ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2019)

August 4-8, 2019      Anchorage, Alaska

 

Tutorial Title:  Incompleteness in Networks: Biases, Skewed Results, and Some Solutions

 

Abstract:  Network analysis is often conducted on incomplete samples of much larger fully observed networks (which are supposed to represent some phenomena of interest). For example, many researchers obtain networks from online data repositories (such as snap.stanford.edu and icon.colorado.edu) without knowing how the networks were collected. Such networks can be poor representations of the fully observed phenomena. More complete data would lead to more accurate analyses, but data acquisition can be at best costly and at worst error-prone (e.g., consider an adversary that deliberately poisons the answer to a query). Past work on this topic has forked into two branches: (1) assume a network model and use the observed data to infer the unobserved data; and (2) do not assume a network model, instead use the observed data to learn a policy for data acquisition given a query budget. We focus on the second branch. That is, given a query budget for identifying additional nodes and edges, how can one improve the observed network sample so that it is a more accurate representation of the fully observed network? This problem is related to, but distinct from, topics such as graph sampling and crawling. In this tutorial, we will discuss latent biases in incomplete networks and present methods for enriching such networks through active probing of nodes and edges. We will focus on multi-armed bandit, online active learning, and Markov decision process formulations of this problem (a.k.a. the network discovery problem); and clarify distinctions between learning to grow the network (a.k.a. active exploration) and learning the “best” function on the network (a.k.a. active learning).

 

Presenters

·      Tina Eliassi-Rad, Northeastern University

·      Rajmonda Caceres, MIT Lincoln Laboratory

·      Timothy LaRock, Northeastern University

 

Contributors

·      Timothy Sakharov, Northeastern University

·      Benjamin A. Miller, Northeastern University

·      Sucheta Soundarajan, Syracuse University

·      Sahely Bhadra, Indian Institute of Technology, Palakkad, Kerala, India

 

Slides and resources: Check back on July 12, 2019 for that information.