Discovering rare categories from graph streams

Dawei Zhou, Arun Karthikeyan, Kangyang Wang, Nan Cao, Jingrui He

Research output: Contribution to journalArticlepeer-review


Nowadays, massive graph streams are produced from various real-world applications, such as financial fraud detection, sensor networks, wireless networks. In contrast to the high volume of data, it is usually the case that only a small percentage of nodes within the time-evolving graphs might be of interest to people. Rare category detection (RCD) is an important topic in data mining, focusing on identifying the initial examples from the rare classes in imbalanced data sets. However, most existing techniques for RCD are designed for static data sets, thus not suitable for time-evolving data. In this paper, we introduce a novel setting of RCD on time-evolving graphs. To address this problem, we propose two incremental algorithms, SIRD and BIRD, which are constructed upon existing density-based techniques for RCD. These algorithms exploit the time-evolving nature of the data by dynamically updating the detection models enabling a “time-flexible” RCD. Moreover, to deal with the cases where the exact priors of the minority classes are not available, we further propose a modified version named BIRD-LI based on BIRD. Besides, we also identify a critical task in RCD named query distribution, which targets to allocate the limited budget among multiple time steps, such that the initial examples from the rare classes are detected as early as possible with the minimum labeling cost. The proposed incremental RCD algorithms and various query distribution strategies are evaluated empirically on both synthetic and real data sets.

Original languageEnglish (US)
Pages (from-to)400-423
Number of pages24
JournalData Mining and Knowledge Discovery
Issue number2
StatePublished - Mar 1 2017
Externally publishedYes


  • Incremental learning
  • Rare category detection
  • Time-evolving graph

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Discovering rare categories from graph streams'. Together they form a unique fingerprint.

Cite this