Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs
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.
Xin Zheng, Miao Zhang, Chunyang Chen, Qin Zhang, Chuan Zhou, Shirui Pan
# 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 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.

graph neural architecture search, graph neural networks, heterophily, diverse message-passing, progressive supernet training +
Footnote †: journal: Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted Ac Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Ac Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted on Accepted Ac Ac Accepted on Accepted on Accepted on Accepted Ac Ac Accepted on Accepted on Accepted on Ac Accepted on Accepted Ac Ac Accepted on Accepted on Accepted Ac Accepted on Accepted on Ac Accepted on Accepted Ac Ac Accepted on Ac Accepted on Accepted on Ac Accepted Ac Ac Accepted on Ac Accepted on Accepted Ac Ac Accepted on Ac Accepted Ac Ac Accepted on Ac Accepted on Ac Accepted Ac Ac Accepted on Ac Accepted Ac Ac Accepted on Ac Accepted Ac Ac Accepted on Ac Accepted Ac Ac Accepted on Ac Accepted Ac Ac Ac Accepted on Ac Accepted Ac Ac Ac Accepted on Ac Accepted Ac Ac Ac Accepted
while heterophilic graphs expect discriminative node representation learning to diversely extract information from similar and dissimilar neighbors.

Very recently, a few researchers divert their attention to develop heterophilic GNNs, typically by introducing higher-order neighbors (Wang et al., 2017) or modelling homophily and heterophily separately in the message passing scheme (Beng et al., 2017). Nevertheless, current heterophilic GNNs highly rely on the knowledge of experts to manually design models for graphs with different degrees of heterophily. For one thing, this process would cost many human efforts and the performance of derived GNNs would be limited by expertise. For another thing, real-world heterophilic graphs generally show the significant complexity and variety in terms of graph structure. It would be harder to artificially customize GNNs to make them adapt to various heterophilic graphs.

In light of this, automated graph neural network learning via neural architecture search (NAS) (Beng et al., 2017; Chen et al., 2017; Li et al., 2017; Li et al., 2018; Li et al., 2019; Li et al., 2019; Li et al., 2019), a line of research for saving human efforts in designing effective GNNs, would be a feasible way of tackling the dilemma of heterophilic GNN development. Through learning in well-designed search spaces with efficient search strategies, automated GNNs via NAS have achieved promising progress on various graph data analysis tasks (Li et al., 2017; Li et al., 2018; Li et al., 2019; Li et al., 2019; Li et al., 2019). However, existing graph NAS studies, _e.g._, GraphNAS (Li et al., 2019) and SANE (Li et al., 2019), are all constrained under the homophily assumption. To the best of our knowledge, there is still a research blank in developing heterophilic graph NAS for automated heterophilic graph learning. The most straightforward way to implement heterophilic graph NAS might be replacing the homophilic operations in existing homophilic search spaces with heterophilic GNN operations, followed by universal gradient-based search strategies. But this direct solution would incur some issues: First, it is difficult to determine what heterophilic operations are beneficial and whether certain homophilic operations should be kept for facilitating heterophilic graph learning, since the heterophilic graphs might be various and complex with different degrees of heterophily. Second, simply making existing universal search strategies adapt to new-defined heterophilic search spaces would limit the searching performance, resulting in suboptimal heterophilic GNN architectures. The heterophily should be integrated into the searching process for architecture optimization as well.

To tackle all the above-mentioned challenges of heterophilic graph NAS, in this paper, we propose a novel automated graph neural network on heterophilic graphs, namely Auto-HeG, to effectively learn heterophilic node representations via heterophily-aware graph neural architecture search. To the best of our knowledge, this is the first automated heterophilic graph learning method, and our theme is to explicitly incorporate heterophily into all stages of automatic heterophily graph learning, containing search space design, supernet training, and architecture selection. **For search space design:** By integrating joint micro-level and macro-level designs, Auto-HeG first builds a comprehensive heterophilic search space through the diverse message-passing scheme, enabling it to incorporate the complexity and diversity of heterophily better. At the micro-level, Auto-HeG conducts non-local neighbor extension, ego-neighbor separation, and diverse message passing; At the macro-level, it introduces adaptive layer-wise combination operations. **For supernet training:** To narrow the scope of candidate operations in the proposed heterophilic search space, Auto-HeG presents a progressive supernet training strategy to dynamically shrink the initial search space according to layer-wise variation of heterophily, resulting in a compact and efficient supernet. **For architecture selection:** Taking heterophily as the specific guidance, Auto-HeG derives a novel heterophily-aware distance as the criterion to select effective operations in the leave-one-out pattern, leading to specialized and expressive heterophilic GNN architectures. Extensive experiments on the node classification task illustrate the superior performance of the proposed Auto-HeG to human-designed models and graph NAS models. In summary, our contributions are listed as follows:

* We propose a novel automated graph neural network on heterophilic graphs by means of heterophily-aware graph neural architecture search, namely **Auto-HeG**, to the best of our knowledge, for the first time.
* To integrate the complex and various heterophily explicitly, we build a comprehensive heterophilic GNN search space that incorporates non-local neighbor extension, ego-neighbor separation, diverse message passing, and layer-wise combination at the micro-level and the macro-level.
* To learn a compact and effective heterophilic supernet, we introduce a progressive supernet training strategy to dynamically shrink the initial search space, enabling the narrowed searching scope with layer-wise heterophily variation.
* To select optimal GNN architectures specifically instructed by heterophily, we derive a heterophily-aware distance criterion to develop powerful heterophilic GNNs in the leave-one-out manner and extensive experiments verify the superiority of Auto-HeG.

## 2. Related Work

_Graph Neural Networks with Heterophily:_ Existing heterophilic GNNs mainly work on two aspects (Li et al., 2019): non-local neighbor extension (Beng et al., 2017; Chen et al., 2017; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019) and GNN architecture refinement (Beng et al., 2017; Chen et al., 2017; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019). In detail, non-local neighbor extension methods focus on exploring the informative neighbor set beyond local topology. In contrast, GNN architecture refinement methods design heterophys-specific message-passing models to learn discriminative node representations. Typically, Mixhop (Beng et al., 2017) and H2GCN (Wang et al., 2017) introduced higher-order neighbor mixing of local one-hop neighbors and non-local \(K\)-hop neighbors to learn discriminative central node representations. And Geom-GCN (Li et al., 2019) defined the split 2D Euclidean geometry locations as the geometric relationships with different degrees of heterophily, enabling it to discover potential neighbors for further effective aggregation. In contrast, FAGCN (Beng et al., 2017) developed diverse aggregation functions by introducing low-pass and high-pass filters, corresponding to learning homophily and heterophily, respectively. Besides, GCNII (Chen et al., 2017) and GPR-GNN (Wang et al., 2017) considered the layer-wise representation integration to boost the performance of GNNs with heterophily. Despite the promising development, these heterophilic GNNs highly rely on the expertise to manually design GNNs for tackling the complex and diverse heterophily. For one thing, it would cost exhausted human efforts. For another thing, the design scopes and flexibility would be constrained by expert
knowledge, leading to limited model performance. In light of this, we are the first to propose an automated graph neural architecture search framework for heterophilic graphs, to significantly save human efforts and automatically derive powerful heterophilic GNN architectures with excellent learning abilities.

Graph Neural Architecture SearchGraph NAS has greatly enlarged the design picture of automated GNN development for discovering excellent and powerful models (Garfani et al., 2017; Goyal et al., 2017; Goyal et al., 2017; Goyal et al., 2017; Goyal et al., 2018; Goyal et al., 2018; Goyal et al., 2019; Goyal et al., 2019). Generally, the development of graph NAS methods focuses on two crucial research aspects: search space and search strategy. The former defines architecture and functional operation candidates in a set space, and the latter explores the powerful model components in the defined search space. Typically, GraphNAS (Goyal et al., 2017) and AGNN (Goyal et al., 2019) constructed the micro-level search space containing classical GNN components and related hyper-parameters, followed by architecture controllers based reinforcement learning (RL) search strategy. And SNAG (Goyal et al., 2019) further simplified GraphNAS at the micro-level and introduced the macro-level inter-layer architecture connections. Based on this search space, SANE (Goyal et al., 2017) implemented DARTS (Goyal et al., 2017), a gradient-based search strategy, to automatically derive effective GNN architectures on graphs in a differential way. Nevertheless, current graph NAS methods are still constrained under the homophily assumption and cannot learn explicitly and effectively on graphs with complex and diverse heterophily. Therefore, we draw inspiration from the lines of NAS research on search space shrinking (Garfani et al., 2017; Goyal et al., 2018; Goyal et al., 2018; Goyal et al., 2019), supernet optimization (Goyal et al., 2017; Goyal et al., 2019), and architecture selection (Goyal et al., 2019), and importantly extend them to the development of automated heterophilic GNNs. Our critical goal is to build a well-designed search space with a customized search strategy via graph NAS, to explicitly integrate the heterophily into full stages of automated heterophilic GNN development.

## 3. Auto-Heg: Automated Graph Neural Network on Heterophilic Graphs

### Preliminary.

Uniform Message PassingLet \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) be an undirected, unweighted graph where \(\mathcal{V}=\{v_{1},\cdots,v_{|\mathcal{V}|}\}\) is the node set and \(\mathcal{E}\in\mathcal{V}\times\mathcal{V}\) is the edge set. The neighbor set of node \(v\) is \(\mathcal{N}(v)=\{u:(v,u)\in\mathcal{E}\}\), and initial node features are represented by \(\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times d_{0}}\) with \(d_{0}\)-dimension features. For the uniform message passing scheme under the homophily assumption, node representations of GNNs are learned by first aggregating the messages from local neighbors, and then updating the ego-node representations by combining the aggregated messages with themselves (Sutskever, 2017). This process can be denoted as:

\[\mathbf{m}_{v}^{(l)}=\text{AGG}^{(l)}((\mathbf{h}_{u}^{(l-1)}:u \in\mathcal{N}(v))),\] \[\mathbf{h}_{v}^{(l)}=\text{UPDATE}^{(l)}(\mathbf{h}_{v}^{(l-1)},\mathbf{m}_{v}^{(l)}), \tag{1}\]

where \(\mathbf{m}_{v}^{(l)}\) and \(\mathbf{h}_{v}^{(l)}\) are the message vector and the representation vector of node \(v\) at the \(l\)-th layer, respectively. \(\text{AGG}(\cdot)\) and \(\text{UPDATE}(\cdot)\) are the aggregation function and update function, respectively. Given the input of the first layer, the learned node representations with \(d_{1}\) dimensions at each layer of \(L\)-layer GNN can be denoted as \(\mathbf{H}^{(l)}\in\mathbb{R}^{|\mathcal{V}|\times d_{1}}\) for \(l=\{1,2,\cdots,L\}\).

Measure of Heterophily & HomophilyIn general, heterophily and homophily of a graph \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) can be measured by node homophily (Goyal et al., 2017). Concretely, the node homophily \(\gamma_{node}\) is the average proportion of the neighbors with the same class of each node as: \(\gamma_{node}=1/|\mathcal{V}|\sum_{v\in\mathcal{V}}(|\{u\in\mathcal{N}(v):y_{ v}=y_{u}\}|/|\mathcal{N}(v)|)\).

The range of \(\gamma_{node}\) is \([0,1]\). Graphs with strong homophily have higher \(\gamma_{node}\) (closer to \(1\)); Whereas graphs with strong heterophily have smaller \(\gamma_{node}\) (closer to \(0\)).

### Heterophilic Search Space Design

To incorporate the complexity and variety of heterophily on graphs, we design a comprehensive heterophilic search space in the proposed Auto-HeG, involving joint micro-level and macro-level candidate operations. At the micro-level, the proposed search space contains three important components: non-local neighbor extension, ego-neighbor separation, and diverse message passing; While the macro-level consists of intermediate layer combination functions and skip connections for integrating layer-wise node representations. The well-designed search space is the basis for building a supernet for search effective architectures on heterophilic graphs as shown in Fig. 1, and we will discuss this further in Sec. 3.3. In the following, we mainly give detailed descriptions of the candidate operations in the proposed heterophilic search space, where its summary is listed in Table 1.

#### 3.2.1. Micro-level Design.

Non-local Neighbor ExtensionHomophilic graphs generally take local nodes from one hop away as neighbors of the ego node for message aggregation, since the same-class nodes mainly locate in their proximal topology. On the contrary, on heterophilic graphs, nodes within the same class could be far away from each other. That means only considering the one-hop-away neighbors would be insufficient to capture the heterophily on graphs explicitly. Hence, to break the local topology limitation under the homophily assumption, we extend local one-hop neighbors to non-local \(K\)-hop neighbors to incorporate heterophilic neighbor information. Concretely, we modify the uniform message passing scheme in Eq. (1) in terms of \(K\)-hop neighbors as follows:

\[\mathbf{m}_{v}^{(l)}=\text{AGG}^{(l)}((\mathbf{h}_{u}^{(l-1)}:u \in\mathcal{N}_{k}(v))),\,k=\{1,2,\cdots,K\}, \tag{2}\]

where \(\mathcal{N}_{k}(v)\) denotes the \(k\)-th hop neighbor set of node \(v\). In this way, the derived heterophilic GNNs could mix latent information from neighbors within the same class at various distances of graph topology. Specifically, to avoid multi-hop neighbors bringing the exponential explosion of graph scale, we restrict the \(k\)-hop neighbor set as neighbors that are connected by at least \(k\) different paths to the ego nodes. For instance, a two-hop neighbor set contains neighbors that are two hops away from ego nodes and have at least two different paths to reach the ego nodes. Note that, different from existing heterophilic GNNs (_e.g._, Mixhop (Garfani et al., 2017) and H2GCN (Goyal et al., 2018)) introducing multi-hop neighbors at each layer and combining them in parallel, we relate the number of neighbor hops to the number of GNN layers correspondingly in the proposed Auto-HeG. The intuition behind this is to alleviate the complexity of the search space but keep its effectiveness at the same time.
_Ego-neighbor Separation._ Despite capturing the messages from non-local neighbors, some local neighbors still have dissimilar class labels with the ego nodes. Hence, it is necessary to separate the ego node representations from their neighbor representations, as verified by the work (Wang et al., 2018). In this way, heterophilic GNNs could learn the ego node features by discriminatively combining the aggregated neighbor information with themselves at the following update step. At this point, we further modify the uniform message passing scheme at the aggregation step in Eq. (2) as

\[\mathbf{m}_{v}^{(l)}=\text{AGG}^{(l)}((\mathbf{h}_{u}^{(l-1)}:u\in\tilde{ \mathcal{N}}_{k}(v))),\,k=\{1,2,\cdots,K\}, \tag{3}\]

where \(\tilde{\mathcal{N}}_{k}(v)\) denotes the neighbor set that excludes the ego node \(v\), \(i\)._e_., removing self-loops in the original graph structure.

_Diverse Message Passing._ Given the extended non-local neighbor set, diverse message-passing scheme is the core of tackling the heterophily on graphs. By distinguishing the information of similar neighbors (likely in the same class) from that of dissimilar neighbors (likely in different classes), heterophilic GNNs could aggregate discriminative messages from diverse neighbors. Typically, we decompose the edge-aware weights \(\mathbf{a}_{uu}\) into homophily-component \(\mathbf{a}_{uu}^{ho}\) and heterophily-component \(\mathbf{a}_{uu}^{he}\) on different neighbor representations \(\mathbf{h}_{u}\), respectively. Hence, we can obtain \(\mathbf{a}_{uu}=[\mathbf{a}_{uu}^{ho};\,\mathbf{a}_{uu}^{he}]\). Moreover, due to the complexity and variety of heterophily, there might be no adequate prior knowledge of the extent of heterophily on graphs. Certain homophilic aggregation functions, \(e\)._g_., GAT (Wang et al., 2018), also have the ability to impose discriminative weights on different neighbors. Hence, we first introduce ample heterophilic and homophilic aggregation functions for the comprehensiveness of the initial search space design. Adaptively learning a more compact search space is postponed to the latter supernet training stage. Specifically, we introduce 18 homophilic and heterophilic aggregation functions, denoting as the diverse aggregation function set \(\mathcal{O}_{AGG}\) shown in Table 1. In this way, the heterophilic message-passing scheme can be denoted as:

\[\mathbf{m}_{o}^{(l)}=\mathcal{O}_{AGG}^{(l)}(\{\mathbf{a}_{uu}^{l-1}\mathbf{ h}_{u}^{(l-1)}:u\in\tilde{\mathcal{N}}_{k}(v)\}),\,k=\{1,2,...,K\}. \tag{4}\]

In summary, the micro-level design of the proposed heterophilic search space mainly works on diverse message passing with extended local and non-local neighbors, along with separated ego and neighbor node representation learning. And such design encourages heterophilic GNNs to adaptively incorporate the heterophily of graphs in each phase of message passing.

#### 3.2.2. Macro-level Design.

To integrate local and global information from different layers, combining intermediate layer representations and introducing skip connections have been verified as beneficial layer-wise operations in human-designed GNNs (Wang et al., 2018; Wang et al., 2018; Wang et al., 2018) and automated GNNs (Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). In light of this, to enable the flexible GNN architecture design on heterophilic graphs, we introduce the inter-layer connections and combinations into the macro-level search space. In this way, the automated heterophilic GNNs could capture hierarchical information at different layers of network architectures. In detail, our macro-level space contains 5 candidate operations as \(\mathcal{O}_{MAC}=\{l\_skip,l\_zero,l\_concat,l\_max,l\_lstm\}\). So that the final output of a heterophilic GNN can be denoted as:

\[\mathbf{h}_{out}=\mathcal{O}_{MAC}[\mathbf{h}^{(1)},\mathbf{h}^{(2)},\cdots, \mathbf{h}^{(L)}]. \tag{5}\]

With the joint micro-level and macro-level candidate operations, the proposed heterophilic search space significantly enlarges the design scopes and the flexibility in developing GNN architectures on graphs with heterophily.

### Progressive Heterophilic Supernet Training

Based on the proposed heterophilic search space, we build a one-shot heterophilic supernet as shown in Fig. 1. Given the heterophilic graph with input feature \(\mathbf{X}\in\mathbb{R}^{|\mathcal{V}|\times d_{0}}\) and adjacency matrix \(\mathbf{A}\in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{V}|}\), the proposed Auto-HeG supernet first implements a linear layer, \(i\)._e_., Multi-layer Perceptron (MLP), to obtain the initial node embedding \(\mathbf{H}^{(0)}\in\mathbb{R}^{|\mathcal{V}|\times d_{1}}\). Then, the node embedding \(\mathbf{H}^{(0)}\) and the adjacency matrix \(\mathbf{A}\) would be fed into the first layer containing micro-level candidate operations with the \(\mathcal{O}_{AGG}\) set, leading to the output node representation \(\mathbf{H}^{(1)}\). Next, \(\mathbf{H}^{(1)}\) is fed into the macro-level \(\mathcal{O}_{MAC}\) for the layer-wise connection. Meanwhile, \(\mathbf{H}^{(1)}\) and the two-hop adjacency matrix \(\mathbf{A}^{2}\) would be the inputs of the next micro-level layer. The above process implements repeatedly layer by layer before the final node representations experience the classifier to obtain the predictions of node classes.

\begin{table}
\begin{tabular}{l|l|l} \hline Search Space & Modules & Operations \\ \hline \multirow{4}{*}{Micro-level} & Neighbors & \{(A,A^{*},\cdots,A^{K}\}\) \\ \cline{2-3}  & \multirow{2}{*}{\(\mathcal{O}_{AGC}\)} & \multirow{2}{*}{homons.} & \{(\{\)GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GG,GGGG,GG,GG,GGGG,
Even though the proposed search space contains as many candidate operations as possible, real-world heterophilic graphs usually show significant differences in complexity and diversity, and we still lack prior knowledge on what heterophilic and homophilic aggregations are beneficial for heterophilic graph learning. The proposed initial search space might be comprehensive but severely challenge the effectiveness of supernet training to automatically derive expressive GNN architectures, especially when heterophily varies on different graphs. In light of this, a possible solution comes: why not let the proposed supernet adaptively keep the beneficial operations and drop the irrelevant counterparts as the process of iterative learning goes on? This would contribute to a more compact supernet with relevant candidate operations specifically driven by current heterophilic graphs and tasks, leading to more effective heterophilic GNN architecture development. Moreover, considering some operations will never be selected by certain layers in the final architectures mentioned by (Wang et al., 2018), this solution ensures different layers flexibly customize their own layer-wise candidate operation sets according to heterophily variation, rather than sharing the entire fixed and large search space with all layers.

Therefore, to derive a more compact heterophilic one-shot supernet for efficient architecture design, we present a progressive training strategy to dynamically shrink the initial search space and adaptively design the candidate operation space in each layer. Specifically, let \(\mathcal{S}_{0}=\left(\mathcal{E}_{0}^{\mathcal{S}},\mathcal{N}_{0}^{\mathcal{S }}\right)\) denotes the initial heterophilic supernet constructed based on the proposed entire search space \(\mathcal{O}\), and \(\mathcal{E}_{0}^{\mathcal{S}}\) and \(\mathcal{N}_{0}^{\mathcal{S}}\) are the edge set and the node set, respectively. We first train \(\mathcal{S}_{0}(\mathbf{\alpha},\mathbf{w})\) several steps for stochastic differentiable search based on the bi-level optimization:

\[\begin{split}\min_{\mathbf{\alpha}}&\quad\mathcal{L}_{ \textit{cal}}\left(\mathbf{w}^{*}(\mathbf{\alpha}),\mathbf{\alpha}\right),\\ s.t.&\quad\mathbf{w}^{*}(\mathbf{\alpha})=\operatorname*{ argmin}_{\mathbf{w}}\mathcal{L}_{\textit{train}}\left(\mathbf{w},\mathbf{\alpha}\right), \end{split} \tag{6}\]

which conducts iterative learning of the architecture weight \(\mathbf{\alpha}\) and the model parameter \(\mathbf{w}\). Let \(o\in\mathcal{O}\) denotes a certain operation in heterophilic search space \(\mathcal{O}\), and a node pair \((\mathbf{x}_{i},\mathbf{x}_{j})\) denotes the latent vectors from \(i\)-th node to \(j\)-th node of the supernet, the learned architecture weights \(\mathbf{\alpha}=\left\{a_{o}^{(i,j)}|o\in\mathcal{O},(i,j)\in\mathcal{N}_{0}^{ \mathcal{S}}\right\}\), and the operation specific weight vector \(a_{o}^{(i,j)}\) can be derived as:

\[\tilde{o}^{(i,j)}(\mathbf{x})=\sum_{o\in\mathcal{O}}\frac{\exp\left[\left(\log a _{o}^{(i,j)}+u_{o}^{(i,j)}\right)/\tau\right]}{\sum_{o^{\prime}\in\mathcal{O} }\exp\left[\left(\log a_{o^{\prime}}^{(i,j)}+u_{o^{\prime}}^{(i,j)}\right)/ \tau\right]}\,\cdot\,o(\mathbf{x}) \tag{7}\]

where \(\tilde{o}^{(i,j)}\) is the mixed operation of edges between \((i,j)\), and \(u_{o}^{(i,j)}=-\log\left(-\log\left(U\right)\right)\) where \(U\sim\operatorname*{Uniform}(0,1)\). \(\tau\) is the temperature factor that controls the extent of the continuous relaxation. When \(\tau\) is closer to \(0\), the weights would be closer to discrete one-hot values.

To further exploit the relevance and importance of candidate operations to heterophily, we rank the obtained \(\mathbf{\alpha}\) layer by layer based on its magnitudes and drop the last \(C\) irrelevant operations, _i.e._, cutting \(C\) number of edges in each layer at the current supernet training stage. By repeating the above process \(T\) iterations, we gradually and dynamically shrink the initial search space and compress the supernet, leading to a compact and effective supernet \(\mathcal{S}_{c}\) by customizing layer-wise heterophilic candidate operation set. The overall process of the proposed progressive supernet training strategy is summarized in Algo. 1.

### Heterophily-guided Architecture Selection

With the magnitudes of the architecture weights as the metric, Auto-HeG progressively learns a compact supernet with layer-wise search spaces driven by the heterophily variation. Considering an extreme case: the supernet shrinks gradually till every edge of it keeps only one operation. Basically, that is the general strategy used by current graph NAS methods, _i.e._, argmax-based architecture selection scheme. That means only the operations corresponding to the maximum edge weights in the architecture supernet could be preserved by such an architecture selection scheme to build the ultimate GNNs. However, very recent research (Shen et al., 2019) has verified the architecture magnitude is not effective enough to indicate the operation strength in the final GNN architecture selection. That is why we only use this strategy as the beginning to generally narrow the scope of candidate operations in the proposed search space.

Therefore, to select powerful GNN architectures specifically instructed by heterophily, we derive a heterophily-aware distance as the criterion to guide heterophilic GNN architecture selection. And inspired by the perturbation-based architecture selection scheme in (Shen et al., 2019), we implement a leave-one-out manner to directly evaluate the contribution of each candidate operation to the compact supernet performance. Specifically, the proposed heterophily-aware distance \(D_{\textit{hete}}\) can be defined with the Euclidean distance as \(D_{\textit{hete}}=||\hat{\mathcal{H}}-\mathcal{H}||^{2}\), where \(\mathcal{H}\) and \(\hat{\mathcal{H}}\) are the heterophilic matrices
denoted as:

\[\mathcal{H}=\left(Y^{T}AY\right)\oslash\left(Y^{T}AE\right),\ \mathcal{\hat{H}}= \left(\hat{Y}^{T}A\hat{Y}\right)\oslash\left(\hat{Y}^{T}AE\right), \tag{8}\]

where \(Y\in\mathbb{R}^{|\mathcal{V}|\times\mathcal{P}}\) is the ground-truth label matrix of the heterophilic graph with \(p\) classes of nodes, \(E\in\mathbb{R}^{|\mathcal{V}|\times\mathcal{P}}\) is an all-ones matrix, and \(\oslash\) denotes the Hadamard division operation. Concretely, \(\mathcal{H}_{i,j}\) indicates the connection probability of nodes (Hinsel and Karim, 2015; Karim, 2015) between the \(i\)-th class and the \(j\)-th class with the ground truth labels, and \(\mathcal{\hat{H}}_{i,j}\) works in the same way but with the predicted labels \(\hat{Y}\in\mathbb{R}^{|\mathcal{V}|\times\mathcal{P}}\), _i.e._, the output of the compact heterophilic supernet.

The proposed heterophily-aware distance \(D_{\textit{Hete}}\) explicitly restricts the connection possibility of nodes in any two classes predicted by the supernet, to be close to that of the ground truth. And smaller \(D_{\textit{Hete}}\) indicates the better discriminative ability of a certain candidate operation to heterophilic node classes. Taking \(D_{\textit{Hete}}\) as the guidance, we select the optimal heterophilic GNN architecture from the pretrained compact supernet \(\mathcal{S}_{\mathcal{C}}\), and the whole process is illustrated in Algo. 2. In summary, Auto-HeG first builds a comprehensive heterophilic search space, and then progressively shrinks the initial search space layer by layer, leading to a more compact supernet with Algo. 1. Finally, Auto-HeG selects the ultimate heterophilic GNN architecture with the guidance of the heterophily-aware distance in Algo. 2. Consequently, Auto-HeG could automatically derive powerful and expressive GNN models for learning discriminative node representations on heterophilic graphs effectively.

## 4. Experiments

In this section, we first provide the experimental setting details. Then, we compare the proposed Auto-HeG with state-of-the-art human-designed and graph NAS models on the node classification task. Finally, we conduct ablation studies to evaluate the effectiveness of each component in Auto-HeG, including heterophilic search space, progressive heterophilic supernet training, and heterophily-guided architecture selection.

### Experimental Setting

_Datasets and Baselines._ We conduct experiments on seven real-world datasets with different degrees of heterophily (\(Y_{\textit{node}}\)) denoted in brackets, where Cornell (0.11), Texas (0.06), and Wisconsin (0.16) are three WebKB web-page dataset (Dai et al., 2017), and Actor (0.24) is an actor co-occurrence network (Zhu et al., 2018). These four datasets are with high heterophily from (Zhu et al., 2018). Furthermore, Cora (0.83) (Citeseer, 0.71) (Citeseer, 0.71), and Pubmed (0.79) (Peters et al., 2019) are three citation network datasets with low heterophily. For comparisons on node classification, we take H2GCN-1 and H2GCN-2 (Han et al., 2017), MixHop (Ashsh et al., 2018), GPR-GNN (Chen et al., 2019), GCNII (Chen et al., 2019), Geom-GCN-I, Geom-GCN-P, and Geom-GCN-S (Zhu et al., 2018), FAGCN (Chen et al., 2019), as well as classical GCN (Ghar et al., 2018), GAT (Zhu et al., 2018), GraphSAGE (Dai et al., 2017), and SGC (Zhu et al., 2018) as human-designed model baselines for high-heterophily and low-heterophily datasets, respectively. Furthermore, we take GraphNAS (Dai et al., 2017), SNAG (Zhu et al., 2018), and SANE (Han et al., 2017) as graph NAS model baselines. To test the performance of simply modifying existing graph NAS search spaces, we develop 'SANE-hete' as another baseline by directly injecting heterophilic aggregation functions into the search space of SANE (Han et al., 2017).

_Implementation._ All experiments run with Pytorch platform on Quadro RTX 6000 GPUs and the core code is built based on PyG library (Krizhevsky et al., 2014). Following the setting in (Han et al., 2017), at the search stage, we search with different random seeds and select the best architecture according to the performance on validation data. At the train from scratch stage, we finetune hyper-parameters on validation data within fixed ranges. For all datasets, we use the same splits as that in Geom-GCN (Zhu et al., 2018) and evaluate the performance of all models on the test sets over provided 10 splits for fair comparisons. We report the mean classification accuracy with standard deviations as the performance metric of node classification.

### Experimental Results on Node Classification

The node classification results of the proposed Auto-HeG and comparison methods on high-heterophily and low-heterophily datasets are shown in Table 2 and Table 3, respectively. And the details of derived architectures on all datasets are provided in Appendix. As shown in Table 2, it can be generally observed that the proposed Auto-HeG achieves the best performance when learning on high-heterophily graphs compared with human-designed and graph NAS models. Specifically, Auto-HeG excesses the second-best model, _i.e._, human-designed H2GCN, with 1.35%, 1.90%, 1.80% and 1.57% performance improvement on Cornell, Texas, Wisconsin, and Actor datasets, respectively. Compared with graph NAS models, first, Auto-HeG greatly outperforms all existing homophilic graph NAS models over all datasets. We attribute this to the elaborate incorporation of heterophily in our Auto-HeG, especially for graphs with high heterophily. Moreover, the superiority of Auto-HeG to SANE-hete verifies that simply injecting the heterophilic aggregation functions into the existing homophilic search space is not an effective solution. This further illustrates the effectiveness of the proposed progressive heterophilic supernet training and heterophily-guided architecture selection in our Auto-HeG. And incorporating the heterophily into all stages of automatic heterophilic GNN design indeed benefits learning on graphs with heterophily.

For comparisons on low-heterophily datasets in Table 3, our Auto-HeG outperforms most human-designed classical GNN models and graph NAS models, further illustrating its ability to analyze graphs even with low heterophily. We attribute these results to two sub-modules in our Auto-HeG: the proposed search space which keeps many homophilic aggregation functions, and the derived progressive supernet training strategy which customizes layer-wise aggregation functions. These components enable the flexible construction of GNN architectures, leading to superior performance even with low-heterophily. Therefore, we could conclude that even lacking the prior information on heterophily degrees, the proposed Auto-HeG could progressively and adaptively select appropriate candidate operations along with the variation of heterophily, leading to consistently impressive performance on graphs with high-heterophily and low-heterophily. This reflects the excellent ability of our Auto-HeG to deal with complex and various heterophily.
### Ablation Study

#### 4.3.1. Effectiveness of heterophilic search space

We derive three variants of the proposed heterophilic search space to verify its effectiveness. Denoting the overall heterophilic search space as \(\mathcal{O}_{\texttt{n}_{0}}\), we consider the following subsets: (1) \(\widetilde{\mathcal{O}}_{homo}\): only keep homophilic aggregation functions and remove all heterophilic ones from \(\mathcal{O}_{\texttt{n}_{0}}\), to verify the importance of integrating heterophilic operations; (2) \(\widetilde{\mathcal{O}}_{hette}\): only keep heterophilic aggregation functions and remove all homophilic ones from \(\mathcal{O}_{\texttt{n}_{0}}\), to observe the performance when the search space only contains heterophilic operations; (3) \(\widetilde{\mathcal{O}}_{he\texttt{e}ho}\): randomly remove several heterophilic and homophilic aggregation functions \(\mathcal{O}_{\texttt{n}_{0}}\), to illustrate the effectiveness of simultaneously involving heterophilic and homophilic operations.

Specifically, we randomly sample 20 architectures from each subset and report the max performance and average performance among them in Fig. 2, respectively. Following observations can be obtained: (1) No best results are achieved in \(\widetilde{\mathcal{O}}_{homo}\) on all datasets in both max and average cases, which naturally verifies the importance of heterophilic operations to heterophilic graph learning; (2) \(\widetilde{\mathcal{O}}_{hette}\) and \(\widetilde{\mathcal{O}}_{he\texttt{e}ho}\) generally have better performance compared to other search space sets, which illustrates the necessity of involving appropriate homophilic operations. Moreover, this shows that merely involving heterophilic operations is not enough for complex and diverse heterophily learning; (3) The overall search space \(\mathcal{O}_{\texttt{n}_{0}}\) performs the best only on Texas and Actor datasets in the max case. This presents that \(\mathcal{O}_{\texttt{n}_{0}}\) could not achieve consistently best performance under the random sampling scenario, even with the largest number of candidate operations. Moreover, this result also verifies that developing a more compact heterophilic search space is necessary and crucial. At this point, it could be concluded that the proposed progressive supernet training strategy is effective, and we could attribute this to its adaptive and dynamic layer-wise search space shrinking schema.

#### 4.3.2. Effectiveness of progressive supernet training

The comparison results with and without the layer-wise search space shrinking in the proposed progressive supernet training strategy are listed in Fig. 3. It can be generally observed that, on both high-heterophily and low-heterophily datasets, the performance of the compact supernet consistently achieves better performance with the proposed supernet training strategy. For example, the compact supernet with

\begin{table}
\begin{tabular}{l|l|c c c c} \hline \hline Methods & Datasets & Cornell & Texas & Wisconsin & Actor \\ \hline \multirow{8}{*}{Human-designed models} & H2GCN-1* & 82.16\(\pm\)4.80 & 84.86\(\pm\)6.77 & 86.67\(\pm\)4.69 & 35.86\(\pm\)1.03 \\  & H2GCN-2* & 82.16\(\pm\)6.00 & 82.16\(\pm\)5.28 & 85.88\(\pm\)4.22 & 35.62\(\pm\)1.30 \\  & MixHop* & 73.51\(\pm\)6.34 & 77.84\(\pm\)7.73 & 75.88\(\pm\)4.90 & 32.22\(\pm\)2.34 \\  & GPR-GNN & 81.89\(\pm\)5.93 & 83.24\(\pm\)4.95 & 84.12\(\pm\)3.45 & 35.27\(\pm\)1.94 \\  & CGNII* & 76.49 & 77.84 & 81.57 & - \\  & Geom-GCN-I* & 56.76 & 57.58 & 58.24 & 29.09 \\  & Geom-GCN-P* & 60.81 & 67.57 & 64.12 & 31.63 \\  & Geom-GCN-S* & 55.68 & 59.73 & 56.67 & 30.30 \\  & FAGCN & 81.35\(\pm\)5.05 & 84.32\(\pm\)6.02 & 83.33\(\pm\)2.01 & 35.74\(\pm\)6.52 \\ \hline \multirow{8}{*}{Graph NAS models} & GraphNAS & 58.11\(\pm\)3.87 & 54.86\(\pm\)6.98 & 56.67\(\pm\)2.99 & 25.47\(\pm\)1.32 \\  & SNAG & 57.03\(\pm\)3.48 & 62.70\(\pm\)5.52 & 62.16\(\pm\)4.63 & 27.84\(\pm\)1.29 \\ \cline{1-1}  & SANE & 56.76\(\pm\)5.51 & 66.22\(\pm\)10.62 & 86.67\(\pm\)5.02 & 33.41\(\pm\)1.41 \\ \cline{1-1}  & SANE-hette & 77.84\(\pm\)5.51 & 77.84\(\pm\)7.51 & 83.92\(\pm\)2.28 & 35.88\(\pm\)1.30 \\ \cline{1-1} \cline{2-5}  & **Auto-HeG (ours)** & **83.51\(\pm\)6.36** & **86.76\(\pm\)4.60** & **87.84\(\pm\)3.59** & **37.43\(\pm\)1.37** \\ \hline \hline \end{tabular}
\end{table}
Table 2. Performance (ACC%\(\pm\)std) of the proposed Auto-HeG compared with human-designed and graph NAS models on high-heterophily datasets. The best results are in bold and the second-best results are underline. Superscript* represents the officially reported results with the same dataset splits, where Geom-GCN and GCNI do not provide the std; And the remains are our reproduced results if official methods do not test under the same dataset splits.

\begin{table}
\begin{tabular}{l|l|c c c} \hline \hline Methods & Datasets & Cora & Citeseer & Pubmed \\ \hline \multirow{8}{*}{Human-designed models} & GCN & 85.69\(\pm\)1.80 & 75.38\(\pm\)1.75 & 86.08\(\pm\)6.4 \\  & GAT & 86.52\(\pm\)1.41 & 75.51\(\pm\)1.85 & 84.75\(\pm\)0.51 \\  & GraphSAGE & 80.60\(\pm\)3.63 & 67.18\(\pm\)5.46 & 81.18\(\pm\)1.12 \\  & SGC & 85.88\(\pm\)3.61 & 73.86\(\pm\)1.73 & 84.87\(\pm\)2.81 \\  & GCNI* & 88.01 & 77.13 & 90.30 \\  & Geom-GCN-I* & 85.19 & 77.99 & 90.05 \\  & Geom-GCN-P* & 84.93 & 75.14 & 88.09 \\  & Geom-GCN-S* & 85.27 & 74.71 & 84.75 \\ \hline \multirow{8}{*}{Graph NAS models} & GraphNAS & 84.10\(\pm\)0.79 & 68.83\(\pm\)2.09 & 82.28\(\pm\)0.64 \\  & SNAG & 81.01\(\pm\)1.31 & 70.14\(\pm\)2.00 & 83.24\(\pm\)0.84 \\ \cline{1-1}  & SANE & 84.25\(\pm\)1.82 & 74.33\(\pm\)1.54 & 87.82\(\pm\)0.57 \\ \cline{1-1}  & SANE-hette & 85.05\(\pm\)0.90 & 74.46\(\pm\)1.59 & 88.99\(\pm\)0.42 \\ \cline{1-1} \cline{2-5}  & **Auto-HeG (ours)** & 86.88\(\pm\)**1.10** & 75.81\(\pm\)1.52 & 89.29\(\pm\)0.27 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Performance (ACC%\(\pm\)std) of the proposed Auto-HeG compared with human-designed and graph NAS models on low-heterophily datasets.
progressive training significantly raises the performance of Cornell from 75.68% to 83.51% and Texas from 72.97% to 86.76%. We attribute such impressive improvements to the excellent ability of our Auto-HeG in building the effective and adaptive supernet. Without the progressive training, the initial search space would keep a large number of operations that might be irrelevant and redundant to specific graphs with heterophily, which brings serious challenges to the search strategy for optimizing in such a large supernet. At this point, Auto-HeG progressively shrinks the search space layer-wisely and dynamically narrows the scope of relevant candidate operations, resulting in a more compact and effective supernet for deriving powerful heterophilic GNNs.

#### 4.3.3. Effectiveness of heterophily-guided architecture selection

We compare the proposed heterophily-guided architecture selection with the other two types of architecture selection methods, _i.e._, architecture weight magnitude based argmax strategy, which is the most commonly used method in existing gradient-based graph NAS (He et al., 2017; Zhang et al., 2018), and perturbation-based architecture selection method with the validation loss criterion proposed by (Wang et al., 2019). The comparison results are listed in Table 4. Generally, our proposed heterophily-guided scheme with the heterophily-aware distance criterion gains the best classification performance on all datasets consistently, illustrating its effectiveness in expressive architecture selection. Furthermore, we can observe that the architecture weight magnitude based argmax strategy, _i.e._, 'Argmax Arch. Select.', performs better than that of perturbation-based architecture selection method with the validation loss criterion, _i.e._, 'Val. Loss Arch. Select.'. Even the work (Wang et al., 2019) has verified the effectiveness of 'Val. Loss Arch. Select.' over CNN-based NAS in the leave-one-out manner, more importantly, we find that it might not well adapt to GNN-based NAS by implementing the validation loss based criterion straightforwardly. This fact further illustrates the effectiveness of the proposed heterophily-aware distance criterion in the leave-one-out-manner for GNN-based NAS with heterophily.

## 5. Conclusion

In this paper, we propose a novel automated graph neural network on heterophilic graphs via heterophily-aware graph neural architecture search, namely Auto-HeG, which is the first work of automatic heterophilic graph learning. By explicitly incorporating heterophily into all stages, _i.e._, search space design, supernet training, and architecture selection, Auto-HeG could develop powerful heterophilic GNNs to deal with the complexity and variety of heterophily effectively. To build a comprehensive heterophilic GNN search space, Auto-HeG includes non-local neighbor extension, ego-neighbor separation, diverse message passing, and layer-wise combination at both micro-level and macro-level. To develop a compact and effective heterophilic supernet based on the initial search space, Auto-HeG conducts the progressive supernet training strategy to dynamically shrink the scope of candidate operations according to layer-wise heterophily variation. In the end, taking the heterophily-aware distance criterion as the guidance, Auto-HeG selects excellent heterophilic GNN architectures by directly evaluating the contribution of each operation in the leave-one-out pattern. Extensive experiments verify the superiority of the proposed Auto-HeG on learning graphs with heterophily to both human-designed models and graph NAS models.

\begin{table}
\begin{tabular}{l|c c c|c c|c c} \hline \hline \multirow{2}{*}{Arch. Select. Methods} & \multicolumn{6}{c|}{\(n_{\text{BB-heterophily Datasets}}\)} & \multicolumn{6}{c}{_Low-heterophily Datasets_} \\ \cline{2-7}  & Cornell & Texas & Wisconsin & Actor & Cora & Citeseer & Pubmed \\ \hline Argmax Arch. Select. & 79.19\(\pm\)3.38 & 79.46\(\pm\)3.67 & 86.27\(\pm\)4.02 & 37.12\(\pm\)1.12 & 85.33\(\pm\)1.46 & 75.43\(\pm\)2.24 & 88.52\(\pm\)0.41 \\ Val. Loss Arch. Select. & 57.84\(\pm\)3.67 & 71.35\(\pm\)5.30 & 80.59\(\pm\)7.09 & 36.96\(\pm\)1.08 & 84.67\(\pm\)1.64 & 73.86\(\pm\)1.11 & 88.23\(\pm\)0.53 \\ \hline
**Heter. Arch. Select. (ours)** & **83.51\(\pm\)6.56** & **86.76\(\pm\)4.60** & **87.84\(\pm\)3.59** & **37.43\(\pm\)**1.37** & **86.88\(\pm\)1.10** & **75.81\(\pm\)1.52** & **89.29\(\pm\)0.27** \\ \hline \hline \end{tabular}
\end{table}
Table 4. Comparison of the proposed heterophily-guided architecture selection scheme (Heter. Arch. Select.) with other architecture selection methods.

Figure 3. Performance w/ and w/o shrinking (srk) for the proposed progressive supernet training.

Figure 2. Illustration of the effectiveness of the proposed search space by evaluating search space variants.
## Acknowledgment

This work was partially supported by an Australian Research Council (ARC) Future Fellowship (FT210100097), Guangdong Provincial Natural Science Foundation under grant NO. 2022A1515010129, and the CAS Project for Young Scientists in Basic Research (YSBR-008).
