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 -