  In this paper, we propose a novel framework to automatically utilize
task-dependent semantic information which is encoded in heterogeneous
information networks (HINs). Specifically, we search for a meta graph, which
can capture more complex semantic relations than a meta path, to determine how
graph neural networks (GNNs) propagate messages along different types of edges.
We formalize the problem within the framework of neural architecture search
(NAS) and then perform the search in a differentiable manner. We design an
expressive search space in the form of a directed acyclic graph (DAG) to
represent candidate meta graphs for a HIN, and we propose task-dependent type
constraint to filter out those edge types along which message passing has no
effect on the representations of nodes that are related to the downstream task.
The size of the search space we define is huge, so we further propose a novel
and efficient search algorithm to make the total search cost on a par with
training a single GNN once. Compared with existing popular NAS algorithms, our
proposed search algorithm improves the search efficiency. We conduct extensive
experiments on different HINs and downstream tasks to evaluate our method, and
experimental results show that our method can outperform state-of-the-art
heterogeneous GNNs and also improves efficiency compared with those methods
which can implicitly learn meta paths.
