Fit Graph Trend Filtering — fit.graph.trend.filtering • geosmooth

Fits graph trend filtering on a supplied undirected graph. Supported orders are 0L, 1L, and 2L: $$ \widehat\beta_\lambda = \arg\min_{\beta\in\mathbb R^n} \left\{ \frac{1}{2}\|y-\beta\|_2^2 + \lambda\|\Delta_w^{(k+1)}\beta\|_1 \right\}. $$

Usage

fit.graph.trend.filtering(
  adj.list,
  weight.list = NULL,
  y,
  order = 0L,
  lambda.grid = NULL,
  lambda.selection = c("cv", "fixed"),
  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"),
  n.lambda = 40L,
  nfolds = 5L,
  foldid = NULL,
  maxsteps = 2000L,
  minlam = 0,
  approx = FALSE,
  rtol = 1e-07,
  btol = 1e-07,
  eps = 1e-04,
  verbose = FALSE
)

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.
y: Numeric response vector of length length(adj.list).
order: Integer trend-filtering order. Supported values are 0L, 1L, and 2L.
lambda.grid: Optional non-negative lambda grid. For lambda.selection = "fixed", this must contain exactly one value. For lambda.selection = "cv", NULL builds a default grid from the fitted full-data solution path.
lambda.selection: "cv" for vertex K-fold cross-validation or "fixed" for a supplied fixed lambda.
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.
n.lambda: Number of default lambda candidates when lambda.grid = NULL and lambda.selection = "cv".
nfolds: Number of CV folds.
foldid: Optional integer fold assignments of length length(y).
maxsteps: Maximum number of path steps passed to genlasso.
minlam: Minimum lambda passed to genlasso.
approx: Logical; passed to genlasso.
rtol, btol, eps: Numerical controls passed to genlasso.
verbose: Logical. If TRUE, pass verbose output to genlasso.

Value

A list of class "graph.trend.filtering.fit" containing fitted values, residuals, selected lambda, the operator, path metadata, and CV diagnostics when requested.

Details

Graph trend filtering is intended as an $\ell_1$-adaptive comparator to the $\ell_2$ graph smoothers now housed in geosmooth and the legacy rdgraph comparator. The low-pass smoother penalizes broad quadratic graph roughness through a term like $$\eta f^\top L f,$$ which shrinks high-frequency variation everywhere. Graph trend filtering instead penalizes absolute graph differences. For order = 0L, this is $$\lambda \sum_e \omega_e |\beta_j-\beta_i|,$$ so many edge differences can become exactly zero while selected edges carry jumps. In this sense order = 0L is locally adaptive: fitted values can be piecewise constant over graph regions. Higher orders use $$\Delta_w^{(1)} = D_w,\qquad \Delta_w^{(2)} = L_w,\qquad \Delta_w^{(3)} = D_w L_w,$$ with $L_w = D_w^\top D_w$.

The supplied weight.list, when used, is interpreted as a graph trend-filtering edge weight or conductance for operator.family = "graph.laplacian.recursive". For operator.family = "path.divided.difference", weight.list is interpreted as metric edge length and is used to form local path coordinates. Use weight.rule = "sqrt.conductance" when the recursive graph square-root convention is desired, and weight.rule = "unit" for an unweighted recursive graph fused-lasso penalty.

The solver backend is currently genlasso. Cross-validation refits the generalized-lasso problem on vertex-held-out training sets using a selection matrix $X$; this is useful for small and moderate diagnostic problems but is not yet a scalable production graph-trend-filtering solver.

References

Wang, Y.-X., Sharpnack, J., Smola, A., and Tibshirani, R. J. (2016). Trend filtering on graphs. Journal of Machine Learning Research, 17(105), 1–41. https://www.jmlr.org/papers/v17/15-147.html

Examples

if (requireNamespace("genlasso", quietly = TRUE)) {
  adj <- list(2L, c(1L, 3L), c(2L, 4L), 3L)
  fit.graph.trend.filtering(
    adj, y = c(0, 0.2, 1.8, 2), lambda.grid = 0.3,
    lambda.selection = "fixed", weight.rule = "unit"
  )
}
#> 
#> Graph Trend-Filtering Fit
#> =========================
#> 
#> Vertices: 4; edges: 3
#> Order: 0; operator family: graph.laplacian.recursive
#> Weight rule: unit
#> Lambda selection: fixed; lambda: 3.0000e-01