  Given a graph with node attributes, what neighborhoods are anomalous? To
answer this question, one needs a quality score that utilizes both structure
and attributes. Popular existing measures either quantify the structure only
and ignore the attributes (e.g., conductance), or only consider the
connectedness of the nodes inside the neighborhood and ignore the cross-edges
at the boundary (e.g., density).
  In this work we propose normality, a new quality measure for attributed
neighborhoods. Normality utilizes structure and attributes together to quantify
both internal consistency and external separability. It exhibits two key
advantages over other measures: (1) It allows many boundary-edges as long as
they can be "exonerated"; i.e., either (i) are expected under a null model,
and/or (ii) the boundary nodes do not exhibit the subset of attributes shared
by the neighborhood members. Existing measures, in contrast, penalize boundary
edges irrespectively. (2) Normality can be efficiently maximized to
automatically infer the shared attribute subspace (and respective weights) that
characterize a neighborhood. This efficient optimization allows us to process
graphs with millions of attributes.
  We capitalize on our measure to present a novel approach for Anomaly Mining
of Entity Neighborhoods (AMEN). Experiments on real-world attributed graphs
illustrate the effectiveness of our measure at anomaly detection, outperforming
popular approaches including conductance, density, OddBall, and SODA. In
addition to anomaly detection, our qualitative analysis demonstrates the
utility of normality as a powerful tool to contrast the correlation between
structure and attributes across different graphs.
