# Efficient and Explainable Graph Neural Architecture Search via Monte-Carlo
Tree Search

Yuya Sasaki<EMAIL_ADDRESS>Osaka UniversitySuitaOsakaJapan

###### Abstract.

Graph neural networks (GNNs) are powerful tools for performing data science
tasks in various domains. Although we use GNNs in wide application scenarios,
it is a laborious task for researchers and practitioners to design/select
optimal GNN architectures in diverse graphs. To save human efforts and
computational costs, graph neural architecture search (Graph NAS) has been
used to search for a sub-optimal GNN architecture that combines existing
components. However, there are no existing Graph NAS methods that satisfy
explainability, efficiency, and adaptability to various graphs. Therefore, we
propose an efficient and explainable Graph NAS method, called ExGNAS, which
consists of (i) a simple search space that can adapt to various graphs and
(ii) a search algorithm that makes the decision process explainable. The
search space includes only fundamental functions that can handle homophilic
and heterophilic graphs. The search algorithm efficiently searches for the
best GNN architecture via Monte-Carlo tree search without neural models. The
combination of our search space and algorithm achieves finding accurate GNN
models and the important functions within the search space. We comprehensively
evaluate our method compared with twelve hand-crafted GNN architectures and
three Graph NAS methods in four graphs. Our experimental results show that
ExGNAS increases AUC up to 3.6 and reduces run time up to 78% compared with
the state-of-the-art Graph NAS methods. Furthermore, we show ExGNAS is
effective in analyzing the difference between GNN architectures in homophilic
and heterophilic graphs.

##  1\. Introduction

Graph Neural Networks (GNNs) are powerful tools for practical data science
tasks in various application scenarios from various domains including
chemistry (Duvenaud et al., 2015; Fung et al., 2021), physics (Sanchez-
Gonzalez et al., 2020), social science (Kipf and Welling, 2017), and
neuroscience (Zhong et al., 2020). Although we have developed numerical GNN
architectures for various graphs, there are no one-size-fits-all GNN
architectures yet. It is laborious to design new GNN architectures and select
optimal GNN architectures from numerous architectures according to the
characteristics of graphs.

To save human efforts and computational costs in designing/selecting GNN
architectures, graph neural architecture search (Graph NAS) has been used to
search for a sub-optimal GNN architecture in a given graph (Gao et al., 2020;
Zhao et al., 2020b; Zhou et al., 2019). Due to increasing the number of GNN
architectures and the demand for graph analysis, Graph NAS becomes important
for researchers and practitioners.

Issues in Graph NAS methods. Graph NAS methods have two technical design
challenges; (1) search space and (2) search algorithm. First, the search space
defines patterns of GNN architectures; GNN architectures are generated by
combinations of components within the search space. If the search space is not
well-designed, there are no suitable GNN architectures within the search
space. Second, search algorithms determine how to preferentially search for
GNN architectures that could achieve high accuracy. If search algorithms are
not sophisticated, the search process becomes inefficient, and suitable GNN
architectures are not found during the search process.

Existing Graph NAS methods address these two challenges to improve accuracy
and efficiency. However, their search algorithms use neural models as the
backbone to run the search from complex search spaces. It causes an
inefficient search process and a low capacity for analyzing the importance of
components in GNN architectures. In addition, their search spaces mainly focus
on homophilic graphs, so they lack the adaptability to heterophilic graphs.

Motivation. We reconsider Graph NAS from the perspective of practical data
science for researchers and practitioners. For researchers, Graph NAS should
provide (i) strong baselines on various graphs and (ii) the important
components, which are helpful in designing new GNN architectures. For
practitioners, Graph NAS should efficiently and easily provide sub-optimal GNN
architectures on various graphs without knowledge of GNNs, the characteristics
of graphs, and heavy hyper-parameter tuning. These indicate the necessity for
efficient and explainable Graph NAS that provides sub-optimal architectures on
various graph types.

Although explainable NAS methods have been studied widely (Li and Talwalkar,
2020; Real et al., 2020; Ru et al., 2021), there are no explainable Graph NAS
methods, to the best of our knowledge. For example, GraphGym (You et al.,
2020) aims to understand the important fundamental components in GNN
architectures. It does not provide search algorithms and GNN architectures for
heterophilic graphs. AutoHeG (Zheng et al., 2023) provides sub-optimal GNN
architecture for heterophilic graphs, but it is inefficient and complex to
understand the important components of GNN architectures. In addition, there
are no studies that empirically compare the important components between
homophilic and heterophilic graphs. Therefore, we need to study efficient and
explainable Graph NAS on homophilic and heterophilic graphs and analyze the
important components across graph types.

Contribution. We are the first to study explainable graph neural architecture
search, to the best of our knowledge. We propose an efficient and explainable
Graph NAS method, called ExGNAS, which consists of a simple but effective
search space and algorithm. First, our search space is well-designed to
achieve high accuracy in both homophilic and heterophilic graphs, despite
being simple. Our search space includes fundamental components of GNN
architectures such as multilayer perceptron (MLP), activation functions, and
jumping knowledge networks (Xu et al., 2018), while does not include any
state-of-the-art GNN layers. This leads to simple GNN architectures that can
easily understand their components. Second, our search algorithm employs
Monte-Carlo tree search without neural models, which makes the decision
process explainable. It selects the next GNN architecture from the average
performance of explored architectures and finally outputs the Monte-Carlo tree
with the importance of components. Our method does not require hyper-parameter
tuning. The elegant combination of the simple search space and algorithm
achieves explanability, high efficiency, and adaptability on homophilic and
heterophilic graphs.

We comprehensively evaluate our Graph NAS method compared with twelve hand-
crafted GNN architectures and four Graph NAS methods in six homophilic and six
heterophilic graphs. Our experimental results show that ExGNAS achieves the
highest average AUC. It increases AUC up to 3.6 and reduces run time up to 78%
compared with the state-of-the-art Graph NAS methods. Furthermore, we validate
that ExGNAS helps to analyze the difference between GNN architectures in
homophilic and heterophilic graphs.

Our contributions are summarized as follows: (1) We first study an explainable
graph neural architecture search, (2) We propose an efficient and explainable
graph neural architecture search method ExGNAS, and (3) Extensive experimental
studies demonstrate that ExGNAS outperforms the state-of-the-art baselines in
heterophilic graphs and helps to analyze GNN architectures.

Repoducability. We open our code at
https://github.com/OnizukaLab/AutoGNN_mcts.

##  2\. Preliminaries and Related work

###  2.1. Graphs

An undirected attributed graph with node labels is a triple
$\mathcal{G}=(\mathbf{S},\mathbf{X},\mathbf{Y})$ where
$\mathbf{S}\in\\{0,1\\}^{n\times n}$ is an adjacency matrix, $\mathbf{X}\in
R^{n\times d}$ is an attribute matrix assigning attributes to nodes, and a
label matrix $\mathbf{Y}\in\\{0,1\\}^{n\times y}$ contains label of each node,
and $n$, $d$, and $y$ are the numbers of nodes, attributes, and labels,
respectively. If there is an edge between nodes $v$ and $u$,
$\mathbf{S}_{(v,u)}$ and $\mathbf{S}_{(u,v)}$ are set to one. $\mathbf{Y}_{v}$
is one hot vector that represents a label of node $v$.

We define two types of graph properties, homophily and heterophily properties,
after defining edge homophilly (Zhu et al., 2020) of graphs. The edge
homophily is calculated as $H(\mathcal{G})=\frac{\sum_{0\leq
v,u<n}\mathbf{S}_{(u,v)}\delta(\mathbf{Y}_{v},\mathbf{Y}_{u})}{\sum_{0\leq
v,u<n}\mathbf{S}_{(u,v)}}$, where $\delta(\mathbf{Y}_{v},\mathbf{Y}_{u})$
returns one if $\mathbf{Y}_{v}=\mathbf{Y}_{u}$ otherwise zero. If
$H(\mathcal{G})$ is large, the graph is homophilic, otherwise heterophilic.
Intuitively, the edge homophily indicates a probability that connected nodes
have the same labels. It is well-known that GNNs for homophilic graphs do not
work well in heterophilic graphs.

###  2.2. Neural Architecture Search

Neural architecture search (NAS) aims to find the best model that achieves the
highest accuracy in a given dataset. A model is represented by a pair
$(\alpha,\mathbf{W})$ where $\alpha$ is a model architecture and $\mathbf{W}$
is a parameter of a neural network. A search space $\mathcal{A}$ defines
patterns of model architectures. The best architecture $\alpha^{*}$ is defined
as follows:

(1) $\displaystyle\alpha^{*}=\mathop{\rm
arg~{}max}\limits_{\alpha\in\mathcal{A}}{\rm
E_{Val}}(\alpha,\mathbf{W}_{\alpha}^{*}).$ (2)
$\displaystyle\mathbf{W}_{\alpha}^{*}=\mathop{\rm
arg~{}min}\limits_{\mathbf{W}}{\rm L_{Train}}(\alpha,\mathbf{W}).$

where $\rm{E_{Val}}$ and $\rm{L_{Train}}$ indicate the evaluation metrics on
validation data and the loss function on train data, respectively.

In this paper, we focus on node classification following existing studies
(e.g., (Cai et al., 2021; Guan et al., 2022; Li and King, 2020; Zhang et al.,
2022a, b; Zhao et al., 2020b, a; Zhou et al., 2019)). In a node
classification, given a graph and partially labeled nodes, it predicts the
labels of the rest of the nodes in the graph.

###  2.3. Related Work

Graph Neural Architecture Search. Graph NAS methods design their search space
and search algorithms to find an optimal architecture in a given graph (Cai et
al., 2021; Ding et al., 2021; Gao et al., 2020; Guan et al., 2022; Huan et
al., 2021; Li et al., 2021; Li and King, 2020; Qin et al., 2022; Shi et al.,
2020; Wang et al., 2022; You et al., 2020; Zhang et al., 2022a, b, 2021; Zhao
et al., 2020b, a; Zheng et al., 2023; Zhou et al., 2019; Xu et al., 2023; Zhu
et al., 2022; Zhang et al., 2023). We review search space and algorithms in
existing Graph NAS methods.

Search Space. The search space is categorized into two parts; architecture
space and hyper-parameter space. The architecture space represents patterns of
GNN architectures such as aggregation and activation functions, while the
hyper-parameter space represents values of hyper-parameters such as learning
rate and weight decay. Graph NAS methods that search architecture space with
given fixed hyper-parameters (Zhou et al., 2019; Zhao et al., 2020b; Li and
King, 2020; Zhao et al., 2020a; Cai et al., 2021; Guan et al., 2022; Zhang et
al., 2022b, a; Zheng et al., 2023) search architecture space with given fixed
hyper-parameters aim to explore a wide variety of architectures, while Graph
NAS methods that search both architecture and hyper-parameter space (You et
al., 2020; Shi et al., 2020; Gao et al., 2020; Huan et al., 2021; Ding et al.,
2021; Li et al., 2021; Cai et al., 2021) consider both combinations of
architectures and hyper-parameters. It is not obvious which search space is
better because if the hyper-parameters are fixed, the architecture space can
include a larger number of GNN architecture patterns. This paper focuses on
the architecture space with fixed hyper-parameters because we aim to analyze
the architecture difference, while our method can naturally include hyper-
parameter space.

The architecture space differs across studies. The architecture space itself
can be considered a large technical contribution even if Graph NAS methods use
existing algorithms (You et al., 2020; Zhang et al., 2023). Most studies
generate GNN layers by combining fundamental functions such as aggregation,
attention, and activation functions, and connect the generated GNN layers by
skip connection and JKNet (You et al., 2020; Li and King, 2020; Guan et al.,
2022; Ding et al., 2021). GraphNAS (Gao et al., 2020) uses functions such as
activation and attention function, and the number of heads, while the number
of GNN layers is fixed. In addition, GraphGym (You et al., 2020) adds
pre-/post processing before/after GNN layers and skip connections. AutoGraph
(Li and King, 2020) focuses on skip connection and automatically selects the
number of GNN layers. GAUSS (Guan et al., 2022) considers graph sampling to
handle large-scale graphs. AutoGT (Zhang et al., 2023) focuses on the
architectures of graph transformers for graph classification tasks. GAP (Cai
et al., 2021), DFG-NAS (Zhang et al., 2022a), PDNAS (Zhao et al., 2020a), and
NAS-Bench-Graph (Qin et al., 2022), and AutoHeG (Zheng et al., 2023) search
for combinations of the state-of-the-art GNN layers with arbitrary patterns of
connections. Among them, AutoHeG (Zheng et al., 2023) only focuses on
heterophilic graphs and others mainly focus on homophilic graphs, so
adaptability to various graphs is not investigated well.

Search Algorithm. Search algorithms support efficiently finding the best GNN
architecture within the search space. The search algorithms have three
representative approaches; reinforcement learning (Zhou et al., 2019; Gao et
al., 2020; Zhao et al., 2020b; Deng and Wu, 2023), evolutionary algorithm
(Zhou et al., 2019; Shi et al., 2020; Li and King, 2020; Zhang et al., 2023),
and differentiable search (Zhao et al., 2020a; Huan et al., 2021; Ding et al.,
2021; Li et al., 2021; Cai et al., 2021; Zheng et al., 2023; Xu et al., 2023).
Monte-Carlo tree search belongs to reinforcement learning. Existing
reinforcement learning-based methods employ neural networks to maximize the
expected performance of GNN models. Evolutionary algorithm-based methods take
over the existing model and change the model partially. Differentiable search-
based methods use search space as learnable parameters, so they aim to
optimize the model architecture gradually. EGNAS (Deng and Wu, 2023) mixes
Monte-Carlo tree search and deep reinforcement learning, which divides the
search space by Monte-Carlo tree search and selects architectures by deep
reinforcement learning. To the best of our knowledge, there are no search
algorithms that focus on explainability.

We here note that many Graph NAS methods do not open their codes publicly
(e.g., (Deng and Wu, 2023; Guan et al., 2022; Xu et al., 2023)), so it is
difficult to compare their performance thoroughly. In addition, some Graph NAS
methods require heavy hyper-parameter tuning for each dataset (e.g., DFG-NAS
(Zhang et al., 2022a), AutoHeG (Zheng et al., 2023)). No open codes and heavy
hyper-parameter tunings become obstacles to practical data science.

Explainable NAS. Explainable NAS methods are actively studied to find the
important components (Carmichael et al., 2021; Deb et al., 2002; Liu et al.,
2021; Ru et al., 2021; Tyagi et al., 2023). Their common design rationale is
to avoid using neural models. For example, FOX-NAS uses a simulated annealing
(Liu et al., 2021), and NAS-BOWL uses Bayesian optimization with Weisfeiler-
Lehman kernels (Ru et al., 2021). These works focus on neural networks for
computer vision tasks, and no studies focus on explainable Graph NAS. To the
best of our knowledge, there are no NAS methods with Monte-Carlo tree search
for explainability yet.

Hand-Crafted GNN Architecture. A wide variety of GNN architectures have been
manually designed to learn the node representations (e.g., (Abu-El-Haija et
al., 2019; Chien et al., 2021; Defferrard et al., 2016; Hamilton et al., 2017;
Lim et al., 2021; Maurya et al., 2021; Monti et al., 2017; Xu et al., 2019;
Zeng et al., 2021, 2020; Zhu et al., 2020)). These architectures have their
own specific functionalities depending on their semantics and targets of
graphs.

Various studies aim to capture the characteristics of heterophilic graphs (Zhu
et al., 2020; Maurya et al., 2021; Chien et al., 2021). In particular,
recently they have revisited simple GNN architectures to understand their
impacts on heterophily (Ma et al., 2021; Luan et al., 2022; Li et al., 2022;
You et al., 2020; Lim et al., 2021). These GNN architectures for heterophilic
graphs commonly aggregate embeddings of high-order neighborhoods and/or
emphasize their own embeddings. We utilize them to design our search space. We
compare the performance difference between hand-crafted GNNs and Graph NAS
methods in our experimental studies.

Figure 1. Search space and Monte-Carlo tree search

##  3\. ExGNAS: Explainable Graph NAS

In this section, we present our graph neural architecture search method,
called ExGNAS. We first define our problem.

###### Definition 0 (Explainable Graph Neural Architecture Search Problem).

Given graph $\mathcal{G}$, train/val/test dataset, and search space
$\mathcal{A}$, the explainable graph neural architecture search problem aims
to output (1) the model that achieves the highest accuracy performance with
explainable decision process and (2) the importance of components in
$\mathcal{A}$.

We design a graph neural architecture search method to understand the decision
process and important components for both homophilic and heterophilic graphs.
The main idea is that we combine a simple but effective search space and
search algorithm.

###  3.1. Search Space

The search space defines patterns of GNN architectures. If the search space is
well-designed, Graph NAS methods can cover sub-optimal models for diverse
graphs. Our search space includes two aspects of GNN architectures: Micro-
architecture and macro-architecture. The micro-architecture specifies the
inside of independent GNN layers, and the macro-architecture specifies the
connections between GNN layers. The left-side image in Figure 1 illustrates
our search space on GNN architectures. Intuitively, GNN $1$ – GNN $n$ indicate
the micro-architectures and the whole structure indicates the macro-
architecture.

Design policy. We design the search space that includes fundamental components
without any state-of-the-art complex techniques. This search space generates
non-complex GNN architectures that help to understand what components are
effective in the given graph. To adapt heterophilic graphs, our search space
includes components for emphasizing their own node attributes and jumping
knowledge which are often effective in heterophilic graphs (Abu-El-Haija et
al., 2019; Chen et al., 2020; Chien et al., 2021; Gasteiger et al., 2019; Zhu
et al., 2020).

We represent our search space by a set of architecture parameters instead of
supernets. While supernets are often used for NAS, in particular computer
vision tasks, it is not often used for graph NAS methods. A set of
architecture parameters is helpful in analyzing the important components
because it is easy to compare the generated architectures, while supernets are
hard to understand the important components due to complex architectures.

Micro-architecture. Multi-layer message passing model is a standard GNN
architecture. Message-passing models learn feature representations of nodes
over layers. Formally, the $l$-the GNN layer can be defined as:

(3)
$\mathbf{z}_{u}^{(l)}=\sigma\left(\sum_{v\in\mathcal{N}_{u}}e_{(u,v)}\mathbf{W}^{(l)}\mathbf{z}_{v}^{(l-1)}\right).$

where $\mathbf{z}_{u}^{(l)}$ is the $l$-th layer embedding of node $u$,
$\mathbf{W}^{(l)}\in R^{|\mathbf{z}^{(l)}|\times|\mathbf{z}^{(l-1)}|}$ is
trainable weights, and $\mathcal{N}_{u}$ is the neighborhood of node $u$.
Here, $\mathbf{z}_{u}^{(0)}$ is the attribute of node $u$. $e_{(u,v)}$ and
$\sigma$ indicate the attention between nodes $u$ and $v$ and activation
function, respectively.

Our micro-architecture has three design dimensions; attention, activation, and
embedding size. These are common and standard components in GNN layers. It
does not include model-specific dimensions (e.g., the number of heads for GAT)
to reduce the number of GNN architecture patterns.

Macro-architecture. The macro-architecture determines how GNN layers are
organized into a whole neural network. The common way is to stack multiple GNN
layers. We use jumping knowledge network (JKNet) that connects each output of
GNN layer to the output of the final GNN layer. We also use multilayer
perceptron (MLP) layers before/after GNN layers; we call them preMLP and
postMLP, respectively. In addition, we add skip connections from preMLP to the
final outputs; we call it PreJKNet.

This macro-architecture benefits achieving high accuracy performance in
heterophilic graphs. It is well-known that in heterophilic graphs, node
attributes are often more important than feature aggregation from
neighborhoods because neighborhoods often have different labels (Ma et al.,
2021; Luan et al., 2022; Li et al., 2022; You et al., 2020; Lim et al., 2021;
Zhu et al., 2020). The combination of PreMLP and preJKNet could be effective
for heterophilic graphs, though no Graph NAS studies investigate their
effectiveness.

Architecture Parameters. We describe the architecture parameters of the search
space. Table 1 summarizes the architecture parameters. We separately set
architecture parameters for each GNN layer, for example, when the number of
GNN layers is two, we can set the embedding sizes of the first and second GNN
layers are 32 and 128, respectively. The search space includes over 20 million
GNN architecture patterns in total. We note that there are dependencies of
some architecture parameters, for example, if JKNet is “max”, all embedding
sizes of preMLP and GNN layers should be the same. We can control the
embedding sizes to be fitted to graph size and GPU memory size adaptively.

Table 1. Summary of architecture parameters. $d_{u}$ and $||$ indicate the
degree of node $u$ and concatenation operation, respectively.

Function | Parameters
---|---
The number of GNN layers | 1, 2, 3
Attention | Constant: $e_{(u,v)}=1$
GCN: $e_{(u,v)}=1/\sqrt{d_{u}d_{v}}$
GAT:
$e_{(u,v)}=leakyReLU(\mathbf{W}_{l}\mathbf{z}_{u}||\mathbf{W}_{r}\mathbf{z}_{v})$
Activation | None, Relu, Sigmoid, Tanh
The embedding size of | 16, 32, 64, 128, 256, $y$
of GNN layer
JKNet | None, concat, max
PreJKNet | None, use
PreMLP | None, use
The embedding size | 16, 32, 64, 128, 256
of preMLP
The number of layers | 0, 1, 2
in postMLP
The hidden size | 64, 128, 256
of postMLP

###  3.2. Search algorithm

The characteristics of our search algorithm are using a Monte-Carlo search
tree and not using neural models, which makes the search process explainable
and efficient. This approach is simple but effective in efficiently selecting
GNN architectures.

The right-side image in Figure 1 illustrates how to select architecture
parameters via Monte-Carlo tree search. It traverses the Monte-Carlo tree to
fix the architecture parameters. We assign components in the search space to
tree depths and their architecture parameters to nodes on Monte-Carlo tree (we
call node on Monte-Carlo tree MCT node). In this figure, the number of layers
is assigned to the first layer.

Design policy. Search algorithms often employ neural models, such as
differentiable algorithms (e.g. (Liu et al., 2019)) and deep reinforcement
learning (e.g. (Gao et al., 2020)), to select the next model architectures.
Neural model-based algorithms could be effective in preferentially selecting
highly accurate GNN architectures. However, it needs a learning process for
search algorithms which leads to inefficiency and inexplanability. Therefore,
we employ Monte-Carlo tree search without neural models, which makes the
decision process explainable and can output the importance of components. In
addition, Monte-Carlo tree search is more scalable (i.e., less memory usage)
than other reinforcement learning such as Q-learning because Monte-Carlo tree
search only manages the constructed tree instead of whole tables like
Q-learning.

Architecture selection. The process to select a GNN architecture is following:
(1) select a leaf MCT node, (2) fix architecture parameters according to MCT
nodes on the path from the root to the selected leaf node, and (3) randomly
fix other architecture parameters not fixed yet.

To select leaf MCT node $i$, we define a score of MCT node, which is an
extension of UCB (Upper Confidence Bound) (Kocsis and Szepesvári, 2006), to
find architectures that are expected to be high accuracy. We select the leaf
MCT node $i$ that has the maximum $ucb$ of the following equation:

(4) $ucb(i)=\frac{\sum_{(\alpha,\mathbf{W})\in\mathcal{M}_{i}}{\rm
E_{{Val}}}(\alpha,\mathbf{W})}{m_{i}}+c\sqrt{\frac{\ln M}{m_{i}}}$

where $\mathcal{M}_{i}$ is a set of evaluated models with architecture
parameters of node $i$. $m_{i}$ indicates the selected times of $i$ and its
descendants, and $M$ indicates the number of explored models. $c$ is a
constant to control the balance of exploration and exploitation; larger values
of $c$ correspond to larger amounts of exploration. Since the value of
$usb(i)$ decreases as $m_{i}$ increases, Monte-Carlo tree search can search
for globally optimal rather than locally optimal GNN architectures.

Tree Update. After selecting model architectures, it trains and tests models
to validate the performance of selected GNN architectures. Then, it updates
$ucb$ of MCT nodes on the path from the root to the selected MCT node. If the
MCT node $i$ is selected at $\theta$ times, it generates its child nodes;
these child nodes are preferentially selected next time because $m=0$ (i.e.,
$ucb=\inf$).

We keep the average accuracy performance, the number of selections, and the
average training time on MCT nodes to understand how components affect
accuracy and efficiency. Hyper-parameters. ExGNAS has two hyper-parameters $c$
and $\theta$. We use $\sqrt{2}$ and 10 as default $c$ and $\theta$,
respectively, following existing study (Kocsis and Szepesvári, 2006). We show
that these values have a small impact on the accuracy performance in
experimental studies. Thus, ExGNAS does not require hyper-parameter tuning.

Component order. We determine the order of components to effectively find the
best architecture. Since the components assigned to small tree depths are
fixed earlier, we can investigate the importance of such components. We here
design component orders according to the impact on the performance following
the trends and existing studies in GNNs.

We first fix the number of GNN layers, preMLP, preJKNet, and JKNet because
they can be considered as the components that highly affect the performance
(Ma et al., 2021; Luan et al., 2022; Zhu et al., 2020; Li et al., 2022;
Gasteiger et al., 2019; Lim et al., 2021). Then, we fix activation and
attention functions in the first GNN layer, the embedding size of PreMLP, the
hidden unit size of PostMLP, and the embedding size of the first GNN layer in
this order. Finally, we fix the other components; activation function,
attention function, and the embedding size of later GNN layers, which are hard
to expect their importance.

Time complexity. The architecture selection process traverses Monte-Carlo tree
from the root to leaf nodes, and then randomly selects other parameters. It
takes $O(|\mathbb{F}||\mathbb{A}|)$ where $|\mathbb{F}|$ and $|\mathbb{A}|$
are the numbers of functions and parameters, respectively. These can be
considered as constant, so the architecture selection takes $O(1)$. The tree
update process also traverses Monte-Carlo tree from the leaf to root nodes, so
its time complexity is also $O(1)$. Consequently, the time complexity of our
search algorithm to select GNN architecture is $O(1)$.

Pseudo-code. Algorithm 1 shows the pseudo-code of ExGNAS. It repeatedly
selects architecture $\alpha$ and trains the model (lines 3–6). After training
models, it updates the Monte-Carlo tree according to the accuracy on
validation data (lines 7–9). It updates the best model $\alpha^{*}$ and
$\mathbf{W}^{*}$ if finding better models (lines 10–11). It repeats these
procedures $L$ times (line 2).

input : $\mathcal{G}$, $L$

output : $\alpha^{*}$, $\mathbf{W}^{*}$, $MCT$

1 Initialize $MCT$, $best$;

2 for  _$1,\ldots,L$_ do

3 $i\leftarrow$ leaf node with the maximum $ucs$;

4 $\alpha\leftarrow$ functions of $n_{i}$ with random parameters;

5 Initialize $\mathbf{W}$ of $\alpha$;

6 Train model $(\alpha,\mathbf{W})$ on $\mathcal{G}$;

7 Update $MCT$;

8 if  _$m_{i}\geq\theta$_ then

9 Generate child nodes of $i$;

10

11 if  _$best <\rm{E_{{VAL}}(\alpha,\mathbf{W})}$_ then

12 $\alpha^{*},\mathbf{W}^{*}\leftarrow\alpha,\mathbf{W}$;

13 $best\leftarrow\rm{E_{{VAL}}(\alpha,\mathbf{W})}$;

14

15

16return $\alpha^{*}$, $\mathbf{W}^{*}$, $MCT$;

end procedure

Algorithm 1 ExGNAS

##  4\. Experimental study

We present the results of an experimental evaluation of our method on node
classification tasks. We designed the experiments to answer the following
questions: Q1. What GNN architectures are found by ExGNAS? Q2. How efficient
is the search algorithm of ExGNAS? and Q3. Is ExGNAS helpful in analyzing GNN
architectures?

We implemented our algorithms by Python3 and used a server with NVIDIA V100
Tensor Core GPU and 16 GB GPU memory which is provided instance p3.x2large on
Amazon Web Service.

###  4.1. Experimental Setting

Dataset. We use twelve graphs that are commonly used in GNN tasks. These
graphs include several application domains with different degrees of edge
homophily $H(\mathcal{G})$. Table 2 shows the statistics of graphs that we
used in our experiments.

Table 2. Dataset summary

Dataset | # nodes | # edges | # features | # labels | $H(\mathcal{G})$
---|---|---|---|---|---
Cora | 2,708 | 5,429 | 1,433 | 7 | 0.81
CiteSeer | 3,327 | 4,732 | 3,703 | 6 | 0.73
Amz-P | 7,650 | 238,162 | 745 | 8 | 0.82
Amz-C | 13,752 | 491,722 | 767 | 10 | 0.77
Co-CS | 18,333 | 163,788 | 6,805 | 15 | 0.79
PubMed | 19,717 | 44,338 | 500 | 3 | 0.81
Cornell | 195 | 304 | 1,703 | 5 | 0.13
Wisconsin | 265 | 530 | 1,703 | 5 | 0.20
Chameleon | 2,277 | 36,101 | 2,325 | 5 | 0.23
Squirrel | 5,201 | 217,073 | 2,089 | 5 | 0.23
Actor | 7,600 | 30,019 | 932 | 5 | 0.23
Penn94 | 38,815 | 2,498,498 | 4,772 | 2 | 0.53

Table 3. Overview of AUC in our methods and baselines with standard
deviations. The best results per dataset are highlighted and bold indicates
the top AUC among hand-crafted GNNs or graph NAS methods. DNF stands for ‘Did
Not Finish within 48 hours,’ and OOM refers to ‘Out of Memory.’

| Heterophilic | Homophilic
---|---|---
| Cornell | Wisconsin | Chameleon | Squirrel | Actor | Penn94 | Average | Cora | CiteSeer | Amz-P | Amz-C | Co-CS | PubMed | Average
GCN | 70.2±0.0 | 67.6±0.1 | 85.7±0.0 | 73.9±0.1 | 56.4±0.0 | 89.3±0.0 | 73.9 | 98.4±0.0 | 92.9±0.0 | 98.8±0.0 | 98.7±0.0 | 99.6±0.0 | 96.5±0.0 | 97.4
SGC | 68.3±0.1 | 66.2±0.7 | 82.6±0.0 | 69.4±0.0 | 56.9±0.0 | 73.6±0.0 | 69.5 | 97.5±0.0 | 92.2±0.0 | 97.1±0.0 | 96.4±0.1 | 99.2±0.0 | 95.6±0.0 | 96.3
GAT | 71.7±0.3 | 66.3±0.1 | 88.4±0.0 | 79.0±0.0 | 58.1±0.0 | 88.5±0.0 | 75.3 | 98.3±0.0 | 92.7±0.0 | 99.4±0.0 | 91.5±0.8 | 99.6±0.0 | 96.6±0.0 | 96.4
GCNJK | 75.4±0.2 | 71.0±0.2 | 81.0±0.7 | 79.4±0.0 | 57.9±0.0 | 89.5±0.0 | 75.7 | 98.1±0.0 | 92.9±0.0 | 99.4±0.0 | 99.1±0.0 | 99.7±0.0 | 94.6±0.2 | 97.3
GATJK | 74.4±0.1 | 72.2±0.2 | 89.6±0.0 | 83.0±0.0 | 58.7±0.0 | 88.5±0.0 | 77.7 | 98.1±0.0 | 93.2±0.0 | 99.5±0.0 | 99.2±0.0 | 99.7±0.0 | 96.8±0.0 | 97.8
APPNP | 89.9±0.1 | 90.5±0.1 | 80.9±0.0 | 67.3±0.2 | 71.1±0.0 | 84.0±0.0 | 80.6 | 98.6±0.0 | 93.1±0.0 | 99.3±0.0 | 98.9±0.0 | 99.8±0.0 | 91.1±1.5 | 96.8
MIXHOP | 80.0±0.2 | 88.9±0.1 | 86.8±0.0 | 69.3±0.8 | 68.4±0.0 | 85.5±1.5 | 79.8 | 98.3±0.0 | 92.6±0.0 | 99.4±0.0 | 98.9±0.0 | 99.7±0.0 | 97.4±0.0 | 97.7
GPRGNN | 88.4±0.8 | 88.6±0.1 | 87.7±0.0 | 63.1±0.4 | 70.7±0.1 | 91.9±0.0 | 81.7 | 98.5±0.0 | 93.0±0.0 | 99.4±0.0 | 91.0±2.6 | 99.8±0.0 | 93.1±0.8 | 95.8
GCN2 | 88.9±0.2 | 92.1±0.1 | 80.3±1.8 | 77.6±0.0 | 71.1±0.0 | 85.6±0.0 | 82.6 | 98.5±0.0 | 93.3±0.0 | 99.5±0.0 | 99.3±0.0 | 99.8±0.0 | 89.7±2.4 | 96.7
H2GCN | 88.7±0.0 | 91.2±0.4 | 89.6±0.0 | 79.0±1.0 | 70.0±0.0 | DNF | 83.7 | 98.4±0.0 | 93.3±0.0 | 99.5±0.0 | 99.1±0.0 | 99.7±0.0 | 97.5±0.0 | 97.9
LINKX | 89.4±0.2 | 86.3±0.6 | 87.5±0.0 | 72.5±1.0 | 67.8±0.2 | 93.4±0.0 | 82.8 | 97.0±0.0 | 91.7±0.0 | 99.2±0.0 | 98.8±0.0 | 99.4±0.0 | 95.1±0.0 | 96.9
GloGNN++ | 89.9±0.0 | 94.2±0.2 | 90.1±0.0 | 66.3±0.0 | 31.3±0.0 | 86.2±0.0 | 76.3 | 96.4±0.0 | 74.6±0.0 | 95.6±0.0 | 92.1±0.0 | 95.2±0.0 | 87.3±0.0 | 90.2
GraphNAS | 89.0±1.9 | 86.7±4.0 | 80.9±0.9 | 70.3±1.1 | 64.1±8.3 | DNF | 78.2 | 96.7±0.3 | 92.2±0.9 | 99.6±0.1 | 99.2±0.0 | 99.7±0.0 | 96.8±0.3 | 97.4
GraphGym | 92.6±2.3 | 96.1±2.6 | 83.4±1.3 | 70.3±0.3 | 72.0±0.5 | 93.0±0.2 | 84.6 | 96.7±0.5 | 92.4±1.0 | 99.6±0.1 | 99.2±0.1 | 99.8±0.0 | 97.5±0.3 | 97.6
DFG-NAS | 93.4±0.0 | 94.1±0.1 | 87.2±0.0 | 76.6±0.0 | 69.6±0.0 | 84.5±0.0 | 84.2 | 98.3±0.0 | 93.4±0.0 | 99.5±0.0 | 98.9±0.0 | 99.9±0.0 | 96.5±0.0 | 97.8
Auto-HeG | 89.5±0.3 | 95.5±0.1 | OOM | OOM | 70.1±0.0 | OOM | 85.0 | 93.0±0.0 | 90.9±0.0 | OOM | OOM | OOM | 87.9±3.1 | 90.6
ExGNAS | 92.2±0.0 | 95.1±0.1 | 86.3±0.0 | 80.2±0.0 | 69.5±0.0 | 91.8±0.0 | 85.9 | 98.0±0.0 | 93.2±0.0 | 99.2±0.0 | 98.8±0.0 | 99.6±0.0 | 96.9±0.0 | 97.6

Baselines. We use hand-crafted GNN architectures and Graph NAS methods that
codes are publicly open. First, we use twelve representative GNN
architectures; GCN (Kipf and Welling, 2017), GAT (Veličković et al., 2018),
GCN with jumping knowledge (GCNJK) (Xu et al., 2018), GAT with jumping
knowledge (GATJK), SGC (Wu et al., 2019), APPNP (Gasteiger et al., 2019),
MIXHOP (Abu-El-Haija et al., 2019), GRGNN (Chien et al., 2021), GCN2 (Chen et
al., 2020), H2GCN (Zhu et al., 2020), LINKX (Lim et al., 2021), and GloGNN++
(Li et al., 2022).

Second, we use four graph NAS methods; GraphNAS (Gao et al., 2020), GraphGym
(You et al., 2020), DFG-NAS (Zhang et al., 2022a), and Auto-HeG (Zheng et al.,
2023). GraphNAS, DFG-NAS, and AutoHeG use deep reinforcement learning,
evolutionary algorithm, and differentiable search for their search algorithms,
respectively. Since GraphGym does not have a search algorithm, we use uniform
sampling following existing works (Zhang et al., 2022a).

Performance evaluation. We report the performance as average AUC on the ROC
curve and standard deviation over five random runs (Bradley, 1997). We divide
a set of nodes into train/validation/test in 0.5/0.25/0.25 following existing
works (Lim et al., 2021).

Hyper-parameters. In hand-crafted GNN architectures, we follow the range of
hyper-parameters in existing works (e.g., (Lim et al., 2021)). We choose the
best parameter set from these candidates by utilizing Optuna (Akiba et al.,
2019) for 1,000 trials. We use early stop if continuously do not improve AUC
on validation data ten times, and the maximum number of epochs is 500. In
Graph NAS methods, we search for 1,000 GNN architectures following existing
studies (e.g., (Wang et al., 2020)). For the hyper-parameters of ExGNAS, we
set $\theta$ and $c$ as 10 and $\sqrt{2}$, respectively. In GraphNAS,
GraphGym, DFG-NAS, and AutoHeG, we use default hyper-parameters provided at
their GitHub repository. We do not tune hyper-parameters in Graph NAS methods
to fairly compare run time. We note that GraphGym and AutoHeG include hyper-
parameter space such as learning rate, while the other Graph NAS methods do
not. We describe details of hyper-parameter settings in the appendix.

###  4.2. Performance comparison

Accuracy performance comparison. Table 3 shows the AUC of each method in
heterophilic and homophilic graphs. In heterophilic graphs, we can see ExGNAS
and AutoHeG achieve the highest and second-highest average accuracy among all
baselines, respectively. This indicates that the search spaces for homophilic
graphs are not suitable for heterophilic graphs. We can confirm that ExGNAS is
effective by combining simple search space and algorithm without neural models
in heterophilic graphs.

In homophilic graphs, most methods achieve high AUC even on standard GCN.
ExGNAS achieves comparable performance to the state-of-the-art hand-crafted
GNN architectures. DFG-NAS achieves the highest performance among Graph NAS
methods, while the performance gap is small compared with ExGNAS, GraphNAS,
and GraphGym. AutoHeG does work well for homophilic graphs because they mainly
focus on heterophilic graphs. We can confirm that only ExGNAS supports both
homophilic and heterophilic graphs.

Graph NAS methods except for GraphNAS are averagely higher performance than
hand-crafted GNNs. On the other hand, if we can select suitable hand-crafted
GNNs for each graph, they have higher performance than Graph NAS methods.
However, we need to know various GNNs and the characteristics of graphs to
select suitable hand-crafted GNNs, which causes tremendous effort for users.
Since ExGNAS achieves averagely high performance, it can be practically
effective for data science. Consequently, ExGNAS achieves the highest average
AUC among twelve graphs, so we can validate that ExGNAS can find accurate GNN
architectures for both heterophilic and homophilic graphs.

Model size comparison. Table 4 shows the numbers of parameters on five hand-
crafted GNNs that are high accuracy on heterophilic graphs and ExGNAS in the
three largest heterophilic and heterophilic graphs. We can see that the
numbers of parameters in the GNN architectures generated by ExGNAS are the
smallest in all graphs except for Penn94. Our simple search space contributes
to succinct architectures.

Table 4. The number of parameters [K].

| Heterophilic | Homophilic
---|---|---
| Squirrel | Actor | Penn94 | Amz-C | Co-CS | PubMed
GPRGNN | 218.6 | 536.3 | 425.5 | 452.6 | 3651.6 | 628.2
GCN2 | 497.4 | 1238.9 | 92.6 | 3018.3 | 5648.9 | 1586.7
H2GCN | 872.0 | 273.7 | 277.3 | 161.7 | 2286.0 | 121.0
LINX | 1921.6 | 5053.5 | 23370.8 | 844.0 | 6689.6 | 1175.5
GloGNN++ | 950.5 | 1109.5 | 5596.2 | 1876.5 | 3236.4 | 2604.9
ExGNAS | 138.6 | 176.4 | 367.8 | 83.0 | 804.5 | 76.1

Search efficiency comparison. Figure 2 shows the run time of Graph NAS methods
in homophilic and heterophilic graphs. The run time includes the architecture
search and model training time of GNNs. From these results, ExGNAS, GraphGym,
and DFG-NAS are efficient because their search algorithms do not use neural
models. ExGNAS is much more efficient than the other methods in heterophilic
graphs, while GraphGym and DFG-NAS are often faster than ExGNAS in homophilic
graphs. This indicates that the search space has impacts to model training
time as well as accuracy. GraphNAS and AuthoHeg take a long time because their
search algorithms need model training. We can validate that our simple search
space and algorithm can efficiently find accurate GNN models.

Comparison of search space/algorithm. Table 5 shows the AUC on GraphGym,
uniform sampling with our search space (Uniform), and preferential search for
the maximum accuracy with our search space (Max). We can compare the
performance difference between the search spaces of ExGNAS and GraphGym, and
between Monte-Carlo tree search and others. First, Uniform is higher AUC than
GraphGym in heterophilic graphs, while GraphGym is higher AUC than Uniform in
homophilic graphs. This indicates that our search space is more suitable for
heterophilic graphs than that of GraphGym because they use the same search
algorithm. ExGNAS outperforms Uniform and Max, so we can confirm that Monte-
Carlo tree search preferentially searches for sub-optimal architectures.

Hyper-parameter sensitivity. ExGNAS has two hyper-parameters, $c$ and
$\theta$. Figure 3 shows their impact on the AUC. From this result, we can see
that $c$ and $\theta$ are not sensitive to the AUC. Therefore, we can use
default parameters without tremendous hyperparameter turnings, which leads to
reducing computational costs and improving ease of use.

(a) Heterophilic graphs

(b) Homophilic graphs

Figure 2. Run time [h] including search and model training time. We terminated
the run if it did not finish within 48 hours. OOM indicates out of out-of-
memory in AutoHeG.  Table 5. Comparison of search spaces and algorithms.

| GraphGym | Uniform | Max | ExGNAS
---|---|---|---|---
Homophilic | 97.6 | 97.3 | 97.3 | 97.6
Heterophilic | 84.6 | 85.5 | 85.4 | 85.9

###  4.3. Architecture analysis

We show how ExGNAS is helpful to analyze GNN architectures. We focus on the
difference between GNN architectures for homophilic and heterophilic graphs.
We note that these analyses cannot be conducted by other Graph NAS because
they cannot find suitable GNN architecture for both homophilic and
heterophilic graphs.

Selected architectures. Figure 4 illustrates the GNN architectures that ExGNAS
found on Citeseer, Amz-c, Cornell, and Squirrel. These examples show that the
best architectures significantly differ across graphs. The GNN architectures
for heterophilic graphs (i.e., Cornell and Squirrel) are more complex than
those for homophilic graphs (i.e., Citeseer and Amz-c). In particular, the
best architecture for Citeseer is quite simple, so it indicates that node
labels can be predicted from attributes of neighborhoods. On the other hand,
in Cornell and Squirrel, attributes of own and high-order neighborhoods are
important.

(a) $c$

(b) $\theta$

Figure 3. Impact on hyper-parameters $c$ and $\theta$

(a) Citeseer

(b) Amz-c

(c) Cornell

(d) Squirrel

Figure 4. Selected GNN architectures

(a) Citeceer

(b) Squirrel

Figure 5. Examples of Monte-Carlo trees. Blue-colored letters indicate the
architecture parameters. Table 6. The ratio of the selected functions

| # of GNN layers | Activation | JKNet | Attention
---|---|---|---|---
| 1 | 2 | 3 | none | ReLU | Sigmoid | Tanh | none | concat | max | constant | GCN | GAT
Hom | 0.14 | 0.63 | 0.23 | 0.32 | 0.10 | 0.04 | 0.55 | 0.29 | 0.54 | 0.17 | 0.30 | 0.48 | 0.22
Hetero | 0 | 0.47 | 0.53 | 0.11 | 0.21 | 0.17 | 0.51 | 0.03 | 0.67 | 0.30 | 0.25 | 0.51 | 0.24

Important components. Figure 5 illustrates the Monte-Carlo trees for Citeseer
and Squirrel corresponding to GNN architectures in Figure 4. Each value next
to MCT nodes is the average AUC of GNN architectures with corresponding
architecture parameters of the MCT nodes. We can know important components and
effective/ineffecive combinations of architecture parameters from these trees.

In Citeseer, the average AUC does not have a large gap between the number of
layers one and two (i.e., MCT nodes 2, 3). However, if we select a single GNN
layer, ReLU activation function, and GCN/GAT (i.e., MCT node 29, 30), the AUC
becomes high. While, if we select constant for attention (i.e., MCT node 28),
the AUC does not become high. In addition, if we select a single GNN layer and
Sigmoid activation function (i.e., MCT node 22), the AUC becomes quite low.
This example shows that combinations of architecture parameters are important
rather than architecture parameters themselves. In Squirrel, if we select
concat JKNet (i.e., MCT nodes 17, 20, and 23), the average AUC is high, which
indicates concat JKNet is averagely effective for Squirrel. In addition, if
the GNN architecture includes three GNN layers and concat JKNet (i.e., MCT
node 23), the average AUC becomes quite high. This indicates that it is
effective to separately aggregate embeddings from high-order neighborhoods. We
can analyze the importance of architecture parameters and their combinations
from Monte-Carlo trees.

Selected architecture parameters. Table 6 shows the ratios of selected
architecture parameters in our experiments. This result reveals four
interesting insights. First, GNN architectures for heterophilic graphs should
stack more multiple GNN layers than ones for homophilic graphs. The default
number of layers in most GNNs is two but it may not be optimal for
heterophilic graphs. Second, Hyperbolic tangent is often selected as an
activation function in the best architectures for both homophilic and
heterophilic graphs, though ReLU is commonly used for GNN architectures. Our
results suggest Hyperbolic tangent is better than ReLU. Also, for homophilic
graphs, no activation functions often work well. Third, JKNet is effective for
heterophilic graphs. Among them, concatenation is the most effective in both
types of graphs. Fourth, the gap is small between ratios of selected attention
functions in homophilic and heterophilic graphs, so it may be hard to decide
the best attention functions among concat, GCN, and GAT from graph types.
These insights help to design GNN architectures.

Following the above analysis, we evaluate the performance of GCN with Tanh
function. Table 7 shows the AUC of GCNs with Relu and Tanh in heterophilic
graphs. In Cornell, Wisconsin, and Actor, the AUC increases, while in others,
does not. In particular, in Wisconsin, the AUC increased by 6.0. This
experiment suggests that we need to select activation functions depending on
graphs. ExGNAS helps to analyze the important components and re-design
existing GNN architectures.

Table 7. Impact on ReLU and Tanh of GCN

| Cornell | Wisconsin | Chameleon | Squirrel | Actor | Penn94
---|---|---|---|---|---|---
GCN (ReLU) | 70.2 | 67.6 | 85.7 | 71.9 | 56.4 | 89.3
GCN (Tanh) | 71.1 | 73.5 | 80.3 | 69.8 | 58.1 | 87.9

##  5\. Conclusion

We introduced the explainable graph neural architecture search problem, which
aims to output the best GNN model and the importance of its components. We
proposed an efficient and explainable Graph NAS method via Monte-Carlo tree
search, called ExGNAS, that can handle both homophilic and heterophilic
graphs. Our experimental study showed that ExGNAS (i) effectively and
efficiently finds models that achieve high accuracy compared with hand-crafted
GNN architectures and Graph NAS method and (ii) helps to analyze the GNN
architecture. In the future, we plan to extend our method to automatically
generate architecture parameters according to graphs and tasks and explore
more sophisticated search space and search algorithms.

## References

  * (1)
  * Abu-El-Haija et al. (2019) Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In _ICML_. 21–29.
  * Akiba et al. (2019) Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. 2019.  Optuna: A next-generation hyperparameter optimization framework. In _KDD_. 2623–2631.
  * Bradley (1997) Andrew P Bradley. 1997\.  The use of the area under the ROC curve in the evaluation of machine learning algorithms.  _Pattern recognition_ 30, 7 (1997), 1145–1159.
  * Cai et al. (2021) Shaofei Cai, Liang Li, Jincan Deng, Beichen Zhang, Zheng-Jun Zha, Li Su, and Qingming Huang. 2021.  Rethinking graph neural architecture search from message-passing. In _CVPR_. 6657–6666.
  * Carmichael et al. (2021) Zachariah Carmichael, Tim Moon, and Sam Ade Jacobs. 2021\.  Learning Interpretable Models Through Multi-Objective Neural Architecture Search.  _arXiv preprint arXiv:2112.08645_ (2021).
  * Chen et al. (2020) Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020.  Simple and deep graph convolutional networks. In _ICML_. 1725–1735.
  * Chien et al. (2021) Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2021\.  Adaptive Universal Generalized PageRank Graph Neural Network. In _ICLR_.
  * Deb et al. (2002) Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and T. Meyarivan. 2002.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  _IEEE transactions on evolutionary computation_ 6, 2 (2002), 182–197.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering. In _NeurIPS_.
  * Deng and Wu (2023) TianJin Deng and Jia Wu. 2023.  Efficient graph neural architecture search using Monte Carlo Tree search and prediction network.  _Expert Systems with Applications_ 213 (2023), 118916.
  * Ding et al. (2021) Yuhui Ding, Quanming Yao, Huan Zhao, and Tong Zhang. 2021\.  DiffMG: Differentiable meta graph search for heterogeneous graph neural networks. In _KDD_. 279–288.
  * Duvenaud et al. (2015) David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. 2015\.  Convolutional networks on graphs for learning molecular fingerprints. In _NeurIPS_.
  * Fung et al. (2021) Victor Fung, Jiaxin Zhang, Eric Juarez, and Bobby G Sumpter. 2021.  Benchmarking graph neural networks for materials chemistry.  _npj Computational Materials_ 7, 1 (2021), 1–8.
  * Gao et al. (2020) Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. 2020.  Graph Neural Architecture Search. In _IJCAI_. 1403–1409.
  * Gasteiger et al. (2019) Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2019.  Predict then propagate: Graph neural networks meet personalized pagerank. In _ICLR_.
  * Guan et al. (2022) Chaoyu Guan, Xin Wang, Hong Chen, Ziwei Zhang, and Wenwu Zhu. 2022.  Large-scale graph neural architecture search. In _ICML_. 7968–7981.
  * Hamilton et al. (2017) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _NeurIPS_.
  * Huan et al. (2021) ZHAO Huan, YAO Quanming, and TU Weiwei. 2021.  Search to aggregate neighborhood for graph neural network. In _ICDE_. 552–563.
  * Kipf and Welling (2017) Thomas N. Kipf and Max Welling. 2017.  Semi-Supervised Classification with Graph Convolutional Networks. In _ICLR_.
  * Kocsis and Szepesvári (2006) Levente Kocsis and Csaba Szepesvári. 2006.  Bandit based monte-carlo planning. In _ECML_. 282–293.
  * Li and Talwalkar (2020) Liam Li and Ameet Talwalkar. 2020.  Random search and reproducibility for neural architecture search. In _UAI_. 367–377.
  * Li et al. (2022) Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. 2022.  Finding global homophily in graph neural networks when meeting heterophily. In _ICML_. 13242–13256.
  * Li and King (2020) Yaoman Li and Irwin King. 2020.  Autograph: Automated graph neural network. In _NeurIPS_.
  * Li et al. (2021) Yanxi Li, Zean Wen, Yunhe Wang, and Chang Xu. 2021\.  One-shot graph neural architecture search with dynamic search space. In _AAAI_. 8510–8517.
  * Lim et al. (2021) Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. 2021.  Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. In _NeurIPS_.
  * Liu et al. (2021) Chia-Hsiang Liu, Yu-Shin Han, Yuan-Yao Sung, Yi Lee, Hung-Yueh Chiang, and Kai-Chiang Wu. 2021\.  FOX-NAS: Fast, On-device and Explainable Neural Architecture Search. In _ICCV_. 789–797.
  * Liu et al. (2019) Hanxiao Liu, Karen Simonyan, and Yiming Yang. 2019\.  Darts: Differentiable architecture search.  _ICLR_.
  * Luan et al. (2022) Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2022\.  Is heterophily a real nightmare for graph neural networks to do node classification?  _ICLR_.
  * Ma et al. (2021) Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. 2021\.  Is homophily a necessity for graph neural networks?  _ICLR_.
  * Maurya et al. (2021) Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. 2021\.  Improving Graph Neural Networks with Simple Architecture Design.  _arXiv preprint_ (2021).
  * Monti et al. (2017) Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. 2017.  Geometric deep learning on graphs and manifolds using mixture model cnns. In _CVPR_.
  * Qin et al. (2022) Yijian Qin, Ziwei Zhang, Xin Wang, Zeyang Zhang, and Wenwu Zhu. 2022.  NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search.  _NeurIPS_.
  * Real et al. (2020) Esteban Real, Chen Liang, David So, and Quoc Le. 2020\.  Automl-zero: Evolving machine learning algorithms from scratch. In _ICML_. 8007–8019.
  * Ru et al. (2021) Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. 2021\.  Interpretable neural architecture search via bayesian optimisation with weisfeiler-lehman kernels.  _ICLR_.
  * Sanchez-Gonzalez et al. (2020) Alvaro Sanchez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter Battaglia. 2020.  Learning to simulate complex physics with graph networks. In _ICML_. 8459––8468.
  * Shi et al. (2020) Min Shi, David A Wilson, Xingquan Zhu, Yu Huang, Yuan Zhuang, Jianxun Liu, and Yufei Tang. 2020.  Evolutionary architecture search for graph neural networks.  _arXiv preprint arXiv:2009.10199_ (2020).
  * Tyagi et al. (2023) Anjul Tyagi, Cong Xie, and Klaus Mueller. 2023.  NAS-Navigator: Visual Steering for Explainable One-Shot Deep Neural Network Synthesis.  _IEEE Transactions on Visualization and Computer Graphics_ (2023).
  * Veličković et al. (2018) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018.  Graph Attention Networks. In _ICLR_.
  * Wang et al. (2020) Linnan Wang, Yiyang Zhao, Yuu Jinnai, Yuandong Tian, and Rodrigo Fonseca. 2020.  Neural architecture search using deep neural networks and monte carlo tree search. In _AAAI_. 9983–9991.
  * Wang et al. (2022) Zhen Wang, Zhewei Wei, Yaliang Li, Weirui Kuang, and Bolin Ding. 2022.  Graph Neural Networks with Node-wise Architecture. In _SIGKDD_. 1949–1958.
  * Wu et al. (2019) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019\.  Simplifying graph convolutional networks. In _ICML_. 6861–6871.
  * Xu et al. (2019) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019\.  How powerful are graph neural networks?  _ICLR_.
  * Xu et al. (2018) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018.  Representation learning on graphs with jumping knowledge networks. In _ICML_. 5453–5462.
  * Xu et al. (2023) Peng Xu, Lin Zhang, Xuanzhou Liu, Jiaqi Sun, Yue Zhao, Haiqin Yang, and Bei Yu. 2023.  Do Not Train It: A Linear Neural Architecture Search of Graph Neural Networks. In _ICML_.
  * You et al. (2020) Jiaxuan You, Zhitao Ying, and Jure Leskovec. 2020.  Design space for graph neural networks.  _NeurIPS_ (2020).
  * Zeng et al. (2021) Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor K. Prasanna, Long Jin, and Ren Chen. 2021.  Decoupling the Depth and Scope of Graph Neural Networks.  _NeurIPS_ (2021).
  * Zeng et al. (2020) Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2020\.  GraphSAINT: Graph Sampling Based Inductive Learning Method. In _ICLR_.
  * Zhang et al. (2022a) Wentao Zhang, Zheyu Lin, Yu Shen, Yang Li, Zhi Yang, and Bin Cui. 2022a.  DFG-NAS: DDeep and Flexible Graph Neural Architecture Search. In _ICML_. 26362–26374.
  * Zhang et al. (2022b) Wentao Zhang, Yu Shen, Zheyu Lin, Yang Li, Xiaosen Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. 2022b.  Pasca: A graph neural architecture search system under the scalable paradigm. In _WWW_. 1817–1828.
  * Zhang et al. (2023) Zizhao Zhang, Xin Wang, Chaoyu Guan, Ziwei Zhang, Haoyang Li, and Wenwu Zhu. 2023\.  Autogt: Automated graph transformer architecture search. In _ICLR_.
  * Zhang et al. (2021) Ziwei Zhang, Xin Wang, and Wenwu Zhu. 2021.  Automated machine learning on graphs: A survey.  _arXiv preprint arXiv:2103.00742_ (2021).
  * Zhao et al. (2020b) Huan Zhao, Lanning Wei, and Quanming Yao. 2020b.  Simplifying architecture search for graph neural network.  _arXiv preprint arXiv:2008.11652_ (2020).
  * Zhao et al. (2020a) Yiren Zhao, Duo Wang, Xitong Gao, Robert Mullins, Pietro Lio, and Mateja Jamnik. 2020a.  Probabilistic dual network architecture search on graphs.  _arXiv preprint arXiv:2003.09676_ (2020).
  * Zheng et al. (2023) Xin Zheng, Miao Zhang, Chunyang Chen, Qin Zhang, Chuan Zhou, and Shirui Pan. 2023\.  Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs.  _WWW_ (2023), 611––620.
  * Zhong et al. (2020) Peixiang Zhong, Di Wang, and Chunyan Miao. 2020.  EEG-based emotion recognition using regularized graph neural networks.  _IEEE Transactions on Affective Computing_ (2020).
  * Zhou et al. (2019) Kaixiong Zhou, Qingquan Song, Xiao Huang, and Xia Hu. 2019\.  Auto-gnn: Neural architecture search of graph neural networks.  _arXiv preprint arXiv:1909.03184_ (2019).
  * Zhu et al. (2022) Guanghui Zhu, Wenjie Wang, Zhuoer Xu, Feng Cheng, Mengchuan Qiu, Chunfeng Yuan, and Yihua Huang. 2022.  PSP: Progressive Space Pruning for Efficient Graph Neural Architecture Search. In _ICDE_. 2168–2181.
  * Zhu et al. (2020) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020\.  Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. In _NeurIPS_.

##  Appendix A Hyper-parameters

We select hyper-parameters for the search space according to their papers or
codebases.

GCN.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

SGC.

  * •

Learning rate: $[0.001-0.1]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Hops: $[1]$

GAT.

  * •

Hidden channel: $[4,8,12,32]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

  * •

Heads: $[2,4,8]$

GCNJK.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[2,3,4]$

  * •

Skip connection: [cat, max]

GATJK.

  * •

Hidden channel: $[4,8,12,32]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[2,3,4]$

  * •

Skip connection: [cat, max]

  * •

Heads: $[2,4,8]$

APPNP.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

  * •

GPR alpha: $[0.1,0.2,0.5,0.9]$

MIXHOP.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

  * •

Hops: $[2]$

GPRGNN.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

  * •

GPR alpha: $[0.1,0.2,0.5,0.9]$

GCN2.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[2,8,16,32,64]$

  * •

GCN2 alpha: $[0.1,0.2,0.5]$

  * •

Theta: $[0.5,1.0,1.5]$

H2GCN.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

LINKX.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $[0.001-0.1]$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $[0.001-0.1]$

  * •

Number of layers: $[1,2,3,4]$

GloGNN++.

  * •

Hidden channel: $[4,8,12,32,64,128,256,512]$

  * •

Learning rate: $\\{0.01,0.005,0.01\\}$

  * •

Dropout: $[0-0.9]$

  * •

Weight decay: $\\{0,0.1,0.01,0.001,0.0001,0.0005,0.00001\\}$

  * •

alpha: [0 – 1]

  * •

beta: {0.1, 1, 10, 100, 1000}

  * •

gamma: [0 – 0.9]

  * •

norm layers: 1, 2, 3

  * •

max hop count: [1 – 6]

  * •

delta: [0 – 1.0]

  * •

Orders (Number of adj orders in norm layer): 1, 2, 3

  * •

Orders func id (Sum function of adj orders in norm layer): 2

  * •

Norm func id (Function of norm layer): 2

  * •

Number of layers: $[1,2,3,4]$

We use different sizes of hidden channels for Penn94 to avoid out of memory.
Hidden channel for penn94 is as follows:

  * •

GAT: $[4,8,12]$

  * •

GATJK: $[4,8,12]$

  * •

GCN2: $[4,8,16,32,64]$

  * •

GCNJK: $[4,8,16,32,64]$

  * •

H2GCN: $[8,16,32,64]$

In Graph NAS methods, we fixed the hyper-parameters except for GraphGym and
AutoHeG. GraphGym and AutoHeG search for best hyper-parameters for GNN
architecture during the search process.

GraphNAS.  We used the default parameters that they provided in their Github
repository. We show some parameters (please see full parameters in their
Github).

  * •

Maximum epoch (the number of loops for training controller and generating
architectures): $[10]$

  * •

Number of derived architectures at an epoch: $[100]$

  * •

Training epoch: $[100]$

  * •

Learning rate: $[0.005]$

  * •

Weight decay: $[0.0005]$

GraphGym.  We used the default parameters that they provided in their Github
repository. In GraphGym, these hyper-parameters are explored in their search
process.

  * •

Epoch: $[100,200,400]$

  * •

Learning rate: $[0.1,0.01,0.001]$

  * •

Number of layers before message passing: $[1,2,3]$

  * •

Number of layers for message passing: $[2,4,6,8]$

  * •

Number of layers after message passing: $[1,2,3]$

  * •

Aggregation type: [add, mean, max]

  * •

Dropout: $[0.0,0.3,0.6]$

  * •

Stage type: [stack, skipsum, skipconcat]

DFG-NAS.  We used the default parameters that they provided in their GitHub
repository. Important parameters are the following:

  * •

CiteSeer

    * –

Epoch: $[200]$

    * –

Learning rate: $[0.03]$

    * –

Weight decay: $[0.0005]$

    * –

Dropout for feature: $[0.5]$

    * –

Dropout for layers: $[0.8]$

  * •

PubMed

    * –

Epoch: $[200]$

    * –

Learning rate: $[0.1]$

    * –

Weight decay: $[0.0005]$

    * –

Dropout for feature: $[0.3]$

    * –

Dropout for layers: $[0.5]$

  * •

The others

    * –

Epoch: $[200]$

    * –

Learning rate: $[0.04]$

    * –

Weight decay: $[0.0002]$

    * –

Dropout for feature: $[0.5]$

    * –

Dropout for layers: $[0.8]$

Auto-HeG.  We used the default parameters that they provided in their GitHub
repository. In AutoHeG, these hyper-parameters are explored in their fine tune
model search process.

  * •

The number of base models: 5

  * •

The number of finetune models: 200

  * •

Base model search.

    * –

Learning rate: $[0.005]$

    * –

Weight decay: $[0.0003]$

  * •

Finetune model search.

    * –

All datasets

      * *

In dropout: $[0,0.1,0.2,0.3,0.4,0.5,0.6]$

      * *

Out dropout: $[0,0.1,0.2,0.3,0.4,0.5,0.6]$

      * *

Learning rate: $[0.001-0.01]$

      * *

Weight decay: $[0.00001-0.001]$

    * –

Actor, CiteSeer, Wisconsin

      * *

Epoch: $[1000]$

      * *

Hidden channel: $[16,32,64,128,256]$

    * –

Cora

      * *

Epoch: $[1200]$

      * *

Hidden channel: $[16,32,64,128,256]$

    * –

Cornell

      * *

Epoch: $[800]$

      * *

Hidden channel: $[16,32,64,128,256]$

    * –

PubMed

      * *

Epoch: $[3500]$

      * *

Hidden channel: $[16,32,64]$

    * –

The others. Out of memory before funetune model search

ExGNAS and Uniform

  * •

Learning rate: $[0.01]$

  * •

Weight decay: $[0.001]$