PageRank Bandits for Link Prediction

Summary

The authors propose PRB, a new method that blends exploration, exploitation from previous neural bandit literature into an architecture that effectively considers graph connectivity in order to boost the performance for both the node classification and link prediction tasks. The authors demonstrate the soundness of the new model with proofs and mathematical reasoning, which also distinguishes it from previous neural bandit research. Additionally, the authors verify the effectiveness of the model by measuring it's performance in online and offline link prediction along with node classification.

Strengths

* Well-written paper that explains PRB's functionality and also highlights the difference between the problem solved by this paper and other neural bandit papers. * PRB empirically tested against SOTA baselines across online and offline link prediction and tested on node classification.

Weaknesses

* Clarity of descriptions is sometimes more dense than necessary, this could be due to the page limitations. For example, Section 4 can be divided into subsections that distinguishes whether it is describing the exploration, exploitation, graph connectivity/bandit princple in PageRank. More examples are determined line-by-line in the questions section of this review. * Lack of inclusion of code for reproducing offline link prediction results on the OGBL Datasets in supplementary material. This is the largest contributing factor to the score provided in this review, further explanation about this concern is detailed in 'Concerns about PRB performance' within the Questions section of this review.

Questions

* Line 135: Are there specific citations to contextual bandits literature that inspires the proposed pseudo-regret metric? * Line 179-180: This statement is certainly interesting, but how does it relate to PRB directly? Concerns about Clarity: ------------------------------ * Line 181-193: Do the super nodes allow PRB to extend to the node classification? From node classification, is PRB then updated to handle link prediction by considering the connections between serving nodes and super nodes? This seems to be the case, since the papers moves from the initial definition of PRB's neural bandit-style architecture onto PRB's applications within the link prediction and node classification tasks. It is difficult to tell without more context or definitions on the relation between super nodes and PRB. Additionally, this paragraph reads much like a mathematical proof, which is good to represent individual components within the system. However, a diagram on how PRB is applied to the node classification task and then how PRB is transformed for the link prediction task would provide clarity through a visual example. Concerns about PRB performance: ---------------------------------------------- * Given how neural bandit models are applied to online scenarios, I understand that the metric of choice for testing neural-bandit methods is regret (or pseudo-regret for PRB). Is it possible to test the accuracy of PRB for offline node classification? This is not necessarily a concern, but offline node classification results could provide insight into whether PRB's performance with pseudo-regret can translate to high-levels of accuracy. * As mentioned in Lines 242-243: the larger the input graph, the more difficult the link prediction task is for PRB. Does that mean that the more links which PRB is required to predict, the more components of the graph PRB is then required to exploit and explore? Is there another reason why neural bandit models have difficulty with larger graphs? Do these difficulties mean neural bandits suffer: when performing link prediction and node classification, with time and space complexity limiitations, or something else? * Considering Lines 242-243, along with PRB outperforming all other tested models, the lack of a script in the current supplementary materials to test how well PRB performs with the Hits@K metric on the much larger ogbl datasets is concerning. I kindly request the authors provide a script for replicating the results detailed in Table 3 for PRB and another model such as BUDDY, along with each model's recommended hyperparameters for the ogbl datasets.

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

2

Limitations

Yes.

Summary

This paper introduces PRB (PageRank Bandits), a novel algorithm for link prediction in graph learning that combines contextual bandits with PageRank to balance exploitation and exploration. Framing link prediction as a sequential decision-making process, the paper provides a new reward formulation and theoretical performance guarantees. PRB demonstrates superior performance over traditional methods in both online and offline evaluations.

Strengths

1. The integration of PageRank with contextual bandits is a compelling concept, and the motivation behind the proposed PRB algorithm is clear. 2. Regret analysis validates the PRB algorithm's efficacy, demonstrating that its cumulative regret approaches sublinear growth. 3. The PRB algorithm exhibits robust performance across real-world tasks, achieving impressive outcomes in both online and offline settings. 4. The organization of this paper is well-structured and straightforward, facilitating ease of comprehension.

Weaknesses

1. The paper does not provide detailed descriptions of experimental settings, such as model hyperparameter configurations and optimizer choices. 2. The complexity analysis of the PRB algorithm, including both time and space complexity, is not thoroughly discussed.

Questions

1. Please respose the above weaknesses first. 2. In practical experiments, how are the transition matrix and the parameter $\alpha$ chosen in the PRB algorithm?

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

3

Limitations

The authors discussed the limitations in the Appendix.

Summary

This paper reformulates link prediction as a sequential decision-making process and propose a algorithm that combines contextual bandits with PageRank for collaborative exploitation and exploration. The experiments validate the effectiveness of the method.

Strengths

1. The problem is interesting and the paper is organized well. 2. The experiments show the effectiveness of the method.

Weaknesses

1. In the introduction, some recent works use GNN models to investigate the graph embedding in temporal networks and the embedding also evolves over time and is applicable to various downstream tasks. However, the relevant works are missing. 2. For the node classification, how to pre-determine the number of clusters? 3. For the PageRank, whether the hyperparameter $\alpha$ need to be learned, and how to determine the best value? 4. Link prediction is well studied problem, why do we really need bandits to study this problem? The proposed reason is not very convincing.

Questions

See above.

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

See above.

Summary

In light of the dynamic and evolving nature of real-world graphs, PageRank Bandits is proposed to make the prediction task consistently meet the context and adapt over time. Both experimental results and theoretical analysis are solid. But the paper organization is not so well.

Strengths

--It is novel to combine contextual bandits with PageRank to find a better tradeoff between exploitation and exploration with graph connectivity. --Both contextual bandits and link prediction models are listed in related work. Moreover, both kinds of methods are compared as baselines in the experiments. --Comprehensive experiments are conducted to verify PageRank Bandits’ effectiveness and ablation study is also done to indicate that the model design is reasonable. --Theoretical analysis is also provided in the paper and the appendix to show its feasibility.

Weaknesses

--The advantage of solving the link prediction task in a bandit setting is unclear. As mentioned in Paragraph 2 from Line 29, the dynamic and evolving nature of real-world graphs should be captured in the link prediction model. Experimental result analysis is short. For example, the failure of graph based baselines is owing to lack of exploration in Line 339. It is hard to understand this single sentence because that the graph neural network provides the capability of message passing. --Contextual bandits have been widely deployed in practice for online personalization and recommendation tasks. --Experimental setting is too simple to be self-contained. Training details are missing. --Font sizes of figures in the appendix are small. --The ablation study of bandits and PageRank should be included in the experiments to verify its main claim that the combination of contextual bandits and PageRank to achieve the balancing between exploitation and exploration. --The inference time should also be compared between the bandit methods and the graph based methods for link prediction in the experiments.

Questions

--The inference time should also be compared between the bandit methods and the graph based methods for link prediction in the experiments.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitation should be provided.

Anonymous Code Link in Reviewing

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