Federated Graph Analytics with Privacy: The Case of Parallel Chain Detection

Federated graph analytics has emerged as a vital paradigm for extracting insights from a large graph distributed across different data holders, where each data holder owns only a local subgraph. This paradigm is particularly vital in the financial sector, where transaction data of different institutions collectively form a global graph. Detecting structural patterns in a large federated transaction graph is highly valuable, greatly facilitating cross-institution anti-money laundering to combat illicit financial activities. Among others, the parallel chain pattern has been proven highly effective in uncovering sophisticated money-laundering behaviors. Detecting such a pattern in the federated setting is thus crucial. However, this is quite challenging since each data holder could be reluctant to directly share its local subgraph due to stringent privacy regulations and severe privacy concerns. This paper introduces OblivPCD, the first system framework supporting oblivious parallel chain detection in a federated graph setting. At the core of OblivPCD is a delicate synergy of insights on graph modeling and cryptographic computation. We implement OblivPCD and evaluate it on graph datasets containing tens of millions of vertices and edges. Experimental results show that OblivPCD greatly outperforms the state-of-the-art prior work in oblivious path extension. In particular, OblivPCD achieves up to a 33.5% reduction in runtime and cuts communication cost by up to 93.7%.