Defending against Social Network Sybils with Interaction Graph Embedding

Today's online social networks (OSNs) are plagued by Sybil attack in the form of the creation of fake accounts. A promising way to perform Sybil detection is to utilize the topological features of social network, but effectively mining such information is difficult as nodes are highly correlated. We propose a new Sybil detection method based on the interaction graph embedding. In particular, we model the friend requests of users as a signed interaction graph, and perform Sybil detection Uy decoupling the graph into independent vectors in a low-dimensional space. The intuition of our embedding is to enable every user to stay close to the people he/she accepts whereas keeping far away from those helshe rejects in the space. We prove that the objective of our embedding is equivalent to finding the graph cut which can reliably detect a region comprised of Sybils. To efficiently obtain the desired embedding, we propose an novel multi-level optimization to solve the aforementioned objective. We show that our embedding-based approach can discern Sybils under a broad range of scenarios and outperform the state-of-the-art algorithm that directly detects Sybil region over the graph.