Glass-Box Graph Additive Models at Scale via All-Distances Sketches

Some graph models are interpretable by construction. The Graph Neural Additive Network (GNAN) is one: it predicts a node's label as a sum of simple one-dimensional curves, one curve per feature, each weighted by a learned curve over graph distance. Every part of the model can be drawn and inspected, and it matches black-box graph networks on most small benchmarks. Its weakness is cost. Each prediction sums over every other node at its exact shortest-path distance, so it needs all-pairs distances, and that rules out graphs with millions of nodes.

All-distances sketches solve the matching problem in graph algorithms. An all-distances sketch is a small, randomly chosen, distance-ordered sample of each node's neighborhood. Paired with an inverse-probability weighting, it gives an unbiased estimate of exactly this kind of distance-weighted sum in near-linear time. We propose to make the sketch the model's actual computation, not an approximation added afterward. The resulting model keeps GNAN's functional form exactly, trains end to end on graphs with millions of nodes, and gives per-prediction explanations that are faithful by construction. Each explanation is a short weighted list of the specific nodes that produced the output.

Core Claim

The Intelligible and Effective Graph Neural Additive Networks predicts

$$\hat{y}_u = \mu + \sum_k f_k(x_{u,k}) + \sum_{v \neq u} \rho(d(u,v)) \sum_k f_k(x_{v,k}),$$

where $f_k$ is a learned univariate shape function for feature $k$, $d(u,v)$ is the hop distance, and $\rho$ is a learned distance-decay curve. GNAN reports 86.9% on PubMed and is best or second-best on 9 of 13 benchmarks, but the double sum makes it quadratic or worse.

The last term is a sum over $v$ of a function of $v$'s features and of $d(u,v)$. That is precisely the class of "distance-based statistics" that All-Distances Sketches, Revisited: HIP Estimators for Massive Graphs Analysis estimates. Its historic inverse probability (HIP) estimator gives each sketch entry a weight $a_{uv} = 1/\tau_{uv}$. Here $\tau_{uv}$ is the probability, conditioned on the random ranks of nodes closer to $u$ than $v$, that $v$ entered $u$'s sketch. The estimator is then

$$\widehat{S}_u = \sum_{v \in \mathrm{ADS}(u)} a_{uv}\, \rho(d(u,v)) \sum_k f_k(x_{v,k}).$$

It is unbiased for any fixed $\rho$ and $f_k$, and the cited paper shows it achieves at least a factor-of-two variance reduction over earlier MinHash estimators.

The point we exploit is that once the sketch is built, the weights $a_{uv}$ and distances are constants. $\widehat{S}_u$ is therefore linear in $\rho$ and $f_k$, so gradients pass through it unchanged.

Our claim has three parts:

  1. Training GNAN directly on $\widehat{S}_u$ yields shape and decay curves close to those of exact GNAN where exact GNAN can be run.
  2. It runs on ogbn-products-scale graphs where exact GNAN cannot.
  3. For decaying $\rho$, it outperforms simpler sampling schemes at equal memory.

Part 3 holds for a specific reason. A bottom-$k$ sketch keeps nearly all close nodes and thins out distant ones, which is the shape of sample a decaying weight function needs.

Research Program

Construction. We build bottom-$k$ all-distances sketches with pruned breadth-first searches in random rank order, as in Reverse Ranking by Graph Structure: Model and Scalable Algorithms. Each sketch has about $k \ln n$ entries per node. For each entry we store the node id, the hop distance, and the HIP weight.

Training. Training is mini-batch over target nodes. Each target touches only its sketch entries, so per-step cost is independent of graph size. The sketch is a fixed random design, so the model could in principle fit its particular noise. To guard against this we precompute $R$ independent sketches, draw one per epoch, and average over all $R$ at inference.

Analysis. We will study four quantities:

  1. Prediction variance across hash seeds. This is the model's only source of randomness.
  2. Curve fidelity. The L2 distance between learned $f_k$ and $\rho$ under sketching and under exact distances, as a function of $k$.
  3. The bias induced by a nonlinear loss on an unbiased aggregator. We will treat this empirically and with a second-order bound.
  4. Memory. Storing all-distances sketches for LiveJournal took 31.5 GB in the reverse-ranking work. We therefore cap $k$ and report accuracy against the memory budget rather than hiding it.

The explanation. A node's prediction decomposes exactly into its own feature curves plus at most $k \ln n$ sketch contributions, each given as $a_{uv}\rho(d)\sum_k f_k(x_{v,k})$. This is the model's literal computation, not a post-hoc approximation.

Baselines

Exact GNAN. We run it with full shortest-path matrices on Cora, Citeseer, and PubMed, using GNAN's protocol, and on ogbn-arxiv if memory permits. It is the reference for fidelity: the same functional form without approximation. The reported number is 86.9% on PubMed from the GNAN paper. Success means coming within one accuracy point while the learned curves stay visually and numerically close.

Strongest black box at scale. The scale comparison is against GraphSAINT and GraphSAGE on ogbn-products. Open Graph Benchmark reports 79.08% test accuracy for GraphSAINT and 78.50% for GraphSAGE. We will rerun both with official code and the same tuning budget as our model.

We do not expect to beat GraphSAINT outright. A glass-box model within about two points of it on a 2.4M-node graph would itself be the result. Exceeding GraphSAGE, whose 94% train and 78.5% test accuracy show a large generalization gap, is plausible, because additive models regularize strongly. No reported result was found on Lacuna for GNAN on any OGB node task.

Truncated exact GNAN. This is the "do nothing clever" reference: the same model restricted to exact 2-hop neighborhoods.

Landmark hybrid. This is the key ablation. It uses exact 1-hop neighbors plus $L$ uniformly sampled global nodes reached by $L$ breadth-first searches, weighted by $n/L$, with $L$ chosen so memory matches our sketch.

Bottom-$k$ with naive weights. The same sketch with naive uniform weights instead of HIP weights. This isolates the contribution of the estimator.

All variants share features, splits, optimizer, and a fixed hyperparameter search budget.

Why not just…?

Why not just truncate GNAN to a few hops and compute exactly? If the learned $\rho$ vanishes after two hops, truncation is cheap and exact. The trouble is that real graphs are small-world. Four Degrees of Separation found an average distance of 4.74 hops on Facebook, so 3-hop neighborhoods already cover much of a large graph. Truncation also fixes $\rho = 0$ by assumption instead of learning it. The truncated baseline tests this directly. If it matches our model on ogbn-products, the honest conclusion is that long-range decay does not matter there.

Why not just sample uniform landmark nodes? This is the real threat. Uniform sampling is simple and also unbiased. Its weakness is that a decaying $\rho$ puts most weight on nearby nodes, which a uniform sample rarely hits, so variance grows with graph size. The landmark-hybrid baseline at matched memory settles the question. If it wins, the sketch adds nothing, and we will report that.

Why not just train GraphSAINT and explain it with GNNExplainer? GNNExplainer approximates the model after training. Interpretable Prototype-based Graph Information Bottleneck reports that it has lower fidelity than built-in bottlenecks. Our explanations are the computation itself, so their fidelity is exact by definition. The cost is whatever accuracy gap remains, which we measure.

Why not just feed sketched overlap features into a linear model? This is the approach of Knowledge Graphs Can be Learned with Just Intersection Features, which reaches 0.781 MRR on WN18RR. It shows that sketch noise is tolerable, but its features are pairwise link statistics that ignore node features, which node classification needs. We will add a tabular model on hop-wise sketched cardinalities plus raw features as an additional reference.

Proposed Experiments

Fidelity on small graphs. On Cora, Citeseer, and PubMed we sweep sketch size $k \in \{4, 8, 16, 32, 64\}$. We report accuracy, the L2 deviation of the curves from exact GNAN, and the standard deviation across five hash seeds.

Scale. On ogbn-arxiv and ogbn-products we report accuracy, wall-clock time, and peak memory against GraphSAINT, GraphSAGE, the truncated model, and the landmark hybrid.

Decisive checks.

  1. At $k = 16$ or below, PubMed accuracy is within one point of 86.9%, and the decay curve $\rho$ keeps the qualitative shape learned by exact GNAN.
  2. At matched memory on ogbn-products, the HIP sketch beats both the landmark hybrid and naive-weight sketches in accuracy and in seed-to-seed variance of predictions.
  3. As $k$ grows, the curve deviation falls roughly as $1/\sqrt{k}$, the scaling expected from an unbiased estimator whose variance is inversely proportional to sample size.

A curve deviation that plateaus would point to the nonlinear-loss bias and would require averaging over multiple sketches during training.