Identifying Multiple Propagation Sources With Motif-Based Graph Convolutional Networks for Social Networks

Abstract

Identifying the sources of propagation in social networks, such as the misinformation propagation, is one of the key issues recently. Most existing studies assume the underlying propagation model is known, which is difficult to obtain in practice. Recent efforts have been devoted to detect multiple sources in real-world situations, and the social influence of neighbors in the propagation is assumed to be identical. However, this assumption will result in inaccurate results as the infection state of a node is determined by its critical neighbors. In this paper, we fill this gap by capturing social influence of neighbors with structural properties in social networks. For instance, opinions are more likely to spread via closely connected friends within small groups. Here we propose a Motif-based Graph Convolutional Networks for Source Identification (MGCNSI) framework based on the GCN-based source identification approach. Specifically, different network motifs are used to capture different types of structural properties. Then each motif extracts the critical neighbors of a particular type, and a motif-based graph convolutional layer is constructed to aggregate critical neighbors for that motif. To adapt to underlying propagation mechanisms, an attention mechanism for aggregation is designed to automatically assign higher weights to more informative motifs. The empirical results demonstrate that MGCNSI outperforms several benchmark methods on both synthetic and real-world networks. The advantage is most obvious for networks with denser node neighborhoods, where MGCNSI can select critical neighbors from the larger neighbor sets. How the motifs can capture the social influence and the underlying critical paths of propagation is also illustrated.

Keywords

• Information propagation
• multiple source identification
• motif
• graph convolutional networks