Finding Critical Users in Social Communities via Graph Convolutions

Finding critical users whose existence keeps a social community cohesive and large is an important issue in social networks. In the literature, such criticalness of a user is measured by the number of followers who will leave the community together when the user leaves. By taking a social community as a k-core, which can be computed in linear time, the problem of finding critical users is to find a set of nodes, U, with a user-given size b in a k-core community that maximizes the number of nodes (followers) to be deleted from the k-core when all nodes in $U$U are deleted. This problem is known to be NP-hard. In the literature, the state-of-the-art approach, a greedy algorithm is proposed with no guarantee on the set of nodes U found, since there does not exist a submodular function the greedy algorithm can use to get a better answer iteratively. Furthermore, the greedy algorithm designed is to handle k-core in any social networks such that it does not consider the structural complexity of a given single graph and cannot get the global optimal by the local optimal found in iterations. In this paper, we propose a novel learning-based approach. Distinguished from traditional experience-based heuristics, we propose a neural network model, called Self-attentive Core Graph Convolution Network (SCGCN), to capture the hidden structure of the criticalness among node combinations that break the engagement of a specific social community. Supervised by sampling node combinations, SCGCN has the ability to inference the criticalness of unseen combinations of nodes. To further reduce the sampling and inference space, we propose a deterministic strategy to prune unpromising nodes on the graph. Our experiments conducted on many real-world graphs show that SCGCN significantly improves the quality of the solution compared with the state-of-the-art greedy algorithm.