Self-supervised Auxiliary Learning with Meta-paths for Heterogeneous Graphs

Introduction

Graph neural networks have been proven effective to learn representations for various tasks such as node classification , link prediction , and graph classification . The powerful representation yields state-of-the-art performance in a variety of applications including social network analysis , citation network analysis , visual understanding , recommender systems , physics , and drug discovery . Despite the wide operating range of graph neural networks, employing auxiliary (pre-text) tasks has been less explored for further improving graph representation learning.

Pre-training with an auxiliary task is a common technique for deep neural networks. Indeed, it is the de facto standard step in natural language processing and computer vision to learn a powerful backbone networks such as BERT and ResNet leveraging large datasets such as BooksCorpus , English Wikipedia, and ImageNet . The models trained on the auxiliary task are often beneficial for the primary (target) task of interest. Despite the success of pre-training, few approaches have been generalized to graph-structured data due to their fundamental challenges. First, graph structure (e.g., the number of nodes/edges, and diameter) and its meaning can significantly differ between domains. So the model trained on an auxiliary task can harm generalization on the primary task, i.e., negative transfer . Also, many graph neural networks are transductive approaches. This often makes transfer learning between datasets inherently infeasible. So, pre-training on the target dataset has been proposed using auxiliary tasks: graph kernel , graph reconstruction , and attribute masking . These assume that the auxiliary tasks for pre-training are carefully selected with substantial domain knowledge and expertise in graph characteristics to assist the primary task. Since most graph neural networks operate on homogeneous graphs, which have a single type of nodes and edges, the previous pre-training/auxiliary tasks are not specifically designed for heterogeneous graphs, which have multiple types of nodes and edges. Heterogeneous graphs commonly occur in real-world applications, for instance, a music dataset has multiple types of nodes (e.g., user, song, artist) and multiple types of relations (e.g., user-artist, song-film, song-instrument).

In this paper, we proposed a framework to train a graph neural networks with automatically selected auxiliary self-supervised tasks which assist the target task without additional data and labels. Our approach first generates meta-paths from heterogeneous graphs without manual labeling and train a model with meta-path prediction to assist the primary task such as link prediction and node classification. This can be formulated as a meta-learning problem. Furthermore, our method can be adopted to existing GNNs in a plug-in manner, enhancing the model performance.

Our contribution is threefold: (i) We propose a self-supervised learning method on a heterogeneous graph via meta-path prediction without additional data. (ii) Our framework automatically selects meta-paths (auxiliary tasks) to assist the primary task via meta-learning. (iii) We develop Hint Network that helps the learner network to benefit from challenging auxiliary tasks. To the best of our knowledge, this is the first auxiliary task with meta-paths specifically designed for leveraging heterogeneous graph structure. Our experiment shows that meta-path prediction improves the representational power and the gain can be further improved to explicitly optimize the auxiliary tasks for the primary task via meta-learning and the Hint Network, built on various state-of-the-art GNNs.

Related Work

Graph Neural Networks have provided promising results for various tasks . Bruna et al. proposed a neural network that performs convolution on the graph domain using the Fourier basis from spectral graph theory. In contrast, non-spectral (spatial) approaches have been developed . Inspired by self-supervised learning and pre-training in computer vision and natural language processing, pre-training for GNNs has been recently proposed . Recent works show promising results that self-supervised learning can be effective for GNNs . Hu et al. have introduced several strategies for pre-training GNNs such as attribute masking and context prediction. Separated from the pre-training and fine-tuning strategy, has studied multi-task learning and analyzed why the pretext tasks are useful for GNNs. However, one problem with both pre-training and multi-task learning strategies is that all the auxiliary tasks are not beneficial for the downstream applications. So, we studied auxiliary learning for GNNs that explicitly focuses on the primary task.

Auxiliary Learning is a learning strategy to employ auxiliary tasks to assist the primary task. It is similar to multi-task learning, but auxiliary learning cares only the performance of the primary task. A number of auxiliary learning methods are proposed in a wide range of tasks . AC-GAN proposed an auxiliary classifier for generative models. Recently, Meta-Auxiliary Learning proposes an elegant solution to generate new auxiliary tasks by collapsing existing classes. However, it cannot be applicable to some tasks such as link prediction which has only one positive class. Our approach generates meta-paths on heterogeneous graphs to make new labels and trains models to predict meta-paths as auxiliary tasks.

Meta-learning aims at learning to learn models efficiently and effectively, and generalizes the learning strategy to new tasks. Meta-learning includes black-box methods to approximate gradients without any information about models , optimization-based methods to learn an optimal initialization for adapting new tasks , learning loss functions and metric-learning or non-parametric methods for few-shot learning . In contrast to classical learning algorithms that generalize across samples, meta-learning generalizes across tasks. In this paper, we use meta-learning to learn a concept across tasks and transfer the knowledge from auxiliary tasks to the primary task.

Method

The goal of our framework is to learn with multiple auxiliary tasks to improve the performance of the primary task. In this work, we demonstrate our framework with meta-path predictions as auxiliary tasks. But our framework could be extended to include other auxiliary tasks. The meta-paths capture diverse and meaningful relations between nodes on heterogeneous graphs . However, learning with auxiliary tasks has multiple challenges: identifying useful auxiliary tasks, balancing the auxiliary tasks with the primary task, and converting challenging auxiliary tasks into solvable (and relevant) tasks. To address the challenges, we propose SELf-supervised Auxiliary LeaRning (SELAR). Our framework consists of two main components: 1) learning weight functions to softly select auxiliary tasks and balance them with the primary task via meta-learning, and 2) learning Hint Networks to convert challenging auxiliary tasks into more relevant and solvable tasks to the primary task learner.

Most existing graph neural networks have been studied focusing on homogeneous graphs that have a single type of nodes and edges. However, in real-world applications, heterogeneous graphs , which have multiple types of nodes and edges, commonly occur. Learning models on the heterogeneous graphs requires different considerations to effectively represent their node and edge heterogeneity.

Heterogeneous graph . Let $G=(V,E)$ be a graph with a set of nodes $V$ and edges $E$. A heterogeneous graph is a graph equipped with a node type mapping function $f_{v}:V\rightarrow\mathcal{T}^{v}$ and an edge type mapping function $f_{e}:E\rightarrow\mathcal{T}^{e}$, where $\mathcal{T}^{v}$ is a set of node types and $\mathcal{T}^{e}$ is a set of edge types. Each node $v_{i}\in V$ (and edge $e_{ij}\in E$ resp.) has one node type, i.e., $f_{v}(v_{i})\in\mathcal{T}^{v}$, (and one edge type $f_{e}(e_{ij})\in\mathcal{T}^{e}$ resp.). In this paper, we consider the heterogeneous graphs with $|\mathcal{T}^{e}|>1$ or $|\mathcal{T}^{v}|>1$. When $|\mathcal{T}^{e}|=1$ and $|\mathcal{T}^{v}|=1$, it becomes a homogeneous graph.

Meta-Path is a path on a heterogeneous graph $G$ that a sequence of nodes connected with heterogeneous edges, i.e., ${v}_{1}\xrightarrow{t_{1}}{v}_{2}\xrightarrow{t_{2}}\ldots\xrightarrow{t_{l}}{v}_{l+1}$, where $t_{l}\in\mathcal{T}^{e}$ denotes an $l$-th edge type of the meta-path. The meta-path can be viewed as a composite relation $R=t_{1}\circ t_{2}\ldots\circ t_{l}$ between node ${v}_{1}$ and ${v}_{l+1}$, where $R_{1}\circ R_{2}$ denotes the composition of relation $R_{1}$ and $R_{2}$. The definition of meta-path generalizes multi-hop connections and is shown to be useful to analyze heterogeneous graphs. For instance, in Book-Crossing dataset, ‘user-item-written.series-item-user’ indicates that a meta-path that connects users who like the same book series.

We introduce meta-path prediction as a self-supervised auxiliary task to improve the representational power of graph neural networks. To our knowledge, the meta-path prediction has not been studied in the context of self-supervised learning for graph neural networks in the literature.

Let $\mathbf{X}\in\textbf{R}^{|V|\times d}$ and $\mathbf{Z}\in\textbf{R}^{|V|\times d^{\prime}}$ be input features and their hidden representations learnt by GNN $f$, i.e., $\mathbf{Z}=f(\boldsymbol{X};\mathbf{w},\boldsymbol{A})$, where $\mathbf{w}$ is the parameter for $f$, and $\mathbf{A}\in\textbf{R}^{|V|\times|V|}$ is the adjacency matrix. Then link prediction and meta-path prediction are obtained by a simple operation as

where $\Phi_{t}$ is the task-specific network for task $t\in\mathcal{T}$ and $z_{u}$ and $z_{v}$ are the node embeddings of node $u$ and $v$. e.g., $\Phi_{0}$ (and $\Phi_{1}$ resp.) for link prediction (and the first type of meta-path prediction resp.).

The architecture is shown in Fig. 1. To optimize the model, as the link prediction, cross entropy is used. The graph neural network $f$ is shared by the link prediction and meta-path predictions. As any auxiliary learning methods, the meta-paths (auxiliary tasks) should be carefully chosen and properly weighted so that the meta-path prediction does not compete with link prediction especially when the capacity of GNNs is limited. To address these issues, we propose our framework that automatically selects meta-paths and balances them with the link prediction via meta-learning.

2 Self-Supervised Auxiliary Learning

Our framework SELAR is learning to learn a primary task with multiple auxiliary tasks to assist the primary task. This can be formally written as

where $\mathcal{L}^{pr}(\cdot)$ is the primary task loss function to evaluate the trained model $f(x;\mathbf{w}^{\ast}(\Theta))$ on meta-data (a validation for meta-learning ) $D^{pr}$ and $\mathcal{L}^{pr+au}$ is the loss function to train a model on training data $D^{pr+au}$ with the primary and auxiliary tasks. To avoid cluttered notation, $f$, $x$, and $y$ are omitted. Each task $\mathcal{T}_{t}$ has $N_{t}$ samples and $\mathcal{T}_{0}$ and $\{\mathcal{T}_{t}\}_{t=1}^{T}$ denote the primary and auxiliary tasks respectively. The proposed formulation in Eq. (2) learns how to assist the primary task by optimizing $\Theta$ via meta-learning. The nested optimization problem given $\Theta$ is a regular training with properly adjusted loss functions to balance the primary and auxiliary tasks. The formulation can be more specifically written as

To circumvent the difficulty of the bi-level optimization, as previous works in meta-learning we approximate it with the updated parameters $\hat{\mathbf{w}}$ using the gradient descent update as

where $\alpha$ is the learning rate for $\mathbf{w}$. We do not numerically evaluate $\hat{\mathbf{w}}^{k}(\Theta)$ instead we plug the computational graph of $\hat{\mathbf{w}}^{k}$ in $\mathcal{L}^{pr}(\mathbf{w}^{\ast}(\Theta))$ to optimize $\Theta$. Let $\nabla_{\Theta}\mathcal{L}^{pr}(\mathbf{w}^{\ast}(\Theta^{k}))$ be the gradient evaluated at $\Theta^{k}$. Then updating parameters $\Theta$ is given as

where $\beta$ is the learning rate for $\Theta$. This update allows softly selecting useful auxiliary tasks (meta-paths) and balance them with the primary task to improve the performance of the primary task. Without balancing tasks with the weighting function $\mathcal{V}(\cdot;\Theta)$, auxiliary tasks can dominate training and degrade the performance of the primary task.

The model parameters $\mathbf{w}^{k}$ for tasks can be updated with optimized $\Theta^{k+1}$ in (7) as

Remarks. The proposed formulation can suffer from the meta-overfitting meaning that the parameters $\Theta$ to learn weights for softly selecting meta-paths and balancing the tasks with the primary task can overfit to the small meta-dataset. In our experiment, we found that the overfitting can be alleviated by meta-validation sets . To learn $\Theta$ that is generalizable across meta-training sets, we optimize $\Theta$ across $k$ different meta-datasets like $k$-fold cross validation using the following equation:

where $D^{pr(meta)}\sim CV$ is a meta-dataset from cross validation. We used 3-fold cross validation and the gradients of $\Theta$ w.r.t different meta-datasets are averaged to update $\Theta^{k}$, see Algorithm 1. The cross validation is crucial to alleviate meta-overfitting and more discussion is Section 4.3.

3 Hint Networks

Meta-path prediction is generally more challenging than link prediction and node classification since it requires the understanding of long-range relations across heterogeneous nodes. The meta-path prediction gets more difficult when mini-batch training is inevitable due to the size of datasets or models. Within a mini-batch, important nodes and edges for meta-paths are not available. Also, a small learner network, e.g., two-layer GNNs, with a limited receptive field, inherently cannot capture long-range relations. The challenges can hinder representation learning and damage the generalization of the primary task. We proposed a Hint Network (HintNet) which makes the challenge tasks more solvable by correcting the answer with more information at the learner’s need. Specifically, in our experiments, the HintNet corrects the answer of the learner with its own answer from the augmented graph with hub nodes, see Fig. 2.

The amount of help (correction) by HintNet is optimized maximizing the learner’s gain. Let $\mathcal{V}_{H}(\cdot)$ and $\Theta_{H}$ be a weight function to determine the amount of hint and its parameters which are optimized by meta-learning. Then, our formulation with HintNet is given as

Experiments

We evaluate our proposed methods on four public benchmark datasets on heterogeneous graphs. Our experiments answer the following research questions: Q1. Is meta-path prediction effective for representation learning on heterogeneous graphs? Q2. Can the meta-path prediction be further improved by the proposed methods (e.g., SELAR, HintNet)? Q3. Why are the proposed methods effective, any relation with hard negative mining?

Datasets. We use two public benchmark datasets from different domains for link prediction: Music dataset Last-FM and Book dataset Book-Crossing, released by KGNN-LS , RippleNet . We use two datasets for node classification: citation network datasets ACM and Movie dataset IMDB, used by HAN for node classification tasks. ACM has three types nodes (Paper(P), Author(A), Subject(S)), four types of edges (PA, AP, PS, SP) and labels (categories of papers). IMDB contains three types of nodes (Movie (M), Actor (A), Director (D)), four types (MA, AM, MD, DM) of edges and labels (genres of movies). ACM and IMDB have node features, which are bag-of-words of keywords and plots. Dataset details are in the supplement.

Baselines. We evaluate our methods with five graph neural networks : GCN , GAT , GIN , SGConv and GTN . Our methods can be applied to both homogeneous graphs and heterogeneous graphs. We compare four learning strategies: Vanilla, standard training of base models only with the primary task samples; w/o meta-path, learning a primary task with sample weighting function $\mathcal{V}(\xi;\Theta)$; w/ meta-path, training with the primary task and auxiliary tasks (meta-path prediction) with a standard loss function; SELAR proposed in Section 3.2, learning the primary task with optimized auxiliary tasks by meta-learning; SELAR+Hint introduced in Section 3.3. In all the experiments, we report the mean performance of three independent runs. Implementation details are in the supplement. Our experiments were mainly performed based on NAVER Smart Machine Learning platform (NSML) .

We used five types of meta-paths of length 2 to 4 for auxiliary tasks. Table 1 shows that our methods consistently improve link prediction performance for all the GNNs, compared to the Vanilla and the method using Meta-Weight-Net only without meta-paths (denoted as w/o meta-path). Overall, a standard training with meta-paths shows 1.1% improvement on average on both Last-FM and Book-Crossing whereas meta-learning that learns sample weights degrades on average on Last-FM and improves only 0.6% on average on Book-Crossing, e.g., GCN, SGC and GTN on Last-FM and GCN and SGC on Book-Crossing, show degradation 0.2% compared to the standard training (Vanilla). As we expected, SELAR and SELAR with HintNet provide more optimized auxiliary learning resulting in 1.9% and 2.0% absolute improvement on Last-FM and 2.6% and 2.7% on the Book-Crossing dataset. Further, in particular, GIN on Book-crossing, SELAR and SELAR+Hint provide $\sim$5.5% and $\sim$5.3% absolute improvement compared to the vanilla algorithm.

2 Learning Node Classification with meta-path prediction

Similar to link prediction above, our SELAR consistently enhances node classification performance of all the GNN models and the improvements are more significant on IMDB which is larger than the ACM dataset. We believe that ACM dataset is already saturated and the room for improvement is limited. However, our methods still show small yet consistent improvement over all the architecture on ACM. We conjecture that the efficacy of our proposed methods differs depending on graph structures. However, it is worth noting that introducing meta-path prediction as auxiliary tasks remarkably improves the performance of primary tasks such as link and node prediction with consistency compared to the existing methods. “w/o meta-path”, the meta-learning to learn sample weight function on a primary task shows marginal degradation in five out of eight settings. Remarkably, SELAR improved the F1-score of GAT on the IMDB by (4.46%) compared to the vanilla learning scheme.

3 Analysis of Weighting Function and Meta-overfitting

The effectiveness of meta-path prediction and the proposed learning strategies are answered above. To address the last research question Q3. why the proposed method is effective, we provide analysis on the weighting function $\mathcal{V}(\xi;\Theta)$ learned by our framework. Also, we show the evidence that meta-overfitting occurs and can be addressed by cross-validation as in Algorithm 1.

Meta cross-validation, i.e., cross-validation for meta-learning, helps to keep weighting function from over-fitting on meta data. Table 3 evidence that our algorithms as other meta-learning methods can overfit to meta-data. As in Algorithm 1, our proposed methods, both SELAR and SELAR with HintNet, with cross-validation denoted as ‘3-fold’ alleviates the meta-overfitting problem and provides a significant performance gain, whereas without meta cross-validation denoted as ‘1-fold’ the proposed method can underperform the vanilla training strategy.

Conclusion

We proposed meta-path prediction as self-supervised auxiliary tasks on heterogeneous graphs. Our experiments show that the representation learning on heterogeneous graphs can benefit from meta-path prediction which encourages to capture rich semantic information. The auxiliary tasks can be further improved by our proposed method SELAR, which automatically balances auxiliary tasks to assist the primary task via a form of meta-learning. The learnt weighting function identifies more beneficial meta-paths for the primary tasks. Within a task, the weighting function can adjust the cross entropy like the focal loss, which focuses on hard examples by decreasing weights for easy samples. Moreover, when it comes to challenging and remotely relevant auxiliary tasks, our HintNet helps the learner by correcting the learner’s answer dynamically and further improves the gain from auxiliary tasks. Our framework based on meta-learning provides learning strategies to balance primary task and auxiliary tasks, and easy/hard (and positive/negative) samples. Interesting future directions include applying our framework to other domains and various auxiliary tasks. Our code is publicly available at https://github.com/mlvlab/SELAR.

Acknowledgements. This work was partly supported by NAVER Corp. and Institute for Information & communications Technology Planning & Evaluation (IITP) grants funded by the Korea government (MSIT): the Regional Strategic Industry Convergence Security Core Talent Training Business (No.2019-0-01343) and the ICT Creative Consilience Program (IITP-2020-0-01819).

Broader Impact

We thank NeurIPS2020 for this opportunity to revisit the broader impact of our work and the potential societal consequence of machine learning researches. Our work is a general learning method to benefit from auxiliary tasks. One interesting finding is that meta-path prediction can be an effective self-supervised task to learn more power representation of heterogeneous graphs. Nowadays, people use social media (e.g., Facebook, Twitter, etc.) on a daily basis. Also, people watch movies and TV-shows online and purchase products on Amazon. All this information can be represented as heterogeneous graphs. We believe that our meta-path auxiliary tasks will benefit the customers with improved services. For instance, more accurate recommender systems will save customers’ time and provide more relevant contents and products. We believe that there is no direct negative consequence of this research. We proposed how to train models with auxiliary tasks. We did not make any algorithms for specific applications. So, no one will be put at a disadvantage from our work. No direct negative consequence of a failure of the system is expected. We used four datasets Last-FM, Book-Crossing, ACM, and IMDB. They may not represent all the population on the earth but our experiments did not leverage any biases in the datasets. We believe that our method will be as effective as we reported in the paper on different datasets from different populations.

References