ImVerde: Vertex-Diminished Random Walk for Learning Network Representation from Imbalanced Data
Preprint
Abstract
Imbalanced data widely exists in many high-impact applications. An example is in air traffic control, where we aim to identify the leading indicators for each type of accident cause from historical records. Among all three types of accident causes, historical records with 'personnel issues' are much more than the other two types ('aircraft issues' and 'environmental issues') combined. Thus, the resulting dataset is highly imbalanced, and can be naturally modeled as a network. Up until now, most existing work on imbalanced data analysis focused on the classification setting, and very little is devoted to learning the node representation from imbalanced networks. To address this problem, in this paper, we propose Vertex-Diminished Random Walk (VDRW) for imbalanced network analysis. The key idea is to encourage the random particle to walk within the same class by adjusting the transition probabilities each step. It resembles the existing Vertex Reinforced Random Walk in terms of the dynamic nature of the transition probabilities, as well as some convergence properties. However, it is more suitable for analyzing imbalanced networks as it leads to more separable node representations in the embedding space. Then, based on VDRW, we propose a semi-supervised network representation learning framework named ImVerde for imbalanced networks, in which context sampling uses VDRW and the label information to create node-context pairs, and balanced-batch sampling adopts a simple under-sampling method to balance these pairs in different classes. Experimental results demonstrate that ImVerde based on VDRW outperforms state-of-the-art algorithms for learning network representation from imbalanced data.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- A Survey on Network EmbeddingIEEE Transactions on Knowledge and Data Engineering, 2018
- Cost-Sensitive Learning of Deep Feature Representations From Imbalanced DataIEEE Transactions on Neural Networks and Learning Systems, 2017
- Learning Deep Representation for Imbalanced Classification2016
- Rare Category Detection on Time-Evolving Graphs2015
- An insight into classification with imbalanced data: Empirical results and current trends on using data intrinsic characteristicsInformation Sciences, 2013
- Graph-Based Rare Category Detection2008
- ADASYN: Adaptive synthetic sampling approach for imbalanced learning2008
- Automating the Construction of Internet Portals with Machine LearningInformation Retrieval Journal, 2000
- Term-weighting approaches in automatic text retrievalInformation Processing & Management, 1988
- An Information Flow Model for Conflict and Fission in Small GroupsJournal of Anthropological Research, 1977