Provably Powerful Graph Neural Networks for Directed Multigraphs
This paper analyses a set of simple adaptations that transform standard
message-passing Graph Neural Networks (GNN) into provably powerful directed
multigraph neural networks. The adaptations include multigraph port numbering,
ego IDs, and reverse message passing. We prove that the combination of these
theoretically enables the detection of any directed subgraph pattern. To
validate the effectiveness of our proposed adaptations in practice, we conduct
experiments on synthetic subgraph detection tasks, which demonstrate
outstanding performance with almost perfect results. Moreover, we apply our
proposed adaptations to two financial crime analysis tasks. We observe dramatic
improvements in detecting money laundering transactions, improving the
minority-class F1 score of a standard message-passing GNN by up to 30%, and
closely matching or outperforming tree-based and GNN baselines. Similarly
impressive results are observed on a real-world phishing detection dataset,
boosting three standard GNNs' F1 scores by around 15% and outperforming all
baselines.
Béni Egressy, Luc von Niederhäusern, Jovan Blanusa, Erik Altman, Roger Wattenhofer, Kubilay Atasu
# Provably Powerful Graph Neural Networks for Directed Multigraphs

###### Abstract

This paper proposes a set of simple adaptations to transform standard message-passing Graph Neural Networks (GNN) into provably powerful directed multigraph neural networks. The adaptations include multigraph port numbering, ego IDs, and reverse message passing. We prove that the combination of these theoretically enables the detection of any directed subgraph pattern. To validate the effectiveness of our proposed adaptations in practice, we conduct experiments on synthetic subgraph detection tasks, which demonstrate outstanding performance with almost perfect results.

Moreover, we apply our proposed adaptations to two financial crime analysis tasks. We observe dramatic improvements in detecting money laundering transactions, improving the minority-class F1 score of a standard message-passing GNN by up to \(45\%\), and clearly outperforming tree-based and GNN baselines. Similarly impressive results are observed on a real-world phishing detection dataset, boosting a standard GNN's F1 score by over \(15\%\) and outperforming all baselines.

## 1 Introduction

Graph neural networks (GNNs) have become the go-to machine learning models for learning from relational data. They have been applied in various fields, ranging from biology, physics, and chemistry to social networks, traffic, and weather forecasting [8; 70; 15; 52; 61; 30; 67; 4]. More recently, there has been growing interest in using GNNs to identify financial crime [10; 28; 60; 59; 42].

The underlying motivating task for this paper is to detect financial crimes that manifest as subgraph patterns in transaction networks. For example, see Figure 1 for examples of established money laundering patterns, or Figure 5 in the appendix for an illustrative scenario. The task seems to lend itself nicely to the use of GNNs. Unfortunately, current GNNs are not equipped to deal with financial transaction networks effectively.

Firstly, financial transaction networks are in fact directed multigraphs, i.e., edges (or transactions) are directed and there can be multiple edges between two nodes (or accounts). Secondly, most GNNs cannot detect certain subgraph patterns, such as cycles [13; 14]. In fact, many efforts have been made
to overcome this limitation [65; 26; 44; 66; 37; 49], all focusing on simple (undirected) graphs. But even on simple graphs, the problem is far from solved. Until very recently, for example, there was no linear-time permutation-equivariant GNN that could count 6-cycles with theoretical guarantees [26].

This paper addresses both of these issues. To the best of our knowledge, this is the first GNN architecture designed specifically for directed multigraphs. Secondly, we first prove that the proposed architecture can theoretically detect any subgraph pattern in directed multigraphs, and then empirically confirm that our proposed architecture can detect the patterns illustrated in Figure 1. Our proposed architecture is based on a set of simple adaptations that can transform any standard GNN architecture into a directed multigraph GNN. The adaptations are reverse message passing [27], port numbering [49], and ego IDs [65]. Although these individual building blocks are present in existing literature, the theoretical and empirical power of combining them has not been explored. In this work, we fill this gap: We combine them, adapt them to directed multigraphs, and showcase both the theoretical and empirical advantages of using them in unison.

**Our contributions.** 1) We propose a set of simple and intuitive adaptations that can transform message-passing GNNs into provably powerful directed multigraph neural networks. 2) We prove that suitably powerful GNNs equipped with ego IDs, port numbering, and reverse message passing can identify any directed subgraph pattern. 3) The theory is tested on synthetic graphs, confirming that GNNs using these adaptations can detect a variety of subgraph patterns, including directed cycles up to length six, scatter-gather patterns, and directed bicliques, setting them apart from previous GNN architectures. 4) The improvements translate to significant gains on financial datasets, with the adaptations boosting GNN performance dramatically on money laundering and phishing datasets, outperforming state-of-the-art financial crime detection models on both simulated and real data.

## 2 Related Work

Xu et al. [63] showed that standard MPNNs are at most as powerful as the Weisfeiler-Lehman (WL) isomorphism test, and provided a GNN architecture, GIN, that theoretically matches the power of the WL test. Although the WL test can asymptotically almost surely differentiate any two non-isomorphic graphs [2], standard MPNNs cannot -- in certain graphs -- detect simple substructures like cycles [13; 14]. This observation motivated researchers to go beyond standard MPNNs.

One direction considers emulating the more powerful k-WL isomorphism test, by conducting message passing between k-tuples or using a tensor-based model [39; 41]. Unfortunately, these models have high complexity and are impractical for most applications. Another line of work uses pre-calculated features to augment the GNN. These works explore adding subgraph counts [9; 3], positional node embeddings [17; 16], random IDs [1; 50], and node IDs [37].

A recent class of expressive GNNs called Subgraph GNNs, model graphs as collections of subgraphs [19; 69]. Papp et al. [43] drop random nodes from the input graph and run the GNN multiple times, gathering more information with each run. Zhang and Li [66] instead extract subgraphs around each node and run the GNN on these. Also falling into this category is ID-GNN using ego IDs [65], where each node is sampled with its neighborhood and given an identifier to differentiate it from neighboring nodes. Although the authors claim that ID-GNNs can count cycles, the proof turns out to

Figure 1: Money Laundering Patterns. The gray fill indicates the nodes to be detected by the synthetic pattern detection tasks. The exact degree/fan pattern sizes here are for illustrative purposes only.
be incorrect. In fact, Huang et al. [26] show that the whole family of Subgraph GNNs cannot count cycles of length greater than 4, and propose \(\mathrm{I}^{2}\)-GNNs that can provably count cycles up to length 6.

There has been much less work on GNNs for directed graphs. Zhang et al. [68] propose a spectral network for directed graphs, but it is difficult to analyze the power of this network or apply it to larger datasets. Similar approaches can be found in [55] and [38]. Jaume et al. [27] extend message passing to aggregate incoming and outgoing neighbors separately, rather than naively treating the graph as undirected. Directed multigraphs have not specifically been considered.

GNNs have been used for various financial applications [33; 18; 12; 67; 32; 62; 64]. Closest to our work, GNNs have been used for fraud detection. Liang et al. [34] and Rao et al. [45] work on bipartite customer-product graphs to uncover insurance and credit card fraud, respectively. Liu et al. [35] use heterogeneous GNNs to detect malicious accounts in the device-activity bipartite graph of an online payment platform. Weber et al. [60] were the first to apply standard GNNs for anti-money laundering (AML), and more recently Cardoso et al. [10] proposed representing the transaction network as a bipartite account-transaction graph and showed promising results in the semi-supervised AML setting. However, it is not clear how these approaches help with detecting typical fraud patterns.

## 3 Background

### Graphs and Financial Transaction Graphs

We will be working with directed multigraphs, \(G\), where the nodes \(v\in V(G)\) represent accounts, and the directed edges \(e=(u,v)\in E(G)\) represent transactions from \(u\) to \(v\). Each node \(u\) (optionally) has a set of associated account features \(h^{(0)}(u)\); this could include the account number, bank ID, and account balance. Each transaction \(e=(u,v)\) has a set of associated transaction features \(h^{(0)}_{(u,v)}\); this includes the amount, currency, and timestamp of the transaction. The incoming and outgoing neighbors of \(u\) are denoted by \(N_{in}(u)\) and \(N_{out}(u)\) respectively. Multiple transactions between the same two accounts are possible, making \(G\) a multigraph. In node (or edge) prediction tasks, each node (or edge) will have a binary label indicating whether the account (or transaction) is illicit.

Financial Crime Patterns.Figure 1 shows a selection of subgraph patterns indicative of money laundering [21; 23; 54; 59; 53]. Unfortunately, these are rather generic patterns and also appear extensively amongst perfectly innocent transactions. For example, a supermarket will have a very high fan-in, and a group of friends may produce a bipartite subgraph. As a result, detecting financial crime relies not just on detecting individual patterns, but also on learning relevant combinations. This makes neural networks promising candidates for the task. However, standard message-passing GNNs typically fail to detect the depicted patterns, with the exception of degree-in. In the next section, we describe architectural adaptations, which enable GNNs to detect each one of these patterns.

Subgraph Detection.Given a subgraph pattern \(H\), we define subgraph detection for nodes, as the task of deciding for each node in a graph whether it is contained in a subgraph that is isomorphic to \(H\); i.e., given a node \(v\in V(G)\), decide whether there exists a graph \(G^{\prime}\), with \(E(G^{\prime})\subseteq E(G)\) and \(V(G^{\prime})\subseteq V(G)\), such that \(v\in V(G^{\prime})\) and \(G^{\prime}\cong H\).

### Message Passing Neural Networks

Message-passing GNNs, commonly referred to as Message Passing Neural Networks (MPNNs), form the most prominent family of GNNs. They include GCN [31], GIN [63], GAT [56], GraphSAGE [22], and many more architectures. They work in three steps: 1) Each node sends a message with its current state \(h(v)\) to its neighbors, 2) Each node aggregates all the messages it receives from its neighbors in the embedding \(a(v)\), 3) Each node updates its state based on \(h(v)\) and \(a(v)\) to produce a new state. These 3 steps constitute a layer of the GNN, and they can be repeated to gather information from further and further reaches of the graph. More formally:

\[a^{(t)}(v) =\textsc{Aggregate}\left(\{h^{(t-1)}(u)\mid u\in N(v)\}\right),\] \[h^{(t)}(v) =\textsc{Update}\left(h^{(t-1)}(v),a^{(t)}(v)\right),\]

where \(\{\{.\}\}\) denotes a multiset, and Aggregate is a permutation-invariant function. We will shorten Aggregate to Agg and for readability, we will use \(\{.\}\) rather than \(\{\{.\}\}\) to indicate multisets.
In the case of directed graphs, we need to distinguish between the incoming and outgoing neighbors of node \(u\). In a standard MPNN, the messages are passed along the directed edges in the direction indicated. As such, the aggregation step only considers messages from incoming neighbors:

\[a^{(t)}(v)=\textsc{Agg}\left(\{h^{(t-1)}(u)\mid u\in N_{in}(v)\}\right),\]

where we now aggregate over the incoming neighbours, \(N_{in}(u)\).

The edges of an input graph may also have their own input features. We denote the input features of directed edge \(e=(u,v)\) by \(h^{(0)}((u,v))\). When using edge features during the message passing, the aggregation step becomes:

\[a^{(t)}(v)=\textsc{Agg}\left(\{(h^{(t-1)}(u),h^{(0)}((u,v)))\mid u\in N_{in}(v )\}\right).\]

In the remainder, we omit edge features from formulas when not needed, in favor of brevity.

## 4 Methods

In this section, we introduce simple adaptations that can be made to standard MPNNs (Message Passing Neural Networks) to enable the detection of the fraud patterns in Figure 1. We consider the adaptations in increasing order of complexity with regard to the patterns they help to detect. We provide theoretical proofs to motivate the adaptations and include results on the synthetic subgraph detection dataset in section 7.1 to support the theoretical results empirically.

### Reverse Message Passing

When using a standard MPNN with directed edges, a node does not receive any messages from outgoing neighbors (unless they happen to also be incoming neighbors), and so is unable to count its outgoing edges. For example, a standard MPNN is unable to distinguish nodes \(a\) and \(b\) in Figure 2. Further, note that naive bidirectional message passing, where edges are treated as undirected and messages travel in both directions, does not solve the problem, because a node can not then distinguish incoming and outgoing edges. So this would fail to distinguish nodes \(a\) and \(d\) in the same figure.

To overcome this issue, we need to indicate the direction of the edges in some way. We propose using a separate message-passing layer for the incoming and outgoing edges respectively, i.e., adding _reverse message passing_. Note that this is akin to using a relational GNN with two edge types [51]. More formally, the aggregation and update mechanisms become:

\[a_{in}^{(t)}(v) =\textsc{Agg}_{in}\left(\{h^{(t-1)}(u)\mid u\in N_{in}(v)\} \right),\] \[a_{out}^{(t)}(v) =\textsc{Agg}_{out}\left(\{h^{(t-1)}(u)\mid u\in N_{out}(v)\} \right),\] \[h^{(t)}(v) =\textsc{Update}\left(h^{(t-1)}(v),a_{in}^{(t)}(v),a_{out}^{(t)} (v)\right),\]

where \(a_{in}\) is now an aggregation of incoming neighbors and \(a_{out}\) of outgoing neighbors. We now prove that message-passing GNNs with reverse MP can solve degree-out.

**Proposition 4.1**.: _An MPNN with sum aggregation and reverse MP can solve degree-out._

Figure 3: Nodes (in gray) with different fan-ins that are not distinguishable by a standard MPNN. The edge labels indicate incoming and outgoing port numbers, respectively.

Figure 2: Nodes (\(a\) and \(b\)) with different out-degrees are not distinguishable by a standard MPNN with directed message passing. Note that naive bidirectional message passing on the other hand is unable to distinguish nodes \(a\) and \(d\).
The proof of Proposition 4.1 can be found in Appendix B. In Section 7.1, we use a synthetic pattern detection task to confirm that the theory translates into practice.

### Directed Multigraph Port Numbering

People often make multiple transactions to the same account. In transaction networks, these are represented as parallel edges. To detect fan-in (or fan-out) patterns, a model has to distinguish between edges from the same neighbor and edges from different neighbors. Using unique account numbers (or in general node ids) would naturally allow for this. However, using account numbers does not generalize well. During training, a model can memorize fraudulent account numbers without learning to identify fraudulent patterns. But such an approach will not generalize to unseen accounts.

Instead, we adapt port numbering [49] to directed multigraphs. Port numbering assigns IDs to each incident edge at a node. This allows a node to identify messages coming across the same edge in consecutive message-passing rounds. To adapt port numbering to directed multigraphs, we assign each directed edge an incoming and an outgoing port number, and edges coming from (or going to) the same node, receive the same incoming (or outgoing) port number. Port numbers have been shown to increase the expressivity of GNNs on simple graphs, but message-passing GNNs with port numbers alone cannot even detect 3-cycles in some cases [20].

In general, the assignment of port numbers around a node is arbitrary. A node with \(d\) incoming neighbors can assign incoming port numbers in \(d!\) ways. In order to break this symmetry in our datasets, we use the transaction timestamps to order the incoming (or outgoing) neighbors. In the case of parallel edges, we use the earliest timestamp to decide the order of the neighbors. Since timestamps carry meaning in financial crime detection, the choice of ordering is motivated; indeed two identical subgraph patterns with different timestamps can have different meanings.

Computing the port numbers in this way can be a time-intensive step, with runtime complexity dominated by sorting all the edges by their timestamps: \(\mathcal{O}(m\log m)\), where \(m=|E(G)|\). However, the port numbers can be calculated in advance for the train, validation, and test sets, so that the train and inference times remain unaffected. Each edge receives an incoming and an outgoing port number as additional edge features. Figure 3 shows an example of graphs with port numbers. We now prove that GNNs using port numbers can correctly identify fan-in and fan-out patterns.

Note that the following proof, and later proofs using port numbers, do not rely on the timestamps for correctness. However, if timestamps that uniquely identify the ports are available, then permutation invariance/equivariance of the GNN will be preserved.

**Proposition 4.2**.: _An MPNN with max aggregation and multigraph port numbering can solve fan-in._

A proof can be found in Appendix B. Adding reverse MP, one can use the same argument to show that fan-out can also be solved. Both propositions are confirmed empirically in Section 7.1.

**Proposition 4.3**.: _An MPNN with max aggregation, multigraph port numbering, and reverse MP can solve fan-out._

### Ego IDs

Although reverse MP and multigraph port numbering help with detecting some of the suspicious patterns in Figure 1, they are not sufficient to detect directed cycles, scatter-gather patterns, and directed bicliques. You et al. [65] introduced ego IDs specifically to help detect cycles in graphs. The idea is that by "marking" a "center" node with a distinct (binary) feature, this node can recognize when a sequence of messages cycles back around to it, thereby detecting cycles that it is part of. However, it turns out that the proof of Proposition 2 in the paper is incorrect, and ego IDs alone do not enable cycle detection. We give a counterexample in Figure 4, giving more details below. Indeed, Huang et al. [26] also note that the proof "confuses walks with paths".

As a counterexample, consider nodes \(u\) and \(u^{\prime}\) in Figure 4. They would receive the same label when using a standard MPNN with ego IDs (\(u\) and \(u^{\prime}\) being the center nodes), but \(u^{\prime}\) is part of several \(5\)-cycles and \(u\) is not. To see intuitively why, note first that the blue edges form two \(3\)-cycles on the one side and a \(6\)-cycle on the other, and that the 1-WL test can not distinguish these alone. Now, when \(u\) and \(u^{\prime}\) are the center nodes, the only extra information is that \(u\) and \(u^{\prime}\) are marked, but since they are fully connected in their graphs, the mark does not help in distinguishing any of the other nodes,
so the neighbors remain indistinguishable and indeed the two ego graphs remain indistinguishable. This means they could not both be labeled correctly in any task that relies on \(5\)-cycles. Note that the predictions for any of the other respective nodes (e.g., \(a\) and \(a^{\prime}\)) will not be identical, since when these are the center nodes with the ego ID, then the GNN can detect that the ones on the left are in \(3\)-cycles, whereas the ones on the right are not.

We see this reflected in the individual results in Table 1. Although ego IDs offer a boost in detecting short cycles, they do not help the baseline (GIN) in detecting longer cycles. This can also be explained theoretically: Assuming a graph has no loops (edges from a node to itself), walks of length two and three that return to the start node are also cycles since there is no possibility to repeat intermediate nodes. Therefore Proposition 2 from You et al. [65] applies in these cases and it is not surprising that GIN+EgoIDs can achieve impressive F1 scores for 2- and 3-cycle detection.

However, in combination with reverse MP and port numbering, ego IDs can detect cycles, scatter-gather patterns, and bipartite subgraphs, completing the list of suspicious patterns. In fact, it can be shown that a suitably powerful standard MPNN with these adaptations can distinguish any two non-isomorphic (sub-)graphs, and given a _consistent_ use of port-numbering they will not mistakenly distinguish any two isomorphic (sub-)graphs. GNNs fulfilling these two properties are often referred to as _universal_. The crux of the proof is showing how the ego ID, port numbers, and reverse MP can be used to assign unique IDs to each node in the graph. Given unique node IDs, sufficiently powerful standard MPNNs are known to be universal [37, 1].

**Theorem 4.4**.: _Ego IDs combined with port numbering and reverse MP can be used to assign unique node IDs in connected directed multigraphs._

The idea of the proof is to show how a GNN can replicate a labeling algorithm that assigns unique node IDs to each node in an ego node's neighborhood. The labeling algorithm as well as the full proof are provided in Appendix B. The universality of the adaptations now follows from this theorem.

**Corollary 4.4.1**.: _GIN with ego IDs, port numbering, and reverse MP can theoretically detect any directed subgraph patterns._

The proof follows from Theorem 4.4 and Corollary 3.1 from Loukas [37].

Similar statements can be made for simple undirected graphs. One can remove the reverse MP from the assumptions since this is only needed to make the proof work with directed edges. Therefore, equivalent statements for undirected graphs can also be made:

**Theorem 4.5**.: _Ego IDs combined with port numbering can be used to assign unique node IDs in connected undirected graphs._

**Corollary 4.5.1**.: _GIN with Ego IDs and port numbering can theoretically detect any subgraph pattern in undirected graphs._

The ablation study in Table 1 of Section 7.1 again supports the theoretical analysis. The combination of the three adaptations achieves impressive scores when detecting subgraph patterns.

## 5 Datasets

**Synthetic Pattern Detection Tasks.**  The AML subgraph patterns seen in Figure 1 are used to create a controllable testbed of synthetic pattern detection tasks. The key design principle is to ensure

Figure 4: Example nodes (\(u\) and \(u^{\prime}\)) with different \(5\)-cycle counts that are not distinguishable by a standard MPNN with ego IDs. For example, \((u^{\prime},a^{\prime},b^{\prime},c^{\prime},d^{\prime},u^{\prime})\) is a \(5\)-cycle on the right, but there are no \(5\)-cycles involving \(\mathtt{u}\) on the left. The example also works with undirected edges.
that the desired subgraph patterns appear randomly, rather than being inserted post hoc into a network. The problem with inserting patterns is that it skews the random distribution, and simple indicators (such as the degrees of nodes) can be enough to solve the task approximately. Consider the extreme case of generating a random \(3\)-regular graph and inserting a pattern. Additionally, if only inserted patterns are labeled, then randomly occurring patterns will be overlooked.

To ensure that the desired subgraph patterns appear randomly, we introduce the _random circulant graph_ generator. Details of the generator and pseudocode can be found in Appendix C.1. The pattern detection tasks include degree-in/out (number of incoming edges), fan-in/out (number of unique incoming neighbors), scatter-gather and directed biclique patterns, and directed cycles of length up to six. Detailed descriptions can be found in Appendix C.2.

Anti-Money Laundering (AML).Given the strict privacy regulations around banking data, real-world financial crime data is not publicly available. Instead, we use simulated money laundering data from IBM, recently released on Kaggle [48]. The simulator behind these datasets generates a financial transaction network by modeling agents (banks, companies, and individuals) in a virtual world. The generator uses well-established money laundering patterns to add realistic money laundering transactions.

We use two small and two medium-sized datasets, one of each size with a higher illicit ratio (HI) and a lower illicit ratio (LI). The dataset sizes and illicit ratios can be seen in Table 4 in the appendix. We use a 60-20-20 temporal train-validation-test split, i.e., we split the transaction indices after ordering them by their timestamps. Details can be found in Appendix D.

Ethereum Phishing Detection (ETH).Since banks do not release their data, we turn to cryptocurrencies for a real-world dataset. We use an Ethereum transaction network published on Kaggle [11], where some nodes are labeled as phishing accounts. We use a temporal train-validation-test split, but this time splitting the nodes. We use a 65-15-20 split because the illicit accounts are skewed towards the end of the dataset. More details and dataset statistics can be found in Appendix D.

## 6 Experimental Setup

Base GNNs and Baselines.GIN with edge features [25] is used as the main GNN base model with our adaptations added on top. GAT [56] and PNA [57] are also used as base models, and we refer to their adapted versions as Multi-GAT and Multi-PNA, respectively. All three are also considered baselines. Additionally, GIN with ego IDs can be considered an ID-GNN [65] baseline, and GIN with port numbering can be considered a CPNGNN [49] baseline. Since AML is posed as a transaction classification problem, we also include a baseline using edge updates (GIN+EU). The edge updates are based on Battaglia et al. [5]. This approach is similar to replacing edges with nodes and running a GNN on said _line graph_. This architecture recently achieved state-of-the-art results in self-supervised money laundering detection [10]. We do not focus on including a more expansive range of GNN architectures as baselines, for the simple reason that without (the proposed) adaptations, they are not equipped to deal with directed multigraphs. As far as we are aware, there are no other GNNs that one could expect to achieve state-of-the-art results on directed multigraphs.

In addition, we include a baseline representing the parallel line of work in financial crime detection that uses pre-calculated graph-based features (GFs) and tree-based classifiers to classify nodes or edges individually. We train a LightGBM [29] model on the individual edges (or nodes) using both the original raw features and additional GFs. This approach has produced state-of-the-art results in financial applications [60; 36]. Details of the model and the graph-mining algorithms can be found in Appendix E.2.

Given the size of the AML and ETH datasets, we use neighborhood sampling [22] for all GNN-based models in these experiments. Further details of the experimental setup for the different datasets can be found in Appendix E.

Scoring.Since we have very imbalanced datasets, accuracy and many other popular metrics are not good measures of model performance. Instead, we use the minority class F1 score. This aligns well with what banks and regulators use in real-world scenarios.
## 7 Results

### Synthetic Pattern Detection Results

The synthetic pattern detection results can be seen in Table 1. The degree-out results reveal that the standard message-passing GNNs are unable to solve the degree-out task, achieving F1 scores below \(44\%\). However, all the GNNs that are equipped with reverse MP score above \(98\%\), thus supporting Proposition 4.1. The next column shows that port numbering is the critical adaptation in solving fan-in, though the F1 score is quite high even for the baseline GIN. On the other hand, for the fan-out task, the combination of reverse MP and port numbering is needed to score above \(99\%\). Again, these results support Propositions 4.2 and 4.3. The ablation study of cumulative adaptations on top of GIN also supports Corollary 4.4.1: The combination of reverse MP, port numbering, and ego IDs, scores high on all of the subtasks, with only 6-cycle detection coming in below \(90\%\). We see similar results when using other base GNN models, with PNA+Adaptations achieving the best overall results. Moreover, on the more complex tasks -- directed cycle, scatter-gather, and biclique detection -- the combination of the three is what leads to the first significant improvement in F1 scores. In the most extreme case, scatter-gather detection, the minority class F1 score jumps from \(67.84\%\) with only reverse MP and port numbers to \(97.42\%\) with ego IDs added in. No adaptation alone is able to come close to this score, so it is clear that the combination is needed here. Similar jumps can be seen for directed 4-, 5-, and 6-cycle, and biclique detection. Increasing the dataset size and restricting the task to only the "complex" subtasks further increases the scores, with 6-cycle detection reaching above \(97\%\). More details can be found in Appendix F.1.

### AML Results

The results on the AML datasets can be seen in Table 2. For AML Small HI, we see that our adaptations boost the minority class F1 score of GIN from \(39.3\%\) to above \(84\%\), a gain of \(45\%\). The largest single improvement is brought by reverse MP, taking the F1 score from \(39.3\%\) up to \(74.8\%\). The final adaptation -- ego IDs -- does not seem to make a difference here. The results for the other AML datasets show a similar trend with overall gains of \(34\%\), \(41\%\), and \(18\%\) when using GIN, again with diminishing returns as more adaptations are added. The greatest individual gains come from reverse MP, but all three adaptations are needed to achieve the highest scores. The two rows corresponding to adding port numbers -- GIN+Ports and +Ports -- indicate clear gains from using port numbering both as an individual adaptation and on top of reverse MP. The support for ego IDs is less clear, with ego IDs improving GIN performance only on the larger datasets, and not impacting the scores significantly when added on top of reverse MP and port numbering. This behavior is in fact not so surprising given that the purpose of ego IDs is to mark/distinguish the center from its neighborhood. The same goal can also be achieved by suitably varied input features. When no input features are used, the effect of ego IDs is more pronounced. See Figure 9 in the appendix.

\begin{table}
\begin{tabular}{l c c c c c c c c c c c} \hline \hline Model & deg-in & deg-out & fan-in & fan-out & C2 & C3 & C4 & C5 & C6 & S-G & B-C \\ \hline GIN [63, 25] & 02.77\(\pm\) & 43.58 & 0.59\(\pm\)0.17 & 35.91 & 34.67 & 58.00 & 50.80 & 43.12 & 48.59 & 69.31 & 63.12 \\ GAT [56] & 10.33 & 10.53 & 9.69 & 0.00 & 0.00 & 0.00 & 25.86 & 0.00 & 0.00 & 0.00 & 0.00 \\ PNA [57] & 02.98\(\pm\) & 43.02 & 0.59\(\pm\)0.13 & 38.93 & 25.77 & 54.75 & 51.92 & 48.79 & 48.40 & 65.88 & 65.51 \\ GIN+EU [5, 10] & 02.50 & 42.74 & 58.01 & 39.13 & 32.58 & 55.91 & 54.65 & 47.62 & 49.68 & 68.54 & 64.64 \\ \hline GIN+EgoIDs [65] & 02.78\(\pm\) & 51.48 & 05.08 & 49.24 & 23.14 & 57.67 & 53.12 & 44.37 & 45.42 & 66.44 & 63.90 \\ GIN+Ports [49] & 02.67 & 45.00 & 02.80 & 41.51 & 27.79 & 56.11 & 42.68 & 41.11 & 44.99 & 67.99 & 65.76 \\ \hline GIN+Reverse MP [27] & 03.87\(\pm\) & 00.08 & 01.00 & 02.88 & 35.96 & 63.85 & 69.09 & 67.44 & 71.23 & 65.83 & 66.18 \\ +Ports & 03.51 & 03.83 & 03.81 & 03.10 & 39.15 & 03.58 & 69.00 & 70.35 & 75.04 & 67.84 & 65.78 \\ +EgoIDs (Multi-GIN) & 09.38\(\pm\) & 09.09 & 09.09 & 09.53 & 08.97 & 09.87 & 09.46 & 01.71 & 05.23 & 07.94 & 09.18 \\ \hline Multi-GAT & 08.05 & 08.26 & 09.28 & 09.38 & 08.03 & 08.93 & 08.50 & 08.52 & 31.31 & 08.05 & 08.02 \\ Multi-PNA & 09.64 & 09.28 & 09.38 & 09.41 & 59.41 & 09.44 & 09.49 & 09.46 & 03.75 & 09.07 & 08.70 \\ Multi-GIN+EU & 09.45 & 09.28 & 09.76 & 09.07 & 09.67 & 09.67 & 09.71 & 08.78 & 05.78 & 08.53 & 09.61 & 07.86 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Minority class F1 scores (\(\%\)) for the synthetic subgraph detection tasks. First from the top are the standard MPNN baselines; then the results with each adaptation added separately on top of GIN; followed by GIN with the adaptations added cumulatively; and finally, results for the other GNN baselines with the three adaptations (Multi-GNNs). The C\(k\) abbreviations stand for to directed \(k\)-cycle detection, S-G stands for scatter-gather and B-C stands for biclique detection. We report minority class F1 scores averaged over five runs. We omit standard deviations in favor of readability.
We further note that GIN with the adaptations clearly outperforms all of the baselines for three out of the four AML datasets. This is particularly impressive when compared with LightGBM+GFs since the graph-based features align perfectly with the illicit money laundering patterns used by the simulator. Moreover, this has been the state-of-the-art method in previous financial applications [60; 36]. For AML Medium LI, the PNA score is almost as high as GIN+Adaptations, but it can be seen further down the table that the adaptations also boost PNA performance significantly, leading to the highest score for the dataset. Finally, the adaptations were tested with several base models in addition to GIN, namely GAT, PNA, and GIN with edge updates. In each case, and across almost all AML datasets, we see clear gains from using the adaptations, although the gains on AML Medium LI are less pronounced. These gains underline the effectiveness and versatility of the approach.

To test the reliance of the models on the input features (edge features) versus on the graph topology, additional experiments were run with all the input features removed. Noteworthy is that the performance of GIN with the adaptations when using no features is close to the performance when all the features are provided. This means that the adapted model is able to use the graph topology effectively to identify illicit transactions. Please see Appendix F.2 for details. For training times and inference throughput rate of GIN with the different adaptations, please see Table 5 in the appendix. Notably, with the adaptations, the inference rate of GIN is above 18k transactions per second on a single GPU.

### ETH Results

Finally, we test our adaptations on a real-world financial crime dataset -- Ethereum phishing account classification, the results of which are given in Table 2. Similar to the AML datasets, we see a continuous improvement in final scores as we add more adaptations. In total, the minority class F1 score jumps from \(26.9\%\) without adaptations to \(42.9\%\) with reverse MP, port numbering, and ego IDs. Again, the largest single improvement is due to the reverse MP. In this case, GIN+Adaptations does not outperform all of the baselines (PNA and LightGBM+GFs score higher), but the adaptations also significantly boost PNA performance, thereby beating all the baselines by more than \(13\%\).

## 8 Conclusion

This work proposes a set of simple adaptations to transform a standard message-passing GNN into a provably powerful directed multigraph learner. We make three contributions to the area of graph neural networks. Firstly, the theoretical analysis fills a gap in the literature about the power of combining different GNN adaptations/augmentations. In particular, we prove that ego IDs combined with port numbering and reverse message passing enable a suitably powerful message-passing GNN (e.g., GIN) to calculate unique node IDs and therefore detect any directed subgraph patterns. Secondly, the theoretical results are confirmed in practice with a range of synthetic subgraph detection tasks. The empirical results align closely with the theory, showing that the combination of all three adaptations is needed to detect the more complex subgraphs. Lastly, we show how our adaptations can be applied to two important financial crime problems: detecting money laundering transactions and detecting

\begin{table}
\begin{tabular}{l|c c c c c} \hline \hline Model & AML Small HI & AML Small LI & AML Medium HI & AML Medium LI & ETH \\ \hline MLP & \(24.11\pm 1.47\) & \(14.59\pm 2.08\) & \(28.16\pm 6.97\) & \(7.95\pm 1.11\) & \(0.10\pm 0.00\) \\ LightGBM+GFs [29; 47] & \(16.91\pm 10.87\) & \(30.01\pm 0.31\) & \(610.98\pm 10.58\) & \(30.20\pm 0.58\) & \(83.20\pm 0.10\) \\ GIN [63; 25] & \(39.31\pm 4.86\) & \(33.09\pm 3.86\) & \(38.48\pm 2.54\) & \(22.04\pm 3.31\) & \(26.92\pm 7.52\) \\ GAT [56] & \(36.17\pm 7.74\) & \(25.67\pm 7.07\) & \(15.66\pm 20.22\) & \(4.90\pm 7.52\) & \(15.94\pm 3.89\) \\ PNA [57] & \(61.87\pm 42.05\) & \(38.29\pm 6.07\) & \(68.96\pm 40.78\) & \(38.02\pm 8.89\) & \(51.49\pm 42.69\) \\ GIN+EU [50; 10] & \(62.51\pm 2.01\) & \(39.27\pm 5.34\) & \(10.77\pm 10.20\) & \(29.28\pm 7.70\) & \(33.92\pm 7.34\) \\ \hline GIN+EgolDs [65] & \(36.82\pm 2.03\) & \(31.77\pm 3.38\) & \(48.90\pm 2.42\) & \(23.33\pm 3.40\) & \(26.01\pm 2.27\) \\ GIN+Ports [49] & \(49.43\pm 7.22\) & \(41.43\pm 15.66\) & \(69.00\pm 10.92\) & \(23.42\pm 3.14\) & \(32.96\pm 0.25\) \\ \hline GIN+ReversMP [27] & \(74.78\pm 14.00\) & \(37.98\pm 10.00\) & \(60.80\pm 10.00\) & \(35.67\pm 2.79\) & \(36.86\pm 8.12\) \\ +Ports & \(89.00\pm 2.08\) & \(62.50\pm 9.18\) & \(70.18\pm 10.00\) & \(39.20\pm 3.60\) & \(42.51\pm 7.16\) \\ +EgolDs (Multi-GIN) & \(84.00\pm 2.08\) & \(92.14\pm 9.50\) & \(90.78\pm 11.02\) & \(40.55\pm 2.08\) & \(42.86\pm 2.53\) \\ \hline Multi-GAT & \(46.79\pm 9.26\) & \(27.02\pm 2.38\) & \(30.27\pm 10.57\) & \(31.5\pm 1.04\) & \(46.36\pm 0.74\) \\ Multi-PNA & \(29.83\pm 11.08\) & \(58.66\pm 10.88\) & \(89.92\pm 1.54\) & \(44.07\pm 5.86\) & \(65.92\pm 5.30\) \\ Multi-GIN+EU & \(51.68\pm 5.68\) & \(59.00\pm 0.076\) & \(78.00\pm 1.50\) & \(29.64\pm 3.60\) & \(48.37\pm 6.62\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Minority class F1 scores (\(\%\)) for the AML and ETH tasks. HI indicates a higher illicit ratio and LI indicates a lower illicit ratio. The models are organized as in Table 1.
phishing accounts. GNNs with our adaptations achieve impressive results in both tasks, clearly outperforming relevant baselines. Reverse message passing and port numbering again prove crucial in reaching the highest scores, however, we find that with sufficiently varied input features, the use of ego IDs does not provide further advantages.

Although this work has focused on financial crime applications, our theoretical and practical results have wider relevance. Immediate future work could involve exploring applications of our methods to other directed multigraph problems, for example, in cybersecurity. Additional future work could explore the relationship between the computational complexity of different subgraph detection problems and the GNN learning and inference complexity.

## Acknowledgments and Disclosure of Funding

The support of the Swiss National Science Foundation (project number 172610) for this work is gratefully acknowledged.
