Graph iForest: Isolation of anomalous and outlier graphs

We present an anomaly and outlier detection method for graph data. The method relies on the consideration that anomalies and outliers are more easily isolated by certain incremental partitionings of the data space. Specifically, we build upon the isolation forest method and introduce a new incremental partitioning of the space of graphs that makes the isolation forest method applicable to generic attributed graphs, i.e., graphs where both nodes and edges can be associated with attributes. Within the considered general setup, the topology and the number of nodes can change from graph to graph, and a node correspondence between different graphs can be absent or unknown. Examples of applications of what proposed include the identification of frauds and fake news in communication networks, and breakage of systems monitored by sensor networks. The main novel contribution of the paper is a graph space partitioning which we prove to be expressive enough to identify anomalies and outlier graphs in a given dataset. An empirical analysis on synthetic and real-world graphs validates the effectiveness of the proposed method.

I. Introduction

Graph data representations demonstrated their great potential in a wide range of machine learning tasks that are crucial for both academia and industry. The advantage of using graphs stems from the possibility of including physical and functional relations among the considered entities. Such extra structure constitutes a relational inductive bias that allows the machine-learning practitioner to integrate prior know ledge to support the model learning [1], [2]. We have seen successful applications of machine learning with graphs spanning from biological systems with molecules and proteins represented as a collection of atoms (or sub-structures) connected by bonds [3]–[5], to sensor networks acquiring signals that can expose a functional dependency [6]. Other examples where a graph representation comes naturally include social networks, smart grids and body networks [7]–[11].