Skip to content
START FOR FREE
START FOR FREE
  • SUPPORT
  • COMMUNITY
Menu
  • SUPPORT
  • COMMUNITY
MENUMENU
  • Products
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      Watch a TigerGraph Demo

      TIGERGRAPH CLOUD

      • Overview
      • TigerGraph Cloud Suite
      • FAQ
      • Pricing

      USER TOOLS

      • GraphStudio
      • Insights
      • Application Workbenches
      • Connectors and Drivers
      • Starter Kits
      • openCypher Support

      TIGERGRAPH DB

      • Overview
      • GSQL Query Language
      • Compare Editions

      GRAPH DATA SCIENCE

      • Graph Data Science Library
      • Machine Learning Workbench
  • Solutions
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      Watch a TigerGraph Demo

      Solutions

      • Solutions Overview

      INCREASE REVENUE

      • Customer Journey/360
      • Product Marketing
      • Entity Resolution
      • Recommendation Engine

      MANAGE RISK

      • Fraud Detection
      • Anti-Money Laundering
      • Threat Detection
      • Risk Monitoring

      IMPROVE OPERATIONS

      • Supply Chain Analysis
      • Energy Management
      • Network Optimization

      By Industry

      • Advertising, Media & Entertainment
      • Financial Services
      • Healthcare & Life Sciences

      FOUNDATIONAL

      • AI & Machine Learning
      • Time Series Analysis
      • Geospatial Analysis
  • Customers
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      CUSTOMER SUCCESS STORIES

      • Ford
      • Intuit
      • JPMorgan Chase
      • READ MORE SUCCESS STORIES
      • Jaguar Land Rover
      • United Health Group
      • Xbox
  • Partners
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      PARTNER PROGRAM

      • Partner Benefits
      • TigerGraph Partners
      • Sign Up
      TigerGraph partners with organizations that offer complementary technology solutions and services.​
  • Resources
    • The World’s Fastest and Most Scalable Graph Platform

      LEARN MORE

      BLOG

      • TigerGraph Blog

      RESOURCES

      • Resource Library
      • Benchmarks
      • Demos
      • O'Reilly Graph + ML Book

      EVENTS & WEBINARS

      • Graph+AI Summit
      • Graph for All - Million Dollar Challenge
      • Events &Trade Shows
      • Webinars

      DEVELOPERS

      • Documentation
      • Ecosystem
      • Developers Hub
      • Community Forum

      SUPPORT

      • Contact Support
      • Production Guidelines

      EDUCATION

      • Training & Certifications
  • Company
    • Join the World’s Fastest and Most Scalable Graph Platform

      WE ARE HIRING

      COMPANY

      • Company Overview
      • Leadership
      • Legal Terms
      • Patents
      • Security and Compliance

      CAREERS

      • Join Us
      • Open Positions

      AWARDS

      • Awards and Recognition
      • Leader in Forrester Wave
      • Gartner Research

      PRESS RELEASE

      • Read All Press Releases
      TigerGraph Reports Exceptional Customer Growth and Product Leadership as More Market-Leading Companies Tap the Power of Graph
      March 1, 2023
      Read More »

      NEWS

      • Read All News
      The-New-Stack-Logo-square

      Multiple Vendors Make Data and Analytics Ubiquitous

      TigerGraph enhances fundamentals in latest platform update

  • START FREE
    • The World’s Fastest and Most Scalable Graph Platform

      GET STARTED

      • Request a Demo
      • CONTACT US
      • Try TigerGraph
      • START FREE
      • TRY AN ONLINE DEMO

Transaction Surveillance with Maximum Flow Algorithm

  • Julia Astashkina
  • February 16, 2023
  • blogs
  • Blog >
  • Transaction Surveillance with Maximum Flow Algorithm

In the banking, payment platforms, and cryptocurrency industries, graph analytic approaches such as PageRank, Label Propagation, and Cycle Detection have proven to be valuable for tracking abnormal transaction patterns, conducting anti-money laundering (AML) measures, and for transaction surveillance purposes.

Additionally, it is crucial to be able to trace the origin and destination of money transfers for effective transaction surveillance. This involves identifying abnormal transaction patterns, such as diverging from a set of accounts, transferring through mule accounts for multiple hops, and then converging into another set of accounts. Detecting these patterns enables the tracking of money transfers and tracing the source of funds for a given account.

Considering the nature of transactional networks or graphs, the transfer of money between accounts can be interpreted as the flow of a network. Maximum flow problems involve finding the highest possible flow rate through a flow network, based on its feasibility. This makes the Maximum Flow algorithm an ideal solution for answering such questions. By using this algorithm, we can determine the maximum amount of money that can be transferred from the source account to the target account. In cases where the money is split into multiple mule accounts before being converged into another account a few hops away, the account in question will have a high maximum flow number.

In this blog, we will introduce an efficient Maximum Flow implementation that can give real time performance and is able to handle massive amounts of data.

 


Edmonds-Karp

The Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network. It uses BFS to keep finding the shortest paths from the source to the sink which is called an augment path. And each time an augment path is found, at least one edge will be saturated. The algorithm keeps finding new augmented paths on the residual graph until no more augmented paths can be found. This guarantees the augment path that is found later always has an equal or longer distance than the previous one. The features of BFS traversal and monotonically increasing augment path length make the Edmonds-Karp algorithm very suitable to be implemented in the TigerGraph architecture.

A lot of very good resources explaining Edmonds-Karp can be found on the internet. For example, Edmonds Karp Algorithm,  Network Flow, and Graph Theory.

Challenges

  • Hard to be applied to pattern detection
    The original Maximum Flow algorithm is designed to take a pair of accounts as input. However, for the purpose of pattern detection, it is necessary to identify the account pairs with a high maximum flow number across the entire neighboring subgraph. Calculating the maximum flow between every pair of accounts within the k-hop neighborhood would result in a significantly high complexity.

  • High complexity for applying restrictions
    In the vast majority of real-life use cases, cycles are subject to certain restrictions, such as the maximum time gap between one transaction and the following one within each cycle, or the requirement for the subsequent transactions to have similar amounts to the previous transaction.

For each account, a restriction check must be performed with a complexity of O(dout*p), where dout represents the number of outgoing transactions, and p represents the number of paths that go through the vertex. This means that for each incoming path of an account, it must verify if every outgoing transaction can be considered as a subsequent transaction in the candidate cycle path. The number of paths going through an account is generally much larger than the number of incoming transactions, as each incoming transaction may initiate one candidate cycle path, while any upper-stream transactions of the incoming transactions can initiate a new candidate cycle path that goes through the downstream accounts.

  • High complexity to calculate shortest paths in multiple passes
    The original implementation requires the calculation of a new shortest path based on the current residual graph, which necessitates multiple scans of the k-hop residual graph.

Innovation

In this blog, we will introduce an efficient method for calculating the Edmonds-Karp maximum flow with the following features:

  • Vertex capacity-based approach where each vertex represents a transaction, and the capacity is the transaction amount
  • Scalable to handle massive amounts of data and provides real-time results
  • Calculates the maximum flow for all k-hop neighborhoods within limited number of hops

Implementation

In this session, we will begin with a basic version of the Edmonds-Karp implementation on TigerGraph. Then, we will explore how to apply it to a transactional graph and how to implement the vertex capacity variant. Finally, we will discuss the approach for calculating the maximum flow for all k-hop neighbors.

The Schema

In this blog, we will present a solution and experiments within the context of the TigerGraph implementation, which is an MPP (Massive Parallel Processing) graph analytical platform.

The graph schema visualization below displays Account and Transaction vertices. An account can either receive money via a transaction or send money via a transaction. Each transaction will have a sender and receiver, and the Trans_Trans edge, which connects transaction vertices, is a directed edge created through an optional preprocessing process.



Preprocessing (Optional)

Intuition: Establish a direct connection between transaction vertices to solve the second challenge. By connecting transaction vertices, we can follow the order of time and fulfill other restrictions. This reduces the complexity of each account from O(dout*p) to O(dout*din) since the checking of restrictions is done only once during this step. Here, din is the number of incoming transactions.

Implementation: Connecting incoming transactions of an account to outgoing transactions if they follow the order of time and have a similar amount. Once the connections are established, the following steps can traverse the Trans_Trans edges without having to perform constraint checking again.

Path Propagation

Intuition: The Edmonds-Karp algorithm evaluates the shortest augment path in every iteration, with the length of the augment paths monotonically increasing. Similarly, we start from all the outgoing transactions of the source account and propagate all paths with lengths from 1 to k to all the k-hop neighboring transactions, evaluating the paths received by the receiver accounts of the transactions.

This approach allows the algorithm to calculate the maximum flow for all k-hop neighborhoods. The path that has exhausted the capacity for one receiver account can be a valid augment path for another receiver account. Moreover, the current paths with length d can be reused for the next iteration to calculate the paths with length d+1. Thus, this approach solves the challenges #1 and #3.

Implementation: During the path propagation, in each iteration, all the possible paths with distance 1 to k are generated from all the outgoing transactions of the source account to all the k-hop neighboring transactions. The generated paths are then evaluated by the receiver accounts of the transactions.

After each iteration, the current maximum flow and capacity information stored on account vertices’ local data structures are updated based on the evaluated paths received. For each path received, if all the transactions’ remaining capacity is larger than 0, the minimum remaining amount is taken as the incremental flow amount to add to the total. Also, this value is reduced from the remaining amount of each transaction on the path.

For example, if we consider Account 1 as the source and Account 2 and 3 as sinks, in each iteration, all possible paths from Account 1 to all k-hop neighboring transactions are generated and evaluated by Account 2 and 3. After each iteration, the maximum flow and capacity information of Account 2 and 3 are updated based on the evaluated paths received.


Traverse Reversed Edge on Residual Graph

In the maximum flow algorithm, it is required to traverse in the reversed direction when calculating the residual graph. The residual graph represents the remaining flow that can be pushed from a given vertex to its adjacent vertices.

When calculating the residual graph, we subtract the current flow from the capacity of the edges that have flow in the forward direction. But we also need to consider the possibility of pushing flow in the opposite direction, which means we need to consider the capacity of the edges in the reverse direction when calculating the residual graph. Therefore, we need to traverse the graph in the reverse direction to find the edges that can potentially carry flow in the reverse direction.

Intuition: To handle the vertex capacity variant of the maximum flow calculation, each vertex is considered as two vertices connected by a directed edge. The incoming vertex represents the capacity entering the vertex, while the outgoing vertex represents the capacity leaving the vertex. The directed edge is created from the incoming vertex to the outgoing vertex to represent the capacity of the vertex.

 


 

Implementation: It is not necessary to convert the graph into format above. We will simulate the logic discussed above on the transaction vertices without creating the actual incoming and outgoing vertices for space saving and simplicity. 

When propagating the path, both directed edges and their reverse edges are traversed. When traverse the reversed edges, it is considered to be traversing the residual edge.

When evaluating the paths, for any edges in the original direction, store the incremental flow amount in a local map on the account vertexes to indicate that between a pair of transactions what is the used amount. Later when we have to traverse in an reversed order for residual graph traversal, the amount accumulated previously will be used to judge if the reversed/residual edge has sufficient flow.

Here is an example:

If we previously traversed path A->C->E, and got minimum flow of 200. 


 

The residual amount on E->C and C->A also become 200. 


 

Later if we traverse the path of C->A->D, since C->A is in reversed order therefore the residual amount will be used. The flow we get from path C->A->D is 100. Note, even A’s amount is used up, but because the residual path doesn’t go through the edge between Incoming A and Outgoing A, therefore it is still a valid path.


 

Below is the value after reducing 100 from the residual edge and incremented the original transaction capacity amount of C.



Conclusion

In conclusion, Maximum Flow algorithms are being used to determine the highest possible flow rate through a flow network, based on its feasibility, making it an ideal solution for transaction surveillance. However, the original Maximum Flow algorithm is designed to take a pair of accounts as input, and applying it to pattern detection poses several challenges, including high complexity for applying restrictions, calculating shortest paths in multiple passes, and identifying account pairs with high maximum flow numbers across the entire neighboring subgraph. Nevertheless, this blog proposes an innovative and efficient approach to calculate the maximum flow with a vertex capacity-based approach, scalable to handle massive amounts of data, providing real-time results, and calculating the maximum flow for all k-hop neighborhoods within a limited number of hops.

You Might Also Like

Trillion edges benchmark: new world record beyond 100TB by TigerGraph featuring AMD based Amazon EC2 instances

Trillion edges benchmark: new world record...

March 13, 2023
Turbocharge your business intelligence with TigerGraph’s ML Workbench on TigerGraph Cloud

Turbocharge your business intelligence with TigerGraph’s...

November 14, 2022
Developer Spotlight: Kapil Saini

Developer Spotlight: Kapil Saini

October 21, 2022

Introducing TigerGraph 3.0

July 1, 2020

Everything to Know to Pass your TigerGraph Certification Test

June 24, 2020

Neo4j 4.0 Fabric – A Look Behind the Curtain

February 7, 2020

TigerGraph Blog

  • Categories
    • blogs
      • About TigerGraph
      • Benchmark
      • Business
      • Community
      • Compliance
      • Customer
      • Customer 360
      • Cybersecurity
      • Developers
      • Digital Twin
      • eCommerce
      • Emerging Use Cases
      • Entity Resolution
      • Finance
      • Fraud / Anti-Money Laundering
      • GQL
      • Graph Database Market
      • Graph Databases
      • GSQL
      • Healthcare
      • Machine Learning / AI
      • Podcast
      • Supply Chain
      • TigerGraph
      • TigerGraph Cloud
    • Graph AI On Demand
      • Analysts and Research
      • Customer 360 and Entity Resolution
      • Customer Spotlight
      • Development
      • Finance, Banking, Insurance
      • Keynote
      • Session
    • Video
  • Recent Posts

    • Trillion edges benchmark: new world record beyond 100TB by TigerGraph featuring AMD based Amazon EC2 instances
    • Overview of Graph and Machine Learning with TigerGraph | Mar 8 @ 11am PST
    • Gartner Data & Analytics Summit 2023, London
    • Gartner Data and Analytics Summit, Orlando
    • Transaction Surveillance with Maximum Flow Algorithm
    TigerGraph

    Product

    SOLUTIONS

    customers

    RESOURCES

    start for free

    TIGERGRAPH DB
    • Overview
    • Features
    • GSQL Query Language
    GRAPH DATA SCIENCE
    • Graph Data Science Library
    • Machine Learning Workbench
    TIGERGRAPH CLOUD
    • Overview
    • Cloud Starter Kits
    • Login
    • FAQ
    • Pricing
    • Cloud Marketplaces
    USEr TOOLS
    • GraphStudio
    • TigerGraph Insights
    • Application Workbenches
    • Connectors and Drivers
    • Starter Kits
    • openCypher Support
    SOLUTIONS
    • Why Graph?
    industry
    • Advertising, Media & Entertainment
    • Financial Services
    • Healthcare & Life Sciences
    use cases
    • Benefits
    • Product & Service Marketing
    • Entity Resolution
    • Customer 360/MDM
    • Recommendation Engine
    • Anti-Money Laundering
    • Cybersecurity Threat Detection
    • Fraud Detection
    • Risk Assessment & Monitoring
    • Energy Management
    • Network & IT Management
    • Supply Chain Analysis
    • AI & Machine Learning
    • Geospatial Analysis
    • Time Series Analysis
    success stories
    • Customer Success Stories

    Partners

    Partner program
    • Partner Benefits
    • TigerGraph Partners
    • Sign Up
    LIBRARY
    • Resources
    • Benchmark
    • Webinars
    Events
    • Trade Shows
    • Graph + AI Summit
    • Million Dollar Challenge
    EDUCATION
    • Training & Certifications
    Blog
    • TigerGraph Blog
    DEVELOPERS
    • Developers Hub
    • Community Forum
    • Documentation
    • Ecosystem

    COMPANY

    Company
    • Overview
    • Careers
    • News
    • Press Release
    • Awards
    • Legal
    • Patents
    • Security and Compliance
    • Contact
    Get Started
    • Start Free
    • Compare Editions
    • Online Demo - Test Drive
    • Request a Demo

    Product

    • Overview
    • TigerGraph 3.0
    • TIGERGRAPH DB
    • TIGERGRAPH CLOUD
    • GRAPHSTUDIO
    • TRY NOW

    customers

    • success stories

    RESOURCES

    • LIBRARY
    • Events
    • EDUCATION
    • BLOG
    • DEVELOPERS

    SOLUTIONS

    • SOLUTIONS
    • use cases
    • industry

    Partners

    • partner program

    company

    • Overview
    • news
    • Press Release
    • Awards

    start for free

    • Request Demo
    • take a test drive
    • SUPPORT
    • COMMUNITY
    • CONTACT
    • Copyright © 2023 TigerGraph
    • Privacy Policy
    • Linkedin
    • Facebook
    • Twitter

    Copyright © 2020 TigerGraph | Privacy Policy

    Copyright © 2020 TigerGraph Privacy Policy

    • SUPPORT
    • COMMUNITY
    • COMPANY
    • CONTACT
    • Linkedin
    • Facebook
    • Twitter

    Copyright © 2020 TigerGraph

    Privacy Policy

    • Products
    • Solutions
    • Customers
    • Partners
    • Resources
    • Company
    • START FREE
    START FOR FREE
    START FOR FREE
    TigerGraph
    PRODUCT
    PRODUCT
    • Overview
    • GraphStudio UI
    • Graph Data Science Library
    TIGERGRAPH DB
    • Overview
    • Features
    • GSQL Query Language
    TIGERGRAPH CLOUD
    • Overview
    • Cloud Starter Kits
    TRY TIGERGRAPH
    • Get Started for Free
    • Compare Editions
    SOLUTIONS
    SOLUTIONS
    • Why Graph?
    use cases
    • Benefits
    • Product & Service Marketing
    • Entity Resolution
    • Customer Journey/360
    • Recommendation Engine
    • Anti-Money Laundering (AML)
    • Cybersecurity Threat Detection
    • Fraud Detection
    • Risk Assessment & Monitoring
    • Energy Management
    • Network Resources Optimization
    • Supply Chain Analysis
    • AI & Machine Learning
    • Geospatial Analysis
    • Time Series Analysis
    industry
    • Advertising, Media & Entertainment
    • Financial Services
    • Healthcare & Life Sciences
    CUSTOMERS
    read all success stories

     

    PARTNERS
    Partner program
    • Partner Benefits
    • TigerGraph Partners
    • Sign Up
    RESOURCES
    LIBRARY
    • Resource Library
    • Benchmark
    • Webinars
    Events
    • Trade Shows
    • Graph + AI Summit
    • Graph for All - Million Dollar Challenge
    EDUCATION
    • TigerGraph Academy
    • Certification
    Blog
    • TigerGraph Blog
    DEVELOPERS
    • Developers Hub
    • Community Forum
    • Documentation
    • Ecosystem
    COMPANY
    COMPANY
    • Overview
    • Leadership
    • Careers  
    NEWS
    PRESS RELEASE
    AWARDS
    START FREE
    Start Free
    • Request a Demo
    • SUPPORT
    • COMMUNITY
    • CONTACT
    Dr. Jay Yu

    Dr. Jay Yu | VP of Product and Innovation

    Dr. Jay Yu is the VP of Product and Innovation at TigerGraph, responsible for driving product strategy and roadmap, as well as fostering innovation in graph database engine and graph solutions. He is a proven hands-on full-stack innovator, strategic thinker, leader, and evangelist for new technology and product, with 25+ years of industry experience ranging from highly scalable distributed database engine company (Teradata), B2B e-commerce services startup, to consumer-facing financial applications company (Intuit). He received his PhD from the University of Wisconsin - Madison, where he specialized in large scale parallel database systems

    Todd Blaschka | COO

    Todd Blaschka is a veteran in the enterprise software industry. He is passionate about creating entirely new segments in data, analytics and AI, with the distinction of establishing graph analytics as a Gartner Top 10 Data & Analytics trend two years in a row. By fervently focusing on critical industry and customer challenges, the companies under Todd's leadership have delivered significant quantifiable results to the largest brands in the world through channel and solution sales approach. Prior to TigerGraph, Todd led go to market and customer experience functions at Clustrix (acquired by MariaDB), Dataguise and IBM.