Abstract
Learning from continuous streams of graph-structured data presents significant challenges due to structural complexity and the potential for infinite feature spaces. This paper introduces LCB-PA (Lossy Counting Based Passive Aggressive), a novel algorithm designed to perform high-accuracy graph classification under strict, pre-defined memory and time constraints. By adapting the "Lossy Counting" stream mining technique to the Passive Aggressive learning framework, the authors demonstrate a system that is orders of magnitude faster than traditional dual-space methods while maintaining competitive classification performance.
The Challenge: Graph Streams and Memory Budgets
In modern data environments, information often arrives as "data streams"—continuous, high-velocity flows that are too large to store in their entirety. When these streams consist of graphs (e.g., chemical structures, social networks), the problem is compounded. Representing graphs for machine learning typically involves kernels that generate a massive number of features. As the stream progresses, most algorithms eventually exceed memory limits or become computationally prohibitive. Furthermore, these streams often exhibit concept drift, where the underlying data distribution changes over time, requiring models to adapt dynamically.
The core question addressed is: How can we learn an accurate classifier from a graph stream using a strictly limited, pre-defined amount of memory?
The LCB-PA Algorithm
The proposed solution, LCB-PA, combines two powerful concepts:
- Passive Aggressive (PA) Learning: An online learning algorithm that updates its model only when a classification error (or insufficient margin) occurs.
- Lossy Counting (LC): A classic algorithm for identifying frequent items in a stream using minimal memory.
The authors extended LC to create LCB (Lossy Counting with Budget), which manages weighted features and enforces a hard memory limit. When the budget is reached, LCB-PA employs a "deletion test" based on theoretical error bounds to prune the least influential features. A unique "ghost event" mechanism ensures the budget is never exceeded, even momentarily, during feature updates.
Experimental Evaluation
The researchers evaluated LCB-PA on several large-scale datasets, including over 80,000 chemical compounds from PubChem and over 32,000 images from LabelMe converted into graphs via Delaunay triangulation.
Key Results
- Exceptional Speed: LCB-PA proved to be the fastest algorithm by a wide margin. On chemical datasets, it processed the stream in under 4 minutes, whereas the traditional "Dual" kernel-based version required over 31 hours.
- Accuracy and Robustness: Despite aggressive pruning, LCB-PA achieved a Balanced Error Rate (BER) comparable to unbudgeted versions. On the Image dataset, LCB-PA with a small budget (10,000 units) actually outperformed algorithms without budget constraints, suggesting that its pruning mechanism effectively filters out noisy features.
Insights and Future Directions
The study highlights that for high-speed graph streams, "Primal" approaches using sparse feature representations are far more viable than "Dual" kernel methods. By integrating frequency-based importance (from Lossy Counting) with weight-based importance (from PA learning), LCB-PA retains the most relevant structural features over time. Future work may explore applying this budgeted approach to other complex data domains, such as Natural Language Processing, and investigating the impact of different structural feature extraction methods on performance.
Summary updated