create.mknn.graph: Compute a Mutual k-Nearest Neighbor Graph with Weights

In dgraphs: Data-Derived Graph Construction Utilities

Compute a Mutual k-Nearest Neighbor Graph with Weights

Description

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. Must be at least 2.
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.

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.

The final graph is always stored in adj_list/weight_list. Lifecycle diagnostic fields follow the same convention as the other graph constructors: raw_* is before pruning and MST repair, and pruned_* is after pruning but before MST repair. The raw_repaired_*, pruned_repaired_*, and repaired_pruned_* branches allow one constructor call to compare native, prune-first, and repair-first graph geodesic geometries.

Value

A list with class "mknn_graph" containing:

adj_list

A list where element i contains the indices of vertices connected to vertex i by an edge in the final graph after optional MST component repair.

weight_list

A list where element i contains the distances between vertex i and its connected neighbors in the final graph (in the same order as adj_list[[i]]).

raw_adj_list, raw_weight_list

The native mutual-kNN graph before pruning and before optional MST component repair.

pruned_adj_list, pruned_weight_list

The graph after optional local geometric pruning and before optional MST component repair. If pruning is disabled, these fields are identical to the raw graph.

raw_repaired_adj_list, raw_repaired_weight_list

The native mutual kNN 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 local geometric pruning to the repaired raw graph.

n_vertices

The number of vertices in the graph.

n_edges

The total number of edges in the graph.

k

The k value used to construct the graph.

See Also

create.mknn.graphs for creating multiple graphs with different k values, summary.mknn_graphs for summarizing graph properties

Examples

set.seed(123)
X <- matrix(rnorm(60), ncol = 2)
graph <- create.mknn.graph(X, k = 4)
graph$n_vertices
graph$n_edges
graph$adj_list[[1]]

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