ImVerde: Vertex-Diminished Random Walk for Learning Imbalanced Network Representation

Jun Wu, Jingrui He, Yongming Liu

TL;DR

This paper introduces ImVerde, a novel framework for learning node representations in imbalanced networks. It tackles the challenge of skewed class distributions by proposing a new random walk method, Vertex-Diminished Random Walk (VDRW), which encourages exploration of under-represented nodes, leading to more separable embeddings.

What Problem Does This Paper Address?

Many real-world applications, such as air traffic control accident analysis, generate data that is inherently imbalanced. When this data is modeled as a network (e.g., accident reports as nodes, similarity as edges), existing methods for learning node representations often assume balanced class distributions. This leads to suboptimal embeddings where minority classes are poorly represented, hindering downstream tasks like classification. The paper aims to bridge this gap by developing a method specifically designed for imbalanced network representation learning.

Methods

The core of the proposed solution is the Vertex-Diminished Random Walk (VDRW). Unlike traditional random walks or Vertex-Reinforced Random Walk (VRRW), VDRW dynamically adjusts transition probabilities by decreasing the probability of visiting a node each time it's encountered. This encourages the random walker to explore less-visited nodes, which is crucial for imbalanced networks where minority class nodes might otherwise be overlooked.

Building on VDRW, the ImVerde framework is a semi-supervised approach that uses VDRW for Context Sampling. This means VDRW is used to generate node-context pairs, leveraging both graph structure and limited label information. To further address imbalance, Balanced-batch Sampling is employed to ensure that mini-batches used during training are balanced across classes.

Datasets

The authors evaluated their framework on several real-world datasets:

  • Zachary's Karate Network: A social network used for case studies and visualization.
  • Cora, Citeseer, Pubmed: Citation networks, reconstructed to create imbalanced binary classification scenarios.
  • NTSB Network: A dataset of historical air traffic accident reports, used for multi-class classification on an imbalanced dataset.

Key Insights and Ideas

  • VDRW's advantage in imbalance: The key insight is that by diminishing transition probabilities, VDRW naturally steers exploration towards less-frequently visited nodes, which are more likely to belong to minority classes in imbalanced networks. This is a significant departure from methods that might favor high-degree nodes.
  • Separability through exploration: The VDRW approach leads to more distinct and separable node representations for different classes in the embedding space, as visualized in Figure 1.
  • Jointly leveraging graph and labels: ImVerde's Context Sampling effectively combines graph structure with limited label information, a more robust approach than methods that treat them separately.
  • Mini-batch balancing is critical: Even with a good random walk, imbalanced node-context pairs can persist. Balanced-batch sampling is essential for effective training.

Key Results

  • ImVerde, particularly when using VDRW for context sampling, significantly outperforms state-of-the-art methods like DeepWalk, node2vec, and Planetoid on node classification tasks for imbalanced networks.
  • For example, on Cora_7 (a specific imbalanced binary classification scenario), ImVerde-VDRW achieved an AUC of 0.95, compared to 0.85 for Planetoid and 0.85 for DeepWalk.
  • The framework shows robustness to varying imbalance ratios, with ImVerde-VDRW's performance being less affected than other methods when imbalance increases.
  • VDRW demonstrates improved "walking path accuracy" within the same class for both minority and majority nodes compared to random walk and VRRW.

Limitations and Future Work

  • Real-world network convergence: The paper acknowledges that real-world networks may not strictly meet the theoretical convergence conditions for VDRW (Corollary 3). However, experimental results suggest that short VDRW walks are still effective.
  • Parameter sensitivity: The performance of ImVerde is sensitive to hyperparameter choices (like a and r in Context Sampling), requiring careful tuning.
  • Future work: The paper implicitly suggests exploring the inductive version of ImVerde (similar to Planetoid-I) and further investigating the theoretical properties and practical applications of VDRW on more complex imbalanced network structures.

Summary updated

Abstract

Imbalanced data widely exist in many high-impact applications. An example is in air traffic control, where among all three types of accident causes, historical accident reports with `personnel issues' are much more than the other two types (`aircraft issues' and `environmental issues') combined. Thus, the resulting data set of accident reports is highly imbalanced. On the other hand, this data set can be naturally modeled as a network, with each node representing an accident report, and each edge indicating the similarity of a pair of accident reports. Up until now, most existing work on imbalanced data analysis focused on the classification setting, and very little is devoted to learning the node representations for imbalanced networks. To bridge this gap, in this paper, we first propose Vertex-Diminished Random Walk (VDRW) for imbalanced network analysis. It is significantly different from the existing Vertex Reinforced Random Walk by discouraging the random particle to return to the nodes that have already been visited. This design is particularly suitable for imbalanced networks as the random particle is more likely to visit the nodes from the same class, which is a desired property for learning node representations. Furthermore, based on VDRW, we propose a semi-supervised network representation learning framework named ImVerde for imbalanced networks, where context sampling uses VDRW and the limited label information to create node-context pairs, and balanced-batch sampling adopts a simple under-sampling method to balance these pairs from different classes. Experimental results demonstrate that ImVerde based on VDRW outperforms state-of-the-art algorithms for learning network representations from imbalanced data.
BibTeX
@inproceedings{wu2018imverde,
  author = {Jun Wu and Jingrui He and Yongming Liu},
  title = {{ImVerde: Vertex-Diminished Random Walk for Learning Imbalanced Network Representation}},
  booktitle = {IEEE BigData},
  year = {2018},
  doi = {10.1109/bigdata.2018.8622603},
}
Figure