Mitigating Over-Smoothing in Graph Neural Networks via Separation Coefficient-Guided Adaptive Graph Structure Adjustment

1 Introduction

Graph Neural Networks (GNNs) are a class of deep learning models specifically designed to handle graph-structured data. In recent years, they have achieved significant progress in tasks such as node classification [Chen et al., 2023], link prediction [Wang et al., 2019], and graph classification [Xu et al., 2019]. The core idea of GNNs is to leverage a message passing mechanism that enables each node to iteratively aggregate the features of its neighboring nodes over multiple layers, thereby learning discriminative node or graphlevel representations. However, with the increase in network depth, GNNs face a common challenge in practical applications: over-smoothing. When the network becomes too deep, node features become progressively indistinguishable due to repeated aggregation, making it difficult to distinguish nodes of different classes, and severely impairing classification or clustering performance.

∗Corresponding Author.

To alleviate over-smoothing, several strategies have been proposed. These strategies mainly focus on either introducing specific mechanisms or adjusting the loss function to limit the feature convergence that results from excessive aggregation. For instance, GCNII [Chen et al., 2020], introduces inter layer skip connections, effectively preserving local node features, and enhancing class-level feature differences during multi-layer information propagation, thereby mitigating the over-smoothing issue. The DropEdge [Rong et al., 2020] method randomly removes some edges in the graph to limit the excessive aggregation of features from heterogeneous node classes during propagation, making the information flow more flexible. The Allen-Cahn method [Wang et al., 2022] draws inspiration from the Allen-Cahn equation in physics by introducing a smoothing term in the model's loss function, which controls the inter-class feature differences and mitigates excessive feature aggregation.

Although these methods help alleviate the over-smoothing problem to some extent, they typically rely on empirical rules or heuristic designs, failing to theoretically reveal the relationship between the message passing process and the variation in inter-class node feature differences. This lack of theoretical guidance makes it difficult to effectively optimize the key factors that lead to over-smoothing, resulting in unstable performance on complex datasets and limiting their generalizability and scalability. Moreover, these methods often have high computational complexity, especially in large-scale graph data or high-dimensional feature cases, leading to significant increases in computational cost and inefficiency in practical applications.

To address these challenges, we first analyze the theoretical causes of over-smoothing in GNNs. We introduce the concept of separation coefficient and, through analyzing the changes in the expected representation distance between classes, propose that the separation coefficient is a key factor in quantifying the contraction of feature distances between classes during multi-layer message propagation. Further analysis shows that the separation coefficient is closely related to the graph structure, and specific graph structures can effectively amplify inter-class distances and improve intra-class compactness, thereby fundamentally mitigating the phenomenon of heterogeneous representations converging. Based on this theoretical insight, we propose a pseudo-label-based adaptive graph structure adjustment method. First, we use a welltrained GNN model to obtain node predicted pseudo-labels, then selectively add or delete edges based on this pseudolabel information, while fine-tuning the GNN parameters to adaptively adjust the graph structure and mitigate the impact of over-smoothing on model performance. Unlike some traditional methods that rely on end-to-end joint training, our approach directly adjusts the graph structure based on interpretable rules, avoiding additional loss function design and large-scale training costs, while enhancing the interpretability and usability of the method. Moreover, we conduct experiments on multiple benchmark datasets, and our method demonstrates its ability to maintain effective class separation even under deep aggregation conditions, outperforming other methods designed to alleviate over-smoothing.

The main contributions of this paper are as follows:

• We describe the causes of over-smoothing in GNNs from the perspective of inter-class expected representations. By introducing the concept of the separation coefficient, we quantify the contraction of feature distances between classes during multi-layer message propagation and reveal the close relationship between this contraction and graph structure, providing a theoretical basis for optimizing graph structures.
• Based on this theory, we propose a pseudo-label-based adaptive graph structure adjustment method. This method utilizes the predicted pseudo-labels from a welltrained GNN to adaptively adjust the graph structure while fine-tuning the GNN model parameters, effectively alleviating the impact of over-smoothing on GNN performance.
• We propose a low-complexity, plug-and-play graph structure optimization algorithm to enhance inter-class separation and intra-class compactness during message passing. Experimental results demonstrate that our method significantly improves node classification performance on various benchmark datasets for both homogeneous and heterogeneous graphs.

2 ProposedMethod

To address the over-smoothing problem in Graph Neural Networks (GNNs), we propose a pseudo-label-based adaptive graph structure adjustment method. Our approach is based on a theoretical analysis of the relationship between node representation changes during message passing and the graph structure, with the goal of optimizing the graph structure to maintain intra-class feature compactness and enhance interclass feature separation, thereby alleviating the negative effects of over-smoothing.

In Section 2.1, we first present the problem statement, clearly defining the research problem and objectives. Section 2.2 provides an in-depth discussion of the causes of over-smoothing in GNNs, introducing the separation coefficient as a key factor influencing the convergence of heterogeneous representations during message passing, and revealing the relationship between the separation coefficient and the graph structure, which serves as a theoretical foundation for graph structure optimization. Section 2.3 presents a detailed description of our algorithm, which generates pseudo-labels based on the non-uniformity of node label predictions and adjusts homogeneous and heterogeneous connections according to the pseudo-label information, thereby optimizing the graph structure and effectively mitigating the over-smoothing problem.

2.1 Problem Statement

In graph neural networks (GNNs), node classification performance is fundamentally constrained by the underlying graph structure and suffers from the over-smoothing problem where node representations become increasingly similar as the network depth increases. Let G = (V,E) be an undirected graph, where each node v ∈ V is associated with a feature vector xv ∈ Rl and a label yv ∈ Y. Given an L-layer GNN model fθ : (G,X) → Y with parameters θ, where X ∈ R|V |×l is the node feature matrix, the node representations h(L) v tend to converge:

Our goal is to optimize the graph structure while maintaining its essential properties:

(2)

where G(G) represents possible graph structures and sim(G′ ,G) ≥ δ ensures structural similarity between the original and optimized graphs.

2.2 Theoretical Analysis

In this section, we first model the interactions between node features, labels, and their neighbors based on Assumption 1. Building on this, we derive the formula for calculating the expected class representation under a general message passing mechanism. Next, we analyze the changes in the expected inter-class feature distances before and after message passing and introduce the separation coefficient to quantify the variation in inter-class feature distances. Finally, we propose the conditions for enhancing the separation coefficient while ensuring intra-class compactness.

In graph-structured data, node features typically originate from some distribution, and node labels are often correlated with the labels of their neighboring nodes. This relationship is crucial for node classification tasks in GNNs. To effectively model this dependency, it is generally assumed that node features are independently sampled from a particular distribution. Additionally, the labels of neighboring nodes influence the learning process of the target node. Therefore, modeling the interactions between node features, node labels, and their neighbors' labels is key to the theoretical analysis of graph learning.

Given the above considerations, we assume the following distribution for node features and labels in our framework:

Assumption 1. We consider a graph G, where each node i has features xi ∈ Rl and label yi. The assumptions are as follows:

1. The feature vector xi of node i is sampled from the feature distribution Fyi .
2. The dimensions of the feature vector xi are independent of each other.
3. All elements of the node feature matrix X are bounded by a positive number B, i.e., maxi,j |X[i, j]| ≤ B.
4. The feature of node i is independent of the labels of its neighbors.

(5) The labels of node i's neighbors are independently sampled from the neighbor distribution Dyi , with the sampling process occurring deg(i) times, where deg(i) is the degree of node i. During the sampling process, the proportion of nodes belonging to the same class is p, and the proportion of nodes belonging to different classes is 1-p K-1 , where K is the total number of classes.

Similar to [Ding et al., 2024][Liao et al., 2021], we model node features as being sampled from label-specific distributions, reflecting the similarity of features among nodes of the same class, while maintaining flexibility for intra-class natural differences. Moreover, the independence of neighbor labels aligns with the Markov property and conforms to the local dependency assumptions of graph data [Bohde et al., 2024]. Although the independence between features and neighbor labels is a simplification, it does not affect practical applications, as Graph Neural Networks (GNNs) can implicitly model these complex relationships during message passing. These assumptions provide a solid foundation for theoretical analysis while ensuring the generalizability and applicability of the method.

Under Assumption 1, we perform a theoretical analysis of the message passing mechanism. Specifically, the representation hi of node i after message passing can be expressed as:

where N(i) is the set of neighbors of node i, deg(i) is the degree of node i, W is the weight matrix, and xj is the original feature of node j. Based on this formula, we can obtain the representation of node i after message passing. Furthermore, in Lemma 1, we derive the formula for the expected representation of class c, denoted as Ec[h].

Lemma 1. Under Assumption 1, the expected representation h of class c can be expressed as:

whereW(k) ∈ Rl×l is the transformation matrix, Y is the set of classes, and Ek[x] is the expected feature of nodes in class k.

Based on Lemma 1, our goal is to analyze the changes in class representations during message passing using the expected class representation. We prove that message passing leads to the convergence of representations from different classes. Moreover, in Theorem 1, we establish the distance relationship between the expected representations of classes c and d before and after message passing.

Theorem 1. Under Assumption 1, the distance between the expected representations of different classes satisfies the following equation:

where Ec[h] and Ed[h] are the expected representations of classes c and d, respectively, Ec[x] and Ed[x] are the expected features of nodes in classes c and d, and σmin(W) is the smallest singular value of matrix W, σmax(W) is the largest singular value of matrix W.

Proof. For the proof, please refer to Appendix.

Since σmax(W) pK-1 K-1 < 1, Theorem 1 demonstrates that for graph neural networks satisfying Assumption 1, after multiple message passing iterations, the distance between the representations of nodes from different classes will gradually decrease. Specifically, when the proportion p of same-class neighbors in the graph remains constant, and the maximum and minimum singular values of the matrix W do not change significantly, the degree of this distance contraction is primarily related to the proportion p. As the number of message passing iterations increases, the representations of nodes from different classes will become increasingly similar, leading to a gradual loss of discriminability between node representations, which may eventually result in the over-smoothing problem. To more precisely describe this phenomenon, we introduce the concept of the separation coefficient to quantify the contraction process of the inter-class representation distance.

Definition 1 (Separation Coefficient). We define the separation coefficient as:

where Ec[h] and Ed[h] are the expected representations of classes c and d, respectively, Ec[x] and Ed[x] are the expected features of nodes in classes c and d, and ∥ · ∥2 denotes the 2norm.

Based on Theorem 1 and the definition of the separation coefficient, we derive a lower bound for the separation coefficient in the general message passing mechanism of Graph Neural Networks (GNNs). Specifically, the separation coefficient satisfies the following inequality:

where σmin(W) is the smallest singular value of the weight matrix W, σmax(W) is the largest singular value of matrix W, p is the proportion of same-class neighbors, and K is the total number of classes.

This inequality shows that, for fixed classes, the lower bound of the separation coefficient is influenced by weight matrix W and the proportion p of same-class neighbors. When the maximum and minimum singular values of W do not decrease, increasing the proportion p of neighboring nodes from the same class will improve the lower bound of the separation coefficient. This means that a graph structure with a higher proportion of same-class neighbors helps enhance the class separability of node representations, thereby better maintaining the inter-class differences during message passing.

However, in the node classification task of GNNs, simply enhancing class separability without considering intra-class compactness may compromise classification accuracy while mitigating over-smoothing. While increasing the separation coefficient effectively improves inter-class discriminability, if the representations of nodes within the same class are too dispersed, intra-class compactness will be insufficient, potentially harming classification performance. Especially in high-dimensional feature spaces, if the inter-class representation differences increase but the representations of sameclass nodes lack compactness, the classifier may struggle to distinguish same-class nodes accurately, thus reducing classification accuracy. Therefore, in Theorem 2, we provide the conditions for ensuring intra-class compactness.

Theorem 2. For any t > 0, if node i belongs to class c, the probability bound that the distance between the observed feature aggregation hi and the expected feature aggregation of class c, Ec[h], exceeds t is given by:

where σmax(W) denotes the largest singular value of the matrixW, l is the feature dimensionality, and deg(i) is the degree of node i. Additionally, p represents the proportion of nodes in the graph that belong to the same class as node i, as specified in Assumption 1.

Theorem 2 proves that, for GNNs satisfying Assumption 1, the representations of nodes are close to their expected representations with a certain probability. The probability of this closeness is influenced by the node degree, the largest singular value of the weight matrix W, and the proportion p of same-class neighbors. Specifically, as long as the number of same-class neighbors and the largest singular value of W do not decrease, increasing the proportion p of same-class neighbors will lead to a higher probability that the node representation is close to its expected class representation.

By combining Theorem 1 and Theorem 2, we can conclude that, when the maximum and minimum singular values of the weight matrix do not decrease, both the intra-class compactness and inter-class separability of the node representations after message passing are closely related to the graph structure. Specifically, we need to increase the proportion p of same-class neighbors while ensuring that the number of same-class neighbors does not decrease, i.e., by enhancing homogeneous connections and removing heterogeneous connections between nodes in the graph structure. This approach not only fosters greater intra-class compactness but also improves the separation coefficient, thereby enhancing the discriminability of the node representations. Through such structural adjustments, we aim to achieve the effects shown in Figure 1.

2.3 Method for Node Classification

In the previous section, we demonstrate that, while keeping the maximum and minimum singular values of the weight matrix invariant, adjusting the graph structure by increasing homophilic connections and reducing heterophilic connections can enhance intra-class node representation compactness and improve inter-class representation separability. Building on this theoretical insight, in this section, we propose an adaptive graph structure adjustment method based on pseudo-labels [Wang et al., 2025], aimed at further optimizing the graph structure and improving downstream task performance.

This method consists of three core steps: (1) generating pseudo-labels based on label non-uniformity; (2) optimizing the graph structure according to the pseudo-labels, by increasing homophilic connections and removing heterophilic connections; (3) incorporating the optimized graph structure into the GNN training process, and performing singular value checks on the weight matrix during training. The overall framework of the algorithm is illustrated in the Figure 2.

By focusing on topological optimization in the post-training phase, our method aligns closely with the principles of DataCentric AI (DCAI), emphasizing data-driven optimization to enhance downstream task performance.

To effectively generate pseudo-labels, we focus on the different dimensions of each node's predicted probability distribution and utilize label prediction non-uniformity to filter out nodes that are far from the class boundaries in classification tasks. Next, we introduce node prediction non-uniformity in Definition 2.

Definition 2 (Node Prediction Non-Uniformity). Let µv = (µv(y1), µv(y2), . . . , µv(y|Y|)) be the predicted probability distribution vector of the base model trained on classifier C(·), with µv(yi) ∈ [0, 1] for each yi ∈ Y and each v ∈ V. Moreover, Y is a finite set of labels, and ∑|Y| j=1 µv(yj) = 1. Therefore, µv(yj ) can be interpreted as the probability weight of node v having label yj. Following [Ji et al., 2023], the la-

Algorithm 1 Graph Optimization with Pseudo-labeling

Input: Graph G = (V, E, X), Weight matrix W trained on G, θ1

Output: Optimized graph structure G′ = (V,E′ ), Updated weight matrix W ′

4: end for

5: Sort nodes by w(v) and select the top θ1 nodes to form V ′

6: for each node v′ ∈ V ′ do

7: Mark the pseudo-label of node v′ as the category with the largest value in uv

8: end for

9: for each pair of nodes (v, v′ ) ∈ V ′ ×V ′ do

10:

if the pseudo-labels of v and v′ are the same then Set E′ (v, v′ ) = 1

• 12: else

• 14: end if
• 15: end for
• 16: Retrain GNN with the optimized graph G′ = (V, E′ )
• 17: Stretch the weight matrixW ′ as follows:

bel non-uniformity at v is defined by

The paper [Ji et al., 2023] points out that there exists a positive correlation between the prediction label non-uniformity of nodes and classification accuracy. When the prediction label non-uniformity of nodes is high, the probability of correct classification increases significantly, as shown in Figure 3. Therefore, we assign pseudo-labels to those nodes with high prediction label non-uniformity, forming a set of nodes with pseudo-labels, denoted as V ′ . Based on Theorem 1 and Theorem 2, within V ′ , we use pseudo-labels to increase homophilic connections and remove heterophilic connections between nodes, resulting in an optimized graph structure E′ . Subsequently, we retrain the GNN using E′ and apply a simple singular value stretching method to ensure that the maximum and minimum singular values of the weight matrix W′ after retraining are no less than σmax(W) and σmin(W), respectively. The proposed pseudo-label-based adaptive graph structure adjustment algorithm is shown in Algorithm 1.

3 Experiments

In this section, we conduct experiments on several publicly available datasets, including both homogeneous and heterogeneous graphs, to evaluate the effectiveness of our proposed pseudo-label-based adaptive graph structure optimization method in semi-supervised node classification tasks. We apply this algorithmic framework to several classic graph neural network models and compare it with multiple baseline methods to validate the relative superiority of our approach. The proposed model is named the Separation Coefficient Optimization Graph Neural Network (SCA-GNN), and the framework enhances node classification performance through simple topological structure adjustments. Specifically, when using Graph Convolution Networks (GCN) as the base model, the framework is referred to as SCA-GCN. The experimental design is aimed at addressing the following research questions:

• How much performance improvement can the proposed method achieve in semi-supervised node classification tasks compared to current mainstream baseline methods?
• What are the significant efficiency advantages of the proposed method in terms of computational complexity compared to existing methods?
• How does the proposed method effectively alleviate the over-smoothing problem caused by the increase in network depth, as observed in GNN classification performance across different network depths?
• To what extent can the proposed method improve the classification performance of different types of nodes on heterogeneous graph datasets?

3.1 Experimental Settings

Baselines

We select seven methods as baselines to evaluate the effectiveness of our proposed framework. We combine our framework with four classic base models: GCN (ICLR 2017) [Kipf and Welling, 2017], GAT (ICLR 2018) [Velickovic et al., 2018], GraphCON (ICML 2022) [Rusch et al., 2023], and MaskGAE (KDD 2023) [Li et al., 2022], to verify whether our method can enhance the performance of these base models. Additionally, we compare our approach with three graph structure learning methods that also optimize the graph structure: Pro-GNN (KDD 2020) [Jin et al., 2020], GEN (WWW 2021) [Wang et al., 2021], and PRI-GSL (AAAI 2023) [Sun et al., 2023], to demonstrate the advantages of our method in terms of both computational efficiency and accuracy.

Datasets

We evaluate the performance of our method on four publicly available homogeneous graph datasets (Cora, Citeseer, Pubmed, and OGBN-Arxiv) and four heterogeneous graph datasets (Texas, Chameleon, Actor and Squirrel). Notably, OGBN-Arxiv is a large-scale dataset containing 169,343 nodes and 1,166,243 edges. Detailed information about the datasets can be found in Appendix. To ensure fairness in the experiments, we use the same standard dataset splits as those in [Ji et al., 2023].

Implementation Details

We first train the base graph neural network (GNN) models on the datasets and use the trained models to generate the predicted label yv, label non-uniformity w(v), and the maximum singular value σmax(W) and minimum singular value σmin(W) of the weight matrix W for each node v. Next, we sort the nodes based on label non-uniformity and select the largest portion, consisting of θ1 × |V | nodes, and assign their pseudo-labels as their predicted labels. To ensure the accuracy of the pseudo-labels, we fix the hyperparameter θ1 to 0.02, consistent across all datasets. Then, based on the pseudo-labels of the nodes, we establish edges between same-class nodes and remove edges between differentclass nodes to generate the edge set E′ . Finally, we retrain the base model on the new graph structure and adjust the weight matrix W during training as follows: W′ = W × max ( σmin(W) σmin(W′ ) , σmax(W) σmax(W′ ) ) to ensure the stability and effectiveness of the new graph structure during training. Our framework is implemented using PyTorch, and all experiments are conducted on an NVIDIA RTX 3090 GPU.

3.2 Experimental Evaluation

Performance Improvement of Our Method in Semi-supervised Node Classification (Q1)

We apply the proposed method to the base models on four homogeneous graph datasets, and the experimental results are presented in Table 1. Across all datasets, our method consistently improves the performance of the base models on the test set. The experimental results demonstrate that our pseudo-label-based adaptive graph structure optimization method significantly and stably enhances the performance of the base models in semi-supervised node classification tasks. Furthermore, our method shows good generalizability and can be easily integrated into most base models, further enhancing their performance.

Computational Complexity Advantage of Our Method (Q2)

We select three commonly used graph structure learning methods and compare their computational complexity with that of our method. The experimental results are shown in Table 2. Since our method adaptively adjusts the graph structure based on interpretable rules, it does not introduce additional training steps or parameters, thus effectively saving computational resources and training time. Compared to other more complex graph structure learning methods, our approach demonstrates significant advantages on large-scale graph datasets. The experimental results indicate that, while maintaining low complexity, our method can significantly improve node classification accuracy.

Performance of Our Method in Multi-layer GNNs (Q3)

Through pseudo-label-based adaptive graph structure optimization, our method maintains intra-class compactness while enhancing the separability of heterogeneous representations, effectively alleviating the over-smoothing phenomenon that occurs in graph neural networks (GNNs) during multiple message passing iterations. To validate the effectiveness of our method in mitigating the over-smoothing problem in GNN models with different depths, we conducted semi-supervised node classification experiments with GCN models containing 1 to 6 layers on the Cora, Citeseer and PubMed datasets, comparing the performance before and after applying our method. The experimental results, shown in Table 3, indicate that although the accuracy of our method decreases as the number of GNN layers increases, it still significantly alleviates the over-smoothing problem compared to the GCN models without our method.

Performance of Our Method on Heterogeneous Graph Datasets (Q4)

Semi-supervised node classification on heterogeneous graph datasets has long been a challenging problem in graph neural networks (GNNs). Studies have shown that due to the presence of many heterogeneous connections in these datasets, models tend to experience significant over-smoothing even at shallow layers. To verify the effectiveness of our method on heterogeneous graph datasets, we applied it to base models on four heterogeneous graph datasets, and the results are shown in Table 4. The experimental results demonstrate that our method significantly improves node classification accuracy on all baseline models across heterogeneous graph datasets.

4 Conclusion

In this paper, we propose a pseudo-label-based adaptive graph structure optimization method aimed at addressing the oversmoothing problem in graph neural networks (GNNs). By analyzing the changes in inter-class representation distances, we introduce the concept of the separation coefficient to quantify the feature contraction process and design a low-complexity graph structure adjustment method. This method enhances the separability of inter-class features while maintaining the compactness of intra-class features. Experimental results demonstrate that our approach significantly improves node classification accuracy across multiple benchmark datasets and outperforms existing methods in terms of computational efficiency. Our research provides an effective solution to alleviate the over-smoothing problem in GNNs and offers strong support for graph structure optimization and the application of GNNs on large-scale datasets.

Acknowledgements

This work is supported by the Young Elite Scientists Sponsorship Program by CAST (No. 2023QNRC001) and the National Natural Science Foundation of China (No. 62106082). We thank Prof. Zijiang James Yang and Rui Ding for helpful discussions.