TY - GEN

T1 - GAWD

T2 - 13th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2021

AU - Lee, Meng Chieh

AU - Nguyen, Hung T.

AU - Berberidis, DImitris

AU - Tseng, Vincent S.

AU - Akoglu, Leman

N1 - Publisher Copyright:
© 2021 Owner/Author.

PY - 2021/11/8

Y1 - 2021/11/8

N2 - Given a set of node-labeled directed weighted graphs, how to find the most anomalous ones? How can we summarize the normal behavior in the database without losing information? We propose GAWD, for detecting anomalous graphs in directed weighted graph databases. The idea is to (1) iteratively identify the "best"substructure (i.e., subgraph or motif) that yields the largest compression when each of its occurrences is replaced by a super-node, and (2) score each graph by how much it compresses over iterations - - the more the compression, the lower the anomaly score. Different from existing work [1] on which we build, GAWD exhibits (i) a lossless graph encoding scheme, (ii) ability to handle numeric edge weights, (iii) interpretability by common patterns, and (iv) scalability with running time linear in input size. Experiments on four datasets injected with anomalies show that GAWD achieves significantly better results than state-of-the-art baselines.

AB - Given a set of node-labeled directed weighted graphs, how to find the most anomalous ones? How can we summarize the normal behavior in the database without losing information? We propose GAWD, for detecting anomalous graphs in directed weighted graph databases. The idea is to (1) iteratively identify the "best"substructure (i.e., subgraph or motif) that yields the largest compression when each of its occurrences is replaced by a super-node, and (2) score each graph by how much it compresses over iterations - - the more the compression, the lower the anomaly score. Different from existing work [1] on which we build, GAWD exhibits (i) a lossless graph encoding scheme, (ii) ability to handle numeric edge weights, (iii) interpretability by common patterns, and (iv) scalability with running time linear in input size. Experiments on four datasets injected with anomalies show that GAWD achieves significantly better results than state-of-the-art baselines.

UR - http://www.scopus.com/inward/record.url?scp=85124377071&partnerID=8YFLogxK

U2 - 10.1145/3487351.3488325

DO - 10.1145/3487351.3488325

M3 - Conference contribution

AN - SCOPUS:85124377071

T3 - Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2021

SP - 143

EP - 150

BT - Proceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2021

A2 - Coscia, Michele

A2 - Cuzzocrea, Alfredo

A2 - Shu, Kai

PB - Association for Computing Machinery, Inc

Y2 - 8 November 2021

ER -