2025-11-12T07:37:09.358830

Incremental Learning with Concept Drift Detection and Prototype-based Embeddings for Graph Stream Classification

Malialis, Li, Panayiotou et al.

Data stream mining aims at extracting meaningful knowledge from continually evolving data streams, addressing the challenges posed by nonstationary environments, particularly, concept drift which refers to a change in the underlying data distribution over time. Graph structures offer a powerful modelling tool to represent complex systems, such as, critical infrastructure systems and social networks. Learning from graph streams becomes a necessity to understand the dynamics of graph structures and to facilitate informed decision-making. This work introduces a novel method for graph stream classification which operates under the general setting where a data generating process produces graphs with varying nodes and edges over time. The method uses incremental learning for continual model adaptation, selecting representative graphs (prototypes) for each class, and creating graph embeddings. Additionally, it incorporates a loss-based concept drift detection mechanism to recalculate graph prototypes when drift is detected.

academic

Incremental Learning with Concept Drift Detection and Prototype-based Embeddings for Graph Stream Classification

基本信息

论文ID: 2404.02572
标题: Incremental Learning with Concept Drift Detection and Prototype-based Embeddings for Graph Stream Classification
作者: Kleanthis Malialis, Jin Li, Christos G. Panayiotou, Marios M. Polycarpou
分类: cs.LG
发表时间: 2024年4月12日 (arXiv v2)
所属机构: 塞浦路斯大学KIOS研究与创新卓越中心，电气与计算机工程系
论文链接: https://arxiv.org/abs/2404.02572

摘要

数据流挖掘旨在从持续演化的数据流中提取有意义的知识，解决非平稳环境带来的挑战，特别是概念漂移（concept drift），即底层数据分布随时间的变化。图结构为表示复杂系统（如关键基础设施系统和社交网络）提供了强大的建模工具。从图流中学习成为理解图结构动态和促进明智决策的必要条件。本工作提出了一种新的图流分类方法，适用于数据生成过程产生具有随时间变化的节点和边的图的一般设置。该方法使用增量学习进行持续模型适应，为每个类别选择代表性图（原型），并创建图嵌入。此外，它还集成了基于损失的概念漂移检测机制，在检测到漂移时重新计算图原型。

研究背景与动机

1. 核心问题

本研究要解决的核心问题是在动态图流环境下的分类任务，其中图的节点数和边数会随时间变化，且存在概念漂移现象。

2. 问题重要性

现实需求: 许多真实世界系统（如关键基础设施、社交网络、推荐系统）都可以用动态图结构表示
数据特征: 这些系统产生的数据具有高速度、大容量和多样性的特点
环境挑战: 非平稳环境中的概念漂移会导致模型性能下降

3. 现有方法局限性

传统图分类方法: 主要针对静态图，无法处理流式动态图
现有图流方法: 大多专注于异常检测，而非多类分类；缺乏有效的概念漂移处理机制
特征提取: 现有方法使用简单的图特征（如边密度、谱间隙），表达能力有限

4. 研究动机

需要开发能够：

处理节点和边数量可变的动态图流
进行多类分类而非仅限于异常检测
有效检测和适应概念漂移
使用更丰富的图表示方法

核心贡献

提出了新的图流分类框架: 适用于节点和边数量可变的一般图流设置，支持多类分类任务
设计了基于原型的图嵌入方法: 通过选择每个类别的代表性图作为原型，将图转换为固定维度的向量表示
集成了混合式概念漂移检测机制: 结合增量学习和基于损失的漂移检测，实现主动-被动混合适应策略
提供了完整的实验验证: 在多个基准数据集上验证了方法的有效性，并进行了详细的消融研究

方法详解

任务定义

给定图流 $D = \{(g_t, y_t)\}_{t=1}^{\infty}$ ，其中：

$g_t = (V, E)$ 是时间步 $t$ 的属性图
$y_t \in \{1, ..., K\}$ 是图的类别标签
图可以有可变数量的节点和边
数据来自可能非平稳的概率分布 $p_t(g, y)$

目标是学习分类器 $h: G \rightarrow Y$ ，能够：

对新到达的图进行准确分类
通过增量学习持续适应
检测并处理概念漂移

模型架构

1. 图内存管理

维护多个队列存储最近的图： $q = \{q_c\}_{c=1}^K$ $q_c = \{g_i\}_{i=1}^L$ 其中 $L$ 是每个类别队列的大小。

2. 图原型选择

使用Centers算法为每个类别选择 $R$ 个原型图： $p_c = \arg\min_{g_1 \in q_c} \sum_{g_2 \in q_c} \delta(g_1, g_2)$ 其中 $\delta(\cdot, \cdot)$ 是图编辑距离。

3. 图嵌入生成

基于原型计算图嵌入： $e_g = \{\delta(g, p_i)\}_{i=1}^{R \times K}$ 将图转换为 $R \times K$ 维向量。

4. 增量学习

使用神经网络分类器，成本函数为： $C = \frac{1}{L \times K} \sum_{i=1}^{L \times K} l(y_i, h(e_{g_i}))$ 分类器通过增量训练更新： $h_t = h_{t-1}.train(\cdot)$

5. 概念漂移检测

维护两个预测准确率队列：

参考队列 $q_{ref}$ ：存储历史预测分数
移动队列 $q_{mov}$ ：存储最近预测分数

使用二项分布建模，检测条件： $\mu_{mov} \leq \mu_{ref} - \beta\sigma_{ref}$ 其中 $\beta$ 是敏感度参数。

技术创新点

原型选择策略: 使用图编辑距离和中位数方法选择最具代表性的图作为原型
混合漂移适应: 结合被动增量学习和主动漂移检测，在检测到漂移时重新计算原型
可变图处理: 通过基于距离的嵌入方法处理节点和边数量可变的图
损失驱动检测: 使用预测性能而非数据分布变化来检测概念漂移

实验设置

数据集

Letter数据集:
- 包含字母"A"、"I"、"Z"的图表示
- 两个变体：Letter high（高扰动）、Letter med high（中-高扰动）
- 用于测试概念漂移适应能力
GREC数据集:
- 建筑和电子图纸符号的图表示
- 五个扰动级别
- 三个类别，图均匀分布
Fingerprint数据集:
- 指纹图像的图表示
- 两个类别："arch"和"left"
- 来自NIST-4指纹数据库

评价指标

使用几何平均值（G-mean）： $G\text{-mean} = \sqrt[K]{\prod_{c=1}^K r_c}$ 其中 $r_c$ 是类别 $c$ 的召回率。

采用带衰减因子的预测评估方法（prequential evaluation），衰减因子设为0.99。

对比方法

提出方法: 使用原型嵌入的完整方法
特征方法: 使用边密度和谱间隙两个简单特征的基线方法

实现细节

图距离：图编辑距离
分类器：全连接神经网络
优化器：Adam
学习率：0.001-0.01（数据集相关）
内存大小： $L = 10$
原型数量： $R = 1$ 或 $R = 3$

实验结果

主要结果

图内存的作用: 使用图内存显著提升学习速度和最终性能，特别是在学习初期阶段。
原型数量影响:
- 在无漂移或轻微漂移情况下，3个原型优于1个原型
- 在严重概念漂移后，较少原型数量表现更好
- GREC和Fingerprint数据集上，3个原型consistently表现更好
概念漂移检测效果:
- 在概念漂移发生前，有无漂移检测器性能相似
- 漂移发生后，带漂移检测器的方法性能显著提升
- 验证了重新计算原型的有效性
方法比较: 提出的基于嵌入的方法在所有数据集上都显著优于基于简单特征的方法。