{'fraction_non_alphanumeric': 0.03580093954881008, 'fraction_numerical': 0.009498735222755666, 'mean_word_length': 5.030977584059776, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Relational Graph Neural Network Design via Progressive Neural Architecture Search

We propose a novel solution to addressing a long-standing dilemma in the representation learning of graph neural networks (GNNs): how to effectively capture and represent useful information embedded in long-distance nodes to improve the performance of nodes with low homophily without leading to performance degradation in nodes with high homophily. This dilemma limits the generalization capability of existing GNNs. Intuitively, interactions with distant nodes introduce more noise for a node than those with close neighbors. However, in most existing works, messages being passed among nodes are mingled together, which is inefficient from a communication perspective. Our solution is based on a novel, simple, yet effective aggregation scheme, resulting in a ladder-style GNN architecture, namely LADDER-GNN. Specifically, we separate messages from different hops, assign different dimensions for them, and then concatenate them to obtain node representations. Such disentangled representations facilitate improving the information-to-noise ratio of messages passed from different hops. To explore an effective hop-dimension relationship, we develop a conditionally progressive neural architecture search strategy. Based on the searching results, we further propose an efficient approximate hop-dimension relation function to facilitate the rapid configuration of the proposed LADDER-GNN. We verify the proposed LADDER-GNN on seven diverse semi-supervised node classification datasets. Experimental results show that our solution achieves better performance than most existing GNNs. We further analyze our aggregation scheme with two commonly used GNN architectures, and the results corroborate that our scheme outperforms existing schemes in classifying low homophily nodes by a large margin.


Introduction
Recently, a large number of research efforts have been dedicated to applying deep learning methods to graphs, known as graph neural networks (GNNs) [15,36], achieving great success in modelling non-structured data, e.g., social networks [25] and recommendation systems [26].
Learning an effective low-dimensional embedding to represent each node in the graph is arguably the most important task for GNN learning, wherein the node embedding is obtained by aggregating information with its direct and indirect neighbouring nodes passed through GNN layers [12]. Earlier GNN works usually aggregate with neighboring nodes that are within a short range (1-2 hops). For many graphs, this may cause the so-called under-reaching issue [3] -distant yet informative nodes are not involved, leading to unsatisfactory results, particularly when the homophily level of the graph is relatively low [31].
Consequently, lots of techniques that attempt to aggregate long-distant neighbours are proposed by deepening or widening the network [19,20,44,45,52]. However, when we aggregate information from too many long-distant neighbours, the so-called over-smoothing problem [20] may occur, causing nodes to be less distinguishable from each other [7]. To the end, the inference performance often greatly degrades, particularly at the nodes with high homophily level. This situation puts the GNN learning into a dilemma. On the one hand, to enhance the generalization capability of existing GNNs, particularly in dealing with graphs with low homophily, we should integrate information embedded in long-distance nodes in the learning process. On the other hand, such an integration under existing aggregation schemes will often cause obvious performance degradation, particularly in graphs with high level of homophily [53].
To alleviate this problem, several hop-aware GNN aggregation schemes are proposed in the literature [2,38,40,49,54]. While showing promising results, the messages passed among nodes are mingled together in these approaches. From a communication perspective, mixing information from clean sources (mostly low-order neighbours) and that from noisy sources (mostly high-order neighbours) would inevitably cause difficulty for the receiver (i.e., the target node) to extract information.
Motivated by the above observations and considerations, we propose a novel, simple, yet effective hop-aware aggregation scheme, resulting in a ladder-style GNN architecture, namely LADDERGNN, to comprehensively address this dilemma. The contributions of this paper include:  Figure 1. The histogram for the number of nodes (y axis) with different homophily ratio, i.e., the percentage of neighbors with the same label as the target node at Hop-k on the Pubmed dataset. It indicates a diminishing information-to-noise ratio for messages ranging from low-order hops to high-order hops.
• We take a communication perspective on GNN message passing. That is, we regard the target node for representation learning as the receiver and group the set of neighbouring nodes with the same distance to it as a transmitter that carries both information and noise. The dimension of the message can be regarded as the capacity of the communication channel. Then, aggregating neighbouring information from multiple hops becomes a multi-source communication problem with multiple transmitters over the communication channel.
• To improve node representation learning, we propose to separate the messages from different transmitters (i.e., Hop-k neighbours), each occupying a proportion of the communication channel (i.e., disjoint message dimensions). As the homophily ratio in highorder neighbours is often lower than that in low-order neighbours, the resulting hop-aware representation is unbalanced with more dimensions allocated to loworder neighbours, leading to a ladder-style aggregation scheme.
• To explore the dimension allocation manner for neighbouring nodes with different hops effectively, we propose a conditionally progressive neural architecture search (NAS) strategy. Motivated by the search results, we introduce an approximate hop-dimension relation function, which can generate close results to the NAS solution without applying compute-expensive NAS. To verify the effectiveness of the proposed GNN representation learning solution, we demonstrate it on seven semisupervised node classification datasets for both homogeneous and heterogeneous graphs with different homophily levels. Experimental results show that our solution achieves better performance than most existing GNNs. We further analyze our aggregation scheme with two commonly used GNN architectures, and the results corroborate that our scheme outperforms existing schemes in classifying low homophily nodes by a large margin.

Related Work and Motivation
GNNs adopt message passing to learn node embeddings, which involves two steps for each node: neighbour aggre-gation and linear transformation [12]. The following formula presents the mathematical form of message passing in a graph convolutional network (GCN) [15]. Given an undirected graph G= (V, E) with N nodes and adjacency matrix A, we can aggregate node features at the l-th layer H (l) ∈ R N ×C (l) i as: is the trainable weight matrix at the l-th layer used to update node embeddings. C h are the channel size of the input and hidden layer, respectively. σ(·) is an activation function.
By taking the importance of different neighbours into consideration, graph attention network (GAT) [36] applies a multi-head self-attention mechanism during aggregation and achieves higher performance than GCN in many datasets. Recent GNN works improve GCN or GAT from two aspects. (i) Some make changes to the input graphs [7,27,32,46,50]. For example, [27] proposes to drop some task-irrelevant or noisy edges to achieve high generalization capability. The underlying thought of such changes is to increase the homophily level of the input graph so as to achieve satisfactory results even when aggregating a short range of neighboring nodes. Unfortunately, for many practical applications, it is difficult, if not impossible, to design a high homophily graph. (ii) Without changing the graph, some GNN works try to further extract relevant information from high-order neighbours. Our work belongs to this category.
In order to aggregate information from high-order neighbours, some earlier works [19,44,45] simply stack deeper networks to retrieve such information recursively. To mitigate the possible over-fitting issues (caused by model complexity), SGC [41] removes the nonlinear operations and directly aggregates node features from multiple hops. To relieve the potential over-smoothing problem that results in less discriminative node representations (due to overmixing) [20], various hop-aware aggregation solutions are proposed. Some of them (e.g. HighOrder [29], MixHop [2],  N-GCN [1], GB-GNN [30]) employ multiple convolutional branches to aggregate neighbors from different hops. Others (e.g. AM-GCN [39], HWGCN [23], MultiHop [54]) try to learn adaptive attention scores when aggregating neighboring nodes from different hops.
As our scheme is closely related to the homophily level of a node, we provide a definition of homophily ratio and further explain our motivation based on this definition. Given a graph G = (V, E), we define the homophily ratio of the node i as , where j is its neighboring nodes, C is the class label, and thus the r i indicates the percentage of nodes with the same class to i in all its neighboring nodes.
In Figure 1, we plot the homophily ratio for nodes in the Pubmed dataset with different hops. As can be observed from the figure, with the increase of hop distance, the percentage of neighbouring nodes with the same label decreases, indicating a diminishing information-to-noise ratio for messages ranging from low-order neighbours to highorder neighbours. This is a common phenomenon when the graph is well designed. Therefore, the critical issue in GNN message passing is how to retrieve information effectively while suppressing noise simultaneously. However, all the existing aggregation schemes do not explicitly and sufficiently consider this issue, making it challenging to achieve good performance in both high homophily nodes and low homophily nodes. This observation motivates us to propose our LADDERGNN architecture.

Method
In Sec. 3.1, we take a communication perspective on GNN message passing and representation learning. Then, we give an overview of the proposed LADDERGNN framework in Sec. 3.2. Next, we explore the dimensions of different hops with an RL-based NAS strategy in Sec. 3.3 and then introduce the approximate hop-dimension relation function in Sec. 3.4.

GNN Representation Learning from a Communication Perspective
In GNN representation learning, messages are passed from neighbouring nodes to the target node and updated its embedding. Figure 2 presents a communication perspective on GNN message passing, wherein we regard the target node as the receiver. Considering neighbouring nodes from different hops tend to contribute unequally (see Figure 1), we group the set of neighbouring nodes with the same distance as one transmitter, and hence we have K transmitters if we would like to aggregate up to K hops. The dimension of the message can be regarded as the communication channel capacity. Then, GNN message passing becomes a multi-source communication problem.
Different from a conventional communication system that employs a well-developed encoder for the information source, one of the primary tasks in GNN representation learning is to learn an effective encoder that extracts useful information with the help of supervision. Consequently, mixing clean information sources (mostly low-order neighbours) and noisy information sources (mostly high-order neighbours) makes the extraction of discriminative features challenging.
The above motivates us to perform GNN message passing without mixing up messages from different hops, as shown in Figure 2(d). At the receiver, we concatenate the messages from various hops, and such disentangled repre- Hop=3 In-hop Aggregation Embedding Transformation Figure 3. Illustration of the process of LADDERGNN of one target node. The height of bars represents the dimension of embeddings from each node. Colors are with respect to hops.
sentations facilitate extracting useful information from various hops with little impact on each other. Moreover, dimensionality significantly impacts any neural networks' generalization and representation capabilities [3,4,22,34], as it controls the amount of quality information learned from data. In GNN message passing, the information-to-noise ratio of low-order neighbours is usually higher than that of high-order neighbours. Therefore, we tend to allocate more dimensions to close neighbours than distant ones, leading to a ladder-style aggregation scheme.

Ladder-Aggregation Framework
With the above, Figure 3 shows the node representation update procedure in the proposed LADDERGNN architecture. For a particular target node (the center node in the figure), we first aggregate node within each hop, which can be conducted by existing node-wise aggregation methods (e.g., GCN or GAT). Next, we determine the dimensions for the aggregated messages from different hops and then concatenate them, instead of mixing them up, for inter-hop aggregation. Finally, we perform a linear transformation to generate the updated node representation.
Specifically, K is the maximum number of neighboring hops for node aggregation. For each group of neighbouring nodes at Hop-k, we determine their respective optimal dimensions and then concatenate their embeddings into H as follows: where A k is the normalized adjacency matrix of the k th hop and X is the input feature. A learnable matrix W k ∈ R Ci×C o,k controls the output dimension of the k th hop as C o,k . means concatenation. Encoding messages from different hops with distinct W k avoids the over-mixing of neighbours, thereby alleviating the impact of noisy information sources on clean information sources during GNN message passing. Accordingly, H is a hop-aware disentangled representation of the target node. Then, with the classifier f after the linear layer W U , we have: where Y is the output softmax values. Given the supervision Y of some nodes, we can use a cross-entropy loss to calculate gradients and optimize the above weights in an end-to-end manner.
With the above, if the adjacency matrix A are the same as the original GCN architecture, the resulting GNN architecture with our ladder-aggregation framework is namely Ladder-GCN. Similarly, when we employ a self-attention scheme within hops to obtain the attention-based adjacency matrixÂ as in the original GAT architecture, the resulting GNN architecture is namely Ladder-GAT. Please note, our proposed ladder-aggregation scheme could also be integrated into other GNN architectures (e.g., [27]).

Hop-Aware Dimension Search
Allocating different dimensions for messages from different hops is the key in LADDERGNN design. As there are numerous hop-dimension allocation possibilities, determining an appropriate allocation is a non-trivial task.
In recent years, neural architecture search (NAS) has been extensively researched, which automatically designs deep neural networks with comparable or even higher performance than manual designs by experts (e.g., [5,21,24,35,55]). Existing NAS works in GNNs [11,33,51] search the graph architectures (e.g., 1-hop aggregators, activation function, aggregation type, attention type, etc) and hyperparameters to reach better performance. However, they ignore to aggregate multi-hop neighbours, let alone the dimensionality of each hop. In the following, we introduce our proposed NAS solution.
Search Space: Different from previous works in GNNs [11,48,51], our search space focuses on the dimension of each hop, called hop-dimension combinations. To limit the possible search space O for hopdimension combinations, we apply exponential sampling 2 0 , 2 1 , 2 2 ,...,C i ,...,2 (n−1) , 2 (n) strategies for dimensions. n are hyper-parameters, representing the index and sampling granularity to cover the possible dimensions. For each strat- egy, the search space should also cover the dimension of initial input feature C i . Basic Search Algorithm: Given the search space O, we target finding the best model M * ∈ M to maximize the expected validation accuracy. We choose the reinforcement learning strategy since its reward is easy to customize for our problem. As shown in Figure 4, a LSTM controller based on the parameters θ generates a sequence of actions a 1: is sampled from the search space mentioned above. Then, we can build a model M mentioned in Sec. 3.2, and train it with a cross-entropy loss function. Then, we test it on the validation set D to get an accuracy R D (M ). Next, we can use the accuracy as a reward signal and perform a policy gradient algorithm to update the parameters θ so that the controller can generate better hopdimension combinations iteratively. The objective function of the model is shown in: Conditionally Progressive Search Algorithm: Considering the extremely large search space with the basic search algorithm, e.g., the search space size will be (n+1) k for the exponential sampling with k hops. This makes it more challenging to search for the optimal combinations with limited computational resources. Moreover, we find that there are a large number of redundant actions in our search space. To improve the efficiency and effectiveness of the search procedure, we are inspired to propose a conditionally progressive search algorithm.
That is, instead of searching the entire space all at once, we divide the searching process into multiple phases, starting with a relatively small number of hops, e.g., K = 3. After obtaining their results, we only keep those hopdimension combinations that are promising, where they are regarded as the conditional search space, with high R D (M ).
Next, we conduct the hop-dimension search for the (K+1) th hop based on the conditional search space filtered from the last step, and again, keep those combinations with high R D (M ). This procedure is conducted progressively until aggregating more hops cannot boost performance. With this algorithm, we can largely reduce the redundant search space to enhance search efficiency.

Hop-Dimension Relation Function
The computational resources required to conduct NAS are extremely expensive for large graphs, even with the proposed progressive search algorithm. Therefore, it is essential to have an efficient method to determine the dimensionality of every hop in practical applications. From our NAS experimental results (Sec. 4.1), we observe that the loworder neighbours within L hops are usually directly aggregated with the original feature dimensions while high-order neighbours are associated with an approximately exponentially decreasing dimensions.
This motivates us to propose a simple yet effective hopdim relation function to approximate the NAS solutions. The output dimension of k th hop is: where 0 < d < 1 is the dimension compression ratio, and C i is the dimension of the input feature. With such an approximate function, there is only one hyper-parameter to determine, significantly reducing the computational cost.

Experiment
In this section, we validate the effectiveness of LAD-DERGNN on seven widely-used semi-supervised node classification datasets. We first analyze the NAS results in Sec Data description: For the semi-supervised node classification task on homogeneous graphs, we evaluate our method on five datasets: Cora [47], Citeseer [47], Pubmed [47], OGB-Arxiv [14] and OGB-Products [14]. We split the training, validation and test set following earlier works [2,15,36,39]. Furthermore, on heterogeneous graphs, we verify the methods on two datasets: ACM and IMDB [38]. Due to page limits, more details about dataset descriptions, data pre-processing procedure and more comparison with existing methods are listed in the Appendix.

Results from Neural Architecture Search
To study the impact of the dimensions among hops, we conduct the NAS on different datasets to find out the optimal hop dimension combinations. There exist a number of NAS approaches for GNN models, including random search (e.g., AGNN [51]), reinforcement learning-based (RL) solution (e.g., GraphNAS [11] and AGNN [51]) and evolutionary algorithm (e.g., Genetic-GNN [33]), wherein the RL-based solutions are more effective than others. Thus, in this work, we follow the same strategy as RL-based solutions to search for appropriate dimensions allocated to each hop. In particular, we search the hop-dimension combinations of 10 hops on Cora, Citeseer, and Pubmed datasets and show experimental results in Table 1. Compared with existing NAS methods, our NAS method achieves better results with conditional progressive search algorithm on Cite-seer and Pubmed datasets, improving over Genetic-GNN by 1.4% and 2.1%, respectively. Meanwhile, we achieve comparable accuracy in the Cora dataset only by considering the hop-dimension combinations. Moreover, compared with w/o cond., we can find 2.6% improvements on conditional progressive search, indicating the effectiveness of this strategy to search optimal hop dimension combinations under a limited search resource. Moreover, the Approx. method show competitive results with NAS-based results, especially on Cora and Citeseer datasets.
Specially, we demonstrate the histogram of the possible dimension assignment for different hops in Figure 5. We can obtain two observations: (i) for low-order neighbors, i.e., when hop is less than 3 in this case, most of the sorted solutions with high accuracy keep the initial feature dimension; (ii) most of the possible dimensions of the hop are only in single digits, which verify the necessity of the proposed conditional strategy to reduce the search space greatly; (iii) The dimensionality tends to be reduced for high-order neighbours, and approximating it with exponentially decreasing dimensions occupies a relatively large proportion of the solutions.
Last, the above results serve two purposes: (i) they facilitate and support the design of the proposed approximate hop-dimension relation function; (ii) they validate the effectiveness of the proposed approximate hop-dimension relation function. Accordingly, we could use the approximate relation function with only one parameter to search for proper hop dimensions with comparable performance to the NAS solution.

Comparison with General GNNs
Quantitative Results: We demonstrate the accuracy among general GNNs, like GCN, GAT and GraphSage on five popular datasets in Table 2. As an effective hop-aware aggregation, we take GCN and GAT as examples to integrate them into our aggregation framework. The results show our methods can boost the performance of GCN and GAT by up to 4.7%, indicating the proposed aggregation is beneficial and robust on different dataset. Detailed Analysis: To understand the benefits provided by LADDERGNN, in Figure 6, we show the classification accuracy for nodes under different homophily ratio. As ex- pected, high homophily nodes (e.g., when the ratio is higher than 50%) are relatively easy to classify with high accuracy, and there is not much difference between the results of our approach and those of existing methods. For the low homophily nodes (e.g., when the ratio is smaller than 25%), LADDERGNN clearly excels with much higher classification accuracy and it even sustains at similar accuracy as those nodes with homophily ratio of 60%.   Table 3. Experimental results are performed on a TITAN-Xp machine. We average ten runs on the Citeseer dataset to obtain the average training time for each epoch, the average test time, and the model accuracy. The settings of the other methods follow the respective papers, and we set K = 5 and d = 0.0625 in Ladder-GCN. As can be seen from Table 3, the computational time and memory costs of Ladder-GCN are moderately larger than SGC, with higher model accuracy.

Comparison with Hop-aware GNNs
Our proposed solution improves the hop-aware GNN representation learning capability when aggregating highorder neighbors during message passing. Table 4 presents the comparison with other hop-aware solutions.
As can be observed, in terms of Top-1 accuracy (%), our LADDERGNN with a simple hop-dimension relation function achieves competitive results on all three datasets, indicating the effectiveness of the proposed solution. Specifically, our method shows more improvements on Citeseer

Heterogeneous Graph Representation Learning
Heterogeneous graphs that consist of different types of entities (i.e., nodes) and relations are ubiquitous. In heterogeneous graph representation learning, meta-path-based solutions are proposed to model the semantics of different relations among entities, e.g., Movie-Actor-Movie and Movie-Director-Movie in the IMDB dataset.
In this section, we apply our method to heterogeneous semi-supervised classification on two popular datasets: ACM and IMDB extracted by HAN [38]. For a fair comparison, we follow the same experimental settings.
Meta-path based baseline: Heterogeneous graph attention network (HAN) introduces hierarchical attention, including node-level and semantic-level attention. It can learn the importance between a node and its meta-path-based neighbours and the importance of different meta-paths for heterogeneous graph representation learning.
Ladder Aggregation at Semantic Level: Since distinct meta-paths have different contributions to the target node representation, we propose to use LADDERGNN for semantic-level aggregation. In particular, with the prior knowledge of the ordinal importance of meta-paths (e.g., MDM is more important than MAM for movie type), we can allocate dimensions for them accordingly. Therefore, the hop-dimension relation function is used here for semantics-dimension relations, wherein more/less relevant semantic embeddings get higher/lower dimensions. Again, the only hyper-parameter in our method is the compression ratio d.
Compare LADDERGNN with Attention-based Aggregation: We use eight kinds of meta-path combinations and compare with GAT 1 and HAN. Experimental results on Top-1 accuracy are shown in Table 5. From the results we can observe: (i) distinguishing heterogeneous paths is essential as the performance of GAT is always the worst; (ii) by allocating distinct dimensions for different semantic embeddings, the proposed LADDERGNN produces better results than state-of-the-art solution 2 (i.e., HAN).

Ablation Study
To analyze the impact of the hop-dimension function in Eq. (5), we conduct experiments by varying two dominant hyper-parameters: the furthest hop K, the dimension compression rate d and the aggregation methods among hops. We present the results on Citeseer. Impact of the largest hop K and compression rate d.
In Table 6, the compression rate d varies from 2 to 0.03125 (1/32) as comparison. We can observe that (i) by increasing the furthest hop K with fixed d, the performance will increase to saturation when d < 1. When increasing K, more information can be aggregated from neighbors. LAD-DERGNN's ability to suppress noise by dimension compression facilitates the performance to saturation. (ii) by decreasing the decay rate on fixed K, the performance first increases and then drops under most situations. The reason for increasing is that the decreased compression rate will map the distant nodes to a lower and suitable dimension space, suppressing the interference of noise in distant nodes. However, there is an upper bound for these improvements given K. When d < 0.0625, the reduced dimension is too low to preserve the overall structural information, leading to worse performance in most cases. (iii) the effective rate d is mainly on {0.125, 0.0625}, which can achieve better results for most K. If K = 5 and d = 0.0625, we obtain the best accuracy of 74.7%. (iv) note that there are significant improvements with dimension compression comparing to dimension increase (d = 2), which validates the effectiveness of the basic principle of dimension compression.
Impact of the aggregation operators.
For aggregation method among hops, most existing solutions (e.g., GCN, SGC and GAT) mix the information from multiple hops, while Ladder-GNN disentangles and concatenates the information from multiple hops. To further demonstrate the effectiveness of the proposed method, we conduct an experiment to substitute concatenation with addition in Ladder-GNN. To accommodate the dimensional differences between features from different hops, we use zero paddings to fill those vacant positions before addition. As can be seen from Table 7, concatenating features show consistently better results.

Conclusion
In this work, we propose a novel, simple, yet effective ladder-style GNN aggregation scheme, namely Ladder-GNN. We take a communication perspective for GNN representation learning, which motivates us to separate messages from different hops and assign different dimensions for them before concatenating them to obtain the node representation. Experimental results on various semi-supervised node classification tasks show that the proposed solution can achieve state-of-the-art performance on most datasets. Particularly, at nodes with low homophily, the proposed solution outperforms existing aggregation schemes by a large margin. This characteristic makes our solution a promising tool to enhance the generalization capability of existing GNNs, particularly in handling nodes with low homophily, which is a pain point of most existing GNNs.

A. Appendices
In the appendix, we first detail our experimental settings, including datasets, our preprocessing procedure and other settings in Appendix B. Then, we apply the proposed LADDERGNN on heterogeneous graph representation learning problem in Appendix C. Next, we discuss the limitations of our work in Appendix G. Finally, we present the broader impact of this work in Appendix H.

A. Experimental Settings
Our experiments are conducted on a machine with an NVIDIA Tesla V100-SXM2-32GB GPU card. Most experiments take up a few hundred MBytes memory.
For the NAS experiment, the controller is a one-layer LSTM with 100 hidden units. We train it with Adam optimizer. The learning rate is 3.5 × 10 −4 , mini-batch is 128, and the weights are randomly initialized, which is the same as GraphNAS [11] for a fair comparison. We train each sampled model M with 150 epochs, and the controller update step is 50. For the conditionally progressive search algorithm, we filter hop-dimension combinations with R D (M ) set as 0.8, 0.7, 0.78 for Cora, Citeseer, Pubmed datasets, respectively. Each model costs about 25 seconds to get its reward R D (M ) and hence it takes about 15 days to get 50, 000 models.
Considering computational efficiency, NAS may not be practical for graphs with a large amount of nodes and edges [14]. Therefore, except for the results shown in Sec. 4.1, all the other experiments are conducted with the proposed approximate hop-dimension relation function in Sec. 3.4. In these experiments, our training settings are the same as SGC [41] with a fixed random seed. The learning rate is 0.2 with Adam optimizer and the total number of epochs is 200. All the hyper-parameters are listed in the scripts of our Code.

B. Homogeneous Data Description
We use six datasets on semi-supervised node classification: Cora, Citeseer, Pubmed, OGB-Arxiv, and OGB-Products. The specifics of these datasets are listed in Table 8.  [47] are citation network datasets, where the nodes are papers and the edges are citation links. The node attributes are the bag-of-words features of papers, and nodes are divided into different areas. We follow the data preprocessing by SGC 4 .
OGB-Arxiv 5 [14] is a citation network between all Computer Science (CS) arXiv papers indexed by MAG [37], where nodes are arxiv papers and edges are citation links. The node feature comes from a 128-dimensional feature vector generated by averaging the embeddings of words in its title and abstract. We follow the data preprocessing by AGD 6 .
OGB-Products 7 [14] is an Amazon product co-purchasing network. Nodes represent products sold on Amazon, and edges between two products indicate that the products are purchased together. We follow previous works [8,14] to process node features and target categories. Specifically, node features are obtained by extracting bag-of-words features from the product descriptions followed by a Principal Component Analysis, and its dimension is reduced to 100. We follow the data preprocessing by SAGN 8 . For GAT, we explore whether GAT itself can aggregate higher-order neighbors effectively. Hence, we use eight multiheads and four kinds of channel sizes {1, 4, 8, 16} for each head in their self-attention scheme. To aggregate K hop neighbors, we set two kinds of baselines with a deeper structure (stacking K layers), named as D-GAT in blue lines and a wider (one layer computes and aggregates multiple-order neighbors) network W-GAT in orange lines. In Figure 7(a), we demonstrate the accuracy of D-GAT and W-GAT with ours in purple line. As we can observe, the D-GAT will suffer from over-smoothing problems suddenly (K=4), especially for the larger channel size. Moreover, the performance of W-GAT will degrade gradually, due to the over-fitting problems with more parameters. Thus, both of the two aggregations drop their performance as hops increase. On the contrary, the proposed Ladder-GAT is robust to the increasing of hops since the proposed LADDERGNN can relieve the above problems when aggregating high-order neighbors.
In Figure 7(b), we compare the original GCN and GAT methods with the proposed Ladder-GCN and Ladder-GAT on Citeseer dataset. We can obtain similar observations. As the high-order neighbors are aggregated, GCN and GAT encounter performance degradation, while our framework can boost the performance and relieve the potential over-smoothing issue.
In Figure 7(c), we compare GCN, SGC with Ladder-GCN, where the low-order L hops are aggregated without dimension reduction and compress the dimensions of hop k (L < k ≤ K). The purple line is set as an interesting setting: only compress the last K th hop to a lower dimension 32 and L=K-1. Under the same horizontal coordinate K hops, Ladder-GCN achieves consistent improvement compared with both GCN and SGC (in orange line). The reasons behind this result is that the parameters updated in SGC are affected by (i) the decrescent information-to-noise ratios within distant hops and (ii) oversquashing phenomena [3] -information from the exponentially-growing receptive field is compressed by fixed-length node vectors, and causing it is difficult to make k th hop neighbors play a role. This observation suggests that compressing the dimension on the last hop can mitigate the over-squashing problem in SGC, which consistently improves the performance of high-order aggregation.

E. Analyses the Differences between LADDERGNN and Attention-based Aggregation
Based on the comparisons in Section 4.4 of heterogeneous graph representation learning, we further study the semantic attention scores learned in HAN. In Figure 8, we demonstrate three kinds of semantic attention scores between two metapaths in the ACM dataset from different self-attention channels from node level, e.g., {4, 8, 16} of each head and the head is 4 here. We find that (i) although these three models obtain similar accuracy, the patterns of their attention scores are quite different, and the scores of the best accuracy are also different, for instance, {PAP=0.823, PSP=0.177} for the first model while {PAP=0.609, PSP=0.391} for the second model; (ii) the learnable attention scores are changed by epochs, which can be vulnerable with training strategies; (iii) if only a score is multiplied over the whole semantic features, then both useful and useless information of the features will be scaled simultaneously. Therefore, the information-to-noise ratio will not be changed. Thus, the attention-based methods tend to obtain worse performance. Compared with these methods, our method shows consistent improvements and proves its effectiveness.  Table 10 shows results on LADDERGNN with other two groups of existing methods, such as general GNNs and GNNs with modified graph structures, in terms of Top-1 accuracy (%) on the most-used datasets. Meanwhile, Table 11 compares LADDERGNN with existing methods on larger graphs. As a new hop-aware aggregation, our method can achieve the stateof-the-art performance in most cases by improving the hop-aware aggregation method of GCN and GAT, and the proposed method can improve GCN and GAT consistently. Specifically, Ladder-GCN surpasses 1.5% with GXN on Citeseer, 0.5% with DisenGCN on Pubmed, respectively. Our method can still show superiority on Citeseer, showing its effectiveness to handle those graphs with lower information-to-noise ratio. Although there are kinds of variants on GNNs, we verify the potential of a better hop-aware aggregation method. Hence, applying the proposed method to other structure modification and aggregation within one hop will be a future direction.

G. Limitations and Future Work
The proposed LADDERGNN focuses on hop-level aggregation and the dimensionality of high-order neighbors is reduced with our hop-dim relation function. The obtain high-quality node representations, LADDERGNN relies on the quality of the given graphs for learning. That is, for node classification problems, the homogeneity ratio of low-order neighbors is higher than that of high-order neighbors for LADDERGNN to perform well. While this is true in most cases, it would be better to jointly optimize the structure of the graph and LADDERGNN, especially for large graphs with a huge amount of nodes and complex relations. We plan to investigate this joint opimiztion problem in our future work.

H. Broader impact
Graph neural networks(GNNs) have been widely used in various real-world applications ranging from chemo-and bioinformatics to recommendation systems and social network analysis. Although our method can boost the development of the GNNs, we also notice that there should be a negative impact of this technique on protecting personal privacy and security. For instance, customers' behaviour may be easily predicted based on their historical relevant hobbies, which provides a convenient way for unscrupulous business people to send spam information. Therefore, we call on researchers to cultivate a responsible AI-ready culture in technology development and avoid the abuse of technologies.