Create Multiple Mutual kNN Graphs with Geometric Pruning

Constructs a series of mutual k-nearest neighbor (MkNN) graphs across a range of k values, with optional geometric pruning to remove redundant edges based on alternative path analysis.

Usage

create.mknn.graphs(
  X,
  k.values,
  max.path.edge.ratio.thld = 1.2,
  path.edge.ratio.percentile = 0.5,
  compute.full = FALSE,
  pca.dim = 100,
  variance.explained = 0.99,
  verbose = FALSE
)

Arguments

X: A numeric matrix where rows represent data points and columns represent features. Data frames will be converted to matrices.
k.values: Strictly increasing integer vector of neighborhood sizes, each between 1 and n - 1.
max.path.edge.ratio.thld: Maximum acceptable ratio of alternative path length to direct edge length for pruning; zero disables pruning. Edges with alternative paths having ratio <= this value will be pruned. Default is 1.2. Set to 0 to disable pruning.
path.edge.ratio.percentile: Percentile threshold (0.0-1.0) for edge lengths to consider for pruning. Only edges with length greater than this percentile are evaluated. Default is 0.5.
compute.full: Logical; if TRUE, returns complete graph structures for each k value. If FALSE, returns only summary statistics. Default is FALSE.
pca.dim: Maximum number of principal components to use if dimensionality reduction is applied. Default is 100. Set to NULL to skip dimensionality reduction.
variance.explained: Target percentage of variance to be explained by the principal components (0-1). Default is 0.99. If this can be achieved with fewer than pca.dim components, the smaller number is used. Set to NULL to use exactly pca.dim components.
verbose: Logical; if TRUE, displays progress messages. Default is FALSE.

Value

An object of class "mknn_graphs" containing:

k_statistics: A data frame with columns: k (k value), n_edges (edges before pruning), n_edges_pruned (edges after pruning), n_removed (number of removed edges), reduction_ratio (proportion of edges removed).
pruned_graphs: If compute.full=TRUE, a named list of pruned graphs for each k value. NULL otherwise.
edge_pruning_stats: A list of pruning statistics for each k value, containing edge lengths and path ratios.

The returned object also has the following attributes:

k.values: The requested neighborhood sizes
max.path.edge.ratio.thld: The pruning threshold used
path.edge.ratio.percentile: The percentile threshold used
pca: If PCA was performed, contains dimensionality reduction details

Details

This function performs the following steps for each k value:

Mutual kNN Graph Construction: Creates a graph where edges exist only between mutually nearest neighbors.
Geometric Pruning (optional): Removes edges where alternative paths exist with acceptable length ratios. An edge (i,j) is pruned if there exists a path i->k->j such that (d(i,k) + d(k,j)) / d(i,j) <= threshold.
Dimensionality Reduction (optional): If the data has more than pca.dim dimensions, PCA is applied before graph construction to improve computational efficiency and reduce noise.

The geometric pruning step helps create sparser graphs by removing edges that can be well-approximated by two-hop paths, which can improve graph quality for clustering and visualization tasks.

Examples

set.seed(123)
X <- matrix(rnorm(80), ncol = 2)
result <- create.mknn.graphs(X, k.values = seq.int(3, 4), compute.full = TRUE, verbose = FALSE)
result$k_statistics
#>   k n_edges n_edges_pruned n_removed reduction_ratio
#> 1 3      39             37         2      0.05128205
#> 2 4      52             48         4      0.07692308

X.high <- matrix(rnorm(120), nrow = 20, ncol = 6)
result.pca <- create.mknn.graphs(X.high, k.values = seq.int(2, 3), pca.dim = 3, verbose = FALSE)
attr(result.pca, "pca")$n_components
#> [1] 3