  Uncovering anomalies in attributed networks has recently gained popularity
due to its importance in unveiling outliers and flagging adversarial behavior
in a gamut of data and network science applications including {the Internet of
Things (IoT)}, finance, security, to list a few. The present work deals with
uncovering anomalous edges in attributed graphs using two distinct formulations
with complementary strengths, which can be easily distributed, and hence
efficient. The first relies on decomposing the graph data matrix into low rank
plus sparse components to markedly improve performance. The second broadens the
scope of the first by performing robust recovery of the unperturbed graph,
which enhances the anomaly identification performance. The novel methods not
only capture anomalous edges linking nodes of different communities, but also
spurious connections between any two nodes with different features. Experiments
conducted on real and synthetic data corroborate the effectiveness of both
methods in the anomaly identification task.
