摘要
我们通过在邻接矩阵上进行迭代特征向量估计的视角,研究边微分隐私(DP)条件下的层次化谱图聚类。我们提出了一种具有微分隐私性的递归谱框架,其中每个二分类划分通过对诱导的邻接子矩阵应用秩一有噪声幂方法来获得。在每次迭代中,精心校准的高斯噪声被注入到矩阵-向量乘法中,在累加隐私核算下(涵盖幂迭代和递归层次级别),保证(ε, δ)-边DP,同时保持经典幂方法的基本收敛性质。我们对所得到的有噪声迭代提供了非渐近分析,通过特征向量估计误差的显式界来刻画隐私与精度之间的权衡。具体而言,我们量化了噪声方差、迭代次数、特征间隙和层次深度如何共同影响每次递归划分的精度以及整体聚类性能。在合成网络和真实世界网络上的实证评估验证了理论预测,并证明所提方法在合理的隐私预算下能够实现强大的多尺度聚类性能。


