Source-linked AI summary
Scalable Anomaly Ranking of Attributed Neighborhoods
Bryan Perozzi, Leman Akoglu
TL;DR
The paper addresses how to detect anomalous neighborhoods when existing measures omit either node attributes or boundary structure. It proposes normality and AMEN, which jointly model internal consistency and external separability while inferring each neighborhood’s focus attributes. On real-world attributed graphs, AMEN outperforms established methods, and the optimization scales linearly with attribute size.
Problem
Existing neighborhood measures may ignore attributes or boundary edges, despite anomaly detection requiring a quality score that uses both structure and attributes.
Method
Normality combines internal connectivity, attribute similarity, and external separability, while AMEN maximizes it to infer latent focus attributes and their weights.
Results
16%-25% mean precision: AMEN outperforms conductance, density, OddBall, and SODA on anomaly detection in real-world attributed graphs.
Takeaways & Limitations
Normality supports neighborhood ranking and comparison of structure–attribute correlations across graphs, with optimization quadratic in neighborhood size and linear in attribute size.
Takeaways & Limitations
The formulation constrains each neighborhood’s focus to a nonnegative weight vector with unit p-norm.
Abstract
from arXiv · showhide
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.
1 Introduction
Graph anomaly detection requires quality measures that capture both neighborhood structure and node attributes. This paper introduces normality and AMEN to identify anomalous attributed neighborhoods by combining internal coherence with external separability and automatically inferring relevant attributes.
- Graph anomaly detection supports applications including network security, spam and fraud detection, and database integrity.
- A neighborhood is any connected subgraph, including clusters, communities, social circles, and ego networks.
- Existing measures often use only structure, focusing on internal connectivity, boundary separability, or both, while attributed methods additionally seek attribute coherence.
- Normality combines topology and attributes to quantify internal consistency and external separability, allowing boundary edges to be exonerated when justified.A neighborhood is high quality when members are internally connected and similar on a shared attribute subspace while remaining separated from or dissimilar to boundary nodes.
- AMEN automatically infers latent focus attributes and their weights by maximizing normality, with an efficient convex optimization that scales to millions of attributes.
- 16%-25% mean precision: AMEN outperforms conductance, density, OddBall, and SODA in anomaly detection on real-world attributed graphs.Qualitative analyses also use normality to contrast structure–attribute correlations across graphs.
2 Problem Statement
The AMEN problem ranks connected entity neighborhoods in an attributed graph by quality. It evaluates internal consistency and external separability using topology, boundary nodes, and attributes, then identifies the neighborhoods with the lowest quality.
- An attributed graph contains nodes, edges, and attributes; each neighborhood is a node set with the edges among its members.
- Boundary nodes are outside the neighborhood but connect to at least one neighborhood member.
- High-quality neighborhoods have many internal edges whose members share similar values on a common set of focus attributes.
- External separability permits either few boundary edges or many cross-edges that can be exonerated by the focus attributes or the underlying graph structure.
- The AMEN task defines a quality measure from internal connectivity, boundary nodes, and attributes, then finds the neighborhoods with the lowest quality.
3 Neighborhood Quality in Attributed Graphs
Normality evaluates attributed neighborhoods through internal consistency and external separability, while allowing boundary edges when a null model or attributes explain them. It uses weighted attribute similarity to identify each neighborhood’s focus.
- Normality: Normality combines internal connectivity, external separability, and node attributes to measure neighborhood quality.High-quality neighborhoods are internally connected and attribute-similar on a shared focus, while separated from or dissimilar to boundary nodes.
- Attribute focus: Weighted dot-product similarity emphasizes a sparse subset of attributes, called the neighborhood focus, rather than treating all attributes equally.Each neighborhood may have its own latent weight vector, with larger weights identifying attributes shared by its members.
- Internal consistency: Internal consistency rewards existing and surprising internal edges whose endpoints have high attribute similarity.The null model uses node degrees, so an internal edge contributes more when it is less expected in a degree-preserving random network.
- External separability: Boundary edges can be exonerated when they are expected under a degree-based null model or when boundary nodes differ on the neighborhood’s focus attributes.This accommodates hub-driven and overlapping-neighborhood cuts that other measures may penalize uniformly.
- Comparison: Normality differs from density, cut-ratio, modularity, and conductance by combining internal and boundary quality and not penalizing every boundary edge equally.Neighborhoods with negative normality are considered lower quality and anomalous.
4 Anomaly Mining of Entity Neighborhoods
AMEN mines anomalous neighborhoods by optimizing normality to infer each neighborhood’s latent attribute focus. It then ranks neighborhoods by their best attainable scores and treats the lowest-scoring ones as anomalous.
- Motivation: The optimization addresses high-dimensional settings where irrelevant attributes make uniform weighting impractical and meaningful weights difficult to assign manually.The focus is latent even when the neighborhood itself is given.
- Neighborhood Focus Extraction: AMEN automatically infers a neighborhood’s attribute-weight vector by maximizing its normality score.The optimization seeks a subspace that makes connected neighborhood nodes similar and boundary nodes dissimilar or explainably connected.
- Anomaly ranking: The method ranks neighborhoods by optimized normality and identifies those with the lowest scores as anomalous.This avoids requiring prior knowledge of which attributes define each neighborhood.
max
The normalized normality objective combines internal consistency and external separability, then optimizes nonnegative, normalized attribute weights to identify neighborhood-relevant attributes. Its optimization is linear in the number of attributes and independent of the full graph size.
- Size-invariant scoring: Normality normalizes internal consistency using bounds from fully connected and edgeless neighborhoods, yielding a weighted analogue of edge density.The internal term is shifted by its minimum and scaled by the range between its minimum and maximum.
- Size-invariant scoring: External separability is normalized similarly to conductance, but weights boundary edges by their surprise and endpoint similarity.The resulting weighted volume considers existing internal and boundary edges rather than treating all boundary edges identically.
- Objective optimization: The objective constrains attribute weights to be nonnegative and unit-normalized under a chosen p-norm, making the weights interpretable.The formulation explicitly imposes ∥wC∥p = 1 and wC(f) ≥ 0.
- Objective optimization: L1 selects the single attribute with the largest relevance value, whereas L2 distributes weight across positive attributes in proportion to their relevance.If all relevance values are negative, no attribute can make normality positive, so the neighborhood is considered anomalous.
- Objective optimization: The relevance vector supports top-k attribute selection and ranks attributes systematically by their neighborhood relevance.The top-k constraint can include both positive and negative relevance values.
- Computational complexity: The optimization costs O(|C|^2d + |EB|d) to compute relevance and O(d) to select relevant attributes, independent of the entire graph size.Because |C| ≪ n, the method is quadratic in neighborhood size and linear in the number of attributes.
5 Experiments
Experiments evaluate AMEN on synthetic perturbations and real ground-truth neighborhoods, then use normality to compare structure–attribute relationships across graphs. AMEN consistently ranks anomalies effectively, while case studies show that normality can recognize focused neighborhoods penalized by conductance and reveal graph-specific attribute patterns.
- 5.1 Anomaly Detection: AMEN is evaluated on perturbed egonets from DBLP, Citeseer, and LastFM, with structure and attribute perturbations applied at varying intensities.Five percent of selected small egonets are perturbed by rewiring internal edges, replacing attributes, or both.
- 5.1 Anomaly Detection: AMEN consistently outperforms competing measures, especially for attribute perturbations and low perturbation intensities.Across datasets and perturbation strategies, AMEN exceeds Flake-ODF by 16%, conductance by 18%, AW-NCut by 20%, SODA by 23%, and average degree by 24%.
- 5.1 Anomaly Detection: The lowest-normality ground-truth circles from Facebook, Twitter, and Google+ combine weak internal connectivity with poor boundary separation.Available attributes do not meaningfully improve their scores, despite these neighborhoods being manually defined social circles.
- 5.1 Anomaly Detection: Normality can remain high for neighborhoods with conductance in (0.9, 1.0] when attributes and structural surprise exonerate their boundary edges.DBLP contains many such neighborhoods, including focused co-authorship circles whose cross-edges arise from collaborators with broader connectivity.
- 5.2 Graph Analysis with Normality: Across graphs, normality distributions have distinct fingerprints, and most score gains come from only a few attributes.Google+ has the weakest attribute characterization, with 99% of circles lacking a positive characterizing attribute; relevance typically approaches zero after about 20 attributes.
- 5.2 Graph Analysis with Normality: L2 normality is positive for 89% of DBLP and 95% of LastFM neighborhoods, whereas most neighborhoods in other graphs are negative apart from a few strong cases.The best Google+ circle reaches approximately 0.6 under L2, and L2 generally preserves the bulk distribution while improving many DBLP and LastFM scores.
6 Conclusion
The paper defines normality to evaluate attributed neighborhoods through internal structure and attributes plus external boundary behavior. It uses scalable optimization for anomaly mining and reports improved ranking performance on real-world graphs.
- High-quality neighborhoods combine surprising internal edges with shared focus attributes and either few or exonerable boundary edges.Cross-edges may be exonerated when unsurprising under the null graph model or dissimilar on focus attributes.
- Normality-based anomaly mining automatically identifies latent focus attributes and their weights through scalable convex optimization.The optimization is quadratic in neighborhood size and linear in attribute size.
- Experiments on real-world graphs show that normality outperforms established measures and methods for ranking neighborhood quality.
A Preliminaries
The preliminaries introduce modularity and assortativity as related measures of structural organization and attribute homophily. Both compare observed same-group or same-type connectivity with an expected baseline.
- Modularity: Modularity measures whether networks have dense within-community connectivity and sparse between-community connectivity.
- Modularity: Modularity is the difference between actual and expected edge fractions connecting nodes in the same community.Its value increases as the observed within-community connectivity exceeds expectation.
- Assortativity: Assortativity measures homophily in attributed networks by comparing actual and expected edges between nodes of the same type.
- Scalar Assortativity: For numerical attributes, assortativity is derived from covariance among attribute values at connected nodes.The edge-based mean weights node attribute values by degree.
- Assortativity: Positive assortativity indicates similar attribute values among connected nodes, whereas zero indicates no attribute-structure correlation.Negative assortativity corresponds to connected nodes varying in opposite directions.
A.4 Modularity vs.
Modularity and assortativity serve different traditional applications but are related because assortative connectivity tends to produce modular communities.
- Modularity is commonly used for community detection and graph partitioning, while assortativity is used to measure homophily in social networks.
- Assortative networks tend to break into communities where similar nodes connect to similar nodes.The paper characterizes assortativity as a force influencing the emergence of modular structure.
B Baselines
The baselines span structural measures of internal consistency, boundary separability, and combined quality, alongside attributed methods. They provide comparisons for normality’s neighborhood-ranking task.
- Non-attributed baselines: Average degree and OddBall assess internal consistency without using node attributes.Average degree uses induced-edge density, while OddBall detects deviations in node density with a linear model.
- Non-attributed baselines: Cut ratio evaluates boundary separability, whereas conductance combines internal and external quality without attributes.Cut ratio uses the fraction of boundary edges; conductance normalizes the cut by neighborhood volume.
- Attributed baselines: SODA uses structure and attributes to separate connected from disconnected nodes with a max-margin hyperplane.It ranks neighborhoods by the hyperplane’s negative margin.
- Attributed baselines: Attribute-Weighted Normalized Cut identifies an attribute subspace and minimizes weighted normalized cut using endpoint similarity.
C.1 Analysis of community structure and quality
Prior work evaluates graph neighborhoods through structural quality, attributed clustering, or anomaly-specific objectives, but these approaches differ in scope and scalability. The paper positions its formulation against methods that are not directly applicable to neighborhood anomaly detection or cannot efficiently infer attribute subspaces.
- Community-quality research compares structural measures and examines how community properties vary across graph scales.
- Global graph-clustering objectives based on attribute correlations or subspace cuts are not directly applicable to anomaly detection of individual neighborhoods.
- Existing graph anomaly methods include frequent subgraph mining, single-attribute node-set detection, and OddBall’s structural egonet anomalies.
- Normalized subspace cut associates each cluster with relevant attributes, but its nonconvex, heuristic optimization and binary weights limit scalability and attribute-weight inference.
- Gupta et al.’s outlier-subgraph method maximizes a connected-versus-disconnected dissimilarity margin, whereas the proposed formulation uses faster optimization and introduces edge exoneration.