Biblio

Sybils are users created for carrying out nefarious actions in online social networks (OSNs) and threaten the security of OSNs. Therefore, Sybil detection is an urgent security task, and various detection methods have been proposed. Existing Sybil detection methods are based on the relationship (i.e., graph structure) of users in OSNs. Structure-based methods can be classified into two categories: Random Walk (RW)-based and Belief Propagation (BP)-based. However, although almost all methods have been experimentally evaluated in terms of their performance and robustness to noise, the theoretical understanding of them is insufficient. In this paper, we interpret the Sybil detection problem from the viewpoint of graph signal processing and provide a framework to formulate RW- and BPbased methods as low-pass filtering. This framework enables us to theoretically compare RW- and BP-based methods and explain why BP-based methods perform well for scale-free graphs, unlike RW-based methods. Furthermore, by this framework, we relate RW- and BP-based methods and Graph Neural Networks (GNNs) and discuss the difference among these methods. Finally, we evaluate the validity of this framework through numerical experiments.