{"id":"b6e94681-ff9a-4163-b9f9-38003e97451d","arxiv_id":"2506.10399","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"FicGCN proposes sparse intra-ciphertext aggregation and node reordering to reduce rotation overhead in homomorphically encrypted GCN inference, achieving up to 4.10x speedup over state-of-the-art.","lead":"The paper presents FicGCN, a homomorphic encryption framework that speeds up privacy-preserving graph neural network inference by packing node features efficiently and aggregating encrypted neighbors with fewer rotations. It reports up to 4.10x lower latency than prior encrypted GCN systems on standard datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main-text Table 4 contradicts Table 3 and Appendix Table 8 on the headline FicGCN+NOO latencies; the Corafull numbers differ by 17%, changing the claimed 4.10x speedup to 3.50x.","rationale":"I reviewed the strongest claim and the data behind it. The headline 'up to 4.10x improvement' is the ratio 31,735s / 7,733s from Table 3. The paper contains two other reports of the same quantity: main-text Table 4 reports Corafull w/ NOO latency 9,075s, and Appendix Table 8 reports 7,733s. The same mismatch appears for Cora, Citeseer, and NTU. One of these sets of numbers must be wrong. If Table 4 is the correct record, the speedup is 3.50x, and every dataset's speedup changes. This is not a matter of disagreeing with the authors' interpretation; it is an internal contradiction in the measurements. A reader cannot decide which table to trust without code or a re-run. The reader's concern about baseline hardware is also valid: Table 3 does not explicitly state whether Gazelle/Penguin/CryptoGCN were re-implemented locally, and no code is provided. But the internal inconsistency is more immediate because even a perfectly fair baseline cannot validate the headline until the FicGCN latencies themselves are pinned down. I would keep the verdict CONDITIONAL: the paper's method is plausible and the appendix largely agrees with Table 3, but the manuscript must be revised to eliminate the contradiction and, ideally, release code. No ad hominem is intended; a copyediting or versioning error may be the cause.","tokens_in":19854,"tokens_out":8304,"duration_ms":90041,"concrete_test":"Re-run the FicGCN+NOO configuration on Corafull (and ideally all four datasets) with the stated SEAL 3.7.2 / i7-9750H setup, recording latency and Rot/PMult/Add counts. Then compare against Table 3, Table 4, and Appendix Table 8. If 9,075s is the correct latency, the 4.10x claim falls to 3.50x; if 7,733s is correct, Table 4 must be corrected and the manuscript should explain why two tables report different measurements.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central 4.10x speedup claim rests on the Corafull latency of 7,733s in Table 3. However, the main-text ablation Table 4 reports 9,075s for the same 'w/ NOO' configuration, while Appendix Table 8 reports 7,733s, matching Table 3. The discrepancies are not limited to Corafull: Cora w/ NOO is 69.28s (Table 4) vs 64.12s (Table 3/Table 8), Citeseer 86.14s vs 79.98s, and NTU 1463.80s vs 1373.82s; the Rot/PMult/Add counts also differ. If the Table 4 numbers were the correct measurements, the speedup over CryptoGCN on Corafull would be 31,735/9,075 = 3.50x, not 4.10x, and the corresponding comparisons on the other datasets would also shift. Because the abstract and conclusion advertise the 4.10x figure, the paper must resolve this internal inconsistency before the headline claim can be evaluated. The factor c and the unexplained '10' in the SpIntra-CA cost model in Section 3.3.2 are secondary; they affect mode selection but are not needed to see that the reported measurements disagree with one another.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FicGCN, a CKKS-based framework for privacy-preserving GCN inference. The framework consists of three main techniques: (i) a latency-aware column-based packing strategy, (ii) a sparse intra-ciphertext aggregation method (SpIntra-CA) with aggregation order and ciphertext processing order optimizations (AOO and CPOO), and (iii) a node order optimization (NOO) algorithm based on BFS region partitioning, interleaved region arrangement, and a greedy conflict-minimizing search. The authors evaluate FicGCN on Cora, Citeseer, Corafull, and NTU datasets against Gazelle, Penguin, and CryptoGCN, reporting speedups up to 4.10x over CryptoGCN on Corafull, and claim the best performance across all tested datasets.","tokens_in":20130,"tokens_out":9654,"duration_ms":96157,"significance":"If the reported speedups (up to 4.10x) hold under a fair comparison, this is a notable practical advance for HE-based GCN inference: the paper directly targets the rotation bottleneck created by irregular graph sparsity and combines it with a realizable packing and reordering pipeline. The paper's strengths include a clear operational breakdown (Rot/PMult/Add), a worst-case analysis of the SpIntra-CA rotation overhead, ablation studies for AOO, CPOO, and NOO, and an overhead analysis of NOO on a large-scale graph (Pokec). However, the headline result currently rests on internally inconsistent measurements across the main text and appendix, and the fairness of the baseline comparison is not fully documented. These issues must be resolved before the empirical claim can be accepted.","major_comments":[{"comment":"The latency reported for the same 'w/ NOO' configuration is inconsistent across tables: for Corafull, Table 3 and Appendix Table 8 report 7,733s, while main-text Table 4 reports 9,075s (with Rot/PMult/Add counts of 36.7K/14.7M/16.9M vs. 32.1K/12.7M/14.9M). Similar discrepancies appear for Cora (64.12s vs. 69.28s), Citeseer (79.98s vs. 86.14s), and NTU (1373.82s vs. 1463.80s). If Table 4 is correct, the claimed 4.10x speedup on Corafull would become 31,735/9,075 = 3.50x, which contradicts the abstract and conclusion. The authors must identify which table is correct and explain the discrepancy.","section":"Tables 3, 4, and Appendix Table 8"},{"comment":"The manuscript does not explicitly state whether the Gazelle, Penguin, and CryptoGCN baseline latencies in Table 3 were re-implemented and measured locally on the same Intel i7-9750H / SEAL 3.7.2 platform. If these numbers were taken from prior publications with different hardware or HE parameter settings, the claimed speedups would not be fair comparisons. Please clarify the provenance of each baseline number and, if they were reproduced, describe the re-implementation and validation steps.","section":"Sections 4.1 and 4.2.1"},{"comment":"Section 2.5 states that all HE parameters are selected to achieve 128-bit security, but Appendix Table 6 lists the NTU configuration with security level '>=80-bit'. Since the paper's privacy guarantee rests on this claim, the contradiction must be resolved, either by adjusting the security statement or by providing parameter estimates that justify 128-bit for the NTU settings.","section":"Section 2.5 vs. Section 4.1 / Appendix Table 6"},{"comment":"The mode-selection formula for SpIntra-CA in Section 3.3.2 uses the term 10cn log2(N) with c in [0,1] a free parameter, while the cost model in Appendix B.1 assumes Rot is 20x slower than PMult/Add. The factor 10 and the choice of c are not derived, and no sensitivity analysis is provided. Because the abstract claims a 'globally optimal balance' between aggregation and combination, this heuristic should be justified or the claims should be softened to describe a heuristic scheduling strategy.","section":"Section 3.3.2 and Appendix B"}],"minor_comments":[{"comment":"The name 'Peinguin' should be 'Penguin'.","section":"Section 2.3"},{"comment":"The text claims '>120x over Gazelle' on Corafull, but Table 3 lists Gazelle's Corafull latency as '/'; explain how this speedup bound was obtained or remove it.","section":"Section 4.2.1 and Table 3"},{"comment":"The text says 'The results are presented in Table 4', but the overhead analysis appears in Table 5.","section":"Section 4.3"},{"comment":"The phrase 'the delay caused by Rot exceeds A%' uses an undefined symbol 'A%'; this should be a concrete percentage or the placeholder should be removed.","section":"Appendix A"},{"comment":"The notation 'Q=2^18' and 'Q=680' is nonstandard for a CKKS modulus; clarify whether these are bit lengths or actual modulus sizes, and use consistent notation throughout.","section":"Section 4.1"},{"comment":"The cross-references to appendix tables are inconsistent: Section C.2 refers to 'Table 6' when the packing ablation is Table 7, and Section C.3 refers to 'Table 7' when the NOO ablation is Table 8.","section":"Appendix C.2 and C.3"},{"comment":"The variable 'n' is used both as a node variable and as the sampled neighbor count; rename one of them to avoid confusion.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to be an ICML 2025 submission, and the arXiv version is a preprint. The authors do not release code, which makes the measurement inconsistencies difficult to resolve by independent reproduction. The editor may want to ask for the raw latency logs or code as supplementary material, since the paper's significance depends entirely on the empirical speedup claims. The 'globally optimal' claim in the abstract is also stronger than the heuristics in Section 3.3.2 support; softening or deriving the mode-selection formula would improve the paper's rigor."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The advertised 4.10x speedup on Corafull is not reproducible from the paper's own tables: Table 3 and Appendix Table 8 report 7,733s, while main-text Table 4 reports 9,075s for the same \"w/ NOO\" configuration. The same mismatch shows up on every dataset — Cora 69.28s vs 64.12s, Citeseer 86.14s vs 79.98s, NTU 1463.80s vs 1373.82s — and the Rot/PMult/Add counts disagree as well. If Table 4 is the correct measurement, the Corafull speedup drops from 4.10x to 3.50x. This does not kill the paper, but it means the headline number is not yet a fact.\n\nWhat is genuinely new: SpIntra-CA is a real idea—using bit-decomposed rotations and masks to do sparse neighbor aggregation inside a single CKKS ciphertext, instead of the node-by-node or multi-ciphertext approaches in CryptoGCN and Penguin. NOO is a sensible ordering heuristic that maps sibling nodes into regions and interleaves them to fit the cyclic ring. The ablations show each piece helps, and the packing-aware mode selection is a reasonable engineering contribution. The authors also measured on a single machine with SEAL 3.7.2, which is more than many papers in this area do.\n\nSoft spots, in proportion. The table inconsistency is the serious one; it must be reconciled. Second, the baseline question the reader raised still stands: the paper says it adopts HE parameters from Penguin/CryptoGCN, but never explicitly states whether Gazelle/Penguin/CryptoGCN were re-implemented and run locally or taken from published numbers. Third, the SpIntra-CA cost model uses a factor c and a factor 10 that are not derived; the \"10\" conflicts with the paper's own \">20x\" Rot-vs-PMult statement in Appendix A. These are design heuristics, not circular evidence, but they deserve a fuller explanation.\n\nWho this is for: people working on HE-GCN inference. It is a competent systems paper with a fixable reporting flaw. My recommendation: send it to peer review, but require the authors to resolve the table discrepancy and state baseline provenance before acceptance. The techniques are worth refereeing; the current numbers are not.","headline":"The 4.10x headline is internally inconsistent across tables; the underlying techniques are real but the numbers need reconciliation before the speedup claim can be trusted.","tokens_in":20709,"tokens_out":1929,"would_cite":false,"duration_ms":21290,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"FicGCN claims a homomorphic-encryption framework that runs privacy-preserving GCN inference up to 4.10x faster than prior designs, by exploiting the irregular sparsity of the graph's adjacency matrix.","keywords":["homomorphic encryption","CKKS","graph convolutional networks","private inference","sparse aggregation","ciphertext packing","node order optimization","latency optimization"],"falsifier":"Re-run FicGCN and CryptoGCN end-to-end on Corafull on the same single-threaded machine using Microsoft SEAL 3.7.2 with the paper's stated parameters ($\\Delta=2^{30}$, $M=2^{12}$, $Q=2^{18}$) and compare latencies: if FicGCN does not finish near 7,733 seconds while CryptoGCN costs near 31,735 seconds, the central 4.10x claim does not reproduce.","tokens_in":19649,"feed_emoji":"🔐","tokens_out":14670,"duration_ms":138355,"temperature":0.7,"pith_summary":"This paper proposes FicGCN, a framework for running Graph Convolutional Network (GCN) inference on homomorphically encrypted data, so that a cloud server can compute on a client's graph features without ever seeing them. Its claim is that the irregular sparsity of the adjacency matrix is a resource, not a nuisance: by packing the encrypted feature matrix in a latency-aware way, gathering neighbours inside a single ciphertext with masked rotations, and reordering nodes around the ciphertext ring, the dominant cost of homomorphic rotations is sharply reduced. Across four benchmark datasets the paper reports the best end-to-end latencies, culminating in 7,733 seconds on the 19,793-node Corafull graph versus 31,735 seconds for the previous fastest design, a 4.10x improvement. If the numbers hold, privacy-preserving graph services for domains such as healthcare and finance move closer to practice, with encrypted inference on a 20,000-node graph shrinking to about two hours on a single CPU thread.","feed_headline":"4.1x faster encrypted GCN inference via graph sparsity","feed_subtitle":"FicGCN exploits sparse, irregular adjacency to slash rotation overhead in homomorphic graph neural network inference.","key_machinery":"The load-bearing mechanism is SpIntra-CA (Sparse Intra-Ciphertext Aggregation), an adaptation of the classic power-of-two ciphertext internal-sum trick to irregular graphs: each node's required rotation length is decomposed into bits, the ciphertext is rotated by $2^0, 2^1, \\ldots$, and after each step a mask plaintext polynomial (a vector of 0s and 1s) keeps the slots that have reached their target neighbour and removes those that have finished. This replaces the one-rotation-per-node strategy with roughly $\\log(N)$ rotations in favourable cases, at the cost of possible slot conflicts when two nodes want the same position; the paper's worst-case analysis gives $O(n\\log^2 N)$ rotations and notes that the exact relationship between conflicts and ciphertext sparsity is hard to derive because it touches the NP-complete graph-colouring problem, so the practical gains are empirical rather than proven bounds. Two supporting devices carry the efficiency: a latency-aware packing scheme that chooses the number of columns $t$ per ciphertext by minimising an objective like $2\\lceil Fn/t\\rceil + 20\\lceil\\log(t)\\rceil$, and Node Order Optimization (NOO), an offline reordering that groups sibling nodes into regions, interleaves regions around the ciphertext ring, and greedily minimises conflicts.","core_discovery":"The paper's central claim is that the irregular sparsity of a GCN's adjacency matrix can be converted directly into speed instead of being fought against. FicGCN packs the encrypted feature matrix column-wise with a per-dataset choice of how many columns share a ciphertext, then decides layer by layer whether to aggregate across ciphertexts (Inter-CA) or within a single ciphertext (SpIntra-CA). In SpIntra-CA, a single packed ciphertext is rotated by powers of two and a 0/1 mask is applied after each rotation, so that every slot simultaneously receives a neighbour or keeps its own value, reaching the target neighbour arrangement in roughly $\\log(N)$ rotations in the ideal case. A node-order optimization pass partitions the graph into sibling-dense regions, interleaves those regions on the ciphertext ring, and greedily places nodes to avoid slot conflicts, which keeps the extra rotations caused by collisions low. With this combination, the paper reports the fastest inference on Cora, Citeseer, Corafull and NTU-cross-View, with the largest gain, 4.10x over CryptoGCN, on Corafull, the biggest graph tested.","pith_inferences":["The paper's cost model — a per-layer choice between sparse intra-ciphertext rotation and dense inter-ciphertext multiplication, driven by feature dimension versus slot count — is a template that could transfer to other CKKS workloads that multiply a sparse plaintext matrix against packed ciphertexts, such as encrypted recommendation or attention layers.","Because the node order inside a ciphertext is a free variable, NOO's region-interleaving idea suggests a testable extension for other message-passing models: re-run the region detection against a given neighbour-sampling scheme and check whether rotation counts fall in proportion to how tightly sibling nodes are co-located on the ring.","The paper's own caveat that conflict behaviour connects to the NP-complete graph-colouring problem implies that the reported speedups are empirical, heuristic results rather than proven bounds, so the method's edge over dense baselines should be re-checked whenever the graph's degree distribution or the sampler changes."],"forward_implications":["On the paper's reported numbers, encrypted inference on the 19,793-node Corafull graph drops from 31,735 seconds (CryptoGCN) to 7,733 seconds (FicGCN), a 4.10x gain, and the gap to the oldest baseline, Gazelle, exceeds 120x.","The gains concentrate where the graph is large relative to the ciphertext slot count: the speedup over the fastest baseline grows from 1.26x on the 25-node NTU dataset to 2.01x on Cora and 4.10x on Corafull.","Ablation results attribute most of the benefit to rotation reduction: Node Order Optimization alone cuts rotations by about 66% on Cora and Citeseer relative to un-reordered SpIntra-CA, and the latency-aware packing choice is worth about 1.27x-1.44x on those datasets.","The offline node-reordering overhead stays comparatively tiny even at scale: on a million-node Pokec estimate the paper measures preprocessing at about 0.002% of the online encrypted-inference time."],"supporting_citations":[{"why":"Introduces the CKKS approximate-arithmetic homomorphic encryption scheme that FicGCN is implemented on, including its addition, multiplication, and rotation semantics.","marker":"(Cheon et al., 2017)"},{"why":"CryptoGCN, the sparsity-aware baseline that is the fastest prior design on Corafull and NTU and the source of the datasets, models, and small-scale HE parameters reused by FicGCN.","marker":"(Ran et al., 2022)"},{"why":"Penguin, the parallel-packed baseline that is the fastest prior design on Cora and Citeseer and the source of the large-scale HE parameter configuration.","marker":"(Ran et al., 2024)"},{"why":"Gazelle, the earliest framework for optimised HE matrix multiplication via diagonal encoding, serving as the oldest and slowest baseline in the comparison.","marker":"(Juvekar et al., 2018)"},{"why":"Defines the GCN layer $X^{l+1}=\\sigma(\\hat{A}X^l W^l)$ whose aggregation-combination structure is the target of FicGCN's optimisation.","marker":"(Kipf and Welling, 2016)"},{"why":"Defines GraphSAGE, whose mean-over-sampled-neighbours aggregation is the forward-propagation form FicGCN accelerates.","marker":"(Hamilton et al., 2017)"},{"why":"Provides the power-of-two rotation scheme for ciphertext internal sums that SpIntra-CA adapts to irregular neighbour gathering.","marker":"(Halevi and Shoup, 2014)"}],"fun_headline_variants":["Sparse packing yields 4.1x faster homomorphic GCN inference","FicGCN exploits graph sparsity for 4.1x speedup in encrypted GCNs","Turning irregular adjacency into encrypted GCN speed","4.1x boost: sparse-aware HE for graph neural networks","Encrypted GCNs get 4.1x faster with sparsity-aware packing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The speedup claims rest on the presumption that the Gazelle, Penguin, and CryptoGCN baseline latencies in Table 3 were measured on the same hardware and with the same ciphertext parameters as FicGCN; the paper states its environment (single-threaded Intel i7-9750H, SEAL 3.7.2) but releases no code, so the baseline figures cannot be independently replayed.","fun_headline_variants_meta":{"raw":{"variants":["Sparse packing yields 4.1x faster homomorphic GCN inference","FicGCN exploits graph sparsity for 4.1x speedup in encrypted GCNs","Turning irregular adjacency into encrypted GCN speed","4.1x boost: sparse-aware HE for graph neural networks","Encrypted GCNs get 4.1x faster with sparsity-aware packing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00025,"raw_usage":{"total_tokens":1587,"prompt_tokens":1014,"completion_tokens":573,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":473}},"tokens_in":630,"tokens_out":573,"duration_ms":6930,"temperature":1.0,"reasoning_tokens":473,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:28:32.602183+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run FicGCN and CryptoGCN end-to-end on Corafull on the same single-threaded machine using Microsoft SEAL 3.7.2 with the paper's stated parameters ($\\Delta=2^{30}$, $M=2^{12}$, $Q=2^{18}$) and compare latencies: if FicGCN does not finish near 7,733 seconds while CryptoGCN costs near 31,735 seconds, the central 4.10x claim does not reproduce.","supporting_citations":[{"cited_title":"H., Kim, A., Kim, M., and Song, Y","cited_arxiv_id":null,"evidence_quote":"Introduces the CKKS approximate-arithmetic homomorphic encryption scheme that FicGCN is implemented on, including its addition, multiplication, and rotation semantics."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"CryptoGCN, the sparsity-aware baseline that is the fastest prior design on Corafull and NTU and the source of the datasets, models, and small-scale HE parameters reused by FicGCN."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Penguin, the parallel-packed baseline that is the fastest prior design on Cora and Citeseer and the source of the large-scale HE parameter configuration."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gazelle, the earliest framework for optimised HE matrix multiplication via diagonal encoding, serving as the oldest and slowest baseline in the comparison."},{"cited_title":"and Shoup, V","cited_arxiv_id":null,"evidence_quote":"Provides the power-of-two rotation scheme for ciphertext internal sums that SpIntra-CA adapts to irregular neighbour gathering."}],"review_version":1}