NeurIPS 2024 · Graph Learning · Adversarial Robustness

Robust Graph Neural Networks via Unbiased Aggregation

Zhichao Hou¹ Ruiqi Feng¹ Tyler Derr² Xiaorui Liu^1†

¹North Carolina State University · ²Vanderbilt University · †Corresponding author

Paper (arXiv) Code Interactive demo BibTeX

Under adaptive attacks, the strongest robust GNNs (SoftMedian, TWIRLS, ElasticGNN) all behave like one model: ℓ₁ graph smoothing. ℓ₁ resists a few bad edges, but its estimate is biased, and every adversarial edge adds to the bias.

RUNG swaps the ℓ₁ penalty for an unbiased one (MCP) and solves the problem with a stepsize-free Quasi-Newton IRLS. Unrolled, each solver step is a GNN layer that reweights edges and cuts the ones connecting nodes with very different features. The demos below run that mechanism live in your browser.

Cora ML · adaptive local attack · budget 200% of node degree

Node classification accuracy (%) on the attacked target nodes (Table 1 of the paper).

The problem

Three defenses, one estimator

Under adaptive attacks, which target the victim model itself instead of a surrogate, most defenses are barely more robust than an undefended GCN.

Three models stand out: SoftMedian, TWIRLS and ElasticGNN. Their architectures look unrelated, yet their robustness curves nearly coincide, and they collapse together once the attacker can add more edges.

All three approximately solve the same problem: graph signal smoothing with an ℓ₁-type penalty on edge differences.

Model	Smoothing penalty	Type
SoftMedian		ℓ₁
TWIRLS		ℓ₁
ElasticGNN		ℓ₁
GCN / APPNP		ℓ₂ · not robust

Why ℓ₁ breaks

Every outlier pulls a little

Message passing estimates a node's feature from its neighbors, which is a mean estimation problem. Adversarial edges add outliers to that sample. Drag the outlier ratio and watch three estimators.

Demo 1

Mean estimation with outliers

Clean sample 𝒩(0, I) Outlier True mean ‖·‖₂² (mean) ‖·‖₂ (ℓ₁, median) MCP (RUGE)

Outlier ratio 30%

MCP threshold γ 3.0

Show IRLS path

Distance to the true mean

The mean moves linearly with the outlier ratio. The ℓ₁ median resists for a while and then drifts, because ℓ₁ shrinks every difference by a constant. MCP stops counting a point once it is farther than γ, so its estimate stays put until the outliers are almost the majority.

The fix

A penalty that stops growing

RUGE, the Robust and Unbiased Graph signal Estimator, keeps the smoothing objective and replaces the edge penalty with the Minimax Concave Penalty ρ_γ:

Eq. 3–4 · RUGE

For small differences ρ_γ behaves like ℓ₁, so normal neighbors are smoothed together. Past γ it is flat: a neighbor that far away adds a constant cost and exerts no pull. That is where the bias goes away.

The right plot is what actually enters the GNN. Each IRLS step weights edge (i, j) by W_ij = dρ/dy², which is exactly zero for y ≥ γ.

Demo 2

Penalty and edge weight

ρ(y): penalty on an edge difference

W(y) = dρ/dy²: edge weight in the layer

ℓ₂ (GCN / APPNP) ℓ₁ (SoftMedian / TWIRLS / ElasticGNN) MCP (RUNG)

Threshold γ 2.0

As γ → ∞, MCP becomes ℓ₁. As γ → 0, it approaches ℓ₀ and prunes almost every edge.

How RUNG works

Dissimilar neighbors lose their vote

We solve RUGE with Quasi-Newton IRLS, which is stepsize-free and decreases the objective at every step (Theorem 2). Unrolled, each step is one GNN layer:

Eq. 8 · RUNG layer

So a RUNG layer is a reweighted neighbor average. The weight W_ij is recomputed in every layer from the feature distance y_ij. Close neighbors count a lot, distant ones count less, and beyond γ an edge counts for nothing. An adversarial edge usually joins two nodes that look different, so it gets cut.

Demo 3

Drag the attacker away from node i

Node i and its clean neighbors Adversarial neighbor (drag it) Edge width = share of the update Pruned (W = 0)

Small crosses mark where node i lands under each penalty. Degree normalization is left out to keep the picture simple.

Edge widths shown for

Adversarial edges 2

MCP threshold γ 2.5

Distance y between node i and the attacker–

Attacker's share of node i's update

Results

RUNG holds up as the budget grows

Adaptive PGD attacks on Cora ML and Citeseer, averaged over 5 splits. Pick a dataset and an attack budget to rank every model.

Every model at one budget

RUNG (ours) ℓ₁-based: SoftMedian · TWIRLS · TWIRLS-T · RUNG-ℓ₁ Undefended: GCN · APPNP GNNGuard

Citation

BibTeX

@inproceedings{hou2024robust,
  title     = {Robust Graph Neural Networks via Unbiased Aggregation},
  author    = {Hou, Zhichao and Feng, Ruiqi and Derr, Tyler and Liu, Xiaorui},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year      = {2024}
}