create.mknn.graphs: Create Multiple Mutual kNN Graphs with Geometric Pruning

In dgraphs: Data-Derived Graph Construction Utilities

Create Multiple Mutual kNN Graphs with Geometric Pruning

Description

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,
  kmin,
  kmax,
  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.
kmin	Minimum k value to consider (positive integer, at least 2).
kmax	Maximum k value to consider (must be >= kmin).
max.path.edge.ratio.thld	Maximum acceptable ratio of alternative path length to direct edge length for pruning. Edges with alternative paths having ratio <= this value will be pruned. Default is 1.2. Set to 0 or negative 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.

Details

This function performs the following steps for each k value:

1. Mutual kNN Graph Construction: Creates a graph where edges exist only between mutually nearest neighbors.

2. 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.

3. 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.

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:

• kmin, kmax: The k range used

• 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

See Also

create.mknn.graph for creating a single MkNN graph, summary.mknn_graphs for summarizing the results

Examples

set.seed(123)
X <- matrix(rnorm(80), ncol = 2)
result <- create.mknn.graphs(
  X, kmin = 3, kmax = 4, compute.full = TRUE, verbose = FALSE
)
result$k_statistics

X.high <- matrix(rnorm(120), nrow = 20, ncol = 6)
result.pca <- create.mknn.graphs(
  X.high, kmin = 2, kmax = 3, pca.dim = 3, verbose = FALSE
)
attr(result.pca, "pca")$n_components

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