{'fraction_non_alphanumeric': 0.03519852919372535, 'fraction_numerical': 0.01073451353675533, 'mean_word_length': 4.8916841369671555, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing

Topology-imbalance is a graph-specific imbalance problem caused by the uneven topology positions of labeled nodes, which significantly damages the performance of GNNs. What topology-imbalance means and how to measure its impact on graph learning remain under-explored. In this paper, we provide a new understanding of topology-imbalance from a global view of the supervision information distribution in terms of under-reaching and over-squashing, which motivates two quantitative metrics as measurements. In light of our analysis, we propose a novel position-aware graph structure learning framework named PASTEL, which directly optimizes the information propagation path and solves the topology-imbalance issue in essence. Our key insight is to enhance the connectivity of nodes within the same class for more supervision information, thereby relieving the under-reaching and over-squashing phenomena. Specifically, we design an anchor-based position encoding mechanism, which better incorporates relative topology position and enhances the intra-class inductive bias by maximizing the label influence. We further propose a class-wise conflict measure as the edge weights, which benefits the separation of different node classes. Extensive experiments demonstrate the superior potential and adaptability of PASTEL in enhancing GNNs' power in different data annotation scenarios.


INTRODUCTION
Graph learning [13,24,52] has gained popularity over the past years due to its versatility and success in representing graph data across a wide range of domains [9,14,26,40,50]. Graph Neural Networks (GNNs) [39,47] have been the "battle horse" of graph learning, which propagate the features on the graph by exchanging information between neighbors in a message-passing paradigm [15]. Due to the asymmetric and uneven topology, learning on graphs by GNNs suffers a specific imbalance problem, i.e., topology-imbalance. Topology-imbalance [7] is caused by the uneven position distribution of labeled nodes in the topology space, which is inevitable in real-world applications due to data availability and the labeling costs. For example, we may only have information for a small group of users within a local community in social networks, resulting in a serious imbalance of labeled node positions. The uneven position distribution of labeled nodes leads to uneven information propagation, resulting in the poor quality of learned representations.
Although the imbalance learning on graphs has attracted many research interests in recent years, most of them focus on the classimbalance issue [30,46], i.e., the imbalanced number of labeled arXiv:2208.08302v1 [cs.LG] 17 Aug 2022 nodes of each class. The topology-imbalance issue is proposed recently and is still under-explored. The only existing work, ReNode [7], provides an understanding of the topology-imbalance issue from the perspective of label propagation and proposes a sample re-weighting method. However, ReNode takes the node topological boundaries as decision boundaries based on a homophily assumption, which does not work with real-world graphs. The strong assumption leads to poor generalization and unsatisfied performance of ReNode (see Section 5.2.1). There are two remaining questions: (1) Why does topology-imbalance affect the performance of graph representation learning? and (2) What kind of graphs are susceptible to topology-imbalance? To answer the above two questions, how to measure the influence of labeled nodes is the key challenge in handling topology-imbalance due to the complex graph connections and the unknown class labels for most nodes in the graph. New understanding for topology-imbalance. In this work, we provide a new understanding of the topology-imbalance issue from a global view of the supervision information distribution in terms of under-reaching and over-squashing: (1) Under-reaching: the influence of labeled nodes decays with the topology distance [3], resulting in the nodes far away from labeled nodes lack of supervision information. In Figure 1, the node cannot reach the valuable labeled node within the receptive field of the GNN model, resulting in the quantity of information it received is limited. (2) Over-squashing: the supervision information of valuable labeled nodes is squashed when passing across the narrow path together with other useless information. In Figure 1, the valuable supervision information of to is compressed into a vector together with the information of many nodes belonging to other classes, resulting in the quality of supervision information that received being poor. Then we introduce two metrics (reaching coefficient and squashing coefficient) to give a quantitative analysis of the relation between the learning performance, label positions, and graph structure properties. We further draw a conclusion that better reachability and lower squashing to labeled nodes lead to better classification performance for GNN models. Present work. In light of the above analysis, we propose a Position-Aware STructurE Learning method named PASTEL, which directly optimizes the information propagation path and solves the problem of topology-imbalance issue in essence. The key insight of PASTEL is to enable nodes within the same class to connect more closely with each other for more supervision information. Specifically, we design a novel anchor-based position encoding mechanism to capture the relative position between nodes and incorporate the position information into structure learning. Then we design a class-wise conflict measure based on the Group PageRank, which measures the influence from labeled nodes of each class and acts as a guide to increase the intra-class connectivity via adjusting edge weight. The main contributions are as follows: • We provide a new understanding of the topology-imbalance issue from the perspective of supervision information distribution in terms of under-reaching and over-squashing and provide two new quantitative metrics for them. • Equipped with the proposed position encodings and class-wise conflict measure, PASTEL can better model the relationships of node pairs and enhance the intra-class inductive bias by maximizing the label influence. • Experimental results demonstrate that the proposed PASTEL enjoys superior effectiveness and indeed enhances the GNN model's power for in-the-wild extrapolation.

RELATED WORK 2.1 Imbalance Learning
Imbalanced classification problems [18,41] have attracted extensive research attention. Most existing works [16,25] focus on the class-imbalance problem, where the model performance is dominated by the majority class. The class-imbalance learning methods can be roughly divided into two types: data-level resampling and algorithm-level re-weighting. Re-sampling methods re-sample [2,5,48] or augment data [30] to balance the number of data for each class during the data selection phase. Re-weighting methods [4,11,32] adjust different weights to different data samples according to the number of data during the training phase. For the graph-specific topology-imbalance issue as mentioned in Section 1, directly applying these methods to the graph data fails to take the special topology properties into consideration. ReNode [7] is the first work for the graph topology-imbalance issue, which follows the paradigm of classical re-weighting methods. Specifically, ReNode defines an influence conflict detection based metric and re-weights the labeled nodes based on their relative positions to class boundaries. However, ReNode is limited by its homophily assumption and only has a slight performance improvement. In this paper, PASTEL alleviates topology-imbalance by learning a new structure that maximizes the intra-class label influence, which can be seen as "label re-distribution" in the topology space.

Graph Structure Learning
Graph structure learning [55] learns an optimized graph structure for representation learning and most of them aim to improve the robustness [20,54] of GNN models. There are also some works [8,10,12,38,42] that utilize the structure learning to improve the graph representation quality. As for the over-squashing problem, [45] assigns different weights to edges connected to two nodes of the same class for better representations. However, [45] still fails with the issue of under-reaching. SDRF [42] rewires edges according to the Ricci curvatures to solve the over-squashing problem by only considering topology properties.
Multiple measurements in existing structure learning works are leveraged for modeling node relations, including node features [53], node degrees [20], node encodings [51] and edge attributes [54]. The node positions play an important role in generating discriminative representations [49] and are seldom considered in structure learning. In this work, we advance the structure learning strategy for the graph topology-imbalance issue and introduce a position-aware framework to better capture the nodes' underlying relations.

UNDERSTANDING TOPOLOGY-IMBALANCE
In this section, we provide a new understanding of the topologyimbalance issue in terms of under-reaching and over-squashing. Then we perform a quantitative analysis of the relations between them to answer two questions: Q1: Why does topology-imbalance affect the performance of graph representation learning? Q2: What kind of graphs are susceptible to topology-imbalance?

Notations and Preliminaries
Consider a graph G = {V, E}, where V is the set of nodes and E is the edge set. Let A ∈ R × be the adjacency matrix and X ∈ R × 0 be the node attribute matrix, where 0 denotes the dimension of node attributes. The diagonal degree matrix is denoted as D ∈ R × where D = =1 A . The graph diameter is denoted as G . Given the labeled node set V and their labels Y where each node is associated with a label , semi-supervised node classification aims to train a node classifier : → R to predict the labels Y of remaining nodes V = V \ V , where denotes the number of classes. we separate the labeled node set V into {V 1 , V 2 , · · · , V }, where V is the nodes of class in V .

Understanding Topology-Imbalance via
Under-reaching and Over-squashing In GNNs, node representations are learned by aggregating information from valuable neighbors. The quantity and quality of the information received by the nodes decide the expressiveness of their representations. We perceive the imbalance of the labeled node positions affects the performance of GNNs for two reasons: (1) Under-reaching: The influence from labeled nodes decays with the topology distance [3], resulting in that the nodes far away from labeled nodes lack supervision information. When the node can't reach enough valuable labeled nodes within the receptive field of the model, the quantity of information it received is limited.
(2) Over-squashing: The receptive field of GNNs is exponentiallygrowing and all information is compressed into fixed-length vectors [1]. The supervision information of valuable labeled nodes is squashed when passing across the narrow path together with other useless information.

Quantitative Analysis
To provide quantitative analysis for topology-imbalance, we propose two metrics for reachability and squashing. First, we define a reaching coefficient based on the shortest path, which determines the minimum layers of GNNs to obtain supervision information: Definition 1 (Reaching coefficient). Given a graph G and labeled node set V , the reaching coefficient of G is the mean length of the shortest path from unlabeled nodes to the labeled nodes of their corresponding classes: where V denotes the nodes in V whose label is , P ( , ) denotes the shortest path between and , and |P ( , )| denotes its length, and G is the diameter of graph G. Specifically, for the unconnected and , we set the length of their shortest path as G .
The reaching coefficient reflects how long the the distance when the GNNs passes the valuable information to the unlabeled nodes. Note that ∈ [0, 1) and larger means better reachability. For the quantitative metric of over-squashing, we define a squashing coefficient using the Ricci curvature to formulate it from a geometric perspective. The Ricci curvature [28] reflects the change of topology properties of the two endpoints of an edge, where the negative ( , ) means that the edge behaves locally as a shortcut or bridge and positive ( , ) indicates that locally there are more triangles in the neighborhood of and [27,42].
Definition 2 (Sqashing coefficient). Given a graph G, the squashing coefficient of G is the mean Ricci curvature of edges on the shortest path from unlabeled nodes to the labeled nodes of their corresponding classes: where N ( ) denotes the labeled nodes of class that can reach , (·, ·) denotes the Ricci curvature, and |P ( , )| denotes the length of shortest path between and .
We leverage the Ollivier-Ricci curvature [28] as (·, ·) here: where (·, ·) is the Wasserstein distance, (·, ·) is the geodesic distance function, and is the mass distribution [28] of node . Note that can be either positive or negative and larger means lower squashing because the ring structures are more friendly for information sharing.
In Figure 2 and Figure 3, we show the relation between the reaching coefficient , the squashing coefficient , and the classification accuracy. The higher the accuracy, the darker and larger the corresponding scatter. First, we analyze the performance of GCN when trained on the same graph structure but with different labeled nodes. In Figure 2, we generate a synthetic graph by the Stochastic Block Model (SBM) [19] with 4 classes and 3,000 nodes. We randomly sample some nodes as the labeled nodes 10 times and scatter the classification accuracy in Figure 2. We can observe that even for the same graph structure, the difference in positions of labeled nodes may bring up to 15.42% difference in accuracy. There is a significant positive correlation between the reaching coefficient, the squashing coefficient, and the model performance.
Then we analyze the performance of GCN when trained with the same labeled nodes but on different graph structures. In Figure 3, we set the labeled nodes to be the same and generate different structures between them by controlling the edge probability between communities in the SBM model. We can observe that with the same supervision information, there is up to a 26.26% difference in accuracy because of the difference in graph structures. There is also a significant positive correlation between the reaching coefficient, the squashing coefficient, and the model performance. When the graph shows better community structure among nodes of the same class, the node representations can be learned better.
Therefore, we make the following conclusions: (1) Topologyimbalance hurts the performance of graph learning in the way of under-reaching and over-squashing. (for Q1) (2) The proposed two quantitative metrics can effectively reflect the degree of topologyimbalance. Graph with poor reachability (i.e., smaller ) and stronger squashing (i.e., smaller ) is more susceptible to topologyimbalance. (for Q2) (3) Optimizing the graph structure can effectively solve the topology-imbalance issue. The above conclusions provide the guideline for designing the framework of PASTEL, i.e., balance the supervision information distribution by learning a structure with better reachability and lower squashing.

ALLEVIATE TOPOLOGY-IMBALANCE BY STRUCTURE LEARNING
In this section, we introduce PASTEL, a Position-Aware STructurE Learning framework, to optimize the information propagation path directly and address the topology-imbalance issue in essence. In light of the analysis in Section 3.2, PASTEL aims to learn a better structure that increases the intra-class label influence for each class and thus relieves the under-reaching and over-squashing phenomena. The overall architecture of PASTEL is shown in Figure 4.

Position-aware Structure Learning
To form structure with better intra-class connectivity, we use an anchor-based position encoding method to capture the topology  distance between unlabeled nodes to labeled nodes. Then we incorporate both the merits of feature information as well as topology information to learn the refined structure.
Anchor-based Position Encoding. Inspired by the position in transformer [36,43], we use an anchor-based position encoding method to capture the relative position of unlabeled nodes with respect to all the labeled nodes of the graph. Since we focus on maximizing the reachability between unlabeled nodes and labeled nodes within the same class, we directly separate the labeled node set V into anchor sets {V 1 , V 2 , · · · , V }, where each subset V denotes the labeled nodes whose labels are . The class-wise anchor sets help distinguish the information from different classes rather than treating all the anchor nodes the same and ignoring the class difference as in [49]. Concretely, for any node , we consider a function (·, ·) which measures the position relations between and the anchor sets in graph G. The function can be defined by the connectivity between the nodes in the graph.
where ( , V ) is the position encoding function defined by the connectivity between the node and the anchor set V in graph.
Here we choose ( , V ) to be the mean length of shortest path between and nodes in V if two nodes are connected: where N ( ) is the nodes connected with in V and |P ( , )| is the length of shortest path between and . Then we transform the position encoding into the 0 dimensional space: where W is a trainable vector. similarity metric functions and we choose the widely used multihead cosine similarity function here: where is the number of heads, W ℎ is the weight matrix of the ℎ-th head, z denotes the representation vector of node and || denotes concatenation. The effectiveness of the position-aware structure learning is evaluated in Section 5.3.1.

Class-wise Conflict Measure
We aim to increase the intra-class connectivity among nodes, thereby increasing the supervision information they received and their influence on each other. Here we propose a class-wise conflict measure to guide what nodes should be more closely connected. According to the inherent relation of GNNs with Label Propagation [7,45], we use the Group PageRank [6] as a conflict measure between nodes. Group PageRank (GPR) extends the traditional PageRank [29] into a label-aware version to measure the supervision information from labeled nodes of each class. Specifically, for class ∈ {1, 2, · · · , }, the corresponding GPR matrix is where A ′ = AD −1 , is the random walk restart probability at a random node in the group and I ∈ R is the teleport vector: where |V | is the number of labeled nodes with class . We calculate the GPR for each group individually and then concatenate all the GPR vectors to form a final GPR matrix P ∈ R × as in [6]: where E is the unit matrix of nodes and I * is the concatenation of {I , = 1, 2, · · · , }. Under P , node corresponds to a GPR vector P (the -th row of P ), where the -th dimension represents the the supervision influence of labeled nodes of class on node . The GPR value contains not only the global topology information but also the annotation information.
For each node pair nodes and , we use the Kullback Leiber (KL) divergence of their GPR vectors to measure their conflict when forming an edge: The distance of GPR vectors reflects the influence conflict of different classes when exchanging information. We use a cosine annealing mechanism to calculate the edge weights by the relative ranking of the conflict measure: where (·) is the ranking function according to the magnitude. The more conflicting the edge is, the less weight is assigned to it. With the class-wise conflict measure, we aim to learn a graph structure that makes the GPR vectors of nodes have "sharp" distributions focusing on their ground-truth classes. Then is used as the connection strength of edge , with the corresponding element˜in the adjacency matrix being: The effectiveness of the class-wise conflict measure is evaluated in Section 5.3.2 and the change of GPR vectors is shown in Section 5.4.3.

Learning with the Optimized Structure
With the above structure learning strategy, we can obtain a positionaware adjacency A with maximum intra-class connectivities: The input graph structure determines the learning performance to a certain extent. Since the structure learned at the beginning is of poor quality, directly using it may lead to non-convergence or unstable training of the whole framework. We hence incorporate the original graph structure A and a structure in a node feature view A as supplementary to formulate an optimized graph structure A * . Specifically, we also learn a graph structure A = { , , ∈ Update model parameters to minimize L ← Eq. (22). 12 end {1, 2, · · · , }} in a node feature view with each element being: where x is the feature vector of node and h 0 is the position encoding with the original structure. Then we can formulate an optimized graph structure A * with respect to the downstream task: where (·) denotes the row-wise normalization function, 1 and 2 are two constants that control the contributions of original structure and feature view structure, respectively. Here we use a dynamic decay mechanism for 1 and 2 to enable the position-aware structure A to play a more and more important role during training.
To control the quality of learned graph structure, we impose additional constraints on it following [10,21] in terms of smoothness, connectivity, and sparsity: where L * = D * − A * is the Laplacian of A * and D * is the degree matrix of A * . To speed up the computation, we extract a symmetric sparse non-negative adjacency matrix by masking off (i.e., set to zero) those elements in A * which are smaller than a predefined non-negative threshold 0 . Then G * = (A * , X) is input into the GNN-Encoder for the node representations Z ∈ R × , predicted labelsˆand classification loss L : L = Cross-Entropy(Y,Ŷ). (21) The overall loss is defined as the combination of the node classification loss and graph regularization loss: The overall process of PASTEL is shown in Algorithm 1.

EXPERIMENT
In this section, we first evaluate PASTEL 1 on both real-world graphs and synthetic graphs. Then we analyze the main mechanisms of PASTEL and the learned structure. We mainly focus on the following research questions: • RQ1. How does PASTEL perform in the node classification task? (Section 5.2) • RQ2. How does the position encoding and the class-wise conflict measure influence the performance of PASTEL? (Section 5.3) • RQ3. What graph structure PASTEL tend to learn? (Section 5.4)

Datasets.
We conduct experiments on synthetic and realworld datasets to analyze the model's capabilities in terms of both graph theory and real-world scenarios. The real-word datasets include various networks with different heterophily degrees to demonstrate the generalization of PASTEL. Cora and Citeseer [35] are citation networks. Photo [37] and and Actor [31] are co-occurrence network. Chameleon and Squirrel [34] are page-page networks in Wikipedia. Since we focus on the topology-imbalance issue in this work, we set the number of labeled nodes in each class to be 20.

Baselines.
We choose representative GNNs as backbones including GCN [22], GAT [44], APPNP [23], and GraphSAGE [17]. The most important baseline is ReNode [7], which is the only existing work for the topology-imbalance issue. We also include some graph structure learning baselines to illustrate the specific effectiveness of PASTEL for the topology-imbalance issue. DropEdge [33] randomly removes edges at each epoch as structure augmentation. To evaluate the effect of increasing the reachability randomly, we use a adding edges method named AddEdge, whose adding strategy is similar to DropEdge. SDRF [42] rewires edges according to their curvatures for the over-squashing issue. NeuralSparse [54] removes potentially task-irrelevant edges for clearer class boundaries. IDGL [10] updates the node representations and structure based on these representations iteratively.

Parameter Settings.
For the GNN backbones, we set their depth to be 2 layers and adopt the implementations from the Py-Torch Geometric Library in all experiments. We set the representation dimension of all baselines and PASTEL to be 256. We reimplement the NeuralSparse [54] and SDRF [42] and the parameters of baseline methods are set as the suggested value in their papers or carefully tuned for fairness. For DropEdge and AddEdge, we set the edge dropping/adding probability to 10%. For PASTEL, we set the number of heads = 4 and the random walk restart probability  = 0.15. The structure fusing coefficients ( 1 and 2 ) and the loss coefficients ( 1 , 2 and 3 ) are tuned for each dataset.

Evaluation (RQ1)
5.2.1 PASTEL for Real-world Graphs. We compare PASTEL with the baselines on several datasets on node classification. The overall Weighted-F1 (W-F1) scores and the class-balance Macro-F1 (M-F1) scores on different backbones are shown in Table 1. The best results are shown in bold and the runner-ups are underlined. PAS-TEL shows overwhelming superiority in improving the performance of backbones on all datasets. It demonstrates that PASTEL is capable of learning better structures with a more balanced label distribution that reinforces the GNN models. ReNode [7] achieves fewer improvements on datasets of poor connectivity (e.g., CiteSeer) and even damages the performance of backbones on heterophilic datasets (e.g., Chameleon and Actor). We think it's because ReNode [7] detects conflicts by Personalized PageRank and fails to reflect the node topological position well when the graph connectivity is poor. Besides, ReNode takes the topology boundary as the decision boundary, which is not applicable for heterophilic graphs. AddEdge doesn't work in most cases, demonstrating that randomly adding edge is not effective in boosting the reachability. The structure augmentation strategy should be carefully designed considering the node relations. SDRF [42] can improve the performance, supporting our intuition that relieving over-squashing helps graph learning. But SDRF is still less effective than PASTEL because it only considers the topological properties rather than the supervision information. Both NeuralSparse [54] and IDGL [10] show good performance among the baselines, showing the effectiveness of learning better structures for downstream tasks. However, they are still less effective than PASTEL which takes the supervision information distribution into consideration.

PASTEL under Different Levels of Topology-imbalance.
To further analyze PASTEL's ability in alleviating the topology-imbalance issue, we verify the PASTEL under different levels of topologyimbalance. We randomly sampled 1,000 training sets and calculate   the reaching coefficient and squashing coefficient as introduced in Section 3.2. Then we choose 3 training sets with different levels of topology-imbalance according to the conclusion in Section 3.3 and we denote them as Cora-L, Cora-M, and Cora-H, according to the degree of topology imbalance. Note that larger means better reachability and larger means lower squashing. We evaluate PASTEL and several baselines with the GCN as the backbone and show the dataset information, the Weighted-F1 scores, and their improvements (Δ) over the backbones in Table 2. The performance of node representation learning generally gets worse with the increase of the topology-imbalance degree of the dataset. Both the node re-weighting method (i.e., ReNode [7]) and the structure learning methods (i.e., IDGL [10], SDRF [42] and PAS-TEL) can achieve more improvement with the increase of dataset topology-imbalance. PASTEL performs best on all datasets with different degrees of topology-imbalance and it can achieve up to 4.4% improvement on the highly topology-imbalance dataset.

PASTEL for Synthetic
Graphs. We generate 7 synthetic graph datasets with different community structures using the Stochastic Block Model (SBM) G( , , , ) [19], where the number of nodes = 3000, the number of community = 6, denotes the edge probability within a community and denotes the edge probability between communities. We show the classification Weighted-F1 scores and improvements are shown in Table 3. With a more clear community structure, the reaching coefficient increases and the squashing coefficient also increases, leading to the increase of GCN's performance, which agrees with the conclusion obtained in

Analysis of PASTEL (RQ2)
We conduct ablation studies for the two main mechanisms of PAS-TEL, position encoding and class-wise conflict measure.

Impact of the Position Encoding.
We design an anchor-based position encoding mechanism in Section 4.1, which reflects the relative topological position to labeled nodes and further maximizes the label influence within a class. To evaluate the effectiveness of position encoding, we compare PASTEL with a variant PASTEL (w/o PE), which removes the position encoding and directly take the node features for metric learning in Eq. (7). Here we use the GCN as the backbone. As shown in Figure 5, the structure learning strategy of PASTEL contributes the most, which can achieve at most 25.5% improvement in terms of Weighted-F1 score with only node features. Although PASTEL (w/o PE) effectively improves the performance of backbones to some extent, the position encoding still benefits learning better structure to relieve the topology-imbalance with 1.0%-1.8% improvements than PASTEL (w/o PE).

5.
3.2 Impact of the Class-wise Conflict Measure. We designed a class-wise conflict measure in Section 4.2 as edge weights to guide learning structures with better intra-class connectivity. Here, we compare PASTEL with its two variants to analyze the impact of the class-wise conflict measure: (1) PASTEL (w/o CCM), which removes the class-wise conflict measure and directly takes the learned edge possibilities in Eq. (7) as the edge weights.

Analysis of Learned Structure (RQ3)
We analyze the learned graph by PASTEL in terms of visualization and structural properties. Figure 7, we visualize the original graph of Cora and the graphs learned by ReNode [7], SDRF [42], IDGL [10] and PASTEL using networkx. For clarity, the edges are not shown. The solid points denote the labeled nodes, the hollow points denote the unlabeled nodes, and the layout of nodes denotes their connectivities. The node size in Figure 7(b) denotes the learned node weight in ReNode, and the solid lines and dashed lines in Figure 7(c) denote the added and deleted edges by SDRF, respectively. As we can observe, ReNode gives more weights to nodes in the topology center of each class and SDRF tends to build connections between distant or isolated nodes. Even though the structure learned by IDGL can make the nodes of a class close, there are still some overlapping and entangled areas between classes. Benefiting from the position encoding and class-wise conflict measure, PASTEL can obtain graph structure with clearer class boundaries.

Change of and .
We also show the reaching coefficient and the squashing coefficient of the above graphs in Figure 7 and the Weighted-F1 score learned on them in Table 4. Here we choose the GCN as the model backbone. All of the structure learning methods (SDRF [42], IDGL [10] and PASTEL) learn structures with larger reaching coefficient and larger squashing coefficient, leading the performance improvement of node classification. This phenomenon supports our propositions in Section 3.3 again.

5.4.3
Change of GPR Vector. The class-wise conflict measure is calculated by the Group PageRank (GPR), which reflects the label influence of each class. We randomly choose 10 nodes for each class in Cora and show their GPR vectors P in the original graph in Figure 8(a) and the learned graph in Figure 8(b), respectively, where the color shade denotes the magnitude, denotes 10 nodes of class and denotes the -th class. In Figure 8(a), the off-diagonal color blocks are also dark, indicating that the label influence of each class that nodes obtained from the original graph is still entangled to some extent, which could bring difficulties to the GNN optimization. After the structure learning guided by the proposed class-wise conflict measure, Figure 8(b) exhibits 7 clear diagonal blocks and the gaps between the diagonal and off-diagonal block are widened, indicating that nodes can receive more supervision information of its ground-truth class. We can further make a conclusion that the class-wise conflict measure plays an important role on giving guidance for more class connectivity orthogonality.

CONCLUSION
We proposed a novel framework named PASTEL for the graph topology-imbalance issue. We provide a new understanding and two quantitative analysis metrics of topology-imbalance in the perspective of under-reaching and over-squashing, answering the questions that how topology-imbalance affects GNN's performance as well as what graphs are susceptible to it. PASTEL designs an anchor-based position encoding mechanism and a class-wise conflict measure to obtain structures with better in-class connectivity. Comprehensive experiments demonstrate the potential and adaptability of PASTEL. An interesting future direction is to incorporate the proposed two quantitative metrics into the learning process to address topology-imbalance more directly.