Pith. sign in

REVIEW 3 cited by

What graph neural networks cannot learn: depth vs width

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1907.03199 v2 pith:GB6GRH25 submitted 2019-07-06 cs.LG stat.ML

Andreas Loukas This is my paper
classification cs.LGstat.ML
keywords depthgnnmpwidthgraphnetworksneuralpowerproblems
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNmp can lose a significant portion of their power when their depth and width is restricted. The proposed impossibility statements stem from a new technique that enables the repurposing of seminal results from distributed computing and leads to lower bounds for an array of decision, optimization, and estimation problems involving graphs. Strikingly, several of these problems are deemed impossible unless the product of a GNNmp's depth and width exceeds a polynomial of the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.

Discussion (0). Sign in to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Universality and Approximation Rates of Graph Neural Networks with Random Features

    cs.LG 2026-07 accept novelty 6.0 of 10

    PENNs with random node features universally approximate measurable perm-invariant/equivariant graph functions in probability, with explicit approximation rates for C^k targets.

  2. GNN-CNN: An Efficient Hybrid Model of Convolutional and Graph Neural Networks for Text Representation

    cs.CL 2025-07 conditional novelty 6.0 of 10

    A hybrid GNN-CNN text classifier with real-time graph generation and injected LLM embeddings achieves near-transformer accuracy at linear complexity.

  3. Future Link Prediction Without Memory or Aggregation

    cs.LG 2025-05 conditional novelty 6.0 of 10

    CRAFT replaces memory and aggregation with learnable node embeddings and destination-to-source-neighbor cross-attention, improving future link prediction on most of 17 temporal graph benchmarks.

Pith tools