Constructing and Diagnosing Data-Derived Graphs

Overview

dgraphs constructs graphs whose vertices are numerical observations. The package supports mutual and symmetric k-nearest-neighbor graphs, fixed and adaptive radius graphs, continuous-kNN graphs, intersection-kNN graphs, and minimum-spanning-tree completion. Constructors retain graph lifecycle stages so that native, pruned, and connectivity-repaired graphs can be compared.

This vignette follows a small example from construction through connectivity repair, parameter inspection, conversion to igraph, and geodesic fidelity diagnostics.

library(dgraphs)

set.seed(20260820)
n <- 60L
theta <- sort(c(
  runif(40L, 0, pi),
  runif(20L, pi, 2 * pi)
))
X <- cbind(x = cos(theta), y = sin(theta)) +
  matrix(rnorm(2L * n, sd = 0.015), ncol = 2)

The unequal sample counts on the two semicircles create a simple variable-density point cloud. Its circular ordering also supplies a known reference distance for later diagnostics.

Construct candidate graph families

The following calls use the same local scale, k = 5, where that parameter is defined. Connectivity repair is requested so every final graph supports all-pairs geodesic distances.

graphs <- list(
  mutual = create.mknn.graph(
    X,
    k = 5,
    connect.components = TRUE
  ),
  symmetric = create.sknn.graph(
    X,
    k = 5,
    neighbor.method = "ann",
    connect.components = TRUE
  ),
  continuous = create.cknn.graph(
    X,
    k.scale = 5,
    delta = 1.2,
    connect.components = TRUE
  ),
  adaptive.max = create.rknn.graph(
    X,
    type = "adaptive.radius",
    k.scale = 5,
    radius.rule = "max",
    connect.components = TRUE
  )
)

Each final graph exposes aligned adj_list and weight_list fields. The weights are Euclidean edge lengths. The raw fields represent the graph before optional pruning and connectivity repair.

graph.summary <- do.call(rbind, lapply(names(graphs), function(name) {
  graph <- graphs[[name]]
  data.frame(
    graph = name,
    edges = sum(lengths(graph$adj_list)) / 2,
    raw.components = length(unique(
      graph.connected.components(graph$raw_adj_list)
    )),
    final.components = length(unique(
      graph.connected.components(graph$adj_list)
    )),
    bridges = graph$n_mst_edges_added
  )
}))
graph.summary
#>          graph edges raw.components final.components bridges
#> 1       mutual   128              3                1       2
#> 2    symmetric   174              1                1       0
#> 3   continuous   164              1                1       0
#> 4 adaptive.max   174              1                1       0

The number of edges is a property of the construction rule, not a quality score by itself. The component columns show when the optional repair stage was needed and how many minimum-spanning-tree bridge edges it added.

Inspect a parameter sequence

Plural constructors make parameter sweeps explicit. Here create.rknn.graphs() constructs adaptive-radius graphs for four local-scale values. Its statistics table separates native edge and component counts from repair counts.

radius.sequence <- create.rknn.graphs(
  X,
  k.values = 3:6,
  radius.search = "ann",
  connect.components = TRUE
)
radius.sequence$k_statistics[, c(
  "k", "n_edges_before_pruning", "n_components_before",
  "n_mst_edges_added", "n_components_after"
)]
#>   k n_edges_before_pruning n_components_before n_mst_edges_added
#> 3 3                    109                   3                 2
#> 4 4                    142                   1                 0
#> 5 5                    174                   1                 0
#> 6 6                    208                   1                 0
#>   n_components_after
#> 3                  1
#> 4                  1
#> 5                  1
#> 6                  1

For exploratory work, this table can identify the smallest neighborhood scale that produces a connected native graph. Scientific applications should also evaluate whether the resulting geodesics preserve the geometry relevant to the analysis.

Convert and inspect a selected graph

Current graph objects convert directly to igraph. Edge lengths become the weight edge attribute.

selected <- graphs$continuous
selected.igraph <- as_igraph(selected)
c(
  vertices = igraph::vcount(selected.igraph),
  edges = igraph::ecount(selected.igraph)
)
#> vertices    edges 
#>       60      164

degree.pmf <- compute.graph.summary.pmf(
  selected,
  summary = "degree_distribution"
)
degree.pmf$pmf
#>          3          4          5          6          7          8 
#> 0.01666667 0.15000000 0.36666667 0.30000000 0.15000000 0.01666667

The graph can also be drawn in the original coordinates without running a layout algorithm.

edge.matrix <- convert.adjacency.to.edge.matrix(
  selected$adj_list
)$edge.matrix

plot(
  X,
  asp = 1,
  pch = 19,
  col = "#1F5A94",
  xlab = "Coordinate 1",
  ylab = "Coordinate 2"
)
segments(
  X[edge.matrix[, 1], 1],
  X[edge.matrix[, 1], 2],
  X[edge.matrix[, 2], 1],
  X[edge.matrix[, 2], 2],
  col = grDevices::adjustcolor("grey35", alpha.f = 0.45)
)
points(X, pch = 19, col = "#1F5A94")

A circular point cloud with denser sampling on the upper semicircle. Gray graph edges connect nearby points around the circle.

Continuous-kNN graph on the variable-density circular point cloud. Lines are graph edges and points are observations.

Diagnose geodesic fidelity

For this example, the reference geodesic distance is the shorter arc between two sample angles. graph.geodesic.distances() computes graph shortest-path distances, and isometry.geodesic.diagnostics() summarizes their deviation from the reference after an optional global scale calibration.

graph.distance <- graph.geodesic.distances(selected)
angle.difference <- abs(outer(theta, theta, "-"))
reference.distance <- pmin(
  angle.difference,
  2 * pi - angle.difference
)

round(isometry.geodesic.diagnostics(
  graph.distance,
  reference.distance
), 3)
#>  rel_geodesic_stress          signed_bias    shortcut_fraction 
#>                0.471               -0.170                0.857 
#> q50_rel_abs_residual q90_rel_abs_residual q95_rel_abs_residual 
#>                0.366                0.541                1.296 
#>      short_band_bias        mid_band_bias       long_band_bias 
#>               -0.361               -0.361               -0.363

The relative stress summarizes overall discrepancy. The shortcut fraction is the fraction of calibrated graph distances that are shorter than their reference distances. The short-, middle-, and long-distance bias entries show whether distortion is concentrated at a particular distance scale.

Practical guidance

No graph family is uniformly best. Mutual-kNN graphs are conservative and can disconnect in sparse regions; symmetric-kNN graphs are more connected but can introduce asymmetric-density links; adaptive-radius and continuous-kNN graphs adjust their support using local scales. Connectivity repair guarantees finite final geodesics, but bridge edges are modeling choices that should be inspected rather than hidden. Parameter sequences, lifecycle fields, graph summaries, and geodesic diagnostics are therefore intended to be used together.