title: Simplifying Architecture Search for Graph Neural Network
authors: Huan Zhao Lanning Wei Quanming Yao
text: 
  
  [
      Leila R. Vale
      December 30, 2023
  =====================
  
  
  
  
  Recent years have witnessed the popularity of Graph Neural Networks (GNN) in various scenarios.  
  To obtain optimal data-specific GNN architectures, researchers turn to neural architecture search (NAS) methods, 
  which have made impressive progress in discovering effective 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 efficiency 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 effectiveness of the SNAG framework compared to human-designed GNNs and NAS methods, including GraphNAS and Auto-GNN.[	Correspondence is to Quanming Yao;
  	and the work was done when Lanning Wei was an intern in 4Paradigm.]
  
  
  
  
  
  
  § INTRODUCTION
  
  
  In recent years, Graph Neural Networks (GNN) <cit.> 
  have been a hot topic due to their promising results on various graph-based tasks, e.g., recommendation <cit.>, fraud detection <cit.>, chemistry <cit.>. 
  In the literature, various GNN models <cit.> have been designed for graph-based tasks.
  Despite the success of these GNN models, 
  there are two challenges facing them. 
  The first one is that there is no optimal architecture which can always behave well in different scenarios. 
  For example, in our experiments (Table <ref> and <ref>), 
  we can see that the best GNN architectures vary on different datasets and tasks. It means that we have to spend huge computational and expertise resources designing and tuning a well-behaved GNN architecture given a specific task, which limits the application of GNN models. Secondly, existing GNN models do not make full use of the best architecture design practices in other established areas, e.g., computer vision (CV). For example, existing multi-layer GNN models tend to stack multiple layers with the same aggregator (see bottom left of Figure <ref>), which aggregates hidden features of multi-hop neighbors. However it remains to be seen whether combinations of different aggregators in a multi-layer GNN model can further improve the performance. 
  These challenges lead to a straightforward question: 
  can we obtain well-behaved data-specific GNN architectures?
  
  To address the above question, researchers turn to neural architecture search (NAS) <cit.> approaches, 
  which have shown promising results in automatically designing architectures for convolutional neural networks (CNN) and recurrent neural networks (RNN). In very recent time, there are two preliminary works, GraphNAS <cit.> and Auto-GNN <cit.>, making the first attempt to apply NAS to GNN architecture design.
  
  Though GraphNAS and Auto-GNN show some promising results,  
  there are some drawbacks in expressive capability and search efficiency of GraphNAS and Auto-GNN due to the designed search space. 
  In the NAS literature <cit.>, 
  a good search space should be both expressive and compact. 
  That is the search space should be large enough to subsume existing human-design architectures, 
  thus the performance of a search method can be guaranteed. 
  However, it will be extremely costly if the search space is too general, which is impractical for any searching method. 
  The search spaces of GraphNAS and Auto-GNN are the same, both of which do not well satisfy the requirement of a good search space. 
  On one hand, they fail to include several latest GNN models, e.g., the GeniePath <cit.>, 
  for which we give a more detailed analysis in Section <ref> (Table <ref>). 
  On the other hand, the search space includes too many choices, making it too complicated to search efficiently. 
  
  
  
  
  
  
  
  
  In this work, to overcome the drawbacks of GraphNAS and Auto-GNN and push forward the research of NAS approaches for GNN, we propose the SNAG framework (Simplified Neural Architecture search for Graph neural networks), consisting of a simpler yet more expressive search space and a RL-based search algorithm. By revisiting extensive existing works, we unify state-of-the-art GNN models in a message passing framework <cit.>, based on which a much more expressive yet simpler search space is designed. The simplified search space can not only emulate a series of existing GNN models, but also be very flexible to use the weight sharing mechanism, which is a widely used technique to accelerate the search algorithm in the NAS literature.
  We conduct extensive experiments to demonstrate the effectiveness 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 Auto-GNN. 
  To better utilize the NAS techniques, 
  we design a novel and effective 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 (SNAG-WS). 
  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 <cit.>. 
  
  
    * Extensive experiments on real-world datasets are conducted to evaluate the proposed SNAG framework, 
  comparing to human-designed GNNs and NAS methods. 
  The experimental results demonstrate the superiority of SNAG in terms of effectiveness and efficiency compared extensive baseline models. 
  
  
  
  
  
  
  
  
  
  
  
  § RELATED WORKS
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Graph Neural Network (GNN)
  
  
  
  GNN is first proposed in <cit.>
  and in the past five years many different variants <cit.> have been designed, all of which are relying on a neighborhood aggregation
  (or message passing) schema <cit.>. As shown in the left part of 
  Figure <ref>, 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 ∈ℝ^N × d, 
  where 𝒱 and ℰ represent the node and edge sets, respectively. N represents the number of nodes and d is the dimension of node features.
  We use N(v) to represent the first-order neighbors of a node v in 𝒢, i.e., N(v) = {u ∈𝒱|(v,u) ∈ℰ}. In the literature, we also create a new set N(v) is the neighbor set including itself, i.e.,  N(v) =  {v}∪{u ∈𝒱|(v,u) ∈ℰ}.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Then a K-layer GNN can be written as follows: the l-th layer
  (l = 1,⋯, K) updates _v for each node v by aggregating its neighborhood as
  
  
  
  
  
  
  
      _v^l =  σ(^(l)·Φ_n({_u^(l-1), ∀ u ∈N(v)})),
  
  where 
  _v^(l)∈ℝ^d_l represents the hidden features of a node v learned by the l-th layer, and d_l is the corresponding dimension. ^(l) is a trainable weight matrix shared by all nodes in the graph, and σ is a non-linear activation function, e.g., a sigmoid or ReLU. Φ_n is the key component, i.e., a pre-defined aggregation function, which varies across on different GNN models. 
  For example, in <cit.>, a weighted summation function is designed as the node aggregators, 
  and in <cit.>, different functions, e.g., mean and max pooling, are proposed as the aggregators. 
  Further, to weigh the importance of different neighbors, attention mechanism is incorporated to design the aggregators <cit.>. 
  
  Usually, the output of the last layer is used as the final representation for each node, which is denoted as _v = _v^(K). In <cit.>, skip-connections <cit.> are incorporated to propagate message from intermediate layers to an extra layer, and the final representation of the node v is computed by a layer aggregation as _v  =  Φ_l( _v^(1),⋯, _v^(K)), and Φ_l can also have different 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 <ref>, we list all node and layer aggregators in this work, which lays the basis for the proposed SNAG framework.
  
  
  
   §.§ Neural Architecture Search (NAS)
  
  
  
  Neural architecture search (NAS) <cit.> 
  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) <cit.>. 
  
  In the literature, one of the representative NAS approaches are reinforcement learning (RL) <cit.>, 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 more promising architectures. GraphNAS <cit.> and Auto-GNN <cit.> are the first two RL-based NAS methods for GNN.
  
  
  
  
  
  Search space is a key component of NAS approaches, the quality of which directly affects the final performance and search efficiency. 
  As mentioned in <cit.>, a good search space should include existing human-designed models, thus the performance of an designed search algorithm can be guaranteed. 
  In this work, by unifying existing GNN models in the message passing framework <cit.> with the proposed node and layer aggregators, we design a more expressive yet simple search space in this work, which is also flexible enough to incorporate the weight sharing mechanism into our RL-based method.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § THE PROPOSED FRAMEWORK
  
  
  
  
  
   §.§ The design of search space
  
  
  
  As introduced in Section <ref>, 
  most existing GNN architectures are relying on a message passing framework <cit.>, 
  which constitutes the backbone of the designed search space in this work. 
  Besides, motivated by JK-Network <cit.>, 
  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 <ref>, which consists of two key components:
  
  	
    * Node aggregators: 
  	We choose 12 node aggregators based on popular GNN models, and they are presented in 
  	Table <ref>. 
  	
  	
    * Layer aggregators: 
  	We choose 3 layer aggregators as shown in Table <ref>. Besides, we have two more operations,  and , related to skip-connections. 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 skip-connection between each intermediate layer and the last layer. To connect, we choose , and  otherwise. 
  
  
  To further inject the domain knowledge from existing GNN architectures, when searching for the skip-connections for each GNN layer, we add one more constraint that the last layer should always be used as the final output, thus for a K-layer GNN architecture, we need to search K-1  or  for the skip-connection options. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Problem formulation
  
  After designing the search space, denoted as 𝒜, the search process implies a bi-level optimization problem <cit.>, as show in the following:
  
      min_α∈𝒜     ℒ_val (α, w^*),
      
      s.t.      w^* = min_w ℒ_train (α, w),
  
  where ℒ_train and ℒ_val represent the training and validation loss, respectively, and 𝒜 represents the search space introduced in Section <ref>. α and w represent the architecture and model parameters. Eq. (<ref>) denotes a trial-and-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 finished.
  
  In this work, motivated by the pioneering NAS works <cit.>, 
  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 θ_c, 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 / as shown in Table <ref>. 
  Then the candidate architecture will be trained till convergence, 
  and the accuracy on a held-out validation set 𝒟_val is returned. 
  The parameters of the RNN controller are then optimized in order to maximize the expected validation accuracy 𝔼_P(α; θ_c)[ℛ] on 𝒟_val, 
  where P(α;θ_c) is the distribution of architectures parameterized by θ_c, 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 first sample n architectures under the trained distribution P(α, θ_c), 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 <cit.>. In our experiments, we empirically set n =10 for simplicity. For more technical details, we refer readers to <cit.>.
  
  Besides, in this work, we also incorporate the weight sharing mechanism into our framework, and propose the 
  SNAG-WS variant. The key difference between SNAG and SNAG-WS lies in that we create a dictionary to load and save the trained parameters of all OPs (Table <ref>) in a sampled architecture during the search process. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § EXPERIMENTS
  
  
  
  
  
  
  
  
   §.§ Experimental Settings
  
  
  
    §.§.§ Datasets and Tasks.
  
  Here, we introduce two tasks and the corresponding datasets (Table <ref>), which are standard ones in the literature <cit.>.
  
  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 <cit.>. 
  Each node represents a paper, and each edge represents the citation relation between two papers. 
  The datasets contain bag-of-words features for each paper (node), and the task is to classify papers into different 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 <cit.>, 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 signatures as features and gene ontology sets as labels. 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.
  
  
  
  
    §.§.§ Compared Methods
  
  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 <cit.>, GraphSAGE <cit.>, GAT <cit.>, GIN <cit.>, LGCN <cit.>, GeniePath <cit.>. For models with variants, like different aggregators in GraphSAGE or different attention functions in GAT, we report the best performance across the variants. Besides, we extend the idea of JK-Network <cit.> in all models except for LGCN, and obtain 5 more baselines: GCN-JK, GraphSAGE-JK, GAT-JK, GIN-JK, GeniePath-JK, which add an extra layer. For LGCN, we use the code released by the authors [https://github.com/HongyangGao/LGCN]. For other baselines, we use the popular open source library Pytorch Geometric (PyG) <cit.> [https://github.com/rusty1s/pytorch_geometric], which implements various GNN models. 
  For all baselines, we train it from scratch with the obtained best hyper-parameters on validation datasets, and get the test performance. We repeat this process for 5 times, and report the final mean accuracy with standard deviation.
  
  NAS methods for GNN.
  We consider the following methods: Random search (denoted as “Random”) and Bayesian optimization <cit.> (denoted as “Bayesian”), which directly search on the search with random sampling and bayesian optimization methods, respectively. Besides, GraphNAS[<https://github.com/GraphNAS/GraphNAS>] <cit.> is chosen as NAS baseline. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Note that for human-designed GNNs and NAS methods, for fair comparison and good balance between efficiency and performance, we choose set the number of GNN layers to be 3, which is an empirically good choice in the literature <cit.>.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Performance comparison
  
  
  In this part, we give the analysis of the performance comparisons on different datasets. 
  
  
  
  
  
  
  
  
  
  
  
  
  From Table <ref>, 
  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 effectiveness 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 <ref>, 
  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 effectiveness of SNAG models, especially the superiority of the search space. 
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Understanding the search space of SNAG
  
  
  In this section, we show the simplicity and expressiveness of the designed search space of SNAG from two aspects: speedup in searching and the performance gain from the layer aggregators.
  
  
  
    §.§.§ Speedup in searching
  
  In this part, to show the simplicity of the designed search space, we compare the efficiency of SNAG and GraphNAS by showing the validation accuracy w.r.t to the running time, and the results are shown in Figure <ref>. The accuracy is obtained by evaluating the sampled architecture on validation set after training it from scratch till convergency, which can reflect the capability of NAS methods in discovering better architectures with time elapsing. From Figure <ref>, we can see that SNAG speeds up the search process significantly comparing to GraphNAS, i.e., the model can obtain better GNN architectures during the search space. Considering the fact that both GraphNAS and SNAG adopt the same RL framework, then this advantage is attributed to simpler and smaller search space.
  
  
  
    §.§.§ 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 <ref>, and we report the test accuracies of both the SNAG and SNAG-WS. From Table <ref>, 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 <ref> that the performance of human-designed GNNs can be improved by adopting the JK-Network architecture.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § CONCLUSION AND FUTURE WORK
  
  
  In this work, to overcome the drawbacks in expressive capability and search efficiency of two existing NAS approaches for GNN, 
  i.e., GraphNAS <cit.> and Auto-GNN <cit.>, we propose the SNAG framework, 
  i.e., Simplified Neural Architecture search for GNN. 
  By revisiting existing works, we unify state-of-the-art GNN models in a message passing framework <cit.>, 
  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 real-world datasets, we not only demonstrate the effectiveness of the proposed SNAG framework comparing to various baselines including GraphNAS and Auto-GNN, but also give better understanding of different components of the proposed SNAG. 
  For future work, we will explore the SNAG framework in more graph-based tasks besides node classification.
  
  plain
  
  
  