| Title: | DRESS - A Continuous Framework for Structural Graph Refinement |
|---|---|
| Description: | DRESS is a deterministic, parameter-free framework for continuous structural graph refinement. It iterates a nonlinear dynamical system on real-valued edge similarities and produces a graph fingerprint as a sorted edge-value vector once the iteration reaches a prescribed stopping criterion. The resulting fingerprint is self-contained, isomorphism-invariant by construction, reproducible across vertex labelings under the reference implementation, numerically robust in practice, and efficient to compute with straightforward parallelization and distribution. |
| Authors: | Eduar Castrillo Velilla [aut, cre] (ORCID: <https://orcid.org/0009-0005-2492-0957>) |
| Maintainer: | Eduar Castrillo Velilla <[email protected]> |
| License: | MIT + file LICENSE |
| Version: | 0.8.3 |
| Built: | 2026-05-26 10:39:19 UTC |
| Source: | https://github.com/cranhaven/cranhaven.r-universe.dev |
An environment containing GPU-accelerated versions of fit,
delta_fit, and nabla_fit with identical signatures. Switch from
CPU to GPU by prefixing calls with cuda$.
The cuda environment provides:
cuda$fit(...)GPU-accelerated fit.
Same arguments and return value.
cuda$delta_fit(...)GPU-accelerated
delta_fit. Same arguments and return value.
cuda$nabla_fit(...)GPU-accelerated
nabla_fit. Same arguments and return value.
CUDA support requires rebuilding the package with DRESS_CUDA=1.
If CUDA is not available, calling either function raises an error.
## Not run: # CPU r1 <- fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) # CUDA -- same signature r2 <- cuda$fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) ## End(Not run)## Not run: # CPU r1 <- fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) # CUDA -- same signature r2 <- cuda$fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) ## End(Not run)
Compute the -DRESS histogram by exhaustively removing
all k-vertex subsets and measuring the change in edge similarity values.
The result is a sparse exact histogram of edge DRESS values pooled across all
subgraphs.
delta_fit(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, k = 0L, variant = DRESS_UNDIRECTED, max_iterations = 100L, epsilon = 1e-6, n_samples = 0L, seed = 0L, precompute = FALSE, keep_multisets = FALSE, compute_histogram = TRUE)delta_fit(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, k = 0L, variant = DRESS_UNDIRECTED, max_iterations = 100L, epsilon = 1e-6, n_samples = 0L, seed = 0L, precompute = FALSE, keep_multisets = FALSE, compute_histogram = TRUE)
n_vertices |
Integer. Number of vertices (vertex ids must be in
|
sources |
Integer vector of length E – edge source endpoints (0-based). |
targets |
Integer vector of length E – edge target endpoints (0-based). |
weights |
Numeric vector of length E – edge weights, or |
vertex_weights |
Numeric vector of length N – vertex weights, or |
k |
Integer. Number of vertices to remove per subset (0 = original graph, default 0). |
variant |
Graph variant (default |
max_iterations |
Maximum number of fitting iterations per subgraph (default 100). |
epsilon |
Convergence threshold (default 1e-6). |
n_samples |
Integer. Number of random subgraphs to sample (0 = exhaustive enumeration, default 0). |
seed |
Integer. Random seed for sampling (default 0). |
precompute |
Logical. Pre-compute common-neighbor intercept index
for faster iteration at the cost of more memory (default |
keep_multisets |
Logical. If |
compute_histogram |
Logical. If |
A list with components:
histogram |
Data frame with columns |
multisets |
Matrix (C(N,k) x E) of per-subgraph edge DRESS values
(only present when |
num_subgraphs |
Integer – C(N,k) (only present when
|
fit for the standard DRESS computation.
# Triangle K3, delta-1: remove 1 vertex at a time res <- delta_fit(3L, c(0L, 1L, 2L), c(1L, 2L, 0L), k = 1L) res$histogram # K4, delta-0 (original graph) res0 <- delta_fit(4L, c(0L,0L,0L,1L,1L,2L), c(1L,2L,3L,2L,3L,3L)) sum(res0$histogram$count) # 6 edge values# Triangle K3, delta-1: remove 1 vertex at a time res <- delta_fit(3L, c(0L, 1L, 2L), c(1L, 2L, 0L), k = 1L) res$histogram # K4, delta-0 (original graph) res0 <- delta_fit(4L, c(0L,0L,0L,1L,1L,2L), c(1L,2L,3L,2L,3L,3L)) sum(res0$histogram$count) # 6 edge values
Create a persistent DRESS graph that stays alive across multiple
fit / get (virtual-edge query) calls without
rebuilding the graph each time.
DRESS(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, variant = DRESS_UNDIRECTED, precompute_intercepts = FALSE)DRESS(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, variant = DRESS_UNDIRECTED, precompute_intercepts = FALSE)
n_vertices |
Integer. Number of vertices (vertex ids must be in
|
sources |
Integer vector of length E – edge source endpoints (0-based). |
targets |
Integer vector of length E – edge target endpoints (0-based). |
weights |
Optional numeric vector of length E – per-edge weights.
|
vertex_weights |
Optional numeric vector of length N – per-vertex weights.
|
variant |
Graph variant (default |
precompute_intercepts |
Logical. Pre-compute common-neighbor index
for faster iteration at the cost of more memory (default |
An environment of class "DRESS" with the following methods:
$fit(max_iterations = 100L, epsilon = 1e-6)
|
Run iterative
fitting. Returns a list with |
$get(u, v, max_iterations = 100L, epsilon = 1e-6, edge_weight = 1.0)
|
Query the DRESS value for an existing or
virtual edge between vertices |
$result() |
Extract current results as a list with
|
$close() |
Explicitly free the underlying C graph. Called automatically by the garbage collector if not invoked manually. |
E. Castrillo, E. Leon, J. Gomez. Dynamic Structural Similarity on Graphs. arXiv:1805.01419, 2018.
g <- DRESS(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) g$fit(100L, 1e-6) g$get(0L, 3L, 100L, 1e-6, 1.0) r <- g$result() g$close()g <- DRESS(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) g$fit(100L, 1e-6) g$get(0L, 3L, 100L, 1e-6, 1.0) r <- g$result() g$close()
Return the version string of the underlying DRESS C library.
dress_version()dress_version()
A character scalar, e.g. "0.7.0".
dress_version()dress_version()
Build a DRESS graph from an edge list and run iterative fitting to compute per-edge structural similarity values.
fit(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, variant = DRESS_UNDIRECTED, max_iterations = 100L, epsilon = 1e-6, precompute_intercepts = FALSE) DRESS_UNDIRECTED DRESS_DIRECTED DRESS_FORWARD DRESS_BACKWARDfit(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, variant = DRESS_UNDIRECTED, max_iterations = 100L, epsilon = 1e-6, precompute_intercepts = FALSE) DRESS_UNDIRECTED DRESS_DIRECTED DRESS_FORWARD DRESS_BACKWARD
n_vertices |
Integer. Number of vertices (vertex ids must be in
|
sources |
Integer vector of length E – edge source endpoints (0-based). |
targets |
Integer vector of length E – edge target endpoints (0-based). |
weights |
Optional numeric vector of length E – per-edge weights.
|
vertex_weights |
Optional numeric vector of length N – per-vertex weights.
|
variant |
Graph variant (default |
max_iterations |
Maximum number of fitting iterations (default 100). |
epsilon |
Convergence threshold – stop when the max per-edge change falls below this value (default 1e-6). |
precompute_intercepts |
Logical. Pre-compute common-neighbor index
for faster iteration at the cost of more memory (default |
A list with components:
sources |
Integer vector [E] – edge source endpoints (0-based). |
targets |
Integer vector [E] – edge target endpoints (0-based). |
edge_dress |
Numeric vector [E] – DRESS similarity per edge. |
edge_weight |
Numeric vector [E] – variant-specific weight. |
vertex_dress |
Numeric vector [N] – per-vertex norm. |
iterations |
Integer – number of iterations performed. |
delta |
Numeric – final max per-edge change. |
vertex_weights |
Numeric vector [N] – vertex weights (if provided). |
E. Castrillo, E. Leon, J. Gomez. Dynamic Structural Similarity on Graphs. arXiv:1805.01419, 2018.
# Triangle + pendant: 0-1, 1-2, 2-0, 2-3 res <- fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) res$edge_dress# Triangle + pendant: 0-1, 1-2, 2-0, 2-3 res <- fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) res$edge_dress
An environment containing MPI-distributed versions of
delta_fit and nabla_fit. Switch from CPU to MPI by prefixing calls
with mpi$.
The mpi environment provides:
mpi$delta_fit(...)MPI-distributed
delta_fit (CPU backend).
Same arguments plus comm_f.
mpi$nabla_fit(...)MPI-distributed
nabla_fit (CPU backend).
Same arguments plus comm_f.
mpi$cuda$delta_fit(...)MPI-distributed
delta_fit (CUDA backend).
Each rank runs GPU-accelerated DRESS.
mpi$cuda$nabla_fit(...)MPI-distributed
nabla_fit (CUDA backend).
mpi$omp$delta_fit(...)MPI-distributed
delta_fit (OpenMP backend).
mpi$omp$nabla_fit(...)MPI-distributed
nabla_fit (OpenMP backend).
MPI support requires rebuilding the package with DRESS_MPI
(auto-detected when mpicc is available).
## Not run: # CPU r1 <- delta_fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L), k = 1L) # MPI -- same signature, distributed r2 <- mpi$delta_fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L), k = 1L) # MPI + CUDA r3 <- mpi$cuda$delta_fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L), k = 1L) ## End(Not run)## Not run: # CPU r1 <- delta_fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L), k = 1L) # MPI -- same signature, distributed r2 <- mpi$delta_fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L), k = 1L) # MPI + CUDA r3 <- mpi$cuda$delta_fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L), k = 1L) ## End(Not run)
Compute the -DRESS histogram by enumerating all
ordered k-tuples of vertices, marking each tuple with
distinct generic vertex weights, running DRESS on each marked graph, and
pooling all converged edge values into a sparse exact histogram.
nabla_fit(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, k = 0L, variant = DRESS_UNDIRECTED, max_iterations = 100L, epsilon = 1e-6, n_samples = 0L, seed = 0L, precompute = FALSE, keep_multisets = FALSE, compute_histogram = TRUE)nabla_fit(n_vertices, sources, targets, weights = NULL, vertex_weights = NULL, k = 0L, variant = DRESS_UNDIRECTED, max_iterations = 100L, epsilon = 1e-6, n_samples = 0L, seed = 0L, precompute = FALSE, keep_multisets = FALSE, compute_histogram = TRUE)
n_vertices |
Integer. Number of vertices (vertex ids must be in
|
sources |
Integer vector of length E – edge source endpoints (0-based). |
targets |
Integer vector of length E – edge target endpoints (0-based). |
weights |
Numeric vector of length E – edge weights, or |
vertex_weights |
Numeric vector of length N – vertex weights, or |
k |
Integer. Number of vertices to individualize per tuple (0 = original graph, default 0). |
variant |
Graph variant (default |
max_iterations |
Maximum number of fitting iterations per marked graph (default 100). |
epsilon |
Convergence threshold (default 1e-6). |
n_samples |
Integer. Number of random tuples to sample (0 = exhaustive enumeration, default 0). |
seed |
Integer. Random seed for sampling (default 0). |
precompute |
Logical. Pre-compute common-neighbor intercept index
for faster iteration at the cost of more memory (default |
keep_multisets |
Logical. If |
compute_histogram |
Logical. If |
A list with components:
histogram |
Data frame with columns |
multisets |
Matrix (P(N,k) x E) of per-tuple edge DRESS values
(only present when |
num_tuples |
Integer – P(N,k) (only present when
|
fit for the standard DRESS computation.
delta_fit for the vertex-deletion variant.
# Triangle K3, nabla-1: individualize 1 vertex at a time res <- nabla_fit(3L, c(0L, 1L, 2L), c(1L, 2L, 0L), k = 1L) res$histogram # K4, nabla-0 (original graph, no individualization) res0 <- nabla_fit(4L, c(0L,0L,0L,1L,1L,2L), c(1L,2L,3L,2L,3L,3L)) sum(res0$histogram$count) # 6 edge values# Triangle K3, nabla-1: individualize 1 vertex at a time res <- nabla_fit(3L, c(0L, 1L, 2L), c(1L, 2L, 0L), k = 1L) res$histogram # K4, nabla-0 (original graph, no individualization) res0 <- nabla_fit(4L, c(0L,0L,0L,1L,1L,2L), c(1L,2L,3L,2L,3L,3L)) sum(res0$histogram$count) # 6 edge values
An environment providing OpenMP-parallel versions of DRESS functions.
Use omp$fit(...), omp$delta_fit(...), and omp$nabla_fit(...) for
OpenMP edge-parallel fitting, subgraph-parallel delta fitting, and
tuple-parallel nabla fitting.
Same parameters as fit, delta_fit, and nabla_fit.
ompomp
## Not run: r <- omp$fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) d <- omp$delta_fit(3L, c(0L,1L,0L), c(1L,2L,2L), k = 1L) n <- omp$nabla_fit(3L, c(0L,1L,0L), c(1L,2L,2L), k = 1L) ## End(Not run)## Not run: r <- omp$fit(4L, c(0L,1L,2L,2L), c(1L,2L,0L,3L)) d <- omp$delta_fit(3L, c(0L,1L,0L), c(1L,2L,2L), k = 1L) n <- omp$nabla_fit(3L, c(0L,1L,0L), c(1L,2L,2L), k = 1L) ## End(Not run)