Discriminative Deep Random Walk for Network Classification

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1004–1013, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Discriminative Deep Random Walk for Network Classification Juzheng Li, Jun Zhu, Bo Zhang Dept. of Comp. Sci. & Tech., State Key Lab of Intell. Tech. & Sys. Tsinghua University, Beijing, 100084, China lijuzheng09@gmail.com; {dcszj,dcszb}@tsinghua.edu.cn Abstract Deep Random Walk (DeepWalk) can learn a latent space representation for describ- ing the topological structure of a network. However, for relational network classifi- cation, DeepWalk can be suboptimal as it lacks a mechanism to optimize the ob- jective of the target task. In this paper, we present Discriminative Deep Random Walk (DDRW), a novel method for re- lational network classification. By solv- ing a joint optimization problem, DDRW can learn the latent space representations that well capture the topological struc- ture and meanwhile are discriminative for the network classification task. Our ex- perimental results on several real social networks demonstrate that DDRW signif- icantly outperforms DeepWalk on multi- label network classification tasks, while retaining the topological structure in the latent space. DDRW is stable and con- sistently outperforms the baseline meth- ods by various percentages of labeled data. DDRW is also an online method that is scalable and can be naturally parallelized. 1 Introduction Categorization is an important task in natural lan- guage processing, especially with the growing scale of documents in the Internet. As the doc- uments are often not isolated, a large amount of the linguistic materials present a network structure such as citation, hyperlink and social networks. The large size of networks calls for scalable ma- chine learning methods to analyze such data. Re- cent efforts have been made in developing statis- tical models for various network analysis tasks, such as network classification (Neville and Jensen, 2000), content recommendation (Fouss et al., 2007), link prediction (Adamic and Adar, 2003), and anomaly detection (Savage et al., 2014). One common challenge of statistical network models is to deal with the sparsity of networks, which may prevent a model from generalizing well. One effective strategy to deal with network sparsity is to learn a latent space representation for the entities in a network (Hoff et al., 2002; Zhu, 2012; Tang and Liu, 2011; Tang et al., 2015). Among various approaches, DeepWalk (Perozzi et al., 2014) is a recent method that embeds all the entities into a continuous vector space using deep learning methods. DeepWalk captures entity fea- tures like neighborhood similarity and represents them by Euclidean distances (See Figure 1(b)). Furthermore, since entities that have closer rela- tionships are more likely to share the same hobbies or belong to the same groups, such an embedding by DeepWalk can be useful for network classifica- tion, where the topological information is explored to encourage a globally consistent labeling. Although DeepWalk is effective on learning embeddings of the topological structure, when dealing with a network classification task, it lacks a mechanism to optimize the objective of the tar- get task and thus often …

Content truncated to 500 words