  Graph-level anomaly detection aims to identify abnormal graphs that exhibit
deviant structures and node attributes compared to the majority in a graph set.
One primary challenge is to learn normal patterns manifested in both
fine-grained and holistic views of graphs for identifying graphs that are
abnormal in part or in whole. To tackle this challenge, we propose a novel
approach called Hierarchical Memory Networks (HimNet), which learns
hierarchical memory modules -- node and graph memory modules -- via a graph
autoencoder network architecture. The node-level memory module is trained to
model fine-grained, internal graph interactions among nodes for detecting
locally abnormal graphs, while the graph-level memory module is dedicated to
the learning of holistic normal patterns for detecting globally abnormal
graphs. The two modules are jointly optimized to detect both locally- and
globally-anomalous graphs. Extensive empirical results on 16 real-world graph
datasets from various domains show that i) HimNet significantly outperforms the
state-of-art methods and ii) it is robust to anomaly contamination. Codes are
available at: https://github.com/Niuchx/HimNet.
