DESIGN: Encrypted GNN Inference via Server-Side Input Graph Pruning
Kaixiang Zhao, Joseph Yousry Attalla, Qian Lou, Yushun Dong · 2025
Read DESIGN: Encrypted GNN Inference via Server-Side Input Graph Pruning by Kaixiang Zhao, Joseph Yousry Attalla, Qian Lou, Yushun Dong (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05649.txt.
Introduction
Kaixiang Zhao and co-authors present in 2025 DESIGN, a framework for running graph neural networks on encrypted data without huge slowdowns. Fully homomorphic encryption lets servers compute on sealed data, but graph models under it are usually too slow for real time use. Their insight is that input graphs carry much redundancy that uniform processing wastes effort on every node.
The server scores node importance from encrypted degree data, then prunes unimportant parts of the graph. It also varies activation complexity by node importance. Tests show large speedups over prior encrypted methods with competitive accuracy. Code is public for secure graph analytics work.
Catalog record
| CREATOR | Kaixiang Zhao, Joseph Yousry Attalla, Qian Lou, Yushun Dong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-05649
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DESIGN: Encrypted GNN Inference via Server-Side Input Graph Pruning Kaixiang Zhao, Joseph Yousry Attalla, Qian Lou, Yushun Dong Abstract Graph Neural Networks (GNNs) have achieved state-of-the-art performance in various graph-based learning tasks. However, enabling privacy-preserving GNNs in encrypted domains, such as under Fully Homomorphic Encryption (FHE), typically incurs substantial computational overhead, rendering real-time and privacy-preserving inference impractical. In this work, we propose DESIGN (Encrypte D GNN Inference via s E rver- S ide I nput G raph pru N ing), a novel framework for efficient encrypted GNN inference. DESIGN tackles the critical efficiency limitations of existing FHE GNN approaches, which often overlook input data redundancy and apply uniform computational strategies. Our framework achieves significant performance gains through a hierarchical optimization strategy executed entirely on the server: first, FHE-compatible node importance scores (based on encrypted degree statistics) are computed from the encrypted graph. These scores then guide a homomorphic partitioning process, generating multi-level importance masks directly under FHE. This dynamically generated mask facilitates both input graph pruning (by logically removing unimportant elements) and a novel adaptive polynomial activation scheme, where activation complexity is tailored to node importance levels. Empirical evaluations demonstrate that DESIGN substantially accelerates FHE GNN inference compared to state-of-the-art methods while maintaining competitive model accuracy, presenting a robust solution for secure graph analytics. Our implementation is publicly available at https://github.com/LabRAI/DESIGN . 1 Introduction Graph Neural Networks (GNNs) have become increasingly popular tools for learning from graph-structured data, demonstrating remarkable performance in diverse real-world applications such as recommendation systems, bioinformatics, and social network analysis gao2019graph ; chen2025lightgnn ; zheng2020robust ; wu2020comprehensive ; wu2022graph . The success of GNNs primarily stems from their inherent ability to capture complex relational information and structural patterns through message-passing mechanisms between nodes gilmer2017neural . However, despite their widespread adoption, the use of GNNs on sensitive graph data, which often contains personal or proprietary information (e.g., user profiles, financial transactions, social connections), raises significant privacy concerns, especially when processed by third-party cloud services zhang2024survey ; ju2024survey ; zhao2025survey ; cao2011privacy ; zhao2025survey1 ; cheng2025atom ; wang2025cega . Such processing can expose confidential details to potential breaches and unauthorized access wang2023secgnn . Fully Homomorphic Encryption (FHE) perfectly aligns with the need for privacy in this domain, as it allows computations to be performed directly on encrypted data (ciphertexts) without requiring decryption by the server, thus ensuring end-to-end data confidentiality gentry2009fully ; brakerski2014leveled . Consequently, applying FHE to GNNs has emerged as a critical research direction to enable secure and private graph analytics ran2022cryptogcn ; peng2023lingcn ; effendi2024privacy ; huang2024privacy . Nevertheless, this combination introduces substantial computational challenges. Basic arithmetic operations under FHE are orders of magnitude more expensive than their unencrypted, i.e., plaintext, counterparts acar2018survey ; asharov2012multiparty ; cheon2017homomorphic . This overhead, particularly from numerous homomorphic multiplications and complex polynomial approximations for non-linearities, makes direct FHE translation of GNN inference prohibitively slow for many practical applications, creating an urgent need for techniques that enhance the efficiency while preserving both privacy and utility. Researchers have explored several approaches to address this privacy-efficiency challenge. Recent methods have primarily focused on optimizing the GNN model’s internal structure, reducing homomorphic operations through adjustments to model architectures and polynomial approximations of activation functions ran2022cryptogcn . These approaches exploit sparsity within adjacency matrices and simplify activation functions to significantly lower computational complexity. Other techniques include statistical pruning methods yik2022input ; liu2023comprehensive ; liao2024unifews ; chen2025lightgnn that have shown promise in plaintext environments but remain underexplored in encrypted domains. Model-centric optimizations typically overlook the inherent redundancy present within the input graph data itself jia2020redundancy ; tan2019graph . Moreover, existing approaches often apply uniform optimization strategies across all graph components panda2022polynomial , missing opportunities for adaptive resource allocation based on node and edge importance. The exploration of efficient privacy-preserving GNN inference techniques that leverage both model and data characteristics thus remains nascent, with substantial gaps in balancing privacy, efficiency, and accuracy. Nevertheless, despite the urgent need for efficient privacy-preserving GNN inference, achieving this under server-side FHE constraints is a non-trivial task, and we identify three fundamental challenges. Operating within the stringent constraints of server-side FHE inference, where users upload fully encrypted graphs and the server cannot decrypt data, presents unique challenges for achieving efficiency through pruning and adaptive computation. We identify three primary challenges: (1) Impracticality of Online Encrypted Pruning. Performing dynamic, data-dependent pruning directly on ciphertexts is largely infeasible. The server operates without access to plaintext graph metrics (e.g., node degrees, feature norms). Attempting to compute even simple proxies for these metrics homomorphically incurs significant FHE overhead, particularly from multiplications, and subsequent comparisons against thresholds require expensive HE comparison protocols. Consequently, most existing graph pruning techniques yik2022input ; liu2023comprehensive ; liao2024unifews ; chen2025lightgnn ; gao2019graph ; zheng2020robust ; yu2021auto ; chen2021dygnn , reliant on plaintext access or efficient comparisons, are unsuitable for online, server-side FHE application. (2) Inefficient Uniform Activation Approximation. Efficiently handling non-linear activation functions under FHE remains a critical bottleneck. While polynomial approximations are necessary ran2022cryptogcn , existing methods typically apply a uniform polynomial degree across all nodes. This is suboptimal, as a high degree for critical nodes dictates overall cost, while a uniform low degree can degrade accuracy. The challenge is to enable adaptive polynomial allocation based on node importance without costly online FHE comparisons. (3) Ensuring GNN Architecture Generality. Developing an efficiency framework applicable across diverse GNN architectures is challenging. An ideal solution should enhance performance without tight coupling to specific GNN types or requiring model modifications, ensuring wider usability. To address the challenges above, in this paper, we propose a principled framework named DESIGN (Encrypte D GNN Inference via s E rver- S ide I nput G raph pru N ing). Specifically, DESIGN offers key advantages by enabling server-side efficiency enhancements for FHE GNN inference without requiring client-side modifications or compromising the core privacy guarantees of FHE. It achieves this by intelligently managing computational resources based on dynamically assessed data importance directly under FHE. To handle the challenge of the Impracticality of Online Encrypted Pruning , DESIGN computes FHE-compatible importance scores (e.g., based on encrypted node degrees inspired by methods like yik2022input ; liu2023comprehensive ; liao2024unifews ; chen2025lightgnn ) from the received encrypted graph. These encrypted scores are then used with approximate homomorphic comparison protocols to generate multi-level importance masks directly on the server. This allows for logical pruning of unimportant elements and significantly decreases the volume of data requiring homomorphic computation, thereby addressing FHE overhead, albeit with the computational cost associated with homomorphic comparisons. To tackle the challenge of Inefficient Uniform Activation Approximation , DESIGN introduces an importance-aware activation function allocation strategy. Guided by the dynamically generated importance levels (encoded in the masks), polynomial approximations of varying degrees are assigned: high-degree polynomials (extending concepts from ran2022cryptogcn ) are used for critical nodes to preserve accuracy, while lower-degree approximations are applied to less important nodes, reducing ciphertext multiplications and overall computational cost. Finally, to address the challenge of Ensuring GNN Architecture Generality , DESIGN’s core mechanisms, dynamically generating importance masks from encrypted data and selecting polynomial degrees based on these mask levels are independent of specific GNN layer operations. This independence allows the framework to be integrated with diverse GNN architectures without requiring significant model-specific alterations. In summary, the