# DELTACON: A Principled Massive-Graph Similarity Function

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Apr 2013.

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

- [Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding](https://mlsanity.com/paper/2102.13582/) (2021)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [Digital Twin-Oriented Complex Networked Systems based on Heterogeneous Node Features and Interaction Rules](https://mlsanity.com/paper/2308.11034/) (2023)
- [An embedding-based distance for temporal graphs](https://mlsanity.com/paper/2401.12843/) (2024)
- [Graph Laplacian Learning with Exponential Family Noise](https://mlsanity.com/paper/2306.08201/) (2023)
- [GraphAnoGAN: Detecting Anomalous Snapshots from Attributed Graphs](https://mlsanity.com/paper/2106.15504/) (2021)
- [Hypergraph Dissimilarity Measures](https://mlsanity.com/paper/2106.08206/) (2021)
- [Efficient Inference of Spatially-varying Gaussian Markov Random Fields with Applications in Gene Regulatory Networks](https://mlsanity.com/paper/2206.10174/) (2022)
- [GeSubNet: Gene Interaction Inference for Disease Subtype Network Generation](https://mlsanity.com/paper/2410.13178/) (2024)
- [When GNNs Fail: Quantifying and Overcoming Temporal Correlation Volatility in Time Series](https://mlsanity.com/paper/2608.07333/) (2026)
- [CARMIL: Context-Aware Regularization on Multiple Instance Learning models for Whole Slide Images](https://mlsanity.com/paper/2408.00427/) (2024)
- [Valid Bootstraps for Network Embeddings with Applications to Network Visualisation](https://mlsanity.com/paper/2410.20895/) (2024)
- [A Framework Based on Graph Cellular Automata for Similarity Evaluation in Urban Spatial Networks](https://mlsanity.com/paper/2511.00768/) (2025)
- [FC-ADL: Efficient Microservice Anomaly Detection and Localisation Through Functional Connectivity](https://mlsanity.com/paper/2512.00844/) (2025)
- [Agent-based Modeling: Equilibrium, Echo Chambers, and Efficiency in Hybrid Coevolutionary Opinion Games](https://mlsanity.com/paper/2609.27639/) (2026)
- [A temporal graph dissimilarity measure capturing epidemic spreading behavior](https://mlsanity.com/paper/2610.16456/) (2026)

## Abstract (arXiv)

How much did a network change since yesterday? How different is the wiring between Bob's brain (a left-handed male) and Alice's brain (a right-handed female)? Graph similarity with known node correspondence, i.e. the detection of changes in the connectivity of graphs, arises in numerous settings. In this work, we formally state the axioms and desired properties of the graph similarity functions, and evaluate when state-of-the-art methods fail to detect crucial connectivity changes in graphs. We propose DeltaCon, a principled, intuitive, and scalable algorithm that assesses the similarity between two graphs on the same nodes (e.g. employees of a company, customers of a mobile carrier). Experiments on various synthetic and real graphs showcase the advantages of our method over existing similarity measures. Finally, we employ DeltaCon to real applications: (a) we classify people to groups of high and low creativity based on their brain connectivity graphs, and (b) do temporal anomaly detection in the who-emails-whom Enron graph.