Compute Gradient Flow Basins with Optional Modulation

Computes basins of attraction for all local extrema of a function defined on a weighted graph. Supports modulated gradient flow that accounts for data density and edge length distributions to produce more robust basins.

Usage

compute.gfc.basins(
  adj.list,
  weight.list,
  y,
  modulation = c("none", "density", "edgelen", "density_edgelen"),
  density = NULL,
  edgelen.bandwidth = -1,
  verbose = TRUE
)

Arguments

adj.list

A list where each element i contains the indices of vertices adjacent to vertex i (1-based indexing).

weight.list

A list where each element i contains the edge weights (lengths) from vertex i to its neighbors.

y

Numeric vector of function values at each vertex.

modulation

Character string specifying gradient flow modulation:

"none"

Standard gradient flow (steepest ascent/descent)

"density"

Density-modulated: \(\rho(u) \cdot \Delta \hat{y}\), favors high-density regions

"edgelen"

Edge-length-modulated: \(dl([v,u]) \cdot \Delta \hat{y}\), penalizes atypical edges

"density_edgelen"

Combined: \(\rho(u) \cdot dl([v,u]) \cdot \Delta \hat{y}\)

density

Optional numeric vector of density values at each vertex. If NULL and modulation includes "density", computed from nearest neighbor distances as \(\rho(v) = 1/d_1(v)\).

edgelen.bandwidth

Bandwidth for edge length KDE. If negative (default), uses Silverman's rule of thumb.

verbose

Logical; if TRUE, print progress information.

Value

An object of class "gfc_basins", a named list where each element corresponds to a local extremum and contains:

extremum.vertex

Vertex index of the local extremum (1-based)

value

Function value at the extremum

is.maximum

Logical; TRUE for maxima, FALSE for minima

vertices

Integer vector of vertices in the basin (1-based)

boundary

Integer vector of boundary vertices (1-based)

Names are formatted as "min_V" or "max_V" where V is the vertex index.

Details

The gradient flow at vertex v follows the edge \([v,u]\) that maximizes the modulated gradient score. For ascending flow (to maxima), this is:

• none: \(\max(\hat{y}(u) - \hat{y}(v))\)

• density: \(\max(\rho(u) · (\hat{y}(u) - \hat{y}(v)))\)

• edgelen: \(\max(dl([v,u]) · (\hat{y}(u) - \hat{y}(v)))\)

• density_edgelen: \(\max(\rho(u) · dl([v,u]) · (\hat{y}(u) - \hat{y}(v)))\)

The density modulation favors flow through high-density regions, avoiding spurious paths through sparse areas. The edge length modulation penalizes very short and very long edges, favoring edges near the mode of the length distribution. This addresses the "long edge basin jumping" problem.

Boundary vertices are neighbors of basin vertices that do not belong to the basin. These are essential for Dirichlet harmonic extension problems.

Examples

if (FALSE) { # \dontrun{
# Compute standard basins
basins <- compute.gfc.basins(adj.list, weight.list, fitted.values,
                              modulation = "none")

# Compute density-modulated basins
basins.density <- compute.gfc.basins(adj.list, weight.list, fitted.values,
                                      modulation = "density")

# Access a specific basin
m1.basin <- basins[["max_1147"]]
print(m1.basin$vertices)
print(m1.basin$boundary)
} # }