Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
Authors: Cheng Yang
Gene Cheung
Wai-tian Tan
Guangtao Zhai
Venue: NeurIPS 2021 Submitted (2021)
Keywords: graph signal processing
binary classification
Gershgorin circle theorem
convex optimization.

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

Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment
Anonymous Author(s)
Affiliation Address email
Abstract
In semi-supervised graph-based binary classifier learning, subset of known labels 2, are used to infer unknown labels, assuming that the label signal x is smooth with respect to similarity graph specified by a Laplacian matrix. When restricting labels 2, to binary values, the problem NP-hard. While a conventional semi- definite programming (SDP) relaxation can be solved in polynomial time using, for example, the alternating direction method of multipliers (ADMM), the complexity of iteratively projecting candidate matrix M onto the positive semi-definite (PSD) cone (M ž 0) remains high. In this paper, leveraging a recent linear algebraic theory called Gershgorin disc perfect alignment (GDPA), propose fast projection-free method by solving sequence of linear programs (LP) instead. Specifically, first recast the SDP relaxation to its SDP dual, where feasible solution H > 0 can be interpreted as Laplacian matrix corresponding to a balanced signed graph sans the last node. To achieve graph balance, we split the last node into two that respectively contain the original positive and negative edges, resulting a new Laplacian H. We repose the SDP dual for solution H, then replace the PSD cone constraint H ž= O with linear constraints derived from GDPA sufficient conditions to ensure H PSD so that the optimization becomes an LP per iteration. Finally, we extract predicted labels from our converged LP solution H. Experiments show that our algorithm enjoyed a 40x speedup on average over the next fastest scheme while retaining comparable label prediction performance.
2
6
10
12
13
14
15
16
17
18
19
20
Introduction
21
Binary classifcation
of labels to N-sample set E 131, to separate two distinct classes-is basic machine learning problem [l. One common setting is semi-supervised graph classifier learning, where M known labels, &t < < M, are used to infer N M unknown labels
23
25 I;, M + < < N, in signal x, assuming that x is smooth with respect to (w.r.t)) a similarity graph G specified by graph Laplacian matrix L 2 3 4. This graph- based binary classification
27 problem is NP-hard in general [5]. A conventional semi semi- definite programming (SDP) relaxation [6] replaces the binary label constraint with more relaxed positive semi-definite (PSD) cone constraint
29 (iee. matrix variable M related to xx satisfying M > 0), and the relaxed problem can be solved in polynomial time using, for example, the alternating direction method of multipliers (ADMM) (7). However, ADMM still requires projection to the PSD cone = (M M ž 0) per iteration, which is expensive (O(N3)) due full matrix iign-ddccompositin. An alternative approach eliminates the
31
32
33
binary constraint and minimizes directly a quadratic graph smoothness term called graph Laplacian regularization (GLR) x Lx g for R and then rounds x; to 1-, However, in general
34
35
spectral methods such as GLR do not have tight performance bounds common in SDP relaxation (9].
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

2
-2
-1
4
M
-2
5
-2
-1
-2
My
GDPA
2
-1.301
-0.5912
SMS
-30776
1.8176
V
4
1.6915
-2.2007
1
-1
5
Figure 1: Example of PD matrix M and its similarity transform M
SMS and their respective
Gershgorin discs V; Note that Gershgorin disc left-ends of M are aligned at Amia (M) = 0.1078.
36 To ensure matrix variable M is PSD without eigen decempoccooooiiinnn. one naive approach is to enforee linear constraints derived directly from the Gershgorin circle theorem (GCT) [10). By GCT, every real eigenvalue À real symmetric matrix M resides inside at least one Gershgorin disc V,- corresponding to row of M with center (M) _ Mi,, and radius r (M( & Σeft [M,.hi i.e.
38
39
MM) r: (M) S S (M) + (M), Ei.
40
The corollary is that the smallest eigenvalue, Amin (M), of M is lower-bounded by the smallest Gershgorin disc left-end, denoted by Amia (M), i.e.,
41
Amin (M) A
ry (M) Amin (M).
42 Thus, to ensure M O, one can impose the sufficient condition Ami (M)
While replacing
43
the PSD cone constraint with a set of N linear constraints, cq (MM) r; (M) 2 0, Vi, is attractive computationally, GCT lower bound Amin (M) tends to be loose. As an example, consider the positive definite (PD) matrix M in Fig. [a) with Amin (M) 0.1078 (T.. The first Gershgorin disc left-end is (M) rı (M) 2 unnecessarily restrict the search space and result in a sub-optimal solution to the posed problem.
44
45
and Xmii (M) O. Thus, imposing u (M) directly would
47
48
A recent linear algebraic theory called Gershgorin disc perfect alignment (GDPA) MII provides theoretical foundation to tighten the GCT lower bound. Specifically, GDPA states that given graph Laplacian matrix L corresponding to a balanced signed graph G [12], one can perform similarity transform I. = SLS-1, where S = diag("] ..... 'N and v is the first eigenvector of L, such that the Gershgorin disc left-ends of L are exactly aligned Amin (L) = >mii (L). This means that transformed L satisfies Xmi (L) = Amia (L); i.e., the GCT lower bound is the tightest possible after an appropriate similarity transform. Continuing our example, similarity transform M = SMS of M has all its disc left-ends exactly aligned at Amin (M)- = Amiu (M) = 0.1078.
49
51
52
53
54
55
56
Leveraging GDPA, we develop a fast projection-free free algorithm for semi-supervised graph classifier learning. We first observe that the optimal solution M of the SDP relaxation an adjacency matrix to balanced signed graph. However, GDPA requires Laplacian matrix, which has opposite signs in the off- aii-diagonal terms the corresponding adjacency matrix of the same graph. Thus, we convert the problem to its SDP dual [13 and interpret the dual variable H instead as a Laplacian to balanced graph sans the last graph node. To achieve graph balance, we split the last node into two and divide the original positive and negative edges among them, resulting in revised Laplacian H. We repose the SDP dual problem for solution H, then replace the PSD cone constraint H > with linear constraints derived from GDPA. This changes the optimization to a linear program (LP) per iteration that is solved efficiently using fast LP solvers [14). Finally, we extract prediction labels from our converged LP solution H. Experiments show that our algorithm enjoyed a 40x speedup on average over the next fastest scheme while retaining comparable label prediction performance.
57
58
59
60
61
63
65
66
67
Related Work
68
89 Graph-based classification was first studied almost two decades ago 23.
With the advent of graph signal processing (GSP) [5 [6] -spectral analysis of discrete signals residing on combinatorial graphs-interes, in the problem was revived [17 18 [9]. The problem of learning a similarity
70
71
72 graph from data has been extensively studied (20]. We focus instead on the orthogonal problem of
predicting binary labels given similarity graph and subset of M labels.
A similarity transform B -SAS-1 and the original matrix A share the same set of eigenvalues 10

---

74
The graph- traph-based binary classification problem is NP-hard in general [5]. SDP useful in approx-
75
imating various NP-hard problems [3] provides an intuitive relaxation 6 An interior point
76
method tailored for the slightly more general binary quadratic problem (BQP) has complexity
((N355 (og(1 (1/e), where e the tolerable error [1]] The complexity was improved to ((N)) by
77
78
SDCut [22 23 via spectrahedron- based relaxation. Replacing PSD cone constraint M 2 0 with a
79
factorization M = XX was proposed in [24], but resulted in a non-convex optimization for X that was solved locally via alternating minimization, where in each iteration matrix inverse of worst-case complexity O(N was required. More recent first-order methods for SDP such as [ used ADMM
81
25 26 27. but the iterative projection onto PSD cone requires full matrix dgen-decoompostiinn and thus expensive. In contrast, leveraging GDPA theory 11. our algorithm is entirely projection-free free.
83
84
It is known in graph spectral theory (28) that balanced signed graphs have unique spectral properties
85
29 ; for example, the signed graph Laplacian matrix [3) has eigenvalue 0 iff the corresponding
86
signed graph is balanced. In contrast, extending the original GCT [00] GDPA [1]] states that the
87
Gershgorin disc left-ends of similarity transform SMS-1 of graph Laplacian M to a balanced
88
graph can be perfectly aligned at Amin (M). GDPA theory was developed for metric learning [31]
89
to optimize a PD matrix M given a convex and differentiable objective Q(M) so that the optimal Mahalanobis distance (f, f,) M(f; -f) for feature vectors f, and f, can be defined. This paper leverages GDPA [I]] in an entirely different direction for graph- based binary classifier learning, Specifically, observing that solution matrix H to the SDP dual a Laplacian to a balanced graph g sans the last graph node, we augment the last node to obtain an overall balanced graph G, and solve modified SDP dual for Laplacian H to 9 via GDPA linearization.
90
91
32
93
94
95
3
Preliminaries
96
3.1
Graph Definitions
97
A graph is defined as E(V.E), with node set V (1..., and edge set E = {(i,)), }. where (i.j) means nodes and j are connected with weight was E R. A node may have self-loop of weights E R. Denote by W the adjacency matrix, where Wi5 = w and W.: u4. We assume that edges are undirected, and W is symmetric. Define next the diagonal degree matrix D, where
98
99
100
D = C, W.,. The combinatorial graph Laplacian matrix [5] is then defined as L = D D- W. To account for self-loops, the generalized graph Laplacian matrix is defined as L D W diag( (W). Note that any real symmetric matrix can be interpreted as a generalized graph Laplacian matrix.
102
103
104
The graph Laplacian regularizer (GLR) specified by C is
[8] that quantifies smoothness of signal x E R. w.r.t. graph
105
x TTLx=
Σ (i-))EE
wis(a; - x2,)² + Σ E
(3)
SEV
106
GLR is also the objective of our graph-based classification problem.
107
3.2
Iterative GDPA Linearization
108
Denote by L a generalized graph Laplacian matrix to a balanced and connected signed graph 9 (with or without self-loops). A balanced graph is graph with cycle of odd number of negative edges. By Cartwright-Haray Theorem (CHT) 11], a graph is balanced iff nodes can be colored into blue and red, such that each positive (negative) edge connects nodes of the same (different) colors. GDPA states that similarity transform L = SCS-1, where S = diag(vī* ,....Uy ", " and v is the first eigenvector of L, has its Gershgorin disc left-ends aligned exactly at Amin (f), ie.,
109
110
111
112
113
C, - > Cr,و J
Σ 1s =min(,, Vi (J. Jo
(4)
114 To solve an optimization of the form mincz Q(C), one can leverage GDPA and optimize iteratively 115 as follows. At iteration i with solution L" compute first eigenvector yf to L corresponding to
116 Amin (C'); extreme eigenvector v can be efficiently computed in complexity (ab)) using Locally
BQP objective takes quadratic form x Qx, but Q is not required to be Laplacian similarity graph.
3

---

V1
V2
Ys
V2
Va
3
W23
W 12
W2.3
1
2 W12
3
W23
Z2
-2
3
4
5
1
a)
b)
2
d)
U
Figure 2: (a) 3-node line graph example. (b) Idcal solution M to SDP primal 8 as adjacency matrix. (c)
Solution H to SDP dual [12) as Laplacian matrix. (d) Solution H to modified SDP dual (20) as Laplacian matrix. Positive / negative edges are colored in blue / red. Self-loop weight in (c) for node 4 is 144 +
Optimal Block Preconditioned Conjugate Gradient (LOBPCG) 32 where is the number of non-
118
zero entries in L and b is the iteration number till convergencd for iteration & 1, solve the following optimization:
Define scalars 8f = 1/04, Vi. Then
min Q(4),
S.t. Lis
W/Lrs/8) Σ j
2 0, Vi
(5)
Linear constraints in (5) ensure that the similarity transform L SCS is PSD by GCT, and hence solution C is PSD. Since scalars } are computed from first eigenvector v² of C = 0, by GDPA SL'S-' has all its disc left-ends aligned exactly at Amin (C') 2 0, and hence L remains feasible at iteration t + 1. Thus, objective Q(2") is monotonically non-increasing with t, and the algorithm converges to local minimum. We invoke this iteration solve posed SDP dual as well.
121
123
4
Formulation of Graph-based Classifier Learning
125
126
graph-based based classifier learning problem and relax it to an SDP problem in Section 4.1 We then present its SDP dual with dual variable matrix in Section 4.2 Finally, we interpret H as a graph Laplacian, and augment its corresponding graph G to a balanced graph 9 for
We first formulate the graph-
127
128
129
GDPA linearization in Section 4.
130
4.1
SDP Primal
Given a PSD graph Laplacian matrix L E NxN of a positive similarity graph 9 (i.e., all edge weights Wr, 2 0), one can formulate a graph-based based binary classification problem as follows:
131
132
a = 1, (1......... x4 S., (i M}
min Lx, s.t. x
(6)
133
where M are the M known labels. The objective in (6) dictates that signal x is smooth w.r.t graph go specified by L. Because PSD [66, the objective loundeb by 0. i.e.,
134
135 x Lx 2 0, vx E R. The first binary constraint ensures 2; E E (-1,1). The second constraint
ensures that entries x; in signal agrees with known labels {
196
137 As an example, consider a 3-node line graph shown in Fig. aaa), where edges (1,2) and (2, have weights 11,2 and W2,,, respectively. The adjacency matrix W and graph Laplacian matrix L are:
138
W1.2
di
W1.2
W- =
W1,2 O
0
W2.3
L
=
W1,2
d2
W2,3
W22 2
W2.3
d3
139 where d, = E, (K,jies Wiy the degree of node é. Suppose known labels are ④1 and f.2 1.
Due to the binary constraint on 2; 's. (6) is NP-hard [5]. One can define SDP relaxation [5] as
141 follows. Define first X = xx and M = X x: x 1]. M is PSD because: i) block [1] is PSD,
142 and ii) the Schur complement of block [1] of M is X - xx O, which also PSD. Thus, the two
Warm start [1] can be employed to reduce b in subsequent iterations given v is computed repeatedly for gradually changing 's See Section 5 for details.

---

143 constraints M = 0 and rank(X) = 1 is equivalent to X = xx", which together with X5z = 1, v4 144 implies 2 Vi. To convexify the problem. we drop the non-convex rank constraint and write the
SDP relaxation for optimization variable M as
X
1, E X
[I,..,,
min Tr(LX) x.
M
X
(8)
X
1
32 54
i (1, M.
146
where Tr(x Lx) Tr(Lxx] )
Tr(LX). Because S has linear objective and constraints with an
additional PSD cone constraint, M 0, it is an SDP problem. We call (8) the SDP primal.
148
Continuing our example, consider ground-trune truth labels x = -1 1]T for the 3-node graph in
149
Fig. 2 a). The corresponding solution matrix M
[xxx x; x i]
-1
1
- 1 1
-1
-1
M
-1
150
Observe that M be interpreted as an adjacency matrix a balanced signed graph: nodes 1, and 4 can be colored blue, and node 2 can be colored red, so that positive (negative) edges connect only nodes of the same (different) colors. See Fig. (bb for illustration of the corresponding signed graph when interpreting M as an adjacency matrix (self-loops are not shown). However, while the solution space for the SDP primal X exhibits desirable graph balance, GDPA requires instead
152
153
154
graph Laplacian matrix to balanced graph, which has opposite signs in the off-diagonal terms as the adjacency matrix. This motivates us to investigate the corresponding SDP dual problem instead.
156
157
4.2
SDP Dual
158
We derive the dual problem based on SDP duality theory
13 We first define
0 ONN
e
A = diag(en+1(i))
B,
(i)
(10)
159
where ex E (0, 1J. is a length-N binary canonical vector with a single non-zero entry equals N-by-N matrix of zeros, and diag(v) is a diagonal matrix with diagonal entries equal to v. Note that A; and B, are symmetric. Next, we collect M known labels
180
1 the i-th entry, ONxN
161
{ J into vector b RRM of length M, i.e.
182
b = 22,
ViE (1....,M},
(11)
163
now define the SDP dual as
N+1
min 1 I +b z, s.t. H Σ y + Σ BB L
(12)
y.
164 where 1n a length-N vector ones, and dual variables are y g- and z E RM Because the objective is minimization, when b; < 0 (i.e., 2; 0), the corresponding x; 2 0. Similarly, for
186 b, > O, 2; S 0. Thus, the signs of variables 2 's are known a priori. Without loss of generality, we assume 2, 0, Vi (1....,M}) M1} and 2 0, Vi E (Mi + 1...., M) in the sequel.
4.3 Reformulating the SDP Dual
169 We interpret H (W++1)x(N+1) in (12) as graph Laplacian corresponding graph G. However, is not a balanced signed graph, because of the last row / column in H. To this, write
C g
H
(13)
9N+1
where g = - [..... zar O Ml Matrix C, E NNN, which equals L, diag(y), uN) L, generalized Laplacian N-node positive graph G However, node N + 1 has both positive
5

---

173
and negative edges to g stemming from negative 's and positive 2, 's, respectively. As result, H a Laplacian corresponding balanced signed graph.
174
175
Continuing our 3-node line graph example with Laplacian L, the corresponding by and H are
y1 + d1
- 11.2
0
+ d1
- -11,2
0
Cy
11
1/ d2 W2.3
W2,
+ d3
H
W1,2
21
0
1/2 + d2
W2,3
22
W2,3
+
0
d3
y4
22
0
(14)
176
Interpreting H as a graph Laplacian, node has degree d4 -21 22. Thus, 1/4 U4 + d4, and
self-loop weight for node 4 iss u4 1/4 + + 22. See Fig. 2(c) for an illustration of this graph G.
178
In graph terminology. node (N++) has positive and negative edges, with respective weights ) M i=1 24- We construct an augmented graph ② with N + 2 nodes from G by splitting node N in & into two in G. dividing positive and negative edges between them. The specific graph construction for 9 procedure is
and { |=M,,
i=M +1+ to G+, and self-loop with weight uN+1 yN+1 Σ
180
1. Construct first N nodes with the same inter-connections sub- sutb-grap G+.
2. Construct node N with positive edges {-z; ) and node N 2 with negative edges
{-2;) M1++1 the first N nodes in sub- sub-graph g+
185
3. Add self-loops for node ++1 and N+2 with respective weights uy-1/2-e and uN+ 12+e, where E IR is parameter to be discussed.
186
Denote by H IR (N+2)) the graph Laplacian matrix corresponding 3. Continuing our
187
3-node graph example, Fig. d shows the augmented graph G, and the corresponding H is
188
+ d1
- W1.2
0
112
1/2 + d2
W2.3
22
H
W2,3
+
d3
0
0
(15)
21
0
[84
21 + 22) -
22
0
1
(U4
21 22)
+
189
Spectrally, H and H are related; we prove that Amin (H) is lower bound for Amin (H).
Lemma 1. The smallest eigenvalue Amin (H) of graph Laplacian H. augmented graph G is lower bound for Amin (H) of Laplacian H to G, i.e.
190
181
Amin (H) < Amin (H).
(16)
192
Proof. Denote by G the graph represented by generalized graph Laplacian H, with inter-node edge weights {wij] and self-loop weights {u.). Denote by v E RRN+1 the first eigenvector of H
194
corresponding to the smallest eigenvalue Amiu (H). From (3). GLR of H computed using v is
M
N
v Hv
Σ
Wis(1: - 03)²
z (1N+1 v;)2 +
Σ
you + UN41" (17)
(1J)EEIISUSE)
1=1
Now construct N+2
where ==01 [U11.... ..U.U UN UN+1 u4+1l TT. GLR of H computed using a is
Mi
a Ha=
Σ
Wh - u,)
2(UN+1 - v2)
Σ
2 - 0x)
M=
N
+ Σ
you +
uN+1
-)
2t u2 +
UN++1
+
UN+1
(18)
2
2
Thus, v HH a Ha. Since first eigenvector v minimizes the Rayleigh quotient of H,
Amin H TH
T Ha
a Amin H
(19)
(a) holds since v v a by construction, and (b) holds since Amin (H) ming x Hx

---

199
From the proof above, the usefulness of parameter e becomes clear: the bound Amiu (H) S Amin (H) becomes tight when the last two entries the first eigenvector of H are similar. To promote this, we set to an appropriate large value, so that the first eigenvector minimizing the Rayleigh quotient of H would choose similar small values for the last two entries.
200
202
Given Lemma 1 we now reformulate the SDP dual (12) by keeping the same objective but imposing
203
204
PSD cone constraint on H instead of H. Define A, B3 and B" similarly to (IO) but for larger
(N 2)- 2) matrix; f.e., A diag(ex)2(1)). B [B; Ow+1; 0 N+1 0J, and B"
(NN+) eN+1 (1); (i) 0j. The reformulated SDP dual is
206
min 1 IN+1 +b y
(20)
Mi
M Σ i= 1=1++1
s.t. H 2
Σ y/ A + KN+I + DN42AAN42 +
2,
BB
zBB² - - L20
207
where KN+1
Σ
24 E and KN+2 11
Li=Mi+1 2 +
M
Given H is now
208
Laplacian to a balanced graph, we discuss the application of GDPA lincarization to solve (20) next.
Algorithm Implementation
209
210
5.1
GDPA Lincarization
We replace the PSD cone constraint on H in 20 with N linear constraints via GDPA [I].
Specifically, at iteration I, we compute first eigenvector v' of solution H' using LOBPCG 32 We
212
define scalars 8; 1/0f, Vi (1, (l,..... N 2). Finally, we write N 2 constraints corresponding
213
(SHS- 1) 2 0, where S diag( (1, ......... ( N2+2), Le.,
Vi + d. - Σ iit 18:00k 83
/ |8,24/ N+
0, Vi E (1...., M1}
IV M MVVV
yi + d, Σ
jæt 18:W0's// / 831
Vie E { [M] + +1, 1,.... M} 0,
0,
1/4 + di
Σ
jzt
Wie (M + +1, 1,...,N) N}
(21)
WN+1 2
Σ 2==1
Ar
9NN+12//3)
UN+1 12 22 + -- 2i= |SN+22//80
215
where the indices for summation Σ Ejæt are {I...., NN \ i. Note that the absolute value operation can be appropriately removed for each term 8/85 and 8,2/sj, since the signs for 8;, Wi, and 2j are known. Together with linear objective in (20), this constitutes an LP for variables y and solvable using any available fast LP solvers [14). Compared to SDP primal (8) with a large matrix
216
218
variable M E (N++))(N++) our LP variables, y E N+1 and z E R M are much smaller.
219
A sequence of LPs are solved, each time with scalars s;'s updated from computed solution H until convergence. The bulk the complexity resides in the computation of the first eigenvector v for each LP solution H'. LOBPCG is iterative algorithm that can benefit from warm start [II: with good initial guess for v the algorithm converges faster. Since H' changes gradually through our iterations, use previously computed eigenvector v*-1 of H initial guess for v' of H'. Experiments show that warm start reduces the iteration number till convergence significantly.
221
223
225
5.2
Initialization & Prediction Label Extraction
227
5.1 requires an initial H to compute first eigenvector vO, so that scalars { N-2 can be defined for N + 2 linear constraints in (2T). To initialize H we set y [1], 0 O Mr M]
Our LP in Section
228
and N
2- ... .. Parameter is set to ef 1 + 1
iteration t. H can
then be computed using definition of H in (20).
231 As similarly done in [ we extract prediction labels x* [2] 10.....7 FN] from converged LP solution
y and x" as follows. We first construct H" using y* and z" using definition of H in (22). We then 233 compute x* = ( en v), where vy is the first entry of the first eigenvector v of H See 5 for details of recovering SDP primal variables from dual variables in BQP.
7

---

6
Experiments
235
236
6.1
Experimental Setup
We implemented our GDPA- GDPA-graph- based classifier learning scheme in Matlab and evaluated it in terms of average classification error rate and running time. We compared our algorithm against the following schemes that solve the SDP primal problem (8) directly: i) two primal-dual interior-point
237
238
239
solvers for SDP, SeDuMi and MOSEK, both of which are available in CVX with CVX Professional
241
license
33 ii) an ADMM first-order operator-splitingg solver CDCS 22 27] with an L.PL-3300
242
License| 34] iii) a spectrahedron-basee based relaxation solver SDCut 122 23 35 that involves L-BFGS-B
243
[6], and iv) a biconvex relaxation solver BCR (24 37]. all of which are implemented in Matlab. In addition, we employed CDCS again to solve our modified SDP dual problem (20).
We set the convergence threshold of the first eigenvector solver LOBPCG to be 10-4, with maximum number of iterations 200. We set the convergence threshold of our LP solver to be 10-4 also, with maximum number of iterations 100, since first-order methods, i.e., CDCS and SDCut, aim at
245
246
247
computing a solution of moderate accuracy [26]. Accordingly, we set the convergence threshold of SeDuMi and MOSEK to be 'low', which is approximately equal to 10-4 and the lowest precision setting in CVX. We set the convergence thresholds of CDCS and SDCut to be 10-3 the maximum number of ADMM iterations in CDCS to be 1000, the maximum number of iterations for L-BFGS-B B in SDCut and the main loop in BCR to be 100, and the Frobenius norm weight in SDCut to be 100. We chose these settings since smaller convergence thresholds and larger number of iterations would cause CDCS, SDCut and BCR to be significantly slower to converge. We used default settings for all remaining solvers. All computations were carried out on a Windows 10 64bit PC with AMD Ryzen Treennhhhn Thhredrripprrr 3960X 24-core processor 3.80 GHz and 128GB of RAM.
249
251
252
253
255
256
257
We adopted 17 binary datasets that are freely available UCI (38 and LibSVM (39 For exper- imental efficiency, we first performed a K'fold (K < 5) split for each dataset with random seed 0, and then created 10 instances of 50% training-5099 test split for each fold, with random seeds
259
1-10 40). The above setup resulted in problem sizes from 29 to 400. We applied the following two data normalization schemes for the training/test data: i) a standardization scheme in [4]] that first subtracts the mean and divides by the feature-wise standard deviation, and then normalizes to unit length sample-wise, and ii) a min-max scheme [40] that rescales each feature to within 0 and 1. We
261
262
263
added 10- 12 noise the dataset to avoid NaN's due to data normalization small samples.
264
285
6.2
Experimental Results
286
Fig. and the first two plots of Fig. show classification error rates and runtime (in log scale) using min max and standardization data re-scaling strategies for 17 different datasets, respectively. The
287
268
axis of each plot denotes the datasets in ascending order of problem sizes. Each point in the plots denotes the average of 10K runs. Fig. (right) shows runtime versus problem size (4 to 24428) using
289
270
the same dataset cod-rna (freely avaiable in LibSVM 39 ) We did not execute SeDuMi, MOSEK,
CDCS (8), BCR, SDeut, or CDCS 20 when the problem size was larger than 976.
272 In terms of classification error rate for min-max re-scaling, MOSEK, CDCS g and SeDuMi had slightly larger error rates: 32.52%, 32.38% and 29.922 92%, respectively. GDPA had 29.11%. which was very close to CDCS (20) 99% and SDCut at 28.76% This shows that our proposed GDPA linearization (T) closely approximated the modified SDP dual (20) in performance. BCR at 26.82% was roughly 2% smaller. In the standardization reascal case, CDCS (8). MOSEK, and SeDuMi had the largest error rates: 32.75 32.75% 32.5% and 31.0%, respectively. GDPA had 26.88%, close to CDCS 20) at 26.9% and SDCut with 26. 82.. BCR at 24.8% was again roughly 2% smaller. By factorizing a PSD) matrix M- = XX BCR avoided any SDP relaxation, which may explain its slightly better performance here. However, BCR solved a non-convex optimization problem converging to local minimum, and thus occasionally the performance was quite poor (e.g., see sonar in Fig. 3 llett).
273
274
275
276
277
278
279
280
282
Overall, all solvers performed similarly given constructed similarity graphs in the two cases.
283
In terms of runtime, BCR was competitive with GDPA when the problem size was small, but GDPA significantly outperformed all competing solvers when the problem size was large. Specifically, the
284
285
speed gain increased as problem size increased; for madelon with problem size 400, the speedup of
results reproducible via code in httphtt//// :/ttoo/oo/ 4open. wwweencee//Dea....ee www.aaaaaaaaaaaaaaaaaaaaaaaaa EF4D/
8

---

286
GDPA over the next fastest scheme BCR was 346x. Fig. (right) also shows that the computation time for GDPA increased gracefully as the problem size increased very large sizes. The reason for our dramatic speed gain is the fast computation of first eigenvectors using LOBPCG, which benefited from warm start during the I.P iterations. In general, GDPA performed fewer than 10 LP's until convergence. In contrast, both CDCS and SDCut required digonddecomposition of a matrix of size N X N per iteration. Because L described a dense graph in our experiments, the speedup of replacing the full eigen-decomposition with simpler first eigenvector computation per iteration was significant. For BCR, each iteration required either N N-diiensional matrix inversion for a least-squares problem or iterative gradient descent, which was computationally expensive as the problem size increased. On average, GDPA enjoyed a 40.9 x speedup over the next fastest solver BCR.
287
289
290
291
293
295
30
SalaMM MOSEK
Seihuli
MCSEK CDCS
eroor rate (%)
29.5
CDCS (R)
26.5
SCR
29
SDccut
CDCS (20)
aror role
40
SDail CDCS (20)
28.5
GDPA
30
26
GDPA
20
10-
Iiverdisarkers
[kaming
5000
colot
voling
monkk
WDBC
ILPD
beaat
breas mamoe-e
anstralia diabotos
punsa
fourt
german misiiion
27.5
27
löver disndissddss
plaminn
Sorant
hoa
WDB
[LPD
broat coltoin
ausraalan
pina
Courclees
greman
modilon
avg.
05
avg.
Figure 3: Error rates (%) for min-max (left) and standardization (right) data re-scaling.
10
10
SeTuMM
104
MOSEK
CDCS (B)
10
SDest
numine (ms)
runlime (mns)
CDCS (20)
rurlimm (ms)
GDPA
10'
100
20a
10
00
0 0000
10
100
10
live decmien
plomtng
Labermail
vollng
mank
I1.D0
huart
broast camtor
auderal an
diabets ees
pina
Fourd lass
gretuss maieiin avg
live live--Ciseeden
Inborman
voling
NDB
LLPD
australian an
pima
foundless
gremon
madidon
avg
10a
10a
problem
Figure 4: Runtime (ms) for min-max (left) and standardization (center) data re-scaling on different datasets,
and runtime (ms) for variable problem sizes on the same dataset cod-rna (right).
7 Conclusion
296
We propose fast projection-free algorithm for the graph-based classifier learning problem. The key idea is to replace the difficul-to-compuuee positive semi-definite (PSD) cone constraint with linear constraints derived from the recent Gershgorin disc perfect alignment (GDPA) theory, so that the optimization can be solved as a sequence of linear programs (LP). Experiments show that our algorithm enjoyed considerable speedup while retaining comparable label prediction performance.
296
300
302
graph classifier scalable to very large sizes encourages ubiquitous deployment for wide-ranging applications. Negative social impact can result if the tool is misused by enabling classification for discriminatory purposes. As an optimization problem, graph-based binary classification is rather
303
304
305
narrowly defined (though multi-class classification can be implemented as tree of binary classifiers). Furthermore, good performance depends heavily on the construction of good similarity graph,
306
which is outside the scope of this paper. However, we conjecture that the general methodology of
308
GDPA linearization can be similarly tailored to other SDP problems with PSD cone constraints. We anticipate that speedups in other SDP problems will also be significant.
9

---

310 References
[1] C. M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Veriee Verlag, Berlin, Heidelberg, 2006.
312
313
[2] D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Scholkopf. "Learning with local and global consistency," in 16th International Conference on Neural Information Processing (NIPS), Whistler, Canada, December 2003.
314
315
316
[3 M. Belkin, I. Matveeva, and P. Niyogi, "Regularization and semisupervised learning large graphs," in Shave-Taylor J., Singer Y. (eds) Learning Theory, COLT 2004, Lecture Notes in Computer Science, 2004, vol. 3120, pp. 624 638.
317
319
[4] A. Guillory and J. Bilmes, "Label selection on graphs." " in Twenty-Third Annual Conference on 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- tion problems." IEEE Signal Processing Magazine, vol. 27, no. 3, pp. 20-34, 2010.
322
323
[6] Z. Li, J. Liu, and X. Tang, "Pairwise constraint propagation by semidefinite programming for semi-supervised classification," in ACM International Conferene on Machine Learning, Helsinki, Finland, July 2008.
324
325
[7] B O' O'Donoghue, E. Chu, N. Parikh nad, and S. Boyd, "Conic optimization via operator splitting and homogeneous self-dual embedding," " in Journal of Optimization Theory and Applications, 2016, vol. 169, no.3, pp. 1042-1068.
327
329
[8] J. Pang and G. Cheung, "Graph Laplacian regularization for inverse imaging: Analysis in the continuous domain," " in IEEE Transactions on Image Processing, April 2017, vol. 26, no.4, pp.
330
331
1770-1788 1785.
332
99] M. Goemans and D. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming," J. ACM, vol. 42, no. 6, pp. 1115-1145, Nov. 1995.
334
335
[10] R. S. Varga, Gershgorin and his circles, Springer, 2004.
[11] C. Yang, G. Cheung, and H. Wei, "Signed graph metric learning via Gershgorin disc perfect alignment," arXiv, 2021.
337
338
[12] D. Cartwright and F. Harary, "Structural balance: a generalization of Heider's theory," in Psychological Review, 1956, vol. 63, no.5, pp. 277-293.
339
340
[13] B. Gartner and J. Matousek, Approximation Algorithms and Semidefinite Programming,
Springer, 2012.
342
[14] R. Vanderbei, Linear Programming: Foundations and Extensions (5th Edition), Springer Nature, 2021.
343
[15] A. Ortega, P. Frossard, J. Kovacevic, J. M. F. Moura, and P. Vandergheynst, "Graph signal processing: Overview, challenges, and applications," in Proceedings of the IEEE, May 2018, vol. 106, no.5, pp. 808-828.
345
347
[16] G. Cheung, F. Magli, Y. Tanaka, and M. Ng, "Graph spectral image processing," in Proceedings 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 high dimensional data: Theory and applications to sumi-super learning," in 27th International Conference Machine Learning, Haifa, Israel, June 2010.
350
352
[18] D. Shuman, M. Faraji, and P. Vandergheynst, "Semi-supervised learning with spectral graph wavelets," in International Conference on Sampling Theory and Applications (Sampíl'A), Singapore, May 2011.
353
354
355
[19] G. Cheung, W.-T. Su, Y. Mao, and C.-W. Lin, "Robust semisupervised graph classifier learning with negative edge weights," in IEEE Transactions on Signal and Information Processing over Networks, December 2018, vol. 4, no.4, pp. 712-726.
357
358
20 X. Dong, D. Thanou, M. Rabbat, and P. Frossard, "Learning graphs from data: A signal representation perspective," " IEEE Signal Processing Magazine, vol. 36, no. 3, pp. 44-63, 2019.
359
360
[21] C. Helmberg, F. Rendl, R. Vanderbei, and H. Wolkowiez, "An interior-point method for semidefinite programming." in SAIM J. Optim., 1996, vol. 6, no.2, pp. 342-361.
10

---

362 [22] P. Wang. C. Shen, and A. van den Hengel, "A fast semidefinite approach to solving binary quadratic problems," in IEEE International Conference on Computer Vision and Pattern Recognition, Portland, OR, June 2013.
363
[23] P. Wang, C. Shen, A. Hengel, and P. Torr "Large-scale binary quadratic optimization using semidefinite relaxation and applications." " IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 3. pp. 470-485, 2017.
386
[24] S. Shah et al., "Biconvex relaxation for semidefinite programming in computer vision," in European Conference on Computer Vision, Amsterdam, the Netherlands, October 2016.
389
370
[25] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, "Distributed optimization and statistical learning via the alternating direction method of multipliers," " in Foundations and Trends in Optimization, 2011, vol. 3, no.1, pp. 1-122.
371
372
[26] Y. Zheng, G. Fantuzzi, and A. Papachristodoulou, "Fast ADMM for sum-of-squares programs using partial orthogonality"" IEEE Transactions on Automatic Control, vol. 64, no. 9, pp.
374
3869-3876, 2019.
[27]
Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, "Chordal decomposition in operator-spliting methods for sparse semidefinite programs," Mathematical Programming,
377
378
vol. 180, pp. 482- 2020.
379
[28]
Chung, Spectral Graph Theory, American Mathematical Society, 1996.
380
[29]
T. Dittrich and G. Matz, "Signal processing on signed graphs: Fundamentals and potentials," in IEEE Signal Processing Magazine, November 2020, vol. 37, no.6, pp. 86-98.
[30] J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E. D. Luca, and S. Albayrak, "Spectral analysis of signed graphs for clustering, prediction and visualization," " in SIAM International Conference on Data Mining, Columbus, OH, May 2010.
383
384
385
[3]] Panagiotis Moutafis, Mengjun Leng, and Ioannis A. Kakadiaris, "An overview and empirical comparison of distance metric learning methods," IEEE Transactions on Cybernetics, vol. 47, no. pp. 612-625, 2017.
386
387
386
[32] A. Knyazev, "Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method," SIAM Journal on Scientific Computing, vol. 23, no.
390
2. pp. 517-541, 2001.
391
[33]
"CVX Research,"
Accessed: 2021-5-28.
392
[34]
"CDCS implementation." http:://gtttooo////oooooottttoto
Accessed: 2021-5-
393
28.
394
[35]
"SDout implementation" httpp:///gitaaa..cc///aaaaaaaaaa
Accessed: 2021-5-28.
395
[36] C. Zhu, R. Byrd, Lu, and J. Nocedal, "Algorithm 778: L-BFGS-B: Fortran subroutines
for large-scale bound-constrained optimization." ACM Trans. Math. Softw. vol. 23, no. 4, pp. 550-560, Dec. 1997.
397
398
[37] "BCR implementation." httter//ghthacccccaacccooo//llss cessed: 2021-5-28.
Ac-
400
[38]
"UCI machine learning repository," httppp//aaraaiee....eedcddda//aa Accessed: 2021-5-28.
[39]
"LibSVM Data: Classification (Binary Class), httpp://www..ww.... wwwp::/wwweeeeenee..mmm wttu.edu..w//ccllii. html Accessed: 2021-5-28.
403
404
[40] S. Russell and P. Norvig, Artificial Intelligence: Modern Approach, Prentice Hall Press, USA, 3rd edition, 2009.
406
[41] M. Dong, Y. Wang, X. Yang, and J. Xue, "Learning local metries and influential regions for classification," IEEE TPAMI, vol. 42, no. 6, pp. 1522-1529, June 2020.
407
Checklist
408
1. For all authors...
11

---

410
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's s contributions and scope? [Yes]. The paper proposes a new fast algorithm for the precisely defined graph-based classifier learning problem.
411
412
(b) Did you describe the limitations of your work? [Yes]. In the conclusion, we discussed the limitation of our work: graph-based binary classification is somewhat narrowly defined, compared to the more general semi-defiitte programming (SDP) problem. However, we conjecture that similar optimization strategies can be customized for other SDP problems, which is left for future work. Moreover, the performance of graph classifier depends heavily on the construction of a similarity graph, which is outside the scope of this paper.
414
416
418
(c) Did you discuss any potential negative societal impacts of your work? [Yes]. In the conclusion, we discussed potential misuse of graph classifiers that may result in discriminatory classification.
421
422
423
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] 2. If you are including theoretical results...
424
425
426
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions for the original SDP primal problem (8) are stated in Section 4.1. Assumptions for Lemma
427
| Jare stated in Section 4.3.
428
429
(b) Did you include complete proofs of all theoretical results? [Yes] Proof of Lemma is provided in Section 4.3.
430
431
3. If you ran experiments...
432
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the suppiemental material or as URL)? [Yes] Code, data, and instructions needed reproduce the main experimental results are available the link provided in footnote 4 of Section 6.1
433
434
435
438
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes] The convergence thresholds and maximum number of iterations of the core algorithms (if any) in each evaluated method were described in paragraph 2 of Section 6.1
437
438
439
440
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We reported the average runtime of each problem for each evaluated method in Fig. of Section (6 We reported the type of resources used in paragraph 2 of Section 6.
443
445
446
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We included the original papers and URL's that produced the code packages in paragraph of Section
448
6.1 We included the URL's where the datasets are freely available in paragraph 3 of |ection|6.1
450
451
(b) Did you mention the license of the assets? [Yes] We included the license of the code packages used in our experiments in paragraph of Section 6.1
452
453
(c) Did you include any new assets either in the supplemental material or as a URL? [No] We included all experimented assets in the main body of our paper.
454
455
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [Yes] We described the datasets used in the experiments, which are freely available in the URL's we provided in (38) and 33 of Section 6.1
456
457
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
459
460
5. If you used crowdsourcing or conducted research with human subjects...
461
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
462
463
(b) Did you describe any potential participant risks, with links to Institutional Review
Board (IRB) approvals, if applicable? [N/A]
12

---

485
(c) Did you include the estimated hourly wage paid to participants and the total amount
486
spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "TH6GQ3D51IX", "reviewer": "Reviewer_EGbx", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is easy to follow. The contribution is not huge but it is clear. The use of the GDPA technique could go beyond the problem considered here and this paper can serve as an example of its implementation. In that sense, the value of the contribution can go beyond the specific problem of binary supervised learning on graphs. \nMy main criticism has to do with the comparisons with other methods in Section 6. The authors consider comparisons mainly with SDP methods (except for BCR), thus showing the computational gain with respect to these SDP baselines. However, there is no comparison with simpler non-convex methods beyond BCR and, more importantly, with very simple relaxations like relaxing the binary constraint to a box constraint [-1, 1] and minimizing the quadratic Laplacian loss. A minimization like that one can probably be implemented very fast, but presumably has worse performance? There is no such comparison in the paper.\n\n--------------------\n\nUpdate after author replies: Thank you for including the new comparison. My evaluation of the paper remains. Also, please note that all the other three reviewers had trouble with the paper writing and organization. The fact that I found it easy to follow (maybe due to more familiarity with the subject) does not invalidate their concerns.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No comment.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "T3Y4MAVMkU", "reviewer": "Reviewer_WMZZ", "summary": "In this paper, the authors consider the classifier learning problem. To avoid the PSD cone constraint which is computationally expensive, the authors relax the problem by using linear constraints following from the Gershgorin disc perfect alignment theory, and propose an algorithm without projection onto the PSD cone.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "In this paper, the authors aim to develop an efficient algorithm for classifier learning.  \n\nThis paper is not well-written, and the paper structure is to be improved. In Introduction, the authors should leave more space for discussing the background and motivation of the problem considered, instead of introducing the Gershgorin circle theorem. More details on the design of the algorithm should be included in Section 5.\n\nThe contributions seem not enough for the paper to be accepted in NeurIPS. More specifically, the main contributions of this paper focus on the algorithm. Starting with the non-convex problem in Eq. (6), the authors first proposed a convex relaxation problem in Eq. (8), then reformulated the dual problem of (8) and obtained the problem (20). The authors continued to change the problem by replacing the PSD cone constraint in (20) with linear constraints. However, the authors do not provide theoretical analysis to guarantee that the final solution obtained can approximate the solution of the original problem well.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors should improve the paper structure, and provide theoretical analysis on the problem relaxation. Please refer to Main Review above for more details.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "POEgDLPGztt", "reviewer": "Reviewer_a4qs", "summary": "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.\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "It is not clear if the proposed method is more efficient than full eigen-decomposition. More precisely, computing the smallest eigenvalue/eigenvector pair is as hard as computing the full eigen-decomposition. The authors should handle the points below if they claim otherwise.\n\n* You should provide explicit bounds on the time complexity of full eigen-solvers $O(n^3)$ versus your approach, i.e., solving a sequence of LPs. What is the time complexity of your proposed approach?\n* What is the time complexity of computing the eigenvector corresponding to the smallest eigenvalue? Can you bound b in L116? As far as I know, computing the smallest eigenvalue/vector is as hard as computing the full eigen-decomposition. Please clarify and be precise in your statements otherwise.\n* Section 5.1. You need to provide a bound on the number of iteration of your GDPA linearization process. How many steps are required to achieve an approximate solution? Please elaborate if there is any bound on the rate of convergence.\n* The abstract is very hard to follow. I would highly recommend that the authors make an attempt to rewrite it. For example, the problem studied is not clear and in L4 is stated that it is NP-hard. Complexity is high (L8) can be more precise. Last but not least, please do not state in the abstract step-by-step how you approach the problem but only state the key insights, i.e., use of GDPA theory and LPs. Removing the part, \"Specifically,... per iteration\" would remove a lot of unnecessary details.\n* Please define the optimization problem in introduction more precisely. For example, what is optimized exactly? Please do not assume the reader is familiar with the problem under study.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have addresses the above points. See my main review for some concerns about the limitations part.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "1q7awmPqOU3", "reviewer": "Reviewer_4zJS", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper makes use of a recent result (Gershgorin disc perfect alignment -- GDPA) to modify a matrix (through a similarity transformation) so as to obtain tight bounds (via Gershgorin discs) on the minimum eigenvalue of the matrix. In order to apply the result, the authors go through multiple stages of transforming the problem of interest, namely semi-supervised graph classifier learning. Overall, I think the paper is potentially interesting in terms of demonstrating how GDPA can be employed to tackle a common formulation of this specific problem. However, I also found the paper to be terse, unclear at times.\n\nHere are some specific comments : \n\n- in various places the expression \"sans the last node\" appears, I'd suggest replacing \"sans\" with \"without\"?\n\n- Introduction : It would be useful to introduce the notion of a \"balanced graph\" with a proper definition. In particular, you can mention that a graph with positive edge weights is balanced.\n\n- If the graph doesn't have self loops, typically the first eigenvector of Laplacian matrices for graphs with positive weights is all ones (with zero eigenvalue) -- for readers not expecting self-loops, it might be good to mention the existence of self-loops.\n\n- line 53 : The sentence starting with \"This means that transformed...\". Is the equality \\lambda^- = \\lambda (i.e., tight bound) obvious? Again, for readers not familiar with GDPA development, it might be good to mention this is a consequence of the GDPA development, because the bound is not tight for regular Gershgorin discs, as you state elsewhere.\n\n- Section 3.1 : It might be good to introduce \"balanced graphs\" properly here, since it is a key concept for GDPA (and generalizes graphs with positive edge  weights).\n\n- Section 3.2 : I recommend including a clear statement of GDPA (possibly along with necessary definitions), since the purpose of the paper is to apply it to a particular problem. Any additional discussion, insight is welcome.\n\n- Paragraph starting at line 148 : I think this discussion is important, but currently, it's really abrupt. Specifically, if you could spare a few more words on how in general M could/should be interpreted as an adjacency matrix.   \n\nAlso, in and of itself, this doesn't motivate the consideration of the dual, is that right? The form of H in the dual resembles a Laplacian, because it contains L, which appears in the cost function of the primal problem.\n\n- line 158 instead of \"We derive\", I would suggest using \"We state\", since there's no derivation in this section. Is (12) obtained from the Lagrangian dual of (8)? If so, I suggest to mention this explicitly. If there are additional hoops one needs to jump through, it would be good to note that as well.\n\n- line 164, sentence starting with \"Because the objective is a minimization, when b_i <0, ... z_i >= 0\" : I'd agree with this statement if the problem (12) were unconstrained. But z_i's also appear in the constraints -- is the statement still obvious?\n\n- line 171 vs eqn (12) : According to eqn (12), shouldn't we have L_y = diag(y_i) - L, as opposed to diag(y_i) + L, as written in line 171?\n\n- eqn (21) : these work for any s_i, don't they (since we're performing a similarity transformation and resorting to bounds obtained from Gershgorin discs)? Even though arbitrary Gershgorin disc bounds may not be tight, they wouldn't lead to solutions that violate any constraints. By including v_i's as you define here, you essentially work with the \"best possible\" before attempting to solve the LP. If you agree with this comment, I'd suggest including something in this direction in the text as well. \n\n\n-----------------------------------\nUpdate after authors' responses :\n\nI have read the other reviews and authors' responses. As I noted in my original review, I do think the paper could be interesting as a demonstration of GDPA to alleviate the numerical problem of projection onto the PSD cone. But I must also note that I am not blown away by the specific application. I thought there are issues with the technical presentation (but not the correctness of the statements). Since I see that the authors have taken steps to make some changes in this direction, I'm increasing my score from 5 to 6 (marginally above the threshold instead of below).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting paper on using the Gershgorin Disk Theorem applied to a special case so that the PSD constraint on the solution of a binary graph classification problem can be replaced by a linear number of linear constraints. This is done by approximating/computing the smallest eigenvalue using an iterative Lanczos type method that has linear complexity. The paper has merit but it fails to convince that it is a better method for the binary graph classification application (for example, compared to other relaxations to the problem). The novelty of the paper is also limited since the GDPA result comes from an existing paper. Some reviewers also felt the writing was not clear.
Decision: Reject