  We propose a simple yet effective method for detecting anomalous instances on
an attribute graph with label information of a small number of instances.
Although with standard anomaly detection methods it is usually assumed that
instances are independent and identically distributed, in many real-world
applications, instances are often explicitly connected with each other,
resulting in so-called attributed graphs. The proposed method embeds nodes
(instances) on the attributed graph in the latent space by taking into account
their attributes as well as the graph structure based on graph convolutional
networks (GCNs). To learn node embeddings specialized for anomaly detection, in
which there is a class imbalance due to the rarity of anomalies, the parameters
of a GCN are trained to minimize the volume of a hypersphere that encloses the
node embeddings of normal instances while embedding anomalous ones outside the
hypersphere. This enables us to detect anomalies by simply calculating the
distances between the node embeddings and hypersphere center. The proposed
method can effectively propagate label information on a small amount of nodes
to unlabeled ones by taking into account the node's attributes, graph
structure, and class imbalance. In experiments with five real-world attributed
graph datasets, we demonstrate that the proposed method achieves better
performance than various existing anomaly detection methods.
