A Graph Anomalies Detection Method Based on Graph Similarity

doi:10.7652/xjtuxb201408012

您当前的位置：

首页 >

文章列表页 >

A Graph Anomalies Detection Method Based on Graph Similarity

更新时间：2025-07-09

- A Graph Anomalies Detection Method Based on Graph Similarity
- Vol. 48, Issue 8, Pages: 67-72+79(2014)
- 作者机构：
  
  1. 华南农业大学现代教育技术中心,广州,510640
  2. 华南理工大学计算机科学与工程学院,广州,510640
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201408012
  CLC： TP391
- Online First：10 August 2014，
  
  Published：2014
- 稿件说明：
移动端阅览
A Graph Anomalies Detection Method Based on Graph Similarity[J]. 2014, 48(8): 67-72+79.
DOI：

A Graph Anomalies Detection Method Based on Graph Similarity[J]. 2014, 48(8): 67-72+79. DOI： 10.7652/xjtuxb201408012.

摘要

针对传统离群点检测方法精确度不高的问题

提出了一种同时基于全局和局部视野综合考虑的离群点检测方法

并将其成功应用于事务图数据集的离群点检测。该方法利用极大公共频繁子图来测量任意两个事务图之间的相似度

提出利用基于公共近邻的裁剪方法对相似矩阵进行裁剪

通过计算数据结点的往返距离得出各个结点的离群值评分

弥补了传统基于稳态分布随机游走的离群点检测方法的缺陷。实验结果表明:该方法在事务图数据离群点检测方面的性能明显优于基于subdue的方法

精确度和错误报警率以及召回率提高了约10%。

Abstract

An anomalies detection method based on considering both the global and the local perspectives is proposed to solve the low accuracy problem in traditional anomalies detection

and is successfully applied to outlier detection in transaction graph data sets. The method evaluates the similarity between any two graphs based on maximum common frequent subgraph

and then cuts out the similarity matrix based on common neighbor. The round-trip distance for a data node is calculated and is used as its anomalies score

that makes up the defect of traditional outlier detection methods based on the steady-state distribution and random walk. Experiments in real datasets show that the performance of the proposed method is better than the performance of the method based on subdue. The precision

the recall rate and the false alarm rate are improved by about 10%.

关键词

Keywords

references

HAN Jiawei. Data mining: concepts and technology[M]. 3rd ed. San Francisco, CA, USA: Morgan Kaufmann, 2012.

林海. 离群检测及离群释义空间查找算法研究[D]. 重庆: 重庆大学, 2012.[3] 于浩, 王斌, 肖刚, 等. 基于距离的不确定离群点检测[J]. 计算机研究与发展, 2010, 47(3): 474-484.

YU Hao, WANG Bin, XIAO Gang, et al. Distance-based outlier detection on uncertain data[J]. Journal of Computer Research and Development, 2010, 47(3): 474-484.

HASSANZADEH R, NAYAK R. A semi-supervised graph-based algorithm for detecting outliers in online-social-networks[C]∥Proceedings of the 28th Annual ACM Symposium on Applied Computing. New York, USA: ACM, 2013: 577-582.

MOONESINGHE H, TAN P N. Outrank: a graph-based outlier detection framework using random walk[J]. International Journal on Artificial Intelligence Tools, 2008, 17(1): 19-36.

EGOZI A, KELLER Y, GUTERMAN H. A probabilistic approach to spectral graph matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(1): 18-27.

AKOGLU L, MCGLOHON M, FALOUTSOS C. Oddball: spotting anomalies in weighted graphs[J]. Lecture Notes in Computer Science, 2010, 6119: 410-421.

MULLER E, SANCHEZ P I, MULLE Y, et al. Ranking outlier nodes in subspaces of attributed graphs[C]∥Proceedings of the 2013 IEEE 29th International Conference on Data Engineering Workshops. Piscataway, NJ, USA: IEEE, 2013: 216-222.

GUO Yanrong, WU Guorong, JIANG Jianguo, et al. Robust anatomical correspondence detection by hierarchical sparse graph matching[J]. IEEE Transactions on Medical Imaging, 2013, 32(2): 268-277.

GUPTA M, GAO Jing, SUN Yizhou, et al. Integrating community matching and outlier detection for mining evolutionary community outliers[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2012: 859-867.

杨茂林. 离群检测算法研究[D]. 武汉: 华中科技大学, 2012.

AGGARWAL C C, ZHAO Yuchen, YU P S. Outlier detection in graph streams[C]∥Proceedings of the 2011 IEEE 27th International Conference on Data Engineering. Piscataway, NJ, USA: IEEE, 2011: 399-409.

CAO Lijun, LIU Xiyin, WANG Zhiping, et al. The spatial outlier mining algorithm based on the KNN graph[J]. Journal of Software, 2013, 8(12): 3158-3165.

YAN Sifeng, HAN Jiawei. Span: graph-based subs-tructure pattern mining[C]∥Proceedings of the 2002 IEEE International Conference on Data Mining. Piscataway, NJ, USA: IEEE, 2002: 721-724.

NOBLE C C, COOK D J. Graph-based anomaly detection[C]∥Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2003: 631-636.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Data Mining for High-Dimensional Design Space of High Pressure Turbine Stage Using SHAP

Feature Selection via Immune Memory Clone

Two New Efficient Algorithms to User Access Prediction

New Classification Algorithm Based on Visual Principles

A Method to Generate Basic Belief Assignment Based on Clustering Analysis and Its Application

Related Author

SONG Liming

WANG Qineng

SU Pengfei

GUO Zhendong

YANG Zhao

焦李成

朱虎明

张东站

Related Institution

School of Energy and Power Engineering, Xi'an Jiaotong University

State Key Laboratory of Clean and Efficient Turbomachinery Power Equipment, Dongfang Turbine Co., Ltd.

Institute of Intelligent Information Processing, Xidian University

School of Information Science and Technology, Xiamen University

School of Sciences, Xi'an Jiaotong University

⁰