# GRANDE : a neural model over directed multigraphs with application to anti-
money laundering

Ruofan Wu, Boqun Ma, Qiong Mao, Wenlong Zhao, Weiqiang Wang and Tianyi Zhang
Ant Group, China ruofan.wrf, boqun.mbq, maoqiong.mq, chicheng.zwl,
weiqiang.wwq<EMAIL_ADDRESS>
###### Abstract.

The application of graph representation learning techniques to the area of
financial risk management (FRM) has attracted significant attention recently.
However, directly modeling transaction networks using graph neural models
remains challenging: Firstly, transaction networks are _directed multigraphs_
by nature, which could not be properly handled with most of the current off-
the-shelf graph neural networks (GNN). Secondly, a crucial problem in FRM
scenarios like anti-money laundering (AML) is to identify risky transactions
and is most naturally cast into an _edge classification_ problem with _rich_
edge-level features, which are not fully exploited by the prevailing GNN
design that follows node-centric message passing protocols. In this paper, we
present a systematic investigation of design aspects of neural models over
directed multigraphs and develop a novel GNN protocol that overcomes the above
challenges via efficiently incorporating directional information, as well as
proposing an enhancement that targets edge-related tasks using a novel message
passing scheme over an extension of edge-to-node dual graph. A concrete GNN
architecture called GRANDE is derived using the proposed protocol, with
several further improvements and generalizations to temporal dynamic graphs.
We apply the GRANDE model to both a real-world anti-money laundering task and
public datasets. Experimental evaluations and online deployment results show
the superiority of the proposed GRANDE architecture over recent state-of-the-
art models on dynamic graph modeling and directed graph modeling.

graph representation learning; financial risk management; edge representation;
edge-to-node duality

##  1\. Introduction

Recent years have witnessed an increasing trend of adopting modern machine
learning paradigms to financial risk management (FRM) scenarios
(akib2020ML4fin). As a typical use case in operational risk scenarios like
fraud detection and anti-money laundering, the identification of risky
entities (user accounts or transactions) is cast into a supervised
classification problem using behavioral data collected from the operating
financial platform (chen2018machine; kute2021aml). For institutions like
commercial banks and online payment platforms, the most important source of
behavior information is the _transaction records_ between users. making
_transaction networks_ (with users as nodes and transactions as edges) a
direct and appropriate data model. Unlike standard pattern recognition tasks
like image recognition where decisions are made according to information of
individual objects, identification of risky patterns over transaction network
requires reasoning beyond any individual scope. The phenomenon is particularly
evident in the area of anti-money laundering (AML), where suspicious
transactions are usually related by several users or accounts, with
transactions between them being highly correlated, thereby exhibiting a
cascading pattern which makes i.i.d. approaches in machine learning
unsuitable. The surging developments of machine learning models over graphs,
especially graph representation learning (hamilton2020graph), have attracted
significant attention in the financial industry and have shown promising
results in the area of FRM (liu2018heterogeneous; liu2021intention). The
dominant practice in graph representation learning is to utilize the panoply
of graph neural networks (GNN) (battaglia2018relational) that produce node-
level representations via principled aggregation mechanisms which are
generally described via message passing protocols (pmlr-v70-gilmer17a) or
spectral mechanisms (kipf2016semi).

Despite their convincing performance, the majority of the existent GNN models
operate over _undirected graphs_ , which makes them inadequate for the direct
modeling of transaction networks. Firstly, many graphs that arise in FRM
applications are directed by nature: i.e., in the case of a transaction
network with users as nodes and transactions as edges, the direction of an
edge is typically understood as the direction of its corresponding cash flow.
In areas like anti-money laundering (AML), directional information is
generally perceived to be of significant importance and shall not be neglected
(Sudjianto2010Statistical). Secondly, there might exist multiple transactions
between certain pairs of users. Thirdly, transactions are naturally associated
with timestamps that indicate the time of occurrence. Therefore, to fully
utilize the graphical structure of transaction networks, we need
representation learning frameworks that support _temporal directed
multigraphs_. While recent progress on _dynamic graph neural networks_
(xu2020inductive; kazemi2020representation) provide appropriate methods to
handle temporality, discussions over neural architectures that supports
directed multigraphs remains nascent (pmlr-v70-gilmer17a; ma2019spectral;
tong2020directed; NEURIPS2020_cffb6e22; zhang2021magnet).

From a practical point of view, the targeted risky entities may be either node
(i.e., malicious users) or edges (i.e., suspicious transactions). Conventional
GNN architectures produce node-level representations via encoding information
of each node’s rooted subtrees (xu2018how), making them a good fit for _user
or account level_ risk identifications. When the underlying task is to detect
risky transactions, the prevailing practice is to present edges using a
combination of node representations corresponding to both ends of edges. While
such design may be adequate for tasks like link prediction, it lacks a way to
effectively integrate edge-level information into the edge representation.
Since financial networks usually contain rich edge-level features (i.e.,
detailed transaction-related information), refinements on edge-level
representations are needed. For example, to accurately represent a
transaction, we need to combine the information of its buyer (cash sender) and
seller (cash receiver), and the transaction-related information, with each of
them requiring aggregating relevant information from related users and
transactions.

$n_{0}$$n_{1}$$n_{2}$$n_{3}$$n_{4}$$n_{5}$$n_{6}$$n_{7}$$n_{8}$$n_{9}$$n_{10}$$e_{0}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$

Figure 1. Illustration on the deficiency of the directed message passing
protocol in (battaglia2018relational): suppose the node of interest is
$n_{0}$, using GNNs designed according to the protocol in
(battaglia2018relational), it becomes impossible for $n_{0}$ to aggregate
information of $n_{9}$ and $n_{10}$. Under the context of financial risk
management, suppose $n_{9}$ and $n_{10}$ corresponds to known fraudsters, and
edges correspond to transactions. Although the riskiness of $n_{5}$ might be
undetermined, the transaction pattern makes it highly suspicious and therefore
uplifts the riskiness of $n_{0}$. To build models that behave coherently with
the above reasoning process, GNN protocols that aggregates information from
_both directions_ are required

A recent line of work (jiang2020censnet; cai2020line; jo2021edge) focused
directly on _learned edge representations_ using the idea of _edge-to-node
duality_ and obtained satisfactory performance over downstream tasks like edge
classification. However, previous works on edge representation learning all
applies to undirected graphs, making the extension to transaction networks
highly non-trivial.

In this paper, we propose a general message passing neural network protocol
that simultaneously outputs node and edge representations over directed
multigraphs. Based on this protocol, we derive a GNN architecture called
GRANDE with an extension to temporal graphs that efficiently leverages the
underlying structural property of transaction networks. More specifically, we
summarize our contribution as follows:

  * •

We develop a novel bi-directional message passing protocol with duality
enhancement (BiMPNN-DE) that strengthens previous proposals over message
passing neural architectures over directed multigraphs. The improvement is
two-fold: Firstly, it effectively combines neighborhood information from both
incoming and outgoing edges of nodes. Secondly, it simultaneously outputs node
and edge representations via performing message passing over both the original
graph and its _augmented_ edge adjacency graph.

  * •

We derive a concrete GNN architecture following the proposed BiMPNN-DE
protocol called GRANDE, that devices the acclaimed transformer
(vaswani2017attention) mechanism for neighborhood aggregation. The proposed
GRANDE framework is made compatible with temporal directed multigraphs through
the integration of a generic time encoding module that further extends
previous works on dynamic graph modeling (xu2020inductive).

  * •

To show the practical effectiveness of GRANDE, we apply it to a suspicious
transaction identification task in anti-money laundering, with the underlying
transaction network data collected from one of the world’s leading online
payment platforms. Comparisons against various undirected and directed GNN
baselines show the superiority of the proposed model. We also provide
evaluations on two public datasets generated from transaction networks to
further verify the strength of GRANDE framework when underlying graph features
are relatively weak.

##  2\. Methodology

###  2.1. Problem formulation

Under the context of financial risk management, we consider the following
_event stream_ representation of recorded transaction data that are available
in most online transaction systems:

(1)
$\displaystyle\mathcal{E}=\\{(u_{1},v_{1},t_{1},\chi_{1}),(u_{2},v_{2},t_{2},\chi_{2}),\ldots\\}$

Each event $(u,v,t,\chi)$ is interpreted as a transaction from user $u$ to
user $v$ that occurred at time $t$, with related features $\chi$ that could
often be further decomposed as user-level features like user account
information, and event-level features like transaction amount and channels. In
this paper, we focus on the representative task of _transaction property
prediction_ that typically takes the form of binary classification that aims
at identifying illicit or fraudulent transactions. The task could be cast into
a graph learning problem of edge classification in a straightforward manner.
We consider the temporal graph modeling paradigm (kazemi2020representation)
that views the underlying temporal graph as being generated from the event
stream $\mathcal{E}$. Therefore, given a time period
$\mathcal{T}=[\tau_{{\text{{start}}}},\tau_{{\text{{end}}}}]$, we construct
the graph data as the snapshot
$G(\mathcal{T})=(V(\mathcal{T}),E(\mathcal{T}))$ of the underlying temporal
graph. Since there may exist multiple transactions between the same set of
users, we consider $G(\mathcal{T})$ to be a _directed multigraph_ with each
edge in the edge multiset $E(\mathcal{T})$ represents an event that happens
inside the time interval $\mathcal{T}$, and the node set $V(\mathcal{T})$
consists of related users corresponding to the included events. During the
training stage, we construct a snapshot $G(\mathcal{T}_{{\text{{train}}}})$,
and obtain a possibly incomplete set of edge labels that are understood as
edge properties annotated using expert knowledge. During testing stage, we
perform inference over snapshots $G(\mathcal{T}_{{\text{{test}}}})$ that are
based on later time intervals than $\mathcal{T}_{{\text{{train}}}}$. We assume
$\mathcal{T}_{{\text{{train}}}}\cap\mathcal{T}_{{\text{{test}}}}=\emptyset$,
hence the problem of interest could be viewed as _inductive edge
classification over temporal graphs_.

###  2.2. Message passing protocols and directed graphs

Let $G=(V,E)$ be a directed multigraph with node set $V$ and edge multiset
$E$. For any pairs of nodes $(u,v)$, denote $\mu(u,v)$ as the number of edges
going from $u$ to $v$. Then $G$ becomes a (simple) graph when $\max_{u\in
V,v\in V}\mu(u,v)\leq 1$. For each $v\in V$, denote $N^{+}(v)=\\{u,(v,u)\in
E\\}$ and $N^{-}(v)=\\{u,(u,v)\in E\\}$ as its in-neighborhood and out-
neighborhood respectively, and let $N(v)=N^{+}(v)\cup N^{-}(v)$ be its
neighborhood. For the sake of presentation clarity, we will overload the
notation $uv$ for both an edge in the undirected graph, or a directed edge
from $u$ to $v$ in a directed (multi)graph from time to time, with its exact
meaning being clear from the context. We are interested in the general case
where both node features $X=\\{x_{v}\\}_{v\in V}$ and edge features
$Z=\\{z_{uv}\\}_{(u,v)\in E}$ are available, where we assume both kinds of
features to be of dimension $d$. In this paper we focus on neural approaches
to such directed multigraphs. A good starting point is the neural message
passing scheme for undirected graphs (pmlr-v70-gilmer17a): let $h^{(l)}_{v}$
denote the hidden representation of node $v$ at the $l$-th layer of the
network, and $h^{(0)}_{v}=x_{v},\forall v\in V$. The message passing graph
neural network protocol (abbreviated as GNN hereafter) is described
recursively as:

(2)

Different combinations of COMBINE, AGG and MESSAGE mechanisms thus form the
_design space_ of undirected GNNs (you2020designspace). To the best of our
knowledge, there are three types of generalization strategies to directed
graphs:

Symmetrization:

The most ad-hoc solution is to ”make it undirected” via padding necessary
reverse edges so that $N(v)=N^{+}(v)=N^{-}(v)$, and apply standard graph
neural networks that operate on undirected graphs like GCN or GAT. Despite its
simplicity and clearness, the symmetrization approach discards directional
information in the digraph and may raise subtleties when dealing with
multigraphs.

DiGraph-theoretic motivations:

A more recent line of work (ma2019spectral; tong2020directed;
NEURIPS2020_cffb6e22; zhang2021magnet) drew insights from directed graph
theory, especially the spectral branch (chung2005laplacians). The proposed
models are mostly digraph analogs of GCN, without the consideration for edge
features, therefore severely limiting the design space of directed message
passing GNNs.

Directed Protocol:

In the seminal work (battaglia2018relational, Algorithm 1), the authors
proposed a GNN protocol that operates on directed multigraphs with edge
features via aggregating messages from only the in-neighborhood, i.e.,
replacing $N(v)$ in (2) with $N^{+}(v))$. 111The original version also
considered incorporation of a _global node_ that aggregates information from
the whole graph regardless of the connectivity structure. While such design
choice may have some gains in moderate size graphs (xiong2021memory), it does
not scale to large graphs. Therefore we will not consider such design choice
in this paper While being a natural extension, such kind of GNN protocol
losses information from the outgoing direction of each node. We present a
pictorial illustration in figure 1.

To address the aforementioned shortcomings, we propose a novel GNN protocol
that operates on directed digraphs termed _bi-directional message passing
neural network (BiMPNN)_. The protocol extends the standard undirected
protocol (2) via enabling each node to aggregate information from both its in-
neighborhood and out-neighborhood:

(3) $\displaystyle\begin{aligned}
h^{(l+1)}_{v}&={\text{{MERGE}}}\left(\phi^{(l+1)}_{v},\psi^{(l+1)}_{v}\right)\\\
\phi^{(l+1)}_{v}&={\text{{COMBINE}}}_{{\text{{in}}}}\left(h^{(l)}_{v},\right.\\\
&\quad\left.{\text{{AGG}}}_{{\text{{in}}}}\left({\text{{MESSAGE}}}_{{\text{{in}}}}(h^{(l)}_{v},h^{(l)}_{u},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}z_{vu}},u\in
N^{+}(v))\right)\right)\\\
\psi^{(l+1)}_{v}&={\text{{COMBINE}}}_{{\text{{out}}}}\left(h^{(l)}_{v},\right.\\\
&\quad\left.{\text{{AGG}}}_{{\text{{out}}}}\left({\text{{MESSAGE}}}_{{\text{{out}}}}(h^{(l)}_{v},h^{(l)}_{r},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}z_{ur}},r\in
N^{-}(v))\right)\right)\end{aligned}$

Despite being more complicated than the undirected protocol, the proposed
BiMPNN protocol remains conceptually clear: for each layer, we aggregate
separately from each node’s in-neighborhood and out-neighborhood using
distinct aggregation mechanisms, and merge the two obtained intermediate
representations into the next layer’s input. Consequently, a $k$-layer GNN
derived from the BiMPNN protocol utilizes both its _root_ -$k$ incoming
subtree and outgoing subtree, thereby providing a richer set of _relational
inductive bias_ than the one proposed in (battaglia2018relational).

###  2.3. Edge-level task and edge-to-node duality

The BiMPNN protocol (3) provides a principled way of obtaining node
representations in directed multigraphs which serves as the building block of
_node-level tasks_. Yet another important type of graph-related tasks (in a
_local_ sense (Scarselli2009)) is _edge-level_ tasks, which exhibits a
dichotomy between _edge-existence_ prediction, i.e., link prediction, and
_edge-property_ prediction, i.e., edge classification. For the later task
type, the very existence of an edge itself suggests basing the predictions on
a properly defined _edge representation_ , which should go beyond naively
concatenating node representations of its ends (jo2021edge). Although the
protocol (3) implicitly encodes edge features into node representations, it
ignores the cascading dynamics of edges (i.e., information implied by cash
flow in FRM applications). To build powerful edge representations that
efficiently adapt to the underlying graph structure. Mechanisms based on the
edge-to-node dual graphs, or _line graph_ s, have been proposed
(chen2017supervised; jiang2020censnet; cai2020line; jo2021edge) under the
undirected GNN protocol (2). To begin our discussion on possible extensions to
directed multigraphs, we first review the definition of line graphs as
follows:

###### Definition 0 (Line graph and Line digraph (godsil2001algebraic;
bang2008digraphs)).

For both undirected graph and directed (multi)graphs where we overload
notation without misunderstandings, $G=(V,E)$, the node set of its line graph
$L(G)=(L(V),L(E))$ is defined as its edge (multi)set $L(V)=E$.

Undirected graph:

the edge set of its line graph is defined as

(4) $\displaystyle L(E)=\left\\{(uv,rs):(u,v)\in E,(r,s)\in
E,\\{u,v\\}\cap\\{r,s\\}\neq\emptyset\right\\}$

Directed (multi)graph:

the edge set of its line graph is defined as

(5) $\displaystyle L(E)=\left\\{(uv,rs):(u,v)\in E,(r,s)\in E,v=r\right\\}$

For undirected graphs, their line graphs provides a natural way to update edge
representations under standard message passing protocols like (2). However,
trivially extending (3) using the definition of line digraphs may incur
significant information loss: We take the graph in figure 1 as an example, its
line graph has an _empty_ edge set, which makes the message passing framework
useless over the derived line graph. While the graph-theoretic definition
enjoys some nice properties (bang2008digraphs), the adjacency criterion might
be overly stringent for deriving useful GNN architectures. Intuitively, we may
expect different transactions triggered by the same account as correlated
rather than independent, which makes connectivity of edges like
$(n_{5},n_{9})$ and $(n_{5},n_{0})$ as desirable. Therefore, we propose the
following _augmentation strategy_ to obtain an _augmented edge adjacency
graph_ $\overline{L(G)}=(\overline{L(V)},\overline{L(E)},T(E))$: The node set
is still defined as $\overline{L(V)}=E$, and we augment the edge set using the
undirected adjacency criterion (4). To retain directional information, we
encode the adjacency pattern of two edges (with four possible patterns: _head-
to-head_ , _head-to-tail_ , _tail-to-head_ , _tail-to-tail_) into a
categorical vector, which we denote as
$T(E)=\\{{\text{{type}}}(uv,rs):(uv,rs)\in\overline{L(E)}\\}$. By
construction, for each edge in $\overline{L(E)}$, its reverse is also in
$\overline{L(E)}$ with possibly different edge types. We provide a pictorial
illustration in the left part of figure 2.

To derive an edge representation update rule, we follow the spirit of the
BiMPNN node update rule (3): let $N^{+}_{L}(uv),N^{-}_{L}(uv)$ be the out and
in neighborhoods in the ordinary line graph $L(G)$ of $G$, and
$\overline{N^{+}_{L}(uv)},\overline{N^{-}_{L}(uv)}$ to be those in
$\overline{L(G)}$, respectively. For each edge $(uv,rs)\in\overline{L(E)}$, we
use ${\text{{C}}}(uv,rs)\in V$ as the common incident node of the edges $uv$
and $rs$. The following updating rule enhances BiMPNN protocol with duality
information, which we term BiMPNN-DE:

(6)

Where we use $g^{(l)}_{uv}$ to denote the hidden representation of edge $uv$
at the $l$-th layer of GNNs derived from the BiMPNN-DE protocol. The protocol
devices an additional edge representation update component that mirrors the
BiMPNN protocol over the augmented edge adjacency graph $\overline{L(G)}$ (see
the last four equations in the display (6)). To obtain an edge representation
counterpart $\tilde{h}^{(l)}_{uv,rs}$ during the aggregation process over
$\overline{L(G)}$, we use an additional ${\text{{COMBINE}}}^{{\text{{type}}}}$
mechanism that combines features of the common incident node and the
information of adjacent types, with is encoded into a learnable edge type
embedding matrix $T\in\mathbb{R}^{4\times d}$. The BiMPNN-DE protocol (6)
offers a much larger design space than that of BiMPNN protocol. In its full
generality, we may specify up to $15$ different mechanisms corresponding to
different MERGE, COMBINE, AGG and MESSAGE operations. From a practical point
of view, we may design the aforementioned operations using parameterized
functions that share the same underlying structure.

###  2.4. The GRANDE architecture

In this section, we devise the previously developed BiMPNN-DE protocol (6) to
derive a concrete GNN architecture that simultaneously outputs node and edge
representations, along with an improvement strategy that targets edge-property
prediction tasks. We base our design upon the acclaimed Transformer
architecture (vaswani2017attention), which has seen abundant adaptations to
GNNs recently (xu2020inductive; dwivedi2020generalization;
ying2021transformers). We define the multiplicative attention mechanism that
incorporates edge information as follows:

(7)

We include commonly used operations in a transformer block, namely LayerNorm
(LN), skip connection and a learnable two layer MLP (FF) as nonlinearity
(vaswani2017attention), and wraps them into a transformer block:

(8) $\displaystyle\begin{aligned}
{\text{{TRANSFORMER}}}&(h_{v},\\{h_{u},g_{uv}\\}_{u\in
N(v)})={\text{{LN}}}(\tilde{h}_{v}+{\text{{FF}}}(\tilde{h}_{v}))\\\
\tilde{h}_{v}&={\text{{LN}}}(h_{v}+{\text{{ATTN}}}(h_{v},\\{h_{u},g_{uv}\\}_{u\in
N(v)}))\end{aligned}$

After defining the basic mechanisms, we write the node and edge update rules
as follows:

(9)

The updating equations (9) involve many learnable parameters, to which we
apply the following naming convention: We use upper case greek letters
$\Phi,\Psi,\Theta,\Gamma$ to denote projection matrices that takes value in
$\mathbb{R}^{2d\times d}$, and we use the subscript $N$ for _node-related
projection_ and $E$ for _edge-related projection_. The
${\text{{COMBINE}}}^{{\text{{type}}}}$ operation is set to be element-wise
addition.

Improvements over edge-property prediction tasks The architecture in (9) is
most helpful when the underlying task is to predict properties of some
existent edges, which serves as the underlying task for many financial
applications like fraud detection and AML. Toward this goal, an ad-hoc
solution is to base the prediction with respect to edge $(u,v)$ upon the
concatenation of $h_{u}$, $h_{v}$ and $g_{uv}$. According to recent practices
over pairwise learning on graphs (wang2019nan; wang2021pairwise),
incorporation of interactions between $N(u)$ and $N(v)$, or _cross node
interactions_ significantly improves prediction performance. However, the
cross-node attention module proposed in (wang2019nan) requires full attention
between $h_{N(u)}$ and $h_{N(v)}$, yielding a potentially large computation
overhead. Here we provide a more efficient alternative to model the cross-node
interactions called the _cross-query attention_ module. Given a node pair
$(u,v)$, compute

(10) $\displaystyle\begin{aligned}
\delta_{uv}={\text{{CONCAT}}}&\left({\text{{ATTN}}}_{{\text{{left}}}}^{{\text{{in}}}}(h_{u},\\{h_{r},g_{rv}\\}_{r\in
N^{+}(v)}),\right.\\\
&\left.{\text{{ATTN}}}_{{\text{{left}}}}^{{\text{{out}}}}(h_{u},\\{h_{s},g_{vs}\\}_{s\in
N^{-}(v)})\right)\\\
\delta_{vu}={\text{{CONCAT}}}&\left({\text{{ATTN}}}_{{\text{{right}}}}^{{\text{{in}}}}(h_{v},\\{h_{r},g_{ru}\\}_{r\in
N^{+}(u)}),\right.\\\
&\left.{\text{{ATTN}}}_{{\text{{right}}}}^{{\text{{out}}}}(h_{v},\\{h_{s},g_{us}\\}_{s\in
N^{-}(u)})\right)\end{aligned}$

The above procedure (10) performs four queries that attends $u$ and $v$ to its
opponent’s in and out neighbors, respectively. Providing the existence of an
edge $(u,v)$, the mechanism (10) could be understood as attending nodes to the
a specific subsets of their _second-order_ neighborhoods which have close
relationship to the edges of interest. Finally we summarize the previous
developments into a framework termed multiGraph tRANsformer with Duality
Enhancement (GRANDE) , that utilizes the following edge representation for
edge-property prediction tasks:

(11) $\displaystyle
g^{{\text{{GRANDE}}}}_{uv}={\text{{CONCAT}}}(g_{uv},h_{v},h_{u},\delta_{uv},\delta_{vu})$

###  2.5. Extension to temporal graphs

According to the formulation in section 2.1, extending the GRANDE framework to
$G(\mathcal{T})$ requires utilization of the edge-wise timestamp information
$\\{t_{uv},(u,v)\in E\\}$ to produce _time-aware node and edge
representations_. Inspired by recent developments of time-aware representation
learning approaches (xu2019self; xu2020inductive), we propose an _extended
generic time encoding_ mechanism that enhances the node and edge update rule
of BiMPNN-DE with temporal information. Finally, to better exploit the
structure of the temporal graph, we suggest a _pruning strategy_ that shrinks
the number of edges of $\overline{L(G_{\mathcal{T}}))}$ by a factor up to two.

Generic time encoding The functional time encoding (FTE) provides a principled
way that modifies the self-attention operation (7) with minimal architecture
change:

(12)

Where ${\text{{TE}}}(|\Delta t_{uv}|)$ is temporal embedding obtained via
certain FTE mechanisms. $\alpha_{uv}$s and $\beta_{uv}$s are calculated
analogously to the rules in (7). In this paper we will follow the Bochner-type
FTE (xu2019self; xu2020inductive):

(13)
$\displaystyle{\text{{TE}}}(s)=\sqrt{\frac{1}{d}}\left[\cos(\rho_{1}s),\sin(\rho_{1}s),\ldots,\cos(\rho_{d}s),\sin(\rho_{d}s)\right]$

with learnable parameters $(\rho_{1},\ldots,\rho_{d})$. According to the setup
in (xu2020inductive), timestamps are associated with nodes rather than edges,
hence the authors used the time difference $\Delta t_{uv}=t_{u}-t_{v}$. The
situation becomes more complicated when timestamps are associated with edges,
for which we propose the following modification:

(14) $\displaystyle\Delta t_{uv}=t_{uv}-\min_{u\in N(v)}t_{uv}$

We use FTE based on (14) and replace the ATTN component with TATTN component
of the node time difference calculation in the node update part of (9). For
the edge update part, the ordinary node time difference method applies
naturally since edge timestamps act as node timestamps in the dual
formulation.

Temporal information and pruning strategies the proposed line graph
augmentation strategy produces an undirected $\overline{L(G)}$. While this
undirected network might provide valuable information in general, in financial
risk management scenarios where edges represent _timestamped transactions_ ,
directed adjacencies between transactions are typically of interest: Consider
a transaction $e_{t_{0}}$ from Bob to Alice, it is reasonable to assume that
_downstream_ transactions of $e_{t_{0}}$ (i.e., transactions $e_{t}$ with
$t>t_{0}$) will be affected by $e_{t_{0}}$, but its upstream transactions
shall not be affected. Inspired from this intuition, we introduce a _causal
pruning strategy_ that applies when temporal information is available in the
underlying graph, i.e, for an edge $e$ that goes from $u$ to $v$, we have its
time of occurrence $t_{e}$. The causal pruning strategy deletes edges in
$\overline{L(G)}$ with the occurrence time of the head node being earlier than
that of the tail node. When the causal pruning strategy is applicable, we may
prune up to $50\%$ of the edges in $\overline{L(G)}$. An illustration is
provided in the right part of figure 2. Note that the proposed strategy is
closely related to the construction of causal temporal subgraphs in temporal
graph modeling literature (xu2020inductive; ddgcl).

$e_{0}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$

$e_{0}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$e_{5}$$e_{6}$$e_{7}$$e_{8}$$e_{9}$

Figure 2. An illustration of the proposed line graph augmentation strategy:
The left figure stands for the augmented edge adjacency graph
$\overline{L(G)}$ for the digraph depicted in figure 1. We use colored edges
to represent edge types:  head-to-head and  tail-to-tail, note that the
remaining two kinds of edge types do not appear in $\overline{L(G)}$. The
right figure shows the effect of the causal pruning strategy under the
additional temporal constraint that $t_{0}<t_{1}<\cdots<t_{9}$, with $t_{i}$
being the occurrence time of edge $t_{i}$ for $i\in\\{0,\ldots,9\\}$

###  2.6. Scalability and complexity

Most of the real-world financial networks like transaction networks are
_sparse_ , i.e., most people only make transactions to a few others given a
finite time window. Consequently, the computational complexity of any message
passing neural networks could be roughly regarded as $O(Ed^{2})$. Extending
ordinary MPNN architectures to BiMPNN protocol doubles the computation cost,
which could be easily resolved through parallelization in modern deep learning
frameworks like tensorflow (abadi2016tensorflow). The extra computational cost
brought by introducing the dual component (6) requires more care: even when
the original graph is sparse, its augmented edge adjacency graph might be
dense or even complete. Such cases do happen in realistic scenarios since
large hubs frequently exist in transaction networks, which corresponds to a
complete subgraph in the dual network. Therefore the worst-case computation
cost of $O(E^{2}d^{2})$ is sometimes inevitable in architectures derived from
the BiMPNN-DE protocol (6). Hence to meet the computational requirement of GNN
architectures like GRANDE , performing GNN training/inference over the whole
graph is unrealistic. Instead, we resort to a _local_ computation alternative
implemented by the AGL system (zhang2020agl) which grabs the $K$-hop rooted
subgraph of each target node and performed batched stochastic training and
efficient parallel inference given distributed infrastructures like MapReduce
(zhang2020agl). In practical scenarios, it is often reasonable to set an upper
bound $M_{{\text{{max}}}}$ on the edges of any $K$-hop rooted subgraph and
device proper sampling methods to meet the requirement. The resulting
computational complexity during training is reduced to
$O(BM^{2}_{{\text{{max}}}}d^{2})$, where $B$ denotes the batch size. Since we
may control $M_{{\text{{max}}}}$ so that the whole batch of subgraphs fits the
storage requirement of high-performance hardware like GPU, the computational
costs of running GRANDE becomes fully affordable for industry-scale
distributed training and inference.

##  3\. Related Works

###  3.1. Neural models over directed graphs

Directional extensions of message passing GNN protocol were mentioned in
pioneer works (pmlr-v70-gilmer17a; battaglia2018relational) without providing
empirical evaluations. Recent developments toward designing GNNs for digraphs
are mostly inspired by different types of graph Laplacians that are defined
over digraphs. For example, (NEURIPS2020_cffb6e22) used the definition in
(chung2005laplacians) and (zhang2021magnet) used the Hermitian magnetic
Laplacian to decouple the aggregation process of graph connectivity and edge
orientations.

###  3.2. GNNs for edge representation learning

The idea of utilizing node-to-edge duality was explored in early works like
LGNN (chen2017supervised), where the authors drew insights from community
detection literature, and use the non-backtracking walk operator
(krzakala2013spectral) to define the dual graph and perform GCN-like
aggregations simultaneously over both graphs. Later developments
(jiang2020censnet; cai2020line; jo2021edge) focused on variants of LGNN with
the alternative definition of the dual, such as the standard LINE graph
(godsil2001algebraic).

###  3.3. Transformer architectures over graphs

The renowned GAT architecture (velivckovic2017graph) could be regarded as
using the _additive_ attention mechanism to form the attention layer, as
opposed to the _multiplicative_ attention mechanism adopted by the Transformer
architecture (vaswani2017attention). Adaptations of the original Transformer
to graph context have been assessed recently, (dwivedi2020generalization)
replaced the additive attention in GAT with inner product attention and use
spectral embedding as a proxy for the positional embedding component in the
original transformer architecture. In (ying2021transformers), the authors
proposed to use _full-attention_ transformers and use graph-theoretical
attributes of nodes and edges to guide the attention procedure. While the
results were shown competitive over biological benchmarks, the computational
overhead is way too heavy for industrial-level graphical applications.

##  4\. Experiments

In this section, we report empirical evaluations of GRANDE over an industrial
application as well as assessments over public datasets. We focus on the edge
classification task over temporal directed multigraphs. Finally, we present a
detailed ablation study to decompose the contributions of different
constituents of GRANDE .

###  4.1. Datasets

We use one industrial dataset and two public datasets, with their summary
statistics listed in table 4 in appendix A.

AML dataset This dataset is generated from transaction records collected from
Alipay, one of the world’s leading online payment systems. The business goal
is to identify transactions that exhibit risky patterns as being highly
suspicious of money laundering. The underlying graph is constructed by
treating users as nodes and transactions as directed edges with arbitrary
multiplicity. We engineer both node and edge features under a two-stage
process: We first obtain raw node features via statistical summaries of
corresponding user’s behavior on the platform during specific time periods,
and raw edge features consist of transaction properties as well as related
features of two users involved in the transaction. 222Per organizational
regulations, the detailed feature engineering logic is not fully described. We
will consider (partially) releasing the AML dataset after passing relevant
security checks of the company, as well as the source code. The decision tree
feature transforms (he2014practical) is then applied to both features so that
after the transform, the input node and edge feature for all the assessed
models are sparse categorical features with dimension $6400$. For both
training and testing, we collect data under a $10$-day period with no overlap
between the training period and the testing period. A random subset
corresponding to 10% of the testing data is held out for validation.

Bitcoin datasets We use two who-trusts-whom networks of people who trade using
Bitcoin on two different platforms, Bitcoin OTC and Bitcoin Alpha
(kumar2016edge; kumar2018rev2). Both networks are directed without edge
multiplicities, each edge is associated with a timestamp and a trust score
ranging from $-10$ to $10$. We consider the task of binary edge classification
with edge labels generated as whether the trust score is negative. Using node
features represented as the concatenation of one-hot representation of in and
out-degree of nodes. For both datasets, we use the chronological split that
uses $70\%$ data for training, $10\%$ for validation, and $20\%$ for testing

###  4.2. Baselines

We compare the proposed GRANDE framework with the following types of
baselines:

Undirected approaches:

We consider two representative GNN architectures GCN (kipf2016semi) and GAT
(velivckovic2017graph) that operate on undirected graphs. Since temporal
information is available in all three datasets, we also include the TGAT
architecture (xu2020inductive). As all the aforementioned methods produce
node-level representations, we use the concatenation of node representations
as edge representation according to the adjacency structure. As frameworks
that directly output edge representation remain few, we include the EHGNN
architecture (jo2021edge) as a strong baseline. To make the undirected
architectures compatible with directed (multi)graphs, we add reverse edges
with duplicated edge features if there exist no edge multiplicities in the
digraph. Otherwise, we keep only one edge between each pair of nodes, with the
corresponding edge feature generated via aggregating the original edge
features (according to the ”multigraph to graph” hierarchy) using the DeepSet
method (zaheer2017deepsets), and add reverse edges thereafter.

DiGraph-oriented approaches:

We consider two digraph GNN architectures that utilizes different notions of
directed graph Laplacians, DGCN (ma2019spectral) and MagNet (zhang2021magnet).

The aforementioned baselines exclude some of the recently proposed state-of-
the-art GNN models like Graphormer (ying2021transformers) for undirected
graphs or directed approaches like DiGCN (NEURIPS2020_cffb6e22) due to
scalability issues, i.e., they require either full graph attention or solving
eigen programs over the full graph Laplacian, which are computationally
infeasible for industry-scale graphs.

###  4.3. Experimental setup

Across all the datasets and models, we use a two-layer architecture with
hidden dimension $d=128$ without further tuning. For models with generic time
encodings, we fix the dimension of time encoding to be $128$. For transformer
related architectures, we follow the practice in (vaswani2017attention) and
use a two-layer MLP with ReLU activation with hidden dimension $512$. As all
the relevant tasks are binary classifications, we adopt the binary cross
entropy loss as the training objective, with $\ell_{2}$ regularization under a
coefficient $0.0001$ uniformly across all experiments. The graph data are
constructed via the GraphFlat component of the AGL system (zhang2020agl) that
transforms the raw graph data into batches of subgraphs with appropriate
sampling. 333The AGL framework is particularly useful when dealing with
industry-scale graphs that are barely possible to process as a whole. However,
it may lose some information in the sampling stage of the preprocessing phase.
To fully mimic the industrial setup, we preprocess all three datasets using
AGL, therefore the results of Bitcoin datasets are not directly comparable to
previously published results.  We use Adam optimizer with a learning rate of
$0.0001$ across all tasks and models. For the bitcoin datasets, we train each
model for $10$ epochs using a batch size of $128$ and select the best-
performed one according to the roc-auc score on the validation data under
periodic evaluations every $100$ steps. For the AML dataset, we train the
model for $2$ epochs with a batch size of $256$ as the size of the dataset is
sufficiently large. We adopt similar model selection criterion as those of
Bitcoin datasets, with periodic evalutions every $500$ steps.

Metrics Since the primary focus of this paper is applications to the FRM
scenario, we choose three representative metrics, namely roc-auc score (AUC),
Kolmogorov-Smirnov statistic (KS) and F$1$ score (F$1$).

Table 1. Experimental results over two public Bitcoin datasets and the AML dataset, with best performances in bold | Bitcoin-OTC | Bitcoin-Alpha | AML
---|---|---|---
| AUC | KS | F$1$ | AUC | KS | F$1$ | AUC | KS | F$1$
GCN (kipf2016semi) | $0.742$ | $0.376$ | $0.432$ | $0.626$ | $0.198$ | $0.282$ | $0.958$ | $0.793$ | $0.704$
GAT (velivckovic2017graph) | $0.736$ | $0.381$ | $0.393$ | $0.626$ | $0.178$ | $0.269$ | $0.962$ | $0.802$ | $0.718$
TGAT (xu2020inductive) | $0.744$ | $0.401$ | $0.422$ | $0.656$ | $0.248$ | $0.294$ | $0.963$ | $0.804$ | $0.720$
EHGNN (jo2021edge) | $0.719$ | $0.356$ | $0.420$ | $0.626$ | $0.228$ | $0.297$ | $0.961$ | $0.804$ | $0.718$
DGCN (ma2019spectral) | $0.634$ | $0.243$ | $0.354$ | $0.633$ | $0.228$ | $0.282$ | $0.962$ | $0.806$ | $0.720$
MagNet (zhang2021magnet) | $0.753$ | $0.388$ | $0.434$ | $0.645$ | $0.217$ | $0.293$ | $0.954$ | $0.780$ | $0.688$
GRANDE (reduced) | $0.789$ | $0.459$ | $0.460$ | $0.669$ | $0.256$ | $0.294$ | $0.965$ | $0.810$ | $0.726$
GRANDE | $\mathbf{0.829}$ | $\mathbf{0.524}$ | $\mathbf{0.532}$ | $\mathbf{0.769}$ | $\mathbf{0.415}$ | $\mathbf{0.398}$ | $\mathbf{0.966}$ | $\mathbf{0.813}$ | $\mathbf{0.734}$
Table 2. Performance summary of ablation studies, with best performance in bold | Bitcoin-OTC | Bitcoin-Alpha | AML
---|---|---|---
| AUC | KS | F$1$ | AUC | KS | F$1$ | AUC | KS | F$1$
GRANDE | $0.829$ | $0.524$ | $\mathbf{0.532}$ | $\mathbf{0.769}$ | $\mathbf{0.415}$ | $\mathbf{0.398}$ | $\mathbf{0.966}$ | $\mathbf{0.813}$ | $\mathbf{0.734}$
\- reduced | $0.789$ | $0.459$ | $0.460$ | $0.669$ | $0.256$ | $0.294$ | $0.965$ | $0.810$ | $0.726$
\- w/o causal pruning | $0.801$ | $0.464$ | $0.485$ | $0.726$ | $0.325$ | $0.339$ | $0.966$ | $0.813$ | $0.732$
\- w/o time encoding | $\mathbf{0.834}$ | $0.525$ | $0.531$ | $0.691$ | $0.265$ | $0.324$ | $0.966$ | $0.813$ | $0.731$
\- w/o cross-query attention | $0.828$ | $\mathbf{0.528}$ | $0.504$ | $0.766$ | $0.395$ | $0.372$ | $0.966$ | $0.813$ | $0.730$
\- w line graph | $0.762$ | $0.405$ | $0.415$ | $0.655$ | $0.229$ | $0.285$ | $0.965$ | $0.812$ | $0.729$

###  4.4. Performance

We present evaluation results in table 1. Apart from the proposed GRANDE
architecture, we report a _reduced_ version of GRANDE via discarding all
operations on the augmented edge adjacency graph, as well as the cross-query
attention module (10). The resulting model could be considered as implementing
a time-aware variant of graph transformer under the BiMPNN protocol. We
summarize our experimental findings as follows:

  * •

For the Bitcoin datasets which could be considered as under the _weak feature_
regime, the GRANDE architecture obtains substantial performance improvement:
On the Bitcoin-OTC dataset, the relative improvement over the best baselines
are $10.1\%$, $30.7\%$ and $22.6\%$ with respect to AUC, KS, and F$1$. On the
Bitcoin-Alpha dataset, the relative improvement is more significant with
$19.2\%$, $67.3\%$, and $35.4\%$ respectively. We attribute the improvements
to both the directional information and the duality information that GRANDE
utilizes. The improvements of the directional information could be inferred
from the results of the reduced GRANDE variant, which exhibits solid
improvements over all the baselines. The incorporation of edge-to-node duality
and cross-query attention systematically encodes more structural information,
therefore yielding further improvements.

  * •

For the AML dataset which could be regarded as under the _strong feature_
regime, the performance improvement is significant with respect to KS and F$1$
metrics while being less significant with respect to AUC. Such improvements
are still valuable in FRM applications since a higher F$1$ score potentially
suggests better patterns of the precision-recall (PR) curve, which we plot in
figure 3. The PR curve shows the dominant performance of GRANDE against
baselines: under various precision levels, the recall of GRANDE surpasses the
best baseline (TGAT) by as many as $5.29\%$ in absolute value and $13.4\%$ in
relative.

$0$$0.2$$0.4$$0.6$$0.8$$0.7$$0.75$$0.8$$0.85$$0.9$$0.95$$1$RecallPrecisionGCNGATTGATDGCNMagNetEHGNNGRANDE

Figure 3. Precision-recall (PR) curve under the AML dataset. We show recall
values corresponding to high precision ranges (from $0.7$ to $1.0$ equally
spaced with $0.025$)

###  4.5. Ablation study

We evaluate the following variants of GRANDE over all three datasets to
investigate contributions of different constituents:

Reduced version:

this is the one reported in table 1

Without causal pruning:

in this model variant we retain the full edge adjacency graph without pruning.
Which is computationally heavier than the GRANDE architecture

Without time encoding:

in this model variant we discard the temporal component of GRANDE and use the
update rule (9)

Without cross-query attention:

in this model variant we discard the cross-query attention module (10), and
use ${\text{{CONCAT}}}(g_{uv},h_{v},h_{u})$ as the output embedding for edge
$(u,v)$.

With line graph:

in this model variant, we use the ordinary directed line graph instead of the
proposed augmented edge adjacency graph. i.e., we replace
$\overline{N_{L}^{+}(uv)}$ and $\overline{N_{L}^{-}(uv)}$ in (9) with
$N_{L}^{+}(uv)$ and $N_{L}^{-}(uv)$, respectively.

Results we report results in table 2 using the same training configuration and
evaluation metrics as in section 4.3. There are a couple of notable
observations: Firstly, the causal pruning procedure saves computation as well
as improves performance, providing a solid relational inductive bias in
temporal graph modeling. Secondly, the incorporation of time encoding and
cross-query attention are in general helpful. Finally, using the ordinary line
graph performs on par with the reduced model, showing the insufficiency of
additional information provided by line digraphs, thereby verifying the
necessity of using the augmented edge adjacency graph.

##  5\. Deployments

The proposed GRANDE model has already been deployed in Alipay’s AML risk
detection system. It provides risk assessment services to millions of entities
every day and contributes more than $50\%$ suspicious entity identification to
AML risk management and control in specific business scenarios. Based on over
11.3 million transaction records within a week provided by the Alipay payment
platform, we conduct an A/B test between GRANDE , TGAT, and the identification
system that has been previously deployed in production (with its working
mechanism a combination of rule-based heuristics and gradient boosting
models). Due to the existence of unknown risk transactions, we first adopt an
empirical white list to mock the output precision of these models and then
evaluate the performance by comparing the recall at the same mock precision.
As summarized in table 3, the results suggest that GRANDE offers better recall
given the same precision level, with an absolute margin of $2.39\%$, which is
consistent with our experimental findings. Finally, a combination of the
output of GRANDE and the previous system (via simple model averaging)
increases the overall coverage rate by an absolute margin of
$36.46\%(45.41\%\rightarrow 81.87\%)$.

Table 3. Deployment summaries Model | Mock Precision | Recall
---|---|---
Previous system | $0.925$ | $0.454$
TGAT | $0.959$ | $0.723$
GRANDE | $0.959$ | $0.747$

##  6\. Discussion

Interpretability The dominating performance of neural approaches comes at the
cost of lacking of _model interpretablity_ , which is crucial to application
scenarios like AML, where outputs of decision making systems tie strongly with
regulatory strictures (kute2021aml). The adoption of neural approaches enjoys
better performance than potentially interpretable methods like linear models
as well as losing interpretability. Model explanation methods targeting graph
neural models are especially challenging (liu2022interpretability) due to the
combinatorial nature of the interpretation problem. Off-the-shelf GNN
explaining tools (refer to (liu2022interpretability) and references therein)
are not yet applicable to neural models over directed graphs, which is a
promising and challenging direction for future explorations.

Multi-task adaptations The representation quality in both node and edge
embeddings gives the GRANDE architecture the possibility to exploit side-
information via multi-task learning paradigms (ruder2017overview). For example
it is quite common in FRM scenarios to obtain both a set of user riskiness
labels alongside transaction labels. We have taken a trivial adaptation of
GRANDE into multi-task setups using extra node labels via adding a node-level
classification loss to the training objective and has shown solid improvement
(we report results in appendix B). Applying more elegant multi-task learning
techniques (ruder2017overview) to further exploit the potential of GRANDE is
an interesting direction for future studies.

##  7\. Conclusion

In this paper we propose a graph representation learning framework for
directed multigraphs that prevail in FRM applications. The proposed framework
generalizes the acclaimed message passing graph neural network protocol to
incorporate directional information, as well as utilizing the edge-to-node
dual relationship to further enhance the relational inductive bias with regard
to edge property prediction tasks. A concrete architecture named GRANDE is
derived according to the proposed protocol with the transformer architecture
being its aggregation mechanism, as well as a cross-query attention module
targeting edge-type tasks. The GRANDE model is generalizable to temporal
dynamic graphs via proper generic time encodings along with a pruning
strategy. Experimental results over both public and industrial datasets verify
the efficacy of the design of GRANDE . The model has been deployed in Alipay’s
online risk management system to fight against financial crime in money
laundering.

##  Appendix A Dataset summary

We list the summary statistics of used datasets in table 4

Table 4. Summary statistics of the evaluation datasets | Bitcoin-otc | Bitcoin-alpha | AML
---|---|---|---
# Nodes | $5881$ | $3783$ | $10268164$
# Edges | $35592$ | $24186$ | $13335278$
# Positive edges | $3563$ | $1536$ | $1338425$
# Negative edges | $32029$ | $22650$ | $11996853$
# Node features | $12012$ | $15210$ | $6400$
# Edge features | $-$ | $-$ | $6400$

##  Appendix B Additional experiments

We conduct an additional experiment using the AML dataset augmenting with a
set of node labels: the labels are obtained via an expert-maintained malicious
user list that takes the form of a binary vector indicating whether the user
is malicious or not. The labels are mapped separately to both the buyer (the
party that sends money) and seller (the party that receives money) of the
transactions, so that for each transaction we may have up to three labels. We
follow exactly the same training configuration and hyperparameter settings in
section 4.3. Comparisons are made under the recall metric under different
precisions, which we report in table 5. The results imply that the
incorporation of side-information yields consistent improvements, especially
in recalls at high precision (with a relative improvement of over $10\%$ in
${\text{{r@p}}}95$), which is wildly considered to be a key factor in the
assessment of models in FRM scenarios.

Table 5. Performance comparison between GRANDE and GRANDE with side-information (node-level labels) over the AML dataset. metric ${\text{{r@p}}}p$ means recall value at precision $p$, with best performance in bold | ${\text{{r@p}}}95$ | ${\text{{r@p}}}90$ | ${\text{{r@p}}}85$ | ${\text{{r@p}}}80$
---|---|---|---|---
GRANDE | $0.160$ | $0.368$ | $0.517$ | $0.624$
GRANDE (multi-task) | $\mathbf{0.186}$ | $\mathbf{0.382}$ | $\mathbf{0.523}$ | $\mathbf{0.629}$