Explaining classification performance and bias via network structure and sampling technique

Applied Network Science, vol. 6

Abstract

Abstract Social networks are very important carriers of information. For instance, the political leaning of our friends can serve as a proxy to identify our own political preferences. This explanatory power is leveraged in many scenarios ranging from business decision-making to scientific research to infer missing attributes using machine learning. However, factors affecting the performance and the direction of bias of these algorithms are not well understood. To this end, we systematically study how structural properties of the network and the training sample influence the results of collective classification. Our main findings show that (i) mean classification performance can empirically and analytically be predicted by structural properties such as homophily, class balance, edge density and sample size, (ii) small training samples are enough for heterophilic networks to achieve high and unbiased classification performance, even with imperfect model estimates, (iii) homophilic networks are more prone to bias issues and low performance when group size differences increase, (iv) when sampling budgets are small, partial crawls achieve the most accurate model estimates, and degree sampling achieves the highest overall performance. Our findings help practitioners to better understand and evaluate their results when sampling budgets are small or when no ground-truth is available.

Authors 5

1. Lisette Espín-Noboa corresponding

   University of Koblenz and Landau · GESIS - Leibniz Institute for the Social Sciences · Universität Koblenz

   Affiliation as printed

   Computational Social Science, GESIS, Cologne, Germany

   Computer Science, University of Koblenz-Landau, Koblenz, Germany

2. Fariba Karimi

   GESIS - Leibniz Institute for the Social Sciences

   Affiliation as printed

   Computational Social Science, GESIS, Cologne, Germany

3. Bruno Ribeiro

   Purdue University West Lafayette

   Affiliation as printed

   Computer Science, Purdue University, West Lafayette, IN, USA

4. Kristina Lerman

   University of Southern California

   Affiliation as printed

   Artificial Intelligence, Information Sciences Institute, Los Angeles, USA

   Computer Science, University of Southern California, Los Angeles, USA

5. Claudia Wagner Aachen Computational Social Science

   GESIS - Leibniz Institute for the Social Sciences · RWTH Aachen University

   Affiliation as printed

   Computational Social Science, GESIS, Cologne, Germany

   Computational Social Science, RWTH Aachen University, Aachen, Germany