Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
main_review: In this paper, the authors aim to develop an efficient algorithm for classifier learning.  

This 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.

The 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.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 
My 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.

--------------------

Update 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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.  
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.

Here are some specific comments : 

- in various places the expression "sans the last node" appears, I'd suggest replacing "sans" with "without"?

- 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.

- 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.

- 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.

- 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).

- 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.

- 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.   

Also, 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.

- 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.

- 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?

- 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?

- 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. 


-----------------------------------
Update after authors' responses :

I 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).

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.

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.

* 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?
* 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.
* 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.
* 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.
* 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.

limitations_and_societal_impact: Yes, the authors have addresses the above points. See my main review for some concerns about the limitations part.
review_title: null

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