What graph neural networks cannot learn: depth vs width

Andreas Loukas

Source-linked AI summary

What graph neural networks cannot learn: depth vs width

Andreas Loukas

arXiv:1907.03199v2Jul 6, 2019cs.LGstat.ML

TL;DR

The paper asks how expressive message-passing graph neural networks are under unrestricted and restricted depth and width. It provides universality conditions and repurposes distributed-computing results to derive lower bounds, showing that many graph problems require polynomial depth-width capacity.

Problem
The paper examines the expressive power and limitations of message-passing graph neural networks, including whether restricted depth and width prevent solving graph problems.
Method
The paper establishes Turing-universality conditions and develops a technique that repurposes seminal distributed-computing results into GNNmp impossibility bounds.
Results
GNNmp with depth-width product dw = ˜Ω(n^δ), δ ∈ [0.5, 2], cannot solve a range of decision, optimization, and estimation problems, while sufficient conditions yield Turing universality.
Takeaways & Limitations
The power of GNNmp depends critically on capacity, with depth and width trading off and discriminative node attributes remaining important.
Takeaways & Limitations
The empirical experiments support qualitative trends rather than tight lower-bound verification because optimization may have reached a local minimum.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies what message-passing graph neural networks can compute and how their depth, width, attributes, and layer expressiveness constrain that power. It establishes universality under strong conditions and lower bounds showing that many graph problems require substantial capacity.

Main results: GNNmp are shown to be Turing universal when layers are sufficiently expressive and wide, the network is sufficiently deep, and nodes can uniquely distinguish each other.The universality result is obtained by establishing equivalence with the Turing-universal LOCAL model.
Main results: Restricting capacity dw causes GNNmp to lose substantial expressive power across decision, optimization, and estimation problems on graphs.The paper repurposes distributed-computing impossibility results to derive these lower bounds.
Main results: The results cover graph classification-relevant detection and verification tasks, as well as graph optimization and estimation problems.Examples include cycle detection, subgraph verification, shortest paths, minimum cut, minimum spanning tree, diameter, and girth.
Main results: dw = ˜Ω(n^δ), with δ ∈ [0.5, 2], is required for solving a range of graph problems involving n-node graphs.The dependence on graph size remains significant even for apparently local tasks and approximate solutions.
Relation to previous impossibility results: The paper presents the first impossibility results explicitly connecting GNNmp depth and width with graph properties while extending beyond isomorphism.The bounds address decision, optimization, and estimation problems.
Limitations: The lower bounds are worst-case, assume sufficiently powerful layer functions, and assume nodes can uniquely identify each other.Non-worst-case depth-versus-width bounds remain open, and discriminative node attributes can substitute for identifiers across graphs.

2 THE GRAPH NEURAL NETWORK COMPUTATIONAL MODEL

The computational model represents graph neural networks as message-passing systems that update node states layer by layer. Their operation is determined by messaging, update, and readout functions, with depth controlling layers and width controlling state dimension.

Model definition: A GNNmp takes an attributed graph as input, with node vectors and optional edge attributes encoding relevant information.Edge attributes can encode properties such as edge direction.
Message passing: Each layer sends messages along directed edges and updates every node by aggregating its state with incoming-neighbor messages.The model can return either one vector per node or a single vector per graph.
Model functions: The messaging, update, and readout functions primarily determine GNNmp operation, and the messaging and update functions are assumed to be general functions.They are instantiated by feed-forward neural networks and can approximate general vector-to-vector mappings under universal approximation results.
Depth and width: Depth d is the number of layers, while width w is the largest dimension of any node state across layers and nodes.Greater depth gives nodes opportunities to learn about more distant parts of the graph.
Representation assumptions: The analysis represents manipulated variables in finite precision using p = Θ(log n) bits so nodes can store unique identifiers.This finite-precision assumption is stated as convenient rather than strictly necessary.

3 SUFFICIENT CONDITIONS FOR TURING UNIVERSALITY

The paper derives Turing universality for sufficiently expressive, deep, and wide GNNmp with uniquely identified nodes. The proof establishes expressive equivalence with the distributed-computing model LOCAL, allowing distributed-algorithm results to transfer to GNNmp.

Sufficient conditions: A GNNmp is computationally universal when it has sufficient width and depth, uniquely identifiable nodes, and sufficiently expressive within-layer functions.Universality means computing anything a Turing machine can compute on an attributed graph.
Equivalence with LOCAL: The derivation establishes equivalence between GNNmp and LOCAL, a classical distributed-computing model that is itself Turing universal.This equivalence transfers LOCAL's expressive-power perspective to message-passing graph networks.
LOCAL model: In LOCAL, computation unfolds in synchronous rounds where nodes receive messages, update their states locally, and send messages to neighbors.Unlike CONGEST, LOCAL imposes no bound on message size.
Information propagation: When depth satisfies d ≥ δG, every node can effectively make decisions using information from the entire graph, provided computation and memory are not limiting factors.Here δG is the graph diameter.
Formal condition: The formal universality condition requires unique node identifiers, Turing-complete messaging and update functions, depth at least the graph diameter, and unbounded width.These conditions jointly apply to connected attributed graphs.
Significance: Universality matters because it removes blind spots in the hypothesis space and shows how design choices affect that space.The paper then examines how relaxing depth and width causes GNNmp to lose a significant portion of their power.
Readout scope: A readout function is excluded from the main universality result because a sufficiently powerful readout could reconstruct the input from one-hop information and perform arbitrary computation.With readout, a one-layer network of O(∆) width could compute any Turing-computable function under the stated construction.

4 IMPOSSIBILITY RESULTS AS A FUNCTION OF DEPTH AND WIDTH

This section translates distributed-computing impossibility results into depth–width lower bounds for message-passing GNNs, covering decision, optimization, and estimation problems. The bounds show that restricted capacity can make even approximate or apparently simple graph tasks infeasible.

General framework: The CONGEST-to-GNNmp translation shows that a problem requiring d rounds with b-bit messages cannot be solved by a GNNmp of corresponding depth and width w = O(b/log n).The logarithmic factor accounts for the precision needed to represent unique node identifiers.
Decision problems: Zero-error graph classifiers must respect the same lower bounds as the corresponding decision problems when the class definition is supplied.The network must output a Boolean decision for every node before accepting or rejecting the graph-level premise.
Decision problems: For decision problems, constant-width GNNmp may require Ω(√n) depth to verify connectivity, while cycle detection requires Ω(√n/(w log n)) or Ω(n/(w log n)) depth for even or odd cycles.The odd-cycle bound is linear in n up to width and logarithmic factors.
Optimization problems: Even approximate solutions remain difficult: constant-width GNNmp cannot approximate minimum cut, shortest s-t path, or minimum spanning tree within any constant factor.The section emphasizes that these are polynomial-time problems, yet their worst-case approximation still faces depth–width barriers.
Optimization problems: For optimization, constant-width GNNmp requires depth Ω(n^2/log^2 n) for minimum vertex cover, maximum independent set, and perfect coloring.These lower bounds apply even when the optimization problems are interpreted as node- or edge-classification tasks.
Implications: The optimization lower bounds can exceed graph diameter by a quadratic factor, suggesting that distributed decision-making in GNNmp does not always outperform centralized paradigms.This conclusion holds even when each layer is allowed exponential computation time.
Estimation problems: For estimation, depth must satisfy Ω(n/(w log n) + δG) for exact diameter and Ω(√n/(w log n) + δG) for diameter and girth approximation.The approximation factors are 3/2 for diameter and 2 for girth; the δG term reflects the need for global information.

5 EMPIRICAL EVIDENCE

Experiments on 4-cycle classification show that discriminative node attributes and sufficient capacity are central to generalization, while depth and width behave largely interchangeably.

Interpretation: The empirical study cannot establish tightness because optimization may return local minima when searching over neural-network parameters.Its results should therefore be interpreted qualitatively as comparisons with theoretical trends.
Capacity and graph size: 240 networks were evaluated across five graph distributions, three widths, four depths, and four independent training iterations.The experiment varied graph size, width, depth, and initialization-dependent training outcomes.
Capacity and graph size: 100% test accuracy was consistently achieved for n ≤ 16 with unique ids, but the strongest networks stayed below 95% for n > 16.For n = 40, the best accuracy was below 80%.
Capacity and graph size: Test accuracy decreased as graph size n increased for networks with the same capacity dw, despite the cycle length remaining four.This pattern agrees with the predicted dependence on dw and n.
Effect of anonymity: Anonymous or degree-based attributes could not support cycle detection, whereas unique node ids enabled exact solutions but inconsistent ids prevented generalization.The graphs used a fixed node set with different edges, and node ids were supplied as one-hot input features.
Exchangeability of depth and width: Almost every network with dw ≥ critical solved the task, while no network with normalized capacity below one did so; depth and width were empirically exchangeable.The theory guarantees dw = ˜Ω(√n) as necessary but not sufficient, so the empirical phase transition is qualitative evidence rather than a tight-bound verification.

6 CONCLUSION

The paper establishes both computational universality and capacity-dependent impossibility for message-passing graph neural networks, with discriminative attributes contributing to their power.

Conclusion: Under sufficient conditions, GNNmp can compute any function on their input that a Turing machine can compute.The universality result concerns computability rather than approximation over only selected function classes.
Conclusion: Restricting capacity dw causes GNNmp to lose power across graph-theoretic decision, optimization, and estimation problems.The paper develops a technique that repurposes impossibility results from distributed computing for GNNmp.
Conclusion: dw = ˜Ω(n^δ), with δ ∈ [0.5, 2], is necessary for solving a range of graph problems.Here, ˜Ω suppresses logarithmic factors.
Conclusion: The results show that GNNmp power depends critically on capacity and illustrate the importance of discriminative node attributes.These conclusions connect architectural capacity and input attributes to graph-learning expressiveness.

B.1 PROOF OF THEOREM 3.1

The proof establishes equivalence between GNNmp layers and distributed-computing aggregation procedures by constructing each aggregation function from the other.

Proof strategy: The proof represents each node state as a vector and compares the inputs processed by GNNmp and distributed aggregation functions.Vectors and strings can encode one another without loss of generality.
Conclusion of proof: Each GNNmp layer is therefore equivalent to one round of the LOCAL model, completing the claimed equivalence.The proof compares the two models after dropping layer and round indices.
Aggregation equivalence: For the forward direction, any aggregation function AGG can be implemented by composing it with a transformation that augments each neighbor element with the central node state.The transformation identifies the central node state and appends it to every multiset element.
Aggregation equivalence: For the backward direction, an aggregation function can be obtained by deleting the central node state from each multiset element before applying the distributed algorithm.This constructs AGG = ALG ◦ h from a given ALG.

B.2 PROOF OF COROLLARY 3.1

The universality proof uses the LOCAL model: after enough communication rounds, each node can contain the entire graph and then compute the desired function.

Proof of universality: Using union aggregation, after d = δG LOCAL rounds each node state contains the entire graph.The same reasoning applies to node and edge attributes.
Proof of universality: A final computation can then be applied to the complete graph representation held at each node.This computation is represented by the final algorithmic step in the LOCAL construction.
Proof of universality: Universality of GNNmp follows from the established equivalence between LOCAL rounds and GNNmp layers.The equivalence transfers the LOCAL construction to message-passing graph neural networks.

B.3 PROOF OF THEOREM 4.1

The proof transfers distributed-computing lower bounds between LOCAL and GNNmp models by mapping node states to network representations, yielding a depth–width constraint.

Model equivalence: LOCAL and GNNmp models are equivalent when no additional memory or width restrictions are imposed.Their node states correspond one-to-one at each layer or level, so state-size impossibility results transfer between models.
Lower-bound transfer: A CONGEST depth lower bound implies a LOCAL lower bound when bounded messages are simulated with bounded node states.The simulation sends the input directly and uses a universal algorithm layer to reproduce the bounded-message computation.
Lower-bound transfer: The simulation requires at least b − log2 n bits of node state when messages are bounded by b bits.The log2 n term represents the node identifier, while the remaining state encodes the message information.
Depth–width consequence: The GNNmp width must be at least (b − log2 n)/p when a problem cannot be solved in fewer than d bounded-message rounds.This follows because p layers of width below that threshold would induce a prohibited LOCAL algorithm.

C AN EXPLANATION OF THE LOWER BOUNDS FOR CYCLE DETECTION AND DIAMETER ESTIMATION

The lower bounds reduce graph problems to two-party set disjointness, encoding private strings into separated graph regions whose connectivity determines the target property.

Reduction framework: Alice and Bob encode secret bit strings into private graph topologies connected by a small cut.A solution to the graph problem would reveal whether the two encoded sets are disjoint.
Lower-bound constructions: Figure 3 illustrates lower-bound graphs for even k-cycle detection and diameter estimation, with only selected edges shown to reduce occlusion.The examples include a 10-cycle lower-bound graph and a diameter lower-bound graph.
Cycle detection: Ω(√n/b) CONGEST depth is necessary to decide whether a graph contains a cycle of length k in the bipartite construction.The construction uses p = √q nodes and yields n = Θ(p^2), producing the stated lower bound.
Cycle detection: GNNmp requires d = Ω(√n/(w log n)) depth for the same cycle-detection problem.Here w denotes the GNNmp width, linking the distributed-computing bound to the network’s depth and width.
Diameter estimation: The diameter construction makes the graph diameter at least five exactly when the encoded sets are disjoint.Because the cut has O(log q) edges, computing diameter requires d = Ω(n/(w log2 n)) GNNmp depth.

D THE COST OF ANONYMITY

Node identifiers substantially affect message-passing power: identifiable nodes can reconstruct topology locally, whereas anonymous nodes may be unable to distinguish graphs containing cycles.

Identifiable nodes: With unique identifiers, a node can reconstruct the entire graph topology after two message-passing rounds in the toy example.After one round it knows its neighbors; after two rounds the red node has reconstructed the graph.
Anonymous nodes: Without identifiers, the red node cannot determine whether the graph contains cycles after two rounds.At least two distinct topologies remain consistent with its observations because neighbors cannot be distinguished by their mutual adjacency.