# SybilHP: Sybil Detection in Directed Social Networks with Adaptive Homophily Prediction
## 1 Introduction  
While celebrities and influencers have a huge influence on OSNs, not all of their followers are authentic human beings on the other side of the screen. It was reported that 9-15% of active Twitter users were bots [1, 2]. By creating and controlling such bots, or Sybil accounts, malicious adversaries in social networks carry out spamming, phishing scams, referral traffic, and manipulating online public opinion, thereby causing a series of security problems and a crisis of trust. In order to counter such abuse in social networks, an increasing number of Sybil-detection methods have been proposed. According to the data used, feature-based and graph-based methods are extensively maintained. Feature-based methods train supervised classifiers for detection using diverse information of Sybil and normal users, such as local connections, profiles, IP addresses, and all kinds of behaviors and content features [3, 4, 5, 6, 7, 8]. While graph-based methods only make use of the global structure of the social graph, and detection relies on exploiting interrelations among entities (e.g., \"friendship\" on Facebook or \"follow\" on Twitter) [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25], GNN-based methods use both node features and structural characteristics of the OSN data to train graph neural networks (GNNs) for user classification [26, 27, 28, 29]. This paper focuses on graph-based detection methods. Theoretically, an underlying assumption for graph-based Sybil-detection methods is that the benign community and the Sybil community are sparsely connected; therefore, theconnections between nodes follow homophily, i.e., adjacent nodes tend to share the same label. Under this assumption, graph-based methods essentially use the block model [30] to represent a network as a set of blocks and discriminate whether an unknown node belongs to a Sybil community or a benign community. Label propagation algorithms [31; 32] are a common class of methods to achieve block segmentation. Starting from some labeled nodes, label propagation algorithms iteratively propagate the users' influence, trust, or reputation along the social connections between them, until sufficient information for label prediction is obtained. By means of propagation, most graph-based methods can be grouped into random walk (RW)-based [9; 10; 11; 12; 13; 14; 15; 22] and Loopy Belief Propagation (LBP)-based [16; 17; 20] methods. However, excluding space and time efficiency, LBP-based methods outperform RW-based methods as they can leverage both labeled benign and Sybil data, and its nonlinear nature endows robustness against label noise [17]. However, existing LBP-based methods suffer from the following problems:  
(1) They either assume a global homophily strength for all edges (e.g., GANG [20]) or predefined edge weights as homophily strength (e.g., SybilSCAR-D uses degree-normalized homophily strength [17]), while such an assumption ignores the local homophily difference of edges and, thus, fails to characterize the behavior pattern of nodes. A clear example is that users may have different capabilities to discern another benign user to follow; hence, their following edges should bear different homophily strengths. (2) They are mostly designed for undirected (symmetric) social graph models, while many real-world platforms, such as Twitter, establish networks by a \"follow\", \"retweet\", or \"thumbs up\", which are asymmetric relationships. Applying these methods directly cannot make full use of edge information. The study in [20] adapts LBP-based methods for directed graphs; however, during two-way message-passing between a directed pair, its edge-potential function acts in the same way, which does not agree with the asymmetric trust relationship. Our work: In order to overcome the limitations above, we propose a novel Sybil-detection method named SybilHP, a Sybil-detection method optimized for directed social networks with adaptive homophily prediction.