Create intersection k-nearest neighbor graphs with dual pruning

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,
  k.values,
  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),
  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.

k.values

Strictly increasing integer vector of neighborhood sizes, each between 1 and n - 1.

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.

Native graph construction is serial.

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.

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.

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.

Examples

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

# Basic usage
res1 <- create.iknn.graphs(X, k.values = seq.int(3, 10), compute.full = FALSE)
#> compute.full=FALSE: geom_pruned_graphs and isize_pruned_graphs will be NULL; returning k_statistics (and edge_pruning_stats if requested).
#> 	Running single-threaded.
#> Processing k values from 3 to 10 for 100 vertices
#> Requested parallel.mode: auto
#> Parallel mode: serial
#> Starting graph processing
#> [compute_knn] running...
[compute_knn] 0.000s
#> [graph_build/geometric_prune/isize_prune] running...
[graph_build/geometric_prune/isize_prune] 0.103s
#> Graph processing completed (0.103)
#> [compute_knn] 0.000s
#> [graph_build] 0.003s
#> [geometric_prune] 0.101s
#> [isize_prune] skipped (with.isize.pruning=FALSE)
#> Creating return list objects ... DONE (0.000)
#> Total elapsed time (0.103)

# With custom pruning parameters
res2 <- create.iknn.graphs(X, k.values = seq.int(3, 10),
    max.path.edge.ratio.deviation.thld = 0.1,
    path.edge.ratio.percentile = 0.5, compute.full = TRUE, verbose = TRUE)
#> with.isize.pruning=FALSE: isize_pruned_graphs will be NULL.
#> 	Running single-threaded.
#> Processing k values from 3 to 10 for 100 vertices
#> Requested parallel.mode: auto
#> Parallel mode: serial
#> Starting graph processing
#> [compute_knn] running...
[compute_knn] 0.000s
#> [graph_build/geometric_prune/isize_prune] running...
[graph_build/geometric_prune/isize_prune] 0.103s
#> Graph processing completed (0.103)
#> [compute_knn] 0.000s
#> [graph_build] 0.003s
#> [geometric_prune] 0.100s
#> [isize_prune] skipped (with.isize.pruning=FALSE)
#> Creating return list objects ... DONE (0.000)
#> Total elapsed time (0.103)

# View statistics for each k
print(res2$k_statistics)
#>       k n_edges n_edges_in_pruned_graph n_removed_edges edge_reduction_ratio
#> [1,]  3     538                     279             259            0.4814126
#> [2,]  4     834                     424             410            0.4916067
#> [3,]  5    1154                     586             568            0.4922010
#> [4,]  6    1450                     733             717            0.4944828
#> [5,]  7    1787                     900             887            0.4963626
#> [6,]  8    2151                    1082            1069            0.4969781
#> [7,]  9    2526                    1271            1255            0.4968329
#> [8,] 10    2863                    1438            1425            0.4977297
#>      n_edges_in_isize_pruned_graph n_removed_edges_in_double_pruning
#> [1,]                           NaN                               NaN
#> [2,]                           NaN                               NaN
#> [3,]                           NaN                               NaN
#> [4,]                           NaN                               NaN
#> [5,]                           NaN                               NaN
#> [6,]                           NaN                               NaN
#> [7,]                           NaN                               NaN
#> [8,]                           NaN                               NaN
#>      double_edge_reduction_ratio
#> [1,]                         NaN
#> [2,]                         NaN
#> [3,]                         NaN
#> [4,]                         NaN
#> [5,]                         NaN
#> [6,]                         NaN
#> [7,]                         NaN
#> [8,]                         NaN