The Expressive Power of Graph Neural Networks: A Survey
Graph neural networks (GNNs) are effective machine learning models for many
graph-related applications. Despite their empirical success, many research
efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive
power. Early works in this domain mainly focus on studying the graph
isomorphism recognition ability of GNNs, and recent works try to leverage the
properties such as subgraph counting and connectivity learning to characterize
the expressive power of GNNs, which are more practical and closer to
real-world. However, no survey papers and open-source repositories
comprehensively summarize and discuss models in this important direction. To
fill the gap, we conduct a first survey for models for enhancing expressive
power under different forms of definition. Concretely, the models are reviewed
based on three categories, i.e., Graph feature enhancement, Graph topology
enhancement, and GNNs architecture enhancement.
Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, Zhong Liu
# The Expressive Power of Graph Neural Networks: A Survey

###### Abstract

Graph neural networks (GNNs) are effective machine learning models for many graph-related applications. Despite their empirical success, many research efforts focus on the theoretical limitations of GNNs, i.e., the GNNs expressive power. Early works in this domain mainly focus on studying the graph isomorphism recognition ability of GNNs, and recent works try to leverage the properties such as subgraph counting and connectivity learning to characterize the expressive power of GNNs, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for models for enhancing expressive power under different forms of definition. Concretely, the models are reviewed based on three categories, i.e., Graph feature enhancement, Graph topology enhancement, and GNNs architecture enhancement.

 Graph Neural Network, Expressive Power, Separation Ability, Approximation Ability.

## 1 Introduction

Graph neural networks (GNNs) have emerged as a prominent model in the field of deep learning, attracting extensive research interests [1, 2, 3]. GNNs have displayed superior ability in learning from graph data, and their variants have been extensively applied in numerous real-world scenarios, including recommendation systems [4], computer vision [5], natural language processing [6], molecular analysis [7], data mining [8], and anomaly detection [9]. For more introductions to the foundations and applications of GNNs, see references [10, 11, 12] for more details.

Compared to well-structured texts and images, graphs are irregular. A fundamental assumption behind machine learning on graphs is that the predicted targets should be invariant to the order of nodes on graphs. To match this assumption, GNNs introduce an inductive bias called permutation invariance [13]. Specifically, GNNs give outputs that are independent of how the node indices of the graph are assigned and the order in which they are processed, i.e., the model parameters are independent of the node order and are shared throughout the graph. Due to this new parameter sharing mechanism, we need new theoretical tools to study their expressive power. However, studying the expressiveness of GNNs faces many challenges. Firstly, most GNNs are usually used as black-box feature extractors for graphs, and it is unclear how well they can capture different graph features and topology. Secondly, due to the introduction of permutation invariance, the results of the classical universal approximation theorem of neural networks (NNs) [14, 15] cannot be directly generalized to GNNs [16, 17, 18]. In addition, in practice, the study of expressive power is related to a number of long-standing difficult problems in graph theory [19, 20]. For example, in the prediction of properties of chemical molecules, it is necessary to judge whether the molecular structure is the same or similar to that of a molecule with known properties, which involves the problem of graph/subgraph isomorphism judgement [19, 21] and graph matching [22, 23], etc. [24]

There exists a pioneering study of the expressive power of GNNs. Morris et al. [25, 26] and Xu et al. [27] introduced to use graph isomorphism recognition to explain the expressive power of GNNs, leading the trend to analyze the separation ability of GNNs. Maron et al. [16] and Chen et al. [28] introduced to use the ability of GNNs to approximate graph functions to account for their expressive power and further gave the set representation of invariant graph functions that can be approximated by GNNs, leading the trend to analyze the approximation ability of GNNs. While multiple studies have emerged in recent years that characterize and enhance the expressive power of GNNs, a comprehensive review in this direction is still lacking. Sato [29] explored the relationship between graph isomorphism testing and expressive power and summarized strategies to overcome the limitations of GNNs expressive power. However, they only describe the GNNs separation ability and approximation ability to characterize the GNNs expressive power, and there also exists other abilities, including subgraph counting ability, spectral decomposition ability [30, 31, 32], logical ability [33, 34, 35, 36, 37, 38, 39], etc., which are also considered as the main categories of GNNs expressive power. Therefore, it is crucial to clarify the definition and scope of the GNNs expressive power, which motivates this work.

In this work, we consider that GNNs expressive power consists of two aspects, including the feature embedding ability and topology representation capability. GNNs, as a member of neural networks, have strong feature embedding ability. The topology representation ability is the unique
ability of GNNs, which makes GNNs different from other machine learning models. Based on these two components, we then analyze the boundaries of the GNNs expressive power and its influencing factors. It is found that the factors affecting the GNNs expressive power also include both features and topology, in which the defects of GNNs in learning and keeping graph topology are the main factors limiting the expression.

Based on the analysis of the factors influencing the expressive power of GNNs, this paper summarizes the existing work of improving GNNs expressive power into three categories, i.e., graph feature enhancement, graph topology enhancement and GNNs architecture enhancement. Graph feature enhancement is to improve the expressive power by enhancing the feature embedding effect. Graph topology enhancement, seeks to represent the graph topology more effectively to help GNNs capture more intricate graph topology information. GNNs architecture enhancement involves improving the permutation invariant aggregation functions that limit the GNNs expressive power.

We also point out several shortcomings in existing benchmarks and evaluation metrics in this direction, and highlight the challenges to determine the GNNs expressive power. Furthermore, we propose several promising future research directions, including a physics-informed methodology for designing more powerful GNNs and utilizing graph neural architecture search.

The structure of this work is organized as follows: Section 2 introduces the preliminary knowledge, including basics of graph neural networks and graph isomorphism. Section 3 gives a unifying definition of GNNs expressive power.

Section 4 analyzes the influencing factors and existing works that are designed to improve GNNs expressive power. Section 5 points several challenges and opportunities in this research direction. Finally, we conclude with Section 6.

## 2 Preliminary

Before presenting the relevant definitions and the problem description, Table I gives a summary of all the notations used in the article.

### _Basics of Graph Neural Networks_

**Graph.** In the following, we consider the problem of representation learning on one or several graphs of possibly varying sizes. Let \(G=(\mathcal{V},\mathcal{E})\in\mathcal{G}\) be a graph of \(n\) nodes with node set \(\mathcal{V}\) and edge set \(\mathcal{E}\), directed or undirected. Each graph has an adjacency matrix \(\mathbf{A}\in\{0,1\}^{n\times n}\), and potential node features \(\mathbf{X}=(\mathbf{x}_{1},...,\mathbf{x}_{n})^{\mathrm{T}}\in\mathbb{R}^{n \times e}\). Combining the adjacency matrix and node features, we may also denote \(G=(\mathbf{A},\mathbf{X})\). When explicit node features are unavailable, an unfeatured graph \(G\) will consider \(\mathbf{X}=\mathbf{1}\mathbf{1}^{\mathrm{T}}\) where \(\mathbf{1}\) is a \(n\times 1\) vector of ones. For a node \(v\in\mathcal{V}\), the set of neighboring nodes is represented as \(N(v)\). We also use \(\mathcal{V}[G]\) to denote the node set of graph \(G\).

**Message Passing Neural Networks (MPNNs).** Out of the numerous architectures proposed, MPNNs have been widely adopted [40, 13, 41]. MPNNs employ a neighborhood aggregation strategy to encode each node \(v\in\mathcal{V}\) with a vector representation \(\mathbf{h}_{v}\). This node representation is updated iteratively by gathering representations of its neighbors before performing a nonlinear transformation of them with neural network (NN) layers:

\[\mathrm{MessagePassing:}\ \mathbf{m}_{u}^{(l)}=\mathrm{MSG}^{(l)}\left(\left\{ \mathbf{h}_{u}^{(l-1)}:u\in N(v)\right\}\right), \tag{1}\]

\[\mathrm{Aggregation:}\ \mathbf{a}_{v}^{(l)}=\mathrm{AGG}^{(l)}\left(\left\{ \mathbf{m}_{u}^{(l-1)}:u\in N(v)\right\}\right), \tag{2}\]

\[\mathrm{Update:}\ \mathbf{h}_{v}^{(l)}=\mathrm{UPD}^{(l)}\left(\mathbf{h}_{v}^{( l-1)},\mathbf{a}_{v}^{(l)}\right). \tag{3}\]

where, \(\mathbf{h}_{v}^{(0)}=\mathbf{x}_{v}\), \(\mathbf{m}_{u}^{(l)}\) represents the message from the neighbors, \(\mathbf{m}_{v}^{(l)}\) represents the aggregated message from neighbors at layer \(l\), \(\mathrm{MSG}^{(l)}\), \(\mathrm{AGG}^{(l)}\) and \(\mathrm{UPD}^{(l)}\) denote the message passing, aggregation and update functions of layer \(l\).

The neighbor aggregation strategy employed by MPNNs allows them to learn relationships between nearby nodes. This inductive bias is well suited for problems requiring relational reasoning [42, 43, 44, 45, 46]. Despite their widespread success, MPNNs nonetheless suffer from several limitations, including over-smoothing [47, 48, 49], over-compression [50, 51], the failure to distinguish between node identity and location [52, 53], and limited expressive power [25, 27]. The lack of expressive power is evident in their inability to compute several crucial graph properties (e.g., shortest/longest cycles, diameters and local clustering coefficients [54]), and their failure to learn the graph topology (for example, whether a graph is connected or whether a particular pattern, such as a cycle, exists in the graph [55]). To address tasks where the graph topology is critical, such as predicting the chemical properties of molecules [56, 57] and solving combinatorial optimization problems [58, 59], more powerful GNNs are required.

**k-order Linear Invariant GNN (k-IGN) Framework.** The k-IGN by Maron is another widely used framework for investigating GNN's expressive power [16, 60]. The k-IGN comprises of alternating layers composed of invariant or equivariant linear layers and nonlinear activation layers.

\begin{table}
\begin{tabular}{|c||c|} \hline
**Notations** & **Descriptions** \\ \hline \{\} & A set. \\ \hline \{\} & A multiset. \\ \hline \(G=(\mathcal{V},\mathcal{E})\) & An unfeatured graph. \\ \hline \(\mathcal{V}\) & The set of nodes in a graph. \\ \hline \(\mathcal{E}\) & The set of edges in a graph. \\ \hline \(N(v)\) & The set of the neighboring nodes of node \(v\). \\ \hline \(G=(\mathbf{A},\mathbf{X})\) & An featured graph. \\ \hline \(\mathbf{A}\) & The adjacency matrix. \\ \hline \(\mathbf{X}\) & The feature matrix. \\ \hline \(\mathbf{h}_{v}^{(l)}\) & The embedding of node \(v\) in the \(l\)-th layer. \\ \hline \(\mathbf{H}^{(l)}\) & The ebbedding matrix in the \(l\)-th layer. \\ \hline \(\mathrm{MSG}^{(l)}\) & The message passing function in the \(l\)-th layer. \\ \hline \(\mathrm{AGG}^{(l)}\) & The aggregation function in the \(l\)-th layer. \\ \hline \(\mathrm{UPD}^{(l)}\) & The update function in the \(l\)-th layer. \\ \hline \end{tabular}
\end{table} TABLE I: Notations in the survey
Each linear function is given as \(L\), and the non-linear activation function is denoted as \(\sigma\). The parameter k in k-IGN refers to the order of the tensor \(\mathbf{A}\), which corresponds to the indices used to represent its elements. For instance, a first-order tensor represents the node feature, a second-order tensor represents the edge feature, and a \(k\)-th order tensor encodes hyper-edge feature. For \(k=2\), the linear layer consists of 15 equivariant layers and 2 invariant layers, which can be expressed as follows:

\[L(\mathbf{A})=\sum_{i=1}^{15}\theta_{i}L_{i}(\mathbf{A})+\sum_{i=16}^{17} \theta_{i}\bar{L}_{i}(\mathbf{A}) \tag{4}\]

After adding the non-linear activation layer, the 2-IGN architecture can be presented as:

\[\mathbf{A}^{(l+1)}=\sigma\left(L^{(l+1)}\left(\mathbf{A}^{(l)}\right)\right) \tag{5}\]

IGN has demonstrated not less expressive power than MPNN and is therefore being widely adopted to augment expressiveness. Aside from the k-IGN frameworks, there also have been efforts to construct more powerful equivariant networks by combining a set of simple permutation equivariant operators [35, 36, 37, 38, 39].

**Permutation Invariance.** Graphs are inherently disordered, with no fixed node order. As a basic inductive bias in graph representation learning, permutation invariance refers to the fact that the output of a model is independent of the input order of nodes. Specifically, a model \(f\) is permutation invariant if it satisfies \(f\circ\pi(G)=f(G)\) for all possible permutations \(\pi\).

**Permutation Equivariance.** On the other hand, permutation equivariance means that the output order of the model corresponds to the input order. When we focus on node features, we expect the model to output in the same order as the input nodes. Specifically, a model \(g\) is permutation invariant equivariant if it satisfies \(g\circ\pi(G)=\pi\circ g(G)\) for all possible permutations \(\pi\).

The design philosophy of GNNs is to generate a permutation equivariant function on the graph by applying a local permutation invariant function to aggregate the neighbor features of each node [60].

### _Basics of Graph Isomorphism_

**Graph Isomorphism.** Graph isomorphism refers to the topological equivalence of two graphs. Given two graphs \(G=(\mathbf{A},\mathbf{X})\) and \(G^{\prime}=(\mathbf{A}^{\prime},\mathbf{X}^{\prime})\) with adjacency matrices \(\mathbf{A}\) and \(\mathbf{A}^{\prime}\) and feature matrices \(\mathbf{X}\) and \(\mathbf{X}^{\prime}\) respectively, an isomorphism between these graphs is a bijective mapping \(\pi:\mathcal{V}[G]\longrightarrow\mathcal{V}[G^{\prime}]\) that satisfies \(\mathbf{A}_{uv}=\mathbf{A}^{\prime}{}_{\pi(u)\pi(v)}\) and \(\mathbf{X}_{v}=\mathbf{X}^{\prime}{}_{\pi(v)}\). We use \(G\cong G^{\prime}\) to denote that \(G\) and \(G\) are isomorphic, where \(G^{\prime}\) can be represented as \(\pi(G)\). If there is no bijection \(\pi\) that satisfies these conditions, we say that \(G\) and \(G^{\prime}\) are non-isomorphic.

**Weisfeiler-Lehman test (WL test).** Graph isomorphism problems are notoriously difficult and are classified as NP-hard in graph theory. The WL test of isomorphism [62, 63], also known as the color refinement algorithm [64]), is an effective algorithm to solve graph isomorphism problems. The WL test utilizes a graph coloring technique to assign color labels to each node in the graph. This iterative process is illustrated in Figure 1[65]. Initially, every node in the graph is assigned a unique color label \(\mathbf{c}\). In each iteration, the central node and its neighbors are combined to form a set of multiple colors, which are subsequently mapped to a new unique color using Hash function, which becomes the new label of the central node. The process is repeated until the node color labels no longer change, resulting in a color distribution histogram of the graph. By comparing the color distributions of two graphs, the WL test can determine whether they are isomorphic or not. This process can be divided into several steps: neighbor label aggregation, multisets sorting, label compression, and label update and can be mathematically formulated as follows:

\[\mathbf{c}_{v}^{(l)}=\mathrm{Hash}\left(\mathbf{c}_{v}^{(l-1)},\left\{ \mathbf{c}_{u}^{(l-1)}|u\in N(v)\right\}\right). \tag{6}\]

```
1:Multiset-label determination  For \(l=0\), set \(M^{l}(v):=c^{0}(v)=c(v)\).  For \(l>0\), assign a multiset-label \(M^{l}(v)\) to each node \(v\) in \(G\) and \(G^{\prime}\) which consists of the multiset \(\{c^{I1}(u)|u\in N(v)\}\).
2:Sorting each multiset Sort elements in \(M^{l}(v)\) in ascending order and concatenate them into a string \(s^{l}(v)\).  Add \(c^{l-1}(v)\) as a prefix to \(s^{l}(v)\) and call the resulting string \(s^{l}(v)\).
3:Label compression Sort all of the strings \(s^{l}(v)\) for all \(v\) from \(G\) and \(G^{\prime}\) in ascending order.  Map each string \(s^{l}(v)\) to a new compressed label, using a function\(f:\Sigma*\rightarrow\Sigma\) such that \(\mathrm{Hash}(s^{l}(v))=\mathrm{Hash}(s^{l}(w))\) if and only if \(s^{l}(v)=s^{l}(w)\).
4:Relabeling Set \(c^{l}(v):=\mathrm{Hash}(s^{l}(v))\) for all nodes in \(G\) and \(G^{\prime}\).
```

**Algorithm 1** One iteration of 1-WL test of graph isomorphism

It is important to note that identical coloring results could only suggest but cannot guarantee graph isomorphism. While the WL test is fast and efficient for most graphs [66], it has limitations in distinguishing members of many important graphs, such as regular graphs. This issue becomes evident when considering non-isomorphic graphs, as displayed in Figure 2, where the algorithm mistakenly identifies them as isomorphic.

The more powerful k-WL algorithm was initially introduced by Weisfeiler [67], expanding the coloring of individual vertices to the coloring of k-tuples. A k-tuple is a unit of k neighbounced nodes, and the k-WL test [17, 18] captures higher-order interactions in the graph by considering the process of iterative aggregation between all neighbounced k-tuple units. Specifically, the labels for tuple units consisting of k nodes are computed, treating these tuple units as significant graph entities for iterative operations. The k-WL becomes increasingly expressive as k grows. For sufficiently large k, it can distinguish any finite set of graphs. It has been observed that the discrimination potential for k\(>\)1, (k+1)-WL test is unequivocally stronger than the k-WL test, creating a hierarchical structure where the discriminative power increases with higher k values. Therefore, the k-WL
test excels at detecting subgraph topology with larger k values, exhibiting an enhanced discrimination ability concerning graph structures.

k-WL iteratively recolors all \(n^{k}\) k-tuples defined on a graph \(G\) with \(n\) nodes. In iteration \(0\), each k-tuple \(\vec{v}=(v_{1},...,v_{k})\in V(G)^{k}\) is initially assigned a color as its atomic type \(c_{k}^{(l)}(\vec{v})\). If \(G\) has \(d\) colors, then \(c_{k}^{(0)}(\vec{v})\) is an ordered vector encoding. Let \(c_{k}^{(l)}(\vec{v})\) denote the color of k-tuple \(\vec{v}\) on graph \(G\) at the t-th iteration of the k-WL.

In the l-th iteration, k-WL updates the color of each \(\vec{v}\ inV(G)^{k}\) according to

\[c_{k}^{(l+1)}(\vec{v})=\text{Hash}(c_{k}^{(l)}(\vec{v}),\] \[\{c_{k}^{(l)}(\vec{v}[x/1]|x\in V(G))\}),..., \tag{7}\] \[\{\{c_{k}^{(l)}(\vec{v}[x/k]|x\in V(G))\}).\]

Let \(c_{k}^{(l)}(G)\) denote the encoding of G at l-th iteration of k-WL. Then,

\[c_{k}^{(l)}(G)=\text{Hash}(\{\{c_{k}^{(l)}(\vec{v})|\vec{v}\in V(G)^{k}\}\}). \tag{8}\]

Moreover, k-WL has interesting connections to logic, games, and linear equations [34, 37, 68]. Another variation of k-WL is known as k-folklore WL (k-FWL), where it is shown that the expressive power of (k+1)-WL is equivalent to that of k-FWL [65].

## 3 The expressive power of GNNs

### _The necessity of GNNs expressive power_

**Expressive power.** All machine learning problems can be abstracted as learning a mapping \(f^{*}\) from the feature space \(\mathcal{X}\) to the target space \(\mathcal{Y}\). \(f^{*}\) is usually approximated using a model \(f_{\theta}\) by optimizing some parameters \(\theta\). In practice, \(f^{*}\) is typically a priori unknown, so one would like \(f_{\theta}\) to approximate a wide range of \(f^{*}\) as much as possible. An estimate of how wide this range is called the _expressive power_ of the model, providing an important measure of the model potential [69], shown in Fig 3 (a).

The powerful expressive power of NNs is reflected in their ability to approximate all continuous functions [70], specifically the ability to embed data within the feature space \(\mathcal{X}\) into the target space \(\mathcal{Y}\) generated by any continuous

Fig. 1: The illustration of the aggregation and update process of WL test. (a) Given two graphs without features, and add color labels to all nodes. (b) In the first iteration, the different information aggregated by the nodes is mapped into new color labels, and then these new labels are redistributed to nodes, and the number of labels is counted after the distribution. After 1st iteration, \(G1\) and \(G2\) have the same color distributions to determine whether they are isomorphic, and the next iteration is performed. (c) Perform the node neighbor aggregation and redistribution of color labels steps again, and get the different color distributions of \(G1\) and \(G2\), at this time, it can be determined that the two are non-isomorphic.

Fig. 2: Some non-isomorphic graphs that cannot be distinguished by WL test.
function, which is in fact feature embedding ability, show in Fig 3 (b). Due to the strong expressive power of NNs, similarly, few works doubt the expressive power of GNNs that have demonstrated significantly superior performance in a variety of application tasks because they naturally feature the superior performance of GNNs to their excellent feature embedding ability.

However, some graph-augmented multilayer perceptron (MLP) models [71, 72] outperform GNNs despite the former's less expressive power than the latter in a number of node classification problems [73], where MLPs [74] use only information from each node to compute feature embeddings of nodes, and GNNs iteratively aggregate the features of neighbouring nodes in each layer, thus allowing the use of global information to compute feature embeddings of nodes. This fact results in a contradiction between our intuitive understanding of expressive power, yet at the same time illustrates that feature embedding power does not describe the expressive power of GNNs well.

GNNs, compared to NNs, add the inductive bias of permutation invariance so that they can propagate and aggregate information over the topology of the graph. [48, 75] demonstrate that if GNNs only have feature embedding ability but lack the ability to maintain the graph topology, then their performance may be inferior to MLP. In addition, we know that the expressive power of feed-forward neural networks is often limited by their width, whereas the GNNs' expressive power is not only limited by their width, but also how they use the graph topology for message propagation and node updates. It follows that the topology representation ability of GNNs, i.e., the ability to maintain the graph topology, becomes the key to their superior performance. To characterise the expressive power of GNNs using their topology representation ability then requires a new set of theoretical tools.

### _The definition and representation of GNNs expressive power_

#### 3.2.1 The definition of GNNs expressive power

Graph data typically contains both feature and topology information. As a neural network model for graph representation learning in the family of NNs, the feature embedding ability of GNNs is unquestionable, and their expressive power is more reflected in their topology representation ability. GNNs map node \(v\) from original space \(\mathcal{X}\) to embedding space \(\mathcal{Y}\) to obtain node embedding \(\mathbf{h}_{v}\) via function \(f\), where \(\mathbf{h}_{v}=f(\mathbf{A}\cdot\mathbf{x}_{v})\). For nodes \(v_{1}\), \(v_{2}\) in different topological positions on graph \(G\), if \(\mathbf{x}_{1}\neq\mathbf{x}_{2}\), the results of the feature embedding ability ensure that \(f(\mathbf{A}\cdot\mathbf{x}_{1})\neq f(\mathbf{A}\cdot\mathbf{x}_{2})\). And if \(\mathbf{x}_{1}=\mathbf{x}_{2}\), to maintain the topology of the graph, it meanwhile requires that \(f(\mathbf{A}\cdot\mathbf{x}_{1})\neq f(\mathbf{A}\cdot\mathbf{x}_{2})\).

**Feature embedding ability.** Let \(\mathbf{X}=\mathbf{random}\), i.e., input graph with node features, the feature embedding ability can be expressed by the size of the value domain space \(\mathcal{F}=\{f(\mathbf{A}\cdot\mathbf{X})|\mathbf{X}=\mathbf{random}\}\) of \(f\).

**Topology representation ability.** Let \(\mathbf{X}=\mathbf{1}\),, i.e., input graph without node features, the topology representation ability can be expressed by the size of the value domain space \(\mathcal{F}^{\prime}=\{f(\mathbf{A}\cdot\mathbf{X})|\mathbf{X}=\mathbf{1}\}\) of \(f\).

The feature embedding ability reflects that nodes with different features can get different node embeddings. Topology representation ability reflects that nodes with different topological positions can get different node embeddings. Together, these two constitute the expressive power of GNNs, illustrated with reference to Fig 4.

**The expressive power of GNNs.** Let \(\mathbf{X}=\mathbf{random}\), the size of the space \(\mathcal{F}\cap\mathcal{F}^{\prime}\) describes the expressive power of \(f\). Typically, \(\mathcal{F}\supseteq\mathcal{F}^{\prime}\), which means that the topology representation ability is the main factor limiting the expression of GNNs. And for two models, \(f_{1}\) and \(f_{2}\), if \(\mathcal{F}_{1}\supset\mathcal{F}_{2}\), we say that \(f_{1}\) is more expressive than \(f_{2}\).

Several prevailing views in current research on the expressive power of GNNs characterise the expressive power as approximation ability, separation ability and subgraph counting ability, respectively.

Fig. 3: An illustration of the expressive power of NNs and their affects on the performance of learned models. (a) Machine learning problems aim to learn the mapping from the feature space to the target space based on several observed examples. (b) The expressive power of NNs refers to the gap between the two spaces \(\mathcal{F}\) and \(\mathcal{F}^{\prime}\). Although NNs are expressive (\(\mathcal{F}^{\prime}\) is dense in \(\mathcal{F}\)), the learned model \(f^{\prime}\) based on NNs may differ signifcantly from \(f^{*}\) due to their overfit of the limited observed data. This figure is with reference to Fig. 5.5 in [69].
_Approximation ability._ The approximation perspective examines GNN's ability in approximating functions on graphs, considering the feature embedding and topology representation. Despite this, exploration of the type of functions that GNNs can approximate remains insufficient to address practical problems directly.

_Separation ability._ This perspective examines GNN's ability in graph isomorphism identification, focusing solely on topology representation. Nevertheless, its scope is limited to unfeatured graphs, resulting in inadequate practical applicability when solving real-world problems.

_Subgraph counting ability._ This perspective examines the potential of GNNs in detecting and utilizing graph subgraph topology, similarly concerned with topology representation. Unlike separability, graph subgraph topology is highly relevant to molecular functional groups and communities in real-world tasks, hence, holding practical application value.

#### 3.2.2 Approximation ability

Models with stronger expressive power can learn more complex mapping functions. Neural networks are known for their strong expressive power, and one of the most famous results is the universal approximation theorem for neural networks [14, 15, 70]. As a member of the neural network family, GNNs can also use the ability to approximate mapping functions to describe their own expressive power. However, because GNNs add inductive bias [13] to graph learning, i.e., permutation invariance, the results of the generalized approximation theorem for neural networks cannot be simply generalized to GNNs. In this context, Maron et al. [16, 17, 18] describe specifically the types of functions that GNNs can approximate, using the _approximate ability_ to approximate to describe the expressive power of GNNs, that is, what kind of permutation invariant graph functions GNNs can approximate. They further give a description of the set of functions that the model can approximate as a measure of expressive power. Assume that GNN is a mapping \(f_{\theta}:\mathcal{G}\to R^{d\times n\times m}\) on graph, where \(\mathcal{G}\) is the set of graphs \(G=(A,X)\), \(X\in R^{d\times n}\) is node feature, \(d\) is the dimension of the feature, \(n=|V|\) and \(m=|\mathcal{G}|\). Denote the output of GNNs by \(f_{\theta}(G)\), the formal definition of approximate ability can be given.

**Function approximation.** Consider a function \(f^{*}\) to be learned, when the input of GNNs is the set of graphs \(\mathcal{G}\), if \(||f^{*}(G)-f_{\theta}(G)||_{\infty}:=sup_{G}|f^{*}(G)-f_{\theta}(G)|<\varepsilon\), for \(G\in\mathcal{G}\)

Fig. 4: An illustration of the expressive power of GNNs. a) The feature embedding ability of GNNs is the same as that of NNs in that both maps the observed examples in the feature space \(\mathcal{X}\) to the target space \(Y\) via \(f\). The strength of the feature embedding ability is measured by the size of the value domain space \(\mathcal{F}\) of \(f\). b) The topology representation capability of GNNs is achieved by mapping the observed examples in the feature space to the target space via \(f\) and preserving the original topology between the examples. The strength of the capability is measured by the size of the value domain space \(\mathcal{F}^{\prime}\) with \(\mathbf{X}=\mathbf{1}\). c) The expressive power of GNNs consists of a combination of feature embedding ability and topology representation ability, measured by the size of the intersection of \(\mathcal{F}\) and \(\mathcal{F}^{\prime}\) with \(\mathbf{X}=\mathbf{random}\).
and \(\varepsilon>0\), then \(f^{*}\) is successfully approximated by \(f_{\theta}\).

**Approximation ability.** The measure of the size of the set of functions composed of all potential \(f_{\theta}\) is the approximation ability of GNNs. Figure 5 shows the representation of input and output under the definition of approximation ability.

However, these theoretical findings are not sufficient to explain the unprecedented success of GNNs in practice, because simply knowing what graph functions the model can approximate does not guide practical production work. It is challenging to analyze the expressive power of GNNs starting from a practical application perspective.

#### 3.2.3 Separation ability

Considering how GNNs make predictions about molecules, GNNs should be able to predict whether a topology corresponds to a valid molecule by identifying whether the topology of the graph is the same or similar to the topology corresponding to a consistent valid molecule. This problem of measuring whether two graphs have the same topology involves the problem of graph isomorphism [19, 21].

In the graph isomorphism perspective, Xu et al. [27] and Morris et al. [25] used _separation ability_ to describe the expressive power of GNNs, that is, whether GNNs can effectively identify non-isomorphic graph topology. By gaining insight into the high similarity and close connection between the WL test and GNNs in the iterative aggregation process, they further used the WL test as a measure of the strength of the separation ability and indicated that the upper limit of the separation ability is 1-WL test. Similarly, the formal definition of the separation ability can be given.

**Graph isomorphism recognition.** Consider two non-isomorphic graphs \(G_{1}=(A_{1},X_{1})\) and \(G_{2}=(A_{2},X_{2})\), where \(X_{1}=X_{2}=\mathbf{1}\). If \(f_{\theta}(G_{1})\neq f_{\theta}(G_{2})\), then it is assumed that GNNs can identify non-isomorphic graph pairs.

**Separation ability.** The measure of the size of the set of all identifiable possible non-isomorphic pairs \(|\mathcal{G}_{1}|\) is the separation ability of GNNs. Figure 7 shows the representation of input and output under the definition of separation ability.

The results of the separation ability show the role that GNNs expressive power plays in practice. And in fact, it has been shown that both separation and approximation ability are theoretically unified. Chen et al. [28] demonstrated the equivalence between the two abilities, showing that the basis of the approximation ability is actually the embedding of two non-isomorphic graphs into different points of the target space, and that a model that can distinguish all nonidentical graphs is also a general function approximator. The result of equivalence provides, in a sense, a practical application for approximation ability.

However, the result of separation ability requires comparison of pairs of graphs, which requires a prior a different GNN for each pair of graphs to distinguish them. This is of little help in practical learning scenarios, because people prefer to give meaningful representations to all graphs through a single GNN. In addition, the graph isomorphism problem measures the expressive power at the graph level, while the expressive power at the node level is equally important, and whether this theory can explain the expressive power of nodes is still questionable [76].

#### 3.2.4 Subgraph counting ability

Considering solving problems at the node level is also very instructive for practice. Continuing with the prediction problem of predicting molecular functions, in addition to the need to identify whether the graph topology is the same as the known functional group topology to determine the molecular properties, sometimes the number of functional groups also has an impact on the function of the molecule, which requires determining how many identical graph topology there are in the graph. To address this issue, Chen et al. [55] have proposed to use _subgraph counting ability_ to describe the GNNs expressive power, emphasizing the GNNs' ability to recognize subgraph topology in graphs. On the one hand, this ability can evaluate node-level embeddings, comparable to the separation ability. On the other hand, real-world graph topology such as molecular and community topology typically involve subgraph topology, Hence this ability has more practical guidance for applications compared to the approximation ability. Similarly, the formal definition of the separation ability can be given.

**Subgraph counting.** Consider two isomorphic subgraphs \(G_{1}=(V_{1},E_{1})\) and \(G_{2}=(V_{2},E_{2})\) of graph \(G=(V,E)\), where \(V_{1},V_{2}\in V\), \(E_{1},E_{2}\in E\) and \(V_{1}\neq V_{2}\). If \(f_{\theta}(G_{1})\neq f_{\theta}(G_{2})\), then it is assumed that GNNs can count subgraphs.

**Subgraph counting ability.** The measure of the size of the set of all identifiable countable isomorphic subgraphs \(|\mathcal{G}_{1}|\) is the subgraph counting ability of GNNs. Figure 5 shows the representation of input and output under the definition of subgraph counting ability.

### _The strength of GNNs expressive power_

When considering the topology representation of GNNs without taking into account feature embeddings, GNNs expressive power is confined to the 1-WL test. This conclusion arises from the observations by Xu et al. [27] and Morris et al. [25] that highlight the striking similarity between neighborhood aggregation in GNNs and neighbor label aggregation in the WL test. The choice of aggregation functions in GNNs is crucial since employing injection functions results in GNNs being equipotent with the WL test in terms of expressive power.

As the consideration extends to feature embedding, GNNs outperform the 1-WL test in expressive power. A compelling demonstration by Kanatsoulis et al. [32] showcases GNNs' ability to discern any graph where at least one node exhibits a unique feature. This finding reaffirms our justifiable definition of GNNs expressive power, emphasizing that the feature embeddings bolsters the GNNs' topology representation.

Provided that the node features adequately characterize node identities, Loukas et al. [77, 78, 79] has confirmed that GNNs with powerful message-passing and update functions become Turing universal, which corroborated in a small instance of the graph isomorphism problem [80]. Nonetheless, the limitations in depth and width of GNNs leads to a diminished expressive power.
## 4 Existing work of improving GNNs expressive power

### _Factors affecting GNNs expressive power_

GNNs expressive power involves the expression of graph features and graph topology, so the effect of graph feature embedding and graph topology representation will affect the expression of GNNs.

The graph features can affect the expression of GNNs. First of all, node features have strong discrimination ability. [77] proved that GNNs can distinguish graphs with different node features. [32] further proved that GNNs can distinguish any graph with at least one node feature differences. In addition, the global graph feature also has discrimination ability. [38] proved that GNNs can distinguish graphs with different global graph features.

The topology of the graph also affects the expression of GNNs. GNNs do not directly encode the graph topology for learning, but use the topology of the graph for information transmission and aggregation, which is realized by the permutation invariant aggregation function. This design hinders the expression of GNNs [81]. Because the permutation invariant aggregation function assumes that the states of all adjacent nodes are equal, the relationship between adjacent nodes is ignored. The node encoding obtained through neighborhood aggregation represents the rooted subtree around the central node, as illustrated in the Figure 6. However, rooted subtrees have limited expressive power for representing non-tree graphs. Therefore, the central node cannot distinguish whether two adjacent nodes are adjacent or not, and cannot identify and reconstruct the graph topology. General GNNs can only explicitly reconstruct a star graph from a 1-hop neighborhood, but cannot model any connections between neighborhoods [55]. Therefore, the permutation invariant aggregation functions cause GNNs to lose the topology of the context in the topology representation and thus fail to learn the basic topological properties of the graph [54].

### _Methods to improve GNNs expressive power_

Improving the expressive power of GNNs can similarly be approached in terms of both improving the feature embedding effect and improving the topology representation effect. The enhancement of the feature embedding effect depends on the enhancement of the features themselves, including the extraction of dependencies between features and the addition of related features. There are two effective ways to enhance the effect of topology representation. One way is to directly encode relevant topology information for GNNs learning, and the other way is to optimise the GNNs model architecture to eliminate the obstacle of maintaining topology caused by permutation invariant aggregation functions.

In this article, we summarise these three approaches as: Graph feature enhancement (enhancing the effect of feature embedding), Graph topology enhancement (encoding of topology information directly), and GNNs architecture enhancement (mitigating the defect of permutation invariant aggregation functions). In line with our expectations, the more powerful model designs for GNNs that are currently known for their means of improving expressive power can all be subsumed under the three approaches we summarised. Table II examines and systematically categorizes the design of more powerful expressive GNNs in recent years them based on their employed design methodologies.

### _Graph feature enhancement_

Graph feature enhancement is to improve the embedding efficiency of graph features. One method is to extract the dependency between features to increase the information quantity of features to improve the embedding effect. The other method is to improve the utilization rate of feature

Fig. 5: Input and output of the GNNs model under different expressive power representations. When approximate ability is used to characterise the expressive power, the input of the model is a set of graphs and the output is a graph embeddings. When separation ability, the input is a pair of graphs and the output is graph embeddings. When the subgraph counting ability, the input is a single graph and the output is a node (set) embeddings.

Fig. 6: The rooted subtree in message passing. The left one represents the original graph \(G\), and the objective is to obtain an embedding of node \(v_{1}\) on \(G\), where node \(v_{1}\) is denoted by red color. The right one is the subtree obtained for node \(v_{1}\) after two rounds of iteration.
information by multiple embedding to enhance the embedding effect. A detailed description of this method of enhancing the effect of feature embedding is shown in Figure 7.

#### 4.3.1 Extracting dependencies between features

**AM-GCN** The adaptive multi-channel graph convolution network (AM-GCN) [82] computes node similarity based on their features, constructing a k-nearest neighbor(k-NN)

\begin{table}
\begin{tabular}{|p{56.9pt}||p{113.8pt}||p{113.8pt}||p{113.8pt}|} \hline
**Methods** & **Subclasses** & **Models** & **Descriptions** \\ \hline Graph feature enhancement & Extracting dependencies between features & AM-GCN [82] & Capture the dependencies between node features by a k-nearest neighbor graph. & Capture the dependencies between node features by a k-nearest neighbor graph. \\ \cline{2-4}  & Enhancing feature use & ACR-GNN [38] & Calculate and add the global node features. \\ \hline  & & Twin-GNN [84] & Assign color labels and identity to nodes. \\ \cline{2-4}  & Adding extra topology information & LD-GNN [52] & Inject a unique color identity to nodes. \\ \cline{2-4}  & Adding extra topology information & CLIP [85] & Give a distinct color to a subset of nodes with same features. \\ \cline{2-4}  & & RP-GNN [86] & Randomly assign an order of nodes as their extra features. \\ \cline{2-4}  & & RNI-GNN [87] & Input randomized initial node features. \\ \cline{2-4}  & & DE-GNN [88] & Capture the distance from a given node to the node set to be learnt. \\ \cline{2-4}  & Encoding micro-topology & P-GNN [53] & Measure the distance from a node to a set of randomly selected anchor nodes. \\ \cline{2-4}  & Graph topology enhancement & PEG [89] & Use separate channels to update both the node features and position features. \\ \cline{2-4}  & & SMP [78] & Employ one-hot encoding learn rich local topological information. \\ \cline{2-4}  & & GD-WL [90] & Encode generalised distance information. \\ \cline{2-4}  & Encoding global-topology & Eigen-GNN [91] & Incorporate eigen decomposition on the adjacency matrix to obtain eigenvectors as topology features. \\ \cline{2-4}  & & GSN [92] & Encode the count of pre-defined subgraph topology appearance in the graph. \\ \cline{2-4}  & & GraphSNN [93] & Enable the transmission of diverse messages based on the topology features of the central node’s 1-hop neighborhood subgraph. \\ \cline{2-4}  & Encoding local-topology & GNN-AK [94] & Extend the scope of local aggregation into more generalized subgraphs. \\ \cline{2-4}  & & NGNN [95] & Extract a local subgraph around each node. \\ \cline{2-4}  & & MPSN [96] & Operates message passing on simplicial complexes. \\ \cline{2-4}  & & ESAN [97] & Represent each graph as a set of subgraphs derived from a predefined policy. \\ \cline{2-4}  & & LRP-GNN [55] & Refer to RP-GNN that operates on subgraphs essentially. \\ \cline{2-4}  & & k-GNN [25] & High-order message passing occurs between k-tuple subgraphs. \\ \cline{2-4}  & & K-hop GNN [98] & Message passing occurs between k-hop neighbors. \\ \cline{2-4}  & & KP-GNN [99] & Learn peripheral subgraph information based on K-hop GNNs. \\ \hline  & & GIN [27] & Aggregation function models an injective function operating on multisets. \\ \cline{2-4}  & Improving aggregation function & modular-GCN [100] & Use three GCN modules of different propagation strategies to compensate the missing topology information. \\ \cline{2-4}  & & diagonal-GNN [32] & Use the diagonal modules to capture broader topology relationships. \\ \cline{2-4}  & & GNN-LF/HF [30] & Graph convolution corresponding to low-pass/high-pass filtering operations. \\ \cline{2-4}  & & Geom-GCN [101] & Map graphs to a continuous latent space and construct topology neighborhoods based on the geometric relations defined in the latent space. \\ \cline{2-4}  & & PG-GNN [102] & Model the dependency relationships between neighboring nodes as a permutation-sensitive function. \\ \cline{2-4}  & & k-IGN [60] & Comprise of a sequence of alternating layers composed of invariant or equivariant linear layers and nonlinear activation layers. \\ \cline{2-4}  & & PPCN [103] & Apply module strategy in k-IGN. \\ \cline{2-4}  & & k-FGNN [104] & Improved tensor calculation techniques in k-IGN. \\ \cline{2-4}  & & Ring-GNN [28] & Only matrix addition and matrix multiplication are used in 2-IGN. \\ \cline{2-4}  & & SUN [105] & Variant of 2-IGN capture of local and global operations simultaneously. \\ \cline{2-4}  & & GNNML [36] & Combine various computation operators. \\ \cline{2-4}  & & k-MPNN [61] & Message passing over k-order neighbors via combination of computational operators. \\ \hline \end{tabular}
\end{table} TABLE II: Summary of the powerful model
graph by selecting the k most analogous neighbors for each node. Then subsequently performs convolutions over both the k-NN graph and original graph, as shown in Figure 8. This design captures the dependencies between node features, thus achieving an enhancement of node features. For a k-NN graph \(\mathcal{G}_{f}=(\mathbf{A}_{f},\mathbf{X})\), \(\mathbf{A}_{f}\) denotes the adjacency matrix. And the message passing along \(\mathcal{G}_{f}\) can be represented as equation (9).

\[\mathbf{h}_{f}^{(l+1)}=\mathrm{RELU}\left(\tilde{\mathbf{D}}_{f}^{-1/2}\tilde{ \mathbf{A}}_{f}\tilde{\mathbf{D}}_{f}^{-1/2}\mathbf{h}_{f}^{(l)}\mathbf{W}_{f }^{(l)}\right), \tag{9}\]

where \(\mathbf{W}_{f}\) is the weight matrix, \(\tilde{\mathbf{A}}_{f}=\mathbf{A}_{f}+\mathbf{I}_{f}\), and \(\tilde{\mathbf{D}}_{f}\) is the diagonal degree matrix of \(\tilde{\mathbf{A}}_{f}\).

**CL-GNN** GNNs can extract more information regarding the local neighborhood dependencies of the nodes by sampling [86], while sampling the predicted node labels also allows GNNs to focus on the relationships between node features, graph topology, and label dependencies. [83] consider using a collective learning framework (CL-GNN), which employs Monte Carlo sampling to further consider label dependencies. This approach enables GNNs to incorporate more information into the estimated joint label distribution, leading to more expressive node embeddings.

#### 4.3.2 Enhancing feature use

**ACR-GNN** Barcelo et al. [38] adds a readout function in the aggregation operation to calculate the global node features for node update, resulting in a novel architecture known as aggregate-combine-readout GNN (ACR-GNN). The update process can be described as follows:

\[\mathbf{h}_{v}^{(l+1)}=\mathrm{UPD}^{(l)}\left(\mathbf{h}_{v}^{( l)},\mathrm{AGG}^{(l)}\left(\left\{\mathbf{h}_{u}^{(l)}:u\in N(v)\right\} \right),\right.\\ \left.\mathrm{READ}^{(l)}\left(\left\{\mathbf{h}_{u}^{(l)}:u\in V \right\}\right)\right). \tag{10}\]

Enhancing the effect of feature embedding, either by adding additional features or by augmenting its own features, brings an increase in computational complexity to varying degrees while improving the expressive power of the model, creating an additional burden on model training. In addition, the addition of random features requires extra attention, and the injection of randomness may destroy the permutation invariance of GNNs, so the permutation invariance has to be restored by additional design [86].

### _Graph topology enhancement_

Graph topology enhancement lies in the direct encoding of learned topology information. One approach is to manually add additional topological relevant node features, the other is to directly encode the topology information inherent in the graph. According to the different topology information encoded, the latter method can be further divided into: encoding the micro-topology (such as distance, position and other topology information), encoding the local-topology (containing the local topological information mainly based on subgraph topology), and encoding the global-topology. A detailed description of this method of encoding the topology of the graph directly is shown in Figure 9.

#### 4.4.1 Adding extra topology information

The aim of adding extra topology information is to increase the discrimination between nodes topologically. A prevalent and straightforward approach entails assigning distinct, recognizable features to nodes, such as identifications [84, 52], colors [85], and random features [106, 87, 86, 107]. The added features can be represented by a characteristic matrix \(\mathbf{C}\), as demonstrated in the equation 11, which enhances the node features \(\mathbf{X}\) via \(\mathbf{C}\). Especially, this method can also be applied to unfeatured graphs, in which case the additional features serve as node features.

\[G=(\mathbf{A},\mathbf{X}\oplus\mathbf{C}). \tag{11}\]

**Twin-GNN** Wang et al. [84] have introduced the Twin-WL test as an extension of the 1-WL test, with improved discriminative power obtained by simultaneously assigning color labels and identity \(id\) to the nodes and executing two sets of aggregation schemes. The identity aggregation as Equation 12. Based on the Twin-WL test, the Twin-GNN has been developed to operate two sets of message passing mechanisms for node features and node identities. The identity passing encodes more complete topology information, allowing for a stronger expression than 1-WL test without significantly increasing computational costs.

\[\mathbf{id}_{v}^{(l)}=f_{id}\left(\mathbf{id}_{v}^{(l-1)},\left\{\mathbf{id}_ {u}^{(l-1)}|u\in N(v)\right\}\right), \tag{12}\]

where \(f\) is a function able to convert the identity multiset to the topology information that can be compared across different graphs.

**ID-GNN** The Identity-aware GNNs (ID-GNNs) [52] are a universal extension of GNNs. A L-layer ID-GNN first extracts the L-hop network \(G_{v}^{(L)}\) of node \(v\), and injects a unique color identity to \(v\). Then, the heterogeneous message passing is performed on the \(G_{v}^{(L)}\) to obtain the node embedding with injected identity. This added identification information enables the distinguishing of subgraphs with the same topology, thereby enhancing the GNNs expressive power.

For \(u\in\mathcal{V}(G_{v}^{(L)})\), there can be categorized into two types throughout the embedding process: nodes with coloring and nodes without coloring. When passing the message of the colored nodes, perform another set of message passing mechanism:

\[\mathbf{m}_{s}^{(l)}=\mathrm{MSG}_{\mathrm{color}}^{(l)}\left(\left\{\mathbf{ h}_{s}^{(l-1)}:s\in N(u)\right\}\right). \tag{13}\]

Fig. 7: A detailed description of this method of Graph feature enhancement.
**CLIP** The GNN called Colored Local Iterative Procedure (CLIP) uses colors to disambiguate identical node features. Nodes with the same features are assigned to different subsets, and then the nodes in a same subset will be given a distinct color \(\mathbf{c}_{i}\) from a finite color set \(C\). And the colored graph can be represented as the following Equation. The CLIP is capable of capturing topology characteristics that traditional MPNNs fail to distinguish, and becomes a provably universal extension of MPNNs.

\[G=(\mathbf{A},\mathbf{X}\oplus[\mathbf{c}_{i}]). \tag{14}\]

**RP-GNN** Murphy et al. [86] considered randomly assigning an order of nodes as their extra features and proposed the relational pooling GNN (RP) as a general method in GNNs. This method takes advantage of the enumeration idea, by enumerating all possible results of different input orders, and then taking the average result as the final output. Suppose there are all \(m\) possible permutations of graph \(G\) and for one permutation \(\pi\), \(\mathbf{I}_{\pi}\) is a one-hot encode matrix of the permutation sequence, \(\pi\circ G=(\mathbf{A},\mathbf{X}\oplus\mathbf{I}_{\pi})\) denotes a permutated graph. Each permutated graph can get the node embeddings \(\mathbf{h}_{v}^{\pi}\) via GNN, and take the average of them as the final embedding \(\mathbf{h}_{v}\).

\[\mathbf{h}_{v}=\frac{1}{m!}\sum_{m}\left(\mathbf{h}_{v}^{\pi}\right). \tag{15}\]

**RNI-GNN** The random node initialization (RNI) [87] is proposed as a means of training and implementing GNNs with randomized initial node features \(\mathbf{R}\). RNI-GNNs are shown to be effective in achieving universal without relying on high-order feature calculations. This also holds with partially randomized initial node features.

\[G=(\mathbf{A},\mathbf{X}\oplus\mathbf{R}). \tag{16}\]

Fig. 8: The propagation process of information through three graph convolution in the architecture of AM-GCN. The left part shows the process to get the k-NN graph by by selecting the k most analogous neighbors for each node in the original graph. The right part shows the convolution over the k-NN graph, original graph and the common convolution process. This figure is referenced to [82] Figure 1.

Fig. 9: A detailed description of this method of Graph topology enhancement.
#### 4.4.2 Encoding the micro-topology

Encoding the micro-topology is to determine the position of each node within the graph topology, accomplished through distance encoding or position encoding.

**DE-GNN** The distance encoding (DE) [88] is proposed as a generic initialization mean of contributing to the node embeddings in GNNs by capturing the distance from a given node to the node set to be learnt. Given a node set \(S\) whose topology representation is to be learnt, for every node \(u\) in the graph, DE is defined as a mapping \(f_{\mathrm{DE}}\) of a set of landing probabilities of random walks from each node of the set \(S\) to node \(u\). DE-GNN is proved to be able to effectively distinguish node sets within nearly all regular graphs where traditional GNNs struggle. While it introduces significant memory and time overhead.

\[\mathbf{d}_{v|S}=\mathrm{AGG}(f_{\mathrm{DE}}(v,u)|u\in S), \tag{17}\]

\[\mathbf{h}_{v}^{(0)}=\mathbf{x}_{v}\otimes\mathbf{d}_{v|S}, \tag{18}\]

where \(\mathbf{d}_{v|S}\) denotes the distance of node \(v\) and set \(S\), \(\otimes\) is the concatenation operation.

**P-GNN** In order to mitigate the computational cost of DE, an approach called position encoding (PE) is applied using the absolute position of the nodes in the graph as an additional feature. This technique approximates DE by measuring the distances between position features and can be shared among different node sets. The position-aware GNN (P-GNN) proposed by You et al. [53] incorporates PE by measuring the distance from a node to a set of randomly selected anchor nodes as Figure 10. However, it has been observed that this approach has slow convergence rate and unsatisfactory performance. The procedure of PE is shown as following:

\[\mathbf{d}_{v,u}^{q}=\left\{\begin{array}{l}\mathbf{d}_{v,u},\mathbf{d}_{v,u}\leq q\\ \infty,\mathrm{otherwise},\end{array}\right. \tag{19}\]

\[\mathbf{d}_{\mathrm{standard}}=\frac{1}{1+\mathbf{d}_{v,u}^{q}}, \tag{20}\]

where \(q\) is the hop from \(v\) to \(u\), \(\mathbf{d}_{v,u}\) is the shortest distance of \(v\) and \(u\).

**PEG** Utilizing PE, [89] introduces a novel approach to constructing more powerful GNNs - a class of GNN layers termed PEG. PEG uses separate channels to update both the node features and position features, exhibiting permutation equivariance and rotation equivariance simultaneously, where Stability is actually an even stronger condition than permutation equivariance because it characterizes how much gap between the predictions of the two graphs is expected when they do not perfectly match each other.

In addition to DE or PE, incorporating marked topology information into message passing mechanisms shows significant enhancement of the GNNs expressive power.

**SMP** The topology message passing (SMP) [78] method employs one-hot encoding to propagate the sole node identification, enabling the learning of local context matrices surrounding each node. This confers SMP with the capability to learn rich local topological information. In SMP, each node of a graph maintains a local context matrix \(\mathbf{U}_{i}\) rather than a feature vector \(\mathbf{x}_{i}\) as in MPNN. The \(\mathbf{U}_{i}\) is initialized as a one-hot encoding \(\mathbf{U}_{i}^{(0)}=\mathbf{1}\) for every \(v_{i}\in\mathcal{V}\), and if there are features \(\mathbf{x}_{i}\) associated with node \(v_{i}\), they are appended to the same row of the local context as \(\mathbf{U}_{i}^{(0)}[i,:]=[1,\mathbf{x}_{i}]\). The message passing process is as Equation 21 showed.

\[\mathbf{U}_{i}^{(l+1)}=\mathrm{UPD}(\mathbf{U}_{i}^{l},\mathrm{AGG}( \mathrm{MSG}(\mathbf{U}_{j}^{l})_{v_{j}\in N(v_{i})}). \tag{21}\]

**GD-WL** One of the main drawbacks of 1-WL is the lack of distance information between nodes. Inspired by some distance coding methods [89, 78, 53, 90] further introduced a new colour refinement framework called Generalized Distance Weisfeller-Lehman (GD-WL).The update rule of GD-WL is very simple and can be written as:

\[\mathbf{c}_{v}^{(l)}=\mathrm{Hash}\left(\mathbf{c}_{v}^{(l-1)},\left\{\left\{ \left(d_{vu},\mathbf{c}_{u}^{(l-1)}\Big{(}\left|u\in N(v)\right\}\right\} \right)\right). \tag{22}\]

Where \(d_{vu}\) can be an arbitrary distance metric.

#### 4.4.3 Encoding the local-topology

This method focuses on local topology, mainly utilizing subgraphs explicitly or implicitly for node embedding to learn more topology information.

**GSN** Graph sub-topology Networks (GSN) [92] represent a topologically-aware message passing scheme based on sub-topology encoding. GSN explicit encodes the count of pre-defined subgraph topology appearance in the graph, as a topology role in message passing to capture a richer topological features and thereby exhibit superior expressive power over the WL test. However, the pre-defined subgraphs require the domain expert knowledge, hampering the model's widespread adoption. Considering \(\mathbf{r}_{v}\) as the topology role induced by the subgraph counts, the message passing process is as following:

\[\mathbf{m}_{v}^{(l+1)}=\mathrm{MSG}(\mathbf{h}_{v}^{(l)},\mathbf{h}_{u}^{(l) },\mathbf{r}_{v},\mathbf{r}_{u}:u\in N(v)). \tag{23}\]

**GraphSNN** Wijesinghe et al. [93] introduced the neighborhood subgraph graph neural network (GraphSNN), which enables the transmission of diverse messages based on the topology features of the central node's 1-hop neighborhood subgraph during message passing. The weight of the delivered message is determined by the extent of overlap subgraph between the central node and its neighbors in Equation 24 and Equation 25, with edge overlap also factored into the weight calculation. By injecting the topology information of the neighborhood subgraph in the message passing process as Equation 26, GraphSNN can improve its expressive power without necessitating specialized knowledge or sacrificing computational complexity.

\[w_{vu}=\frac{\left|E_{vu}\right|}{\left|V_{vu}\right|\cdot\left|V_{vu}-1\right| }\cdot\left|V_{vu}\right|^{\lambda}, \tag{24}\]

\[\mathbf{W}=(\frac{w_{vu}}{\sum_{u\in N(v)}w_{vu}})_{v,u\in V}, \tag{25}\]

\[h_{v}^{(l+1)}=\mathrm{MLP}_{\theta}\left(\gamma^{(l)}\left(\sum_{u\in N(v)} \mathbf{W}_{vu}+1\right)\mathbf{h}_{v}^{(l)}\right. \tag{26}\]
where \(\lambda>0\) and the overlap subgraph is denoted as \(\mathcal{G}_{vu}=(V_{vu},E_{vu})=S_{v}\cap S_{u}\) for neighboring nodes \(v\), \(u\). \(\mathbf{W}\) is the weight matrix. \(\gamma\) and \(\theta\) is learnable scalar parameter.

**GNN-AK**[94] extends the scope of local aggregation in GNNs beyond 1-hop neighbors (star-like) into more generalized subgraphs. This method, termed as GNN-AK, computes the encoding of induced subgraphs of nodes and serves as a wrapper to uplift any GNN, where GNN perform as a kernel. Let \(N_{k}(v)\) be the set of nodes in the k-hop egonet rooted at node \(v\), containing node \(v\). For \(N_{k}(v)\subseteq\mathcal{V}\), \(G[N_{k}(v)]\) is the induced subgraph of \(v\): \(G[N_{k}(v)]=(N_{k}(v),(i,j)\in\mathcal{E}|i,j\in N_{k}(v)\). Every subgraph \(G[N_{k}(v)]\) is encoded as \(\mathbf{g}_{sub(v)}\), concatenating with the node embedding \(\mathbf{h}_{sub(v)}\) aggregated from \(N_{k}(v)\), to obtain the final embedding \(\mathbf{h}_{v}\):

\[\mathbf{g}_{\mathrm{sub}(v)}^{(l+1)}=\mathrm{POOL}^{(l)}(\mathbf{h}_{\mathrm{ sub}(i)}|i\in N_{k}(v)), \tag{27}\]

\[\mathbf{h}_{v}=\mathrm{CON}(\mathbf{g}_{\mathrm{sub}(v)},\mathbf{h}_{\mathrm{ sub}(v)}). \tag{28}\]

**NGNN** Similar to the design philosophy of GNN-AK, Nested Graph Neural Networks (NGNNs) [95] extract a local subgraph around each node and apply a GNN to learning the representation of each subgraph. The overall graph representation is obtained by aggregating these subgraph representations. However, NGNN differs from GNN-AK in subgraph design. Specifically, the height of the rooted subgraph in NGNN can be determined based on the given hop of the node.

**MPSN** The Message Passing Simplex Networks (MPSNs) [96], which operates message passing on simplicial complexes (SCs) [108]. SCs are in correspondence with subgraph topology, where SCs of varying dimensions concretize topology information of graph at different levels. Specifically, 0-simplices can be interpreted as vertices, 1-simplices as edges, 2-simplices as triangles, and so on.

**ESAN** An empirical observation is that although two graphs may not be discriminable by MPNNs, they generally contain distinguishable subgraphs. Thus, [97] recommends representing each graph as a set of subgraphs derived from a predefined policy and proposes a novel equivariant subgraph aggregation network (ESAN) framework for handling them, which comprises the DSS-GNN architecture and subgraph selection policy. The core of the approach is to represent the graph \(G\) as a bag (multiset) \(S_{G}=\{\{G_{1},...,G_{m}\}\}\) of its subgraphs, and to make a prediction on a graph based on this subset. Motivated by the linear characterization, DSS-GNN adopt the same layer topology:

\[F_{DSS-GNN}=E_{\mathrm{sets}}\circ R_{\mathrm{subgraphs}}\circ E_{\mathrm{ subgraphs}}, \tag{29}\]

\[E_{\mathrm{subgraphs}}:(L(\mathbf{A},\mathbf{X}))_{i}=L^{1}(\mathbf{A}_{i}, \mathbf{X}_{i})+L^{2}(\sum_{j=1}^{m}\mathbf{A}_{j},\sum_{j=1}^{m}\mathbf{X}_{ i}), \tag{30}\]

where \(E_{\mathrm{subgraphs}}\) is an equivariant feature encoding layer, \(R_{\mathrm{subgraphs}}\) is a subgraph readout layer, \(E_{\mathrm{sets}}\) is a universal set encoding layer. And \((L(\mathbf{A},\mathbf{X}))_{i}\) denotes the output of the layer on the i-th subgraph, \(L^{1},L^{2}\) represent two graph encoders and can be any type of GNNs layer.

The methods outlined above pertain primarily to explicit utilization of subgraph topology, however implicit utilization can also serve to enhance the learning of graph topology.

**LPR-GNN** Inspired by RP-GNN [86] and subgraph counting task, the Local Relational Pooling model (LRP-GNN) [55] is proposed to achieve competitive performance on sub-topology counting. LRP-GNN refers to RP-GNN that operates on subgraphs essentially, but in comparison to previous works [92, 93, 94], LRP can not only compute sub-topology, but also learn they relevant relation of sub-topology.

**k-GNN** The higher-order message passing (k-GNN) scheme, implicitly utilizes subgraphs. The k-WL test serves as the foundation for k-GNNs. Whereas the standard WL test iteratively aggregates neighbors of a single node, k-WL operates on tuples of k-nodes for iterative aggregation. These k-tuples can be interpreted as subgraphs, where

Fig. 10: The update strategy of P-GNN. (a) is anchor nodes sets of different sizes. (b) is the process of the embedding of \(v_{1}\) in the \(l\)-th layer. This figure is referenced to [53] Figure 2.
higher-order message passing occurs between subgraphs. Equation 31 redefines the neighborhood representation of k-tuples, and Equation 32 enables reliable capture of inherent local graph topology through information propagation and embedding update over k-neighborhoods. It has been proved that the discrimination power of 1-WL is equivalent to 2-WL. Moreover, for k\(\geq\)2, (k+1)-WL is strictly more powerful than k-WL. Notably, 3-WL is considered to be the strongest expressive power to identify all non-isomorphic graphs to date [26, 109]. The k-GNNs expressive power is equal to k-WL, hence when k\(\geq\)2, k-GNNs offers the strongest expression rivaled to 3-WL.

\[N(s)=\left\{t\in[V]^{k}\|s\cap t\mid=k-1\right\}, \tag{31}\]

\[\mathbf{h}_{k}^{(l+1)}(s)=\sigma\left(\mathbf{h}_{k}^{(l)}(s)\cdot\mathbf{W}_ {1}^{(l+1)}+\sum_{u\in N(s)}\mathbf{h}_{k}^{(l)}(u)\cdot\mathbf{W}_{2}^{(l+1)} \right), \tag{32}\]

Where all subsets of size \(k\) over the set \(\mathcal{V}\) are considered as \([V]^{k}\), where a \(k\)-set in \([V]^{k}\) is denoted by \(s=\{v_{1},\ldots,v_{k}\}\) as the central tuple. Moreover, \(N(s)\) denotes the neighborhood of \(s\), and \(\mathbf{W}_{1}\), \(\mathbf{W}_{2}\) are the parameter matrix.

**K-hop GNN** In MPNN, the representation of a node is updated by aggregating its direct neighbours, which are called 1-hop neighbours. Some work extends the message passing to the concept of [110, 111, 112, 113, 114] K-hops. In K-hop message passing, the node representation is updated not only by aggregating the information of the node's 1-hop neighbours, but also by aggregating all the neighbours within the node's K-hop. The K-hop neighbours of node \(v\) refer to all neighbours whose distance from node \(v\) is less than or equal to K. Denote by \(N(v)^{k}\) the K-th hop neighbour of node \(v\), i.e., the neighbour whose distance to the node is exactly equal to K.

\[\mathbf{m}_{v}^{(l,k)}=\mathrm{MSG}^{(l)}\left(\left\{\right\}\mathbf{h}_{u}^{ (l-1)}:u\in N(v)^{k}\right\}\right), \tag{33}\]

\[\mathbf{h}_{v}^{(l,k)}=\mathrm{UPD}^{(l)}\left(\mathbf{m}_{v}^{(l,k)}, \mathbf{h}_{v}^{(l-1)}\right). \tag{34}\]

\[\mathbf{h}_{v}^{(l)}=\mathrm{AGG}^{(l)}\left(\left\{\right\}\mathbf{h}_{v}^{ (l,k)}|k=1,2,...,K\right\}\right), \tag{35}\]

The K-hop message passing is more powerful than 1-WL and can distinguish almost all rule-graphs, but its expressive power is similarly limited by 3-WL.

**KP-GNN**[99] introduced K-hop peripheral-subgraph-enhanced GNN (KP-GNN), a new GNN framework with k-hop message passing, which significantly improves the expressive power of K-hop GNN. KP-GNN aggregates in the neighbour aggregation of each hop not only the neighbouring nodes, but also aggregates peripheral subgraphs (subgraphs induced by neighbours in that hop). This additional information helps KP-GNN learn more expressive local topology information around nodes. This improvement occurs in the message passing process:

\[\mathbf{m}_{v}^{(l,k)}=\mathrm{MSG}^{(l)}\left(\left\{\right\}\mathbf{h}_{u}^ {(l-1)}:u\in N(v)^{k}\right\}\right),G_{v}^{k})\,, \tag{36}\]

Where \(G_{v}^{k}\) is subgraphs induced by neighbours of \(v\) in hop \(k\).

#### 4.4.4 Encoding the global-topology

Encoding the global-topology is to directly extract the topology information of the whole graph for learning.

**Eigen-GNN** Zhang et al. [91] introduced the topology eigen decomposition module, designed as a universal plug-in to GNNs termed as Eigen-GNN. This approach incorporates eigen decomposition of the adjacency matrix \(\mathbf{A}\) of the graph to obtain eigenvectors as topology features, which are subsequently concatenated with node features. The resulting amalgamation is then utilized as input to GNNs, as denoted in Equation 37.

\[\mathbf{H}^{(0)}=[\mathbf{X},f(\mathbf{Q})], \tag{37}\]

where \(\mathbf{Q}\) is the eigenvectors corresponding to the top-d largest absolute eigenvalues of \(\mathbf{A}\), \(f\) is a function such as normalization or identity mapping.

### _GNNs architecture enhancement_

As can be seen from the previous analysis, GNNs cannot learn the correct graph topology information due to the permutation invariant aggregation functions, thus losing its expression. Therefore, in addition to directly encoding topology information for learning, optimizing the GNNs architecture also helps GNNs learn more topology information for expressing by improving aggregation operations or designing equavariant GNNs without aggregation operation. A detailed description of this method of optimizing the GNNs architecture is shown in Figure 11.

#### 4.5.1 Improving aggregation functions

Improving aggregation functions involves improvements to the aggregation operations, wherein most of the modifications are made while retaining the permutation invariance

Fig. 11: A detailed description of this method of GNNs architecture enhancement.
of the aggregation function. However, there exist a few exceptions to break the permutation invariance. The improvement of aggregator that preserves invariance is established based on the theory proposed by Xu et al. [27].

**GIN** The essence of MPNN is actually a function that maps multiple set, where allow repeated elements to exist. The capacity of multi-set functions to discern these repeated elements inherently constrains the expressive power of MPNN. As a result, optimizing the aggregation function necessitates the development of an injective function operating on multisets, ensuring distinct embeddings for different nodes. The graph isomorphism network (GIN) is a simple architecture to satisfy this prerequisite:

\[\mathbf{h}_{v}^{(l+1)}=\mathrm{MLP}\left(\left(1+\varepsilon^{(l)}\right) \mathbf{h}_{v}^{(l)}+\sum_{u\in N(v)}\mathbf{h}_{u}^{(l)}\right), \tag{38}\]

where \(\varepsilon^{(l)}\) represents the learnable or fixed scalar and the MLP plays a critical role in strengthening the expressive power by ensuring the injective property.

**modular-GCN** The global parameter assignment strategy enforced by GCN is actually a permutation invariant aggregation operation. Dehmamy et al. [100] has insight into the loss of topology information in GCN, and designed three GCN modules using three different propagation strategies as (1)\(f_{1}=\mathbf{A}\), (2)\(f_{2}=\mathbf{D}^{-1}\mathbf{A}\), and (3)\(f_{3}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}\) to address this limitation. Combining the three GCN modules compensates for the loss of missing topology information, realizing the optimization of the aggregation function.

Furthermore, the general aggregation operations in GNNs are interpreted as graph convolutions. The graph topology acts as a node feature filter, smoothing node features during the convolution process, which corresponds to a filtering operation. Thereby enable the analysis of GNNs expressive power through spectral decomposition techniques [31].

**diagonal-GNN** Kanatsoulis et al. [32] utilizes spectral decomposition tools to view GNNs as graph feature filters, as shown in Equation 39, and proposed a GNN designed with the diagonal modules (diagonal-GNN). The use of diagonal modules allows GNNs to capture broader topology relationships while also capturing neighborhood relationships, enabling GNNs show the equivalent recognition abilities of featured graphs even on unfeatured graphs.

\[\mathbf{H}=\sigma(\sum_{k=0}^{K-1}\mathbf{A}^{k}\mathbf{X}\mathbf{W}_{k}), \tag{39}\]

\[diagonal-GNN:\mathbf{H}=\sigma(\sum_{k=0}^{K-1}diag(\mathbf{A}^{k})\mathbf{X} \mathbf{W}_{k}), \tag{40}\]

where \(K\) is the length of graph filter, \(\sigma\) denotes a nonlinearity, \(\mathbf{W}_{k}\) is the filter parameters and can be a matrix, a vector, or a scalar.

**GNN-LF/HF** Leveraging spectral decomposition tools to design various convolution processes to handle specific filtering conditions, GNNs can recognize and process more complex low-frequency or high-frequency information. [30] considers two distinct modes of low-pass filtering (LF) and high-pass filtering (HF), develop corresponding convolution operations, and design new models GNN-LF/HF respectively.

The propagation mechanism of GNN-LF can be expressed by the following equations:

\[\mathbf{H}^{(l+1)} =f_{\mathrm{COM}}(\frac{1+\alpha\mu-2\alpha}{1+\alpha\mu-\alpha }\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\mathbf{ H}^{(l)}\] \[+\frac{\alpha\mu}{1+\alpha\mu-\alpha}\mathbf{X}+\frac{\alpha- \alpha\mu}{1+\alpha\mu-\alpha}\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1/2}\mathbf{X}), \tag{41}\]

\[\mathbf{H}^{(0)}=\frac{\mu}{1+\alpha\mu-\alpha}\mathbf{X}+\frac{1-\mu}{1+ \alpha\mu-\alpha}\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D }}^{-1/2}\mathbf{X}. \tag{42}\]

The propagation mechanism of GNN-HF is given by the following equations:

\[\mathbf{H}^{(l+1)} =f_{\mathrm{COM}}(\frac{\alpha\beta-\alpha+1}{\alpha\beta+1} \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\mathbf{ H}^{(l)} \tag{43}\] \[+\frac{\alpha}{\alpha\beta+1}\mathbf{X}+\frac{\alpha\beta}{ \alpha\beta+1}\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{- 1/2}\mathbf{X}),\]

\[\mathbf{H}^{(0)}=\frac{1}{\alpha\beta+1}\mathbf{X}+\frac{\beta}{\alpha\beta+1 }\tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}\mathbf{ X}, \tag{44}\]

where \(\mu\), \(\alpha\), \(\beta\) are hyper parameters that control the trade-off between the topology and feature information at different scales. \(\tilde{\mathbf{A}}\) and \(\tilde{\mathbf{D}}\) are the normalized adjacency matrix and the diagonal degree matrix, respectively, that account for the topology of the graph data.

**Geom-GCN** Pei et al. [101] leverage the network geometry theory to propose a geometric aggregation scheme, implemented within graph convolution networks as Geom-GCN. This scheme maps graphs to a continuous latent space via node embeddings and subsequently constructs topology neighborhoods based on the geometric relations defined in the latent space, effectively preserving the intricate topological patterns present within the graphs. Building upon the definition of the original neighborhood, they further define topology neighborhoods \(\mathcal{N}(v)=(\{N_{g}(v),N_{s}(v)\},\tau)\), consisting of a set of neighborhood \(\{N_{g}(v),N_{s}(v)\}\) and a relation operator on neighborhoods \(\tau\). \(N_{g}(v)=\{u|u\in\mathcal{V},(u,v)\in\mathcal{E}\}\) is the neighborhood in the graph. \(N_{s}(v)=\{u|u\in\mathcal{V},d(\mathbf{z}_{u},\mathbf{z}_{v})<\rho\}\) is the neighborhood in the latent space, where \(d\) is the distance function, \(\rho\) is the pre-given parameter, and \(\mathbf{z}_{v}\in\mathbf{R}\) can be considered as the position of nodes in the latent space via the mapping \(f:v\rightarrow\mathbf{z}_{v}\). And \(\tau:(\mathbf{z}_{v},\mathbf{z}_{u})\to r\in R\), where \(R\) is the set of the geometric relationships and \(r\) can be specified as an arbitrary geometric relationship of interest according to the particular latent space andapplications. On the basis, a bi-level aggregation scheme is introduced:

\[\mathbf{m}_{(i,r)}^{v,l+1}=\underset{i\in g,s}{\mathrm{AGG}_{i}}(\{\mathbf{h}_ {u}^{l}|u\in N_{i}(v),\tau(\mathbf{z}_{u},\mathbf{z}_{u})=r\}), \tag{45}\]

\[\mathbf{m}_{v}^{l+1}=\underset{i\in g,s}{\mathrm{AGG}_{2}}((\mathbf{m}_{(i, r)}^{v,l+1},(i,r))), \tag{46}\]

where \(\mathbf{m}_{(i,r)}^{v,l+1}\) can be considered as the feature of virtual nodes in the latent space which is indexed by \((i,r)\) which is
corresponding to the combination of a neighborhood \(i\) and a relationship \(r\).

The approach of optimizing the permutation invariant aggregation function presents significant limitations. Therefore, alternative designs have been proposed to address this constraint.

**PG-GNN** Permutation sensitive functions are regarded as a symmetry breaking mechanism that disrupts the equidistant status of adjacent nodes, allowing for the capture of relationships between neighboring nodes. However, few permutation-sensitive GNNs [11, 85, 1] are available to real-world applications, due to their complexity. Huang et.al. [102] adopts Recurrent neural networks (RNNs) to model the dependency relationships between neighboring nodes as a permutation-sensitive function approach, wherein all permutations \(\pi\) act on the \(\mathcal{V}\), leading to the following aggregation strategy:

\[\mathbf{h}_{v}^{(l+1)}=\sum_{\pi\text{in}\Pi}\mathrm{RNN}(\mathbf{h}_{\pi(u_ {1})}^{(l)},\mathbf{h}_{\pi(u_{2})}^{(l)},...,\mathbf{h}_{\pi(u_{n})}^{(l)})+ \mathbf{W}^{(l)}\mathbf{h}_{v}^{(l)}, \tag{47}\]

where \(u_{1:n}\in N(v)\), \(\mathbf{W}\) is the parameter matrix.

#### 4.5.2 Adopting equivariant architecture

The bottleneck of GNNs expressive power lies in the permutation invariance of their aggregation operators [77]. While the limitation only serves as a condition to induce permutation equivariance, rather than a requisite component in GNN design. Consequently, abandoning aggregation operations and employing distinct arrangements of equivariant functions or operators can lead to the direct design of equivariant GNNs [17, 18, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 222, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265, 266, 267, 268, 269, 270, 271, 272, 273, 274, 275, 276, 277, 278, 279, 280, 281, 282, 283, 284, 285, 286, 287, 288, 289, 290, 282, 284, 286, 287, 289, 288, 289, 291, 285, 286, 287, 288, 289, 280, 289, 281, 282, 285, 283, 286, 287, 288, 289, 282, 286, 289, 292, 287, 288, 289, 280, 281, 289, 282, 283, 285, 286, 287, 288, 289, 280, 282, 287, 288, 289, 280, 283, 289, 284, 285, 286, 287, 288, 289, 281, 289, 280, 282, 286, 287, 288, 289, 289, 280, 281, 282, 289, 280, 283, 284, 285, 286, 287, 288, 289, 282, 289, 281, 282, 286, 287, 288, 289, 280, 284, 289, 285, 286, 287, 289, 288, 281, 288, 289, 280, 282, 281, 283, 284, 285, 286, 287, 288, 289, 282, 289, 280, 284, 286, 288, 287, 289, 282, 285, 286, 288, 289, 287, 288, 289, 280, 289, 280, 281, 282, 283, 285, 286, 287, 288, 289, 282, 289, 280, 284, 286, 287, 288, 289, 282, 28, 281, 28, 285, 286, 287, 288, 28, 289, 282, 2
area of research holds the promise of clarifying these internal constraints and unraveling the mysteries of the GNN's black-box.

**The physics-informed Designs.** Message passing, as the mainstream paradigm of GNNs, has achieved great success in many applications. However, in terms of expressive power, MPNN is constrained by the WL test constantly. While other frameworks such as LGNN have been successfully applied, their potential for further development is restricted by the complexity of tensor calculations. Bronstein et al. [92] develop a continuous learning GNN model inspired by physics, which draws on differential geometry, algebraic topology, and differential equations. Their model departs from the traditional MPNN framework, introducing a completely new design and exhibiting unprecedented expressive power. Such advancements are expected to pave the way for the development of additional GNN models that challenge the limitations of the MPNN paradigm, which has long dominated the field.

**Graph neural architecture search**. Adopting a modular design for GNNs, without altering the original architecture, can enhance their expressive capacity to varying degrees. This finding underscores the potential promise of graph neural architecture search (GraphNAS) for boosting expressive power. Developing powerful GNN models often necessitates expertise and presents a significant calculation threshold. GraphNAS represents a low-cost and efficient means of automating GNN design. However, current efforts in graph neural architecture search prioritize model generalization over expressiveness in the search space design. Therefore, the challenge lies in designing a specific search space that facilitates the automated design of a powerful GNN model. This issue remains a pressing problem for the research community to tackle.

## 6 Conclusion

Research on the GNNs expressive power has matured considerably, with an increasing number of improved models emerging. However, these studies have not significantly contributed to a deeper understanding of GNNs expressive power. Consequently, we propose a unified theoretic framework for delineating GNNs expressive power, encompassing the definition, limitations, and analysis of the factors influencing expression. Furthermore, we utilize this framework to summarize and categorize the methods currently employed for enhancing GNNs expressive power. Overall, as a paradigm of graph learning models, GNNs expressive power pertains to both graph features and topology. Accordingly, devising methods should address both aspects. Our unified framework offers a novel, standardized path for researching GNNs expressive power in this context.
