Node regression with graph KANs

library(thangldKANr)

Model

Each layer first averages node states over neighborhoods with \(\hat A = D^{-1/2}(A + I)D^{-1/2}\) and then applies a Kolmogorov-Arnold layer with Chebyshev edge functions to every node:

\[H^{(l)} = \mathrm{KAN}_l(\hat A H^{(l-1)}), \qquad \mathrm{KAN}_l(U)_{v,j} = \sum_i \sum_{k=0}^{K} c_{i,j,k} T_k(\tanh U_{v,i}).\]

This is the “aggregate, then KAN” order of graph KANs (Kiamari et al., 2024). An L-layer network sees the L-hop neighborhood of a node. Without a graph (graph = NULL, identity \(\hat A\)) the model is a node-wise Chebyshev KAN, the baseline that tells whether the graph helps.

With self_branch = TRUE each layer receives the node’s own state next to its neighborhood mean, \(H^{(l)} = \mathrm{KAN}_l([H^{(l-1)}, \hat A H^{(l-1)}])\) (the GraphSAGE update), so a deep network can still use one hop or the node’s own features only.

The graph model covers transductive node regression on one graph: all node features are propagated, the loss uses the training nodes only, the validation nodes are used for early stopping, and the labels of other nodes are never read. Standardization constants come from the training nodes.

A simulated graph

There is no graph dataset in base R, so this example uses the stochastic block model simulator. The target depends on one-hop neighborhood means.

g <- thangld_graph_kan_simulate(300, p_in = 0.08, p_out = 0.005, seed = 1)
a <- thangld_graph_kan_adjacency(g$adjacency)
u <- a %*% g$x
set.seed(2)
y <- sin(1.5 * u[, 1]) + 0.5 * u[, 2]^2 + rnorm(300, sd = 0.05)
train <- 1:180; val <- 181:240; test <- 241:300

The base R backend (backend = "r") is used so the vignette builds without libtorch.

fit_g <- thangld_graph_kan_fit(thangld_graph_kan(c(2, 1), degree = 5, seed = 1), g$x, g$adjacency, y,
                       train, val, epochs = 600, lr = 0.02, patience = 60, backend = "r")
fit_0 <- thangld_graph_kan_fit(thangld_graph_kan(c(2, 1), degree = 5, seed = 1), g$x, NULL, y,
                       train, val, epochs = 600, lr = 0.02, patience = 60, backend = "r")
fit_g
#> Graph KAN: widths 2 -> 1 | layer input A_hat H with A_hat = D^-1/2 (A + I) D^-1/2 | edges: Chebyshev K=5 
#> Fitted on 300 nodes: 180 train, 60 validation | backend r | best epoch 600 of 600
rbind(graph = thangld_graph_kan_metrics(y[test], predict(fit_g)[test]),
      no_graph = thangld_graph_kan_metrics(y[test], predict(fit_0)[test]))
#>                rmse        mae        r2
#> graph    0.08694136 0.06820108 0.9861789
#> no_graph 0.60694967 0.50576664 0.3264123
h <- fit_g$history
plot(h$epoch, h$train_loss, type = "l", log = "y", xlab = "epoch", ylab = "MSE (model scale)")
lines(h$epoch, h$val_loss, col = 2)
legend("topright", c("train nodes", "validation nodes"), col = 1:2, lty = 1, bty = "n")

Deeper networks and the self branch

In the plain architecture every layer propagates, so a two-layer network averages over two hops. On the one-hop target that hurts; the self branch removes the problem:

fit2 <- function(sb) thangld_graph_kan_fit(thangld_graph_kan(c(2, 4, 1), degree = 3, self_branch = sb,
                                             seed = 1), g$x, g$adjacency, y, train, val,
                                   epochs = 600, lr = 0.02, patience = 60, backend = "r")
rbind(plain_2layer = thangld_graph_kan_metrics(y[test], predict(fit2(FALSE))[test]),
      self_branch_2layer = thangld_graph_kan_metrics(y[test], predict(fit2(TRUE))[test]))
#>                          rmse        mae        r2
#> plain_2layer       0.31175583 0.25493992 0.8222875
#> self_branch_2layer 0.08924431 0.06889142 0.9854370

Cautions

Validation

thangld_graph_kan_validate() checks the normalized adjacency, the forward pass against explicit neighbor loops, analytic gradients against finite differences, permutation equivariance, the identity-graph reduction and save/load; torch checks are added when the runtime is installed.

v <- thangld_graph_kan_validate("r")
v[, c("check", "pass")]
#>                                                             check pass
#> 1         normalized adjacency vs explicit loop (edge list input) TRUE
#> 2                     edge list and adjacency matrix inputs agree TRUE
#> 3                           Chebyshev recurrence vs cos(k acos z) TRUE
#> 4            oracle vs naive loops (neighbor sums, cos(k acos z)) TRUE
#> 5                coefficients vs central difference O4 (h=0.0001) TRUE
#> 6               node features vs central difference O4 (h=0.0001) TRUE
#> 7                 coefficients vs central difference O4 (h=1e-05) TRUE
#> 8                node features vs central difference O4 (h=1e-05) TRUE
#> 9                 coefficients vs central difference O4 (h=1e-06) TRUE
#> 10               node features vs central difference O4 (h=1e-06) TRUE
#> 11                self branch [H, A_hat H]: oracle vs naive loops TRUE
#> 12  self branch: coefficients vs central difference O4 (h=0.0001) TRUE
#> 13 self branch: node features vs central difference O4 (h=0.0001) TRUE
#> 14   self branch: coefficients vs central difference O4 (h=1e-05) TRUE
#> 15  self branch: node features vs central difference O4 (h=1e-05) TRUE
#> 16   self branch: coefficients vs central difference O4 (h=1e-06) TRUE
#> 17  self branch: node features vs central difference O4 (h=1e-06) TRUE
#> 18               permutation equivariance f(PX, PAP') = P f(X, A) TRUE
#> 19                       identity graph = node-wise Chebyshev KAN TRUE
#> 20          self branch, identity graph = node-wise KAN on [X, X] TRUE
#> 21   self branch with zero neighbor coefficients = graph-free KAN TRUE
#> 22                             predictions before vs after reload TRUE
#> 23      basis "rbf": gradients vs central difference O4 (h=1e-05) TRUE
#> 24 basis "legendre": gradients vs central difference O4 (h=1e-05) TRUE
#> 25  basis "wavelet": gradients vs central difference O4 (h=1e-05) TRUE
#> 26 basis "rational": gradients vs central difference O4 (h=1e-05) TRUE
#> 27   basis "hybrid": gradients vs central difference O4 (h=1e-05) TRUE
#> 28   basis "jacobi": gradients vs central difference O4 (h=1e-05) TRUE
#> 29     basis "relu": gradients vs central difference O4 (h=1e-05) TRUE