DELTACON: A Principled Massive-Graph Similarity Function

Danai Koutra; Joshua T. Vogelstein; Christos Faloutsos

Source-linked AI summary

DELTACON: A Principled Massive-Graph Similarity Function

Danai Koutra, Joshua T. Vogelstein, Christos Faloutsos

arXiv:1304.4657v1Apr 17, 2013cs.SIphysics.soc-ph

TL;DR

The paper addresses how to compare connectivity between graphs with known node correspondence while meeting accuracy and scalability needs. It formalizes similarity axioms and proposes DELTACON, which compares node affinities; experiments and applications evaluate it on synthetic, real, brain, and Enron graphs. DELTACON is reported as principled, intuitive, scalable, and useful for clustering/classification and temporal anomaly detection.

Problem
Graph similarity asks how much two networks differ in connectivity, but graph comparison remains open as graphs grow in number and size and require accurate, scalable methods.
Method
DELTACON formalizes similarity axioms and compares node-affinity matrices for two graphs with the same node set and known correspondence.
Results
DELTACON is reported as principled, intuitive, and scalable, and is evaluated against six state-of-the-art measures in synthetic and real datasets and applications.
Takeaways & Limitations
DELTACON is used for temporal anomaly detection in Enron email graphs and for clustering and classifying brain connectivity graphs.
Takeaways & Limitations
Future work includes parallelizing the algorithm and finding more informative graph partitions than random partitioning.

Abstract

from arXiv · show

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.

1 Introduction

Graph similarity remains an open problem: useful methods must compare connectivity accurately while scaling to graphs with billions of nodes. The paper formalizes desired properties, proposes DELTACON, and applies it to synthetic, real, brain, and Enron graphs.

Graph similarity supports sense-making tasks such as detecting computer attacks, celebrations, and telecommunications problems from connectivity changes.
Graph comparison remains open because growing graphs require methods that are both accurate and scalable to billions of nodes.
The paper asks how to compare networks efficiently and evaluate their similarity scores.
DELTACON is presented as principled, intuitive, and scalable, conforming to formal axioms and producing explainable similarity scores for large-scale graphs.
The authors compare DELTACON with six state-of-the-art methods and apply it to Enron anomaly detection and brain-graph clustering and classification.
Hierarchical clustering of 114 connectomes produced two connectivity-based clusters associated with high and low creativity.

2 Proposed Method: Intuition

DELTACON compares graphs with known node correspondence by comparing node affinities rather than merely overlapping edges. Its affinity construction weights short and long paths, while its design is guided by formal axioms and intuitive properties.

The problem takes two graphs with the same node set and known correspondence and returns a similarity score from 0 for totally different graphs to 1 for identical graphs.
Edge overlap can miss structural importance: removing a bridge may affect information flow more than removing an edge inside a clique.
DELTACON computes pairwise node affinities in each graph, then compares corresponding affinity scores to obtain graph similarity.
The method uses Fast Belief Propagation’s simplified formulation because it has theoretical grounding, runs linearly in the number of edges, and accounts for multistep neighbors.
In S = [I + ϵ^2D − ϵA]^-1, S stores pairwise affinities, A is the adjacency matrix, D contains node degrees, and ϵ controls neighboring influence.
The affinity intuition weights 1-step, 2-step, and longer paths with decreasing influence, while the implementation uses the full matrix formulation rather than the expansion.
The similarity measure is designed to satisfy identity, symmetry, and zero properties, plus edge importance, weight awareness, edge-submodularity, and focus awareness.
Scalability is a stated requirement because generated graphs can be huge and abundant, including graphs with billions of nodes.

3 Proposed Method: Details

DELTACON compares reduced node-affinity matrices rather than all pairwise affinities, using ROOTED distance and a distance-to-similarity transformation. Grouping reduces computation from quadratic affinity scoring to a method linear in graph edges and groups, while preserving the stated similarity properties.

Algorithm: DELTACON computes n × n pairwise node-affinity matrices for the straightforward method, then compares the corresponding matrices of the two graphs.Each matrix entry represents the influence or affinity of one node to another.
Similarity computation: ROOTED distance compares affinity scores after taking their square roots, boosting affinities and detecting smaller graph changes than ordinary Euclidean distance.The resulting distance is converted to sim = 1/(1+d), yielding scores in [0,1].
Scalable approximation: DELTACON0 computes all n^2 affinity scores and therefore has quadratic cost, whereas DELTACON groups nodes and computes only n × g scores with g ≪ n.The grouped scores summarize each node’s affinity to a group of seed nodes.
Scalable approximation: The reduced affinity matrix S′ is computed in time linear in the number of edges, using group-membership vectors as multiple simultaneous seeds.The method solves a linear system with one right-hand side per group.
Scalability: DELTACON runs in O(g · max{m1, m2}) time on two graphs in parallel and takes approximately 160 seconds on a 1.6-million-node graph.The algorithm computes g final scores per node and compares the two reduced matrices with ROOTED distance.
Approximation guarantee: DELTACON’s similarity score upper-bounds DELTACON0’s score, and DELTACON includes DELTACON0 as the special case g = n.The paper attributes the upper bound to the blurring of influence information caused by grouping nodes.

4 Experiments

Experiments test whether DELTACON satisfies stated similarity properties, scales to large graphs, and distinguishes structural changes better than six competing methods. Across synthetic and real datasets, DELTACON satisfies all four properties and scales linearly with graph edges.

4.1 Intuitiveness of DELTACON: DELTACON and DELTACON0 obey all required properties P1–P4, whereas baseline methods fail on several structural requirements.The paper specifically notes failures of spectral methods and Signature Similarity on edge importance and edge-submodularity, and limitations of λ-distance, VEO, and GED.
4.1 Intuitiveness of DELTACON: Only DELTACON distinguishes edge importance with respect to connectivity; every other evaluated method fails at least once.The tests use barbell, wheel-barbell, and lollipop graphs, where bridge edges are more consequential than edges inside dense components.
4.1 Intuitiveness of DELTACON: All methods except VEO and GED are weight-aware when comparing weighted barbell graphs.VEO and GED rely on edge and vertex overlap, so they do not account for edge weights.
4.1 Intuitiveness of DELTACON: Only DELTACON satisfies edge-submodularity in every examined topology and edge-removal case.The experiments compare graph pairs after removing either one or ten edges; non-positive table values indicate violations.
4.1 Intuitiveness of DELTACON: DELTACON is focus-aware: targeted removal of the same number of edges produces lower similarity than random removal.Across four real networks and corruption levels from 10% to 80%, random and targeted scores converge as more edges are deleted.
4.2 Scalability: DELTACON scales linearly with the number of graph edges.Its parallel time complexity is O(g · max{m1, m2}), where g is the number of groups and m1, m2 are graph edge counts.

5 DELTACON at Work

DELTACON is applied to temporal Enron email graphs for anomaly detection and to brain connectivity graphs for clustering. The applications associate detected network changes with Enron events and brain-graph clusters with creativity-related attributes.

5.1 Enron: Daily Enron email-graph similarity scores are monitored using median ±3σ control limits to identify anomalous days.The similarity compares consecutive daily who-emailed-whom graphs, with moving-range estimates used for σ.
5.1 Enron: High similarity between consecutive Enron days usually occurs on weekends, including periods when only two employees exchanged emails.After Enron’s collapse, many consecutive days were also highly similar because email activity was low and concentrated among certain employees.
5.2 Brain Connectivity Graph Clustering: Hierarchical clustering of DELTACON similarities separates 114 brain graphs into two clearly separable groups.Each graph contains 70 cortical-region nodes, with weighted connections converted to undirected, unweighted graphs for analysis.
5.2 Brain Connectivity Graph Clustering: The two brain-graph clusters differ significantly in Composite Creativity Index, with p-value=0.0057.They also correspond to low and high openness index with p-value=0.0558, while age, gender, and IQ lack sufficient evidence of association with brain connectivity.

6 Related Work

Related work distinguishes graph similarity with known node correspondence from methods that must infer correspondence. This paper focuses on the former setting, where correspondence-aware algorithms can outperform methods that omit it.

Known-correspondence methods compare graphs when corresponding nodes are identified, whereas unknown-correspondence methods use features, matching, or graph kernels.
Prior known-correspondence approaches include Signature Similarity, Vertex/Edge Overlap, Graph Edit Distance, and Maximum Common Subgraph.Graph Edit Distance and Maximum Common Subgraph are NP-complete, although Graph Edit Distance can become linear in nodes and edges in a suitable application.
Unknown-correspondence research includes spectral λ-distance, algebraic connectivity, global-feature SVMs, heat-kernel edge curvature, spanning-tree counts, and random-walk graph kernels.
The authors focus on known node correspondence, such as comparing time-evolving phone networks, because correspondence-aware algorithms can use information omitted by other methods.
Node-affinity methods such as PageRank, personalized random walks, electric-network analogies, SimRank, and belief propagation support tasks including ranking, classification, malware detection, and fraud detection.

7 Conclusions

The paper concludes by presenting DELTACON as a principled, intuitive, and scalable method for graph similarity with known node correspondence. It evaluates the method against state-of-the-art measures and applies it to anomaly detection and brain-graph classification.

DELTACON formalizes graph-similarity axioms and desired properties while addressing comparisons between graphs with known node correspondence.
DELTACON needs approximately 160 seconds on commodity hardware for a graph with over 67 million edges.
Experiments evaluate DELTACON’s intuitiveness and compare it with six state-of-the-art similarity measures.
Applications use DELTACON for temporal anomaly detection in ENRON and clustering and classification of brain graphs.
Future work includes parallelizing the algorithm and replacing random graph partitioning with a more informative strategy, such as an elimination tree.

A.1 From Fast Belief Propagation (FABP) to DELTACON

DELTACON is derived from fast approximate loopy belief propagation by truncating a Maclaurin expansion, choosing basis-vector priors, and setting the influence parameter to ε/2.

FABP is a fast approximation of loopy belief propagation that is guaranteed to converge and is expressed through a linear equation.
The FABP equation uses prior scores as input and final scores, or beliefs, as output.
DELTACON’s core formula results from truncating the Maclaurin expansion after power 2, setting the prior vector to a basis vector, and choosing h = ε/2.
The parameter h is described as encoding the influence between neighboring nodes.

A.2 Connection between FABP and Personalized RWR

The paper rewrites the FABP equation into a Personalized Random-Walk-with-Restarts-like form. Linear-algebra transformations define the corresponding adjusted transition matrix and restart vector.

Theorem 2 states that FABP equation (2.1) can be represented in Personalized RWR-like form.
The reformulation sets c′′ = 1 − ε and defines a transformed matrix A* together with a vector y.
The proof derives the RWR-like representation by left-multiplying by D−1, defining F, then left-multiplying by F−1 and rearranging.

A.3 Proofs for Section 3

The appendix establishes DELTACON’s computational complexity, group-affinity relationship, similarity bound, axioms, and selected property guarantees. Theoretical coverage is complete for the axioms but limited to a special case for edge importance.

Complexity: DELTACON runs in O(g · max{m1, m2}) time, linear in the number of graph edges for small constant g.The proof also gives O((g + 1)n + g(m1 + m2)) before simplifying under the stated condition.
Affinity scores: A group affinity score in DELTACON equals the sum of the corresponding individual-node affinity scores in DELTACON0.This equality follows from solving linear systems with grouped right-hand sides.
Similarity bound: DELTACON’s similarity score upper-bounds DELTACON0’s score: simDC−0(G1, G2) ≤ simDC(G1, G2).The associated distance comparison is that DELTACON0’s distance is greater than DELTACON’s distance.
Axioms: DELTACON0 satisfies identity and symmetry exactly, while randomized DELTACON satisfies symmetry on average; similarity between a clique and empty graph tends to zero as n grows.The zero-property proof derives this from the rooted distance becoming arbitrarily large.
Scope of guarantees: The appendix proves edge importance only for the barbell special case; general proofs for this and the remaining properties are left for future work.The Euclidean distance does not always satisfy edge importance.
Edge importance: For the barbell special case, d(A, C)^2 − d(A, B)^2 ≥ 0, showing that removing the bridge affects distance at least as much as removing one clique edge.The result holds whether the missing clique edge is adjacent to the bridge node or elsewhere.