Network Schema Preserving Heterogeneous Information Network Embedding

1 Introduction

Network embedding, which aims to project the nodes of a network into a low-dimensional space while preserving the structural properties of the network, has been a promising research field [Cui et al., 2019]. Most of the existing network embedding methods focus on homogeneous network. However, with the proliferation of interaction systems, Heterogeneous Information Networks (HINs) [Sun et al., 2011], which consist of multiple types of entities and links, have emerged as a powerful tool for modeling complex interaction behaviors. Recently, to handle the ubiquitous heterogeneous network data, representation learning on HIN has drawn increasing attention [Dong et al., 2017; Fu et al., 2017] and is widely used in various real-world applications including node classification, clustering, and recommendation.

∗Both authors contributed equally to this research.

†Corresponding author.

Figure 1: A toy example of an HIN on bibliographic data.

To learn the node representation on HINs, HIN embedding methods have been proposed [Dong et al., 2017; Fu et al., 2017; Shi et al., 2019; Zhang et al., 2018; He et al., 2019], many of which exploit the meta-path(s) guided random walk to retain both the semantics and structural correlations between different types of nodes. Typically, a meta-path is a sequence of relations between two nodes in an HIN. For example, given a bibliography HIN (four types of nodes: author (A), paper (P), Venue (V) and term (T); three types of relations: "write", "publish", and "contain") shown in Figure 1(a), Figure 1(b) displays two meta-paths APA and APVPA which describe the co-author or co-venue structure between two authors, respectively. The meta-path based random walk will confine the node sequence along the predefined metapath, and further capture the high-order semantic structure.

Despite the success of meta-path guided HIN embedding methods, the selection of meta-paths still remains an open yet challenging problem [Sun et al., 2011]. The design of meta-path schemes significantly relies on domain knowledge. Manually selecting meta-paths based on prior knowledge may work for a simple HIN, while it is difficult to determine meta-paths for a complex HIN. Furthermore, different meta-paths will result in different embeddings from different points of view, which leads to another challenging problem, i.e., how to effectively fuse different embeddings to generate uniform embeddings. Some existing works [Shi et al., 2019; Wang et al., 2019; Hu et al., 2019b] use label information to guide the embedding fusion; unfortunately, this is not applicable in unsupervised scenarios.

To tackle the above challenges, we observe that the network schema [Sun et al., 2011], as a uniform blueprint of HIN, comprehensively retains node types and their relations in an HIN. Since network schema is a meta template for HIN, guided by it, we can extract subgraphs (i.e., schema instances) from the HIN. An example is shown in Figure 1(c) and (d), from which we can see that the schema instance depicts the high-order structure information of these four nodes, besides the first-order structure information of two nodes (i.e., pairwise structure). Moreover, the schema instance also contains rich semantics, i.e., a schema instance (shown in Figure 1(d)) naturally describes the overall information, such as the author, the term, and the venue of a paper, as well as their relations. More importantly, different from meta-paths, network schema is a unique structure for an HIN, and thus we do not need domain knowledge to make a choice. These benefits of network schema motivate us to study network schema preserving HIN embedding.

However, it is a non-trivial task. First, how to effectively preserve the network schema structure? Network schema structure usually contains all types of nodes. The widely used random walk (with/without meta-path) strategy cannot guarantee to visit all types of nodes and links, therefore it is not applicable for preserving network schema. Moreover, the numbers of various types of nodes in a network schema structure are usually very different, leading to the bias problem. For example, a paper is associated with one venue, but with many terms. Moreover, how to capture the heterogeneity of nodes and links inside network schema? We need to delicately design a method not only preserving network schema structure but also considering node and link heterogeneity.

In this paper, we make the first attempt to investigate Network Schema preserving Heterogeneous information network Embedding and propose a novel model named NSHE. Based on node embedding generated by heterogeneous graph convolutional network, NSHE optimizes the embedding via node pairs and schema instances sampled from the HIN. Particularly, in the network schema preserving component, we propose a network schema sampling method, which generates sub-graphs (i.e., schema instances) naturally preserving schema structure. Furthermore, for each schema instance, a multi-task learning model is built to predict each node in the instance with other nodes, which tackles the challenge of heterogeneity. Our major contributions are highlighted as follows:

• To the best of our knowledge, we make the first attempt to preserve the network schema structure for HIN embedding, which not only preserves high-order structure in HIN but also alleviates the meta-path selection dilemma in meta-path guided HIN embeddings.
• We propose a novel model NSHE, in which some delicate designs, e.g., network schema sampling and multitask learning, are proposed to solve the schema structure preserving and the heterogeneity challenges.
• We conduct extensive experiments on three real-world datasets to validate the effectiveness of NSHE compared with the state-of-the-art methods.

2 RelatedWork

Our work is related to network embedding, which assigns nodes in a network to low-dimensional representations and effectively preserves the network structure. For example, the neighbor structure preserving network embedding [Perozzi et al., 2014], the second-order structure preserving network embedding [Tang et al., 2015; Wang et al., 2016], and the community structure preserving network embedding [Wang et al., 2017]. Most of these network embedding methods focus on homogeneous networks, and an elaborate review can be found in [Cui et al., 2019].

With the thriving of heterogeneous network data in realworld applications, HIN Embedding methods have drawn increasing research attention recently. Most existing methods utilize the meta-paths to capture HIN structure. For instance, ESim [Shang et al., 2016] accepts meta-paths as guidance to learn node embedding for similarity search. Metapath2Vec [Dong et al., 2017] proposes meta-path guided random walk and heterogeneous Skip-Gram to handle the heterogeneity in HINs. HIN2Vec [Fu et al., 2017] learns HIN embeddings via predicting different relations in HINs. RHINE [Lu et al., 2019] distinguishes the meta-path based relations and deals with them using different models. HeteSpaceyWalk [He et al., 2019] proposes a spacey random walk to preserve the Markov chain nature of meta-paths based random walks. However, these methods suffer from the meta-path selection and fusion conundrums. In addition, several methods perform HIN embedding without using meta-paths. JUST [Hussein et al., 2018] develops a jump and stay strategy on random walks. HetGNN [Zhang et al., 2019] adopts graph neural networks and preserves the first-order and second-order proximity. HeGAN [Hu et al., 2019a] introduces adversarial learning in HIN embeddings. Though these methods perform HIN embedding without using meta-paths, all of them do not explicitly preserves the network schema structure.

3 ProposedMethod

Consider an HIN G = (V,E) composed of a node set V and an edge set E, along with the node type mapping function φ : V → A, and the edge type mapping function ψ : E → R, where A and R denotes the node and edge types, |A| + |R| > 2. The task is to learn the representation of nodes Z ∈ R|V |×d , where d is the dimension of representation.

Figure 2 illustrates the framework of the proposed NSHE. NSHE preserves the pairwise and schema proximity concurrently. First, to fully exploit complex network structure and heterogeneous node feature together, we propose to learn node embedding via heterogeneous node aggregation. Second, we preserve the pairwise structure and the schema structure simultaneously. While directly performing random walk cannot generate the desired schema structure, we propose to sample schema instances and preserve the proximity inside instances. Moreover, as different types of nodes in the instances carry different context, a multi-task learning model is designed to in turn predict a target node with other context nodes to handle heterogeneity inside schema instances. Finally, NSHE iteratively updates node embeddings via optimizing the aggregation of the pairwise and schema preserving loss.

3.1 Preserving Pairwise Proximity

Despite that we need to capture the network schema structure in HIN embedding, the pairwise proximity between nodes [Tang et al., 2015], as one of the most direct expressions of an HIN, still needs to be preserved. It demonstrates that two nodes with a link, regardless of their types, should be similar. Specifically, considering the heterogeneity of different node feature, for each node vi with feature fi and type φ(vi), we use a type-specific mapping matrix Wφ(vi) to map the heterogeneous feature to a common space:

where σ(·) denotes an activation function, and bφ(vi) stands for the bias vector of type φ(vi). Based on Equation (1), all the nodes with different types are mapped to the common space, and we denote their mapped features as H = [f ′ i ]. Then, we use a L-layer graph convolutional network to generate the node embeddings [Kipf and Welling, 2017] as:

where A is the adjacency matrix, and Ai,j = 1 if (vi, vj) ∈ E, otherwise Ai,j = 0. D is a diagonal matrix, where Dii = ∑j Aij. I|V | is the identity matrix of R|V |×|V | . For the first layer, we denote H(0) = H and use the output of the Llayer graph convolutional networks as the node embedding, i.e., Z = H(L) , where the i-th row of Z is the embedding zvi of node vi.

The objective of preserving the pairwise proximity with parameters Θ can be described as:

where Nvi = {vj |(vi, vj) ∈ E}. The conditional probability p (vj |vi; Θ) is defined as a softmax function:

To calculate p (vj|vi;Θ) efficiently, we leverage the negative sampling method [Mikolov et al., 2013] and optimize Θ with the logarithm of Equation (3), therefore the pairwise loss Lp can be calculate by:

where δ(x) = 1/(1 + exp(-x)), Pn (v) is the noisy distribution, and Me is the negative edge sampling rate. Through minimizing Lp, NSHE preserves the pairwise proximity.

3.2 Preserving Network Schema Proximity Network Schema Instance Sampling

Network schema is the blueprint of an HIN [Sun et al., 2011]. Given an HIN G = (V, E), a network schema TG = (A, R) preserves all the node types A and relation types R inside G. Network schema proximity implies that all the nodes with different types in a network schema structure should be similar. However, as we mentioned before, the nodes in a network schema structure are usually biased, i.e., the number of nodes of a certain type is larger than those of other types. For example, in Figure 1(a), a paper has multiple authors, but only one venue. To alleviate such bias, we propose to sample a network schema instance defined as follows: A network schema instance S is the smallest sub-graph of an HIN, which contains all the node types and edge types defined by the network schema TG, if existing. By this definition, each network schema instance is composed of all the node types A and relation types R defined by the schema, i.e., one node for each type. To illustrate, Figure 1(d) shows two instances sampled from the given HIN. The sampling process is as follows: Starting from a set S with one node, we keep adding a new node to S until |S| = |A|, where the new node satisfies: (1) its type is different from the node types in S; (2) it connects with the node(s) in S.

Schema Preserving with Multi-task Learning

Now, we aim to preserve the network schema proximity by predicting whether a network schema instance exists in an HIN. To this end, assume we have a network schema instance S = {A1, P1, V1, T1} as shown in Figure 2, we can predict whether A1 exists given the set {P1, V1, T1}, or whether P1 exists given the set {A1, V1, T1}, and so on. These two predictions are different, because of the node heterogeneity. Considering this, we are motivated to design a multi-task learning model to handle the heterogeneity within schema.

Without loss of generality, assume we have the schema instance S = {vi, vj, vk}, if we aim to predict whether vi exists given {vj, vk}, we call vi the target node and {vj, vk} the context nodes. Therefore, each node will have two roles:

one is as the target node and the other is as the context node, as well as two embeddings: target embedding and context embedding. To fully consider the heterogeneity, each node type φ(vi) is associated with an encoder CEφ(vi) to learn the context embeddings for the context nodes:

where each CE stands for a fully connected layer of neural network. Then for the target node vi, we concatenate its target embedding zvi with the context embeddings to obtain the schema instance embedding with target node vi denoted as zvi S as follows:

After obtaining the embedding zvi S , we predict the probability of S with target node vi, denoted as yvi S , whether exists in the network:

where MLPφ(vi) is the classifier for schema instances with target node type as φ(vi). Similarly, when we treat vj and vk as the target nodes, respectively, yvj S and yvk S can also be obtained following the steps introduced above. Note that, here we take the schema instance with three nodes as an example to explain our method. However, it is easy to extend the model to schema instance with more nodes, since the process is the same.

The schema proximity loss Ls can be obtained by predicting the multi-tasks of the schema instances S sampled from HIN. Additionally, to avoid trivial solutions, we also drawMs negative examples of target type for each schema instance via replacing the target node with another node in the same type. The loss of preserving network schema can be described as:

• DBLP [Lu et al., 2019]: We extract a subset of DBLP which contains 9556 papers (P), 2000 authors (A), and 20 conferences (C). The authors and papers are divided into four areas: database, data mining, machine learning, and information retrieval. We do the two tasks for papers and authors and call them DBLP-P and DBLPA, respectively. We use 4 meta-paths, namely APCPA, APA, PAP, and PCP, for meta-path related baselines.
• IMDB [Wang et al., 2019]: We extract a subset of IMDB which contains 3676 movies (M), 4353 actors (A), and 1678 directors (D). Movies are divided into three classes, namely action, comedy, and drama according to their genre. We use two meta-paths, namely MAM and MDM, for meta-path related baselines.
• ACM [Wang et al., 2019]: We extract papers published in KDD, SIGMOD, SIGCOMM, MobiCOMM, and VLDB and divide them into three classes: database, wireless communication, and data mining. Then we construct an HIN that contains 4019 papers (P), 7167 authors (A), and 60 conference subjects (S). Papers are labeled according to their conferences. Paper features are the bag-of-words representation of keywords. We use PAP and PSP for meta-path related baselines.

We compare NSHE with seven state-of-the-art embedding methods including two homogeneous network embedding methods, i.e., DeepWalk and LINE and five heterogeneous networks embedding methods, i.e., the last five algorithms:

• DeepWalk [Perozzi et al., 2014]: It performs a random walk on networks and then learns the representation of nodes via the Skip-Gram model.

where Rvi S = 1 if Svi is a positive network schema instance, otherwise Rvi S = 0. By minimizing Ls, the schema structure is preserved.

3.3 Optimization Objective

To preserve both the pairwise proximity and the network schema proximity of HINs, NSHE optimizes the overall loss L by aggregating the loss of preserving pairwise proximity Lp and preserving schema proximity Ls :

where β is a balancing coefficient. At last, we adopt the Adam [Kingma and Ba, 2015] algorithm to minimize the objective in Equation (10).

4 Experimental Results and Analysis

4.1 Experimental Setup

In order to demonstrate the effectiveness of the proposed model, we conduct extensive experiments including clustering and classification on three HINs shown below:

• LINE [Tang et al., 2015]: It considers first-order or second-order proximity in networks, denoted as LINE1st and LINE-2nd, respectively.
• Metapath2Vec [Dong et al., 2017]: It adopts metapaths based random walk and heterogeneous Skip-Gram model to perform node embedding.
• HIN2Vec [Fu et al., 2017]: It learns the latent representation of nodes and meta-paths in an HIN by conducting multiple prediction training tasks jointly.
• HERec [Shi et al., 2019]: It adopts meta-paths to filter node sequences of same type with different semantics and applies DeepWalk to perform network embedding.
• DHNE [Tu et al., 2018]: It adopts deep auto-encoders and classifiers to preserve the first and second order proximity of hyper networks. Here we treat the network schema instances as hyper-edges.
• HeGAN [Hu et al., 2019a]: It learns the representation of nodes in HIN via preserving the heterogeneous relations with adversarial learning.

Here, we briefly introduce the experimental settings. For our proposed model, the feature dimension in common space and the embedding dimension d is set as 128. The negative schema instance sample rate Ms in Section 3.2 is set as 4. We perform neighborhood aggregation via an one-layerGCN, i.e., L = 1, and use two-layer-MLPs for schema instance classification. For models that use meta-paths in modeling, we choose the popular meta-paths adopted in previous methods and report the best result. For models that require node feature, we apply DeepWalk [Perozzi et al., 2014] to generate node feature. The code and dataset is publicly available on Github 1 .

4.2 Node Classification

In this section, we evaluate the performance of node embedding with node classification tasks. After learning the node embeddings, we train a logistic classifier with 80% of the labeled nodes and use the remaining data for testing. We use Micro-F1 and Macro-F1 score as the metrics for evaluation. The results are shown in Table 1, from which we have the following observations: (1) Generally speaking, HIN embedding methods perform better than homogeneous network embedding methods, which proves the benefits of considering heterogeneity. (2) Though NSHE does not utilize any prior knowledge, it consistently outperforms the baselines. It demonstrates the effectiveness of our proposed method in classification tasks.

4.3 Node Clustering

We further conduct clustering tasks to evaluate the embeddings learned by NSHE. Here we utilize the K-Means model to perform node clustering and set the number of clusters for K-Means as the number of classes. The performance in terms of NMI is shown in Table 2. Similarly, the proposed method NSHE significantly outperforms others in most cases, which further demonstrates the effectiveness of NSHE.

1 https://github.com/Andy-Border/NSHE

4.4 Comparison of Variants of NSHE

In order to verify the effectiveness of the delicate designs in NSHE, we propose three variants of NSHE as follows:

• NSHE-Pairwise considers the pairwise loss only, i.e., L = Lp. Therefore, the NSHE-Pairwise model does not explicitly preserve the high-order structure of network schema.
• NSHE-NS leverages the structure of network schema only, i.e., L = Ls. Therefore, the NSHE-NS model does not explicitly preserve the pairwise structure.
• NSHE-Homo treats the heterogeneous network schema instances as homogeneous. That is, NSHE-Homo uses one MLP classifier for all of the network schema instances classification tasks.

We use the same parameter for variants of NSHE and show the classification and clustering performances of each model in Figure 3. For better visualization, we scale the NMI value to [0,1] according to the best performance of the variants. It is obvious that NSHE outperforms the variants in most cases. NSHE performs better than NSHE-NS and NSHE-pairwise, indicating that it is necessary to preserve both first-order (i.e., pairwise) and high-order (i.e., network schema) structure information. Moreover, the first-order structure, as the most basic expression of HIN, is more essential, since NSHEPairwise generally performs better than NSHE-NS. The better performance of NSHE against NSHE-Homo confirms the benefit of multi-task learning for handling heterogeneity in network schema instances.

Figure 5: Parameter sensitivity of NSHE w.r.t. the balancing coefficient β and the number of negative schema instances Ms.

4.5 Visualization

To examine the network representations intuitively, we visualize the embeddings of author nodes in DBLP using the tSNE [Maaten and Hinton, 2008] algorithm. We select DeepWalk and Metapath2Vec as the representative baselines for homogeneous and heterogeneous embedding methods. For Metapath2Vec, the APCPA meta-path is adopted, since it achieves the best results on DBLP. The visualization of embeddings generated by different methods is shown in Figure 4, from which we can observe the following phenomenons: The heterogeneous methods (i.e. Metapath2Vec and NSHE) outperform the homogeneous method DeepWalk, whose embedding has blurry boundaries and may lead to inaccuracy in classification tasks. Moreover, without given any prior knowledge or supervision, NSHE still separates the authors in different research areas with distinct boundaries, which further demonstrates that the preservation of both pairwise and the schema structure in HIN is effective.

4.6 Parameter Analysis

In this section, we investigate the sensitivity of parameters and report the results of NSHE in terms of classification on ACM and clustering on DBLP-P with different parameters.

Balance coefficient β. The balance coefficient β, described in Section 3.3, balances the importance between the pairwise similarity and the high-order proximity of network schema. Larger β stands for greater high-order influence on the model. Figure 5(a) and Figure 5(b) show the impact of different β on classification and clustering tasks, respectively. As we can see, for both tasks, it is better to balance the importance of different terms. Specifically, while increasing β, the performance of both tasks firstly increases and reaches a peak with β = e and β = e3 for classification and clustering respectively. Notably, the optimal β differs in different datasets and tasks, which indicates that the importance of the pairwise and the high-order proximity varies in different tasks.

Negative schema instance rate Ms. The negative instance rate, described in Section 3.2, is the ratio between negative and positive network schema instances. Figure 5(c) and Figure 5(d) show the impact of different Ms on classification and clustering tasks, respectively. The results indicate that NSHE needs a suitable negative sample rate to preserve the highorder structure. As we can see, with the growth of the negative sample rate, the performance raises first and then starts to drop slowly after the negative sample rate equals to 4. The reason is that the large negative schema sampling rate will cause imbalance of data which causes trivial solutions (all negative prediction) of classifiers. In this case, the schema proximity cannot be well preserved.

5 Conclusion

In this paper, we make the first attempt to study the network schema preserving embedding in HINs. Network embedding via network schema preserves the semantics of network schema and does not suffer from limited domain knowledge. We propose NSHE, which learns embeddings that preserve pairwise structure and network schema structure concurrently. Particularly, NSHE adopts a network schema instance sampling method to deal with the bias of different types of nodes and uses multi-tasks classifiers to preserve the heterogeneity within HINs. Experimental results including classification and clustering demonstrate the effectiveness of NSHE.

Acknowledgments

J. Zhao, C. Shi, X. Wang, and Z. Liu's work is supported by the National Natural Science Foundation of China (No. U1936220, 61772082, 61702296, 61806020, 61972442), the National Key Research and Development Program of China (2018YFB1402600), the CCF-Tencent Open Research Fund, and the Fundamental Research Funds for the Central Universities. Y. Ye's work is partially supported by the NSF IIS1951504, CNS-1940859, CNS-1946327, CNS-1814825 and OAC-1940855, and the NIJ 2018-75-CX-0032.