conservation-anomaly

Spectral anomaly detection using the conservation ratio of graph Laplacians.

What It Does

Every graph has a Laplacian matrix whose eigenvalues encode structural properties. The conservation ratio (CR) measures how well a graph preserves its structural integrity:

CR = λ₂ / (λₙ - λ₂)

where λ₂ is the Fiedler value (algebraic connectivity) and λₙ is the largest eigenvalue. When CR drops significantly, something structurally anomalous has happened.

Installation

pip install conservation-anomaly

Quick Start

Python API

from conservation_anomaly import AnomalyDetector
import networkx as nx

# Fit a baseline (normal) graph
baseline = nx.complete_graph(10)
detector = AnomalyDetector(threshold=0.3)
detector.fit(baseline)

# Detect anomalies in new graphs
results = detector.detect([nx.path_graph(10), nx.cycle_graph(10)])
for r in results:
    print(f"Graph {r['index']}: CR={r['cr']}, anomaly={r['is_anomaly']}")

# Explain what changed
explanation = detector.explain(nx.path_graph(10))
print("Top contributing nodes:", explanation["node_contributions"])
print("Partition changes:", explanation["partition_changes"])

CLI

# Analyze a graph's conservation ratio
conservation-anomaly analyze graph.csv

# Detect anomalies against a baseline
conservation-anomaly detect baseline.json timeseries.csv --threshold 0.3

# Compare two graphs
conservation-anomaly compare graph1.json graph2.json

# Compute Fiedler partition with visualization
conservation-anomaly fiedler graph.csv --visualize --output partition.png

Input Formats

• CSV: Adjacency matrix (comma-separated, one row per line)
• JSON: Edge list with optional node list

  {
    "nodes": [0, 1, 2, 3],
    "edges": [
      {"source": 0, "target": 1, "weight": 1.0},
      {"source": 1, "target": 2, "weight": 0.5}
    ]
  }
  

• Pickle: NetworkX Graph object

How It Works

1. Conservation Ratio: Computed from the Laplacian eigenvalue spectrum. Higher values indicate more "conserved" (well-connected, regular) structure.

2. Anomaly Detection: Compare a graph's CR against a fitted baseline. A significant drop triggers an anomaly flag.

3. Explanation via Fiedler Analysis: The Fiedler vector (eigenvector for λ₂) reveals the graph's natural bipartition. By comparing Fiedler vectors between baseline and anomalous graphs, we identify which nodes and edges contributed to the structural change.

4. Alignment Coefficient: Measures how similarly two graphs partition their nodes using cosine similarity of Fiedler vectors.

License

MIT