GRAPH FEATURE BASED SYSTEM FOR FLOW MANAGEMENT

Input data is obtained and converted into a graph. Based on the converted input data, a time series of snapshot graphs is generated by selecting edges whose timestamps are in a given time window for each of a plurality of time windows, each edge having a corresponding attribute. Internal flow probabilities are computed for each snapshot graph of the time series of snapshot graphs and a system is controlled based on the internal flow probabilities.

The following disclosure(s) are submitted under 35 U.S.C. 102(b)(1)(A):

Ryo Kawahara and Mikio Takeuchi. Cash Flow Prediction of a Bank Deposit Using Scalable Graph Analysis and Machine Learning. In 2021 IEEE International Conference on Big Data (Big Data) 2021 Dec. 15 (pp. 1647-1656). IEEE.

BACKGROUND

The present invention relates generally to the electrical, electronic and computer arts and, more particularly, to machine learning systems.

Flow management, such as cash flow management, traffic flow management, and the like, is an important task for a variety of applications, from managing monetary flows to managing road traffic. Such flows may be modeled using graphs and analyzed using a graph analysis platform such as a graph database. In analyzing traffic flows (such as network traffic and road traffic), graphs are used to model the arrival and departure of packets, vehicles, and the like.

In banking, cash flows corresponding to bank transfers are used as the main mode of settlement of business trades among enterprises. To support the timely settlements of the trades, a bank must retain a sufficient amount of cash. This amount fluctuates every day depending on the bank's requests for transfers, withdrawals, or deposits from customers, as well as on the incoming transfers. However, keeping excessive amounts of cash will lead to a loss of opportunity for gaining a profit from investing the funds on hand. Since a failure of cash flow management in a bank has a large impact on the liquidity of a nationwide settlement network, the amount of cash that a bank must retain is usually regulated by authorities. Such regulations require each bank to keep the monthly average of its current amount of cash at a certain level. Generally, regulation is appropriate to maintain the liquidity of the nation-wide inter-bank settlement network, and also for the central bank to control the money supply. Thus, each bank needs to predict the total amount of deposits of customers to properly control its cash level and satisfy pertinent governmental regulations. There are, however, issues in the prediction of the aggregate amount of deposits: although there are known patterns in its dynamics, predicting how long a money flow stays within a bank is difficult.

BRIEF SUMMARY

Principles of the invention provide a graph feature-based system for flow management. In one aspect, an exemplary method includes the operations of obtaining input data; converting the input data into a graph; based on the converted input data, generating a time series of snapshot graphs by selecting edges whose timestamps are in a given time window for each of a plurality of time windows, each edge having a corresponding attribute; computing internal flow probabilities for each snapshot graph of the time series of snapshot graphs; and controlling a system based on the internal flow probabilities.

In one aspect, a non-transitory computer readable medium comprises computer executable instructions which when executed by a computer cause the computer to perform the method of obtaining input data; based on the converted input data, converting the input data into a graph; generating a time series of snapshot graphs by selecting edges whose timestamps are in a given time window for each of a plurality of time windows, each edge having a corresponding attribute; computing internal flow probabilities for each snapshot graph of the time series of snapshot graphs; and controlling a system based on the internal flow probabilities.

In one aspect, a shared-memory graph analysis platform based on a graph computer comprises a memory and at least one processor, coupled to the memory, and operative to perform operations comprising obtaining input data; based on the converted input data, converting the input data into a graph; generating a time series of snapshot graphs by selecting edges whose timestamps are in a given time window for each of a plurality of time windows, each edge having a corresponding attribute; computing internal flow probabilities for each snapshot graph of the time series of snapshot graphs; and controlling a system based on the internal flow probabilities.

Techniques as disclosed herein can provide substantial beneficial technical effects. Some embodiments may not have these potential advantages and these potential advantages are not necessarily required of all embodiments. By way of example only and without limitation, one or more embodiments may provide one or more of:improve the technological process of graph-based machine learning in cases where a graph is dynamic (that is, the graph structure and node attributes change over time) by use of snapshot graph sequences, an internal flow feature (where the flow dynamics is approximated as a random walk (or Markov process)), and/or integration with a time series;a transaction graph that is dynamic (that is, the graph structure and node attributes change over time);processes graph edges that have attributes (such as the amount of money transferred in a transaction);handling of large and often scale-free graphs, which indicates the existence of super-hubs that connect a large number of nodes (making it difficult to decompose, filter, or sample the graph);an extensible and scalable graph analysis platform that can extract domain-specific graph features; support for a graph computer which targets machine learning-related tasks, supports a graph programming model, and computes a graph feature with an algorithm that is described in the model;support for the vertex-centric, bulk synchronous parallel programming paradigm, where memory footprints of the attributes and inter-vertex messages for graphs are optimized;formulation of cash flow prediction as a time-series prediction task with a dynamic graph as an input;improved flow analysis using a shared-memory graph analysis platform based on a graph computer;maintenance of edge attributes and node attributes of a snapshot graph in memory for direct access;compact representations of the edge attributes and the node attributes in memory;improved cash flow prediction accuracy by applying graph analysis;significant reduction in the error of a long-term cash flow prediction compared to that of a non-graph-based time-series prediction model;improved ability to detect and mitigate hacking, detect and mitigate money laundering, control traffic flow, and the like; andreduced cost for a bank's cash operation and increased profit in terms of asset liability management (ALM) as a result of improving the accuracy of the cash flow prediction.

Some embodiments may not have these potential advantages and these potential advantages are not necessarily required of all embodiments. These and other features and advantages will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.

DETAILED DESCRIPTION

Principles of inventions described herein will be in the context of illustrative embodiments. Moreover, it will become apparent to those skilled in the art given the teachings herein that numerous modifications can be made to the embodiments shown that are within the scope of the claims. That is, no limitations with respect to the embodiments shown and described herein are intended or should be inferred.

Introduction

Flow management, such as cash flow management, traffic flow management, and the like, is an important task for a variety of applications, from managing monetary flows to managing road traffic. For example, a bank's deposits continuously fluctuate as customers execute transactions and monetary funds flow between different accounts and different banks. Moreover, a bank needs to predict the total amount of deposits of customers to properly control its cash level and satisfy governmental regulations. Such regulations require each bank to keep the monthly average of its current amount of cash at a certain level, a regulation that is needed to maintain the liquidity of the nation-wide inter-bank settlement network and to control the money supply by the central bank. There are, however, issues in the prediction of the aggregate amount of deposits: although there are known patterns in its dynamics, predicting how long a money flow stays within a bank is difficult.

FIG.1illustrates a conventional two-tier, inter-bank settlement system100. A transfer order from A's account at bank104to B's account at bank108is depicted. The actual transfer of funds is performed by the inter-bank settlement system112of the central bank116.

FIG.2illustrates an example conventional graph204of a bank's current deposit in the central bank116, and an example reserve requirement208-1,208-2(upper and lower limits) and target level212. A bank104,108must maintain its amount of deposit in the central bank116between the upper limit208-1and lower limit208-2in terms of its average for a month to maintain the liquidity of the settlement system112. If a bank104,108violates the upper limit208-1of deposits, the bank104,108will be subject, for example, to a reduced interest rate (e.g., −0.1%). (The interest rate of the current deposit in the central bank is determined monthly by the average amount of deposit (the cumulative number) during the evaluation period, as illustrated by chart216. The evaluation period is, for example, from the 15thof a month to the 16thof the next month. It is noted that, depending on economic conditions, the upper limit208-1or the lower limit208-2may be of less importance. For example, during quantitative easing, the upper limit208-1may be of less importance.)

FIG.3illustrates a conventional reserve requirement process300. A monitoring process312monitors, for example, the transactions of customers of the bank104and cash on hand. A prediction process308predicts a future amount of cash on hand. If a bank104has too much cash on hand, it may, for example, purchase bonds via market324to lower the amount of cash on hand. Similarly, if a bank104has too little cash on hand, it may, for example, sell bonds via the market324to increase the amount of cash on hand. This is part of the planning process316and the operations process320. (It is noted that uncontrollable aspects of the money flow include that money for the settlement of customers' money transfer requests fluctuates every day and a precise prediction of the cash demand is important to make the operation efficient. It is also noted that controllable aspects include money for market trades by a bank: excess money can be lent or consumed by government bond purchase, and vice versa. Profitability and the cost of the operation depend on the market conditions.)

When machine learning (ML) is used for the prediction of cash on hand, graph feature vectors can be used to improve its accuracy. In general, bank transfer transactions can be formalized as a graph (Vertex=account, Edge=transfer). Though the transaction graph is a source of rich information, a ML model cannot handle a graph directly because of its non-regular and sparse structure. A conversion to a vector that represents a state of the graph is needed. There are, however, issues in the graph feature extraction:1) many existing methods ignore domain-specific edge attributes (especially money; most of them focus on the topology only); and2) scalability is important, as the transaction graph in a bank104,108is huge (typically on the order of one million nodes and ten million edges).

Pertinent Ideas

FIG.4illustrates a transaction sub-graph400created from transaction data, in accordance with an example embodiment. Each node404,408,412,416,420represents an account (such as an account A={v|v=(id, is_internal)} where id is the account identifier) and edges, such as edges424,428, represent transfers. Node416represents an account at an external bank108; the remaining nodes404,408,412,420represent accounts at the given bank104. When money transfers between accounts of the given bank104, the cash on hand of a given bank104does not change; alternatively, when money transfers between accounts of the given bank104and another bank108, the cash on hand of the given bank104changes. If money is flowing into an account that typically conducts transactions primarily with external banks108, then this money will tend to diminish the cash on hand of the given bank104; alternatively, if money is flowing into an account that typically conducts transactions primarily with accounts of the given bank104(as represented by edge436from node432), then this money will tend to increase the cash on hand of the given bank104. Since node412has a weight w of 0.7, there is a 70% chance of a transfer being internal and a 30% chance of a transfer being external.

In general, cash flow prediction for a bank104is an important task as it is not only related to liquidity risk but is also regulated by financial authorities. As noted above, to improve the prediction, a graph analysis of bank transaction data is advantageous, while its size, scale-free nature, and various attributes make the task challenging.

In one example embodiment, a graph-based machine learning method for a cash flow prediction task is disclosed. An extensible and scalable shared-memory parallel graph analysis platform is introduced that supports the vertex-centric, bulk synchronous parallel programming paradigm. One novel graph feature introduced upon the platform is an internal money flow feature based on the Markov process approximation.

In the context of conventional liquidity risk management, the amount of cash of a bank104,108is regarded as a static parameter of a stochastic risk model. However, a dynamical approach, such as the prediction of the cash flow, has more value since it can enable further optimization of cash flow management by reducing the cost of cash preparation and increasing the profit of the investment.

Generally, each bank104,108has a large amount of transaction data. This data can be used for various financial analysis tasks including anti-money laundering (AML), financial fraud detection, credit risk analysis, and cash flow prediction. One important characteristic of the data is that it can be modeled as a graph, such as the graph400. A graph400can express the structure of the trades, such as counter parties and supply chains, which are often overlooked in the usual time-series analysis. Graph-based machine learning is a promising approach and has already been successfully applied in various areas. However, the financial transaction graph400of a bank104,108may have the following characteristics that are not well addressed in the existing methods:a transaction graph400is dynamic (that is, the graph structure and node attributes change over time);edges424,428have attributes (in particular, the amount of money transferred in that transaction is an attribute of the edge424,428that plays a pertinent role); andthe graph400is large and often scale-free, which indicates the existence of super-hubs that connect a large number of nodes404,408,412,416,420(which makes it difficult to decompose, filter, or sample the graph400).

Because of the aforementioned characteristics of the transaction graph400, we have found that it is appropriate to use an extensible and scalable graph analysis platform that can extract domain-specific graph features.

From the machine-learning perspective in general, the graph feature computation is an embarrassingly parallel problem in which a task (i.e., the computation of a graph feature) of a node404,408,412,416,420(or an edge424,428) is independent of the tasks of other nodes404,408,412,416,420(or edges424,428), while the graph feature computation does not update the graph data itself. As used herein, “embarrassingly parallel” is used in its ordinary sense as will be understood by a skilled artisan; i.e., an embarrassingly parallel workload or problem is one where little or no effort is needed to separate the problem into a number of parallel tasks.

The existing graph analysis platforms are classified into two types. The first type is the graph database. It supports a graph query language and returns a set of sub-graphs that satisfies the condition (i.e., pattern) described in the language. It is suitable for interactive analysis; however, it is impractical to use a graph database for a machine-learning task(s) because (i) in the graph query language, the parallelism is implicit and its scope is limited, and (ii) the graph database has the overhead of supporting persistence and transactions, which are unnecessary in this context.

The second type of platform is the graph computer, which targets machine learning-related tasks. It supports a graph programming model and computes a graph feature with an algorithm that is described in the model. The model does not update the graph400and thus the graph computer does not support persistence or transactions. In addition, the model supports the embarrassing parallelism, which can accelerate graph feature computation from large-scale graphs400.

From these characteristics, a graph computer is used for an exemplary machine learning task in one or more exemplary embodiments. An exemplary embodiment of an extensible and scalable shared-memory graph analysis platform is disclosed that supports the vertex-centric, bulk synchronous parallel programming paradigm, where the memory footprints of the attributes and inter-vertex messages for financial graphs400are optimized. In one example embodiment, an internal cash flow feature based on Markov process approximation is disclosed.

Formulation of an Exemplary Problem

In one example embodiment, cash flow prediction is formulated as a time-series prediction task with a dynamic graph400as an input.

The amount of cash in a bank104,108is affected by multiple factors. Among those, increases or decreases in the amount of deposits of customers have uncertainties and thus prediction is appropriate. Let B(t) be the total amount of deposits in a bank104,108at time step t∈N. This value is not predicted directly because its distribution is not stationary. Moreover, the data set includes transactions and does not contain the amounts of deposits of the accounts. Therefore, the target variable of the prediction is the change in the total amount of deposits in a bank104,108in T time steps from the current step. That is,

In one or more embodiments, the size of the time step/and the length of prediction T∈N are assumed to be one day and approximately one month, respectively. This is because the regulator evaluates the amount of cash of a bank104,108by its monthly average. A shorter prediction length is also useful for optimizing the cash flow management operations, and other prediction timeframes are contemplated.

ΔT(t+T) is predicted from past transaction records and a number of exogenous variables.

where fTis a prediction model to be learned from the data and the total amount of deposits is {f(t)|t<=tc}, x(t) is a feature vector that is derived from the data, and xC(t′) is a feature vector that does not depend on the past data (e.g., whether t′ is a Sunday or not).

In one or more embodiments, the feature vector can be decomposed as x=(xG∥xN), where xG(t) is the graph feature vector, xN(t) is the non-graph feature vector, and (⋅∥⋅) is the vector concatenation.

One pertinent aspect is to define a function FGthat computes the feature xG(t) from the dynamic graph Γ(t). Here, Γ(t) is defined as a sequence of graphs400:

and G(t)=(V(t), E(t)) is a snapshot graph400at time step t, and V(t) and E(t) are the set of vertices404,408,412,416,420and edges424,428at time step t, respectively. Here, a vertex v∈V(t) corresponds to an account, and an edge e∈E(t) corresponds to a transfer transaction. Vertices404,408,412,416,420and edges424,428can have attributes, which are denoted as v.attr and e.attr, respectively, where attr is an attribute name. In particular, an edge e has at least two important attributes: the time stamp and transfer amount. A time window operation is used for each time step to select transfers that are modeled as edges424,428in E(t). The construction process of the snapshot graph400is described in the section entitled Experiment: Pre-processing.

A simplification on the function FGis made so that only one snapshot graph400is processed at a time and converted into a low-dimensional vector to reduce the memory footprint.

where HG: Γ→→d, d∈N is a graph processing function that is implemented on a scalable graph analysis platform.

Scalable Graph Analysis Platform

FIG.7is a block diagram of a shared-memory graph computer800that supports the vertex-centric BSP programming model, in accordance with an example embodiment. The graph computer800includes a plurality of central processing unit (CPU) cores804, . . . ,808that execute, under the control of controller812, a set of algorithms, such vertex programs816,820, . . . ,824, that includes standard ones as well as specialized ones for financial domains. Graph storage828stores the snapshot graph400, including the storage of the edge attributes and the node attributes in attribute storages836and844. In particular, graph storage828includes structure storage832and attribute storage (map)836. Structure storage832includes communications buffer840and attribute storage (field)844for direct field access. Note also the shared memory848implemented as software modules combined with computer memories.

In one example embodiment, the controller812and the vertex programs816,820, . . . ,824are implemented as software modules. In particular, the vertex programs816,820, . . . ,824are software modules that are executed as multiple threads to enable the parallel processing. The graph storage828and sub-modules832,836,840,844are implemented as software modules combined with computer memories to store the graph data. The structure storage832stores nodes404and edges424,428of the snapshot graph400. Attributes of the nodes404and edges424,428are stored in attribute storages836,840. The communication buffer840is used by the vertex programs816,820, . . . ,824for storing intermediate data and the graph features as well as for sharing those values with other vertex programs for communication. Given the teachings herein, the skilled artisan can implement the software modules by programming the logic described herein, using a suitable high-level programming language compiled or interpreted into machine-executable code.

In one example embodiment, an exemplary scalable graph analysis platform, which includes the graph computer and the corresponding algorithms, is written in Java and works as a Java library. The platform also has a command-line interface as well as a representational state transfer (REST) application programming interface (API) that is suitable for a microservice usage and implementation in a cloud environment. In one example embodiment, the platform is a vertex-centric, shared-memory, parallel Java graph library for fast feature generation at high scale (such as, 24 minutes for a |V|=100M, |E|=1B random graph on a conventional central processing unit in a cloud environment).

High performance and scalability are pertinent aspects of a graph computer to enable graph feature computation from large-scale graphs. A pertinent aspect for high performance is fast access to the node- and edge-attributes by keeping them in memory and referencing them directly. (This refers to, for example, attribute storages836,844. In particular, frequently accessed attributes are stored in attribute storage844, which is tightly coupled with structure storage832to provide the fast access.)

The limitation in the in-memory graph analysis of real-world data due to the memory size has been mitigated by advanced semiconductor technology. Combined with the shared-memory nature, one or more exemplary embodiments of the graph computer have no serialization or communication overhead (see communication buffer840), which can lead to better performance compared to other cluster-based graph computers such as are employed in known graph and graph-parallel computation techniques. A pertinent aspect for high scalability is a small footprint which is contradictory to keeping the attributes in memory. In one or more embodiments, this problem is addressed by using compact representations, such as primitives rather than objects, as fields rather than a map (see, attribute storage (direct field)844), and as type-specific collections (arrays, lists, sets, maps, and the like) (see, attribute storage (map)836) rather than generic Java collections (a library of the above data structures provided as a default for Java programs).

New Graph Features Based on Internal Flow

In addition to the existing general-purpose graph features, domain-specific graph features can be utilized, which explicitly exploit edge and vertex attributes.

One graph feature is named internal flow probability. The context behind this feature is explained as follows. A bank's transaction data may contain (a) transfers between accounts in the bank104,108(i.e., internal transfers) as well as (b) transfers from or to accounts in other banks104,108using inter-bank settlement networks (i.e., external transfers). Among these transfers, only the external transfers change the total amount of deposits in a bank104,108.

When an internal account receives money from an external account, it is expected that the money will soon be used for fulfilling their business needs within a typical business cycle (e.g., a company sells their products to receive money from its customers, which requires payments to its suppliers in the monthly cycle). If the account tends to (A) trade with internal accounts, then the money continues to be in the bank104,108, while if the account tends to (B) trade with external accounts, the money will be sent to other banks104,108and the total amount of deposits in the bank104,108returns to its previous level. Scenario (A) is more important in one or more instances because it has a larger impact on the monthly average of the total amount of deposits in the bank104,108.

The difference between Scenarios (A) and (B) are approximately estimated by estimating the ratio of transfer to internal and external accounts from the snapshot graph400whose window size is a typical business cycle (e.g., one month).

Here, the internal flow probability feature is defined. Let M(v, v′) be the amount of money transferred from v to v′ within a time window, and Min(v) and Mout(v) be the amount of money transferred to and from v, respectively. (For example, 300 yen are shown flowing from node412to node404inFIG.4.) The ratios of incoming (from v′ to v) and outgoing (from v to v′) money flow within a time window are defined as follows:

(Other flows and functions include:

sinn(v) (the probability of in-flow previously being internal for n-hops after its entrance); and

sinn+(v): the probability of in-flow previously being internal for more than n-hops.)

The ratios of incoming and outgoing internal money flow of v within a time window are

where D∈{in, out} is a label that indicates the direction, and V(v) is the set of internal neighbor vertices.FIG.4shows an example of those quantities.

To roughly estimate how long money at vertex v can stay in the bank104,108, a random walk on the vertices of the snapshot graph400is considered, where the aforementioned ratio fD(v, v′) is regarded as the transition probability of the random walk. Let n∈N be the number of hops (steps) of a random walk on a graph400. For D=out, the internal flow probability is defined as the probability of money performing a random walk from v in n hops only on the internal vertices404,408,412,420in the graph400before it exits to an external vertex416. Inversely, for D=in, it is defined as the probability of money having performed a random walk to v in n hops only on the internal vertices404,408,412,420after its entry from an external vertex416.

Similarly, the probability of money at v can be expressed doing a random walk for more than n hops as follows.

(It is noted that sinn(v) is the probability of the in-flow previously being internal for n-hops after its entrance; sinn+(v) is the probability of the in-flow previously being internal for more than n-hops; soutn(v) is the probability of the out-flow being internal for n-hops before its exit (modeled as a random walk); and soutn+(v) is the probability of the out-flow being internal for more than n-hops where:

Note that there is a normalization condition for any n.

Here, any temporal and inter-vertex correlations of edges424,428within a time window are ignored. Therefore, the actual sequence of transfers can be different from that of the random walk in general. Rather than considering the detailed and accurate money flow, the extent of the internal transaction network where money flow can reside is roughly estimated from a snapshot graph400.

Once the internal flow probability is defined for each vertex404,408,412,420, the values to be used for predicting the total amount of deposit in a bank104,108are aggregated. Let L be a subset of internal vertices404,408,412,420in the graph400, such as large enterprises. The aggregated internal flow probability is computed as:

where Minext(v) and Moutext(v) are the amount of incoming and outgoing external money flows on vertex v, respectively. The complexity of this algorithm is O(n|E|+n|V|).

FIG.5is a flowchart for an example method500generating a prediction of a future total amount of deposits, in accordance with an example embodiment. In one example embodiment, input data504is obtained (operation508) and converted into a graph400(operation512). A time step is initialized to t=0 (operation516) and a snapshot graph400(graph(t)) is generated (operation520) by selecting edges424,428whose timestamps are in time window [t−T+1, t]. Time step t is incremented (operation524) and a check is performed to determine if t<tc (operation528). If t<tc (YES branch of operation528), the method500proceeds with operation520; otherwise (NO branch of operation528), the time step is set to t=0 (operation532).

Internal flow probabilities for snapshot graph(t) are computed (operation536; described more fully below in conjunction withFIG.6), the aggregated features from internal flow probabilities are computed (operation544), and other features (e.g., various conventional graph features that can be used jointly with the internal flow features, such as degree, a measure that counts the number and quality of links to a web page, a measure for the collection and analysis of egocentric social network data, and the like) are computed (operation548). Time step t is incremented (operation552) and a check is performed to determine if t<tc (operation556). If t<tc (YES branch of operation556), the method500proceeds with operation536; otherwise (NO branch of operation528), a check is performed to determine if method500is performing a training or inferencing operation (operation560). If the method500is performing inferencing (inferencing branch of operation560), the method500proceeds with operation572; otherwise (training branch of operation560), a model is trained (train({(features(t), f(t))|t<=tc})) to generate model568(operation564) and the method500proceeds with operation572. During operation572, the future effect of the internal flows, such as the future total amount of deposits, is predicted to generate prediction576(f(tc+1)=model({features(t)|t<=tc})). Typically, the time step t is set to one day, and the generated prediction576considers 31 days of transaction data. In one example embodiment, the prediction576is used to control a system, such as detecting and mitigating an identified situation (operation580). In one example embodiment, the prediction576is used to detect unusual flows of funds that can be indicative of financial hacking and be used to trigger a blocking of the corresponding malicious network traffic; for example, by adjusting the configuration of a network firewall or the like. In another example, unusual flows of funds that can be indicative of money laundering may be detected and may trigger an alert to the proper authorities. In one example embodiment, the method500is configured to monitor road traffic and the prediction576is used to detect traffic jams and trigger a rerouting of traffic; for example, by controlling traffic signals via an interface to a wide-area network102(seeFIG.8and accompanying text; the firewall configuration could also be controlled via the interface to the wide-area network102, or other wired or wireless connection).

FIG.6is a flowchart for an example method600for generating feature data676, in accordance with an example embodiment. In one example embodiment, graph data of a graph400is obtained (operation608) and all vertices v in V are assigned an unprocessed designation (operation612). An unprocessed vertex v from V is retrieved (operation616) and the edge weight, fin, and foutare computed (operation620). A check is performed to determine if all vertices v in V have been processed (operation624). If all vertices v in V have not been processed (NO branch of operation624), the method600proceeds with operation616; otherwise (YES branch of operation624), all vertices v in V are assigned an unprocessed designation (operation628).

An unprocessed vertex v from V is retrieved (operation632) and the 0-hop probabilities sin0(v), sout0(v) are initialized (operation636). A check is performed to determine if all vertices v in V have been processed (operation640). If all vertices v in V have not been processed (NO branch of operation640), the method600proceeds with operation632; otherwise (YES branch of operation640), hop count n is initialized to one (operation644) and all vertices v in V are assigned an unprocessed designation (operation648).

An unprocessed vertex v from V is retrieved (operation652) and the n-hop probabilities sinn(v), soutn(v) are computed (operation656). A check is performed to determine if all vertices v in V have been processed (operation660). If all vertices v of V have not been processed (NO branch of operation660), the method600proceeds with operation652; otherwise (YES branch of operation660), the hop count n is incremented (operation664). A check is performed to determine if n<n_max (operation668). If n<n_max (YES branch of operation668), the method600proceeds with operation648; otherwise (NO branch of operation668), the n-hop probabilities sinn(v), soutn(v) are output to generate feature data676(operation672).

Comments on Data

Embodiments of the invention can be used on many different kinds of data; for example, a set of bank transactions such as from a large bank104,108. The transaction data can be used, for example, to construct a time series of the total amount of deposits as well as to construct the graphs400. This example of data is intended to be exemplary and non-limiting. One or more embodiments are usable even on scale-free data and/or data that exhibits super-hubs.

In one example embodiment, the transfer log (where {tx|x=(txid, v, v′, amount, timestamp)}) is pre-processed into a sequence of graphs400as follows:extract the accounts that appear in the transactions and convert the extracted accounts into vertices404,408,412,416,420;convert the transfers into a list of edges424,428; andgenerate snapshots for the edge list using a daily sliding window of length W, i.e., transfers that occurred in [t−W+1, t] are selected as a snapshot of the t-th day.

The daily snapshots are then processed as graphs400by the scalable graph analysis platform to extract graph feature vectors. The vectors include a daily time series that describes the dynamics of the graph sequence in a fixed dimension.

Graph Feature Generation

In one experimental setup, a bare-metal machine with 80 cores of a cloud server-level CPU and 800 GB memory was used, with a conventional multi-tasking operating system. Exemplary data included snapshot data on the order of one month with over four million nodes and over 60 million edges, and data on the order of one year with over 10 million nodes and over 590 million edges.

1) Selection of large business accounts: as part of a non-limiting exemplary experiment, for the aggregation of the vertex-level features (see section entitled New graph features based on internal flow), a subset of accounts L was selected from the whole set of accounts. The focus was mainly on large enterprises. This is because the distribution of the amount of money transfers has a power-law tail, which indicates that the top accounts dominate the change of the total amount of deposit.

Such accounts can be found, for example, by listing the top 100 accounts in the monthly amount of transfer for each month and taking the union of them. In the non-limiting exemplary experiment, 100+ accounts were identified in this way and were defined as the elements of the large account set L.2) Prediction model: an implementation of the gradient boosting method for the time series prediction was used. Since the model is decision tree-based, it can handle a non-linear relationship between the input and output.

Among the various input variables, a number of those are based on the current and past transaction data. The features include the prediction target variables and graph features (the internal flow probability). To incorporate the capability of autoregressive integrated moving average (ARIMA)-like models, the features were further processed as follows:raw past value of time step t−p where p=1, 2, 3, . . . ;moving average of length r; anddifference between the current and a past value at t−p.
Here, the features generated by the aforementioned process are called derived features.

Calendar features were also used to incorporate the seasonality. Binary-encoded national and bank holidays, weekends, “five-ten days,” and adjusted five-ten days were used, as well as day of week (0-6), business day (1-27), and day of month (1-31). The five-ten day was defined on the basis of the domain knowledge. That is, the value is 1 if the day of the month is 5, 10, 15, 20, 25, or the end of a month; otherwise, the value is 0. The adjusted five-ten day is equivalent to five-ten days except for weekends and holidays, where five-ten days are moved to the latest weekdays.

The non-graph feature set was defined as a set of ΔT(t) and its derived features and calendar features. Here, T corresponds to the length of the prediction. The non-graph feature set works as the baseline model of this experiment.

The feature selection was further optimized using a greedy removal of unnecessary features from each feature set.3) Metrics of evaluation: for the evaluation of the prediction accuracy, a relative mean absolute error (MAE) was chosen as a metric, instead of the usual root mean square error (RMSE). The relative MAE does not depend on the unit (i.e., currency) of the predicted value. This choice is similar to that of previous studies of ATM cash flow prediction, where symmetric mean absolute percentage error (SMAPE) is used. The reason for the choice is that the minimization of RMSE indicates that the predicted value is the average of the samples, while the average tends to diverge when the samples are derived from a power-law distribution p(x)˜x−awith an exponent a≤2, due to the existence of the large outliers.

To compare the accuracy with that of different time series, the MAE was normalized with that of a baseline MAE, which is called the relative MAE here. A baseline was chosen to be a simple method that uses the mean of the values of the past 50 days as a predicted future value. The idea is somewhat similar to the coefficient of determination (R2). The results of Saturdays, Sundays, and holidays were eliminated since a very small amount is transacted on those days.4) Training, validation, and testing: the data was split into training, validation, and testing data sets. The training (V) and validation data sets were used for the hyper-parameter optimization and the feature selection (see, e.g., discussion of prediction model elsewhere herein). The training (T) and testing data sets were used for the evaluation of the accuracy. A 31-day buffer was put between the training (T) and the testing periods to avoid using future values in the training.

At the beginning of the training time series, the first T steps cannot be used as the target of the prediction when one uses a T days ahead prediction model. In addition, the first T′ steps cannot be used as a feature since the moving average operation requires samples from the past T′ steps. Therefore, the first T+T′ steps of the data set are excluded from the training. In the present case, the first 62 steps were excluded and the length of the training data set was reduced to approximately seven months.

The skilled artisan will be able to apply a time-series cross validation (CV), such as a rolling forecasting origin, instead of the above simple use of the validation set, given a data set with sufficient length of time. It should be noted that, depending on the regression technique employed, the skilled artisan will be able to select appropriate hyper-parameters, given knowledge of the relevant domain and the teachings herein.

It is found that many of the proposed graph features improve the accuracy from the non-graph feature set for the prediction model of 7 days and 31 days ahead (T=7 and T=31).

Given the discussion thus far, it will be appreciated that, in general terms, an exemplary method, according to an aspect of the invention, includes the operations of obtaining input data504(operation508); converting the input data504into a graph400(operation512); based on the converted input data, generating a time series of snapshot graphs400(operation520) by selecting edges424,428whose timestamps are in a given time window for each of a plurality of time windows, each edge424,428having a corresponding attribute; computing internal flow probabilities for each snapshot graph of the time series of snapshot graphs400(operation536); and controlling a system based on the internal flow probabilities.

In one aspect, a non-transitory computer readable medium comprises computer executable instructions which when executed by a computer cause the computer to perform the method of obtaining input data504(operation508); converting the input data504into a graph400(operation512); based on the converted input data, generating a time series of snapshot graphs400(operation520) by selecting edges424,428whose timestamps are in a given time window for each of a plurality of time windows, each edge424,428having a corresponding attribute; computing internal flow probabilities for each snapshot graph of the time series of snapshot graphs400(operation536); and controlling a system based on the internal flow probabilities.

In one aspect, a shared-memory graph analysis platform based on a graph computer comprises a memory and at least one processor, coupled to the memory, and operative to perform operations comprising obtaining input data504(operation508); converting the input data504into a graph400(operation512); based on the converted input data, generating a time series of snapshot graphs400(operation520) by selecting edges424,428whose timestamps are in a given time window for each of a plurality of time windows, each edge424,428having a corresponding attribute; computing internal flow probabilities for each snapshot graph of the time series of snapshot graphs400(operation536); and controlling a system based on the internal flow probabilities.

In one example embodiment, aggregated features are computed from the internal flow probabilities (operation544); a model is trained based on the aggregated features (operation564); and a future effect of internal flows is predicted using the trained model (operation572), wherein controlling the system is based on the predicted future effect of the internal flows.

In one example embodiment, the edge attributes and one or more attributes of nodes of the snapshot graph400are maintained in memory for direct access by using compact representations of the edge attributes and the node attributes.

In one example embodiment, message-passing-based or a vertex-centric BSP algorithm are used for each node.

In one example embodiment, other features are computed from the internal flow probabilities (operation548) and the training of the model is further based on the other computed features. For example, these other features can be in addition to the aggregated features. Generally, those features can be used in addition to the internal flow feature in the case of a node-level prediction, as well as in the case of a graph-level prediction with the aggregated features.

In one example embodiment, a model is trained based on the internal flow probabilities (operation564); and a future effect of internal flows is predicted using the trained model (operation572), where controlling the system is based on the predicted future effect of the internal flows.

In one example embodiment, the input data504comprises account data, an account subset L⊆an internal account set, a time series of a prediction target {f(t′)|t′<=t}, and hyper-parameters comprising a time window size W, a prediction length T, and a maximum number of hops nmax.

In one example embodiment, in the time series of snapshot graphs {snapshot graph(t)|t <=t′}400, each internal vertex corresponds to an internal account of a bank and each of the selected edges424,428corresponds to a transaction and has a timestamp attribute and an amount attribute.

In one example embodiment, the trained model is model MTfor a prediction length T.

In one example embodiment, the computing the internal flow probabilities further comprises computing an edge weight for each edge424,428of each vertex of the graph400(operation620); initializing an in 0-hop probability and an out0-hop probability for each internal vertex of the graph400(operation636); computing an in n-hop probability and an out n-hop probability for each internal vertex of the graph400and for each value of n between one and a maximum value of n (operation656); and outputting the in n-hop probabilities and the out n-hop probabilities to generate feature data676(operation672). Regarding this generated feature data, refer to the above discussion re “these other features”; similar comments apply here as well.

In one example embodiment, a vertex-level feature of a given vertex in the graph400is computed, wherein the vertex-level feature corresponds to an n-hop probability of a random walker to or from the given vertex, wherein a probability of the random walker depends on an edge attribute of an edge which is connected to a vertex and wherein the probability of the random walker depends on a membership of vertices on both ends of the edge which is connected to the vertex, wherein the vertex belongs to a specific subset of vertices in the graph400of a plurality of subsets. Regarding the vertex-level feature, refer to the above discussion re “these other features”; similar comments apply here as well.

In one example embodiment, a graph-level feature of a graph400which is based on vertex-level features of vertices in the graph400is computed by aggregating the vertex-level features with weights, wherein each weight depends on a corresponding vertex, wherein each weight depends on a membership of vertices on both ends of an edge, and wherein a sign of each weight depends on a type of a random walk.

In one example embodiment, controlling the system includes cash flow control of a bank based on the internal flow probabilities (operation580).

In one example embodiment, controlling the system includes account-level or customer-level cash flow control of a bank based on the internal flow probabilities (operation580).

In one example embodiment, controlling the system includes detecting and mitigating financial fraud based on the internal flow probabilities (operation580)

In one example embodiment, controlling the system includes detecting and mitigating money laundering based on the internal flow probabilities (operation580).

The control can be based directly on the internal flow probabilities or on the predicted future effect from the model, rather than directly.