A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks

Summary

The paper investigates the relationship between graph topology and feature evolution in Graph Neural Networks (GNNs). The paper starts by discussing the phenomenon of Neural Collapse (NC) in instance-wise deep classifiers, where within-class variability decreases and class means align to specific symmetric structures. The study is then extended to node-wise classification using Stochastic Block Model (SBM) graphs. An empirical study reveals a decrease in within-class variability in GNNs trained for node classification on SBMs, although not as pronounced as in the instance-wise setting. The authors propose a graph-based mathematical model to understand the influence of node neighborhood patterns and community labels on NC dynamics. The model requires strict structural conditions on the graphs to exhibit exact variability collapse, highlighting the distinction between GNNs and plain deep neural networks. Gradient dynamics analysis of the graph-based model provides theoretical explanations for the observed partial collapse in GNNs. The paper also explores the evolution of features in well-trained GNNs and compares it to spectral clustering methods. Overall, the paper investigates feature evolution in GNNs and provides insights into the impact of graph topology on this process.

Strengths

1. This paper focuses on an interesting topic: Neural Collapse during the training of graph neural networks. 2. The paper concretely shows the decrease of within-class variability.

Weaknesses

1. Analyzing only intra-class (within-class) variability without discussing inter-class variability is meaningless. 2. The study of over-smoothing [1] phenomena has also discussed the decrease of within-class variability. A discussion about the difference between within-class variability caused by over-smoothing and neural collapse can clarify the contribution of this work. 3. The theoretical analysis presented in this work has limited practical utility. [1] Keriven, Nicolas. "Not too little, not too much: a theoretical analysis of graph (over) smoothing." *arXiv preprint arXiv:2205.12156* (2022).

Questions

1. Can the theoretical analysis in this work lead to any practical design improvements? 2. The term "instance-wise case" (line 11) should be defined. 3. The notation of class is used in line 155 but is not defined in the 2.1 data model section. 4. A more detailed discussion should be given about the regime of exact recovery (line 94). 5. The optimizer is defined in line 147, but the loss or objective function to be optimized is not specified.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

2 fair

Contribution

1 poor

Limitations

N/A

Summary

This paper investigates the feature evolution in Graph Neural Networks (GNNs) via the lens of Neural Collapse. They conduct an empirical study that reveals a decrease in within-class variability in the deepest features of GNNs, but not to the extent observed in instance-wise classification settings. By proposing and analyzing a graph-based Unconstrained Features Model (UFM), the authors show that a strict structural condition on the graphs is necessary for exact variability collapse, which is a rare event. They provide theoretical reasoning for the partial collapse observed during GNNs training and study the evolution of features across layers in well-trained GNNs, comparing the decrease in NC metrics with power iterations in spectral clustering methods.

Strengths

This paper presents a pioneering study on Neural Collapse (NC) in Graph Convolutional Networks (GCNs) and the forward process of a neural network, which has the potential to inspire future work. The authors provide unique and valuable theoretical results, such as the partial collapse in Theorem 3.1. Additionally, the paper is well-written, the methodology is clearly explained, and the proposed approaches appear to be solid.

Weaknesses

This paper has a few areas that could be improved upon. 1. Some experimental findings could benefit from stronger support through theoretical results (Please refer to Questions 1-3). 2. The applications and implications of certain theorems could be further elaborated (Please refer to Questions 4-5).

Questions

To enhance the manuscript, the authors may consider addressing the following points: 1. In addition to the collapse of variability (NC1), the preference towards a simplex ETF (NC2) is an important observation in the original NC paper [34]. From Figure 1(c), it seems that some variant of NC2 might also hold in GCNs. To provide a more comprehensive understanding of NC, it would be helpful if the authors could include a theorem or at least a discussion on NC2. 2. While Theorem 3.1 and Theorem 3.2 demonstrate that the within-class variability is non-zero with high probability, the authors have not provided a lower bound for the variability concerning p and q. Analyzing this lower bound could strengthen the paper's contribution. For example, the authors might consider analyzing the expected variability under SSBM. 3. Theorem 3.3 appears to be somewhat weaker compared to existing studies on NC (e.g., [54]). It would be beneficial to provide a local or global convergence. 4. In Lines 270 - 276, the authors show that the ratios in GCN behave differently compared to those in power iterations (i.e., simplified graph convolutional networks). It would be insightful if the authors could explain how this difference benefits GCNs. Additionally, the evolutions in $\mathcal{F}$ and $\mathcal{F}'$ are different, and understanding how this difference impacts the performance of $\mathcal{F}$ and $\mathcal{F}'$ would be valuable. 5. Relating Theorem 4.1 to classic results in GNNs (e.g., over-smoothing) could provide further context and strengthen the paper's overall contribution to the field.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

Yes

Summary

This work tries to investigate the feature evolution in GNNs in inductive setting. In particular, it focuses on the Neural Collapse problem using the SSBM data model to ensure the existence of this phenomenon. Moreover, it proposes to verify that the extent of NC in GNNs is not as severe as in instance-wise classifications.

Strengths

1. It is interesting to study the feature evolution with GNNs and especially the correlation between the topological information. 2. The data model is clearly presented and the experiments are close to the theoretical results.

Weaknesses

1. The study of feature evolution with GNNs and especially the correlation between the topological information is a great topic, however, the data model and the concentration on the NC condition slightly retreat the original claim into a theoretically friendly but less practical direction. 2. Most concerns are raised about the practical value of this study, which lies in two aspects: 1. the motivation of this work needs to be further clarified, e.g. why the NC phenomenon is important, what about other stages of trait development. 2. data model: SSBM is a good model to study the topological features. My concerns are mainly about the practical significance of this paper. If I have missed anything important in the proofs and arguments, please let me know.

Questions

1. Major: 1. A more comprehensive motivation for studying feature evolution in GNNs is highly recommended. And there is another smoothing problem: If the paper focuses on the NC view, the pre-convergence stage is completely missing. Since for most of the case or GNN practitioners are doing with pre-convergence stage, which should be more worthy to study. It is just to make sure that the problem and the perspective are really practical. 2. For the inductive setting, which this paper concentrates on, it is not necessary that the test nodes are in a different graph than the training nodes. It only requires that the test nodes do not appear in the training phase. 3. The experiments are performed only on the graphs simulated by the SSBM assumptions. 2. Minor: 1. Line 53-54: Essentially, we highlight the main differences in the analysis of NC in GNNs by identifying structural conditions on the graphs under which the global minimizers of the training objective exhibit full NC1. Hard to understand, you can split it - since it is one of the main findings of the paper, which needs to be clear enough. 2. Line 79-80, the MLE loss is more and more popular to train DNN classifiers might be misleading somehow. However, MLE is a well-known alternative for more complex loss functions in machine learning theories.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Limitations are not included by the authors. As I presented questions above, my concerns are mainly about the practical significance of this paper.

Summary

EDIT: I am changing my score based on the revision. I think this is a very interesting paper. In particular, it helps us understand why GNNs work well, but not super-duper well. CNNs get full NC, but GNNs don't This work discusses neural collapse of GNNs. Much of the work on neural collapse focuses on unconstrained features which is somewhat in conflict with the constraints imposed by graph structure. The main contributions of this work are. 1. Empirical study showing that some decrease in within class variablility, but not to the same extent as in vanilla DNN 2. Graph based UFM. Prove that with optimistic model, need strict structural condition to get full NC. 3. Study gradient dynamics of graph-UFM that partially explains theoretical reaonsing for partial NC 4. Compare NC1 metrics of GNNs vs spectral clustering Overall, this is a very good paper. It shows that GNNs exhibit partial, but not total neural collapse. In some sense, this may help explain why GNNs are near state of the art for many tasks, but nowhere near "perfect". However, I believe there is an error in the proof of theorem 3.2. I believe this error is fixable, but that the statement of the theorem will have to change. Therefore, I am strongly opposed to acceptance before this issue is fixed. I should also mention that I did not have time to check the last two proofs as thoroughly as I would like. The authors should make sure to check them very carefully before resubmission since there was already one mistake. (I will check aggressively then.) If these issues are addressed, I would likely be in favor of acceptance.

Strengths

This paper contributes many new ideas to understand NC in the graph setting. Much of which are highly-nontrivial extensions of the original NC such as providing a characterization of when NC occurs and showing that the loss function will decrease, but level off before zero.

Weaknesses

Major Issues In the proof of Theorem 3.1, it is not clear what $y_c$ is. This needs to be made more clear. In Section D.2, you should recall the definitions of the different $\Sigma$s or at least reference where they are defined. It is difficult to keep track of the many definitions. I don't understand the inequality of the form $P(A|B)\leq P(A)$ given in 444. I also don't think you need it to obtain equation (50) which I think is correct. Could you please revise or clarify? (I am not overly concerned since the downstream equation appears to me to be correct. However, there is a similar issue for the diagonal terms which I think is more serious.) The bound obtained in Theorem 3.2 is hard to parse an it is not obvious to me whether or not this quanity tends to zero. Perhaps you can approximate via sterlings inequality or something? Footnote 2 is unconvnincing since the terms (and the number of terms) change as n increases. I think you can argue (informally) that for large $n$ the probability that a Binomial RC is exactly equal to its mean, is equivalent to the probability that a normal RV with std $n^{-1/2}$ is within $1/n$ of its mean. Interpretation the standard deviation as average difference between the sample and the mean, this means that the probability of this occuring is on the order of $(1/n)/(1/\sqrt{n})$ which then tends to zero as $n\rightarrow \infty$. (THIS IS THE BIG ONE): I don't think the argument used for the diagonal blocks is the proof of Theorem 3.2 regarding the upper bound for conditional probabilities is correct. For example, Set $t_{cc}=n-1$ and consider the probability of $E^c_{c,i}$ occurring given that $E^c_{c,i}$ for all $i<n$. Given that every other vertex is connected to $n-1$ other vertices of class $c$, this means that the set of all vertices in class $c$ form a clique. Therefore the probability of $E^c_{c,n}$ occurring is one. THIS ISSUE MUST BE FIXED IN ORDER FOR ME TO RECOMMEND ACCEPTANCE. Possible remedies include (i) convince me that I am mistaken (which is possible) (ii) remove the terms corresponding to the diagonal from the statement of the Lemma (in this case you should verify that this still converges to zero) (iii) add the assumptions that we are in the sparse regime to the statement of the lemma. Argue that cliques (or dense subgraphs in general) are exceptionally unlikely in this regime and that for reasonable values of $t$ the events are ``close to being independent." This is likely the best solution, but it would also require a bunch of non-trivial computations in order to make it precise (and the statement of the theorem would still need to change to reflect what you gt in these estimates) (iv) the event that the diagonal blocks satisfy the condition you need is equivalent to an erdos renyi random graph being regular. There is probably a bunch of existing work on this topic. Minor Issues: In the summation on line 121, adding a subscript j to the summation would make things more clear, i.e., $j \in \mathcal{N}_c(v_c,i)$ The capitlizatin is off in some of the refreeneds, in Euclidean shoudl be capitalized in ref [7]. Please fix. Line 344 in the proof of Theorem 3.1: ``Theorem 3.1" should be capitlalized. It might be a good idea to first explain the idea of the proof of theorem 3.2, i.e. that first you show that in the limit, every vertex in class c has the same degree. Therefore, the stated condition that all of the vertices in $v_i$ have the same \textit{fraction} or neighbors in each class $c'$ is equivalent to them having the same \textit{number} or neighbors in $c'$ (which can then be estimated more easily using formulae for binomial RVs) Line 419 in the supplement. I think you should remove the word essentially, right? The number of neigbors IS a binomial RV.

Questions

\subsection{Questions} 1. Line 44, when you say that the rules become similar to the nearest class center in the feature space do you mean the classifier is effectively an NN-classifier? 2. Why is there a $y_k$ in (1), but $y_k(V_k)$ in (2)? This seems inconsistent. 3. In the ``simpler" model (4), is the definition of $\hat{A}$ the same as in (3)? In this setting it would make sense to add self loops as in Kipf and Welling, i.e., $\hat{A}=(A+I)(D+I)^{-1}$. Otherwise, nodes don't communicate with themselves at all. Am I missing something? 4. For the sake of self-containedness, could you please briefly explain the instance-normalizaiton? 5. How important is the assumption of balanced communities in your theoretical analysis and how does this affect the applicablity of your theory to real-world imbalanced datasets 6. Hidden feature is the same size in all layers. How does this affect the results? What happens if you first increase and then decrease (or something) is there still partial NC1? 7. In the Graph UFM, if the $H_k$ are freely optimizable, why do you still need seperate matrices $W_2$ and $H_k$?v (This may be a standard thing. I am not very familiar with UFMs) 8. For the stochasitc block models, shouldn't there be some sort of concentration of measure result where for large $n$ we have $A\approx EA$? This should allow you to apply theorem 3.3 to it, right? 9. In Theorem 3.3, you obtain that $\tilde{NC}_1$ decreases which means it converges to some non-zero limit. Is there a good way to think about what this limit is? Does it, for example go to zero in the case that $E\rightarrow 0$? How does it depend on $\alpha?$ 10. In line 427 of the proof of theorem 3.2, I think you need probability $1-4n^{-r}$ because of the union bound. (This is unimportant but should be fixed.)

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Reply to Author Rebuttal

Thank you for the detailed explanations provided. Regarding my initial query, could you point me to the specific experiments that support your assertion of an "increase in between-class variability"? In line 247, you've showcased empirical results that indicate a gradual decrease in the NC1 metrics as the network depth increases. Would it be possible for you to measure the NC2 under the same experimental conditions?

Response to the authors' rebuttal

I thank the authors for their detailed responses to my concerns. Especially the answers regarding "**Regarding feature evolution and pre-convergence phases of training.**" and the data model greatly improve my understanding. I would like to ask three more questions: 1. Talking about over-smoothing phenomenon, over-smoothing should not be a relative issue to NC, since it is not only "(NC1) The within-class variability of the deepest features decreases", but to a global extent. 2. Still, from a practical point of view, the rewriting point should be included in the discussion of this paper, e.g. a section after the experiments, to help build more reasonableness and soundness of this work. I fully understand that your work is from an analytical point of view. 3. Finally, the sentence "in the case of GNNs, the graphs must satisfy a strict structural condition for collapsed minimizers" gives a good explanation, and this should also be made clear after the theoretical analysis (SSBM and UFM), especially by introducing a quantified variable that controls the randomness in real graphs, and how significant it is by doing empirical measurement. To this end, the understanding should be more smoothing. This may be difficult to achieve in this rebuttal stage, but I would recommend doing so in a later revision. Overall, the authors have addressed most of my concerns well and I would like to raise my score to 5. I ask the authors to be patient with my concerns and suggestions above.