TY - JOUR AU - Conitzer, Vincent AU - Panigrahi, Debmalya AU - Zhang, Hanrui PY - 2022/06/28 Y2 - 2024/03/28 TI - Learning Influence Adoption in Heterogeneous Networks JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 36 IS - 6 SE - AAAI Technical Track on Machine Learning I DO - 10.1609/aaai.v36i6.20592 UR - https://ojs.aaai.org/index.php/AAAI/article/view/20592 SP - 6411-6419 AB - We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each individual node by sampling only a small number of nodes and observing/testing their states. We study this problem in heterogeneous networks, in which each individual node has a set of distinct features that determine how it is affected by the propagating entity. We give an efficient algorithm with nearly optimal sample complexity for two variants of this learning problem, corresponding to symptomatic and asymptomatic spread. In each case, the optimal sample complexity naturally generalizes the complexity of learning how nodes are affected in isolation, and the complexity of learning influence adoption in a homogeneous network. ER -