Source-linked AI summary
Bayesian anomaly detection methods for social networks
Nicholas A. Heard, David J. Weston, Kiriaki Platanioti, David J. Hand
TL;DR
Large dynamic graphs are difficult to learn and monitor for structural change. The paper proposes a two-stage Bayesian screening and network-analysis procedure, demonstrated on real and simulated data. The method identifies anomalous activity efficiently and supports structural analysis of the reduced subnetworks, while its global modeling is mainly suited to short or medium-term settings.
Problem
Learning large-graph structure and monitoring its evolution over time are computationally demanding problems.
Method
The method uses conjugate Bayesian counting-process models to screen pairwise activity, then applies standard network tools to a greatly reduced anomalous subnetwork.
Results
2.0 seconds were required to identify anomalous individual activity among 400 IDs in the VAST data after preprocessing into time series of length 50.
Takeaways & Limitations
The approach can quickly identify anomalous nodes and enable standard structural analysis of the resulting reduced network.
Takeaways & Limitations
A global model is appropriate mainly for short or medium-term modeling, whereas longer-term evolution requires adaptive local models and sacrifices some computational simplicity.
Abstract
from arXiv · showhide
Learning the network structure of a large graph is computationally demanding, and dynamically monitoring the network over time for any changes in structure threatens to be more challenging still. This paper presents a two-stage method for anomaly detection in dynamic graphs: the first stage uses simple, conjugate Bayesian models for discrete time counting processes to track the pairwise links of all nodes in the graph to assess normality of behavior; the second stage applies standard network inference tools on a greatly reduced subset of potentially anomalous nodes. The utility of the method is demonstrated on simulated and real data sets.
1. Introduction.
The paper targets the difficulty of monitoring changing connectivity in large dynamic graphs. It uses communication activity as an initial way to identify individuals associated with meaningful network changes.
- Dynamic graph structure is computationally demanding to learn and even harder to monitor over time.
- The study evaluates the approach on 131 weeks of European Media Monitor data and simulated ten-day cell-phone records covering 400 phones.
- The method focuses first on individuals communicating more or less frequently than usual or communicating with different individuals.
2. Two-stage approach.
The approach first screens all node relationships for anomalous behavior, then applies standard network analysis to a much smaller subnetwork. This separates anomaly detection from subsequent structural characterization.
- The first stage sweeps the database to identify potentially anomalous nodes, while the second constructs a subgraph around them.
- Standard tools such as spectral clustering are then applied to the reduced subnetwork to characterize its structure.
- Pairwise communications are modeled over time as counting processes, and predictive p-values test whether current relationships depart significantly from prior behavior.
- The significance threshold is user-set; this paper uses 0.05, with the resulting anomaly-network size governing follow-up feasibility.
3. Discrete time counting process models.
The paper models network activity at pairwise, individual, and whole-network levels using Bayesian counting processes. Hurdle and nonparametric extensions address the sparse, zero-heavy temporal behavior of social links.
- Pairwise, individual and total activity analysis: Each pair’s communication increments are modeled as a counting process whose normal distribution defines departures to detect.
- Pairwise, individual and total activity analysis: Conjugate Bayesian models produce analytically tractable posterior predictive p-values for unusually extreme counts.
- Pairwise, individual and total activity analysis: Individual-level analyses monitor outgoing and incoming communication counts, while degree-sum processes monitor overall network activity.
- Parametric inference and hurdle models: Temporal sparsity creates many zero-communication periods, making standard exponential-family models inappropriate for normal behavior.
- Parametric inference and hurdle models: Hurdle models separately represent whether a pair is active and how many communications occur when it is active.
- Nonparametric inference: Dirichlet-process models provide a conjugate nonparametric alternative when no suitably simple parametric count model is evident.
4. Sequential and retrospective analyses.
Sequential analysis supports immediate monitoring, whereas retrospective analysis revises earlier assessments using later observations. Retrospective analysis is therefore more thorough but less immediate.
- Early observations are unlikely to be flagged sequentially because few prior data points are available for comparison.
- Retrospective analysis can revise judgments about early periods after incorporating the full observed history.
- Sequential analysis is faster and immediately relevant, while retrospective analysis contains sequential analysis as a special case.
5. Results.
The method identifies anomalous activity in both real media networks and simulated phone-call networks, then supports focused investigation of the implicated nodes, links, and periods.
- 5.1. EMM.: Retrospective analysis detects the known server downtime with very small p-values, whereas sequential analysis treats the downtime as acceptable during the learning phase and flags the period immediately afterward.The sequential analysis p-values therefore differ from the retrospective assessment of the same event.
- 5.1. EMM.: The EMM network contains 1,814 individuals but only 2,817 of 1,644,391 possible node connections are ever made, illustrating its sparsity.The most directly connected individual formed connections with 179 other nodes.
- 5.1. EMM.: The EMM analysis identifies the week ending 28 June 2006 as the period with the highest count of anomalous nodes across parametric and nonparametric models.This week was the 73rd week after the known server downtime.
- 5.1. EMM.: The Olmert–Abbas pair shows an unmatched connectivity peak in the week ending 28 June 2006, when they met in person and agreed to a first official summit.Their individual activity was higher than usual, while their pairwise contact peak was especially distinctive.
- 5.2. VAST 2008.: The sequential individual analysis finds a clear maximum at the start of the eighth day, and all eight anomalous nodes are among those identified by Ye et al. using all ten days.Spectral analysis shows six anomalous nodes appearing together in pairs, where each pair corresponds to one individual switching phones.
- 5.2. VAST 2008.: In the VAST data, predictive p-values fall near zero on days when the anomalous group changes cell-tower usage and begins using previously unused towers.The eighth day includes three uses of tower 30 and first use of towers 7, 9, 17, 20, 21, 22, and 28.
6. Discussion.
The method was applied successfully to real and simulated networks, with evidence of fast, scalable anomaly screening and agreement with external or model-based assessments. Its main scope boundary is that the global model is suited to short- or medium-term monitoring, not longer-term evolution.
- The methodology was successfully applied to real and simulated data sets of moderate size.
- 2.0 seconds was sufficient to identify anomalous individual activity among 400 VAST phone IDs using one computational core.The timing used Matlab 7.3.0 on a 64-bit 1.86 GHz Xenon quad-core machine.
- Agreement across different count models identified the same peak of anomalous behavior, while spectral clustering found a subnetwork structure consistent with other sources.
- The EMM data covered two and a half years, while the simulated cell-phone data covered ten days, providing moderate- and short-duration evaluation settings.
- For longer-term monitoring, a global model is inappropriate because normal behavior between individuals is expected to evolve; adaptive local changepoint models are suggested as an extension.The proposed extension would sacrifice some of the computational simplicity of the present approach.
Supplement A: Hurdle exponential family distributions
The supplementary materials provide technical details for the Bayesian inferential models and implementation code used in the paper.
- Supplement A provides details of the Bayesian inferential models and their parameterizations.
- The supplementary materials separate model specification details from executable implementation resources.
- Supplement B provides Matlab/Octave code for implementing the models used in the paper.