Recent years have witnessed the popularity of Graph Neural Networks (GNN) in various scenarios. To obtain optimal dataspecific GNN architectures, researchers turn to neural architecture search (NAS) methods, which have made impressive progress in discovering efective architectures in convolutional neural networks. Two preliminary works, GraphNAS and Auto-GNN, have made first attempt to apply NAS methods to GNN. Despite the promising results, there are several drawbacks in expressive capability and search eficiency of GraphNAS and Auto-GNN due to the designed search space. To overcome these drawbacks, we propose the SNAG framework (Simplified Neural Architecture search for Graph neural networks), consisting of a novel search space and a reinforcement learning based search algorithm. Extensive experiments on real-world datasets demonstrate the efectiveness of the SNAG framework compared to human-designed GNNs and NAS methods, including GraphNAS and Auto-GNN.1
neural networks (CNN) and recurrent neural networks (RNN). In very recent time, there are two preliminary In recent years, Graph Neural Networks (GNN) [1, 2] works, GraphNAS [18] and Auto-GNN [19], making the have been a hot topic due to their promising results on ifrst attempt to apply NAS to GNN architecture design. various graph-based tasks, e.g., recommendation [3, 4, 5], Though GraphNAS and Auto-GNN show some promising fraud detection [6], chemistry [7]. In the literature, results, there are some drawbacks in expressive capability various GNN models [8, 9, 10, 11, 12, 13, 6, 5] have been and search eficiency of GraphNAS and Auto-GNN due to designed for graph-based tasks. Despite the success of the designed search space. In the NAS literature [14, 15, these GNN models, there are two challenges facing them. 16, 17], a good search space should be both expressive and The first one is that there is no optimal architecture compact. That is the search space should be large enough which can always behave well in diferent scenarios. For to subsume existing human-design architectures, thus example, in our experiments (Table 3 and 4), we can the performance of a search method can be guaranteed. see that the best GNN architectures vary on diferent However, it will be extremely costly if the search space datasets and tasks. It means that we have to spend is too general, which is impractical for any searching huge computational and expertise resources designing method. The search spaces of GraphNAS and Autoand tuning a well-behaved GNN architecture given a GNN are the same, both of which do not well satisfy specific task, which limits the application of GNN models. the requirement of a good search space. On one hand, Secondly, existing GNN models do not make full use of they fail to include several latest GNN models, e.g., the best architecture design practices in other established the GeniePath [6], for which we give a more detailed areas, e.g., computer vision (CV). For example, existing analysis in Section 3.1 (Table 1). On the other hand, the multi-layer GNN models tend to stack multiple layers search space includes too many choices, making it too with the same aggregator (see bottom left of Figure 1), complicated to search eficiently. which aggregates hidden features of multi-hop neighbors. In this work, to overcome the drawbacks of GraphNAS However it remains to be seen whether combinations of and Auto-GNN and push forward the research of NAS diferent aggregators in a multi-layer GNN model can approaches for GNN, we propose the SNAG framework further improve the performance. These challenges lead (Simplified Neural Architecture search for Graph neural to a straightforward question: can we obtain well-behaved networks), consisting of a simpler yet more expressive data-specific GNN architectures ? search space and a RL-based search algorithm. By
To address the above question, researchers turn revisiting extensive existing works, we unify state-ofto neural architecture search (NAS) [14, 15, 16, 17] the-art GNN models in a message passing framework [7], approaches, which have shown promising results in based on which a much more expressive yet simpler automatically designing architectures for convolutional search space is designed. The simplified search space can not only emulate a series of existing GNN models, but Proceedings of the CIKM 2020 Workshops, October 19-20, Galway, also be very flexible to use the weight sharing mechanism, Ireland. which is a widely used technique to accelerate the search algorithm in the NAS literature. We conduct © 2020 Copyright for this paper by its authors. Use permitted under Creative CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g CCoEmmUoRns LWiceonsrekAstthribouptionP4r.0oIncteerenadtiionnagl s(CC(CBYE4U.0)R.-WS.org) following the message passing neighborhood aggregation schema, which computes the embeddings of node “2”; (c) Upper Right: the reinforcement learning pipeline for NAS; d) Bottom Right: an illustration of a search space of the proposed SNAG using 2-layer GNN as backbone, which includes two key components of existing GNN models: node and layer aggregators.
extensive experiments to demonstrate the efectiveness of the SNAG framework comparing to various baselines including GraphNAS and Auto-GNN. To summarize, the contributions of this work are in the following: • In this work, to automatically obtain well-behaved data-specific GNN architectures, we propose the SNAG framework, which can overcome the drawbacks of existing NAS approaches, i.e., GraphNAS and AutoGNN. To better utilize the NAS techniques, we design a novel and efective search space, which can emulate more existing GNN architectures than previous works. • We design a RL-based search algorithm and its variant by adopting the weight sharing mechanism (SNAGWS). By comparing the performance of these two variants, we show that the weight sharing mechanism is not empirically useful as we imagined, which aligns with the latest research in NAS literature [20]. • Extensive experiments on real-world datasets are work, comparing to human-designed GNNs and NAS methods. The experimental results demonstrate the superiority of SNAG in terms of efectiveness and eficiency compared extensive baseline models.
GNN is first proposed in [ 1] and in the past five years many diferent variants [ 8, 9, 10, 11, 12, 13, 6] have been designed, all of which are relying on a neighborhood aggregation (or message passing) schema [7]. As shown in the left part of Figure 1, it tries to learn the representation of a given node in a graph by iteratively aggregating the hidden features (“message”) of its neighbors, and the message can propagate to farther neighborhood in the graph, e.g., the hidden features of two-hop neighbors can be aggregated in a two-step iteration process. Let
= (, ℰ ) be a simple graph with node features X ∈ R× , where and ℰ represent the node and edge sets, respectively. represents the number of nodes and is the dimension of node features. We use () to represent the first-order neighbors of a node in , i.e., () = { ∈ |(, ) ∈ ℰ }. In the literature, we also i.e., ̃︀ () = {} ∪ { ∈ |(, ) ∈ ℰ }.
Then a -layer GNN can be written as follows: the -th layer ( = 1, · · · aggregating its neighborhood as
, ) updates h for each node by h = ︂( ︂( conducted to evaluate the proposed SNAG frame- create a new set ̃︀ () is the neighbor set including itself, where h() ∈
R represents the hidden features of a node learned by the -th layer, and is the
W() · Φ {h(− 1), ∀ ∈ ̃︀ ()} Comparisons of the search space between existing NAS methods and SNAG. For more details of the “Others” columns of GraphNAS/Auto-GNN, we refer readers to the corresponding papers.
Node aggregators
GCN,SAGE-SUM/-MEAN/-MAX, MLP, GAT , GAT-SYM/-COS/ -LINEAR/-GEN-LINEAR , All above plus SAGE-LSTM and GeniePath CONCAT,MAX,LSTM
Hidden Embedding Size,
Attention Head, Activation Function
IDENTITY, ZERO corresponding dimension. W() is a trainable weight matrix shared by all nodes in the graph, and is a nonlinear activation function, e.g., a sigmoid or ReLU. Φ is the key component, i.e., a pre-defined aggregation more promising architectures. GraphNAS [18] and AutoGNN [19] are the first two RL-based NAS methods for GNN.
Search space is a key component of NAS approaches, function, which varies across on diferent GNN models. the quality of which directly afects the final performance For example, in [8], a weighted summation function is and search eficiency. As mentioned in [ 14, 15, 23, 28, 27, designed as the node aggregators, and in [9], diferent 22, 29, 26, 25], a good search space should include existing functions, e.g., mean and max pooling, are proposed as human-designed models, thus the performance of an the aggregators. Further, to weigh the importance of designed search algorithm can be guaranteed. In this diferent neighbors, attention mechanism is incorporated to design the aggregators [10]. work, by unifying existing GNN models in the message passing framework [7] with the proposed node and layer Usually, the output of the last layer is used as the aggregators, we design a more expressive yet simple ifnal representation for each node, which is denoted search space in this work, which is also flexible enough as z =
h(). In [12], skip-connections [21] are incorporated to propagate message from intermediate layers to an extra layer, and the final representation of the node is computed by a layer aggregation as z = Φ ︁( h(1)
, · · · , h())︁ , and Φ can also have diferent options, e.g., max-pooling, concatenation. Based on the node and layer aggregators, we can define the two key components of exiting GNN models, i.e., the neighborhood aggregation function and the range of the neighborhood, which tends to be tuned depending on the tasks. In Table 1, we list all node and layer aggregators in this work, which lays the basis for the proposed SNAG framework.
Neural architecture search (NAS) [14, 15, 16, 17] aims to automatically find better and smaller architectures comparing to expert-designed ones, which have shown promising results in architecture design for CNN and Recurrent Neural Network (RNN) [22, 23, 24, 25, 26]. In the literature, one of the representative NAS approaches are reinforcement learning (RL) [14, 15, 27], which trains an RNN controller in the loop: the controller firstly generates an candidate architecture by sampling a list of actions (operations) from a pre-defined search space, and then trains it to convergence to obtain the performance of the given task. The controller then uses the performance as the guiding signal to update the RNN parameters, and the whole process is repeated for many iterations to find to incorporate the weight sharing mechanism into our RL-based method.
As introduced in Section 2.1, most existing GNN architectures are relying on a message passing framework [7], which constitutes the backbone of the designed search space in this work.
Besides, motivated by JK-Network [13], to further improve the expressive capability, we modify the message framework by adding an extra layer which can adaptively combine the outputs of all node aggregation layers.
In this work, we argue and demonstrate in the experiments that these two components are the key parts for a well-behaved GNN model, denoted as Node arggregators and Layer aggregators. The former one focus on how to aggregate the neighborhood features, while the latter one focus on the range of neighborhood to use. Here we introduce the backbone of the proposed search space, as shown in the bottom right part of Figure 1, which consists of two key components: • Node aggregators: We choose 12 node aggregators based on popular GNN models, and they are presented in Table 1. • Layer aggregators: We choose 3 layer aggregators
as shown in Table 1. Besides, we have two more operations, IDENTITY and ZERO, related to skipconnections. Instead of requiring skip-connections between all intermediate layers and the final layer in JK-Network, in this work, we generalize this option by proposing to search for the existence of skipconnection between each intermediate layer and the last layer. To connect, we choose IDENTITY, and ZERO otherwise.
s.t. * = arg min ℒ(, ),
To further inject the domain knowledge from existing GNN architectures, when searching for the skipconnections for each GNN layer, we add one more constraint that the last layer should always be used as the final output, thus for a -layer GNN architecture, we need to search − 1 IDENTITY or ZERO for the skip-connection options. (, ), and for each architecture, we train them from scratch with some hyper-parameters tuning, e.g., the embedding size and learning rate, etc. We then select the best architecture as the searched one, which aligns with the process in previous works [15, 27]. In our experiments, we empirically set = 10 for simplicity. 3.2. Problem formulation For more technical details, we refer readers to [15, 18]. After designing the search space, denoted as , the search Besides, in this work, we also incorporate the weight process implies a bi-level optimization problem [30, 31], sharing mechanism into our framework, and propose the as show in the following: SNAG-WS variant. The key diference between SNAG and SNAG-WS lies in that we create a dictionary to load min ∈ ℒ(, * ), (2) and save the trained parameters of all OPs (Table 1) in a sampled architecture during the search process. where ℒ and ℒ represent the training and validation loss, respectively, and represents the search space introduced in Section 3.1. and represent the architecture and model parameters. Eq. (2) denotes a trialand-error process for the NAS problem, which selects an architecture from the search space, and then trains it from scratch to obtain the best performance. This process is repeated during the given time budget and the optimal * is kept track of and returned after the search process ifnished.
In this work, motivated by the pioneering NAS works [14, 15], we design a RL method to execute the search process. To be specific, during the search phase, we use a recurrent neural network (RNN) controller, parameterized by , to sample an candidate architecture from the search space. The architecture is represented by a list of actions (OPs), including the node aggregators, layer aggregators and IDENTITY/ZERO as shown in Table 1. Then the candidate architecture will be trained till convergence, and the accuracy on a held-out validation set is returned. The parameters of the RNN controller are then optimized in order to maximize the expected validation accuracy E ( ; )[ℛ] on , where ( ; ) is the distribution of architectures parameterized by , and ℛ is the validation accuracy.
In this way, the RNN controller will generate better architectures over time, and can obtain optimal one in the end of the search phase. After finishing the search process, we need to derive the searched architectures. We ifrst sample architectures under the trained distribution
4.1.1. Datasets and Tasks.
Here, we introduce two tasks and the corresponding datasets (Table 2), which are standard ones in the literature [8, 9, 13].
Transductive Task. Only a subset of nodes in one graph are used as training data, and other nodes are used as validation and test data. For this setting, we use three benchmark dataset: Cora, CiteSeer, PubMed. They are all citation networks, provided by [32]. Each node represents a paper, and each edge represents the citation relation between two papers. The datasets contain bagof-words features for each paper (node), and the task is to classify papers into diferent subjects based on the citation networks.
For all datasets, We split the nodes in all graphs into 60%, 20%, 20% for training, validation, and test. For the transductive task, we use the classification accuracy as the evaluation metric.
Inductive Task. In this task, we use a number of graphs as training data, and other completely unseen graphs as validation/test data. For this setting, we use the PPI dataset, provided by [9], on which the task is to classify protein functions. PPI consists of 24 graphs, with each corresponding to a human tissue. Each node has positional gene sets, motif gene sets and immunological Humandesigned GNN NAS methods ours
Methods GCN GCN-JK GraphSAGE GraphSAGE-JK GAT GAT-JK GIN GIN-JK GeniePath GeniePath-JK LGCN Random Bayesian GraphNAS GraphNAS-WS SNAG SNAG-WS
ours
Cora signatures as features and gene ontology sets as labels. 4.1.2. Compared Methods 20 graphs are used for training, 2 graphs are used for validation and the rest for testing, respectively. For the inductive task, we use Micro-F1 as the evaluation metric.
We compare SNAG with two groups of state-of-the-art methods: human-designed GNN architectures and NAS methods for GNN.
Human-designed GNNs. We use the following popular GNN architectures: GCN [8], GraphSAGE [9], GAT [10],
In this part, we give the analysis of the performance comparisons on diferent datasets.
From Table 3, we can see that SNAG models, including SNAG-WS, win over all baselines on most datasets except CiteSeer. Considering the fact that the performance of SNAG on CiteSeer is very close to the best one (Random), it demonstrates the efectiveness of the NAS methods on GNN. In other words, with SNAG, we can obtain well-behaved GNN architectures given a new task.
When comparing SNAG with GraphNAS methods, the performance gain is evident. We attribute this to the superiority of the expressive yet simple search space.
From Table 4, we can see that the performance trending is very similar to that in transductive task, which is that the NAS methods can obtain better or competitive performance than human-designed GNNs. When looking at the NAS methods, we can see that our proposed SNAG, Random and Bayesian outperforms GraphNAS.
This also demonstrates the superiority of the designed search space.
Taking into consideration the results of these two tasks, we demonstrate the efectiveness of SNAG models, especially the superiority of the search space. (a) Cora.
(b) CiteSeer. (c) PubMed.
(d) PPI.
GIN [12], LGCN [11], GeniePath [6]. For models with variants, like diferent aggregators in GraphSAGE or diferent attention functions in GAT, we report the best 4.3. Understanding the search space of performance across the variants. Besides, we extend the idea of JK-Network [13] in all models except for LGCN, SNAG and obtain 5 more baselines: GCN-JK, GraphSAGE-JK, In this section, we show the simplicity and expressiveness GAT-JK, GIN-JK, GeniePath-JK, which add an extra layer. of the designed search space of SNAG from two aspects: For LGCN, we use the code released by the authors 1. For speedup in searching and the performance gain from the other baselines, we use the popular open source library layer aggregators.
Pytorch Geometric (PyG) [33] 2, which implements various GNN models. For all baselines, we train it from 4.3.1. Speedup in searching scratch with the obtained best hyper-parameters on validation datasets, and get the test performance. We In this part, to show the simplicity of the designed repeat this process for 5 times, and report the final mean search space, we compare the eficiency of SNAG and accuracy with standard deviation. GraphNAS by showing the validation accuracy w.r.t to NAS methods for GNN. We consider the following the running time, and the results are shown in Figure 2. methods: Random search (denoted as “Random”) and The accuracy is obtained by evaluating the sampled Bayesian optimization [34] (denoted as “Bayesian”), architecture on validation set after training it from which directly search on the search with random sam- scratch till convergency, which can reflect the capability pling and bayesian optimization methods, respectively. of NAS methods in discovering better architectures with Besides, GraphNAS3 [18] is chosen as NAS baseline. time elapsing. From Figure 2, we can see that SNAG
Note that for human-designed GNNs and NAS meth- speeds up the search process significantly comparing ods, for fair comparison and good balance between to GraphNAS, i.e., the model can obtain better GNN eficiency and performance, we choose set the number of architectures during the search space. Considering the GNN layers to be 3, which is an empirically good choice fact that both GraphNAS and SNAG adopt the same RL in the literature [10, 6]. framework, then this advantage is attributed to simpler and smaller search space. 1https://github.com/HongyangGao/LGCN 2https://github.com/rusty1s/pytorch_geometric 3https://github.com/GraphNAS/GraphNAS 4.3.2. Influence of layer aggregators In this part, to show the stronger expressive capability of the designed search space, we conduct experiments
on all datasets using a search space only with the node aggregators, i.e., removing the layer aggregators, as comparisons. The results are shown in Table 5, and we report the test accuracies of both the SNAG and SNAGWS. From Table 5, we can see that the performance consistently drops on all datasets when removing the layer aggregators, which demonstrates the importance of the layer aggregators for the final performance and aligns with the observation in Section 4.2 that the performance of human-designed GNNs can be improved by adopting the JK-Network architecture.
In this work, to overcome the drawbacks in expressive capability and search eficiency of two existing NAS approaches for GNN, i.e., GraphNAS [18] and Auto-GNN [19], we propose the SNAG framework, i.e., Simplified Neural Architecture search for GNN. By revisiting existing works, we unify state-of-theart GNN models in a message passing framework [7], and design a simpler yet more expressive search space than that of GraphNAS and Auto-GNN. A RL-based search algorithm is designed and a variant (SNAG-WS) is also proposed by incorporating the weight sharing mechanism. Through extensive experiments on realworld datasets, we not only demonstrate the efectiveness of the proposed SNAG framework comparing to various baselines including GraphNAS and Auto-GNN, but also give better understanding of diferent components of the proposed SNAG. For future work, we will explore the SNAG framework in more graph-based tasks besides node classification.