Outcomes Report:

The high-level goal of the grant was to understand both the theoretical foundations and applications of information dissemination processes on networks. Particular interest was devoted to dealing with missing or uncertain information. More specifically, the project team made the following contributions.

1. At a fundamental level, the team proposed and investigated in depth network generative models with a focus on global (as opposed to local) network properties. Many network generative models focus on matching local features (such as node degrees or small motifs); yet, most network processes of interest, such as spreads of diseases or information, are much more closely characterized by global properties such as the partition of a network into sparsely connected communities. The team's work proposed different sophisticated models which explicitly aim to match the high-level connectivity structure of a given input graph. These models are based on techniques such as non-convex optimization, linear programming, deep generative neural networks, random walks, and local search techniques. Comprehensive experimental evaluation shows that indeed, these models produce networks that match an input network not only in the network's spectrum (the explicit optimization goal) but also in various other related quantities.

2. The team carried out a comprehensive study of algorithmic techniques for inference and optimization of network influence when input data are missing or uncertain. These techniques were based on both more theoretical algorithms (such as PAC learning algorithms of network influence parameters) and more practical heuristics. In order to model such processes accurately, the team formulated various novel influence processes, including mutually influencing point processes and mixtures of cascade models. These models were shown to often result in better fits with real-world data than prior models.

3. Building on the comprehensive study of network influence processes, the team carried out an investigation of the dissemination of misinformation from a network point of view. In particular, the team exhibited significant differences in the patterns and timings of retweets and posts between real news and coordinated disinformation campaigns. These analyses both drew on and informed the models based on mixed influence processes. Experimental evaluation confirmed that using such a network-based approach, it is possible to identify coordinated misinformation campaigns using labeled data or other human annotation. This line of work may have significant applications beyond the immediate scientific interest.

4. In particular, the team leveraged the techniques described above to carry out the first large-scale analysis of coordinated disinformation campaigns about the Covid-19 pandemic. Building on the network models, the team developed a dashboard that allows visualization of coordinated campaigns by the public and by decisionmakers. This dashboard has the potential to reduce the impact of disinformation campaigns, and thereby to lead to significantly more informed decision making.

5. Finally, the team studied how to deal with missing information in learning settings more fundamentally. The team focus on a model of interactive learning, in which an algorithm must repeatedly choose a combinatorial structure, and learns about its mistakes. This setting naturally models learning of classifiers, permutations, or stable matchings, but also the inference of latent network structures by trial and error. The power of the general framework is that it allows the incorporation of incorrect responses as well as dynamic changes in the ground truth while learning happens. Rather than treating each application separately, the framework provides a universal algorithmic approach when can be easily customized.

Last Modified: 11/07/2020
Modified by: David M Kempe