Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a novel graph-embedding framework, which is a rank difference model. This rank model is NP-hard to solve, so the authors optimize the loss formulation by means of the logdet. The transformed model is then solvable and proven to be theoretically effective. The paper also offers connection between the given model and other graph embedding methods, and calculate the upper and lower bound of the proposed loss function. In total, the paper is well written and theoretically innovative.
strengths_and_weaknesses: Strength
1. The COLES can be the special case for the proposed GLEN framework, and the GLEN outperforms the COLES.
2. The theoretical analysis gives the upper and lower bound of the proposed GLEN, which makes the model have good interpretation.
3. The experiments are effective to demonstrate the proposed framework does have good performance.

Weakness
1. It is not clear about the relationship between the proposed model and the contrastive learning, although the contrastive learning is introduced in related work.
2. Compared with the trace model in COLES, the generalization of the proposed rank difference framework is not illustrated clearly. The author should give proof how the trace model can be generalized into the rank model as a special case. 
3. Although GLEN is called the generalized Laplacian Eigenmaps framework, the paper shows no other cases that can also be generalized to GLEN except COLES.
4. The paper does not compare the logdet model with other methods that can serve as a surrogate of the rank problem. There are many methods can be used to solve the problem at present, so the authors should list and compare these methods and explain why the logdet is chosen. 
5. The logdet terms are chosen to solve the rank model, which actually transfers the rank model into a logdet model. Does the logdet model still maintain the generalization property? If so, please give the proof.

questions: 1. Can authors give the proof for the Proposition 1? This proposition lacks the necessary proof.
2. Are there any other cases except COLES that can be generalized to GLEN? If so, please supply examples of these cases. Otherwise, what’s the meaning of the ‘generalization’ of GLEN? 
3. Is the logdet to solve the rank problem the original work of the paper? If not, listing the references is necessary. Does the logdet framework still hold the generalization property？If so, please give the proof.
4. Is there any other effective methods to solve the rank difference problem? The authors should compare these methods and explain the reason why logdet is chosen. 

limitations: The generalization of the proposed framework is not clearly described,  and many other cases need to supply except COLES. Besides, there are other methods to solve the rank difference problem except using logdet. The paper does not list and compare these methods.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a new unsupervised representation learning method, mainly based on GNN. 

The idea is motivated by the scatter matrices that are usually used in LDA. Based on the fact that the features would be discriminative provided that Condition 1 holds, the model aims to maximize rank($S_w$) and minimize rank($S_b$) simultaneously, which is different from the losses of the popular contrastive learning.  

In Section 3, the authors show that the equivalence between the specific two-layer (featureless) GAE and linear (featureless) GAE. 

In Section 4, the authors try to investigate the real impact of ReLU on the hidden layer. 

Then, as the original goal is NP-hard, a surrogate that approximates the rank better than the classical nuclear norm is introduced.  

Finally, sufficient experiments are conducted to verify the idea.  


strengths_and_weaknesses: ### Pros: 

1. The idea to use the scatter matrices to learn discriminative features seems novel. It is different from the popular contrastive models.  
2. The motivation is convincing and interesting to me.  
3. The experimental results, especially on semi-supervised node classification when labels are pretty rare, seem to show effectiveness. 

### Cons: 

1. An important question that confuses me is why not to testify the idea on the setting of general contrastive learning.  If I don't misunderstand the model, the graph (*i.e.*, adjacency) seems to be only used in the implementation of $f_\Theta$, which indicates that $f_\Theta$ could be any neural networks (or other projection techniques).  So why do you constrain the model on the GNNs? If some similar ideas have been proposed in the general contrastive learning (which I'm not familiar with the newest publications), it will severely affect the novelty. 

2. A major concern is the surrogate may be not novel. The idea to use $\log(\cdot)$ to replace the $\ell_p$-norm (which is equivalent to the Schatten-$p$ norm for the rank) has been well studied. Is there a difference between the following literature and this paper? It limits the novelty of the paper. 

   [1] Calibrated Multi-Task Learning, SIGKDD, 2018.   

3. Could the authors also provide some experiments under the common settings of Cora/Citeseer/PubMed, instead of the random split? It is also an important comparison with the existing GNN models.

4. No source code is provided so that it may limit the reproducibility. 

5. There are some typos including but not limited to: 
   - The meaning of letters in boldface is confusing. For example, in Figure 1, the matrix is denoted by $S_b$ while in Section 3.1, all matrices are highlighted by boldface (*e.g.*, $\textbf{S}_w$). In Line 135，$C$ is also bold.
   - In Line-145, Theorem 2 -> Theorem 1?

Overall, I would like to update my score after reading other reviews and the response. 
questions: (More details can be found in the previous part)

1. Why do you constrain the model on the GNNs? In other words, why not conduct experiments on the general datasets?> 

2. Is there a difference between the following literature [1] and this paper? It limits the novelty of the paper. 

   [1] Calibrated Multi-Task Learning, SIGKDD, 2018.   

3. Could the authors also provide some experiments under the common settings of Cora/Citeseer/PubMed, instead of the random split? 
limitations: N/A
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a novel objective for graph embedding, called Generalized Laplacian EigeNmaps (GLEN), to learn graph representation by maximizing the difference of logdet between the total scatter matrix and the within-class scatter matrix. The authors interpret this as a surrogate of rank difference maximization and give some theoretical results. Experiments show that GLEN offers good accuracy and scalability against state-of-the-art baselines on various benchmarks.

** Post Rebuttal Update **

I've read the rebuttal and the other reviewers' comments. I appreciate the update the authors have made, for example, the (supposedly) new experimental updates regarding Reviewer bffF's comment. I appreciate the experimental results against the prior art. My general concern is whether the theorem indeed shows a difference from the prior art. It seems to me that the rank difference formulation or the minimum class separation has been identified in the literature. What's more interesting is to explain why the logdet can be a better objective, which seems quite possible given the new experimental results.



strengths_and_weaknesses: ** Strengths **

S1. The proposed algorithm is based on the scatter matrices, which are of the size of $d\times d$, not $n\times n$. Note that $d$ and $n$ are the embedding dimension and the node number, respectively. Thus, the method is quite scalable to large graphs.

S2. Experiments show strong results in various settings and datasets.

** Weaknesses **

W1. The authors approximate the rank difference with logdet difference. However, it is unclear why optimizing the rank difference or the logdet difference leads to good results.

W2. The notations are confusing and may contain errors. For example, in section 3.1, it seems that $Z$ is $d\times n$ instead of $n\times m$. Also, the $S$ matrices should be $d\times d$ instead of $n\times n$. If $Z$ is $n\times m$ and $S$ is $n\times n$, then the algorithm should not be scalable as $n$ is the number of nodes.


questions: Q1. The motivation of Condition 1 is unclear. In particular, why $\text{Rank}(S_t)=\text{Rank}(S_w)+\text{Rank}(S_b)$ yields good embedding?

Q2. Why formulate the main problem as rank difference? Why not directly analyze the logdet difference?


limitations: The authors didn't discuss the limitation and potential social impact.
review_title: null

Meta-review: metareview: The Authors provided a nice rebuttal, and address major issues in the last round. Therefore, I  recommend to accept this paper.
confidence: Certain
Decision: Accept