What do Graph Neural Networks learn? Insights from Tropical Geometry

Tuan Anh Pham, Vikas GargNeurIPS 2024 · OpenReview

While the Weisfeiler-Leman (WL) test has successfully outlined what Graph Neural Networks (GNNs) cannot do—namely, distinguish certain non-isomorphic graphs—characterizing the exact class of functions they can learn has remained an open challenge. Existing theoretical frameworks often assume injective hash functions, yet real-world GNNs predominantly use non-injective ReLU activations.

This paper bridges this theory-practice gap by characterizing the functional space of ReLU Message Passing Neural Networks (MPNNs). Using the lens of tropical geometry, the authors prove that ReLU-based GNNs learn the exact same class of functions as standard feedforward networks, but with vastly different efficiency profiles depending on their aggregation strategies.

The Tropical Geometry Framework

To analyze ReLU networks, the authors appeal to tropical geometry, a branch of mathematics that replaces standard addition and multiplication with "max" and "plus" operations.

Through this framework, they establish a fundamental functional equivalence: ReLU MPNNs are equivalent to Tropical Rational Signomial Maps (TRSMs). Because TRSMs are already known to be equivalent to ReLU Feedforward Networks (FNNs), this proves that both architectures represent the same class of functions: Continuous Piecewise Linear Maps (CPLMs).

At a high level, a GNN is simply a specific way of structuring a piecewise linear function. Any function a ReLU GNN can learn, a ReLU FNN can also learn, and vice versa. The critical difference lies in their geometric complexity and efficiency.

Summary of the paper's theoretical contributions, mapping key findings to specific theorems and propositions.

Key Insights: Geometric Complexity and Aggregation

To measure the efficiency of these networks, the authors analyze their "geometric complexity"—the number of distinct linear regions a network can create in the input space. More regions generally imply a more flexible and expressive model.

  • The Power of Max Aggregation: One of the most striking findings is that coordinate-wise max aggregation yields significantly higher geometric complexity than sum aggregation. In the tropical geometry framework, max allows the geometric complexity to grow exponentially with the graph's degree, whereas sum is much more restrictive. This provides a rigorous theoretical justification for the empirical success of max-pooling in GNNs.
  • Connectivity Matters: The expressive budget of a GNN is directly tied to the graph's structure. Specifically, the complexity bounds are influenced by the maximum degree and the total number of edges in the graph.
  • Decision Boundaries as Hypersurfaces: The authors characterize the decision boundaries of GNNs for node and graph classification as tropical hypersurfaces. These are the sets of points where two or more "tropical monomials" (the basic building blocks of these functions) reach a tie for the maximum value.

Architectural Trade-offs and New Bounds

The paper provides the first general upper and lower bounds on the number of linear regions for popular architectures like GraphSAGE and GIN.

By introducing four novel MPNN abstractions (Local, Global, Constant, and Hybrid) designed to represent any tropical signomial function, the authors establish clear architectural trade-offs:

  1. Layers vs. Parameters: MPNNs generally require fewer layers than FNNs to represent complex tropical functions (especially when using max aggregation). However, FNNs often require fewer total trainable parameters.
  2. Hybrid Efficiency: A proposed "Hybrid" architecture proves particularly efficient, requiring only one message-passing layer and one feedforward layer to represent any tropical signomial function with a highly optimized parameter count.

Limitations and Open Questions

Because this work is purely theoretical, it focuses on mathematical proofs rather than empirical benchmarks. This leaves several open questions for future research:

  • Theoretical Assumptions: The upper bounds for geometric complexity rely on simplifying assumptions, such as input graphs having a fixed structure.
  • The Optimization Gap: The paper characterizes what these networks can represent, but not necessarily what they will learn in practice. The role of optimization algorithms (like Adam or SGD) in navigating this complex geometric landscape remains unknown.
  • Empirical Validation: It remains to be seen how theoretically efficient architectures, like the proposed Hybrid model, perform on noisy, real-world data.
  • Spectral Properties: The authors note that it is still unknown whether spectral properties of the graph (such as the Laplacian spectrum) influence geometric complexity.

Summary updated

Abstract

Graph neural networks (GNNs) have been analyzed from multiple perspectives, including the WL-hierarchy, which exposes limits on their expressivity to distinguish graphs. However, characterizing the class of functions that they learn has remained unresolved. We address this fundamental question for message passing GNNs under ReLU activations, i.e., the de-facto choice for most GNNs. We first show that such GNNs learn tropical rational signomial maps or continuous piecewise linear functions, establishing an equivalence with feedforward networks (FNNs). We then elucidate the role of the choice of aggregation and update functions, and derive the first general upper and lower bounds on the geometric complexity (i.e., the number of linear regions), establishing new results for popular architectures such as GraphSAGE and GIN. We also introduce and theoretically analyze several new architectures to illuminate the relative merits of the feedforward and the message passing layers, and the tradeoffs involving depth and number of trainable parameters. Finally, we also characterize the decision boundary for node and graph classification tasks.
BibTeX
@inproceedings{pham2024what,
  author = {Tuan Anh Pham and Vikas Garg},
  title = {{What do Graph Neural Networks learn? Insights from Tropical Geometry}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=Oy2x0Xfx0u},
}
Figure