Domain Generalization Deep Graph Transformation

Abstract

Graph transformation that predicts graph transition from one mode to another is an important and common problem. Despite much recent progress in developing advanced graph transformation techniques, the fundamental assumption typically required in machine-learning models that the testing and training data preserve the same distribution does not always hold. As a result, domain generalization graph transformation that predicts graphs not available in the training data is under-explored, with multiple key challenges to be addressed including (1) the extreme space complexity when training on all input-output mode combinations, (2) difference of graph topologies between the input and the output modes, and (3) how to generalize the model to target domains that are not in the training data. To fill the gap, we propose a multi-input, multi-output, hypernetwork-based graph neural network (MultiHyperGNN) that employs a encoder and a decoder to encode both input and output modes and semi-supervised link prediction to enhance the graph transformation task. Instead of training on all mode combinations, MultiHyperGNN preserves a constant space and polynomial computational complexity with the encoder and the decoder produced by two novel hypernetworks. Comprehensive experiments show that MultiHyperGNN has a superior performance than competing models in both prediction and domain generalization tasks.

Motivation

Graph is a ubiquitous data structure characterized by node attributes and the graph topology that describe objects and their relationships. Many tasks on graphs ask for predicting a graph (i.e., graph topology or node attributes) from another one. Applications of such graph transformation include traffic forecasting between two time stamps based on traffic flow, fraud detection between transactional periods, and chemical reaction prediction according to molecular structures.

Despite of a wide spectrum of applications, graph transformation still faces major issues such as insufficient samples of graph pairs for training the model. For instance, as shown in the figure above, if the model is trained to predict gene-gene network on specific tissue pairs (e.g., from heart and blood to brain, from blood to muscle), but in testing process, one may want to generalize the model to unseen tissue pairs (e.g., from heart to muscle) or even to tissues unavailable in the training data. If so, the performance of the graph transformation model may deteriorate due to domain distribution gaps. Therefore, it is imperative and crucial to improve the generalization ability of graph transformation models to generalize the learned graph transformation to other (unseen) graph transformations, namely domain generalization graph transformation.

Domain generalization graph transformation, nevertheless, is still under-explored by the machine-learning community due to the following challenges: (1) High complexity in the training process. To learn the distribution of graph (or mode) pairs in training data, we need to learn the model by traversing on all combinations of input modes to predict all combinations of output modes. In this case, the training complexity would be exponential if we train a single model for all possible input-output mode combinations; (2) Graph transformation between topologically different modes. The existing works regarding graph transformation predict node attributes conditioning on either the same topology or the same set of nodes of input and output modes. Performing graph transformation across modes with varying topologies, including different edges and even varying graph sizes, is a difficult task. Main challenges include how to learn the mapping between distinct topologies and how to incorporate the topology of each mode to enhance the prediction task; (3) Learning graph transformation involving unseen domains and lack of training data. Graph transformation usually requires both the source and target domains to be visible and have adequate training data to train a sophisticated model. However, during the prediction phase, we may be asked to predict a graph in an unseen target domain. Learning such transformation mapping without any training data is an exceedingly challenging task.

To fill the gap, we propose a novel framework for domain generalization graph transformation via a multi-input, multi-output hypernetwork-based graph neural networks (MultiHyperGNN).

• We propose a novel multi-input, multi-output framework of graph transformation for predicting node attributes across multiple input and output modes. We introduced a novel framework leveraging a multi-input, multi-output training strategy, significantly reducing the space complexity from exponential to constant during training.

• We develop an encoder and a decoder for graph transformation between topologically different input and output modes, respectively. Additionally, our model conducts semi-supervised link prediction to complete the output graph, facilitating generalization to all nodes in the output mode. 

• We design two novel hypernetworks that produce the encoder and the decoder for domain generalization. Mode-specific meta information serves as the input to guide the hypernetwork to produce the corresponding encoder or decoder, and generalize to unseen target domains. 

• We conduct extensive experiments to demonstrate the effectiveness of MultiHyperGNN on three real-world datasets. The results show that MultiHyperGNN is superior than competing models.

Problem definition

Model framework

Since the size of the source domain S is O(3^N) as it can contain any combination of modes, leading to an exponential space complexity of O(3^N). MultihyperGNN reduces the space complexity to O(1) as it only needs to train two hypernworks that can process arbitrary combinations of input and output modes during training. 

Algorithms of learning phase

Experiments