Create a Single Intersection-weighted k-Nearest Neighbors Graph

Creates and prunes an intersection-weighted k-nearest neighbors (IWD-kNN) graph from input data. The graph is constructed based on feature space distances and intersection sizes between neighbor sets.

Usage

create.single.iknn.graph(
  X,
  k,
  max.path.edge.ratio.deviation.thld = 0.1,
  prune.method = c("global.geodesic", "none", "local.geodesic", "global.geodesic.ratio"),
  prune.tau = NULL,
  prune.local.k = NULL,
  path.edge.ratio.percentile = 0.5,
  threshold.percentile = 0,
  compute.full = FALSE,
  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),
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2,
  with.lifecycle.branches = FALSE,
  verbose = TRUE,
  knn.cache.path = NULL,
  knn.cache.mode = c("none", "read", "write", "readwrite")
)

Arguments

X

A numeric matrix where rows represent data points and columns represent features. Data frames will be coerced to matrices.

k

Integer scalar. Number of nearest other vertices. Self is explicitly added to each cover, and distance ties use ascending vertex index. Must be positive and less than the number of data points.

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\). Used when prune.method is "global.geodesic" or "global.geodesic.ratio".

prune.method

Character scalar. "global.geodesic" preserves the historical whole-graph geometric pruning behavior controlled by max.path.edge.ratio.deviation.thld and path.edge.ratio.percentile. "global.geodesic.ratio" is a separately named alias for that whole-graph geodesic-ratio behavior. "local.geodesic" applies the same experimental local geometric pruning stage used by sKNN/mKNN. "none" disables geometric pruning; quantile pruning controlled by threshold.percentile is still honored.

prune.tau

Numeric scalar greater than 1, or NULL. Multiplicative threshold for local geometric pruning. If NULL, defaults to max(1 + max.path.edge.ratio.deviation.thld, 1.05).

prune.local.k

Integer scalar or NULL. Number of nearest neighbors used to form local neighborhoods for local geometric pruning. Defaults to k.

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. Retain additional native component diagnostics. Graph stages are always retained; available overlap values are stored as named edge attributes.

with.isize.pruning

Logical scalar. If TRUE, compute intersection-size pruning outputs and related statistics. Default is FALSE.

with.edge.pruning.stats

Logical scalar. If TRUE, compute edge-level pruning statistics. Default is FALSE.

pca.dim

Maximum number of principal components to use if dimensionality reduction is applied (default: 100). Set to NULL to skip dimensionality reduction.

variance.explained

Percentage of variance to be explained by the principal components (default: 0.99). If this threshold can be met with fewer components than pca.dim, the smaller number will be used. Set to NULL to use exactly pca.dim components.

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.

connect.components

Logical scalar. If TRUE, add MST bridge edges to the final pruned graph so it is connected whenever possible. Currently supported only with knn.metric = "euclidean".

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.

with.lifecycle.branches

Logical scalar. If TRUE, compute the additional repaired lifecycle branches raw_repaired_*, pruned_repaired_*, and repaired_pruned_*. This is useful for graph-geodesic reconstruction experiments but can be expensive for the historical global iKNN pruning path, so the default is FALSE.

verbose

Logical. If TRUE, print progress messages. Default is TRUE.

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.

Value

A dgraph object. Use graph.adjacency(), graph.lengths(), graph.edges() and graph.stages() to inspect its stored graph stages. Construction and diagnostic information is stored in metadata.

Details

The default accessors inspect the final graph. Use stage = "raw" or stage = "pruned" to inspect earlier stages. graph.stages() reports which repaired branches are retained; a missing stage is an error.

Examples

# Create sample data
set.seed(123)
X <- matrix(rnorm(100), ncol = 2)
result <- create.single.iknn.graph(X, k = 3)
#> compute.full=FALSE: optional component diagnostics may be omitted; graph stages are retained.
#> Running single-threaded.
#> [compute_knn] running...
[compute_knn] 0.000s
#> [graph_build (inverted index)] running...
[graph_build (inverted index)] 0.000s
#> [geometric_prune] running...[geometric_prune] evaluating candidates: 0.0% (0/77), removed 0, ETA --:--
[geometric_prune] evaluating candidates: 100.0% (77/77), removed 77, ETA 00:00
[geometric_prune] done: 100.0% (77/77), removed 77, elapsed 0.0s
#> 
[geometric_prune] 0.000s
#> [isize_prune] skipped (with.isize.pruning=FALSE)
#> [edge_pruning_stats] skipped (with.edge.pruning.stats=FALSE)
#> Total elapsed time (0.000)
summary(result)
#> Graph Summary:
#> Number of vertices: 50 
#> Number of edges: 103 
#> Number of edges after pruning: 77 
#> Number of edges in final graph: 103 
#> Number of removed edges: 77 
#> Proportion of edges removed: 0.4277778