POPPY: Scalable and Secure Spectral Centrality for Distributed Graphs via Homomorphic Encryption

Claire Guichemerre (Paper author · Université de Rennes, CNRS, IRISA), Tristan Allard (Paper author · Université de Rennes, CNRS, IRISA), Sofiane Azogagh (Paper author · Université du Québec à Montréal), Marc-Olivier Killijian (Paper author · Université du Québec à Montréal), Sébastien Gambs (Paper author · Université du Québec à Montréal), Amr El Abbadi (Paper author · University of California, Santa Barbara)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Beaver

Overview

In an era dominated by vast, interconnected datasets, graphs have emerged as a fundamental structure for representing complex relationships, from financial transactions to social networks. Many of these graphs, however, contain sensitive personal data and are inherently distributed across multiple data centers, often due to legal, contractual, or reputational constraints. This talk, presented by Claire Guichemerre, introduces Poppy, a novel framework designed to enable the secure and scalable computation of spectral centrality measures on these distributed graphs, leveraging the power of Fully Homomorphic Encryption (FHE).

Watch on YouTube · Slides

Visual summary for POPPY: Scalable and Secure Spectral Centrality for Distributed Graphs via Homomorphic Encryption by Claire Guichemerre, Tristan Allard, Sofiane Azogagh, Marc-Olivier Killijian, Sébastien Gambs, Amr El Abbadi
Visual summary for POPPY: Scalable and Secure Spectral Centrality for Distributed Graphs via Homomorphic Encryption by Claire Guichemerre, Tristan Allard, Sofiane Azogagh, Marc-Olivier Killijian, Sébastien Gambs, Amr El Abbadi

Key moments

  1. 0:30 Privacy challenge for distributed graph analysis
  2. 2:00 CKKS homomorphic encryption scheme capabilities
  3. 5:00 Three PoPy algorithms for diverse graph types
  4. 6:00 Novel "ink equivalence" for pruning graph nodes
  5. 7:00 PoPy's accuracy and Pink's performance compared to NoTi
  6. 7:50 Scalability of PoPy with FHE overhead
  7. 8:30 Conclusion and open-source implementation details

POPPY: Scalable and Secure Spectral Centrality for Distributed Graphs via Homomorphic Encryption

Speakers: Claire Guichemerre (Paper author, Université de Rennes, CNRS, IRISA); Tristan Allard (Paper author, Université de Rennes, CNRS, IRISA); Sofiane Azogagh (Paper author, Université du Québec à Montréal); Marc-Olivier Killijian (Paper author, Université du Québec à Montréal); Sébastien Gambs (Paper author, Université du Québec à Montréal); Amr El Abbadi (Paper author, University of California, Santa Barbara)

Conference: PETS

YouTube: https://www.youtube.com/watch?v=WDno4wesBBQ

Overview

In an era dominated by vast, interconnected datasets, graphs have emerged as a fundamental structure for representing complex relationships, from financial transactions to social networks. Many of these graphs, however, contain sensitive personal data and are inherently distributed across multiple data centers, often due to legal, contractual, or reputational constraints. This talk, presented by Claire Guichemerre, introduces Poppy, a novel framework designed to enable the secure and scalable computation of spectral centrality measures on these distributed graphs, leveraging the power of Fully Homomorphic Encryption (FHE).

The core challenge addressed by Poppy is the ability to identify influential nodes—critical for tasks like financial fraud detection—without centralizing the graph data, which could violate stringent privacy regulations such as GDPR. Traditional approaches either compromise privacy or fail to scale effectively. Poppy stands out as the first solution to simultaneously satisfy the requirements of generality (supporting various spectral centrality measures), accuracy (producing results comparable to non-private methods), and scalability (handling large, distributed graphs).

This research, a collaborative effort between Université de Rennes, Université du Québec à Montréal, and University of California, Santa Barbara, provides a robust answer to the growing demand for privacy-preserving analytics on sensitive, distributed datasets. By allowing computations directly on encrypted data, Poppy offers a paradigm shift for organizations needing to extract valuable insights from graph structures while rigorously upholding data confidentiality.

Background

▶ Watch: Privacy challenge for distributed graph analysis (0:30)

The proliferation of large graph datasets is a defining characteristic of modern data analytics. These graphs often represent critical interactions, such as financial transactions between bank accounts or user activities across web pages, and are intrinsically rich in personal data. Consequently, they are frequently partitioned and stored across multiple data centers, driven by a confluence of legal mandates, contractual obligations, and reputational concerns. The speaker highlighted a significant example: the 1.2 billion euro fine imposed on Meta in 2023 for transferring European user data to the USA, underscoring the severe penalties for non-compliance with data localization and privacy regulations.

The objective is to identify influential nodes within these graphs, which is crucial for applications like detecting financial fraud or understanding network dynamics. A widely adopted method for this is spectral centrality measure, exemplified by algorithms like PageRank or HITS/SALSA. These measures assign a score to each node, quantifying its importance based on its structural position within the graph. They are characterized by their reliance on the graph's adjacency matrix, involving iterative linear algebra operations (additions and multiplications). PageRank, for instance, focuses on incoming edges, while HITS and SALSA consider both incoming and outgoing edges. A critical aspect for distributed contexts is the mandatory normalization of these centrality scores, which is essential for understanding the relative importance of local nodes within the global graph structure.

However, the distributed nature of these graphs, coupled with privacy requirements, renders traditional centralized computation infeasible. The "honest but curious" adversary model is assumed, where data centers will follow the protocol but attempt to infer as much information as possible from the exchanged data. This necessitates a privacy-preserving mechanism.

Poppy's foundation lies in Fully Homomorphic Encryption (FHE), a cryptographic primitive that allows arbitrary computations to be performed directly on encrypted data without decrypting it first. Specifically, the project utilizes the CKKS (Cheon-Kim-Kim-Song) homomorphic encryption scheme. CKKS is particularly suited for operations on real numbers, albeit with approximate arithmetic and an inherent error. A key feature of CKKS is its SIMD (Single Instruction, Multiple Data) capabilities, meaning a single ciphertext can be viewed as a fixed-size vector, enabling parallel operations on multiple data points simultaneously. This is achieved through operations such as cell-wise additions, cell-wise multiplications, and rotations (modular shifts). CKKS also supports approximate division, implemented via interpolation of the inverse function. A fundamental limitation of FHE schemes like CKKS is the multiplicative depth, which dictates a bounded number of multiplications that can be performed on a ciphertext before the accumulated error becomes too large. To counteract this, a process called bootstrapping is required, which refreshes the error and allows further computations, albeit at a significant computational cost. Poppy's innovation lies in adapting these FHE primitives to securely and scalably compute spectral centrality measures across distributed, sensitive graphs.

Key Findings

▶ Watch: Three PoPy algorithms for diverse graph types (5:00)

The Poppy project introduces several significant contributions, addressing the long-standing challenge of secure and scalable graph analytics on sensitive, distributed data. The core achievement is the development of three distinct Poppy algorithms, each optimized for different graph characteristics, while collectively demonstrating the first known solution to satisfy the trifecta of generality, accuracy, and scalability in this domain.

Firstly, the research moved beyond a naive "think as a vertex" baseline, which proved unscalable due to its linear dependency on the number of graph nodes. The three proposed algorithms are:

  • PoppyS (Sparse): Designed with a vector representation, making it highly efficient for sparse graphs where nodes have relatively few connections.
  • PoppyD (Dense): Utilizes a matrix representation, better suited for dense graphs characterized by a high number of connections between nodes.
  • PoppyH (Hybrid): An innovative hybrid approach that balances the strengths of PoppyS and PoppyD, particularly effective for graphs with a large number of remote nodes—nodes in distant data centers connected to local nodes.

A pivotal finding is that Poppy successfully achieves the three critical requirements: generality, by supporting various spectral centrality measures; accuracy, demonstrated through rigorous experimental evaluation; and scalability, particularly with respect to the number of data centers involved. This combination represents a significant advancement over prior work, which typically sacrifices one or more of these properties for the others.

Beyond the core centrality computation, Poppy introduces a novel concept: ink equivalence. This is a generalization of the well-known notion of "orbit" in graph theory. While orbits define nodes sharing identical incoming and outgoing structural positions, ink equivalence focuses solely on nodes that share the same incoming structural position in the graph. The talk illustrated this with an example of two green nodes that are ink equivalent but not in the same orbit. To leverage this new concept for computational efficiency, the team developed the Pink algorithm. Pink is designed to prune these ink-equivalent nodes, thereby reducing the computational load during centrality calculations.

The experimental evaluation further validated these findings:

  • Accuracy: Poppy's results are highly accurate, with the Kendall tau correlation coefficient (a measure of rank correlation) consistently above 0.93 for all nodes in the graph and never less than 0.95 for the top 10 most influential nodes. This indicates a strong agreement with non-private, exact centrality computations.
  • Efficiency of Pink: The Pink algorithm significantly outperforms NoTi, the state-of-the-art algorithm for orbit computation. Pink was shown to prune twice the number of nodes compared to NoTi and was one order of magnitude faster, demonstrating substantial gains in preprocessing efficiency.
  • Performance and Scalability: While FHE computations inherently carry a performance overhead (e.g., PoppyS and PoppyD taking less than 3 hours per iteration for a synthetic graph of 25,000 nodes), the results show strong scalability with the number of data centers. Crucially, the time per iteration decreases as the number of data centers increases, highlighting Poppy's suitability for highly distributed environments.

Finally, the project includes an open-source implementation of both Poppy and Pink in C++, ensuring reproducibility and enabling further research and adoption.

Technical Deep Dive

▶ Watch: Novel "ink equivalence" for pruning graph nodes (6:00)

The technical underpinnings of Poppy are sophisticated, marrying advanced cryptographic techniques with efficient graph algorithms. The problem begins with large, distributed graphs where each data center holds a private subgraph. The goal is to compute global spectral centrality scores without revealing the local subgraph structure to other data centers or a central authority.

Initially, the researchers explored a baseline approach adhering to the "think as a vertex" paradigm. In this model, each node in the graph is considered a computing entity, leading to a computational complexity that is linear in the number of nodes. While conceptually simple, this approach proved unscalable for large graphs, making it impractical for real-world distributed scenarios.

Poppy's innovation stems from its tailored algorithms, PoppyS, PoppyD, and PoppyH, which leverage the CKKS homomorphic encryption scheme's SIMD capabilities. CKKS allows multiple real numbers to be packed into a single ciphertext, enabling batch processing. The "cells of the vector [are] full of the active nodes," meaning that operations on these encrypted vectors effectively process multiple node-related values simultaneously.

  1. PoppyS (Sparse Graph Algorithm): This algorithm is optimized for graphs where nodes have a relatively low number of connections. It employs a vector representation for the graph's adjacency information. In a sparse graph, many entries in the adjacency matrix would be zero. By using a vector representation, PoppyS can more efficiently pack only the active (non-zero) connections into the CKKS ciphertext vectors, reducing computational overhead. This is particularly effective when the number of remote nodes connected to a local data center is not excessively high.
  1. PoppyD (Dense Graph Algorithm): In contrast, PoppyD is designed for dense graphs, where nodes are extensively interconnected. For such graphs, a matrix representation becomes more suitable. While this might seem counterintuitive for FHE (which often prefers vector operations), the density means that a significant portion of the matrix entries are non-zero. PoppyD likely structures the data such that matrix operations can be mapped efficiently onto the SIMD vector capabilities of CKKS, potentially by encrypting rows or columns as vectors and performing rotations and multiplications.
  1. PoppyH (Hybrid Algorithm): Recognizing that real-world graphs often exhibit varying densities and distributions of remote connections, PoppyH offers a hybrid approach. It is specifically tailored for graphs with a large number of remote nodes. This suggests an adaptive strategy that might switch between vector and matrix representations or combine elements of both, depending on the local subgraph characteristics and the nature of its connections to distant data centers. The goal is to minimize communication and computation costs associated with interactions between encrypted data from different data centers.

The core of spectral centrality computation is iterative linear algebra. A common step involves multiplying an adjacency matrix (or a representation thereof) by a centrality vector (representing the current scores of nodes). In a distributed FHE setting, this involves:

  • Local Computations: Each data center performs operations on its local, encrypted subgraph data.
  • Encrypted Communication: Data centers exchange encrypted intermediate results.
  • Secure Aggregation: A central server (or a designated party) can perform aggregations on these encrypted results using FHE, without decrypting them.
  • Normalization: The talk emphasized that normalization of centrality scores is mandatory in a distributed context. This likely involves a secure sum or maximum operation over encrypted values to ensure that the relative importance of nodes is correctly maintained across the global graph.

The security of Poppy is formally proven, ensuring that no data center can learn sensitive information about other data centers' subgraphs beyond what is revealed by the final, public centrality scores. The complexity of each Poppy variant has also been rigorously studied, providing insights into their performance characteristics under different graph topologies.

A significant algorithmic contribution is the introduction of ink equivalence and the Pink algorithm. Ink equivalence generalizes the concept of graph orbits. An orbit groups nodes that are structurally identical in terms of both incoming and outgoing edges. Ink equivalence, however, focuses solely on nodes sharing the same incoming structural position. For example, two nodes might receive connections from identical sets of nodes with identical weights, even if their outgoing connections differ. The Pink algorithm leverages this property to identify and prune these ink-equivalent nodes. By treating ink-equivalent nodes as a single representative during computation and then mapping the result back, Pink can significantly reduce the effective size of the graph, thereby accelerating the iterative centrality calculations. This pruning strategy is a crucial optimization to mitigate the high computational cost of FHE. The implementation of both Poppy and Pink is open-source in C++, enabling practical deployment and further research.

Demo / Proof of Concept

▶ Watch: Scalability of PoPy with FHE overhead (7:50)

While the talk did not feature a live, interactive demonstration, the research presented a comprehensive in-depth experimental evaluation that serves as a robust proof of concept for Poppy and Pink. This evaluation, performed on various synthetic graphs, meticulously validates the algorithms' correctness, accuracy, and scalability.

The primary measure of correctness and accuracy for Poppy was the Kendall tau correlation coefficient, which quantifies the ordinal association between the ranks of nodes computed by Poppy (securely) and the ranks computed by a non-private, exact method. The results were highly compelling: the Kendall tau was never less than 0.93 for all nodes in the graph and never less than 0.95 for the top 10 nodes. This high correlation value decisively demonstrates that Poppy accurately identifies the most influential nodes and maintains the overall ranking integrity, despite the approximations inherent in the CKKS homomorphic encryption scheme.

For the Pink algorithm, its performance was benchmarked against NoTi, the state-of-the-art algorithm for computing graph orbits. Pink exhibited superior pruning capabilities and efficiency: it was shown to prune twice the number of nodes compared to NoTi and was approximately one order of magnitude faster. This significant improvement highlights Pink's effectiveness in reducing the computational burden, which is particularly critical when dealing with the overhead of FHE.

The computational cost of homomorphic encryption is a known challenge. The evaluation provided concrete figures for the execution time. For synthetic graphs with 25,000 nodes, PoppyS and PoppyD took less than 3 hours per iteration. While this might seem substantial compared to non-private computations, it represents a practical runtime for complex graph analytics given the strong privacy guarantees. The talk illustrated this with graphs showing average execution time for the largest data center across various synthetic graph sizes.

Crucially, the experiments also validated Poppy's scalability with the number of data centers. The results indicated that as the number of data centers increased, the time required per iteration decreased. This counter-intuitive finding suggests that Poppy's distributed design effectively distributes the computational load, making it well-suited for highly decentralized environments. This is a critical characteristic for real-world deployments involving multiple organizations or regions.

The entire framework, including both Poppy and Pink algorithms, has been made available as an open-source implementation in C++, which the speaker noted was accessible via a QR code linking to GitLab. This open-source release further strengthens the proof of concept by allowing other researchers and practitioners to reproduce the results and build upon this foundational work.

Defensive Implications

▶ Watch: Conclusion and open-source implementation details (8:30)

The Poppy framework offers profound defensive implications for organizations grappling with the dual challenges of data privacy and analytical insight, particularly those managing large, sensitive, and distributed graph data. The ability to compute spectral centrality measures securely without centralizing data directly addresses regulatory compliance and risk mitigation.

For industries such as finance, healthcare, or social media, where graphs represent sensitive relationships (e.g., financial transactions, patient referral networks, social connections), Poppy provides a mechanism to perform crucial analyses without violating privacy laws like GDPR or HIPAA. For example, banks can use Poppy to detect financial fraud by identifying abnormally central or influential accounts within a network of transactions, even if transaction data is distributed across multiple regional data centers and cannot be shared in plaintext. This allows for proactive threat detection while upholding customer data confidentiality. The Meta fine referenced by the speaker serves as a stark reminder of the severe consequences of failing to protect cross-border data. Poppy directly helps avoid such penalties by enabling secure computation in situ.

Defenders should recognize that Poppy empowers them to gain critical intelligence from their distributed graph data. Instead of being forced to choose between privacy and utility, they can now have both. This means:

  • Enhanced Fraud Detection: Identifying key actors or suspicious patterns in financial networks without exposing individual transaction details.
  • Improved Insider Threat Analysis: Analyzing communication or access graphs to detect anomalous influence or collusion among employees, again, without centralizing sensitive internal data.
  • Better Infrastructure Security: Understanding the most critical nodes in a distributed IT network to prioritize defensive measures, even if network topology data is segmented across different departments or cloud environments.

Organizations considering Poppy should evaluate their graph characteristics to select the most appropriate algorithm: PoppyS for sparse graphs, PoppyD for dense graphs, and PoppyH for graphs with many remote connections. This selection is crucial for optimizing performance given the inherent computational cost of FHE. Furthermore, the Pink algorithm should be integrated where applicable, as its ability to prune ink-equivalent nodes significantly reduces computational overhead, making the overall process more efficient.

While FHE introduces a computational cost, the demonstrated scalability with the number of data centers is a key defensive advantage. This means that as an organization's data footprint becomes more distributed, Poppy's per-iteration time can actually decrease, making it a viable solution for large-scale, federated learning and analytics on graph structures. Defenders should view the "less than 3 hours per iteration" for 25,000 nodes as a trade-off for unparalleled privacy, enabling analyses that would otherwise be impossible or legally prohibited.

Ultimately, Poppy provides a robust framework for building privacy-preserving analytical pipelines on distributed graph data. It allows security teams and data scientists to move beyond mere compliance to proactive threat intelligence and risk management, all while maintaining the highest standards of data confidentiality.

Key Takeaways

  • Secure Distributed Graph Analytics: Poppy enables the computation of spectral centrality measures (like PageRank) on large, distributed graphs using Fully Homomorphic Encryption (FHE), ensuring data privacy across multiple data centers.
  • Generality, Accuracy, and Scalability: Poppy is the first solution to simultaneously achieve all three requirements, supporting various centrality measures, providing high accuracy (Kendall tau > 0.93), and demonstrating scalability with the number of data centers.
  • Tailored Algorithms for Graph Types: Three distinct algorithms are offered: PoppyS for sparse graphs, PoppyD for dense graphs, and PoppyH for hybrid graphs with numerous remote nodes, allowing for optimized performance based on graph characteristics.
  • Novel Efficiency Enhancements: The introduction of ink equivalence (a generalization of graph orbits) and the accompanying Pink algorithm significantly improve computational efficiency by pruning structurally similar nodes, outperforming state-of-the-art methods like NoTi.
  • Practical Implementation and Performance: Poppy and Pink are open-source in C++, with experimental results showing that while FHE has a computational cost (e.g., < 3 hours per iteration for 25,000 nodes), the system scales effectively as the number of participating data centers increases.
  • Critical for Privacy-Preserving Insights: Poppy provides a vital tool for organizations in sensitive sectors (e.g., finance, healthcare) to derive crucial insights like fraud detection from distributed data without compromising privacy or violating stringent regulatory requirements.

About the Speaker(s)

The talk was presented by Claire Guichemerre, a key paper author associated with Université de Rennes, CNRS, and IRISA. Her work on Poppy is a collaborative effort involving multiple institutions. The research team also includes Tristan Allard from Université de Rennes, CNRS, and IRISA; Sofiane Azogagh, Marc-Olivier Killijian, and Sébastien Gambs from Université du Québec à Montréal; and Amr El Abbadi from the University of California, Santa Barbara. This interdisciplinary collaboration highlights the complex nature of developing cutting-edge solutions at the intersection of cryptography, distributed systems, and graph theory.

Reviews

Dr. Zero (Offensive Security Researcher) — SOLID

Solid FHE math applied to a real distributed graph problem. It's still moving at the glacial speed of homomorphic encryption, but the algorithmic pruning tricks they introduce are genuinely clever and push the field forward.

Heather Calloway (CISO) — SOLID

FHE is moving from mathematical theory to applied business logic. This research demonstrates how to run fraud-detection algorithms across distributed datasets without pooling the underlying data or violating data residency laws. While the computational overhead isn't ready for Fortune 50 transaction volumes, the strategic implication is clear: the technical excuse for failing to collaborate on fraud intelligence across borders is expiring.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026