  Graph neural architecture search (NAS) has gained popularity in automatically
designing powerful graph neural networks (GNNs) with relieving human efforts.
However, existing graph NAS methods mainly work under the homophily assumption
and overlook another important graph property, i.e., heterophily, which exists
widely in various real-world applications. To date, automated heterophilic
graph learning with NAS is still a research blank to be filled in. Due to the
complexity and variety of heterophilic graphs, the critical challenge of
heterophilic graph NAS mainly lies in developing the heterophily-specific
search space and strategy. Therefore, in this paper, we propose a novel
automated graph neural network on heterophilic graphs, namely Auto-HeG, to
automatically build heterophilic GNN models with expressive learning abilities.
Specifically, Auto-HeG incorporates heterophily into all stages of automatic
heterophilic graph learning, including search space design, supernet training,
and architecture selection. Through the diverse message-passing scheme with
joint micro-level and macro-level designs, we first build a comprehensive
heterophilic GNN search space, enabling Auto-HeG to integrate complex and
various heterophily of graphs. With a progressive supernet training strategy,
we dynamically shrink the initial search space according to layer-wise
variation of heterophily, resulting in a compact and efficient supernet. Taking
a heterophily-aware distance criterion as the guidance, we conduct heterophilic
architecture selection in the leave-one-out pattern, so that specialized and
expressive heterophilic GNN architectures can be derived. Extensive experiments
illustrate the superiority of Auto-HeG in developing excellent heterophilic
GNNs to human-designed models and graph NAS models.
