Rethinking Graph Neural Networks From A Geometric Perspective Of Node Features
Authors: Feng Ji
Yanan Zhao
Kai Zhao
Hanyang Meng
Jielong Yang
Wee Peng Tay
Venue: ICLR 2025 Poster (2025)
Keywords: Graph neural networks
node classification
feature centroid simplex
coarse geometry
Primary area: learning on graphs and other geometries & topologies
TL;DR: We analyze the geometry of node features to understand graph-independent properties of node classification datasets.

Abstract: Many works on graph neural networks (GNNs) focus on graph topologies and analyze graph-related operations to enhance performance on tasks such as node classification. In this paper, we propose to understand GNNs based on a feature-centric approach. Our main idea is to treat the features of nodes from each label class as a whole, from which we can identify the centroid. The convex hull of these centroids forms a simplex called the feature centroid simplex, where a simplex is a high-dimensional generalization of a triangle. We borrow ideas from coarse geometry to analyze the geometric properties of the feature centroid simplex by comparing them with basic geometric models, such as regular simplexes and degenerate simplexes. Such a simplex provides a simple platform to understand graph-based feature aggregation, including phenomena such as heterophily, oversmoothing, and feature re-shuffling. Based on the theory, we also identify simple and useful tricks for the node classification task.

Published as a conference paper at ICLR 2025
RETHINKING GRAPH NEURAL NETWORKS FROM A GE- OMETRIC PERSPECTIVE OF NODE FEATURES
Feng Ji Yanan Zhao' Kai Zhao', Hanyang Meng", Jielong Yang", Wee Peng Tay! 1 "School of Electrical and Electronic Engineeringg Nanyang Technological University, Singapore "Scoool of Internet of Things Engineering, Jiangnan University, Wuxi, China
ABSTRACT
Many works graph neural networks (GNNs) focus graph topologies and analyze graph-related operations to enhance performance on tasks such as node classification. In this paper, we propose to understand GNNs based centric approach. Our main idea is to treat the features of nodes from each label class as a whole, from which we can identify the centroid. The convex hull of these centroids forms simplex called the feature centroid simplex, where a sim- plex is a nigh-dimensional generalization of a triangle. We borrow ideas from coarse geometry to analyze the geometric properties of the feature centroid simplex by comparing them with basic geometric models, such as regular simplexes and degenerate simplexes. Such a simplex provides simple platform to understand graph-based feature aggregation, including phenomena such as heterophily, over- smoothing, and feature re-shuffling. Based on the theory, we also identify simple and useful tricks for the node classification task.
feature-
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as important tools in managing graph-structured data, commonly found in application areas related to social networks, traffic systems, and biochemical structures (Gilmer et al., 2017: Ying al., 2018; Chen et al., 2020; Li al., 2021; Chen et al., 2022; Liu et al., 2022; Brody et al., 2022; Shen et al., 2023; Kang et al., 2023; Liang et al., 2024). The fundamental idea to apply the technique of message passing or information propagation, formally called graph convolution (M. Defferrard, 2016; Shuman et al., 2013; Ortega et al., 2018). In this process, each node aggregates information from its neighboring nodes and potentially itself. Such a process can be repeated for multiple iterations, and the resulting aggregated information is expected to capture key features and hence represent each node better.
However, it is observed that such an approach does not universally work for any graph-structured data. Consider the node classification task, i.e., each node is associated with a label, and the labels of test set of nodes are to be determined. In graph-structured data with the heterophilic property (Pei et al., 2020; Bo et al., 2021; Yan et al., 2022) (i.e., there are many edges connecting nodes from different classes), basic graph convolution (M. Defferrard, 2016; Kipf & Welling, 2017) is demonstrated to be ineffective, and significant modification needed to get reasonable results (Pei et al., 2020). In many subsequent works, rewiring becomes an important tool for handling graph heterophily. most notably based on high-frequency graph spectral analysis. Another well-known phenomenon is oversmoothing (Oono & Suzuki, 2020; Yan al., 2022), which renders training deep graph convolution neural network extremely challenging. Oono & Suzuki (2020) studies the phenomenon by exploring the topological information of the underlying graphs inherent the graph spectra. Techniques such as skip connections (Li et al., 2019; Chen et al., 2020) and diffusion with memory (Kang et al., 2024) have been proposed to address oversmoothing. In this paper, we study the node classification task in GNN models that involves node feature aggregation. We provide unified theoretical framework to understand and analyze GNN phenomena, including graph heterophily and oversmoothing mentioned above, while new observations are also discussed.
*F. Ji and Y. Zhao have contrihuted equally. Corresponding to: J. Yang (jyang022@e..) (tt.0022@ennnnuduusg)) W. P. Tay (wptay @ @tg..cd..g)..

---

Published as a conference paper at ICLR 2025
Cora, Toxas
Actor
Figure I: Illustrations of (parts of) the feature centroid simplexes associated with different datasets. Such simplex is a graph-independdnt and model-agnostic intrinsic feature property. For example, we notice that simplexes of Cora, Texas datasets have a more regular shape. Though the Texas dataset heterophilic, there are still GNN methods based on feature aggregation that achieves high accuracy on this dataset (improving GCN from R 60% to x 90%). On the other hand, for the Actor graph, it does not seem that any approach can significantly improve upon GCN to the level we observe for the Texas dataset. We hope that our framework, based on studying the shape of the shown simplexes, provides a plausible explanation for this phenomenon.
We consider a graph extrinsic property of a dataset, and its construction can suffer from uncertainty and arbitrariness (Zhang et al., 2019; Dong & Kluger, 2023; Ji et al., 2023b). We regard intrinsic property, which is model-agnostic and does not change if the graph
node features is modified, Unlike some works mentioned above that rely on graph structure and graph spectral properties, we focus mainly on graph-independent information that can be extracted from features, hoping to have some fundamental understanding of each dataset from a ceature-centric perspective. In turn, we gain new insights into graph-based approaches.
Our main technical idea is to treat the features of nodes from each label class as a whole (in node classification), from which we can identify the centroid called the class centroid. We see, from explicit datasets, that the ipprocessed feature of node u (with label c) needs not to be close in Euclidean distance the class centroid of c. However, aggregating features of nodes belonging to the same class may output feature much closer in distance to the class centroid. This prompts us to study each class centroid as the sole representative of its label class.
For this purpose, we take a geometric approach and consider the convex hull of these class centroids, forming a simplex called the feature centroid simplex, which is a high-dimensional generalization of triangle (see Fig. 1). We borrow ideas from coarse geometry (Bridson & Häfliger, 2011) to analyze the geometric properties of the feature centroid simplex, by comparing them with basic geometric models, e.g., regular simplexes and degenerate simplexes. Such geometric consideration provides simple platform for us to understand graph-based feature aggregation and gain new insights into GNN phenomena. Moreover, different basic geometric models correspond different intrinsic properties of features, from which we explore possible explanations for the "hardness" of datasets.
In summary, we propose interpret the role of the graph as used determine how aggregation is performed, which mitigates feature variance. Thus the feature centroid simplex is enough to capture essential intrinsic dataset properties. We use new geometric tools study such a simplex. Though our work has limitations (Appendix G), we hope that it draws more attention to the study of "whether current GNN approaches have reached, to certain extent, the Bayesian ervor rate for different datasets". Our main contributions are summarized as follows:
We study GNN phenomena through the lens of node features instead of graph topologies. We introduce the notion of feature centroid simplex and develop a theoretical framework based on coarse geometry and probability theory. It provides us with tools for understanding and analyzing GNN models.
We give alternative explanations to known observations and gain new insights into why it is hard to achieve significant results for certain datasets by any means. Moreover, we justify the effectiveness of some well-known GNN models from our perspective.
Based on these theoretical findings, we identify surprisingly simple graph-independent tricks that are demonstrated to enhance the node classification performance of GNN models on certain datasets. We also explain why they work or fail on different datasets.
Due to space constraints, a notation list and proofs are delegated to Appendix A and B. We provide substantial numerical evidence to support our claims in Appendix E.
2

---

Published as a conference paper at ICLR 2025
2 THE FEATURE SIMPLEX AND ITS COARSE MODELS
In this section, we present the probabilistic model for the feature space of cach label class and propose geometric framework to study its properties. As preview, we use the topological concept of "simplex" to capture essential information about node features and introduce the notion of quasi isometry as the main tool for the study in the next section.
2.1 THE PROBABILISTIC FEATURE MODEL AND FEATURE SIMPLEX
Assume that G (V, F)) is a connected, undirected graph of size n |V. We consider the following feature model. Each node i; is associated with an m-dimensional feature x' (-i,... ...... -.......00....... ) in [0, 11TH C IRm Let C' be the finite set of class labels. We assume that node features x² x are identically independently generated via the following steps:
$1 For each (node) index = 1,.... n, class e is randomly chosen according to prescribed distribution (e.g., uniform distribution).
S2 A feature is generated according to prescribed class-specific distribution Ye-
To avoid technicalities, provide informal version of the geometric lemma convey the key message. In Appendix B, we give a detailed specification of " and formal statement of the lemma. Lemma (Informal). With high probability, (x',...,." are in a convex position, i.e., none of x² is in the convex hull of the remaining feature vectors.
We assume
,,",,,")))))) are in convex position for subsequent discussions. We have verified that the lemma holds for all datasets used in Section below. Intuitivell, the features are random points either the vertices of unit hypercube or in high-dimensional unit ball. In either case, they are in a convex position with high probability due to the high-dimensional stochastic separation phenomenon (Gorban al., 2018).
For each node v. recall x² its feature vector, and let & E be its label class. Definition 1. For each class denote D. for E Vlc c} of size nee Del and define its feature convex hull as A. = conv(fa* " | E De)), the convex hull of {x* | E Dc).
By the assumption following Lemma 1, De is the vertex set of the convex polytope A.. Moreover, A a (n. - 1)- simplex as it is homeomorphic to the standard (ne - -1)-simplex (Hatcher, 2002, p. 9):
Dn, (v1.... ( E {0.11
Σ y1 -
(1)
ISIS
For simplex, useful representative is its centroid.
Definition For each class c, let e, be the probabilistic centroid of the class defined as 6e Ezwy, [x]. Moreover, the geometric centroid 9. of the samples of class c is 1 ne Ev.eD. x² E Ae-
Intuitively, the probabilistic and geometric centroid are close to each other if ne is large. More precisely, have the following simple observation.
Lemma 2. There is a constant K independent of n such that for > 0 that is sufficiently small, P(lle gell 5) < exp(-Kn..22 + 1/4).
Convention:
This observation will used subsequently, and we will refer to the same K and 8 in Lemma 2 without further mention.
Probabilistic centroids {ea I c E C)} are useful for theoretical analysis. However, practice, we do not gain access to them. By Lemma 2, if we have sufficiently many samples for each class, we do not lose much information by using the geometric centroid ge as a proxy of ec.
Recall that the objective of the node classification problem is to assign discrete probability distribu- tion f4 = {ve [0, 1] c C} to each node u E V. Geometrically, such a distribution ft belongs to the probability simplex Ac = conv(fpe E R |c C}), which is the standard (IC) 1)-simplex (here, Pe is the one-hot vector of label class c). Ideally, features near e 9e E Rm (cf. Lemma 2) should be matched with p. via a learning model (illustrated in Fig. 2). This prompts us to study the following simplexes and analyze their relations with Ac.
3

---

Published as a conference paper at ICLR 2025
Definition 3. The feature centroid simplex is the (IC) - simmpleesx A. conv(fee C)) and its proxy is A = conv(19. ((9c E C}).
In this next subsection, we discuss coarse geometry, which serves as the main tool to study feature centroid simplexes and GNNs.
2.2 COARSE GEOMETRY AND STANDARD MODELS
Recall that Ae has the ideal shape of being regular simplex of equal side-length /2, both A and Ag are unlikely to be so. However, if they approximately have regular shape, we can already draw useful conclusions (cf. Section 3). For this, we borrow ideas from coarse geometry (Bridson & Häfliger, 2011), from which we modify the notion of quasi-isometry (Bridson & Häfliger, 2011, 138) to obtain the following simplified version.
Definition 4. Given 2 O, simplexes Ay conv(ly',.... ...., v² and As conv(1z'.... ...,, 22,1 ,..,," are e-quasi isometric, denoted by Dy Re A., for any (a),.... "al....aa. ax)", standard (k- 1)-simplex (see (1)), have
A the
S
Σ 1SiSk
a.y² Σ ISiSk
1w''1-11
Σ 15iSk
Σ 1sisk
bi Sc.
Being e-quasi isometric essentially means that the distance between any pair of points in A, is close, to an error, to the distance between the corresponding pair of points in A.. Hence, geometrically, 4y is small perturbation of A.. While such condition usually hard verify directly, we have the following version that only requires checking the vertices of the simplexes.
CNN mndel
Definition 5. A of points fy'..... v²} is vertex ffr any i + j. we have (v 5²) (='-2)) =2)1
quasi isometric to {2'....,2f, 2²,
Figure 2: A schematic picture of the geometric concepts, c.g., centroids, Ag. A., Ac. Nodes with different col- ors/shapes represent features belonging to different classes.
Lemma 3. Suppose " yy. is vertex e-quasi
isometric to {21 (......, 3*. Then we have Dy conv (y'......." me A. conv((2"....,.''
Recall that two simplexes are congruent to each other if every pair of corresponding edges has the same length. Hence, we can use edge lengths of A g. A_ to probe their quasi-isometric relation. In Appendix E.2, we analyze the shapes of Ag for different datasets using the above notions.
Model shapes The basic idea of the paper is to compare feature centroid simplexes with standard geometric models. As preview of the next section, Ay will be the subject want to study, e.g., Ag and A., while A₂ will model simplex of special shapes. We end this section by describing some of these model shapes to be used later.
We have seen regular simplexes, which are simplexes with equal side lengths. A related notion is the following.
Definition 6. Points {x0,z" 2....... ..... , are said to form a (F1, rreguar k simplex for T1. > 0 the base A' conv {x ,...,." 1"). a regular (k 1)-simplex of side length rı, and ||20 z'll is the same for every 1 S iisk k. Moreover, the distance from a. to the centroid of A' is r2. We call conv((2) xx, xx,....,ak) the associated (F1, (rigra)-regular k-simplex.
For preview, r. shall be used as comparison point to the origin 0.
There are also examples where A₂ is "thin", i.e., some sides have much smaller lengths than others.
Definition 7. We call a (k- 1)-simplex A with vertices z 2'...., 2 degenerate if for some #
2 (see Appendix E.2 for a more general definition).
We shall see such shape corresponds to "hard" dataset.
4

---

Published as a conference paper at ICLR 2025
3 THE GEOMETRY OF GNN MODELS
In this section, we use the geometric setup of Section 2 to analyze the GNN convolution layer. Formally, GCN layer consists of convolution layer, linear layer, and ReLU activation. From empirical evidence in Appendix E Table 7, we observe that including the ReLU activation does not improve GCN performance in some datasets. Moreover, a 1-layer model is only slightly worse than 2-layer model. Hence, to simplify the theoretical analysis in this section, we consider a 1-layer model without ReLUU
Models of eventual GCN type Though theoretical analysis focuses on the simplified GCN as above, the discussion in this section can be extended to more sophisticated models. For this, we define model M to be of eventual GCN type if there exists weighted graph G' (possibly different from the original graph G) such that the output of M is the same as a GCN model applied to G", with the exact same imput features. For such a model, our framework can be used directly analyze M. in conjunction with the properties of G". As preview, let N, be the neighbors of node e. If G' is weighted, it suffices to replace |N₂, in various expressions below with 1/|lW, where W. (We,.o),,EN, is the edge weight vector and We,e is the weight of the edge (e;, v) (using results in Barber (2024)).
Many GNN models are of (or related to) eventual GCN type. For example, attention-basel models (Veličković et al., 2018; Lee et al., 2022; Lv et al., 2021) essentially generate a weighted graph for convolution, where the edge weights are the attention scores. There models having rewiring edge deletion as their components (Rong et al., 2020; Suresh et al., 2021; Topping et al., 2022; Ji al., 2023a). They of eventual GCN type, where G' is the graph topology. In neural diffusion model (Chamberlain et al., 2021; Rusch et al., 2022; Zhao et al., 2023), the basic idea is to iteratively equation. The update rule resembles a GCN convolution on weighted graph that may change in each iteration. The adaptive nature adds flexibility that may mitigate unfavorable phenomena such as oversmoothing. These models can also be analyzed using our framework analogous to our discussion above by keeping track of the shape of De, Ag updates.
forward Euler feature updating scheme to model the solution of diffusion
3.1 FEATURE AGGREGATION
Recall that for each node let N, be the 1-hop neighbor of u, including itself. The convolution (M. Defferrard, 2016) updates the feature of v as
1
Σ R
Dv
We are interested in the location of y, in the feature space R", particularly its proximity to the vertices and special points on the simplex A.. To state the following main result, for C, let No.c = N₂ O Dr and define its mixed centroid
Σ ea.
CN.
N
m.N,
+/4)))++1//)) C
Theorem 1.
(a) We have PP(1.. eN.
(b) Suppose there is 2 0 and a regular (IC) 1)-simplex A = (oov c E C}) with (the common) side length r such that: {eo C} vertex E-quasi isometric to {ue I E C). Then, for any E C, we have
IP [1ve- eell 2 do
- - 6-116)) > (1- (1-eep(-KolN.1+11//
V2
where d2 = =
|Nu.el
|N.1 )2 ) Eetoo
(
|N [.o]
Discussions Notice that the probability bound in Theorem 1 (a) only involves [N,] Intuitively, this means that if node has sufficiently many neighhors (disregarding their label classes), then with high
5

---

Published as a conference paper at ICLR 2025
probability, its aggregated feature is close to the point in Ae aggregated, in the same way, from its vertices. In (b), the model simplex, which is a regular one, plays an essential role. Notice that d,,e R3 if and only if NN,ccl = [N Otherwise by (b), if > c, then with high probability lly, e. has large lower bound. As a consequence, it may be prudent during training to avoid directly fitting a node, with many neighbors from different classes, its ground-truth class. We propose tricks based on this and demonstrate that they work better for datasets with more regular A, in Section 5 (see also discussions in Section and thorough analysis of simplex shapes in Appendix E.2).
3.2 THE LEARNED LABEL. DISTRIBUTION
Following feature aggregation, the convolution layer is a linear transformation. Recall that the goal of any model to generate an element in the probability simplex Ac for each node v E V. We want to investigate the probability distribution linear layer following the feature aggregation can possibly generate. For this, we first introduce a less strict type of simplexes than regular simplexes.
We have used regular simplex to approximate the simplex A.. As illustrated in Appendix E.2 Fig. 7, for many datasets, centroids in {ge c E C} are approximately equal in distance O. Hence, (r1,72) r2)-rguular simplexes introduced in Definition 6 are reasonable model shapes. For the next result, we introduce the following quantity for any (r1, (11;r2)-regun -regular k-simplex.
Suppose (x.,, (x",x)
x*} form an (f1, rreeguar k-simplex A with base A' We define:
p(r1, min
(2(k)) 1/(k-1) 2//2)k)
T1
(5)
which is independent of the locations of x xx
Recall features x1 _t,.... "t,,...,"", ,,,,,,",,,,
and vectors ye, eN, defined earlier (3), (4). We have the following.
Theorem 2. Recall Ac conv((Pe c E C}). Assume that {0) U fealc E C} is vertex e-quasi isometric to {0} U [ee E C} that form an (r1, -regular simplex. Suppose / < T2) and define p(ri, r2, e) = (p(r),72) VIClc)- > Then there a linear transformation L from the feature space to RlC) such that the following holds.
(a) For each e E C, if = arg min yERIC! Evg class e _ll(((x)) - yll. then
P P(Ipe Tel p(r1, r2, p(r1, c)0) 2 1 expl 1xp(-Knn5 + 1/4).
(b) For any node v. let pru E Do be the neighborhood class label probability distribution of ie.. (c) = |No,c//|N, Then
P (I moll p(r1,)2,e)((10) (1- 1il-exp--K/NN/++1/00
Discussions We point out that L(y.) in Theorem 2 (b) corresponds exactly to one GCN layer. Intuitively, the result essentially claims that for each node v, the linear fitting L and hence the GCN layer generates a probability distribution that is almost the same as the neighborhood class label distribution of v, with high probability. A numerical verification using a thought experiment is in Appendix E.3, showing if is known, then forcing the output distribution to be similar to v4 solves the classification problem.
Notice by (5), the factor p(r1, e) in the upper bound is small if r1, > This occurs again if {0) U fee c E C}} forms a simplex relatively regular shape. Therefore, in GNN model design, re- re-shaping Ae into more regular shape is strategy worth considering (see Section 5). In the next subsection, we discuss the consequence if A, does not have a regular shape.
3.3 DEGENERATE MODEL SIMPLEXES
We have thus far discussed only feature centroid simplexes having an almost regular shape. In this subsection, we consider the contrary of having an almost degenerate shape. For the next result, recall yo EN. defined in (3) and (4).
This simplified setting is convenient for theoretical analysis. In GNN model, softmax is usually used and discuss its effect Appendix H.

---

Published as a conference paper at ICLR 2025
Homophilk
Heismphillic cree
MLP
De
Ap
Figure 3: In the homophilic case, the aggregated features (solid disc, while circles are the original features and they are more scattered) are matched approximately to the correct vertex in the probability simplex, while in the heterophilic case, the features no longer suitable fit with vertices of the probability simplex. Therefore, in the heterophilic case, GCN may even underperform against a vanilla MIP, though for the latter the features are more scattered.
Corollary 1. Suppose there is an E O and degenerate simplex A - (t I E C}) (with Ue. "eys? i + j) such that: {ee Ic C} veriex e-quasi isometric to conv (Luel e E CJ). Define EN. E De by replacing ee, with ee, and vice versa. Then
P( P(1 EN. eN.
(C18-0) (1-eep(-K0]]]
Discussions The result suggests that if Ae is almost degenerate simplex, i.e. it is thin, then there is no way to very accurately identify the summands in yo by observing it. Notice that for such A.. if it has sides whose length is much larger than then it cannot be reasonably modeled by regular simplex as in Theorem 1 and Theorem 2. The quasi isometric model of A. is an intrinsic property of features independent of the graph. Therefore, many models of eventual GCN type, which rely only on altering the aggregation mechanism, cannot resolve this inherent issue of features. This is verified by the feature re-shuffling phenomenon in the next section. Datasets (e.g., the Actor dataset) that satisfy the conditions of Corollary are shown in Appendix E.2 and studied further in Appendix E.4, Appendix E.6. We explain the general poor performance of GNN models on these datasets.
4 PHENOMENA IN GNNS
We first summarize general insights derived from the feature-centric perspective in Section 3 to guide our discussions: (a) Feature aggregation essential reduce feature variance (see discussion on the use of normalized adjacency matrix in Appendix H). (b) The efficiency of feature aggregation depends on the shape of the feature centroid simplex, which is an intrinsic graph-independent property, (c) We should aim aggregate features of nodes of the same class in both training and testing, which, a priori, is the role of the graph structure. (d) However, (c) is not always easily achievable. this case, the model output label distribution should be interpreted in conjunction with the aggregation mechanism and the graph structure.
Homophilic graphs v.s. heterophilic graphs If graph is homophilic (illustrated in Fig. 3), then for most of the nodes, their neighbors belong to the same type, i.e., for a node v with label c, |No.el/ |,.| R 1 and NN..e N/ 0 for any c' o In this case, eN, R e, and by Theorem I (a), the aggregated feature is close to e with high probability. Hence, Ve can be fitted close to Pe via the linear map the neighborhood class label distribution Nv. Test error will thus likely occur for those nodes whose neighbors contain a significant number of nodes from different classes. For a simple verification (on Cora), for each test node ii of class C. we compute Me, (c:) (defined in Theorem 2(b)). Its average value is R 0.911 for correctly classified nodes, while only Rs 0.668 for misclassified nodes.
in Theorem 2. while the output probability distribution of a node is close to
On the other hand, in a heterophilic graph (illustrated in Fig. 3), many nodes have neighbors belonging to different label classes, i.e., for a node v of label class c, |No.el is significantly smaller than N,, In this case, du.c in Theorem 1 is significantly larger than 0, which implics that the aggregated feature Ye is bounded away from e, with high probability by Theorem 1 (b). It thus causes significant error try to fit ye with the vertex Pa in the probability simplex Ac. This is why simple MLP sometimes works better as shown in Yan et al. (2022). In Section 5, we focus on heterophilic graphs to address the above issues.
Oversmoothing It is observed in Oono & Suzuki (2020) that oversmoothing is due mainly to the Markovian property of feature aggregation. Oono & Suzuki (2020) explains the phenomenon from
7

---

Published as a conference paper at ICLR 2025
graph spectral perspective. Here, we our geometric perspective of node features to provide another point of view, which can be easily visualized. we disregard the ReLU function, for a T Tlayer model, essentially consider T -tteps of neighborhood aggregation, followed by a linear transformation. We
inspect the change of the simplex A = conv (fge c E C)). Recall that Je Lv,ED, E. x² 23 Ba
by Lemma 2. After the aggregation step, Je becomes
Σ The
Σ
Σ N
9c
-
N R
The m.D.
NyENu
d'EC ey eyEN ei.e!
Σ C'EC
E
x
Re
No.
ByEN
Let and L E.EDD |N 1/\.V,, For each e, there are some c' + c such that and 0 as each neighbor of De belongs to a different class. Hence, Oie,c' 1. Then g from above becomes Eeec Ogeee' EnjED,r T EmEDD..JEN. (N.,T) xr. By a mean-field type assumption, we as- sume for v, belonging to the same class, the non-zero coefficients in front of x² are approximately the same. The coefficient is non-zero if 24 is within the 1-hop neighbor of the entire set D.. If there are many such vi 's, then EnjED, ag EetEDe, [N,,]] )al x egt. Therefore, in conclu- sion, ge e! Evec Oc,e i.e., after single layer of aggregation, the average g: of the updated feature {uu, V. E D&} is approximately e The update coefficients fae,e', E C} depend only on the dataset but not on the iteration number. By the same argument, define iteratively el = Eeec C (t-1), We study how A conv(fe," (() , E C}) evolves for t 2 1 to under- stand the features updates in each iteration. The above formula implies that the vertices of (t) are updated via the matrix M )e,eeC.
Lemma 4. M is stochastic matrix and it has unique stationary distribution
a consequence of the lemma, if (#e)cEC the stationary distribution of M, then each e converges to Ecso S.Ce. Therefore, we have the oversmoothing phenomenon as (4) converges to a single point at + co. A schematic picture is shown in Fig.
We numerically verify by training deep GCN and study the volume Vol ()) of the resulting A after the 1-th layer, expecting to diminishing. For Cora, after layers, the (average) volume is reduced to 1.7% of the initial (average) volume. For Texas, after layers, the (average) volume is reduced to == 2.6% of the initial (average) volume. The observations support the theory.
Figure 4: An illustration of oversmoothing. The simplex { in each it- eration is represented by a (colored) triangle. Af- ter enough iterations, it shrinks to the center.
Feature re-shuffling Our result in Section 3.3 predicts the following: for a dataset, if the feature centroid simplex A, is almost degenerate, then it imposes significant challenge for the classification task. This phenomenon is observed for the Chameleon, Squirrel, and Actor datasets (see results in Section 5 and also Appendix E for further discussions). By the definition of degeneracy, there are at least two classes G₁ Cj. whose associate centroids Ce.y Cey are very close. Therefore, it is expected that we re-shuffle the features of nodes of classes C;,C Cj (possibly resulting in nodes of class e; having features of class eý), there will be no significant drop boost in the classification result. This is verified by the results in Table 1. The study reveals the model-agnostic intrinsic difficulties for the classification task from the feature-cente centric geometric perspective.
For casier datasets whose Ae is more regular (c.g., Cora, Citeseer), re-shuffling nodes belonging to the same class may even improve model performance. A graph is usually constructed with resulting edges connecting nodes with similar features. However, aggregating similar features is less useful in reducing feature variance. Therefore, re-shuffling may overcome such a shorteoming and after re-shuffling, the aggregated features can be closer to the centroid (see Fig. 5). This is verified on Cora and Citeseer Table 1, and similarly observed in Lee et al. (2024).
8

---

Published as a conference paper at ICLR 2025
Table 1: Based on the study in Appendix E.4, we re-shuffle features of class (01, C2), (c1, (C1,03) 03) and (02, c3) using vanilla GAT, GAT, ACM-GCN (as top performers in Table below) for the Chameleon, Squirrel and Actor datasets respectively. Re-shuflling does not harm the performance. For Cora and Citeseer, GCN is applied, and re-shuffling significantly improves the performance.
Chameleon
Squirel
Actor
Cora
Citeseer
Pre re-shuffle
71.6422.69 61.6745.00 00 34.39=1.31 80.95::0.11 70:91=0.48
Post re-shullle
71,274:1.93 62.74.1..8 1.35
86.16:10.26 79.36=20.39
In conclusion, the study supports the presumption that a key role of the graph is for feature aggregation reduce feature variance, and the aggregation alone does not resolve intrinsic issues arising from the suboptimal shape of the simplex Ae.
Asqropoted Scantures
Pro moshmille
Foost
5 EXPERIMENTS
Figure 5: Re-shuffling makes features of nodes connected by an edge less similar. The sulting aggregated feature is thus closer to the class cen- troid.
Simple tricks The theoretical findings suggest simple generic tricks might be employed enhance the performance of GNN mod- els. We propose two such graph independent tricks with justification:
(1) Recall by Theorem (a), the aggregated feature of training node Us is approximate eN., defined in (4). For eN., to be close to Ca.s is desirable have more nodes the neighbor of o to have the same label A simple trick for this is to independently randomly add edges between training nodes of the same class, with
probability 77 (a hyperparameter).
(2) By Theorem I (b) and discussions Section 4, the aggregated feature V/, of a training node v; can deviate from ec; if it has a large percentage of neighbors not from the same class e; (see also Fig. 3). Thus, the better ye, fits with Pc., the more error it causes in testing. We thus propose a very early stopping by training & (a hyperparameter) epochs for small E.
The proposed tricks fall into a few common generic categorics of machine learning techniques. In Appendix C: Related Works, we discuss how they differ from existing methods, belonging to the same categories, at the conceptual level.
The tricks are model-agnostic and can be applied (either separately jointly) to most GNN models. Given a base model M, we use "M-AE" to denote its modification when the tricks are incorporated. The tricks simple and have minimal effect the computation complexity. We consider GCN (Kipf & Welling. 2017), GAT (Veličković et al., 2018), ACM-GCN (Luan et al., 2022), GraphCON (Rusch al., 2022), CDE (Zhao al., 2023), and GloGNN (Li et al., 2022) as base models. Experimental details are in Appendix D. We focus on heterophilic datasets, which have rich structures to analyze (see results for homophilic and large scale non-homophilous datasets in Appendix F.1, which also contains discussions on the feature scarce scenario).
The results are shown in Table Among 48 comparisons, the above tricks significantly (in terms of p-value) improve the performance in 34 instances, and the improvement is insignificant in 14 instances, mainly for Chameleon, Squirrel, and Actor datasets. As explained in Section 3.3, due to the feature centroid simplex being approximately degenerate, it does not seem that any model is particularly effective for these datasets (though some are relatively better).
In Appendix E.2, Appendix E.4, and Appendix E.5, we thoroughly analyze Chameleon, Squirrel, and Actor datasets. We explain why these are the more difficult datasets from our point of view. We also observe that it is more likely to mistakenly predict the class сj for the ground-truth class c; if llge. - 9c, is small, which is consistent with theory and the feature re-shuffling study in Table 1.
The feature normalization trick In Appendix E Fig. 7 and Fig. 9, we observe that a common issue with Chameleon, Squirrel, and Actor datasets is that features of most nodes not expressive in the sense that they have a small norm. The resulting simplex Ag thus has a less regular shape (cf. Section 3.3). We apply simple normalization trick that normalizes each feature vector to have norm

---

Published as a conference paper at ICLR 2025
Table 2: Node classification (ssults(%). The best result for each dataset is highlighted in blue. "-I" and "-II" stand for 1 and 2 layers respectively.
Method
Texas
Cornell
Wisconsin
Chameleon
Squirel
Actor
GCN-I
68.92=7.95
62.97::4.36
62.9714.36
59.19-2233
42,96::1.46
30,68:10.45
GCN-I-AE
79.45=8.30
69.73:27.63
71.377.666
63.54 03.5414.100
65.06:66.22
34.30:12.89
GCN-II
58.11+7.07
60.54++9.0
56.47+7.98
65,42+2.022
48.51+11.22
2..39++1.22
GCN-II-AE
63.24=4.22
61.0845.30
61.9226.46
66 16.25:4.115
50.9613.17
30.85=;1.59
GAT-
77.57+66.95
70.81+8.87
69.61
66.71++3.10
54.21+3.21
28.66
GAT-I-BB
81.08=6.51
74.05=10.69
71.96+t.59
68.93++5.98
55.02-+5.55
32.35-+1.87
GAT-II
65.14:110.50 60.81=10.89
61.5777.03
71.64422.9
61.67+:5.00
28.09::1.60
GAT-II-AE
66.48:110:48 67.30:1..15
63.3118.36
72.24
62.3715.54
31.8211.58
ACM-GCN
48.92:::.26
86.76:17.49
88.2415.11
71.29:8.06
$5.07=8.96 34.39:1..11
ACM-GCN-AR
90.81+5.30
88.91--6.56
91.18+6.46
73.38+9.78
58.08
4..60+3393
GruphCON
88.65::4.65 82.97:14.37
87.8414.554
64.30:1..45
43.34:14.00 30.26:11.53
GraphCON-AR -F
91.08
84.86-+4.88
89.22+2.52
65.13++.77
43.57-+4.69
22.46++2.64
CDE
84.86:55.69
72.97:44.68
82.16::6.1 10 59.93--0.97
43,49:11.88
36.41 1.08
CDE-AE
85.41+5.01
75.68++5.27
85.69+3.83
60.09+22.77
44.01++1.69
36.58++1.05
GloGNN
52.16=55557
82.97=4.00
54.90:5.55
69.78
$7.61
17.1
GloGNN-AE
83.78=4.19
83.24:14.95
86.2743.82
69.32:22552 17.65:1..44 1..33
Intuitively, the procedure relatively increases the size of each component of features with a small norm. In turn, the shape of the simplex Ag may become more regular, which is supported by the analysis in Appendix E.6. We see its usefulness from Table 3. The trick also shown to be very effective for the Ogbn-arxiv dataset in Appendix F.1 Table 10.
Table 3: Normalization (suffix: "- "-AEN") applied to .MMAE: the overall best model ACM-GCN.
Method
AACM-GCN ACM-GCN-AE ACM-GCN-AEN % f over M
Chameleon
72.29-18.06
73.38:19.79
75.22:19.99
4.05%
Squirrel
55.07=8.96 58.08119.6 34.28:12,76
59.47:11.41
7.99% 47.62:6.38
Actor
42,60:1..93
38.9%
The output probability distribution In Theorem (b), it is predicted that the output label dis- tribution v of a node v is approximately its neighborhood label distribution 14. We measure their difference by the mean of é ||2, pe I (the choice of I|-IIa is explained in Appendix H), averaged over all test nodes. From the results in Table 4 (on GCN-I), we see that the tricks indeed improve the average e, As eventual GCN models change the graph structure, more results in Appendix F.3 show that most other models underperform in this metric.
As we show in Appendix E.3 and Fig. 10, knowing (le | E V} accurately sufficient for the node classification problem. In conjugation with Theorem 2 (b), we propose estimating {nm v E V) as an alternative objective for future work. It is possible to further reduce L, by conformal prediction, as mean of distribution denoising. Details can be found in Appendix F.2.
Table 4: The performance of the tricks in the metric of average Ey ||u, Mell22
Method
Texus
Comell Wisconsin Chumeleon Squirrel Actor
GCN-I 0.6874 0.7286
0.7204
0.7360
0.6240
0.9044
GCN-I-AB 0.6181 0.6482
0.5634
0.6934
0.5834
0.8877
6 CONCLUSIONS
In this paper, we propose theoretical framework for understanding GNN models based coarse geometric models feature centroid simplex. It allows us to have a glimpse into theoretical ex- planations of GNN phenomena such oversmoothing and feature re-shuffling, and to enhance our understanding of the mechanisms and fundamental limitations of GNN models. We discuss the limitations of our framework and propose future directions in Appendix G.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
This research is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority under its Future Communications Research and Development Programme.
H. Meng and J. Yang are supported part by the National Science Foundation of China (No.62106082).
REFERENCES
A. Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution- free uncertainty quantification. arXiv:2107.0755 Iv,, 2021.
R. Barber. Hoeffding and Bernstein inequalities for weighted sums of exchangeable random variables. vrXiv:2404.064577 2024.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In AAAI, 2021.
J. Bober, A. Monod, E. Saucan, and K. Webster. Rewiring networks for graph neural network training using discrete geometry. Complex Networks, 2023.
M. Bridson and A. Häfliger. Metric Spaces of Non-Positive Curvature. Springer Science and Business Media, 2011.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive graph attention networks? In Interna- tional Conference on Learning Representations, 2022.
B. Chamberlain, J. Rowbottom, M. Gorinova, S. Webb, E. Rossi, and M. Bronstein. GRAND: Graph neural diffusion. In International Conference Machine Learning, 2021.
M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning. 2020.
Y. Chen, M. Yang, Y. Zhang, M. Zhao, Z. Meng. J. Hao, and I. King. Modeling scale-free graphs with hyperbolic geometry for knowledge-awee aware recommendation. In Proceedings of the 15th ACM International Conference Web Search and Data Mining, pp. 94-102, 2022.
J. Choi, S. Park, H. Wi, S. Cho, and N. Park. PANDA: Expanded width-aware message passing beyond rewiring. In International Conference on Machine Learning, 2024.
Clarkson. Distribution free prediction sets for node classification. In International Conference on Machine Learning, 2023.
M. Dong and Y. Kluger. Towards understanding and reducing graph structural noise for gnns. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
Gilmer, S. Schoenholz, P. Riley, O. Vinyals, and G. Dahl. Neural message passing for quan- tum chemistry. In Proceedings of the 34th International Conference on Machine Learning, pp. 1273-1272, 2017.
A. Gorban, A. Golubkov, B. Grechuk, Mirkes, and I. Tyukin. Correction of Al systems by linear discriminants: Probabilistic foundations. Information Sciences, 466:203-323 322, 2018.
Jiaqi Han, Jiacheng Cen, Liming Wu, Zongzhao Li, Xiangzhe Kong, Rui Jiao, Ziyang Yu, Tingyang Xu, Fandi Wu, Zihe Wang, Hongteng Xu, Zhewei Wei, Yang Liu, Yu Rong, and Wenbing Huang. A survey of geometric graph neural networks: Data structures, models and applica- tions. arXiv:2403.00485 2024.
A. Hatcher. Algebraic Topology. Cambridge University Press, 2002.
M. Horn Brouwer, M. Moor, Y. Moreau, B. Rieck, and K. Borgwardt. Topological graph neural networks. In International Conference Learning Representations, 2022.

---

Published as a conference paper at ICLR 2025
K. Huang, Y. Jin, E. Candès, and J. Leskovec. Uncertainty quantification over graph with conformal- ized graph neural networks. In Advanced Neural Information Processing Systems, 2023.
Ji, S. Lee, H. Meng, K. Zhao, J. Yang, and W. P. Tay. Leveraging label non-uniformity for node classification in graph neural networks. In International Conference Machine Learning. 2023a.
F. Ji, W. P. Tay, and A. Ortega. Graph signal processing over probability space of shift operators. IEEE Transactions on Signal Processing, 71:1159-1174 2023b.
W. Jiang. Process consistency for AdaBoost. The Annals of Statistics, 32(1):13-29, 2004.
Q Kang, K. Zhao, Y. Song. S. Wang. and W. Tay. Node embedding from neural Hamiltonian orbits in graph neural networks. In Proc. International Conference Machine Learning, Haiwaii, USA, Jul. 2023.
Q Kang. K. Zhao, Q. Ding, F. Ji, X. Li, W. Liang, Y. Song, and W. Tay. Unleashing the potential of fractional calculus in graph neural networks with FROND. In International Conference Learning Representations, 2024.
Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In Proc. International Conference Learning Representations, pp. 1-14, 2017.
J. Kohler and A. Lucchi. Sub-sampled cubic regularization for non-convex optimization. In Interna- tional Conference on Machine Learning, 2017.
S. Lalley. Markov chains: basic theory. https://gaal www.:ttoon.cccccoo.eooooo wet.ei....dd//lllleee/ Courses/312 2atps/311//Maarataaaa //MaaMMoCaaiisss pdf,201c
S. Lee, F. Ji, and W. P. Tay. SGAT: Simplicial graph attention network. In International Joint Conference on Artificial Intelligence, 2022.
Lee, Kim, J. Yoo F. Bu, J. Tang, and K. Shin. Feature distribution on graph topology mediates the effect of graph convolution: Homophily perspective, In International Conference on Machine Learning, 2024.
G. Li, M. Muller, A. Thabet, and B. Ghanem. DeepGCNs: Can GCNs go as deep as CNNs? In IEEE International Conference Computer Vision, 2019.
R. Li, X. Yuan, Mo. Radfar, P. Marendy, W. Ni, T. O' O'Brien, and P. Casillas-Fipinnsa. Graph signal processing, graph neural network and graph learning on biological data: systematic review. IEEE Reviews in Biomedical Engineering, PP:1-1, 10 2021. doi: 10. 10911199//M.... 202..3322202111122222
X. Li, R. Zhu, Y. Cheng, C. Shan, S. Luo, D. Li, and W. Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, 2022.
Wenfei Liang, Yanan Zhao, Rui She, Yiming Li, and Wee Peng Tay. Fedsheafhn: Personalized federated learning on graph-structured data, arXiv preprint arXiv:2405. 16056, 2024.
D. Lim, F. Hohne, X. Li, S. Huang, V. Gupta, O. Bhalerao, and S. Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Proc. of the 35rd International Conference on Neural Information Processing Systems, 2021.
W. Liu, Y. Zhang, J. Wang, Y. Hc, J. Caverlee, P. Chan, D. Yeung, and P. Heng. Item relationship graph neural networks for e-commerce. IEEE Transactions on Neural Networks and Learning Systems, 33(9):4785-4799 2022.
Luan, C. Hua, Q. Lu, J. Zhu, M. Zhao, S. Zhang, X. Chang, and D. Precup. Revisiting heterophily for graph neural networks. In Advances in neural information processing systems, volume 35, pp. 1362-1375, 2022.
Q. Lv, M. Ding, Q. Liu, Y. Chen, W. Feng, S. He. C. Zhou, J. Jiang, Y. Dong, and Tang. Are we really making much progress? Revisiting, benchmarking and refining heterogeneous graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD '21, pp. 1150- 1160, 2021.
12

---

Published as a conference paper at ICLR 2025
P. Vandergheynst M. Defferrard, X. Bresson. Convolutional neural networks graphs with fast localized spectral filtering. In Proc. of the 29th International Conference on Neural Information Processing Systems, 2016.
K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
A. Ortega, P. Frossard, J. Kovačević, José M. Moura, and P. Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808 828, April 2018.
Mathilde Papillon, Sophia Sanborn, and Nina Miolane Mustafa Hajij. Architectures of topological deep learning: A survey of pessage-passingg topological neural networks. arXiv:2304. 10031, 2024.
H. Pei, B. Wei, K. Chang, Y. Lei, and B. Yang. Geom-GCN: Geometric graph convolutional networks
In International Conference on Learning Representations, 2020.
Lutz Prechelt. Early Stopping - But When?, pp. 53-67. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
Y. Rong, W. Huang, T. Xu, and J. Huang. DropEdge: Towards deep graph convolutional networks node classification. In International Conference on Learning Representations, 2020.
T. Konstantin Rusch, B. Chamberlain, J. Rowbottom, S. Mishra, and M. Bronstein. Graph-coupled oscillator networks. In Proc. International Conference Machine Learning. 2022.
C. Shen, J. Luo, and K. Xia. Molecular geometric deep learning, 2023.
D. Shuman, S. Narang, Frossard, A. Ortega, and Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Processing Magazine, 30(3):83-98, 2013.
D. Singh and B. Singh. Investigating the impact of data normalization on classification performance. Applied Soft Computing, 97, 2020.
A. Subasi. Practical Machine Learning for Data Analysis Using Python. Elsevier Inc., 2020.
S. Suresh, V. Budde, J. Neville, P. Li, and Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD, 2021.
J. Topping, F. Giovanni, B. Chamberlain, X. Dong, and M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. International Conference on Learning Representations, 2022.
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio. Graph attention networks. In Proc. International Conference Learning Representations, pp. 1-12, 2018.
C. Villani. Optimal Transport, Old and New. Springer, 2009.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra. Two sides the same coin: Heterophily and oversmoothing in graph convolutional neural networks. IEEE International Conference on Data Mining, 2022.
R. Ying, R. He, K. Chen, Eksombatchai, W. Hamilton, and Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 974 983, 2018
Zargarbashi, Antonelli, and A. Bojchevski. Conformal prediction sets for graph neural networks. In International Conference on Machine Learning, 2023.
Y. Zhang, S. Pal, M. Coates, and D. Üstebay. Bayesian graph convolutional neural networks for semi-supervised classification. In Proceedings of the Thirty-Thire AAAI Conference on Artificial Intelligence, 2019.
13

---

Published as a conference paper at ICLR 2025
K. Zhao, Q. Kang. Y. Song, R. She, S. Wang, and W. P. Tay. Graph neural sanvectionddiffuiinn with heterophily. In Proc. International Joint Conference on Artificial Intelligence, Macao, China, Aug 2023.
L. Zhao and L. Akoglu. PairNorm: Tackling oversmoothing in GNNs. In International Conference on Learning Representations, 2020.
14

---

Published as a conference paper at ICLR 2025
A LIST OF NOTATIONS
For easy reference, we list the most used notations Table
Table 5: List of notations
Graph, Vertex set, Edge set
G (with subscripts), V, x² "",y", v
Features and vectors
Nodes
A set of coordinates
I (with subscripts)
A set of label classes
C
Label classes
с (with subscripts)
The set of nodes belong to a class
De
Size of De
The
Probabilistic centroid (of class c)
ee
Geometric centroid (of a class c)
9e
Convex hull
conv (-)
Simplex
A (with subscripts)
The probability simplex
Ac
The feature centroid simplex and its proxy
Des Ag
Aggregated feature
ye
1-hop neighbors, neighbors of class
Nu, Nv.c
Mixed centroid
eN.
Neighborhood class label probability distribution
Pb
B THEORETICAL DISCUSSIONS AND PROOFS
To make Lemma precise, we consider the following specific models for each Ye-
For each class e e C, we assume that there is set of class-specific coordinates Te of 1. such that the following holds:
(a) Let Se be the subset of Th consisting of vectors (II, Inm" ) such that x, = if $ Je and æy (0, 1] if j Te. There is probability distribution 7e Se such that features of class e nodes are drawn independently from S, according to Te-
(b)
There is an my such that if e1 * c2, then [Je, Joyl S m1.
(c) There is an m2 m, such that for each c, Jal 2 m2-
The range [0, 1] is adopted without loss of much generality since component of feature often represents a probability or a correlation. Most applications also have bounded feature component values, which can be normalized to be within [0, 1]. For many datasets (e.g., those in Appendix D.I), the components of each initial feature vector are always either 0 or 1.
Model
For each feature x belonging to the class e and each axis index E Te: the i-th component I; of z follows the Bernoulli distribution with parameter Pc. independently for different i.
Model For each i Te, 2; follows continuous distribution on [0, 1] with density bounded by b. which is independent of c. For different i, the continuous distribution are independent but possibly non-identical.
15

---

Published as a conference paper at ICLR 2025
For example, the first model is used for features in datasets such Cora, Citeseer, Pubmed, while the second model is used for word embedding features and pixel values for CV. We can now state and prove the precise version of Lemma 1 as follows.
Lemma 5. There is B < 1 that depends on b while is independent of m, such that the following holds: the probability that F {x² ..... x") are not in convex position is at most nB / VT.
Unless nt is much larger than m2g the features are in convex position with high probability.
Proof. For Model 1, each feature is a vertex of the m-dimensional hypercube [0, 1lmh, which is a convex set. Therefore, F' is always in a convex position.
For Model 2, suppose xº is in the convex combination of F' C F. Then we may assume that rd and F' belong the same class c, for otherwise, x² is the convex combination of the form r EeeF Qz2, > O. For some x² and x belong to different classes. However, this is impossible as follows. Recall that each component of either æ or x E F is non-negative. Since < m22, there is an index such that either u!. or Iı is zero, but not both. This is contradiction.
Therefore, we have at most i.i.d. vectors belonging to an mg dimensional subspace of RT" Accord- ing to the model for Tes such probability is at most n n. (for some B < independent of m, n) by Gorban et al. (2018) Example and Theorem 2. This proves the lemma.
Lemma 2 follows essentially from concentration type of inequalities, while Lemma 6 below is due to the additional assumption on the feature model.
Proof of Lemma 2. We form independent random vectors y² = x² ee. As each component of y is in [-1, 1]. B(Ib>*|13) o² < co. The result follows now from the vector Bernstein inequality (Kohler & Lucchi, 2017, Lemma 18) applicd to {x/) with K = 1/80².
For different classes c, c', lower bound on l|e.- Ee' tells how different classes are separated away from each other. We have the following observation regarding this.
Lemma 6. Assume that there a universal lower bound b' on the mean for each non-zero component (in To) of all classes. Then l|ee ee'l || 2 (2m2 2-2)) Moreover we have P P(lge ge' S (2m² 1/26 28) S exp(-K (ne + n²)6² + 1/2).
Proof. By our assumptions on Te and Ter, for vectors e. ect, there are at least 2m2 2mm non-zero entries. The absolute value of each such entry is at least b' Therefore, ||ee-ee! 6ee 2 (2m2 2m, ) The second half follows from Lemma and the triangle inequality.
We next show that vertex e-quasi isometry implies e-quasi isometry of simplexes.
Proof of Lemma 3. The following notations are used exclusively for this proof for convenience. We prove the lemma by induction on the number of vectors k. for two sets of vectors {z1, 2k} and (2/,.... 21, that are the vertex e-qusi isometric. Let A = conv(fz)...... 2x1) and A conv(({),.....4//
The case k = 2 is trivial. For h: 3, consider W1, w2 E A. It suffices to show the case when W1, W2 are on two different sides of the triangle A. For otherwise, we can always find a (smaller) triangle in A such that W1, we are the two sides. Then without loss of generality, assume that wi azı + (1 a)æ² and W2 = b21 +
(1 - b)23 for some a 2 b. Let the corresponding vectors in
A be w/ and w³. Hence,
[[ W2) (w( w1)'l
=II(a- 1)((2 - -2a) - (z) - =-) + (1 ((2 - 23) - (2/ 25))
<(a - b)1 - -2a) - -(s =1-il + (1 - a) a))l(z - 2a) - (2/2 24)l
<(a b)c + (1 (1-a) -)ac = -11- b)c <.
Notice that this implies the conclusion of the e-quasi isometry (by the triangle inequality). hence have settled the case k 3. Assume the claim holds for 2, 2,..., k and consider k + 1. For
16

---

Published as a conference paper at ICLR 2025
102
W1
281
Figure 6: An illustration of the points W1, 91, P2. P2, 24, 242-
WI, u2 A, we can always find a triangle with vertices (21, qı, 42) with qı, da the face A conv( 1++1)) }) of A such that the following holds (illustrated in Fig. 6):
Both and are on A1.
w1 is on [91, 21] and we is on 142, 21). Hence, wy (resp. W2) convex combination of @1, 2i (resp. 21).
Φ1 is on a line segment [zi, Pi]. where 2 S 1 I + and p1 is in proper faces of A1- Therefore, pl is convex combination of most k vertices of A zi is missing. The same holds for Q2 on a line segment [Z:g] P2). 2 < i2 < +1
Correspondingly, we have w1, wyy 41 d2. p/. P2,, 2/,, 2/1 in A with the exact same convex combina- tion coefficients. To conclude [|(w] W2) - (wl w/)1 || S e, suffices to successively apply the induction hypothesis to
The proper face of A (resp. A') missing 2i, (resp. missing o4,) and the proper face of A (resp. A') missing 2ig (resp. missing 2/x)) to obtain
[1(2: Pi) (21 -1iill e, I1(2 P22 (21 ---))l sc.
The triangle conv(1E1, P1, 21,)) (resp. conv((zi, 2f, H)) and the triangle
conv(f21,P2 P2, Zi, H) (resp. conv 2 p/2, 2 })) to obtain
[ Q1) (21 Till e, (1(21 42) - (2( %/)l S
The proper face of A (resp. A') missing 21 (resp. z1} obtain
ll(mn 92) (dl . S
The triangle conv((=1, n1, 423) (resp. conv(1z(, &i 121))) to obtain
[1(w1 w2) - (wi w/)il S
The lemma is proved.
We ready prove the main results of the paper.
17

---

Published as a conference paper at ICLR 2025
Proof of Theorem 1. For (a), recall No.e is the set of neighbors of o whose label is We estimate 1 ex. as follows (notice terms with [Nv,el = are ignored):
Nu,el
11
ex.
1Σ
Cc
Σ
x²1
Nool
N
OEC
CEC
Nowel
llee
Σ
x²11)2
[Nol
I.Nocel v.ENo,e
cEC
NN.cl
NNeccl
lee
Σ
x'112) by Cauchy-Schwarts
[Nvel
[AVel
|Nueel N.No
EEC
No.el
1
|lee
x²11?
[N
[No.el
aEC
v.E.s.c
We apply Lemma 2, there is a K independent of v such that
P
llec
Σ
x'1l S
8|Nol
) 1/2
[Ne.cl
NNa.cl
5//vol
21 - expe - K No,,ell
+ 1/4)
|.Nc.el
=1 - 6 + 1/4).
Therefore, with probability at least - e1-exp(- -K8]NN +
1/4))|C we have
N
N
11 1N.
|C|6.
N₂
Ne.el
cEC
This proves the claim.
To prove (b), suffices to prove 1 2 rdu.e c, and then the claim follows from (a) by using the triangle inequality. By Lemma the condition on the vertex e-quasi isometry implies that A Re A. Let u A be the vector that corresponds to EN, E Ae. i.., u = E.ec As A is regular simplex of size length r, |/u uell = rdv.c/ /2.. This can be derived from the probability simplex, which is a regular simplex side length v2. By c-quasi isometry, we have lle, - ex. 2 Iu uell - = rdv.e/ /2 - e. The result follows.
[N [N.l ue-
Proof Theorem 2. Let Vi (resp. V22 be the subspace of the feature space spanned by fee |e C) (resp. (zele E C)). Recall the vertex of the probability simplex Ac in BlC is {pele C). We define linear transformation In RCI + Vi induced by Pe H eay E C. Similarly, define L2 | + V/ induced by Pe + Ze, C. Let o (resp. Ø2) be the least singular value of Li (resp. 02). Order by cI...., Cr, |C]. then the columns of L1 (resp. L2) are {eo....., (resp.
{Ze, :......,24 }).
As A = c(0v((0) U (2e E C}) an (r1, r2) 1..rr2)-rguu regular simplex, up to rotation, A can be positioned
as follows:
In V2, first form A' {>/ c C}. where each 2/ on a unique (positive) coordinate axis with the only non-zere coordinate Tı n1/22.
Z is the unique point placed below A' such that conv 2 e cCC) is (ri,sa)-regulat
A = conv(1z 2' c.c.e. C}) 26-
Notice that rotation does not change the size of the determinant and singular values of Lz. For the above special A, the determinant of Tag has size vol(A) A) and singular value of Tug is either Vi:
18

---

Published as a conference paper at ICLR 2025
(whose eigenvector is or (vol(A)/(r2v 1/(k-1)
Recall that the volume of A
Vkr 1-nk-11p rr2
vol(A)=
klv 2k
Therefore, the constant p(r1, r2) is the least singular value d2 of L.2-
Let Eisisi aiPe, * 0 be vector in V1 that realizes of L1, i.c. Σisig o = and
(p)]l 01. By the Cauchy-Schward inequality, t Eigigi lasl satisfies 1at I |C| and
hence S vcl.
Assume without loss of generality that .1...... and ak+1,...,,0 aa < 0. We estimate
7
1
01
= -
-1
Σ
L, -
a,
Σ
a
Isis
ISiS!
-11
Σ
Σ A+siS
Oj
eeyll
t
t
IsiSk
As Eisieh f conv( (0) feeIce C}). By vertex c-qusi isometry of (0) feelce CJ with (2) CE C}.
di < and ExHisis 41
< 1, both vectors Eisich ee and Estis e are in
we have
a; ee
Σ
Eel
|
Iiick
k+ISiS!
211
des
Σ
2g
-
1SiSk
k+1SiSi
-
[(2(1111 - 02 -.
Therefore, we have
01 2 02 -2 le 2 02 vlcl = p(ri, (2,,) 0.
This implies that L, is invertible and the operator norm ||, is bounded by p(ri, r2, e). We finally define be I, on V1 and on the orthogonal complement Vi.
ey class [(xx))/nn It is now easy to prove the two claims. For (a), it is easy to verify that Te 1E Hence,
Ilp. - Tell = (ee)) - L(ga)l S p(r,, T2, e)lle - gell- Therefore, (a) follows from Lemma 2. Similarly, for (b), have
[(y))) - vmlll = [y()) [(ex))l S p(ri, r2, r2, e)l ex.
The claim in (b) follows from Theorem 1.
Proof of Corollary Let the vectors in A that corresponds to ex, and ët., be u and respectively. As the simplex A is degenerate, we have w. Therefore, by the vertex e-isometry and Lemma 3, we have llen_ EN,.l || S e. The corollary follows immediately from Theorem 1 (a).
Proof of Lemma 4. To show M is stochastic, we compute for each C:
No,.e
IN [N
IN
Σ Ea.e= Σ Σ d'EC'
Σ Σ WED, dEC
Σ 1-1. The
The DEED
[No.1
Tee
C'EC
mEDD
As each node has a self-connection, M aperiodic. For any proper subset C" of C, the set of nodes Use D. has some neighbors whose class labels do not belong to C'. For otherwise, the proper subset Ucec 2 a union connected components of G, which contradicts the assumption that G is connected. This implies that any (C),"") x C' subblock of M contains some positive entries. Therefore, M is irreducible. Being aperiodic and irreducible, M has a unique stationary distribution (see Lalley (2016)).
19

---

Published as a conference paper at ICLR 2025
C
RELATED WORKS
The proposed tricks The tricks proposed in Section 5 belong to the following generic categories of machine learning techniques: rewiring, early stopping, and feature normalization. However, different research works propose different realizations of the above categories of machine learning techniques. The theoretical motivation and the explicit procedure differentiate approaches belonging to the same category.
For "rewiring". DropEdge (Rong et al., 2020) proposes to randomly drop a fraction of edges in each iteration to alleviate the side-effects of oversmoothing. Bober et al. (2023) proposes to add or remove edges to change the graph curvature for issues such as over-squashing. random edge removal at estimated class boundaries (relatively) enhance intra-class connectivities. In contrast to these earlier works, we propose rewiring by adding edges to reduce feature variance. The trick is derived directly from our theoretical findings as discussed in Section 5 (see the subsection on Simple tricks (1)).
et al. (2023a) considers
"Farly stopping" is usually used to reduce overfitting (Prechelt, 2012) or a regularization in boosting (Jiang, 2004). In our paper, we propose extremely early stopping (for heterophilic graphs). It is based on the idea that we want to prevent the aggregated features of training nodes from fitting to their respective label classes, which is unlike what people usually do. This is because the aggregated features are likely be close to the mixed centroids as we have discussed Section 4.
For "feature normalization". people usually do so in general machine learning for model stability and efficiency, and to standardize different scales when features are measured (Singh Singh, 2020; Subasi, 2020). For GNN, for example, Zhao & Akoglu (2020) (the PairNorm model) proposes post-processing normalization layer in terms of the total pairwise squared distance introduced the paper, to alleviate oversmoothing, However, initial feature realization is rarely implemented in GNNs, We propose doing so for the very specific reason reshaping the simplicial complex Dg (supported by Theorem 2 and Corollary 1).
Geometry and GNNs Recent works have used more complicated topological and geometric tools to model node correlations or to capture hidden structural network information. For example, Horn et al. (2022) applies topological data analysis retrieve global topological information such as the number of cycles to enhance GNN expressiveness. The survey Papillon et al. (2024) contains a comprehensive overview of models when graphs are replaced with more complicated and expressive structures such as cellular complexes and hypergraphs. On the other hand, Han et al. (2024) on geometric graph neural networks summarizes approaches given additional geometric information such as explicit locations of nodes in a 3D space. They put emphasis on geometric invariance and they are particularly useful for bio-chemical datasets. Unlike these works, our theme on the geometry of the features instead of the network structure. Hence, though geometric and topological tools are employed, the subjects of study are different.
D DATASETS AND IMPLEMENTATION DETAILS
D.1 DATASETS
The following datasets are used and studied at various places in the paper (including the appendices): Cora, Citeseer, PubMed, Ogbn-arxiv, Texas, Cornell, Wisconsin, Chameleon, Squirrel, Actor, Penn94, arXiv-year, and genius (see Lim et al. (2021)). Their statistics are shown in Table 6.
D.2 HYPERPARAMETERS
There are two hyperparameters used in the tricks in Section 5: for the edge addition probability and for the number of epochs in training. They are tuned according to the following general procedure. For 7). we will first consider 1 1, O.5, 0.2, 0. 0.001, 0.0001 and then fine-tune around one of these values using the validation set. We also keep track of the number of edges as a useful reference when tuning, graphs for different datasets may have large difference in edge size. For example, the Texas graph has only 295 edges and an average degree xs 3.2 while the Squirrel graph has 217k edges and average degree of 83.5.
20

---

Published as a conference paper at ICLR 2025
Table 6: Dataset statistics
Dataset
Nodes
Edges
Classes
Node Features
Data splits
Cora
2708
5429
7
1433
standard
Citeseer
3327
4732
6
3703
standard
PubMed
19717
88651
3
500
standard
Ogbn-arxiv
169343
1166243
40
128
standard
Texas
183
295
1703
48%/32%//00%
Cornel
183
280
5
1703
48%/32%//204
Wisconsin
251
466
5
1703
48%/32%//20
Chameleon
2277
36101
2305
48%/32%/20%%
Squirrel
5201
217073
2089
48%/32%//0%%
Actor
7600
33391
5
932
48%/32%//0%
Penn94 41554
1362229
2
4814
50%
arXiv-year
169343
1166243
128
0096/5%//55%
genius 421961
984979
12
50%/25%//25
For the number of epochs, let & the number of epochs of the base model (Eg 1000 for CDE and GloGNN and = 200 for other base models). We consider & = E,/20, & 10, 8,/ E and then fine-tune around one these values.
D.3 IMPLEMENTATION
The tricks are simple and thus straightforward to implement. The source code to reproduce our re- sults can be found at https: /tpp:///gthhut com/Ya wwtm/aananZhaaol0 23300000/000///// 5300M-30--------0--00A M-AE-MMAAB (base model: ACM-GCN). Experiments are performed on workstation with single NVIDIA GeForce RTX 3090 GPU and 24GB memory.
E NUMERICAL EVIDENCE AND DISCUSSIONS
In this appendix, we provide numerical evidence with discussions to support various claims of the paper.
E. CHOICE OF THE MODEL FOR ANALYAIS
In Table 7, we show results from different variants GCN on Cora and Citeseer datasets, to justify our choice of single-layer convolution without ReLU for theoretical analysis in Section 3.
Table 7: Test accuracies of GCN variants Cora and Citeseer (C: Convolution layer, R: ReLU)
CRCR
CRC
CC
CR
C
Cora Citeseer
71.7% 63.7%
80.3% 70.8%
81.1%
77.9%
77.6%
71.8%
66.7%
68.4%
E.2 THE SHAPES OF Ag
In Fig. we show the pairwise Euclidean distance {go E C'} for all the datasets Appendix D.I. In addition, we also show the distance from each ge to the origin (cf. Theorem 2).
From Fig. 7, we may have a rough estimation how each A, deviates from regular simplex. This is measured by pair (c, such that Ag vertex c-quasi isometric to regular simplex of side length r. For simplicity, we compute the proxies (maxa, min )/2 and (maxa, + mins,) )/2 for and respectively, where maxa, (resp. mina,) the maximum (resp. minimum) among all pairwise
21

---

Published as a conference paper at ICLR 2025
Citesear
Closa
1:tra
1,314
3 81-18
12:11
1.07
1.003
Clos
1,042
1.255
277
1:16
1.701
1,423
Class 2
06003
1.02
1.115
1.292
1.127
1.311
Clacs
1:166
1.938
.66
1.661
1.194
1211
Clsse
Class
1.020
1.359
1.100
Class
Class 5
1.07
1.282
1,312
1.559
0
1.178
1.55
0.5
04
Cbos?
Orign
1:44
1.453
1.207
c06
1:112
220
1.20
Crigin
1.243
1.341
1.352
1,409
1.53
1.521
Class
Cless Closs
Glas
Cleas
Chas?
Orgin
Class
Clans
Class 3
Clans
Class
Clsse
Origin
Toxas
Comell
Class
152
838
3.534
3.539
5.087
Class
4.152
3.672
2,583
2.84
4.95
Glass 3
8.892
2,805
3,107
466
3.886
Class
3.797
2,805
2.529
5.066
3
Class
3.634
2.683
3.886
0
2.984
4.892
5.627
3.639
2.084
Origin
6.1 6.199
4 8688
6.086
B.627
0
Crigin
0.087
4.95
6.209
1.882
3.832
Class 1
Class
Class
Class
Origin
Claso
Clan
Clasa
Clave
Glass
Origin
Wisconsin
Chameleon
Uless
U
5,849
2.80
5.248
33.78
4.88/
Cleas
1.939
0.2676
0.678
0.663
0.0751
Glass
5,049
4.148
72724
4.663
5.726
5
Cicas
0.130
0.2841
0.5638
018404
111000
0.4
Class
5.248
5.724
4.208
4.792
6.871
Class
0.578
00.9636
0.5088
9
0.67
3.5851
0.8
Class
3.516
3.172
4.792
Class
863
8484
1.181
0.57
0,8716
Oriann
1.807
5.728
4.800
6.871
4.618
Origin
Clars
Clars
Clans
Class
Class
Origin
Closs
Glass 2
Glass
Cless
Cless
Origin
Squirrel
Cless
0
0.2379
0.3801
0.E231
0.784
0.28
Class
0.2154
0.2819
0.38824
0.4522
0.7232
Glea
0.2579
0.2601
0.8911
0.6883
0.4273
Class
0.2154
0.1186
0.1808
0.3344
80000
0.8
0.3801
0.9338
Class
0.5231
0.3911
0.2741
0.3999
0.7384
Class
0.8624
0.1892
0.1136
0
0,2211
0.9977
Cless
0.794
0.8583
0.512
1.008
0.4699
0.3344
0.2788
0.2211
1.00
0.2
Origin
0.28
0.4273
0.5921
0.7384
1.008
Crigin
0. 0.7232
0.8828
0.6338
0.98777
1.02
Clasa
Clase
Clase
Cless
Clasa
Orignn
Clasa
Closs
Class
Closa
Class
Origin
Figure 7: The pairwise distance of {ge c C} for all the datasets. For the Texas dataset, class is omitted as there is only 1 node from class 2. The last row/column contains the distance of each gr. to
vertex distances of Ag. In Table 8, tabulate their ratio proxy for c/r. The smaller its value is, the more regular the shape of Ag is.
We that for Chameleon. Squirrel, and Actor, the estimated is 0.5 or larger, which indicates their A, 's are much less regular. Moreover, from Fig. we can sketch the shape of each A, From the illustration in Fig. 8, each Ag has sides with relatively small lengths or side triangles with small
22

---

Published as a conference paper at ICLR 2025
Table 8:
The estimated value for each dataset.
Cora
Citeseer
Texas
Cornel
Wisconsin
Chameleon
Squirrel
Actor
0.174
0.255
0.177
0.236
0.342
0.653
0.494
0.599
areas. Therefore, they resemble degenerate simplexes discussed in Section 3.3. This explains why GNN models generally perform poorly on these datasets by Corollary
A more general notion of degeneracy (as compared with that defined in Section 3.3) is that some ue belongs to the convex hull of (ue' c' & c) (this notion describes better the shape of Actor). Ag c-quasi isometric to a degenerate simplex in this sense, then similar to Corollary 1, it will be hard to identify a feature, that corresponds the label class c, unambiguously.
Chameleon
Squireel
Actor
gcz
96
9c
ges
9e.
9ca
grs
9c3
9ez
Figure 8: We show the illustrations of part of Ag for Chameleon, Squirrel and Actor datasets. For visualization, we can only show the tetrahedron formed from vertices.
We offer plausible explanation of the above phenomenon on the shapes of Ag. For each dataset, we compute and tally in Fig. 9 the 1-norm (i.e., number of non-zero components) of the original feature of each node. From Fig. 9, we see that for Chameleon, Squirrel, and Wisconsin, node feature sizes are much smaller than those of other datasets on average. Consequently, centroids can very close to and hence close to each other, as observed in Fig. 7. Intuitively, this suggests that for these datasets, the features are not sufficiently expressive.
E.3 THE USEFULNESS OF KNOWING 14v
To numerically verify the discussions following Theorem 2, we consider thought experiment by assuming that (4, of each v is known (caution: this is hypothetical and the information is unavailable in the actual problem). Let vy the output label distribution a GCN model. We add the regularization term -2_ Evevl I| pel to the loss & of the model, where 7) is the regularization weight. We vary Vn
and the test accuracies are shown in Fig. 10. From the results, we see that the regularization term indeed plays dominant role. Moreover, 1-layer GCN is better than 2-layer GCN. This is due to that 1-layer GCN considers exactly the 1-hop neighbor of each node. The observations indeed verify the conclusion of Theorem 2 (b). Of course in theory, if the normalized adjacency matrix is invertible, then knowing the ground truth label of each node equivalent to knowing fh for each node.
E.4 AGGREGATED FEATURES AND CENTROIDS
To understand the relation between node features and centroids, we perform the following study. Fix a label class c. We randomly choose nodes from each class and find the distance from their average features to 9c- This process is repeated for 60 instances. In addition, for the class we also obtain results for the average over 10 random nodes and over 20 random nodes. From Fig. 11, we see that for Cora, Citeseer, Texas, Cornell, and Wisconsin datasets, averaging over nodes with label i closer to 9c- However, the same is not observed Chameleon, Squirrel, and Actor datasets. For example, averaging features of 10 random nodes with label is not necessarily closer to Je than averaging features of 5 random nodes from a different class. A possible reason is that different centroids for these datasets can be very close each other (e.g., (gez (c2) for Chameleon, (geg Dcs) for Squirrel
23

---

Published as a conference paper at ICLR 2025
100
Nodewior feuliure siune
300
Nodewibo leattre
200
20-
100
Coza
Citeseer
Tisas
Comell
Wiscomsin
180
Noclewise fealore sine
160
1-00
120
100
60
20
Squirrel
Figure The norm (i.e., number of non-zero components) of the original feature of each node.
Cora
Citesoer
0.55
2-layer GCN
Acurry
Accmooy
I-lger GCN
0188
2-bayer GON
I-byye
0.8
0.71
0.05
20
80
60
80
100
20
40
00
80
100
Regulorization weight n
Regulaciastion weight
Figure 10: regularization scheme that uses neighborhood label distributions.
and (gezs I for Chameleon for actor). The observation is consistent with our discussions regarding the shapes of Ag.
We investigate the features aggregated from a single-layer graph convolution. For each dataset, we randomly choose 50 nodes. For each choose i with label vs we compute its aggregated feature ye, and find its Euclidean distance to the ground- -ruth Je,, the mixed centroid en., and the centroid of a random wrong class. From the results shown in Fig. 12, we see that for the homophilic datasets Cora and Citeseer, the distance to the mixed centroid is almost the same as that to the true label centroid, and both are smaller than the distance to a wrong label centroid. The former observation reflects the homophilic property. For Texas, Cornell, and Wisconsin, as predicted by Theorem 2, the distance to the mixed centroid is noticeably smaller than that to the true label centroid. On the other hand, consistent with our earlier discussions Chameleon, Squirrel, and Actor, the three types of differences are all very similar, rendering classification difficult measured either in both accuracy or t,, (see Section 5).
24

---

Published as a conference paper at ICLR 2025
Corn
Cinesent
3.3-
Disaane to the panteuid
Distance to the controid
2.8
1.5
Chee
1.3
Mlas
Clamm
10
0.5
10
60
20
90
Somple mndex Texas
Sample Index Cornell
Clas Clas
9-
9.
Distamue to the octivvil
Distonne to the ccntroid
Clas Eo
10
20
30
30
00
40
50
Somple Index
Sample Index: C Chamelcon
Wisennsin
3-
Chiss
Disance to the panteud
Distance to the conrasid
2.5
1.5
0.5
10
30
50
60
10
20
90
Somple Index Squirzel
Somple dnde
Actoo
Clue
Clow
1.6
Distamue to the osiivvil
Distoane to the ccntrod
Claan
1.4
Clissa
Cllon 31 50
1.2
2.5
11.8
B.6
0.1
0.5
0.2
1.0
40
50
00
10
20
30
50
60
Semple index
Semple Index
Figure 11: Euclidean distances from average features to class centroids. We only show the results for one fixed c. Generally, similar pattern is observed for other classes given the same dataset. In the legends, ":10" or ":20" means average over 10 20 sample respectively.
E.5 ERRORS AND CENTROID DISTANCES
Our theory suggests strong (negative) correlation between test error and the distance between class centroids. More specifically, for each class G, we count the number of test nodes with ground-truth label while wrongly predicted cy. for each j # i. The results shown in Fig. 13. If we look each row, say the i-th row of the tables, then we observe the following general pattern. Entries with relatively larger error count for that row usually correspond smaller centroid distances for the same
25

---

Published as a conference paper at ICLR 2025
Cora
Citeseer
5.5
ssterd
Disause nippd
cringg
4.5
Distace
Distance
2.5
3.5
2-
1.5
2.5
20
30
50
20
40
50
Sauzpale inndess
Samppe iudex Cornell
Toxos
Lieetanee no trow babel eantoold
[Haracce boled extrnd Dinnazee mijood labed contesid Thear tn dror abot spersss
Distaaoo to pndeod Bullll pootirodd
Distance
Dist anice
10
26
50
20
50
Somple Index
Sample index
W Wisconsim
Chemeleen
10
Diottance trom babed centooid
Ttenacer true lohed cornee
Diiheany sniaed kildd cou
Dikause aiuud label cualesá)
Lostance to wronn lane contrdd
Steacee to mming abo ceatrad
Dissuce
Distance
10
30
50
20
50
Soumple iudexx
Sample indlxx
Squirrel
Actor
Literacce true bavd ouzred
Distane tiue labiel coutindd
Distacce mitddd lilled contrcal
Llatbaan to risedd hitel controd
to woong cratrekd
Didusace to warnag iabed castonid
Dist Dislance
Dist anie
M
10
26
40
50
20 Sample index
Somple Index
Figure 12: We show the distance from ye, its ground-trude label centroid, the mixed label centroid, and random wrong label centroid, for 50 randomly chosen
row (right column of Fig. 13). (Though is not true for every single instance.) This consistent with theory.
26

---

Published as a conference paper at ICLR 2025
Chameleon: pairwise
Chameleon
Class
Cleas
1.139
0.3676
0.677
0.663
0.0751
Ciass
0.130
0.2841
0.5821
018404
1.0600
Class
19
4
0.4
Class
16
15
11
3
Class
0.578
00:5636
0.5083
9
0.67
1.:881
Class
663
8494
581
0.57
0,8716
Class
10
Origin
Class
Class
Class
Class
Class
Class
Glass 2
Glass
Cless
Clsss
Origin
Squirrek pairwise error
Squirrel
Class
Class
0.2379
0.3801
0.3251
0.734
0.28
0.0
Class
0.2579
0.8881
0.3011
0,8583
0.4273
Glass
71
26
32
20
40
Class
31
30
Class
0.0231
0.8911
0.2741
0
0.3998
0.7384
20
0.6683
0.3889
0.2
Class
22
19
43
0
Crigin
0.28
0.4273
0.6921
0.7384
1.008
0
Class 1
Class
Class
Class
Class
Claso
Clan
Class
Clase
Glasa
Origin
Actor: pairwise
test
Actor
Class
120
Class
U21b4
0.28788
0.3022
0.4325
0./232
100
Class
0.2154
0.1186
0.1892
0.3344
0.88329
0.0
Class
12
80
66
Class
84
89
60
Class 0.3624
0.1892
0.1138
0
0.2211
0.9977
Class
Class
0.4622
0.8344
0.2789
1.02
20
Class
Crigin
0. 0.7232
0.8929
0.8338
0.9877
1.02
Class 1
Class
Class 3
Class
Class
Clatt
Cless
Clans
Clans
Clans
Origin
Figure 13: In the left column, we show the summary of test error for each dataset. each table, the (i,j)-th entry is the number belonging to the error type that predicts label class e class cj. The right column is taken from Fig. for comparison.
E.6 FEATURE NORMALIZATION
We analyze the normalization trick (Section 5) when applied to Chameleon, Squirrel, and Actor datasets. As the features are changed, we re-compute the resulting pairwise distance of the centroids {gele c E C) (cf. Fig. 7).
Comparing Fig. 7 and Fig. 14, is observed that the resulting Ag becomes more regular. To quantify, for the three datasets, we compute the value (cf. Table 8) and find that it reduces from approximately 0.653, 0.494 and 0.599 0.497, 0.284 and 0.592 respectively. This is consistent with the performance improvement seen in Section 5 Table 3. Moreover, notice that for the Actor dataset, the change in T is small, and so the corresponding performance improvement for the vanilla 1-layer GCN model.
In Fig. 14, we also show the distance from average features to the centroid of each class (cf. Fig. 11). Comparing Fig. 11 with Fig. 14, we see that after feature normalization, the average features of a class closer (to its centroid 9c,) than the average features of different class. The observation is more prominent for the Chameleon and Squirrel datasets, accounting for the effectiveness of normalization for these datasets.
27

---

Published as a conference paper at ICLR 2025
Chameleon
Charneleon
12
Class
0
3.214
5:222
5.205
5.132
6.888
Distance to the conroodd
Glass
3.214
853
2 883
7.975
4.369
10
Class
8,205
2.983
1.812
1.976
2.622
3
Class
6.132
2.975
1.755
1.976
0
2.637
2.512
Class
Class
Class 3
Class
Class
Origin
20
Sample index Squilrel
Squirral
11
Class
0
1 353
1.62
1 7164
1.705
3 .444
10
Distonne to the ccntrol
Class
1.353
1.061
1.13
1,289
2.88
2
Class
1.784
1.13
0.9841
1.089
3.112
Class
1.706
1.289
1.163
1.099
0
3.498
8.444
8.001
3.112
3.498
Class
Class
Class 3
Class 4
Class
Origin
10
20
50
Sample Itdex
Actor
Actio
Class
0
1.b1b
2.036
2.349
3.149
8.119
Distance to the conresid
Class
1.515
1.168
1.697
2.96
9.079
10
Class
2.349
1.597
0.8072
1.818
8.357
Class
3.149
2.96
2.338
1.818
0
7:277
8.519
8.079
8.718
8.357
7.277
Class
Class
Class
Class
Class
Origin
10
20
40
Sample index
Figure 14: We show the pairwise pairwise distance of Jc, E for the datasets after normalization
(cf. Fig. 7). Moreover, we also show figures analogous to Fig. 11 after normalization.
F MORE RESULTS
F.1 RESULTS ON MORE DATASETS
Homophilic graphs In Table 9, we show the classification results for homophilic graphs. The proposed tricks generally improve the performance base models. However, the tricks have stronger impact on the heterophilic datasets.
For the Ogbn-arxiv dataset, we see that the best accuracy among all models is R 60%. According to our discussion, the dataset is likely to be intrinsically difficult by having an almost degenerate A,. We verify that this is indeed the case, as its estimated 7 value (cf. Table 8) 0.67. Based on our discussion in Section 5, the normalization trick might be useful to enhance the performance, and it is indeed true as shown Table 10.
Large scale non-homophilous graphs In Table 11, we show the node classification results for a few large scale non- non-homophilous graphs introduced in Lim et al. (2021). We use the model LINKX proposed in Lim et al. (2021) as the based model and apply jointly the edge addition and early stopping tricks described in Section 5. We improvement in the test accuracy for each dataset.
28

---

Published as a conference paper at ICLR 2025
Table 9: Node classification results(%) for homophilic graphs. "-I" and "-II" stand for and 2 layers respectively, For the base models, we use directly the source code and data split by the respective authors. Suffix "-AE" is for the models with edge addition and early stopping tricks.
Method
Cora
Citeseer
PubMed
Ogbn-arxiv
GCN-I
75.64.10.33 70.66:10.84
16.97.10.18
42.54.10.88
GCN-I-AE
76.29=00.37 71.03+0.72 77.00+0.15
1.23
GCN-II
80.95+0.441 70.91+0.48
79.29+0.23
37.72++0.55
GCN-II-AE
81.19=0.69
71.32+0.24
79.96#0.25
44.72=10.40
GAT-I
63.50=+0.3
54.98+4.30
66.5443.17
52.02=+1.46
GAT-I-AE
64.48+00.64 57.18+2.33
69.7444443
1.02
GAT-I
73.44::2.50 67.82:1146 75.99:10.98
53.40:1..36
GAT-II-AE
73.73:12.21 68.36:10.52
16.12.10.68
53.63:10.51
ACM-GCN
84.19:10.02 75.42.10.02
89.0711.02
58.8411..0
ACM-GCN-AE
84.63-10.01 76.95.10.02
90.30.1..01
59.01
GraphCON
87.44:1 10::2.33.
87.20+0.88
60.43 1,21
GraphCON-AE
87.91 75.41:12.02
87.38 10.66
60.67
0.72
CDE
83.80 73.45
89.8011.28
OOM
CDE-AE
83.88++0.88
73.72+11.72
89.85
0OM
GloGNN
86.22:1.17 1.8
87.79+0.22
60.00:10.33
GloGNN-AE
86.52+1.23 16. 87.97=0.226 00.24
Table 10: Normalization (suffix: "-AEN") is applied to ACM-GCN for Ogbn-arxiv.
Method ACM-GGN ACM-GCN-AE ACM-GCN-AEN /% over MM
Ogbn-arxiv 18.8411.00 19.01
66.6320.48
13.2%
Limited feature information We study the performance of our proposed tricks for small feature sizes by randomly removing fraction of features. We choose the best base model ACM-GCN and consider retaining 1/2, 1/4, 1/8 feature dimensions. The results are shown in Table 12 and we see that our proposed tricks generally improve the performance.
Table 11: Node classification results(%) () for large scale non-homophilous graphs. Suffix "-AB" is for the model with tricks.
Method
arXiv-year
Penn94
genius
LINKX
54.05-10.36
83,79 84.56=3.69
90.5411.22
LINKX-AE
62.60+0.21
94.6110.11
Table 12; Node classification results(%) if fraction of feature dimension is retained.
Feature dimension
Full 1/2
1/4
1/8
Chameleon
ACM-GCN 71.2948.06 61.95+7.11 52.70+5..36 44, 1743.77.
ACM-GCN-AEN
75.2219.99
63.5347.37 56.0911..66
46.07
Squirrel
ACM-GCN
55.07=8.96
49.6747.43 42.1011.08 36.27+2.72
ACM-GCN-AEN
19.47+11..11 50.49+7.81
44.10+5.99
37.67+2.38
Actor
ACM-GCN
37.28+2.76 33.7442.34 31.32+1.67 26.89+0097
ACM-GCN-AEN
47.6216.38
35.09 32.3311.53 29.2310.85
29

---

Published as a conference paper at ICLR 2025
F.2 CONFORMAL PREDICTION
As we have argued in Section 5, we may consider estimating the neighborhood label distribution pe of each node as an alternative objective. We have seen that the tricks proposed in Section 5 improve the estimated pey for Texas, Cornell, and Wisconsin datasets. We have also provided possible reasons regarding why improvements are not seen for Chameleon, Squirrel, and Actor datasets.
On the other hand, conformal prediction for GNNs has recently drawn much attention (Clarkson, 2023; Zargarbashi et al., 2023; Huang et al., 2023). In a nutshell, it removes each class with very small predicted probability, based on a calibration node set. We view each removed class as "noise", and thus conformal prediction is viewed v, let V, be its predicted probability. regarding as a finite set of weights. We apply the simple scheme in Angelopoulos & Bates (2021, Section 1) remove small weights in Ve, using fraction of the validation set as the calibration set. The remaining weights are normalized to give V/,- We evaluate by computing E. = ||v6 pell II (against
denoising process. More specifically, for each test node
|| - polli).
From the results in Table 13, we see that conformal prediction indeed achieves the desired denoising effect for Texas, Cornell, and Wisconsin datasets. Consistently, for the difficult datasets Chameleon, Squirrel, and Actor, conformal prediction has minimal effect.
Table 13:
The conformal prediction results.
Method
Texas
Cornell Wisconsin Chameleon Squirrel
Actor
GCN-I
0.6874 0.7286
0.7204
0.7360
0.6240
0.9044
GCN-I-C
0.7281
0.7260
0.7423
0.9846
0.8718
0,9160
GCN-I-AE
0.6181
0.6482
0.5634
0.6934
0.5834
0.8877
GCN-I-AE-
0.5886
0,5952
0.5328
0,9671
0.8834
0.9098
F.3 MORE RESULTS ON AVERAGE b,,
In Table 14, we observe that the 1-layer GCN (GCN-I) indeed generally has the smallest average fv. which agrees with what the theory predicts. This is because other eventual GCN models essentially change the graph structure and each Ve is expected to be similar to the neighborhood label distribution in the new graph. As observed in Section 5, GCN-I-AE generally improves the metric of average ty
Table 14: The results on average l, for different models
Method
Texas
Comell
Wisconsin Chameleon Squirrel
Actor
GCN-I
0.6874
0.7286
0.7204
0.7360
0.6240
0,9044
GCN-I-AR
0.6181
0.6482
0.5634
0.6934
0.5834
0.8877
GCN-II
0.7803
0.7435
0.7842
0.8899
0.7323
0.9550
GCN-II-AE
0.8182
0.7161
0.7218
0.8337
0.6961
0.9322
GAT-I
0.6686
0.6726
0.6975
1.0335
0.8966
0.9774
GAT-I-AE
0.6642
0.6598
0.6707
0.9090
0.8784
0.9156
GAT-II
0.7669
0.7652
0.7989
1.1305
1.0255
1.0305
GAT-IIAEE
0.7229
0.7051
0.7235
1.0605
1.0213
0.8668
ACM-GCN
0.6702
0.6596
0.8062
1.0791
0.8308
0.9736
ACM-GCN-AE
0.6567
0.6788
0.7894
0.9760
0.7685
0.9214
GraphCON
0.7697
0,7890
0.8296
1.1419
1.0386
0,9804
GraphCON-AE
0.7337
0.7200
0.7879
1.1161
1.0297
0.9614
CDE 1.2348
1.1720
1.1424
1.2093
1.1140
0.8412
CDE-AE
1.2153
1.1676
1.1361
1.2078
1.1138
0.8374
GloGNN
1.6223
1.3085
1,4972
1.1801
0.9598
1.0368
GloGNN-AE
1.6397
1.3045
1.5049
1.1648
0.9561
1.0285
30

---

Published as a conference paper at ICLR 2025
Softmax
(0
(1.0,0)
(0-1.0)
Figure 15: An illustration of the effect of softmax function.
G LIMITATIONS
The framework provides insights into theoretical explanations for various GNN phenomena and enhances our understanding of the mechanisms and fundamental limitations of GNN models. Given a dataset, we aim and numerical results show that the quasi-isometric shape of the feature centroid simplex useful in distinguishing between easier datasets (e.g., Texas) and more challenging ones (e.g., Actor). However, we have not yet proven that any numerical invariants associated with the shape can provide guaranteed error (lower) bound, such the Bayesian error, for any GNN models. This will be subject of further investigation in future work.
the framework to rigorously assess its hardness quantitatively. Our theoretical
Technically, the reliance of our framework on node features faces challenges when there are few useful features. For example, this occurs for many graph classification tasks (see Table 15), where the graph labels largely depend on the graph structure. For such task, our proposed framework does not immediately give an insightful understanding of the dataset. A possible solution is to apply the framework conjunction with position encoding of the nodes as features.
Table 15: Graph classification results(%). The base models are GIN (Xu et al., 2019) and PANDA (Choi et al., 2024). We apply the only relevant trick for classification: feature normalization (suffix:"- N"). We observe slight improvement over the base model, which prompts further investigation is needed to understand how our framework might be adopted for graph classification.
Method
MUTAG
Proteins ENZYMES
GIN
88.83:16.10 75.60+1.34 48.35::4.47
GIN-N
90.11+4..35 75.71+1.18 49.5244.91
PANDA
88.49+4.90 24.46++2.22 46.33
PANDA-N
89.50 75.51 47.16::4.13
H MISCELLANEOUS
The softmax function Given a feature vector, it is a common practice to obtain a probability distribution by applying the softmax function to the components. For the convenience of theoretical analysis, we have not discussed the effect of the softmax function. As the softmax function is not a linear transformation and is always nonzero, will not match the vertices of simplex to that of the probability simplex A.. However, it is approximately so as illustrated in Fig. 15, Morcover, the softmax function is order- prder-preserving (of the components), therefore, omitting the softmax function does not change prediction accuracy.
The |1-1/ eevalutttonn metric In Section 5, we have proposed considering average f. as evalu- ation metrie. This essentially an 1-norm. We choose this over the 2-norm because the 1-norm is the same as the Wasserstein metric the discrete space C' of label classes (Villani, 2009; Ji et al., 2023a). Moreover, 1-norm reflects better sparsity under the condition that for any given node, most of its neighbors belong 1 or 2 classes. However, the metric is used measure of the closeness between the predicted distribution 2, and the ground-trun -tutth distribution Hy. Using 2-norm is also a reasonable choice.
31

---

Published as a conference paper at ICLR 2025
Normalized adjacency matrix In the early work Kipf & Welling (2017), is already noted that the normalized version of the adjacency matrix should be used for convolution. On the other hand, Xu al. (2019) claims that using the adjacency matrix the aggregator is more expressive. For the node classification, our perspective suggests that feature aggregation is to reduce class feature variance. Therefore, the normalized adjacency matrix serves this purpose better.
32


Reviews:
[{"review_id": "6jJmLSeGN6", "reviewer": "Reviewer_kubS", "summary": "The paper proposes a novel perspective for studying datasets used in node classification, which focuses not on the graph structure but on the \"behavior\" of node features, in particular their centroids.\nThe authors leverage geometric concepts to enhance class representation and model interpretability. Each class is represented through probabilistic centroids and geometric centroids organized within simplexes in lower-dimensional spaces. This approach offers new insights into why it is challenging to achieve significant results on certain datasets, identifying simple strategies that can improve node classification performance in GNN models, such as in the case of degenerate simplex and the feature re-shuffling phenomenon.", "questions": "In Figure 5, I would add class centroid as well.\nI would also use in fig. 1 Squirrel.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The first strength is that the paper introduces a new approach to studying datasets, which in turn allows for the analysis of GNN performance based on input datasets. I also find it particularly interesting that the method is entirely based on node features, making the study simple and fast.\n\nI also believe that other strengths include the solid theoretical support provided by the authors and, above all, the practical aspect of the study, which proposes simple and effective strategies capable of improving GNN performance as well as model interpretability.", "weaknesses": "The paper is well-written and rich in content; however, it is somewhat difficult to follow due to the abundance of theoretical contributions and the numerous references to the appendix. I understand, however, that with the page limit, it is challenging to organize all the material effectively.\n\nIt should also be noted that some assumptions are rather optimistic: for instance, even in the simple Lemma 1, I would expect some overlapping in reality. Nonetheless, I understand that this is intended as a starting point.\n\nAnother shortcoming is that the studies conducted so far have limited applicability, as the approach mainly focuses on node features and datasets used for node classification.  I was wondering if it might be possible to gain some insight in the case of graph classification as well.\n\nIt also seems that a thorough discussion on scalability is lacking (or maybe I missed it): what happens, for instance, when the graphs are not very large or when the features are low-dimensional? \nI did not notice a section dedicated to the actual limitations of the method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "H7w6UgP3ce", "reviewer": "Reviewer_NSvv", "summary": "The paper \"Rethinking Graph Neural Networks from a Geometric Perspective of Node Features\" proposes a new framework for understanding Graph Neural Networks (GNNs) by focusing on node features rather than solely on graph topology. The authors introduce the \"feature centroid simplex,\" a geometric structure representing the distribution of node features across classes, as a tool to explore phenomena like heterophily (when nodes connect across classes), oversmoothing, and feature reshuffling in GNNs. This feature-centric perspective addresses limitations of traditional topology-based approaches, especially for datasets where graph structure alone does not fully capture data complexity. The concept of the \"feature centroid simplex,\" a high-dimensional simplex formed by the centroids of node features within each class introduced by the authors, is presented as a geometric model that enables a deeper understanding of key GNN phenomena, such as heterophily, oversmoothing, and feature aggregation. By studying the convex shapes of these simplexes and their proximities, the paper explains the behavior of GNNs across different graph structures, especially on challenging tasks like node classification. It also suggests simple, graph-independent tricks to improve GNN performance, such as early stopping and feature normalization, particularly on heterophilic datasets where standard GNNs often struggle. The paper works to provide a unified geometric framework to enhance theoretical understanding and practical efficacy in GNN applications​", "questions": "Can the assumptions made to provide proofs to lemmas and theorems be listed and justified as reasonable?\n\nCan the limitations caused by the assumptions made be discussed? \n\nCan the limitations of the approach be made more explicit, and despite those limitations, the novely and contributions of the proposed approach be justified?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper’s novelty lies in its shift from topology-based to feature-centric analysis in understanding GNNs, introducing the concept of a \"feature centroid simplex\" formed by class-based feature centroids, which allows GNN behavior to be studied within feature spaces rather than solely relying on graph structure. By applying coarse geometry to examine simplex shapes, the paper offers new insights into common GNN challenges, including heterophily, oversmoothing, and feature variance. This graph-agnostic, feature-driven approach provides a unique way to assess dataset-specific difficulties, such as classification \"hardness,\" focusing on intrinsic feature properties rather than external graph characteristics. The primary contributions of the paper include developing a theoretical framework based on the feature centroid simplex, which offers new perspectives on GNN phenomena. It also provides practical, graph-independent tricks like early stopping and adding edges between nodes of the same class to improve GNN performance in difficult settings. These insights are supported by empirical validation on heterophilic datasets such as Actor, Chameleon, and Squirrel, where the feature-centric approach and proposed techniques demonstrate substantial improvements over traditional GNN models.\n\nThe paper provides a clear, succinct abstract that outlines its goal to rethink Graph Neural Networks (GNNs) from a feature-centric, geometric perspective. The structure flows logically from a foundational background to theoretical concepts like the feature centroid simplex and quasiisometry, and then to practical applications for GNN improvement. Each section builds upon the previous, and a notation table in the appendix enhances clarity. \n\nThe paper demonstrates theoretical rigor with a strong foundation in geometric and probabilistic models, supported by detailed proofs in the appendices\n\nVisuals, including feature centroid simplexes, effectively clarify complex ideas, and experiments are presented with comprehensive tables and discussions on framework effectiveness across datasets. \n\nAppendices are well-used to include supplementary proofs, notation, and experiments, keeping the main content focused while providing technical depth for interested readers.  Overall, the structure, visual aids, and appendices provide a strong foundation for understanding the paper’s contributions.\n\nThe provided illustration were found to be well done and very informative.", "weaknesses": "The level of novelty and degree of contributions in the work presented were not fully convincing and could perhaps be made clearer by making explicitly the degree to which the proposed work contributes as well as a more explicit discussion on where the proposed work has limitations. For example, the feature-centric approach, while novel, may have limited applicability in cases where feature information alone is insufficient, or where the graph structure itself is crucial, such as in social networks or molecular graphs where node connections are integral to understanding relationships. The framework and tricks presented are mainly beneficial for heterophilic datasets; however, for homophilic graphs, where existing GNN models already perform well, the proposed tricks may not offer significant improvements. Additionally, the tricks suggested, such as early stopping and feature normalization, are simple yet not inherently innovative, as these techniques are standard practices in machine learning for managing overfitting and feature scaling; the novelty lies more in their application to GNNs than in the techniques themselves. \n\nAnother limitation is the paper’s reliance on certain assumptions about feature distribution and convexity, which may not hold across all types of graph data, potentially limiting the framework’s generalizability, especially when features are not easily separable or node classes lack well-defined centroids.\n\nIn terms of novel contributions, the paper's innovation is somewhat limited. Although the feature-centric perspective provides a new approach, it builds on well-known GNN challenges such as oversmoothing and heterophily without fundamentally altering GNN structures or proposing new architectures. Thus, the framework offers insights rather than resolutions to these issues. Furthermore, the recommended tricks, while practical, are widely used machine learning techniques, and applying them to GNNs does not significantly advance the field. The empirical comparisons primarily focus on baseline models and lack a thorough analysis of how more advanced GNNs, with adaptive architectures or attention mechanisms, might perform with these tricks, which constrains the paper’s insights into how its geometric perspective could be leveraged in state-of-the-art models.\n\nThe paper would benefit from an experimental evaluation with datasets with low label informativeness to assess the quality of their feature centric approach such as those offered by recent works such as “A critical look at the evaluation of GNNs under heterophily: Are we really making progress?” by Platonov et. al. A more in depth comparative analysis to other similar methods which perform topological or geometric analysis of the feature space to implore learning model performance such as persistence landscapes or persistence images by Adams et. al.and other methods such as those discussed in Architectures of Topological Deep Learning: A Survey of Message-Passing Topological Neural Networks by Papillon et. al. should be experimentally compared to and definitely discussed in the background and related works section. The authors should also consider comparing to other geometry based approaches as presented in “Feature Expansion for Graph Neural Networks” by Sun et. al. or “A Survey of Geometric Graph Neural Networks: Data Structures, Models and Applications” by  Han, Cen, and Wu et. al. however I have not extensively read these last two works.\n\nOn reading the paper, I was not convinced of the validity and generalized applicability of the approach due to the assumptions that were required in order to provide proof of necessary lemmas and theorems as presented and needed to support the paper's claims. A more detailed analysis of the bounds in the number of sample points is needed in order for the probabilistic claims to be met such as convex positioning or the number of samples needed to justifiably use the geometric centroid of a class. \n\nThe related works discussed in the introduction and background should be expanded as well as more explicit discussion of the proposed paper in the context of contemporary literature. An more explicit discussion with the novelty of the current work could be made more persuasive. A more explicit limitations section and discussion would also be appreciated.\n\nDefinitions of concepts used and background information is at times distributed throughout the paper rather than presented at first in background and related work. Background and foundational concepts should be presented earlier and consolidated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0R7ODYCPfb", "reviewer": "Reviewer_ZoMg", "summary": "This paper introduces a *feature-centric approach* to analyzing GNNs by examining the node embeddings for each class in feature space  rather than graph topology. The authors define a *feature centroid simplex* and leverage coarse geometry to explore GNN behaviors like heterophily and oversmoothing, offering new insights and simple techniques for improving node classification performance. They make extensive experiments to validate their analysis", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces an innovative approach to studying GNNs by focusing on the clustering behavior of node embeddings for each class in feature space.\n2. By defining a *feature centroid simplex* as a (K-1)-simplex using the centers of these clusters, where K is the number of classes, the authors provide a geometric representation in $\\mathbb{R}^m$ that effectively captures class relationships.\n3. They use this geometric perspective to explain key GNN challenges, such as homophily/heterophily and oversmoothing, in terms of the feature centroid simplex.\n4. The mapping of the probability simplex to the *feature centroid simplex* is particularly insightful, as it reveals additional learning opportunities within the feature space.", "weaknesses": "1. **Presentation Quality**: The paper’s main weakness lies in the presentation, which does not effectively communicate its promising ideas. Although grounding concepts in mathematical rigor is essential, the technicalities in this paper obscure the overall clarity and may hinder comprehension.\n\n2. **Mathematical Statements**: The mathematical claims in Sections 2 and 3 lack interpretability. The space of graphs with feature vectors is vast and diverse, requiring more restrictive assumptions or narrowing to particular subclasses for these statements to hold meaning. For instance, Lemma 1 is difficult to justify unless the feature dimension m is very large and comparable to the number of nodes n. Similarly, Lemma 2 could benefit from a focus on the geometric simplex rather than the ambiguous term $e_c$, which complicates the exposition. Such imprecise statements make the argument obscure and challenging to follow.\n\n3. **Distinction of Homophily and Heterophily**: The idea to distinguish homophily and heterophily through feature centroid differences or clustering behaviors of node neighborhoods is promising. However, adding a geometric quantification—such as using the diameter, the volume of the simplex, or embedding of node neighborhoods with normalization—would strengthen the approach and add greater empirical rigor.\n\n4. **Oversmoothing Analysis**: Analyzing changes in the feature centroid simplex under oversmoothing is an excellent idea, with the potential to develop a metric for measuring oversmoothing. To achieve this, the paper would benefit from more precise definitions of the geometric quantities involved, along with a demonstration of changes in these quantities across epochs. For example, seeing the changes in the volume of feature centroid simplex under each epoch for oversmoothing would be very interesting.\n\n5. **Incremental Improvements**: Although the simple tricks suggested are useful, they offer only incremental improvements. A more substantial contribution, such as a more comprehensive approach that integrates the meaningful information (e.g., some geometric quantities) obtained from feature centroid simplex approach to ML pipelines, would significantly strengthen the impact of this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Poq5hWJXCS", "reviewer": "Reviewer_p71D", "summary": "The paper proposes to look at the node features from a simplex perspective. The main observations are a new view on oversmoothing and homo/heterophily. Further, some tricks (feature normalization and feature shuffling) are proposed to improve empirical results.", "questions": "Overall, I believe that a long version of the paper (e.g. one for arxiv), with all examples, filler texts and some proofs re-inserted is a much better version of the paper. Currently, the setup is not well-motivated and the paper not self-contained. It also felt overly formal over large parts of the text.\n\nI would thus like to encourage to work on the presentation.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Node features and their proper handling has proven effective for a number of graph-learning tasks, so focusing on those instead of taking features as a second-class citizen after structure makes sense.\nThe main contribution of the paper is a theoretical model which allows to analyze GNNs wrt overfitting and homo/heterophily.\nExperiments show that the presented tricks can indeed improve empirical performance.", "weaknesses": "The paper is unnecessarily hard to read. There is a lot of notation and the definitions and usage are sometimes far away (including non-standard notation). \nThe paper is also not really self-sufficient, there are very many mentions of the appendix promising e.g. experiments (even though some are in the paper the reference is to the appendix). \nThe probabilistic node feature model is not motivated. Since all results are based on this model, it would be good to at least argue in how far the assumptions are ``natural''. E.g. what does it mean for features to be convex? And does that appear in practice? (again, only a reference to the appendix...)\nNone of the theorems as an extensive description of what it means or why it is important. Usually its just the theorem and nothing else. E.g. 314 mentions an example that is no longer part of the main text. \nThe proposed feature normalization is as informal as it can get (which is surprising, given the formality in the rest of the paper). So its unclear whether each feature (across nodes) or each node's feature vector is normalized. The former is a standard trick and not new at all, so I guess its the latter.\nThe feature-shuffling trick is also not well-explained (but well-motivated). How would that be applied in a real-world dataset where e.g. 5-10% of the nodes are labeled? \n\nFurther small points:\n- 226: G is undefined. (or rather, the quantifier is unclear)\n- 220: please make clear that the model in the paper is not quite the original GCN but rather the version without sqrt(d). I believe that moving the formal definition of GCN in front of 224 would significantly improve readability.\n- 406: how does this now differ from the spectral result? (looks pretty much like the same result)\n- 472: the list of tricks that is applied did not make it into the main paper. I guess that should be changed.\n- 527: please repeat what $\\ell_v$ is about, this is not standard and most of all not just some standard accuracy.\n- 537: \"many\" could be made specific.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)