Multi-Class Imbalanced Graph Convolutional Network Learning

1 Introduction

Graphs are commonly used to encode both direct and implicit relationships between objects, e.g., in a social network the interconnected users tend to share similar interests and represent a unique class collectively [Lee et al., 2018]. Accordingly, current graph-based data mining tasks such as graph representation learning or embedding mainly focus on modeling the relative affinities between nodes from both topological and attribute content perspectives [Zhang et al., 2020], such that nodes belonging to same classes (e.g., "research area" in a citation network) can be clustered together in the embedding space. In the past, significant research efforts have been applied to supervised or semi-supervised graph neural models [Wu et al., 2020], including the recently proposed Graph Convolutional Networks (GCN) [Kipf and Welling,

2016] and many its variants [Zhang et al., 2019]. These methods typically adopt an end-to-end learning paradigm by training a node-level multi-class classifier after convolutional representation learning from the input graph [Veliˇckovi´c et al., 2018], i.e., each node forms its representation by aggregating features from all immediate neighborhoods. Despite the remarkable performance achieved in many application domains such as text classification [Yao et al., 2019], image recognition [Chen et al., 2019] and recommender systems [Wang et al., 2019], existing methods often assume that the input class distributions are nearly or perfectly balanced, i.e., balanced label samples for each class are deliberately provided to ensure representation learning equilibrium across multiple classes thereby avoiding the class imbalance problem entirely.

However, many real-world datasets naturally demonstrate highly-skewed class distributions due to the asymmetric and unrestricted evolution of different parts in these real-world graph-based systems [Huang et al., 2016]. For example, in the NCI chemical compound graph [Pan and Zhu, 2013], only about 5% of molecules are active in the anti-cancer bioassay test. In the Cora citation network [Lin and Cohen, 2010], 26.8% of the papers belong to the Neural Network domain Rule Learning and Reinforcement Learn-

ing domains which only contain 7.9% and 4.8% respectively. When generalizing to graphs with an imbalanced class distribution, existing GCN methods have a tendency to overfit to majority classes, resulting in undesirable embedding results for the minority classes. For example, Figure 1 presents the node classification result for each class on the Cora citation network, where L1 and L6 are minority classes (i.e., they contain far fewer instances than other majority classes such as L0). We observe that, in most cases, nodes from all seven classes can be correctly classified in the balanced setting, whereas for imbalanced setting, nodes from the two minority classes, L1 and L6, are frequently misclassified.

The main issue of class-imbalanced learning lies in that one or more classes may severely overrepresent others, which significantly compromises the performance of most standard learning algorithms [He and Garcia, 2009]. This issue is exacerbated in the case of graph-structured data due to the following two reasons:

• Topological Interplay: In addition to rich features associated with each graph node, different nodes can have

frequent topological connections with each other, meaning the class assignment for each node is no longer simply determined by its respective features but is also strongly impacted by its connected nodes.

• Unclear Boundaries: Graph data often involve multiple highly-skewed node classes, which makes it hard to balance representation learning with accurately identifying class boundaries since the learning of a particular class could be seriously impacted by other nearby class structures throughout the graph, i.e., the majority classes would dominate feature propagation between nodes.

In this paper, we focus on a more general setting of multiclass imbalanced graph learning and develop a novel graph convolutional network incorporating two types of regularization. To the best of our knowledge, this is the first work that studies the node-level class-imbalanced graph embedding problem with graph neural networks. In the proposed framework, we first use a two-layer graph convolution network to derive node representations trained on classimbalanced labels. To make representation learning for different classes of node more distinguishable (e.g., clear boundaries), we incorporate a conditional adversarial training process to help separate the labeled node representations of different classes. In addition, to reduce the negative propagation influence from the convolution training of majority classes enforced on their structure-nearby minority classes, we train all unlabeled nodes to fit a similar data distribution to the well-trained labeled nodes in the learned embedding space, which promotes counterbalanced training between majority and minority classes.

In summary, our contribution is twofold: 1) we propose to study a node-level graph embedding problem that takes class distribution into account; 2) we propose DR-GCN, adopting a conditional adversarial training together with distribution alignment to learn robust node representations for both majority and minority classes.

2 RelatedWork

Graph neural networks. Driven by the promising learning capability of deep neural networks on grid-like data (e.g., images), Graph Neural Networks (GNNs), architectures designed with non-Euclidean geometric data in mind, have seen an explosion in attention over these past five years [Wu et al., 2020]. In essence, GNNs seek to exploit the characteristics of geometric data to provide a more powerful mechanism by which node representations are generated using both structural and contextual information. Graph Convolutional Networks (GCN) [Kipf and Welling, 2016] use a spectralbased convolution filter through which a node's features are aggregated from its direct neighborhood. Such convolution learning has been proven efficient and successfully applied in many problem domains [Yao et al., 2019]. Graph Attention Networks (GAT) [Veliˇckovi´c et al., 2018] are another recently proposed class of end-to-end GNNs similar to GCN, which introduce an attention mechanism that assigns larger weights to more important nodes, walks, or models. Some other useful feature aggregation methods have been proposed [Hamilton et al., 2017], including the Tree-LSTM [Tai et al., 2015] that learns representations for parent nodes by using child-sum tree long short-term memory networks to gather information from all child nodes.

Class imbalanced learning. Class imbalanced learning is a long-standing challenge faced by machine learning [Sun et al., 2009], which aims to avoid model learning bias towards majority classes by lifting the influence of minority classes [Japkowicz and Stephen, 2002]. Conventional methods address this problem either from the data or algorithm level [He and Garcia, 2009]. The data level approach tries to rebalance the prior class distributions through a pre-processing step including over-sampling minority classes [Chawla et al., 2002] or under-sampling majority classes [Drummond et al., 2003]. However, these techniques could cause over-fitting or discard valuable information. In comparison, approaches at the algorithm level seek to modify existing algorithms to emphasize minority classes such as cost-sensitive learning [Dong et al., 2018].

3 ProblemDefinition and Preliminary

3.1 ProblemDefinition

Given a graph with imbalanced node label distributions represented by G = (V,E,X, L), where V = {vi}i=1,··· ,n is a set of n unique nodes, E = {ei,j}i,j=1,··· ,n; i̸=j is a set of edges that can be equal to a n × n adjacency matrix A, with Ai,j = 1 if ei,j ∈ E or Ai,j = 0 otherwise, and self-loops removed. X is a matrix Rn×m containing all n nodes with their associated features, i.e., Xi ∈ Rm is the feature vector of node vi, where m is the number of unique features in the graph. Graph G has multiple classes, denoted by L = {Lk}k=1,··· ,|L| , that partition G to |L| clusters, where each class Lk categorizes a set of similar nodes. The class distribution may be highly-skewed as one or more classes contain many more nodes than others, i.e., |L1| ≫ |L2|. In such a case, L1 belongs to the majority classes while L2 belongs to minority classes.

The task in this paper is to represent graph G in a ddimensional semantic space Hd with naturally imbalanced class labels for semi-supervised training, i.e., randomly sample a few labeled instances from the whole node population.

During training, the node space V = Vl ∪Vu is actually the union of labeled (Vl) and unlabeled (Vu) nodes both with imbalanced class distributions.

3.2 Conditional Generative Adversarial Networks

Conditional Generative Adversarial Networks (cGAN) [Mirza and Osindero, 2014] consist of two components: a generator G(z|y) that maps the noise data z (e.g., sampled from a prior distribution z ∼ pz(z)) to the real data distribution space, and a discriminator that assigns probability D(x|y) to indicate whether or not x is a given real training sample or the probability (1-D(x|y)) to indicate x is a fake generated sample (e.g., x = G(z|y)). The training of cGAN tries to find the optimal discrimination between the real and fake samples, and meanwhile encourages G(z|y) to approach the real data distribution. The objective of optimizing these two aspects is given as:

Both D and G are conditioned on some information y (e.g., class labels), thus G can finally generate samples associated with y and D can well discriminate samples bound with y of varying value assignments.

4 The ProposedMethod

The proposed DR-GCN model for multi-class imbalanced graph learning is shown in Figure 2, which involves three cooperative components as follows.

4.1 Class-Imbalanced Convolution Learning

In this paper, we adopt two-layer graph convolutional network [Kipf and Welling, 2016] to perform node-level representation learning on the input graph G, where the first-order and second-order neighborhood relations can be sequentially modeled as:

Here, ˜A = ˜D- 12 (A + I)˜D- 12 is the normalized symmetric adjacency matrix, where I is the identity matrix and ˜Dii = ∑j (A+ I)ij. W0 ∈ Rm×r and W1 ∈ Rr×d are respectively the learned parameters for the first and second convolution layers, where r is the dimensionality of the first layer hidden representation. ReLU is the activation function represented by f (x) = max(0, x).

The second-layer node embeddings have the same dimension as the number of classes (i.e., d = |L|) passed through a softmax classifier to perform multi-class node classification training by:

Eq. (4) computes the cross-entropy error of classification results, where Vl is a set of labeled training nodes and Y ∈ Rn×|L| is the one-hot label indicator matrix of graph nodes.

In opposition to the deliberately balanced training samples in existing works [Kipf and Welling, 2016; Veliˇckovi´c et al., 2018] (i.e., each training class has a similar number of labeled nodes), we focus on the more practical case of naturally class-imbalanced distributions, i.e., Vl is constructed with randomly sampled nodes from the whole population. However, as demonstrated in Figure 1 traditional GCN fails to handle the class-imbalanced graphs, we thus introduce two types of regularization training to mitigate this problem.

4.2 Class-Conditioned Adversarial Regularization

With standard convolutional learning under the imbalanced setting, the minority classes could be easily assimilated by nearby majority classes. To enhance the separation of different classes, we impose a conditional adversarial training on all labeled nodes. For each real training sample x ∈ Vl (e.g., v6) with its class indicator y (e.g., one-hot vector), the generator takes a noise z generated from the prior normal distribution z ∼ pz(z) as input, which then transforms to a reallike fake sample gx (e.g., g6) after a concatenation with y and through learning with a standard multi-layer perceptron (MLP). On the other hand, the discriminator learns to classify the real and fake samples conditioned on y. To improve the learning capacity of generator, we add a regularization that forces the generated fake node could reconstruct the respective neighborhood relations (e.g., g6 has similar topology role as v6) in the graph by:

where Eq. (5) denotes the pairwise distance between gx and x's neighbors N(x). Finally, the adversarial training objective is given as:

Eq. (6) is trained in a mini-batch fashion with balanced training classes. The main idea of the adversarial training is that while the discriminator learns to correctly classify training samples conditioned on different classes, it would in return encourage the convolution layers to learn distinguishing representations for different classes of nodes.

4.3 Latent Distribution Alignment Regularization

While the adversarial training can promote distinguishing results for labeled nodes, it could lead to overfitting within the labeled space, leaving the minority classes in the unlabeled space under-trained [Japkowicz and Stephen, 2002; He and Garcia, 2009]. We thus propose imposing a distribution alignment training between labeled and unlabeled node representations, where the assumption is that balanced convolution training across multi-imbalanced classes in the unlabeled space will be enforced in order to match the welltrained class-imbalanced nodes in the labeled space.

We assume that representations in labeled space (e.g., hxl ∈ Hd , xl ∈ Vl) and unlabeled space (hxu ∈ Hd , xu ∈ Vu) follow two d-dimensional multivariate Gaussian distributions xl ∼ N(µl,Σl) and xu ∼ N(µu,Σu), where their probability density functions are given as:

where µl, µu ∈ Rd and Σl,Σu ∈ Rd×d are the mean and covariance, respectively. For the situation in which

Algorithm 1: Training the DR-GCN model

Input : An information network: G = (V,E,X,L) Output: The node embeddings: O ∈ Rn×d

Initialization: j = 1, training epoch I and M, batch size N, labeled set Vl and unlabeled set Vu that are both trainable through convolution layers by Eq. (2)

while j ≤ I do

O ← learn convolution representations by Eq. (2) N(µl, Σl) ← learn latent distribution from Vl N(µu, Σu) ← learn latent distribution from Vu L ← compute the classification loss by Eq. (14) [W0,W1] ← update network parameters in Eq. (2) for τ ∈ [1,M] do

x∆ ← sample a batch of N class-balanced training samples from Vl, where x∆ is trainable;

z∆ ← sample a batch of N noise data from z ∼ pz(z)

Update the generator with its stochastic gradient (where xk ∈ x∆ and zk ∈ z∆):

Update the discriminator and the convolution layers (e.g., W0 andW1) with their stochastic gradient:

end

j = j +1

end

class labels have no correlations with each other, Eqs. (7) and (8) can be respectively represented as the product of d independent Gaussian distributions with diagonal covariance matrices Σl = diag(σ2 l,1 , σ2 l,2 , · · · , σ2 l,d ) and Σu = diag(σ2u,1 , σ2u,2 , · · · , σ2u,d ) [Ahrendt, 2005] by:

where the parameters can be approximated from the labeled and unlabeled samples as:

We finally minimize the difference between N (µl, Σl) and N(µu,Σu) based on the Kullback-Leibler divergence (both Σl and Σu are non-singular) [Joyce, 2011] as:

4.4 AlgorithmTraining and Optimization

Algorithm 1 illustrates the proposed framework. DR-GCN is trained through three components: the standard convolution training in a semi-supervised manner, the conditional adversarial training to promote the distinguishing representations for various classes and the distribution alignment training that maintains the learning equilibrium between majority and minority classes. To avoid the strong constraints introduced by the distribution alignment training on the standard representation convolution learning, we combine them together by:

where α is set to balance the two aspects of training.

5 Experimental Setup

Datasets. We use four widely-used benchmark graph datasets [Wu et al., 2020], including Cora, Citeseer, Pubmed, and DBLP. The data statistics are summarized in Table 1. All four graphs are naturally class-imbalanced and their class distributions are shown in Table 2. We can observe that for each graph some classes contain much less number of nodes than others, i.e., for Cora dataset 29% of graph nodes belong to class L0 while only 7% belong to class L6.

Comparedmethods. We comparewith the following stateof-the-art embedding methods, including DeepWalk [Perozzi et al., 2014] that learns node representations based on the SkipGram model [Mikolov et al., 2013], Graph-LSTM [Tai et al., 2015], standard GCN [Kipf and Welling, 2016], GCN combined with random under-sampling (GCNRUS) [Liu et al., 2008] and GAT [Veliˇckovi´c et al., 2018] that all learn node representations from both graph structure and content with spectrum-based convolution filters. We also compare with two variants DR-GCNgan and DR-GCNdist that respectively incorporate the class-conditioned adversarial regularization and the latent distribution alignment regularization.

Settings. We evaluate the model by conducting node classification, graph clustering, and visualization, respectively. We randomly sample 3% of nodes from the entire graph for training as per label rates used by standard GCN methods. The remaining nodes are split into validation and testing sets where 10% are used for hyperparameter optimization, and 90% are used for testing respectively. For node classification, the performance is computed in terms of Accuracy (Acc) and AUC score [Kipf and Welling, 2016]. Each experiment is repeated 10 times and we report the mean values with standard errors. For graph clustering task, the k-means algorithm is used with learned node embeddings as inputs and the performance is computed w.r.t four metrics [Xia et al., 2014] including accuracy (Acc), precision, F1-score (F1) and normalized mutual information (NMI). For GCN-based methods, we set the hidden embedding size r as 10, the dropout rate as 0.3, the L2 norm regularization weight decay as 0.03 and the learning rate for the gradient decent algorithm as 0.002. We set the maximum training epoch I as 1000 with an early stopping of 200. In our approach, the default values for M, N and α are set as 1, |Vl|/2 and 0.7, where |Vl| is the total number of labeled nodes.

5.1 Node Classification

Experiment results. The classification results are shown in Table 3. We can observe that both DR-GCNgan and DRGCNdist perform better than GCN, which demonstrates the effectiveness of the introduced class-conditioned adversarial regularization and latent distribution alignment regularization for class-imbalanced node classification. In addition, on all four class-imbalanced graphs our DR-GCN model outperforms the random under-sampling method GCNRUS and other state-of-the-art methods such as GAT and GraphLSTM, which verifies the superiority of our approach.

Varying imbalance ratio. We test the performance of DRGCN w.r.t training ratio between minority class and majority class on Cora and Citeseer. For Cora dataset, we assume L1

and L6 as minority classes and L0 as majority class. Similarly, we assume L3 as minority class and L1 and L2 as majority classes for Citeseer. Then, we vary the ratio of training samples from minority classes and the ratio for majority classes is changed accordingly (e.g., in Table 2 for Cora the original training ratios for minority and majority classes are (9+7) and 29 percents, respectively. When the ratio for minority classes increases to 18 percent, thereby the ratio for majority classes is reduced to 27 percent). We can observe in Figure 3 that DR-GCN significantly outperforms CGN with various minority class ratios, which demonstrates our model shows better robustness for class-imbalanced graph learning.

Parameter analysis. Figure 4 shows the impact of parameter α to balance the standard convolution learning and the distribution alignment training in Eq. (14). On both Cora and Citeseer datasets, the classification performances first increase and then tend to decline with larger values of α.

5.2 Graph Clustering

Table 4 and Table 5 report the clustering results of all baselines. On both the Cora and Citeseer datasets, we can observe that DR-GCN consistently outperforms GCN, which again verifies the benefit of our regularized learning process. Although GAT has slightly better Acc performance than that of others on Cora, it has a rather poor performance w.r.t. Precision, F1, and NMI compared with DR-GCN on both Cora and Citeseer datasets. The clustering results demonstrate the superiority of our proposed learning frameworks.

5.3 Graph Visualization

Figure 5 shows the 2-D node embedding visualization results on the Cora dataset. Compared with GCN, we can observe that DR-GCN learns more discriminative node embeddings, especially for minority classes, such as L1 and L6, which account for 9% and 7% node population, respectively.

6 Conclusion

Real-world graph structured data usually present highlyskewed class distributions. The most critical challenge, when learning from class-imbalanced graphs, is that the nodes have strong topological interdependence, causing existing network representation learning methods to underperform on minority classes. In this paper, we proposed a novel dual-regularized graph convolutional network that contains a conditional adversarial training to enhance the separation of nodes from different classes and a distribution alignment training to enforce balanced learning between majority and minority classes.

We conducted extensive comparative studies to evaluate the proposed framework for both node classification and unsupervised graph clustering. The validations, visualizations, and comparisons from the experimental results demonstrated that the proposed DR-GCN model is effective to handle graph data with naturally imbalanced class distributions.

Acknowledgements

This research was sponsored in part by the U.S. National Science Foundation through Grant Nos. IIS-1763452 and CNS1828181.