Long-range Meta-path Search on Large-scale Heterogeneous Graphs

Authors: chao  li
zijie  guo
qiuting  he
kun  he
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 10:12:38

Abstract: Utilizing long-range dependency, a concept extensively studied in homogeneous graphs, remains underexplored in heterogeneous graphs, especially on large ones, posing two significant challenges: Reducing computational costs while maximizing effective information utilization in the presence of heterogeneity, and overcoming the over-smoothing issue in graph neural networks. To address this gap, we investigate the importance of different meta-paths and introduce 
an automatic framework for utilizing long-range dependency on heterogeneous graphs, denoted as Long-range Meta-path Search through Progressive Sampling (LMSPS). Specifically, we develop a search space with all meta-paths related to the target node type. By employing a progressive sampling algorithm, LMSPS dynamically shrinks the search space with hop-independent time complexity. Through a sampling evaluation strategy, LMSPS conducts a specialized and effective meta-path selection, leading to retraining with only effective meta-paths, thus mitigating costs and over-smoothing. Extensive experiments across diverse heterogeneous datasets validate LMSPS's capability in discovering effective long-range meta-paths, surpassing state-of-the-art methods. Our code is available at https://github.com/JHL-HUST/LMSPS.

Main paper: 
 introduction: 
 Heterogeneous graphs are widely used for modeling multiple types of entities and relationships in complex systems by various types of nodes and edges. For instance, the large-scale academic network, OGBN-MAG, contains multiple node types, i.e., Paper (P), Author (A), Institution (I), and Field (F), as well as multiple edge types, such as Author ----------→ Institution, and Paper has a topic of --------→Field. These elements can be combined to build higher-level semantic relations called meta-paths [44] . For example, APA is a 2-hop meta-path representing the co-author relationship, and PFPAPFP is a 6-hop meta-path related to long-range dependency.Utilizing long-range dependency is essential for graph representation learning. For homogeneous graphs, many graph neural networks (GNNs) [28, 4, 1, 54] have been developed to gain benefit from long-range dependency. Utilizing long-range dependency is also crucial for heterogeneous graphs. For instance, the Internet movie database (IMDB) contains 21K nodes with only 87K edges. Such sparsity means each node has only a few directly connected neighbors and requires models to enhance the node embedding from long-range neighbors. The main challenge in using long-range dependency on heterogeneous graphs is how to alleviate costs while striving to effectively utilize information in exponentially increased receptive fields, which is much more challenging compared to homogeneous graphs due to the heterogeneity. In addition, the well-known over-smoothing issue [30, 24] occurring in many GNNs also needs to be addressed.Heterogeneous Graph Neural Networks (HGNNs) are popular deep learning techniques for heterogeneous graph representation learning. The key idea is to aggregate valuable neighbor information based on a range of relations to enhance the semantics of vertices. Traditional HGNNs are typically classified into two categories: metapath-free methods and metapath-based methods. Most metapath-free HGNNs [63, 18, 21, 34] utilize information from l-hop neighborhoods by stacking l layers. However, on large-scale heterogeneous graphs, the number of nodes in receptive fields grows exponentially with the number of layers, making them hard to expand to large hops. A recent work [36] employs the graph transformer [54] to learn heterogeneous graphs, which can only exploit long-range dependency in small datasets due to the quadratic complexity of transformer [17] .Metapath-based HGNNs [48, 11, 23, 52] obtain information from l-hop neighborhoods by utilizing single-layer structures and meta-paths with maximum hop l, i.e., all meta-paths no more than l hops. Benefiting from the feature of selective aggregation of neighbors based on meta-path, metapathbased HGNNs show greater potential in handling large-scale datasets [55, 52] . For metapath-based HGNNs, to exploit long-range dependency, the maximum hop needs to be large enough as there are no stacking layers. However, the number of meta-paths also grows exponentially with maximum hop l, corresponding to exponential receptive fields associated with layers in metapath-free methods. For instance, on OGBN-MAG, to gain a 3-hop meta-path based on the 2-hop meta-path PAP, the next node type has three choices (A, P, and F). For each additional hop, the number of possible meta-paths increases exponentially. Hence, utilizing long-range dependencies on large-scale heterogeneous graphs has not been resolved yet.This paper investigates the importance of various meta-paths and makes two key observations: (1) A small number of meta-paths dominate the performance, and (2) certain meta-paths can have a negative impact on performance. The second observation explains why few HGNNs gain benefit from long-range neighbors. Different from homogeneous graphs, messages on heterogeneous graphs can be noisy or redundant for specific tasks, and the presence of long-range dependencies makes it more challenging to exclude negative heterogeneous information, even with the use of attention mechanisms. For example, focusing too much on Institution instead of related Papers is harmful to predicting a paper's field. These observations highlight the opportunity to leverage long-range dependencies by selectively utilizing effective meta-paths.Motivated by the observations mentioned above, we propose a novel method called Long-range Meta-path Search through Progressive Sampling (LMSPS). LMSPS focuses on meta-path search and aims to reduce the exponentially growing meta-paths to a subset that is specifically effective for the given dataset and task. LMSPS builds a comprehensive search space initially, including all meta-paths related to the target nodes. Then, it adopts a progressive sampling algorithm to reduce the search space. Finally, LMSPS selects the top-M meta-paths from the reduced search space based on a sampling evaluation strategy. This search stage reduces the exponential number of meta-paths to a constant for retraining. Experimental results on both real-world and manual sparse large-scale datasets demonstrate that LMSPS outperforms existing state-of-the-art methods for heterogeneous graph representation learning.Our main contributions are summarized as follows:• We propose a novel meta-path search framework termed LMSPS, which to our knowledge is the first HGNNs to utilize long-range dependency in large-scale heterogeneous graphs. • To search for effective meta-paths efficiently, we introduce a novel progressive sampling algorithm to reduce the search space dynamically and a sampling evaluation strategy for meta-path selection. • Moreover, the searched meta-paths of LMSPS can be generalized to other HGNNs to boost their performance. 
preliminaries: 
 Heterogeneous graph [43] . A heterogeneous graph is defined as G = {V, E, T , R, f T , f R } with |T +R|>2, where V denotes the set of nodes, E denotes the set of edges, T is the node-type set and R the edge-type set. Each node v i ∈ V is maped to a node type f T (v i ) ∈ T by mapping function f T : V → T . Similarly, each edge e t←s ∈ E (e ts for short) is mapped to an edge type f R (e ts ) ∈ R by mapping function f R : E → R.Meta-path [44] . A meta-path P is a composite relation that consists of multiple edge types, i.e., P ≜ c1 r12 ←-c 2 • • • c l-1 r (l-1)l←-c l (P = c 1 • • • c l for short), where c 1 , . . . , c l ∈ T and r 12 , . . . , r (l-1)l ∈ R.A meta-path P corresponds to multiple meta-path instances in the underlying heterogeneous graph. For example, meta-path APA corresponds to all paths of co-author relationships on the heterogeneous graph. Using meta-paths means selectively aggregating neighbors on the meta-path instances. 
related works: 
 Heterogeneous Graph Neural Networks. HGNNs are proposed to learn rich and diverse semantic information on heterogeneous graphs. Several HGNNs [29, 23, 34, 36] have involved high-order semantic aggregation. However, their methods are not applied to large-scale datasets due to high costs. Additionally, many HGNNs [56, 21, 48, 23] have implicitly learned meta-paths by attention. However, few work employs the discovered meta-paths to produce final results, let alone generalize them to other HGNNs to demonstrate their effectiveness. For example, GTN [56] and HGT [21] only list the discovered meta-paths. HAN [48] , HPN [23] and MEGNN [5] validate the importance of discovered meta-paths by experiments not directly associated with the learning task. GraphMSE [31] is the only work that shows the performance of the discovered meta-paths. However, they are not as effective as the full meta-path set. So, their learned meta-paths are not effective enough.Meta-structure Search on Heterogeneous Graphs. Recently, some works have attempted to utilize neural architecture search (NAS) to discover meta-structures. GEMS [15] is the first NAS method on heterogeneous graphs, which utilizes an evolutionary algorithm to search meta-graphs for recommendation tasks. DiffMG [8] searches for meta-graphs by a differentiable algorithm to conduct an efficient search. PMMM [27] performs a stable search to find meaningful meta-multigraphs. However, meta-path-based HGNNs are mainstream methods [41, 57, 48, 11] , while meta-graphbased HGNNs are specialized. So, their searched meta-graphs are extremely difficult to generalize to other HGNNs. RL-HGNN [60] proposes a reinforcement learning (RL)-based method to find meta-paths. On recommendation tasks, RMS-HRec [37] also proposes an RL-based meta-path selection strategy to discover meta-paths. Both of them are very time-consuming.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
motivation of long-range meta-path search: 
 Long-range meta-paths can complete the missing information that can not be obtained from close nodes. Take the meta-path MDMDMK (M←D←M←D←M←K) from IMDB as an example. IMDB includes four different entity types: Movies (M), Directors (D), Keywords (K), and Actors (A).The task is to predict the category of the target movies. MDMDMK is a 5-hop meta-path that is hard for experts to understand and then apply. However, for many movies without keywords, the meta-path M←D←M←D←M←K is important because the target movies can aggregate the keyword information from the movies of co-directors.In addition, SeHGNN [52] employs attention mechanisms to fuse all the target-node-related metapaths and outperforms the existing HGNNs. SeHGNN has an important observation that models with single-layer structures and long meta-paths outperform those with multi-layers and short metapaths, indicating the advantages of long-range meta-paths. However, because the number of metapaths increases exponentially with maximum hops, SeHGNN has to use a small maximum hop to save memory and reduce costs. For example, The maximum hop is 2 for large-scale datasets OGBN-MAG [20] , which is insufficient, as shown in Table 2 of the experiments. This inspires us to consider whether we can only use effective meta-paths instead of all meta-paths to reduce the consumption of large maximum hops.We analyze the importance of different meta-paths for SeHGNN on two widely-used real-world datasets DBLP and ACM from HGB [34] . All results are the average of 10 times running with different random initialization. As the number of meta-paths exponentially increases with the maximum hop, in exploratory experiments, we set the maximum hop l = 2 for ease of illustration. Then the meta-path sets are {A, AP, APA, APT, APV} on DBLP, and {P, PA, PC, PP, PAP, PCP, PPA, PPC, PPP} on ACM.In each experiment on DBLP, we remove one meta-path and compare the performance with the result of leveraging the full meta-path set to analyze the importance of the removed meta-path. As shown in Figure 1 (a), removing either A or AP or APA or APT has little impact on the final performance. However, removing APV results in severe degradation in performance, demonstrating APV is the critical meta-path on DBLP when l = 2. We further retain one meta-path and remove others as shown in Figure 1 (b). The performance of utilizing APV is only slightly degraded compared to the full meta-paths set. Consequently, we obtain the first observation: A small number of meta-paths provide major contributions. In each experiment on ACM, we remove some meta-paths to analyze their impact on the final performance. Results in Figure 1 (c) show that the performance of SeHGNN improves after removing a part of meta-paths. For example, after removing PC and PCP, the Micro-F1 scores are improved by 0.52%. So, we can conclude the second observation: Certain meta-paths can have a negative impact for heterogeneous graphs. The second observation is reasonable because heterogeneous information is not consistently beneficial for various tasks compared to homogeneous information. It is supported by the fact that various recent HGNNs [8, 27, 52] have removed some edge types to exclude corresponding heterogeneous information during pre-processing based on substantial domain expertise or empirical observations. This observation explains why most HGNNs use a maximum hop of 2, i.e., it is hard to exclude negative information under larger maximum hops. Additionally, because SeHGNN employs an attention mechanism, the performance degradation indicates the attention mechanism has limitations in dealing with noise.Although long-range meta-paths outperform short meta-paths [52] , they need a large maximum hop, resulting in exponentially increasing meta-paths. Motivated by the above two observations, unlike existing methods [5, 31, 52, 56] , we can employ effective meta-paths instead of the full meta-path set without sacrificing performance. Although the number of meta-paths grows exponentially with the maximum hop, the proportion of effective meta-paths is small, which is similar to the 80/20 rule of Pareto principle [40, 10] . To keep efficiency while trading off the performance, we choose a fixed number of meta-paths (like 30) over all datasets. Therefore, the exponential meta-paths can be reduced to a constant. Now the key point is how to find effective meta-paths. 
the proposed method: 
 The key of our LMSPS is to utilize a search stage to reduce the exponentially increased meta-paths to a subset effective to the current dataset and task. It can overcome the main challenges of utilizing long-range dependency on heterogeneous graphs. First, utilizing effective meta-paths instead of all meta-paths alleviates computational and memory costs while keeping effective heterogeneous information. Second, each target node only aggregates neighbors on the path instances of effective meta-paths. Because the proportion of effective meta-paths is small and each node has a different neighborhood condition, each target node aggregates different neighbors under the constraints of effective meta-path instances. In this way, the over-smoothing issue can also be overcome.Then, the main challenge becomes how to discover effective meta-paths, especially long-range ones.Searching for long-range meta-paths has two main challenges: the exponentially increasing issue and the noise issue. We propose a progressive sampling algorithm and a sampling evaluation strategy to respectively overcome the two challenges. Figure 2 illustrates the overall framework of LMSPS, which consists of a super-net in the search stage and a target-net in the training stage.The super-net aims to automatically discover effective meta-paths for specific datasets or tasks, so the search results should not be affected by specific modules. Based on this consideration, we develop a simple MLP-based instead of transformer-based architecture for meta-path search because the former involves fewer human interventions [45, 16, 3] . In addition, the sampling strategy keeps the parametric modules changing in the search stage, which is important for preventing the search meta-paths from being affected by specific modules. The super-net contains five blocks: neighbor aggregation, feature projection, progressive sampling search, sampling evaluation, and MLP.Let P = {P 1 , • • • , P k , • • • , P K } be the initial search space with all the K target-node-related meta-paths, X ci be the raw feature matrix of all nodes belonging to type c i , and Âci,ci+1 be the row-normalized adjacency matrix between node type c i and c i+1 . The neighbor aggregation block follows SeHGNN [52] , which employs an efficient one-time message passing to pre-process an entire heterogeneous graph into regular-shaped tensors for target nodes. Specifically, it uses the multiplication of adjacency matrices to calculate the final contribution weight of each metapath-based neighbor to targets. As shown in Figure 2 , the neighbor aggregation process of l-hop meta-path P k = c 0 c 1 c 2 . . . c l is:EQUATIONwhere X k is the feature matrices of meta-path P k , and c 0 is the target node type. Then, an MLP-based feature projection block is used to project different feature matrices into the same dimension, namely,X ′ k = MLP k (X k ).To automatically discover meaningful meta-paths for various datasets or tasks without prior, our search space contains all target-node-related meta-paths, severely challenging the efficiency and effectiveness of the search. To address the efficiency challenge, LMSPS utilizes a progressive sampling algorithm to sample meta-paths in each iteration and progressively shrink the search space.Specifically, LMSPS assigns one architecture parameter to each meta-path.Let α = {α 1 , • • • , α k , • • • , α K } ∈ R K bethe architecture parameters of K meta-paths. We use a Gumbelsoftmax [35, 9] over architecture parameters α k to calculate the strength of different meta-paths:EQUATIONwhere q k is the path strength, representing the relative importance of meta path P k . u k = -log (-log (U )) where U ∼ Uniform(0, 1), and τ is temperature controlling relaxation's extent.The progressive sampling algorithm uses the path strength to progressively narrow the search space from K to V to exclude useless meta-paths. Generally, K ≫ V under a large maximum hop. Let q C be the C-th largest path strength ofQ = {q 1 , • • • , q k , • • • , q K }.During the search stage, the search space retains all meta-paths no less than q C . The dynamic search space can be formulated as follows:EQUATION)Here C is the search space size, S C consists of the indexes of retained meta-paths, and ⌈•⌉ indicates the rounding symbol. λ ∈ [0, 1] is a parameter controlling the number of retrained meta-paths and decreases from 1 to 0 as the epoch increases.As the search stage aims to determine top-M meta-paths, we sample M meta-paths from dynamic search space in each iteration. In each iteration, only parameters on the M activated meta-paths are updated, while others remain unchanged. Therefore, the search cost is relevant to M instead of K.The forward propagation can be expressed as:EQUATIONHereq ′ k = exp [(α k + u k ) /τ ] / k∈S exp [(α j + u j ) /τ ]indicates the path strength of activated meta-paths, and UniformSample(S C , M ) indicates a set of M elements chosen randomly from set S C without replacement via a uniform distribution. The parameter update in the super-net involves a bilevel optimization problem [2, 7, 51] .EQUATIONHere L train and L val denote the training and validation loss, respectively. α is the architecture parameters calculating the path strength. ω is the network weights in MLP. Following the NAS-related works in the computer vision field [33, 50, 53] , we address this issue by first-order approximation. Specifically, we alternatively freeze architecture parameters α when training ω on the training set and freeze ω when training α on the validation set.The progressive sampling strategy can contribute to a more compact search space specifically driven by the current HIN and task, leading to a more effective meta-path discovery. Additionally, it can overcome the deep coupling issue [13] because of the randomness in each iteration.After the completion of the progressive sampling search, the search space is narrowed from K to V . Traditional methods in the computer vision field directly derive the final architecture based on the architecture parameters [33, 50, 53] . However, as different meta-paths could be noisy or redundant to each other, top-M meta-paths are not necessarily the optimal solution when their importance is calculated independently. Based on this consideration, we specially designed a novel sampling evaluation strategy by evaluating the overall performance of each meta-path set. Specifically, using path strength at the end of progressive sampling as the probability, we sample M meta-paths from the compact search space S V to evaluate their overall performance. The sampling evaluation is repeated 200 times to filter out the meta-path set with the lowest validation loss. So, we can select the best meta-path set instead of independent top-M meta-paths, which is more reasonable. This stage is not time-consuming because the evaluation does not involve weight training. This sampling process can be represented as:EQUATIONHere, DiscreteSample(S V , M, Q) indicates a set of M elements chosen from set S V without replacement via discrete probability distribution Q. Q is the set of relative path strength calculated by architecture parameters of the V meta-paths based on Equation 2. The overall search algorithm and more discussion are shown in Appendix C.Thereafter, the retained meta-path set is recorded as S M = argminS L val ( S, ω * , α * ). The forward propagation of the target-net for representation learning can be formulated as:EQUATIONHere, ∥ denotes the concatenation operation. Unlike existing HGNNs, the architecture of the targetnet does not contain neighbor attention and semantic attention. Instead, the parametric modules consist of pure MLPs. The training objective is shown in Appendix A.3.As discussed in Section 3, there have been some attempts to find meta-paths automatedly [15, 56, 60] . Three aspects highlight the differences between LMSPS and existing methods. 1) Large-scale dataset: LMSPS is the first HGNN that makes it possible to achieve automated meta-path selection for large-scale heterogeneous graph node property prediction. 2) Long-range dependency: LMSPS is  
experiments and analysis: 
 This section evaluates the benefits of our method against state-of-the-art models on nine heterogeneous datasets. We aim to answer the following questions: Q1. How does LMSPS perform compared with state-of-the-art baselines? Q2. Can LMSPS overcome the over-smoothing and noise issues? Q3. Are the search algorithm and searched meta-paths effective? Q4. Does LMSPS perform better on sparser heterogeneous graphs?We evaluate LMSPS on several representative heterogeneous graph datasets, including DBLP, IMDB, ACM, and Freebase from HGB benchmark [34] , and the large-scale dataset OGBN-MAG from OGB challenge [20] . The statistics of the datasets are listed in Table 7 . The details about all datasets, baselines, and experiment settings are recorded in Appendix A and B.To answer Q1, we report the performance of our approaches and baselines in Table 1 . Random means the result of replacing our searched meta-paths with 30 random meta-paths. We show the average result of 20 random samples. Based on the results, we have the following observations. First, LMSPS outperforms all baselines for different metrics on almost all datasets except Micro-F1 scores on Freebase, sometimes by a significant margin, which validates the power of LMSPS. For example, on the largest dataset OGBN-MAG, LMSPS achieves 54.83% test accuracy, while the best competitor has 51.45% test accuracy. Second, all metapath-free methods encounter out-of-memory (OOM) issues when dealing with large datasets, including highly competitive methods, HINormer and SlotGAT, indicating the advantage of employing meta-paths electively aggregating neighbors on the meta-path instances. Third, although LMSPS is an MLP-based method, the pure MLP method [19] has the worst performance with only 26.92% test accuracy on OGBN-MAG, validating the advantages of pre-processing and meta-path search. Finally, LMSPS outperforms Random significantly, further indicating the importance of meta-path search. More comparisons with top method combinations on OGBN-MAG are shown in Table 10 of Appendix E.2, in which LMSPS also shows the best performance.To answer Q2, we conduct experiments to compare the performance, memory, and efficiency of LMSPS with the method of HGB benchmark, Simple-HGN [34] , and the best metapath-based method, SeHGNN [52] , on DBLP. Figure 3 (a) shows that LMSPS has consistent performance with the increment of maximum hop. The failure of Simple-HGN demonstrates its attention mechanism can not overcome the over-smoothing issue or eliminate the effects of noise under large hop. Figure 3 (b), (c) illustrate each training epoch's average memory and time costs relative to the maximum hop or layer. We can observe that the consumption of SeHGNN exponentially grows, and the consumption of Simple-HGN linearly increases, which is consistent with their time complexity as listed in Table 8 . Meanwhile, LMSPS has almost constant consumption as the maximum hop grows. Figure 3 (c) shows the time cost of LMSPS in the search stage, which also approximates a constant when the number of meta-paths is larger than M = 30. More results about efficiency are shown in Figure 4 of Appendix E.1.We also compare the performance and training time of LMSPS with SeHGNN under different maximum hops on large-scale dataset OGBN-MAG. When the maximum hop l = 1, 2, 3, we utilize the full meta-path set because the number of meta-paths is smaller than M = 30. Following the convention [34, 52] , we measure the average time consumption of one epoch for each model. As shown in Table 2 , the performance of LMSPS keeps increasing as the maximum hop value grows. It indicates that LMSPS can overcome the issues caused by utilizing long-range dependency, e.g., over-smoothing and noise. In addition, when the number of meta-paths is larger than 30, the training time of LMSPS is stable under different maximum hops.To answer Q3, we first explore the effectiveness of our search algorithm. In our architecture, our meta-paths are replaced by those meta-paths discovered by other methods. DARTS [32] is the first differentiable search algorithm in neural networks. SPOS [13] is a classic singe-path differentiable algorithm. DARTS and SPOS aim to search operations, like 3 × 3 convolution, in CNNs. DiffMG [8] and PMMM [27] search for meta-graphs instead of meta-paths. We ignore these differences and focus on the algorithms. The derivation strategies of the four methods are unsuitable for discovering multiple meta-paths. So we changed their derivation strategies to ours to improve their performance. we report the Micro-F1 scores in Table 3 . The performance of LMSPS verifies the effectiveness of our search algorithm.To demonstrate the effectiveness of searched meta-paths, on the one hand, the meta-paths should be effective in the proposed model. On the other hand, the effective meta-paths mainly depend on the dataset instead of the architecture, so the meta-paths should be effective after being generalized to other HGNNs. Because finding meta-paths that work effectively across various HGNNs is a tough task, it has not been achieved by previous works. We verify the generalization of our searched metapath on the most famous HGNN, HAN [48] , and the SOTA metapath-based method SeHGNN [52] .The Micro-F1 scores on three representative datasets are shown in Table 4 . After simply replacing the original meta-path set with our searched meta-paths and keeping other settings unchanged, the performance both improve, demonstrating the effectiveness of our searched meta-paths. In addition, we have shown the interpretability of searched meta-paths in Appendix D.To answer Q4 and explore the necessity of long-range dependency on heterogeneous graphs, we construct four large-scale datasets with high sparsity based on OGBN-MAG. To avoid inappropriate preference seed settings of randomly removing, we construct fixed heterogeneous graphs by limiting the maximum in-degree related to edge type. Specifically, we gradually reduce the maximum indegree related to edge type in OGBN-MAG from 50 to 5 but leave all nodes unchanged. Details of the four datasets are listed in Appendix A. The test accuracy of LMSPS and SOTA method SeHGNN are shown in Table 5 . LMSPS outperforms SeHGNN more significantly with the increasing sparsity. In addition, the leading gap of LMSPS over SeHGNN is more than 4.7% on the highly sparse dataset OGBN-MAG-5. The main difference between SeHGNN and LMSPS is that the former cannot utilize large hops and only use hop 2 while the latter has a maximum hop of 6, demonstrating that long-range dependencies are more effective with decreased direct neighbors on heterogeneous graphs.Two components differentiate our LMSPS from other HGNNs: the search algorithm and semantic fusion without attention. The search algorithm consists of a progressive sampling algorithm and a sampling evaluation strategy. We explore how each of them improves performance through ablation studies under the same settings as the main experiments in Table 1 . As shown in Table 6 , the performance of LMSPS significantly decreases when removing progressive sampling or sampling evaluation strategy. In addition, employing a transformer block for semantic attention on all metapaths shows slightly worse performance even if using many more meta-paths and is out-of-memory on larger datasets, indicating that the transformer cannot eliminate the negative effects of noise. It is reasonable because attention values are calculated based on softmax and are positive even for noise. 
conclusion: 
 This work presented a novel approach, the Long-range Meta-path Search through Progressive Sampling (LMSPS), to tackle the challenges of leveraging long-range dependencies in large-scale heterogeneous graphs, i.e., reducing computational costs while effectively utilizing information and addressing the over-smoothing issue. Based on our two observations, i.e., a few meta-paths dominate the performance, and certain meta-paths can have negative impact on performance, LMSPS introduced a progressive sampling search algorithm and a sampling evaluation strategy to automatically identify effective meta-paths, hence reducing the exponentially growing number of meta-paths to a manageable constant. Extensive experiments demonstrated the superiority of LMSPS over existing methods, particularly on sparse heterogeneous graphs that require long-range dependencies. By employing simple MLPs and complex meta-paths, LMSPS offers a novel direction that emphasizes datadependent semantic relationships rather than relying solely on sophisticated neural architectures. The reproducibility and limitations are discussed in Appendix F and Appendix G, respectively. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We have provided that the computation resource is one Tesla V100 GPU with 16GB GPU memory.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Our work is specific to machine learning for heterogeneous graph node classification; therefore, it has limited possibility for a wide societal impact.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Similarly, our work is specific to machine learning for heterogeneous graph node classification.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: All the data can be found publicly, and the code we provided has no constraints.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: The URL of our code provides a detailed README to reproduce our results.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.• We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In the Appendix, we provide additional details and results not included in the main text due to space limitations. First, we provide the details of datasets, tasks, baselines, and parameter settings for our experiments. Secondly, we show the search algorithm of LMSPS and conduct theoretical analysis about the reasonableness of sampling search and analyze the time complexity. Thirdly, for interpretability, the searched meta-paths are listed and analyzed. Fourthly, we explore the training efficiency and search convergence of LMSPS and compare LMSPS with top method combinations on OGBN-MAG leaderboard. Hyperparameter studies are also conducted. Finally, we discuss the reproducibility and limitations of our research work.We evaluate our method on four widely-used heterogeneous graphs including DBLP, IMDB, ACM, and Freebase from HGB benchmark [34] and the famous large-scale dataset OGBN-MAG from OGB challenge [20] . The datasets from HGB follow a transductive setting, where all edges are available during training, and target type nodes are divided into 24% for training, 6% for validation, and 70% for testing. For the OGBN-MAG dataset, we use the official data partition, where papers published before 2018, in 2018, and since 2019 are nodes for training, validation, and testing, respectively.In addition, we construct four sparse datasets to evaluate the performance of LMSPS by reducing the maximum in-degree related to edge type in OGBN-MAG. The four sparse datasets have the same number of nodes with OGBN-MAG. Follow the convention [34, 52, 36] , we show the details of all datasets in Table 7 .Following the convention [34, 27, 52, 36] , we concentrate on semi-supervised node classification under the transductive setting and leave other downstream tasks related to heterogeneous graph representation learning as future work. Each dataset contains a target node type, and our task is to learn to predict the labels of vertices of this target node type. All the datasets provide fixed data splitting (into training, validation, and test sets) for node classification tasks.An MLP layer is appended after the main module of LMSPS, which reduces the dimension of node-level representations of a heterogeneous graph to the number of classes:EQUATIONwhere ω o ∈ R do×N is the output weight matrix, d o is the dimension of output node representations, and N is the number of classes. Then, the cross-entropy loss is used over all labeled nodes: where V L denotes the set of labeled nodes, y v is a one-hot vector indicating the label of node v, and ȳv is the predicted label for the corresponding node in Ȳ . In the search stage, V L is the training set when updating ω and the validation set when updating α. In the training stage, V L is the training set, and ω is reinitialized and trained.EQUATIONWe compare LMSPS with a large number of HGNN baselines, including MLP [19] , GraphSAGE [14] , RGCN [41] , HAN [48] , GTN [56] , RSHN [63] , HetGNN [57] , MAGNN [11] , HetSANN [18] , GCN [26] , GAT [46] , , Simple-HGN [34] , HGT [21] , GraphMSE [31] , SlotGAT [62] , DiffMG [8] , PMMM [27] , HINormer [36] , NARS [55] , space4HGNN [59] , SeHGNN [52] . GEMS [15] and RMS-HRec [37] are ignored because they are designed for recommendation tasks. RL-HGNN [60] is omitted due to a lack of source code.Note that most of these baselines encounter out-of-memory (OOM) issues when dealing with large datasets. However, there are exceptions among them, including MLP, GraphSAGE, HGT, RGCN, NARS, and SeHGNN. The results of MLP and GraphSAGE come from the OGBN-MAG leaderboard. MLP [19] is famous for its lightweight and GraphSAGE [14] uses a neighbor sampling strategy, so they can handle large-scale datasets. HGT is designed with a graph sampling strategy, making it well-suited for managing large datasets. As for RGCN, while the original version does present OOM issues with large datasets, it is often used as a baseline for large-scale HGNNs [55] . NARS [55] and SeHGNN [52] are metapath-based and pre-computation-based HGNNs, allowing them to handle large-scale datasets.It's worth noting that in the original paper, SeHGNN refers to the full version incorporating label propagation techniques. For clarity and consistency in our study, we have adjusted the terminology: we refer to the version without label propagation as SeHGNN and the version with label propagation as SeHGNN+LP. Note that label propagation is a general technique [64, 61, 22 ] that is compatible with most GNNs and is not used in the results of LMSPS and all other baselines in Table 1 . Therefore, it is considered only in Appendix E.2, where we demonstrate the successful integration of our model with other techniques.For training, we follow the settings of the HGB benchmark [34] and utilize the performance improvement on the validation set as a guide to determine whether the model has been improved. Specifically, if we observe a performance boost on the validation set during training, we update the final model parameters accordingly. Additionally, we adopt the early stopping strategy employed by the HGB benchmark: if no performance improvement on the validation set is observed within a specific count (referred to as patience), the training will be stopped early before reaching the maximum epochs. This approach helps prevent overfitting while also enhancing the computational efficiency of our model training. Following the setting of HGB [34] and OGB [20] , we train our model 5 times for HGB and 10 times for OGB with different random seeds and report the mean performance and standard deviation, respectively. We use Pytorch [38] to run all experiments on one Tesla V100 GPU with 16GB GPU memory.For models such as RGCN, HAN, GTN, RSHN, HetGNN, MAGNN, HetSANN, HGT, GCN, GAT, Simple-HGN, and SeHGNN, the literature [34, 52] provides tuned parameter settings along with corresponding performance on small datasets, namely DBLP, IMDB, ACM, and Freebase. Therefore, we utilize these tuned parameter settings for these models on small datasets and utilize the reported performance.Conversely, in cases where official results are unavailable (such as NARS on small datasets), or where the experimental settings differ, we employ the official or benchmark implementations 3 4 5 6 7 8 9 10 11 of the baseline models. We meticulously fine-tune their hyperparameters to the best of our capabilities. In instances involving hyperparameter analysis, such as in Figure 3 , we only modify the relevant hyperparameters to ensure a fair comparison.We set the number of selected meta-paths M = 30 for all datasets. The final search space V = 60.The maximum hop is 6 for ogbn-mag, DBLP, 5 for IMDB, ACM, and 3 for Freebase. All K architecture parameters α 1 , α 2 , • • • , α K are initialized as 1s. For searching in the super-net, we train for 200 epochs. To train the target-net, we use an early stop mechanism based on the validation performance to promise full training. A two-layer MLP is adopted for each meta-path in the feature projection step, and the hidden size is 512. All network weights are initialized by the Xavier uniform distribution [12] and are optimized with Adam [25] during training. In the search stage, λ is 1 during the first 20 epochs for warmup and decreases to 0 linearly. τ linearly decays with the number of epochs from 8 to 4. The learning rate is 0.001 for all search stages and HGB training stage, and 0.003 for OGBN-MAG training stage. The weight decay is always 0. For the initial search space, we simply preset the maximum hop and use all target-node-related meta-paths no more than this maximum hop.To assess the performance of the models, we employ evaluation metrics consistent with those employed in baseline models. The metrics are chosen as follows. For small datasets, DBLP, IMDB, ACM, and Freebase, we adhere to the evaluation standards established by the HGB benchmark [34] .The metrics reported for these datasets are Macro-F1 and Micro-F1 scores, which evaluate the classification performance. For the OGBN-MAG dataset, evaluation follows the methodology outlined in NARS [55] and SeHGNN [52] , where the classification accuracy score is reported for this dataset.Our search stage aims to discover the most effective meta-path set from all target-node-related meta-paths, severely challenging the efficiency of searching. Take OGBN-MAG as an example. The number of target-node-related meta-paths K is 226 under the maximum hop 6, and we need to find the most effective meta-path set with size 30. Because different meta-paths could be noisy or redundant to each other, top-30 meta-paths are not necessarily the optimal solution when their importance is calculated independently. Therefore, the total number of possible meta-path sets is C 30 226 ≈ 10 37 . Such a large search space is hard to solve efficiently by traditional RL-based algorithms [60, 37] or evolution-based algorithms [49, 39] .To overcome this challenge, our LMSPS first uses a progressive sample algorithm to shrink the search space size from 226 to 60, then utilizes a sampling evaluation strategy to discover the best meta-path set with the lowest validation loss, which is more effective than architecture parameters [47] . In each iteration, we only uniformly sample meta-paths M from the whole search space for parameter updates, so the search cost is relevant to M , which is a predefined small number, rather than K. Calculate the path strength of all meta-paths based on Equation 26: O(N (rd) l F 2 ) O(N (rd) l F ) O(N r l F 2 ) O(N (rd) l F 2 ) Simple-HGN O(N (rd) l F 2 ) O(N (rd) l F ) - O(N (rd) l F 2 ) Simple-HGN † O(N rdlF 2 ) O(N rdlF ) - O(N rdlF 2 ) SeHGNN O(N r l F 2 ) - O(N r l F 2 + N r 2l F ) O(N (r l F 2 + r 2l F )) LMSPS-search O(N M F 2 ) - O(N M F 2 ) O(N M F 2 ) LMSPS-train O(N M F 2 ) - O(N M F 2 ) O(N M F 2 )Lemma C.1. Let m represent the maximum number of activatable paths, and assume each pair of operations satisfies the zero-order condition. We can approximate all 2 m combinations using m types of expectations and variances.Lemma C.1 assures us that we can approximate all 2 m combinations by multiple times sampling. The proof is given as follows.Let y py(y) = f (x), z pz(z) = g(x), x ∼ p x (x). For the case m = 1, the expectation of y and z can be written respectively as:EQUATIONAccording to the zero-order condition, we have f (x) ≈ g(x). And p(x) is same for both y and z, soE[y] ≈ E[z]. Now we prove V ar[y] ≈ V ar[z]. Note that V ar[y] = E y 2 -(E[y]) 2 and V ar[z] = E z 2 - (E[z])2 , thus we only need to prove E y 2 ≈ E z 2 . It can be similarly proved as follows:EQUATIONAccording to the zero-order condition, we haveV ar[y] ≈ V ar[z].For the case of m = 2, when the two paths are both selected, the output becomes y +z, its expectation can be written as:EQUATIONAnd the variance of y + z is,EQUATION) Therefore, there are two kinds of expectations and variances: E[y] and V ar[y] for {y, z}, and 2E[y] and 4V ar[y] for {y + z}. Similarly, in the case where m ∈ [1, n], there will be m kinds of expectations and variances.Following the convention [6, 52] , we compare the time complexity of LMSPS with HAN [48] , Simple-HGN [34] , and SeHGNN [52] under mini-batch training with the total N target nodes. All methods employ l-hop neighborhood. For simplicity, we assume that the number of features is fixed to F for all layers. The average degree of each node is rd, where r is the number of edge types and d is the number of edges connected to the node for each edge type. The complexity analysis is 8 . Because HAN and Simple-HGN require neighbor aggregation during training, and the number of neighbors grows exponentially with hops. So, they have neighbor aggregation costs of O((rd) l ). SeHGNN employs a pre-processing step to avoid the training cost of neighbor aggregation. However, the exponential meta-paths cause SeHGNN to suffer from O(r l ) costs in semantic aggregation. Unlike the above methods, LMSPS samples M meta-paths in each iteration of the search stage and employs M effective meta-paths in the training stage to avoid exponential costs. Generally, we have O((rd) l ) ≫ O(r l ) = O(K) ≫ O(M ) when maximum hop l is large. The time complexity of LMSPS is a constant when N and F are determined, which is the key point for utilizing long-range meta-paths.We have conducted an extensive experimental study to validate the effectiveness of our searched meta-paths in the main text. Here, we illustrate the searched meta-paths of each dataset in Table 9 . Because we discover many more meta-paths than traditional methods and most meta-paths are longer than traditional meta-paths, it is tough to interpret them one by one. So, we focus on the interpretability of meta-paths on large-scale obgn-mag dataset from the Open Graph Benchmark. The OGBN-MAG dataset is a heterogeneous graph composed of a subset of the Microsoft Academic Graph. It includes four different entity types: Papers (P), Authors (A), Institutions (I), and Fields of study (F), as well as four different directed relation types: Author --------→Field . The target node is the paper, and the task is to predict each paper's venue (conference or journal).Based on Table 9 , the hop of effective meta-paths on obgn-mag ranges from 1 to 6, which means utilizing information from neighbors at different distances is important. Because long-range metapaths provide larger receptive fields, LMSPS shows stronger capability in utilizing heterogeneity compared to traditional metapath-based HGNNs. The source node type of 16 meta-paths is P, e.g., PFPFP (P←F←P←F←P). It indicates that the neighborhood papers of the target paper are most significant for predicting its venue, which is consistent with reality: the citation relationship, co-author relationship, and co-topic relationship between papers are usually the most effective information. 12 meta-paths' source node type is F. It implies that the neighborhood fields of the target paper are also crucial in determining its venue, which is also consistent with reality. Because most conferences or journals focus on a few fixed fields, a paper's venue is highly related to its field. The source node type of 2 meta-paths is I. It means the neighborhood institution is not very important for predicting the paper's venue, which is reasonable because almost all institutions have a wide range of conference or journal options for publishing papers. No meta-path has source node type A. It means the neighborhood author is unimportant in determining the paper's venue, which is logical because each paper has multiple authors, and each author can consider different venues. So, it is difficult to determine the paper's venue based on its neighborhood authors. If using too much institution or author information to predict the paper's venue, it actually introduces much useless information, which can be viewed as a kind of noise in obgn-mag for predicting each paper's venue. GTN has a large time consumption and parameters. We ignore it for ease of illustration. We also provide some simple insights from the searced meta-paths of DBLP, IMDB, and ACM.In DBLP with target node type Author, the information from P (Paper) and A (Author) is slightly more important than that from T (Term) and V (Venue). In IMDB with target node type Movie, the importance of information of K (Keyword), M (Movie), A (Actor) and D (Director) gradually decreases. In ACM with target node type Paper, the importance of information of P (Paper), A (Author) and C (Conference) gradually decreases. For all datasets, the importance of node type is highly related to the target node type.In addition, the hand-crafted meta-paths rely on intense expert knowledge, which is both laborious and data-dependent. In contrast, automatic meta-path search frees researchers from the understandthen-apply paradigm. In Table 9 , LMSPS can search effective meta-paths without prior knowledge for various datasets, which is more valuable than manually-defined meta-paths.Following the convention [34, 52] , we show the time cost and parameters of LMSPS and the advanced baselines on DBLP and ACM in Figure 4 . We measure the average time consumption of one epoch for each model. The area of the circles represents the parameters. The hidden size is set to 512 and the maximum hop or layer is 6 for DBLP and 5 for ACM for all methods to test the training time and parameters under the same setting. Some methods perform quite poorly under the large maximum hop or layer. So we show the performance from Table 1 of the main text, which is the results under their best settings. Figure 4 shows that LMSPS has advantages in both training efficiency and performance. Our searched meta-paths are universal after searching once and can be applied to other metapath-based HGNNs based on Table 4 . Because other metapath-based HGNNs don't include the time for discovering manual meta-paths, we also exclude our search time for discovering meta-paths in Figure 4 . The search time is shown in Figure 3 (c) of the main text.The OGBN-MAG benchmark dataset is associated with a public leaderboard. In Table 10 , we compare our method combination against top-performing approaches (method combinations) on the leaderboard. These methods integrate several general techniques, such as Label Propagation As the search stage of LMSPS relies on sampling, we conduct experiments to explore the convergence of the search stage. Because the test set is unavailable in the search stage to avoid label leakage, we show the Micro-F1 scores of the validation set of DBLP, IMDB, ACM, Freebase and test accuracy of the validation set of OGBN-MAG under different searching epochs in Table 11 . As we can see, LMSPS coverages during 100 to 180 epochs for all datasets. The main reason is that the search space size is progressively shrunk from K to 2M under the progressive sampling algorithm. Most negative meta-paths have been removed from the search space in the second half of the search stage.LMSPS randomly samples M meta-paths at each epoch in the search stage and selects the top-M meta-paths in the training stage. Here, we perform analysis on hyper-parameter M on DBLP, IMDB, and ACM. Freebase and OGBN-MAG are ignored because they are relatively large and the experiments are time-consuming. As illustrated in Figure 5 , the performance of LMSPS increases with the growth of M when M is small. In addition, the performance on DBLP and ACM slightly decreases when M is larger than a certain threshold, indicating excessive meta-paths don't benefit performance for some datasets. For unity, we set M = 30 for all datasets.To observe the impact of different maximum hop values, we show the Micro-F1 of LMSPS with respect to different maximum hop values on DBLP, IMDB, and ACM in Figure 6 . We can see LM-SPS show the best performance when the maximum hop is 5 or 6. Additionally, the performance of LMSPS does not always increase with the value of the maximum hop, and the best maximum hop depends on the dataset.We have provided the details of datasets, tasks, baselines, and parameter settings in Appendix A and B and conducted the hyperparameter study in Appendix E. 4 . All reported results are the average of multiple experiments with standard deviations. We have included a pseudocode description of our method in Appendix C. The source code has been provided through an anonymized URL with clear commands on reproducing our results.It is noteworthy that the performance of LMSPS does not always increase with the value of the maximum hop. For instance, based on Figure 3 (a), LMSPS can effectively utilize 12-hop meta-paths on DBLP with high performance and low cost. However, the optimal performance for LMSPS is observed when the maximum hop is 6. It can be attributed to the constraint of maintaining constant time complexity by setting the number of searched meta-paths to 30 for different maximum hop values. When the maximum hop value is 12, the number of target-node-related meta-paths exceeds 1400 (Figure 3 (a)). Searching for 30 effective meta-paths from such an extensive search space is notably challenging, despite LMSPS being the most effective method for meta-path search (as indicated in Table 3 ). The benefits of using longer meta-paths are outweighed by the drawbacks of the significantly more complex search space. So, the best maximum hop depends on the dataset and task and cannot be determined automatically.Nevertheless, based on Table 8 , the time complexity of LMSPS does not increase with the maximum hop. Consequently, it provides an effective solution for utilizing long-range dependency on heterogeneous graphs for possible applications on sparser real-world datasets. In Table 5 , we conduct experiments on four constructed datasets based on OGBN-MAG to demonstrate that the advantages of utilizing long-range dependencies are more obvious for sparser large-scale heterogeneous graphs.For the constructed datasets, we carefully avoid inappropriate preference seed settings of randomly removing by limiting the maximum in-degree related to edge type. We expect sparser large-scale real heterogeneous datasets or more suitable tasks requiring long-range dependency to emerge in the future so we can fully explore our approach.NeurIPS Paper Checklist Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Justification: We have read.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: This paper shows that a small number of meta paths are important for the performance, whereas certain meta-paths can negatively impact it. In light of this, the paper proposes an approach that makes meta path selection via a sampling evaluation strategy. Most reviewers recognize that this paper is well-written, the experiments are strong, and the results are useful. The authors should carefully address all the concerns of the reviewers.

Reviews: review: paper_summary: paper_summary: This paper presents an empirical study demonstrating that not all meta-paths are useful; some even negatively impact performance. Selecting the most meaningful meta-paths is crucial. The authors propose LMSPS, a super-net-based method to select beneficial meta-paths effectively.
strength_weakness: strength_weakness: W1. The paper's title is misleading. According to the title, the work seems to search for meaningful long-range meta-paths only to improve the performance of HIN representation learning. However, I think the major idea is to select effective meta-paths efficiently to overcome the issue of the exponential increase in the number of meta-paths. As shown in Table 9, some short meta-paths are still important. This work is actually a meta-path selection task in my point of view.

W2. The motivation of SeHGNN is that "models with a single-layer structure and long meta-paths outperform those with multi-layers and short meta-paths". I think it does not mean that long-range meta-paths are more important than short paths. I agree that different meta-paths have different importance. But is the length of the paths the main reason for this? As analyzed in the Limitation section, although the maximum hop is set to 12, the best performance is achieved at 6. Some early studies claimed that long paths can introduce noise and less relevant connections between nodes, leading to less accurate or meaningful representations. 

W3. For most datasets, the improvement is marginal compared to the second-best performance. The enhancement brought by the selected meta-paths is not significant enough according to the experimental results.
questions: questions: 1. Please refer to the aforementioned weaknesses.
2. In OGB, I can see that LMSPS achieved the 3rd place. Have you tried to compare with the first two methods?
limitations: limitations: Limitations are sufficiently stated in the appendix. To my knowledge, there is no negative societal impact of this work.
paper_summary: paper_summary: The paper proposes a new framework called Long-range Meta-path Search through Progressive Sampling (LMSPS), which differs from traditional meta-path-based GNN training methods on heterogeneous graphs. LMSPS introduces a strategy for building a search space that includes all meta-paths related to the target node type and employs a sampling evaluation strategy to conduct specialized and effective meta-path selection.
The authors studied two new observations: a) A small number of meta-paths dominate the performance, b) Certain meta-paths can have a negative impact on performance.
They designed the LMSPS framework with a super-net in the search stage and a target-net in the training stage to mitigate costs and the over-smoothing problem that occurs in recent Heterogeneous Graph Neural Networks.
In conclusion, the paper presents a new framework that could help us better understand the challenges of leveraging long-range dependencies in large-scale heterogeneous graphs.
strength_weakness: strength_weakness: * Even though the observations are interesting, I think the paper could do more to explore their implications for robust generalization. What does robust generalization to other classes imply or reveal about the process of long-range meta-path GNN training? The reduction of meta-path samples is effective. The authors clarify that the optimal maximum hop depends on the dataset and task, as mentioned in Appendix G, and cannot be determined automatically. Thus, will the sampling search impact the model's robustness? 
* The evaluation results observed in Figure 1(a) and (b) cannot demonstrate the improvement in performance upon the removal of certain meta-paths. This raises the question of whether the observation that "certain meta-paths can have a negative impact on performance" is generally applicable. The second observation from Figure(c) is derived from the ACM dataset. Will this observation be valid for other heterogeneous graphs?
* What is the cost of the pre-processing stage? Can it be reduced by sampling to decrease the neighbor aggregation costs?
* Line 172 clarifies that MLP requires less human intervention compared to Transformer. Are there specific experiments demonstrating the superiority of MLP?
questions: questions: Please see the weakness section.
limitations: limitations: The authors have adequately addressed the limitations of their work.
paper_summary: paper_summary: The paper proposes a novel framework LMSPS, aimed at efficiently utilizing long-range dependencies in large-scale HIN. The framework addresses two primary challenges: reducing computational costs while maximizing information utilization and overcoming the over-smoothing problem common in GNNs. LMSPS employs a progressive sampling algorithm to dynamically reduce the search space for meta-paths, thus identifying a subset of effective meta-paths tailored to the specific dataset and task.
strength_weakness: strength_weakness: 1. I still have some doubts about the necessity of modeling long-range dependencies in heterogeneous graphs. For example, in an academic network, the label of a paper can be well predicted by relying on some very close nodes. Could the authors provide an example to illustrate specific situations where long-range dependency is crucial?
2. Although the paper compares LMSPS with various baselines, more detailed ablation studies focusing on the individual components of LMSPS would strengthen the validation of its effectiveness.
questions: questions: See W1.
limitations: limitations: NA.
paper_summary: paper_summary: This paper proposes an efficient meta-path search method on large-scale heterogeneous graphs. The proposed progressive sampling strategy and sampling evaluation strategy is effective for reducing the memory and time overhead, especially when the maximum hop is large. Experimental results show the effectiveness and efficiency of the proposed method.
strength_weakness: strength_weakness: 1. This novelty of this paper is limited. 
2. The paper lacks a theoretical analysis about why the sampling strategy in the search stage is valid. 
3. Experimental results on more large-scale graph datasets should be conducted.
questions: questions: 1. The differentiable search strategy is widely used in many automated graph learning tasks, such as DiffMG. There is no significant contribution in the search strategy other than the progressive sampling method. Moreover, the proposed sampling method is simply based on path strength. Similarly, the proposed sampling evaluation that uses multiple sampling to select top-$M$ meta-paths is also straightforward. Overall, the major concern about this paper is the limited novelty, although the experimental results seem good.

2. Why the simple progressive sampling method is effective? The authors should add a theoretical analysis about the effectiveness. For example, is it possible to filter out the promising meta-paths especially in the early stage of the search process? 

3. The paper aims to achieve the meta-path search on large-scale datasets. However, only one large-scale dataset (i.e., OGBN-MAG) is employed. It is suggested to add more large-scale datasets to evaluate the effectiveness of the proposed method.

4. More experimental analysis should focus on large-scale datasets, such as the performance and efficiency analysis in Figure 3. 

5. The interpretability meta-paths searched by LMSPS should be explained in detail. Many searched meta-paths seem strange and unreasonable. For example, PPPPPP in ACM, PPPAIAI in OGBN-MAG. The semantics of these meta-paths is hard to understand.

6. It is suggested to analyze all searched meta-paths in-depth and give more insights about how to choose suitable meta-paths manually.

7. Many hyperparameters need to be tuned on each dataset, such as the search space size $C$, the number of sampled meta-paths $M$, and the maximum hops.
limitations: limitations: NA

Comments: title: Thank you for the detailed response!
Looking forward to your response
Theoretical analysis about the reasonableness of sampling search
Thank you for the detailed response!
Response to the rebuttal
comment: Thank you very much for the detailed response. In the following, we respond to your concerns point by point.

### W1: How do the discovered long-range meta-paths benefit performance? The methodology seems to lack specific techniques for searching meaningful "long-range" meta-paths.

**R1:** Thank you for the insightful question. In the global rebuttal "For the importance of long-range meta-paths," we have provided a detailed example to show the ability of long-range dependencies to complete the missing information that can not be obtained from close nodes. Also, as shown in Table 2 in Section 6.3 (also shown below for quick check),  the performance of LMSPS keeps increasing as the maximum hop value grows, which means gradually adding longer meta-paths. It indicates that LMSPS can overcome the issues caused by utilizing long-range dependency, e.g., over-smoothing and noise. Moreover, as shown in Table 4 of Section 6.4, the discovered meta-path can also benefit SeHGNN.

Searching for long-range meta-paths has two main challenges: the exponentially increasing issue and the noise issue. To overcome both issues, as described in Lines 157-169, we propose a progressive sampling algorithm and a sampling evaluation strategy to overcome the two challenges, respectively. Specifically, the high-efficiency progressive sampling algorithm ensures LMSPS can search effective short and long-range meta-paths under a large maximum hop. As different meta-paths could be noisy or redundant to each other, top-M meta-paths are not necessarily the optimal solution when their importance is calculated independently. The sampling evaluation strategy evaluates the overall performance of each meta-path set. So, it can overcome the noise issue. 

| Max hop | Num path |  SeHGNN (Time / Test Acc (%))  |    LMSPS (Time / Test Acc(%))     |
| :-----: | :------: | :------------------------: | :----------------------------: |
|    1    |    4     | 4.35   /   47.18  |   3.98   /   46.88    |
|    2    |    10    | 6.44   /   51.79  |   5.63   /   51.91    |
|    3    |    23    | 11.28   /   52.44 |   10.02   /   52.72   |
|    4    |    50    |            OOM             |   14.34   /   53.43   |
|    5    |   107    |            OOM             |   14.77   /   53.90   |
|    6    |   226    |            OOM             | 14.71   /   **54.83** |

---

### **W2.1: If this setting is changed to a limited number of meta-paths, SeHGNN could be efficient due to its simplified attention mechanism.**

**R2.1:** Thank you for the insightful comment. Based on our second observation, i.e., certain meta-paths can have a negative impact on heterogeneous graphs; the attention mechanism has limitations in dealing with negative meta-paths. As described in Lines 142-144, the second observation is supported by the fact that various recent HGNNs have removed some edge types to exclude corresponding heterogeneous information during the pre-processing stage. For example, SeHGNN removes all edge types related to node type F (Field) in the ACM dataset. If simplified attention can handle negative meta-paths, this step is unnecessary. On the contrary, by meta-path search, LMSPS can easily drop out negative meta-paths. Table 2 supports this conclusion. When the maximum hop is 3, LMSPS outperforms SeHGNN by 0.28%, even the latter using more meta-paths. 



---



### **W2.2: The experiments should give more discussions about the quality of the discovered meta-paths.** 

**R2.2:**  As described in Lines 310-319, to demonstrate the high quality of searched meta-paths, on the one hand, the meta-paths should be effective in the proposed model. On the other hand, the effective meta-paths mainly depend on the dataset instead of the architecture, so the meta-paths should be effective after being generalized to other HGNNs. Based on the results in Tables 1,2,3,5, using the search meta-paths, LMSPS outperforms the other baselines on almost all conditions, sometimes significantly, which can validate the high quality of the discovered meta-paths on the proposed model. 

Because finding meta-paths that work effectively across various HGNNs is a tough task, it has not been achieved by previous works. However, based on Table 4 (also shown below for quick check), After simply replacing the original meta-path set with our searched meta-paths and keeping other settings unchanged, the performance of HAN and SeHGNN both improve, demonstrating the effectiveness of our searched meta-paths. Thank you very much!

| Method       | DBLP           | IMDB           | ACM            | Freebase       |
| ------------ | -------------- | -------------- | -------------- | -------------- |
| HAN          | 92.05 | 64.63 | 90.79 | 54.77 |
| HAN-LMSPS    | 93.54 | 65.89 | 92.28 | 57.13 |
| SeHGNN       | 95.24 | 68.21 | 93.87 | 63.41 |
| SeHGNN-LMSPS | 95.57 | 68.59 | 94.46 | 65.37 |

---

Thank you once more for your efforts. Please kindly let us know if our response has addressed your concerns.
Thank you for the detailed response. I am sorry for providing my feedback late.

W3 and W4 have been addressed satisfactorily. Below are more comments regarding W1 and W2.

W1: My further concern is that there is no analysis of how the discovered long-range meta-paths benefit performance. It would be interesting to see some discussions about the impact of the discovered long-range meta-paths on performance improvement. Additionally, the methodology seems to lack specific techniques for searching meaningful "long-range" meta-paths. It mainly focuses on utilizing a super-net to discover "useful" meta-paths. The novelty of this part seems marginal.

W2: I think SeHGNN is primarily designed for efficient heterogeneous graph learning rather than discovering useful meta-paths. It cannot handle long-hop meta-paths due to the setting of enumerating all possible meta-paths. If this setting is changed to a limited number of meta-paths, SeHGNN could be efficient due to its simplified attention mechanism. Again, since the motivation of this work is to efficiently select the most effective meta-paths, the experiments should give more discussions about the quality of the discovered meta-paths.
Dear Reviewer #dJZo,

We sincerely appreciate your thorough review and insightful comments on our manuscript. We have taken the time to carefully address all the points you raised, including

- explaining the misleading title
- clarifying the importance of long-range meta-paths and their role
- defending the improvement, especially in the ogbn-mag leaderboard
- explaining the leaderboard issues

Please refer to the **rebuttal content** for details.

As the discussion period is limited to 7 days and only 1 day remains, we kindly request your prompt feedback on our responses. Your expertise is crucial to us, and we welcome any additional thoughts you may have. Thank you once again for your time and attention.

Best regards,

Authors of #4444
**Zero-order condition**: Consider two high-dimensional random variables $\mathbf{y} = f(\mathbf{x}) \in \mathbb{R}^{m \times d_1}$ and $\mathbf{z} = g(\mathbf{x}) \in \mathbb{R}^{m \times d_1}$. We say that $\mathbf{y}$ and $\mathbf{z}$ satisfy the zero-order condition if, for any valid sample $\mathbf{x} \in \mathbb{R}^{n \times d}$, the inequality $|\mathbf{y} - \mathbf{z}|_2 \leq \epsilon$ holds, where $\epsilon$ is a very small positive number.

**Lemma 1**: Let $M$ represent the maximum number of activable paths, with each pair of operations satisfying the zero-order condition. Using $M$ distinct expectations and variances, it is possible to approximate all combinations (i.e., $2^M$).

Lemma 1 guarantees that we can track the combination containing $i$ meta-paths with at least $M$ iterations. **Given that the number of iterations significantly exceeds $M$, the relative importance of the meta-paths can be learned during the search stage.**

Below is the proof of Lemma 1:

Let 

${\mathbf{y}}_{p_y(y)} = f(\mathbf{x})$, 

${\mathbf{z}}_{p_z(z)} = g(\mathbf{x})$, 

and ${\mathbf{x}} \sim p_{x(x)}$.

For the case $M=1$, the expectations of $\mathbf{y}$ and $\mathbf{z}$ can be expressed as follows:

$$
\begin{aligned}
{\\mathbb E}[{\\mathbf y}]&={\\mathbb E}[f\left({\\mathbf x}\right)]=\int p_{{\\mathbf x}}({\\mathbf x}) f({\\mathbf x})  {\mathrm d}{\\mathbf x}
\end{aligned}
$$
$$
\begin{aligned}
{\\mathbb E}[{\\mathbf z}]&={\\mathbb E}[g\left({\\mathbf x}\right)]=\int p_{{\\mathbf x}}({\\mathbf x}) g({\\mathbf x})  {\mathrm d}{\\mathbf x}
\end{aligned}
$$

According to the zero-order condition, $f(\mathbf{x}) \approx g(\mathbf{x})$. Since $p(\mathbf{x})$ is the same for both $\mathbf{y}$ and $\mathbf{z}$, it follows that $\mathbb{E}[\mathbf{y}] \approx \mathbb{E}[\mathbf{z}]$.

Next, we prove that $Var[\mathbf{y}] \approx Var[\mathbf{z}]$. Note that $Var[\mathbf{y}] = \mathbb{E}\left[\mathbf{y}^{2}\right] - \left(\mathbb{E}[\mathbf{y}]\right)^{2}$ and $Var[\mathbf{z}] = \mathbb{E}\left[\mathbf{z}^{2}\right] - \left(\mathbb{E}[\mathbf{z}]\right)^{2}$. Thus, it suffices to prove that $\mathbb{E}\left[\mathbf{y}^{2}\right] \approx \mathbb{E}\left[\mathbf{z}^{2}\right]$. This can be similarly demonstrated as follows:

$$
\begin{aligned}
{\\mathbb E}\left[{\\mathbf y}^{2}\right]&=\int p_{{\\mathbf y}}({\\mathbf y}) {\\mathbf y}^{2} {\mathrm d}  {\\mathbf y} = \int p_{{\\mathbf x}}({\\mathbf x}) f^{2}({\\mathbf x}) {\mathrm d} {\\mathbf x}
\end{aligned}
$$

$$
\begin{aligned}
{\\mathbb E}\left[{\\mathbf z}^{2}\right]&=\int p_{{\\mathbf z}}({\\mathbf z}) {\\mathbf z}^{2} {\mathrm d}  {\\mathbf z} = \int p_{{\\mathbf x}}({\\mathbf x}) g^{2}({\\mathbf x}) {\mathrm d} {\\mathbf x}
\end{aligned}
$$


According to the zero-order condition, we have $Var[\mathbf{y}] \approx Var[\mathbf{z}]$.

For the case of $M=2$, when both paths are selected, the output becomes $\mathbf{y} + \mathbf{z}$, and its expectation can be written as:

$$
\begin{aligned}
{\\mathbb E}[{\\mathbf y} + {\\mathbf z}] &= {\\mathbb E}[{\\mathbf y}] + {\\mathbb E}[{\\mathbf z}] \approx 2{\\mathbb E}[{\\mathbf y}]
\end{aligned}
$$


The variance of $\mathbf{y} + \mathbf{z}$ is:
$$
\begin{aligned}
Var[{\\mathbf y} + {\\mathbf z}] \approx  Var [2{\\mathbf y}] = 4 Var[\\mathbf y]
\end{aligned}
$$

Thus, there are two types of expectations and variances: $\mathbb{E}[\mathbf{y}]$ and $Var[\mathbf{y}]$ for ${\mathbf{y}, \mathbf{z}}$, and $2\mathbb{E}[\mathbf{y}]$ and $4Var[\mathbf{y}]$ for ${\mathbf{y} + \mathbf{z}}$. Similarly, for the case where $M \in [1, K]$, there will be $M$ types of expectations and variances.
Thank you very much for the detailed response. In the following, we respond to your concerns point by point.

---

### **W1: Searching for meta-paths for heterogeneous graphs is not a new topic. Applying a commonly used search method for a not new topic is not very exciting.** 

**R1:** We appreciate that the reviewer gave us the opportunity to highlight our novelty again. We agree that searching for meta-paths for heterogeneous graphs is not a new topic. However, we would like to clarify that:
1. LMSPS is the first HGNN that makes it possible to achieve automated meta-path search for large-scale heterogeneous graph node property prediction*. 
2. LMSPS is the first HGNN to utilize long-range dependency in large-scale heterogeneous graphs.
3. The searched meta-paths of LMSPS can be generalized to other HGNNs to boost their performance, which has not been achieved by existing works. 

**All the above contributions are new topics.** In addition, as described by the reviewer, the differentiable search method is widely used in many applications inspired by NAS. There have been dozens of papers accepted by top conferences. In our paper, we have cited the related paper a dozen times, highlighted the differences between LMSPS and them, and compared LMSPS with the representative methods. **Overall, we can conclude that our search method is totally new.** The theoretical analysis of the reasonableness of the sampling search is provided below. Thank you very much!

---

### **W2: Many large graphs in OGB are heterogeneous and can be used for evaluation**. 

**R2:** Thank you for the question. **We would like to clarify that many excellent works [1-4] also highlight their advantage on large-scale heterogeneous node property prediction only based on the results on OGBN-MAG.** In addition, in OGB, there are only six datasets for node property prediction: ogbn-products, ogbn-proteins, ogbn-arxiv, ogbn-papers100M, and ogbn-mag, and MAG240M. Except for ogbn-mag and MAG240M, all other four datasets are not heterogeneous. Because MAG240M contains over 240,000,000 nodes, it has hardly been tested by related works. The following tables shows the statistics of ogbn-mag and MAG240M. Although we have tried to run MAG240M, our hardware conditions cannot support the training even in the preprocessing stage. Thank you very much!

| Dataset  | Num paper nodes | Num author nodes | Num institution nodes | Num field nodes | Total               |
| -------- | --------------- | ---------------- | --------------------- | --------------- | ------------------- |
| ogbn-mag | 736,389         | 1,134,649        | 8,740                 | 59,965          | 1,939,743           |
| MAG240M  | 121,751,666     | 122,383,112      | 25,721                | -               | 244,160,652  (126x) |

| Dataset  | Num paper-paper edges | Num author-paper edges | Num author-institution edges | Num paper-field edges | Total                |
| -------- | --------------------- | ---------------------- | ---------------------------- | --------------------- | -------------------- |
| ogbn-mag | 5,416,271             | 7,145,660              | 1,043,998                    | 7,505,078             | 21,111,007           |
| MAG240M  | 1,297,748,926         | 386,022,720            | 44,592,586                   | -                     | 1,728,364,232  (82x) |

---

### **W3: The authors should find some common insights from the searched meta-path.**

**R3:** We appreciate that the reviewer gave us the opportunity to highlight our insights again. We have shown insights into DBLP, IMDB, and ACM in the global response. We show them again as follows.

* In DBLP with target node type Author, the information from P (Paper) and A (Author) is slightly more important than that from T (Term) and V (Venue). 
* In IMDB with target node type Movie, the importance of information of K (Keyword), M (Movie), A (Actor) and D (Director) gradually decreases. 
* In ACM with target node type Paper, the importance of information of P (Paper), A (Author) and C (Conference) gradually decreases. 
* **For all related datasets, the importance of node type is highly related to the target node type**.

---

Thank you once more for your efforts. Please kindly let us know if our response has addressed your concerns. We are happy to answer your remaining concerns and questions if you have any.

---

[1] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS, 2020.

[2] Graph Attention Multi-Layer Perceptron. KDD, 2022.

[3] Simple and Efficient Heterogeneous Graph Neural Network. AAAI, 2023.

[4] An Efficient Subgraph-Inferring Framework for Large-Scale Heterogeneous Graphs. AAAI, 2024.
Dear authors, 

Thanks for your rebuttal. My further concerns are as follows:

1. I recognize the statement that a simple and straightforward design is better than a complex design. But, I want to emphasize the novelty is rather incremental although the experimental results seem to be promising. Differentiable search method is widely used in many applications inspired by NAS (Neural Architecture Search). Applying differentiable search method to the meta-path search is not a novel idea. Moreover, some similar ideas for selecting meta-paths and reducing expert experiences have also been proposed. In other words, searching for meta-paths for heterogeneous graphs is not a new topic. Applying a commonly used search method for a not new topic is not very exciting. Although the authors states that the progressive sampling algorithm and sampling evaluation strategy are novel. But, from my view, the two tricks are too engineering without any theoretical analysis. And, the main body of this paper is still the differentiable search method. **Overall, the novelty of the paper is not yet up to level of NeurIPS**. 
2. The paper focus on the meta-path search on large-scale graphs. However, only one large-scale graph is used. Moreover, it is suggested that the authors can choose some large graphs from other fields not limited to academic graphs. **Many large graphs in OGB are heterogeneous and can be used for evaluation**.
3. The concerns that many searched meta-paths seem strange and unreasonable still remains. Although the authors select some searched meta-paths and make explanations. But, most searched meta-paths lack interpretability. Interpreting the searched meta-paths one by one is infeasible. If the authors can find some common characteristics from the searched meta-path, this will have greater significance for guiding the design of the meta-path.

Overall, due to the limited novelty, the lack of more large-scale graph datasets from different fields, and the lack of the interpretability and the insight about the searched meta-paths, I maintain my ratings unchanged.
Thank you for appreciating the effort and insights! We're glad to hear that you're satisfied.
Thank you for your response. These have addressed the majority of my questions. I appreciate the effort and insights the authors put into the paper. I will maintain my original score.