{"id":"ae5058c8-4c1e-4898-aa3f-b77195edc1e5","arxiv_id":"2411.12329","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A collaborative method clusters attributed graphs under vertical data partitioning, using local k-means and secure aggregation to match centralized accuracy with lower communication cost.","lead":"This paper introduces a federation method that lets several organizations cluster a shared graph when each one holds a different slice of the data features, without sending raw data to a central server. On four public datasets it reaches clustering accuracy close to that of a centralized method, while reducing the number of expensive secure computations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof relies on inequality (Appendix B, Eq. 19) that is false in general; even under the reader's alignment assumption, the bound does not follow, so the central theoretical guarantee is unproven.","rationale":"The reader's weakest assumption correctly identifies that the proof of Theorem 1 presupposes alignment between global clusters and intersections of local clusters. However, the more fundamental problem is that the key inequality (Appendix B, Eq. 19) used to establish the proximity condition for the virtual nodes is false in general, even under the alignment assumption. The counterexample with four cardinal points shows the claimed spectral-norm bound fails. The restricted proximity condition does not control the internal residual structure of target clusters, so the proof cannot be repaired simply by adding an alignment assumption. The paper has independent empirical support (four datasets, comparison to AGC/GCC and isolated GraphSAGE) and a novel framework, but the central theoretical guarantee—that local successes imply collaborative success—is not established. The reader's CONDITIONAL verdict should be moved to UNVERDICTED because the main theorem is unverified rather than merely missing a clarifying assumption. A concrete re-derivation or numerical check would settle the validity of Eq. (19).","tokens_in":25710,"tokens_out":24850,"duration_ms":229171,"concrete_test":"Construct the explicit counterexample: L = 1, T_q = {[1,0],[0,1],[−1,0],[0,−1]} with \\hat{\\mu}_q = [0,0], and a second cluster of repeated points at [100,0] so that the restricted proximity condition holds with large margin. Numerically compute both sides of Eq. (19). If the left side exceeds the right side, the proof of Theorem 1 is invalid as written. Alternatively, re-derive Eq. (19) symbolically and show that it would require the rows of X − \\hat{C} on T_q to have rank 1, an assumption not stated anywhere in the paper.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"In the proof of Theorem 1 (Appendix B), the step || |T_q|(X_i − \\hat{\\mu}_q) || ≤ ||(X − \\hat{C})u ||, with u the indicator vector of T_q, is used to conclude ||X_i − \\hat{\\mu}_q|| ≤ (1/√n_q)||X − \\hat{C}||. This is not a consequence of the stated definitions. Even if one adds the alignment condition \\hat{C}_j = \\hat{\\mu}_q for all j ∈ T_q, the inequality can fail. Example: L = 1, T_q = {[1,0],[0,1],[−1,0],[0,−1]}, and \\hat{\\mu}_q = [0,0] so that \\hat{C}_j = \\hat{\\mu}_q for all j. Then n_q = 4, the residual matrix X − \\hat{C} restricted to T_q has spectral norm √2, so the claimed RHS is √2/2 ≈ 0.707, while every point satisfies ||X_i − \\hat{\\mu}_q|| = 1. Hence inequality (19) is false. The failure is not merely a missing alignment assumption; it is a missing bound on the spectral norm of the within-cluster residual relative to the maximum point-to-center distance (e.g., rows of X − \\hat{C} on T_q being nearly parallel). No such condition appears in Theorem 1 or Definition 1. Since this inequality is the only step connecting the virtual nodes of Protocol 3 to the proximity condition required for Lemma 1, the theorem's error bound does not follow from the stated assumptions.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies vertically partitioned attributed graph clustering: L participants share a graph but hold different feature blocks of the same n nodes, and they want to cluster the nodes without sharing raw features. The authors propose kCAGC, which first runs a local k-means procedure (Protocol 1) on each participant's filtered features, then intersects the local clusters across participants to form a set of virtual nodes, and finally runs a secure-aggregation k-means (Protocol 2) on those virtual nodes with cluster sizes as weights. The paper claims a communication reduction from O(nk) secure aggregations to O((Q+1)L k^3) for a tree variant, and it states Theorem 1 asserting that, under a 'restricted proximity condition' plus local and global center separation, at most (L epsilon + O(1)L c^{-4})n nodes are misclassified when each participant has epsilon n local 1-bad nodes, with exact recovery when epsilon = 0. Experiments on Cora, Citeseer, Pubmed, and Wiki compare accuracy with the centralized methods AGC and GCC and with a basic kCAGC baseline, and report training times in LAN and WAN settings.","tokens_in":26054,"tokens_out":12125,"duration_ms":129066,"significance":"If the theoretical claim were established, this would be a useful contribution: it addresses a relatively unexplored vertical unsupervised graph-clustering setting, it gives a concrete protocol for reducing the number of expensive secure aggregations, and it provides a fairly complete experimental evaluation, including a comparison with semi-supervised GraphSAGE models and a privacy-leakage measurement. The implementation is described in detail, with experiments run on real datasets under multiple participant counts and local cluster counts. These empirical strengths are real. However, the central Theorem 1 is not proven as stated: the proof in Appendix B contains a false norm inequality and an unstated alignment assumption between global target clusters and intersections of local clusters. The experimental results may still justify the algorithmic contribution, but the advertised theoretical guarantee needs substantial repair before the abstract and contribution statements are supported.","major_comments":[{"comment":"The proof of Theorem 1 asserts that for i = argmin_i ||X_i - mu_q_hat|| and u the indicator vector of T_q, n_q ||X_i - mu_q_hat|| <= ||(X - C_hat) u||, and hence ||X_i - mu_q_hat|| <= (1/sqrt(n_q)) ||X - C_hat||. This inequality is false. The right-hand side is the norm of the sum of the within-cluster residual vectors, while the left-hand side is n_q times the smallest residual norm; the sum can vanish through cancellation even when every individual residual is large. For example, take L = 1, T_q = {[1,0],[0,1],[-1,0],[0,-1]}, mu_q_hat = [0,0], and C_hat_j = mu_q_hat for all j in T_q. Then n_q = 4, ||(X - C_hat)u|| = 0, and ||X_i - mu_q_hat|| = 1 for every i, so the claimed inequality reads 4 <= 0. Shifting the configuration by a small vector shows the failure is not degenerate. Because Eqs. (19)-(20) are the only bridge from the virtual-node construction to the restricted proximity margin in Eq. (21), Theorem 1 is not established by this proof.","section":"Appendix B, Eq. (19)"},{"comment":"The proof silently assumes an alignment between global target clusters and intersections of local clusters: it treats C_hat_i as equal to mu_q_hat for every i in T_q, which requires that all members of T_q fall into the same local cluster in every participant, i.e., T_q is exactly an intersection of local clusters of the form intersection_l T^l_{r_l}. This condition is not stated in Theorem 1, and it is not shown to follow from local center separation or from the restricted proximity condition in Definition 1. If a local cluster cuts across two global clusters, the virtual node for that intersection combines points from different target clusters, and Protocol 3 line 17 assigns the whole intersection to one output cluster, causing unavoidable misclassifications. The theorem must either state this alignment explicitly as an assumption or bound the number of points contained in misaligned intersections.","section":"Theorem 1 and Appendix B, Eqs. (17)-(20)"},{"comment":"The paper claims that ||X - C_hat|| <= ||X - C|| for k_hat >= k 'since C_hat is the local optimal centers'. This does not follow for the spectral norm. k-means optimality is a statement about the Frobenius norm of the residual matrix, and a finer local clustering can reduce the sum of squared residuals while increasing the largest singular value of the residual matrix. This step is used to argue that the restricted proximity condition is a compromise between Definition 2 and the Kumar-Kannan condition, so the comparison needs either a corrected norm argument or a different definition of the quantities in Definition 1.","section":"Section 3.5, after Eq. (12)"}],"minor_comments":[{"comment":"The contribution bullet and the abstract state that the communication cost drops from O(n) to O(k^3), but Protocol 3 as written produces k_hat^L intersections; the O((Q+1)L k_hat^3) bound is for the tree variant described later in Section 3.4. Please qualify the complexity claim consistently.","section":"Section 1 and Section 3.4"},{"comment":"There are several typos and notation inconsistencies: 'changeling' in Section 1, 'Effenciency' in the Appendix E.3 heading, 'garph' in the Table 8 and Table 9 captions, inconsistent use of 'k-CAGC' versus 'kCAGC', and 'security aggregation' versus 'secure aggregation'.","section":"Throughout"},{"comment":"In Protocol 2, line 26, d^m_{i,r} should be d^j_{i,r}; in Protocol 3, line 7, the participant performing the intersection should be P_L, not P_l.","section":"Protocol 2 and Protocol 3"},{"comment":"The Pubmed row for L = 4, k_hat = k reports 65.61 +/- 5.43, an order-of-magnitude larger standard deviation than the neighboring entries in the table; this outlier deserves a remark or a check.","section":"Table 2"},{"comment":"The setting with split graph structures is described only for two participants; the text should state how the common graph filter G is computed when participants do not share the same Laplacian.","section":"Appendix D"}],"recommendation":"major_revision","confidential_remarks":"The experimental work is solid, but the theoretical contribution in its current form cannot support the paper's central claim. I would be willing to reconsider after the proof is repaired or Theorem 1 is restated with explicit alignment and residual-radius assumptions. I also note that the paper does not mention releasing code or data; given the implementation is described in detail, a code release would strengthen reproducibility."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version: kCAGC is a genuinely new protocol for clustering attributed graphs in a vertical federated setting, and the experimental work is decent. But the proof of Theorem 1 has a load-bearing gap, and I don't think the theoretical guarantee survives as written.\n\nWhat's new: the authors propose the first vertical collaborative attributed graph clustering method. Each participant runs k-means locally on its own feature block (after an SVD projection), then they exchange cluster IDs and form intersections. Each intersection is summarized as a weighted virtual node (local center), and the participants run a weighted k-means on these virtual nodes using secure aggregation to compute distances. The design is clean and the tree-based extension for many participants is a sensible way to keep the communication cost polynomial in the number of local clusters rather than exponential. The restricted proximity condition they introduce is a reasonable compromise between the Kumar-Kannan and Awasthi-Sheffet conditions.\n\nWhat it does well: the experiments are honest and reasonably thorough. On Cora, Citeseer, Pubmed and Wiki, kCAGC reaches accuracy close to the centralized AGC baseline, and it beats models trained on isolated data. They actually implemented the protocol in C++ with GMP and report runtime across LAN and WAN, which is more than many papers in this area do. The privacy analysis is standard but at least it engages with the threat model.\n\nThe soft spot is the theory. In Appendix B, inequality (19) claims that for i = argmin of distance to the virtual center, || |T_q|(X_i - \\hat{\\mu}_q) || <= || (X - \\hat{C}) u ||, which then gives ||X_i - \\hat{\\mu}_q|| <= (1/sqrt(n_q)) ||X - \\hat{C}||. This is false. The left side is the norm of a single row difference scaled by n_q; the right side is the norm of the sum of residuals over T_q. There is no general bound of that form. Even if you add the missing alignment assumption that all members of a global cluster share the same local cluster assignment in every participant, the inequality can fail — a simple example with four points on the unit circle around the origin shows the RHS is about 0.707 while every point is at distance 1 from the center. So the theorem's conclusion does not follow from the stated assumptions. This is a real gap, not a typo, because this inequality is the key step that connects the virtual nodes to the proximity condition needed for Lemma 1. The paper would need either a stronger assumption (e.g., a bound on the maximum row norm of the residual matrix for each cluster) or a different proof strategy.\n\nThere are smaller issues: no released code, no comparison to classical secure multi-party k-means, and some notational sloppiness in the complexity analysis (k vs \\hat{k}).\n\nWho should read this: people working on privacy-preserving graph clustering and vertical federated learning. The protocol idea is worth knowing even if the proof is broken. Deserves a serious referee and a major revision. I'd send it to review, but I would not let the current Theorem 1 stand.","headline":"A genuinely new vertical collaborative graph clustering protocol with honest experiments, but the proof of Theorem 1 rests on a false inequality, so the main theoretical guarantee is unproven.","tokens_in":26581,"tokens_out":4673,"would_cite":false,"duration_ms":48011,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H30","68T05","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that vertical collaborative attributed graph clustering can match centralized accuracy by building virtual nodes from intersections of local clusters, and proves a misclassification bound under a restricted proximity…","keywords":["attributed graph clustering","collaborative learning","vertical federated learning","k-means","secure aggregation","graph filter","proximity condition","communication efficiency"],"falsifier":"Construct a two-participant dataset with $k=2$ global clusters in $\\mathbb{R}^2$ where participant 1 sees only x-coordinates and participant 2 only y-coordinates, arranged so each participant's local k-means with $\\hat{k}=2$ puts half of each global cluster into the same local cluster; running kCAGC with $\\hat{k}=k$ then should produce intersections containing both global clusters, so if the misclassification rate drops far below the centralized k-means rate on the full 2D data, the alignment premise behind Theorem 1 has failed.","tokens_in":1489,"feed_emoji":"🕸️","tokens_out":4619,"duration_ms":91958,"temperature":0.7,"pith_summary":"The paper is trying to establish that attributed graph clustering can be done collaboratively when each participant holds different features of the same nodes, without ever pooling the data. The method's central bet is that global clusters appear at the intersections of local clusters: if each participant can cluster its own feature block, the overlap patterns of those local clusters reveal where the global clusters are. The paper proves a theorem to this effect under a \"restricted proximity condition,\" and supports it with experiments showing accuracy close to centralized methods while cutting the number of expensive secure aggregations from depending on the number of nodes to depending only on the number of clusters and participants.","feed_headline":"Intersecting local clusters enables private graph clustering","feed_subtitle":"Protocol cuts secure aggregations from node count to cluster count, matching centralized accuracy on four public datasets.","key_machinery":"The central object is the intersection of local clusters: each participant's k-means output partitions the shared node set into $\\hat{k}$ local clusters, and the protocol intersects these partitions across participants to produce candidate groups whose centers become weighted \"virtual nodes.\" The restricted proximity condition is the paper's assumption that these intersections align with the global target clusters closely enough that the virtual nodes inherit the classic proximity condition used in centralized spectral-norm clustering analyses, so the centralized misclassification lemma can be applied to them unchanged.","core_discovery":"The paper claims that in a vertically partitioned collaborative setting, the global clustering problem can be solved almost as accurately as centralized clustering by communicating only local-cluster memberships rather than raw features. Each participant runs k-means on its own filtered feature block, the intersections of these local cluster families form a small weighted set of virtual nodes, and secure aggregation over those virtual nodes reproduces the centralized k-means result. Theorem 1 states that with 10-approximate initialization, local center separation, and the restricted proximity condition, at most $(L\\epsilon + O(1)Lc^{-4})n$ nodes are misclassified when each participant has $\\epsilon n$ local 1-bad nodes, and all nodes are correctly assigned when $\\epsilon = 0$. The paper also claims this reduces secure aggregations from $O(nk)$ per iteration to $O((Q+1)L\\hat{k}^3)$, and experiments show accuracy comparable to centralized attributed-graph clustering and better than baselines trained on isolated data subsets.","pith_inferences":["A direct extension would be to verify the restricted proximity condition empirically on real datasets, since the paper's experiments do not measure the fraction of local 1-bad nodes that the theorem's bound depends on.","The one-time exchange of node IDs could be made fully private with private set intersection; the paper notes record linkage can be done this way but does not analyze the combined protocol.","Because accuracy is non-monotonic in the number of local clusters, an adaptive selector for $\\hat{k}$ would likely improve both accuracy and communication cost in practice.","The intersection-of-local-clusters mechanism is not inherently graph-specific and may transfer to other center-based clustering problems in vertical collaborative settings."],"forward_implications":["Communication complexity becomes independent of dataset size: kCAGC needs $O((Q+1)L\\hat{k}^3)$ secure aggregations instead of $O(Qnk)$, so large-sample datasets train in seconds to minutes.","If each participant's local clustering has no 1-bad nodes, Theorem 1 says all nodes are assigned correctly; with $\\epsilon n$ local 1-bad nodes per participant, at most $(L\\epsilon + O(1)Lc^{-4})n$ nodes are misclassified.","Participants never share raw features: the protocol exchanges only node IDs within local clusters and securely aggregated sums of virtual-node centers.","Experiments on four public attributed graphs show accuracy comparable to centralized clustering and better than semi-supervised baselines trained on isolated data subsets.","Training time depends on the number of participants and local clusters rather than on the number of nodes, so a nearly ten-times-larger dataset trains in roughly the same time as smaller ones."],"supporting_citations":[{"why":"Supplies the proximity condition, center separation, and Lemma 1 that the proof of Theorem 1 extends to the collaborative setting.","marker":"[36]"},{"why":"Supplies the original distribution-independent clustering condition and the 10-approximation initialization used by Protocol 1.","marker":"[37]"},{"why":"Supplies the secure aggregation protocol that lets participants sum distance contributions without revealing individual feature values.","marker":"[31]"},{"why":"Supplies the adaptive graph convolution and filtering approach that turns attributed graph clustering into k-means on filtered features, and serves as the main centralized baseline.","marker":"[38]"},{"why":"Supplies the prior horizontal collaborative clustering method whose communication-reduction idea motivates reducing the sample space via local centers.","marker":"[35]"}],"fun_headline_variants":["Private graph clustering via local cluster intersections","Intersecting local clusters shrinks secure aggregation","Collaborative graph clustering matches centralized accuracy","Secure aggregation cost drops from nodes to clusters","Local cluster intersections outperform isolated baselines"],"cache_read_input_tokens":28672,"weakest_assumption_plain":"Every global cluster must be nearly an exact intersection of one local cluster from each participant; if local clusters cut across global cluster boundaries, the virtual nodes mix different global clusters and the weighted k-means on virtual nodes cannot recover the central partition.","fun_headline_variants_meta":{"raw":{"variants":["Private graph clustering via local cluster intersections","Intersecting local clusters shrinks secure aggregation","Collaborative graph clustering matches centralized accuracy","Secure aggregation cost drops from nodes to clusters","Local cluster intersections outperform isolated baselines"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001372,"raw_usage":{"total_tokens":5543,"prompt_tokens":910,"completion_tokens":4633,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":4570}},"tokens_in":526,"tokens_out":4633,"duration_ms":33921,"temperature":1.0,"reasoning_tokens":4570,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:40:06.258389+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a two-participant dataset with $k=2$ global clusters in $\\mathbb{R}^2$ where participant 1 sees only x-coordinates and participant 2 only y-coordinates, arranged so each participant's local k-means with $\\hat{k}=2$ puts half of each global cluster into the same local cluster; running kCAGC with $\\hat{k}=k$ then should produce intersections containing both global clusters, so if the misclassification rate drops far below the centralized k-means rate on the full 2D data, the alignment premise behind Theorem 1 has failed.","supporting_citations":[{"cited_title":"Improved spectral-norm bounds for clustering,","cited_arxiv_id":null,"evidence_quote":"Supplies the proximity condition, center separation, and Lemma 1 that the proof of Theorem 1 extends to the collaborative setting."},{"cited_title":"Clustering with spectral norm and the k-means algorithm,","cited_arxiv_id":null,"evidence_quote":"Supplies the original distribution-independent clustering condition and the 10-approximation initialization used by Protocol 1."},{"cited_title":"Practical secure aggre- gation for privacy-preserving machine learning,","cited_arxiv_id":null,"evidence_quote":"Supplies the secure aggregation protocol that lets participants sum distance contributions without revealing individual feature values."},{"cited_title":"Attributed graph clus- tering via adaptive graph convolution,","cited_arxiv_id":null,"evidence_quote":"Supplies the adaptive graph convolution and filtering approach that turns attributed graph clustering into k-means on filtered features, and serves as the main centralized baseline."},{"cited_title":"Heterogeneity for the win: One- shot federated clustering,","cited_arxiv_id":null,"evidence_quote":"Supplies the prior horizontal collaborative clustering method whose communication-reduction idea motivates reducing the sample space via local centers."}],"review_version":1}