Construct a Reusable Metric Graph Low-Pass Spectral Basis

Builds a metric-conductance graph Laplacian and computes the low-frequency eigensystem used by graph low-pass filters. The resulting object is response-independent and can be reused for many responses and filter parameters.

Usage

metric.graph.lowpass.basis(
  adj.list,
  weight.list,
  conductance.rule = c("inverse.length.power", "exp.length", "exp.length.squared",
    "self.tuned.gaussian"),
  conductance.epsilon = 1e-08,
  conductance.alpha = 1,
  conductance.sigma = NULL,
  conductance.sigma.rule = c("edge.quantile", "median", "local.k"),
  conductance.sigma.quantile = 0.75,
  conductance.local.k = 5L,
  laplacian.type = c("unnormalized", "symmetric.normalized"),
  n.eigenpairs = 50L,
  eigen.solver = c("auto", "sparse", "dense"),
  dense.eigen.threshold = 200L,
  dense.fallback.threshold = 5000L,
  dense.fallback = c("auto", "never", "always"),
  verbose = FALSE
)

Arguments

adj.list

List of integer neighbor vectors using 1-based vertex indices.

weight.list

List of positive metric edge lengths parallel to adj.list. These are interpreted as edge lengths, not conductances.

conductance.rule

Character scalar. One of "inverse.length.power", "exp.length", "exp.length.squared", or "self.tuned.gaussian".

conductance.epsilon

Positive numeric regularizer used by inverse-power conductances and as a local-scale floor.

conductance.alpha

Positive numeric exponent for "inverse.length.power".

conductance.sigma

Optional positive global scale for exponential rules. If NULL, it is selected by conductance.sigma.rule.

conductance.sigma.rule

Rule for selecting a global scale when needed.

conductance.sigma.quantile

Quantile used when conductance.sigma.rule = "edge.quantile".

conductance.local.k

Positive integer local incident-edge order statistic for "self.tuned.gaussian".

laplacian.type

Laplacian operator. "unnormalized" uses the weighted graph Laplacian \(L = D - C\). "symmetric.normalized" uses \(L_{\mathrm{sym}} = I - D^{-1/2} C D^{-1/2}\).

n.eigenpairs

Positive integer number of eigenpairs to compute.

eigen.solver

"auto", "sparse", or "dense".

dense.eigen.threshold

Exact dense threshold for auto mode.

dense.fallback.threshold

Maximum graph size for emergency dense fallback when sparse decomposition fails and fallback is allowed.

dense.fallback

"auto", "never", or "always".

verbose

Logical. Reserved for future diagnostic messages.

Value

A list of class "metric.graph.lowpass.basis" containing the graph operator, eigenvalues, eigenvectors, solver metadata, and spectral completeness diagnostics.

Details

The basis is complete only when it contains one eigenvector per graph vertex. A truncated basis represents only the retained low-frequency subspace. The largest retained eigenvalue supplies a conservative proxy for bounding the contribution of omitted modes because all omitted eigenvalues are at least as large.

Examples

adj <- list(2L, c(1L, 3L), c(2L, 4L), 3L)
lengths <- list(1, c(1, 1), c(1, 1), 1)
metric.graph.lowpass.basis(adj, lengths, n.eigenpairs = 4L,
                           eigen.solver = "dense")
#> $graph
#> $graph$n.vertices
#> [1] 4
#> 
#> $graph$n.edges
#> [1] 3
#> 
#> $graph$adj.list
#> $graph$adj.list[[1]]
#> [1] 2
#> 
#> $graph$adj.list[[2]]
#> [1] 1 3
#> 
#> $graph$adj.list[[3]]
#> [1] 2 4
#> 
#> $graph$adj.list[[4]]
#> [1] 3
#> 
#> 
#> $graph$weight.list
#> $graph$weight.list[[1]]
#> [1] 1
#> 
#> $graph$weight.list[[2]]
#> [1] 1 1
#> 
#> $graph$weight.list[[3]]
#> [1] 1 1
#> 
#> $graph$weight.list[[4]]
#> [1] 1
#> 
#> 
#> 
#> $operator
#> $graph
#> $graph$n.vertices
#> [1] 4
#> 
#> $graph$n.edges
#> [1] 3
#> 
#> $graph$adj.list
#> $graph$adj.list[[1]]
#> [1] 2
#> 
#> $graph$adj.list[[2]]
#> [1] 1 3
#> 
#> $graph$adj.list[[3]]
#> [1] 2 4
#> 
#> $graph$adj.list[[4]]
#> [1] 3
#> 
#> 
#> $graph$weight.list
#> $graph$weight.list[[1]]
#> [1] 1
#> 
#> $graph$weight.list[[2]]
#> [1] 1 1
#> 
#> $graph$weight.list[[3]]
#> [1] 1 1
#> 
#> $graph$weight.list[[4]]
#> [1] 1
#> 
#> 
#> 
#> $edge.table
#>   u v length conductance
#> 1 1 2      1           1
#> 2 2 3      1           1
#> 3 3 4      1           1
#> 
#> $conductance
#> $conductance$rule
#> [1] "inverse.length.power"
#> 
#> $conductance$values
#> [1] 1 1 1
#> 
#> $conductance$local.scales
#> [1] NA NA NA NA
#> 
#> $conductance$summary
#> $conductance$summary$min
#> [1] 1
#> 
#> $conductance$summary$q10
#> [1] 1
#> 
#> $conductance$summary$median
#> [1] 1
#> 
#> $conductance$summary$q90
#> [1] 1
#> 
#> $conductance$summary$max
#> [1] 1
#> 
#> $conductance$summary$mean
#> [1] 1
#> 
#> $conductance$summary$n.nonfinite
#> [1] 0
#> 
#> $conductance$summary$n.clipped
#> [1] 0
#> 
#> 
#> 
#> $degree
#> [1] 1 2 2 1
#> 
#> $laplacian
#> $laplacian$dim
#> [1] 4 4
#> 
#> $laplacian$i
#>  [1] 0 1 0 1 2 1 2 3 2 3
#> 
#> $laplacian$j
#>  [1] 0 0 1 1 1 2 2 2 3 3
#> 
#> $laplacian$x
#>  [1]  1 -1 -1  2 -1 -1  2 -1 -1  1
#> 
#> $laplacian$matrix
#> 4 x 4 sparse Matrix of class "dgCMatrix"
#>                 
#> [1,]  1 -1  .  .
#> [2,] -1  2 -1  .
#> [3,]  . -1  2 -1
#> [4,]  .  . -1  1
#> 
#> 
#> $laplacian.type
#> [1] "unnormalized"
#> 
#> $parameters
#> $parameters$conductance.epsilon
#> [1] 1e-08
#> 
#> $parameters$conductance.alpha
#> [1] 1
#> 
#> $parameters$conductance.sigma
#> [1] NA
#> 
#> $parameters$conductance.sigma.rule
#> [1] "edge.quantile"
#> 
#> $parameters$conductance.sigma.quantile
#> [1] 0.75
#> 
#> $parameters$conductance.local.k
#> [1] 5
#> 
#> $parameters$laplacian.type
#> [1] "unnormalized"
#> 
#> 
#> $diagnostics
#> $diagnostics$degree.summary
#> $diagnostics$degree.summary$min
#> [1] 1
#> 
#> $diagnostics$degree.summary$q10
#> [1] 1
#> 
#> $diagnostics$degree.summary$median
#> [1] 1.5
#> 
#> $diagnostics$degree.summary$q90
#> [1] 2
#> 
#> $diagnostics$degree.summary$max
#> [1] 2
#> 
#> $diagnostics$degree.summary$mean
#> [1] 1.5
#> 
#> $diagnostics$degree.summary$n.nonfinite
#> [1] 0
#> 
#> $diagnostics$degree.summary$n.clipped
#> [1] 0
#> 
#> 
#> $diagnostics$length.summary
#> $diagnostics$length.summary$min
#> [1] 1
#> 
#> $diagnostics$length.summary$q10
#> [1] 1
#> 
#> $diagnostics$length.summary$median
#> [1] 1
#> 
#> $diagnostics$length.summary$q90
#> [1] 1
#> 
#> $diagnostics$length.summary$max
#> [1] 1
#> 
#> $diagnostics$length.summary$mean
#> [1] 1
#> 
#> $diagnostics$length.summary$n.nonfinite
#> [1] 0
#> 
#> $diagnostics$length.summary$n.clipped
#> [1] 0
#> 
#> 
#> 
#> attr(,"class")
#> [1] "metric.graph.lowpass.operator" "list"                         
#> 
#> $conductance
#> $conductance$rule
#> [1] "inverse.length.power"
#> 
#> $conductance$values
#> [1] 1 1 1
#> 
#> $conductance$local.scales
#> [1] NA NA NA NA
#> 
#> $conductance$summary
#> $conductance$summary$min
#> [1] 1
#> 
#> $conductance$summary$q10
#> [1] 1
#> 
#> $conductance$summary$median
#> [1] 1
#> 
#> $conductance$summary$q90
#> [1] 1
#> 
#> $conductance$summary$max
#> [1] 1
#> 
#> $conductance$summary$mean
#> [1] 1
#> 
#> $conductance$summary$n.nonfinite
#> [1] 0
#> 
#> $conductance$summary$n.clipped
#> [1] 0
#> 
#> 
#> 
#> $laplacian
#> $laplacian$dim
#> [1] 4 4
#> 
#> $laplacian$i
#>  [1] 0 1 0 1 2 1 2 3 2 3
#> 
#> $laplacian$j
#>  [1] 0 0 1 1 1 2 2 2 3 3
#> 
#> $laplacian$x
#>  [1]  1 -1 -1  2 -1 -1  2 -1 -1  1
#> 
#> $laplacian$matrix
#> 4 x 4 sparse Matrix of class "dgCMatrix"
#>                 
#> [1,]  1 -1  .  .
#> [2,] -1  2 -1  .
#> [3,]  . -1  2 -1
#> [4,]  .  . -1  1
#> 
#> 
#> $laplacian.type
#> [1] "unnormalized"
#> 
#> $spectral
#> $spectral$eigenvalues
#> [1] -7.244401e-17  5.857864e-01  2.000000e+00  3.414214e+00
#> 
#> $spectral$eigenvectors
#>      [,1]       [,2] [,3]       [,4]
#> [1,] -0.5 -0.6532815 -0.5  0.2705981
#> [2,] -0.5 -0.2705981  0.5 -0.6532815
#> [3,] -0.5  0.2705981  0.5  0.6532815
#> [4,] -0.5  0.6532815 -0.5 -0.2705981
#> 
#> $spectral$backend
#> [1] "dense"
#> 
#> $spectral$n.vertices
#> [1] 4
#> 
#> $spectral$n.eigenpairs
#> [1] 4
#> 
#> $spectral$is.complete
#> [1] TRUE
#> 
#> $spectral$largest.retained.eigenvalue
#> [1] 3.414214
#> 
#> $spectral$smallest.positive.eigenvalue
#> [1] 0.5857864
#> 
#> $spectral$omitted.attenuation.bound.type
#> [1] "complete_spectrum"
#> 
#> 
#> $parameters
#> $parameters$conductance.rule
#> [1] "inverse.length.power"
#> 
#> $parameters$conductance.epsilon
#> [1] 1e-08
#> 
#> $parameters$conductance.alpha
#> [1] 1
#> 
#> $parameters$conductance.sigma
#> [1] NaN
#> 
#> $parameters$conductance.sigma.rule
#> [1] "edge.quantile"
#> 
#> $parameters$conductance.sigma.quantile
#> [1] 0.75
#> 
#> $parameters$conductance.local.k
#> [1] 5
#> 
#> $parameters$laplacian.type
#> [1] "unnormalized"
#> 
#> $parameters$verbose
#> [1] FALSE
#> 
#> $parameters$n.eigenpairs
#> [1] 4
#> 
#> $parameters$eigen.solver
#> [1] "dense"
#> 
#> $parameters$dense.eigen.threshold
#> [1] 200
#> 
#> $parameters$dense.fallback.threshold
#> [1] 5000
#> 
#> $parameters$dense.fallback
#> [1] "auto"
#> 
#> 
#> attr(,"class")
#> [1] "metric.graph.lowpass.basis" "list"