Construct a Graph Trend-Filtering Operator — graph.trend.filtering.operator • geosmooth

Builds the weighted graph difference operators used by graph trend filtering. The default operator.family = "graph.laplacian.recursive" uses recursive graph operators $$k=0:\quad \Delta_w^{(1)} = D_w,$$ $$k=1:\quad \Delta_w^{(2)} = L_w = D_w^\top D_w,$$ and $$k=2:\quad \Delta_w^{(3)} = D_w L_w.$$ The experimental operator.family = "path.divided.difference" builds canonical path rows and computes position-aware finite differences along graph paths using weight.list as metric edge lengths.

Usage

graph.trend.filtering.operator(
  adj.list,
  weight.list = NULL,
  order = 0L,
  weight.rule = c("conductance", "sqrt.conductance", "unit"),
  operator.family = c("graph.laplacian.recursive", "path.divided.difference"),
  path.family = c("branch.continuation", "all.simple"),
  path.weighting = c("unit", "anchor.mean"),
  return.sparse = TRUE
)

Arguments

adj.list: List of integer neighbor vectors using 1-based vertex indices. The graph must be undirected: every edge must appear in both endpoint adjacency lists.
weight.list: Optional list of positive edge weights parallel to adj.list. For operator.family = "graph.laplacian.recursive", weights are graph trend-filtering weights or conductances. For operator.family = "path.divided.difference", weights are metric edge lengths used to define path coordinates. If NULL, all values are one.
order: Integer trend-filtering order. Supported values are 0L, 1L, and 2L.
weight.rule: Character scalar. "conductance" uses weight.list directly as $\omega_e$; "sqrt.conductance" uses $\sqrt{w_e}$; "unit" ignores weight.list. This applies to operator.family = "graph.laplacian.recursive".
operator.family: Character scalar selecting the penalty operator family. The default "graph.laplacian.recursive" preserves the existing graph trend-filtering semantics. "path.divided.difference" uses local pathwise finite differences and is designed to reproduce classical one-dimensional trend filtering on path graphs.
path.family: Character scalar used for operator.family = "path.divided.difference". "branch.continuation" keeps paths whose internal vertices do not pass through branch points. "all.simple" keeps all simple paths of the required length.
path.weighting: Character scalar used for operator.family = "path.divided.difference". "unit" assigns every canonical path row weight one. "anchor.mean" divides rows by the number of retained canonical paths sharing the same canonical start vertex.
return.sparse: Logical. If TRUE, attach Matrix sparse incidence, Laplacian, and penalty matrices.

Value

A list of class "graph.trend.filtering.operator" containing the canonical graph, edge table, trend-filtering weights, incidence, weighted Laplacian, selected penalty operator, and nullity estimate.

Examples

adj <- list(2L, c(1L, 3L), c(2L, 4L), 3L)
graph.trend.filtering.operator(adj, order = 1L, weight.rule = "unit")
#> $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
#> 
#> 
#> 
#> $order
#> [1] 1
#> 
#> $weight.rule
#> [1] "unit"
#> 
#> $operator.family
#> [1] "graph.laplacian.recursive"
#> 
#> $path.family
#> [1] "branch.continuation"
#> 
#> $path.weighting
#> [1] "unit"
#> 
#> $edge.table
#>   edge from to base.weight trend.weight
#> 1    1    1  2           1            1
#> 2    2    2  3           1            1
#> 3    3    3  4           1            1
#> 
#> $incidence
#> $incidence$i
#> [1] 1 1 2 2 3 3
#> 
#> $incidence$j
#> [1] 1 2 2 3 3 4
#> 
#> $incidence$x
#> [1] -1  1 -1  1 -1  1
#> 
#> $incidence$dim
#> [1] 3 4
#> 
#> $incidence$matrix
#> 3 x 4 sparse Matrix of class "dgCMatrix"
#>                
#> [1,] -1  1  . .
#> [2,]  . -1  1 .
#> [3,]  .  . -1 1
#> 
#> 
#> $laplacian
#> $laplacian$i
#>  [1] 1 2 1 2 3 2 3 4 3 4
#> 
#> $laplacian$j
#>  [1] 1 1 2 2 2 3 3 3 4 4
#> 
#> $laplacian$x
#>  [1]  1 -1 -1  2 -1 -1  2 -1 -1  1
#> 
#> $laplacian$dim
#> [1] 4 4
#> 
#> $laplacian$matrix
#> 4 x 4 sparse Matrix of class "dgCMatrix"
#>                 
#> [1,]  1 -1  .  .
#> [2,] -1  2 -1  .
#> [3,]  . -1  2 -1
#> [4,]  .  . -1  1
#> 
#> 
#> $penalty
#> $penalty$i
#>  [1] 1 2 1 2 3 2 3 4 3 4
#> 
#> $penalty$j
#>  [1] 1 1 2 2 2 3 3 3 4 4
#> 
#> $penalty$x
#>  [1]  1 -1 -1  2 -1 -1  2 -1 -1  1
#> 
#> $penalty$dim
#> [1] 4 4
#> 
#> $penalty$matrix
#> 4 x 4 sparse Matrix of class "dgCMatrix"
#>                 
#> [1,]  1 -1  .  .
#> [2,] -1  2 -1  .
#> [3,]  . -1  2 -1
#> [4,]  .  . -1  1
#> 
#> $penalty$order
#> [1] 1
#> 
#> $penalty$kind
#> [1] "laplacian"
#> 
#> 
#> $nullity.estimate
#> [1] 1
#> 
#> $path.table
#> NULL
#> 
#> attr(,"class")
#> [1] "graph.trend.filtering.operator" "list"