TGHE: Template-based Graph Homomorphic Encryption for Privacy-Preserving GNN Inference in Edge-Cloud Systems
TGHE: Template-based Graph Homomorphic Encryption enables scalable privacy-preserving GNN inference on large dynamic graphs, achieving 66.9× speedup with minimal accuracy loss.
Key Findings
Methodology
TGHE employs local ego-graph extraction and canonicalization at the edge, leveraging the template phenomenon where local structures converge into a limited set of shapes. Structural signatures (templates) are computed for each ego-graph, enabling grouping of structurally identical trees into shared CKKS ciphertexts for SIMD parallel inference. Two optimizers—Approximate Template Fitting and Topology Collapse—maximize SIMD coverage by mapping unmatched ego-graphs to templates or collapsing complex neighborhoods. The process involves feature extraction, treeification, signature matching, ciphertext packing, and optimization, decoupling per-query cost from global graph size and supporting large-scale, dynamic graphs.
Key Results
- On DGraphFin (3.7 million nodes, 4.3 million edges), TGHE-Collapse achieves a 66.9× end-to-end speedup over sequential encrypted inference, with less than 0.002 AUC loss. The majority of queries (over 98%) are processed via SIMD batching, significantly improving throughput. The system effectively eliminates fallback paths through topology collapse, reducing rotation counts and ciphertext operations, demonstrating scalability and efficiency in real-world large financial graphs.
Significance
This work addresses the critical challenge of scaling privacy-preserving GNN inference to large, dynamic graphs prevalent in finance and healthcare. By exploiting local structural regularities, TGHE overcomes the limitations of previous graph-centric HE methods, enabling secure, efficient analysis on graphs with millions of nodes. It paves the way for practical deployment of privacy-preserving graph analytics in industry, ensuring data confidentiality while maintaining high performance. The framework's ability to handle real-world, evolving datasets signifies a major step forward in privacy-aware machine learning.
Technical Contribution
The key technical innovation lies in the template-based canonicalization and ciphertext packing strategy, which exploits the structural regularities of local ego-graphs to enable shared encrypted computation. The introduction of Approximate Template Fitting and Topology Collapse optimizers further enhances SIMD utilization, drastically reducing fallback computations. The system architecture supports linear neighbor aggregation, compatible with the GEARSage model, and integrates polynomial activation approximations for HE. These contributions collectively extend HE-GNN scalability from tens of thousands to millions of nodes, with rigorous efficiency and accuracy validation.
Novelty
This is the first systematic exploitation of the template phenomenon in local ego-graphs for encrypted GNN inference, enabling large-scale, dynamic, privacy-preserving graph analysis. Unlike prior graph-centric HE methods limited to small, static graphs, TGHE decouples query cost from global size, using structure signatures for grouping. The combination of template-based SIMD packing and two novel optimizers—Approximate Template Fitting and Topology Collapse—sets a new standard for efficiency and scalability in HE-GNN research, addressing key limitations of existing approaches.
Limitations
- The method relies on specific GNN architectures with linear neighbor aggregation, limiting support for models with nonlinear activations or attention mechanisms. Extending to more complex architectures remains challenging.
- Topology Collapse assumes certain structural properties (e.g., branch separation), which may not hold in highly heterogeneous or dense graphs, reducing effectiveness.
- While optimizations significantly reduce fallback, some residual sequential computations remain, especially in highly irregular graphs or extreme dynamic scenarios, posing scalability challenges.
Future Work
Future research will aim to generalize the template-based approach to support diverse GNN architectures, including attention-based models. Enhancing the robustness of topology collapse in heterogeneous graphs, integrating adaptive capping strategies, and exploring multi-modal data fusion are promising directions. Additionally, efforts to reduce residual leakage and improve real-time performance will facilitate broader industrial adoption.
AI Executive Summary
In recent years, the demand for privacy-preserving graph analysis has surged across industries such as finance and healthcare. Traditional homomorphic encryption (HE) methods for GNN inference, while secure, are limited by their reliance on global adjacency matrices, restricting evaluation to small graphs of tens of thousands of nodes. This bottleneck hampers practical deployment in large-scale, dynamic scenarios like financial transaction networks, which contain millions of nodes and edges.
To address this challenge, the paper introduces TGHE, a novel framework that shifts from a graph-centric paradigm to an ego-centric approach. By extracting local ego-graphs at the edge, canonicalizing their structures, and leveraging the observed template phenomenon—where local structures tend to converge into a limited set of shapes—TGHE enables efficient encrypted inference at scale. The core innovation involves computing structure signatures (templates) for each ego-graph, then grouping structurally identical trees into shared CKKS ciphertexts, allowing SIMD parallel processing. This approach decouples query cost from the global graph size, making it suitable for dynamic, large-scale graphs.
The system incorporates two key optimizers: Approximate Template Fitting, which maps unmatched ego-graphs to nearby templates via padding, and Topology Collapse, which pre-aggregates neighborhood structures to eliminate structural diversity. These optimizations maximize SIMD coverage, drastically reducing the number of rotations and ciphertext operations required. Experimental results on the DGraphFin dataset demonstrate that TGHE-Collapse achieves a 66.9× speedup over sequential encrypted inference, with less than 0.002 AUC loss, validating its practical effectiveness.
This work significantly advances the field of privacy-preserving graph analytics, enabling secure inference on million-node graphs with high efficiency. It opens new avenues for deploying encrypted GNNs in real-world, large-scale applications, ensuring data confidentiality without sacrificing performance. Future work will focus on extending support to more complex GNN architectures and further reducing residual leakage, aiming for broader industrial adoption.
Deep Analysis
Background
随着数据隐私保护需求的不断增长，基于同态加密的图神经网络（HE-GNN）逐渐成为研究热点。早期工作如CryptoGCN、LinGCN等，主要解决在有限规模图上的加密推理问题，但受限于全局邻接矩阵的存储和计算复杂度，难以扩展到百万级节点。近年来，边缘端提取局部子图、结构归一化的思想逐步兴起，旨在突破全局图的限制，实现大规模动态场景下的隐私保护推理。现有方法多依赖静态图结构，存在扩展性差、实时性不足的问题。
Core Problem
现有HE-GNN方法多采用图中心设计，依赖全局邻接矩阵，导致计算复杂度随图规模线性增长，限制在数万节点以内。金融系统中的交易图具有高动态性，节点频繁新增，静态结构难以满足实时需求。此外，结构预处理可能泄露敏感信息，增加部署复杂度。如何在保证隐私的同时，实现大规模、动态、结构多变的金融图的高效推理，成为亟待解决的难题。
Innovation
第一，提出模板现象，利用局部自我图的结构相似性进行归一化和密文共享，突破全局图规模限制；第二，设计结构签名匹配机制，将相似结构的局部树归入同一密文，支持SIMD批处理；第三，开发近似模板拟合和拓扑折叠两大优化器，极大提升密文利用率，减少fallback路径，显著提升效率。这些创新结合边缘提取、结构归一化和密文打包技术，为HE-GNN的实用化提供新思路。
Methodology
- �� 在边缘端提取局部自我图（ego-graph），限制最大深度和邻居数以控制密文复杂度。• 通过确定性截断（capping）和树形化（treeification）将局部子图转化为唯一结构的树形角色图。• 计算每个树的结构签名（模板签名），识别不同查询的结构相似性。• 利用模板签名将结构相似的局部树打包到共享CKKS密文中，实现SIMD并行推理。• 引入近似模板拟合，将不匹配的树通过填充映射到最接近的模板，保证大部分查询在批处理内完成。• 采用拓扑折叠策略，将邻居聚合中的Hop-2结构在明文中预先合并，消除复杂拓扑差异，避免fallback。• 设计多层GNN架构的线性邻居聚合，支持模板折叠，简化密文操作流程。
Experiments
采用DGraphFin（3.7M节点、4.3M边）作为测试平台，训练基于GEARSage架构的两层模型，特征维度为17和32，激活函数为二次多项式。对比非加密顺序基线与TGHE不同优化策略（Base和Collapse），评估指标为ROC-AUC。随机采样10,000查询节点，测量端到端运行时间、旋转次数和密文操作数。通过不同阈值τ调节模板匹配的精度-速度折衷，验证优化器效果。
Results
TGHE-Collapse在DGraphFin上实现66.9倍加速，端到端时间从39107秒降至115.9秒，旋转次数减少99%，AUC损失小于0.002。模板匹配后，98%以上查询通过SIMD批处理，大幅提升效率。拓扑折叠策略完全消除fallback路径，显著降低计算成本。实验验证了方法在大规模金融图上的可行性与高效性，优于传统HE-GNN方案。
Applications
该技术适用于金融欺诈检测、反洗钱、医疗数据分析等场景，能在保证数据隐私的前提下实现大规模图的高效推理。边缘端提取局部子图，云端进行加密推理，满足行业对数据安全和实时性的双重需求。未来可扩展到多模态、多任务场景，推动隐私保护机器学习的产业化。
Limitations & Outlook
目前方法依赖特定的GNN架构（如GEARSage）和线性邻居聚合，难以直接支持非线性激活或注意力机制模型。拓扑折叠在极端异质或高复杂度图中效果有限，需进一步优化。密文打包和优化器虽提升效率，但在超大规模或高动态场景中仍存在性能瓶颈。未来需研究更通用的结构归一化策略和多样化模型支持。
Plain Language Accessible to non-experts
想象你在一个大型工厂里工作，每天都要处理很多不同的产品。工厂里的每个工人只负责自己的一部分工作，比如装配、包装或检验。为了确保产品的隐私和安全，工厂采用一种特殊的秘密箱子（类似加密箱），工人把自己的工作内容放进去，然后交给中央控制室处理。控制室可以在箱子里操作，比如拼装、检测，但看不到具体内容，只能得到一些加密的结果。工厂发现，虽然每个产品都不同，但很多产品的结构都很相似，比如都是装配某几件零件组成的。这种相似性让工厂可以把很多产品的操作合并到一起，用少量的秘密箱子同时处理大量产品，大大提高效率。这个方法就像TGHE一样，利用局部结构的模板，把相似的局部图结构打包在一起，既保护了隐私，又能快速处理海量数据。
ELI14 Explained like you're 14
想象你在学校里，有很多不同的朋友，每个人都喜欢不同的游戏。有些朋友喜欢玩像素风格，有些喜欢3D动作游戏，但他们的游戏玩法其实有很多相似的地方。现在，你想帮大家玩游戏，但又不想让别人知道你们的秘密（比如你们的游戏密码）。于是，你用一种神奇的盒子，把每个朋友的游戏操作都装进去，这样别人只能看到盒子里的内容，不能知道具体细节。更厉害的是，很多朋友的游戏玩法其实很像，比如都需要跳跃、跑步、攻击。你发现，把这些相似的玩法放在一起，用一个大盒子装起来，就可以同时帮很多朋友玩游戏，既快又安全。这就像TGHE用模板把相似的图结构打包，让计算变得更快、更安全，大家都能享受到隐私保护的智能游戏体验！
Abstract
Existing homomorphic encryption (HE)-based GNN systems adopt a graph-centric paradigm that couples per-query cost to global graph size, limiting evaluations to at most ~20k nodes and making them incompatible with dynamic, large-scale financial graphs. We propose TGHE (Template-based Graph Homomorphic Encryption), an ego-centric framework that resolves this by exploiting a template phenomenon: local computation trees in transaction graphs converge into a small set of structural shapes. TGHE canonicalizes ego-graphs at the edge and packs structurally identical trees into shared CKKS ciphertexts for SIMD-parallel encrypted inference, with two long-tail optimizers (Approximate Template Fitting and Topology Collapse) ensuring full SIMD coverage. On DGraphFin (3.7M nodes, 4.3M edges), TGHE-Collapse achieves a 66.9x speedup over the sequential encrypted baseline with less than 0.002 AUC loss.