Compute a Continuous-kNN Graph

Creates an undirected continuous-kNN graph using local scale distances. Let \(\sigma_i\) be the distance from observation \(i\) to its k.scale-th non-self nearest neighbor. Vertices are adjacent when $$\|x_i - x_j\|_2 \le \delta \sqrt{\sigma_i\sigma_j}.$$

This is a convenience wrapper around create.rknn.graph() with type = "adaptive.radius" and radius.rule = "geomean". It is useful as a named data-derived graph construction in geodesic reconstruction benchmarks.

Usage

create.cknn.graph(
  X,
  k.scale,
  delta = 1,
  radius.search = c("ann", "all.pairs"),
  return.timing = FALSE,
  graph.detail = c("full", "minimal"),
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

X

Numeric matrix or data frame with observations in rows.

k.scale

Positive integer smaller than nrow(X). Defines local scale distances \(\sigma_i\).

delta

Positive numeric scalar multiplying the geometric-mean adaptive radius.

radius.search

Character scalar. "ann" uses the bundled ANN kd-tree exact radius-search backend inherited from create.rknn.graph(). "all.pairs" uses the direct \(O(n^2)\) reference path.

return.timing

Logical scalar. If TRUE, attach the same construction timing table returned by create.rknn.graph(), including ANN setup, local-scale search, fixed-radius candidate search, edge materialization, and graph finalization when radius.search = "ann".

graph.detail

Character scalar. "full" returns the complete graph lifecycle object. "minimal" returns only core graph fields and is allowed only with prune.method = "none" and connect.components = FALSE.

prune.method

Character scalar. "none" disables geometric pruning. "local.geodesic" applies the experimental local geometric pruning stage before optional MST connectivity repair. "global.geodesic.ratio" applies whole-graph geodesic-ratio pruning before optional MST connectivity repair.

max.path.edge.ratio.deviation.thld

Numeric scalar in [0, 0.2). For prune.method = "global.geodesic.ratio", an edge may be removed when the shortest alternative path is at most 1 + max.path.edge.ratio.deviation.thld times the direct edge length.

path.edge.ratio.percentile

Numeric scalar in [0, 1]. For prune.method = "global.geodesic.ratio", only edges at or above this edge length percentile are considered.

prune.tau

Numeric scalar greater than 1. For local geometric pruning, an edge may be removed when a retained local alternative path is at most this multiplicative factor times the direct edge length.

prune.local.k

Integer scalar or NULL. Number of nearest neighbors used to form local neighborhoods for pruning. For fixed-radius graphs, NULL uses the median positive raw graph degree, clipped to [1, n - 1]. For adaptive-radius graphs, NULL defaults to k.scale.

with.pruned.edge.stats

Logical scalar. If TRUE, return a data frame with one row per locally pruned edge.

connect.components

Logical scalar. If TRUE, add MST bridge edges so the final graph is connected whenever possible.

connect.method

Character scalar. "component.mst" adds exact shortest inter-component bridges. "component.mst.ann" tries sparse ANN bridge candidates before automatic exact fallback. "global.mst" unions the graph with the full Euclidean MST.

bridge.k

Integer scalar or NULL. Initial ANN bridge neighborhood size for connect.method = "component.mst.ann".

bridge.k.max

Integer scalar or NULL. Maximum ANN bridge neighborhood size before exact fallback.

bridge.growth

Numeric scalar greater than 1. Multiplicative growth factor for ANN bridge neighborhoods.

Value

A list inheriting from "cknn_graph" and "adaptive_radius_graph". It contains the same lifecycle fields as create.rknn.graph() with type = "adaptive.radius", radius_rule = "geomean", radius_factor = delta, and graph_rule = "continuous.knn".

Examples

X <- matrix(c(0, 1, 3), ncol = 1)
as.matrix(graph.edges(create.cknn.graph(X, k.scale = 1, delta = 1))[, c("from", "to")])
#>      from to
#> [1,]    1  2