Robust Negative Sampling for Network Embedding


  • Mohammadreza Armandpour Texas A&M University
  • Patrick Ding Texas A&M University
  • Jianhua Huang Texas A&M University
  • Xia Hu Texas A&M University



Many recent network embedding algorithms use negative sampling (NS) to approximate a variant of the computationally expensive Skip-Gram neural network architecture (SGA) objective. In this paper, we provide theoretical arguments that reveal how NS can fail to properly estimate the SGA objective, and why it is not a suitable candidate for the network embedding problem as a distinct objective. We show NS can learn undesirable embeddings, as the result of the “Popular Neighbor Problem.” We use the theory to develop a new method “R-NS” that alleviates the problems of NS by using a more intelligent negative sampling scheme and careful penalization of the embeddings. R-NS is scalable to large-scale networks, and we empirically demonstrate the superiority of R-NS over NS for multi-label classification on a variety of real-world networks including social networks and language networks.




How to Cite

Armandpour, M., Ding, P., Huang, J., & Hu, X. (2019). Robust Negative Sampling for Network Embedding. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 3191-3198.



AAAI Technical Track: Machine Learning