Create Graph Flow Complex with Harmonic Extension

Computes a graph flow complex by identifying local extrema and their neighborhoods, then applies harmonic extension to smooth spurious extrema while preserving significant topological features. The algorithm uses hop index thresholding to identify and smooth spurious extrema through various smoothing methods.

Usage

create.gflow.cx(
  adj.list,
  weight.list,
  y,
  hop.idx.thld = 5,
  smoother.type = 0,
  max.outer.iterations = 5,
  max.inner.iterations = 100,
  smoothing.tolerance = 1e-06,
  sigma = 1,
  process.in.order = TRUE,
  verbose = TRUE,
  detailed.recording = FALSE
)

Arguments

adj.list

A list where each element i contains the indices of vertices adjacent to vertex i. Indices should be 1-based (R convention). Must have the same length as weight.list and y.

weight.list

A list where each element i contains the weights of edges from vertex i to its neighbors. Must have the same structure and length as adj.list.

y

A numeric vector of function values defined on the graph vertices. Must have the same length as adj.list.

hop.idx.thld

Numeric scalar specifying the hop index threshold. Extrema with hop index less than or equal to this value are considered spurious and will be smoothed. Default is 5. Must be non-negative.

smoother.type

Integer specifying the smoothing algorithm:

• 0: Weighted Mean (default) - Simple weighted averaging

• 1: Harmonic Iterative - Iterative harmonic smoothing

• 2: Harmonic Eigen - Eigenfunction-based harmonic smoothing

• 3: Hybrid Biharmonic-Harmonic - Combined biharmonic and harmonic

• 4: Boundary Smoothed Harmonic - Harmonic with boundary smoothing

max.outer.iterations

Maximum number of outer iterations for the smoothing process. Default is 5.

max.inner.iterations

Maximum number of iterations for each individual smoothing operation. Default is 100.

smoothing.tolerance

Numeric scalar for convergence tolerance in smoothing algorithms. Default is 1e-6.

sigma

Numeric scalar controlling the width of the smoothing kernel. Default is 1.0. Larger values produce more smoothing.

process.in.order

Logical; if TRUE (default), processes extrema in ascending order of hop index, smoothing the most spurious extrema first.

verbose

Logical; if TRUE (default), prints progress information during the computation.

detailed.recording

Logical; if TRUE, records detailed information about each smoothing step for later visualization. Default is FALSE. Note that this increases memory usage.

Value

An object of class "gflow_cx" containing:

harmonic_predictions

Numeric vector of smoothed function values at each vertex after applying harmonic extension.

lmin_hop_nbhds

List of hop neighborhoods for local minima. Each element contains vertex index, hop index, and neighborhood information.

lmax_hop_nbhds

List of hop neighborhoods for local maxima. Each element contains vertex index, hop index, and neighborhood information.

extrema_df

Data frame summarizing all extrema with columns: vertex, hop_idx, is_max, label, and fn_value.

extrema_df2

Alternative data frame format with spurious extrema information included.

smoothing_history

(If detailed.recording=TRUE) List of records detailing each smoothing step for visualization.

The object also has attributes:

• smoother.type: The integer smoother type used

• smoother.name: Human-readable name of the smoother

• hop.idx.threshold: The hop index threshold used

Details

The algorithm proceeds in several steps:

1. Identifies local minima and maxima in the function values on the graph

2. Computes hop neighborhoods around each extremum

3. Calculates hop indices measuring the significance of each extremum

4. Identifies spurious extrema (those with hop index <= threshold)

5. Applies harmonic extension to smooth out spurious extrema

6. Returns the smoothed function values and extrema information

The hop index measures how many graph hops are needed before the function value exceeds the extremum value, providing a scale-free measure of extremum significance. Spurious extrema typically have small hop indices and represent noise or insignificant features.

See also

create.hop.nbhd.extrema.df for extracting extrema information,

Examples

# Create a simple triangle graph
adj.list <- list(c(2,3), c(1,3), c(1,2))
weight.list <- list(c(1,1), c(1,1), c(1,1))

# Function with a spurious maximum at vertex 2
y <- c(0.5, 1.0, 0.7)

# Smooth out spurious extrema
result <- create.gflow.cx(
  adj.list, weight.list, y,
  hop.idx.thld = 1,
  smoother.type = 0,  # Weighted Mean
  verbose = FALSE
)

# Check smoothed values
print(result$harmonic_predictions)

# \donttest{
# More complex example with detailed recording
# Create a larger graph (grid)
n <- 5
adj.list <- vector("list", n*n)
weight.list <- vector("list", n*n)

for(i in 1:n) {
  for(j in 1:n) {
    idx <- (i-1)*n + j
    neighbors <- c()
    weights <- c()

    # Add edges to grid neighbors
    if(i > 1) { neighbors <- c(neighbors, (i-2)*n + j); weights <- c(weights, 1) }
    if(i < n) { neighbors <- c(neighbors, i*n + j); weights <- c(weights, 1) }
    if(j > 1) { neighbors <- c(neighbors, (i-1)*n + j-1); weights <- c(weights, 1) }
    if(j < n) { neighbors <- c(neighbors, (i-1)*n + j+1); weights <- c(weights, 1) }

    adj.list[[idx]] <- neighbors
    weight.list[[idx]] <- weights
  }
}

# Create function with multiple extrema
y <- sin(seq(0, 2*pi, length.out = n*n)) + 0.1*rnorm(n*n)

# Apply smoothing with detailed recording
result <- create.gflow.cx(
  adj.list, weight.list, y,
  hop.idx.thld = 2,
  smoother.type = 2,  # Harmonic Eigen
  detailed.recording = TRUE,
  verbose = TRUE
)

# Examine extrema
print(result$extrema_df)
# }