When a Message-Passing Neural Network (MPNN) computes a representation for a node, it doesn't "see" the graph as a global adjacency matrix. Instead, it sees a recursive expansion of neighborhoods. From the perspective of a single node, the graph unfolds into a hierarchical structure where the node itself is the root, its neighbors are its children, and their neighbors are the grandchildren.
This structure is known as a computation tree (or unfolding tree). Recent research suggests that these trees are not just a byproduct of message passing, but the fundamental unit of information that determines what a GNN can learn, how it generalizes, and how it can be transferred across different domains.
The Graph as a Forest of Trees
In a standard GNN, each layer of message passing corresponds to one level of depth in a computation tree. If a GNN has $L$ layers, the final embedding of a node is a function of a tree of depth $L$.
Giuseppe Alessio D’Inverno and Maria Lucia Sampoli demonstrate in On the approximation capability of GNNs in node classification/regression tasks that this tree representation is the key to GNN expressivity. They show that GNNs are universal approximators for node-level functions precisely because they can encode these unfolding trees into unique feature vectors. By using injective aggregation functions, a GNN effectively maps each unique tree structure to a unique point in embedding space, mirroring the behavior of the 1-Weisfeiler-Lehman (1-WL) isomorphism test.
From this perspective, a whole graph can be viewed as a distribution of computation trees. As Levi Rauchwerger, Stefanie Jegelka, and Ron Levie argue in Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs, understanding a GNN’s performance requires looking at how it processes these tree distributions. This framework allows researchers to bridge the gap between theoretical expressivity (can the GNN distinguish two graphs?) and practical generalization (will it work on unseen data?).
A Universal Vocabulary for Transfer Learning
If computation trees are the "atoms" of graph structure, can we use them to build a universal language for graphs? This is the core intuition behind the work of Zehong Wang and colleagues.
In GFT: Graph Foundation Model with Transferable Tree Vocabulary, they introduce a "tree vocabulary" by quantizing common computation tree structures into discrete tokens. Just as Large Language Models use a fixed vocabulary of sub-word tokens to handle any text, GFT uses a vocabulary of structural trees to handle any graph. Because a specific local motif (like a star-shaped neighborhood) looks the same whether it appears in a molecule or a social network, this tree-based approach enables a single model to generalize across vastly different domains.
Compressing Graphs via Tree Mining
The computation tree perspective also offers a powerful way to handle massive datasets. If a graph is just a collection of trees, many of which are redundant or structurally similar, we can "distill" the graph by keeping only the most representative trees.
Mridul Gupta and Sayan Ranu leverage this in Mirage: Model-agnostic Graph Distillation for Graph Classification. Instead of traditional distillation methods that rely on expensive gradient matching, MIRAGE identifies frequent computation trees in the training set. By summarizing a dataset as a small collection of these trees, they can compress data by orders of magnitude while maintaining the structural patterns that GNNs need to learn.
Eliminating Redundancy in the Tree
While the computation tree is a powerful abstraction, it can also be inefficient. In a standard GNN, the same node might appear multiple times in a single computation tree if there are cycles in the graph, leading to redundant calculations and "oversquashing" of information.
Franka Bause and Nils Morten Kriege address this in On the Two Sides of Redundancy in Graph Neural Networks. They propose DAG-MLP, which prunes these redundant message-passing trees into compact Directed Acyclic Graphs (DAGs). By merging identical sub-trees, they maintain the same expressive power as the full computation tree but with much higher computational efficiency and less information loss.
Why It Works
The computation tree perspective works because it aligns the mathematical definition of a GNN with its structural constraints. By treating the local, recursive expansion of a node as the primary object of study, researchers have moved away from viewing graphs as static global objects and toward viewing them as dynamic, hierarchical collections of local patterns. This shift has provided the tools to prove universality, enable cross-domain transfer, and optimize the very architecture of graph learning.