Interplay Between Topology and Social Learning Over Weak Graphs

This work examines a distributed learning problem where the agents of a network form their beliefs about certain hypotheses of interest. Each agent collects streaming (private) data and updates continually its belief by means of a diffusion strategy, which blends the agent's data with the beliefs of its neighbors. We focus on weakly-connected graphs, where the network is partitioned into sending and receiving sub-networks, and we allow for heterogeneous models across the agents. First, we examine what agents learn (social learning) and provide an analytical characterization for the long-term beliefs at the agents. Among other effects, the analysis predicts when a leader-follower behavior is possible, where some sending agents control the beliefs of the receiving agents by forcing them to choose a particular and possibly fake hypothesis. Second, we consider the dual or reverse learning problem that reveals how agents learn: given the beliefs collected at a receiving agent, we would like to discover the influence that any sending sub-network might have exerted on this receiving agent (topology learning). An unexpected interplay between social and topology learning emerges: given H hypotheses and S sending sub-networks, topology learning can be feasible when H >= S. The latter being only a necessary condition, we then examine the feasibility of topology learning for two useful classes of problems. The analysis reveals that a critical element to enable topology learning is a sufficient degree of diversity in the statistical models of the sending sub-networks.