Welcome Back to Arbitrage Basics

In our previous post on triangular arbitrage, we explored the fundamentals of 3-pair arbitrage opportunities. Today, we’re taking a significant leap forward by applying graph theory to discover arbitrage opportunities across any number of trading pairs. This approach transforms arbitrage detection from manual triangle checking into a systematic algorithmic problem.

By modeling trading pairs as a weighted directed graph, we can use classical algorithms like Bellman-Ford to detect negative cycles - mathematical representations of profitable arbitrage loops.

Why Graph Theory for Arbitrage?

Traditional triangular arbitrage only checks predefined 3-token paths. But what if profitable opportunities exist across 4, 5, or even 10 different tokens? Manual enumeration becomes computationally expensive and misses complex paths.

Graph theory solves this elegantly:

  • Vertices represent tokens (ETH, USDC, DAI, etc.)
  • Edges represent trading pairs with weights as negative log exchange rates
  • Negative cycles indicate arbitrage opportunities
  • Shortest path algorithms find optimal trading sequences

Mathematical Foundation

The key insight is transforming multiplicative arbitrage into additive shortest path problems using logarithms.

Exchange Rate Transformation

For an exchange rate r from token A to token B:

weight(A→B) = -log(r)

Why negative logarithm?

  • Multiplying exchange rates → Adding logarithms
  • Finding maximum profit → Finding minimum path weight
  • Profitable cycles → Negative weight cycles

Example Transformation

Consider these exchange rates:

  • ETH → USDC: 3000 (1 ETH = 3000 USDC)
  • USDC → DAI: 1.01 (1 USDC = 1.01 DAI)
  • DAI → ETH: 0.000334 (1 DAI = 0.000334 ETH)

Graph weights become:

  • ETH → USDC: -log(3000) ≈ -8.006
  • USDC → DAI: -log(1.01) ≈ -0.00995
  • DAI → ETH: -log(0.000334) ≈ 8.003

Cycle weight: -8.006 + (-0.00995) + 8.003 = -0.01295 (negative = profitable!)

The Bellman-Ford Algorithm

Bellman-Ford detects negative cycles by relaxing all edges repeatedly. If distances continue decreasing after |V|-1 iterations, a negative cycle exists.

How Bellman-Ford Works

The algorithm operates on a simple principle: if a graph contains no negative cycles, then the shortest path between any two vertices contains at most |V|-1 edges (where |V| is the number of vertices). This is because the shortest path can visit each vertex at most once.

Detailed Algorithm Steps

1. Initialize Distances

Set the distance to the source vertex as 0, and all other vertices as infinity. This represents that we can reach the source with zero cost, but don’t yet know how to reach other vertices.

// Example initialization for vertices [ETH, USDC, DAI]
const distances = {
    ETH: 0,        // Starting point
    USDC: Infinity, // Unknown distance
    DAI: Infinity   // Unknown distance
}

2. Edge Relaxation Process

For exactly |V|-1 iterations, examine every edge and update distances if a shorter path is found. Relaxation means: “Can I get to vertex B cheaper by going through vertex A?”

// Relaxation check for edge A → B with weight w
if (distance[A] + weight(A,B) < distance[B]) {
    distance[B] = distance[A] + weight(A,B);
    predecessor[B] = A;  // Remember how we got here
}

Why |V|-1 iterations? In a graph with no negative cycles, the longest possible shortest path visits each vertex exactly once. With V vertices, this path can have at most V-1 edges.

3. Negative Cycle Detection

After |V|-1 iterations, try relaxation one more time. If any distance can still be improved, a negative cycle exists.

// After |V|-1 iterations, this should never be true in a normal graph
if (distance[A] + weight(A,B) < distance[B]) {
    // Negative cycle detected!
    console.log("Arbitrage opportunity found!");
}

Step-by-Step Example

Let’s trace through a simple 3-token example:

Tokens: ETH, USDC, DAI
Exchange rates:

  • ETH → USDC: 3000 (weight: -8.006)
  • USDC → DAI: 1.01 (weight: -0.00995)
  • DAI → ETH: 0.000334 (weight: 8.003)

Iteration 0 (Initialize):

distances: { ETH: 0, USDC: ∞, DAI: ∞ }

Iteration 1:

  • Check ETH → USDC: 0 + (-8.006) = -8.006 < ∞ ✓
  • Check USDC → DAI: ∞ + (-0.00995) = ∞ (no update)
  • Check DAI → ETH: ∞ + 8.003 = ∞ (no update)
distances: { ETH: 0, USDC: -8.006, DAI: ∞ }

Iteration 2:

  • Check ETH → USDC: 0 + (-8.006) = -8.006 (no change)
  • Check USDC → DAI: -8.006 + (-0.00995) = -8.016 < ∞ ✓
  • Check DAI → ETH: ∞ + 8.003 = ∞ (no update)
distances: { ETH: 0, USDC: -8.006, DAI: -8.016 }

Iteration 3 (V-1 = 2, so this is our detection phase):

  • Check ETH → USDC: 0 + (-8.006) = -8.006 (no change)
  • Check USDC → DAI: -8.006 + (-0.00995) = -8.016 (no change)
  • Check DAI → ETH: -8.016 + 8.003 = -0.013 < 0 ✓ NEGATIVE CYCLE DETECTED!

The fact that we can still improve the distance to ETH (from 0 to -0.013) after |V|-1 iterations proves a negative cycle exists.

Understanding Negative Cycle Detection

The key insight is that negative cycles break the fundamental assumption of shortest paths. In a normal graph, once you’ve found the shortest path to a vertex, you can’t make it any shorter. But negative cycles create a paradox: you can keep going around the cycle to make paths arbitrarily short (or profitable).

Why This Means Arbitrage

In our context:

  • Negative cycle weight = Profitable trading loop
  • Cycle weight of -0.013 means we can multiply our starting amount by e^0.013 ≈ 1.013 (1.3% profit)
  • Starting with 1 ETH → Ending with 1.013 ETH after completing the cycle

Tracing the Profitable Path

Once we detect a negative cycle, we need to reconstruct the actual trading sequence:

function traceCycle(predecessor, start) {
    const visited = new Set();
    const path = [];
    let current = start;
    
    // Walk back to find cycle start
    // This is crucial: we need to find where the cycle actually begins
    for (let i = 0; i < vertices.size; i++) {
        current = predecessor.get(current);
        if (!current) return []; // No cycle found
    }
    
    // Now we're guaranteed to be in the cycle
    const cycleStart = current;
    do {
        if (visited.has(current)) break;
        visited.add(current);
        path.push(current);
        current = predecessor.get(current);
    } while (current !== cycleStart && path.length < vertices.size);
    
    path.push(cycleStart); // Complete the cycle
    return path.reverse();
}

Multiple Cycles and Optimization

In real markets, you might find multiple negative cycles:

// Example output from findArbitrageOpportunities()
Found 3 arbitrage opportunities:

1. Profit: 2.1500% 
   Path: ETH → USDC → LINK → ETH
   ETH → USDC: 3000.000000
   USDC → LINK: 0.071500
   LINK → ETH: 0.000467

2. Profit: 1.3400%
   Path: USDC → DAI → USDT → USDC  
   USDC → DAI: 1.008000
   DAI → USDT: 0.999200
   USDT → USDC: 1.005100

3. Profit: 0.8900%
   Path: ETH → DAI → USDT → LINK → ETH
   ETH → DAI: 3024.000000
   DAI → USDT: 0.999200  
   USDT → LINK: 0.000071
   LINK → ETH: 0.000467

The algorithm automatically finds the most profitable cycles first due to our sorting by profit percentage.

Visual Algorithm Walkthrough

Here’s how the algorithm progresses through our example graph:

Initial Graph:
    ETH ──(-8.006)──> USDC
     ∧                  │
     │                  │(-0.00995)
(8.003)                 ∨
     │                 DAI
     └─────────────────────

Iteration 1 - Relaxation Phase:
    ETH[0] ──(-8.006)──> USDC[-8.006] ✓ UPDATED
     ∧                      │
     │                      │(-0.00995)  
(8.003)                     ∨
     │                    DAI[∞]
     └───────────────────────

Iteration 2 - Relaxation Phase:  
    ETH[0] ──(-8.006)──> USDC[-8.006]
     ∧                      │
     │                      │(-0.00995)
(8.003)                     ∨
     │                    DAI[-8.016] ✓ UPDATED
     └───────────────────────

Iteration 3 - Detection Phase:
    ETH[-0.013] ✓ CYCLE! <──(-8.006)──── USDC[-8.006]
     ∧                                      │
     │                                      │(-0.00995)
(8.003)                                     ∨
     │                                    DAI[-8.016]
     └───────────────────────────────────────

Profit Calculation:
Total cycle weight: -8.006 + (-0.00995) + 8.003 = -0.01295
Profit multiplier: e^(0.01295) = 1.013 = 1.3% profit

This visual shows how distances propagate through the graph and how the algorithm detects when a cycle allows infinite improvement (negative cycle = arbitrage opportunity).

Implementation

Let’s implement a comprehensive graph-based arbitrage detector:

import { ethers } from 'ethers';
import dotenv from 'dotenv';
dotenv.config();

const provider = new ethers.JsonRpcProvider(process.env.RPC_URL);

// Graph state
let vertices = new Set();
let edges = new Map();
let tokenAddresses = new Map();
let addressToToken = new Map();

function addToken(symbol, address) {
    vertices.add(symbol);
    tokenAddresses.set(symbol, address);
    addressToToken.set(address.toLowerCase(), symbol);
    edges.set(symbol, new Map());
}

async function addPair(tokenA, tokenB) {
    try {
        const reserves = await getReserves(
            tokenAddresses.get(tokenA),
            tokenAddresses.get(tokenB)
        );
        
        // Calculate exchange rates
        const rateAtoB = Number(reserves.reserveB) / Number(reserves.reserveA);
        const rateBtoA = Number(reserves.reserveA) / Number(reserves.reserveB);
        
        // Add edges with negative log weights
        edges.get(tokenA).set(tokenB, {
            weight: -Math.log(rateAtoB),
            rate: rateAtoB,
            reserves: reserves
        });
        
        edges.get(tokenB).set(tokenA, {
            weight: -Math.log(rateBtoA),
            rate: rateBtoA,
            reserves: { reserveA: reserves.reserveB, reserveB: reserves.reserveA }
        });
        
    } catch (error) {
        console.error(`Failed to add pair ${tokenA}/${tokenB}:`, error.message);
    }
}

async function getReserves(tokenA, tokenB) {
    const factoryABI = [
        'function getPair(address tokenA, address tokenB) external view returns (address pair)'
    ];
    
    const pairABI = [
        'function getReserves() external view returns (uint112 reserve0, uint112 reserve1, uint32 blockTimestampLast)',
        'function token0() external view returns (address)',
        'function token1() external view returns (address)'
    ];
    
    const factory = new ethers.Contract(
        '0x5C69bEe701ef814a2B6a3EDD4B1652CB9cc5aA6f',
        factoryABI,
        provider
    );
    
    const pairAddress = await factory.getPair(tokenA, tokenB);
    
    if (pairAddress === ethers.ZeroAddress) {
        throw new Error(`No pair exists for ${tokenA}/${tokenB}`);
    }
    
    const pair = new ethers.Contract(pairAddress, pairABI, provider);
    const [reserve0, reserve1] = await pair.getReserves();
    const token0 = await pair.token0();
    
    if (token0.toLowerCase() === tokenA.toLowerCase()) {
        return { reserveA: reserve0, reserveB: reserve1 };
    } else {
        return { reserveA: reserve1, reserveB: reserve0 };
    }
}

function bellmanFord(source) {
    const distance = new Map();
    const predecessor = new Map();
    
    // Initialize distances
    for (const vertex of vertices) {
        distance.set(vertex, vertex === source ? 0 : Infinity);
        predecessor.set(vertex, null);
    }
    
    // Relax edges |V|-1 times
    for (let i = 0; i < vertices.size - 1; i++) {
        for (const u of vertices) {
            if (distance.get(u) === Infinity) continue;
            
            for (const [v, edge] of edges.get(u)) {
                const newDist = distance.get(u) + edge.weight;
                if (newDist < distance.get(v)) {
                    distance.set(v, newDist);
                    predecessor.set(v, u);
                }
            }
        }
    }
    
    // Check for negative cycles
    const negativeCycles = [];
    const inCycle = new Set();
    
    for (const u of vertices) {
        if (distance.get(u) === Infinity) continue;
        
        for (const [v, edge] of edges.get(u)) {
            const newDist = distance.get(u) + edge.weight;
            if (newDist < distance.get(v) && !inCycle.has(v)) {
                // Negative cycle detected, trace it
                const cycle = traceCycle(predecessor, v);
                if (cycle.length > 0) {
                    negativeCycles.push(cycle);
                    cycle.forEach(node => inCycle.add(node));
                }
            }
        }
    }
    
    return {
        distances: distance,
        predecessors: predecessor,
        negativeCycles: negativeCycles
    };
}

function traceCycle(predecessor, start) {
    const visited = new Set();
    const path = [];
    let current = start;
    
    // Walk back to find cycle start
    for (let i = 0; i < vertices.size; i++) {
        current = predecessor.get(current);
        if (!current) return [];
    }
    
    // Trace the actual cycle
    const cycleStart = current;
    do {
        if (visited.has(current)) break;
        visited.add(current);
        path.push(current);
        current = predecessor.get(current);
    } while (current !== cycleStart && path.length < vertices.size);
    
    path.push(cycleStart); // Complete the cycle
    return path.reverse();
}

function calculateCycleProfit(cycle) {
    let totalWeight = 0;
    let path = [];
    
    for (let i = 0; i < cycle.length - 1; i++) {
        const from = cycle[i];
        const to = cycle[i + 1];
        const edge = edges.get(from).get(to);
        
        if (!edge) {
            console.error(`No edge found from ${from} to ${to}`);
            return null;
        }
        
        totalWeight += edge.weight;
        path.push({ from, to, rate: edge.rate, weight: edge.weight });
    }
    
    // Convert back from log space
    const profitMultiplier = Math.exp(-totalWeight);
    const profitPercentage = (profitMultiplier - 1) * 100;
    
    return {
        cycle: cycle,
        path: path,
        totalWeight: totalWeight,
        profitMultiplier: profitMultiplier,
        profitPercentage: profitPercentage,
        profitable: profitMultiplier > 1.01 // Account for fees
    };
}

async function findArbitrageOpportunities() {
    const opportunities = [];
    
    for (const source of vertices) {
        const result = bellmanFord(source);
        
        for (const cycle of result.negativeCycles) {
            const profit = calculateCycleProfit(cycle);
            if (profit && profit.profitable) {
                opportunities.push(profit);
            }
        }
    }
    
    // Sort by profit percentage descending
    return opportunities.sort((a, b) => b.profitPercentage - a.profitPercentage);
}

Advanced Optimizations

1. SPFA (Shortest Path Faster Algorithm)

SPFA optimizes Bellman-Ford by only processing vertices whose distances changed:

function spfa(source) {
    const distance = new Map();
    const predecessor = new Map();
    const inQueue = new Map();
    const queue = [];
    
    // Initialize
    for (const vertex of vertices) {
        distance.set(vertex, vertex === source ? 0 : Infinity);
        predecessor.set(vertex, null);
        inQueue.set(vertex, false);
    }
    
    queue.push(source);
    inQueue.set(source, true);
    
    while (queue.length > 0) {
        const u = queue.shift();
        inQueue.set(u, false);
        
        for (const [v, edge] of edges.get(u)) {
            const newDist = distance.get(u) + edge.weight;
            if (newDist < distance.get(v)) {
                distance.set(v, newDist);
                predecessor.set(v, u);
                
                if (!inQueue.get(v)) {
                    queue.push(v);
                    inQueue.set(v, true);
                }
            }
        }
    }
    
    return { distances: distance, predecessors: predecessor };
}

2. Dynamic Graph Updates

Instead of rebuilding the entire graph, update only changed pairs:

async updatePair(tokenA, tokenB) {
    const reserves = await this.getReserves(
        this.tokenAddresses.get(tokenA),
        this.tokenAddresses.get(tokenB)
    );
    
    const rateAtoB = Number(reserves.reserveB) / Number(reserves.reserveA);
    const rateBtoA = Number(reserves.reserveA) / Number(reserves.reserveB);
    
    // Update edges
    this.edges.get(tokenA).set(tokenB, {
        weight: -Math.log(rateAtoB),
        rate: rateAtoB,
        reserves: reserves,
        lastUpdate: Date.now()
    });
    
    this.edges.get(tokenB).set(tokenA, {
        weight: -Math.log(rateBtoA),
        rate: rateBtoA,
        reserves: { reserveA: reserves.reserveB, reserveB: reserves.reserveA },
        lastUpdate: Date.now()
    });
}

Usage Example

async function main() {
    // Add tokens
    const tokens = {
        WETH: '0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2',
        USDC: '0xA0b86a33E6417c7C4c7d2fD426c8bC3F1a44B9aF',
        DAI: '0x6B175474E89094C44Da98b954EedeAC495271d0F',
        USDT: '0xdAC17F958D2ee523a2206206994597C13D831ec7',
        LINK: '0x514910771AF9Ca656af840dff83E8264EcF986CA'
    };
    
    for (const [symbol, address] of Object.entries(tokens)) {
        addToken(symbol, address);
    }
    
    // Add all possible pairs
    const tokenSymbols = Object.keys(tokens);
    for (let i = 0; i < tokenSymbols.length; i++) {
        for (let j = i + 1; j < tokenSymbols.length; j++) {
            await addPair(tokenSymbols[i], tokenSymbols[j]);
        }
    }
    
    // Find opportunities
    const opportunities = await findArbitrageOpportunities();
    
    console.log(`Found ${opportunities.length} arbitrage opportunities:`);
    opportunities.forEach((opp, index) => {
        console.log(`\n${index + 1}. Profit: ${opp.profitPercentage.toFixed(4)}%`);
        console.log(`   Path: ${opp.cycle.join(' → ')}`);
        opp.path.forEach(step => {
            console.log(`   ${step.from} → ${step.to}: ${step.rate.toFixed(6)}`);
        });
    });
}

main().catch(console.error);

Gas Optimization Considerations

Multi-pair arbitrage requires careful gas management:

1. Batch Transactions

Instead of sequential swaps, use multicall patterns:

async function executeBatchArbitrage(opportunity) {
    const calls = opportunity.path.map(step => ({
        target: routerAddress,
        callData: router.interface.encodeFunctionData('swapExactTokensForTokens', [
            step.amountIn,
            step.amountOutMin,
            [step.from, step.to],
            wallet.address,
            deadline
        ])
    }));
    
    const multicall = new ethers.Contract(multicallAddress, multicallABI, wallet);
    const tx = await multicall.aggregate(calls, { gasLimit: 800000 });
    await tx.wait();
}

Risk Management

1. Slippage Protection

Calculate minimum outputs accounting for slippage:

calculateMinOutputs(path, slippageTolerance = 0.05) {
    return path.map(step => {
        const expectedOutput = step.expectedAmount;
        return expectedOutput * BigInt(Math.floor((1 - slippageTolerance) * 1000)) / 1000n;
    });
}

2. MEV Protection

Implement private mempool submission or use services like Flashbots:

async function submitPrivateTransaction(tx) {
    const flashbotsRelay = 'https://relay.flashbots.net';
    const bundle = [{ signedTransaction: tx }];
    
    const response = await fetch(flashbotsRelay, {
        method: 'POST',
        headers: { 'Content-Type': 'application/json' },
        body: JSON.stringify({
            method: 'eth_sendBundle',
            params: [bundle, await provider.getBlockNumber() + 1]
        })
    });
    
    return response.json();
}

Performance Benchmarks

Graph-based arbitrage detection scales significantly better than manual enumeration:

  • 3 tokens: 1 triangle vs 1 cycle detection
  • 5 tokens: 10 triangles vs 1 graph scan
  • 10 tokens: 120 triangles vs 1 graph scan
  • 20 tokens: 1140 triangles vs 1 graph scan

Time complexity: O(V³) triangular enumeration vs O(VE) Bellman-Ford

Conclusion

Graph theory transforms arbitrage detection from a manual process into a systematic algorithmic approach. By modeling trading pairs as weighted graphs and using algorithms like Bellman-Ford, we can:

  • Discover complex multi-pair arbitrage opportunities
  • Scale to any number of tokens efficiently
  • Optimize for maximum profit paths
  • Handle dynamic market conditions

The mathematical foundation provides robustness, while implementation optimizations ensure competitive performance in the fast-moving DeFi landscape.

Next Steps: Consider exploring cycle enumeration algorithms (Johnson’s algorithm), parallel processing for real-time detection, and integration with DEX aggregators for cross-protocol arbitrage.

Important: Always test on testnets first, implement proper risk management, and consider gas costs in profitability calculations. The complexity of multi-pair arbitrage increases both potential profits and potential risks.