PageRank Bandits for Link Prediction

Thank you for your constructive feedback and precious time. Here, we try our best to address the questions and concerns in the form of Q&A. Similar questions raised by other reviewers are addressed in the Global Response. Additional content has been added to the 1-page PDF to better address reviewers' questions.

---

Q1: Clarity of descriptions

Thank you for your suggestion, and we will divide Section 4 into three subsections to introduce exploitation, exploration, and PageRank, respectively.

---

Q2: Details for reproducing OGBL results

We are happy to provide a script to reproduce the results of PRB in the offline link prediction setting. Please refer to our newly submitted anonymous link for additional supplementary codes and hyperparameter settings.

We also provide detailed experimental set-ups for all our experiments including both online and offline settings on Global Response Q2.

For all graph-based baselines, we used the source code and followed the same hyper-parameter settings from [1] (source code link provided in the paper). The results of the baselines are sourced from Table 2 of [1]. These baseline results are also commonly used in other works such as [2,3].

---

Q3: Citations about pseudo-regret metric

Our pseudo-regret metric is inspired by contextual bandits literature such as neural contextual bandits [4] and neural active learning [5] to evaluate sequential decision-making. The pseudo-regret metric is a widely used evaluation metric in the literature of contextual bandits [7,8].

---

Q4: Relation of statement 179-180 to PRB

As stated in Section 4, PRB incorporates a PageRank component to address Line 8 in Algorithm 1 of the manuscript. To mitigate the additional time and space complexity introduced by this component, we aim to adapt methods that can efficiently solve the PageRank problem. The statement in Lines 179-180 highlights that Line 8 in Algorithm 1 can be accelerated and solved efficiently by using a PageRank variant, such as the one proposed by [6], thereby ensuring the overall efficiency of PRB.

---

Q5: Clarity for node classification algorithm

Thanks for your valuable suggestions. We've drawn a figure with an example (Figure 1 in Global PDF) to illustrate the process of transforming the node classification to the link prediction problem. Then, we use the method described in Lines 187-189 to generate contexts for supernode. With this transformation, we can directly apply PRB to this problem and predict the links between serving nodes and super nodes.

---

Q6: Offline node classification accuracy

Regarding the reviewer's question, we evaluated the accuracy performance of the PRB against three bandit-based baselines in the offline node classification task.

In this experiment setup, we randomly split nodes on each dataset into 60%/20%/20% for training/validation/testing. We follow the same setup for each method in Global Response Q2. We then evaluate the accuracy of each trained model on the testing set. The accuracy of the test set was assessed over 10 runs to ensure robustness.

The results are shown in the following table. PRB demonstrates the overall best accuracy performance. This indicates that the low regret of PRB's performance can translate into high-level accuracy.

We also provide the related code in our newly submitted anonymous link.

---

Q7: Difficulty of large graphs

The reviewer's observation is correct. The more target candidate nodes there are, the more options are needed to exploit and explore, increasing the task's difficulty. This mirrors real-world decision-making, where having more options makes it harder to choose the best one. Importantly, our theoretical analysis shows that the cumulative regret of PRB grows sublinearly with the size of the candidate node pool. However, existing graph-based methods may also suffer from the increasing complexity of the graph despite not providing a theoretical performance upper bound for analysis.

Moreover, to better show the scalability of our method, we recorded the inference time of PRB and competitive baselines in both online and offline settings.

Table 3 in Global PDF reports the inference time (one round in seconds) of bandit-based methods on three datasets for online link prediction. Although PRB takes a slightly longer time, it remains in the same order of magnitude as the other baselines. We adopt the approximated methods from [6] for the PageRank component to significantly reduce computation costs while ensuring good empirical performance.

Table 4 in Global PDF reports the inference time (one epoch of testing in seconds) of graph-based methods on three datasets for offline link prediction. PRB is faster than SEAL and shows competitive inference time as compared to other baselines.

---

References
[1] Neural Common Neighbor with Completion for Link Prediction. ICLR 2024
[2] Graph neural networks for link prediction with subgraph sketching. ICLR 2023
[3] Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. NeurIPS 2021
[4] EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits. ICLR 2022
[5] Neural Active Learning with Performance Guarantees. NeurIPS 2021
[6] Everything Evolves in Personalized PageRank. WWW 2023
[7] Neural contextual bandits with UCB-based exploration. ICML 2020
[8] Improved algorithms for linear stochastic bandits. NeurIPS 2011

Thank you very much for your constructive feedback and precious time. Here, we will try our best to address the questions and concerns in the form of Q&A. Since some of your questions are also raised by other reviewers, we have moved some answers to the Global Response. We also include additional content in the 1-page PDF file of Global Response to better answer reviewers' questions.

---

Q1: Experiment setting

Please refer to Global Response Q2, where we provide the setups for both online and offline link prediction experiments and report the hyperparameter settings for PRB and all baselines.

---

Q2: Time and space complexity

Time Complexity: Let $n$ be the number of nodes, $t$ be the index of the current round of link prediction, $k$ be the number of target candidate nodes, $d$ be the number of context dimensions, and $p$ be neural network width.

Online Setting: Let $m_t$ be the number of edges at round $t$. In the setting of online link prediction, the time complexity of PRB is $O(kdp + m_t k)$, where the first term is the cost of calculating the exploitation-exploration score for each candidate node and the second term is the cost of running PageRank, following [1]. The space complexity is $O(n + m_t)$ to store node weights and edges.

Offline Setting: Let $m$ be the number of edges in the testing dataset. Let $F$ be the number of target links to predict. Then, the inference time complexity of PRB for $F$ links is $O(ndp) + \tilde{O}(mF)$. The first term is the cost of calculating the exploitation-exploration score for each node. The second term is the cost of PageRank [1]. The comparison with existing methods is listed in the following table:

$l'$ is the number of hops of the subgraph in SEAL and $h$ is the complexity of hash operation in BUDDY.

Space Complexity: The space complexity of PRB is $O(nd + m)$ to store the context vector for each node and run PageRank.

Moreover, we recorded the inference time of PRB and competitive baselines in both online and offline settings.
The following table reports the inference time (one round in seconds) of bandit-based methods on three datasets for online link prediction. Although PRB takes a slightly longer time, it remains in the same order of magnitude as the other baselines. We adopt the approximated methods from [1] for the PageRank component to significantly reduce computation costs while ensuring good empirical performance.

The following table reports the inference time (one epoch of testing in seconds) of graph-based methods on three datasets for offline link prediction. PRB is faster than SEAL and shows competitive inference time as compared to other baselines.

---

Q3: Choice of transition matrix and $\alpha$

Transition matrix: In our experiment, the transition matrix $P$ is computed as $D^{-1}A$, where $A$ is the adjacency matrix and $D$ is the degree matrix of the graph, following existing works such as [1,2].

Choice of $\alpha$: For our experimental implementation, we conducted a grid search for $\alpha$ over {0.1, 0.3, 0.5, 0.85, 0.9}, as shown in Figure 2 of Global PDF. We found that $\alpha = 0.85$ achieves the best empirical performance, so we set $\alpha = 0.85$ for PRB in all experiments. Additionally, we would like to point out that in existing works of PageRank [1,2,3,4,5], the decay factor $\alpha$ is typically set to 0.85, which has demonstrated great empirical success.

---

References
[1] Everything Evolves in Personalized PageRank. WWW 2023
[2] Fast and accurate random walk with restart on dynamic graphs with guarantees. WWW 2018
[3] Tpa: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. ICDE 2018
[4] Temporal pagerank. ECML PKDD 2016
[5] Efficient pagerank tracking in evolving networks. ACM SIGKDD 2015

We sincerely thank the reviewer for your constructive feedback and precious time. Here, we try our best to address the questions and concerns in the form of Q&A. Since some of your questions are also raised by other reviewers, we have moved some answers to the Global Response. We also include additional content in the 1-page PDF file of the Global Response to better answer reviewers' questions.

---

Q1: Related work of temporal Link prediction

Thank you for pointing out these important relevant works. We have conducted a related literature review and included additional experiments to compare PRB with temporal graph neural networks. We appreciate it if the Reviewer could help to provide some related work that we may miss.

Related Work. Representation learning on temporal graphs for link prediction has been widely studied in recent years to exploit patterns in historical sequences, particularly with GNN-based methods [1,2,3,4,5,6]. However, these approaches are still conventional supervised-learning-based methods that chronologically split the dataset into training and testing sets. Specifically, these methods train a GNN-based model on the temporal training data and then employ the trained model to predict links in the test data. In contrast, we formulate link predictions as sequential decision-making, where each link prediction is made sequentially. In each round of link prediction, after making the prediction, the learner directly receives feedback (i.e., whether the prediction is correct or not). The learner can then leverage this feedback (reward) to update the model for the next round of link prediction. Therefore, these conventional methods cannot directly apply to the setting of online link predictions that we focus on.

As stated in our later reply to Q4 (please also refer to Global Response Q1), compared to conventional graph-based approaches for link prediction, our bandit-based method offers the following three advantages: (1) Adaptation over time; (2) Balancing exploitation and exploration; and (3) Theoretical performance guarantee. Link prediction methods on temporal graphs may adapt their models by incorporating timestamp information, but balancing exploitation and exploration and providing a theoretical performance guarantee are two unique advantages of our method.

We will include all of these discussions in our revised version to broaden the scope of our method.

Additional Experiment. To further demonstrate the effectiveness of our approach, we adapted PRB to the temporal link prediction setting by training it on the training dataset and only making predictions on the test dataset. Following the same setup for temporal link prediction as in [1], we chronologically split the dataset with ratios of 70%-15%-15% for training, validation, and testing. Since PRB is not designed to incorporate link features, we selected three datasets without available link features: UCI, Enron, and LastFM. The setup of PRB follows the setup described in Global Response Q2. We compared PRB against 10 baselines: JODIE, DyRep, TGAT, TGN, CAWN, EdgeBank, TCL, GraphMixer, DyGFormer [2], and FreeDyG [1]. Detailed descriptions of each baseline can be found in [1].

The results are reported in Table 2 of Global PDF, with baseline results sourced from [1].

PRB outperforms other temporal graph-based methods, demonstrating its unique advantage in balancing exploitation and exploration. We will include the additional conducted experiments in our paper to broaden the applicability of PRB.

To reproduce the results, please find the codes in our newly submitted anonymous link.

---

Q2: Number of clusters in node classification

We've drawn a figure (Please refer to Figure 1 of Global PDF), to illustrate the process of transforming the node classification to the link prediction problem, where we use one supernode to represent each cluster. Therefore, the number of classes will be the number of supernodes, which is prior knowledge in our problem setting. Then, we use the method described in Lines 187-189 to generate contexts for the supernode. With this transformation, we can directly apply PRB to this problem and predict the links between serving nodes and supernodes.

---

Q3: Choice of $\alpha$

In the experiments, we conducted a grid search for $\alpha$ over {0.1, 0.3, 0.5, 0.85, 0.9}, as shown in Figure 2 of Global PDF. We found that $\alpha = 0.85$ achieves the best empirical performance, so we set $\alpha = 0.85$ for PRB in all experiments. Additionally, we would like to point out that in existing works of PageRank [7,8,9], the decay factor $\alpha$ is typically set to 0.85, which has demonstrated great empirical success.

---

Q4: Motivation of solving link predictions in the contextual bandit setting

Please refer to Global Response Q1 for detailed answers, where we elaborate on three advantages of solving link predictions via contextual bandits: (1) PRB can adapt over time by leveraging the feedback from each round; (2) PRB can balance exploitation and exploration in sequential link predictions; and (3) PRB has a theoretical performance guarantee.

---

Reference

[1] FreeDyG: Frequency Enhanced Continuous-Time Dynamic Graph Model for Link Prediction. ICLR 2024
[2] Towards better dynamic graph learning: New architecture and unified library. NeurIPS 2023
[3] Do we really need complicated model architectures for temporal networks? ICLR 2023
[4] Inductive representation learning on temporal graphs. ICLR 2020
[5] Inductive representation learning in temporal networks via causal anonymous walks. ICLR 2021
[6] Temporal graph networks for deep learning on dynamic graphs. arXiv 2020
[7] Everything Evolves in Personalized PageRank. WWW 2023
[8] Fast and accurate random walk with restart on dynamic graphs with guarantees. WWW 2018
[9] Temporal pagerank. ECML PKDD 2016

We would like to thank the reviewer for your constructive feedback and precious time. Here, we try our best to address the questions and concerns in the form of Q&A. Since some of your questions are also raised by other reviewers, we have moved some answers to the Global Response. We also include additional content in the 1-page PDF file of the Global Response to better answer reviewers' questions.

---

Q1: Advantages of solving link predictions in the contextual bandit setting

Please refer to Global Response Q1 for detailed answers, where we elaborate on three advantages of solving link predictions via contextual bandits: (1) PRB can adapt over time by leveraging the feedback from each round; (2) PRB can balance exploitation and exploration in sequential link predictions; and (3) PRB has a theoretical performance guarantee.

---

Q2: Experiment setting

Please refer to Global Response Q2, where we provide the setups for both online and offline link prediction experiments and report the hyperparameter settings for PRB and all baselines.

---

Q3: Ablation study of bandits and PageRank

We've conducted the ablation study for the bandit component and PageRank component of PRB, respectively. The result is placed in Appendix A of the original manuscript (Lines 518-525, Figure 6).

In Figure 6 of the original manuscript, we compare the performance of PRB with EvePPR (PageRank component) and EEnet (bandit component). On one hand, PRB significantly outperforms PageRank, because PRB can integrate the exploitation and exploration of node context in sequential link predictions to boost the performance. On the other hand, PRB surpasses Bandits, as PRB can leverage the graph's structure and connectivity through enhanced PageRank. Overall, PRB consistently achieves lower regrets compared to both PageRank and Bandits, demonstrating the effectiveness of combining exploitation-exploration trade-off with PageRank.

---

Q4: Inference time comparison

We recorded the inference time of PRB and competitive baselines in both online and offline settings.

The following table reports the inference time (one round in seconds) of bandit-based methods on three datasets for online link prediction. Although PRB takes a slightly longer time, it remains in the same order of magnitude as the other baselines. We adopt the approximated methods from [1] for the PageRank component to significantly reduce computation costs while ensuring good empirical performance.

The following table reports the inference time (one epoch of testing in seconds) of graph-based methods on three datasets for offline link prediction. PRB is faster than SEAL and shows competitive inference time as compared to other baselines.

---

Other Suggestions

We sincerely thank the reviewer for detailed and valuable suggestions. We will revise the manuscript by integrating more experiment settings into the experiment section, enlarging the font size of the figures in the Appendix, and emphasizing the advantages of combining PageRank with Bandits.

---

Reference
[1] Everything Evolves in Personalized PageRank. WWW 2023

Dear Reviewers,

We would like to take this opportunity to thank you all for your constructive feedback and detailed comments on our work. We have organized the codes into an anonymous link to support reproducing the experimental results, including:

1. The codes for reproducing results in offline link prediction for PRB and all baselines.
2. The codes for reproducing results in node classification accuracy.
3. The codes for reproducing results in temporal link predictions.

As external links are not allowed to be directly shown on Rebuttal according to NeurIPS policy, we have submitted the anonymous code link to the Area Chair (AC) for anonymous review. The code link will be visible to all reviewers once we receive approval from the AC.

Thank you for your understanding, and we appreciate the AC's time and efforts in reviewing.

We would also like to provide a short summary of the uploaded Global PDF, which includes:

1. [Figure 1] illustrates the process of transforming node classification to link prediction.
2. [Figure 2] shows the ablation study for $\alpha$.
3. [Table 1] provides the node classification accuracy in the offline setting.
4. [Table 2] reports the average precision for temporal link prediction.
5. [Tables 3-4] show the inference time of PRB in both online and offline settings.
6. [Tables 5-6] provide the time and space complexity of PRB.

Thank you once again, and please let us know if you have any questions.

Best regards,
The Authors