Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper finds that the conventional Graph Regularized MLPs(GR-MLPs) suffer from the dimensional collapse phenomenon that a few large eigenvalues dominate the embedding space and proposes ORTHO-REG, a GR-MLP model that encourages orthogonal embeddings to mitigate the issue.
strength_and_weaknesses: This paper demonstrates that the conventional GR-MLPs suffer from the dimensional collapse phenomenon in which a few large eigenvalues dominate the embedding space, thus restricting the representation power of these models through theoretical analysis and empirical results. To solve this problem, the authors propose ORTHO-REG, a GR-MLP model that adds regularization terms to encourage orthogonal embeddings and tackle high-order connectivity and non-homophily graphs. The model shows improved performance compared with conventional GR-MLPs and some GNNs on semi-supervised datasets and cold-start scenarios. In general, the paper explains the failure of existing GR-MLPs and is of good structure. However, there are some issues the authors need to address.

1. The theoretical analysis in Sec.3 is questionable. Lemma 1 and Theorem 1 only consider the laplacian smoothing term as the loss function and do not consider the effect of classification loss, which makes the whole theoretical analysis fundamentally problematic. In fact, the proof of lemma 1 implicitly assumes that the laplacian smoothing loss will be optimized to zero. However, in most cases, the smoothing term will not converge to zero because of the classification loss’s influence; thus, the relative value of the smaller eigenvalues to the largest one may not always decrease. Therefore, the lemma, as well as the theorem, does not hold.

2. In the experiment of Sec.3, the eigenspectra for node embeddings do not change much as the weight of the smoothing term increases, which may indicate the dimensional collapse phenomenon is not too severe. It also suggests that classification loss dominates the training process instead of smoothing loss, which contradicts the assumption of the above theoretical analysis.

3. The relation between the dimensional collapse phenomenon and the poor performance of existing GR-MLPs should be explained. Sec.3 mainly demonstrates the existence of the dimensional collapse phenomenon. However, there is no evidence that this phenomenon causes performance degradation of existing models. Intuitively, a modest dimensional collapse might help improve model performance because it might filter noise from input features.

4. Furthermore, the final model is inconsistent with the previous analysis because it introduces higher-order connectivity information, so it cannot be demonstrated that mitigating the dimensional collapse phenomenon alone will improve model performance. To verify this, experiments using the model based on eq.4 are suggested.

clarity,_quality,_novelty_and_reproducibility: On the whole, these are OK.
summary_of_the_review: This paper tries to show that the dimensional collapse phenomenon leads to poor performance of the existing GR-MLP model, but there are defects in both the experiment and the theory, which makes a claim not strong enough.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies graph-regularized MLPs performance limitations. They show that the node embeddings space from a conventional GR-MLP suffers from dimensional collapse (or spectral collapse). Their solution, ORTHO-REG, mitigates this issue by introducing a soft regularization term based on the correlation matrix of node embeddings in the loss function and then removing the dependency of graph structure on the MLP loss term. Their experimental evaluation shows performance improvement over the SOTA.
strength_and_weaknesses: Pros:
1. The authors take into account the related methods and explain their differences from their technique clearly. For example, differences from the graph-augmented MLPs were explained. 
2. The idea of combining node embeddings and summary embeddings in Eq.7 is neat but with certain caveats, I believe. The choice of \alpha and \beta will play a vital role here. 
3. The results in Table 1 are impressive 
4. The paper in general clearly states the contribution and comparison with related works.

Comments
1. Extension to other graph types, Multi-graphs, graphs with hypernodes? As these types are typically used to represent knowledge graphs, do you foresee any issues with generalising the guarantees to these graph types?
2. (Page 3, 1st para) “Note that GNNs explicitly utilize the graph structure information through learning the mapping from node features and graph adjacency matrix to predicted labels. However, due to the above limitations, we seek for learning an MLP encoder, i.e., H = fθ(X) that only takes node features for making predictions.” Can you please explain the limitations? Are the limitations introduced by the graph structure, can you please give examples as GNNs perform quite well on graph structured data? (I might be missing some context here, in that case, kindly add more explanation in the draft. Maybe, here the authors might want to introduce the idea of soft-regularization.)
3. The theoretical results are for linear f(X). How well will they hold for the non-linear nature of MLPs? I only see empirical justification. This will be a strong paper if some theory can be developed in that direction, as pointed out in page 4.  
4. What are the values of \alpha and \beta in table3, for the bottom 3 rows? I would like to understand how the regularization terms trade-off with each other. Thanks.
5. Have you studied other types of graph regularizations?

clarity,_quality,_novelty_and_reproducibility: <covered in the above section>
summary_of_the_review: Ablation study on the range of \alpha and \beta parameters done in section 5.4.2 highlights the strengths as well as limitations. Although, the authors demonstrate empirically that their regularization mitigates the spectral collapse problem, the theory proposed is not sufficient.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to investigate why the performance of graph-regularized methods could not match GNN models. It shows that the spectral collapse occurs under the linearity assumption of the mapping module (i.e., linear MLP). Then, the authors design a new regularization term for GR-MLPs. The experimental results show that the proposed term works pretty well on real datasets. 
strength_and_weaknesses: ### Strength
- The paper is well-written and well-motivated. The idea and motivation are clarified and the paper is easy to follow. 
- The experiments are strong and the performance could match the results of SOTA GNN models. 

### Weakness
- The theoretical conclusions are based on the linearity assumption, which is not clarified in ABSTRACT. It is an important precondition of the theoretical analysis and it should be emphasized. 
- When theoretically analyzing the existence of dimensionality collapse, the supervised loss, ($\ell_{xent}$, is neglected. It also produce the gradient w.r.t. W. However, Lemma 1 fails to clarify it. If I don't misunderstand, the conclusion only holds when $\lambda \rightarrow \infty$ ($\lambda$ is defined in Eq. 1). It is the main limitation of the anlaysis and the preconditions have to be clarified in Lemma 1. 
- $\{\lambda_i^C\}$  seems to only appear in the beginning of theoretical analysis. I know the convergence of $\sigma_i(W(t))$ would lead to the statement, but there should be some descriptions of $\{\lambda_i^C\}_{i=1}$ after Lemma 1. 
- As the authors claim that the efficiency of graph models is quite important, Eq. 5 seems a quite time-consuming operation. What is the difference between the GR-MLP with the proposed term and other models, including existing GR-MLPs and GNNs?
clarity,_quality,_novelty_and_reproducibility: - The dimensionality collapse has been investigated in self-supervised learning, and the authors try to use it to find why GR-MLPs fail to match GNNs. Although the orthogonal penalty term is pretty common in recent works, the paper is well-motivated. 

- The paper seems technically sound. 
summary_of_the_review: Overall, the paper is well-motivated and easy to follow. The theoretical analysis makes the orthogonal term convincing. The paper has some  merits, but there are several drawbacks as well. I'd like to update my score after reading the feedback and other reviews.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a theoretical and empirical study on the problem of dimensional collapse due to over-smoothing in graph-regularized MLPs. Then, they propose to regularize the cross-correlation between node features and pooled features to alleviate this problem. The resulting model "Ortho-Reg" surpasses the performance of the compared baselines on semi-supervised and cold-start scenarios. Additional experiments show that the proposed regularization helps to alleviate the smoothing problem, that the proposed model is robust to perturbations, and the robustness to different hyperparameter choices.

strength_and_weaknesses: Strengths
=======
* The proposed method is sound and it improves performance of GraphMLPs. 
* The authors provide code and ablations, which makes their method more reproducible
* The additional analysis / empirical study is interesting

Weaknesses
=========
* There exists another OrthoReg in the literature [A] that is also a regularization that enforces orthogonality. Although this does not affect the novelty of this work (since they were proposed for different purposes), it could generate some confusion. I suggest to change the name to CorrReg / OrthoGraph / OrthoGraphMLP / OrthoNodeReg / OrthoGraphReg / ....
* The number of baselines is small compared to other works [B]. Is there any reason for that?
* In Figure 2 I cannot see a big difference between different coefficients.

[A]  "Regularizing cnns with locally constrained decorrelations." ICLR 2017.

[B] "Node Representation Learning in Graph via Node-to-Neighbourhood Mutual Information Maximization." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.
clarity,_quality,_novelty_and_reproducibility: Clarity
=====
For the most part the submission is clear. I have some questions though:
* Is th $\mathbf{T}$ in the appendix related with the $T$ in equation 5?
* I cannot follow the two last steps in Equation 8. Could you explain them?
* You claim to introduce a new model but the submission is centered on the regularization technique. Are there other model-level contributions besides the regularization?
* Why didn't you choose baselines like the ones in [B]?
* Do you regularize the correlation or the covariance matrix?

There are some minor typos that sometimes hinder readability:
* Section 2.1: However, their performances are still hard to match that of GNN models. -> However, their performances are still hard to match *compared to* that of GNN models.
* Section 2.3: Ineffective -> Inefficient
* Theorem 1: the largest a few -> the largest few
* Section 4.2: while recent -> While recent
* RQ3: mitigates -> mitigate
* Section 5.4.1: lead -> leads
* Section 5.5: rather than -> rather than edges

Quality
=====
The method is sound and the claims are reasonably supported. About the experimental quality:
* There is no much difference between the curves in Figure 2. Are they for one run or multiple runs? Could you provide confidence intervals?
* Sometimes results in bold in the tables have their confidence intervals overlapping with those of other rows. Please either remove the bold font in these cases or put the overlapping numbers in bold too.

Novelty
======
* Besides the overlap with other literature in imposing orthogonality in neural networks, and the name of the method [A], this work is novel to the best of my knowledge.

Reproducibility
===========
* The authors provide the code and ablations.
summary_of_the_review: Overall the method is sound and interesting, the authors add details for reproducibility and include theoretical and empirical insights. Most of my concerns are about clarity and I suggest the authors to go through my questions above. Also, there is the name of the method, which has been used in the past in a slightly-related topic.

Given that this work still needs polishing, I think it is "marginally below the acceptance threshold". However, I think my concerns are easy to address in a rebuttal and I encourage the authors to do so. 

After rebuttal
==========
The authors' responses clarified all my questions and resolved most of the other reviewers' concerns. Thus, I raise my score to accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper investigates the dimensional collapse phenomenon, i.e., a few large eigenvalues dominate the embedding space, in conventional Graph Regularized MLPs (GR-MLPs). The paper then proposes ORTHO-REG, a GR-MLP model that encourages orthogonal embeddings to mitigate the issue. Both theoretical and empirical results are promising.

While the expert reviewers agree that the paper has some merits, there is a clear reservation as a result of the following major concerns: 

- The theoretical analysis is incomplete (Reviewers GzRn and Mv49). Reviewer GzRn and Mv49 pointed out the issue with the theoretical analysis in Lemma 1, i.e., it neglects the supervised loss and the linearity assumption is made.  Lemma 1 fails to clarify why it is reasonable to consider only the Laplacian smoothing term without the supervised loss. Hence, it's unclear to what extent the theoretical result reflects what really happens in practice. After the rebuttal and discussion phases, the reviewers remain skeptical about this aspect of the paper. 

- The empirical analysis, which could have alleviated this issue, does not show a clear collapse when using the supervised loss (Reviewer JMnM).

As a result, I cannot recommend this paper in its current form to be accepted for publication at ICLR 2023.
justification_for_why_not_higher_score: There are concerns with paper which requires a major revision and thereby another round of peer review.
Decision: Reject