Semi-supervised Learning over Heterogeneous Information Networks by Ensemble of Meta-graph Guided Random Walks

1 Introduction

Semi-supervised learning, a machine learning paradigm that learns from partially labeled data, has been well studied in machine learning community [Chapelle et al., 2006]. One of the mainstream semi-supervised learning approaches is the so-called graph based semi-supervised learning [Zhu et al., 2003; Zhou et al., 2003]. Graph based semi-supervised learning views the data as a graph, e.g., manually constructed k-nearest-neighbor graph built on data similarities. Then it performs label propagation over the graph, which is regarded as a random walk with the labeled data being viewed as the "absorbing boundary" [Zhu et al., 2003]. Zhou et al. (2003) further relaxed the random walk framework to be constrained learning by graph regularization. This framework corresponds to a generalized lazy random walk over the labeled graph [Zhou and Sch¨olkopf, 2004], where the random walk considers an additional probability to stay at the current position.

In the real world, however, there are many kinds of data that can be naturally represented as heterogeneous information networks (HINs) [Sun and Han, 2012] rather than the homogeneous graph used by graph based semi-supervised learning. The difference between heterogeneous information networks and homogeneous networks is that the nodes and edges can be classified into different types. For example, social networks with users, tags, URLs, locations, etc., can be considered as an HIN [Kong et al., 2013]. The scholar network, containing papers, authors, venues, keywords, is an HIN [Sun et al., 2011]. The patient network, incorporated with gene network, drug network, and disease network, is also an HIN [Denny, 2012]. Moreover, the knowledge graphs, such as Freebase and Google Knowledge Vault, are naturally HINs since all the entities and relations are typed with categories. When there are not enough annotations for certain types of nodes, semi-supervised learning can be considered. For example, we want to predict the users' genders in social network, classify the papers in scholar network into topics, group patients with potential diseases, and classify new entities based on the existing knowledge on knowledge graphs. Different classification problems still need a lot of labeling efforts. Thus, developing a semi-supervised learning algorithm over HINs can benefit a lot of real problems.

Semi-supervised learning over heterogeneous information network has a significant difference from original graph based semi-supervised learning, since the nodes and edges are with types. The labels propagating through different paths may have different effects. For example, if we consider a knowledge graph network with entity types actor, director, movie, musician, singer, and song, when we want to classify a specific entity, e.g., Leonardo DiCaprio, the labels that are propagated from other actors through actors and directors are more useful than the actor labels propagated through singers and songs. Thus, if we can have a strategy to guide the random walk over the heterogeneous information network, we can more effectively propagate the limited labels.

In this paper, we propose a meta-graph guided lazy random walk algorithm to guide the label propagation path with certain entity types. The meta-graph is an entity type network that characterizes the relationships between types, e.g., actor actIn ---→movie, director direct ---→movie, and singer sing --→song, etc. When we constrain entity types of random walk, the random walk path follows two graphs: meta-graph and the original entity graph. We can enumerate a lot of meta-graphs based on the existing types of an HIN. Then after performing random walk guided by different meta-graphs, we ensemble the classification results using a supervised classifier, a maximum likelihood estimation of true labels given a lot of noisy labels [Dawid and Skene, 1979; Sheng et al., 2008], as well as a co-training mechanism to jointly optimize the labels and the ensemble weights [Wan et al., 2015]. We use knowledge graph (Freebase) enriched documents in 20newsgroups and RCV1 datasets to demonstrate the effectiveness of semi-supervised learning over HIN, although other kinds of HINs should also be applicable. Extensive experiments show that by using HIN representation of documents, we can improve semi-supervised learning in a significant way. The code has been released at https://github.com/ HKUST-KnowComp/semihin.

2 RelatedWork

In this section, we introduce the related work on semisupervised learning on graphs or networks.

As we have described in the introduction, graph based semi-supervised learning has been well studied [Zhu et al., 2003; Zhou et al., 2003; Chapelle et al., 2006]. In the context of graph link analysis in computer science community, the history of the research can be traced back to Pagerank [Page et al., 1999] and HITS [Kleinberg, 1998] algorithms. When there are some annotation or preference on the nodes, personalized Pagerank can be used [Jeh and Widom, 2003; Haveliwala, 2003]. The formulation of personalized Pagerank is the same as Zhou's semi-supervised learning [Zhu et al., 2003] although the meanings of the label/preference vectors are different. All the above algorithms assume that the graph has homogeneous type of nodes. The first work introduced heterogeneous information in random walk is used for recommendation problem [Brand, 2005], where the random walk is performed over a user-item bipartite graph.

For the recent development of HIN, there have been some attempts that use semi-supervised or side information to get better results for different tasks on HIN. For example, the entity similarities can be guided with partially labeled pairwise constraints [Sun et al., 2012]. When documents can be represented as HINs using external knowledge graphs, pairwise constraints can also be used to guide document clustering [Wang et al., 2015a]. Moreover, for a scholar network, transductive classification of entities on HIN has been developed [Ji et al., 2010]. This algorithm discards the higher oder relationships but only uses the pairwise typed relations in the HIN. Recent study further extends this work by improving the weights on the network [Bangcharoensap et al., 2016]. To avoid the single relation paths, topology shrinking sub-network algorithm [Wan et al., 2015; Li et al., 2016] is proposed to use meta-paths to first compute the similarities between the same type of nodes using a symmetric meta-path, and then it uses a linear combination of graph Laplacians computed from each similarity matrix as a whole to perform semi-supervised learning. Before performing semi-supervised learning, these methods need to compute the commuting matrices based on each meta-path, which is more costly than our approach. Moreover, there has been no existing work that attempts to use random walk over the original HIN for semi-supervised learning. The previously developed random walk process guided by metapath [Lao and Cohen, 2010], however, can be a non-stationary process for some mata-paths for semi-supervised learning to converge.

Another line of research, which may not be called "semisupervised learning over graph" but may be related is called collective classification [London and Getoor, 2014]. Collective classification uses the labeled nodes in the graph to predict unlabeled nodes. Different from pure random walk, collective classification assumes that the nodes can have features, e.g., the attributes of nodes, profiles of social users, etc. In the context of HIN, there has been some existing work using meta-paths to generate features for collective classification [Kong et al., 2013].

3 Ensemble of Meta-graph Guided Random Walk Framework

In this section, we introduce the detailed algorithm of semisupervised learning over HIN based on meta-graph guided random walk. We first analyze of lazy random walk over graph, and then show the key problems with meta-path and meta-graph guided random walk. Then we introduce different ensemble algorithms for multiple random walks.

3.1 Lazy RandomWalk over Graph

Given a set of n nodes and corresponding edges, we can construct an adjacency matrix W ∈ Rn×n . Then a lazy random walk over this graph considers a transition probability matrix:

where D is the degree matrix with diagonal values Dii = ∑j Wij, and α ∈ (0, 1) is a parameter controlling the probability of staying at the current position with probability 1 - α and moving to a random neighbor proportional to the weights on edge with probability α. There is an existing unique stationary distribution π ∈ Rn×1 satisfying

We denote Ti,j = min{t ≥ 0|Vt = vj, V0 = vi, vi ̸= vj} as the first hitting time to node vj starting from vi, and denote Ti,i = min{t > 0|Vt = vi, V0 = vi} as the first returning time to vj starting from vi. The expectation of Ti,j is the commonly used hitting time, which we denote as Hij . Then the commuting time between vi and vj is defined as Cij =

Hij +Hji. Let G = (D- αW)† be the pseudo-inverse of D-αW, then we have [Ham et al., 2004]:

This relation is similar to the inner product similarity (G) and norm distance (C) in Euclidean space [Zhou and Sch¨olkopf, 2004]. The longer the distance between vi and vj (larger Cij commuting time), the smaller the similarity between vi and vj .

When there are labeled nodes in the graph, we perform random walk starting from the labeled data. To formulate the process, we denote a label vector for each class k as lk ∈ Rn×1 , where the labeled nodes are denoted as 1 while the other nodes as 0. Then the lazy random walk can be done by iteratively computing [Zhou et al., 2003]:

where f t+1 k is the learned label vector for class k at time t + 1. Note that this equation also often refers to personalized Pagerank when lk characterizes nodes' preferences using some real values [Jeh and Widom, 2003].

The optimal value for fk is:

which corresponds to

where ¯Gij = Gij/√CiiCjj [Zhou and Sch¨olkopf, 2004]. This means that the estimated label fk(vi) of vi is the sum of ¯Gij starting from labeled nodes. If vi and vj are more "similar" ( ¯Gij is greater), then the contribution of vj as labeled data is greater for unlabeled data vi. Then the assigned label by lazy random walk for unlabeled data is to choose the maximum fk(vj) from all k = 1, . . . , K classes for vj .

3.2 Meta-path vs. Meta-graph Guidance

In this section, we discuss the difference between meta-path and meta-graph based random walk. Before going into the details, we briefly introduce the core concepts of heterogeneous information network [Sun et al., 2011].

Definition 1 A heterogeneous information network (HIN) is a graph G = (V, E) with an entity type mapping φ: V → A and a relation type mapping ψ: E → R, where V denotes the entity set and E denotes the link set, A denotes the entity type set, and R denotes the relation type set.

We can further use network schema to give a more abstractive description of the HIN.

Definition 2 Given an HIN G = (V, E) with the entity type mapping φ: V → A and the relation type mapping ψ: E → R, the network schema for network G, denoted as TG = (A,R), is a graph with nodes as entity types from A and edges as relation types fromR.

One of the important concepts developed for HIN is the meta-path, the path defined over the entity types on the network schema [Sun et al., 2011; Lao and Cohen, 2010].

Definition 3 A meta-path P is a path defined on the graph of network schema TG = (A,R), and is denoted in the form of A1 R1 --→ A2 R2 --→ . . . RL --→AL+1 , which defines a composite relation R = R1 · R2 · . . . · RL between types A1 and AL+1, where · denotes relation composition operator, and L

is the length of P. A commuting matrix MP for a metapath P = (A1 -A2 - . . . -AL+1 ) is defined as MP = WA1A2WA2A3 . . .WALAL+1 , where WAiAj is the adjacency matrix between types Ai and Aj . MP(i, j) represents the number of path instances between objects xi and yj, where φ(xi) = A1 and φ(yj) = AL+1, under meta-path P.

The difference between PathSim [Sun et al., 2011] and path ranking algorithm (PRA) [Lao and Cohen, 2010] is PathSim normalizes the overall commuting matrix while PRA normalizes separate WAiAj 's.

Besides the meta-path, people have also found that metagraph (or meta-structure) is very useful when defining the similarities between entities [Fang et al., 2016; Huang et al., 2016].

Definition 4 A meta-graph Ts = (As, Rs) is a sub-graph of network schema TG = (A, R), where As ⊆ A and Rs ⊆ R. We also denote the meta-graph derived subgraph of original HIN as Gs = (Vs, Es), where Vs ⊆ V and Es ⊆ E. The entities on the subgraph of HIN also follow the mapping φ: Vs → As and a relation type mapping ψ: Es → Rs.

Now we show an example to illustrate why we work over meta-graphs rather than over meta-paths. Suppose we have an HIN with three entity types: A1, A2, and A3. For example, we can think about actor, director, and movie with relations marriage, actIn, actIn-1 , direct and direct-1 . One meta-path generated from the HIN is shown in the left in Figure 1(a). Suppose we have two labeled entities in type A1. Then two typical paths of random walk starting from the labeled entities following the meta-path are shown in the middle in Figure 1(a). Note that a path of random walk following a meta-path should be constrained by the types in the meta-path [Lao and Cohen, 2010]. For example, the path v1 → v2 → v3 → v4 → v5 should follow φ(v1) = A1, φ(v2) = A2, φ(v3) = A3, φ(v4) = A2, and φ(v5) = A1. Given this desired random walk, we try to formulate the transition matrix. From the right of Figure 1(a) that for A1 → A2 → A3 → A2, we can easily fill in the submatrices based on WA1,A2 , WA2,A3 , WA3,A2 . However, for the final random walk A2 → A1 if we fill in withWA2,A1 and normalize the whole as probability distribution, then when we do random walk for A2 → A3, there is also a probability to walk to entities with type A1, which cannot strictly follow the meta-path. Thus, in this case, we need to either augment the meta-path to have an edge A2 → A1 in parallel to A1 → A2, or introduce another order of Markov chain to handle the type switching. For the former case, the meta-path is no longer a path, but rather a graph. For the latter case, a higher order random walk should be carefully designed depending on different meta-paths, where the storage of the stationary distribution should be handled carefully, e.g., by a non-Markovian randomwalk [Benson et al., 2016].

To avoid the above problem with meta-path guided random walk, we propose to use meta-graph to guide the random walk. In the left of Figure 1(b), we show the meta-graph of fully connected bi-directional graph with nodes A1, A2, and A3. Then in the middle of Figure 1(b), we show two typical random walk paths based on the constraints of meta-graph.

(b) Meta-graph based random walk.

Figure 1: Comparison of meta-path based and meta-graph based random walks.

Finally in the right of Figure 1(b), we show the transition matrix of this random walk, which is consistent over time.

3.3 Ensemble

For a network schema, we can enumerate exponential number of meta-graphs. Thus, we should seek a better way to obtain sufficiently informative meta-graphs for us to use. One simple way is to first enumerate all the paths with certain lengths in the network schema. Then we automatically complete the meta-graph based on the selected meta-paths by checking the original network schema. Afterwards we have a set of meta-graphs that we can use for constraining the random walk. Here, we formally introduce the concept of meta-graph guided rand walk over HIN.

Definition 5 A meta-graph guided random walk over HIN first obtains a set of meta-graphs Ts1 , . . . TsG constructed from network schema TG = (A,R). Then we construct the corresponding adjacency matricesW(s1) , . . . ,W(sG) for the meta-graph derived subgraphs. For eachW(si) and for each class k, we run random walk for the estimated labels f (si) k t+1 in iteration t:

where D(si) is the degree matrix with diagonal values D(si) ii = ∑j W(si) ij , and α ∈ (0, 1) is a parameter controlling the probability of staying at the current position with probability 1 - α and moving to a random neighbor proportional to the weights on edge with probability α.

By running meta-graph guided random walk, we choose labels for the data by combining different estimated labels:

where f (si) k (vj) is the label of vj generated by meta-graph si indicating whether it belongs to class k.

Given we have multiple label assignments from different random walks, we propose to use three meta-algorithms to find the final solution:

• SVM. Simply by exploiting the output scores of the meta-graph guided random walk, we use the labeled data to learn the linear combination of output scores. Given SG meta-graphs and K classes, we learn a Kclass Support Vector Machine (SVM) with SG × K dimensional features.
• EM. We use the soft voting algorithm [Dawid and Skene, 1979] which can estimate the quality of each label vector ˆl(si) (which is done by selecting the maximum value of ˆl(si) (vj) = argmaxk f (si) k (vj) from all k = 1, . . . ,K classes for vj) to vote for the final label assignment for all the nodes we are interested in. Note that this voting algorithm has been improved in [Sheng et al., 2008] for crowdsourcing with noisy labels, and in [Ipeirotis et al., 2010] it shows that it can also incorporate partially labeled data.
• Co-training. Because each meta-graph carries different semantic information, each meta-graph is capable for classifying some samples and yields random results on other samples. Thus we use a co-training-like algorithm, to iteratively assign the soft labels for each meta-graph and the weight of the meta-graph for voting, which can propagate high confidence labels based on some metagraphs to others. Our implementation is based on [Wan et al., 2015].

4 Experiments

In this section, we present the results to show effectiveness and efficiency of our approach.

4.1 Datasets

We use two datasets to evaluate different algorithms.

20Newsgroups (20NG): The 20newsgroups dataset [Lang, 1995] contains about 20,000 newsgroups documents evenly distributed across 20 newsgroups. 1

RCV1: The RCV1 dataset is a dataset containing manually labeled newswire stories from Reuter Ltd [Lewis et al., 2004]. The news documents are categorized with respect to three controlled vocabularies: industries, topics and regions. There are 103 categories including all nodes except for root in the topic hierarchy. We select top category GCAT (Government/Social) to perform classification. In total, we have 60,608 documents with 16 leaf categories.

For both datasets, we obtained the semantic parsing results based on [Wang et al., 2015a] which are now publicly available 2 . We follow [Wang et al., 2016] to use four subsets of these to datasets to test our algorithms, which are 20NG-SIM (comp.graphics, comp.sys.mac.hardware, and comp.os.ms-windows.misc), 20NG-DIF (rec.autos, comp.os.mswindows.misc, and sci.space), GCATSIM (GWEA (Weather), GDIS (Disasters), and GENV (Environment and Natural World)), and GCAT-DIF (GENT (Arts, Culture, and Entertainment), GODD (Human Interest), and GDEF (Defense)). The statistics of the four dataset are summarized in Table 1. After meta-path selection [Wang et al., 2015b] and further pruning low-frequency entities, we use nine augmented meta-graphs for 20NG datasets and eight meta-graphs for GCAT datasets based on the meta-paths.

4.2 Baseline Methods

We test the performance of our semi-supervised classification algorithm with different groups of baseline methods.

First, we test different types of features for text classification. Our algorithm is general for HINs. However, here we use knowledge augmented graph as HIN for text classification. Thus, a natural baseline for us is to see whether the knowledge we add in should be represented as HIN instead of other features. Here we compare two types of features for traditional machine learning algorithms:

BOW: Traditional bag-of-words model with term frequency weighting mechanism.

BOW+Entity: BOW augmented with additional features from entities in grounded knowledge from Freebase. This setting incorporates knowledge as flat features.

1 http://qwone.com/˜jason/20Newsgroups/

2 https://github.com/cgraywang/TextHINData

Second, we test different graph based semi-supervised learning mechanisms:

LP: We use LP to denote the traditional graph based label propagation algorithm operated based on similarity graph constructed by data dependent features [Zhou et al., 2003]. We empirically select 10-nearest-neighbors for all the experiments.

LP-Meta-path: We implemented a simplified version of the state-of-the-art meta-path based semi-supervised learning algorithm [Wan et al., 2015]. It uses meta-paths to first compute PathSims [Sun et al., 2011] and the corresponding Laplacians. Then it jointly learns the propagated labels and the weights for different meta-paths to propagate the labels.

LP-KnowSim: We also implemented a simplified version of KnowSim [Wang et al., 2015b], an unsupervised meta-path weighting based similarity, for the meta-paths we used to generate the similarities between documents and then construct the 10-nearest-neighbor based graph for label propagation.

SemiHIN-DWD: This is the simple bipartite graph version of our algorithm, which only considers the document-word relationships. In this case, our algorithm reduces to semisupervised learning on bipartite graphs.

SemiHIN-Full-Graph: We also compare our algorithm with random walk over the full parsed graph. In our ensemble, we also incorporate this full graph.

SemiHIN-Ensemble: As shown in Section 3.3, we proposed three ways of ensemble of different predictions. Here, to simplify notations, we denote them as Ensemble-SVM, Ensemble-EM, and Ensemble-Co-train.

All the semi-supervised learning is performed with the same fixed controlling parameter α = 0.98 shown in Eq. (4). To make sure having the best performance, before performing random walk, we also performed unsupervised feature selection [He et al., 2006] for SemiHIN-Full-Graph, and applied the selection weights to each feature when computing ensemble of random walks.

4.3 Comparison

We first show the comparison results for all the configurations in Table 2. All the experiments are trained with five labeled data for each class. We evaluate algorithms in a transductive setting, which means we check whether an algorithm can use the five labels for each class to classify all the remaining examples correctly. Thus, all the results are averaged numbers of classification accuracy with 50 random trials. For supervised learning algorithms such as naive Bayes (NB) and support vector machine (SVM), they can only see the labeled data. For all semi-supervised learning algorithms, they can see the whole data including both labeled and unlabeled data.

From Table 2 we can see that, supervised learning with BOW+entity is comparable and often better than BOW, since we add more features about entities. LP based semi-supervised learning on 20NG datasets is better than supervised learning with the same amount of labeled data, since it leverages the unlabeled data. However, for GCAT datasets, LP based semi-supervised learning is slightly worse than supervised learning. This may be because for GCAT data, there are some words very class-indicative so that when

#labeled instances for each class

Figure 2: Classification results on 20NG-DIF dataset with different numbers of labeled documents per class.

converting i.i.d. features to similarities (which are used in LP), it introduces more ambiguity.

For HIN based algorithms, we found LP-Meta-path is better than LP based on BOW+Entity features. This makes sense since LP-Meta-path also incorporates DWD path, which is based on BOW. Co-training seems effective to mutually boost different meta-paths. LP-Meta-path is also comparable or better than KnowSim, since KnowSim is only unsupervised ensemble of meta-path based similarities while LP-Meta-path co-trains the weights of different meta-paths.

SemiHIN-Full-Graph is better than LP-BOW+Entity. This means the structural information among entities indeed helps improving semi-supervised learning. For the ensemble results, in general SVM is the worst, EM is better, and Co-train performs best. Ensemble-Co-train is better than SemiHINFull-Graph on 20NG data and GCAT-DIF. This may be because there are some other meta-graphs (or meta-paths) producing better results than the full graph. Then co-training can bootstrap the final labeling accuracy. Ensemble can help us automatically find a good solution without trying different meta-graphs based on the limited partially labeled data. Comparing Ensemble-Co-train and LP-Meta-path, it is shown that Ensemble-Co-train is better. An additional benefit of not working with PathSim is that we do not need to compute PathSim which could be more computational costly in practice.

Besides the overall results, we show results on 20NG-DIF dataset with different numbers of labeled data for each class in Figure 2. From the figure we can see that, with more labels, all the algorithms' classification results can be improved. In general, all the results are consistent with Table 2.

4.4 Computational Time

The computation of random walk with the sparse transition matrix is at worst O(N 3 ). As we observed that the undirected graph Laplacian is semi-positive definite, we can replace the inversion with a conjugate gradient descent (CGD) algorithm. For sparse matrix, the CGD method can achieve O(m√r) time, where m is the number of links, and r represents the condition number of the sparse matrix. We report the time based on a retail laptop with an Intel i7-4750HQ CPU and 16 Gigabytes RAM. For 20NG-SIM data, SemiHIN with matrix multiplication and inversion costed 52, 410 seconds while it only costed 1.8 seconds with CGD. Both NB and SVM costed less than 1 second. The original LP costed 2.2 seconds.

5 Conclusion

In this paper, we present a meta-graph guided random walk ensemble algorithm over heterogeneous information networks for semi-supervised learning. We first propose the undirected meta-graph structure and apply a graph-based semi-supervised learning algorithm. Then we combined predictions from different meta-graphs using three different ensemble algorithms. We demonstrated that our approach outperforms other state-of-the-art traditional and HIN based semi-supervised learning algorithms. We believe meta-graph is a general representation of many graphs. We would also study different graphs using meta-graph in the future.

Acknowledgements

This paper was supported by HKUST WeChat WhatLab, China 973 Fundamental R&D Program (No.2014CB340304), National Natural Science Foundation of China (NSFC Grant Nos. 61472006 and 91646202), and NSF Career Award #1741634.