--- title: "Bandit Online Learning on Graphs via Adaptive Optimization" authors: - "Peng Yang" - "Peilin Zhao" - "Xin Gao" doi: "10.24963/ijcai.2018/415" url: "https://ijcai.org/proceedings/2018/415" pdf: "https://ijcai.org/proceedings/2018/0415.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "2991-2997" track: "Main track" keywords: - "Uncertainty in AI: Uncertainty in AI" - "Machine Learning Applications: Networks" - "Machine Learning: Online Learning" --- # Bandit Online Learning on Graphs via Adaptive Optimization Peng Yang, Peilin Zhao, Xin Gao *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 2991-2997. DOI: [10.24963/ijcai.2018/415](https://doi.org/10.24963/ijcai.2018/415) ## Abstract Traditional online learning on graphs adapts graph Laplacian into ridge regression, which may not guarantee reasonable accuracy when the data are adversarially generated. To solve this issue, we exploit an adaptive optimization framework for online classification on graphs. The derived model can achieve a min-max regret under an adversarial mechanism of data generation. To take advantage of the informative labels, we propose an adaptive large-margin update rule, which enjoys a lower regret than the algorithms using error-driven update rules. However, this algorithm assumes that the full information label is provided for each node, which is violated in many practical applications where labeling is expensive and the oracle may only tell whether the prediction is correct or not. To address this issue, we propose a bandit online algorithm on graphs. It derives per-instance confidence region of the prediction, from which the model can be learned adaptively to minimize the online regret. Experiments on benchmark graph datasets show that the proposed bandit algorithm outperforms state-of-the-art competitors, even sometimes beats the algorithms using full information label feedback. ## Full text ## 1 Introduction Existing online learning on graphs usually adapts the graph Lapalacian regularization into ridge regression [Herbster and Pontil, 2006; Gu et al., 2013], which may not guarantee sufficiently high performance in a non-stationary environment where the label for each node (i.e. xt) is adversarially generated [Vovk, 1998]. To solve this problem, online learning has been extensively studied in the adversarial setting [Moroshko et al., 2015; Kuznetsov and Mohri, 2016]. Although those methods are applicable, they assume that the true label is provided for each node, which violates many real-world scenarios where labeling is very expensive and the label oracle may return partial label feedback for each prediction. To address this issue, online multi-class classification with bandit feedback has been studied recently: in each round of the prediction of a given node, the learner receives a binary feedback indicating whether the predicted label is correct or not. An early work of this problem is Banditron [Kakade et al., 2008], a first-order bandit online algorithm. However, this model cannot optimize the direction of update. To solve this issue, a second-order bandit algorithm was proposed, which tracks a spectral structure of observed inputs [Crammer and Gentile, 2013]. However, previous algorithms were seldom designed on graphs, among which Gu et al. [Gu and Han, 2014] derived a bandit online algorithm with Laplacian regularization. Although this method is effective in solving the bandit problem, it is limited by a fix-margin rule for model learning, instead of an adaptive learning strategy [Yang et al., 2015]. Recent studies focus on the general contextual bandit problem on graphs [Carpentier and Valko, 2016; Alon et al., 2015], where context-reward pairs are generated i.i.d., which we do not assume here. For a comprehensive survey on Online Learning, please refer to [Hoi et al., 2018]. In this paper, based on the observation above, we present an adaptive optimization framework for online classification on graphs. The derived online algorithm can bound the choices of an adversary under a stochastic setting of data generation [Abernethy et al., 2009; Vovk, 1998]. In particular, we propose an adaptive large-margin update rule to prioritize the informative labels. The theoretical result shows that the proposed algorithm, thanks to the aggressive update trials, can achieve a lower error bound than the algorithms using errordriven update rules. However, this algorithm assumes that the true label is provided for every node, which is impractical in many scenarios where labeling is expensive and label oracle may only give a one-bit feedback indicating whether the prediction is correct. To solve this issue, we propose a bandit online algorithm on graphs. We adapt both confident weight and adaptive margin into bandit setting, with which the model can be learned adaptively to significantly reduce the regret of bandit online learning. Experiments on several benchmark graph datasets show that the proposed bandit algorithm outperforms several competitors, even sometimes beats state-ofthe-art algorithms that use full label feedback. Notation. With an appropriate size, an identity matrix is denoted as I, zero vector as 0 and diagonal matrix as diag(·). The inverse of a matrix A is denoted as A-1 , and the pseudo inverse as A† . Finally, the ℓ2-norm of a vector w is denoted as ‖w‖2, Frobenius norm of matrix A as ‖A‖F , trace and determinant of a matrix as tr(A) and |A|, respectively. ## 2 Framework of Graph Node Classification A graph defined by G = (V, E) consists of an vertex set V = {vi}ni=1 , and an edge set E = {eij = {vi, vj}|vi, vj ∈ V}. An adjacency matrix of the graph G is denoted as S ∈ Rn×n , where the element value Sij is computed based on the edge affinity of a pair {vi, vj}. We assume that graph G is connected and undirected. Graph Laplacian is defined by L = D - S, where D is a diagonal matrix with Dii = ∑k Sik while the off-diagonal elements are 0. The eigendecomposition of the graph Laplacian is L = VΛV⊤, where V = [v1, . . . , vn] are the eigenvectors, and Λ = diag(λ1, . . . , λn) (0 =λ1≤. . .≤λn ≤ 2) are the eigenvalues. Graph regularization [Smola and Kondor, 2003] is built based on the concept of label smoothness on the graph, i.e., ∑ni,j=1 Sij‖fi - fj‖2 = tr(F⊤LF), where F = [f1, . . . , fn]⊤ is a prediction matrix, while fi ∈ RK is node i's prediction given the class number K. We solve the problem of multiclass classification on the graph as below, where ℓ(fi, yi) is the loss suffered by the algorithm on the ith node, yi ∈ RK is the actual label of that node, and b > 0 is a trade-off parameter. In the multi-class classification with labeled and unlabeled nodes on the graph, this optimization is to learn the function F that satisfies two requirements: (i) the predictions for labeled nodes should be close to the given labels for those nodes; (ii) label-smoothness on graphs: the nodes nearby on graphs should have similar predictions. To solve Eq. (1), we consider its dual form. According to the definition of graph kernel [Smola and Kondor, 2003; Belkin et al., 2006], the function F is formulated as, where L† is the pseudo inverse of L and Ω ∈ Rn×K is a parameter matrix. We further decompose L† = ∑i 1 λi viv⊤ i as L† = X⊤X with X = [ 1 √λ1 v1, . . . , 1 √λn vn]⊤, and the kernel Eq. (2) can be rewritten as a linear model form, F = X⊤W where W = XΩ ∈ Rn×K . Substituting the graph kernel Eq. (2) into Eq. (1) with XLX⊤ = I, we have In this way, we derive an objective function similar to the ridge regression formulation. Eq. (3) can be used to derive the online learning under a new graph node representation. ## 2.1 LowRank Approximation Recall that X = [ 1 √λ1 v1, . . . , 1 √λn vn]⊤, the graph kernel F is built exactly, but the time complexity of our algorithm becomes O(n2 ), which is computationally expensive on largesized graphs. In order to make our online algorithm scalable on large graphs, we propose to choose X as follows, where d ≪ n. Thus ˜F = (∑di=1 1 λi viv⊤ i )Ω is a rank-d approximation of F, with a reduced time complexity O(d2 ) ≪ O(n2 ). We analyze the impact of the low-rank approximation on the kernel ˜F. Since λ1 ≤ . . . ≤ λn, ˜L† = ∑di=1 1 λi viv⊤ i retains the top-d largest egivenvalues of L† . According to Young-Mirsky theorem [Eckart and Young, 1936], we claim that ˜L† is the best rank-d approximation of L† . Thus, ˜F is the best rank-d approximation of F. Equipped with ˜X = [˜x1, . . . , ˜xn] ∈ Rd×n where ˜xi = [ 1 √λ1 (v1)i, . . . , 1 √λd (vd)i]⊤, the regularized Laplacian term can turn to a sparse form, i.e., tr(˜F⊤L˜F) = ‖ ˜W‖2F , while the graph regularized problem can be formulated as a lowrank form, i.e., inf ˜W ∑ni=1 ℓ( ˜W; (˜xi, yi)) + b‖ ˜W‖2F . ## 3 Online Learning on Graphs The objective of online learning on graphs aims to achieve a low regret compared to the best linear model in hindsight. Let {(x1, y1), . . . , (xT , yT )} (T ≤ n) be an arbitrary node-label sequence. At round t, an online algorithm receives a node xt, and predicts its label: ˆ yt = argmaxi∈[K](W⊤ t-1xt)i, where the model Wt-1 is learned from the previous t - 1 rounds. Then the actual label yt is revealed, the algorithm uses it to update the model and then proceeds to the next round. For any matrix U ∈ Rd×K , we denote by ℓt(U) = ‖U⊤xt -yt‖2 as the instantaneous loss of xt, and by LT (U) = ∑Tt=1 ℓt(U) as the cumulative loss over T rounds. Formally, we define the regret of the algorithm to be The objective is to let the cumulative loss of the online algorithm converge to the loss of the best linear function in hindsight. We next solve the regret in an adversarial setting. ## 3.1 Adaptive Online Optimization In the adversarial environment, the regret is solved based on a last-step min-max optimization [Forster, 1999; Yang and Zhao, 2015]. An algorithm following this objective outputs a min-max prediction assuming that the current iteration is the last one, while ˆ yt and yt serve as min and max quantifiers, respectively, i.e., the goal of the learner is to minimize the regret while the adversary is to maximize it. Note that our objective function is different from [Forster, 1999; Yang and Zhao, 2015], we introduce an adaptive-weighted cumulative loss, where {at}Tt=1 ≥ 0 are the input-dependent weights. Substituting Eq. (3) and Eq. (4) into the regret RT , our variant of the adaptive-weighted algorithm predicts, where ft = W⊤ t-1xt. We next solve the min-max adaptiveweighted function Eq. (5), starting with additional notations, The solution of the internal infimum is obtained as below. Lemma 1 For all t ≥ 1, Gt(U) = Lat (U) + b‖U‖2F is minimal at a unique point U, given by, Substituting Lemma 1 back into Eq. (5), we reformulate the objective function, ˆ yT =minˆ yT maxyT F(yt, ft), where We show that, by appropriately setting the weight aT , the min-max weighted problem could be concave in yT and convex in ˆ yT . The optimal solution of our objective function is summarized as follows. Theorem 1 Assume that 1 + aTx⊤T A-1 T-1xT - aT ≤ 0, then the optimal prediction of the min-max adaptive-weighted function ˆ yT = argminˆ yT maxyT F(yT , fT ) is Proof. The proof is provided on the website 1 . □ Remark. Although the solution is applicable for 1 + aT x⊤T A-1 T-1xT - aT ≤ 0, we make aT = 1 1-x⊤T A-1 T-1 xT in the rest of the paper. The aT depends on previous learned rounds {x1, . . . , xT } with a fixed computational cost O(d2 ). Specifically, the above model maintains two quantities: At and Bt. Inspired by [Azoury and Warmuth, 2001], we exploit the current input to predict its label ft = B⊤t-1A-1 t xt where At = At-1 + atxtx⊤t . Then its actual label yt is revealed and the algorithm updates the model in terms of Bt and At in a recursive way: Bt = Bt-1 + atxty⊤ t , and A-1 t = A-1 t-1 - A-1 t-1xtx⊤t A-1 t-1 according to Woodbury identity. In each round of update, the runtime is O(d2 ) and the required memory is O(d2 ). Assume our algorithm updates the model when an error occurs (ft · yt ≤ 0), then its mistake bound holds in the following lemma. Theorem 2 Assume {(x1, y1), . . . , (xT , yT )} is a node sequence, an online algorithm predicts with ˆ yT = arg maxi∈[K](B⊤T -1A-1 T-1xT )i, and updates AT and BT with Eq. (6). Let Z = {t | ft · yt ≤ 0} be updated trials, then the following inequality holds for any U ∈ Rd×K , Proof. The proof is provided on the website1 . □ 1 https://github.com/YoungBigBird1985/MOLG/ Algorithm 1 MOLG-F: Adaptive Optimization for Online Learning on Graphs with Full Label Feedback - 1: Input: Adjacency matrix S, rank d, and regularization parameters b and φ. - 2: Output: WT . 3: Initialize: W0 = 0,B0 = 0,A0 = bI. 4: Compute L =D-S and X fromL† ; 5: for t = 1, . . . , T do 6: Let Zt = 0; Receive xt; 7: A-1 t = (At-1 +atxtx⊤t )-1 ,Wt-1 =A-1 t Bt-1; 8: Predict ˆ yt = argmaxi∈[K](W⊤ t-1xt)i; 9: if ˆ yt ̸= yt then Zt = 1; 10: else 11: Θt = ˆ∆t -φσt; 12: if Θt < 0 then Zt = 1; 13: end if 14: end if 15: Update A-1 t = (At-1 +Ztatxtxt)-1 ; 16: Update Bt =Bt-1 +Ztatxty⊤ t ; - 17: end for ## 3.2 Adaptive-Margin Learning When our algorithm uses an error-driven update rule (e.g., ft · yt ≤ 0), it usually ignores the correctly predicted labels of low predicted confidence, especially in early stage of online learning. To solve this issue, we propose an adaptive large-margin update rule. We begin with an annotation of the prediction margin in multiclass classification, where the label vector yt ∈ RK assigns +1 to the true class entry yt, -1 to the class entry j = argmaxi̸=yt (W⊤ t-1xt)i, and 0 to the remain entries. Definition 1 Given an input xt (t ∈ [T]), the algorithm predicts its label ft =W⊤ t-1xt and updates the model whenever the function Θt < 0, where Θt is an adaptive margin towards the current prediction, The Θt is a function parameterized by ˆ∆t and σt, where ˆ∆t is the prediction margin, and σt is the confidence region of current prediction. In this way, Θt = ˆ∆t-σt acts as the lower confidence bound of the prediction. Note that the adaptivemargin conception has been studied in [Wang et al., 2012; Yang et al., 2016]. Different from the previous methods, our Θt is derived from the weighted min-max framework on graphs. We summarize the algorithm, the Adaptive Optimization for Online Learning on Graph (defined by (6), (7) and (9)), in Algorithm 1. We next theoretically analyze the effectiveness of our algorithm. In Algorithm 1, the update trials are partitioned into two disjoint sets, M = {t : ˆ∆t ≤ 0, ˆ yt ̸= yt} with M = |M| includes the indices on which an update is issued when an error occurs, and D = {t : 0 < ˆ∆t < σt, ˆ yt = yt} with D = |D| includes the indices on which an aggressive update is issued, even if the prediction is correct. Let Z = {t : Zt = 1} with Z = |Z| be the update trials containing Z = M +D. Theorem 3 Algorithm 1 runs on an arbitrary node sequence {(x1, y1), . . . , (xT , yT )}. Let ˜ L(x) = max(0, 1-x) be hinge loss, the following inequality holds for any U ∈ Rd×K , Proof. The proof is provided on our website1 . □ Remark. Since A-1 t ⪯ A-1 t-1 is decreased over t, we have x⊤t A-1 t xt ≤ . . . ≤ x⊤t A-1 0 xt ≤ 1b where b > 1 and ‖x‖2 ≤ 1. Thus, at = 1 1-x⊤t A-1 t-1 xt ≤ b b-1 , and tr(U⊤AZU) ≤ ∑t∈Z at‖U⊤xt‖2 ≤ Zb b-1 ‖U‖2F . Moreover, log | 1b AT | ≤ Kd log(1+ T Kdb ) [Moroshko and Crammer, 2014]. Due to the deduction of the aggressive update trials |D|, we claim that MOLG-F achieves a lower mistake bound than the algorithm using error-driven update rule in Theorem 2. Discussion: ∑t∈Z ˜ L(yt ·U⊤xt) is the cumulative hinge loss made by U. We rewrite the error bound as one by which the number of mistakes exceeds the cumulative loss of the best linear model over the update trials, In a low-rank setting where d ≪ T , the above bound achieves a regret of O(log T) with respect to the best linear model. ## 3.3 Online Learning with Bandit Feedback We propose a bandit online algorithm on graphs, MOLG-B, in Algorithm 2. Note that MOLG-B is the first work that adapts both confidence weight and adaptive margin into bandit setting. Specifically, confident weight at for the parameter update can guide the magnitude of bandit learning. Moreover, different from the update rules in Confidit [Crammer and Gentile, 2013] or SOBA [Beygelzimer et al., 2017], MOLGB proposes an adaptive-margin update strategy, which updates model based on the confidence of current prediction. These techniques improve the efficiency of bandit online learning. In bandit setting, MOLG-B receives a node xt at round t and predicts its label as ˆ yt ∈ [K]. Different from Algorithm 1, the learner receives a one-bit feedback Ct ∈ {+1,-1} indicating whether the output ˆ yt is correct or not, i.e., Ct = I(yt ̸= ˆ yt). Following the setting of [Crammer and Gentile, 2013], we assume the label of a node xt is sampled with a probabilistic model, P(yt = i|xt) = 1+∆it 2 , i ∈ [K], where ∆it = ui⊤xt ∈ [-1, 1] and ∑Ki=1 ∆it = 2 - K. MOLG-B maintains a set of model parameters for multiple classes {(bi ∈ Rd ,Ai ∈ Rd×d )}Ki=1 , initialized with b0 = 0,A0 = bI. Provided with the one-bit feedback, the Algorithm 2 MOLG-B: Adaptive Optimization for Online Learning on Graphs with Bandit Feedback - 1: Input: Adjacency matrix S, rank d, and regularization parameters b, ϕ and φ. - 2: Output: WT . - 3: Initialize: bi0 = 0,Ai0 = bI for all i ∈ [K]. 4: Compute L =D-S and X fromL† ; 5: for t = 1, . . . , T do 6: Let Zt = 0; Receive xt; 7: For i ∈ [K], (Ait )-1 = (Ait-1 +aitxtx⊤t )-1 ; 8: For i ∈ [K], wit-1 = (Ait )-1bit-1 ; 9: ˆ yt = argmaxi∈[K](wi⊤ t-1xt + ϕit√σi t ), observe Ct; 10: if yt ̸= ˆ yt then Zt = 1; 11: else // we denote k = ˆ yt 12: if wk t-1 · xt < φσk t then Zt = 1; 13: end if 14: end if 15: Update (Akt )-1 = (Akt-1 +Ztakt xtx⊤t )-1 ; 16: Update bkt = bkt-1 +Ztakt ytxt; - 17: end for basic idea is to maintain a tradeoff between exploration and exploitation [Auer, 2002; Crammer and Gentile, 2013]. Intuitively, the algorithm should output the label with the largest score, i.e., argmaxi∈[K] ˆ∆it = wi⊤ t-1xt, which is called exploitation. However, if the feedback is negative, the true class is still uncertain. Thus, the algorithm tries to explore the classes with high predicted uncertainties, measured by σi t = 12 (ait )2x⊤t (Ait )-1xt. Generally, a large score of σi t infers a low confidence of the current prediction ˆ∆it . The bandit algorithm chooses an estimation from the prediction margin and the predicted confidence, so that the upper confidence bound (UCB) of the prediction is maximized, where ϕit > 0 controls the exploration-exploitation tradeoff. This UCB technique has been widely used in bandit online learning [Crammer and Gentile, 2013; Gu and Han, 2014; Beygelzimer et al., 2017]. We theoretically analyze the regret of Algorithm 2. It exploits the proofs of the lemmas in [Crammer and Gentile, 2013; Dekel et al., 2010]. Given the Bayes optimal predictor y∗ t = argmaxi∈[K] P(yt = i|xt), we aim to bound the regret, RT = ∑Tt=1 (Pt(yt ̸= ˆ yt) - Pt(yt ̸= y∗ t )) = ∑Tt=1 ∆t- ˆ∆t 2 , where Pt = P(·|x1, . . . , xt, y1, . . . , yt) is the conditional probability. Theorem 4 Algorithm 2 runs on an arbitrary node-label sequence {(x1, y1), . . . , (xT , yT )}. If we set ϕi2 t = ( b b-1 )2 (4(b-1)‖U‖2F +4γ log | 1b Ait-1 |+144 log t+4 δ ) where ℓt(U) ≤ γ, then for any U ∈ Rd×K , such that |ui⊤xt| ≤ 1, the inequality holds, with probability at least 1 - δ over T trials, where H1 = 2(b - 1)‖U‖2F + 72 log t+4 δ and H2 = 2Kdγ log(1+ T Kdb ). Proof. The proof is provided on the website1 . □ Remark. Theorem 4 shows that the regret bound of MOLGB is O(√T log T ), which is only a √T factor worse than that of MOLG-F, i.e., O(logT). However, it is worth noting that the two regrets are incomparable due to the different regret definitions in two algorithms. ## 4 Experimental Results We begin with data sets and experimental evaluation metrics, and then show empirical results of the proposed algorithms. ## 4.1 Data Sets and EvaluationMetrics Data Sets: We exploit 4 real-world graph datasets to evaluate all the algorithms: 1) Coauthor2 is a coauthor graph of the DBLP dataset, with 1711 authors as nodes and 7507 coauthored associations as edges. These authors are categorized into 4 research topics: "Machine Learning", "Data Ming", "Database" and "Information Retrieval". 2) Cora 2 is a citation graph of 2485 scientific publications and 10138 citation links. Each publication is categorized into 7 domains, "Reinforcement Learning", "Neural Networks", "Case based", "Genetic Algorithms", "Probabilistic Methods", "Rule Learning" and "Theory". 3) IMDB 3 is an up-todate movie dataset with 17046 motives as nodes and 993528 co-actor relations as edges. Each movie is labeled by one of 4 genres: "Animation", "Action", "Thriller" and "Romance". 4) PubMed 4 is a graph of 19717 scientific publications of diabetes labeled by one of 3 types. It has 88651 citation links. All graphs are supposed to be undirected and connected. In case some edges are directed, they are transformed into undirected ones. If a graph is disconnected, the biggest connected subgraph is selected for evaluation. Evaluation Metrics and Parameter Setting: We evaluate the performance of the algorithms with two measures: (i) cumulative error rate, and (ii) cumulative number of updates. The error rate reflects the prediction accuracy of the online learning while the number of updates measures the computational efficiency of an online algorithm. Note that the smaller the two measures, the better the performance of an online algorithm. In order to fairly compare the algorithms, we randomly shuffle the sample ordering of each dataset. We run all the algorithms 20 times for each dataset and compute the averaged result. We compare the proposed algorithms with five baselines mentioned in the introduction. The algorithms we studied and their parameter settings are summarized as follows: (a) GPA [Herbster and Pontil, 2006] is the first-order nonparametric online learning algorithm on graphs. (b) OSLG [Gu and Han, 2014] and MSG [Yang et al., 2016] are second-order online algorithms on graphs with full information feedback. (c) Two variants of Banditron, i.e., Confidit [Crammer and Gentile, 2013] and SOBA [Beygelzimer et al., 2017], and OSLG-Bandit [Gu and Han, 2014] are second-order online bandit algorithms. All parameters of the baselines are tuned according to their recommended instructions. (d) MOLG-F and MOLG-B are the proposed online algorithms for graph node classification with full information and bandit label feedback, respectively. For both methods, we tune the parameter φ with the grid {10-2 , . . . , 10}. For MOLG-B, we fix the exploration parameter ϕt = 0.05 for all t ∈ [T]. We set b = 10 for Cora and Coauthor and b = 100 for IMDB and PubMed due to variable graph structures. Finally, we fix d = 100 for the dimension of low-rank representation. 2 http://www.cs.umd.edu/ sen/lbc-proj/data/ 3 http://www.imdb.com/ 4 http://www.cs.umd.edu/projects/linqs/projects/lbc/ ## 4.2 Empirical Results The experimental results are presented in Table 1. The improvement of MOLG and OSLG over GPA is always significant on the four datasets. This is consistent with previous observations in online learning: the second-order algorithms are generally better than the first-order algorithms [Wang et al., 2012]. The reason is that the covariance matrix At that encodes the confidence of parameters can guide the direction of the parameter update in the learning process. MOLG-B always enjoys smaller number of updates and lower error rates than OSLG-Bandit and Banditron. The possible reasons are two folds: (1) the confidence weight can guide the magnitude and direction of the parameter update; (2) the adaptive-margin update rule can prioritize the instances with predicted uncertainty. These techniques speed up the convergence of online learning, so that the number of update and the error rate can be reduced further when the model has learned sufficient knowledge of the data. It demonstrates both the computational efficiency and label efficiency of our algorithm. MOLG-B is slightly worse than MOLG-F in Coauthor and Cora datasets. This is reasonable, since MOLG-B uses partial information labels, whereas MOLG-F uses the full information labels. Thus, the performance of the bandit algorithm should be no better than that of the algorithm in the full information setting. However, MOLG-F requires more updates than MOLG-B to achieve better accuracy. The reason is obvious: provided with one-bit feedback, MOLG-B can choose one class to update its parameter in each round, while MOLGF can exploit the full information to update the parameters of multiple classes. Overall, MOLG-B is computationally more efficient than MOLG-F. Finally, MOLG-B outperforms MOLG-F in IMDB and PubMed datasets. The reason may be due to class-imbalanced issue. In the multiclass setting, for each class, its training instances are fewer than that of negative classes (remaining K - 1 classes). MOLG-B updates one class model per trial, while MOLG-F can exploit full label information to update the models of multiple classes in each round. Thus, in MOLG-F, negative update may dominate the predictive model and lead to poor performance [Zhang et al., 2016]. ## 4.3 Sensitivity Analysis on Update Ratio In the adaptive-margin update rule, the tradeoff parameter φ has an influence on the update ratio. The model with a smaller value of φ would like to conduct a fewer number of update and vice versa. Specifically, we set the φ to {10-2 , . . . , 10} Table 1: Performance in terms of mean and standard deviation (Banditron, OSLG-Bandit and GPA update all the rounds. Bandit algorithms choose one class to update its parameter in each round. Banditron represents the best result from Confidit and SOBA) | Algorithm | Coauthor - Error rate (%) | Coauthor - #Update number | Cora - Error rate (%) | Cora - #Update number | |-------------------------------|--------------------------------------------------------|--------------------------------------------|-------------------------------------------------------------------|-------------------------------------------------------| | GPA MSG OSLG MOLG-F Banditron | 54.74±2.66 29.53±0.97 31.02±0.55 27.86±0.50 39.18±3.34 | 3422 1774±42.48 2123±37.66 1739±22.77 1711 | 58.49±2.03 18.95±0.44 20.77±0.31 18.16±0.39 41.49±0.53 | 4970 3810.8±37.49 3612.7±54.13 2629.7±25.99 2485 | | | IMDB | IMDB | PubMed | PubMed | | OSLG-Bandit MOLG-B Algorithm | 33.81±1.85 32.45±0.92 Error rate (%) | 1711 1122.5±16.90 #Update number | 28.56±1.54 23.87±1.48 Error rate (%) | 2485 1363.8±27.64 #Update number | | GPA MSG OSLG MOLG-F | 68.70±0.46 50.89±0.29 48.27±0.60 45.86±0.91 52.88±0.38 | 34092 29788±173.8 32910±409.6 22147±336.3 | 57.95±0.29 22.64±0.10 25.51±0.39 20.96±0.07 24.53±0.15 21.07±0.18 | 39434 27336±128.9 15087±231.4 17198±28.63 19717 19717 | | Banditron OSLG-Bandit MOLG-B | | 17046 | | | | | | 17046 | | | | | 46.91±0.39 | | | | | | | | | 13633±112.2 | | | | | 20.74±0.18 | | | | | 13316.7±259.2 | | | | | 45.30±1.17 | | | | Figure 1: Sensitivity analysis of the update ratio. ![Image](https://ijcai.org/proceedings/2018/fulltext/415/image_000000_8268e0566b99bafdf172f59b41be43f41dcbbcd51cdf51f48ca023ba40355dd1.png) and calculate the averaged ratio of update over the 20 times of experiments. MSG, OSLG and MOLG-F are used for comparison since other baselines update all the rounds. The result in Fig.1 shows that MOLG-F achieves the best performance consistently under different ratios of update. OSLG uses an error-driven update rule, thus ignoring the correctly predicted labels. The better empirical performance achieved by MOLG-F shows that the labels with low predicted confidence are informative to improve the performance of online model. ## 4.4 Sensitivity Analysis of Low-rank Graph Data The empirical results are affected by the rank approximation. To study the impact of the low-rank representation, we set the parameter d with the grid {10, 100, 250, 500, 750, 1000}. Coauthor and IMDB are used as the case studies since similar conclusions are obtained on Cora and PubMed. The results in Fig. 2 show that MOLG-F and MOLG-B outperform OSLG and OSLG-Bandit, respectively, under various low-rank approximations. Note that, in the bandit setting, a higher rank increases the uncertainty of the data, thus the bandit algorithms require more updates to achieve a lower or comparable error rate. In the full information setting, a higher rank increases the knowledge of the data, thus the updates can be further reduced when the model learns sufficient information. However, with a higher rank, the algorithms need higher computational time to update the model. To achieve a balance, we choose d = 100 since the algorithm achieves a good accuracy while the number of update is small enough. Figure 2: Sensitivity analysis of low rank impact on performance. ![Image](https://ijcai.org/proceedings/2018/fulltext/415/image_000001_721b427bbc0fb65857ebab0deb31b085a526c41db65e48fa836b778a84ad1db1.png) ## 5 Conclusion and FutureWork We explore adaptive optimization for online graph classification with full information and bandit label feedbacks. The main contributions of our work are four folds: (i) We propose a weighted min-max optimization framework for online learning on graphs; (ii) An adaptive-margin update rule is proposed, which achieves a lower regret than the algorithm using error-driven update rule; (iii) We adapt both confidence weight and adaptive margin into bandit setting, which significantly reduces the regret of bandit learning; (iv) the proposed algorithms outperform state-of-the-art competitors in the empirical results. In the future, we shall study several other directions for online learning on Graphs, including: online optimization of ranking performance [Zhao et al., 2011], multi-task online learning [Yang et al., 2017], etc. ## References 1. [Abernethy et al., 2009] Jacob Abernethy, Alekh Agarwal, and Peter L Bartlett. A stochastic view of optimal regret through minimax duality. In COLT, 2009. 2. [Alon et al., 2015] Noga Alon, Nicolo Cesa-Bianchi, Ofer Dekel, and Tomer Koren. Online learning with feedback graphs: Beyond bandits. In COLT, pages 23-35, 2015. 3. [Auer, 2002] Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. JMLR, 3(Nov):397- 422, 2002. 4. [Azoury and Warmuth, 2001] Katy S Azoury and Manfred K Warmuth. Relative loss bounds for on-line density estima- tion with the exponential family of distributions. Machine Learning, 43(3):211-246, 2001. 5. [Belkin et al., 2006] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled exam- ples. JMLR, 7:2399-2434, 2006. 6. [Beygelzimer et al., 2017] Alina Beygelzimer, Francesco Orabona, and Chicheng Zhang. Efficient online bandit multiclass learning with Õ( √ T ) regret. In ICML, pages 488-497, 2017. 7. [Carpentier and Valko, 2016] Alexandra Carpentier and Michal Valko. Revealing graph bandits for maximizing local influence. In AISTATS, pages 10-18, 2016. 8. [Crammer and Gentile, 2013] Koby Crammer and Claudio Gentile. Multiclass classification with bandit feedback us- ing adaptive regularization. Machine learning, 90(3):347- 383, 2013. 9. [Dekel et al., 2010] Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Robust selective sampling from single and multiple teachers. In COLT, pages 346-358, 2010. 10. [Eckart and Young, 1936] Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211-218, 1936. 11. [Forster, 1999] Jürgen Forster. On relative loss bounds in generalized linear regression. In Fundamentals of Com- putation Theory, pages 269-280, 1999. 12. [Gu and Han, 2014] Quanquan Gu and Jiawei Han. Online spectral learning on a graph with bandit feedback. In ICDM-14, pages 833-838. IEEE, 2014. 13. [Gu et al., 2013] Quanquan Gu, Charu Aggarwal, Jialu Liu, and Jiawei Han. Selective sampling on graphs for classi- fication. In Proceedings of the 19th ACM SIGKDD, pages 131-139, 2013. 14. [Herbster and Pontil, 2006] Mark Herbster and Massimil- iano Pontil. Prediction on a graph with a perceptron. In NIPS-06, pages 577-584, 2006. 15. [Hoi et al., 2018] Steven C. H. Hoi, Doyen Sahoo, Jing Lu, and Peilin Zhao. Online learning: A comprehensive sur- vey. CoRR, abs/1802.02871, 2018. 16. [Kakade et al., 2008] Sham M Kakade, Shai Shalev- Shwartz, and Ambuj Tewari. Efficient bandit algorithms for online multiclass prediction. In ICML, pages 440-447. ACM, 2008. 17. [Kuznetsov and Mohri, 2016] Vitaly Kuznetsov and Mehryar Mohri. Time series prediction and online learning. In COLT, pages 1190-1213, 2016. 18. [Moroshko and Crammer, 2014] Edward Moroshko and Koby Crammer. Weighted last-step min-max algorithm with improved sub-logarithmic regret. Theoretical Computer Science, 558:107-124, 2014. 19. [Moroshko et al., 2015] Edward Moroshko, Nina Vaits, and Koby Crammer. Second-order non-stationary online learn- ing for regression. JMLR, 16:1481-1517, 2015. 20. [Smola and Kondor, 2003] Alexander J Smola and Risi Kon- dor. Kernels and regularization on graphs. In Learning the- ory and kernel machines, pages 144-158. Springer, 2003. 21. [Vovk, 1998] Volodya Vovk. Competitive on-line linear re- gression. NIPS-98, pages 364-370, 1998. 22. [Wang et al., 2012] Jialei Wang, Peilin Zhao, and Steven C Hoi. Exact soft confidence-weighted learning. In ICML, pages 121-128, 2012. 23. [Yang and Zhao, 2015] Peng Yang and Peilin Zhao. A min- max optimization framework for online graph classifica- tion. In CIKM, pages 643-652. ACM, 2015. 24. [Yang et al., 2015] Peng Yang, Peilin Zhao, Vincent W Zheng, and Xiao-Li Li. An aggressive graph-based selec- tive sampling algorithm for classification. In ICDM, pages 509-518. IEEE, 2015. 25. [Yang et al., 2016] Peng Yang, Peilin Zhao, Zhen Hai, Wei Liu, Steven CH Hoi, and Xiao-Li Li. Efficient multi-class selective sampling on graphs. In UAI, page 805. AUAI Press, 2016. 26. [Yang et al., 2017] Peng Yang, Peilin Zhao, and Xin Gao. Robust online multi-task learning with correlative and per- sonalized structures. IEEE Trans. Knowl. Data Eng., 29(11):2510-2521, 2017. 27. [Zhang et al., 2016] Xiaoxuan Zhang, Tianbao Yang, and Padmini Srinivasan. Online asymmetric active learning with imbalanced data. In ACM SIGKDD, pages 2055- 2064. ACM, 2016. 28. [Zhao et al., 2011] Peilin Zhao, Steven C. H. Hoi, Rong Jin, and Tianbao Yang. Online AUC maximization. In Pro- ceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 -July 2, 2011, pages 233-240, 2011.