# Universal Local Attractors on Graphs
## 2 Background
### Universal Approximation of AGFs  
Typically, GNNs are required to be equivariant or invariant under node permutations. These properties correspond to outputs following the node permutations or being independent of them, respectively. An AGF \(A(M,H)\) satisfies them if, for all attributed graphs \((M,H)\) with adjacency matrices \(M\) and node features \(H\),  
\[A(\sigma\,M,\sigma\,H) =\sigma A(M,H)\] (equivariance) \[A(\sigma\,M,\sigma\,H) =A(M,H)\] (invariance)  
where \(\sigma\) is a matrix that permutes node order. We treat permutation as an operator. In this work, we tackle only equivariance, given that reduction mechanisms across nodes (e.g., an average of all feature values across nodes) turn equivariance into invariance. These properties are not inherently covered by the universal approximation theorems of traditional neural networks, which GNNs aim to generalize. It is, then, of interest to understand the expressive power of these architectures given that they satisfy one of the properties. In this way, one may obtain a sense of what to expect from their predictive ability. Theoretical research has procured various universal approximation theorems for certain architectures that show either a general ability to approximate any AGF or the ability to differentiate graphs up to the Weisfeiler-Lehman isomorphism test of order k (WL-k), which is a weaker version of graph isomorphism. For example, WL-2 architectures can learn to at most recognize triangles but cannot necessarily differentiate between more complex structures, as shown in Figure 3. The folkore WL-k (FWL-k) test [14] has also been used as a non-overlapping alternative [15] (there is no clear distinction between the strengths of the two tests). Universal approximation is stronger than both in that it can perfectly detect isomorphism. Simple architectures, like GNNML1 [11], GCN [12], and APPNP [8], are at most as powerful as the WL-1 test in distinguishing between graphs of different structures, but remain popular for parsing large graphs thanks to their tractable implementations that take advantage of adjacency matrix sparsity to compute forward passes in times \(O(|\mathcal{E}|\,L)\), where \(|\mathcal{E}|\) is the number of graph edges and \(L\) the number of message-passing layers (usually 2, 5, 10, or 64 depending on the architecture and how well it tackles the oversmoothing problem). On the other hand, architectures like 1-2-3 GNN [16] and PPGN [15] satisfy the WL-3 test but come at the cost of high computational demands (e.g., millions of hidden dimensions) by considering all tuples or triplets of node combinations, in the last case exhibiting computational complexity \(\Theta(|\mathcal{V}|^{3})\), where \(|\mathcal{V}|\) is the number of nodes. For a summary on the expressive power of several architectures, refer to the work of [PERSON] et al. [11], who also introduce the GNNML3 architecture to overcome these limits with appropriate injection of spectral node features. In addition to WL-k or other types of limited expressiveness, some works tackle universal approximation over all AGFs. Historically, deep set learning [17] introduced universal approximation for equivariant and invariant functions over sets, and results  
Figure 3: Two non-isomorphic graphs that can be distinguished by FWL-2 but not by WL-1 or WL-2. were quickly generalized to graph structures. However, such powerful architectures also suffer from computational intractability, like unbounded tensor order for internal representations [18], and the tensor order of internal representations needing to be at least half the number of input feature dimensions rounded down [19]. Increasing tensor order dimensions is so computationally intensive that these works experimented with graphs of few nodes. An alternate research direction is to create MPNNs that, even though limited to WL-1 expressive power by themselves [16; 20], can be strengthened with additional components.