Abstract
This paper studies detecting anomalous edges in directed graphs that model social networks. We exploit edge exchangeability as a criterion for distinguishing anomalous edges from normal edges. Then we present an anomaly detector based on conformal prediction theory; this detector has a guaranteed upper bound for false positive rate. In numerical experiments, we show that the proposed algorithm achieves superior performance to baseline methods.
Introduction
Detecting malicious activity in social networks—such as spam bots, cyber-bullying, or misinformation—is often modeled as finding "anomalous edges" in a graph. However, two major hurdles exist:
- Modeling Sparsity: Traditional graph models often assume "vertex exchangeability," which mathematically forces graphs to be either empty or extremely dense—neither of which describes a real social network.
- Lack of Guarantees: Most modern detectors are "black boxes" or heuristics. They might provide an anomaly score, but they cannot guarantee the false positive rate, which is critical for security-critical applications.
This work bridges this gap by using a model that naturally handles sparse, growing networks and wrapping it in a framework that offers provable statistical safety.
Methodology
The proposed approach rests on three pillars: edge exchangeability, the Asymmetric Dirichlet Network Distribution (ADND) model, and inductive conformal prediction.
Edge Exchangeability
Instead of focusing on nodes, the sequence of edges is treated as the fundamental unit. A sequence is "exchangeable" if its joint distribution remains invariant under permutations of the edge order. This assumption is better suited for the sparse, power-law nature of real-world social networks compared to vertex exchangeability.
The ADND Model
To model "normal" network behavior, the authors use the Asymmetric Dirichlet Network Distribution (ADND). This Bayesian nonparametric model clusters edges into "topics" based on the roles of the sender and receiver. It is flexible enough to account for asymmetric behaviors, such as news bots that primarily send information versus users who primarily receive it.
Inductive Conformal Prediction
This framework provides the mathematical guarantee for the false positive rate. The algorithm calculates a non-conformity measure (NCM)—a "surprise" score—for a new edge based on the ADND model. By comparing this score to a calibration set of known "normal" edges, the system produces a $p$-value. If the $p$-value is below a user-defined threshold $\epsilon$, the edge is flagged as anomalous. The authors prove that the probability of a false alarm is mathematically bounded by $\epsilon$.
Experimental Evaluation
The model was evaluated using Ethereum blockchain transaction data from Uniswap V3 token swaps. In this context, most swaps occur through established liquidity pools (normal edges), while "multi-hop" swaps without a direct liquidity pair can indicate pricing anomalies or arbitrage (anomalous edges).
Key Results
- Performance: The Conformal Detector achieved an AUC of 0.901 on the Ethereum dataset.
- Comparison: While the RHSS baseline achieved a slightly higher AUC (0.962), it lacks the theoretical guarantees and robustness to model misspecification provided by the conformal framework.
- Provable Safety: The most significant result is the proof that the detector's false positive rate will not exceed the pre-specified significance level $\epsilon$, provided the "normal" data is exchangeable.
Discussion and Conclusion
By shifting the focus from "Who are the nodes?" to "What are the interactions?", the model handles the "cold start" problem (new nodes appearing) more effectively than traditional adjacency-matrix-based methods. Furthermore, turning an anomaly score into a $p$-value with a guaranteed error bound allows operators to set a specific "budget" for false alarms.
Future work includes addressing the "static" assumption of exchangeability for networks that change drastically over time and integrating the conformal framework with Graph Neural Networks (GNNs) to enhance detection power.
Summary updated