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

Jun Wu, Jingrui He, Yongming Liu

Abstract

Network representation learning often fails in imbalanced scenarios where majority-class nodes dominate the graph topology. We propose ImVerde, a framework centered on the Vertex-Diminished Random Walk (VDRW). VDRW dynamically reduces transition probabilities to frequently visited nodes, preventing the walk from being trapped in majority-class hubs. Combined with a label-aware jumping scheme and balanced-batch sampling, ImVerde significantly improves minority class representation and classification accuracy across various real-world datasets.

Introduction

In graph machine learning, the distribution of classes is rarely uniform. Real-world networks, such as aviation accident reports or citation graphs, often exhibit extreme class imbalance. Standard embedding methods like DeepWalk or node2vec rely on random walks to capture local neighborhoods. However, in imbalanced networks, majority-class nodes typically have higher degrees, acting as "hubs" that capture the random walker. This results in embeddings that over-represent majority patterns while neglecting the unique structural features of minority communities.

A team from Arizona State University has proposed ImVerde, a semi-supervised framework designed to learn high-quality node embeddings in these challenging environments. The core of the framework is the Vertex-Diminished Random Walk (VDRW), which forces exploration of the graph's periphery.

The ImVerde Framework

Vertex-Diminished Random Walk (VDRW)

The primary innovation of ImVerde is the VDRW mechanism. Traditional random walks have constant transition probabilities, and reinforced walks actually prefer frequently visited nodes. In contrast, VDRW decreases the probability of moving to a node each time it is visited.

Comparison of transition probabilities in (a) standard Random Walk, (b) Vertex-Reinforced Random Walk (VRRW), and (c) the proposed Vertex-Diminished Random Walk (VDRW).

As shown in the figure above, VDRW weakens the transition probability to nodes in "affected areas" (frequently visited regions). This "anti-popularity" mechanism ensures the walker explores the fringes of the graph where minority nodes often reside, preventing the majority class from dominating the generated node-context pairs.

Context Sampling and Training

Beyond the walk itself, ImVerde employs two additional strategies to handle imbalance:

  1. Label-Aware Jumping Scheme: To leverage available label information, the walker can jump directly to another node of the same class with a probability $r$. This creates "virtual edges" between rare nodes, helping the algorithm recognize their similarity even if they are topologically distant.
  2. Balanced-batch Sampling: During training, the model uses an under-sampling approach for mini-batches. This ensures that each gradient update is informed by an equal number of node-context pairs from both majority and minority classes.

Experimental Evaluation

The researchers evaluated ImVerde on five datasets, including standard citation networks (Cora, Citeseer, Pubmed) and the real-world NTSB aviation accident network. They compared the framework against state-of-the-art baselines like Planetoid, DeepWalk, and node2vec, as well as over-sampling techniques like SMOTE.

Results and Discussion

ImVerde consistently outperformed all baselines. In the Cora dataset, ImVerde achieved an Average Precision (AP) between 0.720 and 0.910, a significant improvement over Planetoid's range of 0.501 to 0.900. On the highly imbalanced NTSB dataset, ImVerde reached 46% accuracy, surpassing both DeepWalk and Planetoid.

t-SNE visualization of node embeddings for (a) Planetoid and (b) ImVerde, demonstrating improved minority class separation.

The impact of VDRW is most visible in the latent space. As seen in the t-SNE visualizations above, ImVerde creates much clearer clusters for minority classes. While Planetoid often lumps minority nodes into the majority cluster, ImVerde successfully isolates them, facilitating better downstream classification.

Conclusion

ImVerde addresses the fundamental topological bias in network embedding by discouraging walkers from lingering in majority-class hubs. By combining the Vertex-Diminished Random Walk with label-aware jumping and balanced sampling, the framework provides a robust solution for imbalanced graph data. Future work may involve extending this approach to dynamic networks or integrating it with more complex Graph Convolutional Network (GCN) architectures.

Summary updated

BibTeX
@inproceedings{wu2018imverde,
  author = {Jun Wu and Jingrui He and Yongming Liu},
  title = {{ImVerde: Vertex-Diminished Random Walk for Learning Network Representation from Imbalanced Data}},
  booktitle = {IEEE BigData},
  year = {2018},
  doi = {10.1109/bigdata.2018.8622603},
}
Figure