提出新基准与重建方法，解决图数据碎片化下的隐私泄露问题。
Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction
- 构建局部图基准LoGraB，模拟真实碎片化场景
- AFR方法在9个数据集上7个领先，抗噪性强
- 适用于联邦学习等隐私敏感场景的图分析
图神经网络在关系数据上表现优异，但传统评估假设图全局可得，与实际不符。在联邦图学习、分布式系统和隐私敏感场景中，图数据常为局部化、碎片化、带噪声且存在隐私泄露风险。本文提出统一框架，引入LoGraB（局部图基准），通过三种策略和四类控制（邻域半径$d$、谱质量$k$、噪声水平$σ$、覆盖率$p$）将标准数据集分解为碎片化基准。支持图重建、局部节点分类和跨片段链接预测，并引入岛内凝聚力机制。提出AFR（自适应保真度重建）方法，通过保真度度量（包含间隙-截断稳定性比与结构熵）评估碎片质量，采用RANSAC-Procrustes对齐、自适应拼接与捆绑调整组装碎片。不强制重构单一全局图，而是恢复大而忠实的岛屿。理论证明了热核边恢复性、Davis-Kahan扰动稳定性及有界对齐误差。建立谱泄漏命题：在谱隙假设下，一旦共享足够特征向量，多项式时间贝叶斯恢复可行，补充了AFR的确定性保证。九个基准实验显示，LoGraB揭示模型在碎片化下的真实性能，AFR在7/9数据集上取得最优F1，且在$(ε,δ)$-高斯差分隐私下（$ε=2$），仍保持原无防护时75%的F1。匿名代码已公开。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) excel on relational data, but standard benchmarks unrealistically assume the graph is centrally available. In practice, settings such as Federated Graph Learning, distributed systems, and privacy-sensitive applications involve graph data that are localized, fragmented, noisy, and privacy-leaking. We present a unified framework for this setting. We introduce LoGraB (Local Graph Benchmark), which decomposes standard datasets into fragmented benchmarks using three strategies and four controls: neighborhood radius $d$, spectral quality $k$, noise level $σ$, and coverage ratio $p$. LoGraB supports graph reconstruction, localized node classification, and inter-fragment link prediction, with Island Cohesion. We propose AFR (Adaptive Fidelity-driven Reconstruction), a method for noisy spectral fragments. AFR scores patch quality via a fidelity measure combining a gap-to-truncation stability ratio and structural entropy, then assembles fragments using RANSAC-Procrustes alignment, adaptive stitching, and Bundle Adjustment. Rather than forcing a single global graph, AFR recovers large faithful islands. We prove heat-kernel edge recovery under a separation condition, Davis--Kahan perturbation stability, and bounded alignment error. We establish a Spectral Leakage Proposition: under a spectral-gap assumption, polynomial-time Bayesian recovery is feasible once enough eigenvectors are shared, complementing AFR's deterministic guarantees. Experiments on nine benchmarks show that LoGraB reveals model strengths and weaknesses under fragmentation, AFR achieves the best F1 on 7/9 datasets, and under per-embedding $(ε,δ)$-Gaussian differential privacy, AFR retains 75% of its undefended F1 at $ε=2$. Our anonymous code is available at https://anonymous.4open.science/r/JMLR_submission
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。