DRESS: A parameter-free graph fingerprint that matches…
0 reactions
DRESS: A parameter-free graph fingerprint that matches 2-WL at O cost, with 9 language bindings
I've been working on a continuous framework for structural graph refinement called DRESS. It's a single nonlinear fixed-point equation on edges that converges to a unique, deterministic solution in \0, 2\], no hyperparameters, no training.
**What it does:** Given any graph's edge list, DRESS iteratively computes a self-consistent similarity value for every edge. Sorting these values produces a canonical graph fingerprint.
**Key results:**
* **Expressiveness:** Original DRESS (depth-0) matches **2-WL** in distinguishing power. Under the Reconstruction Conjecture, depth-k DRESS is at least as powerful as (k+2)-WL at O(C(n,k) · I · m · d\_max) cost vs. O(n\^{k+3}) for (k+2)-WL.
* **Isomorphism testing:** Tested on SRGs, CFI constructions, and the standard MiVIA and IsoBench benchmarks.
* **GED regression:** DRESS fingerprint differences fed to a simple regressor achieve **15× lower MSE** than TaGSim on LINUX graphs
* **Convergence:** On a 59M-vertex Facebook graph, it converges in 26 iterations. Iteration count grows very slowly with graph size.
**Why it might interest this community:**
1. It's a drop-in structural feature. One real per edge that encode 2-WL-level information. You can use them as edge features in any GNN.
2. It's parameter-free and deterministic. No training, no randomness, no tuning.
3. The higher-order variant (Δ\^k-DRESS) empirically distinguishes Strongly Regular Graphs that confound 3-WL, connecting to the Reconstruction Conjecture.
4. Support weighted graphs for encoding semantic information.
**Code & papers:**
The arXiv papers are outdated and will be updated next week. The latest versions including the proof in Paper 2, are in the GitHub repo.
* GitHub: [github.com/velicast/dress-graph https://github.com/velicast/dress-graph
* Paper 1 (framework): arXiv:2602.20833 https://github.com/velicast/dress-graph/blob/main/research/k-DRESS.pdf
* Paper 2 (WL hierarchy): arXiv:2602.21557 https://github.com/velicast/dress-graph/blob/main/research/vertex-k-DRESS.pdf
* Bindings: C, C++, Python (`pip install dress-graph`), Rust, Go, Julia, R, MATLAB, WASM
* Docs: velicast.github.io/dress-graph https://velicast.github.io/dress-graph/
Happy to answer questions. The core idea started during my master's thesis in 2018 as an edge scoring function for community detection, it turned out to be something more fundamental.
#technology
source
I've been working on a continuous framework for structural graph refinement called DRESS. It's a single nonlinear fixed-point equation on edges that converges to a unique, deterministic solution in \0, 2\], no hyperparameters, no training.
**What it does:** Given any graph's edge list, DRESS iteratively computes a self-consistent similarity value for every edge. Sorting these values produces a canonical graph fingerprint.
**Key results:**
* **Expressiveness:** Original DRESS (depth-0) matches **2-WL** in distinguishing power. Under the Reconstruction Conjecture, depth-k DRESS is at least as powerful as (k+2)-WL at O(C(n,k) · I · m · d\_max) cost vs. O(n\^{k+3}) for (k+2)-WL.
* **Isomorphism testing:** Tested on SRGs, CFI constructions, and the standard MiVIA and IsoBench benchmarks.
* **GED regression:** DRESS fingerprint differences fed to a simple regressor achieve **15× lower MSE** than TaGSim on LINUX graphs
* **Convergence:** On a 59M-vertex Facebook graph, it converges in 26 iterations. Iteration count grows very slowly with graph size.
**Why it might interest this community:**
1. It's a drop-in structural feature. One real per edge that encode 2-WL-level information. You can use them as edge features in any GNN.
2. It's parameter-free and deterministic. No training, no randomness, no tuning.
3. The higher-order variant (Δ\^k-DRESS) empirically distinguishes Strongly Regular Graphs that confound 3-WL, connecting to the Reconstruction Conjecture.
4. Support weighted graphs for encoding semantic information.
**Code & papers:**
The arXiv papers are outdated and will be updated next week. The latest versions including the proof in Paper 2, are in the GitHub repo.
* GitHub: [github.com/velicast/dress-graph https://github.com/velicast/dress-graph
* Paper 1 (framework): arXiv:2602.20833 https://github.com/velicast/dress-graph/blob/main/research/k-DRESS.pdf
* Paper 2 (WL hierarchy): arXiv:2602.21557 https://github.com/velicast/dress-graph/blob/main/research/vertex-k-DRESS.pdf
* Bindings: C, C++, Python (`pip install dress-graph`), Rust, Go, Julia, R, MATLAB, WASM
* Docs: velicast.github.io/dress-graph https://velicast.github.io/dress-graph/
Happy to answer questions. The core idea started during my master's thesis in 2018 as an edge scoring function for community detection, it turned out to be something more fundamental.
#technology
source
| 3,000 mlx | |
| 3 | |
| 0 |