# Anomalous Edge Detection in Edge Exchangeable Social Network Models

arXiv: https://arxiv.org/abs/2109.12727 · HTML: https://mlsanity.com/paper/2109.12727/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 59 references that are in the map.
- First posted on arXiv 27 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Graph-based Anomaly Detection and Description: A Survey](https://mlsanity.com/paper/1404.4679/) (2014)
- [Conformal Prediction: a Unified Review of Theory and New Challenges](https://mlsanity.com/paper/2005.07972/) (2020)
- [Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More](https://mlsanity.com/paper/2008.12952/) (2020)
- [Real-time Out-of-distribution Detection in Learning-Enabled Cyber-Physical Systems](https://mlsanity.com/paper/2001.10494/) (2020)
- [Exchangeability, Conformal Prediction, and Rank Tests](https://mlsanity.com/paper/2005.06095/) (2020)
- [MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams](https://mlsanity.com/paper/1911.04464/) (2019)
- [F-FADE: Frequency Factorization for Anomaly Detection in Edge Streams](https://mlsanity.com/paper/2011.04723/) (2020)
- [Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures](https://mlsanity.com/paper/1312.7857/) (2013)
- [Sparse graphs using exchangeable random measures](https://mlsanity.com/paper/1401.1137/) (2014)
- [Inductive Conformal Martingales for Change-Point Detection](https://mlsanity.com/paper/1706.03415/) (2017)
- [Conformal k-NN Anomaly Detector for Univariate Data Streams](https://mlsanity.com/paper/1706.03412/) (2017)
- [Edge-exchangeable graphs and sparsity](https://mlsanity.com/paper/1603.06898/) (2016)
- [Exchangeable Variable Models](https://mlsanity.com/paper/1405.0501/) (2014)

## Built on by (most cited first, 17 of 17)

- [Trustworthy Classification through Rank-Based Conformal Prediction Sets](https://mlsanity.com/paper/2407.04407/) (2024)
- [Conformal Prediction for Network-Assisted Regression](https://mlsanity.com/paper/2302.10095/) (2023)
- [Conformal Load Prediction with Transductive Graph Autoencoders](https://mlsanity.com/paper/2406.08281/) (2024)
- [Weighted Aggregation of Conformity Scores for Classification](https://mlsanity.com/paper/2407.10230/) (2024)
- [Conformal link prediction for false discovery rate control](https://mlsanity.com/paper/2306.14693/) (2023)
- [Extending Conformal Prediction to Hidden Markov Models with Exact Validity via de Finetti's Theorem for Markov Chains](https://mlsanity.com/paper/2210.02271/) (2022)
- [Entropy Reweighted Conformal Classification](https://mlsanity.com/paper/2407.17377/) (2024)
- [Conformalized Interval Arithmetic with Symmetric Calibration](https://mlsanity.com/paper/2408.10939/) (2024)
- [Conditional Conformal Risk Adaptation](https://mlsanity.com/paper/2504.07611/) (2025)
- [Volume-Sorted Prediction Set: Efficient Conformal Prediction for Multi-Target Regression](https://mlsanity.com/paper/2503.02205/) (2025)
- [Enhancing Adversarial Robustness with Conformal Prediction: A Framework for Guaranteed Model Reliability](https://mlsanity.com/paper/2506.07804/) (2025)
- [Enhanced Route Planning with Calibrated Uncertainty Set](https://mlsanity.com/paper/2503.10088/) (2025)
- [Uncertainty Quantification on Graph Learning: A Survey](https://mlsanity.com/paper/2404.14642/) (2024)
- [Fast Conformal Prediction using Conditional Interquantile Intervals](https://mlsanity.com/paper/2601.02769/) (2026)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)
- [Residual Reweighted Conformal Prediction for Graph Neural Networks](https://mlsanity.com/paper/2506.07854/) (2025)
- [Conflict Forecasting via Conformal Prediction for Markov Processes](https://mlsanity.com/paper/2604.25139/) (2026)

## Abstract (arXiv)

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.