PaperlayerView exact revision on arXiv

Source-linked AI summary

ImGAGN:Imbalanced Network Embedding via Generative Adversarial Graph Networks

Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, Hongzhi Yin

arXiv:2106.02817v1cs.LGcs.AI

TL;DR

Imbalanced graph classification is challenging because minority nodes are scarce and difficult to separate from majority nodes, while most existing GNNs target balanced networks. ImGAGN generates synthetic minority nodes using both attribute and topology distributions, then trains a GCN discriminator on the balanced graph. Experiments on four real-world datasets report superiority over state-of-the-art balanced and imbalanced network-embedding methods.

  • Problem

    Existing network-embedding methods generally assume balanced labels, whereas imbalanced graphs contain scarce minority nodes that are difficult to label and separate from majority nodes.

  • Method

    ImGAGN uses GraphGenerator to model minority-node attributes and topology, generate synthetic minority nodes, and train a GCN discriminator on the balanced network.

  • Results

    ImGAGN outperforms comparison methods on recall and AUC across all evaluated datasets and is superior to state-of-the-art balanced and imbalanced network-embedding techniques.

  • Takeaways & Limitations

    The experiments support ImGAGN as an effective method for semi-supervised imbalanced node classification and network-layout evaluation.

Abstract

from arXiv · show

Imbalanced classification on graphs is ubiquitous yet challenging in many real-world applications, such as fraudulent node detection. Recently, graph neural networks (GNNs) have shown promising performance on many network analysis tasks. However, most existing GNNs have almost exclusively focused on the balanced networks, and would get unappealing performance on the imbalanced networks. To bridge this gap, in this paper, we present a generative adversarial graph network model, called ImGAGN to address the imbalanced classification problem on graphs. It introduces a novel generator for graph structure data, named GraphGenerator, which can simulate both the minority class nodes' attribute distribution and network topological structure distribution by generating a set of synthetic minority nodes such that the number of nodes in different classes can be balanced. Then a graph convolutional network (GCN) discriminator is trained to discriminate between real nodes and fake (i.e., generated) nodes, and also between minority nodes and majority nodes on the synthetic balanced network. To validate the effectiveness of the proposed method, extensive experiments are conducted on four real-world imbalanced network datasets. Experimental results demonstrate that the proposed method ImGAGN outperforms state-of-the-art algorithms for semi-supervised imbalanced node classification task.

1 INTRODUCTION

Imbalanced graph classification is difficult because minority nodes are scarce, expensive to label, and hard to separate from majority nodes. ImGAGN addresses this by generating synthetic minority nodes and training a GCN discriminator on the resulting balanced network.

  • 1 INTRODUCTION: Network embedding maps graph nodes into low-dimensional vectors while preserving network structure for tasks including node classification, link prediction, and community detection.Existing approaches include unsupervised methods such as DeepWalk and semi-supervised methods such as GCN.
  • 1 INTRODUCTION: Imbalanced networks contain far fewer minority nodes, whose labels are expensive to obtain and whose representations may overlap with majority nodes.These challenges are illustrated in fraudulent-node detection, where fraudsters are rare and may disguise themselves as normal users.
  • 1 INTRODUCTION: ImGAGN uses GraphGenerator to simulate minority-node attributes and topology, generating synthetic minority nodes linked to real minority nodes to balance the classes.The generator obtains synthetic-node attributes by averaging neighboring real minority-node attributes.
  • 1 INTRODUCTION: A GCN discriminator distinguishes real from generated nodes and minority from majority nodes on the synthetic balanced network.The balanced network is constructed after the training/testing split, with generated nodes linked only to training minority nodes.

2 RELATED WORKS

Related work covers general imbalanced learning and graph-specific imbalanced network embedding. Existing approaches use sampling, cost-sensitive or kernel-based learning, and specialized graph embedding strategies.

  • 2 RELATED WORKS: The paper positions Imbalanced network embedding as a distinct research field within broader imbalanced learning.The related-work discussion separates general imbalanced-learning techniques from graph-specific embedding methods.
  • 2 RELATED WORKS: Imbalanced learning addresses settings where minority examples are much rarer than majority examples, including high-impact applications such as cancer and fraud detection.The field includes oversampling, undersampling, cost-sensitive learning, and kernel-based methods.
  • 2 RELATED WORKS: Imbalanced network embedding methods target imbalanced learning on graph-structured data.Representative methods include GRADE, ImVerde, SPARC, and RSDNE, which use different clustering, sampling, prediction, or manifold strategies.

3 PROPOSED METHOD

ImGAGN balances imbalanced graph classes by generating synthetic minority nodes that model both minority attributes and links, then uses a GCN discriminator for joint authenticity and class discrimination. Its optimization combines adversarial, classification, embedding-separation, and regularization objectives, with stated complexity dominated by the discriminator plus a comparatively small generator cost.

  • ImGAGN framework: ImGAGN generates synthetic minority nodes to balance the original network, then applies a GCN discriminator to distinguish real from generated nodes and minority from majority nodes.The balanced graph incorporates generated nodes, edges, features, and labels alongside the original network.
  • 3.2.1 GraphGenerator (G): GraphGenerator learns graph structure by linking each synthetic minority node to real minority nodes and averaging linked minority features to construct its attributes.Its normalized link matrix represents generated-to-real minority relationships, while generated features are aggregated from linked real minority features.
  • 3.2.2 Discriminator (D): The discriminator operates on a balanced graph with three labels—real minority, real majority, and fake minority—and uses a two-layer GCN for multiclass node classification.The generated majority label is excluded because GraphGenerator produces only minority nodes.
  • 3.2.3 Model Optimization: GraphGenerator’s loss combines fake-versus-real and minority-class confusion terms with a distribution-matching term and weight regularization, while the discriminator uses fake/real, class, embedding-margin, and regularization terms.The generator regularizer uses coefficient α, and the discriminator regularizer uses coefficient β.
  • 3.3 Time Complexity: The total time complexity is O((L−1)n_gH^2 + n_gn_min^2 + λ2(K|E|d + Kn d^2)), with generator-only overhead simplified to O(nH^2) when λ2 is constant.The discriminator complexity is O(K|E|d + Kn d^2), and λ2 is stated to be less than 100.

4 EXPERIMENT

Experiments on four real-world datasets evaluate ImGAGN through imbalanced classification, network-layout visualization, and hyperparameter sensitivity analyses.

  • The experiments assess ImGAGN on imbalanced node classification, network layouts, and parameter sensitivity across four real-world datasets.

4.1 Experimental setup

The study uses four citation-network datasets and compares ImGAGN with balanced and imbalanced embedding methods under specified experimental settings.

  • Datasets: Experiments use Cora, Citeseer, Pubmed, and DBLP citation networks, where papers are nodes, citations are edges, and bag-of-words vectors are node features.
  • Comparison Algorithms: The comparison includes balanced methods GCN, GraphSAGE, DeepWalk, Node2vec, and LINE, alongside imbalanced methods GCN-SMOTE, SPARC, DR-GCN, and RECT.
  • Comparison Algorithms: GCN-SMOTE oversamples minority training nodes to balance classes before training GCN, while ImGAGN generates minority nodes through its GraphGenerator.
  • Implementation: ImGAGN uses a three-layer generator and a two-layer GCN discriminator, with generated-node output sized to the training-set class difference.

4.2 Imbalanced binary node classification (RQ1)

On four datasets, ImGAGN substantially outperforms comparison methods on recall and AUC while remaining competitive on precision.

  • ImGAGN substantially outperforms all comparison methods in recall and AUC across all datasets, while matching RECT comparably in precision on Pubmed and DBLP.It improves recall over RECT by 11.44% on Pubmed and 8.73% on DBLP.
  • Imbalanced embedding methods generally outperform balanced methods because they focus more on minority-class label learning.
  • ImGAGN outperforms GCN-SMOTE, suggesting benefits from modeling both minority-node attribute and implicit topological-structure distributions.

4.3 Network layout (RQ2)

A t-SNE visualization on Cora examines whether learned embeddings separate minority and majority nodes and distinguish generated from real nodes.

  • ImGAGN separates real from generated nodes and minority from majority nodes, indicating that its embeddings capture latent representations of both classes.
  • Semi-supervised methods generally separate majority and minority classes better than unsupervised methods by using node features and labels together.

4.4 Parameters sensitivity analysis (RQ3)

ImGAGN performance improves as the training minority-node ratio and discriminator training steps increase, then levels off. High performance is reported for λ1 > 0.7 and λ2 > 50.

  • High performance is achieved with λ1 > 0.7 and λ2 > 50.Here, λ1 is the ratio of all training minority nodes to majority nodes, while λ2 is the number of discriminator training steps.
  • Imbalanced node-classification performance, especially recall, increases with λ1 before reaching a plateau.When λ1 = 0, ImGAGN degenerates to GCN; increasing λ1 can therefore improve GCN performance on imbalanced networks.
  • Performance increases with discriminator training steps λ2 and then tends to flatten.The reported explanation is that the discriminator needs sufficient training steps to learn node embeddings.
  • Figure 4 analyzes sensitivity to the training minority-nodes ratio λ1.
  • Figure 5 analyzes sensitivity to the discriminator training steps λ2.

5 CONCLUSION

The paper concludes that ImGAGN uses GraphGenerator and a GCN discriminator to address imbalanced network embedding. Across four real-world datasets, it outperforms state-of-the-art methods in most imbalanced node-classification cases and separates minority nodes in learned embeddings.

  • ImGAGN outperforms state-of-the-art imbalanced network-embedding algorithms in most cases for recall, precision, and AUC.The evaluation covers four real-world datasets and the imbalanced node-classification task.
  • GraphGenerator simulates minority-node attribute and network-topology distributions by generating synthetic minority nodes to balance class counts.
  • A GCN discriminator distinguishes real from generated nodes and minority from majority nodes on the synthetic balanced network.
  • Visualization results show that ImGAGN learns embeddings in which minority nodes can separate from majority nodes.
Loading 2106.02817v1…