| 本文已被：浏览 1073次 下载 1632次 |
码上扫一扫！ |
|
|
| 基于结构熵的属性图异常检测 |
|
吴江豪1,2, 段亮1,2, 岳昆1,2, 李昂生3, 杨培忠1,2
|
|
1.云南省智能系统与计算重点实验室(云南大学), 云南 昆明 650500;2.云南大学 信息学院, 云南 昆明 650500;3.北京航空航天大学 计算机学院, 北京 100191
|
|
| 摘要: |
| 属性图越来越多地用于描述带有关联关系的数据, 其异常检测日益受到关注. 由于属性图具有属性信息丰富、结构信息复杂等特点, 存在全局、结构和社区等多种类型的异常, 且异常特性往往隐藏于图的深度结构信息中, 现有方法仍存在结构信息丢失、异常节点检测困难等问题. 结构信息论使用编码树表示数据中的层次关系、通过最小化结构熵生成不同层次之间的关联, 可有效度量图中所蕴含的实质结构, 研究基于结构熵的属性图异常检测方法. 首先, 综合考虑属性图的结构和属性信息, 通过最小化图的结构熵, 构造属性图的K维编码树, 以描述其中的层次社区结构. 然后, 充分利用编码树中的节点属性和层次社区信息, 基于节点间的欧氏距离和连接程度, 设计结构异常和属性异常的评分机制, 从而确定属性图中的异常节点、检测多种类型的异常. 在多个属性图数据集上对所提方法进行对比测试, 实验结果表明, 所提方法能有效检测属性图的各类异常且显著优于现有方法. |
| 关键词: 属性图 异常检测 结构信息论 编码树 结构熵 层次社区结构 |
| DOI：10.13328/j.cnki.jos.007374 |
| 分类号:TP311 |
| 基金项目:国家自然科学基金区域创新发展联合基金重点项目(U23A20298); 云南省智能系统与计算重点实验室项目(202405AV340009) |
|
| Structural-entropy-based Anomaly Detection in Attributed Graph |
|
WU Jiang-Hao1,2, DUAN Liang1,2, YUE Kun1,2, LI Ang-Sheng3, YANG Pei-Zhong1,2
|
|
1.Yunnan Key Laboratory of Intelligent Systems and Computing (Yunnan University), Kunming 650500, China;2.School of Information Science and Engineering, Yunnan University, Kunming 650500, China;3.School of Computer Science and Engineering, Beihang University, Beijing 100191, China
|
| Abstract: |
| Attributed graphs are increasingly used to represent data with relational structures, and detecting anomalies with them is gaining attention. Due to their characteristics, such as rich attribute information and complex structural relationships, various types of anomalies may exist, including global, structural, and community anomalies, which often remain hidden within the graph’s deep structure. Existing methods face challenges such as loss of structural information and difficulty identifying abnormal nodes. Structural information theory leverages encoding trees to represent hierarchical relationships within data and establishes correlations across different levels by minimizing structural entropy, effectively capturing the graph’s essential structure. This study proposes an anomaly detection method for attributed graphs based on structural entropy. First, by integrating the structural and attribute information of attributed graphs, a K-dimensional encoding tree to represent the hierarchical community structure through structural entropy minimization is constructed. Next, using the node attributes and hierarchical community information within the encoding tree, scoring mechanisms for detecting structural and attribute anomalies based on Euclidean distance and connection strength between nodes are designed. This approach identifies abnormal nodes and detects various types of anomalies. The proposed method is evaluated through comparative tests on several attributed graph datasets. Experimental results demonstrate that the proposed method effectively detects different types of anomalies and significantly outperforms existing state-of-the-art methods. |
| Key words: attributed graph anomaly detection structural information theory encoding tree structural entropy hierarchical community structure |
