HN Showcase
Back to browse
GitHub Repository

DRESS: A Continuous Framework for Structural Graph Refinement

4 starsC

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

by velicast·Feb 24, 2026·2 points·0 comments
Visit ProjectView on HN

AI Analysis

●●●BangerBig BrainWizardryZero to One

Provably stronger than Weisfeiler-Leman without parameters—pure graph math, peer-reviewed.

Strengths
  • •Mathematically proven to exceed 1-WL expressiveness on known hard instances (prism/K₃,₃)
  • •Parameter-free deterministic algorithm eliminates hyperparameter tuning
  • •Broad language coverage (8+ bindings) lowers adoption friction for existing ecosystems
Weaknesses
  • •Niche audience (graph ML researchers); limited downstream production use cases shown
  • •Paper published 2018; newer GNN methods may have overshadowed original contribution
Category
AI/ML
Target Audience

Graph ML researchers, computational chemists, and network scientists evaluating graph isomorphism and structure analysis.

Similar To

Weisfeiler-Leman algorithm · Graph Neural Networks (GNNs) · PyTorch Geometric

Post Description

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?

Similar Projects