selib

A standardized library for structural entropy — compute it, optimize it, and benchmark SE methods against classical baselines under one API.

GitHub repo · SE gallery · SE tutorial · recursive structures · periodic table · survey maps · raw results JSON · reproduction benchmark · survey paper

What this is

Every SE paper ships its own loader, metric, and (often unmaintained) code, so "does structural entropy actually help?" is hard to answer on equal footing. selib fixes the interface: one Method.fit_predict(G, k, seed) contract, a native 2D-structural-entropy encoding-tree core, shared datasets and metrics, and a one-call benchmark — so an SE method and a Louvain baseline are scored exactly the same way. The tables below are produced by that benchmark; the headline takeaway matches the survey's regime-dependent verdict.

import selib
recs = selib.benchmark(["louvain", "leiden", "se_agglomerative"],
                       ["Karate", "SBM-Clean", "SBM-Noisy"])
selib.summarize(recs, "nmi")

0 · The library's SE optimizer

The shipped se_agglomerative only ever merges, so an early bad merge can never be undone — it gets stuck in poor local optima. se_louvain is this library's stronger minimizer of the same 2D structural-entropy objective: Louvain-style local node moves + community aggregation + multistart, with an O(degree) exact move delta. Validated against the canonical metric and against brute-force exhaustive optima on small graphs (gap 0.000).

2D structural entropy reached on each graph (lower is better); Δ is the relative reduction of se_louvain over the naive merger. se_louvain wins on 8/9 graphs.

0b · The library's hierarchical SE optimizer

Structural entropy is defined over an encoding tree, not just a flat partition. se_hier builds a multilevel tree (binary se_agglomerative dendrogram + recursive se_louvain inits) and refines it with exact-guarded local moves — collapse a redundant level, relocate a subtree — accepting a move only when it strictly lowers the exact tree structural entropy H^T. Because refinement starts from the naive dendrogram and only takes improving moves, the result is ≤ the naive dendrogram by construction; it is strictly lower on 6/6 graphs.

Encoding-tree structural entropy H^T (lower better)

Dasgupta cost of the hierarchy (lower better)

Validated in selib.htree: a 2-level tree's H^T equals the canonical 2D structural entropy exactly, and refinement is monotone. louvain_2level is a flat (2-level) hierarchy baseline.

0c · Comparison with existing work

All methods run on the identical graphs, all at free k (so the structural-entropy objective is compared fairly). The published SE community detectors CoDeSEG (original C++) and deDoc (original Java, the founding SE algorithm) run their real implementations through selib's wrappers. For the hierarchical comparison the original HCSE and BBM code (github.com/Hardict/HCSE) build the trees, and classical hierarchies (Paris, average / Ward linkage) are included — all scored on the same encoding-tree objective as se_hier. (* = structural-entropy method.)

2D structural entropy reached — free k (lower better)

2D community detection — NMI vs. ground truth (higher better)

On its own objective, se_louvain wins: it reaches the lowest 2D structural entropy on every graph — below the modularity methods and the published CoDeSEG. NMI tells a subtler, honest story: minimizing 2D-SE at free k tends to over-segment relative to the planted communities, so on clean graphs the modularity methods (Louvain/Leiden) recover ground truth better even though their structural entropy is higher. Run with a target k (§1) se_louvain recovers ground truth strongly. It beats the published SE detector CoDeSEG on NMI on 4/6 graphs; CoDeSEG's finer segmentation helps only on the hardest (noisy SBM, μ=0.5). Lesson: lower structural entropy ≠ better label recovery — a point the survey makes. deDoc (the founding SE algorithm, original Java) recovers the clean SBM almost perfectly (NMI 0.985) but degenerates to near-singletons on sparse Karate/LFR — it was designed for dense weighted Hi-C matrices; this exactly reproduces the survey campaign's numbers. (Its successor deDoc2 is excluded here: it only forms contiguous TAD-like domains over genomically-ordered bins, so on a general graph it groups consecutive node IDs and ignores the topology — a Hi-C tool, not a community detector.)

Hierarchical — encoding-tree structural entropy H^T (lower better)

Hierarchical — Dasgupta cost (lower better)

se_hier reaches the lowest H^T on every graph — below the original BBM and HCSE code, Paris, and the linkage baselines. It warm-starts from several constructions (binary SE dendrogram, recursive se_louvain, Paris) and refines the best with exact-guarded moves, so it is ≤ each by construction. BBM (deep binary merge) is the strongest original SE tree; HCSE targets a height-constrained hierarchy, so its full-depth H^T is higher here. Paris is the best non-SE classical tree.

Attributed graphs — citation networks with node features

se_gnn is selib's attribute-aware method (ported from the author's glass-jax prototype): a tiny GCN trained end-to-end to minimize a differentiable soft 2D structural entropy — validated so that the soft objective at a hard assignment equals the canonical 2D-SE exactly. DeSE / LSENet are the published feature-aware SE methods (reproduction-campaign numbers); the rest are run fresh by selib on the same standard Planetoid data.

NMI

ARI

Reading: feature-aware beats topology-only. se_gnn (2-layer GCN over the normalized adjacency + a balanced Sinkhorn assignment head, best-of-starts selected by the SE objective) finds the full number of communities (k = 6–7, no collapse) and beats every topology method on NMI, ARI and ACC on both datasets — on Cora it matches LSENet (NMI 0.487 vs 0.495) with a far smaller model. The Sinkhorn head is what prevents the cluster collapse that pure SE minimization induces with a plain softmax (ablation in segnn_head_eval.json). DeSE still leads NMI — the remaining gap.

Visualizations

What the optimizers actually produce — node-link layouts coloured by se_louvain communities, and the se_hier encoding tree. Rendered as inline SVG from the run.

0d · Robustness & scale

Every synthetic comparison repeated over 3 independent graph realizations (means shown). se_louvain has the lowest mean 2D-SE on 5/5 generators; se_hier ≤ Paris (the strongest classical tree) on 5/5.

Hierarchy quality at n = 500–1000

The first-improvement refinement (exact-guarded, O(m log h) scoring) extends se_hier beyond small graphs: it reaches the lowest H^T at every size, with growing margins over Paris and the original BBM.

1 · Real graphs & controlled SBM

Accuracy — ARI vs. ground truth

Higher is better.

Cross-objective — modularity

Higher = more modular partition.

SE (se_agglomerative, the native greedy 2D-SE encoding tree) matches the baselines on clean, well-separated structure and on Karate, but does not rescue performance once the planted signal is weak — the same fragility the survey reports for unsupervised community detection.

2 · LFR difficulty sweep

LFR graphs (n=500), mixing parameter μ on the x-axis: higher μ = more inter-community edges = harder. Mean NMI over 5 seeds.

All methods — SE and baselines alike — degrade together as μ rises and collapse past the detectability threshold; no method's curve is rescued by the SE objective. This is the core empirical message, now reproducible in one call.

3 · Scalability

SBM with per-node community signal held constant as N grows (k=10 blocks). Left: wall-clock per run; right table: NMI stays high, so runtime is measured on a task every method can solve.

Scalability — NMI

Per-node community signal held constant as N grows.

The native se_agglomerative core is a pure-Python greedy merge; the optimized C/igraph baselines (Louvain/Leiden/Infomap) are faster, while spectral clustering's dense eigendecomposition scales worst. These are wall-clock facts from the run, not claims.

Datasets

Reproduce

git clone https://github.com/SuuTTT/selib && cd selib
pip install -e ".[extra]"
python3 scripts/run_full_benchmark.py     # writes results/benchmark_results.json
python3 scripts/build_site.py             # regenerates this page from that JSON

All numbers on this page are read directly from results/benchmark_results.json produced by the run above on an RTX 3070 box. Methods that wrap a paper's original code (deDoc, CoDeSEG) are available through the same API once their upstream artifact is configured; the runs shown here use the native methods + classical baselines.