Active Discriminative Network Representation Learning

1 Introduction

Network representation plays a critical role in the network analysis area [Perozzi et al., 2014; Cavallari et al., 2017], which aims to learn the embedding feature for each node, i.e., embedding the nodes into a low-dimensional feature space while preserving their neighborhood relationships. To date, network representation learning has been successfully applied to many noteworthy applications, such as node classification [Tu et al., 2016], recommendations [Gao et al., 2016; Gao et al., 2017] and link prediction [Cai et al., 2018].

Most of previous network representation models are learned in unsupervised manner, and the learned representations are often weak in particular prediction scenarios, such as node classification[Yang et al., 2016]. In reality, the network usually contains additional label information that summarizes the features of nodes. For example, documents in the citation network Citeseer are associated with field labels for the clear summarization and easy retrieval. It is worth pointing out that the label information is valuable for learning the discriminative network representations.

However, the labels of all training nodes are difficult, timeconsuming and expensive to obtain, and manually labeling all the nodes for training is inapplicable. Different sets of labeled nodes for training lead to different network representation results [Cai et al., 2017]. Thus, it is nontrivial to select nodes for labeling so as to maximize the performance of discriminative network representations. Active learning (AL) is demonstrated to be promising in solving the labeling problem [Zhu et al., 2003; Aggarwal et al., 2014; Konyushkova et al., 2017]. The idea behind AL is that better models can be learned with less effort and lower cost by selecting training data cleverly, rather than at independent and identically distributed (i.i.d.) random [Zhang et al., 2017].

Motivated by the above observations, with a given labeling budget, we aim to design a network representation learning method under the active learning principle to improve the performance by actively selecting the training labeled nodes. The objective mainly has the following challenges: 1) How to design the AL strategy based on the networking data, due to the fact that the nodes in the network are not independently and identically distributed; 2) With the given labeling budget and the strategy, how to adaptively select the informative nodes to label at each iteration; 3) The network representation learning and active learning affect each other, and how to jointly consider the both to maximize the performance.

Currently, there are few studies fully addressing the above challenges. The work [Cai et al., 2017] proposes the method AGE that utilizes three AL query strategies to select the corresponding informative nodes to label. Different criteria are combined linearly using the time-sensitive parameters that follow the same distribution for each data set. However, considering that no single combinational module is likely to satisfy the characteristics of each data set, they fail to adaptively choose the nodes based on the estimated contributions to the performance measure of interest. Thus, the learned network representations may be not promising for the classification task.

In this paper, we propose a novel method, termed as ANRMAB, to learn the Active discriminative Network Representations with a Multi-Armed Bandit mechanism in the active learning setting, as illustrated in Figure 1. ANRMAB mainly contains three parts: query strategy component, active node selection component and active discriminative network representation component. In the query strategy component, three query strategies are designed based on the networking data and the trained network representations. Specifically, considering that the nodes are not i.i.d., but are associated with link relations, the node centrality that reflects its sociological origin [Newman, 2010] is given to evaluate the node's representativeness. The information entropy and the information density, which are widely used in most AL methods, are calculated (Challenge #1).

For the active node selection component, we use the multiarmed bandit mechanism for adaptive decision making by treating each query strategy as one bandit machine and deriving an effective reward scheme that is closely related to the estimated performance measure of interest. Based on our careful design of node selection process, the most informative nodes can then be chosen to label in each iteration (Challenge #2). For the active discriminative network representation component, we use the graph convolutional network (GCN) [Kipf and Welling, 2016] as an example method to derive the discriminative network representations.

The AL query strategy is generated at the end of the discriminative network representation learning. As more informative labeled nodes are provided for model training, network representations generally become more discriminative and accurate. Meanwhile, as the information density and information entropy are derived using the better trained network representations, the query strategies yield more informative nodes that will be queried by the active node selection component (Challenge #3).

The main contributions are summarized as follows.

• We propose a novel method ANRMAB for the active discriminative network representation learning with a multi-armed bandit mechanism in the AL setting.
• We give three AL query strategies based on the networking data and the trained network representations. A multi-armed bandit algorithm is designed to adaptively select the most informative node to label. Furthermore, the three components of ANRMAB affect each other and are collaboratively learned for better discriminative network representations.
• We conduct extensive experiments on three public data sets to verify the effectiveness of ANRMAB. We also conduct the visualization using t-SNE to illustrate the discrimination of the learned network representations.

2 Preliminaries

In this section, we introduce the preliminaries and then give our problem statement. The notations used throughout the paper are summarized in Table 1. The matrices and the vectors are marked as the bold characters.

2.1 Active Learning

We consider a pool-based AL setting [Settles and Craven, 2008; Zhang et al., 2017] in this paper, where there exists a small set of labeled data L and a large pool of unlabeled data U. The idea behind is to strategically make a query to select instances from U to label, so as to maximize the performance of the classification task. The query strategy, such as uncertainty sampling, is usually used to score the candidate instances in the pool.

The key for the query strategy is to design an informative measure. Let x∗ be the most informative instance given a query strategy φ(xi;Θ), which evaluates each instance xi in U conditioned on the current set of parameters Θ. The instance selection protocol can be defined as follows

2.2 Multi-Armed Bandit Problem

The multi-armed bandit problem is a well-known adaptive learning problem [Gittins et al., 1989; Vermorel and Mohri, 2005], which simulates what a gambler would do in a casino. Given K bandit machines and a budget of T iterations, the gambler then sequentially decides which machine to pull in each iteration t (t = 1, . . . , T ). Once being pulled, the bandit machine gives a reward randomly from a machine-specific distribution unknown to the gambler [Hsu and Lin, 2015]. The goal of the gambler is to maximize his total rewards in the series of trials.

3 Problem Statement

For a network G = (V, E) along with its adjacency matrix A ∈ RN×N and node feature matrix F ∈ RN×M , the notation V denotes the nodes set, E denotes the edges set, N is the number of nodes in G and M is the dimensionality of the feature vector of each node. Considering that different sets of training labeled nodes result in different model learning results, we aim to learn the discriminative network representations R ∈ RN×D in the active learning setting, where D is the dimensionality of the node embedding space. Given labeling budget B and the number of initial labeled nodes Linit, the key point is to design the AL query strategy φ(vi;Θ) to actively select the most informative node v∗ from the unlabeled set U in each iteration. The node v∗ is then added to the labeled set L for further network representation learning, so as to maximize the performance of the classification task.

4 Our Solution: ANRMAB

In this section, we introduce our solution ANRMAB for learning the discriminative network representations with a multiarmed bandit mechanism in the AL setting. We first detail its main three parts: AL query strategy component, active node selection component and active discriminative network representation component, and then give a summarization of ANRMAB.

4.1 ALQuery Strategy

As suggested by the AL literatures [Settles, 2010; Aggarwal et al., 2014], uncertainty and representativeness are usually served as the measures. uncertainty sampling queries the nodes about which the classification model is least certain how to label. However, the nodes with greater uncertainty may not be representative of the data, and may refer to the noisy nodes or the outliers [Cai et al., 2017]. The representativeness-based strategies are often used to balance the informativeness of the node with its uncertainty properties.

In our AL query strategy component, we adopt information entropy as the uncertainty measure, node centrality and information density as the representativeness measures.

Information Entropy

Given network G, the adjacency matrix A, node feature matrix F and the labeled nodes set L, the information entropy based query strategy φIE(vi; ΘIE) for a candidate node vi in U is defined as follows

(2)

where Pic(vi; A, F, L) is the probability of the candidate node vi belonging to class c predicted by the active discriminative network representation component, which is detailed in Section 4.3, and ΘIE := {A, F,L} is the parameters set. The larger φIE(vi;ΘIE) is, the more uncertain the current model is with respect to node vi.

Node Centrality

Considering that nodes in the network are not i.i.d., but are associated with link relations, the node centrality based on the network structure is given to evaluate the node's representativeness. There have been various metrics evaluating the centrality of a node, such as degree centrality [Newman, 2010], closeness centrality [Stephenson and Zelen, 1989] and PageRank centrality [Page et al., 1999]. We adopt PageRank centrality, which has better performance for learning [Cai et al., 2017], to calculate the query strategy.

The node centrality based query strategy φNC(vi;ΘNC) for a candidate node vi in U is defined as follows

where d is the damping factor and ΘNC := {A} is the parameter set. The node with the larger node centrality is favored in the node selection process.

Information Density

With the network representations R learned by the active discriminative network representation component, we can find the representative node in the latent D-dimensional embedding space. We apply the simple Kmeans method on the embeddings of all the nodes in U to calculate the information density of each candidate node vi. The information density based query strategy φID(vi; ΘID) for a candidate node vi in U is calculated as follows

where d(·) is the distance measure, such as the Euclidean distance, in the embedding space, Rvi is the node embedding of vi, and cvi is the center of the cluster that vi belongs to. ΘID := {R} is the parameter set.

4.2 Active Node Selection

Given the labeling budget B, it is intuitive that no single strategy is likely to satisfy the needs of each data set and to find the most informative node in each iteration. Our active node selection component aims to use a multi-armed bandit mechanism to adaptively choose the most informative node by treating each AL query strategy as one bandit machine and deriving an effective reward scheme that is closely related to the estimated performance measure of interest.

Multi-Armed Bandit Method

As the learning performance generally becomes better when L becomes larger after adding the labeled node in each iteration t (t = 1, . . . ,B), it is intuitive that the rewards, which are associated with the learning performance, are not independent random variables across the iterations. Meanwhile, the contributions to the learning performance can be time-sensitive as different query strategies may select different nodes in different iterations [Donmez et al., 2007]. The above observations can satisfy the adversarial setting in the multi-armed bandit problem [Auer et al., 2002].

To adaptively choose the most informative node from the designed query strategies, we adjust the method ALBL proposed in [Hsu and Lin, 2015], which modifies the EXP4.P method [Beygelzimer et al., 2011] that is with a strong theoretical guarantee for the adversarial setting.

Let wt = (wt1 , . . . ,wtK ) be the adaptive weight vector in iteration t, where the k-th element wtk is the non-negative weight of the k-th AL query strategy. We then scale the weight vector wt to a probability vector pt = (pt1 , . . . , ptK ), where the value of the k-th element is ptk ∈ [pmin, 1] with some parameter pmin > 0. In practice, pmin is set as pmin = √ lnK KB . Our method ANRMAB chooses the AL query strategy based on the probability vector pt and obtains the corresponding reward of this action.

We introduce the query matrix Qt ∈ RK×N tu to make a probability query from U t , where N tu is the number of nodes in U t in iteration t and the element Qtkj denotes the preference of the k-th AL query strategy on querying the label of xj ∈ U t in iteration t, ∑N tu j=1 Qtkj = 1.

To sum up, given the AL query strategies, ANRMAB takes the probabilistic decision to sample the node vj from the unlabeled nodes set U t in t-th iteration based on the probability ψt j , which is defined as follows

Reward Scheme

Considering that the test accuracy, which is the targeted performance measure of interest, is usually not available because a test set is generally impossible to obtain for AL, we here adjust the importance weighting technique [Beygelzimer et al., 2009; Ganti and Gray, 2012] to define the reward scheme. Assume that the node vi is selected to query in iteration t, for the classifier f t which is learned by our active discriminative network representation component, the reward function rt (vi; f t , τ) is defined after τ iterations as follows

where ˜ W t = (ψt j )-1 , yj is the label of the node vj and f t (vj) is the predicted label of vj.

ANRMAB takes rt (vi; f t , τ) as the reward in iteration t to evaluate how much the chosen query strategy helps improving the classifier f t . Considering that different query

Algorithm 1: The proposed ANRMAB algorithm.

Input: network G, adjacency matrix A, node feature matrix F, nodes sets {L, U}, budget T = B, iteration t = 1.

Output: the final network representation RT+1 .

• 1 calculate ̂A = ˜D- 1 2 ˜A˜D- 12 , and set w1k = 1 for k = 1, . . . ,K.
• 2 calculate query strategy φtNC for t = 1, . . . , T using Eq. (3).

3 while t ≤ T do

• 4 obtain Rt and the classifier f t from method in Section 4.3.
• 5 calculate query strategies φtIE and φtID using Eqs. (2), (4).
• 6 set W t = ∑Kk=1 wtk, and for k = 1, . . . ,K, set

• 7 calculate query matrix Qt and probability ψt using Eq. (5).
• 8 sample the informative node v∗ based on ψt .
• 9 update the nodes sets Lt and U t using v∗ .
• 10 calculate the reward scheme rt (vi; f t , τ) using Eq. (6).

.

• 12 return the discriminative network representation RT+1 .

strategies may suggest the same node, we use rt (vi;f t ,τ)Qtk∗ ψt∗ to update wtk on all the query strategies that make the same suggestion for selecting the node v∗.

4.3 Active Discriminative Network Representation

Given labeled nodes set L and network G = (V, E) with its adjacency matrix A and node feature matrix F, we adopt the state-of-the-art method GCN proposed in [Kipf and Welling, 2016] to learn the discriminative network representations R. Any other semi-supervised network representation learning methods can be readily incorporated into ANRMAB.

The layer-wise propagation rule of GCN is defined as follows

where ˜A is set as ˜A = A + IN with IN being the identify matrix, ˜Dii = ∑j ˜Aij and W(l) is a layer-specific trainable weight matrix. We use ReLU(·) as the activation function σ(·). H(l) is the matrix of activations in l-th layer. H(0) is initialed as F. We can calculate ̂A = ˜D- 1 2 ˜A˜D- 12 in a preprocessing step.

The activation function in the last layer is the softmax function, defined as softmax(xi) = 1Λ exp(xi) with Λ = ∑i exp(xi), which is applied row-wise. The loss function is defined as the cross-entropy error over all labeled nodes, loss = - ∑l ∑Cc=1 YlclnZlc, where Ylc is the indicator of node vl belongs to label c and Z is the output of GCN. Take a two-layer model for node classification as an example, the model has the following formulation:

For the trained model, the matrix of activations in the l-th layer H(l) (l = 1, 2, . . . ), can be regarded as the corresponding network representations in the node embedding space. For specified l-th layer, R = H(l) .

4.4 Method Summary

The proposed method ANRMAB, illustrated in Figure 1, mainly contains three parts, i.e., AL query strategy component, active node selection component and active discriminative network representation component, which are detailed in Sections 4.1-4.3. In iteration t (t = 1, . . . ,B), the active discriminative network representation component takes network G with its adjacency matrix A and node feature matrix F as well as the updated nodes set Lt as input, and outputs the network representations Rt and the measures of node classification, based on which three AL query strategies, i.e., information entropy φtIE , node centrality φtNC and information density φtID are generated. By using the reward scheme rt (vi; f t , τ), ANRMAB takes a multi-armed bandit mechanism to adaptively query the most informative node v∗ from the unlabeled nodes set U t . v∗ is then added to Lt to form the updated training data Lt+1 , which is used for learning Rt+1 . The above process continues until the labeling budget B is reached. The pseudo-code of ANRMAB is listed in Algorithm 1.

5 Experiments

In this section, we evaluate experimental performance of the proposed method ANRMAB using node classification task on three public data sets. All the experiments are conducted on a Linux system with Intel(R) Core(TM) i7-2600 CPU @3.40GHz*8 and 10G memory.

5.1 Data Sets

We consider three public citation network data sets 1 , Citeseer, Cora and Pubmed [Sen et al., 2008], which contain sparse bag-of-words feature vector for each document and a list of citation links between documents. Each document has a class label. We treat documents as nodes and the citation links as the edges. Table 2 summarizes the statistics of the data sets.

5.2 Baseline Methods and EvaluationMetrics

We compare ANRMAB with the following baselines and its variants: 1) GCN [Kipf and Welling, 2016] is the stateof-the-art semi-supervised network representation algorithm, which is used to randomly select the node to query in AL setting; 2) AGE [Cai et al., 2017] is the active graph embedding method which combines the AL query strategies linearly using the time-sensitive parameters; 3) ANRMAB-entropy is the variant of our method that excludes the information entropy query strategy; 4) ANRMAB-centrality is the variant that excludes the node centrality strategy; 5) ANRMABdensity is the variant that excludes the information density strategy.

Two popular metrics, Macro-F1 and Micro-F1 [Perozzi et al., 2014], are adopted for performance evaluations.

5.3 Experimental Settings

For fair comparison, we follow the same experimental settings as in [Kipf and Welling, 2016; Cai et al., 2017]. For each data set, we use 1,000 labeled nodes as the testing set for evaluation. To ensure that the performance variation in the experiments is due to different AL query strategies and their selections, we randomly sample 500 labeled nodes from the non-testing nodes for validation, which is repeated for 10 times. Label rate in Table 2 represents a maximum amount of labeled nodes (denoted as Lmax) that are used for training divided by the total number of nodes in each data set. The discriminative network representation learning in all the compared methods are trained using Eq. (8) for a maximum of 600 epochs using Adam [Kingma and Ba, 2014] with a learning rate of 0.01, a hidden layer size of 32 and early stopping with a window size of 10.

1 https://linqs.soe.ucsc.edu/data

In the AL scenario, we set the labeling budget as B = Lmax - Linit for each data set, where Linit is the number of initial labeled nodes. Considering the label balance across classes, we randomly initialize 4 labeled nodes for each class. We repeat the process for 10 times and report the average results for all experiments.

5.4 Results

Figure 2 shows the Macro-F1 and Micro-F1 performance comparisons with different number of labeled nodes for training, for which each compared method queries a corresponding informative node added to the training data in each iteration. From the figures, we see that with the increasing number of labeled nodes for training, the Macro-F1 and Micro-F1 values show an overall upward trend as more label information is considered. No variant method of ANRMAB outperforms other variants across the three data sets and the span of sizes of training labeled nodes sets, which shows that no single or specific combinational module can satisfy the needs of all data sets and the informative nodes should be queried adaptively.

Considering the above observations, our method ANRMAB significantly outperforms its peers in most cases across all the data sets. Table 3 shows the Macro-F1 and Micro-F1 values averaged over all the cases, from which we see that ANRMAB obtains the best performance. For example, compared with AGE and GCN, ANRMAB improves the value of Macro-F1 by 1.87% and 7.49%, Micro-F1 by 2.53% and 6.62% that averaged over all the data sets. The above experimental results demonstrate the effectiveness of ANRMAB.

To illustrate the discrimination of the learned network representations, by tuning the parameters setting of t-SNE [Maaten and Hinton, 2008], Figure 3 gives an interesting visualization using the matrix of activations in the last layer trained by ANRMAB on Lmax labeled nodes. Though the nodes marked as red in Figure 3(a) are scattered, which account for 7.48% of nodes in Citeseer data set, the visualization results of ANRMAB for all the data sets are quite clear, with meaningful layout for each class.

6 Conclusions

In this paper, we propose a novel method ANRMAB to learn the discriminative network representations under the active learning setting to improve the performance, considering that different training labeled nodes lead to different results. We argue that no single or specific combinational module can satisfy the needs of all data distributions. By using three AL query strategies, ANRMAB incorporates a multi-armed bandit mechanism for adaptive decision making with an effective reward scheme. We conduct extensive experiments on three public data sets to demonstrate the effectiveness of ANRMAB.

Acknowledgments

We would like to thank the anonymous reviewers for their valuable comments and suggestions. This work was supported by the National Key Research and Development Program of China (No.2016YFB0801301), the NSFC (No.61502479), the MQNS Grant (No.9201701203), the MQ Enterprise Partnership Scheme Pilot Res Grant (No. 9201701455), and the Youth Innovation Promotion Association CAS (No. 2017210). J. Wu is the corresponding author.