| 摘要: |
| 图异常检测将实体间通联关系抽象为复杂网络形式表示，旨在利用结构特征识别网络中存在的异常行为与实体，具有关系客观存在且异常可解释较强的优点。目前该类方法主要以无向网络结构为基础提取特征，以达到识别异常的目的，主要关注于连边层面异常结构，对于由集体异常行为构成的异常子图识别问题研究仍较少，缺少对行为方向异常协同关系的分析。传统方法通过提取节点邻域结构特征构建特征空间，并根据节点邻域结构在特征空间中的映射点距离发现离群点，虽可发现结构具有明显差异的异常子图，但忽略了网络结构中节点的实际物理联系，以及行为由于主客体不同所导致个体间关系非对等的实际情况。针对该问题，本文提出了基于有向网络非对等关系的异常子图识别算法，通过连边方向信息提取节点间行为方向特征，度量节点间关系非对等强度，后转化为子图密度形式表示，结合基于密度的异常识别方法挖掘异常，保留了实际物理联系。通过在4种不同异常类型的合成数据集与存在实际异常的真实数据集上进行实验，验证了其具有较高的异常识别精度与鲁棒性。 |
| 关键词: 图异常检测 有向网络 非对等关系 异常子图 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2022.01.06 |
| Received:April 14, 2021Revised:July 03, 2021 |
| 基金项目:本课题得到国家自然科学基金（No.61803384）资助。 |
|
| Anomaly Subgraph Identification Algorithm based on Non-peer Relationship in Directed Network |
| SHI Haoran,JI Lixin,LIU Shuxin,Zhang Yiming |
| People's Liberation Army Strategic Support Force Information Engineering University, Zhengzhou 450001, China |
| Abstract: |
| Graph anomaly detection abstracts the communication relationship between entities into a complex network representation, aiming to use structural features to identify abnormal behaviors and entities in the network. It has the advantages of objective existence and strong explanation of abnormalities. At present, this type of method mainly extracts features based on the undirected network structure to achieve the purpose of identifying anomalies. It mainly focuses on the abnormal structure at the interconnection level. There are still few studies on the identification of abnormal subgraphs composed of collective abnormal behaviors, and there is a lack of correctness. Analysis of abnormal synergy in behavior direction. The traditional method constructs the feature space by extracting the features of the node neighborhood structure, and finds outliers according to the distance of the mapping point of the node neighborhood structure in the feature space. Although abnormal subgraphs with obvious differences in structure can be found, it ignores the network structure. The actual physical connection of nodes and the actual situation of non-equivalence between individuals due to different subject and object behaviors. In response to this problem, this paper proposes an abnormal subgraph recognition algorithm based on non-equivalent relationships in directed networks. The behavior direction characteristics between nodes are extracted through the connection direction information, and the non-equivalence strength between nodes is measured, and then converted into sub-graph density form. Said that combining the density-based anomaly identification method to mine anomalies, the actual physical connection is retained. Experiments on synthetic data sets with four different anomaly types and real data sets with actual anomalies have verified its high anomaly recognition accuracy and robustness. |
| Key words: graph anomaly detection directed network non-peer relationship abnormal subgraph |
