Expressivity of Graph Neural Networks Through the Lens of Adversarial
  Robustness
We perform the first adversarial robustness study into Graph Neural Networks
(GNNs) that are provably more powerful than traditional Message Passing Neural
Networks (MPNNs). In particular, we use adversarial robustness as a tool to
uncover a significant gap between their theoretically possible and empirically
achieved expressive power. To do so, we focus on the ability of GNNs to count
specific subgraph patterns, which is an established measure of expressivity,
and extend the concept of adversarial robustness to this task. Based on this,
we develop efficient adversarial attacks for subgraph counting and show that
more powerful GNNs fail to generalize even to small perturbations to the
graph's structure. Expanding on this, we show that such architectures also fail
to count substructures on out-of-distribution graphs.
Francesco Campi, Lukas Gosch, Tom Wollschläger, Yan Scholten, Stephan Günnemann
# Expressivity of Graph Neural Networks

###### Abstract

We perform the first adversarial robustness study into Graph Neural Networks (GNNs) that are provably more powerful than traditional Message Passing Neural Networks (MPNNs). In particular, we use adversarial robustness as a tool to uncover a significant gap between their theoretically possible and empirically achieved expressive power. To do so, we focus on the ability of GNNs to count specific subgraph patterns, which is an established measure of expressivity, and extend the concept of adversarial robustness to this task. Based on this, we develop efficient adversarial attacks for subgraph counting and show that more powerful GNNs fail to generalize even to small perturbations to the graph's structure. Expanding on this, we show that such architectures also fail to count substructures on out-of-distribution graphs.

Machine Learning, Graph Neural Networks, Graph Neural Networks

## 1 Introduction

In recent years, significant efforts have been made to develop Graph Neural Netwoks (GNNs), for several graph-related tasks, such as molecule property predictions (Gasteiger et al., 2020), social network analysis (Fan et al., 2019), or combinatorial problems (Gasse et al., 2019), to name a few. The most commonly used architectures are based on message passing, which iteratively updates the embedding of each node based on the embeddings of its neighbors (Gilmer et al., 2017). Despite their broad success and wide adoption, different works have pointed out that so called Message Passing Neural Networks (MPNNs) are at most as powerful as the 1-Weisfeiler-Lehman (WL) algorithm (Morris et al., 2019; Xu et al., 2019) and thus, have important limitations in their expressive power (Chen et al., 2020). This encouraged the development of provably more powerful architectures.

However, there is no guarantee that the training process also yields models that are as powerful as theoretically guaranteed. Thus, this work investigates if and to what extent the empirically achieved expressivity of such GNNs lacks behind their theoretic possibilities by taking a novel look from the perspective of adversarial robustness. In particular, we focus on the task of counting different subgraphs, which is provably impossible for MPNNs (Chen et al., 2020) (except for very limited cases), but important for many downstream tasks (Huang et al., 2023; Liu et al., 2019; Monti et al., 2018).

Using our new adversarial framework for subgraph counting, we find that the counting ability of theoretically more powerful GNNs fail to generalize even to small perturbations to the graph's structure (see Figure 1). A result even more interesting given that subgraph counting is polynomially solvable for fixed subgraph sizes (Shervashidze et al., 2009).1 We expand on these results and show that these architectures also fail to count substructures on out-of-distribution (OOD) graphs. Furthermore, retraining the last MLP layers responsible for the prediction based on the graph embedding does not entirely resolve this issue.

Footnote 1: In general, this problem is NP-complete (Ribeiro et al., 2021)

**Contributions.** (i) We perform the first study into the adversarial robustness of GNNs provably more powerful than the 1-WL and use it as an effective tool to uncover a significant gap between the theoretically possible and empirically achieved expressivity for substrucu

Figure 1: GNNs more powerful than 1-WL are not adversarially robust for subgraph-counting tasks.
(see Section 6). (ii) We extend the concept of an adversarial example from classification to (integer) regression tasks and develop multiple perturbations spaces interesting for the task of subgraph counting (see Section 4). (iii) We develop efficient and effective adversarial attacks for subgraph counting, operating in these perturbations spaces and creating _sound_ perturbations, i.e., where we know the ground truth (see Section 5). (iv) In Section 6.2 we show that subgraph-counting GNNs also fail to generalize to out-of-distribution graphs, providing additional evidence that these GNNs fail to reach their theoretically possible expressivity. Our code implementation can be found at [https://github.com/francesco-campi/Rob-Subgraphs](https://github.com/francesco-campi/Rob-Subgraphs).

## 2 Background

We consider undirected, unattributes graphs \(G\)=\((V,E)\) with nodes \(V\)=\(\{1,\ldots,n\}\) and edges \(E\)\(\subseteq\)\(\{\{i,j\}\mid i,j\in V,i\neq j\}\), represented by adjacency matrix \(\mathbf{A}\in\{0,1\}^{n\times n}\). A graph \(G_{S}=(V_{S},E_{S})\) is a _subgraph_ of \(G\) if \(V_{S}\subseteq V\) and \(E_{S}\subseteq E\). We say \(G_{S}\) is an _induced_ subgraph if \(E_{S}\) contains all edges in \(E\) that connect pairs of nodes in \(V_{S}\). An egonet \(\mathrm{ego}_{l}(i)\) is the induced subgraph containing all nodes with a distance of at most \(l\) from root node \(i\). Furthermore, two graphs \(G,G^{\prime}\) are isomorphic (\(\simeq\)) if there exists a bijection \(f:V\to V^{\prime}\) such that \(\{i,j\}\in E\) if and only if \(\{f(i),f(j)\}\in E^{\prime}\). Lastly, the diameter \(\mathrm{diam}(G)\) denotes the length of the largest shortest path in graph \(G\).

### Subgraph-Counting

Consider a fixed graph \(H\) which we call a pattern (Figure 2). A classic graph-related problem is the _(induced-) subgraph-counting_ of the pattern \(H\)(Ribeiro et al., 2021), which consists of enumerating the (induced) subgraphs of \(G\) isomorphic to \(H\). The subgraph-count of \(H\) is denoted by \(\mathcal{C}(G,H)\), and by \(\mathcal{C}_{I}(G,H)\) in the induced case. To simplify the notation we will also refer to it as \(\mathcal{C}(G)\) if \(H\) is given in the context. Several algorithms have been developed to solve the task of subgraph-counting. In this work we specifically consider the (exact) algorithm of Shervashidze et al. (2009) (presented in Appendix B) due to its low computational cost.

### Expressivity of Graph Neural Networks

The expressivity of machine learning models is about which functions they can and cannot approximate. There are different ways of studying the expressive power of GNNs. In this work we specifically consider their ability to count subgraphs (Chen et al., 2020) because it is strictly related to different real-world tasks such as computational chemistry (Jin et al., 2020) and social network analysis (Jiang et al., 2010). We define the ability to count subgraphs as follows:

**Definition 2.1**.: A family of functions \(\mathcal{F}\) can perform _subgraph-counting_ of a target pattern \(H\) on a graph class \(\mathcal{G}\) if for any two graphs \(G_{1},G_{2}\in\mathcal{G}\) with \(\mathcal{C}(G_{1},H)\neq\mathcal{C}(G_{2},H)\) there exists a function \(f\in\mathcal{F}\) such that \(f(G_{1})\neq f(G_{2})\).

Surprisingly, MPNNs have considerable limitations in subgraph-counting. In fact, Chen et al. (2020) show that MPNNs are not able to count induced patterns with three or more nodes, leaving out only the ability to count edges. For example, Figure 3 shows two graphs that, despite having different triangle counts, will always return identical outputs when fed in the same MPNN.

A different perspective to measure the expressive power is graph isomorphism. In this regard, Xu et al. (2019); Morris et al. (2019) demonstrated that an MPNN is at most as powerful as 1-WL isomorphism test at distinguishing pairs of non-isomorphic graphs. Moreover, since the WL algorithms are designed to extract representation vectors from graphs, they could be used also to perform subgraph-counting. In particular, Chen et al. (2020) showed that \(k\)-WL, and equivalently powerful architectures, can perform substructure-counting for patterns with at most \(k\) nodes, creating a connection between the two approaches.

### More Expressive Graph Neural Networks

In this work, we analyze two state-of-the-art architectures for the task of subgraph counting: PPGN (Maron et al., 2019), and I\({}^{2}\)-GNN (Huang et al., 2023). PPGN represents the graph structure in a tensor and exploits tensor multiplications to enhance the expressivity. It reaches the same expressive power of 3-WL, which makes it capable of counting patterns of size three. I\({}^{2}\)-GNN, following the approach of subgraph GNNs (Frasca et al., 2022), decomposes the whole graph into different subgraphs and processes them independently with an MPNN. It has been explicitly developed to be expressive enough for counting different substructures and most important for this work, can count arbitrary patterns of size four. Both, PPGN and I\({}^{2}\)-GNN are effective architectures for downstream tasks such as molecular property predictions.

Figure 3: Pair of undistinguishable graphs for MPNNs with different triangle counts.

Figure 2: Examples of graph patterns used for subgraph-counting.
## 3 Related Work

Chen et al. (2020) were the first to study the expressivity of GNNs w.r.t. their ability to count substructures. They, and later Tahmasebi et al. (2021) proposed architectures for counting substructures. However, these suffer from high computational complexity. Yu et al. (2023) proposed an architecture purely focusing on subgraph counting. However, subgraph counting alone can be solved by efficient randomized algorithms (Bressan et al., 2021). Thus, in this work, we focus on efficient architectures, which leverage their subgraph counting ability to improve generalization for other downstream tasks. In particular, we focus on PPGN (Maron et al., 2019) and I\({}^{2}\)-GNN (Huang et al., 2023). Both achieve state-of-the-art results for substructure counting while having formal expressivity guarantees.

Different works have studied the adversarial robustness of GNNs for graph-level classification (Dai et al., 2018) and node-level classification (Zugner et al., 2018). Regarding the latter, Gosch et al. (2023) exactly define (semantic-preserving) adversarial examples. Moreover, Geisler et al. (2022) use adversarial attacks with sound perturbation models, i.e., where the ground truth change is known, to investigate the generalization of neural combinatorial solvers. Conversely, adversarial robustness for regression tasks has currently received very little attention (Deng et al., 2020).

## 4 Robustness in Subgraph-Counting

The field of adversarial robustness is about the problem that machine learning models are vulnerable to small changes to their inputs (Goodfellow et al., 2015). In particular, for the subgraph-counting problem we want to analyze whether the error of the models increases when tested on perturbed input graphs \(\tilde{G}\) of a graph from a set of perturbed graphs \(\mathcal{P}(G)\). To evaluate the performance of a model \(f\) on perturbed graphs \(\tilde{G}\in\mathcal{P}(G)\) we use the following adversarial loss:

\[\ell_{adv}(\tilde{G}):=|f(\tilde{G})-\mathcal{C}(\tilde{G},H)|.\]

### Subgraph-Counting Adversarial Examples

To empirically evaluate the expressivity of machine learning models for subgraph-counting via adversarial robustness, we have to introduce a notion of adversarial example. In classification tasks adversarial examples are simply perturbations that change the predicted class. In general regression tasks one can define a threshold on \(\ell_{adv}\) for which we call a perturbed graph an adversarial example (Deng et al., 2020). However, this definition is application-dependent and, in our work, we define a specific threshold exploiting the fact that subgraph-counting is an _integer_ regression task.

**Definition 4.1**.: Given a model \(f\) and clean graph \(G\), we say that \(\tilde{G}\in\mathcal{P}(G)\) is an _adversarial example_ for \(f\) if:

1. \(\lfloor f(G)+0.5\rfloor=\mathcal{C}(G)\)
2. \(\lfloor f(\tilde{G})+0.5\rfloor\neq\mathcal{C}(\tilde{G})\)
3. \(\frac{\ell_{adv}(\tilde{G})-\ell_{adv}(G)}{\ell_{adv}(G)}>\delta\).

The conditions \((i)\) and \((ii)\) guarantee that the model prediction, when approximated to the nearest integer, is correct for \(G\) and wrong for \(\tilde{G}\). Here, having a correct initial prediction is essential to clearly distinguish the performances on the original graph from the perturbed graph. In addition, the condition \((iii)\) ensures that a margin exists between the errors on the original data instance and the perturbed one, and the size of the margin depends on the value of \(\delta\). This requisite prevents easily generating adversarial examples from graphs that are almost wrongly predicted, i.e. \(\ell_{adv}(G)\approx 0.5\).

### Perturbation Spaces

We define different perturbation spaces for a graph \(G\) as constrained sets of structurally perturbed graphs constructed from \(G\). In particular, we consider different combinations of edge deletions and additions, for example \(E^{\prime}=E\cup\{i,j\}\) with \(\{i,j\}\notin E\) represents an edge addition. We always consider sound perturbation models, i.e, where we know the ground truth change. These are efficiently implemented as described in Section 5. It is meaningful to limit the number of perturbations in order to control how shifted the distribution of the perturbed subgraph-counts is compared to the distribution of the original ones. Then, we define the _constrained_ perturbation space with maximal budget \(\Delta\) as:

\[\mathcal{P}_{\Delta}(G):=\{\tilde{G}\mid\frac{1}{2}\|\mathbf{A}-\mathbf{A}^{ \prime}\|_{0}\leq\Delta\}, \tag{1}\]

where \(\|\cdot\|_{0}\) represents the number of non-zero elements, i.e. the number of perturbed edges.

**Semantic-Preserving Perturbations.** Additionally, we conduct a robustness analysis more closely in line with adversarial examples for classification tasks, by incorporating a further constraint to guarantee the preservation of a specific level of semantic meaning. In particular, we define the _count-preserving_ perturbation space as:

\[\mathcal{P}_{\Delta}^{c}(G)\coloneqq\{\tilde{G}\mid\tilde{G}\in\mathcal{P}_{ \Delta}(G)\ \wedge\ \mathcal{C}(\tilde{G})=\mathcal{C}(G)\}. \tag{2}\]

Additionally, when considering induced subgraphs, keeping the count constant does not guarantee that the subgraphs isomorphic to the pattern remain the same. In fact, perturbations can simultaneously delete a subgraph isomorphic to the pattern and generate a new one (see Figure 4). We will denote the _subgraph-preserving_ perturbation space by

\[\mathcal{P}_{\Delta}^{s}(G)\coloneqq\{\tilde{G}\mid\tilde{G}\in \mathcal{P}_{\Delta}(G)\wedge \tag{3}\] \[G_{S}\subseteq G,G_{S}\simeq H\iff G_{S}\subseteq\tilde{G},G_{S }\simeq H\}.\]
## 5 Subgraph-Counting Adversarial Attacks

For a subgraph-counting model \(f\), the goal of an adversarial attack is to find the pertubed graph \(G^{*}\in\mathcal{P}(G)\) that causes the maximal error increase. This problem can be formulated as an optimization problem:

\[G^{*}=\operatorname*{argmax}_{\tilde{G}\in\mathcal{P}(G)}\ell_{adv}(\tilde{G}). \tag{4}\]

Attacking subgraph-counting GNNs for studying their empirical expressivity is particularly challenging. In fact, (i) the subgraph-count can vary significantly even for slight structural changes, and (ii) finding \(G^{*}\) of Equation (4) requires solving a discrete optimization problem.

### Sound Perturbations for Subgraph-Counting

To tackle the sensitivity of the counts to structural changes, we exploit the exact algorithm to update the ground-truth count after every perturbation. In this way, we generate sound perturbations since the exact ground-truth value is know. In order to prevent this step to become computationally prohibitive, we develop an efficient count updating scheme that uses only a small portion of the graph.

**Proposition 5.1**.: _Consider a graph \(G\) and a pattern \(H\) with \(\operatorname{diam}(H)=d\). Then, for every edges \(\{i,j\}\) we have that \(\operatorname{ego}_{d}(i)\) and \(\operatorname{ego}_{d}(j)\) contain all the subgraphs \(G_{S}\subset G\) such that \(G_{S}\simeq H\) and \(i,j\in V_{S}\)._

Proof in Appendix A.

When an edge \(\{i,j\}\) is perturbed, only the subgraphs containing both the end nodes can be affected and potentially change their isomorphism relation with \(H\). Therefore, according to Proposition 5.1, it is sufficient to verify potential count changes only in \(\operatorname{ego}_{d}(i)\) (or equivalently \(\operatorname{ego}_{d}(j)\)). Specifically, the theorem assumes that \(\{i,j\}\) is contained in the graph, hence we extract the egonet from the graph including \(\{i,j\}\) (original for edge deletion and perturbed for addition). Next, from the nodes of \(\operatorname{ego}_{d}(i)\) we generate the induced subgraphs \(G_{S}\) and \(\tilde{G}_{S}\) from the original and perturbed graphs respectively. Since the possible alterations of the subgraph-count are enclosed in \(G_{S}\) and \(\tilde{G}_{S}\), we have the following count update rule.

**Proposition 5.2**.: _Let \(\tilde{G}\) be a perturbation of a single edge of a graph \(G\), then there holds:_

\[\mathcal{C}(\tilde{G})=\mathcal{C}(G)+\mathcal{C}(\tilde{G}_{S})-\mathcal{C}( G_{S}).\]

Following Proposition 5.2 we need to run the subgraph-counting algorithm only on the smaller subgraphs \(G_{S}\) and \(\tilde{G}_{S}\), rather than on the whole graph \(\tilde{G}\). Additionally, Proposition 5.1 guarantees that potential changes in the subgraphs isomorphic to the patterns are also constrained in the egonet, thus it can be used also identify perturbations belonging to the subgraph-preserving perturbation space \(\mathcal{P}_{\Delta}^{s}\).

### Construction of Adversarial Examples

To create adversarial examples we need to solve the discrete optimization problem in Equation (4). To do so we develop algorithms that generate more powerful perturbation one change at a time, in this way, we keep track of the exact count with the update rule (Proposition 5.2).

**Greedy Search.** We develop an efficient and effective greedy search algorithm (Algorithm 1). At each step we select the most effective perturbation of the current perturbed graph \(\tilde{G}\) in \(\mathcal{P}_{1}(\tilde{G})\) (or in \(\mathcal{P}_{1}^{c}(\tilde{G}),\mathcal{P}_{1}^{s}(\tilde{G})\)) until the budget limit is reached. The new subgraph-counts of perturbations in \(\mathcal{P}_{1}(\tilde{G})\) are computed with Proposition 5.2, whereas the preserving perturbation spaces are generated with Algorithm 2.

```
Input:\(G,\Delta,k\) \(\mathcal{G}^{(0)}=\{G\}\) for\(i=0\)to\(\Delta-1\)do \(\mathcal{P}^{(i)}=\{\}\) for\(\tilde{G}\)in\(\mathcal{G}^{(i)}\)do \(\mathcal{P}^{(i)}=\mathcal{P}^{(i)}\cup\mathcal{P}_{1}(\tilde{G})\) \(\{\text{or}\ \mathcal{P}_{1}^{c}(G),\mathcal{P}_{1}^{s}(G)\}\) endfor \(\mathcal{G}^{(i+1)}=\)greatest \(k\) in \(\{\ell_{adv}(\tilde{G})\mid\tilde{G}\in\mathcal{P}^{(i)}\}\) endfor Return:\(G^{*}=\operatorname*{argmax}_{\tilde{G}\in\mathcal{G}^{(\Delta)}}\{\ell_{adv}( \tilde{G})\}\)
```

**Algorithm 1** Beam search (greedy search for \(k=1\))

**Beam search.** A more advanced algorithm that does not increase the computational complexity is beam search. Concretely, it follows simultaneously \(k\) different paths to explore more extensively the perturbation space (see Algorithm 1).

To improve the computational efficiency the perturbations in \(\mathcal{P}_{1}\) can be randomly selected according to the degrees of the end nodes of the perturbed edge. Concretely, the probability to pick the perturbation where the edge \(\{i,j\}\) has been added (or deleted) is proportional to \(d(i)^{2}+d(j)^{2}\), since intuitively these are the most relevant edges.

Figure 4: This Figure shows examples demonstrating that not all the count-preserving perturbations are also subgraph-preserving ones. On the left a subgraph- and count-preserving perturbation for 4-cycles where the red edge has been deleted. On the right a perturbation that leaves unchanged the count of 2-paths, but it deletes the induced substructure \(\{2,3,4\}\) to generate \(\{1,2,3\}\).
## 6 Experiments

In Section 6.1, we analyze the empirical expressivity of GNNs using our subgraph-counting adversarial attacks and using generalization as a (proxy) measure. Extending on this, in Section 6.2 we investigate if the same GNNs can count subgraph patterns for out-of-distribution graphs. Here we present the results of the induced subgraph-counting of triangles, 4-cycles and chordal cycles, for other patterns refer to Appendix C.

### Adversarial Robustness

Here, we analyze the empirical expressivity of GNNs using our subgraph-counting adversarial attacks.

Dataset and models.We generate a synthetic dataset of \(5\),\(000\) Stochastic-Block-Model graphs with 30 nodes divided into 3 different communities. The probabilities of generating edges connecting nodes within the same community are \([0.2,0.3,0.4]\), while the probability of generating edges between nodes of different communities is 0.1. We randomly split the dataset into training, validation, and test sets with percentages \(30\%,20\%,50\%\). We then train PPGN (Maron et al., 2019) and I\({}^{2}\)-GNN (Huang et al., 2023).

Experimental Settings.We train each model 5 times using different initialization seeds to prevent bad weight initialization influencing the final results. Then, for each of the trained models \(f_{i}\) with seed \(i\), we use our adversarial attacks (see Section 5) to generate adversarial examples from 100 correctly predicted test graphs and average the percentage of successful attacks over all seeds. Furthermore, we investigate if the adversarial graphs for a model \(f_{i}\) transfer to the other models \(f_{j}\) trained with a different initialization seed \(j\neq i\). We inspect all three different perturbation spaces with budgets \(\Delta\) of \(1\%,5\%,10\%\) and \(25\%\) with respect to the average number of edges of the graphs in the dataset and use \(\delta=1\) as margin. In detail, we use beam search with beam width \(k=10\) to explore \(\mathcal{P}^{*}_{\Delta}\) and \(\mathcal{P}^{*}_{\Delta}\), while we rely on greedy search for \(\mathcal{P}_{\Delta}\).

Results.The plots in Figure 5 show the percentage of perturbations found by the optimization algorithms that represent a successful adversarial example according to Definition 4.1. To condensate the results in a numerical value, we report in Table 1 the area under the curve (AUC) of the functions Non-Robust and Non-Robust (Transfer) in Figure 5. The results are reported as the proportion with respect to the area under the unity function \(f(x)=1\), which represents the worse case where all permutations generate an adversarial example already at \(\Delta=1\%\). Interestingly, the results show that we can find several adversarial examples for both architectures. In particular, PPGN is highly unrobust in the subgraph-counting of patterns with four nodes. However, several adversarial examples can be found also for the triangle count, even though the theoretical expressivity of PPGN claims that it is a family of functions that can count 3-dimensional subgraphs in the sense of Definition 2.1. Similarly, the more expressive model I\({}^{2}\)-GNN is fooled on 4-dimensional patterns, in spite of being sufficiently powerful to count them. This indicates that the empirical expressivity achieved does not match the theoretical expressivity since the models are not able to generalize to subgraph-counting tasks that they should in theory be able to solve. Additionally, in Appendix C.2 we investigate some structural properties of the adversarial examples.
**Experimental Settings.** Firstly, we train the PPGN and I\({}^{2}\)-GNN architectures on the dataset d\({}_{1}\) and test them on both d\({}_{1}\) and d\({}_{2}\) to investigate the OOD generalization performances of the architectures. Additionally, we train the models directly on d\({}_{2}\) to have a comparison of the best performances achievable on this dataset. The errors are expressed using the mean absolute error (\(\ell_{1}\)) and an extension of it, which is obtained by normalizing by the ground-truth count (\(\ell_{c}\)).

**Results.** Table 2 shows the test errors of the aforementioned settings averaged over five different initialization seeds. Here we observe that the models achieve very poor performances on general OOD graphs compared to their ideal performances (OOD and d\({}_{2}\) rows). However, if the model were able to perform subgraph-counting, as theoretically claimed, they should be able to perform this task regardless of the graph distribution. This result matches with Section 6.1 and shows that the models do not learn to detect the patterns and they rather overfit on the training distribution. However, this behavior could be intrinsic to the models' architecture. The models are designed to extract a vector representation from each input graph, which is then mapped to the prediction through an MLP. Then, the fact that different graph distributions might generate different graph representations leads us to investigate whether the problem is a poor generalization of the map between the graph embedding and the count. To test this possibility, we retrain on d\({}_{2}\) only the final MLP of the models previously trained on d\({}_{1}\) (row MLP in Table 2). While this adjustment is helpful, the errors are consistently one order of magnitude higher than the ones obtained training directly on d\({}_{2}\). This indicates that the graph representations do not achieve their theoretic separation power and that the problem does _not_ only lie in the last MLP prediction layers.

## 7 Conclusion

We proposed a novel approach to assess the empirical expressivity achieved by subgraph-counting GNNs via adversarial robustness. We show that despite being theoretically capable of counting certain patterns, the models lack generalization as they struggle to correctly predict adversarially perturbed and OOD graphs. Therefore, the training algorithms are not able to find weights corresponding to a maximally expressive solution. Extending our study to other related GNNs such as KP-GNN (Feng et al., 2022) or to include adversarial training (Gosch et al., 2023; Geisler et al., 2022) to steer towards more robust and expressive solutions, are interesting directions for future work.

\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{Arch.} & Exp. & \multicolumn{3}{c}{Trangle} & \multicolumn{2}{c}{4-Cycle} & \multicolumn{2}{c}{Chord. C.} \\ \cline{3-8}  & Setting & \(\ell_{1}\) & \(\ell_{c}\) & \(\ell_{c}\) & \(\ell_{c}\) & \(\ell_{1}\) & \(\ell_{c}\) \\ \hline \hline \multirow{4}{*}{PPGN} & d\({}_{1}\) & 0.0058 & 7.8e-4 & 0.059 & 0.010 & 0.10 & 0.011 \\  & OOD & 2.98 & 0.041 & 5.40 & 1.17 & 20.0 & 0.25 \\  & d\({}_{2}\) & 0.0091 & 1.7e-4 & 0.040 & 0.0050 & 0.12 & 0.0017 \\  & MLP & 0.059 & 9.8e-4 & 0.29 & 0.043 & 1.083 & 0.014 \\ \hline \multirow{4}{*}{\(\mathrm{I}\)-GNN} & d\({}_{1}\) & 0.0027 & 2.8e-4 & 0.035 & 0.0062 & 0.020 & 0.0023 \\  & OOD & 3.25 & 0.044 & 2.16 & 0.45 & 6.75 & 0.084 \\ \cline{1-1}  & d\({}_{2}\) & 0.032 & 6.2e-4 & 0.028 & 0.0031 & 0.30 & 0.0042 \\ \cline{1-1}  & MLP & 0.20 & 0.0031 & 0.19 & 0.025 & 1.56 & 0.020 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Test errors of the OOD experiments that investigate the generalization abilities of the architectures. Specifically, d\({}_{1}\) represents models trained and tested on the same dataset d\({}_{i}\), OOD models trained on d\({}_{1}\) and tested in d\({}_{2}\) and in MLP we additionally retrain the final layers on d\({}_{2}\).

Figure 5: The plots illustrate in blue the success rate of our subgraph-counting adversarial attacks at finding perturbations that represent adversarial examples according to Definition 4.1 constrained and subgraph preserving perturbation spaces. In orange, we represent how effective the adversarial examples are when transferred to the models trained with a different initialization seed. The values are the average of the results obtained with 5 different initialization seeds with the relative standard errors.