create.single.iknn.graph: Create a Single Intersection-weighted k-Nearest Neighbors...

In dgraphs: Data-Derived Graph Construction Utilities

Create a Single Intersection-weighted k-Nearest Neighbors Graph

Description

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. The number of nearest neighbors to consider for each point. 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 scalar controlling additional full-payload outputs. If TRUE, keeps legacy original-graph components isize_list and conn_comps. Lifecycle graph payloads are always returned: raw_adj_list/raw_weight_list, pruned_adj_list/pruned_weight_list, and final adj_list/weight_list.
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.

Details

adj_list and weight_list always contain the final graph used by downstream algorithms. ⁠raw_*⁠ fields contain the native graph before pruning, and ⁠pruned_*⁠ fields contain the graph after pruning but before optional MST component repair. If pruning is disabled, ⁠pruned_*⁠ is identical to ⁠raw_*⁠. The repaired lifecycle branches allow direct comparison of raw, prune-first, and repair-first graph geodesic distances from a single constructor call.

Value

An object of class "IkNN" (inheriting from "list") containing:

adj_list

Adjacency lists for the final graph after optional MST repair

weight_list

Edge weights for the final graph

raw_adj_list

Adjacency lists for the native graph before pruning

raw_weight_list

Edge weights for the native graph before pruning

pruned_adj_list

Adjacency lists after pruning and before MST repair

pruned_weight_list

Edge weights after pruning and before MST repair

raw_repaired_adj_list, raw_repaired_weight_list

The native graph after MST component repair.

pruned_repaired_adj_list, pruned_repaired_weight_list

The prune-first branch after MST component repair.

repaired_pruned_adj_list, repaired_pruned_weight_list

The repair-first branch after applying the selected pruning method to the repaired raw graph.

n_edges

Total number of edges in original graph

n_edges_in_pruned_graph

Number of edges after pruning

n_removed_edges

Number of edges removed by pruning

edge_reduction_ratio

Proportion of edges removed

call

The matched function call

k

Number of nearest neighbors used

n

Number of data points

d

Number of features

If compute.full = TRUE, additional components include:

isize_list

Intersection sizes for original edges

conn_comps

Connected components identification

connected_components

Alternative format of connected components

Examples

# Create sample data
set.seed(123)
X <- matrix(rnorm(100), ncol = 2)
result <- create.single.iknn.graph(X, k = 3)
summary(result)

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