Max-Margin DeepWalk: Discriminative Learning of Network Representation

1 1 Introduction

Network representation plays a critical role in the area of network analysis. An effective network representation is helpful to many network analysis tasks, such as vertex classification, clustering and link prediction. As a basic component in network, every vertex is typically represented as a discrete symbol, which is called one-hot representation. Due to its simplicity, such representation method has been widely adopted for network analysis. However, one-hot representation usually suffers from the sparsity issue and does not fully consider relatedness between vertices.

⇤ Indicates equal contribution

Corresponding Author: Zhiyuan Liu (liuzy@tsinghua.edu.cn)

Motivated by the ideology of distributed representation learning in recent years, network representation learning (NRL) is proposed to address these issues. NRL aims to learn a real-valued vector for each vertex to reflect its network information. The learnt vectors are capable of various network analysis tasks, such as vertex classification and link prediction. The relatedness between vertices can also be achieved on the basis of real-valued vectors.

There have been a number of NRL models proposed in recent years, such as DeepWalk [Perozzi et al., 2014] and LINE [Tang et al., 2015]. [Perozzi et al., 2014] proposed an online NRL model, DeepWalk, that learns vertex representations based on local network information. It conducts random walks to obtain vertex sequences. With a mass of sequences, DeepWalk employs Skip-Gram [Mikolov et al., 2013a], an efficient word representation learning model, to learn vertex representations by treating vertex sequences as word sentences. This straightforward analogy between words and vertices has been verified on multi-label network classification tasks.

Most of the previous NRL models are learnt in unsupervised schemas. Though the learnt representations can be applied to various tasks, they can be weak in the particular prediction task. It's worth pointing out that there are many additional labeling information for social network vertices in real world. For example, pages in Wikipedia 1 can have their categorical labels, like "arts", "history", "science"; papers in Cora and Citeseer are also stored with field labels for easy retrieval. Such labeling information usually contains a useful summarization or features of the vertices, but is not directly utilized in the original network representation learning models.

It is nontrivial to explore how to integrate labeling information into network representation learning and learn discriminative representations for network vertices. Inspired by max-margin principle, we propose max-margin DeepWalk (MMDW), a discriminative NRL model, to seek predictive representations for vertices in social networks.

As illustrated in Fig. 1, MMDW firstly learns DeepWalk as matrix factorization. Afterwards, it trains a max-margin based classifier (e.g., support vector machine [Hearst et al., 1998]) and enlarges the distance between support vectors and classification boundaries. In other words, MMDW jointly optimizes the max-margin based classifier (e.g., support vector machine) and NRL model. Influenced by max-margin classifier, the representations of vertices are therefore more discriminative and more suitable for prediction tasks, which we will demonstrate in the following sections.

In conclusion, we make several noteworthy contributions as follows:

(1) We propose a discriminative NRL model, max-margin DeepWalk, to incorporate labeling information into vertex representations. As a semi-supervised model, it applies maxmargin principle to network representation learning for the first time.

(2) We put forward the idea of Biased Gradient in NRL. The biased gradient of a vector indicates the direction where the vector should move towards. The movement is able to enlarge the margin between two categories, and is conducted in the gradient form in gradient descent algorithms.

(3) We conduct vertex classification experiments on several real-world datasets to verify the effectiveness of MMDW. The experimental results demonstrate that MMDW significantly outperforms traditional NRL models. It achieves 5% to 10% improvements compared to typical NRL methods. Besides, we also compare the visualizations using t-SNE to illustrate the discrimination of MMDW.

2 2 RelatedWork

Network representation learning (NRL) aims to encode network structure into a low-dimensional space. The learnt representations can be adopted to many network analysis tasks, such as vertex classification, clustering and link prediction.

Many NRL models have been proposed to learn efficient vertex representations. Inspired by Skip-Gram [Mikolov et al., 2013a], a widely adopted word representation learning model in NLP, [Perozzi et al., 2014] proposed DeepWalk by corresponding vertices to words. DeepWalk performs random walks to generate vertex sequences and trains SkipGram model to obtain vertex representations. Derived from Skip-Gram, DeepWalk has been extensively verified on various network analysis tasks. Another typical NRL model is LINE [Tang et al., 2015], which is proposed to handle largescale networks with millions of vertices and billions of edges.

1 https://en.wikipedia.org

There have been some max-margin based learning methods in other fields. [Roller, 2004] firstly introduced max-margin principle into markov networks. [Zhu et al., 2012] proposed maximum entropy discrimination LDA (MedLDA) to learn a discriminative topic model (e.g., latent Dirichlet allocation [Blei et al., 2003]). Besides, max-margin also benefits many NLP tasks, such as semantic parsing [Taskar et al., 2004] and word segmentation [Pei et al., 2014].

However, to the best of our knowledge, there is little work learning discriminative network representations with labeling information considered. Most of the mentioned NRL methods are learnt in unsupervised fashions. To fill this gap, we propose max-margin DeepWalk (MMDW) to learn discriminative representations for vertices in social networks.

3 3 The Framework

In this section, we present a novel semi-supervised social representation model, max-margin DeepWalk (MMDW), that utilizes the labeling information when learning vertex representations. MMDW is a unified learning framework based on matrix factorization. In this model, we optimize the maxmargin based classifier (SVM) as well as the aimed matrix factorization model. In contrast, the conventional approaches usually learn social representations without leveraging the labeling information and apply the learnt representations into classification tasks. The vertices' labels are not able to influence the way representations are learnt. Therefore, the learnt representations are often found not so discriminative.

3.1 3.1 Formalizations

Let us begin with formally defining the problem of social representation learning. Suppose there is a social network G = (V↪E), where V is the set of all vertices, and E are connections between these vertices, i.e., E ⇢ V ⇥ V , social representation learning aims to build a low-dimensional representation xv 2 Rk for each vertex v 2 V , where k is the the dimension of representation space and expected much smaller than ♣V ♣ . The learnt representations encode semantic roles of vertices in the social network, which can be used to measure relatedness between vertices, and can also play as features for classification tasks. With the corresponding label l 2 ¶1↪ · · · ↪m♦, classifiers like logistic regression and SVM can be trained.

In the following parts, we introduce a typical social representation model, DeepWalk, and its matrix factorization form. Afterwards, we give detailed introduction to maxmargin DeepWalk.

3.2 3.2 DeepWalk as Matrix Factorization

DeepWalk [Perozzi et al., 2014] performs random walks over a network to build vertex sequences. By regarding vertex sequences as word sequences, it adopts Skip-Gram [Mikolov et al., 2013b], a widely-used word representation algorithm, to learn network representations. The performance of DeepWalk has been extensively verified on multiple tasks and datasets.

Motivated by Skip-Gram, DeepWalk aims to maximize the co-occurrence probability between a target vertex and its context vertices within a random-walk window. Formally, suppose we have a random walk sequence s = ¶v1↪ ▷ ▷ ▷ ↪ vM♦ with each vi 2 V . We set a window size K, and for each target vertex vi, we define its context vertices ci = (vi-K↪ ▷ ▷ ▷ ↪ vi+K) ∩ vi. Thus, the objective of DeepWalk can be formalized as follows,

Here, S is the set of random walk sequences generated from random walks. The probability Pr(vj♣vi) is computed using softmax function,

[Yang et al., 2015] proved that DeepWalk actually factorizes a matrix M. Each entry in M is formalized as

where xj and xi are the representation vectors of the vertices vj and vi, and (·) is the inner product between vectors.

Here, A is the transition matrix, which can be seen as the row normalized adjacency matrix. ei denotes an indicator vector, in which the i-th entry is 1 and the others are all 0. The entry vij is logarithm of the average probability that vertex i walks to vertex j in t steps.

From Eq. 3, we find that computing an precise M is timeconsuming. Thus, we employ the settings in [Yang et al., 2015], by factorizing the matrix as M = (A + A2 )◁2. In practice, we factorize M instead of logM, since logM has much more non-zero entries than M and the complexity of matrix factorization is proportional to the number of non-zero entries [Yu et al., 2014].

Now, we formalize the DeepWalk using matrix factorization M = XT Y . We aim to find matrices X 2 Rk⇥♣V ♣ and Y 2 Rk⇥♣V ♣ to minimize

where the factor λ controls the weight of regularization part.

3.3 3.3 Max-Margin DeepWalk

Max-margin methods, such as support vector machines (SVMs) [Hearst et al., 1998], are usually applied to various discriminative problems including document categorization and handwritten character recognition.

In this work, we take the learnt representations X as features and train an SVM for vertex classification. Suppose the training set is T = ¶(x1↪ l1)↪ · · · ↪ (xT ↪ lT )♦, the multi-class SVM aims to find optimal linear functions by solving the following constrained optimization problem:

where

Here, W = [w1↪ · · · ↪wm]T is the weight matrix of SVM, and ⇠ = [⇠1↪ · · · ↪ ⇠T ] is the slack variable that tolerates errors in the training set.

As mentioned in previous parts, such pipeline method can not influence the way vertex representations are learnt. With learnt representations, SVM only helps to find optimal classifying boundaries. As a result, the representations themselves are not discriminative.

Inspired by max-margin learning on topic model [Zhu et al., 2012], we present max-margin DeepWalk (MMDW) to learn discriminative representations of vertices in social networks. MMDW aims to optimize the max-margin classifier of SVM as well as matrix factorization based DeepWalk. The objective is defined as follows:

4 4 Optimization of MMDW

The parameters in the objective 7 include vertex representation matrix X, context representation matrix Y , weight matrix W and slack variable vector ⇠. We employ an effective optimization strategy by optimizing the two parts separately. With the introduction of Biased Gradient, the matrix factorization is significantly affected by trained max-margin classifier.

We perform our optimization algorithm as follows.

4.1 4.1 Optimization over W and ⇠:

When X and Y are fixed, the primal problem 7 becomes the same as a standard multi-class SVM problem proposed by Crammer and Singer (2000), which has the following dual form:

where

and

Here, the lagrangian multiplier ↵j i is replaced by C j li - zj i for short.

To solve this dual problem, we utilize a coordinate descent method to decompose Z into blocks [z1↪ · · · ↪ zT ], where

An efficient sequential dual method [Keerthi et al., 2008] is applied to solve the sub-problem formed by zi.

4.2 Optimization over X and Y :

When W and ⇠ are fixed, the primal problem 7 turns into minimizing the square loss of matrix factorization with additional boundary constraints as follows:

Without the consideration of constraints, we have

8i 2 T ↪ j 2 1↪ · · · ↪m, if li 6= j and ↵j i 6= 0, according to KKT conditions, we have

When the decision boundary is fixed, we want to bias such support vector xi towards the direction that favors a more accurate prediction. Thus the biased vector can enlarge the discrimination.

Here we explain how the bias is calculated. Given a vertex i 2 T , for the j-th constraint, we add a component ↵j i (wli - wj)T to xi, then the constraint becomes

Note that, we utilize the lagrangian multiplier ↵j i to judge whether the vector is on the decision boundary. Only xi with ↵j i 6= 0 is added a bias based on the j-th constraint.

For a vertex i 2 T , the gradient becomes @L @xi + ⌘ Pmj=1 ↵j i (wli - wj)T , which is named Biased Gradient. Here, ⌘ balances the primal gradient and the bias.

Before X is updated, W and ⇠ satisfy the KKT conditions of SVM, and this solution is initially optimal. But after updating X, the KKT conditions do not hold. This will lead to a slight increase of the objective, but this increase is usually within an acceptable range according to our experiments.

5 5 Experiments

In this section, we conduct vertex classification in social networks to evaluate our proposed model. Besides, we also visualize the learnt representations to verify that MMDW is able to learn discriminative representations.

5.1 5.1 Datasets and Experiment Settings

We employ the following three typical datasets for vertex classification.

Cora. Cora 2 is a research paper set constructed by [McCallum et al., 2000]. It contains 2↪ 708 machine learning papers which are categorized into 7 classes. The citation relationships between them form a typical social network.

Citeseer. Citeseer is another research paper set constructed by [McCallum et al., 2000]. It contains 3↪ 312 publications and 4↪ 732 connections between them. These papers are from 6 classes.

Wiki. Wiki [Sen et al., 2008] contains 2↪ 405 web pages from 19 categories and 17↪ 981 links between them. It's much denser than Cora and Citeseer.

For evaluation, we randomly sample a portion of labeled vertices and take their representations as features for training, and the rest are used for testing. We increase the training ratio from 10% to 90%, and employ multi-class SVM [Crammer and Singer, 2002] to build classifiers.

5.2 5.2 Baseline Methods

DeepWalk. DeepWalk [Perozzi et al., 2014] is a typical NRL model that learns vertex representations based on network structures. We set parameters in DeepWalk as follows, window size K = 5, walks per vertex γ = 80 and representation dimension k = 200. For a vertex v, we take the representation v as network feature vector.

DeepWalk as Matrix Factorization. In previous part, we have introduced that DeepWalk can be trained in a matrix factorization form. Thus we factorize the matrix M = (A + A2 )◁2 and take the factorized matrix X as representations of vertices.

2nd-LINE. LINE [Tang et al., 2015] is another NRL model that learns network representations in large-scale networks. We employ the second-order proximity LINE (2nd-LINE) to learn representations for directed networks. Same as DeepWalk, we also set the representation length as 200.

5.3 5.3 Experimental Results and Analysis

Table 1, Table 2 and Table 3 show classification accuracies with different training ratios on different datasets. In these tables, we denote DeepWalk as DW , matrix factorization form of DeepWalk as MFDW and 2nd-LINE as LINE for short. We also show the performance of MMDW with ⌘ ranging from 10-4 to 10-2 . From these tables, we have the following observations:

(1) The proposed max-margin DeepWalk consistently and significantly outperforms all the baselines on all different datasets and different training ratios. Note that, MMDW achieves nearly 10% improvement on Citerseer and 5% improvement on Wiki when the training ratio is around 50%.

2 https://people.cs.umass.edu/ mccallum/data.html

DeepWalk can not represent vertices in Citeseer and Wiki well, while MMDW is capable of managing such situation. These improvements demonstrate that MMDW is more robust and especially performs better when the quality of network representations is poor.

(2) What calls for special attention is that MMDW outperforms the original DeepWalk with half less training data on Citeseer and Wiki. It demonstrates that MMDW is effective when applied to predictive tasks.

(3) The proposed MMDW obtains considerable improvements than primal social representation learning methods. In contrast, the performance of original DeepWalk and DeepWalk as matrix factorization is unstable on various datasets. This indicates that the introduction of supervised information is important and MMDW is flexible to diversified networks.

Observations above demonstrate that MMDW is able to incorporate labeling information for generating high quality representations. MMDW is not application-specific. The learnt representations of vertices can be utilized in many tasks, including vertex similarity, link prediction, classification and so on. The idea of biased gradient can be easily extended to other matrix factorization methods.

5.4 5.4 Convergence and Parameter Sensitivity

MMDW optimizes the max-margin classifier and matrix factorization alternately. In the top part of Fig. 2, we show the convergence trend of accuracies when model is trained with different training ratios. We observe that our proposed MMDW always achieves the best performance after 2 or 3 iterations. The performance of MMDW rises rapidly at the beginning, then becomes stable. The fast convergence rate indicates the efficiency of training MMDW.

As the primal gradient and the bias are calculated through different ways, they are initially under different orders of magnitude. Thus, we introduce a hyper-parameter ⌘ to balance the biased gradient and original gradient. We fix training ratio to 50% and test the performance of MMDW with different ⌘.

From the bottom part of Fig. 2, we observe that MMDW

has a stable performance when ⌘ ranges from 10-5 to 10-2 and gains the best performance when ⌘ = 10-2 . A fixed parameter ⌘ is suitable for different datasets.

5.5 5.5 Visualization

In this paper, we propose max-margin DeepWalk to learn discriminative representations for social networks. To verify whether the learnt representations is discriminative, we show the 2D representations of vertices using t-SNE visualization tool in Fig. 3. In this figure, each dot represents a vertex and each color represents a category. We randomly select 4 categories to show the trend more clearly.

From Fig. 3, we observe that MMDW learns a better clustering and separation of the vertices. On the contrary, the representations learnt by DeepWalk tend to mix together. A well-separated representation is more discriminative and easier to categorize. These significant improvements prove the effectiveness of our discriminative learning model.

5.6 5.6 Case Study

To demonstrate the effectiveness of MMDW, we provide an instance in Cora dataset for example. The title of this instance is "Fast Online Q(λ)", and it belongs to the category of "Reinforcement Learning". As shown in Table 4, we list Top5 nearest neighbors with the representations learnt by DeepWalk and MMDW. Here, we employ the cosine similarity to measure the distance between vertices.

From Table 4, we observe that only 2 neighbors found by DeepWalk belong to the same category as the instance does, while MMDW finds 5. From the title of the instance, we can get that it is relevant to "online learning" and "Q problem". Most of the neighbors found by DeepWalk have no relatedness with these topics, while, most of the neighbors found by MMDW are closely related to them. It indicates that MMDW improves the quality of representations with the consideration of labeling information.

6 6 Conclusion and FutureWork

In this paper, we propose max-margin DeepWalk (MMDW), a discriminative representation learning model for social networks. With the introduction of labeling information and max-margin principle, MMDW learns vertex representations which reflect both their network structure and labeling information. Experimental results on real-world datasets show that MMDW is effective for predictive tasks. Moreover, visualizations of the learnt representations confirm the discrimination of MMDW.

We will explore more in future work as follows:

• ÷ We have proved the effectiveness of max-margin DeepWalk. In the future, we aim to explore how to conduct maxmargin methods on other social representation learning models, such as LINE.
• ÷ We learn a discriminative DeepWalk by transforming the orignal DeepWalk into matrix factorization form. In this way, it's easier to balance the bias vector and the gradient. Nevertheless, it's an offline method. In the future, we strive to explore the online discriminative learning methods.

7 Acknowledgements

This work is supported by the 973 Program (No. 2014CB340501), the Major Project of the National Social Science Foundation of China (13&ZD190) and the Singapore National Research Foundation under its International Research Centre @ Singapore Funding Initiative and administered by the IDM Programme Office.