LinGCN: Structural Linearized Graph Convolutional Network for Homomorphically Encrypted Inference

Summary

The paper propose a novel framework called LinGCN, which reduces the multiplication depth and optimize the performance of Homomorphic Encryption based GCN inference. According to the evaluation results, LinGCN shows promising results in both latency speedup and inference accuracy over existing approaches.

Strengths

* The paper is well-written, with illustrative figures on the framework and evaluation results. * I'm not an expert in privacy-preserving computation, but the evaluation results seem promising to me. The proposed framework not only improves the latency speedup but also the inference accuracy. Behind the stage is their proposed differentiable structural linearization, which reduces the multiplication depth in the HE process.

Weaknesses

* The authors should better provide analytical results on the reduced computational cost and the utility loss. I mean although the intuition and the methodology design is convincing, some analytical statements may further support the empirical results. * The authors should also discuss how the security of the HE-based GCN inference process is influenced with the modified designs proposed in the paper.

Questions

See the weakness part above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See the weakness part above.

Summary

To improve the efficiency of HE-based PPML for GCN, in this paper, the authors propose LinGCN, an end-to-end framework for non-linear reduction and polynomial replacement. LinGCN features 3 key elements, including 1) a differentiable structural linearization algorithm, 2) a compact node-wise polynomial replacement policy, and 3) finer-grained operator fusion for node-wise activation functions. The authors demonstrate good improvement over the baseline CryptoGCN.

Strengths

1. The paper is well-written and the motivation is well-explained. 2. The authors demonstrate both higher accuracy and lower latency compared to the baseline CrypoGCN. 3. The ablation experiments is comprehensive.

Weaknesses

1. Only one dataset is shown in the paper. This makes it doubtful for how well the proposed techniques generalize to other datasets, e.g., Cora? 2. Similar techniques have all been proposed by previous method. For example, ReLU linearization and polynomial replacement are widely studied for CNN. The proposed fusion technique is also widely used in plaintext CNN inference. Although the synchronized linearization is unique for GCN, it still makes the proposed method incremental. 3. It is unclear why LinGCN demonstrates better accuracy compared to CryptoGCN. Although KD is helpful, more analysis needs to be provided.

Questions

1. What can LinGCN achieve better accuracy compared to CryptoGCN? What if similar distillation is leveraged for CryptoGCN as well? 2. How are the proposed linearization method different compared to those used for CNNs, like Selective Network Linearization (SNL), RRNet, etc. 3. How does the proposed method generalize to other datasets or tasks?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

LinGCN optimizes HE-based GCN inference by reducing multiplication levels through a differentiable structural linearization algorithm and a compact node-wise polynomial replacement policy, both guided by a two-level distillation from an all-ReLU teacher model. LinGCN also improves HE solutions for GCN private inference, enabling finer operator fusion for node-wise activation functions.

Strengths

1 Important and well-motivated problem 2 Experiments show a clear improvement in latency and accuracy compared to prior work.

Weaknesses

While the concepts of structural linearization and the replacement of ReLU with a polynomial function are not novel in themselves, their application to Graph Convolutional Networks (GCN) is noteworthy. However, it's important to mention that the degree of novelty in this approach is not particularly significant, given the pre-existing knowledge in this field.

Questions

The curves in Figure 1 is confusing. Why the blue curve encompasses a variety of points (red stars, orange dots, and blue dots)? Similarly, the black curve also exhibits this characteristic.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper does not discuss the limitations of the current work nor does it discuss any negative societal impact. Concentrating solely on non-linear operations may not be sufficient for achieving PPML-efficient architectures. This is particularly true in light of emerging lighter cryptographic topologies for non-linear operations, such as those discussed in the following work: Huang, Zhicong, et al. "Cheetah: Lean and fast secure {two-party} deep neural network inference." 31st USENIX Security Symposium (USENIX Security 22). 2022.

Summary

This study presents an approach for enhancing the efficiency of private inference ( using homomorphic encryption (HE)) in Spatiotemporal graph convolutional networks through fine-grained and structured pruning/dropping of non-linearity. The proposed method consists of two main steps. Firstly, ReLUs are eliminated by substituting them with identity/linear operations, reducing the multiplicative depth required for HE operations. Subsequently, the remaining non-linearities are replaced with HE-friendly quadratic activations.

Strengths

1. The idea of optimizing ReLUs with a fine-grained and structured approach is promising. Typically, fine-grained optimizations tend to lack structure, which can reduce the overall benefits of optimization. 2. The paper is well-structured and easy to understand. The proposed method is explained clearly and organized, making it accessible to readers. The authors provide detailed explanations and build a strong foundation for their approach, ensuring it can be easily grasped.

Weaknesses

**Limited novelty (compared to CryptoGCN)**: Compared to the CryptoGCN paper (NeurIPS'22), this paper demonstrates limited novelty. Both papers propose techniques to reduce the multiplicative depth in STGCN and replace ReLUs with quadratic activations. However, while CryptoGCN employs fine-tuning to recover the accuracy drop, this paper utilizes logit and feature-based distillation to address the accuracy drop resulting from the reduction in non-linearity. For a fair comparison, particularly regarding the improvement in accuracy, an ablation study should be included in the paper to demonstrate the benefits of logit-based knowledge distillation, feature-based knowledge distillation, and the combined usage of both techniques compared to CryptoGCN. **CKKS implementation is used rather than rotation-free HE** In this paper, the authors used the CKKS implementation of Homomorphic Encryption (HE), which incurs a significant total latency due to the rotation operations. The provided Table 2 in the Appendix demonstrates that **approximately 90%** of the total HE latency is consumed by rotation operation in the 12-STGCN-6-256 model. This highlights the inefficiency of the CKKS implementation for private inference, especially when considering the availability of rotation-free HE techniques [1] and their implementation in Microsoft-SEAL. **Minor corrections** As stated in lines #157 to #161, the optimizations implemented in SNL, DELPHI, and SAFENet are sub-optimal for achieving high efficiency in HE. It is important to note that these optimizations primarily aim to minimize the cost of non-linearity in Multi-Party Computation, under the assumption that intensive HE operations can be carried out offline. 1. Huang et al., "Cheetah: Lean and fast secure two-party deep neural network inference," USENIX Security 2022.

Questions

1. The sensitivity analysis (Figure 5) shows that ReLUs in the penultimate layers (layer 4) are highly effective, which aligns with similar findings in CNN studies like DeepReDuce (ICML'21) and SENet (ICLR'23). What does it imply about feature learning within CNNs vs GCNs? 2. Is the better accuracy of LINGCN over CryptoGCN only due to CryptoGCN's use of two-level Knowledge Distillation? Both these methods use second-degree polynomial activation (instead ReLUs). 3. Does the accuracy mentioned in the paper refer to floating-point accuracy (in plaintext) or fixed-point accuracy (after converting weights/biases and activation to fixed-point for operations in the ciphertext domain)? **Note** I am open to increasing the score if most concerns are addressed in the rebuttal.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations are not discussed in the paper.

Rebuttal's response

Thank you for the rebuttal, and I acknowledge the Author's effort in producing results on the new dataset. I'm convinced with the ablation study presented in Figure 6c and Figure 6d, and it is evident that the accuracy benefits (over CryptoGCN) of the proposed method mainly stem from the (relatively) loss-less reduction to multiplicative depth. I have *only one question* about the study presented in Figure 5 (an extension to the previously asked Q1): What is Authro's intuition behind Layer 4's criticality being the highest? Figure 5 is a **good observation**; however, the Authors should have presented the **insights** for the same. In general, the semantic information presented in a layer of a network increases from the initial layer to the deeper layer, and the redundancy in features is higher in the deeper layer.