# AutoHEnsGNN: Winning Solution to AutoGraph Challenge for KDD Cup 2020

1st Jin Xu 1  Tsinghua University
Beijing, China
<EMAIL_ADDRESS>2nd Mingjian Chen 1 1The first two authors
contributed equally. Meituan
Beijing, China
<EMAIL_ADDRESS>3rd Jianqiang Huang  Meituan
Beijing, China
<EMAIL_ADDRESS>4th Xingyuan Tang  Meituan
Beijing, China
<EMAIL_ADDRESS>5th Ke Hu  Meituan
Beijing, China
<EMAIL_ADDRESS>6th Jian Li  Tsinghua University
Beijing, China
<EMAIL_ADDRESS>7th Jia Cheng  Meituan
Beijing, China
<EMAIL_ADDRESS>8th Jun Lei  Meituan
Beijing, China
<EMAIL_ADDRESS>
###### Abstract

Graph Neural Networks (GNNs) have become increasingly popular and achieved
impressive results in many graph-based applications. However, extensive manual
work and domain knowledge are required to design effective architectures, and
the results of GNN models have high variance with different training setups,
which limits the application of existing GNN models. In this paper, we present
AutoHEnsGNN, a framework to build effective and robust models for graph tasks
without any human intervention. AutoHEnsGNN won first place in the AutoGraph
Challenge for KDD Cup 2020, and achieved the best rank score of five real-life
datasets in the final phase. Given a task, AutoHEnsGNN first applies a fast
proxy evaluation to automatically select a pool of promising GNN models. Then
it builds a hierarchical ensemble framework: 1) We propose graph self-ensemble
(GSE), which can reduce the variance of weight initialization and efficiently
exploit the information of local and global neighborhoods; 2) Based on GSE, a
weighted ensemble of different types of GNN models is used to effectively
learn more discriminative node representations. To efficiently search the
architectures and ensemble weights, we propose
AutoHEnsGNN${}_{\text{Gradient}}$, which treats the architectures and ensemble
weights as architecture parameters and uses gradient-based architecture search
to obtain optimal configurations, and AutoHEnsGNN${}_{\text{Adaptive}}$, which
can adaptively adjust the ensemble weight based on the model accuracy.
Extensive experiments on node classification, graph classification, edge
prediction and KDD Cup challenge demonstrate the effectiveness and generality
of AutoHEnsGNN.

###### Index Terms:

graph neural network, automated, hierarchical ensemble, kddcup

##  I Introduction

Graphs have been widely applied in real-world applications to model
interacting objects, such as social networks [1, 2], social media [3],
knowledge graphs [4], stocks in the financial market [5] and blockchain [6,
7]. Recently, deep learning on the graph-structured data, named Graph Neural
Network (GNN), has become increasingly popular and produced impressive results
in many real-life graph applications [8, 9, 10]. Many GNN models [11, 12, 13,
14, 15, 16, 17] have been proposed and have achieved start-of-the-art results
in diverse domains [15, 16, 18].

Despite the success of advanced GNN models, there is no single winner that can
dominate others across different tasks [19, 9]. To build an effective model
for practical usage, two problems need to be addressed: 1) Extensive manual
efforts and domain knowledge are required to design an effective architecture,
which can be expensive to design architectures for numerous applications; 2)
For GNN models, the nodes in the graph are not mutually independent and share
the same trainable weights. Thus, the performance of GNN models has high
variance with different initialization or training/validation splits of the
graph, called pitfalls of GNN evaluation (see [19]). For real-life scenarios,
we need to manually (usually randomly) decide the split of training and
validation, and obtain reliable predictions for the unseen test set. Without
considering variance caused by these factors, models may not generalize well
to the unseen test set. These problems hinder real-life applications of the
existing GNN models due to the demand of human experts and the variance of GNN
models. Therefore, there is a strong demand for automatically designing and
training GNN models which can deliver robust and accurate predictions for
various tasks.

Previous work on automated GNN [20, 21, 22, 23, 24] mainly focuses on
searching a single novel architecture (e.g., aggregate function, activate
function), which has achieved impressive performance on the public benchmark
[8]. However, reinforcement learning [20, 21, 22] and evolutionary algorithms
[22] based micro-search on a single model usually require significant
computational resources, which is unaffordable for practical deployment. One-
shot supernet based methods [21, 24] mainly utilize weight sharing to improve
efficiency but the weight sharing is quite sensitive to the search space [25,
26, 27, 28], which still requires careful design of search space by human
experts. In addition, existing work does not consider the variance of the GNN
model, which is important for real-life applications.

To resolve the above issues, we propose Automated Hierarchical Ensemble of
Graph Neural Network (AutoHEnsGNN) to automatically ensemble a group of
effective models for graph tasks without any human intervention. Rather than
searching novel architectures for individual models, the core idea is that
ensemble of multiple models can be much more effective and robust than
individual models [29, 30, 31, 32]. Specifically, we first propose a novel
proxy evaluation method to efficiently rank the existing models and select a
pool of models with high performance for a given task. Our experiments
demonstrate that the model selection accelerated by proxy evaluation can be
5$\sim$10 $\times$ faster than the accurate selection, and can find top-
performing models with a high Kendall rank correlation coefficient. Then, we
propose graph self-ensemble (GSE), which constructs the ensemble of the same
type of models from the pool with different initializations to reduce the
variance and different layers to exploit the information from local and global
neighborhoods. Real-world graphs usually have a combination of several
properties, which are difficult to capture by a single approach. Thus, we
further apply a weighted ensemble of different types of models in the pool to
aggregate multiple graph representation. To efficiently search the layers and
ensemble weights, we propose a gradient-based algorithm called
AutoHEnsGNN${}_{\text{Gradient}}$ by treating them as architecture parameters
and formulating the search as a bi-level optimization problem [33, 34, 35].
Then we apply time-efficient first-order approximation to iteratively update
the weights of the model and architectures. Besides, we propose
AutoHEnsGNN${}_{\text{Adaptive}}$, which can adaptively adjust the ensemble
weights according to the performance of models in the pool. It can avoid co-
training different types of models and is tailored for scenarios with limited
GPU memory. In addition, we also construct bagging of models trained on the
different splits of the dataset to further reduce the variance.

We summarize our contributions as follows:

  * •

We propose a novel and practical framework, named AutoHEnsGNN, which can
automatically ensemble a pool of effective models to enable robust and
accurate predictions for graph tasks without any human intervention.

  * •

To improve the efficiency, we propose a proxy evaluation method for automatic
model selection, and a gradient-based optimization algorithm for searching
ensemble weights and model configurations. Besides, for scenarios with limited
GPU memory, we propose a method to adaptively adjust the ensemble weights.

  * •

In the AutoGraph challenge for KDD Cup 2020, AutoHEnsGNN won 1st place and
achieved the best rank score of five datasets on average in the final phase.
The ablation study and extensive experiments also show the effectiveness of
AutoHEnsGNN.

##  II Related Work

Figure 1: Overview of AutoHEnsGNN. Given an input graph dataset, AutoHENsGNN
automatically builds models and makes predictions without any human
intervention. First, a proxy evaluation method is conducted to efficiently
select several top-performing GNN models $\mathcal{P}_{\text{GNN}}$ from
numerous candidate ones. Then, these top-performing models can be organized in
a way of the hierarchical ensemble. Two algorithms
AutoHEnsGNN${}_{\text{Adaptive}}$ and AutoHEnsGNN${}_{\text{Gradient}}$ can be
used to search for the hierarchical ensemble’s configurations such as ensemble
weights and architecture parameters. Finally, top-performing models with
searched optimal configurations from scratch are re-trained and aggregated in
the way of the hierarchical ensemble for effective and robust predictions.

###  II-A Graph Neural Network

Graph Neural Network (GNN) [13, 36, 37, 38, 39, 40, 41], as a new type of
neural network for learning over graphs, has shown its superiority over graph-
agnostic neural networks on diverse tasks [12, 14, 13, 42]. Many designs of
aggregators such as convolutional aggregator [12, 43, 13], attention
aggregator [11], gate updater [44] and skip connection [45] have been proposed
and achieved impressive results in diverse domains [15, 16, 18]. Each type of
design can exploit a specific structural property [46]. For example, GIN [14],
with injective aggregating function, can better capture the structure
properties, GCNII [47], with deeper layers, can capture long-distance
dependency in the graph. However, it has been shown that no single model
outperforms other methods across different datasets [48, 19]. Real-life graphs
usually have a combination of several properties and they are difficult to
characterize and capture by a single model. Moreover, the performance of the
model has high variance with the different splits of the dataset and training
configurations [19]. In this paper, rather than using individual models, we
automatically ensemble a group of effective models to exploit diverse
properties of the dataset, and propose hierarchical ensemble to obtain
effective and robust results.

###  II-B Automatic Neural Architecture Search for Graphs

Neural Architecture Search (NAS) automates the process of discovering high-
performance architectures and has, therefore, received broad attention [20,
22, 23, 22, 49, 50]. To automatically search a GNN model for a task, previous
work mainly focuses on neural architecture search to deliver an individual
model based on reinforcement learning [20, 22, 23], evolutionary algorithms
[22] and one-shot supernet [21, 24]. However, reinforcement learning and
evolution based methods are computationally expensive since they require
training architectures from scratch to obtain their ground-truth accuracy.
One-shot supernet based methods mainly utilize weight sharing to improve
training efficiency by maintaining a single copy of weights on a supernet that
contains all the sub-models (architectures) in the search space and reuse the
weights of shared operators from previously trained sub-models. However, the
training process with weight sharing is quite sensitive to the design of the
search space [25, 26, 27, 28] and configurations of searching [25, 28] due to
the interference of different sub-models [51]. These methods still require
human expertise to carefully design the search space and searching
configurations to get good results. Different from existing methods,
AutoHEnsGNN automatically selects models from the candidate pool and
efficiently searches the optimal configurations of the hierarchical ensemble
without human intervention, which is more effective and reliable for real-life
deployment. Note that the novel architectures searched by NAS algorithms are
complementary to AutoHEnsGNN, that is, one can first apply NAS to search novel
architectures and then add them to the candidate pool for the ensemble.

###  II-C Ensemble Learning of Graph Neural Network

Ensemble learning, as an efficient technique that aggregates multiple machine
learning models, can achieve overall high prediction accuracy and good
generalization [52]. Zhao et al. [53] integrate individual graph embedding for
biological gene interaction prediction. Ren et al. [54] use an ensemble of
GNNs to increases model accuracy for the circuit parameter prediction. Kong et
al. [55] leverage tree-based feature extractors followed by graph neural
networks to learn robust representation on omics data. These methods manually
selects several models for ensemble and directly apply ensemble to get more
accurate and stable performance on specific tasks. Goyal et al. [46] greedily
add the model to the ensemble and theoretically study the benefits of the
ensemble for graph tasks. Different from existing work, AutoHEnsGNN
automatically and efficiently selects top-performing models, and then uses
novel hierarchical ensemble and search algorithms for effective and robust
predictions.

##  III Method

In this section, we introduce the details of AutohEnsGNN, which automatically
builds effective and robust GNN models without human intervention. We first
give an overview of AutohEnsGNN, and then introduce each component of it.

###  III-A Overview

In this paper, we focus on the semi-supervised node classification tasks in
graphs, which is a fundamental problem in graph mining. We are given a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A})$, where $\mathcal{V}$ is the
set of vertices $\\{v_{1},\cdots,v_{n}\\}$, $\mathcal{E}$ is the set of edges,
and $\mathbf{A}\in\mathbb{R}^{n\times n}$ is the weighted adjacency matrix of
the graph. AutoHEnsGNN mainly contains two components:

  * •

Proxy evaluation for GNN model selection. Considering the heavy computation
cost of training for model selection, we approximate the performance of each
model on the proxy task to enable fast and parallel training. Then we can
efficiently rank the candidates and select top-performing ones.

  * •

Hierarchical ensemble and architecture search. We first aggregate
representations learned by models (same type but different initializations and
layers) and then apply a weighted ensemble on different types of models. The
design is based on three considerations: 1) The results of GNN models are
sensitive to the initialization (see [19]); 2) Different layers of GNN models
can be aggregated to effectively exploit the information from local and global
neighborhoods [56, 57]; 3) Ensemble of models can capture different properties
of graphs to further improve the performance. Then, we propose two algorithms
to efficiently search configurations of the hierarchical ensemble. After
searching, we can re-train the hierarchical model with optimal configurations
and make predictions. The overview of AutoHEnsGNN is shown in Figure 1.

###  III-B Proxy evaluation for GNN model Selection

Although it has been shown that various specific architectures can efficiently
capture certain properties of a graph and achieve state-of-the-art results
[11, 12, 13, 14, 15, 16], there is no model that can surpass other ones across
all the datasets [19, 9]. Given a new dataset, we aim to first select models
with the top performance from existing work, and then construct the ensemble
for predictions. To get the accurate evaluation for a GNN model, we 1)
randomly split the dataset into training and validation dataset, search the
optimal configurations and train the GNN model on the training set; 2) repeat
1) many times and construct bagging of models trained on the different splits
of the dataset to reduce variance in the resulting predictions. Since we
cannot access the labels of the test set, we randomly split a test set from
the training set. Then, we can evaluate models on the same test set and select
the top ones.

Many GNN models have been proposed [58] and achieved state-of-the-art results
on diverse domains [1, 3, 4, 15, 16, 18]. It is time-consuming to accurately
evaluate the performance of these candidate models and their variants. To
improve the efficiency of model selection, we propose to approximate the
performance of the model on the proxy task and select promising models. The
proxy task contains 1) a proxy dataset: the model is trained on the sampled
training dataset (sub-graph), which can largely reduce the training time and
GPU memory consumption; 2) a proxy model: a model with a smaller hidden size
is trained to reduce the computational cost and accelerate the training
process; 3) a proxy bagging: a few models are trained on the different splits
of the dataset for bagging. The key insight of proxy evaluation is that we
actually care about the ranking of candidate models to select the promising
models for the next stage, thus, it is not necessary to acquire highly
accurate results. Due to fast training and low GPU memory consumption, we can
quickly evaluate the performance of candidate models in parallel, and choose
the top ones for the next stage. We empirically demonstrate the effectiveness
of proxy evaluation in Section IV-B.

###  III-C Hierarchical Ensemble and Architecture Search

Denote the pool of GNN models selected by proxy evaluation as
$\mathcal{P}_{\text{GNN}}=\\{\mathcal{N}_{i}\\}_{i=1,\cdots,N}$, where $N$ is
the number of models for ensemble. In this section, we present how to build a
hierarchical ensemble and search the configurations efficiently. First, we
describe the framework of the hierarchical ensemble. Then, to search the
layers of each sub-model and ensemble weight, we propose
AutoHEnsGNN${}_{\text{Gradient}}$, which jointly optimizes architecture
parameters via gradient-based search. Besides, we also propose a memory-
efficient algorithm, AutoHEnsGNN${}_{\text{Adaptive}}$, which optimizes each
model separately and adaptively adjusts the ensemble weights based on the
accuracy of models.

####  III-C1 Hierarchical Ensemble

Figure 2: Given $N$ different types of graph sub-models, we build a
hierarchical ensemble network. For each type of sub-model, we build $K$
repeated models with different initialization seeds and layers, where each one
is equipped with a one-hot vector $\alpha$ to decide which layer’s output for
aggregation. $K$ repeated models are aggregated (graph self-ensemble) for
joint predictions to reduce the variance and efficiently exploit the
information of local and global neighborhoods. Then, we further apply a
weighed ensemble (weight $\beta$) of different types of sub-models to
effectively learn more discriminative node presentation. $\alpha$ and $\beta$
can be searched efficiently by AutoHEnsGNN${}_{\text{Adaptive}}$ and
AutoHEnsGNN${}_{\text{Gradient}}$ algorithms (best viewed in color).

To reduce the variance and efficiently aggregate the information of local and
global neighborhoods, we propose graph self-ensemble (GSE), where several sub-
models with different initializations and layers are assembled for joint
prediction. First, for each sub-model $\mathcal{N}$ in $\mathcal{P}$,

$\mathbf{H}^{(l)}=f_{\mathcal{N}}^{l}(\mathbf{A},\mathbf{H}^{(l-1)}),l=1,\cdots,L$
(1)

where $f_{\mathcal{N}}^{l}$ is the $l$-th layer of network $\mathcal{N}$,
$\mathbf{H}^{(0)}$ represents the input features matrix, $\mathbf{H}^{(l)}$
refers to the output of the $l$-th layer and $L$ is the maximum number of
layers of the model. For node classification, the last layer of GNN predicts
the labels via a softmax classifier. Denote the predictions for $n$ nodes as
$\mathbf{\hat{Y}}\in\mathbb{R}^{n\times C}$ where $C$ is number of classes. To
search the number of layers for the sub-model, we further introduce a set of
one-hot architecture parameters
$\bm{\alpha}=\\{\alpha_{1},\cdots,\alpha_{L}\\}$. Then, the prediction of the
model can be written as

$\mathbf{\hat{Y}}=\text{softmax}((\sum_{l=1}^{N}\alpha_{l}\mathbf{H}^{(l)})\mathbf{W}),$
(2)

where $\mathbf{W}$ is a learnable transformation matrix. In this way, we can
simply adjust $\mathbf{\alpha}$ to select the number of layers for a sub-
model. Recent GNN models follow a neighborhood aggregation procedure and learn
to iteratively aggregate the hidden features of every node in the graph with
its adjacent nodes layer by layer [12, 14, 13, 42, 59, 43, 11]. Theoretically,
an aggregation process of $l$ layers can access the $l$-hop neighborhood.
However, for the GNN model, [57, 14] find that aggregating the information
from different layers (local and global neighborhoods) can lead to more
discriminative node representation. In light of the fact, we build several
sub-models denoted as $\\{\mathcal{N}^{(1)},\cdots,\mathcal{N}^{(K)}\\}$ with
different layers (different $\bm{\alpha}$) and the final output of the sub-
model $\mathcal{N}$ can be written as

$\mathbf{\hat{Y}_{\mathcal{N}}}=\frac{1}{K}\sum_{k=1}^{K}\mathbf{\hat{Y}_{k}}.$
(3)

The overview of GSE is shown in Fig. 2. $K$ models with different layers and
initialization seeds are aggregated for joint predictions.

GSE can exploit the potential of individual GNN models and reduce the variance
caused by initializations. However, real-world graphs have a combination of
multiple properties that are difficult to characterize by a single approach.
For example, the behavior of a user in the social network may be affected by
both the community (global) and its neighbors (local), which requires models
to be able to find the communities and effectively aggregate the information
from adjacent nodes. Thus, we first construct GSE to each sub-model in
$\mathcal{P}_{\text{GNN}}$ and assemble these models as in Fig. 2. In this
way, self-ensemble of different layers can force each sub-model to learn
different structures due to different reception fields (layers); 2) different
models may be good at extracting different features (local/global), and thus
ensemble of them could combine their advantages. Formally, we can get
$\mathbf{\hat{Y}_{\mathcal{N}_{j}}}$, according to Eqn. 3, for each sub-model
$\mathcal{N}_{j}$ in $\mathcal{P}_{\text{GNN}}$. Then the final results can be
formulated as

$\mathbf{\hat{Y}_{\mathcal{P}}}=\sum_{j=1}^{N}\beta_{j}\mathbf{\hat{Y}_{\mathcal{N}_{j}}},$
(4)

where the different sub-models are assembled with the weight vector
$\bm{\beta}=\\{\beta_{1},\cdots,\beta_{N}\\}$ and
$\beta_{j}=\frac{\text{exp}(\hat{\beta}_{j})}{\sum_{j^{{}^{\prime}}=1}^{N}\text{exp}(\hat{\beta}_{j^{{}^{\prime}}})}$
is the normalized weight to determine the contribution of different sub-models
to final predictions. For node classification problems, the cross-entropy loss
$\mathcal{L}$ is given by

$\mathcal{L}=-\mathbf{Y}\cdot\log(\mathbf{\hat{Y}_{\mathcal{P}}}),$ (5)

where $\mathbf{Y}\in\mathbb{R}^{n\times C}$ is the ground truth label.

To efficiently search the architectures parameter $\bm{\alpha}$ and ensemble
weight $\bm{\beta}$, we introduce AutoHEnsGNN${}_{\text{Gradient}}$ and
AutoHEnsGN-N${}_{\text{Adaptive}}$.

####  III-C2 AutoHEnsGNN${}_{\text{Gradient}}$

Searching the effective architectures ($\bm{\alpha}$ and $\bm{\beta}$) can be
formulated as a bi-level optimization problem [33, 34, 35] as follows:

$\displaystyle\min_{\bm{\alpha},\bm{\beta}}\mathcal{L}_{val}(\bm{w}^{*}(\bm{\alpha},\bm{\beta}),\bm{\alpha},\bm{\beta}),$
(6) $\displaystyle
s.t.\qquad\bm{w}^{*}(\bm{\alpha},\bm{\beta})=\text{argmin}_{\bm{w}}\mathcal{L}_{train}(\bm{w},\bm{\alpha},\bm{\beta}).$

It means that, given architecture parameters $\bm{\alpha},\bm{\beta}$, the
trainable weight $\bm{w}^{*}$ associated with the architecture are obtained by
minimizing the training loss. Then our goal of architecture search is to find
the best architecture configurations $\bm{\alpha}^{*},\bm{\beta}^{*}$ that
minimizes the validation loss
$\mathcal{L}_{val}(\bm{w}^{*},\bm{\alpha}^{*},\bm{\beta}^{*})$. To make the
search space continous so that we can calculate the gradient, we relax the
one-hot vector $\bm{\alpha}$ to a softmax over all possible layers, and then
the prediction of the sub-model in Eqn. 2 can be written as:

$\mathbf{\hat{Y}}=\text{softmax}((\sum_{l=1}^{N}\frac{\text{exp}(\hat{\alpha}_{l})}{\sum_{l^{{}^{\prime}}=1}^{N}\text{exp}(\hat{\alpha}_{l^{{}^{\prime}}})}\mathbf{H}^{(l)})\mathbf{W}),$
(7)

where $\hat{\alpha}_{l}$ is trainable parameter.

By relaxing $\bm{\alpha}$, we can directly calculate the gradient
$\nabla_{\bm{\alpha}}\mathcal{L}_{val}(\bm{w}^{*}(\bm{\alpha}),\bm{\alpha})$
and $\nabla_{\bm{\beta}}\mathcal{L}_{val}(\bm{w}^{*}(\bm{\beta}),\bm{\beta})$.
To avoid expensive inner optimization, we use the first-order approximation
[35] to iteratively update weights of model and architectures. The procedure
is given by Algorithm 1. After the optimization, we can derive the sub-model
with $L^{*}$ layers where
$L^{*}=\text{arg}\max_{l}\frac{\text{exp}(\hat{\alpha}_{l})}{\sum_{l^{{}^{\prime}}=1}^{N}\text{exp}(\hat{\alpha}_{l^{{}^{\prime}}})}$.
Then, the layers of sub-models and $\bm{\beta}$ are fixed and each model in
AutoHEnsGNN can be re-trained separately and aggregated in the way of the
hierarchical ensemble.

Joint optimization of architecture parameters can search for better
configurations due to consideration of the interaction of different models.
Because of the gradient optimization, the search time is roughly equal to the
training time of each individual model. However, the GPU memory consumption is
roughly $K\times N$ times that of each individual model. To reduce the
computational cost, we train the model on the proxy task (small hidden size,
sampled dataset) as mentioned in Section III-B.

Result: Return $\bm{\alpha}$ and $\bm{\beta}$

1 i=0; Update architecture weights $\bm{\alpha}$ and $\bm{\beta}$ every $M$
iterations;

2 while  _not converged_ do

3 i+=1;

4 Get the $i$-th iteration of data;

5 Calculate the gradient
$\nabla_{w}\mathcal{L}_{train}(\bm{w},\bm{\alpha},\bm{\beta})$ of weight $w$
and apply gradient descent;

6 if  _(i % M == 0)_ then

7 Calculate the gradient
$\nabla_{\mathbf{\bm{\alpha}}}\mathcal{L}_{val}(\bm{w}^{*}(\bm{\alpha}),\bm{\alpha})$
of weight $\bm{\alpha}$ and apply gradient descent;

8 Calculate the gradient
$\nabla_{\bm{\beta}}\mathcal{L}_{val}(\bm{w}^{*}(\bm{\beta}),\bm{\beta})$ of
weight $\bm{\beta}$ and apply gradient descent;

9 end if

10

11 end while

Algorithm 1 Architecture Search for AutoHEnsGNNGradient

####  III-C3 AutoHEnsGNN${}_{\text{Adaptive}}$

Although the proxy task can reduce the computational cost,
AutoHEnsGNN${}_{\text{Gradient}}$ still consumes more GPU memory as analyzed
above, which cannot meet the requirements of scenarios with very limited GPU
memory. Thus, we further propose AutoHEnsGNN${}_{\text{Adaptive}}$ to
adaptively adjust ensemble weights according to the accuracy of each model: 1)
Rather than co-training to search the number of layers of different self-
ensembles, AutoHEnsGNN${}_{\text{Adaptive}}$ individually optimize each one,
which can largely reduce the search space from $L^{K\times N}$ to $L^{K}$; 2)
For each self-ensemble, considering the reduced search space,
AutoHEnsGNN${}_{\text{Adaptive}}$ directly applies grid search to find the
best configurations; 3) Rather than searching the ensemble weight, we design
an adaptive $\bm{\beta}$ as follows:

$\displaystyle\bm{\beta}=\text{softmax}(\frac{\textbf{acc}}{\tau}),$ (8)
$\displaystyle\tau=1+\frac{(1+\min(\epsilon,1+\log(\frac{\text{\\#edges}}{\text{\\#nodes}}+1)))^{\lambda}}{\gamma},$

where $\tau$ is the annealing temperature,
$\textbf{acc}=\\{\text{acc}_{1},\cdots,\text{acc}_{N}\\}$ is the normalized
validation accuracy of different sub-models, $\epsilon$, $\gamma$ and
$\lambda$ are hyper-parameters. The intuition is that models with a high score
should be assigned with a large weight. We empirically find that, when the
average degree is small (sparse graph), a sharp softmax distribution can
obtain better results. Given a sparse graph (the term in Eqn 8 is smaller than
$\epsilon$), the sparser graph, the smaller $\tau$, which can assign more
weights to promising models.

##  IV Experiments and Results

###  IV-A Datasets

TABLE I: Statistics of anonymous public datasets in AutoGraph Challenge of KDD
Cup 2020.

Dataset |  | Node
---
Feat.
| Edge
---
Feat.
Directed |  | Nodes
---
Train/Test
Edges | Classes
A | $\checkmark$ | - | - | 1088/1620 | 5278 | 7
B | $\checkmark$ | - | - | 1334/1993 | 4552 | 6
C | $\checkmark$ | - | - | 4026/5974 | 733316 | 41
D | $\checkmark$ | $\checkmark$ | $\checkmark$ | 4009/5991 | 5833962 | 20
E | - | - | - | 3011/4510 | 7804 | 3

####  IV-A1 Anonymous datasets in AutoGraph Challenge of KDD Cup 2020

The competition focuses on the semi-supervised classification tasks on graphs.
As is shown in Table I, there are 5 anonymous public datasets provided by KDD
Cup 2020. The datasets are collected from real-world business, and are
shuffled and split into training and test parts. Each dataset contains two
node files (training and test), an edge file, a feature file, a training
dataset label file, and a metadata file. Table X in Appendix presents an
example of the anonymous dataset.

####  IV-A2 Public Datasets

We also conduct experiments on three benchmark graphs Cora, Citeseer, and
Pubmed [60], which are the most widely used benchmark datasets for semi-
supervised node classification [8]. Since these graph datasets only have
thousands of nodes, we further conduct experiments on ogbn-arxiv [9], which
contains 169,243 nodes, to demonstrate the scalability of our proposed
methods. We do not conduct data processing or feature engineering on these
datasets.

###  IV-B Analysis of Proxy Evaluation

To construct the hierarchical ensemble, firstly, we need to construct a pool
of promising models by evaluating the performance of the given task. In order
to avoid time-consuming evaluation, we propose to train the models on the
proxy task. The key to proxy evaluation is to efficiently train the model and
rank the models accurately. In this section, we use more than 20 models to
demonstrate that proxy evaluation can be more memory-efficient and 5$\sim$10
$\times$ faster than accurate evaluation with high ranking accuracy.

---
|  $D_{\text{proxy}}$ (%) |  $B_{\text{proxy}}$ |  $M_{\text{proxy}}$ (%)
---|---|---
(a) Dataset A
|  $D_{\text{proxy}}$ (%) |  $B_{\text{proxy}}$ |  $M_{\text{proxy}}$ (%)
---|---|---
(b) Cora
Figure 3: Analysis of proxy evaluation. Each row (dataset) has three sub-
figures from left to right, which show the Kendall rank correlation
coefficient and training efficiency related to the proxy dataset, proxy
bagging, and proxy model respectively.

####  IV-B1 Models for Proxy Evaluation

To demonstrate the effectiveness of proxy evaluation, we select more than 20
types of GNN models with diverse designs of aggregators including
convolutional aggregator (including spectral-based [12, 61, 43, 62] and
spatial-based [13, 36, 14, 39, 63, 64, 41, 65, 66, 67] aggregators), attention
aggregator [68, 69], skip connection [45, 70, 47], gate updater [44] and
dynamic updater [71]. These models have achieved impressive results from
diverse domains and have potential to handle different types of graphs.111We
just sample some models from each category in our experiments. Models that are
not listed here do not indicate poor performance. For example, [36] can make
use of edge weight (edge feature) for message passing and GCNII [47], with
deeper layers, can capture long-distance dependency in the graph.

####  IV-B2 Effectiveness of Proxy Evaluation

##### Training Configurations

The model architectures follow the original papers and we implement them with
Pytorch [72]. For public datasets Cora, Citeseer, and Pubmed, we use the exact
training configurations and hyper-parameters as the original implements. For
the anonymous dataset in AutoGraoh Challenge, we use the same training
procedure for all of the models. More details are introduced in Appendix A-A1.

TABLE II: Results on the anonymous dataset in AutoGraph Challenge. P-values
are calculated between AutoHEnsGNN${}_{\text{Gradient}}$ and Goyal et al.
[46]. AutoHEnsGNN${}_{\text{Gradient}}$ significantly outperforms baseline
methods in A, B, C and D dataset (two-side wilcoxon test, p-values$<$0.05).

Method | A | B | C | D | E
---|---|---|---|---|---
GCN [12] | 85.2$\pm$0.8 | 72.0$\pm$0.5 | 92.5$\pm$0.3 | 94.9$\pm$0.1 | 87.5$\pm$0.1
GAT [11] | 83.3$\pm$0.8 | 71.2$\pm$0.4 | 89.4$\pm$0.7 | 94.6$\pm$0.4 | 87.8$\pm$0.1
APPNP [65] | 76.8$\pm$0.6 | 69.2$\pm$1.0 | 72.8$\pm$0.8 | 93.8$\pm$0.0 | 87.4$\pm$0.1
TAGC [61] | 85.6$\pm$0.6 | 72.5$\pm$0.5 | 91.6$\pm$1.2 | 93.9$\pm$0.1 | 88.6$\pm$0.1
DNA [45] | 82.7$\pm$1.2 | 71.0$\pm$0.7 | 88.6$\pm$0.6 | 93.8$\pm$0.0 | 87.4$\pm$0.2
GraphSAGE [13] | 84.4$\pm$0.7 | 71.1$\pm$0.4 | 73.6$\pm$3.5 | 93.9$\pm$0.0 | 88.1$\pm$0.2
GraphMix [73] | 86.3$\pm$0.4 | 73.1$\pm$0.7 | 87.5$\pm$0.3 | 94.0$\pm$0.2 | 87.7$\pm$0.0
Grand [66] | 87.0$\pm$0.5 | 73.9$\pm$0.5 | 91.0$\pm$0.7 | 93.6$\pm$0.2 | 88.0$\pm$0.2
GCNII [47] | 87.7$\pm$0.5 | 73.6$\pm$0.6 | 89.3$\pm$0.8 | 93.5$\pm$0.1 | 88.1$\pm$0.0
D-ensemble | 88.1$\pm$0.3 | 74.3$\pm$0.4 | 93.4$\pm$0.4 | 95.0$\pm$0.1 | 88.7$\pm$0.1
L-ensemble | 88.5$\pm$0.3 | 75.0$\pm$0.2 | 93.8$\pm$0.6 | 95.5$\pm$0.1 | 88.7$\pm$0.1
Goyal et al. [46] | 88.7$\pm$0.3 | 74.5$\pm$0.3 | 93.9$\pm$0.4 | 95.7$\pm$0.0 | 88.7$\pm$0.1
AutoHEnsGNN${}_{\text{Ada.}}$ | 89.3$\pm$0.1 | 75.5$\pm$0.2 | 94.4$\pm$0.2 | 96.1$\pm$0.0 | 88.7$\pm$0.1
AutoHEnsGNN${}_{\text{Grad.}}$ | 89.6$\pm$0.1 | 76.1$\pm$0.2 | 94.7$\pm$0.2 | 96.3$\pm$0.0 | 88.8$\pm$0.1

##### Analysis

We can evaluate a model accurately by 1) randomly splitting the dataset into
training and validation dataset, automatically searching the best hyper-
parameters and optimizing the weight of the GNN model on the train set; 2)
repeating 1) many times (10 times in our experiments) and constructing bagging
of models trained on the different splits of the dataset to get robust and
accurate results. To avoid time-consuming evaluation, we optimize the model
with a smaller hidden size (proxy model) on the partial training set (proxy
dataset) and repeat a few times of 1) for bagging (proxy bagging). We denote
the ratio of the sampled training set, training times for bagging, and the
ratio of the hidden size of the reduced model compared to that of the original
model by $D_{\text{proxy}}$, $B_{\text{proxy}}$ and $M_{\text{proxy}}$
respectively. We calculate the Kendall rank correlation coefficient [74] to
measure the ranking correlation between models trained with proxy evaluation
and accurate evaluation. The results on dataset A and Cora are presented in
Figure 3. The left sub-figures show the Kendall rank and speedup of total
training time. We can observe that proxy dataset with $D_{\text{proxy}}$=30%
can achieve a good trade-off of ranking accuracy (0.836 on Dataset A and 0.841
on Cora) and speed (4.7$\times$ on Dataset A and 2.6$\times$ on Cora). In the
middle sub-figure, we fix $D_{\text{proxy}}$=30% and study the effect of proxy
bagging. Since bagging is used mainly to reduce variance, we also report the
STD of Kendell Rank by repeating experiments 100 times. From Figure 3, we can
find that $B_{\text{proxy}}$=6 can get both relatively high Kendall rank and
low variance. Furthermore, we fix $D_{\text{proxy}}$=30% and
$B_{\text{proxy}}$=6 to study the $M_{\text{proxy}}$ in the right sub-figures.
It can be seen that Kendall rank is low when the model is small
($M_{\text{proxy}}$=10%), a reasonable Kendall rank (0.758 on Dataset A and
0.795 on Cora) and speedup (10.4$\times$ on Dataset A and 5.7$\times$ on Cora)
can be achieved by $M_{\text{proxy}}$=50%. $M_{\text{proxy}}$=50% can also
reduce GPU memory consumption. These results demonstrate that, by combining
proxy dataset, bagging, and model, we can greatly improve the efficiency of
evaluation and keep a high Kendall rank. Due to the GPU memory reduction, we
can also conduct a parallel evaluation of different models (up to the limit of
GPU memory) to further accelerate this procedure. In the following parts, we
set $D_{\text{proxy}}$=30%, $B_{\text{proxy}}$=6, and $M_{\text{proxy}}$=50%
as default for proxy evaluation.

###  IV-C Results of AutoHEnsGNN

##### Training Configurations

For each dataset, AutoHEnsGNN can automatically run the proxy evaluation and
select top models $\mathcal{P}_{\text{GNN}}$ for the hierarchical ensemble. As
described in Section III-C, AutoHEnsGN-N${}_{\text{Gradient}}$ and
AutoHEnsGNN${}_{\text{Adaptive}}$ are proposed to search $\alpha$ and $\beta$.
Detailed hyper-parameters of search are presented in Appendix A-A2. After
searching, each sub-model is re-trained separately and aggregated in the way
of the hierarchical ensemble. For the anonymous datasets in AutoGraph
Challenge, we construct bagging by randomly splitting the dataset twice for
all methods. For the public datasets, we do not construct bagging on the
different splits of the dataset and follow standard fixed
training/validation/test split (20 nodes per class for training, 500 nodes for
validation and 1,000 nodes for test) [8] in Cora, Citeseer and Pubmed for a
fair comparison with other methods.

##### Results on Anonymous datasets in AutoGraph Challenge

In Table II, we present top models in AutoHEnsGNN $\mathcal{P}_{\text{GNN}}$
and add the ensemble-based baselines for comparison. The ensemble-based
methods are as follows:

  * •

D-ensemble directly averages the scores of different models for predictions.

  * •

L-ensemble stacks a learnable weight for ensemble and learns the ensemble
weight on the validation set.

  * •

Goyal et al. [46] greedily adds the hidden representation learned by the next
model to the current representation for the ensemble.

These ensemble methods share the same GNN pools $\mathcal{P}_{\text{GNN}}$
with AutoHEnsGNN for a fair comparison. In Table II,
AutoHEnsGNN${}_{\text{Adaptive}}$ outperform all baselines on five datasets.
Furthermore, AutoHEnsGN-N${}_{\text{Gradient}}$, which considers the
relationship of different models by jointly training multiple graph self-
ensembles to search the optimal configurations, can get better results than
AutoHEnsGNN${}_{\text{Adaptive}}$. We can observe that, the performance of
models on dataset C differs significantly. Ensemble-based methods (Ensemble,
L-ensemble, Goyal et al. [46] and AutoHEnsGNN) using the models selected by
proxy evaluation can get better results than individual models, which shows
that proxy evaluation can select top models for the ensemble. Furthermore,
AutoHEnsGNN equipped with the hierarchical ensemble can achieve a lower
standard deviation, which demonstrates the robustness of our methods.

TABLE III: Results on the Cora, Citeceer and Pubmed. P-values are calculated between AutoHEnsGNN${}_{\text{Gradient}}$ and L-ensemble. AutoHEnsGNN${}_{\text{Gradient}}$ significantly outperforms baseline methods on all datasets (p-values$<$0.05). Method | Cora | Citeseer | Pubmed
---|---|---|---
GCN [12] | 81.5 | 70.3 | 79.0
GAT [11] | 83.0$\pm$0.7 | 72.5$\pm$0.7 | 79.0$\pm$0.3
APPNP [65] | 83.8$\pm$0.3 | 71.6$\pm$0.5 | 79.7$\pm$0.3
Graph U-Net [gao2019graph] | 84.4$\pm$0.6 | 73.2$\pm$0.5 | 79.6$\pm$0.2
SGC [39] | 82.0$\pm$0.0 | 71.9$\pm$0.1 | 78.9$\pm$0.0
MixHop [75] | 81.9$\pm$0.4 | 71.4$\pm$0.8 | 80.8$\pm$0.6
GraphSAGE [13] | 78.9$\pm$0.8 | 67.4$\pm$0.7 | 77.8$\pm$0.6
GraphMix [73] | 83.9$\pm$0.6 | 74.5$\pm$0.6 | 81.0$\pm$0.6
GRAND [66] | 85.4$\pm$0.4 | 75.5$\pm$0.4 | 82.7$\pm$0.6
GCNII [47] | 85.5$\pm$0.5 | 73.4$\pm$0.6 | 80.2$\pm$0.4
D-ensemble | 85.6$\pm$0.3 | 75.7$\pm$0.2 | 82.7$\pm$0.4
L-ensemble | 85.9$\pm$0.2 | 76.0$\pm$0.2 | 82.9$\pm$0.1
Goyal et al. [46] | 85.9$\pm$0.3 | 75.7$\pm$0.2 | 82.8$\pm$0.2
MixCobra [76] | 85.3$\pm$0.7 | 75.5$\pm$0.7 | 82.3$\pm$0.4
AutoHEnsGNN${}_{\text{Adaptive}}$ | 86.1$\pm$0.2 | 76.3$\pm$0.1 | 83.5$\pm$0.2
AutoHEnsGNN${}_{\text{Gradient}}$ | 86.5$\pm$0.2 | 76.9$\pm$0.2 | 84.0$\pm$0.1
---
|  Dataset A |  Dataset B |  Dataset C |  Dataset D |  Dataset E
---|---|---|---|---
Figure 4: Analysis of model variance with different initializations. “+GSE”
refers to using graph self-ensemble.
---
|  Dataset A |  Dataset B |  Dataset C |  Dataset D |  Dataset E
---|---|---|---|---
Figure 5: Analysis of model variance on different splits of datasets. “-B”
refers training with bagging. “Ada” and “Gra” refer to
AutoHEnsGNN${}_{\text{Adaptive}}$ and AutoHEnsGNN${}_{\text{Gradient}}$.

##### Results on the public datasets

We compare AutoHEnsGNN with 1) start-of-the-art models [12, 11, 65,
gao2019graph, 39, 75, 13, 73, 66, 47] and 2) ensemble-based methods including
D-ensemble, L-ensemble, Goyal et al. [46] and kernel-based ensemble baseline
MixCobra [76]. As shown in Table III, among recent start-of-the-art single
models, GCNII [47] achieves 85.5% accuracy on Cora dataset and GRAND [66]
obtains 75.5% and 82.7% accuracy on Citeseer and Pubmed. Compared to GCNII and
GRAND, AutoHEnsGNN consistently achieves large-margin outperformance across
all datasets with low standard deviation, which demonstrates the effectiveness
and robustness of our proposed methods. When compared to ensemble-based
methods [46], the proposed hierarchical ensemble achieves 0.6%, 1.2%, and 1.2%
(absolute differences) improvements on Cora, Citeseer, and Pubmed
respectively.

TABLE IV: Ablation Study. “PE” and “GSE” refer to proxy evaluation and graph self-ensemble. Method | A | B | C | D | E
---|---|---|---|---|---
Single Model | 65.2$\sim$87.7 | 42.0$\sim$74.5 | 29.1$\sim$92.5 | 93.1$\sim$95.0 | 46.5$\sim$88.2
Random Ensemble | 83.3$\pm$2.5 | 73.5$\pm$1.3 | 79.4$\pm$4.7 | 94.2$\pm$0.3 | 87.7$\pm$0.2
Ensemble + PE | 87.3$\pm$0.8 | 74.7+-0.3 | 93.3$\pm$0.9 | 95.3$\pm$0.1 | 88.0$\pm$0.1
Ensemble + PE + GSE | 88.6$\pm$0.3 | 75.0$\pm$0.4 | 93.8$\pm$0.2 | 95.7$\pm$0.1 | 88.3$\pm$0.1
Ensemble + PE + GSE + Adaptive | 89.3$\pm$0.1 | 75.5$\pm$0.2 | 94.4$\pm$0.2 | 96.1$\pm$0.0 | 88.7$\pm$0.1
Ensemble + PE + GSE + Gradient | 89.6$\pm$0.1 | 76.1$\pm$0.2 | 94.7$\pm$0.2 | 96.3$\pm$0.0 | 88.8$\pm$0.1

###  IV-D Method Analysis

####  IV-D1 Robustness Study

To demonstrate the variance caused by different initializations, we present
the results of GAT [11] in Figure 4 by repeating 100 experiments on a fixed
split of the dataset. From the figure, for example, we can find that the
results of GAT vary from 81.2% to 85.5% on dataset A and 86.2% to 91.1% on
dataset C with only different initializations, which is undesirable for
practical deployment. By using GSE ($K=3$), the differences of GAT due to
initializations are reduced from 4.3% to 1.1% on dataset A and 4.9% to 1.0% on
dataset C. Besides, it can be seen that the average performance is improved
significantly. Since GSE can adaptively aggregate models with different
layers, models equipped with GSE can exploit the diverse information from
different neighborhoods and learn more discriminative and robust
representation.

We further analyze the variance of training on different training/validation
splits. We first run GAT [11] and GCN [12] with 100 random training/validation
splits. As shown in Figure 5, training on different data splits is also a
factor leading to high variance. For example, GCN [12] vary from 69.2% to
73.1% on dataset B. Since the nodes in the graph are not mutually independent,
different splits of training sets may lead to that models fit different data
distributions and have different generality on the test set. When leveraging
bagging on different splits of datasets (three splits in the experiments), we
can see that the differences caused by data splits are reduced from 3.9% to
2.0% for GCN on dataset B. Similarly, GAT [11] and results on other datasets
share the same case. We further adopt GAT and GCN as the candidate pools,
build AutoHEnsGNN with three splits for bagging, and repeat 100 experiments.
As shown in Figure 5, it can be clearly observed that AutoHEnsGNN can achieve
better results with a lower variance, which demonstrates the effectiveness and
robustness of our models.

####  IV-D2 Ablation Study

The proposed AutoHEnsGNN consists of several key components: PE (proxy
evaluation), GSE (graph self-ensemble), and search algorithms (adaptive or
gradient-based). To study the contribution of each component of AutoHEnsGNN,
the performance of successively adding each component is presented in Table
IV. The results indicate that all of these procedures are crucial.
Specifically, compared to the random ensemble (random select models for the
ensemble), the ensemble with models selected by PE can largely improve the
performance, demonstrating the necessity of selecting the proper models. By
adding GSE, the model consistently achieve the lower variance and better
accuracy across all datasets. Furthermore, models via the adaptive and
gradient-based algorithms, which efficiently and effectively search
configurations of the hierarchical ensemble, can obtain better results.

####  IV-D3 Scalability Study

To investigate the scalability of AutoHEnsGNN, we conduct experiments on the
large citation dataset _ogbn-arxiv_ [9]. Ogbn-arxiv is a recently proposed
large-scale dataset of paper citation networks [9] with 169,343 nodes and
1,166,243 edges. In the citation networks, nodes represent arXiv papers and
edges denote the citations between two papers. We follow the public data split
[9] to train models for a fair comparison.

Since AutoHEnsGNN${}_{\text{Adaptive}}$ individually optimizes each graph
self-ensemble (GSE) and directly searches the best configurations, it consumes
the same GPU memory as baseline graph neural networks. However,
AutoHEnsGNN${}_{\text{Gradient}}$ leverages joint gradient optimization to
search for the best architecture parameters and ensemble weights, which
requires more GPU resources. To reduce the GPU memory consumption, in the
search stage, AutoHEnsGNN${}_{\text{Gradient}}$ uses the proxy model and proxy
dataset (as mentioned in Section III-B). The configurations of the proxy model
and proxy dataset are the same as those mentioned in Section IV-B2. We
empirically find that proxy dataset and evaluation for
AutoHEnsGNN${}_{\text{Gradient}}$ do not degrade its final re-training
performance for such a large dataset. As a result, both AutoHEnsGNN and
baselines can be run in one NVIDIA P40 GPU.

TABLE V: Results on the test set of large dataset ogbn-arxiv. “NormAdj” refers to the normalized adjacency matrix, “C&S” refers to Correct and Smooth and “Label Reuse” refers to utilizing not only the true values on training nodes, but also predicted values on test nodes as inputs [77, 78]. P-values are calculated between AutoHEnsGNN${}_{\text{Gradient}}$ and Goyal et al. [46]. AutoHEnsGNN${}_{\text{Gradient}}$ significantly outperforms baseline methods (p-values$<$0.05). Method | obgn-arxiv |
---|---|---
MLP [9] | 57.7$\pm$0.1 |
Node2vec [79] | 71.3$\pm$0.1 |
GCN [12] | 71.7$\pm$0.3 |
GAT [11] | 73.2$\pm$0.2 |
APPNP [65] | 66.4$\pm$0.4 |
SIGN [80] | 72.0$\pm$0.1 |
SGC [39] | 69.4$\pm$0.2 |
GaAN [81] | 72.0$\pm$0.2 |
GraphSAGE [13] | 71.5$\pm$0.3 |
JKNet [56] | 72.2$\pm$0.2 |
DAGNN [57] | 72.1$\pm$0.3 |
DeeperGCN[70] | 71.9$\pm$0.2 |
GCNII [47] | 72.7$\pm$0.2 |
GAT + C&S [77] | 73.9$\pm$0.1 |
GAT + NormAdj + Label reuse + C&S [77] | 73.9$\pm$0.1 |
RevGAT + NormAdj + Label reuse [82] | 74.0$\pm$0.0 |
D-ensemble | 73.9$\pm$0.0 |
L-ensemble | 74.0$\pm$0.2 |
Goyal et al. [46] | 74.0$\pm$0.1 |
AutoHEnsGNN${}_{\text{Adaptive}}$ | 74.2$\pm$0.0 |
AutoHEnsGNN${}_{\text{Gradient}}$ | 74.3$\pm$0.0 |

The results on the ogbn-arxiv dataset are shown in Table V. The baseline
models are implemented following their publicly available codes. Previous work
[77, 78] enhances their models with additional tricks such NormAdj, label
reuse and C&S [77, 78] to boost the performance. For a fair comparison, we
also apply them on ensemble-based baselines and our AutoHEnsGNN. From Table V,
we can see that AutoHEnsGNN${}_{\text{Gradient}}$ outperforms baseline models
and ensemble-based models with higher accuracy 74.3% score and lower variance
for the large dataset ogbn-arxiv, which demonstrates the scalability of our
proposed methods.

TABLE VI: Runtime statistics on large dataset ogbn-arxiv. The “Peak GPU” means the max GPU usage during the training process. “PE” refers to proxy evaluation. Model | Model Selection | Training | Total
---|---|---|---
Time (s) | Peak GPU | Time (s) | Peak GPU | Time (s) | Peak GPU
Search | Train | Search | Train
AutoHEnsGNN${}_{\text{Adaptive}}$ | 12410 | 10.2G | 511 | 8989 | 2.8G | 2.6G | 21910 | 10.2G
AutoHEnsGNN${}_{\text{Gradient}}$ | 12410 | 10.2G | 696 | 8121 | 6.9G | 2.5G | 21227 | 10.2G
D-Ensemble, L-Ensemble | 12410 | 10.2G | - | 10116 | - | 2.6G | 22526 | 10.2G
Goyal et al. [46] | 12410 | 10.2G | - | 10116 | - | 2.6G | 22526 | 10.2G
Ensemble + PE | 12410 | 10.2G | - | 3293 | - | 2.6G | 14266 | 10.2G
Ensemble | 52730 | 19.4G | - | - | - | - | 52730 | 19.4G

####  IV-D4 Runtime Statistics

The experiments on Section IV-D show that a single model suffers from high
variance and undesirable performance, which is also discussed by Shchur et al.
[19] and is named pitfalls of GNN evaluation. It hinders practical usage in
real-life scenarios for a single GNN model. To obtain robust and accurate
predictions, AutoHEnsGNN leverages hierarchical ensemble on a pool of
effective models to reduce variance and improve accuracy, and thus surpass
ensemble baselines. In addition to superior performance, we further
investigate runtime statistics. We conduct experiments on the large graph
dataset ogbn-arxiv and make a comparison with other ensemble methods in Table
VI. “Ensemble” means the naive ensemble of all possible candidate models (20
models as introduced in Section IV-B1). “Ensemble+PE” refers to the ensemble
of the models in the pool selected by proxy evaluation. Other methods adopt
the proxy evaluation and ensemble models with different initialization to
reduce variance. For example, in L-ensemble, each kind of model ($N$ models in
the pool) is trained with $K$ different initialization. Then L-ensemble learns
the ensemble weights of the $N\times K$ models ($N$=3, $K$=3 for ogbn-arxiv).
The statistics are measured on a single NVIDIA P40 GPU.

From Table VI, we can observe that 1) Proxy evaluation can greatly improve the
training efficiency in terms of time and GPU memory; 2) “Ensemble+PE” obtains
the lowest time cost since it does not run the models multiple times with
different initialization. Despite its time efficiency, it usually cannot
achieve good performance as discussed in Section IV-D. As reported in
experiments on dataset A in Table V, “Ensemble+PE” only reaches accuracy 87.3
with a variance of 0.8. By applying our proposed graph self-ensemble and
searching algorithms, the accuracy can be improved by a large margin (87.3 to
89.6) with lower variance (0.1); 3) Other methods consume similar time and GPU
memory in total, in which AutoHEnsGNN${}_{\text{Gradient}}$ uses slightly less
time; 4) AutoHEnsGNN${}_{\text{Gradient}}$ consumes more GPU memory and less
time cost than AutoHEnsGNN${}_{\text{Adaptive}}$ at the training stage. For
scenarios where models should be trained in an online manner within limited
GPU memory, AutoHEnsGNN${}_{\text{Adaptive}}$ can be a better choice.

Figure 6: Hyper-parameters study on Cora for the hierarchical ensemble. $N$
refers to pool size, and $K$ refers to the number of models for self-ensemble.
Values in the figure are the average of 10 repeated experiments with different
seeds. Figure 7: Hyper-parameters study on Cora for
AutoHEnsGNN${}_{\text{Adaptive}}$. $\lambda$, $\epsilon$ and $\gamma$ decide
the annealing temperature in Eqn (8). Values in the figure are the average of
10 repeated experiments with different seeds.

####  IV-D5 Hyper-parameter study

We study the effects of hyper-parameters in AutoHEnsGNN on Cora dataset. The
experiments are designed by adjusting a single hyper-parameter while keeping
others fixed (using the default values).

#####  $K$ and $N$

There are two hyper-parameters in the hierarchical ensemble: the pool size $N$
and the number of models $K$ for self-ensemble. We first present a study on
the pool size by varying $N$ from 1 to 9. As shown in Figure 6, a large pool
size cannot bring more benefits since some models with poor performance may be
selected, and a small pool size such as $N=3$ is better. We further study the
number of models $K$ for self-ensemble by varying it from 1 to 9. We can find
that more models with different initialization for ensemble can lead to more
robust and better performance. Considering the trade-off of efficiency and
performance, $K=3$ is set as the default value in our experiments. In all, we
can observe that the performance of AutoHEnsGNN is relatively stable across
different hyper-parameters.

#####  $\epsilon$, $\gamma$ and $\lambda$

For AutoHEnsGNN${}_{\text{Adaptive}}$, three hyper-parameters decide the
adaptive ensemble weight $\bm{\beta}$. The study of these hyper-parameters is
shown in Table 7. Small $\lambda$, $\epsilon$ or large $\gamma$ can lead to
bias to those models with high accuracy, while large $\lambda$, $\epsilon$ or
small $\gamma$ encourage to assign ensemble weights evenly. According to
experimental results, proper hyper-parameters, which can incorporate model
diversity and meanwhile assign higher weights on high-accuracy models, can
achieve best performance.

###  IV-E Automatic Prediction without Human Intervention on the AutoGraph
Challenge of KDD Cup 2020

The competition requires participants to automatically make predictions on the
final 5 real-life datasets without any human intervention. These tasks are
constrained by the time budget and GPU memory. To avoid failure caused by
unexpected GPU memory/time consumption, we submit the codes implemented with
AutoHEnsGNN${}_{\text{Adaptive}}$ and reduce the search space of $\alpha$ and
other hyper-parameters (e.g., dropout rate)222The code is publicly available
at https://github.com/aister2020/KDDCUP_2020_AutoGraph_1st_Place.. As is shown
in Table VII, our team aister won 1st place, which achieves the best rank
score on average of 5 datasets in the final phase. The competition results on
the 5 real-life datasets demonstrate the effectiveness of AutoHEnsGNN.

TABLE VII: Results of KDD Cup 2020 AutoGraph Competitions. Our team “aister” won 1st place with the best rank score in the final phase. Rank | Team | Average Rank Score
---|---|---
1 | aister (ours) | 4.8
2 | PASA_NJU | 5.2
3 | qqerret | 5.4
4 | common | 6.6
5 | PostDawn | 7.4
6 | SmartMN-THU | 7.8
7 | JunweiSun | 7.8
8 | u1234x1234 | 9.2
9 | shiqitao | 9.6
10 | supergx | 11.8

##  V Edge Prediction and Graph Classification

To investigate the generality of AutoHEnsGNN, we further conduct experiments
on two common graph tasks: edge prediction and graph classification. The
former is conducted on three citation networks: Cora, CiteSeer and PubMeb
[60], and the latter is conducted chemical compounds dataset PROTEINS [83].
PROTEINS is a binary classification dataset, which contains 1,113 graphs with
average degrees 39.06 and average links 72.82. The data splits follow their
common practice [60, 83]. We leverage 6 [84, 85, 86, 87, 88, 89] and 7 [14,
13, 90, 91, 86, gao2019graph, 92] GNN models as the candidate pool for graph
prediction and classification task respectively. The K is set to 3 and N is
set to 2. Other hyper-parameters are the same as those for node classification
tasks in Section IV-C.

As shown in Table VIII and Table IX, AutoHEnsGNN consistently outperforms
other methods by a large margin, which verifies the generality of our
algorithms. Meanwhile, AutoHEnsGNN greatly surpasses the existing work in edge
prediction tasks and achieves the state-of-the-art results333See
https://paperswithcode.com/task/link-prediction..

TABLE VIII: Accuracy is measured by “AUC” on edge prediction tasks. P-values are calculated between AutoHEnsGNN${}_{\text{Gradient}}$ and L-ensemble. AutoHEnsGNN${}_{\text{Gradient}}$ significantly outperforms baseline methods on all datasets (p-values$<$0.05). Method | Cora | Pubmed | Citeceer
---|---|---|---
Walkpooling [84] | 95.9 | 98.7 | 95.9
S-VGAE [85] | 94.1 | 96.0 | 94.7
sGraphite-VAE [86] | 93.7 | 94.8 | 94.1
Graph InfoClust [87] | 93.5 | 93.7 | 97.0
BANE [88] | 93.5 | - | 95.6
ARGE [89] | 92.4 | 96.8 | 91.9
D-enesmble | 95.2$\pm$1.0 | 98.0$\pm$0.0 | 95.5$\pm$0.5
L-ensemble | 95.9$\pm$0.9 | 98.6$\pm$0.0 | 96.4$\pm$0.3
Goyal et al. [46] | 96.7$\pm$0.3 | 96.2$\pm$0.2 | 96.4$\pm$0.3
AutoHEnsGNN${}_{\text{Adaptive}}$ | 97.3$\pm$0.3 | 99.7$\pm$0.0 | 97.6$\pm$0.3
AutoHEnsGNN${}_{\text{Gradient}}$ | 97.4$\pm$0.1 | 99.8$\pm$0.0 | 97.5$\pm$0.2
TABLE IX: Accuracy on the graph classification task. P-values are calculated between AutoHEnsGNN${}_{\text{Gradient}}$ and L-ensemble. AutoHEnsGNN${}_{\text{Gradient}}$ significantly outperform baseline methods (p-values$<$0.05). Method | PROTEINS
---|---
GIN [14] | 76.2
GraphSAGE [13] | 73.0
MEWISPool [90] | 80.7
U2GNN [91] | 80.0
sGIN [86] | 79.0
hGANet [gao2019graph] | 78.7
HGP-SL [92] | 84.9
D-enesmble | 84.8$\pm$0.5
L-ensemble | 84.9$\pm$0.6
Goyal et al. [46] | 84.8$\pm$0.5
AutoHEnsGNN${}_{\text{Adaptive}}$ | 85.4$\pm$0.3
AutoHEnsGNN${}_{\text{Gradient}}$ | 85.6$\pm$0.3

##  VI Conclusion

In this paper, we propose AutoHEnsGNN for graph tasks, which automatically
builds a hierarchical ensemble model for robust and accurate prediction. We
propose proxy evaluation and efficient algorithms
AutoHEnsGNN${}_{\text{Gradient}}$ and AutoHEnsGNN${}_{\text{Adaptive}}$, which
can improve the efficiency and enable the automatic search. AutoHEnsGNN has
won 1st place in the AutoGraph Challenge for KDD Cup 2020. The extensive
experiments further demonstrate the effectiveness of AutoHEnsGNN. For future
work, we will try to combine NAS, which is used to search novel architectures,
with AutoHEnsGNN to achieve better performance.

##  VII Acknowledgements

Jin Xu and Jian Li are supported in part by the National Natural Science
Foundation of China Grant 61822203, 61772297, 61632016, Turing AI Institute of
Nanjing and Xi’an Institute for Interdisciplinary Information Core Technology.
We also thank Kaitao Song for the helpful discussion and anonymous reviewers
for the constructive comments.

##  Appendix A Reproducibility

###  A-A Training Configurations

####  A-A1 Proxy evaluation

For public datasets Cora, Citeseer, and Pubmed, we use the exact training
configurations and hyper-parameters as the original implements. For the
anonymous dataset in AutoGraoh Challenge, we use Adam [93] optimizer with
$\beta_{1}$=0.9, $\beta_{2}$=0.98, $\epsilon$=10-9, train the model with a
weight decay rate 5e-4, dropout rate {0.5, 0.25, 0.1} and learning rate {5e-2,
3e-2, 1e-2, 7.5e-3, 5e-3, 3e-3, 1e-3, 5e-4}. The learning rate is decayed with
rate 0.9 every 3 epochs. We apply the early stop with patience 20 epochs and
save the model with the best validation accuracy. We perform grid search for
the key hyper-parameters including learning rate, dropout rate, and variants
of models (e.g., GraphSAGE-mean, GraphSAGE-pool [13]). The optimal
configurations can be automatically searched.

####  A-A2 AutoHEnsGNN

For AutoHEnsGNN${}_{\text{Gradient}}$, the architecture weights $\alpha$ and
$\beta$ are updated at the end of every epoch as described in Algorithm 1.
Each sub-model directly uses the hyper-parameters (dropout rate, etc.) in the
proxy evaluation stage. The $K$ is set to 3 for self-ensemble. We use Adam
optimizer with learning rate {5e-2, 3e-2, 1e-2, 7.5e-3, 5e-3, 3e-3, 1e-3,
5e-4} for the model weights and learning rate 3e-4 for architecture weights.
The learning rate for the model weights is searched based on the validation
accuracy. We apply the early stop with patience 5 epochs and obtain the
$\alpha$ and $\beta$ when the model achieves the best validation accuracy. To
reduce GPU memory consumption, we use proxy model with $M_{\text{proxy}}$=50%
for GPU memory reduction. For AutoHEnsGNN${}_{\text{Adaptive}}$, $\alpha$ for
each self-ensemble is decided by grid search and $\beta$ is decided by
Equation 8 with $\epsilon=3$, $\gamma=8000$ and $\lambda=5$.

####  A-A3 L-ensemble

Rather than averaging the scores of different models for the ensemble, another
method is to learn the ensemble weight on the validation set. To learn the
weight, we split the $20\%$ dataset from the training set as the validation
set. Then we fix the model weight of different models and apply gradient
update on the learnable ensemble weight until convergence. We use Adam [93]
optimizer with $\beta_{1}$=0.9, $\beta_{2}$=0.98, $\epsilon$=10-9, learning
rate {1e-3, 1e-2, 1e-1} and do not use weight decay.

TABLE X: An example of an anonymous dataset in AutoGraph Challenge of KDD Cup
2020.

Node File
---
Training nodes index (Int) | 1,2,3,4,5,$\cdots$
Test node index (Int) | 128,129,130,$\cdots$
Edge File
Source_index | Destination_index | Edge weight
Int | Int | Float
0 | 62 | 1
0 | 40 | 1
1 | 41 | 2
$\cdots$
Feature File
Node Index | F0 | F1 | $\cdots$
Int | Float | Float | Float
0 | 0.477758 | 0.053875 | 0.729954
1 | 0.3422409 | 0.669304 | 0.0873657
2 | 0.825985 | 0.442136 | 0.987225
$\cdots$
Label File
Node Index | Class
0 | 1
1 | 3
2 | 1
$\cdots$
Metadata File
Time Budget (s) | n_class
500 | 7

###  A-B AutoGraph Challenge for KDD Cup 2020

The Automatic Graph Representation Learning challenge (AutoGraph), the first
AutoML challenge applied to Graph-structured data, is the AutoML track
challenge in KDD Cup 2020 provided by 4Paradigm, ChaLearn, Stanford and
Google. The challenge website could be found online
444https://www.automl.ai/competitions/3. In this challenge, participants need
to design a computer program capable of providing solutions to graph
representation learning problems without any human intervention. The tasks are
also constrained by the time budget. This challenge focuses on the problem of
graph node classification tasks to evaluate the quality of learned
representations. AutoGraph Challenge provides 15 graph datasets: 5 public
datasets, which can be downloaded, are provided to the participants; 5
feedback datasets are also provided to evaluate the public leaderboard scores
of solutions; 5 final datasets are used to evaluate the quality of solutions
in the final phase. The features of datasets are anonymous and numerical.
There are more than one hundred teams that participated in this competition.
Our team “aister” won 1st place in the final phase and our code is also
publicly available.

Figure 8: Time efficiency study by varying pool size $N$.

###  A-C Time efficiency study by varying the pool size $N$

We study the time efficiency of AutoHEnsGNN on different pool sizes $N$ and
conduct experiments on Cora datasets. We vary the pool size from 1 to 5 and
measure the time consumption of the search stage on a single NVIDIA P40 GPU.
As shown in Figure 8, the time consumption grows linearly for
AutoHEnsGNN${}_{\text{Adaptive}}$ as $N$ increases. However, due to the
gradient optimization, AutoHEnsGNN${}_{\text{Gradient}}$ does not
significantly consume more time, which verifies the time efficiency of the bi-
level optimization in Algorithm 1.

## References

  * [1] T. Derr, C. Wang, S. Wang, and J. Tang, “Relevance measurements in online signed social networks,” in _Proceedings of the 14th international workshop on mining and learning with graphs (MLG)_ , 2018.
  * [2] Y. Qi, K. Hu, B. Zhang, J. Cheng, and J. Lei, “Trilateral spatiotemporal attention network for user behavior modeling in location-based search,” in _CIKM ’21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 - 5, 2021_ , G. Demartini, G. Zuccon, J. S. Culpepper, Z. Huang, and H. Tong, Eds. ACM, 2021, pp. 3373–3377. [Online]. Available: https://doi.org/10.1145/3459637.3482206
  * [3] L. Liu, F. Zhu, L. Zhang, and S. Yang, “A probabilistic graphical model for topic and preference discovery on social media,” _Neurocomputing_ , vol. 95, pp. 78–88, 2012.
  * [4] C. C. Aggarwal, H. Wang _et al._ , _Managing and mining graph data_. Springer, vol. 40.
  * [5] J. Xu, J. Zhou, Y. Jia, J. Li, and X. Hui, “An adaptive master-slave regularized model for unexpected revenue prediction enhanced with alternative data,” in _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 2020, pp. 601–612.
  * [6] Y. Li, U. Islambekov, C. Akcora, E. Smirnova, Y. R. Gel, and M. Kantarcioglu, “Dissecting ethereum blockchain analytics: What we learn from topology and geometry of the ethereum graph?” in _Proceedings of the 2020 SIAM International Conference on Data Mining_. SIAM, 2020, pp. 523–531.
  * [7] N. C. Abay, C. G. Akcora, Y. R. Gel, M. Kantarcioglu, U. D. Islambekov, Y. Tian, and B. M. Thuraisingham, “Chainnet: Learning on blockchain graphs with topological features,” in _2019 IEEE International Conference on Data Mining, ICDM 2019, Beijing, China, November 8-11, 2019_ , J. Wang, K. Shim, and X. Wu, Eds. IEEE, 2019, pp. 946–951. [Online]. Available: https://doi.org/10.1109/ICDM.2019.00105
  * [8] Z. Yang, W. Cohen, and R. Salakhudinov, “Revisiting semi-supervised learning with graph embeddings,” in _International conference on machine learning_. PMLR, 2016, pp. 40–48.
  * [9] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec, “Open graph benchmark: Datasets for machine learning on graphs,” in _Advances in neural information processing systems_ , 2020.
  * [10] X. Wang, Y. Ma, Y. Wang, W. Jin, X. Wang, J. Tang, C. Jia, and J. Yu, “Traffic flow prediction via spatial temporal graph neural network,” in _Proceedings of The Web Conference 2020_ , 2020, pp. 1082–1092.
  * [11] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _International Conference on Learning Representations_ , 2018.
  * [12] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [13] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _Advances in neural information processing systems_ , 2017, pp. 1024–1034.
  * [14] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _International Conference on Learning Representations_ , 2018\.
  * [15] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, “Graph convolutional neural networks for web-scale recommender systems,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 974–983.
  * [16] T. Derr, Y. Ma, and J. Tang, “Signed graph convolutional networks,” in _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 2018, pp. 929–934.
  * [17] L. Zeng, J. Xu, Z. Yao, Y. Zhu, and J. Li, “Graph symbiosis learning,” _CoRR_ , vol. abs/2106.05455, 2021. [Online]. Available: https://arxiv.org/abs/2106.05455
  * [18] M. Zitnik, M. Agrawal, and J. Leskovec, “Modeling polypharmacy side effects with graph convolutional networks,” _Bioinformatics_ , vol. 34, no. 13, pp. i457–i466, 2018.
  * [19] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, “Pitfalls of graph neural network evaluation,” _arXiv preprint arXiv:1811.05868_ , 2018.
  * [20] Y. Gao, H. Yang, P. Zhang, C. Zhou, and Y. Hu, “Graph neural architecture search,” in _IJCAI_ , vol. 20, 2020, pp. 1403–1409.
  * [21] K. Zhou, Q. Song, X. Huang, and X. Hu, “Auto-gnn: Neural architecture search of graph neural networks,” _arXiv preprint arXiv:1909.03184_ , 2019.
  * [22] M. Nunes and G. L. Pappa, “Neural architecture search in graph neural networks,” in _Brazilian Conference on Intelligent Systems_. Springer, 2020, pp. 302–317.
  * [23] H. Zhao, L. Wei, and Q. Yao, “Simplifying architecture search for graph neural network,” _arXiv preprint arXiv:2008.11652_ , 2020.
  * [24] Anonymous, “Efficient graph neural architecture search,” in _Submitted to International Conference on Learning Representations_ , 2021, under review. [Online]. Available: https://openreview.net/forum?id=IjIzIOkK2D6
  * [25] A. Pourchot, A. Ducarouge, and O. Sigaud, “To share or not to share: A comprehensive appraisal of weight-sharing,” _arXiv preprint arXiv:2002.04289_ , 2020.
  * [26] Y. Shu, W. Wang, and S. Cai, “Understanding architectures learnt by cell-based neural architecture search,” in _International Conference on Learning Representations_ , 2019.
  * [27] L. Xie, X. Chen, K. Bi, L. Wei, Y. Xu, Z. Chen, L. Wang, A. Xiao, J. Chang, X. Zhang _et al._ , “Weight-sharing neural architecture search:a battle to shrink the optimization gap,” _arXiv preprint arXiv:2008.01475_ , 2020\.
  * [28] K. Yu, R. Ranftl, and M. Salzmann, “How to train your super-net: An analysis of training heuristics in weight-sharing nas,” _arXiv preprint arXiv:2003.04276_ , 2020.
  * [29] X. Wang, D. Kondratyuk, K. M. Kitani, Y. Movshovitz-Attias, and E. Eban, “Multiple networks are more efficient than one: Fast and accurate models via ensembles and cascades,” _arXiv preprint arXiv:2012.01988_ , 2020.
  * [30] H. Wang, W. Fan, P. S. Yu, and J. Han, “Mining concept-drifting data streams using ensemble classifiers,” in _Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2003, pp. 226–235.
  * [31] S. Puuronen, A. Tsymbal, and I. Skrypnyk, “Correlation-based and contextual merit-based ensemble feature selection,” in _International Symposium on Intelligent Data Analysis_. Springer, 2001, pp. 135–144.
  * [32] S. Puuronen, I. Skrypnyk, and A. Tsymbal, “Ensemble feature selection based on the contextual merit,” in _International Conference on Data Warehousing and Knowledge Discovery_. Springer, 2001, pp. 111–120.
  * [33] G. Anandalingam and T. L. Friesz, “Hierarchical optimization: An introduction,” _Annals of Operations Research_ , vol. 34, no. 1, pp. 1–11, 1992.
  * [34] B. Colson, P. Marcotte, and G. Savard, “An overview of bilevel optimization,” _Annals of operations research_ , vol. 153, no. 1, pp. 235–256, 2007.
  * [35] H. Liu, K. Simonyan, and Y. Yang, “Darts: Differentiable architecture search,” in _International Conference on Learning Representations_ , 2018\.
  * [36] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, “Weisfeiler and leman go neural: Higher-order graph neural networks,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 4602–4609.
  * [37] Y. Liu, Y. Gu, Z. Ding, J. Gao, Z. Guo, Y. Bao, and W. Yan, “Decoupled graph convolution network for inferring substitutable and complementary items,” in _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, 2020, pp. 2621–2628.
  * [38] Z. Wang, W. Wei, G. Cong, X.-L. Li, X.-L. Mao, and M. Qiu, “Global context enhanced graph neural networks for session-based recommendation,” in _Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2020, pp. 169–178.
  * [39] F. Wu, A. H. Souza Jr, T. Zhang, C. Fifty, T. Yu, and K. Q. Weinberger, “Simplifying graph convolutional networks,” in _ICML_ , 2019.
  * [40] L. Zeng, J. Xu, Z. Yao, Y. Zhu, and J. Li, “Graph symbiosis learning,” _arXiv preprint arXiv:2106.05455_ , 2021.
  * [41] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh, “Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks,” in _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2019, pp. 257–266.
  * [42] V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson, “Benchmarking graph neural networks,” _arXiv preprint arXiv:2003.00982_ , 2020.
  * [43] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” _Advances in neural information processing systems_ , vol. 29, pp. 3844–3852, 2016.
  * [44] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph sequence neural networks,” _arXiv preprint arXiv:1511.05493_ , 2015.
  * [45] M. Fey, “Just jump: Dynamic neighborhood aggregation in graph neural networks,” _arXiv preprint arXiv:1904.04849_ , 2019.
  * [46] P. Goyal, D. Huang, S. R. Chhetri, A. Canedo, J. Shree, and E. Patterson, “Graph representation ensemble learning,” _arXiv preprint arXiv:1909.02811_ , 2019.
  * [47] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li, “Simple and deep graph convolutional networks,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 1725–1735.
  * [48] P. Goyal and E. Ferrara, “Graph embedding techniques, applications, and performance: A survey,” _Knowledge-Based Systems_ , vol. 151, pp. 78–94, 2018.
  * [49] J. Xu, X. Tan, K. Song, R. Luo, Y. Leng, T. Qin, T. Liu, and J. Li, “Analyzing and mitigating interference in neural architecture search,” _CoRR_ , vol. abs/2108.12821, 2021. [Online]. Available: https://arxiv.org/abs/2108.12821
  * [50] J. Xu, X. Tan, R. Luo, K. Song, J. Li, T. Qin, and T. Liu, “NAS-BERT: task-agnostic and adaptive-size BERT compression with neural architecture search,” in _KDD ’21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021_ , F. Zhu, B. C. Ooi, and C. Miao, Eds. ACM, 2021, pp. 1933–1943. [Online]. Available: https://doi.org/10.1145/3447548.3467262
  * [51] Y. Zhang, Z. Lin, J. Jiang, Q. Zhang, Y. Wang, H. Xue, C. Zhang, and Y. Yang, “Deeper insights into weight sharing in neural architecture search,” _arXiv preprint arXiv:2001.01431_ , 2020.
  * [52] R. Polikar, “Ensemble based systems in decision making,” _IEEE Circuits and systems magazine_ , vol. 6, no. 3, pp. 21–45, 2006.
  * [53] C. Zhao, Y. Qiu, S. Zhou, S. Liu, W. Zhang, and Y. Niu, “Graph embedding ensemble methods based on the heterogeneous network for lncrna-mirna interaction prediction,” _BMC genomics_ , vol. 21, no. 13, pp. 1–12, 2020\.
  * [54] H. Ren, G. F. Kokai, W. J. Turner, and T.-S. Ku, “Paragraph: Layout parasitics and device parameter prediction using graph neural networks,” in _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2020, pp. 1–6.
  * [55] Y. Kong and T. Yu, “forgenet: A graph deep neural network model using tree-based ensemble classifiers for feature extraction,” _arXiv preprint arXiv:1905.09889_ , 2019.
  * [56] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka, “Representation learning on graphs with jumping knowledge networks,” in _ICML_ , 2018.
  * [57] M. Liu, H. Gao, and S. Ji, “Towards deeper graph neural networks,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 338–348.
  * [58] Z. Zhang, P. Cui, and W. Zhu, “Deep learning on graphs: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , 2020.
  * [59] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in _ICML_ , 2017.
  * [60] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad, “Collective classification in network data,” _AI magazine_ , vol. 29, no. 3, pp. 93–93, 2008.
  * [61] J. Du, S. Zhang, G. Wu, J. M. Moura, and S. Kar, “Topology adaptive graph convolutional networks,” _arXiv preprint arXiv:1710.10370_ , 2017.
  * [62] F. M. Bianchi, D. Grattarola, L. Livi, and C. Alippi, “Graph neural networks with convolutional arma filters,” _arXiv preprint arXiv:1901.01343_ , 2019\.
  * [63] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” _Advances in neural information processing systems_ , vol. 28, pp. 2224–2232, 2015.
  * [64] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein, “Geometric deep learning on graphs and manifolds using mixture model cnns,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 5115–5124.
  * [65] J. Klicpera, A. Bojchevski, and S. Günnemann, “Predict then propagate: Graph neural networks meet personalized pagerank,” _arXiv preprint arXiv:1810.05997_ , 2018.
  * [66] W. Feng, J. Zhang, Y. Dong, Y. Han, H. Luan, Q. Xu, Q. Yang, E. Kharlamov, and J. Tang, “Graph random neural networks for semi-supervised learning on graphs,” _Advances in Neural Information Processing Systems_ , vol. 33, 2020\.
  * [67] T. Xie and J. C. Grossman, “Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties,” _Physical review letters_ , vol. 120, no. 14, p. 145301, 2018.
  * [68] K. K. Thekumparampil, C. Wang, S. Oh, and L.-J. Li, “Attention-based graph neural network for semi-supervised learning,” _arXiv preprint arXiv:1803.03735_ , 2018.
  * [69] E. Ranjan, S. Sanyal, and P. P. Talukdar, “Asap: Adaptive structure aware pooling for learning hierarchical graph representations.” in _AAAI_ , 2020, pp. 5470–5477.
  * [70] G. Li, C. Xiong, A. Thabet, and B. Ghanem, “Deepergcn: All you need to train deeper gcns,” _arXiv preprint arXiv:2006.07739_ , 2020.
  * [71] Y. Wang, Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon, “Dynamic graph cnn for learning on point clouds,” _Acm Transactions On Graphics (tog)_ , vol. 38, no. 5, pp. 1–12, 2019.
  * [72] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in Neural Information Processing Systems 32_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds. Curran Associates, Inc., 2019, pp. 8024–8035. [Online]. Available: http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdf
  * [73] V. Verma, M. Qu, A. Lamb, Y. Bengio, J. Kannala, and J. Tang, “Graphmix: Regularized training of graph neural networks for semi-supervised learning,” _arXiv preprint arXiv:1909.11715_ , 2019.
  * [74] M. G. Kendall, “A new measure of rank correlation,” _Biometrika_ , vol. 30, no. 1/2, pp. 81–93, 1938.
  * [75] S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan, “Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing,” in _International Conference on Machine Learning_ , 2019, pp. 21–29.
  * [76] A. Fischer and M. Mougeot, “Aggregation using input–output trade-off,” _Journal of Statistical Planning and Inference_ , vol. 200, pp. 1–19, 2019\.
  * [77] Q. Huang, H. He, A. Singh, S.-N. Lim, and A. Benson, “Combining label propagation and simple models out-performs graph neural networks,” in _International Conference on Learning Representations_ , 2020.
  * [78] Y. Wang, J. Jin, W. Zhang, Y. Yu, Z. Zhang, and D. Wipf, “Bag of tricks for node classification with graph neural networks,” _arXiv preprint arXiv:2103.13355_ , 2021.
  * [79] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2016, pp. 855–864.
  * [80] F. Frasca, E. Rossi, D. Eynard, B. Chamberlain, M. Bronstein, and F. Monti, “Sign: Scalable inception graph neural networks,” in _ICML 2020 Workshop on Graph Representation Learning and Beyond_ , 2020.
  * [81] J. Zhang, X. Shi, J. Xie, H. Ma, I. King, and D.-Y. Yeung, “Gaan: Gated attention networks for learning on large and spatiotemporal graphs,” _arXiv preprint arXiv:1803.07294_ , 2018.
  * [82] G. Li, M. Müller, B. Ghanem, and V. Koltun, “Training graph neural networks with 1000 layers,” _arXiv preprint arXiv:2106.07476_ , 2021.
  * [83] C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, “Tudataset: A collection of benchmark datasets for learning with graphs,” _arXiv preprint arXiv:2007.08663_ , 2020.
  * [84] L. Pan, C. Shi, and I. Dokmanić, “Neural link prediction with walk pooling,” _arXiv preprint arXiv:2110.04375_ , 2021.
  * [85] T. R. Davidson, L. Falorsi, N. De Cao, T. Kipf, and J. M. Tomczak, “Hyperspherical variational auto-encoders,” in _34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018_. Association For Uncertainty in Artificial Intelligence (AUAI), 2018, pp. 856–865.
  * [86] X. Di, P. Yu, R. Bu, and M. Sun, “Mutual information maximization in graph neural networks,” in _2020 International Joint Conference on Neural Networks (IJCNN)_. IEEE, 2020, pp. 1–7.
  * [87] C. Mavromatis and G. Karypis, “Graph infoclust: Leveraging cluster-level node information for unsupervised graph representation learning,” _arXiv preprint arXiv:2009.06946_ , 2020.
  * [88] H. Yang, S. Pan, P. Zhang, L. Chen, D. Lian, and C. Zhang, “Binarized attributed network embedding,” in _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 2018, pp. 1476–1481.
  * [89] S. Pan, R. Hu, G. Long, J. Jiang, L. Yao, and C. Zhang, “Adversarially regularized graph autoencoder for graph embedding,” in _IJCAI International Joint Conference on Artificial Intelligence_ , 2018.
  * [90] A. Nouranizadeh, M. Matinkia, M. Rahmati, and R. Safabakhsh, “Maximum entropy weighted independent set pooling for graph neural networks,” _arXiv preprint arXiv:2107.01410_ , 2021.
  * [91] D. Q. Nguyen, T. D. Nguyen, and D. Phung, “Universal graph transformer self-attention networks,” _arXiv preprint arXiv:1909.11855_ , 2019.
  * [92] Z. Zhang, J. Bu, M. Ester, J. Zhang, C. Yao, Z. Yu, and C. Wang, “Hierarchical graph pooling with structure learning,” _arXiv preprint arXiv:1911.05954_ , 2019.
  * [93] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _ICLR (Poster)_ , 2015.