create.iknn.graphs: Create intersection k-nearest neighbor graphs with dual...

In dgraphs: Data-Derived Graph Construction Utilities

Create intersection k-nearest neighbor graphs with dual pruning

Description

For each k \in [k_{\mathrm{min}},\,k_{\mathrm{max}}], builds an intersection-weighted k-NN graph and applies two pruning schemes: (1) geometric (path-to-edge ratio) and (2) intersection-size. Optionally performs PCA before graph construction.

Usage

create.iknn.graphs(
  X,
  kmin,
  kmax,
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  threshold.percentile = 0,
  compute.full = TRUE,
  with.isize.pruning = FALSE,
  with.edge.pruning.stats = FALSE,
  pca.dim = 100,
  variance.explained = 0.99,
  knn.metric = c("euclidean", "linf.simplex"),
  linf.tol = sqrt(.Machine$double.eps),
  n.cores = 1L,
  parallel.mode = c("auto", "k", "bucket", "hybrid", "bucket.prune"),
  hybrid.batch.size = 2L,
  verbose = TRUE,
  knn.cache.path = NULL,
  knn.cache.mode = c("none", "read", "write", "readwrite")
)

Arguments

X	A numeric matrix (or object coercible to a numeric matrix) with rows = observations and columns = features.
kmin	Integer \ge 1, the minimum k.
kmax	Integer > k_{\mathrm{min}}, the maximum k.
max.path.edge.ratio.deviation.thld	Numeric in [0, 0.2). Geometric pruning removes an edge (i,j) when there exists an alternative path between i and j whose path/edge length ratio minus 1.0 is less than this threshold. This is a deviation threshold \delta in [0, 0.2). Internally we compare the path-to-edge ratio R to 1 + \delta.
path.edge.ratio.percentile	Numeric in [0,1]. Only edges with length above this percentile are considered for geometric pruning.
threshold.percentile	Numeric in [0, 0.5]. Percentile threshold for quantile-based edge length pruning. Default is 0 (no quantile pruning). When greater than 0, edges in the top (1 - threshold.percentile) quantile by length are removed if their removal preserves graph connectivity. For example, threshold.percentile = 0.9 removes edges in the top 10\ This pruning is applied after geometric pruning and targets unusually long edges based on absolute edge lengths rather than path-to-edge ratios.
compute.full	Logical controlling graph-list outputs. If TRUE, return geom_pruned_graphs (and isize_pruned_graphs when with.isize.pruning = TRUE). If FALSE, both graph lists are NULL and only summary outputs are returned (k_statistics, plus edge_pruning_stats when requested).
with.isize.pruning	Logical. If TRUE, compute and return intersection-size pruned graphs/statistics. Default is FALSE.
with.edge.pruning.stats	Logical. If TRUE, compute and return edge-level pruning statistics. Default is FALSE.
pca.dim	Positive integer or NULL. If not NULL and ncol(X) > pca.dim, PCA is used to reduce to at most pca.dim components.
variance.explained	Numeric in (0,1] or NULL. If not NULL, choose the smallest number of PCs whose cumulative variance explained exceeds this threshold, capped by pca.dim.
knn.metric	Character scalar specifying the geometry used for kNN search. "euclidean" uses ordinary ambient Euclidean distance. "linf.simplex" uses the unfolded intrinsic metric on the L^\infty-simplex and requires rows of X to be L^\infty-normalized.
linf.tol	Positive numeric tolerance used only when knn.metric = "linf.simplex" to identify active simplex faces and validate that max(row) = 1.
n.cores	Integer or NULL. Number of CPU cores. NULL uses the maximum available (OpenMP build only).
parallel.mode	Character execution mode for graph construction: "auto", "k", "bucket", "hybrid" (or alias "bucket.prune"). "hybrid" performs bucket-parallel graph build and then k-parallel pruning in batches.
hybrid.batch.size	Positive integer batch size used when parallel.mode = "hybrid".
verbose	Logical; print progress and timing.
knn.cache.path	Optional character scalar path to a binary kNN cache file. Used only when knn.cache.mode != "none".
knn.cache.mode	Character cache mode: "none": always compute kNN; do not read/write cache. "read": read kNN from cache only; if cache is missing/invalid, error. "write": always compute kNN and atomically write/overwrite cache. "readwrite": read valid cache when available; if cache file is missing, compute and write cache; if cache exists but is invalid, error.

Details

Geometric pruning uses the deviation threshold max.path.edge.ratio.deviation.thld and the filtering percentile path.edge.ratio.percentile. Intersection-size pruning currently uses a maximum alternative path length of 2.

Output behavior by flags:

• compute.full = FALSE: both geom_pruned_graphs and isize_pruned_graphs are NULL.

• compute.full = TRUE and with.isize.pruning = FALSE: geom_pruned_graphs is returned and isize_pruned_graphs is NULL.

Value

A list of class "iknn_graphs" with entries:

k_statistics

Matrix of per-k edge counts and reductions. (If the C++ side supplies column names, they’re preserved. Otherwise we add names consistent with what the C++ returns.)

geom_pruned_graphs

If compute.full=TRUE, list of geometrically pruned graphs (adjacency + weights); otherwise NULL.

isize_pruned_graphs

If compute.full=TRUE and with.isize.pruning=TRUE, list of intersection-size pruned graphs; otherwise NULL.

edge_pruning_stats

If with.edge.pruning.stats=TRUE, list (per k) of edge-level statistics; otherwise NULL.

Examples

# Generate sample data
X <- matrix(rnorm(100 * 5), 100, 5)

# Basic usage
res1 <- create.iknn.graphs(
  X, kmin = 3, kmax = 10, n.cores = 1,
  compute.full = FALSE
)

# With custom pruning parameters
res2 <- create.iknn.graphs(
  X, kmin = 3, kmax = 10,
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  compute.full = TRUE,
  n.cores = 1,
  verbose = TRUE
)

# View statistics for each k
print(res2$k_statistics)

dgraphs documentation built on Aug. 21, 2026, 1:08 a.m.