Bag of Features: New Baselines for GNNs for Link Prediction

We express our gratitude to the reviewer for the insightful and constructive feedback. In light of your valuable comments, as well as those from other reviewers, we are revising our paper. We are confident that these revisions have substantially enhanced the quality of our work. We hope that our responses will be sufficiently informative for you to reconsider assessing a higher rating for the revised paper.

$**Q1. Table Discrepancy.**$

Thanks for sharing this point. For OGB-Collab, we used the results given in [1], a review paper that compares the performances of recent Graph Neural Networks (GNNs) in the link prediction task. All the reported performances are extracted from this source. On the OGB-Leaderboard, we observed that GraphSage's performance was suboptimal, so we opted for another configuration with improved hyperparameters.

In response to Reviewer Dape's request, we included additional GNN baselines in Table 5. These supplementary results are sourced from [1], specifically Table 2 in the reference.

[1] Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J. and Yin, D., 2023. Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking. arXiv preprint arXiv:2306.10453.

$**Q2. Extra Datasets:**$ Tables 3 and 4 follow the methods of (Zhao et al., 2022) and (Guo et al., 2022), respectively. To enhance comprehensiveness, the authors should consider adding Facebook and OGB-DDI to Table 3, and Cora, Citeseer, and DBLP to Table 4.

Thank you very much for this suggestion. These two papers use different splits (70/10/20 and 85/5/10) so we did not add our CORA/CITESEER results from Table 3 to Table 4 not to cause any confusion. We add these results to the appendix with different splits (Table 9). We will try to complete the experiments for the suggested datasets (FACEBOOK, DBLP, and OGB dataset) before the rebuttal deadline, and let you know the results.

$**Q3. Heterophilic Datasets.**$

Thank you very much for this great suggestion. We will add experiments for some heterophilic datasets before the rebuttal deadline, and let you know the results.

$**Q4. Ablation Study for Individual Features.**$

Thank you very much for this suggestion. We added the ablation study table for feature importance in the appendix (Table 7)

Please let us know if you have further questions. Thank you very much again for your valuable time and feedback.

We express our gratitude to the reviewer for the insightful and constructive feedback. In light of your valuable comments, as well as those from other reviewers, we are revising our paper. We are confident that these revisions have substantially enhanced the quality of our work. We hope that our responses will be sufficiently informative for you to reconsider assessing a higher rating for the revised paper.

$**W1. Novelty:**$ Novelty is limited. Most methods are ordinary feature extraction tricks.

Thank you very much for sharing this concern. We wish to emphasize that the novelty of our work lies in substantiating that traditional feature engineering methods can stand shoulder-to-shoulder with cutting-edge GNN models. We argue this based on consistently outperforming powerful GNN methods on various datasets, which are published in top conferences. This supports our claim that our Bag of Features model is a practical and effective alternative to these computationally intensive models.

$**W2/Q1. Extra OGB experiments:**$ Experiments are not conducted on OGB datasets other than collab.

We are working on additional OGB experiments. We hope to provide the results before the rebuttal deadline.

$**Q2. XGBoost vs. other ML classifiers:**$ This work used XGBoost as the ML model. Did you conduct ablation study for it? For example, use Logistic regression and SVM instead ?

Thank you very much for this suggestion. We added the ablation study table reporting the performance of several ML classifiers (including Naive Bayes and Logistic Regression) in the appendix (Table 11). We will add other ML classifiers soon.

Please let us know if you have further questions. Thank you very much again for your valuable time and feedback.

We express our gratitude to the reviewer for the insightful and constructive feedback. In light of your valuable comments, as well as those from other reviewers, we are revising our paper. We are confident that these revisions have substantially enhanced the quality of our work. We hope that our responses will be sufficiently informative for you to reconsider assessing a higher rating for the revised paper.

$**W1: Novelty:**$ The paper's novelty appears constrained. The significance of graph structural features in the realm of link prediction has been previously underscored by several studies, such as [1][2][3].

Thank you very much for bringing these references to our attention. We added these references to our paper. We wish to emphasize that the novelty of our work lies in substantiating that traditional feature engineering methods can stand shoulder-to-shoulder with cutting-edge GNN models. We argue this based on consistently outperforming powerful GNN methods on various datasets, which are published in top conferences. This supports our claim that our Bag of Features model is a practical and effective alternative to these computationally intensive models.

$**W2. Sota Baselines:**$ The evaluation omits several critical baselines that similarly exploit graph structural features. Notably absent are BUDDY, Neo-GNN, NCN, NCNC, and NBFNet.

By using reference [1], we give the performance comparison of these GNN models with our model. For OGBL-COLLAB, we report Hits@50 results below, and add them into our accuracy table (Table 5). However, for CORA, CITESEER, and PUMED datasets, the reported performances use different splits. Considering our model uses less training data, it produces highly competitive results with these cutting edge GNN models. Since the experimental setups are different, we opt out these performances in our accuracy table in the main text, however we added this table to appendix (Table 7).

OGBL-COLLAB | Model | Hits@50 | |---------|--------------| | SEAL | 63.37 ± 0.69 | | BUDDY | 64.59 ± 0.46 | | Neo-GNN | 66.13 ± 0.61 | | NCN | 63.86 ± 0.51 | | NCNC | 65.97 ± 1.03 | | NBFNet | OOM | | Ours | 76.50 ± 0.27 |

| Model | Split | CORA | CITESEER | PUBMED | |----------|------------|--------------|--------------|--------------| | BUDDY | 85:05:10 | 95.06±0.36 | 96.72±0.26 | 98.20±0.05 | | Neo-GNN | 85:05:10 | 93.73±0.36 | 94.89±0.60 | 98.71±0.05 | | NCN | 85:05:10 | 96.76±0.18 | 97.04±0.26 | 98.98±0.04 | | NCNC | 85:05:10 | 96.90±0.28 | 97.65±0.30 | 99.14±0.03 | | NBFNet | 85:05:10 | 92.85±0.17 | 91.06±0.15 | 98.34±0.02 | | Ours | 70:10:20 | 94.54±0.30 | 95.01±0.35 | 94.73±0.15 |

[1] Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J. and Yin, D., 2023. Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking. arXiv preprint arXiv:2306.10453.

$**W3. Extra OGB experiments:**$

We are working on additional OGB experiments. We hope to provide the results before the rebuttal deadline. We will let you know when we have the results.

$**W4. Ablation Study.**$ There are no ablation studies about the importance of each feature.

Thank you very much for this suggestion. We added the ablation study table reporting the impact of each individual feature in the appendix (Table 7), which you can see in our revision.

$**W5. No Code:**$

Thanks for letting us know about the mistake in the link. We've fixed it in the paper, and you can find the correct link below. If you have any more questions about our code, please let us know. https://github.com/workrep20232/LinkPrediction

$**W6. Using original features for node similarity?**$ Using the original feature to measure the node similarity might be unreasonable.

Thanks for raising this concern. Our primary objective with our approach is to provide a highly generalized method for gathering all relevant similarity/dissimilarity information between node pairs and leveraging these features in the task of link prediction. You correctly point out that the efficacy of domain features may vary depending on the dataset's nature, whether it exhibits homophily or heterophily. We acknowledge that, in the PHOTO and COMPUTERS datasets, domain features did not contribute substantially to performance. In contrast, for CORA, CITESEER, and PUBMED datasets, the inclusion of domain features notably enhanced performance. It's noteworthy that incorporating these features didn't compromise performance across all datasets; instead, it consistently improved performance across the board. You can check our Feature Importance table (Table 7) in the appendix.

Please let us know if you have further questions. Thank you very much again for your valuable time and feedback.

Thank you very much for your questions.

1. Different data splits.

Yes, in our original submission, we used the performances reported in two very recent papers' results as baselines [1,2], but they were using different data splits. So, we had one table for Cora/Citeseer/PubMed (70:10:20), and Photos/Computers (85:5:10). However, with the request of Reviewers rEua and in5m, we added these comparisons with different splits for Cora/Citeseer/PubMed. In our original submission, we did not want to cause any confusion by giving two different results for the same datasets. To avoid the confusion, we give these results in the appendix. If needed, we can repeat the experiments with new splits, and report them in the appendix.

2. Scalability Issue

We believe scalability is one of the advantages of our simple approach. We give the details of our runtime and computational complexities in Experiments section. The computational complexities of our similarity indices are $\mathcal{O}(|V|.k^3)$ where $|V|$ is the total number of nodes and $k$ is the maximum degree in the network. For a large network, the computational time needed for our approach is much less than the training time for a message passing GNN. Therefore, our approach provides a good alternative to common methods when dealing with large networks.

3. OGB Datasets.

Unfortunately, due to unforeseen circumstances, we could not complete OGBL-PPA experiments yet. We will add the results to the paper when we have it. However, in OGBL-COLLAB, we outperform all the existing results with our simple model. We are expecting a competitive result with OGB Leaderboard in OGBL-PPA dataset considering its high performance in all other (both homophilic and heterophilic) datasets, too.

Thank you very much for your valuable time and feedback. Please let us know if you have further questions.

[1] Li, Juanhui, Harry Shomer, Haitao Mao, Shenglai Zeng, Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. "Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking." arXiv preprint arXiv:2306.10453 (2023).

[2] Guo, Zhihao, Feng Wang, Kaixuan Yao, Jiye Liang, and Zhiqiang Wang. "Multi-scale variational graph autoencoder for link prediction." In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, pp. 334-342. 2022.

1. Different Splits

We want to clarify that our Table 3 is all 70:10:20 using baselines from (Guo et all 2022). We are not using different split there.

For Tables 8 and 9, we are adding new GNN baselines by using the performances from (Li et al, 2023) which uses 85:05:10 split. If your question is about these two tables, we are sorry that we misunderstood your concern. We will add the experiments with 85:05:10 splits for Cora/Citeseer/PubMed datasets. Since we already have the features, it should take only a couple of hours. We'll get back to you soon.

2. OGB Datasets

Unfortunately, we could not finish the OGB experiments in time. Considering the size of these datasets, we had to use our university clusters. We were expecting to finish one of these datasets in time: OGBL-PPA. We were able to get the features, however, we had a problem with running ML classifiers.

Nonetheless, we were not expecting to finish all three OGB datasets in one week considering their sizes. Our structural features are always the same, but domain features need to be customized and it should be tailored for each dataset. For PPA, we were able to do it, but since OGBL-Citation2 and OGBl-DDI are completely different formats, we need time to extract meaningful features from the node and edge features provided.

Again, we want to underline that our aim is not to promote feature engineering models but to show that current GNN performances are not far from traditional methods, verifying the recent theoretical studies. Thank you very much for your time and feedback.

We express our gratitude to the reviewer for the insightful and constructive feedback. In light of your valuable comments, as well as those from other reviewers, we are revising our paper. We are confident that these revisions have substantially enhanced the quality of our work. We hope that our responses will be sufficiently informative for you to reconsider assessing a higher rating for the revised paper.

$**W1\ - \ Novelty:**$

Thank you very much for sharing this concern. We wish to emphasize that the novelty of our work lies in substantiating that traditional feature engineering methods can stand shoulder-to-shoulder with cutting-edge GNN models. We argue this based on consistently giving shoulder-to-shoulder performance with powerful GNN methods on various datasets, which are published in top conferences. This supports our claim that our Bag of Features model is a scalable and effective alternative to these computationally intensive models.

The key reason behind our success is revealed in our ablation study. Our approach of effectively feeding both structural and domain features in our ML classifier has proven to be crucial. The study confirms that, in most datasets, using only structural or domain features leads to lower performance. However, combining them effectively significantly boosts the overall performance of our model.

$**W2. GNN comparison for Other Graph Learning Tasks**$

Thank you for raising this issue. It's accurate to observe that our focus in this manuscript centers specifically on the challenge of link prediction. The decision to narrow our attention to this particular task within graph representation learning was primarily influenced by space limitations. In a distinct investigation, we employed similar techniques to compare Graph Neural Networks (GNNs) with traditional feature extraction in the context of a node classification task. Across six benchmark datasets in that study, we outperformed all state-of-the-art GNNs. While our findings with the OGBGN dataset did not outperform the OGB leaders, but gave highly competitive results. To preserve anonymity, we refrain from providing additional details.

Given the inherent differences between node classification and link prediction tasks, the employed feature extraction methods also diverge significantly. Consequently, we opted to present these two studies in separate papers. Nevertheless, the outcomes from both studies imply that existing GNNs do not exhibit a substantial superiority over traditional feature engineering models. It is crucial to clarify that our intention in this paper is not to advocate for the adoption of feature engineering methods moving forward. Instead, we aim to document that current GNN models do not demonstrate a significant advantage over them. This revelation should illuminate the current state of affairs with GNNs and motivate researchers to advance and refine these models further.

$**W3. SOTA Baselines:**$ The experimental part of this article does not compare with state-of-the-art GNN methods, such as NBFNet[1] and Seal[2].

Thanks for pointing out these baseline references. It's important to mention that SEAL [2] has already been given in Table 3 - row 4. For NBFNet, we report the result for a different split of 85:5:10 below by using reference [3]. However, since we use a different split for Table 3 (70:10:20), we opted not to include NBFNet in Table 3. On the other hand, with the suggestion of Reviewer Dape, we added several recent GNN baselines to our Table 5, and Table 8. We also acknowledged this reference in our related work section.

The specifics of AUC performances are outlined in the table provided below. | | Split | CORA | CITESEER | PUBMED | |------|------------|-------|----------|--------| | SEAL | 70:10:20 | 92.55 | 85.82 | 96.36 | | NBFNet | 85:05:10 | 95.60 | 92.30 | 98.30 | | Ours | 70:10:20 | 94.54 | 95.01 | 94.73 |

[3] Li, J., Shomer, H., Mao, H., Zeng, S., Ma, Y., Shah, N., Tang, J. and Yin, D., 2023. Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking. arXiv preprint arXiv:2306.10453.

Please let us know if you have further questions. Thank you very much again for your valuable time and feedback.