#  Provably Powerful Graph Neural Networks for Directed Multigraphs

Béni Egressy
ETH Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>
&Luc von Niederhäusern
ETH Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>
&Jovan Blanuša
IBM Research Europe
Zurich, Switzerland
<EMAIL_ADDRESS>
&Erik Altman
IBM Watson Research
Yorktown Heights, NY, USA
<EMAIL_ADDRESS>
&Roger Wattenhofer
ETH Zurich
Zurich, Switzerland
<EMAIL_ADDRESS>
&Kubilay Atasu
IBM Research Europe
Zurich, Switzerland
<EMAIL_ADDRESS>
This work was performed when Béni Egressy and Luc von Niederhäusern were with
IBM Research Europe, Zurich, Switzerland

###### 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 [9, 71, 16, 53, 62, 31, 68, 5]. More recently, there has
been growing interest in using GNNs to identify financial crime [11, 29, 61,
60, 43].

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 [14, 15]. In fact, many efforts have been
made to overcome this limitation [66, 27, 45, 67, 38, 50], 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 [27].

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 [28], port numbering [50],
and ego IDs [66]. 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.

(a) Degree-in = 4

(b) Degree-out = 4

(c) Directed Biclique

(d) Scatter-Gather

(e) Fan-in = 3

(f) Fan-out = 2

(g) Directed Cycle (5)

(h) Gather-Scatter

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.

##  2 Related Work

Xu et al. [64] 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 [3],
standard MPNNs cannot — in certain graphs — detect simple substructures like
cycles [14, 15]. 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 [40,
42]. 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 [10, 4],
positional node embeddings [18, 17], random IDs [2, 51], and node IDs [38].

A recent class of expressive GNNs called Subgraph GNNs, model graphs as
collections of subgraphs [20, 70]. Papp et al. [44] drop random nodes from the
input graph and run the GNN multiple times, gathering more information with
each run. Zhang and Li [67] instead extract subgraphs around each node and run
the GNN on these. Also falling into this category is ID-GNN using ego IDs
[66], 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 be incorrect. In fact, Huang
et al. [27] show that the whole family of Subgraph GNNs cannot count cycles of
length greater than 4, and propose I2-GNNs that can provably count cycles up
to length 6.

There has been much less work on GNNs for directed graphs. Zhang et al. [69]
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 [56] and [39]. Jaume et al. [28] 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 [34, 19, 13, 68, 33,
63, 65]. Closest to our work, GNNs have been used for fraud detection. Liang
et al. [35] and Rao et al. [46] work on bipartite customer-product graphs to
uncover insurance and credit card fraud, respectively. Liu et al. [36] use
heterogeneous GNNs to detect malicious accounts in the device-activity
bipartite graph of an online payment platform. Weber et al. [61] were the
first to apply standard GNNs for anti-money laundering (AML), and more
recently Cardoso et al. [11] 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

###  3.1 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 [22, 24, 55, 60, 54]. 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$.

###  3.2 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 [32], GIN
[64], GAT [57], GraphSAGE [23], 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:

$\displaystyle a^{(t)}(v)$
$\displaystyle=\textsc{Aggregate}\left(\\{h^{(t-1)}(u)\mid u\in
N(v)\\}\right),$ $\displaystyle h^{(t)}(v)$
$\displaystyle=\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:

$\displaystyle a^{(t)}(v)$
$\displaystyle=\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)}{\left((u,v)\right)}$. When using edge features during the message
passing, the aggregation step becomes:

$\displaystyle a^{(t)}(v)$
$\displaystyle=\textsc{Agg}\left(\\{(h^{(t-1)}(u),h^{(0)}{\left((u,v)\right)})\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.

###  4.1 Reverse Message Passing

$a$$b$$c$$d$ 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$.  (2,1)(2,1)(1,1)(1,1)(2,1)(3,1) 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.

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 [52]. More
formally, the aggregation and update mechanisms become:

$\displaystyle a_{in}^{(t)}(v)$
$\displaystyle=\textsc{Agg}_{in}\left(\\{h^{(t-1)}(u)\mid u\in
N_{in}(v)\\}\right),$ $\displaystyle a_{out}^{(t)}(v)$
$\displaystyle=\textsc{Agg}_{out}\left(\\{h^{(t-1)}(u)\mid u\in
N_{out}(v)\\}\right),$ $\displaystyle h^{(t)}(v)$
$\displaystyle=\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.

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.

###  4.2 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 [50] 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 [21].

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=\lvert E(G)\rvert$. 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.

###  4.3 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.
[66] 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. [27] 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. [66] 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 [38, 2].

$a$$b$$c$$d$$e$$f$$u$$a^{\prime}$$b^{\prime}$$c^{\prime}$$d^{\prime}$$e^{\prime}$$f^{\prime}$$u^{\prime}$
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 u on the left.
The example also works with undirected edges.

######  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 [38].

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 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 [49]. 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 [12], 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 [26] is used as the main GNN
base model with our adaptations added on top. GAT [57] and PNA [58] 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 [66] baseline, and
GIN with port numbering can be considered a CPNGNN [50] 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.
[6]. 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 [11]. 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 [30] 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 [61, 37]. 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 [23]
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

###  7.1 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.

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.

Model | deg-in | deg-out | fan-in | fan-out | C2 | C3 | C4 | C5 | C6 | S-G | B-C
---|---|---|---|---|---|---|---|---|---|---|---
GIN [64, 26] |  99.77 |  43.58 |  95.57 |  35.91 |  34.67 |  58.00 |  50.80 |  43.12 |  48.59 |  69.31 |  63.12
GAT [57] |  10.33 |  10.53 |  9.69 |  0.00 |  0.00 |  0.00 |  25.86 |  0.00 |  0.00 |  0.00 |  0.00
PNA [58] |  99.63 |  43.02 |  95.00 |  38.93 |  25.77 |  54.75 |  51.92 |  48.79 |  48.40 |  65.88 |  65.51
GIN+EU [6, 11] |  99.30 |  42.74 |  95.70 |  39.13 |  32.58 |  55.91 |  54.65 |  47.62 |  49.68 |  68.54 |  64.64
GIN+EgoIDs [66] |  99.78 |  51.48 |  95.06 |  49.24 |  98.13 |  97.97 |  53.12 |  44.37 |  45.42 |  66.44 |  63.90
GIN+Ports [50] |  99.47 |  45.00 |  99.59 |  41.51 |  27.79 |  56.11 |  42.68 |  41.11 |  44.99 |  67.99 |  65.76
GIN+ReverseMP [28] |  98.87 |  99.08 |  94.99 |  95.25 |  35.96 |  63.85 |  69.09 |  67.44 |  71.23 |  65.83 |  66.18
+Ports |  98.41 |  98.35 |  98.51 |  99.16 |  39.15 |  63.58 |  69.00 |  70.35 |  75.04 |  67.84 |  65.78
+EgoIDs (Multi-GIN) |  99.48 |  99.09 |  99.62 |  99.32 |  98.97 |  98.73 |  97.46 |  91.60 |  84.23 |  97.42 |  94.33
Multi-GAT |  98.68 |  98.36 |  99.28 |  99.33 |  98.61 |  98.93 |  98.90 |  95.82 |  91.81 |  96.66 |  86.92
Multi-PNA |  99.64 |  99.25 |  99.53 |  99.41 |  99.71 |  99.54 |  99.49 |  97.46 |  88.75 |  99.07 |  96.77
Multi-GIN+EU |  99.55 |  99.53 |  99.76 |  99.77 |  99.37 |  99.71 |  98.73 |  95.73 |  88.38 |  98.81 |  97.82

###  7.2 AML Results

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.

Model | AML Small HI | AML Small LI | AML Medium HI | AML Medium LI | ETH
---|---|---|---|---|---
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 [30, 48] |  $64.08\pm 0.47$ |  $30.01\pm 0.31$ |  $60.93\pm 0.48$ |  $30.20\pm 0.58$ |  $53.20\pm 0.60$
GIN [64, 26] |  $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 [57] |  $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 [58] |  $51.87\pm 4.25$ |  $38.29\pm 6.07$ |  $68.12\pm 2.63$ |  $38.02\pm 8.89$ |  $51.49\pm 4.26$
GIN+EU [6, 11] |  $59.21\pm 4.61$ |  $39.27\pm 5.34$ |  $54.90\pm 1.62$ |  $29.28\pm 7.70$ |  $33.92\pm 7.34$
GIN+EgoIDs [66] |  $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 [50] |  $49.43\pm 7.22$ |  $41.43\pm 1.56$ |  $57.03\pm 4.52$ |  $23.42\pm 3.14$ |  $32.96\pm 0.25$
GIN+ReverseMP [28] |  $74.78\pm 13.96$ |  $54.63\pm 6.09$ |  $67.80\pm 1.62$ |  $35.67\pm 2.79$ |  $36.86\pm 8.12$
+Ports |  $84.90\pm 2.08$ |  $67.39\pm 3.18$ |  $79.18\pm 1.50$ |  $39.20\pm 3.60$ |  $42.51\pm 7.16$
+EgoIDs (Multi-GIN) |  $84.26\pm 2.93$ |  $67.41\pm 2.86$ |  $79.75\pm 1.12$ |  $40.55\pm 2.08$ |  $42.86\pm 2.53$
Multi-GAT |  $46.79\pm 9.26$ |  $27.02\pm 2.38$ |  $30.27\pm 10.57$ |  $3.15\pm 4.04$ |  $46.36\pm 0.74$
Multi-PNA |  $72.98\pm 11.95$ |  $63.79\pm 6.83$ |  $82.92\pm 1.42$ |  $47.07\pm 5.86$ |  $65.28\pm 2.89$
Multi-GIN+EU |  $81.48\pm 5.43$ |  $59.06\pm 6.75$ |  $73.06\pm 1.50$ |  $29.64\pm 3.60$ |  $48.37\pm 6.62$

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.

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 [61, 37]. 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.

###  7.3 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 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.

## References

  * [1]
  * Abboud et al. [2020] Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. 2020.  The surprising power of graph neural networks with random node initialization.  arXiv preprint arXiv:2010.01179 (2020).
  * Babai et al. [1980] László Babai, Paul Erdos, and Stanley M Selkow. 1980\.  Random graph isomorphism.  SIaM Journal on computing 9, 3 (1980), 628–635.
  * Barceló et al. [2021] Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. 2021.  Graph neural networks with local graph parameters.  Advances in Neural Information Processing Systems 34 (2021), 25280–25293.
  * Battaglia et al. [2016] Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. 2016\.  Interaction networks for learning about objects, relations and physics.  Advances in neural information processing systems 29 (2016).
  * Battaglia et al. [2018] Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018\.  Relational inductive biases, deep learning, and graph networks.  arXiv preprint arXiv:1806.01261 (2018).
  * Blanusa et al. [2022] Jovan Blanusa, Paolo Ienne, and Kubilay Atasu. 2022\.  Scalable Fine-Grained Parallel Cycle Enumeration Algorithms. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. 247–258.
  * Blanuša et al. [2023] Jovan Blanuša, Kubilay Atasu, and Paolo Ienne. 2023\.  Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles.  http://arxiv.org/abs/2301.01068 arXiv:2301.01068 [cs].
  * Bongini et al. [2021] Pietro Bongini, Monica Bianchini, and Franco Scarselli. 2021\.  Molecular generative graph neural networks for drug discovery.  Neurocomputing 450 (2021), 242–252.
  * Bouritsas et al. [2022] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. 2022.  Improving graph neural network expressivity via subgraph isomorphism counting.  IEEE Transactions on Pattern Analysis and Machine Intelligence (2022).
  * Cardoso et al. [2022] Mário Cardoso, Pedro Saleiro, and Pedro Bizarro. 2022\.  LaundroGraph: Self-Supervised Graph Representation Learning for Anti-Money Laundering. In Proceedings of the Third ACM International Conference on AI in Finance. 130–138.
  * Chen et al. [2019a] Liang Chen, Jiaying Peng, Yang Liu, Jintang Li, Fenfang Xie, and Zibin Zheng. 2019a.  XBLOCK Blockchain Datasets: InPlusLab Ethereum Phishing Detection Datasets.  http://xblock.pro/ethereum/.
  * Chen et al. [2018] Yingmei Chen, Zhongyu Wei, and Xuanjing Huang. 2018\.  Incorporating corporation relationship via graph convolutional neural networks for stock price prediction. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 1655–1658.
  * Chen et al. [2020] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. 2020\.  Can graph neural networks count substructures?  Advances in neural information processing systems 33 (2020), 10383–10395.
  * Chen et al. [2019b] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. 2019b.  On the equivalence between graph isomorphism testing and function approximation with gnns.  Advances in neural information processing systems 32 (2019).
  * Derrow-Pinion et al. [2021] Austin Derrow-Pinion, Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Marc Nunkesser, Seongjae Lee, Xueying Guo, Brett Wiltshire, et al. 2021\.  Eta prediction with graph neural networks in google maps. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 3767–3776.
  * Dwivedi et al. [2021] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2021\.  Graph neural networks with learnable structural and positional representations.  arXiv preprint arXiv:2110.07875 (2021).
  * Egressy and Wattenhofer [2022] Beni Egressy and Roger Wattenhofer. 2022.  Graph Neural Networks with Precomputed Node Features.  arXiv preprint arXiv:2206.00637 (2022).
  * Feng et al. [2019] Fuli Feng, Xiangnan He, Xiang Wang, Cheng Luo, Yiqun Liu, and Tat-Seng Chua. 2019\.  Temporal relational ranking for stock prediction.  ACM Transactions on Information Systems (TOIS) 37, 2 (2019), 1–30.
  * Frasca et al. [2022] Fabrizio Frasca, Beatrice Bevilacqua, Michael M Bronstein, and Haggai Maron. 2022.  Understanding and extending subgraph gnns by rethinking their symmetries.  arXiv preprint arXiv:2206.11140 (2022).
  * Garg et al. [2020] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. 2020\.  Generalization and representational limits of graph neural networks. In International Conference on Machine Learning. PMLR, 3419–3430.
  * Granados and Vargas [2022] Oscar M Granados and Andrés Vargas. 2022.  The geometry of suspicious money laundering activities in financial networks.  EPJ Data Science 11, 1 (2022), 6.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017\.  Inductive representation learning on large graphs.  Advances in neural information processing systems 30 (2017).
  * He et al. [2021] Jing He, Jiao Tian, Yuanyuan Wu, Xinyi Cia, Kai Zhang, Mengjiao Guo, Hui Zheng, Junfeng Wu, and Yimu Ji. 2021.  An efficient solution to detect common topologies in money launderings based on coupling and connection.  IEEE Intelligent Systems 36, 1 (2021), 64–74.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. 1989\.  Multilayer feedforward networks are universal approximators.  Neural networks 2, 5 (1989), 359–366.
  * Hu et al. [2019] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. 2019.  Strategies for pre-training graph neural networks.  arXiv preprint arXiv:1905.12265 (2019).
  * Huang et al. [2022] Yinan Huang, Xingang Peng, Jianzhu Ma, and Muhan Zhang. 2022\.  Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs.  arXiv preprint arXiv:2210.13978 (2022).
  * Jaume et al. [2019] Guillaume Jaume, An-phi Nguyen, María Rodríguez Martínez, Jean-Philippe Thiran, and Maria Gabrani. 2019.  edGNN: a Simple and Powerful GNN for Directed Labeled Graphs.  arXiv preprint arXiv:1904.08745 (2019).
  * Kanezashi et al. [2022] Hiroki Kanezashi, Toyotaro Suzumura, Xin Liu, and Takahiro Hirofuchi. 2022.  Ethereum Fraud Detection with Heterogeneous Graph Neural Networks.  arXiv preprint arXiv:2203.12363 (2022).
  * Ke et al. [2017] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-Yan Liu. 2017\.  Lightgbm: A highly efficient gradient boosting decision tree.  Advances in neural information processing systems 30 (2017).
  * Keisler [2022] Ryan Keisler. 2022\.  Forecasting global weather with graph neural networks.  arXiv preprint arXiv:2202.07575 (2022).
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907 (2016).
  * Li et al. [2019] Chong Li, Kunyang Jia, Dan Shen, C-J Richard Shi, and Hongxia Yang. 2019.  Hierarchical Representation Learning for Bipartite Graphs.. In IJCAI, Vol. 19. 2873–2879.
  * Li et al. [2021] Wei Li, Ruihan Bao, Keiko Harimoto, Deli Chen, Jingjing Xu, and Qi Su. 2021\.  Modeling the stock relation with graph network for overnight stock movement prediction. In Proceedings of the twenty-ninth international conference on international joint conferences on artificial intelligence. 4541–4547.
  * Liang et al. [2019] Chen Liang, Ziqi Liu, Bin Liu, Jun Zhou, Xiaolong Li, Shuang Yang, and Yuan Qi. 2019.  Uncovering insurance fraud conspiracy with network learning. In Proceedings of the 42nd international ACM SIGIR conference on research and development in information retrieval. 1181–1184.
  * Liu et al. [2018] Ziqi Liu, Chaochao Chen, Xinxing Yang, Jun Zhou, Xiaolong Li, and Le Song. 2018\.  Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM international conference on information and knowledge management. 2077–2085.
  * Lo et al. [2022] Wai Weng Lo, Siamak Layeghy, and Marius Portmann. 2022\.  Inspection-L: Practical GNN-based money laundering detection system for bitcoin.  arXiv preprint arXiv:2203.10465 (2022).
  * Loukas [2019] Andreas Loukas. 2019\.  What graph neural networks cannot learn: depth vs width.  arXiv preprint arXiv:1907.03199 (2019).
  * Ma et al. [2019] Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. 2019\.  Spectral-based graph convolutional network for directed graphs.  arXiv preprint arXiv:1907.08990 (2019).
  * Maron et al. [2019] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. 2019.  Provably powerful graph networks.  Advances in neural information processing systems 32 (2019).
  * Medvedev [[n. d.]] Evgeny Medvedev. [n. d.].  ETH-etl.  https://github.com/blockchain-etl/ethereum-etl.  Accessed: 01-12-2022.
  * Morris et al. [2019] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019\.  Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33. 4602–4609.
  * Nicholls et al. [2021] Jack Nicholls, Aditya Kuppa, and Nhien-An Le-Khac. 2021\.  Financial cybercrime: A comprehensive survey of deep learning approaches to tackle the evolving financial crime landscape.  Ieee Access 9 (2021), 163965–163986.
  * Papp et al. [2021] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. 2021.  DropGNN: Random dropouts increase the expressiveness of graph neural networks.  Advances in Neural Information Processing Systems 34 (2021), 21997–22009.
  * Papp and Wattenhofer [2022] Pál András Papp and Roger Wattenhofer. 2022.  A theoretical comparison of graph neural network extensions. In International Conference on Machine Learning. PMLR, 17323–17345.
  * Rao et al. [2021] Susie Xi Rao, Shuai Zhang, Zhichao Han, Zitao Zhang, Wei Min, Zhiyao Chen, Yinan Shan, Yang Zhao, and Ce Zhang. 2021.  xFraud: explainable fraud transaction detection.  Proceedings of the VLDB Endowment 3 (2021), 427–436.
  * Research [2022a] IBM Research. 2022a.  Graph Feature Preprocessor PyPI Documentation.  https://snapml.readthedocs.io/en/latest/graph_preprocessor.html Accessed: 2023-01-10.
  * Research [2022b] IBM Research. 2022b.  Snap ML PyPI package.  https://pypi.org/project/snapml/ Accessed: 2023-01-10.
  * Research [2023] IBM Research. 2023\.  IBM Transactions for Anti Money Laundering (AML).  https://www.kaggle.com/datasets/ealtman2019/ibm-transactions-for-anti-money-laundering-aml Accessed: 2023-02-28.
  * Sato et al. [2019] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2019\.  Approximation ratios of graph neural networks for combinatorial problems.  Advances in Neural Information Processing Systems 32 (2019).
  * Sato et al. [2021] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2021\.  Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM). SIAM, 333–341.
  * Schlichtkrull et al. [2018] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018.  Modeling relational data with graph convolutional networks. In European semantic web conference. Springer, 593–607.
  * Shu et al. [2019] Kai Shu, Suhang Wang, and Huan Liu. 2019.  Beyond news contents: The role of social context for fake news detection. In Proceedings of the twelfth ACM international conference on web search and data mining. 312–320.
  * Starnini et al. [2021] Michele Starnini, Charalampos E Tsourakakis, Maryam Zamanipour, André Panisson, Walter Allasia, Marco Fornasiero, Laura Li Puma, Valeria Ricci, Silvia Ronchiadin, Angela Ugrinoska, et al. 2021\.  Smurf-Based Anti-money Laundering in Time-Evolving Transaction Networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 171–186.
  * Suzumura [[n. d.]] Toyotaro Suzumura. [n. d.].  AMLSIM library wiki.  https://github.com/IBM/AMLSim/wiki/Transaction-Model:-Alert-Model.  Accessed: 30-11-2022.
  * Tong et al. [2020] Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. 2020\.  Digraph inception convolutional networks.  Advances in neural information processing systems 33 (2020), 17907–17918.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  arXiv preprint arXiv:1710.10903 (2017).
  * Velickovic et al. [2019] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. 2019.  Deep Graph Infomax.  ICLR (Poster) 2, 3 (2019), 4.
  * Watts and Strogatz [1998] Duncan J Watts and Steven H Strogatz. 1998.  Collective dynamics of ‘small-world’networks.  nature 393, 6684 (1998), 440–442.
  * Weber et al. [2018] Mark Weber, Jie Chen, Toyotaro Suzumura, Aldo Pareja, Tengfei Ma, Hiroki Kanezashi, Tim Kaler, Charles E Leiserson, and Tao B Schardl. 2018.  Scalable graph learning for anti-money laundering: A first look.  arXiv preprint arXiv:1812.00076 (2018).
  * Weber et al. [2019] Mark Weber, Giacomo Domeniconi, Jie Chen, Daniel Karl I Weidele, Claudio Bellei, Tom Robinson, and Charles E Leiserson. 2019\.  Anti-money laundering in bitcoin: Experimenting with graph convolutional networks for financial forensics.  arXiv preprint arXiv:1908.02591 (2019).
  * Wu et al. [2020] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020\.  A comprehensive survey on graph neural networks.  IEEE transactions on neural networks and learning systems 32, 1 (2020), 4–24.
  * Xu et al. [2021] Bingbing Xu, Huawei Shen, Bingjie Sun, Rong An, Qi Cao, and Xueqi Cheng. 2021.  Towards consumer loan fraud detection: Graph neural networks with role-constrained conditional random field. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 4537–4545.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826 (2018).
  * Yang et al. [2021] Shuo Yang, Zhiqiang Zhang, Jun Zhou, Yang Wang, Wang Sun, Xingyu Zhong, Yanming Fang, Quan Yu, and Yuan Qi. 2021.  Financial risk analysis for SMEs with graph-based supply chain mining. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 4661–4667.
  * You et al. [2021] Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. 2021.  Identity-aware graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 35. 10737–10745.
  * Zhang and Li [2021] Muhan Zhang and Pan Li. 2021.  Nested graph neural networks.  Advances in Neural Information Processing Systems 34 (2021), 15734–15747.
  * Zhang et al. [2019] Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. 2019\.  Deep learning based recommender system: A survey and new perspectives.  ACM computing surveys (CSUR) 52, 1 (2019), 1–38.
  * Zhang et al. [2021] Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. 2021.  Magnet: A neural network for directed graphs.  Advances in neural information processing systems 34 (2021), 27003–27015.
  * Zhao et al. [2021] Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. 2021\.  From stars to subgraphs: Uplifting any GNN with local structure awareness.  arXiv preprint arXiv:2110.03753 (2021).
  * Zhou et al. [2020] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020.  Graph neural networks: A review of methods and applications.  AI open 1 (2020), 57–81.

##  Appendix A Motivating Financial Transaction Graph Example

$$$$$$$$$$$$$$$$$$AliceBobSeanTim Figure 5: Example of money laundering in a
network of financial transactions. Alice and Bob stay at a hotel, which is run
by a criminal group headed by Tim. Sean has some dirty money (red dollars)
from criminal activities that he wants to transfer to Tim. They use the hotel
for laundering the money. They mix the dirty cash with clean money from
guests, pay different contractors for supplies, and then transfer these
payments to Tim. The money transfer from Sean to the hotel is a cash payment
hidden from banks and financial authorities (dotted edge). However, the
scatter-gather pattern (bold, red edges) could be revealing of a money
laundering scheme.

##  Appendix B Proofs

###  B.1 Proof of Proposition 4.1

###### Proof.

Consider a message-passing GNN with sum aggregation. Then with a single GNN
layer, initial node features $h^{(0)}(v)=1$ for all $v\in V(G)$, we have
$a_{in}^{(t)}(v)=d_{in}(v)$ and $a_{out}^{(t)}(v)=d_{out}(v)$. Choosing
$\textsc{Update}\left(h,a_{in},a_{out}\right)=a_{out}$, we get
$h^{(1)}(v)=a_{out}^{(t)}(v)=d_{out}(v)$. ∎

###  B.2 Proof of Proposition 4.2

###### Proof.

Since consecutive integers are used to number the incoming ports, the max
aggregation function can directly output the maximum of the incoming port
numbers to give the desired result. ∎

The statement also holds for MPNNs with sum aggregation. However, the proof is
less intuitive and relies on the universality of sum aggregation for multisets
(Lemma 5 from Xu et al. [64]).

###  B.3 Proof of Theorem 4.4

For the purposes of this proof, we assume the Universal Approximation Theorem
[25] for multi-layer perceptrons (MLPs), stating that any continuous function
with finite support can be approximated by an MLP with at least one hidden
layer. We refer to this result to avoid giving explicit constructions for GNN
layers. We also assume that the GNN uses min aggregation, consisting of an MLP
applied elementwise to the set of incoming messages, followed by taking the
minimum.

###### Proof.

Initially, the ego node or root node starts with the node feature
$h^{(0)}(r)=1$, which will be its final node ID. The other nodes, $v\in
V(G)\setminus\\{r\\}$ start with $h^{(0)}(v)=0$, which indicates that they
have not yet been assigned a final ID. The node IDs will be assigned layer by
layer, such that a node that is $k$ hops away from $r$ receives a final ID
after $k$ rounds of message passing.

We call a node active if it has received a message from an active node in the
previous round. At $t=0$, only the root node is active. Once a node is active,
it switches to inactive for all the remaining rounds. A GNN can keep track of
active nodes, by using a dimension of the hidden node embeddings to indicate
whether the node is currently active and another dimension to indicate whether
the node has already been active. This information is then “included” in its
messages, so neighboring nodes know when to activate. Notice that only nodes
that are exactly distance $k$ (where edges can be traversed in either
direction) from the root node will be active in the $k^{th}$ round.

By ignoring messages from inactive nodes, a GNN can replicate Algorithm 1. In
each round, nodes receive messages from their neighbors, consisting of the
send a message consisting of their ID and the incoming (or outgoing) port
number to each of their incoming (or outgoing) neighbors respectively. The
message is an integer in base $2n$ made by concatenating the node ID and the
port number ($n$ is added to the port number if it is an incoming edge). The
message can be viewed as a node ID proposal, every active node proposes a node
ID to each of its neighbors. Then all nodes that receive proposals accept the
smallest of these proposals (again in base $2n$) as their node ID and become
active.

In a GNN, this can be replicated from the receiver’s perspective. In each
round, nodes receive messages from their neighbors, consisting of the
neighboring node’s current state and the port numbers along the edge. The MLP
at each node $v$, “ignores” messages from inactive nodes, e.g. by encoding
them as a very high value. For the remaining messages, $v$ encodes the
neighbor’s current state and port numbers as the concatenation of the
neighbor’s node ID (current state minus the two dimensions indicating
activity) and the port number $v$ has at its neighbor. In this way, the MLP
essentially constructs the proposals from the algorithm. Node $v$ then selects
the minimum proposal.

Since our input graph is connected, every node in the graph will be reached
(receive a proposal) within $D$ rounds, since $D$ is the diameter of the
graph. Therefore every node will end up with a node ID.

It remains to be shown that this node ID will be unique. First, note that
nodes at different distances from the root cannot end up with the same node
ID. A node at distance $k$ will receive its first proposal in round $k$ and
will therefore have an ID with exactly $k+1$ digits. Finally, an inductive
argument shows that active nodes (nodes at the same distance) cannot have the
same node IDs. Certainly, this is true at the start when $X=\\{r\\}$. Now
assuming all active nodes from the previous round ($k-1$) had distinct node
IDs, then the only way two active nodes (in round $k$) can have the same ID is
if they accept a proposal from the same neighboring node. This is because,
assuming the induction hypothesis, proposals from different nodes will already
differ in their first $k-1$ digits. But if two active nodes accepted a
proposal from the same node, then they would have received different port
numbers — incoming ports are distinct, outgoing ports are distinct, and $n$ is
added to all incoming ports so that they cannot be the same as any outgoing
ports. Therefore the active nodes always accept unique proposals. ∎

The algorithm used in the proof is given below. Figure 6 gives an example
output of the algorithm.

Data: Connected directed multigraph $G=(V,E)$ with $n$ nodes, with diameter
$D$ and with root (or ego) node $r\in V$. Active nodes $X\subseteq V$ and
finished nodes $F\subseteq V$. Port numbering $P:E\rightarrow\mathbb{N}^{2}$.

Result: A unique node ID $h(v)$ in base $2n$ for all $v\in V$

$h(r)\leftarrow 1$; $h(v)\leftarrow 0$ for all $v\in V\setminus\\{r\\}$;

$F\leftarrow\emptyset$; $X\leftarrow\\{r\\}$;

for $k\leftarrow 1$ to $D$ do

for $v\in V$ do

if $v\in X$ then

send $h(v)\mathbin{\|}P((v,u))_{out}$ to all $u\in N_{out}(v)$;

send $h(v)\mathbin{\|}n+P((u,v))_{in}$ to all $u\in N_{in}(v)$;

$F\leftarrow F\cup\\{v\\}$; $X\leftarrow X\setminus\\{v\\}$;

end if

if $v\notin F$ then

if Incoming (active) messages, $M(v)\neq\emptyset$ then

$h(v)\leftarrow\min\\{M(v)\\}$;

$X\leftarrow X\cup\\{v\\}$;

end if

end if

end for

end for

Algorithm 1 BFS node ID assignment (Theorem 4.4)
(1,1)(1,1)(1,2)(2,1)(1,2)(2,1)$h=1$$h=11,\text{\sout{$16$}}$$h=12$$h=17$$h=112,\text{\sout{$121$}}$
Figure 6: Example output of Algorithm 1 with the root (or ego) node indicated
in gray. The edge labels show the (incoming, and outgoing) directed multigraph
port numbers. The blue numbers indicate node ID proposals; declined proposals
are struck through, leaving the final assigned node IDs. In this example $n=5$
so node IDs are to be understood in base $10$.

##  Appendix C Synthetic Pattern Detection Datasets

To ensure that the desired subgraph patterns appear randomly, we introduce the
random circulant graph generator. The generator is parameterized by the number
of nodes $n$, the average degree $d$, and a radius $r$ controlling the local
density of the generated graph. Together, these parameters control the rate of
generating the various subgraph patterns. For example, by choosing a high
average degree and a low radius, we can ensure that more dense patterns also
appear randomly.

###  C.1 Random Circulant Graphs

A random circulant graph, $G_{n,d,r}$, has $n$ nodes $\\{1,2,\ldots,n\\}$, and
$\lfloor\frac{nd}{2}\rfloor$ edges; one end, $u$, of each edge is sampled
uniformly from $\\{1,2,\ldots,n\\}$, and the other end, $v$, is sampled from a
normal distribution around $u$ with standard deviation $r$, and then rounded
to the nearest integer, i.e., $v=\lfloor X+\frac{1}{2}\rfloor$, where
$X\sim\mathcal{N}(u,r)$. Algorithm 2 shows a step-by-step description of the
algorithm.

Data: Number of nodes $n$, average degree $d$, locality radius $r$.

Result: A graph $G=(V,E)$.

$N_{edges}\leftarrow\lfloor\frac{nd}{2}\rfloor$;

$\vec{u}\leftarrow(u_{i}\mid
i=1,\ldots,N_{edges})\overset{\text{iid}}{\sim}\text{unif}(\\{1,\ldots,n\\})$
;

/* Sample tail nodes */

$\vec{v}\leftarrow(v_{i}\mid
i=1,\ldots,N_{edges})\overset{\text{iid}}{\sim}\mathcal{N}(u_{i},r)$ ;

/* Sample head nodes */

$\vec{v}\leftarrow(\lfloor v_{i}+\frac{1}{2}\rfloor\mid i=1,\ldots,N_{edges})$
;

/* Round head nodes to nearest integer */

$V(G)=\\{1,\ldots,n\\}$;

$E(G)=\\{(u_{i},v_{i})\mid i=1,\ldots,N_{edges}\\}$;

Algorithm 2 Random Circulant Graph Generator

This model is similar to the Watts–Strogatz small-world model [59], where
nodes are also arranged in a ring, each node is connected to its k nearest
neighbors, and edges are randomly rewired with a chosen probability. However,
standard Watts–Strogatz implementations produce undirected graphs and do not
allow for multiple edges between a pair of vertices. In particular, a randomly
oriented Watts-Strogatz graph — a directed graph created by generating an
undirected Watts-Strogatz graph, and then choosing an arbitrary direction for
each edge independently and uniformly at random — doesn’t allow for testing
the detection of directed cycles of length 2 and fan patterns (without
parallel edges fan patterns are identical to degree patterns).

###  C.2 Pattern Detection Tasks

The synthetic pattern detection dataset includes the following (sub-)tasks:

  * •

Degree-in (-out): Degree -in and -out of a node is the number of incoming and
outgoing transactions respectively. Note that multiple transactions can come
from the same node, and these are counted separately.

  * •

Fan-in (-out): Fan -in and -out of a node is the number of unique incoming and
outgoing neighbors, respectively. Neighbors with multiple edges are counted
only once, but a node can contribute to both the fan-in and fan-out counts, as
it can be both an incoming and outgoing neighbor.

  * •

Cycle (k): A node receives a positive label if it is part of a directed cycle
of length $k$. We only consider directed cycle patterns and omit the word
“directed”.

  * •

Scatter-Gather: A node receives a positive label if it is the sink node of a
scatter-gather pattern with at least $2$ intermediate nodes. A scatter-gather
pattern consists of a source node, intermediate nodes, and a sink node. Given
a sink node $v$, a node $u$ is considered a source node if there is a directed
path of length $2$ from $u$ to $v$. A node $w_{i}$ is considered an
intermediate node if there is a directed path of length $2$ from $u$ to $v$
through $w_{i}$, i.e., if both $(u,w_{i})$ and $(w_{i},v)$ are in $E(G)$. Note
that a scatter-gather pattern with a single intermediate node is simply a
directed path of length $2$. This does not capture the pattern we are
interested in, so we require at least $2$ intermediate nodes.

  * •

Gather-Scatter: We do not explicitly include this pattern as a subtask since
it is a combination of fan-in and fan-out.

  * •

Biclique: A biclique (or complete bipartite graph) is a bipartite graph, where
every node of the first set is connected to every node of the second set. We
consider a special case of the directed biclique, where every node in the
first set has at least one outgoing edge to every node in the second set. We
call the nodes in the first set source nodes, and the nodes in the second set
sink nodes. The task is to identify all nodes that are the sink nodes of some
directed $K_{2,2}$ biclique with (at least) $2$ source nodes and (at least)
$2$ sink nodes.

All the (sub-)tasks are combined in one overall task, i.e., the output of the
models is a vector, where each element of the vector corresponds to one of the
subtasks.

We implement pattern detection algorithms to find the desired patterns and
generate binary node labels. The parameters are adjusted to achieve relatively
balanced labels, but since a perfect split (for all subtasks) is not
guaranteed, we rely on minority class F1 scores rather than accuracy to
measure the performance of our models. All subtasks in the final dataset have
at least $19\%$ and at most $68\%$ positive labels.

Thresholds are used in some cases to produce binary labels. For example, for
the degree-in task, nodes with an in-degree greater than 3 receive the label
$1$, while low in-degree nodes receive the label $0$. For degree-in/-out and
fan-in/-out the threshold is 3. For degree-in-time-span and maximum-degree-in
the thresholds are 1 and 4 respectively. Examples of the patterns are provided
in Figure 1.

We use $n=8192$ nodes, average degree $d=6$, and radius $r=11.1$ to generate
our pattern detection data. To avoid any information leakage between train,
validation, and test sets, we generate an independent random circulant graph
$G_{n,d,r}$ for each dataset. Table 3 shows the thresholds and distribution of
labels for each subtask.

Table 3: Synthetic pattern detection task statistics Subtask | Threshold | Positive Ratio
---|---|---
Degree-in | >3 | 0.352
Degree-out | >3 | 0.349
Fan-in | >3 | 0.324
Fan-out | >3 | 0.323
Cycle (2) | - | 0.191
Cycle (3) | - | 0.344
Cycle (4) | - | 0.527
Cycle (5) | - | 0.677
Cycle (6) | - | 0.779
Scatter-Gather | - | 0.321
Biclique | - | 0.318

##  Appendix D AML and ETH Datasets

Table 4: AML and ETH task statistics. HI indicates a higher illicit ratio and LI indicates a lower illicit ratio. Dataset | # nodes | # edges | Illicit Ratio
---|---|---|---
AML Small HI | 0.5M | 5M | 0.07%
AML Small LI | 0.7M | 7M | 0.05%
AML Medium HI | 2.1M | 32M | 0.11%
AML Medium LI | 2.0M | 31M | 0.05%
ETH | 2.9M | 13M | 0.04%

###  D.1 AML Data Split

We use a 60-20-20 temporal train-validation-test split, i.e., we split the
transaction indices after ordering them by their timestamps. The data split is
defined by two timestamps $t_{1}$ and $t_{2}$. Train indices correspond to
transactions before time $t_{1}$, validation indices to transactions between
times $t_{1}$ and $t_{2}$, and test indices to transactions after $t_{2}$.
However, the validation and test set transactions need access to the previous
transactions to identify patterns. So we construct train, validation, and test
graphs. This corresponds to considering the financial transaction graph as a
dynamic graph and taking three snapshots at times $t_{1}$, $t_{2}$, and
$t_{3}=t_{max}$. The train graph contains only the training transactions (and
corresponding nodes). The validation graph contains the training and
validation transactions, but only the validation indices are used for
evaluation. The test graph contains all the transactions, but only the test
indices are used for evaluation. This is the most likely scenario faced by
banks and financial authorities who want to classify new batches of
transactions.

###  D.2 ETH Dataset

The Kaggle dataset was constructed by starting from $1165$ reported phishing
nodes and crawling the whole Ethereum transaction network via breadth-first
search. The dataset originally comes with four edge features: transaction
time, transaction amount, source node address, and destination node address.
Each node has one feature, the account address. As this information is
minimal, we enhance the dataset with additional transaction features taken
directly from the blockchain using Ethereum ETL [41]. We add nonce, block
number, gas, and gas price. These are cryptocurrency terms for the number of
transactions made by the sender prior to the given transaction; the block
containing this transaction; and the transaction fees the sender provided for
the transaction to go through. Table 4 shows the number of nodes (accounts)
and edges (transactions) and the illicit ratio. Unlike AML, this is a node
classification task, where the goal is to classify nodes as phishing accounts.

Unlike the AML use case, we do not know a priori what subgraph patterns to
look for to identify phishing nodes. To this end, we defined fraudulent
clusters and visualized these to give an indication of the patterns our model
might need to detect. The clusters were constructed by starting from the
$1165$ reported phishing nodes, adding their 1-hop neighborhoods, and then
joining any clusters sharing a common node. Figure 7 shows an example of one
of these fraudulent clusters.

Figure 7: One of the fraudulent clusters identified in the ETH phishing
dataset. The patterns that might help identify a fraudulent node are mostly
1-hop, namely in-degree, out-degree, fan-in, fan-out patterns, and 2-cycles.

Similar to AML, we use a temporal train-validation-test split, but this time
we split the nodes. We order the nodes by the first transaction they are
involved in (either as sender or receiver) before splitting. Again this gives
us threshold times $t_{1}$ and $t_{2}$, and we use these times to create our
train, validation, and test graphs. See the AML dataset split for more
details. This time we use a 65-15-20 split because the illicit accounts are
skewed towards the end of the dataset, with few illicit accounts in the first
half of the data.

##  Appendix E Experimental Details

###  E.1 Hyperparameter Tuning and Scoring

We used random sampling to identify a good range of hyperparameters. A second
round of random sampling was conducted with this narrower range to pick our
final set of hyperparameters. We varied the following hyperparameters: the
number of GNN layers, hidden embedding size, learning rate, dropout, and
minority class weight (for the weighted loss function). The number of random
samples ranged between 10 to 50, depending on the training time of the model
on a particular dataset.

To get our final results, we use the hyperparameters with the best validation
score to train five models initialized with five different random seeds. The
results of the five runs are then averaged and the standard deviation is
calculated to give the reported scores.

###  E.2 LightGBM with Graph-based Features

We include a LightGBM baseline using pre-calculated graph features to classify
nodes or edges individually. Calculating complex subgraph features naively can
be prohibitively expensive, therefore we rely on Snap ML algorithms from IBM
[48, 47, 8, 7] to efficiently enumerate subgraph patterns.

We use these graph-mining algorithms to enumerate the suspicious patterns
introduced in Figure 1. We enumerate on a fine-grained level, counting
patterns of different sizes separately. For the edge classification tasks
(AML) we count patterns that an edge is contained in and add these counts as
additional edge features. We do the same with nodes for the node
classification task (ETH).

We train a LightGBM [30] model on the individual edges (or nodes) with the
full set of features (original raw features and additional graph-based
features). The pattern enumeration can be restricted to a certain time range;
we optimize the range (as a hyperparameter) for each dataset to get the best
performance.

###  E.3 Synthetic Pattern Detection Experiments

Unlike the much larger AML and ETH datasets, we do not have to subsample the
neighborhood. Instead, we use the whole 3-hop neighborhood in our model to
ensure that all of the patterns can be found. Moreover, we used six GNN layers
to ensure that 6-cycles can also be detected.

###  E.4 AML Experiments

Since this is an edge classification dataset, all GNNs use a final edge
readout layer that takes the edge embedding and the corresponding endpoint
node embeddings as its input. We use neighborhood sampling, sampling $100$
one- and two-hop neighbors respectively. We remove node IDs from edge and node
features to avoid, as far as possible, overfitting to the fraudulent node IDs.
Since we know what financial crime patterns were used for generating this
dataset, we use the graph mining library to enumerate exactly these suspicious
patterns for each transaction: degree-in/-out, fan-in/-out, directed cycle,
undirected cycle, and scatter-gather patterns of different sizes. We leave out
bicliques, as these are not currently included in the library. For the low IR
datasets, we took the hyperparameters from the high IR datasets and only
optimized the minority class weight. We found that this has to be optimized to
account for the greater class imbalance.

###  E.5 AML Runtimes

The table below shows the runtime cost of adding the adaptations to GIN when
running on the AML Small HI dataset. The size of the GNN models was kept the
same: 2 GNN layers and a hidden size of 64. All models were run on an Nvidia
GeForce RTX 3090 GPU.

Table 5: Total training times (TTT) and Transaction per Second (TPS) for all GIN-based models on the AML Small HI dataset. The TPS values were measured in evaluation mode. Model | TTT (s) | TPS (inference)
---|---|---
GIN | 1876 | 53130
Individual Adaptations
GIN+Ports | 2007 | 58663
GIN+EgoIDs | 1873 | 58533
GIN+ReverseMP | 12510 | 21067
Cumulative Adaptations
GIN+ReverseMP+Ports | 13051 | 18763
+EgoIDs | 12958 | 18700

###  E.6 ETH Experiments

Since this is a node classification dataset, all GNNs use a final node readout
layer that takes only the corresponding node embedding as its input. We use
neighborhood sampling, sampling $1000$ one- and two-hop neighbors
respectively.

For the LightGBM baseline, we use the graph mining library to enumerate the
same graph-based patterns as for AML, but this time for nodes. Additionally,
we calculate basic node statistics (such as averages, maximums, and variances)
of the transaction amounts and the time between transactions to improve the
baseline further. The statistical features give a significant boost to the
minority class F1 scores, from $27.1\%$ with only raw and graph-based features
to above $50\%$ with the additional statistical features.

##  Appendix F Additional Experiments

###  F.1 Complex Synthetic Tasks and Dataset Size

Additional experiments were carried out to measure the influence of dataset
size on the subgraph detection tasks. We restrict these experiments to the GIN
model with all the adaptations. We also restrict to the more “complex” tasks
that were not solved almost perfectly, namely C4, C5, C6, Scatter-Gather, and
Biclique detection. Dataset sizes of 1024 up to 16384 are used, increasing by
a factor of 2. All other graph generator settings are kept constant. In
particular, we use the same average degree and average radius.

The results can be seen in Figure 8, and specific values can be found in Table
6. One can see that increasing the training dataset size gradually increases
the scores on all the complex tasks, with even 6-cycle detection reaching
above $97\%$ minority class F1 score. The starred results also show that
restricting to a smaller set of tasks significantly improves performance.

Table 6: Minority class F1 scores for the “complex” subgraph detection tasks
with different dataset sizes. GIN+Adaptations is used in all experiments. The
∗ indicates that these results are copied from Table 1, where all subgraph
tasks were learned at once. All other experiments were restricted to the
subtasks shown.

No. Training Nodes | C4 | C5 | C6 | S-G | B-C
---|---|---|---|---|---
1024 |  65.22 $\pm$ 3.34 |  61.38 $\pm$ 7.25 |  59.97 $\pm$ 7.30 |  65.12 $\pm$ 2.83 |  60.11 $\pm$ 2.86
2048 |  78.06 $\pm$ 6.19 |  72.44 $\pm$ 4.48 |  70.19 $\pm$ 2.49 |  75.82 $\pm$ 4.77 |  67.82 $\pm$ 1.53
4096 |  95.85 $\pm$ 0.86 |  92.06 $\pm$ 1.81 |  76.57 $\pm$ 0.96 |  92.90 $\pm$ 1.29 |  89.64 $\pm$ 1.74
8192∗ |  97.46 $\pm$ 0.43 |  91.60 $\pm$ 1.50 |  84.23 $\pm$ 1.12 |  97.42 $\pm$ 0.85 |  94.33 $\pm$ 0.95
8192 |  99.46 $\pm$ 0.05 |  97.92 $\pm$ 0.26 |  93.72 $\pm$ 0.75 |  98.77 $\pm$ 0.18 |  97.75 $\pm$ 0.21
16384 |  99.72 $\pm$ 0.06 |  98.66 $\pm$ 0.15 |  97.24 $\pm$ 0.19 |  99.61 $\pm$ 0.08 |  99.53 $\pm$ 0.07

Figure 8: Performance of GIN+Adaptations on the “complex” subtasks as training
dataset size is increased.

###  F.2 AML Experiments Without Input Features

To test the reliance of the GNN models on the input features (edge features)
versus on the topology of the graph, additional experiments were run with
features removed. We ran three settings: Using all the edge (transaction)
features; removing the node IDs (“source account number” and “destination
account number”) from the edge features; removing the edge features
altogether. Note, that no node features are used in any of these experiments,
so the last setting only has the graph topology as input.

Plots of the results with cumulative adaptations (based on GIN) can be seen in
Figure 9. Noteworthy is that the performance of GIN with the adaptations when
using no features is not far off 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. It is also clear that in all
settings, the adaptations boost the base model’s performance drastically. The
contribution of each adaptation is clearest in the no features setting. In the
other settings, there is no indication that ego IDs make a positive
contribution.

(a) AML Small HI

(b) AML Small LI

Figure 9: Performance of GIN with cumulative adaptations on AML Small datasets
under three different input feature settings.