Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs

Abstract

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. In contrast, heterophily, which shares an opposite property of graph data to homophily, exists widely in various real-world applications, eg, online social networks and transactions. Despite its vital role in the web socio-economic system, 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.

Publication
The ACM Web Conference 2023, WWW-23, Austin, Texas, USA, April 30 - May 4, 2023 (CORE A*)
Xin Zheng
Xin Zheng
PhD Students @ Monash (04/2021-)

My research interests include computer vision, machine learning, adversarial attack, and graph analysis.

Miao Zhang
Miao Zhang
Professor @ Harbin Institute of Technology

My research interests include Neural Architecture Search(NAS), Bayesian Optimization, High-dimensional Data, and Evolutionary Algorithm.

Shirui Pan
Shirui Pan
Professor | ARC Future Fellow

My research interests include data mining, machine learning, and graph analysis.