Show HN: Dress – A parameter-free O(E) graph equation that provably exceeds 1-WL

2 points

3 months ago

DRESS is a nonlinear fixed-point equation that assigns a continuous similarity value to every edge in a graph. No parameters, no learning, just iterate until convergence. The result is deterministic, bounded in [0,2], and unique.

I published the original equation in 2018 (arXiv:1805.01419). I've now proved it's strictly more powerful than 1-WL (Weisfeiler-Leman colour refinement) — the standard benchmark for graph neural network expressiveness. The proof uses the prism graph vs K₃,₃, the textbook pair that 1-WL can't separate. DRESS distinguishes them because it works on edges, and different edge roles (triangle edges vs bridge edges) force different fixed-point values.

Two extensions — Motif-DRESS and Δ-DRESS — empirically distinguish Strongly Regular Graphs that defeat 3-WL, at near-linear cost instead of O(n⁴).

The library is written in C with bindings for C++, Python, Rust, Go, Julia, R, MATLAB, and WebAssembly. pip install dress-graph to try it.

Paper: https://github.com/velicast/dress-graph/blob/main/research/k...

Docs: https://velicast.github.io/dress-graph/

Looking for feedback. What am I missing? What should I test next?