DELTACON: A Principled Massive-Graph Similarity Function
arXiv:1304.4657
Abstract
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.
2013 SIAM International Conference in Data Mining (SDM)
Cited by in corpus (26)
- NetLSD: Hearing the Shape of a Graph
- Graph-based Anomaly Detection and Description: A Survey
- DDGK: Learning Graph Representations for Deep Divergence Graph Kernels
- Joint Embedding of Graphs
- Discovering and Deciphering Relationships Across Disparate Data Modalities
- netrd: A library for network reconstruction and graph distances
- Real-Time Anomaly Detection in Edge Streams
- Multilayer patent citation networks: A comprehensive analytical framework for studying explicit technological relationships
- Graph Comparison via the Non-backtracking Spectrum
- Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs
- Anomaly Detection in Dynamic Networks of Varying Size
- Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous Graphs
- Found Graph Data and Planted Vertex Covers
- Constant State of Change: Engagement Inequality in Temporal Dynamic Networks
- Size Agnostic Change Point Detection Framework for Evolving Networks
- A Review of Network Inference Techniques for Neural Activation Time Series
- Mapper Comparison with Wasserstein Metrics
- Linearized and Single-Pass Belief Propagation
- RECS: Robust Graph Embedding Using Connection Subgraphs
- Mining Density Contrast Subgraphs
- Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative GLASSO and Projection
- CADDeLaG: Framework for distributed anomaly detection in large dense graph sequences
- Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
- Quantum walk inspired algorithm for graph similarity and isomorphism
- Graph comparison via nonlinear quantum search
- Intrinsic Geometric Information Transfer Learning on Multiple Graph-Structured Datasets