  Online social networks (OSNs) are threatened by Sybil attacks, which create
fake accounts (also called Sybils) on OSNs and use them for various malicious
activities. Therefore, Sybil detection is a fundamental task for OSN security.
Most existing Sybil detection methods are based on the graph structure of OSNs,
and various methods have been proposed recently. However, although almost all
methods have been compared experimentally in terms of detection performance and
noise robustness, theoretical understanding of them is still lacking. In this
study, we show that existing graph-based Sybil detection methods can be
interpreted in a unified framework of low-pass filtering. This framework
enables us to theoretically compare and analyze each method from two
perspectives: filter kernel properties and the spectrum of shift matrices. Our
analysis reveals that the detection performance of each method depends on how
well low-pass filtering can extract low frequency components and remove noisy
high frequency components. Furthermore, on the basis of the analysis, we
propose a novel Sybil detection method called SybilHeat. Numerical experiments
on synthetic graphs and real social networks demonstrate that SybilHeat
performs consistently well on graphs with various structural properties. This
study lays a theoretical foundation for graph-based Sybil detection and leads
to a better understanding of Sybil detection methods.
