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

Thank you for the detailed response!

Thank you very much for the detailed response. In the following, we respond to your concerns point by point. --- ### **W1: Searching for meta-paths for heterogeneous graphs is not a new topic. Applying a commonly used search method for a not new topic is not very exciting.** **R1:** We appreciate that the reviewer gave us the opportunity to highlight our novelty again. We agree that searching for meta-paths for heterogeneous graphs is not a new topic. However, we would like to clarify that: 1. LMSPS is the first HGNN that makes it possible to achieve automated meta-path search for large-scale heterogeneous graph node property prediction*. 2. LMSPS is the first HGNN to utilize long-range dependency in large-scale heterogeneous graphs. 3. The searched meta-paths of LMSPS can be generalized to other HGNNs to boost their performance, which has not been achieved by existing works. **All the above contributions are new topics.** In addition, as described by the reviewer, the differentiable search method is widely used in many applications inspired by NAS. There have been dozens of papers accepted by top conferences. In our paper, we have cited the related paper a dozen times, highlighted the differences between LMSPS and them, and compared LMSPS with the representative methods. **Overall, we can conclude that our search method is totally new.** The theoretical analysis of the reasonableness of the sampling search is provided below. Thank you very much! --- ### **W2: Many large graphs in OGB are heterogeneous and can be used for evaluation**. **R2:** Thank you for the question. **We would like to clarify that many excellent works [1-4] also highlight their advantage on large-scale heterogeneous node property prediction only based on the results on OGBN-MAG.** In addition, in OGB, there are only six datasets for node property prediction: ogbn-products, ogbn-proteins, ogbn-arxiv, ogbn-papers100M, and ogbn-mag, and MAG240M. Except for ogbn-mag and MAG240M, all other four datasets are not heterogeneous. Because MAG240M contains over 240,000,000 nodes, it has hardly been tested by related works. The following tables shows the statistics of ogbn-mag and MAG240M. Although we have tried to run MAG240M, our hardware conditions cannot support the training even in the preprocessing stage. Thank you very much! | Dataset | Num paper nodes | Num author nodes | Num institution nodes | Num field nodes | Total | | -------- | --------------- | ---------------- | --------------------- | --------------- | ------------------- | | ogbn-mag | 736,389 | 1,134,649 | 8,740 | 59,965 | 1,939,743 | | MAG240M | 121,751,666 | 122,383,112 | 25,721 | - | 244,160,652 (126x) | | Dataset | Num paper-paper edges | Num author-paper edges | Num author-institution edges | Num paper-field edges | Total | | -------- | --------------------- | ---------------------- | ---------------------------- | --------------------- | -------------------- | | ogbn-mag | 5,416,271 | 7,145,660 | 1,043,998 | 7,505,078 | 21,111,007 | | MAG240M | 1,297,748,926 | 386,022,720 | 44,592,586 | - | 1,728,364,232 (82x) | --- ### **W3: The authors should find some common insights from the searched meta-path.** **R3:** We appreciate that the reviewer gave us the opportunity to highlight our insights again. We have shown insights into DBLP, IMDB, and ACM in the global response. We show them again as follows. * In DBLP with target node type Author, the information from P (Paper) and A (Author) is slightly more important than that from T (Term) and V (Venue). * In IMDB with target node type Movie, the importance of information of K (Keyword), M (Movie), A (Actor) and D (Director) gradually decreases. * In ACM with target node type Paper, the importance of information of P (Paper), A (Author) and C (Conference) gradually decreases. * **For all related datasets, the importance of node type is highly related to the target node type**. --- Thank you once more for your efforts. Please kindly let us know if our response has addressed your concerns. We are happy to answer your remaining concerns and questions if you have any. --- [1] Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS, 2020. [2] Graph Attention Multi-Layer Perceptron. KDD, 2022. [3] Simple and Efficient Heterogeneous Graph Neural Network. AAAI, 2023. [4] An Efficient Subgraph-Inferring Framework for Large-Scale Heterogeneous Graphs. AAAI, 2024.

Looking forward to your response

Dear Reviewer #dJZo, We sincerely appreciate your thorough review and insightful comments on our manuscript. We have taken the time to carefully address all the points you raised, including - explaining the misleading title - clarifying the importance of long-range meta-paths and their role - defending the improvement, especially in the ogbn-mag leaderboard - explaining the leaderboard issues Please refer to the **rebuttal content** for details. As the discussion period is limited to 7 days and only 1 day remains, we kindly request your prompt feedback on our responses. Your expertise is crucial to us, and we welcome any additional thoughts you may have. Thank you once again for your time and attention. Best regards, Authors of #4444

Thank you for the detailed response!

Thank you very much for the detailed response. In the following, we respond to your concerns point by point. ### W1: How do the discovered long-range meta-paths benefit performance? The methodology seems to lack specific techniques for searching meaningful "long-range" meta-paths. **R1:** Thank you for the insightful question. In the global rebuttal "For the importance of long-range meta-paths," we have provided a detailed example to show the ability of long-range dependencies to complete the missing information that can not be obtained from close nodes. Also, as shown in Table 2 in Section 6.3 (also shown below for quick check), the performance of LMSPS keeps increasing as the maximum hop value grows, which means gradually adding longer meta-paths. It indicates that LMSPS can overcome the issues caused by utilizing long-range dependency, e.g., over-smoothing and noise. Moreover, as shown in Table 4 of Section 6.4, the discovered meta-path can also benefit SeHGNN. Searching for long-range meta-paths has two main challenges: the exponentially increasing issue and the noise issue. To overcome both issues, as described in Lines 157-169, we propose a progressive sampling algorithm and a sampling evaluation strategy to overcome the two challenges, respectively. Specifically, the high-efficiency progressive sampling algorithm ensures LMSPS can search effective short and long-range meta-paths under a large maximum hop. As different meta-paths could be noisy or redundant to each other, top-M meta-paths are not necessarily the optimal solution when their importance is calculated independently. The sampling evaluation strategy evaluates the overall performance of each meta-path set. So, it can overcome the noise issue. | Max hop | Num path | SeHGNN (Time / Test Acc (%)) | LMSPS (Time / Test Acc(%)) | | :-----: | :------: | :------------------------: | :----------------------------: | | 1 | 4 | 4.35 / 47.18 | 3.98 / 46.88 | | 2 | 10 | 6.44 / 51.79 | 5.63 / 51.91 | | 3 | 23 | 11.28 / 52.44 | 10.02 / 52.72 | | 4 | 50 | OOM | 14.34 / 53.43 | | 5 | 107 | OOM | 14.77 / 53.90 | | 6 | 226 | OOM | 14.71 / **54.83** | --- ### **W2.1: If this setting is changed to a limited number of meta-paths, SeHGNN could be efficient due to its simplified attention mechanism.** **R2.1:** Thank you for the insightful comment. Based on our second observation, i.e., certain meta-paths can have a negative impact on heterogeneous graphs; the attention mechanism has limitations in dealing with negative meta-paths. As described in Lines 142-144, the second observation is supported by the fact that various recent HGNNs have removed some edge types to exclude corresponding heterogeneous information during the pre-processing stage. For example, SeHGNN removes all edge types related to node type F (Field) in the ACM dataset. If simplified attention can handle negative meta-paths, this step is unnecessary. On the contrary, by meta-path search, LMSPS can easily drop out negative meta-paths. Table 2 supports this conclusion. When the maximum hop is 3, LMSPS outperforms SeHGNN by 0.28%, even the latter using more meta-paths. --- ### **W2.2: The experiments should give more discussions about the quality of the discovered meta-paths.** **R2.2:** As described in Lines 310-319, to demonstrate the high quality of searched meta-paths, on the one hand, the meta-paths should be effective in the proposed model. On the other hand, the effective meta-paths mainly depend on the dataset instead of the architecture, so the meta-paths should be effective after being generalized to other HGNNs. Based on the results in Tables 1,2,3,5, using the search meta-paths, LMSPS outperforms the other baselines on almost all conditions, sometimes significantly, which can validate the high quality of the discovered meta-paths on the proposed model. Because finding meta-paths that work effectively across various HGNNs is a tough task, it has not been achieved by previous works. However, based on Table 4 (also shown below for quick check), After simply replacing the original meta-path set with our searched meta-paths and keeping other settings unchanged, the performance of HAN and SeHGNN both improve, demonstrating the effectiveness of our searched meta-paths. Thank you very much! | Method | DBLP | IMDB | ACM | Freebase | | ------------ | -------------- | -------------- | -------------- | -------------- | | HAN | 92.05 | 64.63 | 90.79 | 54.77 | | HAN-LMSPS | 93.54 | 65.89 | 92.28 | 57.13 | | SeHGNN | 95.24 | 68.21 | 93.87 | 63.41 | | SeHGNN-LMSPS | 95.57 | 68.59 | 94.46 | 65.37 | --- Thank you once more for your efforts. Please kindly let us know if our response has addressed your concerns.

Theoretical analysis about the reasonableness of sampling search

**Zero-order condition**: Consider two high-dimensional random variables $\mathbf{y} = f(\mathbf{x}) \in \mathbb{R}^{m \times d_1}$ and $\mathbf{z} = g(\mathbf{x}) \in \mathbb{R}^{m \times d_1}$. We say that $\mathbf{y}$ and $\mathbf{z}$ satisfy the zero-order condition if, for any valid sample $\mathbf{x} \in \mathbb{R}^{n \times d}$, the inequality $|\mathbf{y} - \mathbf{z}|_2 \leq \epsilon$ holds, where $\epsilon$ is a very small positive number. **Lemma 1**: Let $M$ represent the maximum number of activable paths, with each pair of operations satisfying the zero-order condition. Using $M$ distinct expectations and variances, it is possible to approximate all combinations (i.e., $2^M$). Lemma 1 guarantees that we can track the combination containing $i$ meta-paths with at least $M$ iterations. **Given that the number of iterations significantly exceeds $M$, the relative importance of the meta-paths can be learned during the search stage.** Below is the proof of Lemma 1: Let ${\mathbf{y}}_{p_y(y)} = f(\mathbf{x})$, ${\mathbf{z}}_{p_z(z)} = g(\mathbf{x})$, and ${\mathbf{x}} \sim p_{x(x)}$. For the case $M=1$, the expectations of $\mathbf{y}$ and $\mathbf{z}$ can be expressed as follows: $$ \begin{aligned} {\\mathbb E}[{\\mathbf y}]&={\\mathbb E}[f\left({\\mathbf x}\right)]=\int p_{{\\mathbf x}}({\\mathbf x}) f({\\mathbf x}) {\mathrm d}{\\mathbf x} \end{aligned} $$ $$ \begin{aligned} {\\mathbb E}[{\\mathbf z}]&={\\mathbb E}[g\left({\\mathbf x}\right)]=\int p_{{\\mathbf x}}({\\mathbf x}) g({\\mathbf x}) {\mathrm d}{\\mathbf x} \end{aligned} $$ According to the zero-order condition, $f(\mathbf{x}) \approx g(\mathbf{x})$. Since $p(\mathbf{x})$ is the same for both $\mathbf{y}$ and $\mathbf{z}$, it follows that $\mathbb{E}[\mathbf{y}] \approx \mathbb{E}[\mathbf{z}]$. Next, we prove that $Var[\mathbf{y}] \approx Var[\mathbf{z}]$. Note that $Var[\mathbf{y}] = \mathbb{E}\left[\mathbf{y}^{2}\right] - \left(\mathbb{E}[\mathbf{y}]\right)^{2}$ and $Var[\mathbf{z}] = \mathbb{E}\left[\mathbf{z}^{2}\right] - \left(\mathbb{E}[\mathbf{z}]\right)^{2}$. Thus, it suffices to prove that $\mathbb{E}\left[\mathbf{y}^{2}\right] \approx \mathbb{E}\left[\mathbf{z}^{2}\right]$. This can be similarly demonstrated as follows: $$ \begin{aligned} {\\mathbb E}\left[{\\mathbf y}^{2}\right]&=\int p_{{\\mathbf y}}({\\mathbf y}) {\\mathbf y}^{2} {\mathrm d} {\\mathbf y} = \int p_{{\\mathbf x}}({\\mathbf x}) f^{2}({\\mathbf x}) {\mathrm d} {\\mathbf x} \end{aligned} $$ $$ \begin{aligned} {\\mathbb E}\left[{\\mathbf z}^{2}\right]&=\int p_{{\\mathbf z}}({\\mathbf z}) {\\mathbf z}^{2} {\mathrm d} {\\mathbf z} = \int p_{{\\mathbf x}}({\\mathbf x}) g^{2}({\\mathbf x}) {\mathrm d} {\\mathbf x} \end{aligned} $$ According to the zero-order condition, we have $Var[\mathbf{y}] \approx Var[\mathbf{z}]$. For the case of $M=2$, when both paths are selected, the output becomes $\mathbf{y} + \mathbf{z}$, and its expectation can be written as: $$ \begin{aligned} {\\mathbb E}[{\\mathbf y} + {\\mathbf z}] &= {\\mathbb E}[{\\mathbf y}] + {\\mathbb E}[{\\mathbf z}] \approx 2{\\mathbb E}[{\\mathbf y}] \end{aligned} $$ The variance of $\mathbf{y} + \mathbf{z}$ is: $$ \begin{aligned} Var[{\\mathbf y} + {\\mathbf z}] \approx Var [2{\\mathbf y}] = 4 Var[\\mathbf y] \end{aligned} $$ Thus, there are two types of expectations and variances: $\mathbb{E}[\mathbf{y}]$ and $Var[\mathbf{y}]$ for ${\mathbf{y}, \mathbf{z}}$, and $2\mathbb{E}[\mathbf{y}]$ and $4Var[\mathbf{y}]$ for ${\mathbf{y} + \mathbf{z}}$. Similarly, for the case where $M \in [1, K]$, there will be $M$ types of expectations and variances.