Improving Sybil Detection via Graph Pruning and Regularization Techniques

Huanhuan Zhang, Jie Zhang, Carol Fung, Chang Xu
Asian Conference on Machine Learning, PMLR 45:189-204, 2016.

Abstract

Due to their open and anonymous nature, online social networks are particularly vulnerable to Sybil attacks. In recent years, there has been a rising interest in leveraging social network topological structures to combat Sybil attacks. Unfortunately, due to their strong dependency on unrealistic assumptions, existing graph-based Sybil defense mechanisms suffer from high false detection rates. In this paper, we focus on enhancing those mechanisms by considering additional graph structural information underlying social networks. Our solutions are based on our novel understanding and interpretation of Sybil detection as the problem of partially labeled classification. Specifically, we first propose an effective graph pruning technique to enhance the robustness of existing Sybil defense mechanisms against target attacks, by utilizing the local structural similarity between neighboring nodes in a social network. Second, we design a domain-specific graph regularization method to further improve the performance of those mechanisms by exploiting the relational property of the social network. Experimental results on four popular online social network datasets demonstrate that our proposed techniques can significantly improve the detection accuracy over the original Sybil defense mechanisms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v45-Zhang15b, title = {Improving Sybil Detection via Graph Pruning and Regularization Techniques}, author = {Zhang, Huanhuan and Zhang, Jie and Fung, Carol and Xu, Chang}, booktitle = {Asian Conference on Machine Learning}, pages = {189--204}, year = {2016}, editor = {Holmes, Geoffrey and Liu, Tie-Yan}, volume = {45}, series = {Proceedings of Machine Learning Research}, address = {Hong Kong}, month = {20--22 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v45/Zhang15b.pdf}, url = {https://proceedings.mlr.press/v45/Zhang15b.html}, abstract = {Due to their open and anonymous nature, online social networks are particularly vulnerable to Sybil attacks. In recent years, there has been a rising interest in leveraging social network topological structures to combat Sybil attacks. Unfortunately, due to their strong dependency on unrealistic assumptions, existing graph-based Sybil defense mechanisms suffer from high false detection rates. In this paper, we focus on enhancing those mechanisms by considering additional graph structural information underlying social networks. Our solutions are based on our novel understanding and interpretation of Sybil detection as the problem of partially labeled classification. Specifically, we first propose an effective graph pruning technique to enhance the robustness of existing Sybil defense mechanisms against target attacks, by utilizing the local structural similarity between neighboring nodes in a social network. Second, we design a domain-specific graph regularization method to further improve the performance of those mechanisms by exploiting the relational property of the social network. Experimental results on four popular online social network datasets demonstrate that our proposed techniques can significantly improve the detection accuracy over the original Sybil defense mechanisms.} }
Endnote
%0 Conference Paper %T Improving Sybil Detection via Graph Pruning and Regularization Techniques %A Huanhuan Zhang %A Jie Zhang %A Carol Fung %A Chang Xu %B Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Geoffrey Holmes %E Tie-Yan Liu %F pmlr-v45-Zhang15b %I PMLR %P 189--204 %U https://proceedings.mlr.press/v45/Zhang15b.html %V 45 %X Due to their open and anonymous nature, online social networks are particularly vulnerable to Sybil attacks. In recent years, there has been a rising interest in leveraging social network topological structures to combat Sybil attacks. Unfortunately, due to their strong dependency on unrealistic assumptions, existing graph-based Sybil defense mechanisms suffer from high false detection rates. In this paper, we focus on enhancing those mechanisms by considering additional graph structural information underlying social networks. Our solutions are based on our novel understanding and interpretation of Sybil detection as the problem of partially labeled classification. Specifically, we first propose an effective graph pruning technique to enhance the robustness of existing Sybil defense mechanisms against target attacks, by utilizing the local structural similarity between neighboring nodes in a social network. Second, we design a domain-specific graph regularization method to further improve the performance of those mechanisms by exploiting the relational property of the social network. Experimental results on four popular online social network datasets demonstrate that our proposed techniques can significantly improve the detection accuracy over the original Sybil defense mechanisms.
RIS
TY - CPAPER TI - Improving Sybil Detection via Graph Pruning and Regularization Techniques AU - Huanhuan Zhang AU - Jie Zhang AU - Carol Fung AU - Chang Xu BT - Asian Conference on Machine Learning DA - 2016/02/25 ED - Geoffrey Holmes ED - Tie-Yan Liu ID - pmlr-v45-Zhang15b PB - PMLR DP - Proceedings of Machine Learning Research VL - 45 SP - 189 EP - 204 L1 - http://proceedings.mlr.press/v45/Zhang15b.pdf UR - https://proceedings.mlr.press/v45/Zhang15b.html AB - Due to their open and anonymous nature, online social networks are particularly vulnerable to Sybil attacks. In recent years, there has been a rising interest in leveraging social network topological structures to combat Sybil attacks. Unfortunately, due to their strong dependency on unrealistic assumptions, existing graph-based Sybil defense mechanisms suffer from high false detection rates. In this paper, we focus on enhancing those mechanisms by considering additional graph structural information underlying social networks. Our solutions are based on our novel understanding and interpretation of Sybil detection as the problem of partially labeled classification. Specifically, we first propose an effective graph pruning technique to enhance the robustness of existing Sybil defense mechanisms against target attacks, by utilizing the local structural similarity between neighboring nodes in a social network. Second, we design a domain-specific graph regularization method to further improve the performance of those mechanisms by exploiting the relational property of the social network. Experimental results on four popular online social network datasets demonstrate that our proposed techniques can significantly improve the detection accuracy over the original Sybil defense mechanisms. ER -
APA
Zhang, H., Zhang, J., Fung, C. & Xu, C.. (2016). Improving Sybil Detection via Graph Pruning and Regularization Techniques. Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 45:189-204 Available from https://proceedings.mlr.press/v45/Zhang15b.html.

Related Material