Layer-stacked Attention for Heterogeneous Network Embedding

In recent years, many classes of GNN methods have been developed for a variety of heterogeneous network types (Schlichtkrull et al. 2018; Zhang et al. 2019; Wang et al. 2019; Zhou et al. 2019; Hu et al. 2020). Although these types of GNNs are flexible for end-to-end supervised prediction tasks, they only optimize for predictions between direct interactions. Compared to conventional network embedding methods (Grover and Leskovec 2016; Tang et al. 2015), standard GNNs generally do not take advantage of second-order relationships between indirect neighboring nodes. Recently, a paper by (Huang et al. 2020) applied a fusion technique to combine first-order and second-order embeddings at alternating steps. Additionally, the Jumping Knowledge architecture from (Xu et al. 2018) and the GraphSAGE (sampling and aggregation) from (Hamilton, Ying, and Leskovec 2017) has proposed to extend the neighborhood ranges; however, there has yet to be an extension of such techniques for heterogeneous networks.

Notably, GTN (Yun et al. 2019) was recently proposed to enable learning on higher-order meta paths in heterogeneous networks. It proposes a mechanism that soft-selects a convex combination of meta path layers using attention weights, then applies multiplication of adjacency matrices successively to reveal arbitrary-length transitive meta paths. This mechanism is unique in that it can infer attention weights not only on the given relations, but also on higher-order relations generated by deeper layers, a feature that most existing GNN methods often neglect. A few limitations with GTN is it necessarily assumes the feature distribution and representation space of different node and link types to be the same, and it cannot weigh the importance of each meta path separately for each node type. Additionally, GTN can be computationally expensive, since it requires computations involving the adjacency structure of all node types at once.

It is worth mentioning the approaches designed for a subclass of the heterogeneous network, the multiplex network. Many of the current multiplex or multiview network embedding methods (Fu, Lee, and Lei 2017; Matsuno and Murata 2018; Qu et al. 2017; Shi et al. 2018) have proposed strategies for aggregating the learned embeddings of multiple network “layers” into a single unified embedding. This class of methods typically specify separate objectives for each of the layers to estimate the node features independently, then apply another objective to aggregate the information from all layers together.

Another paradigm is to use random-walk of meta paths to model heterogeneous structures, as proposed in (Perozzi, Al-Rfou, and Skiena 2014; Dong, Chawla, and Swami 2017; Fu, Lee, and Lei 2017). This class of approaches can learn network representations without supervised training for a specific task. However, they only learn representations for the primary node type, which consequently requires the customized design of meta paths. Also, they can be sensitive to the random walk’s hyper-parameter settings, which may introduce unwanted biases or is computationally costly, thus can lead to lacking performance. Another class of algorithm utilizing embedding translations can also be applied for embedding heterogeneous networks. For instance, (Bordes et al. 2013) learned linear transformations for each relation to model semantic relationships between entities. While embedding translations can effectively model heterogeneous networks, they are mainly fitted for link prediction tasks.

We consider a heterogeneous network as a complex system involving multiple types of links between nodes of various types. To effectively represent the complex structure of the system, it is important to define separate adjacency matrices to distinguish the nature of relationships. In this section, we define coherent notations to study the class of attributed heterogeneous networks.

In this section, we start by describing the attention-based layers used in the LATTE heterogeneous network embedding architecture. The attention mechanism utilized in our method closely follows GAT (Veličković et al. 2018) but is extended to infer higher-order link proximity scores for nodes and links of heterogeneous types. We also introduce the layer building blocks where each layer has the roles of inferring node embeddings from heterogeneous node content and preserving higher-order link proximities.

The input to our model is the set of heterogeneous adjacency matrices $\mathcal{A}$ and the heterogeneous node features $\mathcal{X}=\{\mathbf{X}_{m}|\exists m\in\mathcal{T_{V}}\}$, where $\mathbf{X}_{m}=\{\mathbf{x}_{i}\in\mathbb{R}^{D_{m}}|\forall i\in\mathcal{V}_{m}\}$. At each $t^{\text{th}}$ layer, we define the node embeddings output $\mathbf{h}^{t}\in\mathbb{R}^{|\mathcal{V}|\times F}$, where $F$ is the embedding dimension, as:

$$\mathbf{h}^{t}=f_{t}(\mathbf{h}^{t-1},\mathcal{A}^{t})$$

where $\mathbf{h}_{i}^{0}=\mathbf{x}_{i}$, and $\mathcal{A}^{t}$ is the heterogeneous link adjacency matrices in the $t^{\text{th}}$-order. In the next section, we describe the operations involved when $t=1$.

In this section, we describe the layer-stacking operations involved to extract higher-order proximities when $t\geq 2$. The t${}^{\text{th}}$-order proximity applies to indirect $t$-length metapaths achieved by combining two matching meta relations. For instance, when $t=2$, we can connect a relation $\mathbf{A}^{(m,n)}\in\mathcal{A}^{t-1}$ with target type $n$ to another relation $\mathbf{A}^{(n,p)}\in\mathcal{A}$ with matching source type $n$. Then, computing the Adamic-Adar (Adamic and Adar 2003) as:

$$\begin{split}\mathbf{A}^{(m,n,p)}&=\mathbf{A}^{(m,n)}\mathbf{D}^{-1}\mathbf{A}^{(n,p)}\\ \mathbf{D}_{jj}&=\sum_{i\in\mathcal{V}_{m}}a^{(m,n)}_{ij}+\sum_{k\in\mathcal{V}_{p}}a^{(n,p)}_{jk}\end{split}$$

(5)

yields $\mathbf{A}^{(m,n,p)}$ as the degree-normalized biadjacency matrix consisting of length-2 metapaths from $\mathcal{V}_{m}$ nodes to $\mathcal{V}_{p}$ nodes. We define the set of meta relations containing all length-$t$ metapaths in the network, as:

$$\mathcal{A}^{t}=\mathcal{A}^{t-1}\times\mathcal{A}$$

(6)

where $\times$ behaves as a cartesian product that yields the Adamic-Adar only for matching pairs of relations. A length-$t$ sequence of meta relations with source type $m$ and target type $p$ is denoted as $(m\overset{{}_{t}}{\shortrightarrow}p)$. This is directly applicable to the classical metapath paradigm (Sun et al. 2011), where all possible $t$-length metapaths are decomposed in each separate relation in $\mathcal{A}^{t}$. Note that throughout this paper, the meta relations $(m,n)$ notation is overloaded for brevity. In fact, this architecture can handle multiple meta relation types with the same source type and target type, i.e. $\phi(e_{ij})=\left<\phi(i),\phi(e),\phi(j)\right>$, without loss of generalization.

We repurpose the computed attention scores to estimate the heterogeneous pairwise proximities in the network explicitly. Incorporating this objective not only enables our model for unsupervised learning but also allows the node-level attention mechanism to reinforce highly connected node pairs by taking advantage of weighted links. To preserve pairwise t^th-order proximities for all links in each $(m\overset{{}_{t}}{\shortrightarrow}p)$ relation, we apply the Noise Contrastive Estimation with negative sampling (Mikolov et al. 2013) objective as:

$$\begin{split}L_{t}(\mathbf{A}^{(m\overset{{}_{t}}{\shortrightarrow}p)})=&-\frac{1}{|\mathbf{A}^{(m\overset{{}_{t}}{\shortrightarrow}p)}|}\sum_{a_{ik}}^{\mathbf{A}^{(m\overset{{}_{t}}{\shortrightarrow}p)}}a_{ik}\log(\rho(e^{t}_{ik}))\\ &-\frac{1}{K}\sum_{k}^{K}E_{a_{uv}\sim P(\mathbf{A}^{(m\overset{{}_{t}}{\shortrightarrow}p)})}[\log\rho(-e^{t}_{uv})]\\ \end{split}$$

(11)

where $\rho$ denotes the sigmoid function applied to the attention score to infer a probability value. The first term models the observed links, the second term models the negative links drawn from the noise distribution in $(m\overset{{}_{t}}{\shortrightarrow}p)$, and $K$ is the number of sampled negative links. Typically, $K$ is chosen to be between 2 to 5 times the number of positive links.

To learn from both the heterogeneous network’s attributes and topology, we optimize the proximity-preserving objectives and the downstream objective of the embedding outputs with the standard back-propagation algorithm. For semi-supervised node classification, a multi-layer perceptron $g(\mathbf{h}_{i})=\widetilde{\mathbf{y}}_{i}\in[0,1]^{G}$ follows the LATTE layers in order to predicts $G$ labels given the node embedding. The cross-entropy minimization objectives are defined as:

$$L(\mathcal{X},\mathcal{A})=-\sum_{i\in\mathcal{V}_{Y}}\mathbf{y}_{i}log(g(\mathbf{h}_{i}))+\sum_{t=1}^{T}\sum^{\mathcal{A}^{t}}_{\mathbf{A}^{(m\overset{{}_{t}}{\shortrightarrow}n)}}L_{t}(\mathbf{A}^{(m\overset{{}_{t}}{\shortrightarrow}n)})$$

(12)

where $\mathcal{V}_{Y}$ is the set of nodes that have labels, and $\mathbf{y}_{i}$ is the true label. The first term aims to encode the node embedding representations with attention mechanisms, while the second term reinforces the attention scores by iterating through weighted positive and sampled negative links.

Our model allows for computing embeddings for a subnetwork each iteration; thus, it does not require computations involving the global network structure of all nodes at once. This approach not only enables mini-batch training on large networks that do not fit on memory but also makes our technique fitted for inductive learning. To perform online training at each iteration, an input batch is generated by recursively sampling a fixed number of neighbor nodes (Hamilton, Ying, and Leskovec 2017). Then, LATTE can yield embedding outputs for a sampled subnetwork given the local links and node attributes.

We conduct performance comparison experiments over several benchmark heterogeneous network datasets. In Table 1, a summary of the network statistics is provided for each of the following datasets:

1. 1.

   DBLP¹¹1https://dblp.uni-trier.de: a heterogenous network extracted from a bibliography dataset on major computer science journals and proceedings. The dataset have been preprocessed to contain 14328 papers, 4057 authors, 20 conferences, and 8789 terms. There are 3 relations types paper-author, paper-conference and paper-term considered. The author’s attributes are a bag-of-word representation of publication keywords. The classification task is to predict the label for each author among four domain areas: database, data mining, machine learning, and information retrieval.

2. 2.

   ACM²²2https://dl.acm.org: A small citation network dataset containing paper-author and paper-subject relation types among 3025 papers, 5835 authors, and 56 subjects node types. Paper nodes are associated with a bag-of-words presentation of keywords as features. The task is to label the conference each paper is published in, among the KDD, SIGMOD, SIGCOM, MobiCOMM, and VLDB venues.

3. 3.

   IMDB (Cantador, Brusilovsky, and Kuflik 2011): A movie database network containing movie-actor and movie-director relations among 4780 movies, 5841 actors, and 2269 directors. Each movie contain bag-of-words features of the plot, and the prediction task is to label the movie’s genre among Action, Comedy, and Drama.

In each of the datasets, all directed relation have a reverse relation included. All self-loop links have been removed, unless if required for a certain algorithm.

To provide a consistent and reproducible experimental setup, the preprocessed networks were obtained from the CogDL Toolkit (Cen et al. 2020) benchmark datasets. Each of the datasets has been provided with a standard separation of train, validation, and test sets, as well as the full input features and labels set. Since our model evaluates these datasets based on their standard environment, the result from different experiments can be directly compared.

We consider the semi-supervised classification tasks in both inductive and transductive settings to perform thorough evaluations of representation learning in heterogeneous networks. In the transductive setting, models can traverse on the subgraph containing nodes in the test set during training. In contrast, the inductive setting requires the models never to encounter the test subgraph during the training phase and must predict testing nodes’ labels on the novel subgraph at the testing phase. We train and evaluate all baseline methods to predict test nodes for each transductive and inductive setting over ten trials.

To measure the classification performance of the prediction outputs, we record the precision and recall for each class label to compute the F1 score. Due to the apparent class imbalance in the three datasets, we report only the averaged Macro-F1 score, which was the more challenging metric in similar experiments (Wang et al. 2019). The performance comparisons are reported in Table 2. For metapath2vec, HIN2Vec, HAN, and GTN, the benchmark Macro F1 scores in the transductive setting has been provided by the CogDL Toolkit, while the Macro F1 in the inductive setting are averaged scores over 10 experiment runs.

The top performance by LATTE-2_prox indicates its effectiveness at learning node representations on the high-order meta relation structures, especially with 80-90% of the network set aside for testing. Compared to HAN, which does not consider higher-order relations, GTN and LATTE-2 have a significant edge in inductive prediction because both can capture global properties. Compared to GTN, which does not maintain the semantic space of individual meta path, LATTE-2_prox outperforms with explicit proximity-preserving objectives for each of the decomposed higher-order meta relations.

LATTE’s fundamental properties are the construction of higher-order meta relations and the attention mechanism that weighs the importance of those relations. To demonstrate these features’ benefits, we interpret the importance levels chosen for each meta relations and verify whether they reflect the structural topology in the heterogeneous network. Given the learned weights $\boldsymbol{\beta}^{t,i}$ for each node $i$ at a layer $t$, we can assess not only the averaged meta relation weights for a node type, but also the individual meta relation weights for each node. In Fig. 1, we report the average and standard deviation of the meta relation attention weights for IMDB, as well as the correlation between those weights and the node degrees for each relation. The meta relation weights for DLBP and ACM are reported as supplementary material.

For IMDB movies, it can be observed that on average, the MA, MD, MDM, and MAM meta relations have the highest attention weights. This indicates that information from the movie-actor neighborhoods, movie-director neighborhoods, and node’s features are relatively more represented in each movie’s first-order embedding. This selection also persists in the second-order embeddings, where MDM and MAM have higher weights. Additionally, when looking at the correlation between MA’s weights and the degree of MA links over all nodes, there is a $0.73$ correlation, which indicates the attention mechanism can adaptively weigh the relation based on the number connections present in the node. Interestingly, there is a substantial negative correlation of $-0.88$ between the M “self” relation weights and the node degree. This fact indicates that nodes with fewer or no links will choose a higher weight for its own features, since little information can be gained from other modalities. As individual nodes may have varying levels of participation among the various relations, this result demonstrates that LATTE can select the most effective meta relation for individual nodes depending on its local and global properties in the heterogeneous topology.

The hyper-parameter tuning were conducted by the Weight and Biases³³3Biewald, L. 2020. Experiment Tracking with Weights and Biases. URL https://www.wandb.com/. Software available from wandb.com. platform, where we utilize a random search approach that chooses random sets of parameter values. The parameters tested for are the embedding dimension, ${t}$-order, attention scores activation function, number of neighbors sampled, negative sampling ratio, embedding output activation function, and dropout probability.

Following the demonstration to interpret the learned attention weights in the IMDB dataset, we report the same attention weights and the weights-degree correlation results for the DBLP and ACM datasets. In Fig. 4 and 5, it can be observed that correlation between the meta relation weights and the node degree exhibits the same phenomenon described for IMDB.