dress-graph

PyPi Crates NPM CRAN

Deterministic graph fingerprinting. No training. No parameters. Just math.

DRESS assigns every edge in a graph a continuous structural similarity score via a convergent dynamical system. The sorted vector of scores is a canonical fingerprint: isomorphic graphs always get identical fingerprints.

pip install dress-graph

from dress import dress_fit

# Are these two graphs the same structure?
prism  = dress_fit(6, [0,1,2,0,1,2,3,4,5], [1,2,0,3,4,5,4,5,3])
k33    = dress_fit(6, [0,0,0,1,1,1,2,2,2], [3,4,5,3,4,5,3,4,5])

print("Prism:", sorted(prism.edge_dress))
print("K3,3: ", sorted(k33.edge_dress))
print("Distinguished:", sorted(prism.edge_dress) != sorted(k33.edge_dress))
# → True (DRESS separates them; 1-WL cannot)

Try it now:

Why DRESS?

Applications

• Graph Isomorphism: Δ¹-DRESS separates 100% of 51,816 hard benchmark graphs (576M+ pairs). Strictly exceeds 3-WL.
• Classification: DRESS fingerprints as features for standard classifiers, matching WL baselines on TU datasets.
• Community Detection: Edge values naturally classify intra- vs inter-community edges.
• Graph Retrieval: Fingerprint distances correlate with graph edit distance.
• GED Regression: 15× lower MSE than TaGSim on LINUX graphs, no GNN needed.
• Edge Robustness: O(km) edge-importance ranking beating betweenness centrality.
• DRESS + GNN: Plug-in features that boost GIN/PNA/GPS on ZINC-12K.

Δ^k-DRESS (higher-order refinement)

from dress import delta_dress_fit

result = delta_dress_fit(
    n_vertices=4,
    sources=[0, 1, 2, 0],
    targets=[1, 2, 3, 3],
    k=1,              # delete 1 vertex at a time
    epsilon=1e-6,
)
print(result.histogram)   # histogram of edge DRESS values across all subgraphs
print(result.hist_size)   # number of bins

Examples & experiments

End-to-end examples for every language and backend (CPU, CUDA, MPI, MPI+CUDA) live in examples/.

Reproducible benchmarks, datasets, and experiment scripts (isomorphism, classification, retrieval, GED regression, and more) live in the dedicated dress-experiments repository.

Interactive notebooks

Notebook	Description
	Quickstart: DRESS on the Karate Club graph
	Prism vs K₃,₃: separates graphs that 1-WL cannot
	Rook vs Shrikhande: Δ¹-DRESS beats 3-WL

Language bindings

C · C++ · Python · Rust · Go · Julia · R · MATLAB/Octave · JavaScript/WASM

All backends: CPU, CUDA, MPI, MPI+CUDA. Switch by changing the import.

See the full documentation → for complete API reference.

#include "dress/dress.h"            // CPU
#include "dress/cuda/dress.h"       // CUDA  (replaces CPU header)
#include "dress/mpi/dress.h"        // MPI   (replaces CPU header)
#include "dress/mpi/cuda/dress.h"   // MPI + CUDA (single include)

p_dress_graph_t g = init_dress_graph(N, E, U, V, W, DRESS_VARIANT_UNDIRECTED, 0);
int hs; int64_t ns;
int64_t *hist = delta_dress_fit(g, /*k=*/1, /*iter=*/100, /*eps=*/1e-6,
                                &hs, /*keep_multisets=*/0, NULL, &ns);
free_dress_graph(g);

#include "dress/dress.hpp"              // CPU           → ::DRESS
#include "dress/cuda/dress.hpp"         // CUDA          → cuda::DRESS
#include "dress/mpi/dress.hpp"          // MPI           → mpi::DRESS
#include "dress/mpi/cuda/dress.hpp"     // MPI + CUDA    → mpi::cuda::DRESS

DRESS g(N, U, V);                       // (or cuda::DRESS, mpi::DRESS, …)
auto r = g.deltaFit(/*k=*/1, /*maxIter=*/100, /*eps=*/1e-6);
// r.histogram, r.hist_size, r.num_subgraphs

from dress import delta_dress_fit            # CPU
from dress.cuda import delta_dress_fit       # CUDA
from dress.mpi import delta_dress_fit        # MPI
from dress.mpi.cuda import delta_dress_fit   # MPI + CUDA

result = delta_dress_fit(
    n_vertices=6, sources=[0,1,2,0,1,2,3,4,5],
    targets=[1,2,0,3,4,5,4,5,3], k=1,
)
print(result.histogram, result.hist_size)

use dress_graph::DRESS;                     // CPU
use dress_graph::cuda::DRESS;               // CUDA
use dress_graph::mpi;                       // MPI
use dress_graph::mpi::cuda;                 // MPI + CUDA

let r = DRESS::delta_fit(
    6, sources, targets, None,
    /*k=*/1, /*max_iter=*/100, /*eps=*/1e-6,
    Variant::Undirected, false, false, 0, 1,
)?;

import dress "github.com/velicast/dress-graph/go"            // CPU
import dress "github.com/velicast/dress-graph/go/cuda"        // CUDA
import dress "github.com/velicast/dress-graph/go/mpi"         // MPI
import dress "github.com/velicast/dress-graph/go/mpi/cuda"    // MPI + CUDA

r, err := dress.DeltaDressFit(6, sources, targets, nil,
    1, dress.Undirected, 100, 1e-6, false, false, 0, 1)

using DRESS                      # CPU
using DRESS.CUDA                 # CUDA
using DRESS; using DRESS.MPI     # MPI

r = delta_dress_fit(6, sources, targets; k=1)
# r.histogram, r.hist_size, r.num_subgraphs

library(dress.graph)

delta_dress_fit(6, sources, targets, k = 1L)         # CPU
cuda$delta_dress_fit(6, sources, targets, k = 1L)     # CUDA
mpi$delta_dress_fit(6, sources, targets, k = 1L)      # MPI
mpi$cuda$delta_dress_fit(6, sources, targets, k = 1L) # MPI + CUDA

result = delta_dress_fit(6, sources, targets, 'K', 1);
% result.histogram, result.hist_size, result.num_subgraphs

import { deltaDressFit } from './dress.js';

const r = await deltaDressFit({
    numVertices: 6, sources, targets, k: 1,
});
// r.histogram, r.histSize, r.numSubgraphs

Benchmarks

Convergence on real-world graphs (ε = 10⁻⁶):

Even on graphs with 59M vertices, DRESS converges in fewer than 31 iterations.

// Δ⁰ : edge fingerprint
p_dress_graph_t g = init_dress_graph(N, E, U, V, NULL, DRESS_VARIANT_UNDIRECTED, 0);
int iters; double delta;
dress_fit(g, 100, 1e-6, &iters, &delta);        // CPU
dress_fit_cuda(g, 100, 1e-6, &iters, &delta);   // CUDA

// Δ¹ : histogram fingerprint
int hs; int64_t ns;
int64_t *hist = delta_dress_fit(g, /*k=*/1, 100, 1e-6, &hs, 0, NULL, &ns);
int64_t *hist = delta_dress_fit_mpi(g, 1, 100, 1e-6, &hs, 0, NULL, &ns, MPI_COMM_WORLD);
int64_t *hist = delta_dress_fit_mpi_cuda(g, 1, 100, 1e-6, &hs, 0, NULL, &ns, MPI_COMM_WORLD);

free(hist);
free_dress_graph(g);

// igraph wrapper : same API names, transparent backend switching
#include <dress/igraph/dress.h>           // CPU
#include <dress/cuda/igraph/dress.h>      // CUDA
#include <dress/mpi/igraph/dress.h>       // MPI
#include <dress/mpi/cuda/igraph/dress.h>  // MPI + CUDA

dress_result_igraph_t r;
dress_fit(&graph, NULL, DRESS_VARIANT_UNDIRECTED,
          100, 1e-6, 1, &r);             // same call for all backends
dress_free(&r);

delta_dress_result_igraph_t dr;
delta_dress_fit(&graph, NULL, DRESS_VARIANT_UNDIRECTED,
                /*k=*/1, 100, 1e-6, 1, &dr);  // CPU / MPI / CUDA, per header
delta_dress_free(&dr);

DRESS g(N, sources, targets);              // or cuda::DRESS, mpi::DRESS, mpi::cuda::DRESS
auto r = g.fit(100, 1e-6);                 // → {iterations, delta}
auto d = g.deltaFit(/*k=*/1);             // → {histogram, hist_size, num_subgraphs}
double val = g.edgeDress(e);               // per-edge value after fit

# Δ⁰ : edge fingerprint
result = dress_fit(n_vertices, sources, targets)
result.edge_dress    # per-edge values
result.node_dress    # per-node norms
result.iterations    # convergence iterations

# Δ¹ : histogram fingerprint
result = delta_dress_fit(n_vertices, sources, targets, k=1)
result.histogram     # bin counts
result.hist_size     # number of bins

# NetworkX: pass a graph directly
import networkx as nx
from dress.networkx import dress_graph, delta_dress_graph

G = nx.karate_club_graph()
result = dress_graph(G, set_attributes=True)
G.edges[0, 1]["dress"]      # per-edge similarity

delta = delta_dress_graph(G, k=1, keep_multisets=True)
delta.histogram              # bin counts

# MPI NetworkX: same API, distributed
from dress.mpi.networkx import delta_dress_graph
delta = delta_dress_graph(G, k=1)  # uses MPI.COMM_WORLD

// Builder pattern (CPU / CUDA)
let result = DRESS::builder(n, sources, targets)
    .variant(Variant::Undirected)
    .build_and_fit()?;
// result.edge_dress, result.iterations, result.delta

// MPI delta fit
let r = mpi::delta_fit(n, sources, targets, None,
    /*k=*/1, 100, 1e-6, Variant::Undirected, false, false, &world)?;
// r.histogram, r.hist_size, r.num_subgraphs

// CPU / CUDA: same function, different import
result, _ := dress.DressFit(n, sources, targets, nil,
    dress.Undirected, 100, 1e-6, false)
// result.EdgeDress, result.Iterations, result.Delta

// MPI / MPI+CUDA: delta only
dress.Init()
defer dress.Finalize()
r, _ := dress.DeltaDressFit(n, sources, targets, nil,
    /*k=*/1, dress.Undirected, 100, 1e-6, false, false)
// r.Histogram, r.HistSize, r.NumSubgraphs

# Δ⁰ : edge fingerprint
r = dress_fit(N, sources, targets)
# r.edge_dress, r.node_dress, r.iterations, r.delta

# Δ¹ : histogram fingerprint
r = delta_dress_fit(N, sources, targets; k=1)
# r.histogram, r.hist_size, r.num_subgraphs

library(dress.graph)

# Δ⁰ : edge fingerprint
r <- dress_fit(6L, sources, targets)
# r$edge_dress, r$node_dress, r$iterations, r$delta

# Δ¹ : histogram fingerprint
r <- delta_dress_fit(6L, sources, targets, k = 1L)       # CPU
r <- cuda$delta_dress_fit(6L, sources, targets, k = 1L)   # CUDA
r <- mpi$delta_dress_fit(6L, sources, targets, k = 1L)    # MPI
r <- mpi$cuda$delta_dress_fit(6L, sources, targets, k = 1L) # MPI+CUDA

% Δ⁰ : edge fingerprint
result = dress_fit(6, int32(sources), int32(targets));
% result.edge_dress, result.node_dress, result.iterations, result.delta

% Δ¹ : histogram fingerprint
result = delta_dress_fit(6, int32(sources), int32(targets), ...
    'K', 1, 'KeepMultisets', true);
% result.histogram, result.hist_size, result.multisets, result.num_subgraphs

% Persistent graph with get()
g = DRESS(6, int32(sources), int32(targets));
g.fit('MaxIterations', 100, 'Epsilon', 1e-6);
d = g.get(u, v);     % query edge similarity
g.close();

// Δ⁰ : edge fingerprint
const result = await dressFit({
    numVertices: 6, sources, targets,
});
// result.edgeDress, result.nodeDress, result.iterations, result.delta

// Δ¹ : histogram fingerprint
const r = await deltaDressFit({
    numVertices: 6, sources, targets,
    k: 1, keepMultisets: true,
});
// r.histogram, r.histSize, r.multisets, r.numSubgraphs

// Persistent graph with get()
const g = await DRESS.create({ numVertices: 6, sources, targets });
g.fit(100, 1e-6);
const d = g.get(u, v);   // query edge similarity
g.free();

Building from source

./build.sh --no-test

# Python
cd python && pip install .

Documentation

Full documentation (theory, applications, API reference):
https://velicast.github.io/dress-graph/

For the theory and generalizations (DRESS Family), see the research paper:
arXiv:2602.20833

Publications

• E. Castrillo. DRESS: A Continuous Framework for Structural Graph Refinement. arXiv:2602.20833
• E. Castrillo. DRESS and the WL Hierarchy: Climbing One Deletion at a Time. arXiv:2602.21557
• E. Castrillo. Breaking Hard Isomorphism Benchmarks with DRESS. arXiv:2603.18582
• E. Castrillo, E. León, J. Gómez. Dynamic Structural Similarity on Graphs. arXiv:1805.01419
• E. Castrillo, E. León, J. Gómez. Fast Heuristic Algorithm for Multi-Scale Hierarchical Community Detection. ASONAM 2017
• E. Castrillo, E. León, J. Gómez. High-Quality Disjoint and Overlapping Community Structure in Large-Scale Complex Networks. arXiv:1805.12238

Original implementation (2018): github.com/velicast/WMW

Citing

If you use DRESS in your research, please cite:

@misc{castrillo2026dress,
  title   = {DRESS: A Continuous Framework for Structural Graph Refinement},
  author  = {Eduar Castrillo Velilla},
  year    = {2026},
  eprint  = {2602.20833},
  archivePrefix = {arXiv},
  primaryClass  = {cs.DS},
  url     = {https://arxiv.org/abs/2602.20833}
}

@misc{castrillo2018dress,
  title   = {Dynamic Structural Similarity on Graphs},
  author  = {Eduar Castrillo and Elizabeth Le{\'o}n and Jonatan G{\'o}mez},
  year    = {2018},
  eprint  = {1805.01419},
  archivePrefix = {arXiv},
  primaryClass  = {cs.SI},
  url     = {https://arxiv.org/abs/1805.01419}
}

Why "DRESS"? DRESS computes an edge labeling that reveals the graph's hidden
structural identity; it dresses the bare skeleton (adjacency) with
meaningful values. A graph without DRESS is "naked" topology; after DRESS,
every edge wears the structural role that fits it best. And dress_fit()
is literally fitting the dress to the graph: few iterations give a loose fit,
more iterations tighten it, and at steady state the fit is true to size.

License

MIT