---
kind: concept
slug: graph-structure-learning
title: Graph structure learning
summary: >-
  Graph structure learning lets a model decide which edges to use, or learns the adjacency from data, instead of taking the given graph as fixed. Covered: gating and pruning an observed graph with the task loss, and learning a dense adjacency from node embeddings. The trade-off: extra parameters and per-step cost, and the numbers are author-reported on different tasks.
tags: [graph-learning, learned-graph-structure, edge-sparsification, adaptive-adjacency, robustness, multivariate-forecasting]
papers: ["2011.07057", "2401.00423"]
related: [graph-neural-network, nuclear-norm-regularization, time-series-forecasting, self-attention, relational-graph-convolution, graph-transformer, dynamic-graph-embedding, adversarial-robustness]
status: draft
updated_at: 2026-11-01
---

## Overview

A graph model usually takes the adjacency matrix as an input it trusts. Graph
structure learning relaxes that trust in one of two ways. Either the model
keeps the given edges but learns how much each one should count, or it learns
the adjacency itself from the node features. In both cases the structure is
trained with the task loss, so the graph is chosen for the task and not by a
fixed rule [arxiv:2011.07057 §4.2] [arxiv:2401.00423 §4.3].

Two cards on wikillm list this concept. They use it for different jobs:
node classification on a citation graph with noisy edges [arxiv:2011.07057
§5.1], and multivariate forecasting where the relations between series are not
given [arxiv:2401.00423 §1]. The two sets of numbers do not compare, so read
each variant against its own baselines.

## Variants

### Gating and pruning an observed graph

The model keeps the given edges and attaches a small learned scorer to each
GNN layer. The scorer reads the two endpoint states of an edge and produces a
score for it [arxiv:2011.07057 §4.2.1]. A hard-concrete relaxation turns the
score into a keep-gate that is differentiable, and a stretch-and-clip step
makes some gates exactly zero [arxiv:2011.07057 §4.2.2] [eq. 3–4]. Two
penalties are added to the loss: an expected count of kept edges [eq. 5], and
a nuclear-norm term on the masked adjacency, approximated by its top-K
singular values with power iteration [arxiv:2011.07057 §4.3] [alg. 2].
Card: [PTDNet](/papers/2011.07057).

The authors report that the gain grows with the share of random edges they
add. With 20,000 random edges on Cora, the relative gain over the basic GCN
is 37.37% [arxiv:2011.07057 §5.3]. On the standard benchmarks the gains vary
by dataset: Cora with GCN goes from 0.811 to 0.828 and PPI with GCN from 0.660
to 0.803, with the standard deviations given in the table [arxiv:2011.07057
tab. 3]. DropEdge, which drops edges at
random without a learned scorer, is worse than the basic backbone in most of
their noisy cases [arxiv:2011.07057 §5.3] [fig. 3].

### Dense adjacency learned from node embeddings

Here no input graph is needed. Each time scale gets its own adjacency,
computed as a row softmax over the product of two trainable node-embedding
matrices passed through a ReLU [arxiv:2401.00423 §4.3] [eq. 6]. A Mixhop
graph convolution mixes each variable with its neighbours over a set of
adjacency powers [eq. 7]. The tables give the Mixhop order as 2
[arxiv:2401.00423 tab. 5], but the set of powers is not stated in the text.
Card: [MSGNet](/papers/2401.00423).

The ablation on Flight, averaged over horizons 96 and 336, shows MSE 0.195
for the full model and 0.302 when the learned graph is removed. With one
graph shared across scales the MSE is 0.213 [arxiv:2401.00423 tab. 2]. These
are the authors' numbers on one dataset. The average rank over eight
datasets is 1.813, against 2.750 for TimesNet [arxiv:2401.00423 tab. 1].

## When to use which

| Situation | Use | Why |
|---|---|---|
| A graph is given, some of its edges are likely wrong for the task, and labels are available | Gating and pruning an observed graph (PTDNet) | The scorer uses the task loss to decide per edge. Author-reported Cora GCN 0.828 against 0.811 for the basic model [arxiv:2011.07057 tab. 3]. |
| A graph is given and you need a cheap, task-blind baseline | Random edge dropping (DropEdge, described in the PTDNet paper) | No extra scorer, but the authors report it below the basic backbone in most noisy settings [arxiv:2011.07057 §5.3]. |
| No graph is given; the entities are series or variables whose relations you do not know | Dense adjacency learned from embeddings (MSGNet) | The relations are learned from the data, as in the ablation where removing them raises Flight MSE from 0.195 to 0.302 [arxiv:2401.00423 tab. 2]. |
| The relations may differ across time scales | One adjacency per scale (MSGNet) | The paper argues one graph is not enough when correlations depend on the time scale [arxiv:2401.00423 §1] [fig. 1]. Sharing one graph gave MSE 0.213 against 0.195 [tab. 2]. |
| Memory or latency is tight | Check cost before choosing | The learned dense adjacency grows with the number of variables. Electricity GPU memory rises from 13.04 GB at horizon 96 to 16.98 GB at 720, at batch size 32 [arxiv:2401.00423 tab. 7]. PTDNet's cost per step is not reported in its benchmarks. Its authors show only that run time rises with K [arxiv:2011.07057 §5.6]. |
| Need a graph that is exactly sparse at test time | Gating (PTDNet) | The hard-concrete clip gives exact zeros when γ < 0 [arxiv:2011.07057 §4.2.2]. |

## Implementation sketch

The two variants share the same pattern: a learned weight per edge or per
pair, then a message-passing step that uses it. The pseudocode below shows
one gated layer and one learned-adjacency mixing step. The shapes are for
orientation only.

```pseudocode
# Gated layer on an observed graph  [arxiv:2011.07057 §4.2]
# Input:  node states H (n, d), edge list E, adjacency A
# Output: new node states, and a penalty to add to the loss

def gated_layer(H, E, A):
    # Score each edge from its two endpoint states  [§4.2.1]
    alpha = score_mlp(H[E.src], H[E.dst])          # (|E|,)
    # Draw a relaxed keep-gate; stretch and clip  [eq. 3] [eq. 4]
    gate = hard_concrete(alpha, gamma, zeta, tau)  # (|E|,)
    # Penalise the expected number of kept edges  [eq. 5] [eq. 10]
    edge_penalty = sum(expected_kept(alpha))
    # Penalise the top-K nuclear norm of the masked adjacency  [§4.3]
    low_rank = top_k_nuclear(mask(A, E, gate), K)
    # Message passing on the masked graph  [§4.2.2]
    H_out = message_pass(H, mask(A, E, gate))      # (n, d')
    return H_out, edge_penalty, low_rank


# Learned adjacency for one time scale  [arxiv:2401.00423 §4.3]
# Input:  node features X (n, d), trainable E1, E2 (n, h)
# Output: mixed node features (n, d)

def adaptive_graph_mix(X, E1, E2, powers):
    # Learn the adjacency from two embedding tables  [eq. 6]
    A = softmax(relu(E1 @ E2.T), axis=1)           # (n, n)
    # Mix neighbours over several powers of A  [eq. 7]
    parts = [A_j @ X for j in powers]              # the set is not stated
    return mlp(concat([X] + parts))                # (n, d)
```

Points the papers leave open: the gate parameters γ, ζ and the temperature τ
are not given in the paper beyond their signs [arxiv:2011.07057 §4.2.2]. The
weights for the two penalties are given only for synthetic data
[arxiv:2011.07057 tab. 4]. The power set for the learned adjacency is not
stated in the text [arxiv:2401.00423 §4.3]. Decide these from the cited papers'
tables and from your own validation data, and report them.

## Contradictions

None known between these two cards. They test different tasks, node
classification and forecasting, and use different baselines, so their numbers
do not compare. Within the PTDNet paper, some gaps in its main table are
smaller than the reported standard deviations. For example, Cora with GCN gives
0.828 ± 0.026 for PTDNet against 0.821 ± 0.014 for NeuralSparse
[arxiv:2011.07057 tab. 3]. The authors describe their method as matching or
beating the baselines, and the gap alone does not show a win.

## Papers

- [PTDNet](/papers/2011.07057): learned edge gates on an observed graph with an edge-count penalty and a top-K nuclear-norm penalty.
- [MSGNet](/papers/2401.00423): one learned dense adjacency per FFT-selected time scale, mixed with Mixhop convolution.