RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage

Arbitrage is a challenging data science problem characterized by rapidly fluctuating price discrepancies across multiple markets, necessitating real-time solutions. To overcome the challenge, we model it as a k -hop negative cycle detection problem in graphs and introduce RICH: Real-time Identification of negative Cycles for High-efficiency arbitrage. RICH is a novel framework that leverages color-coding and dynamic programming to accelerate the identification of negative-weight cycles without exhaustive graph traversal. Additionally, RICH incorporates encoding techniques and graph reduction to minimize computational overhead while maintaining probabilistic guarantees. Our extensive experiments on real-world datasets demonstrate that RICH is up to 32.69× faster than state-of-the-art methods, enabling timely arbitrage execution while outperforming existing methods in both speed and accuracy. We further validate its effectiveness in identifying arbitrage opportunities in cryptocurrency markets and foreign exchange markets.