Compute a Symmetric k-Nearest Neighbor Graph

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,
  knn.index = NULL,
  graph.detail = c("full", "minimal"),
  bridge.k = NULL,
  bridge.k.max = NULL,
  bridge.growth = 2,
  input.type = c("observations", "distances")
)

Arguments

X

Numeric observation matrix/data frame, or a symmetric numeric distance matrix or dist object when input.type = "distances".

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.

knn.index

Optional integer matrix of precomputed, one-based, ordered non-self neighbor indices. It must have nrow(X) rows and at least k columns. This is supported only with neighbor.method = "ann" and is primarily useful when constructing several graphs from one cached search.

graph.detail

Character scalar. "full" returns the complete graph lifecycle object. "minimal" skips lifecycle branch construction and is allowed only with prune.method = "none", prune.edges = FALSE, and connect.components = FALSE.

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.

input.type

Input interpretation. Defaults to "observations" for backward compatibility; symmetry never triggers automatic detection.

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

With input.type = "distances", supplied distances determine exact neighbor rankings, every edge length, and component/global MST repair. Distance input must be finite, nonnegative, square and symmetric, with a zero diagonal. Symmetry and diagonal tolerance is 1e-12 * max(1, max(X)); accepted asymmetry is averaged and the diagonal set to zero. Row and column names, if present, must be identical and unique. Off-diagonal zeros are allowed. Triangle inequality is not tested, so symmetric dissimilarities are accepted. Ties are resolved by increasing vertex index, excluding self explicitly. ANN search/repair and pruning are unsupported for distance input and error. The series constructor validates distances and ranks neighbors once, through its largest requested k. Full lifecycle stages use these same distances.

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.

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$metadata$n_components_before
#> [1] 2
g$metadata$n_components_after
#> [1] 1
g$metadata$mst_edge_matrix
#>      [,1] [,2]
#> [1,]    2    3