A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks
Authors: Vignesh Kothapalli
Tom Tirer
Joan Bruna
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural collapse
Graph neural networks
Community detection
TL;DR: We analyze feature evolution in GNNs from a neural collapse (NC) perspective and identify the role of topology on NC dynamics.

Abstract: Graph neural networks (GNNs) have become increasingly popular for classification tasks on graph-structured data. Yet, the interplay between graph topology and feature evolution in GNNs is not well understood. In this paper, we focus on node-wise classification, illustrated with community detection on stochastic block model graphs, and explore the feature evolution through the lens of the "Neural Collapse" (NC) phenomenon. When training instance-wise deep classifiers (e.g. for image classification) beyond the zero training error point, NC demonstrates a reduction in the deepest features' within-class variability and an increased alignment of their class means to certain symmetric structures. We start with an empirical study that shows that a decrease in within-class variability is also prevalent in the node-wise classification setting, however, not to the extent observed in the instance-wise case. Then, we theoretically study this distinction. Specifically, we show that even an "optimistic" mathematical model requires that the graphs obey a strict structural condition in order to possess a minimizer with exact collapse. Furthermore, by studying the gradient dynamics of this model, we provide reasoning for the partial collapse observed empirically. Finally, we present a study on the evolution of within- and between-class feature variability across layers of a well-trained GNN and contrast the behavior with spectral methods.

A Neural Collapse Perspective on Feature Evolution in Graph Neural Networks
Vignesh Kothapalli New York University
Tom Tirer Bar-Ilan University
Joan Bruna New York University
Abstract
Graph neural networks (GNNs) have become increasingly popular for classification tasks on graph-strune graph-structured data. Yet, the interplay between graph topology and feature evolution in GNNs is not well understood. In this paper, we focus on node- wise classification, illustrated with community detection on stochastic block model graphs, and explore the feature evolution through the lens of the "Neural Collapse" (NC) phenomenon. When training instance-wise deep classifiers (e.g. for image classification) beyond the zero training error point, NC demonstrates reduction in the deepest features' within-class variability and an increased alignment of their class means certain symmetric structures. We start with an empirical study that shows that a decrease within-class variability is also prevalent in the node- wise classification setting, however, not to the extent observed in the instance wise case. Then, we theoretically study this distinction. Specifically, we show that even an "optimistic" mathematical model requires that the graphs obey strict structural condition order to possess a minimizer with exact collapse. Interestingly, this condition viable also for heterophilic graphs and relates recent empirical studies on settings with improved GNNs generalization. Furthermore, by studying the gradient dynamics of the theoretical model, we provide reasoning for the partial collapse observed empirically. Finally, we present study on the evolution of within- and between-class feature variability across layers of well-trained GNN and contrast the behavior with spectral methods.
Introduction
Graph neural networks [52] employ mnessage-passnng mechanisms capture intricate topological relationships in data and have become de-facto standard architectures to handle data with non-
Euclidean geometric structure [[]] 12
22
24
3
60
66
70 However, the influence of
topological information on feature learning in GNNs is yet to be fully understood 40
69
In this paper, study the feature evolution in GNNs in node-wise supervised classification setting. In order to gain insights into the role of topology, we focus on the controlled environment of the The SBM provides effective framework to control the level of sparsity, homophily, and heterophily in the random graphs and facilitates analysis of GNN which relies solely structural information
prominent stochastic block model (SBM) [1-3 29 45
g 16
20) While inductive
supervised learning on graphs is a relatively more difficult problem than transductive learning, aligns with practical scenarios where nodes need to be classified in unseen graphs (24), and is also amenable to training GNNs that are deeper than conventional shallow Graph Convolution Network (GCN) models
14 16
62
70).
The empirical and theoretical study of GNNs' feature evolution in this paper employs a "Neural Collapse" perspective [48). When training Deep Neural Networks (DNNs) for classification,
"Correpondence to: Vignesh Kothapalli @nnuu.duu
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

is common to continue optimizing the networks' parameters beyond the zero training error point 9 28 39. stage that was referred to in 48 as the "terminal phase of training" (TPT). Papyan. Han, and Donoho 25 48 have empirically shown that a phenomenon, dubbed Neural Collapse (NC), occurs during the TPT of plain D on standard instance-wise classification datasets. NC encompasses several simultaneous properties: (NC1) The within-class variability of the deepest features decreases (i.e., outputs of the penultimate layer for training samples from the same class tend to their mean); (NC2) After subtracting their global mean, the mean features of different classes become closer to a geometrical structure known as a simplex equiangular tight frame; (NC3) The last layer's weights exhibit alignment with the classes' mean features. A consequence of NC1-3 is that the classifier's 's decision rule becomes similar to the nearest class center in the feature space. We refer to 34 for review on this topic.
The common approach to theoretically study the NC phenomenon is the "Unconstrained Features Model" (UFM) [3 43 'he core idea behind this "optimistic" mathematical model is that the deepest features are considered to be freely optimizable. This idea has facilitated recent surge of theoretical works in effort to understand the global optimality conditions and gradient dynamics
of these features and the last layer's 's weights in DNNs [8 25 37 our work, we extend NC analysis to settings where relational information in data is paramount, and creates a tension with the 'freeness' associated with the UFM model. In essence, we highlight the key differences when analyzing NC in GNNs by identifying structural conditions the graphs, under which the global minimizers of the training objective exhibit full NC1. Interestingly, the structural conditions that we rigorously establish in this paper are aligned with the neighborhood conditions on heterophilic graphs that have been empirically hypothesized to facilitate learning by Ma et al. 44
43 54 61 65 71 74). In
Our main contributions can be summarized as follows:
We conduct an extensive empirical study that shows that decrease in within-class variability is prevalent also in the deepest features of GNNs trained for node classification on SBMs. However, not to the extent observed in the instance- wise setting.
We propose and analyze a graph- graph-based UFM to understand the role of node neighborhood patterns and their community labels on NC dynamics. We prove that even this optimistic model requires a strict structural condition on the graphs in order to possess minimizer with exact variability collapse. Then, we show that satisfying this condition is a rare event, which theoretically justifies the distinction between observations for GNNs and plain DNNs.
Nevertheless, by studying the gradient dynamics of the graph-based UFM, we provide theoretical reasoning for the partial collapse during GNNs training.
Finally, we study the evolution of features across the layers of well-trained GNNs and contrast the decrease in NCI metrics along depth with a NC1 decrease along power iterations in spectral clustering methods.
2 Preliminaries and Problem Setup
We focus on supervised learning on graphs for inductive community detection. Formally, we consider
collection of K undirected graphs (Gx- (Vr, {x) each with N nodes, C non-overlapping balanced communities and a node labelling ground truth function yk : Vic + {ei.... ec) ). Here, Ve [C], e, E C indicates the standard basis vector, where we use the notation [C] = {1, ... C).
The goal is to learn a parameterized GNN model (.) which minimizes the empirical risk given by:
K Σ L(vo UN (VR) + X ||1|
1 K
min
(1)
where |1-11p represents the Frobenius norm, L is the loss function that is invariant to label permutations 16), and X= > 0 is the penalty parameter. We choose L based the mean squared error (MSE)
((vb(Ga)) un) = min 1
live (Gx) n (yu (Vx)))
SESc 2N
where æ belongs to the permutation group over C elements. Using the MSE loss for training DNN classifiers has become increasingly popular recently. For example, Hui and Belkin 330 have
Throughout the paper, by (plain) DNNs we mean networks that output an mnstanc-wwis prediction (e.g.. image class rather than pixel class), while by GNNs we networks that output node-wise predictions.

---

performed an extensive empirical study that shows that training with MSE loss yields performance that is similar to (and sometimes even better than) training with CE loss. This choice also facilitates theoretical analyses 25 55
2.1
Data model
We employ the Symmetric Stochastic Block Model (SSBM) to generate graphs {9x = (Ve,&))) I==1" Stochastic block models (originated in [29] are classical random graph models that have been extensively studied in statistics, physics, and computer science. In the SSBM model that is considered in this paper, each graph G5 is associated with an adjacency matrix A E T degree matrix D& diag(A: E TR- and random node features matrix X E RdxN with entries sampled from normal distribution. Formally, if P E I CxC represents symmetric matrix with diagonal entries p and off-diagonal entries q. random graph Gy is considered be drawn from the distribution SSBM C, q) if an edge between vertices M/y is formed with probability (P), (w4)..e
We choose the regime of exact recovery 333 45 in sparse graphs where p = N , = M
allm(N)
N
for parameters a, b 2 0 such that Ivā b vC. The need for exact recovery (information- theoretically) stems from the requirement that the should be able to reach TPT (Appendix B).
2.2 Graph neural networks
Inspired by the widely studied model of higher-order GNNs by Morris et al. 44]. we design the based on family of graph operators F = (I. A
}, vk E [K], and denote it as ve. Formally, for
GNN the with L layers, the node features H E RdxN at layer / E [L] is given by:
x (1) H (1-1) + W H( As, (1) (x) H
(3)
where H X,, and (.) represents a point-wise activation function such as ReLU. W w E xd:4 are the weight matrices and A A is the normalized adjacency matrix, also known as the moddom-walk matrix. We also consider a simpler family without the identity operator J' = (A&), Ak E [K] and analyze the GNN vi"" with only graph convolution functionality. Formally, the node features !!!) RddxNN for vi is given by:
x w ( ((
(4)
H 1 o (x
Here, the subscript for the weight matrix (!( is retained to highlight that it acts on 11 A
Finally, we employ the training strategy of Chen et al. [16] and apply instance-normalizztion [58 on
o (x!!) ( e (1....,, , ,--1) 1} to prevent training instability.
2.3 Tracking neural collapse in GNNs
In our setup, reaching zero training error (TPT) implies that the network perfectly classifies all the nodes (up to label permutations) in all the training graphs. To this end, we leverage the NC [4] and extend them to GNNs in an inductive setting. To begin with, let us consider a single graph Ge = (V,, &x), k E [K] with a normalized adjacency matrix Aş- Additionally, denote H R&xNN the output of layer [L 1), irrespective of the GNN design. Now, by dropping the subscript and superseript for notational convenience, we define the class means and the global mean of H as follows:
metrics introduced in [88 55 56
C
h Σ has Vc E (C),
ha Cn
h
(5)
c=1
where n N/C represents the number of nodes in each of the O balanced communities, and h is the feature vector (a column in H) associated with Ve,i E V. i.e., the 1th node belonging to class
In setup, the nodes of sampled SSBM graphs are allowed to have self-edges.
3

---

c E [C]. Next, let (v,,,) denote all the neighbors of thss and let No (Ve,i) denote only the neighbors of Veş that belong class c' E [C]. We define the class means and global mean of HA, which is unique to the GNN setting as follows:
h
h Vc E [C],
KG
h
(6)
On
where ha. (EresENa(van) bed + Evg JEN hes) /IV(vo;))
Variability collapse in features H: For given features matrix H, let define the within- and between-class covariance matrices, (w(H) and Eg (H) as:
Ew (H)
1 Cn
be ho) (bott ho)"
(7)
EB(H) =
he - ho) (he - he)² (ho-hc)
(8)
To empirically track the within claas variability collapse with respect to the between-class variability, define two NC1 metrics:
1 - Ew (H)E
Tr Ew (H)
(H =
(H) = Tr (E
(9)
where denotes the Moore-Penrood pseudo-inverse, and Tr(-) denotes the trace of a matrix. Although NC1 the original NC1 metric used by Papyan et al. [4]. we consider also NC1, which has been proposed by Tirer et al. [56] alternative metric that is more amenable to theoretical analysis.
Variability collapse in hethbborhood-gggrggaee features HÂ: Similarly to the above, track features matrix HA by Ew (HA) and Σ (HA) (computed using hi and lig ), as well as NC₂ (HA) and NC1 (HA). (See Appendix for formal definitions.) Finally, we follow a simple approach and track the mean and variance of NC, NH),NC (H), (HA), NCC), (HÂ) across all K graphs our experiments.
the within- and between-class variability of the "neighborhoodd-ggrreeene N
As the primary focus of our paper is the analysis of feature variability during training and inference, we defer the definition and examination of metrics based on NC2 and NC3 Appendix C
3 Evolution of penultimate layer features during training
In this section, we explore the evolution of the deepest features of GNNs during training. In Section 3. present empirical results of GNNs in the setup that is detailed in Section [ showing that a decrease in within-class feature variability is present in GNNs that reach zero training error, but not to the extent observed with plain DNNs. Then, in Section 3.2 we theoretically study mathematical model that provides reasoning for the empirical observations.
3.1 Experiments
v Setup. We focus on the training performance of GNNs 1/e on sparse graphs and generate dataset of K 1000 random SSBM graphs with C N, 1000, p 0.025, q 0.0017. The networks vi the are composed of L = 32 layers with graph operator, ReLU activation, and functionality. The hidden feature dimension set to 8 across layers. They are trained for epochs using stochastic gradient descent (SGD) with learning rate 0.004, momentum 0.9, and a weight decay of 5 x 10 During training, we track the NC1 metrics for the penultimate
layer features H (.. (.(--)) by computing their mean and standard deviation across & [K] graphs after every epoch. To measure the performance the GNN, we compute the 'overlap" [16] between predicted communities and ground truth communities (up to permutations):
(g(e). - (1-))
overlap(ý. v) = max TE9C
(10)

---

0.5
0.6
TrEa Mileeiing
86 (648 (ug30
0.8
NF Ingiht
8.5
00
-.3
-3.0
04
0.4
-1.
93
0.0
0.2
-1.
-2.0
per11100
Meri1000
ROM61000
loss
(b) overlap
NCI: H
(d) NCI: HA
Figure I: GNN 3 Illustration of loss, overlap, and NC₁ plots for H. HÂ during training.
0.6
0.99
0.
0.4
R5,06 Jegin
0.3
0.2
0.97
-1.0
-1.0
-15
Mita
-1.
0.0
0.94
4or%
20/41030
(a) loss
(b) overlap
(c) NCI: H
(d) NCI: HA
Figure GNN ve
Illustration of loss, overlap, and NC1 plots for H. HÁ during training.
where is the node labelling function based GNN design and N Limi dg(es) (g(e)))(((r.))) is the training accuracy (ō denotes the Kronecker delta). The overlap allows us to measure the improvements in performance over random guessing while retaining the indication that the GNN has reached TPT. (zero training error), then overlap(ý.2 y) and present extensive experiments (showing similar
Formally, when + Ei=1 (g(e)).a(((v.)))
We
illustrate the empirical results in Figures D [nd 2 behavior) along with infrastructure details Appendix
H
tend to reduce and plateau during TPT in Vir and v/e"" Notice that even though we consider a controlled SSBM-based setting, the AC, values observed here are higher than values observed
Observation:
The key takeaway is that NC1 (H
(H NC
case of plain DNNs on real- Additionally, we can observe that trends for NC, (H (L-) A&). NC, (H (1) AA)) are similar to those of NC, ". , (H.11-)) )))
world instance-wil wise datasets
48
74]
3.2 Theoretical analysis
In this section, provide a theory for this empirical behavior. Most, if not all, of the theoretical
papers on NC, adopt the UFM approach, which treats the features as free optimization variables - disconnected from data [18 25
55 56 74). Here, consider graph-based adaptation of this approach, that dubbed gUFM We consider GNNs of the form of vhr which is more tractable for mathematical analysis. Formally, by considering C to be the MSE loss, treating { (L-1) JKK as freely optimizable variables, and representing ! RCxde-1 . (--11) Rdd2-1NN as W2, H₃ (for notational convenience), the empirical risk based on the gUFM can be formulated as follows:
43
Re (We, (Ha)
WaHaA.
Y
Y
2
AH |
12
Aw
W2
K
2N
2
(11)
where Y E N is the target matrix, which is composed of one-hot vectors associated with the different classes, and Aw, AH 0 are regularization hyperparameters. To simplify the analysis, let us assume that Y Ic & 1 where @ denotes the Kronecker product. Namely, the training data is balanced (a common assumption in UFM-based analyses in literature) with n = N/C nodes per
'Code available http://gthhubboom//ignshs/////// collapse
5

---

class in each graph and (without loss of generality) organized class-by-class Note that for K = (which allows omitting the graph index k) and graphical structure, i.., A (since A = D.
reduces to the plain UFM that has been studied in [25 55 7TI this case, it has been shown that any minimizer (W2. H") is collapsed, i.e., its features have exactly zero within-class variability:
h
han = h
E EC]
(12)
which implies Σw (H*) O. We will show now that the situation in gUFM is significantly different.
Considering the K case, we start by showing that, to have minimizers of (TI) that possess the property in (2), the graph must obey a strict structural condition. For K > 1, having minimizer (W2. (Hi}) where, for some j E [ H is collapsed directly follows from having the structural condition satisfied by the j-th graph (as shown in our proof, the sufficiency of the condition does not depend on the shared weights W2). On the other hand, generalizing the necessity of the structural condition to the case of K > 1 is technically challenging (see the appendix for details). For that reason, we state the condition in the following theorem only for K = 1. Note also that, showing that the condition is unlikely to be satisfied per graph is enough for explaining the plateaus above zero of NC metrics (computed over multiple graphs), which are demonstrated in Section 3.1
Theorem 3.1. Consider the gUFM in (11 with = 1 and denote the fraction of neighbors of node N. (vall Let the condition C based on Sce' be given by: Ve, that belong to class d' as Sec', [.
($c1,1, Scc,1)
(Sel,ns ,cCC,), Vc E [C].
(C)
If graph G satisfies condition C, then there exist minimizers of the gUFM that are collapsed
(satisfying 12). Conversely, when either vλHdW, = 0, or VHAWW, > 0 and G is regular (so that A A A if there exists collapsed non-degenerate minimizer of gUFM, then condition C necessarily holds.
Remark: The proof is presented in Appendix D The symmetry assumption on À (which implies that G is regular graph) in the second part of the theorem has been made to pass technical obstacles in the proof rather than due to a true limitation. Thus, together with the results of our experiments (where no symmetry is enforced), we believe that this assumption can be dropped. Accordingly, we state the following conjecture.
Conjecture 3.1. Consider the gUFM in 11 with K = 1 and condition C as stated in theorem 3.1 The minimizers of the gUFM are collapsed (satisfying (2) iff the graph satisfies condition C.
Let us dwell on the implication of Theorem 3.1 The stated condition C essentially holds when any node i E [x]] of a certain class c obeys (Scl. -. ScC,s) ($.1, ... Sec) for some ($c1, 1. Scc), tuple of the ratio of neighbors (E Siee 1) independent of i. That is, (Sc1, ... S.C) must be the same for nodes within the same class but can be different for nodes belonging to different classes.
For example, for a plain UFM this condition trivially holds, as A I. Under the SSBM distribution, it is also easy to see that EA satisfies this condition. However, for more practical graphs, such as those drawn from SSBM, the probability of having graph that obeys condition negligible. This is shown in the following theorem.
Theorem 3.2. Let G = (V,E) be drawn from SSBM C,p.g). For N >>> C, we have
Cie
m)m= (
Σ (?) (1)))))))-
( obeys C)
<
(13)
The proof is presented in Appendix E It is not hard to see that as the number of per-class nodes increases, the probability of satisfying condition C decreases as numerically exemplified below.
Numerical example. Let's consider setting with C 2, N 1000, 3.75. b = 0.25. This gives us n = N/C = 500, p = 0.025, = 0.0017, for which P(g obeys C) < 2.18 x 10 10-188, 188
In Appendix F we further show by exhaustive computation of PCG obeys C) that its value is negligible even for smaller scale graphs. Thus, the probability of sampling a graph structure for which the gUFM minimizers exhibit exact collapse is practically 0.

---

MC thg
RICUAMI Regin
10
0.4
-10
15
-15
-20
Irtal
-20
0.0
235
Ner%50050
16.0
Ser%50000
03
23
5.0
10.0
Ror550000
loss
(b) overlap
NCI: H
(d) NCI: HA
Figure 3: gUFM for vo Illustration loss, overlap, and NC₁ plots for H. HÂ during training on
10 SSBM graphs satisfying condition C.
(iii 0og (oc
10--0 tep scets scoles
15
310
5
0.2
01
0.0
80
3:1
R00
4ee 5500000
11e 1100000
(a) Ioss
(b) overlap
(c) NCI: H
(d) NCI: HÁ
Figure 4: gUFM for Vo Illustration of loss, overlap, and NC1 plots for H. HÂ during training 10 SSBM graphs which do not satisfy condition C.
gUFM experiments. For a better understanding of these results, we present small-scale experiments using the gUFM model graphs that satisfy and do not satisfy condition C. By training the gUFM (based on v/ metrics on H, HÂ reduce significantly.
K 10 graphs that satisfy condition C, we observe from Figure that NC1
the other hand, these metrics plateau after sufficient reduction when the graphs fail to satisfy condition C, as shown in Figure 4 In both the cases, the SSBM parameters are = 2, N = 1000, p = 0.025, q = 0.0017, and the gUFM is trained using plain gradient descent for 50000 epochs with learning rate of 0.1 and L2 regularization parameters Aw; Aw; = λи = 5 x 10 Extensive experiments with varying choices of N, C. p, 9. feature transformation based v and additional NC metrics provided in Appendix H (The additional
NC metrics measure the alignment of the classes' mean features with simplex Equiangular Tight Frame (ETF) and Orthogonal Frame (OF) structures.)
Remark. Note that previous papers consider UFM configurations which the minimizers possess exact NC, typically without any condition the number of samples on the hyperparameters of the settings. As the UFMs are "optimistic" models, in the sense that they ignore all the limitations on modifying the features that exist in the training of practical DNNs, such results can be understood as "zero-order" reasoning for practical NC behavior. On the other hand, here we show that even the optimistic gUFM will not yield perfectly collapsed minimizers for graph structures that not rare. This provides a purer understanding of the gaps in GNNs features from exact collapse and why these gaps larger than for plain DNNs. We also highlight the observation that condition C applies to homophilic as well as heterophilic graphs, as the constraint on neighborhood ratios is independent of label similarity. Thus providing insights on the effectiveness of GNNs highly heterophilic graphs as empirically observed by Ma et al. 40
By now, we have provided theory for the distinction between the deepest features of GNNs and plain DNNs. Next, to provide reasoning for the partial collapse in GNNs, which is observed empirically, turn to study the gradient dynamics of our gUFM.
Gradient flow:
We consider the K case and, following the common practice
analyze the gradient flow along the "central path" - i..., when W₂ = (H the optimal minimizer of R. (W H)
25 56
-egeneegeee minimizers the sense that W RCXN is full-rank. This climinates degencrate 'zem' solutions which are obtained when the regularization hyper-paramette are large.
Each term in each of the sums is the th power of a number smaller than (a binomial probability).
7

---

W.L.t W2. which has a flosed-form expression function of H. The resulting gradient flow is:
dH, - (H.,,,
(14)
dt
Similarly to 22 56), we aim to gain insights on the evolution of Ew (H₂) and Σg (H,, (in particular, their traces) along this flow. Yet, the presence of the structure matrix A significantly complicates the analysis compared to existing works (which are essentially restricted to = I). Accordingly, we focus on the case of two classes, C' 2, and adopt a perturbation approach, analyzing the flow for graph À EA. + E, where the expectation taken with respect to the SSBM distribution and E is sufficiently small perturbation matrix. Our results are stated in the following theorem.
0 and E such that for 0- < AH < a and 0 < [|l < E, along the gradient flow stated in (44 associated with the graph A EA- + E, we have that: (1) Tr(E (H))H decreases, and (2) Tr (T(E)(H))) increases. Accordingly, NC, (H;) decreases.
Theorem 3.3. Let K 1, C 2 and Xw; > O. There exist
The proof is presented in Appendix The importance of the theorem comes from showing that even graphs that do not satisfy condition C (in the context of the analysis: perturbations around EA) exhibit reduction in the within-class covariance and increase in the between-class covariance of the features. This implies a reduction of NC1 metrics (to some extent), which is aligned with the empirical results in Section 3.1 Additionally, we highlight that since an increase in (r(EB(H,) and decrease in Tr(2w (Hz) is desirable for NC, this behavior of the penultimate layer's 's features can potentially serve remedy for the over-smoothing problem in GNNs (more details in Appendix A
4 Feature separation across layers during inference
Till now, we have analyzed the feature evolution of the deepest GNN layer during training. In this section, we use these well-trained GNNs to classify nodes in unseen SSBM graphs and explore the depthwise evolution of features. In essence, we take an NC perspective on characterizing the weights of these well-trained networks that facilitate good generalization. To this end, we present empirical results demonstrating a gradual decrease of NC1 metrics along the network's 'ss depth. The observations hold resemblance to the with plain DNNs (shown empirically in (20 555 and more recently in (26). and theoretically in (56)) To gain insights into this depthwise behavior we also compare it with the behavior of spectral clustering methods along their projected power iterations.
4.1 Experiments
Setup. We consider the 32- laylree networks Vig V/ which have been designed and trained as per the setup section and have reached TPT. These networks are now tested dataset of K 100 unseen random SSBM graphs with C = N = 1000, = 0.025, = 0.0017. Additionally, we perform spectral clustering using projected power iterations on the Normalized Laplacian (NL) and Bethe-Hessian (BH) matrices [51] for each of the test graphs. The motivation behind this approach is to obtaín an approximation of the Fiedler vector of NL/BH that sheds light on the hidden community structure [1] 46 67). Formally, for a test graph G = (V,E), the NL and BH matrices are given by:
NL(G) = 1- 1 1/22 AD11/2 1/2
(15)
BH(G,r) - 1)I - D. where r E R is the BH scaling factor. Now, by treating B to be either NL or BH matrix, a projected power iteration to estimate the second largest eigenvector of B = |B|| - B is given by:
(16)
(1 - (x((-1), v)v
x( (w-(--), where (1-1) x((11) (xxl1-1), v)vl
(17)
with the vector E N denoting the largest eigenvector of B. Thus, we start with random normal vector w" R-V and iteratively compute the feature vector (!) RNN, which represents the 1-D feature for each node after iteration
'Interestingly, the connection between message passing in GNNs and power iterations without the normaliza- tion has been explored in [36). However, projection and normalization are paramount to our setup (with random features) for approximating the Fiedler vector.
8

---

THC OF Telatt
hitugghet Oy Inbulg nemaaio
Irdaaiieiall norratee
35
TrClaaiiiaal Op Pogarrtial manis
PrTE WiTaePhaaa DO
2.
1.4
lover
nonile Irtpa
TrOgg) commatio
Frial
Frilah
(rdaal normaliic
Thial normalze
(a) Normalized Laplacian
(b) Bethe Hessian
(c) GNN 6e
(d) GNN di
Figure 5: (H), metrics (top) and traces of covariance matrices (bottom) across pro-
jected power iterations for NI. and BH (a,b), and across layers for GNNs vh and vor (c,d).
THE Insp
Thene sate wwp10
4.2
(a) Normalized Laplacian
(b) Bethe Hessian
(c) GNN v
(d) GNN 1/
Figure 6: Ratio of traces of covariance matrices across projected power iterations for NL, and BH (a,b), and across layers for GNNs vi and vi (c,d).
4.2 Towards understanding depthwise behavior
From Figure 5 we can observe that the rate of decrease in NCI metrics is much higher in vig and V/5 (avg test overlap = 1) when compared the baseline spectral approaches (avg test overlap NL= 0.04, BH 0.15) with random normal feature initialization. For vig and vi the NC1 metrics and traces of covariance matrices are tracked after each of the components of a layer: graph operator, ReL.U and instance normalization. For spectral methods, the components are: the operator B and the normalization. Interestingly, this rate seems to be relatively higher in wh than in ver and the variance of metrics tends to reduce significantly across all the test graphs after certain depth in vee and v-5- Intuitively, the presence of W, in v/ seems to delay this reduction across layers. On the other hand, owing to the non-parametric nature of the spectral approaches, observe that the ratios (x(B((()) /)/Tr))TTTrr)r) (T((E(((((-)))) Tr(Ew (x())) / (rrrrTr(((w (T[EEw((-)) (w((-1))) tend to be constant throughout all iterations. However, the GNNs behave differently as Tr(Eg X (x))) (/TT(EBBBB (H"-)))
Tr( Tr(Ew(C (X ())) Tr/TTr(Ew (H(1-1) tend to decrease across depth (Figure 6).
For a better understanding of this phenomenon, we consider the case of C' = 2 (without loss of generality) and assume that the (1 (1-1) (1-1)th-aan -laer features (l-1) of nodes belonging to class e = 1,2 drawn from distributions Di, D2 respectively. We do not make any assumptions on the nature (t-1)
of the distributions and simply consider μ ((-1) H2 E R4 and {((-1) ((--1) E 1xde-1 as their mean vectors and covariance matrices, respectively. In the following theorem, we present bounds on the ratio of traces of feature covariance matrices after the graph operator applied.

---

Theorem 4.1. Let C = 2.),;()), x_10) p B1 = p-g f2 n(pta)) 1(p+-))
indicate the tth largest and smallest eigenvalue of a matrix, and denote
Tw = w1 w + $2
W W w
+ W1 ( w: 22 T
TB (w: + 3 w
(wiT) + $1 w
Then, the ratios of traces are bounded as follows:
Tx(E0((())
TH (x >}
for layer I E (2, ,L, of network ehg
Th The (1)-))))
di-1 X- Eg (H (("-")) A (TB)
Tr Tr Tx(E((X()))
di-1 i= do (E (B((H- A (TB)
D d EB (H(-
Th(En (H()))))
DE de (EBl (EB(H(L))) H())
di X-1 [Ew (H) de (Tw)
Tr Tr (x())
ii= d (Ew (H)-)))) 11)) x (Tw)
1=1
Σde d (Ew (H(-)))
Tr(Ew (H(-I)))
Σ Xe (Ew(H (H(-1))
The proof is presented in Appendix G To understand the implications of this result, first observe that by setting Wi 0 and modifying Tw B3 W (8) w Ta 3 w w we can obtain similar bound formulation for vie To this end, as Tw, TB depend on the spectrum of w the ratios (x T: () are highly dependent on 31, $3. Notice that since (H( Ty(Ew (H))
Wi (h(h) in Tw is not scaled by any factor that is inversely dependent on n. it tends to act as a spectrum controlling mechanism and the reduction in within-class variability of features in vig is relatively slow when compared to vig Thus, justifying the empirical behavior that we observed in subplots 6c and 6d in Figure
5 Conclusion
In this work, we studied the feature evolution in GNNs for inductive node classification tasks. Adopting Neural Collapse (NC) perspective, we analyzed both empirically and theoretically the within- and between-class variability of features along the training epochs and along the layers during inference. We showed that a partial decrease in within-class variability (and NC1 metrics) is present in the GNNs' dcepest features and provided theory that indicates that greater collapse is not expected when training GNNs on practical graphs (as it requires strict structural conditions). We also showed depthwise decrease in variability metrics, which resembles the case with plain DNNs. Especially, by leveraging the analogy of feature transformation across layers in GNNs with spectral clustering along projected power iterations, we provided insights into this GNN behavior and distinctions between two GNN architectures.
Interestingly, the structural conditions on graphs for exact collapse, which we rigorously established in this paper, are aligned with those that have been empirically hypothesized to facilitate GNNs learning in [40] (outside the context of NC). As a direction for future research, one may try to use this connection to link NC behavior with the generalization performance of GNNs. Moreover, note that a reduction in NC1 metrics of the deepest features implies not only that the within-class variability decreases but also that the between- class variability is bounded from below. Therefore, methods that are based on promoting NC (c.g., by utilizing the established structural conditions) can potentially mitigate the over-smoothing problem in GNNs. See Appendix A a formal statement on the relation of NC and over-smoothin and additional discussions on the potential usage of graph rewiring strategies for this goal.
Acknowledgments and Disclosure of Funding
The authors would like to thank Jonathan Niles- Weed, Soledad Villar, Teresa Huang, Zhengdao Chen, Lei Chen and the anonymous reviewers for informative discussions and feedback. The authors acknowledge the NYU High Performance Computing services for providing the computing resources to run the experiments reported in this manuscript. V.K and J.B are partially supported by NSF DMS 2134216, NSF CAREER CIF 1845360. NSF IIS 1901091, and the Alfred Sloan Foundation. T. partially supported by ISF grant no. 1940/23.
10

---

References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-633) 6531, 2017.
[2] Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 670-688. IEEE, 2015.
[3] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic block model. IEEE Transactions information theory, (2(1):471-487 2015.
[4] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics, 48(3):1452) 2020.
[5] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. International Conferencee on Learning Representations, 2021.
[6] Adrián Araazz modizzRo Ahmed Begga, Francisco Escolano, and Nuria M Oliver. Diffwire: Inductive graph rewiring via the lovász bound. In Learning on Graphs Conference, pages 15-1. PMLR, 2022.
[7] Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-8. IEEE, 2022.
[8] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in deep networks. arXiv preprint arXiv:2204.092 092977 2022.
(9] Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619. PMLR, 2019.
[10] Ravi Boppana. Figenvalues and graph bisection: An average-case analysis. In 28th Annual Symposium Foundations of Computer Science (sfes 1987), pages 280-285. IEEE, 1987.
[11] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34 (4):18 2017.
[12] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint arXiv: 132.6223, 2013.
[13] Thang Bui, S. Chaudhuri, T. Leighton, and M. Sipser. Graph bisection algorithins with good average case behavior. In 25th Annual Symposium on FnFuddations of Computer Science, 1984., pages 181-192, 1984. doi: 10.
[14] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint 2rXiv:2006.1331 2020.
[15] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 3438 3445, 2020.
[16] Zhengdao Chen, Joan Bruna, and Lisha Li. Supervised community detection with line graph neural networks. In 7th International Conference Learning Representations (ICLR), 2019.
[17] Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 571), 1960.
[18] Cong Fang, Hangfeng He, Qi Long, and Weijie J Su. Exploring deep neural networks via layer-peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118(43), 2021.

---

[19] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. /1 1188, 2020.
[20] Tomer Galanti. A note on the implicit bias towards minimal depth of deep neural networks. arXiv preprint Siti::222.0002233 2022.
[21] Johannes Gasteiger, Stefan Weißenbeerger, and Stephan Günnemann. Diffusion improves graph learning. Advances in neural information processing systems, 32, 2019.
[22] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1272. PMLR, 2017.
[23] Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: dynamically rewired message passing with delay. In International Conference on Machine Learning, pages 12252-12267. PMLR, 2023.
[24] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[25] XY Han, Vardan Papyan, and David L Donoho. Neural collapse under mse loss: Proximity to and dynamics on the central path. arXiv preprint urXiv:2106.02073 2021.
[26] Hangfeng He and Weijie Su. A law of data separation in deep learning. arXiv preprint 2tt::222001170200 2022.
[27] Nicholas Higham and Hyun-Min Kim. Numerical analysis of a quadratic matrix equation. IMA Journal of Numerical Analysis, 20(4):499-519, 2000.
[28] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. Advances in neural information processing systems, 30, 2017.
[29] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-13)) 137, 1983.
[30] Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks. In The Ninth International Conference on Learning Representations (ICLR), 2021.
[31] Wenlong Ji, Yiping Lu, Yiliang Zhang, Zhun Deng, and Weijie J Su. An unconstrained layer-peeled perspective on neural collapse. arXiv preprint arXiv:2110.02700 2021.
[32] Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over) smoothing. arXiv preprint arXiv:2205. 12156, 2022.
[33] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint / 2016.
[34] Vignesh Kothapalli. Neural collapse: A review on modelling principles and generaliza- tion. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL hhtpps / //openreview Copeareeieer.nt//oouritttieeeee 1et.foormmmdd00Xocpp..9pp
[35] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[36] Xue Li and Yuanzhi Cheng. Understanding the message passing in graph neural networks via power iteration clustering. Neural Networks, 140:130-1355 2021.
[37] Jianfeng Lu and Stefan Steinerberger. Neural collapse under cross-entropy loss. Applied and Computational Harmonic Analysis, 2022
12

---

[38] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:1362-1375. 2022.
[39] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. International Conference on Machine Learning, pages 3325-3334, PMLR, 2018.
[40] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations (ICLR), 2022.
[41] Albert W Marshall, Ingram Olkin, and Barry C Amold. Incqualities: theory of majorization and its applications. 1979.
[42] Nikhil Mehta, Lawrence Carin Duke, and Piyush Rai. Stochastie blockmodels meet graph neural networks. In International Conference on Machine Learning, pages 4466-4474, PMLR, 2019.
[43] Dustin G Mixon, Hans Parshall, and Jianzong Pi. Neural collapse with unconstrained features. arXiv preprini arXiv:201 1.1 2020.
[44] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602 4609,4609,000 2019.
[45] Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for binary symmetric block models. arXiv preprint 1wX..v:407.1550 3(5), 2014.
[46] Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):8577-8582 2006.
[47] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv: 1905. 10947, 2019.
[48] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117 (40):24652-24663 2020.
[49] Luana Ruiz, Soledad Villar, et al. Graph neural networks for community detection sparse graphs. arXiv preprint
2022.
[50] Konstantin Rusch, Michael Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. SAM Research Report, 2023, 2023.
[51] Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. Advances in Neural Information Processing Systems, 27, 2014.
[52] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
[53] Kathrin Schacke. On the kronecker product. Master's thesis, University of Waterloo, 2004.
[54] Christos Thrampoulidis, Ganesh R Kini, Vala Vakilian, and Tina Behnia. Imbalance trouble:
Revisiting neural-collapse geometry. arXiv preprint arXiv:2208.0553 2022.
[55] Tom Tirer and Joan Bruna. Extended unconstrained features model for exploring deep neural collapse. In International Conference on Machine Learning, pages 21478-21505. PMLR, 2022.
[56] Tom Tirer, Haoxiang Huang, and Jonathan Wiles-Weed. Perturbation analysis of neural collapse. arXiv preprint arXiv:22 16658, 2022.
[57] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
13

---

[58] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv: 2016.
[59] Charles F Van Loan. The ubiquitous kronecker product. Journal of computational and applied mathematics, 123(1-2):85-100 2000.
[60] Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint
2017.
[61] Stephan Wojtowytsch et al. On the emergence of simplex symmetry in the final and penultimate layers of neural network classifiers. Proceedings of Machine Learning Research, 145:1-21, 2021.
[62] Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non asymptotic analysis of oversmoothing graph neural networks. arXiv preprint arXiv:2212. 10701, 2022.
[63] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22) 24, 2020.
[64] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
[65] Yibo Yang, Liang Xie, Shixiang Chen, Xiangtai Li, Zhouchen Lin, and Dacheng Tao. Do we really need learnable classifier at the end of deep neural network? arXiv preprint vrXiv:2203.0908) 2022.
[66] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33:5812-5822,, 2020.
[67] Se- Young Yun and Alexandre Proutiere. Accurate community detection in the stochastic block model via spectral algorithms. arXiv preprint arXiv: 2014.
[68] Fuzhen Zhang and Qingling Zhang. Eigenvalue inequalities for matrix product. IEEE Transac- lions on Automatic Control, 196661500611000 2006.
[69] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082, 2022.
[70] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI open, 1:57-81, 2020.
[71] Jinxin Zhou, Xiao Li, Tianyu Ding, Chong You, Qing Qu, and Zhihui Zhu. On the optimization landscape of neural collapse under mse loss: Global optimality with unconstrained features. In International Conference Machine Learning, pages 17179-27200 PMLR, 2022.
[72] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
[73] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11168- 1117,, 2021.
[74] Zhihui Zhu, Tianyu Ding, Jinxin Zhou, Xiao Li, Chong You, Jeremias Sulam, and Qing Qu
A geometric analysis of neural collapse with unconstrained features. Advances in Neural Information Processing Systems, 14:29820-29834 2021.
14

---

A Discussion on Oversmoothing and Graph Rewiring
In this appendix, briefly discuss oversmoothing and graph rewiring from neural collapse perspective along with some limitations and scope for future efforts.
A.1
Oversmoothing
Repeated message-passingg operations the node features across the depth of a GNN lead to the "oversmoothing' phenomenon, which leads to poor node classification performance [4 15 47
62
64
We adopt the formal definition of oversmoothing by Rusch et al. [50] to our setup follows:
Definition A.1. (Oversmoothing): For an undirected, connected graph G (V,8) with M = N
and I-th layer hidden features H' |R a function μ Rdxx >R20 called node-similarity measure if it satisfies:
1. 3c E Rdh with H. for all nodes i E O (H) for H Rdxx
2. μ(H + T) S (H) for all H. T
Oversmoothing with respect μ is now defined as the layer-wise exponential convergence of the node-similarity measure to zero, i.e,
"(H') Cie for 1, L with some constants C1, C2 > 0.
Observe from the definition that as the depth / increases, all the node features converge to a single feature vector c. This implies that both Ew (H4-1), E (H(-1) -> 0. In this context, if the penultimate layer features exhibit neural collapse during training, then Ew (H decreases, and (B(4111) is bounded from below. Thus, potentially addressing the oversmoothing problem.
To this end, in the unconstrained features setting, Theorem 3.I indicates that the graph must satisfy a strict structural condition for having exact neural collapse solution minimizer of the empirical risk. Additionally, we obtained conditions on the amount of regularization needed for Σg (HH to increase along the gradient flow in Theorem 3.3 (also see Appendix (F). However, since cannot
expect graphs to satisfy this condition (Theorem 3.2). ), a potential alternative is to explore graph rewiring techniques, which are discussed below.
A.2 Graph Rewiring
Graph rewiring techniques aim to propagate messages between nodes via computational graphs that
23 24 57). One of the popular examples is the Personalized PageRank (PPR) and Heat kernel (HK) based diffusion on graphs by Gasteiger et al. (21). This approach leverages the diffusion matrix facilitate message-passing between nodes many hops apart in the actual graph. However, the graph resulting from the diffusion operations tends to be quite dense. On the other hand, recent works addressing over-squashing in long-range dependent tasks leverage the "curvature" information for rewiring [57]
suitable for the task 7 19 21
In the context of our paper, one can aim to design rewiring technique that can modify the input graph to satisfy condition C. In previous work, Ma et [40] generate synthetic graphs based on CORA by ignoring the original graph and adding edges between nodes to satisfy certain uniform neighborhood distributions. Alternatively, exploring an edge re- re-weighting scheme as proposed by Yan et (64] can also be interesting research direction. From scalability perspective, a neighborhood sampling technique based on condition C can also aid in better representation learning. Additionally, note that condition C is not limited to homophilic graphs and can be extended to heterophilic settings well
38 73,, provided the class/community (refer to the necessity condition in the proof of Theorem [31 in Appendix [D for more details). We believe that further research in this direction shed some light Conjecture 3.1 and improve our understanding of the nature of global minimizers.
of slices of the columns in Å R N are the same for all nodes in
15

---

A.2.1 Measuring neighborhood similarity
A key question that pops up when rewiring graph to achieve condition C is trackable metric for node neighborhoods. The "Cross- Ceass Neighborhood Similarity (CCNS)' metric by Ma et [40] serves good starting point to numerically track the cosine similarity in intra-class neighborhoods and dissimilarity of inter-class neighborhoods of nodes. The definition from Ma et al. [40] is given as:
Definition A.2. Cross-Class Neighborhood Similarity (CCNS): Given a graph 9 and labels y for all
nodes, the CCNS between classes c' is c'c,c')= = [V.liv LieVe.tEve cos(d(i), d(j)) where Ve
indicates the set of nodes in class and d(i) indicates the empirical histogram (over C classes) of node i's neighbors' labels, and the function cos(;;) measures the cosine similarity.
limitation of this metric is that the CCNS between two classes measured as an average of the cosine similarity of node neighborhood histograms while failing to incorporate the variance of these neighborhood similarities. Now, note that when condition C in Theorem 3.I combined with CCNS, we can ensure that the variance of the cosine similarities is zero for any pair of classes e, d [C)). Overall, better metrics based on different similarity meusures and the condition C, along with efficient rewiring techniques to muximizee/inimizz such metrics can be valuable fature effort the community.
B A Brief Note on Exact Recovery of Planted Communities
Phase transitions in recovering the planted communities of the Stochastic Block Model (SBM) graphs have been extensively studied the literature. this context, 'exact recovery' indicates a perfect assignment of nodes to their respective communities/clusters. For the bi-clustering problem (i.e.,
C = 2), one can date back to the works of Bui et al. [13] for min-cut based clustering, and Boppana 10 for spectral clustering based approach (Refer to 2 for historical perspective and additional references on this topic). Along these series of developments to find thresholds in terms of p, g for the exact recovery of communities, the seminal work of Abbe al. K leveraged an information theoretic perspective to identify sharp thresholds in the logarithmic degree settings. The requirement for logarithmic degree can be understood from the following observation. If consider p q. then the SBM is essentially an Erdos-Renyi (ER) random graph model with edge-connection probability Based on the results by Erdös et al. 17 if p clug N then randomly sampled ER graph from ER(N, clng connected with high probability if and only с (see section 2.5 in (T). Thus, in order to achieve exact recovery, one must ensure that the SBM graph is connected along with some over-sampling of edges. In the Symmetric SBM case, when p log N 9 blog N
this condition N
can be represented using the l Vbl > VC inequality (see Theorem 13 and the following remarks in (I]. Finally, observe that from a Neural Collapse perspective, we sample SSBM graphs in this regime ensure that a GNN can achieve zero noss-clasiification error and reach TPT.
16

---

C
Additional neural collapse metrics
In this appendix, we define additional NC metries pertaining NC1-3 for our problem setup.
Variability collapse in neighborhood-aggrreaaatd features HÂ: We track the within- and between-class variability of the "neighborthood-ggrreaatee features matrix HÂ by defining the
covariance matrices Ew
HA
ΣB
HA
as:
c
12
Ew
HA
h
(n n
On
C
EB
HÀ
= Σ
h
lic
DG
6=1
To this end, we define the NC1
HA)
,NC
(HA)
metrics as follows:
Tr Ew
HA
NC,, (A π Tr
Ew
HA Σ
HA
NC,
HÀ
(18)
Tr
Σn
HA
Their primary purpose is to track the within-class variability of neighborhood aggregated features HA relative their between-class variability, both now dependent on the topological structure of graph G. The motivation to track these features arises from the P2 condition in the proof of theorem 3.1 in Appendix B. Essentially, this condition states that the neighborhood aggregated features should collapse to their respective class means for the minimizer to satisfy NC.
SNR for variance collapse: We track the following "Signal-to-Nee ratios pertaining to variability collapse of H and HA:
W. H 2 1,)
SNR(NC)) =
(19)
W, HH H & 1.))
W2 H 1
SNR(NON) W2 (H H & 817)
F
(20)
These SNR metrics provide alternate perspective for us to empirically analyze the desirability of variance collapse. Here H == [
htc E RdxxC and H h N A'
h E Rdxx
the class-mean matrices without and with neighborhood aggregation respectively.
t Convergence of weights to simplex ETF; To track the convergence of the weights W1, W2 to
simplex ETF structure, define NCFT WC. (W2)
NCETP (W1) =
W,W7
1
1 Ic (T--
(6-Jool))
(21)
WiWi |1
VC-1
W
1
Ic 10- 1 -
NCTE (W2)= =
(22)
W2W,
VC-1
Convergence weights to an Orthogonal Frame (OF); track the convergence of the weights W,, W2 to an orthogonal frame structure, we define N NC (W1), (Wa) as:
W.W.
Ic
NC (W1) = W.W
(23)
Vc
F
W Ic
(COF(W.)
= W.W.
(24)
F VC
17

---

Convergence of features to simplex ETF: To track the convergence of the features H, HA to
simplex ETF structure, define N N (HA) as:
ECETF (H)
H H
1
(Io
cl016)
1
(25)
H
VC-1
F
HNTHV H
1
1 Ic (1-Clolo)
NC (HA)
(26)
H HN
VC-
F
where H h1 hg he ha] E Bdxc and H
R4 C are the re-centered class-meat without and with neighborhood aggregation respectively.
Convergence of features to an OF: To track the convergence of the features H, HA to an OF
structure, we define NC2 NC2 (HA) as:
H H
Lc
NC (H)
(27)
VC
F
Ic
NC (HA)=
(28)
vC
F
F
Generic alignment of weights and features: To track the alignment of W with its dual H, we define (W1, H) as:
W1
H
WC,(W H) ==
(29)
|
F
Similarly, to track the alignment of W₂ with its dual HA, we define NC3 (W2, HÂ) as:
N
W2
H
NCs 22, HA)
(30)
W2lle
H
N
F
Alignment of weights and features with respect to simplex ETF: To track the alignment of W and its dual with respect to a simplex ETF, we define NC (W,, H) as:
W
Ic -o- 1 ( VC-1
NCET F (W,, H) =
(31)
W H
Similarly, we track the alignment of W2 and its dual HÂ with respect to a simplex ETF using:
W
(Ic - clo
NOETP (W2, HÂ)
(32)
W&H.
VC-T
Alignment of weights and features with respect to OF: To track the alignment of W, and its dual H with respect to an OF, define NCOF (W,, H) as:
W.H
Ic VC
NC (Wi, H) =
(33)
W H
Similarly, track the alignment of W2 and its dual HÁ with respect an OF using:
H
Ic
NCO (W HÂ)
(34)
W.H
VC
F
18

---

D Proof of Theorem 3.1
In this appendix, we present the proof for Theorem 3.1 by analyzing the sufficiency and necessity conditions of the graph structure given by:
18 ,,,l,, = =...
(8el.as" s,C,),, Ve E [C},
(C)
where the fraction of neighbors of node Ue.i that belong to class d' as Bec!, = [W(e..)
Proof sketch: Our aim is to identify the structural properties of a graph 9 (especially A), such that the features H, which exhibit neural collapse are indeed the minimizers of the risk. First, obtain a lower bound for the risk using Jensen's 's inequality and show that, for a 'collapsed' H to be the minimizer, it is sufficient the graph G satisfies condition C. However, the inequality is applied on a convex function of { (standard basis vectors) that is not strictly convex, and so, this analysis does not imply necessity. Thus, we show the necessity of condition C for 'collapsed" H to be minimizer of the risk by analyzing the optimality conditions of the stationary points. Additional details of the sketch for the 'necessity' argument are also presented.
Sufficiency: We begin by revisiting the risk R. for K 1. For simplicity, drop the superscript F, subscript k; and treat the unconstrained features of the corresponding graph G = (V, 8) as H,
and denote A AD-1 The risk R(W,, H) is now given by:
W.HÂ |
λH
AW 2
R(W,, H) = 2N
+
H
+
(35)
2
=: C(W, H) + Aw
Now, by denoting Ce, E RV as the one-hot vector associated with the index of the feature column he. (among the N feature columns), we lower bound Z(W2,
2, H) as follows
(( 2. H) = 2N
1
W.HÂ
+ I
λи 2
2
C
1
W2HÂe xx( +
A
Heer
2N
1
WrHAe yo 1|
A
+
He
2N
n
2
71
(36)
2
1
A
1
Σ
W HÀ
Ce,t Ye
+
H
e
2N
2
71
1
W
N
ye
+
n
2N
2
Note that Jensen's 's inequality, which we used above, is applied on convex function of e that not strictly convex. Therefore, the lower-bound in equation 336 can be attained despite having different ec,3 is, e.g., when the properties P1 and P2, which are stated below, hold Ve E [C]:
P1: h = ..... he h
P2: hy
.V h
c,n
The first property P1 indicates zero intra-class variability of H. i.e., Ew (H) -> 0. and the second property P2 indicates zero intra-class variability HÁ i.e, Ew (HA) + 0.
Recall condition C:
-) 2(W,, H2) + Awa 12 Thus, each of the Z 2(W,, Hy) terms can be lower-bounded independently, resulting lower-bound for R( (H)K,, itself.
'When K > 1, observe that R 2.
19

---

. C: (sc1,1.'. ,cC,1)
(ScI.n (cC,,) = (Sc1, ,&C)),
where (Sel,-.. Sec) (shared by any node E [rx] in class c) represents any suitable tuple of the ratio of neighbors per class
We just need to show that if C is satisfied then H with both P1 and P2 exists. Equivalently, can assume P1 (which is in the "feasible set" of the optimization) and show that then C implies P2. Indeed, in this case
ENo(vo,)) has + ENeerioloo.) hes h
(37)
(W((o,))
Exaleme ha ENereolean he
Σ d==1
Sce' he
(38)
[W(ve,)] Therefore P2 holds: h =.... h h Accordingly, Cs sufficient for having H that obeys P1 and P2, and thus minimizes the risk.
b.a
Sketch for 'Necessity': The goal of this analysis is to nullify the possibility of having minimizer that exhibits collapse (i.e., H which satisfies P1) for a graph that does not satisfy condition C. We do so by analyzing the optimality conditions of the stationary points satisfying P1, and obtaining conditions on the A matrix. Specifically, we obtain system of linear equations that is shared by all nodes within a class, which in turn leads to condition C. Thus, proving its necessity.
Necessity: Analysing the necessity of condition C is relatively more complicated than the sufficiency case. Nonetheless, we prove the necessity by considering K 1, and by leveraging the idea of tight-convex alternative for R(2,, H) as been used in 55 Formally, assuming dr,-1 2 C, we minimize:
74
for the conventional UFMs 10
1 IZĀ YIE + Az /Z||,
R(Z = 2N
(39)
where \z VAHAW.. Ze CxN and ||- denotes the nuclear norm. Namely, if W2 and H minimize the former, then Z = W,H minimizes the latter, which follows from:
(AY
XW2 ||
λH
VAndw, |Z||- W..H s.t. WaH-Z
min
[H]
(40)
2
We start with providing necessity analysis for the case Az 0. Later, we generalize this analysis to address the case Az > 0.
Analysis for Az = When Az O, observe that ZÄ = [y ly,,..,, ycl 8 1, = Ic X 1, gives us the minimum value for R(Z). Here y. E C represent the one-hot label vectors corresponding to nodes of class C [C]]
Now, note that NC1 implies = - = Z = Z & 1, (where H Rd XC and Z W2H RCXC). Thus, by leveraging this Kronecker structure of Z Z 7 1 Zi.... Zol 1 and Y = [yI...,,yel @ 1, we formulate:
a
a
a
2 2 1T
2c & 1
(41)
ai.
ac.c
ac.c
y1 2
1
YC & 1
where a RR" represents the slice of columns in A corresponding to node E [n] belonging to class e E [C] and forming edges with nodes from class c' E [C]. Additionally, since À is the
Note that the tuple can be different for nodes belonging to different classes, but must be the same for nodes within the same class.
WTee K 1 setting allows us to employ analysis strategies based on a tight convex formulation. which is not applicable for K > settings. Specifically, we cannot generalize the problem stated for Z = W.H to multiple (Hx) ) they share the same W2.
20

---

normalized adjacency matrix, we have scer = 1, 1, a E IR which represents the sum of elements in a c. This gives us:
Sec =
(42)
because A AD-1 is the pegree-normalizer adjacency matrix. Now, multiplying the matrix Z = Z @ 1 with the first column of A gives us:
$11,1 ž + +... +...... &1 =1
(43)
Similarly, due to the block structure of Z, Y. we get for E [n]] and c == 1:
$11,1 2i +... S1 Y1
(44)
where $11.1 +... $1C,2C Y1 itself can be written C linear equations (one for each of the vector components) as formulated below:
21,1
E0,1
$ $11,
= yı
(45)
11.
30,0_
$1C,1
Now, by treating (811,5," ".. 81C.1) the C unknowns which satisfy equation 42 observe that the
solution to this linear system remains the same for all nodes belonging to class c 1. This implies:
$1e(,1
81c Ve' E [C),
(46)
The generalization of this result for all C classes essentially indicates that: (5el , ScC,a), Ve E [C],
(Sat,1,'' ScC,1)
(47)
which exactly represents condition C as stated above.
Analysis for Àz > 0: When H exhibits neural collapse, have the optimality condition for the minimizer of equation 39 based on the sub-differential of the nuclear norm as follows:
ZÂ - Y) A + UZU =
N
(48)
1 1 =. vn
(Z01)A- Ic AT U2 8
N
Where Z E CCC is the matrix of "collapsed" columns of Z. and Uz E RCx V2 E NxC represent the left and right singular vectors of Z. Additionally, since holds "block" structure, we represent V
V @ va 1, where V E RCXC
Matrix Quadratic Form: By considering
- ~Z Z 7 B, we get:
(ZÁ Y)Ā = B,
(49)
as our optimality condition. Analyzing this condition along the same lines as Az = 0 is non-trivial due to the outer product of Ä To address this complication, we leverage the fact that SSBM graphs tend to be regular with high probability N increases. Thus, by assuming that Å is symmetric, we obtain the following matrix quadratic form:
Z YÀ - B = 0.
(50)
As Z is rectangular, we can take the pseudo-inverse and obtain:
π- Z z - 0.
(51)
Since ZiY, Z E RNNN we can treat Ā as the variable matrix and leverage the results on quadratic matrix equations by Higham and Kim [27]. Especially, we leverage theorem 3 in Higham and Kim (27] and employ generalized Schur decomposition technique to obtain a condition on
Á (as shown in the following lemma). This condition on À allows to obtain system of linear equations that are shared by all n nodes within a class (similar to the Az = case). Thus, establishing the necessity of condition C.
21

---

Lemma D.1. Ler 0
I
G
= R 2NNx and the generalized Schur
Z'B Z
0 I
decomposition of F, G be given by:
Q Q'FK=T,
QTGK E,
K 2
1
where Q K are unitary and T, are upper triangular.
2N2N
is x x
K2a
block matrix with blocks of size N x N. Then À satisfies: KI1 = K21-
Proof. The proof is relatively straightforward once observe that Å satisfies:
F
A = G
A.
(52)
A
Now, the condition K K21 is direct consequence of theorem 3 in [27 which leverages the
QR decomposition of A using K as the orthogonal matrix.
Kronecker structure of F: To leverage the relationship between À and K as per Lemma D.1 closer look at is required. Observe that:
Z 0
Z
z
(53)
Z
Z'Y
Z B
Z
0
Z
B
Y
By expanding the Kronecker structures of Z, B,
Y, get:
Z
I
Z I Ic 1 Ziz:
F
A B
0
Zi
1
(54)
0 Z'bc
Z'zc Z Z'ec
& 1
Z
Ziei
Observe that the pseudo-inverse Zi can represented by:
z = (V 1.))
(55)
which also holds a "block" structure (but with respect to rows, instead of columns):
v U
Z
S
(56)
Vn
Vn
NxC
Where V, E RC,Yj
Vj E [C] and vJ is the 8th row of Vz E cxc, With this formulation, matrix-vector product term in F, for instance Z Zib,,ie E [C], can be given as:
U.b
ztb,
=(VzStUBb.)
& Vn
1
(57)
Vn
7 b Nx1
By considering the following notational simplifications:
b, Vzs/
2, VzSLUzZ
(58)
ē; = VzS/
22

---

we can represent F as:
Z Z1 Z e1
@ R
b1
Z bc
Z ec
21 8
1
c
X 1
vn x
8 1
(59)
b1
bc
8
1 ln
é1
1n
è 8 vn l
n
0
0
Z1
zc
ln 1
b1
bc
e1
e1
20x20
Vn
n
Schur decomposition of F: For notational simplicity, let:
1
Vn 8
1
1
(60)
Z
2c
Where: F
b
bc
el
é 2Cx20'
Since G I, the diagonal entries of S must equal the eigenvalues of I. This condition is satisfied
when Q = K. This also simplifies the generalized Schur decomposition for square matrices F, G
to the standard Schur decomposition of F. Now, let the schur decomposition of F E 22Nx2N F 220xxC be given as:
KTK F- KTK
(61)
Here K, T R2Nx2N and T E R2Cx20 To find relation between K, T, K, T, we can leverage the Schur decomposition properties of Kronecker products [53 59 and obtain:
F= 8
1
& 1
(62)
=
1
(63)
Vn
KTK
KTK
(JOJT)
(64)
K
&J
T
o) k &J").
(65)
Where J, O 1axx are unitary and upper triangular respectively, and are the Schur decomposition
factors of vn 1 E Bax.
Linear systems: In matrix form, K = K @ J can be represented as:
K X J
K @ J K
K
(66)
K2 x J
@
2Nx2N
Where K11, K1 K2n, K2 RCx, Now, observe that K₁i K21 (based Lemma D.1 can
be reformulated as:
Kn e 3) Ā
Ky &J).
(67)
Now, per equation 41
leverage the same line of analysis that we followed for the \z 0 case. For notational simplicity, we represent the unitary matrix E jaax in column format as follows:
J
jn],
(68)
where j. E R", [r|] are linearly independent vectors. Now, by multiplying the first row of Ki @J and the first column of A, get:
23

---

d1,1
dn,1
(K1),, [1
Jnl
( Di
jnl
(.21)1.111-
(CCIIut11
aCn,1
This translates to the following linear equation:
01.1 (Ku)), + +... an, (KI)),,,,, +
(69)
(K(n)))t1nn((iieeeeee + ... + acn, (Ku)).c.. (K21)1.J1-
Due to linear independence of vectors ji, [n]. obtain the following equations pertaining the coefficients of j::
a1,1 (K1)1,1 ((C-1)++1111 a (Ku)ic (K21)1.1
a2 (Kn)a, + ..... a (ic-)m42((Kn11. =
an, (Kn1,, + a (K1)), O.
By adding all these equations, we get:
$11, (KI)1I+ sIc. (KI.(, (K21)1.1-
(70)
By following the same approach for the other rows of K1 @ K1, and the first column of A, we get the following system equations for node v1.1:
KK (KI)a
(Kn)io
811.1
(K21)1,1
=
(71)
(Knley
(Kn)a
81C,1
(Kn)an
The same line of analysis can be applied for all the rows Kn @ K,, and the second column of A. get the following system of equations for node v1,2
K Ku1)a
$11.2
(K (Kr))1
=
(72)
(Kn)aa
(Kn)c
SIC.2
(K (21))11
Thus, straightforward that the systems of equations are the same for all nodes belonging to class 1, as the procedure of row and column multiplication remains the same. Thus, the C unknowns these linear systems have the same solution for all nodes belonging to class c 1. is straightforward to extend this to any class [C] and obtain:
($a1,1, ScC.1) _... (S scC,m,, Wc E [C],
(73)
which exactly represents the condition C as per the theorem.
24

---

E Proof of Theorem 3.2
In this appendix, we derive the upper bound on the probability of sampling the desired neighborhood for condition C.
Recall that to satisfy condition C, the requirement w.r.t À is for
(ve.a)) (W(raa) >i.. (N(()..))
(Ne
Vi E [n]]
be the same for a given e E [C]. To this end, we are primarily concerned with the probabilities of edges between nodes ti, 0j 1 S i S S N. Thus, as per preliminaries, the probability matrix P can
be given in block form as:
pl, I1n
Il 1
p1,1
g1.1
P
p1 NxN
Where we are only concerned with the diagonal and upper triangular value Now, for a pair of classes c, c' E [C], we are concemed with the block probability matrix pl,,1, when c = and q1,,1, when e * d' for sampling edges between nodes. Observe that sampling edges within a community based on diagonal block matrix pl, is the same as sampling an Frdos--Reyyi graph with edge probability p. Similarly, sampling edges between communities based on off-diagonal block matrix ql,1, 1, is the same as sampling bipartite graph with edge probability q.
To begin with, consider the set of nodes belonging to class E (C) as 22 (Ve.1,"" Ve,n) Now, satisfy condition C, the fraction of neighbors of nodes Ve, Ve.j. + E [ni that belong to class c' E (C) should be equal, i.e Seet.i
Concentration of pairwise neighbor ratios:
Sec' jj- Formally,
this leads to:
(ers)))) (Ves))))) (W(w,)) [N(ve,))
(N,()e,)) ((vea)
(Wrr)e [W
Without loss of generality, observe that (We,()) is the sum of independent Bernoulli random e'd
1) = 9. This implies that EE (ve,s) = ng. Now, we apply variables Vor VI [n] with F( e'd
the Chernoff bound obtain:
P ([I (Ve,)) - ngl 2 ōnq) S 2c -nng22
Where 8 [0, 1] and 1 0 is a constant. By choosing
In for sufficiently large
fng
r > N C, we get (1)) as = in the class, we get:
Now, by taking a union bound over all the nodes & N
P E [m], lWW (ve,:) - nal 2 8mg) < 2ne On-e((++)lng
Thus, with a probability at-least 1 - 2n-r, we get:
[o na 01))
By applying the same line of argument to (vos)) and assuming a sufficiently large value of n, we get with probability at-least 1 4n-" that:
(ve,))
+
(1o.))l
To this end, we assume that (vc.a)l ) (Mas)),
Ve Ve [ [n] with a high probability for the rest of the analysis. The consequence of this assumption is that all the nodes belonging the same class have the same degree. However, it is not necessary that the graph itself is regular.
Off-diagonal blocks: Without loss of generality, consider the set of nodes belonging to a pair of classes c + d' E [C] as Ω2 {Ve.1, J, , P. (" vn respectively. Now, we need
Due to symmetry. one can equivalently consider the lower triangular values and proceed with sums of columns instead of sums of rows.
25

---

to ensure that every node Ve,i E Se is connected to (say) exactly tce R,, S toe I n. nodes in Ωe If (tee indicates that such event occurs for node Ve,i E Ω with respect Qee, we can formally [n].Vj (1,...,m)
c'' represent it the sum of independent Bernoulli random variables %e. with P( 1) q sum too as follows:
((Eg)()ee) = (110) g (1-9)" fem
tece
Now, are concerned with intersection of events pertaining to all nodes in Qe which ensures that each node has exactly tee' neighbors in Sed By considering the event Eg (tee') N (tce) and leveraging the fact that edges are sampled independently, we obtain:
P P(E (terr) =P (P )
-
n2 8
(1
(od
Now, to account for all possible values of S loo S n, we compute the probability of the union of events E
-t =0 E (teet) as:
n2 g/o0' / (1 9)" Eoo
100
=0c==0
Note that this result can be applied to any distinct pair of classes # c' E [C] based the characteristics of the SSBM. Since we have (2) = 2
C(C-1) combinations of distinct communities,
the probability of occurrence of all the corresponding events is given by:
C-1 IIII
n
P
n
Σ
gf
m)mtted
(74)
(tee
d'=ct1
d'=0+1 foo
Observe that the binomial expansion of (g + 9)ah t is given by:
1= (q -q)" = Σ
tee q' (1 - m)m
(75)
foo==0
where each term, say f(toe)) (1 )( (1 (1-9)" ")" in the sum is strictly less than 1. Additionally,
(
1"
Σ f(toe)
E E
ko, Ko....,, "o
II
(76)
knn
=0
to fo m.kk 20
leat =0
( n
Σ
f(toor)
Σ
II
f(teo )
to =n,05k Annn ko.... knn) fourm0
(77)
This gives us:
Σ f(tcr)""= =1
Σ
II flt
(78)
to "n. An Ko.
kn
terms in Et (tace 1 and the maximum value that ffac' can take is < 1. Thus, each of the f(aae) terms tend to zero after taking the nh power, as n. - oc, leading to Σx_ ) f(te))" 0.
Observe that there
Diagonal blocks:
Handling the exact event probabilities when e c' [C] not so straightforward due to symmetry constraints. To begin with, observe that the sum of n independent Bernoulli random = sum to fer is given by:
variables y. i E [n] E (1.....n) with P(,c.) c.j
(21) ee (1 mlee
(tac)) =
Σ 1=1
toc
=
t0c
26

---

Since P(E (tec)) for > i E [n]] is conditional on (tce), the desired probability for the event (too)) = -i==1 (teo) can be formulated as:
(to(())) Ee (to()
PE ( (tan) n Ee F
n
IP (F21((ac) (F22(loa) (,,())))) (F ...
Obtaining clean expression for the diagonal case is complicated by the fact that the events Ea, (foe), E. (too)) BEen (teo) are not independent. Since we have already shown the off- diagonal case that the P Te inequality P (ta)) < 1 to convey the message of this theorem. Thus, we estimate the probability of the intersection of all events pertaining to c, c' [C] as:
Ne=ct1 E
0 as + we proceed with the simpler
P
IIXI
toel )/re) )
(
-9) )
n
c d'zce
c=l e'
=0
c(C-11
=
Ee
Σ
g (1-9) -1)--))
(79)
c'=c
E.1 Illustration with exhaustive combinations for small graph
A key assumption in our theoretical analysis has been N >> C, which allowed us to assume that nodes belonging the same class have the same degree. However, for intuitive understanding
of condition C, let us consider an extremely simple graph with N = 4, C = 2. This leads to the following adjacency matrix formulation:
712
714
A
712
722
723
721
(80)
7/3
733
Y31
711
724
734
Y41
Where Vhy represents Bernoulli random variable depending on p. We defer assigning values to p. until the end as we are interested the 'realizations' of A that satisfy condition C. Observe that there are only 10 random variables in A due to symmetry (4 on the diagonal and 6 on the apper-triangulat part). Since each can either take a value 0, 1, there are 1024 unique realizations of A. To this end, condition C can be represented as:
711 +
+ 722
and
711 + 712 713 714
7/2
722 723
+ 724
713 + 7/4
7/3
724
and
7/1 + 712 + 713 7/1
712
722 + 7/3 + 724
(81)
T13
7/23
7/4
7/44
and
7/3 + 723 + Yaa 734
714 + 724 + 134 + 7/4
733
734
731 Y44
713 + 723 + 733 734
714 + 724 + 734 + 744
Based simulations for graphs with self-edges, less than 1/10 of the 1024 realizations satisfy this property. few are illustrated below:
0
17
1
0
0
A
A
0
0
0
0
1
1
1
1
0
0
0
1
0
1
1
0
A
A
0
0
1
1
0
1
0
27

---

By considering 0.2.9 0.05, the probability of sampling such A is z 0.046. Interestingly, when p 0.05, q 0.2, the probability increases edges in the graph, i.e., when = 0.4,g = 0.1 and p 0.1,4 q 0.4, we get probability values 0.166, 0.178 respectively. Now, let us consider the case where N = 8, have 36 Bernoulli random variables Tij. i S E (1.... 8). The number of possible values for A turns out to be 23 = 68, 719, 476, 736, for which the brute force approach to validate condition C is efficient. To this end, we follow simple Monte-Carlo approach and draw 000, 000 random graphs from SSBM(N = 8, C 2. = 0.5, 0.2). We observed that only = 800 graphs out of 1, 0000, 000 satisfied condition C, i..,, probability of Rs 0.0008. A few are illustrated below:
0.06. Now, by increasing the density of
In this case, we
0
1
0
1
1
0
07
1
1
0
0
0
0
1
0
1
0
I
0
0
0
1
1
0
0
0
1 0
1
1
0
0
0 1 1
000
I
1
0
0
0
0
0
1
1
A
OODO
O
1
1
0
0 0
0
0
11111110
0
1
O
0
1
O
0
1 0
1
L
O
O
0
0
O
1
1
O
1
1
07
1 T
10011000
1 1
1
111111
OOII
1
0
1
0
0
O
O
1
A
0
O 1 1
=
I
1
0
1
1
0
1
0
1
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
1
Thus, the takeaway is that, even for small-medium scale homophilic and heterophilic SSBM graphs, random graphs that satisfy condition are rarely sampled.
28

---

Proof of Theorem 3.3
In this appendix, we analyse the gradient flow stated (14 and establish the results stated in Theorem 3.3 Our analysis is inspired by the one in [56), but significantly differs from it, as need to overcome the complexity introduced by the graph structure matrix.
Based on the setup of gUFM for GNN sir"", we analyze the risk RF given as follows:
RF (W2, (He
1 K
W2H
|| +
AH
H& 12
Aw
W2ll
2N
2
By taking the derivatives of R² with respect to (W2, H3), we get:
ORJ
W. W,H,A, AH) Aw, W₂
OW2
2
KN
R
W (W
YIĀT
An, H
OH
KN
K
Now, by setting OR
0 we get the closed form representation of W2 in terms of H.
oW;
OR
K
Σ
WWHHA
A + +W, W2 =0
aw2
KN
H. YATH.)
+ Aw, -YAH =0
K Σ
W₂
H.A.A + AWA.N = K k=1
Σ H.
K
A=1
Thus, the ideal value of W; is given by:
W
2
K
1
YA
H
Σ
K
H + Aw, NT
Now, under the assumption that = 1, C= 2, we drop the subscript for Hg, A to get:
W = (YÂTH) H (HÄÄ H + +AW,NI)
(82)
To this end, return risk minimization formulation for single graph with these optimal values as follows:
1
x| Awa 2
Aн 2
R
F
H
WHH
I
H
(83)
2N
F.1 À as a perturbation of EA
Since we are dealing with SSBM graphs, we can formulate À as the perturbed version its expected value. Formally, À = EÄ + E where EÄ E N is the expected normalized adjacency matrix and E E N is the perturbation matrix, IAA can be written in block matrix form as:
1
p1 n q1 1
EA-
(84)
nop + ng
11
NxN
29

---

In
Where the EA has eigenvalues 1, ptg respectively. Thus, we can represent EA using its spectral information follows:
p-4 associated with eigenvectors 1 VN
and c
vN
-ln N
EÅ
+ q
p- 9
cc
(p
+
2
2
c]
Q1
0
[1N
cj'
0
022
(85)
[1N
c]
Va
0r
IN
c]
02
0
vaz
QQ
Where 01 = N,
p-q (p+0)x
and Q =
[I
c
Vai
0
E
R Nx2 is the factor matrix.
va
F.2 Preliminary results
Let recall the definitions of the within- and between-class covariance matrices, Ew (H) and EB (H), for computing the preliminary results:
C n
hhat he) (ho.e he) T
Ew(H) Cn
[n = C
Σ
(he
ha) (he ha)
Here, the class means h. Ve E [C] and the global mean he of H are given as follows:
he Σ bas Ve E [C),
he
h
Cn
F.211 Relating Σg (H), (H)
Since = 2 in our analysis and hig = hh due to balanced communities, note that:
Eg [he hc) (he - -ha)
(h) lio) (hi -ha)) T + (h2 - hi) (h2 ht6) nb6)²)
(hi-ha) h2) (hi -h2)
[igh + hob -hihg hoh
2 m (H) - hibb - h2hh
Thus, we get the following relation between En (H), En (H):
2 B H 4E h h h2h
(86)
Additionally, we can extend this result to the following:
2Σ (H) 45 h + h2h
(2hg h2) h (2hg h h
2hg [ij + h h h
=4E,(H) 2 (H)
30

---

Where Eg ligh.. This gives us:
(b(H) Ec(H) ΣE(H) (H)
(87)
F.2.2 Expanding HAH
Based on the perturbed representation of À
EA + E, we can modify HAH and HA H as:
HÂH
H
EA
H
HEH"
=
[QQ
HQ
НEH
HÂH
H
EA
HE
H
=
EA
+ HE H
[Q
HQ]
HE"H' H
Observe that HQ can be broken down in terms of he, C [C], E [n]] as follows:
Vai
0
HQ = [hi,
h
1
h2 de- [N NN
vaz
2x2
[Vai 2am1
Ei bos
vaz
E>
h - Ei h2
/2n/aahi nva2
hh
h2)
This leads the following expansion of [QQ [QQ]
2n ha T
HQ [Q] = =I2n/aito n/a2 (h))
n\ h h2g
(88)
=nnaaticte + n a2 [h, - h2) (hi hg)
4n + 4n (h hi)) [h, ho
Since ng h. (due to balanced classes). This also implies that:
HQ HQ] = 4n a, ho + 4n"ay hh hG)
(h2 hc) T
(89)
Thus, by taking the average of values in equation
88
89
we get:
HQQ [Q] = 4n an Eg
(H) + 4n
Eg (H) + (p- g)
4n²
(p + N E (H)
N
( + (p 4)
2n
(H)
E HH)
(p 4)
2q
2n
(H)
(p En (H)
Finally, HAH can be simplified to:
HÂH
Σ
(H)
24
+ A En(H)
(90)
(p + 9)
Where A HEH corresponds to the first order perturbation term. Similarly,
29
HÂ H 2n (H)
EB H + +AT
(91)
(p+
31

---

F.2.3 Expanding HAA
H
Expanding T can done along the same lines:
EA
+
E
EA
E
EA
+
EE
+ E
EA
+ EA E
EA
2
=
[IN
c)
a1
0
02
0
[1
c]
[1N
c)
[a
02
0
[1N
c)'
c]
a1
0
Na1
[I
c]
0
a2
Na
VaiN
0
VanN
Q
Q
Vo2N
N
0
Va2N
Based on the formulations above, H
EA
H
can be given by:
Va
VaiN
H
EA
H
HQ
HQ
0
Va2N
0
VagN
2nan /Nng
[2na] VhhG
nagv (hi -h)]
T
(92)
max2 N (hi - ha)
4n of Nhghh n o2N (h, h2))
[hi hg)
4n on Nha 4n og2 (hi ha) (hi ha)
Since hig 4. (due to balanced classes). This also implies that:
EA
H
= a + 4n
hT2 hg)) (h2 - -hh)
(93)
Thus, based on taking the average of values in equation 92
93 we get:
H EA
4n a
H + 4n 2 4m EBH
(p (p- 9)²
8n
Eg
H
N2 + q)2 (
N2
2n
(n(H)
4p4
EE H)
(p+ 2)2
Finally, HAA H can be simplified to:
4pg (p + q)²
HÂÄ H
2n
Σg
(H)
Σ H
2
(94)
Where A2
EET +
EA + EA
is a symmetric matrix corresponding to the
first and second order perturbation terms.
E.2.4
Expanding YÂ
YH
We follow similar line of expansions for Y T H to get:
YÀ
EA H YE H = (I2 8 n
EA
H + YETH'
nph + +ngh2
-(h 1
YETH
np + ng
ngh + +ph
(95)
n
ph + ghg
+
+ Aa
q
ghو + phg
32

---

Where A3 = YE" is the first order perturbation term. Next, observe that:
YH
(I2 & 1 H nH
(96)
F.2.5
Expanding HÁY
T
HÁY H
H
EA E Y Y
EA
E
H
ph + ghg
+ +
phj
T
ghg
+ +
p
وhو + ph2
ptq
[gb]
ph2
n²
phj - qhi
[phi + qhi
qhi + pha
+ As
(p q)3
ghi + +ph
n
(12
h
h2hb))
+ (2pm)
h11bg high )
+ +o
(p q)
n
2(0² +
ΣB (H) + (2pq)
(2 (E)(H)) + As
(p + q)²
4py
2n²
(H)
EB (H)
As
(p+ q)²
(97)
Where AS H (EY YET + EA Y YET + -YY Y
[A HJ and the equality (a) is
based on equation 86
F.3 Trace formulation of risk
Now, note that the risk can be formulated in terms of matrix traces as follows:
R
H
2N Tr (W:HÂ- - -Y) (W;HH-
x)]} +
Awa
Tr (W:
2
(98)
Ah Tr HH
2
Where the term (W:HÂ- x)) (W:Hā- - can be expanded as follows:
(W:Hā- x) (W:HÂ- x)"
WHHHÄ H WT WAY
YA H W + YY
Since W;
HAÄTH H + AW,NI = YA we can multiply W on both sides and get:
w NW Using these simplifications and matrix trace properties, the risk can be modified as:
WH W
1
(WHHÂ x) (W:HÂ- (ITHAAY)- x)
Aw Tr (W>W2T) }
Ah Tr HH
Tr
2N
-
1
Tr
WH tYYT]
Au Tr [HHT} 2
2N
1
Tr
YÀ T HĀÄTH NT
HÂY YYT }
dy Tr (HH")
2N
1
HÄÄT AW,NI -1)
Tr
2N
Tr
YY
Tr [HHT}
2N
2
33

---

Where the covariance matrix formulations for HAÄ H", HÁY H formulate the risk as:
can be leveraged to
RJ
(H) = 2N
Tr
2n²
(H)
(p + q)2 Σn (H))) + م3
4pg
2n
(H)
4pq
D (H) + + + Aw, NI
-1
+
(99)
(p 9)
2
+ Au
(H))
F44
Trace evolution of covariance matrices
Now, analyze the traces of dEw dEn along the gradient flow:
dt
dH, VR H.)).
(100)
dt
Let Okgt represent the derivative of thh entry of hj.. For notational simplicity, we also consider Ew (H), En (H) En En (H), Σr EH)). This leads to:
Ew
Oez1 EB
1
ci (h. - hGa) + (hx ha) cf
2n
Oey1 =
e + [hree
2n
(101)
1
e (he. ha) T + (ba. hs)) e,
O2ji Ew
2n
1
Oez1
Er
(c hz.5ot)
2n
Now, considering
2n
EE
4pg
EBB we formulate R (H) as:
(pta))
-1 - 2N
J A2 Aw, N1] (1T
N NAH (2eThes)
OugIR R
(H)
Tr
Onji
+
4n
Since = 2 in our analysis, the derivative expands into:
Ag
degiR F (H) =
Okyt
+
[ + A2 + Aw,
4
1
Ag
Ouyl (J A2 Aw..NI] ()
Tr
J
dHe had
4
Where the second term can be expanded as:
1
Ag
[ + Ag + (T]
Tr
Okji
1
Ag
Tr
J +
J + A2 +
Aw, NT
Okzt (J + A2) [J A2 Aw, NI 1
4
A J
Tr
[ + Ao + NT]
J + A2 Aws,NIJ Oezi (J + A2)
n
34

---

Now, by expanding Oazi (J) in terms of covariance matrix derivatives, we get:
4pg
Oeyi (J) 0k
ΣB
EB
q)²
= (eiby + +hree)
4pg
el (he [ia)) + -hr - ha) ej
(p q)2
(p=T)) ppp
4pg
+ ((D (P--)) 2
4pq
el
h&
hG
h4 +
(p + 9)² he ej
(p+ q)²
This leads to the following formulation for Okyi R F (H):
Oagi
Tr
A2 + Nw {J)
4
+ Tr
[ + A2 Nw,
[ + A2 + AW,
Okyi (J)
+ A h + Pkjı
ba )
2
Tr
[ + A2 + NW
e,
p -
p +
h +
(p q)2
4pg
A
+ == Tr
[ + A2 + NI
[ + A2 + AWa
2
C₁
p
h +
4pg
he
luoe has + Pkji
p +
(p + q)2
Where Payt represents the remaining trace terms pertaining to the partial derivatives of Az, As:
1
A
Pkit - Tr Tr
[ + Ao + NI.
On.si
1 + -Tr
[J + A2 NI
J +
[ + A2 +
NIJ
Oaye (12)
We now denote M : [ + A2
Aw; NT]
to obtain:
Oes1 R
H
=
1
M M
J +
A
M
p p-
h +
4pg LoG (p+ q)2
22
2
p p
+ Pkyt
(102)
Without loss of generality, since Pkjı E R. we consider Pkjt = Pk. er where P&o E Rd is a random vector which represents the overall perturbation effect of Pxyz- Note that the randomness associated with the E matrix in A2. Ag. We can now represent R. (H) (RR.j, e1), where:
R
1
M
9
hg
4pq
hG
2 harj 2pp.
2
p 1 q
(p + q)²
(103)
M
M
M
J +
M
35

---

Derivative of Eg: By denoting Σz(a, = e Ege, as the (a, -leemmenn of ΣB, we use the above result for O2zIR (H) and the chain rule to compute dEs along the flow 14 as follows:
dEp(a,b)
dh dl
EBa,
Σ
Snsi Eos,. (-OkaiR (H)
dl
kij.
R.jd
Σ
((e,)e))(es hu -ha) + (ea: h& (er) (Ri el)
k.j
1
Σ
(lea:
Rky)
hs hi)) + (Ca: h4 haa) (Rs, on))
2n
kg
Ca
Σ
REj
hhg
ha)
(hg- - -ha) R e6
2n
hid
e
Σ
M
p
2
h&
+
4pg
hg
2A - 2pas
(hs ha) T
eb
4n
+
(p + q)2
Rid
+
1
C
Σ
hh
hc)
M
p (D-1) p
9
2 h +
4pg Too
-22 - 2pk.s
4n
(p + q)2
kj
For further simplification, let's consider the following term:
Σ
p
h +
4pg
hG
he ha]
p
(p+
2)2
kjj
1
Σ
(v 2)² Thp + Apggti
[ hd]
(p
4)²
kg
1
(p 4) 2) hh -pp - " + 4pghah - 4ppliche
(p
2)²
kjj
1
(p 4) 2n EnpgEG 2nEE ((p- - g)² 4pm))
(p 2)
1
[2n(p 2) + 2n(p 2) SnpqEc - 2nEo ((p - q)² - -4p4)
(p + 0)²
p q
EB
Next, we proceed with the simplification of Eks - -n (h+ ha) A (h+ ho)h
Σ
hes (ha To) + (hi hi)))
kjj
(n (hi - hO) + nh2(h2 - ha) T + n(h - ha)h; + n(h2 - ha)h? )
-A (2mhii + 2nhihhn
-T nhi - nhatio nhott - -
-n + 2nhgh - Anhiait = -nn(InEn 4nEa) = -nn En
These results now simplify
a dt
dEB
1
PP- q p x+
(D-9)
e
2n
ME + 2n
Σn - - -Pr (104)
dl.
4n
ppt
36

---

Where PB- 2 Pkd (h. - ha) + (hs he Pk.
Derivative of Ew: By denoting Ew (a, b) ca Ewes the (a, b)-emmeen of Ew,
similar line of analysis as above compute dEw follows:
DEl(a,b) dt
Σ
JR... Ew (a,b)
dhg.j
Ou.s (w,a,) (- --OR,, (H)
dt
Ki
(lea, 0z) (ob, hksj hς) + (Da: ha.j
(e)(er,)))) (Rk.j.
2n
Rd
(leas Rk
(es (es, hE. h&) (ear ha.j h4) (R
Σ
Rk. (br.s - hb)
(hi.j - h3s R Cb
2n
RJ
q
2
4pq hG
(hu. - hx) T
M
h +
- 2A
2p
eb
4n
+ q
(p + 9)²
kjj
+
T
Σ
h
hic)
M
p
h +
4pd
h6 2A - 2pkc
eb
4n
p p
(p q)²
Ai
For further simplification, let's consider the following term:
4pq
Σ
h +
(p + 4)2 he
[hu he
p x
p p-9
2
h + (p + 9)2
4pg
ha
Σ (he.. h+)
p+4
Next, simplify
ber (hr.) hT) Ahe hig follows:
>
(he
hT) (ha.j Ty kg)))
Σ
(ha hac TT
+ bught highte))
kn
-AAB
E
(Ba. he + hh Lahli hgh hahh
Ajj
-n (2nEw + 2nEr 2n5ra = -nnA Ew
dEw Where the last inequality is based the fact that Ex. Ew + ΣB. These results simplify
de as:
dEw 1 oo (-8nAH Ew Pww) c
(105)
dt
4n
Where Pw Ek, Pk.j (ha. h.) T+ (ha.j DR)
Trace of covariance matrices along the flow: Taking the derivative Tr (Ew) gives us dTr (Ew) -22 2>
1
(Pw)
- Tr
dt
4n
(106)
--2AxTT(Enn
Tr
Σ
pk.s (hr.s heo""
kj
37

---

Similarly, the derivative of Tr (EB) gives us:
dTr (En) 22
1
p p-4
Tr
2n
MEB + 22
ΣBM PB
dt
4n
p
p q
= --2AATT(BB) +
1
Tr
2n
p P-9
M 2 >
Dk.j Ph hb)
2n
P
k.j
pp+g (PTT))
2
= --2An(1(BB) + Trr
MEB
TT
Σ
Pkd (hx - ha)) T
hjj
(p= p ((((0-))
2
= -Tr -Th(
M 11
DB
-Tr
Σ k.j
Pk.s (he - -ho)T
n
(107)
Observe that for small enough perturbation matrix E, formally for |E|| < E for sufficiently small E, the sign of <Tw(Ew)) and dTr(Eg) depends on first term each of them, and not on the second dt
dt
term that depends on E. Therefore, since A > 0, we have that Tr (Ew) decreases. It is left to show that Tr EB) increases this regime.
Since the trace of the product of positive definite matrix and a non-zero positive semidefinite matrix
positive by Von-Neumann trace inequality, we aim for conditions that allow
M
2A
ptq
to be positive definite. First, observe that M is symmetrie:
3
M
M M
M
M
[ + A2 + Aw, NT]
4pg
2n
Σ
EB
(p+ 2)
Since EB, EB, D2 and Â3 are symmetric.
4pn Observe that (D+g)²
S 1, because
0 < (p a)²= =1² 2pq + + -4p4 (p+ 1)² -4p4.
Thus,
4pg
2n ΣB
EB
ΣB En} -2n 2n 2 0
(p + q)²
Thus also M >> 0 for small A2. Note also that [J + AW -11 J I. Therefore, for small enough E (and thus small A2, As), have that
A M M M J
M> 0.
Thus, ( (x=E)
2 M 22 positive definite when:
2
p (P-2) ạ
2\ Amin
M
(108)
Here Amin
M
represents the smallest eigenvalue of M.
38

---

G Proof of Theorem 4.1
Let's begin by calculating the expected value and covariance of features X which are obtained after the graph convolution operation based on equation 3
Case c= 1:
We begin by considering the features of a node belonging class 1 as follows:
[ w f w A
(109)
By expanding the H) A, term based on neighbors from all classes, we get:
(Ze,eeA h + Eestena( h2
w (1-1) w
(110)
[((er,)
Now, by taking expectations on both sides with respect to features h (1-1) and structure As we get: w1
EenjEN((ons) h + ENsteen h2
E A x 1,1
11)
E A. 1,
(1-1)
E A
[((11))
1 11-1)
-auul 11-1)
= -W p1
(1(-1) W
a(p+9)
= =(wr0% ptq
w
pel (1(11)
+ ( p+g
wa!l))
pa (1-1)
(111)
Similarly, the covariance E A
(Ix)) -OxEEA Ex, 10
-
(1)
x1,1 - E [an=?]] is based on:
(1-1) + W
(1)) A.c1, E E x
w: ((-t)) w H (1)) A E
(0)
p/1 p (1-1) 11-1)
wi(0 (n - m 1 + w
H ((-1)),,e1, A,e,,
p+ ạ
[w]0) (n 11 11) + we (!)
pMd (1 11-1) + 9142
(1-1)
(1-1))
p+ 9
wi (n(-1)) - -11 11) (n (--1) - 11 1-1 T
W1
pH (1-1)
pH(11)
(1-1)
+ ( (1---) - ii 1 1) A
+ qp22
W
p+
ppd (l-1)
(1-1)
+ w
1) -
A,e1,
que2
(((-1)) - 11 -1( - W!!!
p+g 9
(1 pwd (1-1) + qu1b (1-1)
(1-1)
(1-1) T
w
H A
+
9u12
W
p+q 9
p
(112)
The expectation of the term wi(h)
(n - 14 11) (n /----)
( is given by:
A w:( (1)
(1(--) u1 1-1 (nf--1) 11=---u---) 1) T
w
Ex (nn//") u (-)) (nf u / T WT!'T
(113)
-W (1) Wi((TT
39

---

The expectation of W1" (1)
(h4,") - ui 1 (1 i
pu 1) - 11
W
is given
p-q
by the following:
phl 11-1) ppll11) + qu1
(1-1)
(1 (n1, - -M1 )
H H A1e1,
p+9
PHi (1-1)
(1-1) T
w h h,
(1-1)
+ quu
W
=E
p+q
phl 11-1)
(1-1)
wT(0) ui
1111)
11l A,e,,
+ 911
W
p+q
En
h1
p
PΣ
1 (1-1)
+ + 2
2.5
pll
(1-1) (1-1)
qu1
W
n1p + q)
p -
En
11-1)
p
(1-1)T
w
hi
n(p +
(1-1)
1.j + EØ=
(1-1) 25
9111 (
(1-1) (1-1) WHO
En
h
n(p + ②)
p + q
Since the features are independent draws from their normal distributions, we can simplify the expectation as follows:
pMl (1-1) (1-1) T
(1
(nf..") - 14 1) H(l A,e,,
+ qu2
E A.h
p
-W
P
(I(( + 44 (111) w1 ((-1)T) WanT
x(p+g)
(114)
(n- 1)ppp [1-1] + nquu (1-1)
phd (1((-1)
+ qu2 quul1))) (111)
ww())
(1-1)
W
n(p +
p
w((()
p
(1)
W
n(p +(p+g)
Similarly, the expectation of w
(I ((ll)),,e1,
ppe (1
(nfl.")) 11 (1(-11) w-
pig
given by the following:
pHl (1-1) (1-1)
Ex,
(
((-1)),,11,
que
hn (h( u (111)) w:!!)T
p+ ạ
pdd (1-1)
+ q41 (1-1)
E A
(:(!)) (1-1)) u1 11))
H (1-1 A,e
WTT
(115)
p q
w.())
(1)
1
n(p q)
40

---

Next, the expectation of: "2 can be computed as follows:
H A
pu -tggt 1)
H
pil ll 1) tqpe
W
pt9
p+4
pp (11) 1)
(1-1)
Ex W
H
+ quu
p+
(1-1)
11-1)
H
A
pHi
+qu02
W W
p+
p1l (1-1) (1-1) T
Woll)) (H ).e..)
+ 4u1
A
p+ q
pnl 11-1) qup (111)
pul 1)
11-1)
E Ex
(:(l)
H(-1)) A.er,
+ qu1
(+
p p+g g
p+
Where the second term reduces to O. On expanding the first term, we get:
II!-))A,e,, pll (1
(1-1)
( (1-1)
wilh) (H
+ 9112
E A.h
p+q
-W2 EAn
(1 (
(HLL))
"
W
P14 (1-1)
(1-1)
- -w2
(1(-11)Are..)
+ gquz
p
= -Wi''Bn
p p his
h2g
(1-1)
p PΣ h1-1))
+ E
h2s
(1-1)
W;''
n(p 9)
n(p + ②)
pHl (1-1 + 9122
(1-1)
(1-1) (1-1) TJ
phl
+ q1z
p+0
+ 9
p" Eド bi 1,j + 9² Σラ h2 22.
(1-1) (1-1)T
(1-1) (1-1)T
-W En
W
n2(p - 9) 2
1² Σラ= Ej
(1-1) (11))
q² EE= E
Ej
h2 h2
(1-1) (1-1)T
W.. En
W-(!T
n²(p + 9)
pa Ei Ep=1
(11)T
+ p4 Di=ı =1 h h
(1-1) (1-1)T
( En
2
1.3"
n²(p + q)²
(1-1)
91122 +guu (1-1)
pd (1-1) + quu (1-1)
(
ppl
+
p + 9
p + q
Due to the independence of the features, we can simplify the expectation as follows:
41

---

3x W2 (Hi-1) (nU-I) A,e,,
pP4
(1-1)
+ 9112
(1-1) T
W
p+ ạ
np² 1 + ui / Mi 1 + nnq²
(2 - faz
(1-1) 1
-w
plz
W
n² (p + q)²
p² (22 m)H1 (1-1) pi
(!-
+ qp (n 12 p1
(1-1) (111)
+ w
W2
n² + q)2
pqn² pi 11-1) (1-1) + pqn" 21z pi
(1-1) (1-1)T
f12
W
2 + q)²
p² fi (1-1) 1111) iqdd
pli
(1-1) (1-1)
Mi
+ + 11-1)
ui + q² u2
11-1) (-1)T
(p+g)
(2 [1-1] + / (1-
W
w
n(p + q)²
(116)
Putting these results together, the covariance Ea (1x (x..) - E Ex (1)
')
(1)
is:
(1 [x]. E
Ex,
(1)
x1.3
(1)
Ex EX
w (1) D21 w (()T
W 21(
(1(1-1) W
nlp + 4)
(117)
T1'I| 92 22 (1 1)
p
W (1) Σ (W (1)T w
W
n(p + 4)
n(p + 9)2
To summarize, the means and covariance matrices for (() can be given by:
(w
P
w-(())
((-1 +
{_ q w (1-1)
P1
12
p+q
p+q
50() wi M 11-1 w
(1)T
P w
!!) > (w((T
n(p+g)
(118)
1² (1 (1-1) 1) + 9² 11-1)
p
(1 11 w (1)
w-( (1)T w
n(p +
n(p + q)²
Case == 2:
The analysis presented above can be extended for e in a straightforward fashion to get it2 as follows:
=(1
50
(1) 112 = (w(()) +
P
wi(!))
(11))
9
14 (1-1) E w
wi(())
11
+
ptq
5((1)
wT Σ!
w!(!)
P
W
n(p+g)
(119)
2² (1-))) + 9² = 11-1)
p
W Σ
(1=1) ww (!)
+ w!(!))
W!(lT
n(p+ g)
n(p + q)2
42

---

G.1 Modelling an increase/decrease in between-class variability
Eg(X (n() m (nl)) -m²²) Let 20-11 (un- 142 - [ [1
(1-1) -1 11--1) T
indicate the between-class covariance matrix
for features at layer - 1. Based on the equations 118 119 we analyze Σg (X()) to understand the effect of the convolution layer feature separation. First, observe that:
(Wr(0) 9 wr(
-12 1)
p + 9
+ p- a w2(!!) T
(120)
(41 (1-1)
142 12211 1)
p+ q
(w
+ p - ww(
E EB(H(U
w)(())
+ p - 1 w-(())
p -+ 9
p+q
By taking the trace on both sides, we get:
Tr (En(X
+ p 2-9
(w(()) (n(H1-1) + p- ww(!))
Tr
2
p+q
p+
Tt (H(-)(
(w(())
+ p ---2w w
(w + p- y w: (1)
p p+q
p+
(121)
Where (WT)) + (-
(w10) w E Rd-11xd-1 is a symmetric and positive
p+y
semi-definite matrix. This matrix product formulation allows us to leverage the eigenvalue- based (wr + p+o wx We
trace inequalities [4] (8). Formally, let Ta
(w())
p+g
now leverage Corollary.6 in Zhang and Zhang 688 and get the following inequality based on the cigenvalues Eg (H())))) TB as:
d
Ad (IB(H(-1)) A (TB)
S Tr En
(122)
d
N (Hú-))) A (TB)
i=1
Where Ax)) represents the jth largest eigenvalue a matrix. Additionally, based on the standard trace equality: Tr (E Een' X (E (H (H))))) the increase/decrease in Tr (En (Tx())) ())
with respect to [E ( (H))))) boils down
Ad i+1
H (I)))))
X (Tb)
Tr (X"))
Σ X EB (H())))) x; (TB)
<
TreBB (H))
X (ED(H()))))
Σ > EE (H(-))) ==1
(123)
G.2 Modelling an increase/decrease in within-class variability
Let Ew (H = 1/ - = represent the within-class covariance matrix for features
(I-1) in our balanced class setting. Similar to the previous analysis, leverage the results in
43

---

equations
118 119 to model Ew (X as follows:
Ew (x
21 + Σ
((l))
(T("))
(x + + - w((11T)
2
p
w (1)
Σ ((|1 + ) w
+
n(p + ②)
(124)
1
wi( (ا(ااع) + - wil17
+
2
n(p + ②)
(p² + q2) |ل( + -
w2
w
+ 2
nlp + 902
By taking trace on both sides, we get:
Tr
(Ew(x"))
Ew
(H(
W ( w
Tr
p
Ew H (H W (!) w
n(p + q)
+ Tr
P
Ew H
wo
n(p+ 9)
(p² +99
w-(())
+
Ew
n(p + 4)2
Ew (H)
W w1 wi
p
w w + w w,
"( g)
(p² + (²)
W w7
n(p + q)²
(125)
Let Tw = WT w + m(ptg)
p
W W + w w +
m(ptg]2 W w
(p
Then, observe that Tw E Rd-ixdi- xd:=1 symmetric and positive semi-definite. To this end, the increase/decrease in Tr Ew (x())) with respect to Tr (E((H(-1) boils down to:
di
Ad (H(--))) X (Tw)
Σ A Ew (Ew(H(--)) X; (Tw)
Tr(E (x()) Tr (H(l-))))
A W (H())))
A EEw (H(-1)))
(126)
44

---

Addition Experiments
Infrastructure details: We perform experiments on virtual machine with 8 Intel(R) Xeon(R) Platinum 8268 CPUs, 32GB of RAM, and Quadro RTX 8000 GPU with 32GB of allocated memory. Our Python package "gnn_cctee haop__ollapeee leverages Py ToToo 1.12.1 and Py Terrh-Geeometrr (PyG) 2.1.0 frameworks. For reproducible experiments and consistency with previous research, we extend the SBM generator by Chen et al. [6] and NC metrics by Zhu et al. 77]
H.1 Experiments with GNNs track penultimate layer features
Datasets: We consider a variety of SSBM graph datasets as follows:
D1: C' = 2, N 1000, p 0.025, 9 0.0017, K 1000
D2: C 4, N 1500. 0.072. q = 0.0048, K 1000
GNNs: In our experiments, we empirically track the NC metrics of penultimate layer features during training for both the GNN designs vi 1he The number of layers is set to 32 and the hidden dimension is set to 8 across layers for datasets with C 2 and set 16 for datasets with C 4.
The GNNs are trained for epochs using stochastic gradient descent (SGD) with momentum 0.9, weight decay 5 x 10-4, and learning rate set to 0.004 for D1 and 0.006 for D2.
Optimization:
Observations: Figures 7 g illustrate the training loss, overlap and all the NC metrics that we defined in our setup for v ehe on dataset D1. Note that when C' 2, the re-centering of the 2 class- means by subtracting the global mean, always leads to separation with maximal angle, irrespective of the configuration of the non-centered class-means. Thus, we skip the corresponding AC22 plots for
H, HÁ when = 2. Additionally, we can observe similar trends in NC metrics from Figures 10 after increasing N, C in dataset D2.
Additionally, in all these experiments, notice that NC2. NC3 metrics do not show a significant reduction. In this context, reduction indicates that a simplex equiangular tight-frame (simplex ETF) or an orthogonal frame (OF) the desired configuration for weights and penultimate layer feature (re-centered) Blass-means. This behaviour can linked to the presence of Á in the risk formulation. However, our understanding of the role of A in determining these alignments towards simplex ETF or an OF is still unclear and would be valuable future effort.
0.5
0.6
0.5
0.5
MG,U0 (lgg zoole!
NC:00 mog10 scek)
Intutinnal
+0.5
30.3
-0.5
-1.0
0.2
-1.0
-1.
6.1
-2.0
Ner13000
Mer11000
Mer11000
Ite100000
3.5
2.0
0.1
10
10g
1.0
1000 SCMO
MCC 00 scate)
0,1
(1pp30
0.5
[bg20
3.0
-0.
-03
0.0
-0.6
Nerk3000
Ner00000
Mer06000
Ier150000
Figure 7: GNN oor on D1: C 2, 1000, 0.025, 0.0017, K 1000. Iusstrttio of training loss, training AVC, plots for H, HÂ, SNR((C,) for H, HÀ Frobenius norms of W,, We. H. HA,NG, plots for W,, WC,WC, plots for W, H and W, HA.
45

---

0.6
1.00
0.5
0.99
0.0
0.90
oveehp
-0.5
103
0.97
11.0
-1.
0.1
-2.3
-2.0
0.0
ttr150000
1.2
0.0
(0g10
(Md) [+9)
(og10
Cog
1..
[HQp
0.25
0.00
0.4
Figure 8: GNN ve on D1: C 2, = 1000, 0.025, - 0.0017, K = 1000. Illustration of training loss, training overlap, plots for H, HÂ, SNR(NC,) for HA Frobenius norms of 22, H, HA, NC2 plots for W2, and WC3 plots for W2, HA.
1.0
0.4
1.7
0.5
0.8
0.7
-0.5
0.2
11.0
0.4
-1.
0.3
Aer762000
Mer%6000
Jir 1000000
1.50
0.3
2777
0.30
1.25
61077)
1971
1.5
[M]]
-022
0.15
1.0
0.10
025
0.33
0.00
-0.4
-0.25
0.0
-0.5
ker162000
Nerle3000
ter00000
Figure 9: GNN wo on D2: - N,N 1500, p- 0.072, 0.0048, K 1000. Iusstration of training loss, training overlap, NC, plots for H, HA, SN SNN() for H, HÀ Frobenius norms of
W,, We. H. HA,,C, plots for W,, W,, H. HA, NCg plots for W, H and Wa, HÁ.
46

---

1.00
10
10
(C,00) (lgglD sccall
NG.0eii Ioa20 100000 sueeel
0.5
0.50
0.
0.0
115xl
0.85
-0.
-0.3
0.10
0.80
-1.0
0.05
0.25
-15
-1.5
0.00
-2.0
-2.0
ker%6000
At761000
nte161000
terie1000
3.04
2.0
0.4
Begio scade)
-0.2
NCA (Cp2000000cl sccete)
N5 (ogil0aask
0.2
-0.3
P/8:
0.0
1.00
-04
0.5
-33
MNTTF
-06
((T))
-0.4
0.90
4
10000000
1o014000
Figure 10: GNN wig on D2: C == 4,N 1500, 0.072, 0.0048, K = 1000. Illustration of training loss, training Werlap,.NC, plots for H, HÄ, SNR(CC,) for HA, Frobenius norms of W2, H, HÁ, NC2 plots for W2, H, HA and NC3 plots for W2, HA.
H.2 Experiments with UFM to model penultimate layer behavior
To improve our understanding of the empirical behavior of GNNs and to validate our theoretical results with the gUFM, we prepare datasets based on two strategies:
Case C+: This represents graph that satisfies condition C. Without loss of generality, we leverage the expected degrees of nodes and consider Loce [n * p),c E [C] and tec n q].c * c' [C). Based on our notation, recall that 22,, Pe represents the set of nodes belonging to classescommuuittes) c. E [C]] respectively. To this end, observe that the following conditions should be satisfied
The sub- sub-graph formed by nodes Ω2 should be reguulr,, for all E [C].
2. The bipartite sub-graph formed by Ωz Qgr should be -regulr,,, for all c, e [C).
Case C This represents graph that does not satisfy condition C. Since any random graph sampled from SSBM(N, C, q) satisfies this requirement with a high probability (as per theorem 3.2), simply use this randomly sampled graph. As simple sanity check, one can verify if the sampled graph satisfies the condition C and re-sample.
Especially, we consider the C variants of SSBM graphs with following parameters:
D1: C N 1000, p 0.025, 9 0.0017, K 10
D2: C 4, N 1500, p 0.072, 9 = 0.0048, K
Optimization: The gUFMs are trained using plain gradient descent for 50000 epochs with a learning rate of 0.1 and L2 regularization parameters \w, \w, λH 10 L3
18 illustrate the training loss, overlap and the NC metrics for the gUFM acting on C variants of datasets D1, D2 respectively. Although gUFM is an optimistic mathematical model, we can observe a close resemblance of the values and trends of NC metrics to those of the penultimate layer features of the actual GNNs. This observation is justified any random SSBM graph fails to satisfy condition C with a high probability. To this end, observe from Figures 13 15 that when graphs satisfy condition C, the NC1 metrics tend to reduce drastically (for gUFM designs based on viz vi and C 2, 4). Thus proving our theoretical results. Furthermore,
Observations: Figures 12 and 16
i1
We utilize NetworkX python libraries to generate SSBM graphs that satisfy these conditions. Aw, is not applicable for gUFM based on eez
47

---

observe from Figures 15 simplex ETF and tend converge such configuration. Based on our previous observations for GNN training, we underscore this observation for gUFM and emphasize that rigorous theoretical analysis the role of A in determining the structures of H can be crucial future effort.
that the (re-centered) class means for H, HA tend to align very closely
0-3
NC) (CL (bgi0 scaloo
RCC Reg20 scole)
130.6
-10
-25
-2
20
3
-25
-30
2.5
7.5
5.3
16.0
15.0
25
Ne/1500200
1e-000000
Rer5650000
Ner150000
2.0
1868
0.2
3.00
prbp
--0.4
im
-350
1.0
-.25
0.8
-12
-100
-125
-14
ne/500000
kersb0020
karsssc00
Figure 11: gUFM ve C+ variant of D1: C = 2, 1000, 0.025, 0.0017,
10. Illustration of training loss, training overlap, .V1, plots for H, HÁ, SNR(NC) for H, HÁ. Frobenius norms of W,, W,, H, NC,NC, plots for W,, W2.WCs plots for Wz, H and W., HA.
25
0.8
0.6
10
2
2er1000000
0er1430000
(NR700000
Aar760000
2.0
(M8)
0.25
1.0
1.8
80. wij
-0.2
(1p310 SCMM)
1.6
copp0 scate
C..4
0.0
-0.8
15th
-0.50
-6.8
-0.55
6055
155)
-1.0
-1.00
0.8
1.0
-1.2
0.6
-1.5
0.0
-1.4
10.3
3.0
5.0
3010
0.5
60
75
100050000
1BN350000
3eer650000
Figure 12: gUFM vy on C- variant of D1: C 2, 1000, p 0.025, 0.0017,
10. Illustration of training loss, training overlap, plots for H. HA, SNN((C,) for H. HÁ, Frobenius norms of W, W2, H. AA,, plots for W, W2,WCg, plots for W, H H and W HA.
48

---

NG,HO Topt0 scolel
15
AC-IMM 0ng70
1005
-10
-00
0.4
0.2
Rilel
0.0
2erR50000
0.0
2tr150000
3.0
Ner1450000
0.0
0er7000000
0.25
10
1.8
1993
1946
-0.
0.00
SMN (1gg000000 uecle)
1.6
NSS Cog SC30)
0.25
0077
0.0
-1.30
-1.0
1.25
0.8
0.
255
5.0
10.0
00
2.5
K00
10.0
30
25
5.0
75
301
0.0
255
5.5
75
300
Figure 13: gUFM ve on C+ variant of D1: C = 2, = 1000, 0.025,0- 0.0017, 10.
Illustration of training loss, training overlap, NVc, plots for H. HA, SN,,NC for HÂ, Frobenius norms of W2, H, HÁ, .C₂ plots for W2, and NCa plots for W2, HA.
20.0
17.5
nc (M) (uck))
15.0
12.5
10.0
0.4
0.2
0.0
0.0
5.0
16.3
3.0
5.
0.0
5.0
0.0
2.3
5.0
Iter000000
Ner%50000
Ite3550000
Ner550000
2.0
0.0
0.29
Mh, wi
1.0
-0.2
0.50
2.0
(0gg1
-0.5
(0e:10
0.50
100
66.75
-225
1.0
1.00
11.00
-350
-1.7
-0.75
VA
-3.50
75
0er330000
Ner1630000
Figure 14: gUFM vi C variant of D1: C 2, 1000, 0.025, 0.0017, 10.
Illustration of training loss, training overlap. NC,, plots for H, HÂ, SNNNNN(CC for HÂ Frobenius norms of W2, H. HA,NC, NC, plots for We, and AC2 plots for Wa, HA.
49

---

NCC (M0 (0Sg sCON)
NCCINNI 00g30 SCaIO
10
-10
20
0.2
-25
215
DIS
0.0
0.0
5.0
10.0
0.0
255
100
1000
75
1000
100
tor000000
1e0000000
144
00.41
2.25
1991
1991
1.75
36.4
3.50
kam
1.25
21.00
0.50
0.0
2.5
5.5
10.0
0.0
25
5:5
100
25
53
75
100
00
2.5
5.3
7.5
200
Figure 15: gUFM vog on C+ variant of D2: C = 4,N = 1500, p = 0.072, = 0.0048, K
10. Illustration of training loss, training overlap, .VC, plots for H. HA. SNR(NG) for H, HA
Frobenius norms of W,, 1, W2, H. HA, plots for W1, W2. H. HA, NCc plots for W H and
W2, HA.
80
104
0.8
NC, (M) (1oc10 scalll
10.40%
Mecpee mog scrwe)
40
0.0
3.0
2.5
3.2
7.5
10.0
0.2
23
5.0
150
3.0
25
5.3
7.5
10.5
0.0
23
13
100
Nar950003
4e0100000
15000
3.5
2.25
2.00
(0
1.0
1.75
ICC 1o scael
-0.5
0.5
3.50
0.0
1:25
185.1
1.00
-2.
1R0/46
0.75
0.50
IRCALOO
Ner%63000
Ior950003
000410000
t00000000
Figure 16: gUFM th C- variant of D2: C 4,N 1500, p 0.072, 0.0048,
10. Illustration of training loss, training overlap, NC, plots for H. HA, SNR(NC, for H HA, Frobenius norms of W1, We, H, HÂ, plots for W1, Wz. H. WC,, plots for W,, H and W2. HA.
50

---

0.5
deg
-10
0.4
20
Irdal
0
-20
Kur0550000
Sur550050
Nach50003
Aur 5L50000
2.2
143
NC. rog18 sco
11-00011
3.0
(CT7
26
(aved Fi
18,07.20 ov
1.0
00
5.0 Kor550000
10.0
0.0
2.5
X:1
7.5
10.0
0.0
25
50
3.5
160
0.0
25
K.6
155
160
Mer1650000
RB7550002
Figure 17: gUFM ve
C+ variant of D2: C = 4, p 0.072, 0.0048, K 10.
Illustration of training loss, training overlap, .VC, plots for H. HA, SN SNN(C for HA, Frobenius norms of W2, H, HA, plots for W2, H, HÂ, and NCa plots for W2, HA.
1.0
Intal Ietutp/orr (iG.Ait
50
0.0
ACG00A legh0 scale)
10
0.2
110
3.0
130
2.5
7.5
0.0
30
10.0
23
7.5
200
ner3430900
1ar*33000
Rar350000
Ner%50000
3.0
1939
0.8
2.0
260M o1
06:M
0.0
-3.0
-0.5
0.4
0og
-3.5
-1.0
0.2
3.4
0.0
DCC:
-0.2
-0.4
0.8
-3.0
199
-25
herl500000
1te 1Ee0500000
Per250000
tee1550000
Figure 18: gUFM vo on C- variant of D2: C 4,N 1500, 0.072, 0.0048, K 10. Illustration training loss, training overlap, plots for H, HÂ, SN SNN((CC) for HÁ Frobenius norms of W2, H. HÂ,NC, plots for W2, H, HA,, and NCa plots for W2, HA.
H.3 Experiments with GNNs and Spectral Methods
The main focus of this section is to emphasize the differences between power iterations-based spectral methods and GNNs. To this end, we consider the following datasets and GNNs as follows:
D1: C' = N = 1000, 0.025, g = 0.0017, K (train) 1000, K (test) 100
D2: C 2, N 1000, 0.0017, q 0.025, K(train) 1000, K K(test) 100
GNNs: In our experiments, we empirically track the NC metrics of penultimate layer features during training for both the GNN designs v/ v/.5" The number of layers varied based on 64, 128 and the hidden dimension is set to 8 across layers.
51

---

The number of projected power-iteration are varied based on L = 64, 128 for a fair comparison with GNNs.
Spectral methods:
Optimization: The GNNs are trained for 8 epochs using stochastic gradient descent (SGD) with learning rate of 0.004, momentum 0.9 and weight decay of 5 x 10
Observations: For the dataset DI with homophilic graphs, we first plot the training metrics for GNNs eig. vo with = 64 in Figures 19 20 respectively and ensure that they reach TPT. Now, from Figures 21 22 observe that the ratios (wwxxxx))
TT(EB(x()) (T(() (w((11))) out the power iterations for spectral methods, whereas, the GNNs behave differently as Tr(EB (XT)) (H()))), Tr(Ew Tr(Ew(X()) (/TT) (H(-)))) tend to decrease across depth.
(w( tend to be constant through-
We make similar observations for GNNs vh. vg with L = -28 in Figures 23 24 25 26 and note that the behaviour is the same L 32 case illustrated in the main text. However, when considering the dataset D2 with heterophilic graphs, even though the GNNs reach TPT during training (Figures 27 28 30 ), the evolution ratios (H Tr(E w //Trr(>>>> HH
tends to differ especially for the GNN vi when 64 (Figures 31 and L 128 (Figures
Thus, highlighting the empirical role of depth in GNN design which requires further investigations future efforts.
0.5
0.5
0.4
21.0
0.2
0.9
11.0
-15
7dal
-1.5
Xt:161000
Ncr441000
0e/361000
Ate151000
2.0
0.2
0.2
3x30))
0.2
2.0
[M3
10.2
14)
Cog
00.3
-02
-0.3
R,
(07
-0.3
-0.4
(R/LLOP)
(RUA)
100761000
300960000
08/61000
Figure 19: GNN ve with L 64 on DI: C = 2, 1000, 0.025, 0.0017, K
1000. Illustration of training loss, training overlap, NNC; plots for H, H, SNN(NC, for H. HÁ. Frobenius norms of W1, W2, H. HÁ, plots for W1, W2, plots for W1, H and W.. HA.
52

---

1.00
0.2
6,5
0.99
Reg:0
0.3
0.0
0.20
0.25
10.3
PCUMA (egtt0
-0.5
0:35
1.3
-..
0.30
-1.5
-1.
0.09
-2.7
-2.0
0.00
2
2.0
0.2
0.0
1.0
-0.2
DMC (lgg scolet
-0.5
(0g10
1.0
(Md)
10.4
HHlp
0.6
0.5
M: (377
100760000
Figure 20: GNN vi with L = 64 on DI: = 2, N = 1000, 0.025, 0.0017, K = 1000. Illustration of training loss, training overlap, .VC, plots for H, HA, SNN(NC,) for HA Frobenius norms of W2, H. HA, NC2 plots for W2, and NCa plots for W2, HA.
MCJUN meg10 sccl)
Intlud VC: Inteaiintallo Os Tribultiibal remie
NC Hff Fagtt
Ii Op
TrSButt Op
Triaa)
Frtpa normakie
Ti nermaloe
Tolla:: normalie
Pors teptiroooo
Trial
Tock 1001 wollt
Triial normalze
Tr1p):
In5al
Tr nomaliee
layer
Macer
(a) Normalized Laplacian
(b) Bethe Hessian
(c) GNN the
(d) GNN Wh
Figure 21: NC, NC, (H) metrics (top) and traces of covariance matrices (bottom) across 64 projected power iterations for NL and BH (a.b), and across 64 layers for GNNs vor and ei (c.d) on DI: C = 2, N 1000, p = 0.025, g = 0.0017, K(test) = 100.
7.
Thopreee Prgi7 woRe 5
3110
3..0
2.00
2.50
2.50
25
(a) Normalized Laplacian
(b) Bethe Hessian
(c) GNN di
(d) GNN Wi
Figure 22: Ratio of traces of covariance matrices across 64 projected power iterations for NL and BH (a,b), and across 64 layers for GNNs wir and wh (c,d) on DI: C 2, N 1000, p = 0.025, 9 = 0.0017, K (test) = 100.
53

---

0.6
0.5
0.5
0.9
WC,00 u5g scaee
0.0
ACcov Bog30 stees
Intutinnal
0.0
-03
-0.5
30.3
-1.0
-1.0
1.5
0.7
-3.0
-1.5
0.1
0.0
-3.0%
ter141000
Mers1000
tork6000
iter51000
1.25
0,2
Hogg0000000 sc3e)
0.75
Begto scoles
NC 4S/oog00
-0.2
NS Cop10 scete))
0.1
194
0.25
-0.4
0.00
0P..11
0.0
Adt
0.50
-0.5
-0.8
001
Itr11000
Figure 23: GNN vi with 128 on DI: N, = 1000, p = 0.025, = 0.0017,
1000. Illustration of training loss, training overlap, NN1, plots for H, HA, SN for H, HA. Frobenius norms of W 1, W2, H, NC, plots for W W2. plots for W H and W HA.
0.30
0.5
0.5
102
0.25
0.59
0.2
0.0
10049-00 Ovl
00.5
30 30.35
+1.0
(MI
0.10
1.5
0.96
0.05
-2.3
-2.0
0.55
100%.1000
100%
14751000
1t07h1000
3.2
K9/04
2.0
0.3
0.0
2.5
11gg 233
-0.5
0..2
3.0
1.0
119)
(og70
(94)
0.3
-2.0
0.0
-0.5
1R..4
09,44 CO
Xer%6100
Ber%
Figure 24: GNN v-5" with 128 on DI: C N 1000, 0.025, = 0.0017, ((trai)) 1000. Illustration of training loss, training overlap, NCC, plots for H, HA, SN SNNC) for HA, Frobenius norms of W2. H. HÁ, plots for W2. and WC, plots for W2, HA.
54

---

Petappli:- OF intaliinaais Trdggiiitall rearell
TIEa OO
mnbuetrta tha costt
TiDustiiaal can
Inte42'VC. cpp
Iitadt UC normaliz
Sayer
PiTTal Do
Trtkl Op
Tridgl navee
0p t0iall samslice
Irtal: tommalos
100
300 116
(a) Normalized Laplacian
(b) Bethe Hessian
(c) GNN de
(d) GNN d
Figure 25: :NC, NH), (H) metrics (top) and traces of covariance matrices (bottom) across 128 projected power iterations for NI. and BH (a.b), and across 128 layers for GNNs v/ and wh (c,d)
on D1: C 2, N 1000, p = 0.025, g = 0.0017, K(test) 100.
12.5
1y 12
102
122
(a) Normalized Laplacian
(b) Bethe Hessian
(c) GNN dh
(d) GNN 1
Figure 26: Ratio of traces of covariance matrices across 128 projected power iterations for NL and BH (a.b), and across 128 layers for GNNs vir and v. (c.d) on D1: C = N, = 1000, = 0.025, 0.0017, K (test)) = 100.
3.0
0.5
0.5
0.5
MCJ00 PEL001oog HlggD zcale!
NC:IA reg10 scat0)
0.0
ovettp
30
0.8
-1.0
0.2
-1.0
0.1
-1.5
-2.0
0.0
Ner14000
Ner11000
Mer161000
Iter140000
1.25
2.0
10,
0,2
10
0.0
(0g.0l000s000 Sc300)
0.75
NS (og10:00000 (0460)
AS Cop10 scate)
0.1
0.50
[bg10
1.0
-0.1
0.0
-02
0.1
0.00
1.0
-0.3
0.25
-0.2
-0.4
-0.3
NerN3000
Mer00000
ter00000
Ier350000
Figure 27: GNN 1/ with L 64 on D2: C 2, 1000, 0.0017, 0.025, K
1000. Illustration of training loss, training overlap, plots for for H, SNR(CC,) for H, HÀ Frobenius norms of W, 1, W2, H, AC,, plots for W, W2, plots for W, H. and W,, HA.
55

---

1.00
0.5
0.90
0.3
wed
0,5
0.96
Reg:0
0.3
0.0
3
000500
0.94
-0.3
-0.5
0.92
1.3
0.0
1.1
0.2
EogT0 scoeet
(Md)
0.0
[+f)
[Hlp
-0.4
-2.0
0.
M: (377
-2.0
0.4
-0.8
Figure 28: GNN vi with I, = 64 on D2: C 2, = 1000, 0.0017, = 0.025, K 1000 Illustration of training loss, training overlap, .NC, plots for H. HA, SNN(CCC) for HA, Frobenius norms of W2, H, HÅ, .C₂ plots for W2. and NCa plots for W2, HA.
0.6
Tillo
0.95
0.5
AC cod nog18 scaa)
0.50
MGqi0 logt
-c.5
-0.
30.3
0.80
-1.0
-1.0
0.7
0.75
-1.
6.1
0.50
-2.0
-2.0
Ats161000
ter13000
Ite1551000
NerA0000
1.0
2.0
0.0
0.25
100.0
10
0.20
(0g 53301
-C.4
0.15
0.4
1 11g10
1.0
(eg00
legg0
0.30
0.2
0.5
0.0
-3.0
0:30
(m))
-1.4
ib0660000
ter33000
har350000
Nork2000
Figure 29; GNN vi with L 128 on D2: C 2 1000, p 0.0017, = 0.025, K
1000. Illustration of training loss, training overlap, NC,, plots for HÁ, SNR(AC,) for H, HÁ, Frobenius norms of W, W2, H. AC,, plots for W, W,. plots for W, H. and W HA.
W
56

---

0.30
1.00
100
Irial
0.5
0.5
Mita
0.5
(CUUA Bog thgl0 sccia)
00
MCI PELNN Ibatt scell)
0.0
+0.5
3
0.99
=1.0
-10
0.97
8.05
0.90
0.00
ter%1000
teric000
MC Coo10 scald
-02
MCC C0030 scoted
+0.5
[nd- PSg
3.8
0.75
-1.
-0.9
025
0.00
0.5
-2.5
Figure 30: GNN ve with L = 128 on D2: C 2, = 1000. 0.0017, 0.025, 1 Illustration of training loss, training overlap, plots for H. HA, SNN(CCC) for HA, Frobenius norms of W2, H, HA, .C₂ plots for W2, and NCa plots for W2, HA.
PrEEu Op
Thtaty Op
THEE
NCCUP9 Uogi0 sCaR))
TTEE Op
Frilalg normalze
RCAi Deg10 scar)
0.5
TiTal Op
Tilaaa VC normatiee
0.0
Prttuiistaa normalzze
Triza namalie
-1.5
-2.0
Sayer
Sayer
32
Trttal Op
Trita) non
Triaa) nomaliee
Track Eogi0 scale)
Triba) Up
sacce 1wg.g sccie
Trtaa) non-in
Trita) nommaize
20
Mayer 18x
(a) GNN wi
GNN 1i
Figure 31: (H)
(H) NC (H) metrics (top) and traces of covariance matrices (bottom) across 64
layers for vir and di (a.b) on D2: C = 2, N = 1000, 0.0017, 9 = 0.025, K K(test) = 100.
F'
57

---

Tince reto Dogge schee
Prop
Trace loggó
Trig urreg Tri2g urr12
(a) GNN vhe
(b) GNN 1o
Figure 32: Ratio of traces of covariance matrices across 64 layers for GNNs wh and v/ (a.b) on
D2: = 2, N 1000, p = 0.0017, = 0.025, K (lest)) 100.
TIC Op
Tat Op
Triaat
Trilell non-ss
ICC 0ogl0 scale)
ThEaaliiiall Op
Tritat ICC
1oog0ssoo scoee
Trilady VC
TrilaliFrtal-- Op
TriZalliiaal nos-in
TrclaliFrta)) ner-in
Vittaalitall nomallee
MC 10 togio
Trclaiiiktal normalze
20
60
100
120
40
03
100
120
TriTal
THtal
Taace (egg0 sca8e)
Taxe (holo scta)
75
7r1lal: normalize
Layer 1ds
layer
(a) GNN th
GNN the
Figure 33: (H), (H) metrics (top) and traces of covariance matrices (bottom) across 128
layers for v/ and wig (a.b) on D2: C = N = 1000, p = 0.0017, = 0.025, K (test) = 100.
14
Trag" -
Trace ligg scaee
Thoce rato Dop10 scain)
50.0
2.5
3.0
layer 150
(a) GNN 16
(b) GNN 1/
Figure 34: Ratio of traces of covariance matrices across 128 layers for GNNs vig and v/ (a,b) on
D2: C = 2, N = 1000, p = 0.0017, 0.025, K K(lest) = 100.
58


Reviews:
[{"review_id": "QjfTdqL4qF", "reviewer": "Reviewer_4uoY", "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\n\nThis 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.\n\n\n1. Empirical study showing that some decrease in within class variablility, but not to the same extent as in vanilla DNN\n\n2. Graph based UFM. Prove that with optimistic model, need strict structural condition to get full NC.\n\n3. Study gradient dynamics of graph-UFM that partially explains theoretical reaonsing for partial NC\n\n4. Compare NC1 metrics of GNNs vs spectral clustering\n\nOverall, 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.\n\nI 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.)\n\nIf these issues are addressed, I would likely be in favor of acceptance.", "questions": "\n\\subsection{Questions}\n1. 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?\n\n2. Why is there a $y_k$ in (1), but $y_k(V_k)$ in (2)? This seems inconsistent. \n\n3. 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?\n\n4. For the sake of self-containedness, could you please briefly explain the instance-normalizaiton?\n\n5. 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\n\n6. 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?\n\n7. 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)\n\n8. 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? \n\n9. 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?$\n\n10. 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.)\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 4, "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\n\nIn the proof of Theorem 3.1, it is not clear what $y_c$ is. This needs to be made more clear.\n\nIn 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.\n\nI 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.)\n\nThe 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$.\n\n(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.\n\nMinor Issues:\n\nIn 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)$\n\nThe capitlizatin is off in some of the refreeneds, in Euclidean shoudl be capitalized in ref [7]. Please fix.\n\nLine 344 in the proof of Theorem 3.1: ``Theorem 3.1\" should be capitlalized. \n\nIt 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) \n\nLine 419 in the supplement. I think you should remove the word essentially, right? The number of neigbors IS a binomial RV.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General note:** We sincerely thank **Reviewer 4uoY** for the detailed feedback. Due to character limits, please find the responses to all the key questions below. All the minor issues will be fixed in the revision.\n\n**Q: I don't understand the inequality of the form $P(A|B) < P(A)$ given in 444. I also don't think you need it. Could you please revise or clarify?...**\n\n**A:** **We agree** with the reviewer that this inequality is not needed for the analysis of the off-diagonal block (ln 444). We will remove the statement corresponding to this inequality to avoid confusion.\n\n**Q: The bound obtained in Theorem 3.2 is hard to parse and it is not obvious to me whether or not this quantity tends to zero...**\n\n**A:** The term corresponding to the \"off-diagonal blocks\" in Theorem 3.2 is given by:\n \\begin{align}\n     \\left( \\sum_{t=0}^n \\bigg[{n \\choose t}q^{t}(1-q)^{n - t}\\bigg]^n\\right)^{\\frac{C(C-1)}{2}} \n \\end{align}\nHere, observe that the binomial expansion of $(q + 1-q)^n$ is given by:\n \\begin{align}\n     1 = (q + 1-q)^n = \\sum_{t=0}^n {n \\choose t}q^{t}(1-q)^{n - t},\n \\end{align} \n where each term, say $f(t) = {n \\choose t}q^{t}(1-q)^{n - t}$ in the sum is strictly less than 1. Also, note that:\n \\begin{align}\n     1^n = \\left(\\sum_{t=0}^n f(t) \\right)^n \n      &= \\sum_{t=0}^n f(t)^n + \\sum_{k_0+ \\cdots + k_n = n, 0 \\le k_0, \\cdots, k_n < n} {n \\choose k_0,\\cdots,k_n} \\prod_{t=0}^n f(t)^{k_t}.\n \\end{align} This gives us:\n \\begin{align}\n     \\sum_{t=0}^n f(t)^n = 1 - \\sum_{k_0+ \\cdots + k_n = n, 0 \\le k_0, \\cdots, k_n < n} {n \\choose k_0,\\cdots,k_n} \\prod_{t=0}^n f(t)^{k_t}.\n \\end{align}\n As $n$ increases, it is true that the terms and the (number of terms) change in LHS but recall that $\\sum_{t=0}^n f(t) = 1$. As the maximum value that $f(t)$ can take is $<1$, it tends to zero after taking the $n^{th}$ power, as $n$ grows larger. Thus $\\mathbb{P}(\\mathcal{G} \\text{ obeys \\textbf{C}} )$ is negligible as $N >> C$.\n\n**Q: (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...**\n\n**A:** Thanks for pointing it out. To recall, the purpose of theorem 3.2 is to show that SSBM graphs rarely satisfy condition C. After exploring the insightful directions provided by the reviewer, we feel that just considering the off-diagonal blocks **(suggestion (ii) by reviewer)** should be sufficient to convey the idea in a simple manner, as we have shown (in the above response) that even this probability tends to 0. \n\n**(Revised) Theorem 3.2:** Let $\\mathcal{G}=(\\mathcal{V}, \\mathcal{E})$ be drawn from SSBM$(N, C, p, q)$. For $N >> C$, we have\n\\begin{align}\n\\mathbb{P}\\left(\\mathcal{G} \\text{ obeys \\textbf{C}}  \\right) < \\left( \\sum_{t=0}^n \\bigg[{n \\choose t}q^{t}(1-q)^{n - t}\\bigg]^n\\right)^{\\frac{C(C-1)}{2}}.\n\\end{align} which converges to $0$ for large $n$ as shown above. Numerically, when $C=2, N = 1000, q=0.0017$, we get $\\mathbb{P}(\\mathcal{G} \\text{ obeys \\textbf{C}} ) < 2.18 \\times 10^{-188}$, which is practically zero.\n\n**A note on suggestion (iii):** We found that this line of analysis is quite non-trivial. Especially, formalizing the \"almost independent\" notion of the events: $\\{ E_{c,1}^c (t), E_{c,2}^c (t), \\cdots, E_{c,n}^c (t)\\}$ is not well justified as $\\prod_{i=1}^n P(E_{c,i}^c(t)) = \\left[ {n \\choose t}p^t(1-p)^{n-t} \\right]^n$ tends to smaller values [1] for any $t$ as $n$ increases (shown in the above response).\n\n**Regularity of erdos-renyi graphs:** We explored the literature on the existence of regular graphs on $n$ nodes and found that even asymptotic results for $p \\propto \\frac{\\log N}{N}$ settings seem to be not well explored [2]. Also, the existing results for degree $O(\\sqrt{n}), c/n$ etc are extremely non-trivial for the message we want to convey in this theorem.\n\n[1] Dykstra, R. L., et.al \"Events which are almost independent.\" The Annals of Statistics 1.4 (1973)\n\n[2] Wormald, Nicholas C. \"Models of random regular graphs.\"\n\n**Q: It would make sense to add self-loops, otherwise, nodes don't communicate with themselves at all...?**\n\n**A:** We have not used $\\hat{A} = (A + I)(D + I)^{-1}$ explicitly as the nodes of the sampled SSBM graphs are allowed to have self-edges. We will explicitly mention this in the revision to avoid confusion.\n\n**Q: Importance of balanced communities and practical relevance.**\n\n**A:** This assumption is critical as we extensively leverage the properties of Kronecker products in most of our proofs. In the case of GNNs, since we show partial collapse even in the ideal scenario of balanced communities, specific \"rewiring\" mechanisms for the computational graph might be needed in practical settings (for ex: to satisfy condition C with our GNN design) to aid the optimizers. Additionally, a promising real-world application is a mitigation of over-smoothing by such rewiring mechanisms as NC1 indicates a maximal separation between class-mean features.\n\n**Q: Role of varying hidden dimensions.**\n\n**A:** Scenario 1: first 16 layers: dim = 8 + next 16 layers: dim = 16, Scenario 2:  first 16 layers: dim = 8 + next 16 layers: dim=4. Final layer dim = 2 for both scenarios. We observed that both the scenarios exhibited partial NC but the \"collapse\" in scenario 2 was relatively higher (i.e. relatively lower NC1 values).\n\n**Q: Intuition about the limit in Theorem 3.3 and role of $\\alpha$.**\n\n**A:** Intuitively, one can think of this limit as a state at which the $\\Sigma_W$ has reduced (sufficiently) and $\\Sigma_B$ has increased (sufficiently) as the exact collapse is not the desired state for $A$ that is randomly sampled from SSBM. When $E \\to 0$, then the resulting $\\mathbb{E}A$ theoretically satisfies condition C and the gradient flow will tend towards the NC1 state, which indicates that $\\widetilde{NC}_1$ will tend to 0. Finally, $\\alpha$ can be thought of as the regularization needed for the trace of between-class covariance to increase along the flow.\n"}, {"review_id": "pjogrol23D", "reviewer": "Reviewer_t9NA", "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.", "questions": "1. Major:\n    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.\n    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.\n    3. The experiments are performed only on the graphs simulated by the SSBM assumptions.\n2. Minor:\n    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.\n    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.", "limitations": "Limitations are not included by the authors. As I presented questions above, my concerns are mainly about the practical significance of this paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is interesting to study the feature evolution with GNNs and especially the correlation between the topological information.\n2. 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.\n2. Most concerns are raised about the practical value of this study, which lies in two aspects:\n    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.\n    2. data model: SSBM is a good model to study the topological features.\n\nMy 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General note:** We would like to thank **Reviewer t9NA** for the constructive feedback. The 2 minor issues will be fixed in the revision.\n\n**The importance of neural collapse (NC).** In standard DNN settings (e.g., image classification on MNIST), the classifiers tend to exhibit NC once they perfectly classify the training data (i,e during TPT). NC includes both: \"reduction\" in the features’ within-class variability\nand \"increase\" (or stabilization) in the between-class variability, such that the features form certain low-dimensional geometric structures. This phenomenon has allowed the community to understand the benign effects of overparameterization and the benefits of training beyond the \"zero-classification-error\" stage for DNNs (e.g., cases with better test accuracy and improved adversarial robustness [1]). Importantly, we demonstrate that the case with GNNs is not similar to any previous work on NC as the structural constraints of graphs tend to hinder the ability of NC. Also, since the over-smoothing problem is common in deep GNNs, NC shows potential to address such key issues and have a promising impact.\n\n**The data and network models.** To explore the level of NC in GNNs in a principled fashion, we start with SSBM graphs, as their properties are well-suited for theoretical GNN analysis [2]. The gUFM model presented in this paper is much more complicated than any theoretical model in previous publications on NC [4] as we retain the graph topology in the analysis. Importantly, even for our “optimistic\" model, we show that the desired configuration of the penultimate layer features (in terms of optimization optimality) does not exhibit exact NC unless the graph satisfies a strict structural condition. This immediately implies an inherent difference between practical GNNs and DNNs. Also, note that it seems very difficult to derive the exact training dynamics in GNNs without trivial assumptions on the structure. Thus, we leverage the literature on SSBM graphs and present a rigorous gradient flow analysis to explain the partial collapse observed in our experiments. This analysis is already a major step beyond analyzing only the minimizers of the model.\n\n**Practical significance:**\n\n1. Observe that attaining NC solves the over-smoothing problem as NC represents the maximal separation between feature class means in addition to zero within-class feature variability.\n\n2. Recently, Ma et,al [3] showed that homophily might not be necessary for good GNN performance on node classification tasks. By leveraging Theorem 3.1 from our work, we can observe that the structural condition required for collapsed minimizers addresses both the homophilic and heterophilic graphs. Thus, providing insights into Ma's surprising empirical results.\n\n3. Our work can potentially shed light on an ideal \"graph-rewiring\" strategy as we know the nature of the minimizers when condition C is satisfied by the computational graph.\n\n**Q: Regarding feature evolution and pre-convergence phases of training.**\n\n**A:**  To address the reviewer's comment, we would like to emphasize that the contribution of our analysis is to understand why GNNs are unable to reach the convergence (TPT) phase. Our result in Theorem 3.1 highlights that, when using the MSE loss, even though DNNs exhibit NC minimizers [4], in the case of GNNs, the graphs must satisfy a strict structural condition for collapsed minimizers. \n\nRegarding the pre-convergence phase, we have provided a detailed analysis of the reduction in NC1 along the gradient flow in Theorem 3.3. As a practical takeaway, we have provided bounds on the regularization (Theorem 3.3 proof) that is needed for the trace of between-class feature covariance to increase along the flow. Overall, the reason for initiating this line of work through a theoretical approach is to present optimistic settings in which GNNs fail to exhibit NC and promote further study in the community.\n\n**Q: Regarding test nodes in the inductive setting.**\n\n**A:** We have followed the setup of Chen et, al [5] which has been widely adopted for community detection in supervised settings.\n\n**Q: Regarding experiments only on SSBM graphs**\n\n**A:** Attaining TPT state is not so simple for GNNs on real-world graphs as indicated by a lack of rigorous benchmarks in the community on supervised community detection (in inductive settings). We have performed experiments on the real-world graphs as per the strategy of [5] as follows:\n\n**Dataset.** We consider the \"com-amazon\" graph from the SNAP collection and prepare 1000 training graphs and 100 test graphs, with each graph having 2 non-overlapping communities from the top 5,000 communities provided by the SNAP collection.\n\n**Baselines and results**: Although the graphs obtained in this fashion are not of the same size and have imbalanced communities, we did observe a partial collapse even in the pre-convergence phase (however, not to the extent observed in the SSBM case as the datasets are relatively complex to attain TPT).\n\n**We thank the reviewer for the comments and will include these key discussions in the revision.**\n\n[1] Papyan, Vardan, et,al \"Prevalence of neural collapse during the terminal phase of deep learning training.\" PNAS 2020\n\n[2] Keriven, Nicolas. \"Not too little, not too much: a theoretical analysis of graph (over) smoothing.\" NeurIPS (2022)\n\n[3] Yao Ma, et al. Is homophily a necessity for graph neural networks?  (ICLR), 2022\n\n[4] Han, X. Y., et.al. \"Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path.\" ICLR. 2021\n\n[5] Chen, Zhengdao et al. \"Supervised Community Detection with Line Graph Neural Networks.\" ICLR 2019."}, {"review_id": "GLR2mhv4ic", "reviewer": "Reviewer_pASb", "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.", "questions": "To enhance the manuscript, the authors may consider addressing the following points:\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\n5. 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.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "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.\n\n1. Some experimental findings could benefit from stronger support through theoretical results (Please refer to Questions 1-3).\n\n2. The applications and implications of certain theorems could be further elaborated (Please refer to Questions 4-5).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General comment:** We are grateful to **Reviewer pASb** for an encouraging review and for raising interesting questions.\n\n**Q:** Regarding theoretical results and a discussion on NC2.\n\n**A:** We agree with the reviewer's point that NC2 might also hold to some extent for GNNs. We show these metrics in Appendix F. In those experiments, NC2 metrics indicate that the (centered) class-mean features do not align significantly with a simplex ETF. This is due to $\\hat{A}$ in the risk formulation, for which, our understanding is not theoretically rigorous yet. We attempted to analyze the risk via a matrix factorization approach as followed by previous efforts [1]. The SVD approach on $W_2H\\hat{A}$ along the \"central path\"[2, 1] is complicated by the presence of $V^T_HU_{\\hat{A}}$, where $V_H$ represents the right-singular basis for $H$ and $U_{\\hat{A}}$ represents the left-singular basis for $\\hat{A}$. These bases are not guaranteed to align (at least the assumption of $V^T_HU_{\\hat{A}}$ is diagonal seemed too strong). Without it, the analysis is extremely difficult to obtain the properties of the singular values (s.v) of $H$ w.r.t those of $\\hat{A}$. Additionally, in the non-GNN NC literature, there are efforts that fix the last layer weights to a simplex ETF and observe only a minimal drop in DNN performance. Sometimes, this also helps in addressing class-imbalance issues.\n\n**Q: Regarding the lower bound for the variability w.r.t p and q.**\n\n**A:** In Theorem 3.1 we obtained the conditions on the graph structure for which NC solutions are the minimizers of the risk. Also, since the expected adjacency matrix $\\mathbb{E}\\hat{A}$ satisfies this condition, neural collapse is desirable. However, to lower-bound the variability (which pertains to the partial collapse result that we see in the experiments), we believe our gradient flow analysis in Theorem 3.3 can serve as a starting point. Through this analysis, we obtain the rate of change of trace of within and between class variability along the flow  (Appendix D.4). These rates depend on the perturbation from the expected SSBM structure. Thus, the optimal within-class/between-class variability depends on the perturbation (which in turn depends on $p,q$). The challenge with obtaining an exact lower-bound lies in calculating the derivatives of terms such as  $HEE^\\top H^\\top$ (notation as per proof of Theorem 3.3), which turned out to be more complicated than expected. An alternative approach can involve a spectral analysis of $E$ in terms of $p,q$. However, we believe it requires a separate study on its own.\n\n**Q: 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.**\n\n**A:** The work of [54] (ref in paper) analyzed the loss landscape and convergence when the risk is based on cross-entropy loss. However, they do not analyze the gradient dynamics. Other NC works that analyze gradient dynamics [15,40] (ref in paper) consider only a plain (non-graph) UFM, which is much simpler to analyze (and the gradient flow is ensured to reach an NC minimizer, which is not the case with gUFM). In Theorem 3.3 we analyze NC1 along the gradient dynamics of a gUFM which is much more involved as the flow is not guaranteed to reach an NC minimizer.\n\n**Q: Regarding the different trace ratios for spectral methods and GNNs.**\n\n**A:** Through the analysis in section 4, we wish to characterize the nature of the learnable weights that allow a GNN to perform \"better\" than spectral methods. In this context, \"better\" indicates that the GNN requires less number of layers than the number of projected power iterations by spectral methods for reduction in NC1 (and to achieve good inference results). In Appendix.F, we show additional experiments with depths of 64, 128. The takeaway from our observations is that the weights $W_1, W_2$ of the GNNs are playing a major role in projecting the features and aiding in faster reduction rates of NC1. Since spectral methods do not comprise any learnable projections, the benefits of GNNs are evident in this scenario.\n\nRegarding the GNNs $\\mathcal{F}, \\mathcal{F}'$, we have not observed any significant difference in their performance that may be caused due to varying rates of reduction in NC1. It seems like the presence of $W_1$ is delaying the NC1 reduction, but both networks reach approximately the same level of NC1 at the last layer. From a practical viewpoint, one can look at GNN layer pruning based on NC1 reduction rates for efficient inference.\n\n**Q: Regarding section 4 (Theorem 4.1) and the connection with over-smoothing**\n\n**A:** Indeed, over-smoothing has been widely studied in the literature to model the reduction of within-class and between-class feature variability across layers of a GNN during training. On the contrary, NC studies the reduction in within-class and an \"increase\" in between-class feature variability (especially of the penultimate layer during training). Interestingly, when the penultimate layer features exhibit NC, we can say that the over-smoothing problem is resolved. This is indeed an important takeaway to the GNN community, which we will clarify in the revision.\n\nHowever, our analysis in section 4 considers well-trained GNNs in inductive settings for layer-wise analysis during **inference**. This setup inherently differs from the over-smoothing analysis (for ex: [3]) which considers the training phase in semi-supervised settings. Interestingly, even during inference, we found variability reduction patterns (fig 5) that resemble partial over-smoothing observed by [3].\n\n[1] Tirer, Tom, et,al. \"Extended unconstrained features model for exploring deep neural collapse.\" ICML, 2022.\n\n[2] Han, X. Y., et.al. \"Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path.\" ICLR. 2021\n\n[3] Keriven, Nicolas. \"Not too little, not too much: a theoretical analysis of graph (over) smoothing.\" NeurIPS 2022."}, {"review_id": "uT0FuuiOjC", "reviewer": "Reviewer_GzMi", "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.", "questions": "1. Can the theoretical analysis in this work lead to any practical design improvements?\n\n2. The term \"instance-wise case\" (line 11) should be defined.\n\n3. The notation of class is used in line 155 but is not defined in the 2.1 data model section.\n\n4. A more detailed discussion should be given about the regime of exact recovery (line 94).\n\n5. The optimizer is defined in line 147, but the loss or objective function to be optimized is not specified.", "limitations": "N/A", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 1, "strengths": "1. This paper focuses on an interesting topic: Neural Collapse during the training of graph neural networks.\n\n2. 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.\n\n2. 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.\n\n3. The theoretical analysis presented in this work has limited practical utility.\n\n\n[1] Keriven, Nicolas. \"Not too little, not too much: a theoretical analysis of graph (over) smoothing.\" *arXiv preprint arXiv:2205.12156* (2022).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**General comment:** We would like to thank **Reviewer GzMi** for the helpful feedback.\n\n**Q: Analyzing only intra-class (within-class) variability without discussing inter-class variability is meaningless.**\n\n**A:** We have included a thorough analysis of the increase in between-class variability of the penultimate layer features in Theorem 3.3. These results are also corroborated by experiments.\n\n**Q: 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.\n[1] Keriven, Nicolas. \"Not too little, not too much: a theoretical analysis of graph (over) smoothing.\"**\n\n**A:** Over-smoothing has been widely studied in the literature to model the reduction of within-class **and** between-class feature variability across layers of a GNN during training. On the contrary, neural collapse (NC) studies the reduction in within-class but an \"increase\" in between-class feature variability (especially of the penultimate layer during training). Interestingly, note that when the penultimate layer features exhibit neural collapse, we can address the over-smoothing problem as neural collapse also represents the maximal separation between feature class means in addition to zero within-class feature variability.\n\nThe NC analysis presented in this work covers two aspects: training and inference. In section 3, where the training phase is considered, we analyze the evolution of the penultimate layer features during training (this is a standard practice that various papers analyzing NC have followed). The significance of this approach is that we can now analyze the role of the objective function and the inherent graph structure in determining the \"desirable\" properties of these features to attain the global minima (Theorem 3.1). The characterization of the strict structural properties for which NC minimizers exist is a unique contribution of this work. Additionally, our gradient flow analysis for these penultimate layer features not only models the decrease in within-class variability but an increase in between-class variability as well. We present the conditions for the amount of regularization needed for this behavior in Theorem 3.3. Thus, presenting a unique perspective on feature evolution compared to previous over-smoothing analyses.\n\nAdditionally, in section 4, we present a layer-wise feature evolution in a well-trained GNN. This analysis considers well-trained GNNs in inductive settings for layer-wise analysis and inherently differs from the over-smoothing analysis of [1] which considers networks in the training phase of semi-supervised settings. We will make sure to include this discussion in the main text. Thank you again for highlighting this point. \n\n**Q: The theoretical analysis presented in this work has limited practical utility.**\n\n**A:** We believe that our work can have the following practical significance: \n\n1. The results in Theorem 3.1 on the strict structural condition of the graph and the gradient flow analysis in Theorem 3.3 indicates that contrary to the case of DNNs where MSE loss leads to collapsed minimizers, the feature evolution in GNNs during training is leading only to partial collapse (even in the most simplistic settings). This result sheds light on the impact of structural conditions on the ideal feature configurations of an expressive GNN. \n\n2. Additionally, observe that attaining neural collapse solves the over-smoothing problem as neural collapse represents the maximal separation between feature class means in addition to zero within-class feature variability. This is indeed an important takeaway to the GNN community, which we will clarify in the revision.\n\n3. A recent work by Ma et,al [1] showed that homophily might not be necessary for good GNN performance on node classification tasks. By leveraging Theorem 3.1 from this work, we can observe that the structural condition (dubbed condition C) required for collapsed minimizers addresses both the homophilic and heterophilic graphs. Thus, our results provide insight into these surprising empirical results [1].\n\n4. Our work can potentially shed light on an ideal \"graph-rewiring\" strategy for improved GNN performance as we know the nature of the minimizers when condition C is satisfied by the computational graph.\n\n5. We believe that extensions of our analysis to semi-supervised /self-supervised settings would be of great value to the community. For instance, the structural conditions that we analyze in this work can be used for graph augmentation in graph contrastive learning.\n\n[1] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations (ICLR), 2022\n\n**Q: The term \"instance-wise case\" (line 11) should be defined.**\n\n**A:** Footnote 1 clarifies this definition. We will incorporate it into the main text for clarity. Throughout the paper, by (plain) DNNs we mean networks that output an instance-wise prediction (e.g.,image class rather than pixel class), while by GNNs we mean networks that output node-wise predictions.\n\n**Q: The notation of class is used in line 155 but is not defined in the 2.1 data model section.**\n\n**A:** It is defined in the setup section (line 74).\n\n**Q: A more detailed discussion should be given about the regime of exact recovery (line 94).**\n\n**A:** Thanks for the suggestion. We will add a discussion in the revised version.\n\n**Q: The optimizer is defined in line 147, but the loss or objective function to be optimized is not specified..**\n\n**A:** We consider the MSE loss in our analysis. It is specified in line 78, above equation 2. "}]

Author rebuttal:
**Our response to the general comments on motivation, theoretical modeling, practical significance, over-smoothing, and a fix to Theorem 3.2.**

**Modifying Theorem 3.2 to ignore the non-rigorous diagonal block case**

As pointed out by one of the reviewers, we have updated Theorem 3.2 to leverage only the off-diagonal blocks in the probability-bound calculation. The case for the diagonal block led to non-trivial assumptions and results which seemed to complicate the message of the theorem.

**The importance of neural collapse (NC).** In standard DNN settings (e.g., image classification on MNIST), the classifiers tend to exhibit NC once they perfectly classify the training data (i,e during TPT). NC includes both: "reduction" in the features’ within-class variability and "increase" (or stabilization) in the between-class variability, such that the features form certain low-dimensional geometric structures. This phenomenon has allowed the community to understand the benign effects of overparameterization and the benefits of training beyond the "zero-classification-error" stage for DNNs (e.g., cases with better test accuracy and improved adversarial robustness [1]). Importantly, we demonstrate that the case with GNNs is not similar to any previous work on NC as the structural constraints of graphs tend to hinder the ability of NC. Also, since the over-smoothing problem is common in deep GNNs, NC shows potential to address such key issues and have a promising impact.

**The data and network models.** To explore the level of NC in GNNs in a principled fashion, we start with SSBM graphs, as their properties are well-suited for theoretical GNN analysis [2]. The gUFM model presented in this paper is much more complicated than any theoretical model in previous publications on NC [4] as we retain the graph topology in the analysis. Importantly, even for our “optimistic" model, we show that the desired configuration of the penultimate layer features (in terms of optimization optimality) does not exhibit exact NC unless the graph satisfies a strict structural condition. This immediately implies an inherent difference between practical GNNs and DNNs. Also, note that it seems very difficult to derive the exact training dynamics in GNNs without trivial assumptions on the structure. Thus, we leverage the literature on SSBM graphs and present a rigorous gradient flow analysis to explain the partial collapse observed in our experiments. This analysis is already a major step beyond analyzing only the minimizers of the model.

**Significance.**
1. The results in Theorem 3.1 on the strict structural condition of the graph and the gradient flow analysis in Theorem 3.3 indicates that contrary to the case of DNNs where MSE loss leads to collapsed minimizers, the feature evolution in GNNs during training is leading only to partial collapse (even in the simplified/optimistic setting). This result sheds light on the impact of structural conditions on the ideal feature configurations of an expressive GNN.

2. Additionally, observe that attaining neural collapse solves the over-smoothing problem as neural collapse represents the maximal separation between feature class means in addition to zero within-class feature variability. This is indeed an important takeaway to the GNN community, which we will clarify in the revision.

3. A recent work by Ma et,al [3] showed that homophily might not be necessary for good GNN performance on node classification tasks. By leveraging Theorem 3.1 from our work, we can observe that the structural condition (dubbed condition C) required for collapsed minimizers addresses both the homophilic and heterophilic graphs. Thus, our results provide insight into these surprising empirical results.

4. Our work can potentially shed light on an ideal "graph-rewiring" strategy for improved GNN performance as we know the nature of the minimizers when condition C is satisfied by the computational graph.

5. We believe that extensions of our analysis to semi-supervised /self-supervised settings would be of great value to the community. For instance, the structural conditions that we analyze in this work can be used for graph augmentation in graph contrastive learning.

**Oversmoothing and neural collapse.**
Over-smoothing has been widely studied in the literature to model the reduction of within-class and between-class feature variability across layers of a GNN during training. On the contrary, NC studies the reduction in within-class but an "increase" in between-class feature variability (especially of the penultimate layer). Interestingly, note that when the penultimate layer features exhibit neural collapse, we can address the over-smoothing problem. In addition to section 3, which highlights the NC results for the penultimate layer during training, In section 4, we presented a layer-wise feature evolution in a well-trained GNN. This analysis considers well-trained GNNs in inductive settings for layer-wise analysis and inherently differs from the over-smoothing analysis of [2] which considers networks in the training phase of semi-supervised settings.

**Overall, we would like to thank the reviewers for their insightful discussions and for strengthening the quality of our paper.**

[1] Papyan, Vardan, et,al "Prevalence of neural collapse during the terminal phase of deep learning training." PNAS 2020

[2] Keriven, Nicolas. "Not too little, not too much: a theoretical analysis of graph (over) smoothing." NeurIPS (2022)

[3] Yao Ma, et al. Is homophily a necessity for graph neural networks? (ICLR), 2022

[4] Han, X. Y., et.al. "Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path." ICLR. 2021


Meta-review: Most of the reviewers were highly impressed by the quality and significance of your research. We would like to highlight the key points that contributed to the positive evaluation of your paper:

1. Novel Contributions to Graph Neural Networks:
The reviewers recognized that your paper introduces a range of innovative ideas that significantly contribute to the understanding of Neural Collapse (NC) in the graph setting. 

2. In-depth Analysis of Feature Evolution with GNNs:
Reviewers found your study of feature evolution with Graph Neural Networks (GNNs) intriguing, particularly the examination of the correlation between topological information and feature changes. The clear presentation of the data model are clear and intuitive, coupled with experiments that align with theoretical results

3. Valuable Theoretical Insights:
Your paper stood out for its  exploration of Neural Collapse in Graph Convolutional Networks (GCNs) and the forward process of neural networks. The reviewers found your theoretical results, including the unique and valuable Theorem 3.1 on partial collapse, to be particularly noteworthy. Such insights have the potential to inspire future research in the field of graph-based neural networks.

4. Clarity of Presentation and Methodology:
The reviewers appreciated the clarity of your paper's presentation. They highlighted the well-written nature of the manuscript and noted that the methodology is effectively explained, making it accessible to a wide audience. 

Please incorporate all the reviewers' feedback in the final version.
Decision: Accept (poster)