create.sknn.graph: Compute a Symmetric k-Nearest Neighbor Graph

In dgraphs: Data-Derived Graph Construction Utilities

Compute a Symmetric k-Nearest Neighbor Graph

Description

Creates an undirected symmetric k-nearest neighbor (sKNN) graph from a numeric data matrix. An edge between vertices i and j is present when either j is among the k nearest neighbors of i, or i is among the k nearest neighbors of j.

Usage

create.sknn.graph(
  X,
  k,
  prune.edges = FALSE,
  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"),
  edge.weight = c("distance"),
  neighbor.method = c("exact", "ann"),
  ann.eps = 0,
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2
)

Arguments

X	Numeric matrix or data frame with observations in rows.
k	Integer scalar. Number of non-self nearest neighbors.
prune.edges	Logical scalar. If TRUE, apply experimental local geometric edge pruning before optional MST connectivity repair.
prune.method	Character scalar. "none" disables pruning. "local.geodesic" applies experimental local geometric edge pruning. "global.geodesic.ratio" applies whole-graph geodesic-ratio pruning.
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. An edge may be pruned when the shortest 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 pruned edge and columns for direct length, replacement path length, and their ratio.
connect.components	Logical scalar. If TRUE, add MST bridge edges so that the final graph is connected whenever possible.
connect.method	Character scalar. "component.mst" adds the minimum number of shortest inter-component bridges. "component.mst.ann" tries sparse ANN bridge candidates before automatic exact fallback. "global.mst" unions the sKNN graph with the Euclidean MST on all vertices.
edge.weight	Character scalar. Currently only "distance" is supported.
neighbor.method	Character scalar. "exact" uses all pairwise distances for kNN construction. "ann" uses the bundled ANN kd-tree backend for the kNN construction itself.
ann.eps	Non-negative numeric scalar reserved for approximate ANN search. Currently only 0 is supported.
bridge.k	Integer scalar or NULL. Initial number of ANN neighbors to use for sparse inter-component bridge search when connect.method = "component.mst.ann". Defaults to max(k, 10), capped at nrow(X) - 1.
bridge.k.max	Integer scalar or NULL. Maximum number of ANN neighbors to use before exact fallback. Defaults to min(nrow(X) - 1, max(50, 8 * k, bridge.k)).
bridge.growth	Numeric scalar greater than 1. Multiplicative growth factor for bridge candidate neighborhoods.

Details

With no nearest-neighbor ties, the sKNN edge rule is equivalent to

d_{ij} \le \max(\sigma_i, \sigma_j),

where \sigma_i is the distance from point i to its k-th non-self nearest neighbor.

If connect.components = TRUE, the graph is augmented with MST edges. The default connect.method = "component.mst" first collapses each connected component of the sKNN graph to one component vertex, weights each component pair by the shortest data-space edge between them, and adds the minimum spanning tree of this component graph. This adds exactly m - 1 bridge edges when the original sKNN graph has m connected components. connect.method = "component.mst.ann" uses ANN nearest-neighbor bridge candidates first and automatically falls back to exact component MST when the sparse candidate graph does not connect all components. The alternative connect.method = "global.mst" unions the sKNN graph with the full Euclidean MST on the data points.

neighbor.method = "exact" computes all pairwise distances and is the deterministic reference implementation. neighbor.method = "ann" uses the bundled ANN kd-tree for the Euclidean kNN search step; exact parity can differ only in nearest-neighbor tie cases. Edge weights are always returned as ordinary Euclidean distances. Exact component.mst repair uses exact pairwise bridge distances; component.mst.ann uses ANN bridge candidates before guaranteed exact fallback.

If prune.method = "local.geodesic" or prune.edges = TRUE, an experimental local-geodesic pruning stage is applied after the sKNN support is built and before optional MST connectivity repair. Candidate edges are processed longest-first. For an edge ⁠(i, j)⁠, the edge is removed only when the currently retained graph contains an alternative path from i to j, restricted to the union of their local neighborhoods, whose length is at most prune.tau times the direct edge length. prune.method = "global.geodesic.ratio" instead uses the whole graph as the alternative-path search domain and removes long edges whose shortest alternative path is within the configured geodesic-ratio threshold.

Value

A list of class "sknn_graph" with adjacency lists, weights, edge matrix, kNN index matrix, component diagnostics, and any MST edges added. The graph lifecycle fields are:

raw_adj_list, raw_weight_list

The native sKNN 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 sKNN 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.

adj_list, weight_list

The final graph after optional MST component repair. Downstream algorithms should use these fields unless they explicitly need a lifecycle diagnostic stage.

Examples

X <- rbind(c(0, 0), c(1, 0), c(10, 0), c(11, 0))
g <- create.sknn.graph(X, k = 1, connect.components = TRUE)
g$n_components_before
g$n_components_after
g$mst_edge_matrix

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