Compute a Mutual k-Nearest Neighbor Graph with Weights

Creates an undirected graph where two points are connected by an edge if and only if they are present in each other's k-nearest neighbor (kNN) lists. The weight of each edge represents the distance between the connected vertices.

Usage

create.mknn.graph(
  X,
  k,
  prune.method = c("none", "local.geodesic", "global.geodesic.ratio"),
  max.path.edge.ratio.deviation.thld = 0.1,
  path.edge.ratio.percentile = 0.5,
  prune.tau = 1.05,
  prune.local.k = NULL,
  with.pruned.edge.stats = FALSE,
  connect.components = FALSE,
  connect.method = c("component.mst", "component.mst.ann", "global.mst"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

X: A numeric matrix or data frame where each row represents a data point and each column represents a feature/dimension.
k: A positive integer specifying the number of nearest neighbors to consider, excluding self; require 1 <= k < n.
prune.method: Character scalar. "none" disables geometric pruning. "local.geodesic" applies the experimental local geometric pruning stage before optional MST connectivity repair. "global.geodesic.ratio" applies whole-graph geodesic-ratio pruning before optional MST connectivity repair.
max.path.edge.ratio.deviation.thld: Numeric scalar in [0, 0.2). For prune.method = "global.geodesic.ratio", an edge may be removed when the shortest alternative path is at most 1 + max.path.edge.ratio.deviation.thld times the direct edge length.
path.edge.ratio.percentile: Numeric scalar in [0, 1]. For prune.method = "global.geodesic.ratio", only edges at or above this edge length percentile are considered.
prune.tau: Numeric scalar greater than 1. For local geometric pruning, an edge may be removed when a retained local alternative path is at most this multiplicative factor times the direct edge length.
prune.local.k: Integer scalar or NULL. Number of nearest neighbors used to form local neighborhoods for pruning. Defaults to k.
with.pruned.edge.stats: Logical scalar. If TRUE, return a data frame with one row per locally pruned edge.
connect.components: Logical scalar. If TRUE, add MST bridge edges so the final graph is connected whenever possible.
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.

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 mutual k-nearest neighbor graph is a symmetric graph where an edge between vertices i and j exists if and only if:

j is among the k nearest neighbors of i, AND
i is among the k nearest neighbors of j

This mutual relationship ensures that the resulting graph is undirected and typically sparser than a standard k-nearest neighbor graph.

Use graph accessors for the final graph and graph.stages() to list stored raw, pruned and repaired stages. Construction details are in metadata.

Examples

set.seed(123)
X <- matrix(rnorm(60), ncol = 2)
graph <- create.mknn.graph(X, k = 4)
graph.order(graph)
#> [1] 30
nrow(graph.edges(graph))
#> [1] 39
graph.adjacency(graph)[[1]]
#> [1] 21