spectral-cleavage

A spectral formalization of political cleavage in signed networks, and a benchmark harness that tests it head-to-head against the signed-graph community-detection literature across multiple datasets.

Idea

A cleavage is the latent axis along which a polity splits into antagonistic camps. This project formalizes it as a spectral object: the leading eigenvector of the signed adjacency matrix — the direction u that maximizes uᵀ A u. Each actor's commitment is |uᵢ|; the side is sign(uᵢ); weakly committed actors form a neutral bridge.

The method is called CSA (Common Spectral Axis). Two quantities make it more than a single-snapshot detector:

• κ (unidimensionality) = 1 − λ₂⁺/λ₁ — how dominant the cleavage axis is. κ→1: one clear cleavage (stable regime); κ→0: competing axes (realignment).
• Realignment gradient Gₜ = sin²∠(ũₜ⁻, ũₜ⁺) — the rotation of the cleavage axis across time t. Local maxima mark structural realignments.

Why a benchmark, not just a method

The contribution only counts if the spectral axis recovers factions competitively with hand-crafted signed-partition methods and reveals temporal structure they cannot. So every detector — the proposed CSA and every baseline — implements one interface (SignedGraph → Partition) and is scored identically. The headline contrast is with FAULTANA (Fraxanet et al., Unpacking Polarization, PNAS Nexus 2024), the canonical recent method for polarization in signed online networks: it finds factions by pure frustration minimization with no spectral step. Same task, opposite mechanism.

Baselines

Detector	Mechanism	Reference
CSA (proposed)	leading eigenvector of A + commitment threshold	this work
pcd	regularized balance objective, local search	Aronsson & Chehreghani, NeurIPS 2025
eigensign	dominant eigenvector + Rayleigh threshold sweep	Bonchi et al., 2019
sponge	signed Laplacian generalized eigenproblem	Cucuringu et al., 2019
frustration_greedy	min-frustration bipartition (FAULTANA-style)	Fraxanet et al., 2024
correlation_clustering	Pivot	Ailon, Charikar, Newman, 2008

Install

pip install -e ".[dev]"

Use

scleavage list                                   # registered detectors & datasets
scleavage bench --detectors csa,pcd,eigensign --datasets synthetic,bitcoin_otc

from scleavage.datasets import load
from scleavage.detectors import build
from scleavage.core import label_recovery
from scleavage.temporal import kappa, common_axis, realignment_gradient

g = load("synthetic", n=400, noise=0.05)
part = build("csa")(g)
print(label_recovery(part, g.labels))            # {'ari': ..., 'nmi': ...}
print("kappa =", kappa(g.A))

Scorecards

Birdwatch BW1 — vs. Fraxanet's frustration-optimal labels (n=2676, real data)

The decisive contrast: the spectral axis recovered against the labels FAULTANA produces by frustration minimization. CSA recovers the published split at ARI 0.97 and beats the frustration-greedy baseline (0.91), while declaring a neutral core instead of forcing every node onto a side.

detector	ari	nmi	coverage	neutrals	runtime_s	note
csa	0.973	0.939	0.55	1193	0.001	spectral axis + neutral core
pcd	0.997	0.991	0.42	1544	0.004	balance local search (strongest)
eigensign	1.000	1.000	0.07	2500	0.005	perfect on a tiny core; abstains on 93%
frustration_greedy	0.923	0.855	1.00	0	0.010	FAULTANA-style mechanism
sponge	0.001	0.001	1.00	0	2.20	collapses here (needs τ tuning)

Synthetic planted partition (n=200, sanity check)

All balance/spectral methods recover the planted split; CSA fastest with a clean neutral set. Correlation-clustering Pivot fragments into many clusters — expected.

detector	ari	coverage	neutrals	runtime_s
csa	1.00	0.94	12	0.001
pcd	1.00	0.98	5	0.055
eigensign	1.00	0.88	25	0.000
sponge	1.00	1.00	0	1.83
frustration_greedy	1.00	1.00	0	0.24
correlation_clustering	0.04	1.00	0	0.02

Reproduce: scleavage bench --detectors csa,pcd,eigensign,sponge,frustration_greedy --datasets birdwatch_bw1 (downloads the BW1 CSVs from OSF on first run).

Performance

Compute concentrates in two places, handled differently:

• Spectral detectors (CSA, EigenSign, SPONGE) are already native — a sparse symmetric eigensolve runs in ARPACK/LAPACK (C/Fortran) under SciPy. Nothing to gain from a rewrite.

• Combinatorial local search (frustration_greedy, pcd) were the only pure-Python bottlenecks. Their inner loops run as JIT-compiled CSR kernels (detectors/_kernels.py, Numba) — no system C++ compiler required, LLVM ships in the wheel. On Birdwatch BW1:

  kernel	pure Python	JIT (warm)	speedup
  frustration_greedy	4.33 s	0.010 s	~430×
  pcd	1.12 s	0.004 s	~280×

  Recovery is unchanged (ARI within noise). The first call compiles once (~1–2 s, cached to disk); install with pip install -e ".[perf]". If Numba is absent the kernels fall back to pure Python, so the package never hard-depends on it.

Numba vs. a hand-written C++ kernel

To bound what a native rewrite buys, cpp/frustration.cpp reimplements the frustration search in C++17 and cpp/compare.py runs it head-to-head on Birdwatch BW1 (same graph, same scoring):

impl	ARI	time_s
C++ (MSVC /O2)	0.909	0.0050
Numba	0.923	0.0112
pure Python (baseline)	0.907	4.33

C++ is ~2.3× over Numba — but both are ~400–800× over pure Python. The decisive jump is Python → compiled; compiled → C++ is marginal here. So the kernels stay in Numba (no system compiler, JIT in the wheel); the C++ path is kept for reference and for graphs large enough that the constant factor starts to matter.

The data-handling glue (CSV parsing, ARI/NMI, downloads) stays in Python by design — it is not the bottleneck, and SciPy/scikit-learn already back it with compiled code.

Layout

src/scleavage/
  core/        SignedGraph, Partition, metrics      (the contract — see docs/adr/0001)
  detectors/   csa + baselines, one registry
  datasets/    loaders (SNAP, Fraxanet/OSF, synthetic), one registry
  temporal/    kappa, common axis, realignment gradient   (the differentiated track)
  eval/        scorecard, significance

Datasets

Public datasets are downloaded by the loaders and never vendored. The Fraxanet signed networks (Birdwatch, DerStandard) require a manual download from OSF (CC-BY 4.0) — see docs/datasets.md. The method is documented in docs/method.md.

License

MIT (code). Datasets retain their own licenses; cite the originals.