Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
Year: 2021

Abstract:
In semi-supervised graph-based binary classifier learning, a subset of known labels 1 x̂i are used to infer unknown labels, assuming that the label signal x is smooth 2 with respect to a similarity graph specified by a Laplacian matrix. When restricting 3 labels xi to binary values, the problem is NP-hard. While a conventional semi4 definite programming (SDP) relaxation can be solved in polynomial time using, for 5 example, the alternating direction method of multipliers (ADMM), the complexity 6 of iteratively projecting a candidate matrix M onto the positive semi-definite 7 (PSD) cone (M 0) remains high. In this paper, leveraging a recent linear 8 algebraic theory called Gershgorin disc perfect alignment (GDPA), we propose a 9 fast projection-free method by solving a sequence of linear programs (LP) instead. 10 Specifically, we first recast the SDP relaxation to its SDP dual, where a feasible 11 solution H 0 can be interpreted as a Laplacian matrix corresponding to a 12 balanced signed graph sans the last node. To achieve graph balance, we split the 13 last node into two that respectively contain the original positive and negative edges, 14 resulting in a new Laplacian H̄. We repose the SDP dual for solution H̄, then 15 replace the PSD cone constraint H̄ 0 with linear constraints derived from GDPA— 16 sufficient conditions to ensure H̄ is PSD—so that the optimization becomes an LP 17 per iteration. Finally, we extract predicted labels from our converged LP solution 18 H̄. Experiments show that our algorithm enjoyed a 40× speedup on average over 19 the next fastest scheme while retaining comparable label prediction performance. 20

In semi-supervised graph-based binary classifier learning, a subset of known labels1 x̂i are used to infer unknown labels, assuming that the label signal x is smooth2 with respect to a similarity graph specified by a Laplacian matrix. When restricting3 labels xi to binary values, the problem is NP-hard. While a conventional semi-4 definite programming (SDP) relaxation can be solved in polynomial time using, for5 example, the alternating direction method of multipliers (ADMM), the complexity6 of iteratively projecting a candidate matrix M onto the positive semi-definite7 (PSD) cone (M 0) remains high. In this paper, leveraging a recent linear8 algebraic theory called Gershgorin disc perfect alignment (GDPA), we propose a9 fast projection-free method by solving a sequence of linear programs (LP) instead.10 Specifically, we first recast the SDP relaxation to its SDP dual, where a feasible11 solution H 0 can be interpreted as a Laplacian matrix corresponding to a12 balanced signed graph sans the last node. To achieve graph balance, we split the13 last node into two that respectively contain the original positive and negative edges,14 resulting in a new Laplacian H̄. We repose the SDP dual for solution H̄, then15 replace the PSD cone constraint H̄ 0 with linear constraints derived from GDPA—16 sufficient conditions to ensure H̄ is PSD—so that the optimization becomes an LP17 per iteration. Finally, we extract predicted labels from our converged LP solution18 H̄. Experiments show that our algorithm enjoyed a 40× speedup on average over19 the next fastest scheme while retaining comparable label prediction performance.20
1 Introduction21
Binary classification—assignment of labels to anN -sample set x ∈ {−1, 1}N to separate two distinct22 classes—is a basic machine learning problem [1]. One common setting is semi-supervised graph23 classifier learning, where M known labels, x̂i, 1 ≤ i ≤M , are used to infer N −M unknown labels24 xi, M + 1 ≤ i ≤ N , in signal x, assuming that x is smooth with respect to (w.r.t.) a similarity25 graph G specified by a graph Laplacian matrix L [2, 3, 4]. This graph-based binary classification26 problem is NP-hard in general [5]. A conventional semi-definite programming (SDP) relaxation [6]27 replaces the binary label constraint with a more relaxed positive semi-definite (PSD) cone constraint28 (i.e., matrix variable M related to xx> satisfying M 0), and the relaxed problem can be solved in29 polynomial time using, for example, the alternating direction method of multipliers (ADMM) [7].30 However, ADMM still requires projection to the PSD cone S = {M |M 0} per iteration, which is31 expensive (O(N3)) due to full matrix eigen-decomposition. An alternative approach eliminates the32 binary constraint and minimizes directly a quadratic graph smoothness term called graph Laplacian33 regularization (GLR) x>Lx [8] for x ∈ RN , and then rounds xi’s to {−1, 1}. However, in general34 spectral methods such as GLR do not have tight performance bounds common in SDP relaxation [9].35
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.
To ensure matrix variable M is PSD without eigen-decomposition, one naïve approach is to enforce36 linear constraints derived directly from the Gershgorin circle theorem (GCT) [10]. By GCT, every37 real eigenvalue λ of a real symmetric matrix M resides inside at least one Gershgorin disc Ψi—38 corresponding to row i of M—with center ci(M) ,Mi,i and radius ri(M) , ∑ j 6=i |Mi,j |, i.e.,39
ci(M)− ri(M) ≤ λ ≤ ci(M) + ri(M), ∃i. (1) The corollary is that the smallest eigenvalue, λmin(M), of M is lower-bounded by the smallest40 Gershgorin disc left-end, denoted by λ−min(M), i.e.,41
λ−min(M) , mini ci(M)− ri(M) ≤ λmin(M). (2)
Thus, to ensure M 0, one can impose the sufficient condition λ−min(M) ≥ 0. While replacing42 the PSD cone constraint with a set of N linear constraints, ci(M) − ri(M) ≥ 0,∀i, is attractive43 computationally, GCT lower bound λ−min(M) tends to be loose. As an example, consider the positive44 definite (PD) matrix M in Fig. 1(a) with λmin(M) = 0.1078 [11]. The first Gershgorin disc left-end45 is c1(M)− r1(M) = 2− 3 = −1, and λ−min(M) < 0. Thus, imposing λ − min(M) ≥ 0 directly would46 unnecessarily restrict the search space and result in a sub-optimal solution to the posed problem.47
A recent linear algebraic theory called Gershgorin disc perfect alignment (GDPA) [11] provides a48 theoretical foundation to tighten the GCT lower bound. Specifically, GDPA states that given a graph49 Laplacian matrix L corresponding to a balanced signed graph G [12], one can perform a similarity50 transform1, L̃ = SLS−1, where S = diag(v−11 , . . . , v −1 N ) and v is the first eigenvector of L, such51 that the Gershgorin disc left-ends of L̃ are exactly aligned at λmin(L) = λmin(L̃). This means that52 transformed L̃ satisfies λ−min(L̃) = λmin(L̃); i.e., the GCT lower bound is the tightest possible after53 an appropriate similarity transform. Continuing our example, similarity transform M̃ = SMS−1 of54 M has all its disc left-ends exactly aligned at λmin(M) = λmin(M̃) = 0.1078.55
Leveraging GDPA, we develop a fast projection-free algorithm for semi-supervised graph classifier56 learning. We first observe that the optimal solution M of the SDP relaxation is an adjacency matrix57 to a balanced signed graph. However, GDPA requires a Laplacian matrix, which has opposite signs in58 the off-diagonal terms to the corresponding adjacency matrix of the same graph. Thus, we convert the59 problem to its SDP dual [13] and interpret the dual variable H instead as a Laplacian to a balanced60 graph sans the last graph node. To achieve graph balance, we split the last node into two and divide61 the original positive and negative edges among them, resulting in a revised Laplacian H̄. We repose62 the SDP dual problem for solution H̄, then replace the PSD cone constraint H̄ 0 with linear63 constraints derived from GDPA. This changes the optimization to a linear program (LP) per iteration64 that is solved efficiently using fast LP solvers [14]. Finally, we extract prediction labels from our65 converged LP solution H̄. Experiments show that our algorithm enjoyed a 40× speedup on average66 over the next fastest scheme while retaining comparable label prediction performance.67
2 Related Work68
Graph-based classification was first studied almost two decades ago [2, 3, 4]. With the advent of graph69 signal processing (GSP) [15, 16]—spectral analysis of discrete signals residing on combinatorial70 graphs—interest in the problem was revived [17, 18, 19]. The problem of learning a similarity71 graph from data has been extensively studied [20]. We focus instead on the orthogonal problem of72 predicting binary labels given a similarity graph and a subset of M labels.73
1A similarity transform B = SAS−1 and the original matrix A share the same set of eigenvalues [10].
The graph-based binary classification problem is NP-hard in general [5]. SDP—useful in approx-74 imating various NP-hard problems [13]—provides an intuitive relaxation [6]. An interior point75 method tailored for the slightly more general binary quadratic problem2 (BQP) has complexity76 O(N3.5 log(1/ )), where is the tolerable error [21]. The complexity was improved to O(N3) by77 SDCut [22, 23] via spectrahedron-based relaxation. Replacing PSD cone constraint M 0 with a78 factorization M = XX> was proposed in [24], but resulted in a non-convex optimization for X that79 was solved locally via alternating minimization, where in each iteration a matrix inverse of worst-case80 complexity O(N3) was required. More recent first-order methods for SDP such as [7] used ADMM81 [25, 26, 27], but the iterative projection onto PSD cone requires full matrix eigen-decomposition and82 thus expensive. In contrast, leveraging GDPA theory [11], our algorithm is entirely projection-free.83
It is known in graph spectral theory [28] that balanced signed graphs have unique spectral properties84 [29]; for example, the signed graph Laplacian matrix [30] has eigenvalue 0 iff the corresponding85 signed graph is balanced. In contrast, extending the original GCT [10], GDPA [11] states that the86 Gershgorin disc left-ends of a similarity transform SMS−1 of graph Laplacian M to a balanced87 graph can be perfectly aligned at λmin(M). GDPA theory was developed for metric learning [31]88 to optimize a PD matrix M given a convex and differentiable objective Q(M) so that the optimal89 Mahalanobis distance (fi − fj)>M(fi − fj) for feature vectors fi and fj can be defined. This paper90 leverages GDPA [11] in an entirely different direction for graph-based binary classifier learning.91 Specifically, observing that solution matrix H to the SDP dual is a Laplacian to a balanced graph G92 sans the last graph node, we augment the last node to obtain an overall balanced graph Ḡ, and solve a93 modified SDP dual for Laplacian H̄ to Ḡ via GDPA linearization.94
3 Preliminaries95
3.1 Graph Definitions96
A graph is defined as G(V, E), with node set V = {1 . . . , N}, and edge set E = {(i, j)}, where97 (i, j) means nodes i and j are connected with weight wi,j ∈ R. A node i may have self-loop of98 weights ui ∈ R. Denote by W the adjacency matrix, where Wi,j = wi,j and Wi,i = ui. We assume99 that edges are undirected, and W is symmetric. Define next the diagonal degree matrix D, where100 Di,i = ∑ j Wi,j . The combinatorial graph Laplacian matrix [15] is then defined as L = D−W. To101 account for self-loops, the generalized graph Laplacian matrix is defined as L = D−W+ diag(W).102 Note that any real symmetric matrix can be interpreted as a generalized graph Laplacian matrix.103
The graph Laplacian regularizer (GLR) [8] that quantifies smoothness of signal x ∈ RN w.r.t. graph104 specified by L is105
x>Lx = ∑
(i,j)∈E wi,j(xi − xj)2 + ∑ i∈V uix 2 i . (3)
GLR is also the objective of our graph-based classification problem.106
3.2 Iterative GDPA Linearization107
Denote by L a generalized graph Laplacian matrix to a balanced and connected signed graph G (with108 or without self-loops). A balanced graph is a graph with no cycle of odd number of negative edges.109 By Cartwright-Harary Theorem (CHT) [12], a graph is balanced iff nodes can be colored into blue110 and red, such that each positive (negative) edge connects nodes of the same (different) colors. GDPA111 [11] states that a similarity transform L̃ = SLS−1, where S = diag(v−11 , . . . , v −1 N ) and v is the first112 eigenvector of L, has its Gershgorin disc left-ends aligned exactly at λmin(L), i.e.,113
L̃i,i − ∑ j 6=i |L̃i,j | = Li,i − ∑ j 6=i |siLi,j/sj | = λmin(L), ∀i ∈ {1, . . . , N}. (4)
To solve an optimization of the form minL 0Q(L), one can leverage GDPA and optimize iteratively114 as follows. At iteration t with solution Lt, compute first eigenvector vt to Lt corresponding to115 λmin(Lt); extreme eigenvector vt can be efficiently computed in complexity O(ab) using Locally116
2BQP objective takes a quadratic form x>Qx, but Q is not required to be a Laplacian to a similarity graph.
Optimal Block Preconditioned Conjugate Gradient (LOBPCG) [32], where a is the number of non-117 zero entries in Lt and b is the iteration number till convergence3. Define scalars sti = 1/vti ,∀i. Then118 for iteration t+ 1, solve the following optimization:119
min L Q(L), s.t. Li,i − ∑ j 6=i |stiLi,j/stj | ≥ 0, ∀i ∈ {1, . . . , N}. (5)
Linear constraints in (5) ensure that the similarity transform L̃ = SLS−1 is PSD by GCT, and hence120 solution L is PSD. Since scalars {sti} are computed from first eigenvector vt of Lt 0, by GDPA121 SLtS−1 has all its disc left-ends aligned exactly at λmin(Lt) ≥ 0, and hence Lt remains feasible at122 iteration t + 1. Thus, objective Q(Lt) is monotonically non-increasing with t, and the algorithm123 converges to a local minimum. We invoke this iteration to solve our posed SDP dual as well.124
4 Formulation of Graph-based Classifier Learning125
We first formulate the graph-based classifier learning problem and relax it to an SDP problem in126 Section 4.1. We then present its SDP dual with dual variable matrix H in Section 4.2. Finally, we127 interpret H as a graph Laplacian, and augment its corresponding graph G to a balanced graph Ḡ for128 GDPA linearization in Section 4.3.129
4.1 SDP Primal130
Given a PSD graph Laplacian matrix L ∈ RN×N of a positive similarity graph Go (i.e., all edge131 weights wi,j ≥ 0), one can formulate a graph-based binary classification problem as follows:132
min x x>Lx, s.t. { x2i = 1, ∀i ∈ {1, . . . , N} xi = x̂i, ∀i ∈ {1, . . . ,M} . (6)
where {x̂i}Mi=1 are the M known labels. The objective in (6) dictates that signal x is smooth133 w.r.t. graph Go specified by L. Because L is PSD [16], the objective is lower-bounded by 0, i.e.,134 x>Lx ≥ 0,∀x ∈ RN . The first binary constraint ensures xi ∈ {−1, 1}. The second constraint135 ensures that entries xi in signal x agrees with known labels {x̂i}Mi=1.136 As an example, consider a 3-node line graph shown in Fig. 2(a), where edges (1, 2) and (2, 3) have137 weights w1,2 and w2,3, respectively. The adjacency matrix W and graph Laplacian matrix L are:138
W = [ 0 w1,2 0 w1,2 0 w2,3
0 w2,3 0
] , L = [ d1 −w1,2 0 −w1,2 d2 −w2,3
0 −w2,3 d3
] (7)
where di = ∑ j|(i,j)∈E wi,j is the degree of node i. Suppose known labels are x̂1 = 1 and x̂2 = −1.139
Due to the binary constraint on xi’s, (6) is NP-hard [5]. One can define an SDP relaxation [5] as140 follows. Define first X = xx> and M = [X x; x> 1]. M is PSD because: i) block [1] is PSD,141 and ii) the Schur complement of block [1] of M is X− xx> = 0, which is also PSD. Thus, the two142
3Warm start [11] can be employed to reduce b in subsequent iterations given vt is computed repeatedly for gradually changing Lt’s. See Section 5 for details.
constraints M 0 and rank(X) = 1 is equivalent to X = xx>, which together with Xii = 1,∀i143 implies x2i = 1,∀i. To convexify the problem, we drop the non-convex rank constraint and write the144 SDP relaxation for optimization variable M as145
min x,X Tr(LX) s.t.  Xii = 1, i ∈ {1, . . . , N} M , [ X x x> 1 ] 0
xi = x̂i, i ∈ {1, . . . ,M}
(8)
where Tr(x>Lx) = Tr(Lxx>) = Tr(LX). Because (8) has linear objective and constraints with an146 additional PSD cone constraint, M 0, it is an SDP problem. We call (8) the SDP primal.147 Continuing our example, consider ground-truth labels x = [1 − 1 1]> for the 3-node graph in148 Fig. 2(a). The corresponding solution matrix M = [xx> x; x> 1] is149
M =  1 −1 1 1−1 1 −1 −11 −1 1 1 1 −1 1 1  . (9) Observe that M can be interpreted as an adjacency matrix to a balanced signed graph; nodes 1, 3150 and 4 can be colored blue, and node 2 can be colored red, so that positive (negative) edges connect151 only nodes of the same (different) colors. See Fig. 2(b) for an illustration of the corresponding signed152 graph when interpreting M as an adjacency matrix (self-loops are not shown). However, while the153 solution space for the SDP primal (8) exhibits desirable graph balance, GDPA requires instead a154 graph Laplacian matrix to a balanced graph, which has opposite signs in the off-diagonal terms as the155 adjacency matrix. This motivates us to investigate the corresponding SDP dual problem instead.156
4.2 SDP Dual157
We derive the dual problem based on SDP duality theory [13]. We first define158 Ai = diag(eN+1(i)), Bi = [
0N×N eN (i) e>N (i) 0
] . (10)
where eN (i) ∈ {0, 1}N is a length-N binary canonical vector with a single non-zero entry equals159 to 1 at the i-th entry, 0N×N is a N -by-N matrix of zeros, and diag(v) is a diagonal matrix with160 diagonal entries equal to v. Note that Ai and Bi are symmetric. Next, we collect M known labels161 {x̂i}Mi=1 into a vector b ∈ RM of length M , i.e.,162
bi = 2x̂i, ∀i ∈ {1, . . . ,M}. (11)
We now define the SDP dual of (8) as163
min y,z
1>N+1y + b >z, s.t. H , N+1∑ i=1 yiAi + M∑ i=1 ziBi − L 0 (12)
where 1N is a length-N vector of ones, and dual variables are y ∈ RN+1 and z ∈ RM . Because164 the objective is a minimization, when bi < 0 (i.e., x̂i < 0), the corresponding zi ≥ 0. Similarly, for165 bi > 0, zi ≤ 0. Thus, the signs of variables zi’s are known a priori. Without loss of generality, we166 assume zi ≤ 0,∀i ∈ {1, . . . ,M1} and zi ≥ 0,∀i ∈ {M1 + 1, . . . ,M} in the sequel.167
4.3 Reformulating the SDP Dual168
We interpret H ∈ R(N+1)×(N+1) in (12) as a graph Laplacian corresponding to a graph G. However,169 G is not a balanced signed graph, because of the last row / column in H. To see this, we write170
H = [ Ly g g> yN+1 ] (13)
where g = [z1 . . . zM 0>N−M ] >. Matrix Ly ∈ RN×N , which equals to Ly = diag(y1, . . . , yN ) + L,171 is a generalized Laplacian to a N -node positive graph G+. However, node N + 1 has both positive172
and negative edges to G+ stemming from negative zi’s and positive zi’s, respectively. As a result, H173 is not a Laplacian corresponding to a balanced signed graph.174
Continuing our 3-node line graph example with Laplacian L, the corresponding Ly and H are175
Ly = [ y1 + d1 −w1,2 0 −w1,2 y2 + d2 −w2,3
0 −w2,3 y3 + d3
] , H =  y1 + d1 −w1,2 0 z1−w1,2 y2 + d2 −w2,3 z20 −w2,3 y3 + d3 0 z1 z2 0 y4  . (14) Interpreting H as a graph Laplacian, node 4 has degree d4 = −z1 − z2. Thus, y4 = u4 + d4, and176 self-loop weight for node 4 iss u4 = y4 + z1 + z2. See Fig. 2(c) for an illustration of this graph G.177
In graph terminology, node (N+1) has positive and negative edges, with respective weights {−zi}M1i=1178 and {−zi}Mi=M1+1, to G +, and a self-loop with weight uN+1 = yN+1 + ∑M
i=1 zi. We construct an179 augmented graph Ḡ with N + 2 nodes from G by splitting node N + 1 in G into two in Ḡ, dividing180 positive and negative edges between them. The specific graph construction for Ḡ procedure is181
1. Construct first N nodes with the same inter-connections as sub-graph G+.182 2. Construct node N + 1 with positive edges {−zi}M1i=1 and node N + 2 with negative edges183 {−zi}Mi=M1+1 to the first N nodes in sub-graph G +.184 3. Add self-loops for nodeN+1 andN+2 with respective weights uN+1/2− and uN+1/2+ ,185 where ∈ R is a parameter to be discussed.186
Denote by H̄ ∈ R(N+2)×(N+2) the graph Laplacian matrix corresponding to Ḡ. Continuing our187 3-node graph example, Fig. 2(d) shows the augmented graph Ḡ, and the corresponding H̄ is188
H̄ =  y1 + d1 −w1,2 0 z1 0 −w1,2 y2 + d2 −w2,3 0 z2
0 −w2,3 y3 + d3 0 0 z1 0 0 1 2 (y4 − z1 + z2)− 0
0 z2 0 0 1 2 (y4 + z1 − z2) +  . (15) Spectrally, H̄ and H are related; we prove that λmin(H̄) is a lower bound for λmin(H).189 Lemma 1. The smallest eigenvalue λmin(H̄) of graph Laplacian H̄ to augmented graph Ḡ is a lower190 bound for λmin(H) of Laplacian H to G, i.e.,191
λmin(H̄) ≤ λmin(H). (16) 192
Proof. Denote by G the graph represented by generalized graph Laplacian H, with inter-node193 edge weights {wij} and self-loop weights {ui}. Denote by v ∈ RN+1 the first eigenvector of H194 corresponding to the smallest eigenvalue λmin(H). From (3), GLR of H computed using v is195
v>Hv = ∑
(i,j)∈E | 1≤i,j≤N wi,j(vi − vj)2 − M∑ i=1 zi(vN+1 − vi)2 + N∑ i=1 yiv 2 i + uN+1v 2 N+1. (17)
Now construct α ∈ RN+2, where α = [v1 . . . vN vN+1 vN+1]>. GLR of H̄ computed using α is196
α>H̄α = ∑
(i,j)∈E | 1≤i,j≤N wi,j(vi − vj)2 − M1∑ i=1 zi(vN+1 − vi)2 − M∑ i=M1+1 zi(vN+1 − vi)2
+ N∑ i=1 yiv 2 i + (uN+1 2 − ) v2N+1 + (uN+1 2 + ) v2N+1. (18)
Thus, v>Hv = α>H̄α. Since first eigenvector v minimizes the Rayleigh quotient of H,197
λmin(H) = v>Hv
v>v
(a) ≥ α >H̄α
α>α
(b) ≥ λmin(H̄). (19)
(a) holds since v>v ≤ α>α by construction, and (b) holds since λmin(H̄) = minx x >H̄x x>x .198
From the proof above, the usefulness of parameter becomes clear: the bound λmin(H̄) ≤ λmin(H)199 becomes tight when the last two entries in the first eigenvector of H̄ are similar. To promote this, we200 set to an appropriate large value, so that the first eigenvector minimizing the Rayleigh quotient of201 H̄ would choose similar small values for the last two entries.202
Given Lemma 1, we now reformulate the SDP dual (12) by keeping the same objective but imposing203 PSD cone constraint on H̄ instead of H. Define A′i, B ′ i and B ′′ i similarly to (10) but for a larger204
(N + 2)-by-(N + 2) matrix; i.e., A′i = diag(eN+2(i)), B ′ i = [Bi 0N+1;0 > N+1 0], and B ′′ i =205
[0(N+1)×(N+1) eN+1(i); e > N+1(i) 0]. The reformulated SDP dual is206
min y,z
1>N+1y + b >z, (20)
s.t. H̄ , N∑ i=1 yiA ′ i + κN+1A ′ N+1 + κN+2A ′ N+2 + M1∑ i=1 ziB ′ i + M∑ i=M1+1 ziB ′′ i − L 0
where κN+1 = uN+1 2 − ∑M1 i=1 zi − and κN+2 = uN+1 2 − ∑M i=M1+1 zi + . Given H̄ is now a207 Laplacian to a balanced graph, we discuss the application of GDPA linearization to solve (20) next.208
5 Algorithm Implementation209
5.1 GDPA Linearization210
We replace the PSD cone constraint on H̄ in (20) with N + 2 linear constraints via GDPA [11].211 Specifically, at iteration t, we compute first eigenvector vt of solution H̄t using LOBPCG [32]. We212 define scalars si = 1/vti ,∀i ∈ {1, . . . , N + 2}. Finally, we write N + 2 constraints corresponding to213 λ−min(SH̄S −1) ≥ 0, where S = diag(s1, . . . , sN+2), i.e.,214
yi + di − ∑
j 6=i |siwi,j/sj | − |sizi/sN+1| ≥ 0, ∀i ∈ {1, . . . ,M1} yi + di − ∑ j 6=i |siwi,j/sj | − |sizi/sN+2| ≥ 0, ∀i ∈ {M1 + 1, . . . ,M} yi + di − ∑ j 6=i |siwi,j/sj | ≥ 0, ∀i ∈ {M + 1, . . . , N}
uN+1/2− − ∑M1
j=1 |sN+1zj/sj | ≥ 0 uN+1/2 + − ∑M j=M1+1 |sN+2zj/sj | ≥ 0
(21)
where the indices for summation ∑
j 6=i are {1, . . . , N} \ i. Note that the absolute value operation215 can be appropriately removed for each term siwi,j/sj and sizi/sj , since the signs for si, wi,j and216 zi are known. Together with linear objective in (20), this constitutes an LP for variables y and z,217 solvable using any available fast LP solvers [14]. Compared to SDP primal (8) with a large matrix218 variable M ∈ R(N+1)×(N+1), our LP variables, y ∈ RN+1 and z ∈ RM , are much smaller.219 A sequence of LPs are solved, each time with scalars si’s updated from computed solution H̄t, until220 convergence. The bulk of the complexity resides in the computation of the first eigenvector vt for221 each LP solution H̄t. LOBPCG is an iterative algorithm that can benefit from warm start [11]: with222 a good initial guess for vt, the algorithm converges faster. Since H̄t changes gradually through223 our iterations, we use previously computed eigenvector vt−1 of H̄t−1 as initial guess for vt of H̄t.224 Experiments show that warm start reduces the iteration number till convergence significantly.225
5.2 Initialization & Prediction Label Extraction226
Our LP in Section 5.1 requires an initial H̄0 to compute first eigenvector v0, so that scalars {si}N+2i=1227 can be defined for N + 2 linear constraints in (21). To initialize H̄0, we set y0 = [1>M 0 > N−M M ] >228 and z0 = [−x̂1 . . . − x̂M ]. Parameter is set to t = 1>N+1yt−1 + 1>Mzt−1 at iteration t. H̄0 can229 then be computed using definition of H̄ in (20).230
As similarly done in [5], we extract prediction labels x∗ = [x1 . . . xN ]> from converged LP solution231 y∗ and z∗ as follows. We first construct H∗ using y∗ and z∗ using definition of H in (12). We then232 compute x∗ = sign(x̂1v1v), where v1 is the first entry of the first eigenvector v of H∗. See [5] for233 details of recovering SDP primal variables from dual variables in BQP.234
6 Experiments235
6.1 Experimental Setup236
We implemented our GDPA-graph-based classifier learning scheme in Matlab4, and evaluated it in237 terms of average classification error rate and running time. We compared our algorithm against the238 following schemes that solve the SDP primal problem (8) directly: i) two primal-dual interior-point239 solvers for SDP, SeDuMi and MOSEK, both of which are available in CVX with a CVX Professional240 license [33], ii) an ADMM first-order operator-splitting solver CDCS [26, 27] with an LGPL-3.0241 License [34], iii) a spectrahedron-based relaxation solver SDCut [22, 23, 35] that involves L-BFGS-B242 [36], and iv) a biconvex relaxation solver BCR [24, 37], all of which are implemented in Matlab. In243 addition, we employed CDCS again to solve our modified SDP dual problem (20).244
We set the convergence threshold of the first eigenvector solver LOBPCG to be 10−4, with maximum245 number of iterations 200. We set the convergence threshold of our LP solver to be 10−4 also,246 with maximum number of iterations 100, since first-order methods, i.e., CDCS and SDCut, aim at247 computing a solution of moderate accuracy [26]. Accordingly, we set the convergence threshold of248 SeDuMi and MOSEK to be ‘low’, which is approximately equal to 10−4 and the lowest precision249 setting in CVX. We set the convergence thresholds of CDCS and SDCut to be 10−3, the maximum250 number of ADMM iterations in CDCS to be 1000, the maximum number of iterations for L-BFGS-B251 in SDCut and the main loop in BCR to be 100, and the Frobenius norm weight in SDCut to be 100.252 We chose these settings since smaller convergence thresholds and larger number of iterations would253 cause CDCS, SDCut and BCR to be significantly slower to converge. We used default settings for254 all remaining solvers. All computations were carried out on a Windows 10 64bit PC with AMD255 RyzenThreadripper 3960X 24-core processor 3.80 GHz and 128GB of RAM.256
We adopted 17 binary datasets that are freely available in UCI [38] and LibSVM [39]. For exper-257 imental efficiency, we first performed a K-fold (K ≤ 5) split for each dataset with random seed258 0, and then created 10 instances of 50% training-50% test split for each fold, with random seeds259 1-10 [40]. The above setup resulted in problem sizes from 29 to 400. We applied the following two260 data normalization schemes for the training/test data: i) a standardization scheme in [41] that first261 subtracts the mean and divides by the feature-wise standard deviation, and then normalizes to unit262 length sample-wise, and ii) a min-max scheme [40] that rescales each feature to within 0 and 1. We263 added 10−12 noise to the dataset to avoid NaN’s due to data normalization on small samples.264
6.2 Experimental Results265
Fig. 3 and the first two plots of Fig. 4 show classification error rates and runtime (in log scale) using266 min-max and standardization data re-scaling strategies for 17 different datasets, respectively. The267 x-axis of each plot denotes the datasets in ascending order of problem sizes. Each point in the plots268 denotes the average of 10K runs. Fig. 4 (right) shows runtime versus problem size (4 to 24428) using269 the same dataset cod-rna (freely avaiable in LibSVM [39]). We did not execute SeDuMi, MOSEK,270 CDCS (8), BCR, SDcut, or CDCS (20) when the problem size was larger than 976.271
In terms of classification error rate for min-max re-scaling, MOSEK, CDCS (8) and SeDuMi had272 slightly larger error rates: 32.52%, 32.38% and 29.92%, respectively. GDPA had 29.11%, which273 was very close to CDCS (20) at 29.24% and SDCut at 28.76%. This shows that our proposed GDPA274 linearization (21) closely approximated the modified SDP dual (20) in performance. BCR at 26.82%275 was roughly 2% smaller. In the standardization re-scaling case, CDCS (8), MOSEK, and SeDuMi had276 the largest error rates: 32.75%, 32.5% and 31.0%, respectively. GDPA had 26.88%, close to CDCS277 (20) at 26.9% and SDCut with 26.82%. BCR at 24.8% was again roughly 2% smaller. By factorizing278 a PSD matrix M = XX>, BCR avoided any SDP relaxation, which may explain its slightly better279 performance here. However, BCR solved a non-convex optimization problem converging to a local280 minimum, and thus occasionally the performance was quite poor (e.g., see sonar in Fig. 3(left)).281 Overall, all solvers performed similarly given constructed similarity graphs in the two cases.282
In terms of runtime, BCR was competitive with GDPA when the problem size was small, but GDPA283 significantly outperformed all competing solvers when the problem size was large. Specifically, the284 speed gain increased as problem size increased; for madelon with problem size 400, the speedup of285
4results reproducible via code in https://anonymous.4open.science/r/GDPA_matlab-EF4D/
GDPA over the next fastest scheme BCR was 346×. Fig. 4 (right) also shows that the computation286 time for GDPA increased gracefully as the problem size increased to very large sizes. The reason for287 our dramatic speed gain is the fast computation of first eigenvectors using LOBPCG, which benefited288 from warm start during the LP iterations. In general, GDPA performed fewer than 10 LP’s until289 convergence. In contrast, both CDCS and SDCut required eigen-decomposition of a matrix of size290 N ×N per iteration. Because L described a dense graph in our experiments, the speedup of replacing291 the full eigen-decomposition with simpler first eigenvector computation per iteration was significant.292 For BCR, each iteration required either N -dimensional matrix inversion for a least-squares problem293 or iterative gradient descent, which was computationally expensive as the problem size increased. On294 average, GDPA enjoyed a 40.9× speedup over the next fastest solver BCR.295
7 Conclusion296
We propose a fast projection-free algorithm for the graph-based classifier learning problem. The297 key idea is to replace the difficult-to-compute positive semi-definite (PSD) cone constraint with298 linear constraints derived from the recent Gershgorin disc perfect alignment (GDPA) theory, so that299 the optimization can be solved as a sequence of linear programs (LP). Experiments show that our300 algorithm enjoyed a considerable speedup while retaining comparable label prediction performance.301
A graph classifier scalable to very large sizes encourages ubiquitous deployment for wide-ranging302 applications. Negative social impact can result if the tool is misused by enabling classification for303 discriminatory purposes. As an optimization problem, graph-based binary classification is rather304 narrowly defined (though multi-class classification can be implemented as a tree of binary classifiers).305 Furthermore, good performance depends heavily on the construction of a good similarity graph,306 which is outside the scope of this paper. However, we conjecture that the general methodology of307 GDPA linearization can be similarly tailored to other SDP problems with PSD cone constraints. We308 anticipate that speedups in other SDP problems will also be significant.309
References310 [1] C. M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics),311 Springer-Verlag, Berlin, Heidelberg, 2006.312 [2] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Scholkopf, “Learning with local and313 global consistency,” in 16th International Conference on Neural Information Processing (NIPS),314 Whistler, Canada, December 2003.315
[3] M. Belkin, I. Matveeva, and P. Niyogi, “Regularization and semisupervised learning on large316 graphs,” in Shawe-Taylor J., Singer Y. (eds) Learning Theory, COLT 2004, Lecture Notes in317 Computer Science, 2004, vol. 3120, pp. 624–638.318
[4] A. Guillory and J. Bilmes, “Label selection on graphs,” in Twenty-Third Annual Conference on319 Neural Information Processing Systems, Vancouver, Canada, December 2009.320
[5] Z. Luo, W. Ma, A. M. So, Y. Ye, and S. Zhang, “Semidefinite relaxation of quadratic optimiza-321 tion problems,” IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 20–34, 2010.322
[6] Z. Li, J. Liu, and X. Tang, “Pairwise constraint propagation by semidefinite programming323 for semi-supervised classification,” in ACM International Conferene on Machine Learning,324 Helsinki, Finland, July 2008.325
[7] B O’Donoghue, E. Chu, N. Parikh nad, and S. Boyd, “Conic optimization via operator splitting326 and homogeneous self-dual embedding,” in Journal of Optimization Theory and Applications,327 2016, vol. 169, no.3, pp. 1042–1068.328
[8] J. Pang and G. Cheung, “Graph Laplacian regularization for inverse imaging: Analysis in the329 continuous domain,” in IEEE Transactions on Image Processing, April 2017, vol. 26, no.4, pp.330 1770–1785.331
[9] M. Goemans and D. Williamson, “Improved approximation algorithms for maximum cut and332 satisfiability problems using semidefinite programming,” J. ACM, vol. 42, no. 6, pp. 1115–1145,333 Nov. 1995.334
[10] R. S. Varga, Gershgorin and his circles, Springer, 2004.335 [11] C. Yang, G. Cheung, and H. Wei, “Signed graph metric learning via Gershgorin disc perfect336 alignment,” arXiv, 2021.337 [12] D. Cartwright and F. Harary, “Structural balance: a generalization of Heider’s theory,” in338 Psychological Review, 1956, vol. 63, no.5, pp. 277–293.339 [13] B. Gartner and J. Matousek, Approximation Algorithms and Semidefinite Programming,340 Springer, 2012.341 [14] R. Vanderbei, Linear Programming: Foundations and Extensions (5th Edition), Springer342 Nature, 2021.343 [15] A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, “Graph signal344 processing: Overview, challenges, and applications,” in Proceedings of the IEEE, May 2018,345 vol. 106, no.5, pp. 808–828.346
[16] G. Cheung, E. Magli, Y. Tanaka, and M. Ng, “Graph spectral image processing,” in Proceedings347 of the IEEE, May 2018, vol. 106, no.5, pp. 907–930.348
[17] M. Gavish, B. Nadler, and R. Coifman, “Multiscale wavelets on trees, graphs and high349 dimensional data: Theory and applications to semi-supervised learning,” in 27th International350 Conference on Machine Learning, Haifa, Israel, June 2010.351
[18] D. Shuman, M. Faraji, and P. Vandergheynst, “Semi-supervised learning with spectral graph352 wavelets,” in International Conference on Sampling Theory and Applications (SampTA),353 Singapore, May 2011.354
[19] G. Cheung, W.-T. Su, Y. Mao, and C.-W. Lin, “Robust semisupervised graph classifier learning355 with negative edge weights,” in IEEE Transactions on Signal and Information Processing over356 Networks, December 2018, vol. 4, no.4, pp. 712–726.357
[20] X. Dong, D. Thanou, M. Rabbat, and P. Frossard, “Learning graphs from data: A signal358 representation perspective,” IEEE Signal Processing Magazine, vol. 36, no. 3, pp. 44–63, 2019.359
[21] C. Helmberg, F. Rendl, R. Vanderbei, and H. Wolkowicz, “An interior-point method for360 semidefinite programming,” in SAIM J. Optim., 1996, vol. 6, no.2, pp. 342–361.361
[22] P. Wang, C. Shen, and A. van den Hengel, “A fast semidefinite approach to solving binary362 quadratic problems,” in IEEE International Conference on Computer Vision and Pattern363 Recognition, Portland, OR, June 2013.364
[23] P. Wang, C. Shen, A. Hengel, and P. Torr, “Large-scale binary quadratic optimization using365 semidefinite relaxation and applications,” IEEE Transactions on Pattern Analysis and Machine366 Intelligence, vol. 39, no. 3, pp. 470–485, 2017.367
[24] S. Shah et al., “Biconvex relaxation for semidefinite programming in computer vision,” in368 European Conference on Computer Vision, Amsterdam, the Netherlands, October 2016.369
[25] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical370 learning via the alternating direction method of multipliers,” in Foundations and Trends in371 Optimization, 2011, vol. 3, no.1, pp. 1–122.372
[26] Y. Zheng, G. Fantuzzi, and A. Papachristodoulou, “Fast ADMM for sum-of-squares programs373 using partial orthogonality,” IEEE Transactions on Automatic Control, vol. 64, no. 9, pp.374 3869–3876, 2019.375
[27] Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, “Chordal decomposition376 in operator-splitting methods for sparse semidefinite programs,” Mathematical Programming,377 vol. 180, pp. 489—-532, 2020.378
[28] F. Chung, Spectral Graph Theory, American Mathematical Society, 1996.379
[29] T. Dittrich and G. Matz, “Signal processing on signed graphs: Fundamentals and potentials,” in380 IEEE Signal Processing Magazine, November 2020, vol. 37, no.6, pp. 86–98.381
[30] J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E. D. Luca, and S. Albayrak, “Spectral382 analysis of signed graphs for clustering, prediction and visualization,” in SIAM International383 Conference on Data Mining, Columbus, OH, May 2010.384
[31] Panagiotis Moutafis, Mengjun Leng, and Ioannis A. Kakadiaris, “An overview and empirical385 comparison of distance metric learning methods,” IEEE Transactions on Cybernetics, vol. 47,386 no. 3, pp. 612–625, 2017.387
[32] A. V. Knyazev, “Toward the optimal preconditioned eigensolver: Locally optimal block388 preconditioned conjugate gradient method,” SIAM Journal on Scientific Computing, vol. 23, no.389 2, pp. 517–541, 2001.390
[33] “CVX Research,” http://cvxr.com/cvx/, Accessed: 2021-5-28.391
[34] “CDCS implementation,” https://github.com/oxfordcontrol/CDCS, Accessed: 2021-5-392 28.393
[35] “SDcut implementation,” https://github.com/chhshen/SDCut, Accessed: 2021-5-28.394
[36] C. Zhu, R. Byrd, P. Lu, and J. Nocedal, “Algorithm 778: L-BFGS-B: Fortran subroutines395 for large-scale bound-constrained optimization,” ACM Trans. Math. Softw., vol. 23, no. 4, pp.396 550–560, Dec. 1997.397
[37] “BCR implementation,” https://github.com/shahsohil/biconvex-relaxation, Ac-398 cessed: 2021-5-28.399
[38] “UCI machine learning repository,” https://archive.ics.uci.edu/ml/datasets.php,400 Accessed: 2021-5-28.401
[39] “LibSVM Data: Classification (Binary Class),” https://www.csie.ntu.edu.tw/~cjlin/402 libsvmtools/datasets/binary.html, Accessed: 2021-5-28.403
[40] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice Hall Press, USA,404 3rd edition, 2009.405
[41] M. Dong, Y. Wang, X. Yang, and J. Xue, “Learning local metrics and influential regions for406 classification,” IEEE TPAMI, vol. 42, no. 6, pp. 1522–1529, June 2020.407
Checklist408
1. For all authors...409
(a) Do the main claims made in the abstract and introduction accurately reflect the paper’s410 contributions and scope? [Yes] . The paper proposes a new fast algorithm for the411 precisely defined graph-based classifier learning problem.412
(b) Did you describe the limitations of your work? [Yes] . In the conclusion, we discussed413 the limitation of our work: graph-based binary classification is somewhat narrowly414 defined, compared to the more general semi-definite programming (SDP) problem.415 However, we conjecture that similar optimization strategies can be customized for other416 SDP problems, which is left for future work. Moreover, the performance of a graph417 classifier depends heavily on the construction of a similarity graph, which is outside418 the scope of this paper.419
(c) Did you discuss any potential negative societal impacts of your work? [Yes] . In420 the conclusion, we discussed potential misuse of graph classifiers that may result in421 discriminatory classification.422
(d) Have you read the ethics review guidelines and ensured that your paper conforms to423 them? [Yes]424
2. If you are including theoretical results...425 (a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions426 for the original SDP primal problem (8) are stated in Section 4.1. Assumptions for427 Lemma 1 are stated in Section 4.3.428
(b) Did you include complete proofs of all theoretical results? [Yes] Proof of Lemma 1 is429 provided in Section 4.3.430
3. If you ran experiments...431 (a) Did you include the code, data, and instructions needed to reproduce the main experi-432 mental results (either in the supplemental material or as a URL)? [Yes] Code, data,433 and instructions needed to reproduce the main experimental results are available at the434 link provided in footnote 4 of Section 6.1.435
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they436 were chosen)? [Yes] The convergence thresholds and maximum number of iterations437 of the core algorithms (if any) in each evaluated method were described in paragraph 2438 of Section 6.1.439
(c) Did you report error bars (e.g., with respect to the random seed after running experi-440 ments multiple times)? [No]441
(d) Did you include the total amount of compute and the type of resources used (e.g., type442 of GPUs, internal cluster, or cloud provider)? [Yes] We reported the average runtime443 of each problem for each evaluated method in Fig. 4 of Section 6. We reported the type444 of resources used in paragraph 2 of Section 6.1.445
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...446 (a) If your work uses existing assets, did you cite the creators? [Yes] We included the447 original papers and URL’s that produced the code packages in paragraph 1 of Section448 6.1. We included the URL’s where the datasets are freely available in paragraph 3 of449 Section 6.1.450
(b) Did you mention the license of the assets? [Yes] We included the license of the code451 packages used in our experiments in paragraph 1 of Section 6.1.452
(c) Did you include any new assets either in the supplemental material or as a URL? [No]453 We included all experimented assets in the main body of our paper.454
(d) Did you discuss whether and how consent was obtained from people whose data you’re455 using/curating? [Yes] We described the datasets used in the experiments, which are456 freely available in the URL’s we provided in [38] and [39] of Section 6.1.457
(e) Did you discuss whether the data you are using/curating contains personally identifiable458 information or offensive content? [N/A]459
5. If you used crowdsourcing or conducted research with human subjects...460 (a) Did you include the full text of instructions given to participants and screenshots, if461 applicable? [N/A]462 (b) Did you describe any potential participant risks, with links to Institutional Review463 Board (IRB) approvals, if applicable? [N/A]464
(c) Did you include the estimated hourly wage paid to participants and the total amount465 spent on participant compensation? [N/A]466

Review summaries:
The authors propose a projection-free algorithm for the graph-based binary classifier learning problem. The main novelty is the replacement of the PSD cone constraint projection step (full eigen-decomposition) with an iterative process that requires solving linear programs. The linear constraints are derived via a Gershgorin disc perfect alignment results in combination with the smallest non-zero eigenvalue/eigenvector pair of a Laplacian matrix. 

The authors propose an efficient algorithm for a semi-supervised classification problem, applicable for graphs (i.e., each node receives a binary label). Specifically, the problem assumes that we have available a weighted undirectional graph where a subset of the nodes are labeled (as 1, or -1). The goal is to estimate the labels of the remaining nodes, while respecting the graph structure imposed by the available edge weights. For this, the authors consider a well-known formulation, which requires solving a computationally challenging non-convex (discrete) minimization problem. In order to make it computationally tractable, they resort to a common SDP relaxation. Noting that such relaxation can be computationally demanding, due  to the need to perform a projection onto the positive semi-definite code, the authors leverage a recent result that provides simple tight bounds on the minimum eigenvalue of special matrices (Laplacian matrices of balanced graphs). In order to employ this result, they consider the dual of the SDP relaxed problem, and further modify this dual to reach a formulation for which the mentioned bounds apply. Employing these bounds allow them to devise an algorithm that requires a minimum eigenvector computation, followed by solving a linear program. They demonstrate numerically that this scheme compares favorably against existing approaches.  

This paper proposes a method based on the Gershgorin Disc Perfect Alignment (GDPA) to efficiently solve a binary semi-supervised learning problem over graphs. In short, the semi-supervised learning problem can be naturally relaxed to an SDP problem through the well-established lifting operation. The authors claim that projecting to the PSD cone can be time consuming and, instead, propose an approach to ensure that the smallest eigenvalue is non-negative (thus, the matrix being PSD) based on the GDPA, which can be encoded as a series of linear constraints. This reformulation is actually achievable in the dual of the original SDP since the tightness of the GDPA approach requires certain assumptions that are not satisfied in the primal.