Tree Structure-Aware Graph Representation Learning via Integrated Hierarchical Aggregation and Relational Metric Learning

For a node $n_{o}$, we have discussed we can use hierarchical tree schemas to divide its multi-hop neighborhood into multiple structured trees, each of those represents a distinctive neighborhood for $n_{o}$. Given the hierarchical tree extracted by one schema $s$ where $n_{o}$ is the root node, and the initial feature vectors $\mathbf{x}_{i}\in\mathbb{R}^{d_{t}}$($d_{t}$: the initial feature vector dimension) of each node on this tree, our intuition is to aggregate the information from all the neighbors under $n_{o}$’s level on the tree as well as $\mathbf{x}_{o}$ to form its representations.

As the neighbor information in the propagation can be regarded as sequential inputs divided by levels and GNN can not process sequential data. We conduct Gated Recurrent Unit (GRU) module combining with GNN on this tree to encode $\mathbf{x}_{o}$ and its neighbors information into a schema-specific output $\mathbf{z}^{s}_{o}$, the basic recurrence of the aggregation modules and propagation modules on hierarchical trees is:

where $0<a\leq m$, $\widehat{h^{(a)}_{i}}$ represents the output hidden sate of node $n_{i}$ which is on the $a$th level of the tree with schema $s$, i,e, . The hidden state $h_{i}^{(a-1)}$ represents the neighborhood message of $n_{i}$ passing from all its neighbors on the $(a-1)$th level. The $GRU(\mathbf{x}_{i},h_{i}^{(a-1)})$ is formulated as:

Where $\sigma(x)=\frac{1}{1+e^{-x}}$ is the sigmoid function and $\circ$ is element-wise multiplication. The aggregator function $AGGREGATE_{r_{a}}(\cdot)$ is a information aggregator of $n_{i}$’s sub-level neighbors specific for relation type $r_{a}$, which could be a mean pooling layer, max pooling layer, or a GNN aggregator, such as mean aggregator, LSTM aggregator, pooling aggregator introduced in GraphSAGE[15], graph attentional layer introduced in GAT[16]. In our paper, we use weighted mean aggregator, then the $h_{i}^{(a-1)}$ in Eq.1 is reformulated as:

where $r_{a}$ is the relation type between level $a$ and level $a-1$ on $s$ that connect $n_{i}$ with its sub-level neighbors, $N^{r}_{i}$ denotes the set of neighbors indices of node $n_{i}$ under the relation $r\in\mathcal{R}$. $W_{r}$ is a trainable weight matrix specific for relation type $r$. $c^{r}_{ij}$ is the weight or normalization constant of the edge $(n_{i},n_{j})$ with type $r$.

After the $m$ levels’ propagation on hierarchical trees structured neighborhood, the hidden output of node $n_{o}$ on schema $s$ can be obtained by:

Where $\mathbf{z}_{o}\in\mathbb{R}^{d^{\prime}}$($d^{\prime}$: representation dimension). To make model tuning easy, we also set the dimension of hidden states as $d^{\prime}$. In the neighbor information aggregation, parameters in GRU modules are shared and those in GNN modules are shared for same relation types. In practice, to save the calculation time, we use tensor operation and avoid the repeated aggregating on different trees with the same schemas, for example, for schema $\overrightarrow{TP}$ of paper nodes and $\overrightarrow{TPA}$ of author nodes, the aggregating processes from $T$ to $P$ are same for two schema and we only calculate once.

We have noticed that the gated neural units have been applied to some graph neural network models[17, 18, 19], majority of which are originated from GGNN[20]. Their main idea is stacking $k$-layer GNNs, and using GRU module to process the $k$ hidden layer outputs of each node as the sequenced information. Our proposed model is different from this idea: 1) We use the GRU module to help GNN directly aggregates the sequence information composed of neighbor nodes with arbitrary length, 2) Instead of stacking a fixed number of layers, our proposed T-GNN can stack different numbers of propagation layers for different node types according to their neighborhood depths.

Then given the hierarchical tree schema set $\mathcal{S}_{t}=\{s_{1},s_{2},...,s_{k}\}$ of $n_{o}$, we can obtain the hidden output set $\mathbf{Z}_{o}=\{\mathbf{z}^{1}_{o},\mathbf{z}^{2}_{o},...,\mathbf{z}^{k}_{o}\}$ of $n_{o}$ and $\mathbf{z}^{i}_{o}\in\mathbb{R}^{d^{\prime}}$. These hidden representations that contain different neighborhood information may make different contributions to $n_{o}$’s final representation. We employ the attention mechanism to combine these $k$ hidden representations with $n_{o}$’s feature vectors into the final representation vector of $n_{o}$, formulated as:

Where $\mathbf{u}_{o}\in\mathbb{R}^{d^{\prime}}$ is the final representation vector of $n_{o}$, $\alpha^{*}_{o}$ indicates the importance of different hidden representations for $n_{o}$, $W_{t}\in\mathbb{R}^{d^{\prime}\times d}$ is a type-specific linear transformation to project the features vectors of nodes with type $t$ into a hidden representation vector, which represent the feature information aggregated from each node itself. For brevity, we denote that $\mathbf{z}^{0}_{o}=W_{t}\mathbf{x}_{o}$ and add it into representation set $\mathbf{Z}_{o}$, then $\mathbf{u}_{o}$ can be reformulated as:

We leverage self-attention to learn the attention weights $\alpha^{i}_{o}$, which are calculated via softmax function:

which can be interpreted as the importance of the hidden representation $\mathbf{z}^{i}_{o}$, the higher the $\alpha^{i}_{o}$, the more important $\mathbf{z}^{i}_{o}$. $LeakyReLU$ denotes the leaky version of a Rectified Linear Unit, $a\in\mathbb{R}^{1\times 2d^{\prime}}$ is the attention parameter.

Then we can apply the final node representation vector $\mathbf{u}_{o}$ to the loss functions in supervised tasks, semi-supervised tasks, or unsupervised tasks, and optimize the propagation model via back propagation.

To perform heterogeneous graph representation learning, in this section, we leverage a graph context loss to optimize the model. Given a heterogeneous graph $G=(N,E,\mathcal{T},\mathcal{R})$, we aim to learn effective node representations by maximizing the probability of any node $n_{i}$ having its neighbor node $n_{c}$:

where $N_{r}(n_{i})$ is a set of neighbors of $n_{i}$, and $\forall n_{c}\in N_{r}(n_{i})$ connects $n_{i}$ with relation $r$, $\theta$ represents the parameters of the whole model. $p(n_{c}|n_{i},\theta)$ is the probability of any node $n_{i}$ having its neighbor node $n_{c}$, defined as a softmax function:

where $\mathbf{u}_{i}$ represents the encoded representation vector of $n_{i}$, $s(\mathbf{u}_{i},\mathbf{u}_{j})$ is the similarity between node $n_{i}$ and $n_{j}$. $N_{t}$ represents the node set of type $t$ and $t=\phi(n_{c})$. The softmax function is normalized with respect to the node type of the context $n_{c}$, so each type of the neighborhood in the output layer is specified to one distinct multinomial distribution.

As we aim to embed each type $t\in\mathcal{T}$ of nodes into a distinct space, we set $s(\mathbf{u}_{i},\mathbf{u}_{j})=\mathbf{u}_{i}^{T}\mathbf{u}_{j}$ if $n_{i}$ and $n_{j}$ have same type and in the same embedding space. For each node pair $(\mathbf{u}_{i},\mathbf{u}_{j})$ with distinct node type $t_{a}$ and $t_{b}$ and connected by a relation with type $r$ (which can be an atomic relation or a composite relation), we formulate the similarity $s(\mathbf{u}_{i},\mathbf{u}_{j})$ by introduce two candidate similarity metrics specific for $r$, which are described as:

• •

  Bilinear. A multiplicative similarity metric. We introduce a bilinear metric $M_{r}\in\mathbb{R}^{d^{\prime}\times d^{\prime}}$, which is shared by each node pair $(\mathbf{u}_{i},\mathbf{u}_{j})$ with relation type $r$ and specific to different relation types to avoid the similarity calculation on respective semantics to dampen each other.

  $$s(\mathbf{u}_{i},\mathbf{u}_{j})={\mathbf{u}_{i}}^{T}M_{r}\mathbf{u}_{j}$$

  (10)

• •

  Perceptron. A additive similarity metric. We first input $\mathbf{u}_{i}$ and $\mathbf{u}_{j}$ to node-type-specific multilayer perceptrons with output metric dimension $d_{m}$, then add the outputs of them, next with a tanh activation layer we can obtain the hidden representation vector of node pair $(\mathbf{u}_{i},\mathbf{u}_{j})$. Then a relation-type-specific metric $m_{r}\in\mathbb{R}^{d_{m}}$ is multiplied to calculate the similarity.

  $$s(\mathbf{u}_{i},\mathbf{u}_{j})=m_{r}^{T}\tanh(M_{t_{a}}\mathbf{u}_{i}+M_{t_{b}}\mathbf{u}_{j})$$

  (11)

The metrics are trainable parameters and are learned to measure which $\mathbf{u}_{j}$ under the relation $r$ is closer to $\mathbf{u}_{i}$, whose mechanism is similar to the mechanism of attention models. Note that the parameters of metrics are shared for same relation type $r$, while different relation types make use of different metrics and the corresponding distance on these relations of nodes is calculated in different metric spaces,

Then, we adopt the popular negative sampling method proposed in [21] to sample negative nodes to increase the optimization efficiency. Then, the probability $\log p(n_{c}|n_{i},\theta)$ can be approximately defined as:

where $\sigma(x)=\frac{1}{1+e^{-x}}$ is the sigmoid function and $N_{neg}^{i}\subseteq N_{t}$ is a negative node set for $n_{i}$ sampled from a pre-computed node frequency distribution $P_{t}(n_{i})$, we set $P(n_{i})\propto f_{n_{i}}^{3/4}$, where $f_{n_{i}}^{3/4}$ is the frequency of $n_{i}$ in $\mathcal{P}$. Then, we conduct random walks on the $G$ to sample a set of paths $\mathcal{P}$. Therefore, we can use skip-gram model on these paths and reformulate the objective in eq.8 as follows:

where $k$ is the windows size of context, $C_{i}^{k}$ is the context set containing the previous $k$ context nodes and next $k$ context nodes of $n_{i}$ in the path $p$. Parameter $\lambda$ controls penalty of regularization for over-fitting. Finally, we use a mini-batch Adam optimizer to minimize $\mathcal{L}$ and optimize the parameters in the whole model.

To evaluate the proposed method, we use three kinds of real-world datasets: academic graphs (DBLP), movie graphs (MOVIE), and review graph (YELP). The detailed descriptions of these datasets are as follows:

• •

  DBLP²²2https://www.aminer.cn/citation: DBLP is an academic bibliography with millions of publications. We extract a subset of DBLP with four areas: Data Mining (DM), Database (DB), Natural Language Processing (NLP) and Computer Vision (CV) from the year of 2013 to 2017. For each area, we choose three top venues³³3DM: KDD, ICDM, WSDM. DB: SIGMOD, VLDB, ICDE. NLP: ACL, EMNLP, NAACL. CV: CVPR, ICCV, ECCV. and related papers(P), terms(T), authors(A) to construct an heterogeneous graph.

• •

  IMDB⁴⁴4https://www.kaggle.com/tmdb/tmdb-movie-metadata: IMDB dataset contains knowledge about movies. We extract three genres of movie information from IMDB: Action, Comedy and Drama. Then we construct a movie heterogeneous graph which contains movies(M), actors(A), directors(D) and Tags(T).

• •

  YELP⁵⁵5https://www.kaggle.com/yelp-dataset/yelp-dataset: YELP is a datasets containing the data of restaurants reviews. We extract a subset of YELP containing costumers(C), review(V), keywords(K) and restaurants(R) from the information of restaurants with types: American, Chinese, Japanese and French to form a restaurant review heterogeneous graph.

We select some types of nodes and use graph representation learning methods to learn their representation vectors, Table I shows the statistics of these nodes and their corresponding hierarchical tree schemas used in our proposed model.

To validate the performance of our proposed method, we compare with some state-of-art baselines, including homogeneous heterogeneous graph representation learning method (DeepWalk), heterogeneous graph representation learning methods (Metapath2vec, RHINE), homogeneous graph neural networks (GraphSAGE, GAT) and heterogeneous graph neural networks (HAN, HetGNN). The brief descriptions of these baselines are as follows:

• •

  DeepWalk:DeepWalk[22] is a graph representation learning method based on random walks and skip-gram model to learn latent node representations.

• •

  Metapath2vec: Metapath2vec[23] uses meta-path based random walks to construct the heterogeneous neighborhood of nodes and then leverages a heterogeneous skip-gram model to perform node representations. We leverage the meta-paths APVPA, AMDMA and CRC in DBLP, IMDB, and Yelp respectively.

• •

  RHINE: RHINE[24] explore the different structural characteristics of relations in HINs and present two structure-related measures for two distinct categories of relations: IR and AR. We select the same relations in their paper on DBLP and YELP, for IMDB, we select AM, AMD as IR, and TM, TMD, TMA as AR.

• •

  GraphSAGE: GraphSAGE[15] learn node representations through different aggregation function form local neighborhood of nodes. We use the GCN module as the aggregator of GraphSAGE.

• •

  GAT: GAT[16] consider the attention mechanism and measure impacts of different neighbors’ feature information by multi-head self-attention neural network.

• •

  HAN: HAN[9] leverages node level attention and semantic-level attention to respectively learn the importance of neighbors based on same meta-path and different meta-paths. We select meta-paths CRC, RCR for YELP, and meta-paths same as theirs for DBLP, IMDB.

• •

  HetGNN: HetGNN[11] jointly considered heterogeneous neighbors sampling, node heterogeneous contents encoding, type based neighbors aggregation, and heterogeneous types combination.

We use Par2vec[25] to pre-train the text content of nodes and set the dimension of initial feature vector as 128. For the proposed T-GNN, we set all the hidden layer dimensions and final representation dimension of nodes as 128. We use the Adam optimizer with a learning rate of $10^{-3}$ and the l2 penalty parameter $\lambda$ is $10^{-4}$. We set the windows size $k$ of skip-gram model as 2, the size of negative samples as 3 for all datasets, the similarity metric is chosen to Perceptron and the metric space dimension $d_{m}$ is 32. As GAT and HAN only mention semi-supervised objective function for node representations, for a fair comparison, we optimize their models same as our method to learn unsupervised node representations. For the baselines, we set the dimension of nodes in three datasets also as 128 and the other hyper-parameter setting are based on default values or the values specified in their own papers. All the experiments are repeated many times to make sure the results can reflect the performances of methods.

First, we conduct clustering and classification tasks to evaluate the performance of the methods. For DBLP, we label papers by areas of their venues and label authors by their representative areas (the area with the majority of their papers). For IMDB, we label the movies by genres and label actors by the genre with the majority of their acted movies. For YELP, we label the restaurant by type. Then we evaluate these nodes’ representations by clustering and multi-class classification. We learn the node representations on the heterogeneous graphs by each model. For clustering task, we feed node representations into the K-Means algorithm, the number of clusters is set to the true number of classes for each dataset, we evaluate the clustering performance in terms of normalized mutual information (NMI) and adjusted rand index (ARI). For multi-class classification task, the learned node representations are used as the input to a logistic regression classifier, the proportion of training and valid data is set to 50%, 10%, the remaining nodes are used for test. We use both Micro-F1 and Macro-F1 as classification evaluation metrics.

Results. Table II shows the performance evaluation of clustering on three datasets and Table III shows the classification results. The proposed T-GNN model consistently outperform all baselines in terms of two tasks, showing that it can learn more effective node representations than other methods. The relative improvements (%) of T-GNN over the best baselines range from 1.7%-10.7% for clustering task and 1.4%-2.2% for classification task. We can also observe 1) GNN based graph representation learning models achieve better performance than the traditional graph representation learning methods on these two tasks, that is because besides the graph structure information, GNNs can also capture node attributes information to node representations. 2) Heterogeneous models perform better than homogeneous models because they can differentiate different types of relations and capture more semantic information to node representations. 3) T-GNN’s performance is better than two heterogeneous graph neural network models HAN and HetGNN, showing that it can better capture the information of heterogeneous neighborhood.

In this task, we evaluate the inductive capability of our proposed T-GNN on DBLP dataset and compare with the graph neural network based baselines GraphSAGE, GAT, HAN and HetGNN. Specifically, for author nodes and paper nodes which to be evaluated, we randomly set a part of them as the invisible nodes for graph representation learning methods, and use the rest visible nodes and the links between them on the graph to train the models. Then we use the learned models on the whole graph to infer the representations of all invisible nodes. Finally, we use the inferred representations as the input of clustering tasks. For the classification tasks, the visible nodes are used to train the classifier, and the invisible nodes are used to evaluate. The labels and evaluation metrics are the same as the previous clustering and classification tasks. We report the results of the invisible nodes ratio in as 10% and 20% respectively.

Results. Figure 5 shows the performance of GNN models on the inductive learning task. Our proposed T-GNN model achieves the best performance among all the homogeneous and heterogeneous models. Specifically, for the comparison of heterogeneous models, our proposed T-GNN outperforms HAN and HetGNN, because the representations of invisible nodes are mainly inferred by their neighborhood information, but HAN uses meta-path to sample neighbors, ignoring the intermediate nodes; HetGNN uses random walks to sample neighbors, them both unable to process tree structured information and path correlation on multi-hop neighborhood.

In this section, we aim to evaluate the performance of our graph representation learning methods on the link prediction task, which is a practical problem in many applications such as user/item recommendation. We formulate this task as a binary classification problem to predict whether a relation link between two nodes exists. We consider two types of links: links of two author collaborating one paper in DBLP dataset, and links of a user giving a review to an restaurant in YELP dataset. Specifically, for DBLP, we sample the collaborating links before 2013 for training, in 2013 for validation and after 2013 for test. For YELP, we randomly sample 60% reviewing links for training, 10% for validation, and the rest for testing. In training, we remove the links in the validation and testing sets and use graph representation learning methods on graphs to learn the node representations. We use the element-wise multiplication of two candidate nodes’ representations as the link representation, then input link representations into a binary logistic classifier. Also negative links (not connected in graphs) with three times the number of true links are randomly sampled to the training, validation and testing sets. We use AUC and F1 as evaluate metrics.

Results. Table IV shows the prediction results on two datasets. We can find that our proposed T-GNN model achieves the best performance or is comparable to the best methods on the link prediction task. We believe the reason is that our proposed T-GNN model has outstanding ability in preserve heterogeneity into node representations, which helps to overcome the mutual interference of different relations on the node distributions, and improve the quality of node representations.

In order to further verify the effectiveness of the metrics on learning node representations, we design three variant heterogeneous graph representation learning models based on T-GNN and different output models: T-GNN_dp, T-GNN_pe, T-GNN_bi. T-GNN_dp do not use metrics and leverage dot product as the similarity $s(n_{i},n_{j})$ of any two nodes $n_{i}$ and $n_{j}$, T-GNN_pe use the Perceptron as the similarity metric of nodes with different types and T-GNN_bi use Bilinear, both of them are introduced in Section III-C. We evaluate these three models on the node clustering task and classification task. The experiment setting are same as mentioned above. The results are shown in Figure 6. It is evident that using two kinds of metrics achieves better performance. Besides, the performance of T-GNN_pe is better than T-GNN_bi. We believe the reason is that there are more parameters in Perceptron metric than Bilinear metric, leading to Perceptron metric is better in preserve the complicated proximities between multiple nodes.

We have discussed that our model can embed each type of nodes into type-specific space with distinct distribution. In this section, we compare our model with metapath2vec and GraphSAGE by visualizing node representations with different types. Specifically, we first learn the node representations in the year of 2015 of four venue: CVPR, ACL, KDD, SIGMOD in DBLP data, representing four research areas. Then we use t-SNE to respectively project author representations and paper representations into 2-dimensional spaces.

The results are shown in Figure 7. We can observe that while metapath2vec cluster papers and authors into small groups, some nodes belonging to the same research area are far away from each other, and some belonging to different areas are mixed with each other, GraphSAGE can roughly partition nodes with different research areas, but the boundaries between different clusters are not sharp, and many nodes overlap at the same points. We can observe that in the visualization of T-GNN, 1) the representations of paper nodes in the same area cluster closely and can be well distinguished from each other. Author nodes are also embedded well comparing with other two methods, but some of them are embedded on the boundary between different clusters, which is because some authors may have multiple research areas. 2) Authors and papers in their own space have independent distributions, showing high intra-class similarities and distinct boundaries between different research areas.