Benchmarks

Empirical evaluation of the IsalGraph framework across five real-world graph datasets. Results from López-Rubio & Pascual-González (2026).

1. Message Length Efficiency

IsalGraph encodes graph structure using fewer bits than the GED information-theoretic model. The ratio compares IsalGraph's uniform-alphabet encoding against the GED standard baseline (\(\lceil \log_2(|V|!) \rceil + |E| \cdot \lceil \log_2(|V|^2) \rceil\) bits).

Compression ratio by dataset (standard baseline)

Ratio > 1.0 means IsalGraph uses fewer bits. Higher is better. All methods achieve ratio > 1.3 on every dataset.

Detailed comparison

2. Empirical Time Complexity

Power-law scaling \(T(n) \propto n^{\alpha}\) on synthetic graphs (Barabási–Albert, Erdős–Rényi, paths, stars, cycles, complete, binary trees, grids). The greedy single-start encoder scales as \(O(n^{2.7})\), significantly faster than exact GED.

Scaling exponents by method (overall fit)

Scaling exponents by graph family

3. Correlation with Graph Edit Distance

Spearman rank correlation (\(\rho\)) between the IsalGraph Levenshtein distance and exact graph edit distance. Strong correlation on structured graphs (IAM Letter LOW: \(\rho = 0.93\)), moderate on sparse molecular graphs (AIDS: \(\rho = 0.33\)).

Spearman ρ by dataset (Canonical Pruned)

Method comparison

Comparison with Weisfeiler-Leman kernel

IsalGraph (Canonical Pruned) outperforms the 3-iteration WL subtree kernel on 4 of 5 datasets. The WL kernel is slightly better on AIDS (sparse molecular graphs with high structural heterogeneity).

4. Computational Speedup

End-to-end wall-clock comparison: IsalGraph encoding + Levenshtein distance vs. exact GED computation. Speedup increases with graph size.