Long-range Meta-path Search on Large-scale Heterogeneous Graphs
Authors: Chao Li
Zijie Guo
Qiuting He
Kun He
Venue: NeurIPS 2024 poster (2024)
Keywords: Heterogeneous graph
long-range dependency
meta-path
sampling
Primary area: graph_neural_networks
TL;DR: We utilize long-range dependency in heterogeneous graphs by dynamically selects effective meta-paths through progressive sampling so as to reduce computational costs and overcome over-smoothing issues.

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.

Long-range Meta-path Search on Lcrge-scale Heterogeneous Graphs
Chao Li Zijie Guo Qiuting He', Kun Heht
'School of Computer Science and Technology, Huazhong University of Science and Technology
China Mobile Information Technology Co.,Ltd. School of Computer Science, Fudan University {chaoli, j jiguuo brooklet600 @hust.edu.
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 investi- gate the importance of different meta-paths and introduce an automatic framework heterogeneous graphs, denoted Long-
for utilizing long-range dependency range Meta-path Search through Progressive Sampling (LMSPS). Specifically, we develop search space with all meta-paths related to the target node type. By em- ploying a progressive sampling algorithm, LMSPS dynamically shrinks the search space with -ooeinndeenddnt time complexity. Through a sampling evaluation strat- egy, LMSPS conducts a specialized and effective meta meta-path selection, leading to retraining with only effective meta-paths, thus mitigating Extensive experiments across diverse heterogeneous datasets validate LMSPS's ca- pability in discovering effective long-range meta-paths, surpassing state-of-the-art methods. Our code is available at atthtps: /ttp//ggttttt///////////e com/ JHL- HUST/LMPSS
and over-smoothing.
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 writes Paper, Paper cites Paper, Author is affiliated with has a topic of *Ficld These elements can be combined build higher-level semantic relations called meta-patie meta-paths [44). For example, APA is a 2-hop meta-path representing the co-author relationship, and PFPAPFP a 6-hop meta-path related long-range dependency.
Institution. and Paper
Utilizing long-range dependency essential for graph representation learning. For homogeneous graphs, many graph neural networks (GNNs) (28 long-range dependency. Utilizing long-range dependency 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 heterogencous graphs is how to alleviate costs while striving to effectively utilize information in exponentially increased receptive fields, which much more challenging compared homogeneous
have been developed gain benefit from
'The first two authors contribute equally.
1 Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

graphs due to the heterogeneity. In addition, the well-known over-smoothing issue [30 24 in many GNNs also needs to be addressed.
occurring
Heterogeneous Graph Neural Networks (HGNNs) are popular deep learning techniques for hetero- geneous graph representation learning. The key idea is aggregate valuable neighbor information based on a range of relations to enhance the semantics of vertices. Traditional HGNNs are typ- ically classified into two categories: metapath-free methods and metapath-basee methods. Most 21
utilize information from Z-hop neighborhoods by stacking I layers. However, on sarge-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 [66] 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-free HGNNs [63 18
3
23 52 obtain information from 1-hop neighborhoods by utilizing single-layer structures and meta-paths with maximum hop 1, i.e., all meta-paths no more than I hops. Benefiting from the feature of selective aggregation of neighbors based on meta-path, metapath- based HGNNs show greater potential in handling large-scale datasets [55] [2]. For metapath-based HGNNs, to exploit long-range dependency, the maximum hop needs be large enough as there are no stacking layers. However, the number of meta-paths also grows exponentially with maximum hop I, corresponding to exponential receptive fields associated with layers in metapath free methods. For instance, on OGEN-MAC to gain a 3-hop meta- meta-path based on the 2-hop meta- 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.
Metapath-based HGNNS 48
This paper investigates the importance of various meta-paths and makes two key observations: (I) A small number of meta-paths dominate the performance, and (2) certain meta-paths can have 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-pate paths.
Motivated by the observations mentioned above, we propose novel method called Long-range Meta-path Search through Progressive Sampling (LMSPS). LMSPS focuses on meta-path search and aims reduce the exponentially growing meta-paths 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, adopts a progressive sampling algorithm to reduce the search space. Finally. LMSPS selects the top-M meta-path from the reduced search space based on a sampling evaluation strategy. This search stage reduces the exponential number of meta- peeta-paths to constant for retraining. Experimental results on both real-world and manual sparse large-scale datasets demonstrate that LMSPS outperforms existing state-of-the--e 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- meta-paths efficiently, we introduce a novel progressive sampling algorithm to reduce the search space dynamically and sampling evaluation strategy for meta-path selection.
Moreover, the searched meta- 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 = EV,E, fT. fR} with [T 2 where denotes the set of nodes, denotes the set of edges, T is the node-type sei and R the edge-type set. Each node v; V is maped to node type [T(r:) E T by mapping function JT : - Similarly, each edge etes E (ets for short) is mapped to an edge type f (e(x)) E R by mapping function fR : E + R.
2

---

Meta-path 44) A meta-path P is composite relation that consists of multiple edge rypes, i.c., P -
C1 ct-1
11
Ci (P- = Ci c. for short), where C1,..., Ct E T and T12, (t- E R.
A meta-path P corresponds to multiple meta-path instances in the underlying heterogeneous graph. For example, meta-pati 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.
3 Related Works
Heterogeneous Graph Neural Networks. HGNNs are proposed to learn rich and diverse semantic
information on heterogeneous graphs. Several HGNNs (2 23 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 patta.ppths..ao 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 [5 is the first NAS method on heterogeneous graphs, which utilizes an evolutionary algorithm to search meta-graphs for recommendation tasks. DifTMG (8] searches for meta-graphs by a differentiable algorithm to conduct an efficient search. PMMM [27 performs stable search to find meaningful meta-multigrahhs.
However, meta- petta-pat--based HGNNs are mainstream methods 41 57 48 [1, while meta meta--raph-
based HGNNs are specialized. So, their searched meta- 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-pate meta-path selection strategy to discover meta-paths. Both of them are very time-consuming.
4 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-- 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
from IMDB as example. IMDB
D is important because the target movies can aggregate the keyword information from the movies of co-directors.
In addition, ScHGNN [52] employs attention mechanisms to fuse all the target-node-related meta- paths 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 meta- paths, indicating the advantages of long-range meta-paths. However, because the number of meta- paths increases exponentially with maximum hops, SeHGNN has use 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 ScHGNN 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 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
3

---

94:12
95-
Micro F1 (86)
Micro (56
Micro F1 (36
93.64
93:70
90
931
04.54
92.04
80.94
80
70.86
80
A1 pwmh
Ddly
A31
petho
07
APM
APP
APT
pMh
5.FC
6977
Figure 1: Analysis of the importance of different meta-paths. (a) illustrates the results after removing a single meta- meta-path on DBLP; (b) shows the performance of utilizing single meta-path on DBLP; (c) illustrates the performance after removing a part of meta-paths on ACM.
in Figure ! (a), removing either 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 = 2. We further retain one meta-path and remove others as shown in Figure (b). The performance of utilizing APV is only slightly degraded compared to the full meta meta-paths set. Consequently, we obtain the first observation: small number of mntaappath provide major contributions. In each experiment their impact on the final performance. Results Figure [igure[(c) show that the performance of ScHGNN improves after removing 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 negative impact for heterogeneous graphs. The second observation is reasonable because heterogeneous information not consistently beneficial for various tasks compared to homogeneous information. It is supported by the fact that various recent HGNNs S 27 52 have removed some edge types to exclude corresponding heterogeneous information during pre- pre-processing based on substantial domain expertise empirical observations. This observation explains why most HGNNs use a maximum hop of 2, iee., 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.
ACM, remove
meta- mncta-paths to analyze
Although long-range meta-paths outperform short meta-paths [52), they need large maximum hop, resulting in exponentially increasing meta-paths. Motivated by the above two observations, unlike existing methods [5] 31 [52 [56],
employ effective meta- meta-paths instead of the full meta-pate 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 constant. Now the key point is how to find effective meta-paths.
5
The Proposed Method
The key of our LMSPS to utilize a search stage to reduce the exponentially increased meta-patha paths to 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 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 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 illlsttaaess the overall framework of LMSPS. which consists 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 simple MLP-based instead of transformer-ban based architecture for meta-path search because the

---

HIN
Sourch By
SAN
Eieradion
Trakking
MLP
MLP
Nara
XAAA
Nai
XaPa
Sampli
Scuech Stage
Xux
Kittopela 8-21
Iicalinn
Xypt
S0ac2
MLP
MLP
Negatto EpprOUsciN)
Training
The overall framework of LMSPS. Based on the progressive sampling and sampling evaluation in the search stage, the training stage employs M effective meta-paths instead of the full K rrget-node-relatee meta-paths. It exhibits aggregation of meta-paths with maximum hop 2, Le., 0, and 2-hop meta-paths. The weight updates of feature projection are not shown for ease of illustration.
Figure 2:
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.
former involves fewer human interventions [45 16
5.1 Progressive Sampling Search
Let IP .PP.....,PP... ....... .KK be the initial search space with all the K target-node-related meta-paths, X be the raw feature matrix of all nodes belonging to type c,, and A be the row-normalized adjacency matrix between node type and G--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 I-hop meta- meta-path Pk = CDC1 C2 .q is:
X A Acr, A X
1= 0
X
(1)
1> 0
where X2 is the feature matrices of meta-path Pt. and co 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 MLPP (X)s)
To automatically discover meaningful meta-paths for various datasets or tasks without prior, our search space contains all auget-nodderelated meta-paths, severely challenging the efficiency and effectiveness of the search. To address the efficiency challenge, LMSPS utilizes progressive sampling algorithm sample meta-paths in each iteration and progressively shrink the search space.
Specifically, LMSPS assigns one architecture parameter to each meta-path. Let a {a)..... Org." (ak) E K be the architecture parameters of K meta-paths. We use Gumbel- softmax 35 over architecture parameters ag to calculate the strength of different meta-paths:
exp [(ag ux) /T]
4: Σj= exp [(a, + u,) 4T)
where ds is the path strength, representing the relative importance of meta path Pa- Ug - -log (- log (U)) where U ~ Uniform 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 @c be the C- largest path strength of Q = {q1. . .K: space retains all meta- meta-paths no less than qc. The dynamic search space can be formulated follows:
99K ). During the search stage, the search
Sc
(klg; 2 Tc, V1 < k < K} where C = [X(K -V) V..
Here C' is the search space size, Sc consists of the indexes of retained meta-paths, and [-] indicates the rounding symbol. E [0, 1] a parameter controlling the number of retrained mata-paths and decreases from to 0 as the epoch increases.
5

---

As the search stage aims to determine top-M meta- sattappatss, we sample M meta-paths from dynamic search space in each iteration. 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:
Z MT.P
dk MLPxx(x.) where $ = UniformSaaplo(Se, M).
KEB
Here ok2 exp [ov + up) /T Exep meta-paths, and UniformSample (Sc, M) indicates set of M elements chosen randomly from set Sc without replacement via a uniform distribution.
expl(aj + u;) /r] indicates the path strength of activated
The parameter update in the super-net involves a bilevel optimization problem
2
7
51
min Leat w (a)) a)) s.t. w"(a)= argmin Ctrain w. a).
(5)
Here Ltrain and Leal denote the training and validation loss, respectively. is the architecture parameters calculating the path strength. w is the network weights in MLP. Following the NAS-related works in the computer vision field [33 50 [53,, address this issue by first-order approximation. Specifically, we alternatively freeze architecture parameters a when training w 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 more effective meta-path discovery. Additionally, it can overcome the deep coupling issue [13] because of the randomness each iteration.
5.2 Sampling Evaluation
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 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, sample M meta-paths from the compact search space Sy 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- meta-path set instead of independent top-M meta-paths, which is more reasonable. This stage is not cime-consuming because the evaluation does not involve weight training. This sampling process can be represented as:
DiscreteSSamlle(Sv, M, Q).
Here, DiscreteSample(Sy. M, @) indicates a set of M elements chosen from set Sy without re- placement via discrete probability distribution Q Q is the set of relative path strengthh calculated by architecture parameters of the V meta-paths based on Equation 2 The overall search algorithm and more discussion are shown in Appendix
Thereafter, the retained meta-path set is recorded as SM argming Leal (S, ww,a""), The forward propagation of the target-net for representation learning can be formulated as:
= MLP
MLP)(X.)).
KEBM
Here, || denotes the concatenation operation. Unlike existing HGNNs, the architecture of the target- net 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
5.3 Discussion on Differences with Prior Works
As discussed in Section 3 there have been some attempts to find meta-pathe 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 heterogencous graph node property prediction. 2) Long-range dependency: LMSPS is

---

Table I: Performance small and large datasets. Best is in bold, and the runner-up is underlined.
Method
DRLP
IMDR
DCBN-MARY
Micro
MLP
GraphSAGi
40.
0.67
RGCN
91.52 1. 0.50
92.07
10.50
58.85
0.26
62.05
0.15
91.35
0.74
91.41
0.75
36.75 1.777
58.33 1.7
47.37 0.48
HAN 48
91.07 + 0.40
92.05
+ 0.62
67.74
0.56
GL.63
0.58
00.89
0.4
90-79-4
+ 0.43
21.3 + 1.68
54.77 + 1.40
001
GIN 56
58.52 8: 0.55
98.97
4 4..54
61.47
0.38
63.14
0.44
91.31
0.70
91.20
0.71
00M
003
0011
RSHN [3
53.34 + 0.58
99.61
+.0.5
50.85
3:21
61.22
1.05
90.50
1.51
90.32-+
1.54
0OM
0DMr
001
HeGGNN [37
91.76 1 0.43
0.441
08.25
2: 0.67
51.16
0.665
85.91
0.25
86,05
1: 0.25
0OM
003
0O1
MAGNN [1]
50.28 1 0.51
90.76.100.5
58.49
1.20
61.67
1.67
50,86
0.64
96.17 1 0.65
0OM
003
OOM
HctSANN 18
78.00 2.42
SIL5S + 1.50
69.47 +: 1:21
57.68
11.04
11355
80.31 =:
0OM
00M
OOM
GCN 26
50.84 0.050
91.47 0.034
57.88
1:18
61.82
0.64
90.17
92.12
00.23
0:92
OOM
GAT
50.85
55.39 0.33
58.54
1.35
99.26
92.19
258
65.26
0.80
OON
Simple 1IGN 88
94.01 1. 0.24
94.45 0.22
63.53
1.36
67.36
0.57
S0.42
93.35
0.45
47.72 1.48
06,29 0.455
OOM
HGT 21
6200
07.20
2.02
60.1 1:16
46.78
GraphME
57.60
00M
DiIMG 8
84,01
96.20
58.00
59.75
0OM
00M
Randow
90.84
0.74
21.22
2.66
35.14
NARS [55
54.18+0000 0.47
96.61 0.422
03:51
0.08
09.18
0.70
98.31
0.33
49.3 1:77
1:26 65 1.94
GOLA6 0.22
swcelBiONN
94.24
06.63
61:57
1.10
63
0.43
92.50
92.58
0.10
41 57
OOM
PMMM [2]
54.82
95.14
0:22
65.81
0.20
67.38
0.22
50.78
11.25
90.71
22 0.17
00M
003
0ON
H[Nommer 30
94.57 1. 0.23
94.94 0:221
64.65
0.50
67.88
0.34
50.91
0.42
90.85
0.45
$2.15 0.30
64.92 0.48
0OM
ScHGNN [2]
94.86
0.34
95.24 + 0.18
68:43
0.54
G6 21
0.882
00.96
0.48
98.88
+ 0.50
60.71
+ 0.44
63:41 +0447
61.45 0.29
SlonGAT
54.05
0.0.0
05.51
1:0 1.0.0
61.05
0.60
66
0.55
00
00.00-
0.25
94.06
1: 0.20
10.88
1.97
66.83 0.30
OOM
LMSPS (ouEs)
95.35
2 0.22
95,66
1: 0.20
66.99
0.32
08.70
= 0,36
94.73
0.41
$4.09 =: 0.36
$3.26
à 0.47
06.00 a 0.51
54,83 : 0.20
OGBN-MAG is a large dataset with nodes' numbers 10 175 times that of the other four datasets.
the first HGNN to utilize long-range dependency in large-scale heterogeneous graphs. To achieve the above two goals, LMSPS has addressed two key challenges: (a) alleviating costs while striving effectively utilize information in exponentially increased receptive fields and (b) overcoming the well-known over-smoothing issue. 3) High generalization: Based on Table 4 the searched meta-path of LMSPS can be generalized to other HGNNs to boost their performance, which has not been achieved by existing works. To accomplish this objective, LMSPS uses an MLPP-basdd architecture instead of transformer-basee one for meta-path search because the former involves fewer inductive
biases 45 16 3, i.e., human interventions.
Experiments and Analysis
This section evaluates the benefits of our method against state-of-the-ar models on nine heterogeneous datasets. We aim to answer the following questions: Q1. How does LMSPS perform compared with state-of-the-arr 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?
6.1 Datasets and Baselines
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-MA -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
6.2 Performance Analysis
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 metries on almost all datasets except Micro-F1 scores on Freebase, sometimes by significant margin, which validates the power of LMSPS. For example, on the largest dataset OGBN MMGG LMSPS achieves 54.83% test accuracy, while the best competitor has 11.45% test accuracy. Second, all metapath- -ree methods encounter out-of of-memory (OOM) issues when dealing with large datasets, including highly competitive methods, HINormer and SlotGAT, indicating the advantage of employing meta- 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-procedt proceecsssing and meta-path search. Finally, LMSPS outperforms Random significantly, further indicating the importance of meta-path search. More comparisons with top method combinations
7

---

1144
15.0
0.7
Smplerics
12.5
(POPS
CCM
94.5
1.00
10.0
0.5
USS
Micro
6.68
7.5
0.3
63.5
5.0
0.2
23.0
0.28
2.5
92.5
0.0
0.0
1.0
12
Maximum hop/ Layer
hop Layer
Maximum hop Layer
(a) Micro-F1
(b) GPU memory cost
(c) Time cost
Figure 3: Illustration of (a) performance, (b) memory cost, (c) average training time of Simple-HOn HGN, SeHGNN, and LMSPS relative to the maximum hop or layer on DBLP. The gray dotted line in (a) indicates the number of target-node-related meta-paths under different maximum hops, which is exponential.
Table 2: Experiments on DGBN-MMN analyze the performance of SeHGNN and LMSPS under different maximum hops #MP the number of meta-paths under different maximum hops
Table Experiments to explore the effectiveness of our search algorithm. In our LMSPS, the meta- paths are replaced by those discovered by other
methods.
Max hop
4MP
Time
SaHGNN Test accuracy
Time
LMSPS
Test accuracy
Method
0.14
DBLP
05.85
IMD3
ACM
Freehase
0.28
0.10
05.33+0.00
0.36
0.30
2
6.14
51.79
0.21
5.63
51.91 0.13
DARTS
95.35
66.23
0.14
33.45
0:11
63.25 0.42
3
25
11.28
52:44 0.16
10.02
02.72
0.24
SPOS
95.41
67.10
0:29
90.64
0:3.7
64.02 :: 0.62
4
50
0OM
0OM
14.34
03.43
+ 0.18
95.45 0.449
66.98
0.45
64.56
90.74
64.83
226
0OM
OOM
14.71
54.83
0.20
LMSPS
95.66 1: 0.20
68.70 0.26
94.69 :: 0.36
66.09 :: 0.51
on OGBN-MAG are shown Table 10 of Appendix E.2
in which LMSPS also shows the best
performance.
6.3 Analysis on Large Maximum Hops
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- baasdd method, SeHGNN [52) on DBLP. Figure 3 (a) shows that LMSPS has consistent performance with the increment of maximum hop. The failure 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 Meanwhile, LMSPS has almost constant consumption the maximum hop grows. Figure 3 shows the time cost of LMSPS 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 of Appendix E.
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 1, 2,3, we utilize the full meta-pan tatatppahhhaae set because the number of meta-paths is smaller than M = 30. Following the convention [34. (2), we measure the average time consumption of one epoch for each model. As shown in Table 2 the performance of LMSPS keeps increasing the maximum hop value grows. 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 stable under different maximum hops.
6.4 Effectiveness of the Search Algorithm and Searched Meta-paths
To answer Q3, we first explore the effectiveness of our search algorithm. In our architecture, our meta- meta-paths are replaced by those meta meta-paths discovered by other methods. DARTS [32] is the first differentiable search algorithm neural networks. SPOS [13] is classic singe-path differentiable algorithm. DARTS and SPOS aim to search operations, like 3 x 3 convolution, in CNNs. DiffMG g and PMMM 27 search for meta-graphs instead of meta-paths. We ignore these differences and focus the algorithms. The derivation strategies of the four methods unsuitable for discovering
8

---

Table 4: Experiments on the generalization of the searched meta paths. means using the meta-paths
Table 5: Results of LMSPS and SeHGNN on the sparse large-scale heterogeneous graphs. t means the improvements in test accuracy.
searched in LMSPS.
Machod
DBLF
LMDB
ACM
Freebase
Daiaset
ScHONN
LMSPS
HAN
82.05 + 0.62
64.63
0.58
90.79 + 0.43
54.77 + 1.40
OGBN-MAG-S
36.04 0.64
40.82
0.42
4.78
HAN
08.54:00.15
05.89
0.52
92.25
+ 0.47
57.13=0077
OGBN-MAG- 10
38.27=0.01
42.30 1: 0.23
4.03
SCHONN
93.87
0.50
65.41
OGBN-MAG--M
42.65+00.11 39.18-0.00
3.47
SeHGNN
85.57 + 0.23
68.50 + 0.24
94.46
+ 0.18
65.37 + 0.42
OGBN-MAG-50
=9.50=0.13
12.82
3.32
Table 6: Experiments on small and large datasets analyze the effects of different blocks in LMSPS. PS means progressive sampling strategy, and SE means sampling evaluation strategy. i means employing all meta-paths and replacing the concatenation operation with the transformer module.
Method
Maceo-F1
DBLP
MicroFF
Macro-F1
IMDB
MicroFI
Macro-F1
ACM
MicroFFi
Macro-FI
Freebuse
MicroFFl
OGEN MAG
LMSPS wio
91.71 # 0123
=500=
61 = 0.48
9E19 0.34
u1:44
38.99 1.47
4738
IMSPS WF SF
05.15 0.28
05.48
65.46
0.48
67.13 0:47
06.20 0.35
94.15
0.31
52.08 0.33
64.84 0.38
52.94 0.34
LMSPS
0.221
95.38 0.21
66.85
1 0.37
68.58
1 0.36
91.80
1. 0.42
01.57
0.39
GOM
GOM
00M
LMSPS
95.35 + 0.22
95.66 = 0.29
66.99 + 0.32
68.70
0.26
94.73 0.41
94.09
0.36
53.26 = 0,47 66,09 = 0.51
54.83 0.20
multiple meta-paths. So we changed their derivation strategies to ours to improve their performance. we report the Micro-F1 scores in Table The performance of LMSPS verifies the effectiveness of 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-pan meta-paths should be effective after being generalized to other HGNNs. Because finding meta-paths that work effectively across various HGNNs is tough task, it has not been achieved by previous works. We verify the generalization of our searched meta- path the most famous HGNN, HAN 48 and the SOTA metapath-based method SeHGNN (52). The Micro-FI scores on three representative datasets are shown in Table 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- meta-paths. In addition, we have shown the interpretability of scarched meta-paths in Appendix
6.5 Necessity of Long-range Dependency
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 in- degree related to edge type in OCBN-MAC 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 LMSPS outperforms SeHGNN more significantly with the increasing sparsity. In addition, the leading gap of LMSPSS 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 more effective with decreased direct neighbors on heterogencous graphs.
6.6 Ablation Study
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 sampling evaluation strategy. We explore how each of them improves performance through ablation studies under the same settings as the main experiments in Table [ As shown in Table 66 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 meta- paths shows slightly worse performance even if using many more meta-paths and is out-of-mennt memoryy on larger datasets, indicating that the transformer cannot eliminate the negative effects of noise. reasonable because attention values are calculated based softmax and are positive even for noise.

---

7 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, í.e., reducing computational costs while effectively utilizing information and addressing the over-smoothing issue. Based the performance, and certain meta meta-paths can have negative impact on performance, LMSPS introduced progressive sampling search algorithm and sampling evaluation strategy automatically identify effective meta-paths, hence reducing the exponentially growing number of meta-paths to a manageable constant. Extensive experiments demonstrated the superiority of L.SPPS existing methods, particularly on sparse heterogeneous graphs that require long-range dependencies, By employing simple MLPs and complex meta-paths, LMSPS offers novel direction that emphasizes data- dependent semantic relationships rather than relying solely on sophisticated neural architectures. The reproducibility and limitations discussed Appendix and Appendix G respectively.
two observations, i.e., a few meta-paths dominate
Acknowledgments
This work supported by National Natural Science Foundation (62076105,22222017),
References
[1] U. Alon and E. Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR, 2021.
[2] G. Anandalingam and T. L. Friesz. Hierarchical Optimization: An Introduction. Annals of Operations Research, pages 1-11, 1992.
[3] G. Bachmann, Anagnostidis, and Hofmann. Scaling mips: A tale of inductive bias. In Advances in Neural Information Processing Systems, NeurlPS, 2023.
[4] M. Bianchi, D. Grattarola, and C. Alippi. Spectral clustering with graph neural networks for graph pooling. In International conference machine learning. ICML, pages 874 883. PMLR, 2020.
[5] Y. Chang, C. Chen, W. Hu, Z. Zheng, X. Zhou, and Chen. MEGNN: Meta-path Extracted Graph Neural Network for Heterogeneous Graph Representation Learning. Knowledge-Based Systems, page 107611, 2022.
[6] W. Chiang, X. Liu, Si, Y. Li, Bengio, and C. Hsieh. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In KDD '19: In Proceedings of the 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 257-266. 2019.
[7] B. Colson, P. Marcotte, and G. Savard. An Overview of Bilevel Optimization. Annals of Operations Research, pages 235-256, 2007.
[8] Y. Ding, Q. Yao, H. Zhao, and T. Zhang. DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks. In KDD '11: In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 279-288, 2021.
[9] X. Dong and Y. Yang. Searching for a robust neural architecture four gpu hours. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, ICCV, pages 1761-1770, 2019.
[10] Erridge. The pareto principle. British Dental Journal, 201(7):419-419) 2006.
[11] X. Fu, J. Zhang, Z. Meng, and I. King. MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding. In Proceedings of the ACM Web Conference, WWW, pages 1331-2341, 2020.
10

---

[12] X. Glorot and Y. Bengio. Understanding the Difficulty of Training Deep Feedforward Neural Networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS, pages 249-256, 2010.
[13] Z. Guo, X. Zhang. H. Mu, W. Heng, Z. Liu, Y. Wei, and J. Sun, Single Path One-Shot Neural Architecture Search with Uniform Sampling. In European Conference on Computer Vision, ECCV, pages 544-560 144-500220 2020.
[14] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, NeurIPS, 30, 2017.
[15] Z. Han, F. Xu, J. Shi, Y. Shang, H. Ma, P. Hui, and Y. Li. Genetic Meta-Structure Search for Recommendation on Heterogeneous Information Network. In CIKM '20: The 29th ACM International Conference on Information and Knowledge Management, pages 455-464, 2020.
[16] X. He, B. Hooi, T. Laurent, A. Perold, Y. LeCun, and X. Bresson. A generalization of vit/mlp- mixer to graphs. In International Conference on Machine Learning, ICML, volume 202, pages 12724-12745, 2023.
[17] X. He, B. Hooi, T. Laurent, A. Perold, Y. LeCun, and X. Bresson. A generalization of vit/mlp- mixer to graphs. In International conference on machine learning, ICML, pages 12724-12745. PMLR, 2023.
[18] H. Hong, H. Guo, Lin, X. Yang. Z. Li, and J. Ye. An Attention-based Graph Neural Network for Heterogeneous Structural Learning. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, pages 4132 4139, 2020.
[19] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information 2020.
Processing Systems, NeurIPS, 33:22118-2211
[20] W. Hu, M. Fey, H. Ren, M. Nakata, Y. Dong, and J. Leskovec. OGB-LSC: A Large-Scale Chal- lenge for Machine Learning on Graphs. In Proceedings of the Neurul Information Processing Systems Track on Datasets and Benchmarks, 2021.
[21] Z. Hu, Y. Dong, K. Wang. and Y. Sun. Heterogeneous Graph Transformer. In Proceedings of the ACM Web Conference, WWW, pages 2704-2710, 2020.
[22] Q. Huang, H. He, A. Singh, S. Lim, and A. Benson. Combining label propagation and simple models out-performs graph neural networks. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[23] H. Ji. X. Wang, C. Shi, B. Wang, and S. Y. Philip. Heterogeneous Graph Propagation Network. IEEE Transactions on Knowledge and Data Engineering, pages 521-532, 2021.
[24] N. Keriven. Not too little, not too much: a theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, NeurIPS, 35:2268-2281 2022.
[25] D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. In Y. Bengio and
Y. LeCun, editors, International Conference on Learning Representations, ICLR, 2015.
[26] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representation, ICLR, 2017.
[27] C. Li, H. Xu, and K. He. Differentiable Meta Multigraph Search with Partial Message Propaga- tion on Heterogeneous Information Networks. Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, 2023.
[28] G. Li, M. Muller, A. Thabet, and B. Ghanem. Deepgens: Can gens go deep cnns? In Proceedings of the IEEE/CVF international conference on computer vision, ICCV, pages 9267-9276, 2019.
[29] J. Li, H. Peng, Cao, Y. Dou, H. Zhang, S. Y. Philip, and L. He. Higher-order Attribute- enhancing Heterogeneous Graph Neural Networks. IEEE Transactions on Knowledge and Data Engineering, pages 560-574, 2021.
11

---

[30] Q. Li, Z. Han, and X.-M. Wu. Deeper Insights Into Graph Convolutional Networks for Semi- supervised Learning. In Proceedings of the AAAI conference on artificial intelligence. AAAI, 2018.
[31] Y. Li, Y. Jin, G. Song, Z. Zhu, C. Shi, and Y. Wang. GraphMSE: Efficient Meta-path Selection in Semantically Aligned Feature Space for Graph Neural Networks. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, pages 4214, 2021.
[32] H. Liu, K. Simonyan, and Y. Yang. DARTS: differentiable architecture search. In 7th Interna- tional Conference on Learning Representations, ICLR, 2019.
[33] H. Liu, K. Simonyan, and Y. Yang. DARTS: Architecture Search. In 7th International Conference on Learning Representations, ICLR, 2019.
[34] Q. Lv, M. Ding, Q. Liu, Y. Chen, W. Feng. S. He, C. Zhou, J. Jiang, Y. Dong, and J. Tang. Are We Really Making Much Progress? Revisiting, Benchmarking and Refining Heterogeneous Graph Neural Networks. In KDD 21: In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1150-1160, 2021.
[35] C. J. Maddison, A. Mnih, and Y. W. Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint 1610012, 2016.
[36] Q. Mao, Z. Liu, C. Liu, and J. Sun. Hinormer: Representation learning on heterogencous information networks with graph transformer. In Proceedings of the ACM Web Conference, www, pages 599-610, 2023.
[37] W. Ning, R. Cheng, J. Shen, N. A. H. Haldar, B. Kao, X. Yan, N. Huo, W. K. Lam, T. Li, and B. Tang. Automatic meta-path discovery for effective graph- based recommendation. In Pro- ceedings of the 31 ACM International Conference on Information Knowledge Management, pages 1573-1572, 2022.
[38] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, NeurlPS, 32, 2019.
[39] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le, and A. Kurakin. Large-scale evolution of image classifiers. International conference on machine learning, ICML, pages 2902-2911, 2017.
[40] R. Sanders. The pareto principle: its use and abuse. Journal of Services Marketing, 1(2):37-40, 1987.
[41] M. Schlichtkrull, T. N. Kipf. P. Bloem, v. Berg, I. Titov, and M. Welling. Modeling Relational Data with Graph Convolutional Networks. In European semantic web conference, pages 593-607, 2018
[42] C. Sun, H. Gu, and Hu. Scalable and Adaptive Graph Neural Networks with Self-label- enhanced Training. arXiv preprint arXiv:2104.0955 09376. 2021.
[43] Y. Sun and J. Han. Mining Heterogeneous Information Networks: Structural Analysis Approach. SIGKDD Explor. pages 20-28, 2012.
[44] Y. Sun, J. Han, X. Yan, P. S. Yu, and T. Wu. PathSim: Meta Path-Based Top-K K Similarity Search in Heterogeneous Information Networks. Proc. VLDB Endow., pages 992-1003, 2011.
[45] O.O. Tolstikhin, N. Houlsby, A. Kolesnikov, L. Beyer, X. Zhai, T. Unterthiner,) Yung, A. Steiner, D. Keysers, J. Uszkoreit, et al. Mlp-mixer: An all-mip architecture for vision. Advances in Neural Information Processing Systems, NeurIPS, 34:24261 1222212-22222- 2021.
[46] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30- May 3, 2018, Conference Track Proceedings, 2018
[47] R. Wang, M. Cheng, X. Chen, X. Tang, and C.-J. Hsieh. Rethinking architecture selection in differentiable nas. In International Conference on Learning Representation, ICLR, 2021.
12

---

[48] X. Wang, H. Ji, C. Shi, B. Wang, Y. Ye, P. Cui, and P. Yu. Heterogeneous Graph Attention Network. In Proceedings of the ACM Web Conference, wwW. pages 2022-2032, 2019.
[49] L. Xie and A. L. Yuille, Genetic CNN. In IEEE International Conference on Computer Vision, ICCV, pages 1388-1397, 2017.
[50] S. Xie, H. Zheng, C. Liu, and L.. Lin. SNAS: Stochastic Neural Architecture Search. In 7th International Conference on Learning Representations, ICLR, 2019.
[51] C. Xue, X. Wang, J. Yan, Y. Hu, X. Yang, and K. Sun. Rethinking Bi-Level Optimization in Neural Architecture Search: A Gibbs Sampling Perspective. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, pages 10551-10559, 2021.
[52] X. Yang, M. Yan, S. Pan, X. Ye, and D. Fan. Simple and Efficient Heterogeneous Graph Neural Network, Proceedings of the AAAI Conference on Artificial Intelligence, AAAI, 2023.
[53] Q. Yao, J. Xu, W.-W. Tu, and Z. Zhu, Efficient Neural Architecture Search via Proximal Iterations. In Proceedings of the AAAI Conference Artificial Intelligence, AAAI, 2020.
[54] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T.-Y. Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, NeurIPS, 34:28877-28888. 2021.
[55] L. Yu, J. Shen, J. Li, and A. Lerer. Scalable Graph Neural Networks for Heterogeneous Graphs. arXiv preprint arXiv:2011.0966 2020.
[56] S. Yun, M. Jeong, R. Kim, J. Kang, and H. Kim. Graph Transformer Networks. In Advances Neural Information Processing Systems, NeurlPS, pages 11960-11970, 2019.
[57] C. Zhang, D. Song, C. Huang, A. Swami, and N. V. Chawla. Heterogeneous Graph Neural Network. In KDD 'I9: In Proceedings of the 25th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 793-803 2019.
[58] W. Zhang, Z. Yin, Z. Sheng, Y. Li, W. Ouyang, X. Li, Y. Tao, Z. Yang, and B. Cui. Graph Attention Multi-layer Perceptron. In KDD '22: In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, page 4560-4570, 2022.
[59] T. Zhao, C. Yang, Y. Li, Q. Gan, Z. Wang, F. Liang, H. Zhao, Y. Shao, X. Wang, and C. Shi. Space4hgnn: a novel, modularized and reproducible platform to evaluate heterogeneous graph neural network. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2776-2788 2022.
[60] Z. Zhong, C.-T. Li, and J. Pang. Reinforcement learning enhanced heterogeneous graph neural network. arXiv preprint arXiv:2010.1377 2020.
[61] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. Learning with local and global consistency. In Advances in Neural Information Processing Systems, NeurlPS, pages 321-328, 2003.
[62] Z. Zhou, Shi, R. Yang. Y. Zou, and Q. Li. Slotgat: slot-based message passing for heteroge- neous graphs. In International Conference on Machine Learning, ICML, pages 42644-42657. PMLR, 2023.
[63] S. Zhu, C. Zhou, S. Pan, X. Zhu, and B. Wang. Relation Structure-aware Heterogeneous Graph Neural Network. In 2019 IEEE International Conference on Data Mining, ICDM, pages 1539, 2019.
[64] X. J. Zhu. Semi-supervised learning literature survey. 2005.
13

---

Appendix Supplemenntll Material
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 reproducibility and limitations of our research work.
A Dataset and Task
A.1 Dataset Details
We evaluate method 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 (0)- The datasets from HGB follow transductive setting, where all edges 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 we show the details of all
number of nodes with OGBN-MAN Follow the convention [4 52 36 datasets in Table
A.2 Node Classification Tasks
Following the convention under the transductive setting and leave other downstream tasks related to heterogeneous graph representation learning as future work. Each dataset contains 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.
36), we concentrate on semi-supervised node classification
A.3 Searching and Training Objective
An MLP layer is appended after the main module of LMSPS, which reduces the dimension of node-level representations of heterogeneous graph the number of classes:
Y softmax Zw.),
(8)
where wa E RdoxN is the output weight matrix, d, 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:
f= E VEV, Σ,"
yo log [n],
Table 7: Statistics of the datasets.
Dataset
#Nodes
#Node types
#Edges
WEdge types
Target ICClasses
DBLP
26, 128
4
239, 566
author
4
IMDB
21, 420
4
86, 642
movie
5
ACM
10, 9112
4
5/17, 872
8
paper
3
Freebase
180,098 098
8
1, 057, 688
36
bonk
7
OGBN-MAG
9.939, 743
21, 111,
paper
349
OGBN- MAG-50
.393,,
9,531,
paper
349
OGBN MAG-20
0,93,,
7,975,
paper
349
OGBN- MAG-10
2,939,
6,610,
paper
349
DEBN-MAG-S
0,939,
4
4, 05,58,
paper
349
14

---

where VL denotes the set of labeled nodes, is a one-hot vector indicating the label of node v, and y, the predicted label for the corresponding node in Y. In the search stage, Vr. is the training set when updating w and the validation set when updating a. In the training stage, Vr. is the training set, and w is reinitialized and trained.
B Baselines and Parameter Settings
B.1 Baselines
We compare LMSPS with large number of HGNN baselines, including MLP [9]. GraphSAGE [4]
RGCN 41], HAN [8). GTN [56.. RSHN [63
HetGNN [57], MAGNN [T HetSANN [8]
GCN 26]. GAT
44 Simple- HGNple-HGN 34
HGT 21), GraphMSE 31. SlotGAT 62]. DiffMG 8
PMMM 27
HINormer (6), NARS 55
space4HGNN (99) SeHGNN (2). GEMS (15) and
RMS- HRee (7 are ignored because they are designed for recommendation tasks. RL-HGNN 60
omitted due 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 neighbor sampling strategy, so they can handle large-scale datasets. HGT is designed with a graph sampling strategy. making 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 scgeesscaeeeeo HGNNs (55). NARS (55) and SeHGNN [52] metapath-basse and pre-computation- based HGNNs, allowing them 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 SeHGNN and the version with label propagation as ScHGNN+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 Therefore,
is considered only in Appendix E.2 where we demonstrate the successful integration of our model with other techniques.
B,2 Training Settings
For training, we follow the settings of the HGB benchmark 34 and utilize the performance improve- ment on the validation set as guide to determine whether the model has been improved. Specifically, we observe 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: no performance improvement on the validation set observed within a specific count (referred to 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 (2), 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.
B.3 Parameter Settings for Baselines
For models such as RGCN, HAN, GTN, RSHN, HeIGNN, MAGNN, HeISANN, HGT, GCN, GAT,
Simple-HGN, and SeHGNN, the literature 34 52 provides tuned parameter settings along with corresponding performance small datasets, namely DBLP, IMDB, ACK, and Freebase. Therefore, we utilize these tuned parameter settings for these models on small datasets and utilize the reported performance.
15

---

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 33 Il 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.
B.4 Parameter Settings for LMSPS
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 maag DBLP, 5 for IMDB, ACM, and 3 for Freebase. All K architecture parameters 1,,, Q22, , aKK 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 meta-path path in the feature projection step, and the hidden size 512. All network weights are initialized by the Xavier uniform distribution [[2] and are optimized with Adam [25] during training. In the search stage, À is 1 during the first 20 epochs for warmup and decreases to linearly. r linearly decays with the number of epochs from 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 O. For the initial search space, we simply preset the maximum hop and use all aagge-node-relate meta-ppttss more than this maximum hop.
B.5 Evaluation Metrics
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.
C Algorithm
C.1
The Search Algorithm
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 OGEN-MAG as example. The number of farget-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 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-pate patt sets is C:3 10
Such 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 sampling evaluation strategy discover the best meta-patt 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. Because the search stage has many iterations and the initial values of architecture parameters are
httpp:://githuu..com/HUUU
htttpe//giitabb.ccc/////////////
hatpee//ggthhabbbccmm//HHHHH1/1
16

---

Algorithm The search algorithm of LMSPS
meta-path sets P (P,,.... Pk J: number of sampling meta-paths M; number of training iterations T'; number of sampling evaluation E
Input:
Parameter: Network weights w in MLP₁ for feature projection and MLP for downstream tasks; architecture parameters = {a1...... ag}
Output: The index set of selected meta- meta-paths
paths Sas
1: Neighbor aggregation
2: Calculate neighbor aggregation of raw features for each Ps E P based Equation
3: while
do
4: % Path strength
5: Calculate the path strength of all meta-paths based on Equation 2
6: % Dynamic search space
7: Calculate the current search space Sc based on Equations S
8:
% Sampling
9: Determine the set of indexes of sampled meta-paths based on Equation
10:
% Semantic fusion
11:
Fused the semantic information of the sampled meta-paths based on Equation
% Parameters updation
13: Update weights w by V. Werainn (w, (x)
Update parameters by V VaLval ox)
15:
end while
Evaluation
17: while < E do
Randomly sample M meta-paths from Se as S based on Equation
19: Calculate (S) of the sampled meta-paths
20: end while
21: Select the best meta-path set SM argining Le
22:
return SM
the same, all architecture parameters will be updated multiple times and the relative importance can be learned during training, making the total search cost similar to training a single HGNN once. Specifically, for OGBN-MAG, LMSPS can finish searching in two hours.
Except for efficiency. LMSPS can also overcome the over-squashing issue [ when utilizing long- range dependency. Over-squashing means the distortion of messages being propagated from distant nodes, which has been heuristically attributed graph bottlenecks where the number of (-hop neighbors grows rapidly with L. In LMSPS, we set the number of searched meta-paths A = 30 for all datasets, which is independent of Because the exponential meta-paths in metapath- methods correspond to exponential receptive fields in metapath- free methods, the constant M means approximately constant I-hop neighbors, i.e., LMSPS selectively aggregate effective neighbors for each target-net. Therefore, the over-squashing issue is overcome.
We have introduced the components of LMSPS in detail in the main text. LMSPS first employs progressive sample algorithm to narrow the search space from K to V. then utilizes sample evaluation filter out the best meta-path set with M meta-paths. V is parameter to trade off the importance of progressive sampling search and sampling evaluation. When V is too large, we need to repeat the sampling evaluation many more times, which will decrease the efficiency. When V is too small, some effective meta-pathe meta-paths may be dropped too early. So, we simply set V 2M. Generally, K >> M under large maximum hop. For small maximum hop, when K < M, the search stage is unnecessary because we can directly use all sanget-node-rllaee progressive sampling algorithm unnecessary because the search space small enough. When K 2M, we show the overall search algorithm in Algorithm
meta meta-ppths: when K < 2M, the
C.2 Theoretical analysis of the reasonableness of sampling search
Definition Zero-order condition: Given two high-dimensional random variables, y = f(x) Mxdd and g(x) R Mxd1, the zero-order condition is satisfied if ly z/2 S efor any valid sample R Nxd where is a small positive constant.
17

---

Table 8: Time complexity comparison of every training epoch. i means time complexity under small-scale datasets and full-batch training.
Method
Feature projection Neighbor aggregation Semantic fusion
Total
O[N(rd)) pa) O Fe)
O(N(rdj'
O(NYF")
OlN(rd) F2 O(N(rd) F2) ((Nrd(F2)
Simple-HGN
O(N(rd) O(Nrd(F)
Simple-GGN
((NrdF=*)
ScHGNN
F(N
O(NY' = O(NMP))
O(N F + F))( O(NMF2) O(NMF")
LMSPS-search
ONNFF
LMSPS-train
O(NMF
O(NMP*)
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 combinations using m rypes of expectations and variances.
Lemma C.I assures us that we can approximate all 2 combinations by multiple times sampling. The proof is given as follows.
Let Yp (y) fxx, (x)(2) g(x), x Px(x). For the case m 1, the expectation of y and can be written respectively as:
Efyl = Elf [x)] = - (x)xx
(10)
Elz] Elg (x)] / p> (xxxx(xx)xx
According to the zero-order condition, we have [xx ~ g(x). And p(x) is same for both y and z, so Ely] Elz].
Now prove Varly] Var[z]. Note that Varly] [y²] (Ely))² and Varlz] E [z²]
(E[z))", thus we only need to prove E [y²] so E [z²]. It can be similarly proved as follows:
E y = / by (y))) = / px(x)) (xx)xx
(1I)
E 2 / Pe (2)
/ Dx (x))) (x))))
According to the zero-order condition, we have Varly] R Var[z].
For the case of m 2, when the two paths are both selected, the output becomes y +2, its expectation can be written as:
E + z) = EEy] + E[z] yE
(12)
And the variance of y 2 is.
Varly + 2] [ar[2y] = 4Varly]
(13)
Therefore, there are two kinds of expectations and variances: [E(] and Var(y] for {y: 2), and 2E[y] and 4Var(y ar(y] for {y z}. Similarly, in the case where E [1, there will be kinds of expectations and variances.
C.3 Time Complexity Analysis
Following the convention 6 52), we compare the time complexity of LMSPS with HAN [48]. Simple-HGN 34,, and SeHGNN under mini-batch training with total target nodes. All methods employ [-hop neighborhood. For simplicity, we assume that the number of features is fixed to for all layers. The average degree of each node is rd, where the number of edge types and df is the number of edges connected to the node for each edge type. The complexity analysis is
18

---

Table 9: Meta-paths searched by LMSPS on different datasets.
Datasct
Meta-paths learnt by LMSPS
AP, APT. APVP. APAPA, APTPA, APTPT. APTPV, APVPA, APVPV, APAPAP, APAPTE. APAPVP. APTPTP, APTPVP, APVPTE, APAPAPY, APAPTPA, APAPTPV, APAPVPA, APAPYPT, APAPVPV. APTPAPA, APTPAPT, APTPIPT, APTPVPV, APYPAPT, APVPTPA, APVPVPA, APVPVPT, APYPVPV
DBLP
M. MA. MK. MAM. MDM. MKM. MAMK. MDMK. MKMD. MDMKM. MKMAM,
MKMDM, MKMKM, MAMAMK, MAMDMA, MAMDMK, MAMKMD, MAМKNK, MDMAMA, MDMAMD. MDMDMA, MDMDMK, MDMKMA, MKMAMA, MKMAMD, MKMAMK, MKMDMA,
IMDB
MKMDMK, MKMKMI,, MKMKMK
PPP. PAPP, PCPA, PCPP, PPPC. PPPP, PAPAP, PAPPP, PCPAP, PCPPA, PPAPA, PPAPC, PPAPP, PAPAPA, PAPCPA, PAPPAR, PAPPCP, PAPPPP, PCPAPP, PCPCPP, PCPPAP, PCPPPP, PPAPAP, PPAPCP, PPAPPA, PPAPPP, PPCPAP, PPPAPA, PPPCPA, PPPPPP
ACM
PE, PAPE, PFPP. PAPPP, PEPER, PPAPP, PPPAP, PPPER, PALAPP, PAPAPE, PFPAPE. PFPPPE. PEPPPR, PPAPPE, PPPAPE, PPPPAR, PPPPPE, PAIAPAP, PAPAPAP, PAPAPPP, PAPPPAI, PAPPPPE, PAPPPPR, PEPAPAP. PUPPEPE, PEPPPPE, PPAPAPE, PPAPAPP, PPPAIAL, PPPAPPP
OGBN-MAG
summarized in Table g 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 ((rd))). SeHGNN employs a pre- pre-processing step to avoid the training cost of neighbor aggregation. However, the exponential meta meta-paths cause SeHGNN to suffer from O(r") 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-pathi in the training stage to avoid exponential costs. Generally, we have ((rd)') > O(r')= O(K) >> (M) when maximum hop 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.
D Interpretability of Searched 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 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 the interpretability of meta-paths on large-scale obgn-mag dataset from the Open Graph Benchmark. The OGBN-MAG dataset is heterogeneous graph composed of 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 writes
Paper, Paper cites Paper, Institution, and Paper has topic "Field. The target node is the paper, and the task is to predict each paper's 's venue (conference or journal).
Author is affiliated with
Based on Table the hop of effective meta-paths obgn-mag ranges from 1 to 6, which means utilizing information from neighbors at different distances is important. Because long-range meta- paths provide larger receptive fields, LMSPS shows stronger capability in utilizing heterogeneity compared to traditional metapath-basee PFPFP (P--F-Pt-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 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 meta-paths is I. means the neighborhood institution is not very important for predicting the paper's 's venue, which is reasonable because almost all institutions have wide range of conference or journal options for publishing papers. No meta-pati -ath has source node type A. means the neighborhood author is unimportant in determining the paper's '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 kind of noise in obgn- mag for predicting each paper's 's venue.
HGNNs. The source node type of 16 meta- paths is P, e.g.,
19

---

96.0
SeHGNN
95.5
94.0
PMM
95.0
Simple-HGN
PM
Micro-Fi (96
03.0
Simple/HGN
94.5
DHiMMG
RGCN
93.5
MAGNN
91.0
00.0
RRSHN
MAGNN
93.0
92.0
RGCN
HAN
10
10
10
10
10a
Training time (s/epoch)
Training time (s/epoch)
(a) DBLP
(b) ACM
Figure 4: Micro-FI scores, time consumption, and parameters of various HGNNs on DBLP and ACM. GTN has large time consumption and parameters. We ignore for ease of illustration.
Table 10: Performance of top mothod combinations OGBN-MAG leaderboard.
OGBN-MAG
Method
Validation Accuracy
Test Accuracy
SAGN 42 +..
52.25 0.30
51.17 + 0.32
GAMLP S8PP
53.23 0.23
51.63 0.22
ScHGNN=L.P
55.95 0.11
53.99 0.18
LMSPS +LP
56.98 0.10
55.10 1 0.11
SHHGNNNLPPMSS
58.70 0.05
56.71 + 0.14
BOHGNN-LPAMSS-EN
59.17 0.09
57.19 0.12
1.MSPS +S
59.51 0.07
57.84 + 0.22
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-path: rely on intense expert knowledge, which is both laborious and data-dependent. In contrast, automatic meta-path search frees researchers from the understand- then-apply paradigm. In Table LMSPS can search effective meta-paths without prior knowledge for various datasets, which is more valuable than manually-define meta-paths.
E
More Experiments
E.1
Comparison on Training Efficiency
Following the convention 34 52 we show the time cost and parameters of LMSPS and the advanced We measure the average time consumption of one epoch for each model. The area of the circles represents the parameters. The hidden size set to 512 and the maximum hop 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 [ of the main text, which is the results under their best settings. Figure shows that LMSPS has advantages in both training efficiency and performance. Our searched meta- veta-ppths universal after searching once and can be applied to other metapath-busce HGNNs based on Table 4 Because other metapath- baase HGNNs don't t include the time for discovering manual meta-paths, also exclude our search time for discovering meta-pathe patt-pats in Figure The search time is shown in Figure (c) the main text.
baselines on DBLP and ACM in Figure [
F.2 Comparison with Top Method Combinations
The OGBN-MAG benchmark dataset is associated with 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
20

---

Table 11: The performance of LMSPS under different searching epochs.
Datasel
20
60
100
120
140
160
180
200
DBLF
38.52
08.75
71.20
72.03
71.05
70.50
73.12
13.70
T3.56
73.85
73.81
74.36
71.01
IMDB
43.48
49.78
53.88
38. 38.48
57.03
58.40
58.05
58.65
57.54
58.70
38.59
58.72
58.81
79.03
85.43
89.85
89.70
89.91
Froebase
18.37
29.55
39.62
39.58
44.43
46.37
47.52
48.3
54.59
55.81
35.52
53.66
55.79
OGBN MAG
14.21
26.20
32.41
37.00
40.82
45.89
41.74
44.00
48.40
48.55
48.70
48.43
48.39
06
70
95
Micro-FI (96
Micro-FI (%6
68-
Micro- F1 (96)
94-
93
04
M
M
(a) DBLP
(b) IMDB
(c) ACM
Figure 5: Micro-FI with respect to different hyper-parameter M on DBLP, IMDB, and ACM.
100
MBB
Micro-F11 (%)
80
70
60
50
40
10
Maximum hop
Figure Micro-F1 scores with respect to different maximum hops on DBLP, IMDB, and ACM.
(LP), Multi-Stage Training (MS), and pre-trained Embeddings (Emb). By integrating LP and MS, LMSPS HEPSSLP+MM outperforms SeHGNN+LP+MS by large margin. SeHGNN shows the results with extra embeddings as an enhancement. Though we cannot conduct a fair comparison with this trick due the untouchability its embedding file, LMSPS still outperforms their best result.
E.3
Convergence of the Search Stage
As the search stage of LMSPS relies on sampling, we conduct experiments to explore the convergence of the search stage. Because the test is unavailable the search stage 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 DGBN-MAG under different searching epochs in Table 11 we can see, LMSPS coverages during 100 to 180 epochs for all datasets. The main reason is that the search space size progressively shrunk from K 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.
E.4 Hyperparameter Study
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 hyper-parametes M DBLP, IMDB, and ACM. Freebase and OGBN-MAG are ignored because they are relatively large and the experiments time-consuming. As illustrated in Figure 5 the performance of LMSPS increases with the growth of M when is small. In addition, the performance on DBLP and ACM slightly decreases when M larger than certain threshold, indicating excessive meta- meta-paths don't benefit performance for some datasets. For unity, we set M = 30 for datasets.
To observe the impact of different maximum hop values, show the Micro-F1 of LMSPS with respect to different maximum hop values on DBLP, IMDB, and ACM in Figure ( We can see LM- SPS show the best performance when the maximum hop is 5 or 6. Additionally, the performance of
21

---

LMSPS does not always increase with the value of the maximum hop, and the best maximum hop depends on the dataset.
Reproducibility Statement
We have provided the details of datasets, tasks. baselines, and parameter settings in Appendix A and Bnd and conducted the hyperparameter study in Appendix(E.4 All reported results are the average of multiple experiments with standard deviations. We have included pseudocode description of our The source code has been provided through an anonymized URL with clear commands reproducing results.
method in Appendix C
G Limitations
It is noteworthy that the performance of LMSPS does not always increase with the value of the maximum hop. For instance, based on Figure (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. can be attributed 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-relatd meta-paths exceeds 1400 (Figure 3 (a)). Searching for 30 effective meta-paths from such extensive search space notably challenging, despite LMSPSS being the most effective method for meta-path search (as indicated in Table 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 the time complexity of LMSPS does not increase with the maxi- mum 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 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 more suitable tasks requiring long-range dependency to emerge in the future so we can fully explore our approach.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have provided cases, motivation, and also extensive experiments for verification to support our claim.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have talked about the limitation of work in Appendix G
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 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 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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
We have provided theoretical analysis of the reasonableness of the sampling
search in Appendix C.2
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided extensive experiments, results, descriptions, and also provided the code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
24

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
The code is provided a URL in the Abstract.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //iisscc/ppile wttp:ccppppcccceeeeeeeeee..c.ett httaa//gggiiee//eeuuabiisisssss /Co///ooddiisssseeeeeeee ssiiissiiciiiyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The details of datasets, tasks, baselines, and parameter settings are shown in Appendix and The hyperparameter study is shown in Appendix E.4
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The mean and variance the experimental results are reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
25

---

The method for calculating the error bars should be explained (closed form formula, call 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.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 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 range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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 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).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:pp:://oorrrps.pppppppbeeeee
Answer: [Yes]
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 heterogencous graph node classification; therefore, has limited possibility for a wide societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 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 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).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Similarly, work is specific to machine learning for heterogeneous graph node classification.
Guidelines:
The answer NA means that the paper poses 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 best faith effort.
12. Licenses for existing assets
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?
Question:
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 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 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.
27

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. 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 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/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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.
14. Crowdsoureing 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 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 the supplemental material is fine, but if the main contribu- tion 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.
15. 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 equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending 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.
28

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
29


Reviews:
[{"review_id": "jVdMO8AQTb", "reviewer": "Reviewer_dJZo", "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.", "questions": "1. Please refer to the aforementioned weaknesses.\n2. In OGB, I can see that LMSPS achieved the 3rd place. Have you tried to compare with the first two methods?", "limitations": "Limitations are sufficiently stated in the appendix. To my knowledge, there is no negative societal impact of this work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1. The presentation is excellent and easy to follow.\nS2. This paper is the first attempt to combine super-net and heterogeneous graph learning.\nS3. Experimental results show that their model achieves state-of-the-art (SOTA) performance.", "weaknesses": "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.\n\nW2. 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. \n\nW3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments. In the following, we respond to your concerns point by point.\n\n---\n\n### **W1: The paper's title is misleading. I think the major idea is to select effective meta-paths efficiently to overcome the issue of the exponential increase in meta-paths.**\n\n**R1:**  Thank you for the careful reading and insightful comments. On homogeneous graph fields, there have been many outstanding works [1-4] that highlight long-range dependencies in their title but still employ short-range dependencies. We think that the logic behind the behavior is **the importance of short-range dependencies is widely accepted and utilizing them is not challenging**. So, they highlight long-range dependencies in their title. Similarly, although our work can search meaningful short meta-paths, the most significant contribution differentiating this work from others is the ability to search effective long-range meta-paths in heterogeneous graphs. \n\nMoreover, though the major idea is totally the same as you mentioned, the issue of exponential increase in the number of meta-paths comes from our attempt to search long-range meta-paths. So, utilizing long-range dependency in heterogeneous graphs is the purpose, and overcoming the exponential issue is the specific process. \n\nIf the reviewer could kindly provide a more suitable title, we would love to use it. Thank you very much!\n\n---\n\n### **W2: I think SeHGNN does not mean that long-range meta-paths are more important than short paths. Long paths can introduce noise and less relevant connections between nodes, leading to less accuracy.**\n\n**R2:** Thank you. This is a very insightful comment. Although we also do not think long-range meta-paths are more important than short meta-paths, we appreciate that the reviewer gave us the opportunity to explain our key idea of utilizing long meta-paths. Compared to existing work only utilizing short meta-paths, the key advantage of LMSPS is freely combining the effective information from long and short meta-paths \n\n**Although most long meta-paths can introduce noise or redundant information, some effective long meta-paths can bring extra valuable information beyond short meta-paths**. The exact example can be found in the global response. Searching for effective long-range meta-paths is exactly one of our key contributions. As shown in Table 2 of Section 6.3, the performance of SeHGNN [5] and LMSPS keeps increasing as longer meta-paths are gradually introduced. However, SeHGNN can not utilize meth-paths larger than three hops on OGBN-MAG and the best performance is 52.44%, while the performance of LMSPS increases from 52.72% to 54.83% when the maximum hop grows from 3 to 6. So, utilizing effective long meta-paths can improve performance instead of leading to less accuracy. We will clarify it more clearly in the revised manuscript. Thank you very much!\n\n---\n\n### **W3: The enhancement is not significant enough according to the experimental results.**\n\n**R3:** Although the other three reviewers highlighted the enhancement of experimental results in Strengths, we appreciate that the reviewer allowed us to explain our results more clearly. Based on Table 1, most of the second-best results come from SlotGAT [6]. LMSPS achieves an average of 1.00% absolute improvement compared to SlotGAT on small and medium datasets. Considering these datasets are widely used and the existing scores are high enough, a 1.00% average improvement is not bad. Moreover, SlotGAT can not run on OGBN-MAG due to the out-of-memory issue, highlighting the advantage of LMSPS.\n\nThe second-best result on OGBN-MAG is 51.45%, which is outperformed by LMSPS by a large margin of 3.38%. Considering that OGBN-MAG is a large-scale dataset that is much more challenging than the other datasets and LMSPS is designed for large-scale heterogeneous graphs, the improvements can validate its effectiveness. In addition, based on Table 5, LMSPS outperforms the second-best method by a large margin of 4.78% on the sparser large-scale dataset, which is also significant. We will explain our results more clearly in the revised manuscript. Thank you very much! \n\n---\n\n### **W4: LMSPS achieves the 3rd place in ogbn-mag leaderboard. Have you tried to compare with the first two methods?** \n\n**R4:** Thank you for the question. I have tried to compare LMSPS with the first two methods, which use curriculum learning to change the input sequence of the data. However, we notice their results have been widely questioned due to the test label leakage problem (The code for the first place is completely based on that for the second place). The OGB team also noticed this problem and has asked the authors to investigate the results in two weeks. However, the authors haven't finished the investigation yet and have asked the OGB team to remove the leaderboard submission. Although we can not provide the external link due to the rebuttal policy, the discussion can be easily searched on GitHub. In addition, neither of the above works has complete papers, making their methods less trustworthy. \n\nIn summary, **LMSPS still ranks 1st on the ogbn-mag with trustworthy results**. \n\nThank you once again for your insightful comments.\n\n---\n\n**References:**\n\n[1] Representing Long-Range Context for Graph Neural Networks with Global Attention. NeurIPS, 2021.\n\n[2] Graph-based high-order relation modeling for long-term action recognition. CVPR, 2021.\n\n[3] Hope: High-order graph ode for modeling interacting dynamics. ICML, 2023.\n\n[4] High-order pooling for graph neural networks with tensor decomposition. NeurIPS, 2022.\n\n[5] Simple and Efficient Heterogeneous Graph Neural Network. AAAI, 2023.\n\n[6] SlotGAT: Slot-based Message Passing for Heterogeneous Graphs. ICML, 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HZ9FPoCh7E", "reviewer": "Reviewer_msas", "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.\nThe 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.\nThey 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.\nIn 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.", "questions": "Please see the weakness section.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "* The paper in general presents a nice framework. The paper is well-written, has good coherence, and is well-structured.\n* The two observations are interesting, i.e., a few meta-paths dominate the performance, and certain meta-paths can have negative impact on performance.\n* The paper is very clear with thorough experiments and analysis. The originality of the experiment is strong. \n* The experiments have demonstrated their limitations and possibilities to improve the effectiveness across datasets.", "weaknesses": "* 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? \n* 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?\n* What is the cost of the pre-processing stage? Can it be reduced by sampling to decrease the neighbor aggregation costs?\n* Line 172 clarifies that MLP requires less human intervention compared to Transformer. Are there specific experiments demonstrating the superiority of MLP?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments that greatly encourage us. In the following, we respond to your concerns point by point.\n\n---\n\n### **W1:  What does robust generalization to other classes imply or reveal about the process of long-range meta-path GNN training? Will the sampling search impact the model's robustness on searched meta-paths?**\n\n**R1:**   Thank you for the insightful question. As described in Lines 170-171,  to discover meta-paths with high generalization,  the search results should not be affected by specific modules. So, the more complex the model, the harder it is for the discovered meta-paths to generalize well, which can be viewed as a kind of overfitting on architectures. Based on this consideration, compared to the previous works [1-3] that do not show the generalization, the architecture of our model is very simple, with pure MLPs as the parametric modules.\n\nThe sampling strategy is very important for our meta-paths search. Its function can be summarized as follows.\n\n* Similar to dropout, 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. **So, the sampling search can increase the generalization ability.**\n* When the maximum hop is large, the search stage will run out of memory without the sampling strategy.\n* The sampling strategy can overcome the deep coupling issue [4] of differentiable search by introducing randomness in each iteration.\n\nAs the search stage aims to determine the relative importance of meta-paths rather than achieve robust accuracy, the sampling search has little impact on the robustness of the searched meta-paths. Specifically, because the search stage has many iterations, the architecture parameter of each meta-path will be updated multiple times and the relative importance can be learned during training even with the sampling strategy. It is supported by Table 11 in Appendix E.3, which shows that the search stage of LMSPS can converge well on all five datasets. Thanks to the question, we will clarify the corresponding part more clearly in the revised manuscript.\n\n---\n\n### **W2:  Will the second observation, \"certain meta-paths can have a negative impact for heterogeneous graphs\", be valid for other heterogeneous graphs?**\n\n**R2:**  Thank you for the insightful question. Except for ACM, in Lines 142-143, we have described an important fact that various recent HGNNs [5-7] have removed some edge types in the Freebase dataset to exclude corresponding heterogeneous information during pre-processing based on substantial domain expertise or empirical observations. The basic logic behind this behavior is that the meta-paths related to the edge types have negative impacts on heterogeneous graphs in the task. In addition, in Figure 5 of Appendix E.4, we can see that the performance of LMSPS doesn't always increase with the growth of the number of utilized meta-paths on DBLP, IMDB, and ACM, which also supports the second observation to some extent. Thanks to the question, we will clarify the corresponding part more clearly.\n\n---\n\n### **W3: What is the cost of the pre-processing stage? Can it be reduced by sampling to decrease the neighbor aggregation costs?**\n\n**R3:** Thank you for the questions. Following SeHGNN [7], the pre-processing executes the simplified neighbor aggregation only once without any parameter updating. Specifically, we use the multiplication of adjacency matrices to calculate the final contribution weight of each node to targets without calculating nodes in the middle of paths, which is much more efficient than the pre-processing step in HAN [3]. On small datasets, the pre-processing stage takes 1~4 seconds. On OGBN-MAG, the pre-processing stage takes about 130 seconds, which is about 1.2% of the whole training stage. We believe the neighbor aggregation costs can be reduced by sampling. However, it is not very necessary because the current pre-processing cost is much smaller than the training cost. We will explore this in future work and clarify the corresponding part more clearly in the revised manuscript. Thank you!\n\n---\n\n### **W4: Line 172 clarifies that MLP requires less human intervention compared to Transformer. Are there specific experiments demonstrating the superiority of MLP to Transformer?** \n\n**R4:** Thank you for the question. Although the Transformer is a widely used and powerful model, in line 172, we highlight that the Transformer involves more inductive bias, i.e., human intervention, than MLPs, which have been supported by many works [8-10]. \n\nIn LMSPS, the difference of importance between the searched effective meta-paths is much smaller than that between the full meta-path set, making the attention mechanism seem unnecessary. For higher efficiency and generalization, we use pure MLPs instead of Transformer. In Table 6 of the ablation study, we employ the Transformer for semantic attention on all meta paths. The Transformer version performs slightly worse than LMSPS even if it uses many more meta-paths and is out-of-memory on Freebase and OGBN-MAG. We will clarify the corresponding part more clearly in the revised manuscript. Thank you very much!\n\n---\n\n**References:**\n\n[1] Graph Transformer Networks. NeurIPS, 2019.\n\n[2] Heterogeneous Graph Transformer. WWW, 2020.  \n\n[3] Heterogeneous Graph Attention Network. WWW, 2022.  \n\n[4] Single Path One-Shot Neural Architecture Search with Uniform Sampling. ECCV, 2020.\n\n[5] DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks. KDD, 2021.\n\n[6] Differentiable Meta Multigraph Search with Partial Message Propagation on Heterogeneous Information Networks. AAAI, 2023.\n\n[7] Simple and Efficient Heterogeneous Graph Neural Network. AAAI, 2023.\n\n[8] MLP-Mixer: An all-MLP Architecture for Vision. NeurIPS, 2021.\n\n[9] A Generalization of ViT/MLP-Mixer to Graphs. ICML, 2023.\n\n[10] Scaling MLPs: A Tale of Inductive Bias. NeurIPS, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j6geneAPSz", "reviewer": "Reviewer_71Wo", "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.", "questions": "See W1.", "limitations": "NA.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and easy to follow. The technical designs are clearly described.\n2. The idea of using a progressive sampling algorithm to narrow the search space for meta-paths is novel and well motivated. \n3. The framework is designed to handle large-scale graphs efficiently, maintaining stable performance and resource usage even as the complexity of meta-paths increases. \n4. The proposed method consistently outperforms SOTA baselines across multiple datasets, including large-scale datasets like OGBN-MAG, demonstrating its robustness and effectiveness.", "weaknesses": "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?\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comments that greatly encourage us. In the following, we respond to your concerns point by point.\n\n---\n\n### **W1: I still have some doubts about the necessity of modeling long-range dependencies in heterogeneous graphs. Could the authors provide an example to illustrate specific situations where long-range dependency is crucial?**\n\n**R1:**  Thank you so much for the insightful question. As shown in Table 2 of Section 6.3, SeHGNN can not utilize meth-paths larger than three hops on OGBN-MAG, and the best performance is 52.44%, while the performance of LMSPS increases from 52.72% to 54.83% when the maximum hop grows from 3 to 6. We can see that long meta-paths can increase performance significantly, but the performance of short meta-paths is also not bad. Utilizing long meta-paths means freely combining effective information from long and short meta-paths, which is the core advantage of LMSPS.\n\nUnderstanding long meta-paths is difficult. However, automatic meta-path search actually frees researchers from the understand-then-apply paradigm. Based on LMSPS, we can search long and effective meta-paths without prior knowledge for various datasets. It is much more convenient than defining manual meta-paths based on expert knowledge, which is both laborious and data/task-dependent.\n\nThanks to your suggestion, we 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←D←D←M←K is important because the target movies can aggregate the keyword information from the movies of co-directors. This example shows **the ability of long-range dependencies to complete the missing information that can not be obtained from close nodes**. \n\nWe hope the example meets your requirements. We will clarify the necessity of modeling long-range dependencies more clearly in the revised manuscript. Thank you!\n\n---\n\n### **W2: More detailed ablation studies focusing on the individual components of LMSPS would strengthen the validation of its effectiveness.**\n\n**R2:** Thank you for the kind suggestion. In Table 6 of Section 6.6, we have conducted ablation studies to analyze the effects of individual components in LMSPS. Specifically, we separately remove the progressive sampling method, sampling evaluation strategy, and concatenation operation to observe the performance of LMSPS. As shown in Table 6, the performance of LMSPS significantly decreases when removing progressive sampling or sampling evaluation strategy and slightly decreases after replacing the concatenation operation with the transformer block. We will highlight the ablation study in the revised manuscript. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1eO6QeJm9Z", "reviewer": "Reviewer_r1gQ", "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.", "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.\n\n2. 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? \n\n3. 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.\n\n4. More experimental analysis should focus on large-scale datasets, such as the performance and efficiency analysis in Figure 3. \n\n5. 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.\n\n6. It is suggested to analyze all searched meta-paths in-depth and give more insights about how to choose suitable meta-paths manually.\n\n7. 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": "NA", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written and easy to understand.\n2. The experiments are comprehensive and the experimental results reveal the effectiveness of the proposed method.\n3. The motivation sounds reasonable.", "weaknesses": "1. This novelty of this paper is limited. \n2. The paper lacks a theoretical analysis about why the sampling strategy in the search stage is valid. \n3. Experimental results on more large-scale graph datasets should be conducted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments. In the following, we respond to your concerns point by point.\n\n---\n\n### **W1: This paper has limited novelty because the proposed method is simple and straightforward.** \n\n**R1:** Although the other three reviewers enjoyed the novelty, we appreciate that the reviewer gave us the opportunity to highlight our novelty. We would like to clarify that the simplicity of the proposed LMSPS does not mean the novelty is limited. The novelty is highly related to the contribution. **If a method is effective,  a simple and straightforward design is better than a complex design**. \n\nThe contributions of LMSPS have been summarized in the global response. To achieve the goals listed in the contributions, we propose a progressive sampling algorithm and a sampling evaluation strategy to overcome the efficiency and effectiveness challenges, respectively. **The high efficiency and high generalization of LMSPS exactly come from the simplicity** of the proposed method. \n\nIn addition, compared to other differentiable search methods such as DiffMG, both the progressive sampling algorithm and sampling evaluation strategy are novel. In Table 3, LMSPS is compared with them and shows obvious advantages. We will clarify the novelty more clearly in the revised manuscript. Thank you very much!\n\n---\n\n### **W2: Why is the simple progressive sampling method effective?** \n\n**R2:** Thank you for the insightful question. As you mentioned, it is hard to filter out promising meta-paths in the early stage. So, as described in Lines 609-610 of Appendix B.4, LMSPS **warmups the parameters** for 20 epochs without dropping out any meta-paths. \n\nBecause **the effectiveness of the algorithm is determined entirely by the final performance**, we can not provide theoretical analysis without experimental results to demonstrate the effectiveness. However, we have conducted adequate experiments to validate its effectiveness.\n* In Table 3, LMSPS is compared with six methods and shows obvious advantages.\n* In Table 6, the ablation study shows that both the progressive sampling method and sampling evaluation strategy can improve performance significantly.\n* In Table 11, the results show that the search stage of LMSPS can converge well on all five datasets.\n\nWe believe these results have validated the effectiveness.  In addition, we have also provided an intuitive analysis of the effectiveness in Lines 634-639. Thanks to your question, we will highlight the effectiveness of the algorithm more clearly. \n\n---\n\n### **W3: It is suggested that more large-scale heterogeneous datasets be added.**\n\n**R3:** Thank you for the suggestion. Different from homogeneous graph fields, there are few academic large-scale datasets in heterogeneous graph fields due to heterogeneity. OGBN-MAG is the only large-scale heterogeneous graph dataset with a leaderboard and comparable baselines.\n\nTo evaluate the effectiveness of LMSPS in more large-scale heterogeneous graphs, in Table 5, we also 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 heterogeneous graphs. Based on your suggestion, if you could kindly provide some suitable large-scale heterogeneous datasets, we would love to evaluate LMSPS on them. Thank you!\n\n---\n\n### **W4:  More analysis, such as performance and efficiency analysis, should focus on large-scale datasets.**\n\n**R4:** Thank you for the suggestion. We would like to clarify that Table 2 and Lines 292-299 have analyzed the performance and efficiency of LMSPS on large-scale datasets under different maximum hops. In addition to Table 2, we also conducted a large number of experiments on large-scale datasets in Tables 1, 5, 6, 10, and 11. For most other experiments, we can only conduct reasonable comparisons on small and medium datasets **because most baselines run out of memory on large-scale heterogeneous graphs**. We will highlight the experiments and analysis of large-scale datasets in the revised manuscript. Thank you!\n\n---\n\n### **W5&W6: The interpretability of searched meta-paths should be explained. It is suggested to give more insights about how to choose meta-paths manually.** \n\n**R5&R6:** Thank you for the suggestion. One of the important features of meta-paths is their hop count. The 5-hop meta-path \"PPPPPP\" means aggregating the node features from 5-hop \"P\" neighbors through the paths \"PPPPPP\". We also provided a detailed example in the global response for understanding the searched meta-paths.\n\nThe manual meta-paths rely on intense expert knowledge, which is both laborious and data/task-dependent. Considering it is impossible to understand the meta-paths of all real-world heterogeneous graphs, our automatic meta-path search shows great advantage by freeing researchers from the understand-then-apply paradigm. \n\nIn lines 674-706, we have focused on explaining and giving some insights about choosing meta-paths in OGBN-MAG. We summarize them as: **The importance of information from P (Papers), F (Fields), I (Instructions)  to A (Authors)  gradually decreases**. \n\nThe insights of the other datasets are shown in the global response. Due to space limitations, we can not interpret hundreds of meta-paths one by one here. We will add the explanations and insights in the revised manuscript. Thank you!\n\n---\n\n### **W7: Many hyperparameters need to be tuned on each dataset, such as C, M, and the maximum hops.**\n\n**R7:** Thank you for the question. We would like to clarify that **both C and M are not tuned on each dataset**. In Line 603, we have described that the number of selected meta-paths M is 30 for all datasets. Similarly, C is not tuned on each dataset. Based on Eq. (3), C is not a hyper-parameter but a dynamic value progressively decreasing with the search epochs. We will clarify them in the revised manuscript.\n\nThank you once again for your insightful comments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are very grateful to the reviewers for carefully reviewing our paper and providing constructive comments and suggestions that have helped improve our submission. We especially thank the reviews for recognizing that our paper has: 

1. **good originality** on method ((Reviewers djZo and 71Wo) and experiments (Reviewer maas),
2. **outstanding experiment results** (All Reviewers),
3. **nice presentation** (All Reviewers).

The main concerns include the limited novelty (r1gQ), the third-place ranking in OGB (djZo), the importance of long-range meta-paths (dJZo, 71Wo), and the insights from searched meta-paths (r1gQ). We briefly introduce the responses to these concerns in this general response section and provide concrete details in the response to each reviewer.

**For the limited novelty**, because the novelty is highly related to the contributions. We summarize the contributions as follows.

- 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.
- Long-range dependency. LMSPS is the first HGNN to utilize long-range dependency in large-scale heterogeneous graphs. To achieve the above two goals, LMSPS has addressed two key challenges: (1) Alleviating costs while striving to effectively utilize information in exponentially increased receptive fields and (2) overcoming the well-known over-smoothing issue. 
- High generalization. As shown in Table 6, the searched meta-paths of LMSPS can be generalized to other HGNNs to boost their performance, which has not been achieved by existing works. To accomplish this objective, LMSPS uses an MLP-based architecture instead of a transformer-based architecture for meta-path search because the former involves fewer inductive biases, i.e., human interventions. 

**For the third place ranking in OGB**, we have provided the details that the first two methods were questioned by the OGB team due to the test label leakage problem. The authors have asked the OGB team to remove the leaderboard submission.

**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. 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←D←D←M←K is important because the target movies can aggregate the keyword information from the movies of co-directors. 

**For the insights from searched meta-paths**, we have added the missing 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. In addition, the importance of node type is highly related to the target node type.

**We hope that our response has addressed your concerns. In case you still have some concerns or we missed anything, please let us know.**

**Best regards**

Meta-review: 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.
Decision: Accept (poster)