Graph structure learning

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 2011.07057 §4.2 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 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 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 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 2011.07057 §4.3 alg. 2. Card: PTDNet.

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% 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 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 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 2401.00423 tab. 5, but the set of powers is not stated in the text. Card: MSGNet.

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 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 2401.00423 tab. 1.

When to use which

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.

# 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 2011.07057 §4.2.2. The weights for the two penalties are given only for synthetic data 2011.07057 tab. 4. The power set for the learned adjacency is not stated in the text 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 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: learned edge gates on an observed graph with an edge-count penalty and a top-K nuclear-norm penalty.
• MSGNet: one learned dense adjacency per FFT-selected time scale, mixed with Mixhop convolution.