Imbalanced Node Classification Beyond Homophilic Assumption

1 Introduction

Graph Neural Networks (GNNs) successfully extend deep learning approaches to graph data and have exhibited powerful learning ability on node classification task [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Liu et al., 2023]. Despite their effectiveness, most existing GNNs neglect the widely existing class-imbalance problem in real-world networks, where certain class(es) have significantly fewer node samples for training than other classes [Sun et al., 2021b]. For example, in online transaction networks, the majority of nodes are normal customers while only a small number are fraudsters; in molecular networks, there are much more lowmass atoms than high-mass atoms. Due to the dominating role of majority class nodes in the training set, classical GNNs are often highly inclined to majority classes, leading to severe performance degradation for minority node classification.

† Corresponding authors.

To address the class-imbalance problem in the node classification task, many methods have been proposed recently. They mainly relieve the imbalance problem by generating synthetic nodes for minority classes and further constructing synthetic edges between the generated nodes and the original nodes. For example, GraphSMOTE [Zhao et al., 2021] generates synthetic nodes by interpolating nodes of the same minority class through SMOTE [Chawla et al., 2002] and generates their linkages through a pre-trained edge generator. ImGAGN [Qu et al., 2021] also synthesizes minority class nodes and connects them to real minority class nodes through a generative adversarial network. GraphENS [Park et al., 2022] further synthesizes the whole ego networks for synthetic minority nodes based on information from both minority and majority classes.

Although having acquired prominent performances on certain imbalanced datasets, these existing methods are based on the homophily assumption that edges tend to connect nodes of the same class label (Figure 1(a)). However, many investigations [Sun et al., 2021a; Yu et al., 2020] show that heterophilic connections which link nodes of different classes also widely exist in imbalanced graphs (Figure 1(b)). Existing imbalanced node classification methods suffer from three severe problems when applied to networks with a large portion of heterophilic connections. P1: Most existing methods generate synthetic nodes based on homophilic interpolation, which restricts interpolated node pairs to be the same minority class. This causes synthetic nodes to lack diversity when real minority class nodes are very limited. P2: Existing models mainly resort to node feature similarity for synthetic edge construction. This strategy works well for homophilic edges which connect nodes with similar features but fail in constructing heterophilic edges and would thus introduce structure bias (i.e., heterophilic/homophilic edge distribution drift). P3: Existing methods conduct uniform message passing for both homophilic and heterophilic edges when aggregating features, and consequently result in much noisy information from dissimilar neighbors derived from heterophilic edges to be aggregated into the target nodes. This would seriously degrade the quality of node embeddings and hurt the following node classification task.

In light of this, we propose a novel Subgraph-aware Adaptive Graph Neural Network (GraphSANN) for imbalanced node classification on both homophilic and heterophilic graphs. GraphSANN consists of three major components, i.e., unified feature mixer, adaptive subgraph extractor, and multi-filter subgraph encoder. Specifically, to tackle P1, GraphSANN first applies a unified feature mixer to carry out both homophilic and heterophilic interpolation in a unified way. Next, to tackle P2, instead of generating edges based on feature similarity, we propose an adaptive subgraph extractor to extract the surrounding subgraphs of candidate synthetic edges with flexible ranges. In this way, distant but similar nodes can be absorbed into the subgraph whose general structural information will be encoded to predict the existence of the edge. To tackle P3 and encode the subgraphs consisting of both homophilic and heterophilic connections, we design a multi-filter subgraph encoder to aggregate messages only from similar nodes instead of dissimilar ones by fusing the output messages of three distinct filters. Finally, after generating synthetic nodes/edges and attaching them to the original graph, we apply a multi-filter GNN as node classifier to encode the acquired balanced graph for node classification.

The major contributions of this work are stated as follows:

• To the best of our knowledge, this paper is the first work to tackle the imbalanced node classification problem beyond the homophilic assumption.
• We design a novel imbalanced node classification model GraphSANN which is able to build balanced graph by generating synthetic nodes and constructing both homophilic
• and heterophilic synthetic edges between generated and original nodes, and aggregates the information from homophilic and heterophilic neighbors discriminatively.
• Extensive experiments on eight benchmark datasets show that GraphSANN acquires superior performance on both imbalanced homophilic and heterophilic graphs.

2 RelatedWork

2.1 Heterophilic Graph Neural Networks

Since most existing GNNs follow the homophily assumption and thus face significant performance degradation on heterophilic graphs, heterophily-based GNNs have been proposed, which can be roughly categorized into two groups [Zheng et al., 2022]: (1) Neighbor extension methods which aim to expand local neighborhood to absorb features from distant but informative nodes. For example, MixHop [Abu-El-Haija et al., 2019] aggregates messages from multi-hop neighbors respectively and mixes them together through concatenation. UGCN [Jin et al., 2021] further restricts nodes from two-hop neighbors to have at least two different paths to the ego node. (2) Adaptive message aggregation methods which design adaptive aggregation operations to learn discriminative information from homophilic and heterophilic linkages. For example, FAGCN [Bo et al., 2021] adopts a self-gating attention mechanism to uniformly learn low-frequency and high-frequency signals from neighbors. ACM [Luan et al., 2022] further designs a linear combination of low-pass and high-pass filters to adaptively learn information from different filter channels.

2.2 Imbalanced Node Classification

Generally, imbalanced node classification methods can be divided into two groups, generic and network-specific methods. Generic ones directly combine general class-imbalance approaches (e.g. oversampling, re-weight, SMOTE [Chawla et al., 2002], etc.) with GNNs to graph data. For example, Oversampling [Buda et al., 2018] replicates existing node embeddings learned from GNNs to produce more minority node representations; Re-weight [Yuan and Ma, 2012] assigns larger penalty weights to minority nodes when computing training loss. Network-specific methods usually take account of the sophisticated topology of graphs to generate synthetic nodes and further determine the connections between the generated nodes and original nodes [Chen et al., 2021; Xia et al., 2021]. Among them, DR-GCN [Shi et al., 2020] utilizes class-conditional adversarial training to enhance the separation of different classes. GraphSMOTE [Zhao et al., 2021] interpolates nodes from minority classes as synthetic nodes and generates linkages through a pre-trained edge generator. ImGAGN [Qu et al., 2021] synthesizes minority nodes and connects them to original nodes through a generative adversarial network. GraphENS [Park et al., 2022] demonstrates the overfitting problem of neighbor memorization and proposes to generate the whole ego-networks for synthetic nodes based on information from all classes.

However, these models are all based on the homophily assumption and thus suffer from performance degradation when applied to networks with strong heterophily.

3 Notations and ProblemDefinition

Definition 1. Graph Homophily and Heterophily. Given a graph G = {V, E}, where V represents the node set, and for each edge e = (v, µ), v, µ ∈ V, if v and µ have the same class label, the edge e is homophilic. Otherwise, e is heterophilic. Most graphs have both homophilic and heterophilic edges at the same time. We define the node homophily Hnode and edge homophily Hedge to quantitatively measure the homophily degree of a graph as follows.

Based on the definitions of Hnode,Hedge ∈ [0, 1], the node heterophily and edge heterophily can be defined as 1-Hnode and 1 -Hedge, respectively. Graphs with strong homophily have higher Hnode and Hedge, and vice versa.

Problem Definition. Let G = {V, E,X} denote an attribute graph, where X ∈ R|V|×d is node feature matrix whose ith row represents a d-dimensional feature vector of the ith node. For node classification, each node is also associated with a one-hot node label Yi,: ∈ RC where C is the number of node classes. If the class size distribution is imbalanced, we name it as an imbalanced node classification problem. The imbalance ratio is defined as im ratio = minc(|Vc|) maxc(|Vc|) ≪ 1, where |Vc| denotes the node set with class label c ∈ {1, 2, · · · ,C}. Then, we give the formal definition of imbalanced node classification as follows.

Given an imbalanced graph G = {V, E,X} composed of both homophilic and heterophilic edges, our goal is to learn a node classifier f : f(V, E,X) → Y that can well classify both majority and minority classes and can be well generalized on graphs with either low or high heterophily.

4 Methodology

In this section, we introduce our novel GraphSANN for imbalanced node classification. As illustrated in Figure 2, GraphSANN consists of three core components, (1) Unified Feature Mixer which carries out both homophilic and heterophilic interpolation to generate synthetic nodes (Subsection 4.1); (2) Adaptive Subgraph Extractor which adaptively extracts subgraphs around candidate synthetic edges (Subsection 4.2) and (3) Multi-filter based subgraph encoder which encodes the subgraphs extracted from component (2) into edge score using multiple passes of filters (Subsection 4.3). Please refer to Algorithm 1 in the Appendix for the forward propagation procedure of GraphSANN . We elaborate on each component in the following subsections.

4.1 Unified Feature Mixer

Most existing class-imbalance models apply homophilic interpolation on existing node pairs < vs, vt > to generate synthetic nodes, which restricts vs and vt to be the nearest neighbors of the same minority class [Zhao et al., 2021;

Qu et al., 2021]. The generated nodes under this strategy suffer from feature diversity problem especially when original minority nodes are very limited [Park et al., 2022]. To address this problem, we propose a unified feature mixer that conducts both homophilic and heterophilic interpolation in a unified way, which consists of two steps: (1) unified node pair sampling and (2) integrated gradient based feature mixup.

Unified Node Pair Sampling

Before conducting feature mixup to generate synthetic minority nodes, we first sample node pairs < vs, vt > from the existing node set for interpolation. Here vs is sampled from minority classes while vt is from the entire classes, and thus it could have either the same or different class compared to vs, formed as Spair = {< vs, vt >| vs ∈ Vminor, vt ∈ V}. Let C = {1, 2, . . . , C} and CM ⊂ C be the entire class set and minority class set, the sampling distributions for vs and vt are denoted as vs ∼ ps(u | CM) and vt ∼ pt(u | C), respectively. To obtain a uniformly sampling vt from all the classes, we define ps and pt as follows:

It is straightforward to get that pt reaches the peak when |Vc| = 2 and gets 0 when |Vc| = 0 or |Vc| = ∞. In this way, even if the sizes of majority classes are significantly larger than minority classes, nodes from the entire classes have roughly equal chances to be sampled as vt. Here we use over-sampling scale ζ to control the amount of sampled node pairs.

Integrated Gradient based Feature Mixup

Afterward, we interpolate the raw features of each node pair < vs, vt > to generate synthetic nodes. Since vt is sampled beyond the same minority class as vs, we only preserve generic node attributes which are irrelevant to class prediction to avoid introducing distracting information. As introduced by [Sundararajan et al., 2017], integrating gradient can effectively evaluate the contributions of input features to the model prediction. Compared to directly using gradients to evaluate feature importance [Park et al., 2022], integrated gradient addresses the saturation and thresholding problems [Shrikumar et al., 2017] and can acquire more reliable feature importance. Specifically, the integrated gradient IGi(x) along the i-th dimension of input node feature x ∈ Rd is calculated as follows:

where y represents the vector of true class labels and Lcls denotes the node classification loss. Then, we compute the distance ψst between vs and vt by:

where Wp ∈ Rd×d′ represents the projection matrix, and xs and xt are raw attributes of vs and vt, respectively. We define ˆ ψst = 1 1+ψst ∈ [0, 1] as the similarity between vs and vt. Finally, we construct the masking vector Mt ∈ Rd as follows:

where It ∈ Rd is an all-ones vector, κ is a hyper-parameter, Dt = [IG1(xt), . . . , IGd(xt)] is the feature importance vector for xt, and 1R+(·) is an indicator function which returns 1 when the input is positive otherwise 0. Thus, the mixed feature xsyn of synthetic nodes is formulated as follows:

4.2 Adaptive Subgraph Extractor

After generating synthetic nodes vsyn ∈ Vsyn for the minority classes, we need to determine their connections to the original graph. The existence of an edge e = (vsyn, u) is highly related to the structural information embedded in its surrounding subgraph Ge = {Ve, Ee} regardless of its homophily or heterophily [Zhang and Chen, 2018]. Here, we first randomly sample connections between synthetic and original nodes as candidate edges, then we adaptively extract the subgraphs of candidate edges and finally encode their structure information to predict edge existence. Specifically, given the node pair set Spair and synthetic node set Vsyn, the candidate synthetic edge set Esyn is constructed as follows:

where N1(v) returns 1-hop neighbors of v and v itself, [·]ξ is random sampling with sampling ratio ξ. After obtaining Esyn, we extract the enclosing subgraph Ge for each e ∈ Esyn. Considering that nodes with high structural and semantic similarities might be distant from each other in heterophilic graphs, instead of fixing the subgraph to h-hop neighbors, we adaptively adjust the range of a subgraph based on a relevance score function frel(·). For any h-hop neighbor k ∈ Nh(v) ∪Nh(u), frel(k) is calculated as follows:

Where δ(k, v) is the length of shortest path from k to v, αk,i ∈ R3 represents the multi-pass weight vector between node k and i (further illustrated in Subsection 4.3). α(l) k,· is the mean value of all the coefficient vectors between k and its 1-hop neighbors, which reflects the homophily status of node k. Wk ∈ R3×3 is a weight matrix. Then we select top M nodes from frel(k) along with central nodes u and v to construct the enclosing subgraph. The M is calculated based on subgraph density: M = ⌈|Ve|(1+ 2|Ee| |Ve|(|Ve-1|) )⌉.

4.3 Multi-filter Subgraph Encoder

In this section, we propose a novel subgraph encoder to embed the subgraph surrounding a candidate edge e ∈ Esyn into a vector, and then predict whether the edge e should be generated or not based on that. Let Ge be the extracted enclosing subgraph of the candidate edge e. Considering the widely existing heterophilic connections in Ge, we design a multi-filter subgraph encoder that can discriminatively aggregate information from homophilic and heterophilic neighbors. Specifically, let h(l-1) u ∈ Rdl-1×1 denote the (l - 1)- th layer feature of node u ∈ Ge, h(0) u = [xu ∥ zu] where zu is one-hot labeling feature acquired by DRNL[Zhang and Chen, 2018]. We now compute the weight coefficients α(l) L,(u,k) , α(l) H,(u,k) , α(l) I,(u,k) which reflect the importance of different frequencies of signals as follows:

Where W(l) L ,W(l) H , W(l) I ∈ Rdl×dl-1 are the weight matrices that project h(l-1) u into low-frequency, high-frequency and identity messages, respectively. gT L ∈ R2dl×1 , gTH , gT I ∈ Rdl×1 are the convolutional vectors, σ(·) is the Sigmoid function. Then we compute weight vector α(l) (u,k) by normalizing the importance weights of different frequencies:

Next, we aggregate multi-frequency messages of neighbor nodes k with weight vector α(l) (u,k) to compute the central node embedding h(l) u :

Where ω is a hyper-parameter, h(L) u denotes the aggregated node embedding of node u ∈ Ge after stacking L-layer encoders. To acquire structural information from different orders of neighbors, we concatenate node embeddings from different layers and utilize a mean readout to compute the existence probability pe of subgraph Ge:

Where Wpool ∈ R1×(d1+...+dL) projects the latent embeddings into a scalar pe which reflects the existence probability of synthetic edge e. We remove the edges with low pe from Esyn based on threshold η and attach the rest of synthetic edges to the original graph to construct the adjacency matrix ˜A after over-sampling:

4.4 Optimization Objective

In this section, we introduce the optimization objective of our proposed GraphSANN for imbalanced node classification, which consists of two optimization tasks: 1) adjacency matrix reconstruction and 2) node classification.

Adjacency Matrix Reconstruction. We train our multi-filter subgraph encoder with an adjacency matrix reconstruction task. Let A denote the adjacency matrix of the original graph, and A(u, v) = 1 indicate the existence of an edge between u and v. Considering the sparsity of positive edges, we also adopt negative sampling [Zhou et al., 2022]. Specifically, for each positive edge A(u, v) = 1, we randomly sample an unlinked edge which makes A(u, m) = 0 as a negative sample and constructs a negative set M-. The loss function for adjacency matrix reconstruction is formed as follows:

where ˆA is the predicted adjacency matrix of original graph. Node classification. After attaching the synthetic nodes and edges to the original graph, we transform it into a balanced network. Since the balanced graph can also be heterophilic, we adopt the multi-filter graph encoder introduced in 4.3 as node classifier by replacing the readout procedure with a onelayer MLP followed by Softmax:

The output dimension of MLP(·) is equal to class number C. The loss function of node classification is defined as follows:

The overall objective function is then formed as follows with λ ∈ (0, 1]:

5 Experiment

In this section, we conduct extensive experiments on eight public datasets to evaluate the effectiveness of GraphSANN, which aim to answer five research questions: RQ1: How does GraphSANN perform compared to other baselines in imbalanced node classification on both homophilic and heterophilic graphs? RQ2: How effective is GraphSANN under different imbalance ratios? RQ3: How does each core component of GraphSANN contribute to the performance gain? RQ4: How do different hyper-parameter values affect the performance of GraphSANN ? RQ5: Can GraphSANN learn effective node representation to separate different classes of nodes in the embedding space?

5.1 Experimental Setup

Datasets. To thoroughly evaluate the performance of GraphSANN , we conduct experiments on eight benchmark datasets including six artificial imbalanced datasets and two genuine ones. Among the artificial datasets, Cora, Citeseer and Pubmed are three citation networks with high homophily, while Chameleon, Squirrel and Film are three Wikipedia networks with high heterophily. 3, 3, 2, 2, 2, and 2 classes are randomly selected as minority classes for these six datasets by down-sampling. Following [Zhao et al., 2021], all majority classes have 20 nodes while minority classes only have 20 × im ratio nodes in the training set. For two Amazon product networks whose class distributions are genuinely imbalanced, we use their original class ratios. The detailed statistical information of the six datasets is summarized in Table 1.

Baselines. We compare GraphSANN with eight state-ofthe-art baselines for imbalanced node classification problem, including two vanilla models: GCN [Kipf and Welling, 2017] and ACM [Luan et al., 2022]; two generic classimbalance methods: Oversampling and Reweight; and four network-specific methods: DR-GCN [Shi et al., 2020], ImGAGN [Qu et al., 2021], GraphSMOTE [Zhao et al., 2021] and GraphENS [Park et al., 2022]. Please refer to Appendix 7.5 for detailed descriptions of each baseline.

Evaluation Metrics. Following existing works [Zhao et al., 2021] in evaluating imbalanced classification, three evaluation metrics are adopted in this paper: Accuracy, AUC-ROC, and Macro-F1, where both AUC-ROC and Macro-F1 are reported by averaging the metrics over each class.

Parameter settings. The following hyper-parameters are set for our model in all the datasets. Layer number L = 2 with hidden dimensions 64 and 32 for both edge generation and node classification. Adam optimizer with learning rate lr = 0.001 for homophilic graphs and 0.01 for heterophilic graphs. Dropout rate γ = 0.7. Epochs = 2000 with early stop strategy. Weight decay= 5e-4. Hyper-parameters κ = 1.05, ω = 0.3. Initial hop h = 2, threshold η = 0.5 and loss weight λ = 1e-6. Sampling ratio of candidate edges ξ = 0.3. Over-sampling scale ζ = 1.0.

5.2 Imbalanced Node Classification (RQ1)

To answer RQ1, we compare the node classification performance of GraphSANN with other baselines across all eight datasets and report the average performances along with standard deviations of each metric. Table 2 shows the node classification results for six imitative datasets and two genuine datasets. From the table, we can observe that: (1) GraphSANN outperforms all the other baselines by all metrics on all eight datasets. This indicates our proposed model consistently acquires better performance on either homophilic or heterophilic networks. (2) On three heterophilic datasets, most class-imbalance baselines only acquire slightly better, or even worse performance (e.g. DR-GCN on Film and GraphSMOTE on Squirrel) than vanilla models i.e., GCN or ACM. This is because these baselines rely on homophilic assumption and generate synthetic edges based on feature similarity. Thus they perform poorly on heterophilic graphs whose edges link nodes with dissimilar features. GraphSANN, however, thanks to the adaptive subgraph extractor and multi-filter encoder blocks, can discriminatively aggregate similar node features to generate heterophilic edges, and thus achieve significant performance gains over the baselines. (3) On genuine datasets, compared to the most competitive baseline GraphENS, GraphSANN still acquires 4.5%

and 3.6% performance gains w.r.t. F1-score on AmazonComputers and Amazon-Photo, respectively.

5.3 Influence of Imbalance Ratio (RQ2)

To answer RQ2, in this subsection, we further compare the performance of GraphSANN with other baselines under different im ratios. The imbalance ratio varies from 0.1 to 0.6. Each experiment is repeated 5 times and the average results are reported in Figure 3. From Figure 3, we can observe that (1) GraphSANN consistently outperforms other baselines across all the imbalance ratios on all the datasets, this demonstrates the generalization and robustness of our model under different imbalanced scenarios. (2) Generally, GraphSANN has more significant performance improvement over other baselines under more extreme imbalance ratios. As imbalance ratio increases, the datasets become more balanced, which offsets the effects brought by node/edge augmentation.

5.4 Ablation Study (RQ3)

To further investigate the contribution of each component of GraphSANN, we perform an ablation study and report the results in Table 3. w/o UFM replaces the unified feature mixer component with simple SMOTE strategy [Chawla et al., 2002]; w/o ASE replaces the adaptive subgraph extractor with fixed 2-hop neighbors of target edge to form subgraphs; and w/o MSE replaces multi-filter subgraph encoder component with a raw GCN. GraphSANN represents the full model with all the components available. From this table, we can observe that: (1) All three components contribute to the performance improvement of GraphSANN ; (2) Adaptive subgraph extractor and multi-filter encoder exhibit crucial effects on heterophilic networks in view of sharp performance drops between w/o ASE and GraphSANN and between w/o MSE and GraphSANN on Chameleon.

5.5 Parameter Sensitivity Study (RQ4)

In this subsection, we investigate the impact of two crucial hyper-parameters, i.e., dropout rate γ of adaptive classifier and sampling ratio ξ of candidate synthetic edges on model performance. We vary γ from 0.1 to 0.9 with step size 0.1 and vary ξ from 0.01 to 0.9. The experiments are conducted on both Cora and Chameleon and test accuracy curves are shown in Figure 4. From Figure 4, we can observe that: (1) As γ increases, model performance gradually rises and reaches peak values when γ reaches 0.7 on both datasets. Then, as dropout rate keeps increasing, the performance gradually drops. (2) The performance decreases as the sampling ratio is under 0.3 or over 0.5. Our explanation is that the original edge distribution is not sufficiently simulated at low ξ, while a high ξ impedes feature aggregations by introducing too many noisy edges, resulting in performance degradation.

5.6 Visualization (RQ5)

In this subsection, we project the latent node embeddings of GraphSANN and the most competitive baseline GraphENS on Cora into two-dimensional space using t-SNE [Van der Maaten and Hinton, 2008] and color the nodes based on their class labels. As shown in Figure 5, we can observe that the minority class representations of GraphENS (e.g. blue and dark cyan dots) are hard to be distinguished and have large mixed areas with majority clusters, while node representations of GraphSANN are clustered tightly together with clear boundaries for both majority and minority classes. This proves the superiority of GraphSANN in terms of embedding quality for separating different classes despite the classimbalance problem.

6 Conclusion

In this paper, we design a novel GraphSANN for imbalanced node classification on both homophilic and heterophilic graphs. The elaborately designed three components within it can unifiedly interpolate synthetic nodes, adaptively extracts surrounding subgraphs of candidate synthetic edges, and discriminatively encode them to predict the existence of synthetic edges. Extensive experiments on eight benchmark datasets have demonstrated the superiority of GraphSANN.

Acknowledgments

This work is partially supported by The National Key Research and Development Program of China (Grant No. 2020AAA0108504), Australian Research Council Future Fellowship (Grant No. FT210100624), Discovery Project (Grant No. DP190101985), and Discovery Early Career Research Award (Grant No.DE200101465).