Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work studies the privacy-preserving graph neural networks (GNN) using fully homomorphic encryption. Existing works mainly focus on protecting the data privacy of convolutional neural networks (CNN) using fully homomorphic encryption. This paper tries to explore if fully homomorphic encryption can be used to protect the data privacy pf graph neural networks.  The paper argues that directly applying techniques in privacy-preserving CNN will not work since graph neural network operations brings additional matrix multiplication. To reduce the computational overhead, the paper mainly proposed two techniques including Adjacency Matrix-Aware (AMA) multiplication, and activation pruning techniques. 
strengths_and_weaknesses: Strengths: 

1. Graph neural networks are ubiquitous now and protecting the data privacy of input data is strongly needed. 
2. Fully homomorphic encryption (FHE) is a popular method to enable a privacy-preserving computing on cloud. Combining FHE and GNN is a promising direction.
3. The paper is well-written. 

Weakness: 
1. There are some overclaims. For example, the author claims “this is the first work that builds the PPML pipeline for GCN-based models”. As I know, there are multiple existing  PPML for GCN based networks, like [1].

[1] Igamberdiev, T., & Habernal, I. (2021). Privacy-preserving graph convolutional networks for text classification. arXiv preprint arXiv:2102. 09604.

2. The difference between CNN and GCN is not clear. Although the paper uses figure 1 to highlight that GCN has one more matrix multiplication, the GCN and CNN have same operators. How to design efficient homomorphic encryption matrix multiplication is not novel. Please try to explain the difference compared to existing works like [2][3][4]. It is important to know why existing techniques in FHE-based CNN or [2][3][4] do not work for the GCN. It is also important to know what is the motivation of the proposed AMA-based matrix multiplication. Is it specific for GCN?

[2]Chiang, J. (2022). A Novel Matrix-Encoding Method for Privacy-Preserving Neural Networks (Inference). arXiv preprint arXiv:2201.12577.

[3] Jiang X, Kim M, Lauter K, Song Y. Secure Outsourced Matrix Computation and Application to Neural Networks. Conf Comput Commun Secur. 2018 Oct;2018:1209-1222. doi: 10.1145/3243734.3243837. PMID: 31404438; PMCID: PMC6689419.

[4] Cui, J., Chen, C., Lyu, L., Yang, C., & Li, W. (2021). Exploiting Data Sparsity in Secure Cross-Platform Social Recommendation. Advances in Neural Information Processing Systems, 34, 10524–10534.


3. Paper checklist. The reproduction is not clear to me. It is still not clear why the activation pruning does not significantly hurt the accuracy.


questions: 1. The difference between CNN and GCN is not clear. Although the paper uses figure 1 to highlight that GCN has one more matrix multiplication, the GCN and CNN have the same operators. How to design efficient homomorphic encryption matrix multiplication is not novel. Please try to explain the difference compared to existing works like [2][3][4]. It is important to know why existing techniques in FHE-based CNN or [2][3][4] do not work for the GCN. It is also important to know what is the motivation of the proposed AMA-based matrix multiplication. Is it specific for GCN?

2. The reproduction is not clear to me. It is still not clear why the activation pruning does not significantly hurt the accuracy.
limitations: There are some overclaims. For example, the author claims “this is the first work that builds the PPML pipeline for GCN-based models”. As I know, there are multiple existing PPML for GCN based networks, like [1].
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies private inference of graph convolutional neural networks using leveled homomorphic encryption. The main contributions are, i) a data encoding scheme that is aware of the adjacency matrix of the graph and allows for more efficient spatial convolution that exploits the graph structure to perform matrix-matrix multiplication, and ii) pruning ReLUs to reduce computation overhead.

The method is evaluated on the NTU-XVIEW skeleton joint dataset and demonstrates lower latency compared to existing baseline methods.


strengths_and_weaknesses: **Strengths:**
+ Important and well-motivated problem. 
+ A customized data formatting of GCN over encrypted data under the CKKS scheme. Because CKKS supports SIMD and it is necessary to find a customized way to encode data that is fed into a GCN so that it can better take advantage of SIMD. Previous work majorly focuses on CNNs. There are some presentation issues though as described below.
+ Experiments show a clear improvement in latency compared to the baselines. 

**Weaknesses:**
- Pruning ReLU is not a new idea. Existing methods such as SafeNet (which searches channel-wise mixed-degree approximation of ReLU including pruning), CryptoNAS (explicitly focuses on removing ReLU layers), and Delphi also shares similar ideas and performs layer-wise pruning.
- This is more of a presentation issue rather than a fatal flaw. The AMA-based matrix-matrix multiplication shown in Fig 2(c) is not clear to this reviewer. The description in lines 178-180 is not clear in terms of how exactly is this being computed. An algorithm was provided for the AMA data formatting but not for the matrix-matrix multiplication. To summarize, while the AMA data formating is very clear, how it is being used for matrix-matrix multiplication is not clear from the description in the paper.

questions: 
- In Fig 2c, is the 4x4 matrix with numbers from 1-16 the adjacency matrix? Why is it dense? 
- Can the computational complexity in Tables 5 and 7 (i.e., rotations, PMult, CMult, etc.) be provided in terms of the number of samples $n$, data dimension $d$, batch-size $b$, etc. instead of just showing the numerical values?
- The abstract says, "we develop an approach that can effectively take advantage of the sparsity of matrix operations in GCN inference to significantly reduce the computational overhead". It is not clear to this reviewer where exactly is the sparsity of $A$ being leveraged.
- When you compare CryptoGCN with CHET and Fast-HEAR, you report the computation complexity, i.e. the number of homomorphic operations. I am just wondering if CryptoGCN’s operations take the same time as CHET and Fast-HEAR? Although CHET and Fast-HEAR are both using CKKS, do you maintain the same cryptographic parameters? Can the row-major format use a smaller ring size and be efficient as well?
- This is more of a suggestion. Algorithm 2 is heuristic and not efficient. You train the model with $i$-th activation layer pruned
one by one and sort the performance. Activation pruning is a combination problem. If you only estimate the importance of each ReLU, it is not accurate. Both SafeNet and Delphi use PBT to solve this problem. PBT should be more efficient and can get better solutions than the proposed Activation Prune algorithm.

Will revise the rating of the paper based on the author's rebuttal.
limitations: - The paper does not discuss the limitations of the current work nor does it discuss any negative societal impact. I guess since the paper is focused on private inference, there is limited negative societal impact beyond making "black-box" GCNs even more "black-box" via encryption.
review_title: null

final_score: 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.
review_content: summary: This work deals with two core techniques to efficiently perform GCN networks on HE with a reduced amount of homomorphic operations. First, since the GCN networks usually use the multiplication with the sparse plaintext matrix, the authors devise AMA data formatting to reduce the homomorphic operations using this sparsity of the matrices. Second, they pruned some activation functions less affecting the performance of the GCN networks, and also proposed a method to find these less-affecting activation functions. With these techniques, the authors successfully reduced the number of homomorphic operations compared to the prior works applied to GCN networks, where these works were not optimized for the GCN networks. 
strengths_and_weaknesses: Strengths
- This work deals with the GCN network on HE for the first time. It is desirable to optimize the important networks on HE other than traditional CNN models. 
- The authors observe the sparsity of the matrix in the GCN network and effectively devise the packing method using this sparsity of the matrix. The academic contribution of this technique is good enough.
- The activation pruning technique is not limited to the GCN network and can be applied to more general frameworks, and this technique can be a useful practical technique for reducing the number of homomorphic operations.
- The numerical comparison and theoretical analysis are well shown. Even though this work proposed the first GCN network on HE, they compared the proposed model with the prior work applied to GCN networks. Thus, these techniques were well proven to be effective in GCN networks on HE compared to the prior work for traditional CNN networks.

Weaknesses
- The AMA data formatting is not sufficiently presented. Algorithm 1 is too compact and abstract to be understood exactly, and there is no algorithm for AMA data format-aided matrix-matrix multiplication. Although the authors explain these algorithms in Figure 2, the figures usually play the role of only supplementary material to ease the understanding of the algorithm. I know there is no sufficient margin for this algorithm, but the author should add the specific and detailed pseudocode for these algorithms in Appendix for readers who want to understand the algorithms exactly.

questions: - Will the implementation of this model be open to the public after acceptance?
limitations: There is no negative societal impact.
review_title: null

Meta-review: metareview: The reviewers appreciate the importance of both GCNs as an application, as well as the application of FHE to make their computations secure. The authors are strongly encouraged to:
1) Include the comparison to the prior work that reviewer RkGQ identified in the camera ready version.
2) Discuss complexity, and include the extended table, at the very least in the supplement.
3) Update Fig. 3, and surface the main takeaways from responses to issues raised by Reviewer YLFb to the main text.

confidence: Certain
Decision: Accept