Banking fraud causes billion-dollar losses for banks worldwide. In fraud detection, graphs help understand complex transaction patterns and discovering new fraud schemes. This work explores graph patterns in a real-world transaction dataset by extracting and analyzing its network motifs. Since banking graphs are heterogeneous, we focus on heterogeneous network motifs. Additionally, we propose a novel network randomization process that generates valid banking graphs. From our exploratory analysis, we conclude that network motifs extract insightful and interpretable patterns.
Payment information theft renders online transactions susceptible to fraud. Once detected, fraud entails a reimbursement from the cardholder’s bank, leading to monetary costs to financial institutions and customer friction.
Fraud detection thus requires a deep understanding of the
underlying fraud patterns, and graphs ofer an intuitive way to
visualize these patterns. One can further leverage graph mining in
transaction data to understand fraud schemes in a wide range of
applications. Hajdu and Krész [
In this work, we build networks from a real-world banking
dataset of card purchases and apply a widely used graph mining
tool – heterogeneous network motifs [
To the best of our knowledge, this work is the first to find and explore heterogeneous network motifs in a real-world banking setting. Notably, we have two main contributions from this work: • We propose a randomization process (i.e., a null model) adequate to banking datasets, a vital component for the definition of network motifs used to provide the baseline frequencies of each subgraph (detailed in Section 2.2.1). • We extract network motifs from graphs built from card transaction data and review them thoroughly. We include an analysis of how the motif significance evolves as more random networks are used (detailed in Section 3).
The remainder of this paper is organized as follows. Section 2 presents our method and discusses the key components necessary for our analysis. We describe the data and present results in Section 3. Usage scenarios are proposed in Section 4. We put forward our main takeaways and ofer directions for future work in Section 5. 2
In this section we present our methodological choices. First, we discuss how we build networks from banking datasets (Section 2.1). Then, we introduce heterogeneous network motifs and describe how to compute and identify these motifs in banking datasets, with a special focus on the null model and the measure of motif significance. (Section 2.2) 2.1
Banking datasets usually consist of transactions between entities, such as people, merchants, and businesses. They can include diferent types of transactions such as card payments or bank transfers.
From a banking dataset, we can build two graph representations, namely (a) entity graphs and (b) transaction graphs, as illustrated in Figure 1. 2.1.1 Entity graph. In an entity graph, = ( , ), nodes represent entities, such as merchants or clients, and edges connect entities with at least one shared transaction. This way of representing banking datasets is helpful to highlight suspicious entity behavior.
Transaction Entity Graph
(a) C1
M1
Consider, for example, the entity graph in Figure 1 (a). There, we represent C1 and M1 as two connected nodes of diferent types, i.e., {1, 1} ∈ , (1, 1) ∈ , and (1) ≠ (1), where () is the type of node . Since we connect all entities in a transaction, they form a -node clique in the graph. When the same two entities are parties to multiple transactions (e.g., a person makes several purchases at a retail store), we aggregate the transaction information into a single edge (, ) ∈ .
Therefore, an entity graph is undirected and heterogeneous. The node label () corresponds to the entity’s type (i.e., client, card, merchant, or terminal). The edge label (, ) is binary, indicating whether there is at least one fraudulent transaction involving the two entities. 2.1.2 Transaction graph. In a transaction graph, = ( , ), nodes represent individual transactions, and edges connect transactions that share entities.
In the transaction graph from Figure 1 (b), transactions T1 and T2 are represented as two nodes connected by an edge indicating that the same client made both, i.e., { 1, 2} ∈ and ( 1, 2) ∈ . Since connecting all transactions with common entities would result in very dense graphs, we only connect transactions that occurred within a time window, e.g., transactions made by a client in less than 24 hours. Moreover, we use edge direction to encode the temporal sequence of transactions, with edges connecting older transactions to more recent ones, i.e., if (, ) ∈ , then is more recent than . If two transactions occur in the same timestamp, we add a bidirectional edge between the two nodes, i.e., {(, ), (, )} ∈ .
Thus, a transaction graph is directed and heterogeneous. The node label is binary (the transaction is fraudulent or legitimate), i.e., ( ) ∈ { , }. The edge label is one of 2 − 1 possible labels, all the combinations of sharing one or more of diferent entities, i..e, (, ) ∈ , | | = 2 − 1. In Figure 1, = 2, hence there are 3 possible labels for edges, = 3.
Transaction can be used to investigate patterns between
transactions. Additionally, machine learning classification models can
benefit from receiving topological information (including centrality
measures or node embeddings) extracted from transaction graphs
[
A network motif is a subgraph that appears more frequently than
expected. The concept of appearing more frequently than expected
commonly relies on building a large set of randomized networks
R that are similar to the original network [
Suppose the frequency of a given subgraph in the original network is, according to some significance measure (Section 2.2.2), much higher than the (average) frequency on similar randomized networks, i.e., (, ) >> _ (, R ). In that case, subgraph is a network motif. Similarly, if the subgraph’s frequency is much lower than the (average) frequency on similar randomized networks, that subgraph is an anti-motif. In this work, we are interested in both motifs and anti-motifs.
Motif discovery involves computing the frequency of a given set
of subgraphs and entails subgraph counting [
In this work, we use g-tries for subgraph counting since they are
a general framework able to count subgraphs of arbitrary size in
heterogenous graphs [
Since our graphs are heterogeneous, we need network motifs that consider node and edge heterogeneity. Concretely, we need to extract heterogeneous motifs and anti-motifs.
As an illustrative example, consider a 3-node clique where nodes and edges are homogeneous (Figure 2 (a)) and the following heterogeneous graph settings: (i) if nodes can be of two diferent types, there are four possible 3-node cliques (Figure 2 (b)), (ii) if edges can be of two diferent types, there are four possible 3-node cliques (Figure 2 (c)). Thus, in our work, disregarding node or edge labels undermines the necessary diferentiation of topological structures. Heterogeneous motif discovery is more informative than traditional homogeneous motif discovery and more complex to extract and analyze.
In banking fraud analysis, heterogeneous network motifs are
more helpful than homogeneous motifs. For instance, knowing that
"clients connected to many diferent cards are more likely to be
fraudulent" is arguably more informative than just knowing that
"dense subgraphs can be indicative of fraud".
2.2.1 Network randomization. Computing the expected frequency
of a given subgraph requires randomizing the original network
so that randomized networks are similar to the original. However,
defining network similarity is non-trivial and task-dependent. In
practice, the following two approaches are common:
• Initialize the randomized graph as a copy of the original
graph and iteratively swap random pairs of edges [
However, these strategies are unsuitable to the banking fraud domain as they fundamentally change the semantic structure of banking graphs. For instance, in an entity graph, entities of the same type are never directly connected by an edge. However, adding or removing edges indiscriminately (while preserving each node’s degree) will eventually lead to connecting nodes of the same type and thus compromise the validity of the randomized network. Since these strategies do not take node and edge labels into account, we need to follow a diferent approach for network randomization.
Instead of randomizing the original graph directly, we apply
a randomization procedure directly on the tabular data and then
build the randomized networks from the randomized tabular data.
Thus, the randomization procedure works as follows:
(1) Shufle all the fraud labels. This step maintains the fraud
rate of the original dataset but randomizes its attribution to
diferent transactions.
(2) Iterate over each entity type and, for each entity type, we
randomly chose ∗ pairs of values to be swapped. Here,
∈ [
This network randomization strategy guarantees semantically
valid banking networks with a random topology.
2.2.2 Motif significance measures. After doing subgraph counting
on both the original network and the randomized networks, we use
a motif significance measure to evaluate which subgraphs are
overand under-represented. Several measures have been proposed [
The z-score of a subgraph, , is computed as follows: Where, = −
• is the frequency of subgraph in the original network. • and are the mean and standard deviation of the frequencies of subgraph in the randomized networks, respectively.
We compute the ratio of a subgraph, , as follows:
=
Our goal is to find the subgraphs with the highest z-scores/ratio (i.e., the motifs) and subgraphs with the lowest z-scores/ratio (i.e., the anti-motifs).
In our experiments (Section 3), we show the ratio of the subgraphs since it is more interpretable than the z-score: if = 100, the subgraph appears 100 times more often in the original network than in the randomized networks. We complement our analysis by reporting , , and . (1) (2) 3 3.1
Table 1 outlines the parameters used to generate the entity graph and the transaction graph and provides summary statistics on the two graphs.
In the entity graph, we consider four node types (i.e., client, merchant, terminal, and card) and two edge types (i.e., fraudulent or legitimate).
In the transaction graph, we consider two node types (i.e., fraudulent and legitimate) and three edge types (i.e., only client, only merchant, or both client and merchant). The rationale for choosing these two entities lies in the close relationship between clients and cards and, similarly, merchants and terminals. In other words, since most clients use few cards and most merchants have few terminals, we simplify the graph by dropping the card and terminal entities.
Additionally, we found it necessary to constrain the considered time window due to computational constraints on subgraph counting.
Both graphs have hundreds of thousands of edges and many diferent connected components. The fraud rate in the entity graph is the number of fraudulent edges, while, in the transaction graph, the fraud rate is the number of fraudulent nodes. As a result, the fraud rates difer depending on the graph type. 3.2
In this subsection, we start with the entity graph results and then show the results of the transaction graph.
We analyze which subgraphs are motifs and anti-motifs based on the ratio (Equation 2): we consider subgraphs that have a considerably higher ratio than the others to be motifs, and subgraphs with the lowest ratios to be anti-motifs.
We focus on subgraphs of size three due to the higher computational cost of larger subgraphs. 3.2.1 Entity graph. From Figure 3 we can see that, for most cases, the ratio of all subgraphs stabilizes relatively quickly at ≈ 40 random networks. We observe that a few subgraphs have significantly higher ratio than the others ( > 100). Moreover, a few subgraphs
Number have significantly lower ratio than the others ( ≈ 0.01). We consider the first to be the motifs, and the last to be the anti-motifs, shown in Figure 4 (a) and Figure 4 (b), respectively.
From Figure 4 we notice that none of the subgraphs is a 3-node clique. This result might seem counter-intuitive as all transactions form a 4-node clique. A possible explanation is that some merchants are hub nodes and thus induce chain-like subgraphs. Another general observation is that all edges in the motifs are fraudulent, which is not true for the anti-motifs. Domain knowledge indicates that fraudulent transactions tend to be closely connected.
The first three motifs from Figure 4 (a) have a client at its center, connected to either (i) two terminals, (ii) one terminal and a merchant, or (iii) two merchants. Subgraphs (i) and (iii) tell us that the client made two fraudulent transactions at diferent merchants and terminals, respectively. These two subgraphs are motifs because fraud is sometimes recurring for fraudulent clients, and this information is lost in the randomized networks since they reshufle fraud labels. Subgraph (ii) tells us a similar story but notice that, since the merchant and the terminal are not connected, the merchant and the terminal are from diferent transactions. The last three motifs are equivalent to the first three but with the card at the center of the subgraph. Since clients can use multiple cards, the original network counts are lower for subgraphs with the card at the center of the chain than the counts of the subgraphs with the client at the center of the chain. We also note that, in practice, it might be interesting to investigate all cards used by the client.
The first three anti-motifs from Figure 4 (b) have a merchant at its center. All three anti-motifs convey the same information: merchants typically either have only legitimate transactions or only fraud transactions, i.e., fraud tends to cluster around the same risky merchants. In the randomized networks, since we randomly swap edges, these relations are lost. Finally, the last anti-motif tells us that it is not common for clients to use multiple cards in legitimate transactions. Indeed, clients that use multiple cards are typically associated with fraudulent activity. 3.2.2 Transaction graph. Figure 5 shows the evolution of the ratio for each 3-node subgraph in the transaction graph. After 80 random networks, the ratios seem to stabilize, and we can clearly distinguish ifve subgraphs that stand out, namely, the top-4 subgraphs and the bottom-1 subgraph. These subgraphs are presented in Figure 6.
The common feature in the four motifs is at least two transactions that share the same client and merchant. We may lose this pattern during the randomization since we swap merchants and clients independently. However, it is still interesting to observe a significant number of patterns where the same client makes two or three transactions in the same merchant in less than six hours. 10,000 1,000 100 10 1 0.1
Motifs
Number
Three of the four top motifs are a 3-node clique, which happens when three transactions that share a merchant or client occur within the same six-hour window. Once again, the randomization of the entities breaks such patterns.
It is important to note that some motifs contain transactions processed in the same timestamp (represented with bi-directional edges). This pattern can happen in the same merchant when the merchant is processing transactions in a batch or has multiple terminals.
The only anti-motif is a sequence of three transactions in the same merchant, where the middle transaction is fraudulent, and the other two are legitimate. This pattern is less frequent in the original network than in the randomized networks since fraud transactions typically occur together in reality, and the randomized networks break this pattern.
The motif analysis can be a tool to characterize banking datasets. Beyond summary statistics, the list of motifs and anti-motifs surfaces underlying fraud patterns.
Fraud experts, who may not be knowledgeable in data science or statistics, often use graph visualization for data exploration. Motif analysis serves as a visual summary characterization of a dataset for fraud detection.
As an illustrative example, let us consider a fraud expert at a bank. Their role entails designing new rules to prevent fraud and reviewing unlabelled transactions. The expert can review the characteristic patterns surfaced by motif analysis to tailor the fraud detection system in place. Over time, fraudsters design new schemes to evade detection. Periodic analysis of motifs surfaces upcoming fraud schemes and overall behavioral trends. 1759 / 0.14 ± 0.99 2507 / 0.30 ± 0.54 2,223 289 / 0.13 ± 0.34
1,567
When reviewing an unlabelled transaction, the expert can compare the respective subgraph with known motifs. This context can give insight into which pattern, fraudulent or legitimate, might occur.
On the other hand, by extracting the most relevant transaction patterns and uncovering new fraud schemes, motif analysis can complement common fraud detection systems. These insights can be used to improve both machine learning models and rule-based systems. 5
We explore motifs and anti-motifs in the context of banking fraud using two graph representations, namely entity graphs and transaction graphs. We propose a novel randomization method that operates directly on tabular data. This way, we overcome the limitations of current network randomization methods in the context of banking fraud.
Moreover, we extract heterogeneous network motifs that convey more information than traditional network motifs and find they ofer interpretable results. Insights extracted from motif analysis can be used to aid fraud analyst investigate specific cases and improve fraud detection systems by uncovering new fraud schemes.
As future work, one can investigate whether diferent banking
datasets have similar motifs (and anti-motifs) and if those patterns
are diferent in merchant datasets. This research would follow the
ifndings by Milo et al . [