Oryx: Private detection of cycles in federated graphs
Authors: Ke Zhong (University of Pennsylvania), Sebastian Angel (University of Pennsylvania)
Volume: 2025
Issue: 2
Pages: 527–542
DOI: https://doi.org/10.56553/popets-2025-0075
Abstract: This paper proposes Oryx, a system for efficiently detecting cycles in federated graphs where parts of the graph are held by different parties and are private. Cycle identification is an important building block in designing fraud detection algorithms that operate on confidential transaction data held by different financial institutions. Oryx allows detecting cycles of various length while keeping the topology of the graphs secret, and it does so efficiently. Oryx leverages the observation that financial graphs are very sparse, and uses this to achieve computational complexity that scales with the average degree of nodes in the graph rather than the maximum degree. Our implementation of Oryx running on a single 32-core AWS machine (for each party) can detect all cycles of up to length 6 in under 5 hours in a financial transaction graph that consists of tens of millions of nodes and edges. While the costs are high, Oryx's protocol parallelizes well and can use additional hardware resources. Furthermore, Oryx is, to our knowledge, the first system that can handle this task for large graphs.
Keywords: Multi-party computation, Private graph cycle detection
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
