PageRank Bandits for Link Prediction
Authors: Yikun Ban
Jiaru Zou
Zihao Li
Yunzhe Qi
Dongqi Fu
Jian Kang
Hanghang Tong
Jingrui He
Venue: NeurIPS 2024 poster (2024)
Keywords: Link Prediction
PageRank
Graph Mining
Primary area: machine_learning_for_social_sciences
TL;DR: A method that combines contextual bandits and PageRank for online and offline link prediction.

Abstract: Link prediction is a critical problem in graph learning with broad applications such as recommender systems and knowledge graph completion. Numerous research efforts have been directed at solving this problem, including approaches based on similarity metrics and Graph Neural Networks (GNN). However, most existing solutions are still rooted in conventional supervised learning, which makes it challenging to adapt over time to changing customer interests and to address the inherent dilemma of exploitation versus exploration in link prediction.
To tackle these challenges, this paper reformulates link prediction as a sequential decision-making process, where each link prediction interaction occurs sequentially. We propose a novel fusion algorithm, PRB (PageRank Bandits), which is the first to combine contextual bandits with PageRank for collaborative exploitation and exploration. We also introduce a new reward formulation and provide a theoretical performance guarantee for PRB. Finally, we extensively evaluate PRB in both online and offline settings, comparing it with bandit-based and graph-based methods. The empirical success of PRB demonstrates the value of the proposed fusion approach. Our code is released at https://github.com/jiaruzouu/PRB.

PageRank Bandits for Link Prediction
Yikun Ban Jiaru Zou'r, Zihao Li', Yunzhe Qi', Dongqi Fu², Jian Kang², Hanghang Tong', .Jingrui He'
University Illinois Urbana-Chann Chaaaanaaa,,,nn MMeta AI, 'University Rochester (yykkun22, jiaruz2, zihaoli5, yunzheq2, htong, jingrui) @ elllinois.eeuu dongqifuu@ meta.com, jaia rochester.edu
Abstract
Link prediction a critical problem in graph learning with broad applications such recommender systems and knowledge graph completion. Numerous research efforts have been directed at solving this problem, including approaches based on similarity metrics and Graph Neural Networks (GNN). However, most existing solutions are still rooted in conventional supervised learning, which makes it challenging to adapt over time to changing customer interests and address the inherent dilemma of exploitation versus exploration in link prediction. To tackle these challenges, this paper reformulates link prediction as sequential decision making process, where each link prediction interaction occurs sequentially. We propose novel fusion algorithm, PRB (PageRank Bandits), which the first to combine contextual bandits with PageRank for collaborative exploitation and exploration. We also introduce new reward formulation and provide a theoretical performance guarantee for PRB. Finally, we extensively evaluate PRB in both online and offline settings, comparing it with bandit-based and graph-based methods. The empirical success of PRB demonstrates the value of the proposed fusion approach. Our code is released
Introduction
Link prediction is essential problem in graph machine learning, focusing on predicting whether link will exist between two nodes. Given the ubiquitous graph data in real-world applications, link prediction has become powerful tool in domains such as recommender systems [72] and knowledge graph completion [49 41 Considerable research efforts have been dedicated to solving this problem. One type of classic research approaches is heuristic-bai based methods, which infer the likelihood of links based on node similarity metrics [43 46]. Graph Neural Networks (GNNs) have been widely utilized for link prediction. For example, Graph Autoencoders leverage Message Passing Neural Network (MPNN) representations to predict links 29). Recently, MPNNs have been combined with structural features better explore pairwise relations between target nodes [73
18 61).
Existing supervised-eaaringg ler----eeannn--beeeedddd methods for link prediction are designed for either the static
26 75), they (chrono- logically) split the dataset into training and testing sets. Due to the dynamic and evolving nature of many real-world graphs, ideal link prediction methods should adapt over time consistently meet the contexts and goals of the serving nodes. For instance, in short-video recommender systems, both video content and user preferences change dynamically over time (28). Another significant challenge is the dilemma of exploitation and exploration in link prediction. The learner must not only exploit past collected data predict links with high likelihood but also explore nower-confidence target nodes to acquire new knowledge for long- term benefits. For example, in social recommendations, it
73 70 [8 61) relatively dynamic environment 64
55
62
58
69
19
27
Equal contribution.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is necessary to prioritize popular users by 'exploiting' knowledge gained from previous interactions, while also' 'xissoonplrnng' potential value from new or under-explored users to seek long-term benefits 77. Furthermore, while existing works often analyze time and space complexity, they generally lack theoretical guarantees regarding the performance of link prediction. To address these challenges, in this paper, we make the following contributions:
Problem Formulation and Algorithm. We formulate the task of link prediction as sequential decision-making under the framework of contextual bandits, where each interaction of link prediction regarded as one round of decision-making performance of this decision process. More specifically, we propose fusion algorithm named PRB (PageRank Bandits), which combines the exploitation and exploration balance of contextual bandits with the graph structure utilization of PageRank (59] 42). Compared to contextual bandit approaches, PRB leverages graph connectivity for an aggregated representation. In contrast to PageRank, incorporates the principles of exploitation and exploration from contextual bandits to achieve collaborative trade-off. Additionally, we extend PRB to node classification by introducing a novel transformation from node classification to link prediction, thereby broadening the applicability of PRB.
We introduce a pseudo-regret metric to evaluate the
Theoretical Analysis. We introduce a new formulation of the reward function to represent the mapping from both node contexts and graph connectivity to the reward. We provide one theoretical guarantee for the link prediction performance of the proposed algorithm, demonstrating that the cumulative regret induced by PRB can grow sub-linearly with respect the number of rounds. This regret upper bound also provides insights into the relationship between the reward and damping factor, as well as the required realization complexity of the neural function class.
Empirical Evaluation. We extensively evaluate PRB in two mainstream settings. (1) Online Link Prediction. In this setting, each link prediction is made sequentially. In each round, given serving node, the model is required to choose one target node that has the highest likelihood of forming a link with the serving node. The model then observes feedback and performs corresponding optimizations. The goal is to minimize regret over I rounds (e.g.. T = 10, 000). We compare PRB with state-of- the-art (SOTA) vandit-based approaches (e.g.. (76 12 which are designed for sequential decision- making. PRB significantly outperforms these bandit-based baselines, demonstrating the success of fusing contextual bandits with PageRank for collaborative exploitation and exploration. (2) Offline Link Prediction. In this setting, both training and testing data are provided, following the typical supervised learning process. Although PRB is designed for online learning, it can be directly applied to offline learning on the training data. We then use the trained model to perform link prediction on the testing data, comparing it with SOTA GNNs-based methods (e.g.. (1).... The superior performance of PRB indicates that principled exploitation and exploration can break the performance bottleneck in link prediction. Additionally, we conduct ablation and sensitivity studies for a comprehensive evaluation of PRB.
2 Related Work
Contextual Bandits. The first line of works studies the linear reward assumption, typically calculated using ridge regression [39 8
21 53 Linear (CBBhasee bandit algorithms [1 9 40 and linear 2 can achieve satisfactory performance and a near-optimal regret bound of
60
Thompson Sampling
Ö(VT). To learn general reward functions, deep neural networks have been adapted to bandits in various ways [10 Sampling on the final layer for exploration. [76 introduced the first provable neural-based contextual bandit algorithm with a UCB exploration strategy, and 74 later extended to the TS framework. 12 provides sharper regret upper bound for neural bandits with neural online regression. Their regret analysis builds on recent advances in the convergence theory of over- wver-parameterized neural networks 24 [ and uses the Neural Tangent Kernel [34] 6 to establish connections with lincar contextual bandits M. 112 13 retains the powerful representation ability of neural networks to
54 47 develop L-layer DNNs to learn arm embeddings and apply Thompson
learn the reward function while using another neural network for exploration. [52 51] integrates applottation-explorateet
neural networks into the graph neural networks for fine- fine-graines grained exploration and exploration. Recently, neural bandits have been adapted to solve other learning problems, such as active learning [14] 77 meta learning
Link Prediction Models. Three primary approaches have been identified for link prediction models.
Node embedding methods, as described by previous work [50, 30 57
23
44 45] 25), focus on

---

mapping each node to an embedding vector and leveraging these embeddings to predict connections. Another approach involves link prediction heuristics, as explored by 443 13 777 which utilize crafted structural features and network topology to estimate the likelihood of connections between nodes in a network. The third category employs GNNs for predicting link existence; notable is the Graph Autoencoder (GAE) [36], which learns low-dimensional representations of graph- structured data through an unsupervised learning process. GAE utilizes the inner product of MPNN representations of target nodes to forecast links but might not capture pairwise relations between nodes effectively. More sophisticated GNN models that combine MPNN with additional structural features, such as those by [71 70, 18,, have demonstrated superior performance by integrating both node and structural attributes. One such combined architecture is 1F-then-MPPNN as adopted by 77 778. In this approach, the input graph is first enriched with structural features (SF) and then processed by the MPNN to enhance its expressivity. However, since structural features change with each target link, the MPNN must be re-run for each link, reducing scalability. For instance, the SEAL model [71 first enhances node features by incorporating the shortest path distances and extracting k-hop subgraphs, then applies MPNN across these subgraphs to generate more comprehensive link representations. Another combined architecture is SF-and-MPNN. Models like Neo-GNN [70] and BUDDY [88] apply MPNN the entire graph and concatenate features such as common neighbor counts to enhance representational fidelity. In addition, [6]] has developed the Neural Common Neighbor with Completion (NCNC) which utilizes the MPNN-then-SS architecture to achieve higher expressivity and address the graph incompleteness.
Recently, representation learning temporal graphs for link prediction has also been widely studied to exploit patterns in historical sequences, particularly with GNN-based methods [58] 69 19 64
62 55, However, these approaches are still conventional supervised-leaming-
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- where each link prediction is made sequentially. Node classification [66 67 [6) also a prominent direction in graph learning, but it is not the main focus of this paper.
3 Problem Definition
Let Go (V, be an undirected graph at initialization, where V is the set of n nodes, |V| = n, and Fg S V x V represents the set of edges. Fl can be an empty set in the cold-start setting or include some existing edges with warm start. Each node it V is associated with a context vector Fo,: E TR. Then, we formulate link prediction as the problem of sequential decision-making under the framework of contextual bandits. Suppose the learner is required to finish a total of T link predictions. We adapt the above notation to all the evolving T graphs {G, (V, E.))
Y== and
let [7] = (1....,77) 7). In round of link prediction / E [T), given G,- = (V, 12-1), the learner is presented with serving node U2 E V and a set of l candidate nodes V (V vt,.) C V, where V is associated with the corresponding k contexts X, = (ft,1,-... xt, and [il = k. In the scenario of social recommendation, Vt can be considered the user that the platform (learner) intends to recommend potential friends to, and the other candidate users will be represented by V.. V, can be set as the remaining nodes V.- Vi/v, or formed by some pre-selection algorithm V. C V..
The goal of the learner is to predict which node in V will generate a link or edge with 242 Therefore, we can consider each node in V2 an arm, and aim to select the arm with the maximal reward the arm with the maximal probability of generating an edge with v, For simplicity, we define the reward of link prediction as the binary reward. Let v4, V. be the node selected by the learner. Then, the corresponding reward is defined as r,, 1 if the link [ee, U2 really generated; otherwise, r,, 0. After observing the reward r,,3- we update E,_ obtain the new edge set E,, and thus new G..
For any node vt,i E V,, denote by Dylee.. the conditional distribution of the random reward rt, with respect to Fi,i, where ) = (11 O). Then, inspired by the literature of contextual bandits, we define the following pseudo regret:
R
Ery - Dyll Dylre, [r(x]] - Br, (real) = P(re,- = 1/x0,-) - -P(r, = 1/xr,))
(3.1)
3

---

Algorithm PRB (PageRank Bandits)
Input: [1, T, Go. 7,,, 122 (learning rate), a (damping factor) Initialize fgj 8
2: for t= 2....... T T'do do 3: Observe serving node ut, candidate nodes Ve, contexts Nr and Graph G:-1
4: h-=0
5:
for each 1/ E V do
6:
h = fi (Ir.s: 0/_1) fo (1)1))
7:
end for
8:
Compute P. based on Gt-1
9:
Solve = aP + (1 (x h;
10:
Select i = arg EV,, [i]
11:
Observe 1,
if r, == then
13:
Add "e,il to G and set as G.
14:
else
15:
G. G.-1
16:
end
0: = 0-11 - 111 V 0:_, C ((.
17:
18:
0 = 0- V 09_ [ (((1,,)) (
19:
end for
where 1* = arg EV, P(rr. 1(x,,)) the tie is broken randomly, and is the index of selected node. Ry reflects the performance difference of the learned model from the Bayes-optimal predictor. The goal of the learner is to minimize R.-.
4 Proposed Algorithms
Algorithm| I describes the proposed algorithm PRB. It integrates contextual bandits and PageRank to combine the power of balancing exploitation and exploration with graph connectivity. The first step to balance the exploitation and exploration in terms of the reward mapping concerning node contexts, and the second step to propagate the exploitation and exploration score via graph connectivity.
To exploit the node contexts, we use a neural network to estimate rewards from the node contexts. Let fi(: 0*) be neural network to learn the mapping from the node context the reward. Denote the initialized parameter of fi by 0j In round f, let 0/ be parameter trained on the collected data of previous 1-1 1 rounds including all selected nodes and the received rewards. Given the serving node ut+ for any candidate node Ut,i E V. fi (Iz,;; i), E V, is the estimated reward by greedily exploiting the observed contexts, which we refer update 0/_1, we can conduct stochastic gradient descent to update 0¹ based on the collected training
"exploitation" Suppose i is the index of selected nodes. To
sample (ar,," T,,i) with the squared loss function L (xr,3- Tr,; 0-11 = [f 0111) /2,
Denote the updated parameters by 0 for the next round of link prediction.
In addition to exploiting the observed contexts, employ another neural network estimate the potential gain of each candidate node in terms of reward for exploration. This idea is inspired by [12]. Denote the exploration network by 02). is to learn the mapping from node contexts and the discriminative ability of f1 to the potential gain. In round / E (T), given node context It,; E V, and its estimated reward fi (zs,;; 0.-1), the input of f2 is the gradient of fi 0)-z) with respect to B/_1. denoted by p(21,), and fa(ø(z o²_,) is the estimated potential gain. After the learner selects the node ,,, and observes the reward Tg the potential gain is defined as rr, fi (I 0)-1). which is used to train fz. Thus, after this interaction, we conduct the stochastic gradient descent to update 8² based on the collected sample (0(#,,;) re,a (I 0(_1)) with the squared loss function
(ol,,))ree Ve. - S1(0, 1::1); 0-.) = [/ 0_ (re, -1 ( (-)))) /2. Denote by 02

---

Binary Node Classification
Link Prediction with Two Super Nodes
Class O
Super Node o (Clss 0)
Class
Super Node 1 (Class 1)
Figure 1: Transforming Node Classification to Link Prediction. Consider binary node classi- fication problem. In the left figure, given a graph, the learner tries to classify node 4 into one of two classes. First, we add two supernodes to the graph, each representing one of the classes. The node classification problem is then transformed into predicting links between node 4 and the two supernodes in the right figure. Suppose the learner predicts that a link will exist between node 4 and supernode O. If node 4 belongs to Class O, the reward is 1, and an edge is added hetween node 4 and supernode O; otherwise, the reward O, and an edge is added between node and supernode 1.
the updated parameters of f2 for the next round of link prediction. The reasons for setting ( as the input of /2 are as follows: (1) it incorporates the information of both z,,2 and discriminative ability of fi (:; 0)-1); (2) the statistical form of the confidence interval for reward estimation can be regarded as the mapping function from ((ra.)) to the potential gain, and f2 is learn the unknown mapping [1]]
The previous steps demonstrate the exploitation and exploration of node contexts to facilitate decision- making in link prediction. Since graph connectivity is also crucial, we next introduce our method of integrating the bandit principle with PageRank to enable collaborative exploitation and exploration. PageRank calculates the stationary distribution of the random walker starting from some node, iteratively moving to a random neighbor with probability a (damping factor) or returning to its original position with probability 1 - a. Let v, be the stationary distribution vector calculated based on the graph Gt. Then, V, satisfies:
V, aP, + (1 ax) h,
(4.1)
where P, E Enxn the transition matrix built on G;-1 and h, typically regarded as a position vector mark the starting node. e is computed as D A,- A where D E Raxx R is the degree
matrix of G.-1 and A, E IR" "x is the adjacency matrix of G.-1.
Here we propose to use h, to include the starting exploitation and exploration scores of candidate nodes, defined as:
E V2 b, = (1 0/-1) f2(1r.:: 0211), and i E V/V, h = 0.
(4.2)
Therefore, V, is the vector for the final decision deeision-making based on collaborative exploitation and exploration. Some research efforts have been devoted to accelerating the calculation of Eq 4. in the evolving graph, egg., (42, which can be integrated into PRB (Line Algorithm to boost its efficiency and scalability.
PRB for Node Classification. We also extend PRB to solve the problem of node classification as illus- trated in Figure Consider a k-class classification problem. We add is super nodes (Ū1, U2,,..... T the graph, which represents & classes, respectively. Then, we transform the node classification problem into the link prediction problem, aiming to predict the link between the serving node and the i super nodes. To be specific, round E [T'. the learner is presented with the serving node v and the h candidate (super) nodes V;- {ūz, U2...., ēx} associated with & corresponding contexts X, = {Ir,,1, Ft.2, ). Recall x, is the context associated with vr. Then, we define the con- texts of super nodes as Ft,1 [ar] 0, .Q.....C 0) x
[0, x ...... O]T _................. Te, E Ad E [k). This context definition is adopted from neural contextual bandits [2 76. Then, the learner is required to select one node from V/. Let 0, be the selected node and ūs; be ground- truth node (17 is the index of ground-truth class of node vx). Then, after observing the reward rt.i one edge (wy, 6. is added to the graph G,-1, if us belongs to the class it, i.e., = : and reward rt.i, 1. Otherwise, rt.s, = O and the edge [Ve, ūx; is added to G.-1- Then, we can naturally apply PRB to this problem. We detail our extended algorithm for node classification in Algorithm
[0, 0. ......... Tr)T,
...., Ft,K
5

---

PRB Greedy. We also introduce a greedy version of PRB which integrates PageRank solely with contextual bandit exploitation, as outlined in Algorithm 3 We will compare each variant of algorithms in our experiment section.
5 Regret Analysis
In this section, we provide the theoretical analysis of PRB by bounding the regret defined in Eq 3.1 One important step is the definition of the reward function, as this problem is different from the standard bandit setting that focuses on the arm (node) contexts and does not take into account the graph connectivity. First, we define the following general function to represent the mapping from the node contexts to the reward. Given the serving node 2t and an arm node Vt, V2 associated with the context t the reward conditioned on and Vt, is assumed to be governed by the function:
[F(rr, my, [4,a] = y (Ir,s)
(5.1)
where y is unknown but bounded function that can be either linear or non-linear. Next, provide the formulation of the final reward function. In round E [T]. let ys be the vector to represent the expected rewards of all candidate arms y: [y (Ira,) Ut,i E Vi]. Given the graph G.- its normalized adjacency matrix Pt, and the damping factor a, inspired by PageRank, the optimizing problem is defined as: v arg miny o. (I P.)v + a)]lv /212/2. Then, its optimal solution is
Vi = aaPP + a1-
(5.2)
For any candidate node vt,; E Vr, we define its expected reward as Br. [Tr.]] vt v flexible reward function that reflects the mapping relation of both node contexts and graph connectivity. is a hyper-parameter and node contexts. When a O, v, turns into the reward function in contextual bandits [76] [2]: when a 1, Vē is the optimal solution solely for graph connectivity. Here, we assume a is prior knowledge. Finally, the pseudo-regret is defined as
trade-off between the leading role of graph connectivity
T
R Σ (vili))-vv0)
(5.3)
where i" arg max vē [1] and is the index of the selected node. The regret analysis is associated with the Neural Tangent Kernel (NTK) matrix as follows:
Definition 5.1 (NTK 34 63). Let N denote the normal distribution. Given all data instances {z, (2,)7% for i,j / E [Tk], define
Σ
H = E. = (0i, A
E/ =2E 2
HIJ = -H a (o. (o'()) (b) E
Then, the NTK matrix is defined as H= (H+ + Σ 1/2 Assumption 5.1. There exists A 0, such that H AoI.
The assumption 5.1 is generally made in the literature of neural bandits 76
74
20
35
12
10
ensure the existence of solution for NTK regression.
As the standard setting in contextual bandits, all node contexts normalized to the unit length. Given Fe,i E d with |122 = 1, E [ E [kt], without loss of generality, we define fully-connected network with depth L and width m:
f( 0) =
1.0.....(WW ( (WI1..)))
(5.4)
where is the ReLU activation function, W1 E mxd W. E R mmxm, for 2 < 1 L 1. W I and 0 [vec(W,) vec w2) ..... vee(Wr T E Rr. Note that our analysis can also be readily generalized to other neural architectures such as CNNs and ResNet [4]. We
employ the following initialization 17 for For E [L - 1). each entry of W, drawn from the normal distribution (0 2/m); each entry of W, r, is drawn from the normal distribution ( 1/m).
The network f1 and f2 follows the structure of f. Define y = [1((,,,)) : L (T), E [k]] Finally, we provide the performance guarantee stated in the following Theorem.

---

Theorem 5.1. Given the number of rounds T. for any a, ô E (0,1), suppose m 2 ((poly(T, L)- log(1/6)), 71 = 1/2 ym and set Fr,i = t E [T], [k]. Then, with probability least over the initialization, Algorithm achieves the following regret upper bound:
R S Ö(VdkT)
/max(d, 52)
(5.5)
where d = log HI) and S = H H
log( (TT))
Theorem 5.1 provides regret upper bound for PRB with the complexity of O(dvkI kT) (see proofs in Appendix Instead, the graph-based methods (e.g.. 18, 61) lack an upper bound terms of their performance. Theorem |.1 provides insightful results in terms of PRB's performance. First, PRB's 's regret can grow sub-linearly with respective to T. Second, PRB's performance is affected by the number of nodes k. This indicates the larger the graph the more difficult the link prediction problem is. Third, d and in the regret upper bound reflect the complexity of the required neural function class to realize the underlying reward function v,, i.e., the difficulty of learning v? d is the effective dimension, which measures the actual underlying dimension in the RKHS space spanned by NTK. S' is to provide an upper bound on the optimal parameters in the context of NTK regression. Both d and S are two complexity terms that commonly exist in the literature of neural contextual bandits 76 74. In the general case when > 0, learning Vē proportionally turns into a bandit optimization problem and the upper bound provided in Theorem 5.1 matches the SOTA results in neural bandits 776 [4). In fact, the regret upper bound closely related to the graph structure of G, In the special case when
1, learning Vi turns into simple convex optimization problem (Eq. (4.1) ) and PRB can really find the optimal solution, which leads to zero regrets. When a the problem turns into complete bandit optimization problem with the same regret upper bound as Thcorem 5.1
Experiments
In this section, we begin by conducting a comprehensive evaluation of our proposed method, PRB, compared with both bandit-based and graph-based baselines across online and offline link prediction settings. Then, we analyze the computational costs associated with each experiment and present additional ablation studies related to PRB. In the implementation of PRB, we adapt the efficient PageRank algorithm
42 to solve Eq. 44.1).
6.1
Online Link Prediction
MovieLens
AmazonFashion
Facebook
GrQc
Methods
Mean
Std
Mean + Std
Mean Std
Mean Std
HE-Net
1638 15.3
1698 + 19.3
2274 + 27.1
3419 16.5
NeuGreedy
1955 + 17.3
1952 + 27.4
2601 + 14.2
3629 + 18.2
NcuralUCB
1737 + 16.8
1913 + 18.6
2190 + 16.3
3719 + 16.4
NeuralTS
1683 + 14.7
2055 + 21.9
2251
19.5
3814 + 23.3
PRB
1555 21.7
1455 + 18.4
1929
17.0
3236 18.5
Table 1: Cumulative regret of bandit- methods online link prediction.
/980
Figure 2: Regret comparison of handit-based methods on online link prediction datasets (average of 10 runs with standard deviation in shadow, detailed in Table I
7

---

In this sub-section, we evaluate PRB on the setting of online link prediction and node classification as described in Sec. compared with bandit-bard based baselines.
Datasets and Setups. We use three categories of real-world datasets to compare PRB with bandit- based baselines. The details and experiment settings
follows.
(I) Recommendation datasets: Movielens [32] and Amazon Fashion 448 (Bipartite Graph). Given
the user set U and item set I, let Go be the graph with no edges, Go (V = U + I, Eo 0). In round E [7', we randomly select user e, E U, and then randomly pick 100 items (arms) from L, including 2/2 10 purchased items, forming V. PRB runs based on G₁-1 and selects an arm (node) 21, E V₁. If the selected arm V/, is the purchased item by ue the regret is 0 (or reward is 1) and we add the edge [v,, V4,23 to G--1, to form the new graph G₁; otherwise, the regret is 1 (or reward is 0) and G, = -.-1-
(2) Social network datasets: Facebook 38 and GR-QC
Given the user set V, we have Go = (V, E = 0). a round E (T], we randomly select a source node it that can be thought of as the serving user. Then,
37
randomly choose 100 nodes, including E2 's 10 connected nodes but their edges are removed, which form the arm pool V/ associated with the context set Xi Then, PRB will select one arm , E Vg. If on and f are connected in the original graph, the regret is 0 and add the edge [uv, v,,ū] Gr- otherwise, the regret is and G; G.-
(3) Node classification datasets: Cora, Citeseer, and Pubmed from the Planetoid citation networks Recall the problem setting described Sec. A Consider k-class node classification problem. Given graph GVV, Eo = 0). we randomly select node U, V to predict its belonging class, in round E [T] Then, PRB select one super node Ut If belongs to class it, the regret is and add [u,, to 1 Otherwise, the regret is and G, Gt-1.
68
Baselines. For bandit- based methods, we apply Neural Greedy 12 that leverages the greedy exploration strategy on the exploitation network, NeuralUCB (76) that uses the exploitation network to learn the reward function along with an UCB-based exploration strategy, NeuralTS 74 that adopts the exploitation network to learn the reward function along with the Thompson Sampling exploration strategy, and EE-net 12 that utilizes the exploitation exxplortionnlllootttin network to learn the reward function. Following [76 12 for all methods, we train each network every 50 rounds for the first 2000 rounds and then every 100 rounds for the remaining rounds. See Appendix A. for additional experimental setups.
Online Link Prediction. We use Figure 2 to depict the regret trajectories over 10,000 rounds, and Table to detail the cumulative regret after 10,000 rounds for all methods, where the lower is better. Based on the regret comparison, PRB consistently outperforms all other baselines across all datasets. For example, the cumulative regret at 10,000 rounds for PRB on MovieLens is considerably lower than the best-performing baseline, EE-Net. Similarly, in the AmazonFashion dataset, PRB achieved the lowest regret, surpassing the strongest baseline EE-Net over 14%. This trend is consistent across the Facebook and GrQe datasets, where PRB maintains its lead with the lowest regrets respectively. The consistency in PRB's 's performance across various datasets suggests the importance of utilizing the graph structure formed by previous link predictions.
Cora
Citeseer
Pubmed
Methods
Mean + Std
Mean + Std
Mean + Std
EE-Net
1990 = 13.8
2299 = 33.4
1659 +:: 11.3
NeuGreedy
2826 = 21.4
2543 = 24.6
1693 +/2 13.5
NeuralUCB
2713 = 21.7
3101 = 22.0
1672 + 14.3
NeuralTS
1998 = 15.6
3419 = 39.5
1647 = 11.3
PRB
1874 = 25.6
2168 = 35.7
1577 + 10.7
Table 2: Cumulative regret of bandit-based methods on online node classification.
Online Node classification. Figure S and Table 2 show the regret comparison on online node classification. PRB consistently demonstrates the lowest cumulative regret by outperforming other
8

---

206
Gnedy
1063
Nexial Gready
Houral Gredd
30
Ne Recsalic
Nos saUCE
PRI
3000
6003
0830
3000
6330
Figure 3: Regret comparison of bandit-based methods on online node classification datasets (average of 10 runs with standard deviation in shadow, detailed in Table
Cora
Citeseer
Pubmed
Collab
PPA
DDI
Methods
HR@ 100 = Std
HR@ 100 + Std
HR 100
Std
HR@50 + Std
HR 100 Std
HR@20 + Std
CN
33,92 0.46
29.79 + 0.90
23.13 0.15
56,44 0.00
27.65 0.00
17.73 = 0.00
AA
39.85 1.34
35.19 + 1.33
27.38 = 0.11
64.35 = 0.00
32,45 = 0.00
18.61 + 0.00
RA
41.07 0.48
33.56 0.17
27.03 0.35
64.00 0.00
49.33 0.00
27.60 0.00
GCN
66.79 1.65
67.08 1: 2.94
53.02 + 1.39
44.75 = 1.07
18.67 = 1.32
37.07 +: 5.07
SAGE
55.02
$7.01 3.74
39.66 0.72
48.10
2.40
$3,90 4.74
SEAL
81,71
83.89 2.15
75.54 1.32
64.74 0.43
48.80 = 3.16
30.56 3.86
NBFnet
71.65 2.27
74.07 1.75
58.73 1.99
OOM
OOM
4.00 0.58
Nco-GNN
80.42 1.31
84.67 2.16
73.93 1.19
$7.52 0.37
49.13 0.60
63.57 3.52
BUDDY
88.00 0.44
92.93 + 0.27
74.10 = 0.78
65.94 = 0.58
49.85 = 0.20
78.51 + 1.36
NCN
89.05 0.96
91.56 + 1.43
79.05 = 1.16
64.76 = 0.87
61.19 = 0.85
82.32 + 6.
NCNC
89.65 1.36
93.47 + 0.95
81.29 + 0.95
66.61 = 0.71
61.42 0.73
84.11 + 3.67
PRB
92.33 0.57
95.13 +: 1,28
84,54 #: 0.86
67.29 0.31
63.47 1.75
88.31 4.36
Table 3: Results on offline link prediction benchmarks. OOM means out of GPU memory.
bandit methods round 10,000, respectively. Overall, PRB decreases regrets by 3.0%, 1.2%, and 3.5% compared to of the best baselines, NeuralTS. This experiment demonstrates that PRB is versatile enough for applications beyond online link prediction, extending to other real-world tasks such online node classification. This highlights PRB's advantage of fusing contextual bandits with PageRank for collaborative exploitation and exploration.
Offline Link Prediction
In this subsection, we evaluate PRB in the setting of offline link prediction compared with graph-based baselines, where training and testing datasets are provided, following the same evaluation process of
[18 61. Here, we train PRB on the training dataset using the same sequential optimization method Sec. 6.1 Then, we run the trained PRB on the testing dataset. Notice that PRB never sees the test data in the training process other basclines.
Datasets. In this study, we use real-world link- pike-rreiittion datasets to compare PRB with graph-based baselines. Specifically, we apply Cora, Citeseer, and Pubmed from Planetoid citation networks [68]; ogbl-collab, ogbl-ppa, and ogbl-ddi from Open Graph Benchmark [33] (See dataset statistics Appendix (
Setting: We strictly follow the experimental setup in 18 and use the Hits @k metric for evaluation. Please also refer to A. for additional setups.
Baselines. For graph-based methods, we choose traditional link precccicdittion heuristics including CN [15], RA (77). AA B and common GNNs including GCN [36] and SAGE [3I]. Then, we
employ SF-then-MPNN models, including SEAL [7I) and NBFNet (78), as well SF-and-MPNN models like Neo-GNN 770 and BUDDY 18). Additionally, we also select the
model
NCN [6] and NCNC 61 The results of the baselines sourced from Table 2 of [61].
Comparison with Graph-based Baselines. We present the experimental results in Table for all methods. The results demonstrate that PRB consistently outperforms other baselines across all six datasets. Specifically, compared to most recent method, NCNC, PRB achieves a minimum improvement of 0.68% the Collab dataset, maximum of 4.2%, and average of 2.42% across

---

MovieLens
AmazonFushion
Facebook
GrQq
Cora
Citeseer
Pubmed
Methods
Mean
Std
Mean +: Std
Mean + Std
Mean +: Std
Mcan + Std
Mcan +: Std
Mcan +: Std
PRB
I555 = 21.7
1455 +: 18.4
1929 17.0
3236
18.5
1874 25.6
2168 35.7
1577 10,7
PRB-Greedy
1892 15.1
1567 24.6
23.6
3332 15.9
1932 24.1
2194 23.3
1634 12.3
PRB-(10%-G)
1521 17.6
1408 23.5
1858 15.7
3085 14.3
1804 23.5
2158 33.1
1630 11.5
Table 4: Cumulative regrets of PRB variants for online link prediction and node classification.
all datasets. Given that all baselines lack the perspective of exploration, the results demonstrate that fusing the exploitation and exploration in contextual bandits along with learning graph connectivity through PageRank does significantly enhance accuracy for link prediction.
6.3 Ablation and Sensitivity Studies
Table presents the performance of different variants PRB, including PRB-greedy that only use the exploitation network and PRB-(10%-G) that has the warm start with addition 10% edges in Go. The results show that exploration is crucial to the final performance and the additional graph knowledge can boost the performance.
Due the space limit, we move all other experiment sections to Appendix including computational cost analysis on PRB and additional ablation & sensitivity studies.
7 Conclusion
This paper introduces a fusion algorithm for link prediction, which integrates the power of contextual bandits in balancing exploitation and exploration with propagation on graph structure by PageRank. We further provide the theoretical performance analysis for PRB, showing the regret of the proposed algorithm can grow sublinearly. We conduct extensive experiments link prediction evaluate PRB's 's effectiveness, compared with both bandit-based and graph-based baselines.
Acknowledgments and Disclosure of Funding
This work is supported by the National Science Foundation under Award No. IIS-2117902 and DARPA (HR001 121C0165). The views and conclusions are those of the authors and should be interpreted as representing the official policies of the funding agencies or the government.
References
[1] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, pages 2312-2320, 2011.
[2] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statisties, pages 176-184. PMLR, 2017.
[3] Lada Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211- 230, 2003.
[4] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference Machine Learning, pages 127-135. PMLR, 2013.
[5] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-parameterization.. In International Conference on Machine Learning, pages 242-252. PMIR, 2019.
[6] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang- exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pages 8141-8150, 2019.
10

---

[7] Yikun Ban, Ishika Agarwal, Ziwei Wu, Yada Zhu, Kommy Weldemariam, Hanghang Tong, and Jingrui He. Neural active learning beyond bandits. arXiv preprint arXiv:240.11252,, 2024.
[8] Yikun Ban and Jingrui He. Generic outlier detection in multi-armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 913-923, 2020.
[9] Yikun Ban and Jingrui He. Local clustering in contextual multi-armes bandits. In Proceedings of the Web Conference 2021, pages 2335 2346, 2021.
[10] Yikun Ban, Jingrui He, and Curtiss B Cook. Multi-facet contextual bandits: A neural network perspective. In The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singupore, August 14-18, 2021, pages 35-45, 2021.
[11] Yikun Ban, Yunzhe Qi. Tianxin Wei, Lihui Liu, and Jingrui He. Meta clustering of neural bandits. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 95-106, 2024.
[12] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. EE-net: Exploitation-exploratiee neural networks in contextual bandits. In International Conference on Learning Representations, 2022.
[13] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Neural exploitation and exploration of contextual bandits. arXiv preprint arXiv:2305.03784, 2023.
[14] Yikun Ban, Yuheng Zhang, Hanghang Tong, Arindam Banerjee, and Jingrui He. Improved algorithms for neural active learning. Advances in Neural Information Processing Systems, 35:27497-27509, 2022.
[15] Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):599-512, 1999.
[16] Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classification in social networks. Social network data analytics, pages 115-148, 2011.
[17] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 10:36-66-1 2019.
[18] Benjamin Paul Chamberlain, Sergey Shirobokov, Emanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In The eleventh international conference on learning representations, 2022.
[19] Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? arXiv preprint arXiv:2302. 1166, 2023.
[20] Zhongxiang Dai, Yao Shu, Arun Verma, Flint Xiaofeng Fan, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated neural bandit. arXiv preprint arXiv:2205. 14309, 2022.
[21] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback, 2008
[22] Rohan Deb, Yikun Ban, Shiliang Zuo, Jingrui He, and Arindam Banerjee. Contextual bandits with online neural regression. arXiv preprint arXiv:2312.07145. 2023.
[23] Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey. ACM SIGKDD Explorations Newsletter, 24(2):61-77, 2022.
[24] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
11

---

[25] Dongqi Fu, Yikun Ban, Hanghang Tong, Ross Maciejewski, and Jingrui He. Disco: Compre- hensive and explainable disinformation detection. In Proceedings of the 31st ACM International Conference Information & Knowledge Management, pages 4848-4852, 2022.
[26] Dongqi Fu. Liri Fang, Ross Maciejewski, Vetle I. Torvik, and Jingrui He. Meta-learned metrics multi-evolution temporal graphs. In Aidong Zhang and Huzefa Rangwala, editors, KDD '22: The 28th ACM SIGKDI) Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14- 18, 2022, pages 367-377. ACM, 2022.
[27] Dongqi Fu and Jingrui He. SDG: A simplified and dynamic graph neural network. In Fernando Diaz, Chirag Shah, Torsten Suel, Pablo Castells, Rosie Jones, and Tetsuya Sakai, editors, SIGIR '21: The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, Virtual Event, Canada, July 11-15, 2021, pages 2273-2277 ACM, 2021.
[28] Chongming Gao, Kexin Huang, Jiawei Chen, Yuan Zhang, Biao Li, Peng Jiang, Shiqi Wang, Zhong Zhang, and Xiangnan He. Alleviating matthew effect of offline reinforcement learning in interactive recommendation. arXiv preprint vrXiv:230700551,, 2023.
[29] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning, pages 1263-1272. PMLR, 2017.
[30] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 355-864,20 2016.
[31] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[32] Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions interactive intelligent systems (tiis), 5(4):1-19, 2015.
[33] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-2333,,, 2020.
[34] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pages 8571-8580, 2018
[35] Yiling Jia, Weitong Zhang, Dongruo Zhou, Quanquan Gu, and Hongning Wang. Learning neural contextual bandits through perturbed rewards. In International Conference on Learning Representations, 2022.
[36] Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 10XVv11609.02907,22 2016.
[37] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):-es, 2007.
[38] Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.
[39] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual- approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web. pages 661-670, 2010.
[40] Shuai Li, Alexandros Karatzoglou, and Claudio Gentile. Collaborative filtering bandits. In Proceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval, pages 539-548, 2016.
12

---

[41] Zihao Li. Yuyi Ao. and Jingrui He. Sphere: Expressive and interpretable knowledge graph embedding for retrieval. Grace Hui Yang. Hongning Wang, Sam Han, Claudia Hauff, Guido Zuccon, and Yi Zhang, editors, Proceedings of the 47th International ACM SIGIR Conference on Research and Development Information Retrieval, SIGIR 2024, Washington DC, USA, July 14-18, 2024, pages (629-2634, ACM, 2024.
[42] Zihao Li, Dongqi Fu, and Jingrui He. Everything evolves in personalized pagerank. In Proceedings of the ACM Web Conference 2023, pages 3342-3352, 2023.
[43] David Liben-Ne -Nwell and Jon Kleinberg. The link prediction problem for social networks. In Proceedings of the twelfth international conference on Information and knowledge management, pages 556-559, 2003.
[44] Xiao Lin, Jian Kang. Weilin Cong, and Hanghang Tong. Bemap: Balanced message passing for fair graph neural network. In Learning on Graphs Conference, pages 37-1. PMLR, 2024.
[45] Xiao Lin, Zhining Liu, Dongqi Fu, Ruizhong Qiu, and Hanghang Tong. Backtime: Backdoor attacks on multivariate time series forecasting. arXiv preprini arXiv:2410.02195, 2024.
[46] Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its upplications, 390(6); 150-1170, 2011.
[47] Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. arXiv preprint arXiv:1705.07347 2017.
[48] Jianmo Ni, Jiacheng Li, and Julian McAuley. Justifying recommendations using distantly- labeled reviews and fine- fine-grained aspects. In Proceedings of the 2019 conference empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP), pages 188-197, 2019.
[49] Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):11-33, 2015.
[50] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[51] Yunzhe Qi, Yikun Ban, and Jingrui He. Neural bandit with arm group graph. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1379 1389, 2022.
[52] Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1920-1931, 2023.
[53] Yunzhe Qi, Yikun Ban, Tianxin Wei, Jiaru Zou, Huaxiu Yao, and Jingrui He. Meta-learning with neural bandit scheduler. Advances in Neural Information Processing Systems, 36, 2024.
[54] Carlos Riquelme, George Tucker, and Jasper Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. arXiv preprint arXiv:1802.09127, 2018.
[55] Emanuele Rossi. Ben Chamberlain, Fabrizio Frasca, Davide Eynard. Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. arXiv preprint 27Xiv:2006.10637, 2020.
[56] Yuan Sui, Jiaru Zou, Mengyu Zhou, Xinyi He, Lun Du, Shi Han, and Dongmei Zhang. Tap4llm: Table provider sampling, augmenting. and packing semi-structured data for large language model reasoning. arXiv preprint arXiv:2312.09m) 2023.
[57] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. Proceedings of the 24th international conference on world wide web, pages 1077
13

---

[58] Yuxing Tian, Yiyan Qi, and Fan Guo. Freedyg: Frequency enhanced continuous time dy- namic graph model for link prediction. In The Tweifth International Conference on Learning Representations, 2023.
[59] Hanghang Tong, Christos Faloutsos, and Jia-Yo Pan. Fast random walk with restart and its applications. In Sixth international conference on data mining (ICDM'06 pages 622-
IEEE, 2006.
[60] Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint arXiv: 1.0..30006.. 68699, 2013.
[61] Xiyuan Wang, Haotong Yang, and Muhan Zhang. Neural common neighbor with completion for link prediction. In The Twelfth International Conference Learning Representations, 2023.
[62] Yanbang Wang, Yen-Ye Yu Chang, Yunyu Liu, Jure Leskovec, and Pan Li. Inductive representation learning in temporal networks via causal anonymous walks. arXiv preprint arXiv:2101.05974, 2021.
[63] Zhilei Wang, Pranjal Awasthi, Christoph Dann, Ayush Sekhari, and Claudio Gentile. Neural active learning with performance guarantees. Advances in Neural Information Processing Systems, 34, 2021.
[64] Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive representation learning on temporal graphs. arXiv preprint UrXiv:2002.07962 2020.
[65] Pan Xu, Zheng Wen, Handong Zhao, and Quanquan Gu. Neural contextual bandits with deep representation and shallow exploration. arXiv preprint arXiv:2012.01 00700000.00..... 2020.
[66] Zhe Xu, Yuzhong Chen, Qinghai Zhou, Yuhang Wu, Menghai Pan, Hao Yang, and Hanghang Tong, Node classification beyond homophily: Towards a general solution. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2862-2873, 2023.
[67] Zhe Xu, Boxin Du and Hanghang Tong. Graph sanitation with application to node classification. In Proceedings of the ACM Web Conference 2022, pages 1136-1147, 2022.
[68] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016.
[69] Le Yu, Leilei Sun, Bowen Du, and Weifeng Lv. Towards better dynamic graph learning: New architecture and unified library. Advances in Neural Information Processing Systems, 36:67686-67700, 2023.
[70] Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo Kim. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Processing Systems, 34:13683-13694 2021.
[71] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
[72] Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. arXiv preprint arXiv: 1904. / /2058, 2019.
[73] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances Neural Information Processing Systems, 34:9061 -9073, 2021.
[74] Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. In International Conference on Learning Representations, 2021.
[75] Lecheng Zheng, Baoyu Jing, Zihao Li, Hanghang Tong, and Jingrui He. Heterogeneous contrastive learning for foundation models and beyond. Ricardo Baeza-Yates and Francesco Bonchi, editors, Proceedings of the 30th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD 2024, Barcelona, Spain, August 25-29, 2024, pages 6666-6676. ACM, 2024.
14

---

[76] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb- based exploration. International Conference on Machine Learning, pages 11492-11502. PMLR, 2020.
[77] Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71:623 630, 2009.
[78] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang. Neural bellman- ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29490, 2021.
[79] Jiaru Zou, Mengyu Zhou, Tao Li, Shi Han, and Dongmei Zhang. Promptintern: Saving inference costs by internalizing recurrent prompt during large language model fine-tuning. arXiv preprint 1rXiv:2407.02211, 2024.
15

---

A Additional Experiments
A.1 Experiment Setups
Online Link Prediction Setups. For all bandit-based methods including PRB, for fair comparison. the exploitation network fi is built by a 2-layer fully connected network with 100-width. For the exploration network of EE-Net and PRB, we use a 2-layer fully connected network with 100-width as well. For NeuralUCB and NeuralTS, following the setting of 776 744, we use the exploitation network fi and conduct the grid search for the exploration parameter over {0.001, 0.01, 0.1,1} and for the regularization parameter À over {0.01, 0.1, 1}. For the neural bandits NeuralUCB/TS, following their setting, as they have expensive computation costs to store and compute the whole gradient matrix, we use a diagonal matrix to make an approximation. For all grid-searched parameters, we choose the best of them for comparison and report the average results of 10 runs for all methods. For all bandit-based methods,
use SGD as the optimizer for the exploitation network fi. Additionally, for EE-Net and PRB, we use the Adam optimizer for the exploration network f2. For all neural networks, we conduct the grid search for learning rate over {0.01, 0.001, 0.0005, 0.0001 For PRB, we strictly follow the settings in 42 to implement the PageRank component. Specifically, we set the parameter = 0.85 after grid search over {0.1, 0.3, 0.5, 0.85, 0.9), and the terminated accuracy each dataset, we first shuffle the data and then run each network for 10,000 rounds (t = 10, 000). We train each network every 50 rounds when < 2000 and every 100 rounds when 2000 < t < 10, 000.
10 6, For
Offiine Link Prediction Setups. For the graph-based methods, we strictly follow the experimental and hyperparameters settings in [8] to reproduce the experimental results. Offline link prediction task requires graph links to play dual roles as both supervision labels and message passing links. For all datasets, the message-passing links at training time are equal to the supervision links, while at test and validation time, disjoint sets of links are held out for supervision that are never seen during training. All hyperparameters are tuned using Weights and Biases random search, exploring the search space of hidden dimensions from 64 to 512, dropout from 0 to I, layers from 1 to 3, weight decay from 0 to 0.001, and learning rates from 0.0001 to 0.01. Hyperparameters yielding the highest validation accuracy are selected, and results are reported on a single-use test set. For PRB, we use setups similar those in the online setting. We utilize the exploitation network fi and exploration network f2 both with 500-width. We set the training epoch to 100 and evaluate the model performance on validation and test datasets. We utilize the Adam optimizer for all baseline models. For PRB implementation, We utilize the SGD optimizer for fi and the Adam optimizer for f2.
A.2
Computational Cost Analysis
We conduct all of our experiments on an Nvidia 3060 GPU with an x64-based processor.
Time and space complexity. Let n be the number of nodes, / be the index of the current round of link prediction, & be the number of target candidate nodes, d be the number of context dimensions, and be neural network width. For the online setting, let m, be the number of edges at round t. In the setting of online link prediction, the time complexity of PRB is (kdpp + myk), where the first term is the cost of calculating the exploitation-exploraaio score for each candidate node and the second term is the cost of running PageRank, following [42). And, the space complexity is O(n + m,) to store node weights and edges. For the offline setting, let m be the number of edges in the testing dataset. Let be the number target links to predict. Then, the inference time complexity of PRB for F links is (ndp)) + O(.P). The first term is the cost of calculating the exploitation-exploratio score for each node. The second term is the cost of PageRank [42] The comparison with existing methods is listed in the following table:
In Figure 5 we analyze the running time of the internal components of PRB and PRB-Greedy (Algorithm The comparison of the internal components reveals that the Random Walk phase accounts for 10% (PRB) and 6.3% (PRB-Greedy on average of the total running time across seven datasets. Previous results also demonstrate that PRB significantly outperforms EE-Net which solely relies on the peploitation-Explortttt the Random Walk component.
framework, by dedicating small additional portion of time to
By recording the total training time of 10,000 rounds, we also compare PRB with other bandit-based baselines in Figure Across all datasets, NeuralTS achieves the minimum average running time at 10.9 minutes, while PRB has the maximum at 17.5 minutes. Additionally, given that the Random
16

---

Neural UCB
Neural TS
Neural Greedy
EE-net
PRB-Greedy
PRB
25
time/min
15
Movielens
Facebook
Amazon Fashion
Citeseer
Pubmed
Figure 4: Running time comparison of PRB and handit-based baselines.
Explotattio-Explraate Rondom
Exploitation- Expleratooon
Random Walk
Figure 5: Proportion running time for PRB-Greedy (left) and PRB (right) between exploitation- exploration and random walk.
Walk component takes only minimal portion of our algorithm's rumning time, the average running times are relatively close between PRB-Greedy (15.4 minutes) and Neural Greedy (14.8 minutes), and between PRB (17.5 minutes) and EE-net (16.7 minutes). The comparative analysis reveals that while PRB incurs a relatively extended running time, it remains competitive with established baselines and demonstrates significant enhancement in performance. This observation underscores the efficacy of PRB and supports its potential utility in practical applications despite its temporal demands.
Table rreporrs the inference time (one round in seconds) of bandit-based methods three datasets for online link prediction. Although PRB takes slightly longer time, remains in the same order of magnitude the other baselines. We adopt the approximated methods from [2) for the PageRank component to significantly reduce computation costs while ensuring good empirical performance.
Table reports the inference time (one epoch of testing in seconds) of graph- based methods on three datasets for offline link prediction. PRB faster than SEAL and shows competitive inference time as compared to other baselines.
Methods
Cora
Pubmed
Collab
Methods
MovieLens
GrQc
Amazon
SEAL
6.31
22.74
68.36
NeuralUCB
0.11
0.01
0.02
Neo-GNN
0.12
0.24
9.47
Neural Greedy
0.14
0.02
0.03
BUDDY
0.27
0.33
2.75
EE-Net
0.17
0.03
0.04
NCNC
0.04
0.07
1.58
PRB
0.20
0.03
0.04
PRB
0.11
0.58
3.52
Table 5: Inference Time (s) of PRB and bandit- based methods for online setting
Table 6: graph-based methods for offline setting
Inference Time (s) of PRE and
17

---

Movieters
1750
1750
1500
1500
1000
1000
750
750
500
500
Groedy
PRB Creesy
PRB
PRB
MRB:P
(10%--4)
PAB: Prior 110%
2000
4000
5000
9000
10005
1005
2000
5000
4203
5000
Rounds
Aounds
2300
Phoebook
4020
GrO:
3500
2014
1500
2000
2000
500
Greedy
Greedy
500
PRB
(10%)-6)
PAB (10%6-G)
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
2500
Dore
2500
Citwuerr
2000
2000
1300
1500
boguss
500
Groody
500
(20%6-0
(10%--)
2000
2003
Rounds
Rounds
Puomed
1500
1250
750
500
PRB-Greedy
250
Rounds
Figure 6: Regret Comparison of PRB-Greedy, PRB, and PRB-Prior (mean of 10 runs with standard deviation in shadow, detailed in Table 4 and I.
18

---

Movieters
1750
1500
baver
1.00
1000
750
500
320
ExePPR
Elnet
EveRPR
PRB
PRB
2000
4000
5000
9000
10005
1005
2000
3000
5000
Rounds
Aounds
2300
Phoebook
4020
GrO:
3500
20141
1500
Rog
2000
2000
500
EEnet BuePPR
EEnet EuePPR
500
PAB
PAB
2000
4000
5000
8000
10000
2000
4000
6000
8000
10000
2500
Dore
2500
Citrueer
2000
2000
1500
1500
500
500
2000
Rounds
Rounds
Puomed
1500
1250
730
530
EEner
250
EvespR
PRB
Rounds
Figure 7: Regret Comparison of PRB, EEnet, and EvePPR (mean of 10 runs with standard deviation in shadow, detailed in Table
19

---

A.3 Additional Ablation and Sensitivity Studies
PRB variants. To extensively evaluate PRB in our experiments, we provide the following variants. The initial graph Go only contains all nodes without any edges. PRB-Gre Greedreedy the greedy version of Algorithm by removing the exploration network, as specified in Algorithm 3 PRB-Prior (10%-G) is Algorithm I with prior knowledge by revealing 10% of training edges on the initial graph. We apply PRB-Prior in our experiments to demonstrate how extra prior knowledge about the graph improves PRB's decision-makee process.
PRB is the direct implementation of Algorithm T
Figure 6 and Table 4 highlights the regret comparison of three PRB variants: PRB, PRB-Greedy, and PRB-Prior. For both online link prediction and node classification, PRB surpasses PRB- PRB-Greedy by an average of 5.8%, highlighting the robustness of the exploration network embedded within PRB. Additionally, in online link prediction, the PRB-Prior (10%-G) variant consistently outperforms its counterparts across a majority of datasets. This is particularly evident in the MovieLens and AmazonFashion datasets, where it achieves notably low cumulative regrets of 1521 and 1408. Same online node classification, PRB-Prior (10%-Gi demonstrates exceptional performance on two out of three datasets, recording cumulative regrets of 1804 in Cora and 21558 in Citeseer. These results emphasize the benefits of incorporating prior knowledge within PRB to enhance predictive accuracy.
Effectiveness of Bandits and PageRank. In Figure 7 we compare the performance of PRB with that of EvePPR 42) and EE-Net [2). which represent methodologies based PageRank and contextual bandits respectively. On one hand, PRB significantly outperforms EvePPR by integrating the exploitation and exploration strategy. which enhances PageRank's decision- making capabilities. On the other hand, PRB surpasses EE-net by leveraging a more comprehensive understanding of the input graph's 's structure and connectivity through enhanced PageRank. Overall, PRB consistently achieves lower regrets compared to both EvePPR and EE-Net, demonstrating the effectiveness of combining the exploitation-exploraiie with PageRank.
B Limitations
In this paper, propose the PRB algorithm that integrates the exploitation-cxplraatie of contextual bandits with PageRank. We do not investigate other integration methods, such as combining such exploitation-explraaiie
with other Random Walk algorithms or GNNs. We also evaluate PRB on online link prediction and node classification. Several other real-world tasks, such as Subgraph Matching and Node Clustering, remain unexplored. Our future research will extend PRB these and additional related tasks 77 56 to assess its broader implications.
C Graph Dataset Statisties
Cora
Citeseer
Pubmed
Collab
PPA
DDI
#Nodes
2,708
3,327
18,717
235,868
576,289
4,267
#Edges
5,278
4,676
44,327
1,285,465
30,326,273
1,334,889 fixed 312.84
Splits
random 3.9
random 2.74
random 4.5
fixed 5.45
fixed 52.62
Average Degree
Table 7: Dataset Statistics
The statistics of each dataset are shown in Table 7 Random splits training, validation, and test set respectively.
70%, and 20% edges for
20

---

D Variant Algorithms
Algorithm 2 PRB-N (Node Classification)
Input: [1, /2. T, Go. 7,, 12 (learning rate)
I: Initialize 0g 0j
2: for t= 1....... T do
3:
Observe serving node Us, candidate nodes V. {Ū1, 02...... ..., contexts X and Graph
G,-1
4:
for each U1 E V. do
5:
h,[i] = fi (Te, 0/-1) fo (Ø (11,));
6:
end for
7:
Compute P, based Gt-1
8:
Solve = aP.v + (1 (x h;
9:
Select i = arg EVV, [c]
10:
Observe r,
if r, == then
12:
Add [Uz, "t,āl to G and set as G:
13:
else
14:
G: Gi-1
15:
end
0: 0=00 0/1111111 - 111 V 0:_, L (2.35150))))
16:
17:
0 = 0--1 - V2 09_ L ((0(2,,)) (
18:
end for
Algorithm 3 PRB-Rrree PRB-Greedy
Input: S2. T, Go. 7)1 72 (learning rate)
1: Initialize 0/. 68
2: for t= 1,,,...... ... do 3: Observe serving node itz, candidate nodes V., contexts Xr and Graph G.-1
4: for each V1 V4 do
5:
[ fi (Ir, 11
6: end for
7:
Compute P, based Gt-1
8: Solve v, = aP.v, V + (1 (1--0 a:) h,
9: Select i arg EV,, Vz
Observe r
11:
if r, 1 then
Add 21 al Gi-1 and as G2
else
14:
G: = Gi-1
end
8. = -AL1 m1 Vot L (2.0
17:
end for
21

---

E Proof of Theorem 5.1
E.1 Preliminaries
Following neural function definitions and Lemmas [13] given an instance v, we define the outputs of hidden layers of the neural network (Eq. (5.4):
ho z, by (Wih E [L 1].
Then, define the binary diagonal matrix functioning ReLU;
Dj = diag(1 (1 ((Whhi-))),.... (((Whht-))))) ((.)))))........))))))))))....
[T--1] -
Accordingly, the neural network (Eq.
5.4 is represented by
L-1
f(x;0)- WL( II D,Wi2 [ml
(E.1)
and
h Woll D, D, WE --pl=
Vw.
(E.2)
Here, given constant R >> 0, we define the following function class:
B(G.. R) = {o R ||0 Bul2 - R/ R/m///}.
(E.3)
Let L, represent the squared loss function in round t. We use 2 22. ................................ Ure represent all the context vectors presented in 7 rounds. Then, we define the following instance-dependent complexity
cotppppeeeeecooooeeitietccc term:
Tk Σ
Ve w R) = inf (B,(BO.
((((zr)) -
(E.4)
Then, we have the following auxiliary lemmas.
Lemma E.1. Suppose m, 71, 112 satisfy the conditions in Theorem 5.1
With probability at least
1 (TTb) exp( exp(=S(w==15 L)) over the random initialization, for all E [T], E [k], 0 satisfying
||0 f S w with OLL m]
))),
), it holds uniformly that
(f), O0(1.
(2), Vo 0)112 OO(DD)
33)
Lemma E.2. Suppose m. Th 72 satisfy the conditions in Theorem
With probability at least
1 1- -TOO. exp( - (1mm@mm2 2/3 L.),, for all t E [T], E [k], 0, 8' (or θ
satisfying ||e 0,l12, 1|0'
Boll2 S w with w S OLL 9/2 log m]-3), it holds uniformly that
[f 0) f(x; 6') o fzz 8'). 0')l 1/3
1/3 1 log (ogmm)(60 0' 1'
Lemma E.3. Suppose m, m1. 172 satisfy the conditions Theorem 5.7
With probability at least
1 1-0 exp(-9((m)) (mp(-((m=22)))) (Xp(-S((m=2 for all t E [T). i E [k). f H' satisfying || 0ol12, 110' - Boll2 S w with < O(T. [ m] -3), it holds uniformly that
(1) (z - f(x; 0') < O(wVD)+
/lg m))
(E.5)
Lemma E.4 (Almost Convexity). Let C,) (f(zr00) r1)2 Suppose m, Th 722 satisfy
the conditions in Theorem 5.1 With probability least 1 O(TkL?) (mw L)] over randomness of t2. for all TT, and 0, satisfying ||0 0oll2 & w and 1| Aull2 S w with
w < OLL <L m] -3/2), holds uniformly that
L,(0') > L,(0) (V)C,(0), 0)
where 1
22

---

Lemma E.5 (User Trajectory Ball). Suppose m. 71 122 satisfy the conditions in Theorem 5.1 With
probability at least 1 - (TKLL)
L)] over randomness of Bo for any R > 0. it holds
uniformly that
||0 0oll2 O(R/m)/4), [T].
Lemma E.6 (intance-dependenn Loss Bound). Let (0) = (f -
r2)2222222 Suppose m. 71 7/2
satisfy the conditions Theorem 5.1 With probability at least 1 - O(TkL3) expl expp-50(mm)) Nm 2/3 L)]
over randomness of 01, given any R 0 holds that
T
T
TLR vm
Σ (.),.) S Σ 00)))
+ O
(E.6)
m
where 0" = arginleeB(to...
Σ. L.)
E,2
Regret analysis
Lemma E.7. Suppose m, nh T2 satisfies the conditions in Theorem 5.1 In round t E [T], let be the index selected by the algorithm. Then, For any E (0, 1), R >> 0, with probability at least 1 for t [T), it holds uniformly
E [100, + f2(0((0,,)) 0211) -rrji 17
(E.7)
V R) + O11)
Vt
where Hi = (x,,50 -0,,,or,, r r.,)+= represents of historical data selected by n. and expectation is taken over the reward.
Proof. First, according to Lemma E.5
og....,0f 0,-1 all are in B(0o, R/m²//), Then, according to
Lemma F.1 for any E Rd || it holds uniformly [i (x 02) + f2(0(11,;;;03) re ((1). Then, any r E [4] define
V, = E ((a(o(=,)):00-111 (rr,3 fi fi 35 ((=,,;0+11))) 0-1))1|
(E.8)
12:6((,,;):60 (rr,3 - f1 07 0111)) 1))
Then, we have
E V
F,
E x
[fa [f: (r,
2): (r,,3 fi fi r.
(E.9)
where F7-1 denotes the r-algebra generated by the history H--1-
Therefore, the sequence {V, Vy is the martingale difference sequence. Applying the Hoeffding- Azuma incquality, with probability at least 6, we have
2 1og(1/5)
P
V
E V
S
(E.
t
r=1
23

---

As 11 is equal to O, we have
E [1)( - (r,,3 - f1 0
2log(1/6)
(E.11)
f2 (b( (Fr,3 f1 (x 0 7- 11) +V
For Ia. based on Lemma E.6 for any 0' satisfying 10" - -0il2 S R/m//44 with probability at least
1 - 6, we have
13 5 Vt
(f((((,,)):0-11 (rr,5 --ffi f1(0,,800
Σ (f(0((,))))) - (r., - fi (=(=,,:0--1))) +
O Vt
(E.
17
INE
V0,, R) + O1)
where (a) is based on the definition of instance-dependent complexity term. Combining the above inequalities together, with probability least 6, we have
E (1(0(e,,)):00111 (rr.) -i Σ
(E.13)
(bu, R) + 0(1)
2 2log(O(1))
Vi
The proof is completed.
Corollary E.1. Suppose m, 12 satisfy the conditions in Theorem 5.1 For any E TT. let i be the index selected by some fixed policy and rı, the corresponding reward, and denote the policy by π.. Let 0 be the intermediate parameters trained by Algorithmm using the data select by x²" Then, with probability least (1 5) over the random of the initialization, for any 5 E (0, 1), R 0, it holds that
[ (1is- (x ( (T" H;
E
Pr...
T=1
(E.14)
/ (0b. R) + 011) 2 2log(O(())()
Vt
where Ht-1 (Ir T F represents the historical data produced by n² and the expectation is laken over the reward.
Define g(rx;0VVo f(z;;0) 0) for brevity.
Lemma F.8. Suppose m satisfies the conditions in Theorem 5.1 the initialization, there exists O' E B(0,, (1(33/2)), such that
With probability at least 8 over
Tk
El(re - (xx: 01)2//1 5 (Vālog(1 + Tk) log 8 + +++1)
- + Tk).
24

---

Proof.
Tk
(r= - f(x(; 01)
TK
Σ (v((z)) - f(x1;;1))
t=1
2 TK
(v log
(det(Ar)
(T Vlg' m/3
20
2log + +S+11 det(I)
11a (o)l:; 2TK. .0 Σ 1=1
(6)
dlog(1 + Tk) 2log + + +5+11
ddlog( + Tk) +1) + 0(11,
where (a) is based Lemma E.9 and (b) is application of Lemma 11 in and Lemma E.12 and (1) is induced by the choice of m. By ignoring (11), The proof is completed.
Definition E.1. Given the context vectors {at)i=1 and the rewards {rilE1 then we define the estimation Og via ridge regression:
A. I+ Σ gla, 0o)g(;;00)
b: rig(a; 0o)
0. = A,
Lemma E.9. Suppose m satisfies the conditions in Theorem 5.1 With probability at least over the initialization, there exists E B(0.. (1(T3/2)) for all E [T), such that
lv(x))- 10)= (V
det(A det(A.))
(
Vrogs m
- 2 log d + s51) (1g(;;;;))) 00)la, +
det(I)
m!!
Proof. Given a set of context vectors {x) with the ground-truth function / and a fully-connected neural network f, we have
(((x)) f(xx:(0))
$ v(x))) - (g(z); 0o), (g( 0.)) + fzz; 8¹) (g(x;; 0o). 0.)
where 0' is the estimation of ridge regression from Definition E. Then, based on the Lemma E.10 there exists 0" E R. such that h(x,) = (g(2,, 0o), 0*). Thus, we have
M((x)) (g(#;; 0o), 0.)
= Ko(on 00), 0*) - (0(z): 0o), 0.)
so (1/oss dde((Ar)
log 5 + S (1a(z 00)lla;
det([))
where the final inequality is based on the the Theorem 2 in with probability least for any t e [T].
Second, need to bound
[(xx; - (g(ar; 0n), 0.)
< 11(m;; 0¹) (g(x;; 0o), 0' 0o)
+ (glar 0o). - 00) - (0(x,;00),00)
25

---

To bound the above inequality, we first bound
f(z;; 0*) (o(ari 0' -oo = - f(x4;00) - (0), 0f - -80)
50( V logm)
O(14/2)
where we initialize [(x;; 0o) = 0 and the inequality derived by Lemma R.2 with w Next, need to bound
m174
(g(te;;0)) - 0o) - (g(es; 0o); 0.}l
= (1( 0o). (0' 0o 8.171
<11g(1;:00) A." 110' - 00 ŌellA.
119(2e;00)1 A, ||Ac|l2 110' 0o - -rlll..
Due to the Lemma E.12 and Lemma E.11 we have
| ||0' 6 Bell2 S (1+ (1+10(L) 1+ O(tL) 0(1).
Finally, putting everything together, have
(w(*;) f(x;;))) /0)l( A, +
The proof is completed.
Definition F.2.
G (0) [0( 0o), ..c......9((,,, fo)l E R2xT
Go [9(:1; g((T::))) RPxTK
r= (ri,'., ,r)) ERT
G and are formed by the selected contexts and observed rewards in T rounds, Go are formed by all the presented contexts. Inspired by Lemma B.2 in 1761. with 7 m m1/4 define the auxiliary sequence following:
0o = ( g(++1) = ((و - (o) (I
0o) -r) (000)-00)
Lemma E.10. Suppose m satisfies the conditions in Theorem 5.1
With probability at least 1 6 over the initialization, for any [T), [k],, the result uniformly holds:
ho, (Te.s) (g( 0o), , 0" 0o).
Proof. Based on Lemma E.13 with proper choice of have
GJ Go 2 H
|G]] Go
H pl = H A01/2 H/2 ž 0.
Define h [hw, (a1).... ... Bur (ITT)]- Suppose the singular value decomposition of Go is
PAQ T P RoxTK A RTRXX E RTTTTR then, A - 0. Define 0r 0 PA PA- h.
Then, we have
G (0" 0o) QAP PA 'QQ hh=h
which leads
T k
Σ)
(hr, (Ir,e) - (g(2,,100)) 00), - -o)) = O.
1=1
Therefore, the result holds:
||0 - h TQQ - h hT Go) < 2h T -
(E.15)
26

---

Lemma E.11. There exist 6' E B(du. /(T L + vTJ), such that, with probability at least 1 - 6, the results hold:
(1) 0ol12 - O(T + VT)
m//4 (2) - dn - 0.112 $ 1+ O(TL)
Proof.
The sequence of 80) is updates by using gradient descent the loss function:
min 2( [ - )
rr12 + mn
00 0
For any j > 0, the results holds:
|| |F S VT
max [g(zz; 00)ll2 S O(VTL). [E[T]
where the last inequality is held by Lemma
E.1
Finally, given the j >> 0.
T//++ VTX))
||00] 10 S n |
0o) (0 - 0o) -r) +(0(0) 60) -
m!/4
(E.16)
For (2), by standard results gradient descent on ridge regression, g(i), and the optimum is g + 0.. Therefore, have
||0 g(o) - 0.11 - -11
maj 2 (C(B(0) C(( + 0.)
2(1 nA E(0(0)
2(1 - 7mA))
||=12
X
2
T(1 -nA
X
By setting À - 1 and j = log((T + O((T log(1 - m m1/4), we have ||00] - 0o -0 1 <
1+0(TE)) Replacing i and X in (E.16) finishes the proof.
Lemma E.12. Suppose m satisfies the conditions in Theorem 5.1 over the initialization, the result holds:
With probability at least 1 -
||AT||2 1 O(TL)
dct Ar dlog(1 + TK) +
log
det
Proof. Based on the Lemma E. for any & E (g( 00)112 S OVVL). Then, for the first item:
T
|| Ar = |I +
Σ
g( 00)g(((:0)) 112
(=1
T
[1]| + Σ
g 00)g((r; 0o) T 1|2
11
|1 11 <1
Next, we have
det( AT) log dIt(I)
Tk g( (0)g(2;;00))) = det(I + G
log det(I +
27

---

Then, we have
log GoG))
log ded ( - H))
< log de + (II+ H) (G. H))
I log d + [[I+ H) G H
< log H) Go H|
+ +1
dlog(1 Tk) + 1.
The first inequality is because the concavity of det: The third inequality due to |[ HA
'Ile < ||F S <T; The last inequality is because of the choice the m, based on Lemma
E.13
The last equality is because of the Definition of d. The proof is completed.
Lemma E.13. For any 8 (0,1), if = 22 1 Log((TkL/8) ) the results hold:
then with probability at least 1 - 5,
[GoG. H||F S.
Proof. This is an application of Lemma B.1 in 76 by properly setting
Lemma E.14 (Exactness of PageRank
When PageRank achieves the stationary distribution,
V.
aa. h,-
Finally, we provide the proof of Theorem 5.1
Proof.
v][("] v
=v][i"] V. [8] v. vi
(1)
[v][A" ve[a"] v v
<[v]['1 1.[7"] [v vill
<2 34 vall2
(2)
1
1 - aP, h
yt
aP,
lly: h2ll2
aP
where (1) is by the choice of PRB and (2) is based on the exact solution of PageRank [42] Let Amax be the maximal eigenvalue of P.. Because P, stochastic matrix, Amax Then, have
I aP, z (1 admax 1 1 (1 - a.I.
Accordingly, we have
1y
htll2
lly: h4ll2 lly: -hll2-
P
2
0
28

---

Then, based on Corollary
E.1 Lemma E.8
and Lemma E.3
with shadow parameters, we have
y
hell2
Σ (v(a),)) - (f2 (z(r)) +
Σ
life (o (21,)); - -
Õ (0o: Rj)
2
k
Vi
<ō(v v Tk/T))
V max(d, $2).
To sum up, we have
T [vili*] vi(1)
R
T Ily, h2l2
[=1
< Ö6( dkT) V / 52)
The proof is completed.
29

---

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 included discussion for our contributions in the Abstract and Intro- duction.
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 included the discussion of the limitation in the Appendix B
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]
30

---

Justification:
Please see theoretical analysis section and appendix for details.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but 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 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please appendix and submitted source 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 to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 are appropriate to the research performed.
While NeurIPS 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 to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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 to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer: [Yes]
Justification:
We include the source code along with our submission.
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 guwdes/dde/eeee Cooeeeoodeesssseeeeee 7/nips.com htte:/uulllllliiieeee//eeeueaasl ssiniiiiccy 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 supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: We have shown detailed experimental settings/details in the Experiment and Appendix section.
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:
We have provided standard deviation as part our experiment results.
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 enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
32

---

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 error 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 out 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 in 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: Please see the appendix where we mention our computational infrastructure and time of execution.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpp/////eerppp....ppppptttette
Answer: [Yes]
Justification:
We confirm this perform conform with the NeurIPS Code of Ethics.
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 circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in 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:
This paper does not perform 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.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
33

---

The conference expects that many papers will be foundational research and not tied 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 being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
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:
This paper does not include any data or models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 require this, but we encourage authors to take this into account and make the best faith effort.
12. Lieenses 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: We have credited correctly for the existing data and models referred.
Guidelines:
existing assets. The authors should cite the original paper that produced the code package or dataset.
The answer NA means that the paper does
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
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.
34

---

If this information is 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: [NA]
Justification: No new datasets are introduced.
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 was 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. Crowdsourcing 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: No human subjects are involved.
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with human subjects.
Including this information in 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 the NeurIPS Code of Ethies, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No human subjects are involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
35


Reviews:
[{"review_id": "X9u4MohpPq", "reviewer": "Reviewer_616o", "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.", "questions": "--The inference time should also be compared between the bandit methods and the graph based methods for link prediction in the experiments.", "limitations": "Limitation should be provided.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "--It is novel to combine contextual bandits with PageRank to find a better tradeoff between exploitation and exploration with graph connectivity.\n\n--Both contextual bandits and link prediction models are listed in related work. Moreover, both kinds of methods are compared as baselines in the experiments.\n\n--Comprehensive experiments are conducted to verify PageRank Bandits’ effectiveness and ablation study is also done to indicate that the model design is reasonable.\n\n--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.\n\n--Contextual bandits have been widely deployed in practice for online personalization and recommendation tasks.\n\n--Experimental setting is too simple to be self-contained. Training details are missing. \n\n--Font sizes of figures in the appendix are small.\n\n--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.\n\n--The inference time should also be compared between the bandit methods and the graph based methods for link prediction in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n## Q1: Advantages of solving link predictions in the contextual bandit setting   \nPlease 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.\n\n---\n## Q2: Experiment setting   \nPlease 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.\n\n---\n## Q3: Ablation study of bandits and PageRank    \nWe'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).   \n\nIn 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.\n\n---\n## Q4: Inference time comparison   \nWe recorded the inference time of PRB and competitive baselines in both online and offline settings.\n\nThe 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.  \n| Methods   | MovieLens | GrQc  | Amazon Fashion |\n|-----------|-----------|-------|----------------|\n| NeuralUCB | 0.11      | 0.01  | 0.02           |\n| NeuralTS  | 0.10      | 0.01  | 0.02           |\n| EE-Net    | 0.17      | 0.03  | 0.04           |\n| PRB       | 0.20      | 0.03  | 0.04           |\n\nThe 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.\n| Methods | Cora  | Pubmed | Collab |\n|---------|-------|--------|--------|\n| SEAL    | 6.31  | 22.74  | 68.36  |\n| Neo-GNN | 0.12  | 0.24   | 9.47   |\n| Buddy   | 0.27  | 0.33   | 2.75   |\n| NCNC    | 0.04  | 0.07   | 1.58   |\n| PRB     | 0.11  | 0.58   | 3.52   |\n\n---\n## Other Suggestions  \nWe 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.\n\n---\n**Reference**   \n[1] Everything Evolves in Personalized PageRank. WWW 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": "7dsLA0kPQk", "reviewer": "Reviewer_EydH", "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.", "questions": "See above.", "limitations": "See above.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The problem is interesting and the paper is organized well.\n2. 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.\n2. For the node classification, how to pre-determine the number of clusters?\n3. For the PageRank, whether the hyperparameter $\\alpha$ need to be learned, and how to determine the best value?\n4. Link prediction is well studied problem, why do we really need bandits to study this problem? The proposed reason is not very convincing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n## Q1: Related work of temporal Link prediction\nThank 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.\n\n**Related Work**. \nRepresentation 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. \n\nAs 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.\n\nWe will include all of these discussions in our revised version to broaden the scope of our method.\n\n**Additional Experiment**.\nTo 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].\n\n\n**The results are reported in Table 2 of Global PDF**, with baseline results sourced from [1].\n\n\n\n\nPRB 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.\n\nTo reproduce the results, please find the codes in our newly submitted anonymous link. \n\n---\n## Q2:  Number of clusters in node classification\n\nWe'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.\nThen, 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.\n\n---\n## Q3: Choice of $\\alpha$\n\nIn 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.\n\n---\n## Q4: Motivation of solving link predictions in the contextual bandit setting\n\nPlease 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.\n\n---\n**Reference**\n\n[1] FreeDyG: Frequency Enhanced Continuous-Time Dynamic Graph Model for Link Prediction. ICLR 2024 \\\n[2] Towards better dynamic graph learning: New architecture and unified library. NeurIPS 2023 \\\n[3] Do we really need complicated model architectures for temporal networks? ICLR 2023 \\\n[4] Inductive representation learning on temporal graphs. ICLR 2020 \\\n[5] Inductive representation learning in temporal networks via causal anonymous walks. ICLR 2021 \\\n[6] Temporal graph networks for deep learning on dynamic graphs. arXiv 2020 \\\n[7] Everything Evolves in Personalized PageRank. WWW 2023 \\\n[8] Fast and accurate random walk with restart on dynamic graphs with guarantees. WWW 2018\\\n[9] Temporal pagerank. ECML PKDD 2016", "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": "5NpCYeEqOx", "reviewer": "Reviewer_AzV9", "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.", "questions": "1. Please respose the above weaknesses first.\n2. In practical experiments, how are the transition matrix and the parameter $\\alpha$ chosen in the PRB algorithm?", "limitations": "The authors discussed the limitations in the Appendix.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The integration of PageRank with contextual bandits is a compelling concept, and the motivation behind the proposed PRB algorithm is clear.\n2. Regret analysis validates the PRB algorithm's efficacy, demonstrating that its cumulative regret approaches sublinear growth.\n3. The PRB algorithm exhibits robust performance across real-world tasks, achieving impressive outcomes in both online and offline settings.\n4. 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.\n2. The complexity analysis of the PRB algorithm, including both time and space complexity, is not thoroughly discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n ## Q1: Experiment setting \nPlease 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.  \n\n---\n## Q2: Time and space complexity   \n**Time Complexity:** \nLet $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.\n\n**Online Setting:** \nLet $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.\n\n**Offline Setting:**\nLet $m$ be the number of edges in the testing dataset. Let $F$ be the number of target links to predict.\nThen, 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].\nThe comparison with existing methods is listed in the following table:  \n| Method | Complexity |\n|--------|------------|\n| SEAL   | $O( n^{l'+1} p^2 F  )$ |\n| BUDDY  | $O(n^2 p + nh +(h + p^2)F )$ |\n| NCNC   | $O(n^2d + n d^2 + (n^2d +nd^2)F )$ |\n| PRB    | $O(ndp) + \\tilde{O}(mF)$ |\n\n $l'$ is the number of hops of the subgraph in SEAL and $h$ is the complexity of hash operation in BUDDY.\n\n**Space Complexity:** The space complexity of PRB is $O(nd + m)$ to store the context vector for each node and run PageRank.   \n\n| Method | Complexity |\n|--------|------------|\n| SEAL   | $O(n^{l'+1}d)$ |\n| BUDDY  | $O(d + h)$ |\n| NCNC   | $O(n^2d)$ |\n| PRB    | $O(n + m)$ |\n\nMoreover, we recorded the inference time of PRB and competitive baselines in both online and offline settings.   \nThe 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.\n| Methods   | MovieLens | GrQc  | Amazon Fashion |\n|-----------|-----------|-------|----------------|\n| NeuralUCB | 0.11      | 0.01  | 0.02           |\n| NeuralTS  | 0.10      | 0.01  | 0.02           |\n| EE-Net    | 0.17      | 0.03  | 0.04           |\n| PRB       | 0.20      | 0.03  | 0.04           |\n\nThe 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.\n| Methods | Cora  | Pubmed | Collab |\n|---------|-------|--------|--------|\n| SEAL    | 6.31  | 22.74  | 68.36  |\n| Neo-GNN | 0.12  | 0.24   | 9.47   |\n| Buddy   | 0.27  | 0.33   | 2.75   |\n| NCNC    | 0.04  | 0.07   | 1.58   |\n| PRB     | 0.11  | 0.58   | 3.52   |\n\n---\n\n## Q3: Choice of transition matrix and $\\alpha$\n**Transition matrix:**\nIn 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].\n\n**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. \nAdditionally, 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.\n\n---\n**References**   \n[1] Everything Evolves in Personalized PageRank. WWW 2023    \n[2] Fast and accurate random walk with restart on dynamic graphs with guarantees. WWW 2018   \n[3] Tpa: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. ICDE 2018  \n[4] Temporal pagerank. ECML PKDD 2016   \n[5] Efficient pagerank tracking in evolving networks. ACM SIGKDD 2015", "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": "QCVbSGJiUb", "reviewer": "Reviewer_bPwg", "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.", "questions": "* Line 135: Are there specific citations to contextual bandits literature that inspires the proposed pseudo-regret metric?\n* Line 179-180: This statement is certainly interesting, but how does it relate to PRB directly?\n\nConcerns about Clarity:\n------------------------------\n* 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.\n\n\nConcerns about PRB performance: \n----------------------------------------------\n* 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.\n* 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?\n* 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.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n* 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.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n## Q1: Clarity of descriptions\n\nThank you for your suggestion, and we will divide Section 4 into three subsections to introduce exploitation, exploration, and PageRank, respectively.\n\n---\n## Q2: Details for reproducing OGBL results\nWe 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. \n\nWe also provide detailed experimental set-ups for all our experiments including both online and offline settings on **Global Response Q2**. \n\nFor 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].\n\n---\n## Q3: Citations about pseudo-regret metric  \nOur 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].\n\n---\n## Q4: Relation of statement 179-180 to PRB\nAs 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.\n\n---\n## Q5: Clarity for node classification algorithm \nThanks 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.\n\n---\n## Q6: Offline node classification accuracy\nRegarding the reviewer's question, we evaluated the accuracy performance of the PRB against three bandit-based baselines in the offline node classification task.\n\nIn 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.\n\nThe 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.\n\n|Methods|Cora| Citeseer|Pubmed|\n|--|-|-|-|\n| NeuralTS | 73.2 | 66.5     | 82.4   |\n| NeuralUCB| 75.7 | 66.7     | 83.5   |\n| EE-Net   | 77.1 | 70.8     | 84.2   |\n| **PRB**  | **82.6** | **73.5**     | **87.4**   |\n\nWe also provide the related code in our newly submitted anonymous link.\n\n---\n## Q7: Difficulty of large graphs\nThe 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\ndespite not providing a theoretical performance upper bound for analysis.\n\nMoreover, to better show the scalability of our method, we recorded the inference time of PRB and competitive baselines in both online and offline settings.\n\n**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.\n\n**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.\n\n---\n**References**   \n[1] Neural Common Neighbor with Completion for Link Prediction. ICLR 2024 \\\n[2] Graph neural networks for link prediction with subgraph sketching. ICLR 2023 \\\n[3] Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. NeurIPS 2021\\\n[4] EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits. ICLR 2022\\\n[5] Neural Active Learning with Performance Guarantees. NeurIPS 2021 \\\n[6] Everything Evolves in Personalized PageRank. WWW 2023 \\\n[7] Neural contextual bandits with UCB-based exploration. ICML 2020 \\\n[8] Improved algorithms for linear stochastic bandits. NeurIPS 2011", "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:
---
## Q1: Advantages of solving link predictions in the contextual bandit setting   
(1)  **Adaptation over Time**.
   As links in real-world graphs are typically formed sequentially, it is natural to frame link predictions as a sequential decision-making process. Each link prediction can be viewed as an individual decision, and we introduce the regret metric to formulate this goal. To minimize cumulative regret, the model must adapt over time, leveraging the rewards from each round of decision-making. In contrast, traditional supervised models are often static; they are trained on a dataset and then make predictions on a separate testing dataset without further adaptation.

(2) **Balancing Exploitation and Exploration**.
The challenge of balancing exploitation and exploration is prevalent in link predictions. The learner must exploit previously formed links to select high-confidence links, while also exploring under-explored or low-confidence links to gather information for long-term benefit. \
*Example*: Users and videos form a bipartite graph on a short-video social media platform. In round $t$, let $u_t$ be the user being served and $H_t$ be their interaction history. The goal is to select and display videos that $u_t$ is likely to "like". By exploiting $H_t$ (e.g., $u_t$ has previously liked many sports videos), the platform recommends another popular sports video (exploitation). Alternatively, the platform could explore by recommending a cooking video uploaded by a new user (exploration), which $u_t$ has not interacted with before. If $u_t$ likes the video, it reveals a new preference; if not, it provides insights into $u_t$’s dislikes and the potential quality of the new user's content. *While this exploration may not be optimal for round $t$, it offers long-term benefits by improving future link predictions*.\
Contextual bandits offer a principled approach to managing the trade-off between exploitation and exploration, which PRB can utilize. In contrast, most graph-based methods lack an explicit exploration strategy.

(3) **Theoretical Performance Guarantee**.
 Formulating link prediction within a contextual bandit setting allows us to offer a rigorous theoretical performance guarantee for PRB. This theoretical framework ensures that the cumulative regret of PRB increases sublinearly with the number of rounds in the worst case. 
 In other words, with high probability, the number of wrong predictions PRB makes up to round $T$ is upper bounded by $\tilde{O}(\sqrt{T})$.
 In contrast, most graph-based methods do not provide such theoretical guarantees.

---

## Q2: Experiment Setting

**Online Link Prediction Setups**.
For all bandit-based methods including PRB, for fair comparison,  the exploitation network $f_1$ is built by a 2-layer fully connected network with 100-width. For the exploration network of EE-Net and PRB, we use a 2-layer fully connected network with 100-width as well. For NeuralUCB and NeuralTS, following the setting of [1,2], we use the exploitation network $f_1$ and conduct the grid search for the exploration parameter $\nu$ over {0.001, 0.01, 0.1, 1} and for the regularization parameter $\lambda$ over {0.01, 0.1, 1}. For the neural bandits NeuralUCB/TS, following their setting, as they have expensive computation costs to store and compute the whole gradient matrix, we use a diagonal matrix to make an approximation. For all grid-searched parameters, we choose the best of them for comparison and report the average results of 10 runs for all methods.
For all bandit-based methods, we use SGD as the optimizer for the exploitation network $f_1$. 
Additionally, for EE-Net and PRB, we use the Adam optimizer for the exploration network $f_2$. 
For all neural networks, we conduct the grid search for learning rate over {0.01, 0.001, 0.0005, 0.0001}.
For PRB, we strictly follow the settings in [3] to implement the PageRank component. Specifically, we set the parameter $\alpha = 0.85$ after grid search over {0.1, 0.3, 0.5, 0.85, 0.9}, and the terminated accuracy $\epsilon = 10^{-6}$.
For each dataset, we first shuffle the data and then run each network for 10,000 rounds ($t = 10,000$). We train each network every 50 rounds when $t < 2000$ and every 100 rounds when $2000 < t < 10,000$.


**Offline Link Prediction Setups**. For the graph-based methods, we strictly follow the experimental and hyperparameters settings in [4,5] to reproduce the experimental results. 
Offline link prediction task requires graph links to play dual roles as both supervision labels and message passing links. For all datasets, the message-passing links at training time are equal to the supervision links, while at test and validation time,
disjoint sets of links are held out for supervision that are never seen during training. 
All hyperparameters are tuned using Weights and Biases random search, exploring the search space of hidden dimensions from 64 to 512, dropout from 0 to 1, layers from 1 to 3, weight decay from 0 to 0.001, and learning rates from 0.0001 to 0.01. Hyperparameters yielding the highest validation accuracy are selected, and results are reported on a single-use test set.
For PRB, we use setups similar to those in the online setting. We utilize the exploitation network $f_1$ and exploration network $f_2$ both with 500-width. We set the training epoch to 100 and evaluate the model performance on validation and test datasets. We utilize the Adam optimizer for all baseline models. For PRB implementation, We utilize the SGD optimizer for $f_1$ and the Adam optimizer for $f_2$.    

--- 
**References**    

[1] Neural contextual bandits with UCB-based exploration. ICML 2020\
[2] Neural Thompson Sampling. ICLR 2021\
[3] Everything Evolves in Personalized PageRank. WWW 2023\
[4] Neural Common Neighbor with Completion for Link Prediction. ICLR 2024\
[5] Graph neural networks for link prediction with subgraph sketching. ICLR 2023

Meta-review: The authors cast the link prediction problem as a sequential decision-making process. They also propose a fusion algorithm called PageRank Bandits, which brings together contextual bandits with PageRank. The reviewers all agree that this paper is well written, and the idea of doing link prediction in the framework of contextual bandits is interesting. The authors should motivate the use of contextual bandits more. They should also clearly specify the choice of hyperparameters and experimental settings to enhance the reproducibility of the results.
Decision: Accept (poster)