  The study of networks has emerged in diverse disciplines as a means of
analyzing complex relationship data. Beyond graph analysis tasks like graph
query processing, link analysis, influence propagation, there has recently been
some work in the area of outlier detection for information network data.
Although various kinds of outliers have been studied for graph data, there is
not much work on anomaly detection from edge-attributed graphs. In this paper,
we introduce a method that detects novel outlier graph nodes by taking into
account the node data and edge data simultaneously to detect anomalies. We
model the problem as a community detection task, where outliers form a separate
community. We propose a method that uses a probabilistic graph model (Hidden
Markov Random Field) for joint modeling of nodes and edges in the network to
compute Holistic Community Outliers (HCOutliers). Thus, our model presents a
natural setting for heterogeneous graphs that have multiple edges/relationships
between two nodes. EM (Expectation Maximization) is used to learn model
parameters, and infer hidden community labels. Experimental results on
synthetic datasets and the DBLP dataset show the effectiveness of our approach
for finding novel outliers from networks.
