图信号恢复:抽样策略的基本限制

  摘要: 本文构建了三种采样策略(均匀采样,实验设计采样和主动采样)下恢复平滑图形信号,近似带限图信号的恢复理论基础。然后,我们根据这三种抽样策略,对近似带限涂信豪的最大风险进行了极小下限描述,表明主动抽样不能从根本上优于实验设计的抽样。我们提出了一种恢复策略,将均匀采样与实际设计的采样进行比较。由于提出的恢复策略很适合统计分析,因此我们得出每个抽样策略的精确均方误差。为了研究收敛速度,我们引入两种类型的图表,发现1)提出的恢复策略达到最优利率;和2)实验设计的抽样基本上胜过了Type-2类图的统一抽样。为了验证我们提出的恢复策略,我们在五个具体的图表上进行测试:具有k个最近邻居的环形图,Erdo“-Re'nyi图,随机几何图,小世界图,发现实验结果与拟议理论吻合良好。本文还提供了有关使用图形进行半监督学习的时间和原因的综合解释。

  关键词: 主动采样,实验设计采样,半监督学习,图形信号处理,信号恢复。

一、 简介

  来自不同来源的大量数据,包括在线社交网络,引用网络,生物网络和物理基础设施,已经激发了一个新兴的研究领域,用于分析图数据[2],[3]。图形上的信号处理是用复杂的非规则结构分析高维数据的理论框架[4],[5]。它将传统的离散信号处理扩展到具有这种结构的信号,通过图形信号,图形信号,通用概念和经典离散信号处理到图形信号处理的工具对其进行建模。最近的工作涉及图形信号的采样[6] - [8],图形信号的恢复[9],[10],图形信号的表示[11],[12],图上的不确定性原理[13] 14],图形字典构造[15],半监督学习与图[16],[17],图去噪[18],[19],社区检测和聚类图[20] - [22]基于滤波器组[18],[23],[24]和基于图的变换[25] - [28]等。

  在本文中,我们考虑采样和恢复的经典信号处理任务[29],[30]。 作为连接序列和功能的桥梁,经典抽样理论表明,如果采样率足够高,则可以从其采样序列中完全恢复带限信号。 在香农60年来,出现了许多新的常规和非常规的采样和恢复框架,以恢复具有不同特性的信号。 例如,有限的创新采样率考虑了每单位时间具有有限数量自由度的信号的采样和恢复[31],[32],压缩感测考虑了稀疏信号或信号的采样和恢复,可以是 由一些相干冗余的字典[33],[34]稀疏地表示,子空间采样考虑了来自子空间的信号的采样和恢复[35],[36]。

  图形信号的采样和恢复的兴趣在过去几年有所增加[8],[37] - [40]。 在[9]中,作者提出了一种算法来恢复在均匀采样下具有小变化的图形信号,并且具有重新识别误差的上限。 在[6],[7]中,作者提出了图形信号的采样理论,并在实验设计的采样下显示了带状图信号的完美恢复。 扩展包括快速分布式算法[41],[42],局部加权测量[43],局部聚合[44]和播种节点的传播[45]。

  在本文中,我们关注平滑图形信号,即每个节点的系数与其邻居系数相似的信号。我们提出了一种新的平滑图形信号,被称为近似带限,并构建理论模型,以了解此类均匀采样,实验设计采样和主动采样的采样和恢复。我们提出一种恢复策略来比较统一抽样和实验设计抽样;这种恢复策略是低频组件的无偏估计,并且在图结构的某些假设下达到最佳收敛速率。在精神上,我们的工作遵循以前的工作,研究了被动和主动采样从样本恢复功能的理论能力[46],[47];不同之处在于我们考虑离散设置并处理不规则结构。因为平滑的性质,主动采样,实验设计的采样和均匀采样具有统计学意义上的相同性能[46],[48]。然而,对于近似的带限图形信号,我们将看到,当实际采样实现与实验设计的采样相同的收敛速率时,实验设计的采样在图形不规则时基本上优于平均采样。

  为了验证恢复策略,我们在五个具体图表上进行测试:具有k个最近邻居的环形图,Erdo“-Re'nyi图,随机几何图,小世界图和幂律图,以及 表明实验结果与拟议理论相符。

  贡献:本文的贡献如下:我们提出

  1. 与现有类别的平滑图形信号相关的新类平滑图形信号;
  2. 三种抽样策略下的恢复误差最小下限;
  3. 恢复策略,在两种特定类型的图形上实现最佳的收敛速度;
  4. 图形结构的统计分析; 和
  5. 综合解释实时设计抽样的时间和原因,并为图形的半监督学习提供参考。

  论文概要:第二部分简要回顾图形信号处理; 第三部分回顾平滑图形信号模型并制定采样和恢复策略。 我们提出了第四节中恢复误差的最小下限以及在第五节中进行均匀采样和实验设计采样的恢复策略。第六部分结合了前面两节的结果,并显示了二次恢复的最佳收敛速度 图形类型。 拟议的恢复策略在第五节已知的图表类别中进行了评估。 第八节总结了本文,并指出了未来的发展方向。

二、 图信号处理

  我们现在简要回顾图形上的信号处理[5],为所提出的工作奠定了基础。 我们考虑一个图G =(V,A),其中V = {v0,...,vN-1}是节点集合,并且A∈RN×N是图移位,或加权值邻接矩阵,表示离散版本的图形。 节点vi和vj之间的边缘权重Ai,j是它们之间的底层关系的定量表达,如相似性,依赖性或通信模式。 为了保证移位的信号被正确缩放以便与原始信号进行比较[49],我们对图形移位进行归一化,使得|λmax(A)| = 1.节点顺序固定后,图形信号被写为向量

zJmmK4O - 图信号恢复:抽样策略的基本限制

  A的约旦分解是

Ys3fTNT - 图信号恢复:抽样策略的基本限制

  图信号处理的常用符号表示为

TtLSS22 - 图信号恢复:抽样策略的基本限制

  其中A的广义特征向量形成矩阵V的列,U = V-1(每列的范数归一化为1),特征值矩阵Λ∈RN×N是相应特征值λ0的块二进制矩阵 ,λ1,...,λN-1(1 =λ0≥λ1≥...,≥λN-1≥-1)。 这些特征值表示图上的频率[49]。

  x∈RN的图形傅立叶变换是

jGjtY1o - 图信号恢复:抽样策略的基本限制

  图的傅里叶反变换是

xQjsLIi - 图信号恢复:抽样策略的基本限制

  其中vk是V的第k列? xk/hat是X/hat的第k个组成部分。矢量X/hat中的x表示信号在特征向量中的扩展,并描述图形信号x的频率分量。 逆图傅里叶变换通过组合图形频率分量重建图形信号。 一般来说,V不是正交的; 为了限制其行为,我们假设

iqqpWp1 - 图信号恢复:抽样策略的基本限制

  其中α1,α2> 0,即V是具有稳定性常数α1,α2的Riesz基 [29]。 当A表示无向图时,它是对称的,我们有U = VT,U和V都是正交的。 为了简单起见,我们考虑A在本文中表示无向图,即我们假设α1=α2= 1,但是所提出的图形信号模型和采样策略对于有向图同样适用。 注意,存在图形傅里叶变换的其他版本,基于不同的方法来校正邻接矩阵,例如图拉普拉斯矩阵的特征向量矩阵[4]; 我们提出的方法适用于图形傅里叶变换的所有版本。 表一列出了本文中使用的符号。

三、 问题建模

  我们现在回顾三类平滑图形信号,并显示它们之间的连接。 然后,我们描述感兴趣的抽样和恢复策略,将此工作与以前关于图形抽样理论的工作相结合。

   A. 图信号模型

  当每个节点的系数与其邻居的系数相似时,我们认为图形信号是平滑的。 我们先前在[6],[9]中定义了两类平滑图形信号。

  定义1:图形信号x∈RN在参数η≥0的图A∈RN×N上是全局平滑的

QKzNtaC - 图信号恢复:抽样策略的基本限制

  用GSA(η)表示这一类图形信号。

  在上面,Ax是x的移位版本,x-Ax给出一阶差[49]。 由于我们对图移动进行归一化,使得|λmax(A)| = 1

4j51NCy - 图信号恢复:抽样策略的基本限制

  定义2:一个图信号x∈R^N在图A∈R^NxN是近似带限的,当对于参数K∈{0,1,2,……,N-1},当图的频率陈芬满足下式时成立:

qBr1Bub - 图信号恢复:抽样策略的基本限制

  用BLA(K)表示这一类图形信号。请注意,[6]中的原始定义只是要求x hat要k阶稀疏,意思是x hat不一定是低通。这里,我们修正频率的排序,并要求带通图形信号为低通。 以下定理详细说明了这两个类之间的关系。

  定理1:对于任何K∈{0,1,...。 ,N - 1},BLACK)是当η≥(1-λK-1)2时GAS(η)的子集。

  定义3:当存在一个K∈{0,1时,一个图形信号x∈RN对于参数β≥1和μ≥0的图A∈RN×N近似带限。。 ,N-1},使得图形傅里叶变换 x满足

eEwfLJu - 图信号恢复:抽样策略的基本限制

  近似带限类允许在第一K个频率分量之后的尾部,其形状和衰减由μ和β控制; μ越小,尾部允许的高频分量的能量越少,β越大,这些高频分量的能量的惩罚越高。 ABLA(K)的类与以前文献[51]中的椭球约束类似,其中所有频率分量在约束条件下被考虑; 换句话说,ABLA(K)对低频组件的限制较少。 许多真实图形信号表现出近似带限性质; 例如,图1和图2显示了美国各地的温度读数和整个明尼苏达州的风速都是近似带状图形信号。我们发现,当表示实际图形信号时,近似带限制类别比带宽类更强大。

  以下定理详细描述了ABLA(K,β,μ)和GSA(η)之间的关系。

  图1:美国的温度读数是近似的带状图形信号。 在第十个频率分量(黑色虚线)之后,能量衰减快。 (一个温度计。 (b)频率内容。

   B. 采样和恢复策略

  我们考虑采样和恢复的过程如下:我们从具有噪声的图形信号x∈RN采样m个系数,以产生噪声采样信号y∈Rm

mdIS0wn - 图信号恢复:抽样策略的基本限制

  其中噪声服从N(0,σ2Im×m),M =(M1,...,Mm)表示称为采样集的样本索引序列,其中∈{0,1。。 。,N - 1},| M | = m,采样算子Ψ是从RN到Rm的线性映射,定义为【11】

wQCPuoH - 图信号恢复:抽样策略的基本限制

  然后我们插值y得到x *∈RN,它可以精确地或者近似地恢复x。

  我们考虑三种不同的抽样策略:

  1. 均匀采样意味着样本索引从{0,1,...中选择。。 ,N - 1};
  2. 实验设计抽样意味着样品索引可以预先选择; 和
  3. 主动采样意味着可以将样本索引作为样本点的函数进行选择,并且直到该情况收集的样本,即仅依赖于{Mj,yj} j <i。

  很明显,均匀采样是实验设计的采样的一个子集,它也是主动采样的一个子集。 本文的目的是研究在恢复近似带状图信号时这三种采样策略的基本限制。 这项研究与许多现实世界的应用有关。 例如,在半监督学习中,数据集被建模为具有作为节点的数据样本和这些数据样本之间的相似性作为边缘的图。 与数据样本相关联的特征和标签形成近似带状图信号。 我们的目的是选择数据样本作为标记数据,并恢复未标记数据的标签。 采样策略有助于选择信息丰富的数据样本,并最大限度地减少恢复误差。 一些其他应用包括基于风速的路线规划[52],传感器位置选择[53]和压缩光谱聚类[54]。

四、采样策略的基本限制

  在本节中,我们研究了通过显示最小下限来恢复ABLA(K,β,μ)的三种抽样策略的基本限制。 我们通过遵循最小化决策规则并在所有可能的恢复策略中找到极小风险的紧密下限来实现[48]。 换句话说,我们尝试在最坏的情况下最小化恢复错误,并使用紧密的下限来描述这个极小错误。 我们首先引入一些符号[46]。

  定义4:对于恢复策略(x*,M)和向量x∈RN,恢复策略风险为:

c7FhlJQ - 图信号恢复:抽样策略的基本限制

  其中Ex,M是关于{xi,yi}i∈M的概率测度的期望值,d(x,x)是误差度量。 这里我们使用2范数规范|x-x|^2。 恢复策略的最大风险是supx∈RN R(x,M,x)。

  我们提出的下限将是形式

frM5dKT - 图信号恢复:抽样策略的基本限制

  其中inf是最小(最大下限),sup是上限(最小上限),m是样本数,m0∈N,c> 0是常数,φm是收敛到零的正序列,Θ 是所有恢复策略的集合。 序列φm^ 2表示为较低的收敛速率。

  最大风险的上限通常通过明确的恢复策略获得,如第五节所示。我们提供的上限将是形式

dLOxM4R - 图信号恢复:抽样策略的基本限制

  其中C>0是常数。 如果(9)和(10)都成立,那么φm被认为是最优收敛速度,没有恢复策略渐近超过所提出的收敛速度。 当谈到最优收敛速度时,我们用多项式来约束该序列,并形成以下形式的语句:给定γ1<γ<γ2,当且仅当m-γ2<φm时,收敛速度φ2m等于m-γ ^ 2 <m-γ1为n足够大

  注意,一般边界是用于任意图形,因此涉及取决于图形结构的参数; 给出图形结构,我们可以指定参数并显示明确的收敛速度,我们将在第六节中做。

  令V(2,K)为V的子矩阵,由V的第K至第(2K-1)列组成。

五. 恢复策略

  在上一节中,我们提出了三个抽样策略中的每一个的最小下限,并表明主动抽样不能从实验设计的抽样中获得更好的效果。 我们现在提出了统一采样和实验设计采样的恢复策略,并对其统计特性进行了评估。

   A. 算法

  为了以类似的方式分析统一抽样和实验设计抽样,我们考虑采样取样,统一了两种抽样策略。 抽样评分抽样意味着样本索引从与某些抽样得分成比例的重要性抽样分布中选出。 令{πi} Ni = 1是一组抽样分数,其中πi表示在每个随机试验中选择第i个样本的概率。 当每个节点的抽样得分相同时,我们得到统一的抽样; 当基于图形结构设计每个节点的抽样分数时,我们得到实验设计的抽样。

  对于ABLA(K),大部分能量集中在前K个频率分量中,并且可以通过使用图形信号近似恢复图形信号。 我们考虑以下恢复策略来通过将样本投影到由第一K个频率分量跨越的带限空间来估计这些频率分量。

  算法1:我们对图形信号进行m次采样。 每次,我们独立地选择一个节点Mj = i,j = 1,。。。 ,m,概率πi,并进行测量yMj。 令∈Rm×N为采样算子,V(K)∈RN×K为V的第k列,D∈RN×N为Di,i = 1 /√mπi的对角重标矩阵。 我们通过解决以下优化问题来恢复原始图形信号:

Zp7CPA7 - 图信号恢复:抽样策略的基本限制

  其中y是样本(7)的向量表示。

  我们称算法1为采样投影(SampleProj)算法,因为我们重新更新权重并将样本投影到带限空间上。 ΨTy∈RN通过零填充重新调整采样信号y∈Rm。重调整矩阵D2补偿采样中的不均匀权重,并从不同抽样得分中取样。术语ΨTΨD2ΨTy表示均衡和零填充样本。目标函数(11)使我们的估计和样本之间的距离最小化。解决方案(12)的直觉是,我们将均衡和零填充样本投影到由V(K)跨越的带限空间中以消除混叠。项U(K)ΨTΨD2ΨTy是前K个频率分量的无偏估计器,稍后将示出。因此,在期望中,恢复的图形信号x * SP是任何图形信号x的线性近似。当x是带限,x * SP完美恢复x,当x近似带限时,由于存在高频分量,x * SP有偏差。

   B. 统计分析

  我们通过提供偏差,协方差,均方误差(MSE)和最优采样分布来研究算法1的统计特性。

  以下引理表明,采样投影估计器是任何采样分数的前K个频率分量的无偏估计。

  引理1:具有带宽K和任意采样分数的采样投影估计器是前K个频率分量的无偏估计器。

5B2TLQs - 图信号恢复:抽样策略的基本限制

  其中x*是算法1的解。

  引理2给出了采样投影估计器的精确协方差。

  引理2:采样投影估计器x*的协方差具有以下属性:

pZZaXUS - 图信号恢复:抽样策略的基本限制

  其中Tr(·)是矩阵的迹,WC是对角矩阵,具有(WC)i,i =(x2i)+σ2)/(mπi)。

  定理4显示了采样投影估计器的精确MSE和上限。

  定理4:对于x∈ABLA(K,β,μ),令x*是具有带宽κ≥K的采样投影估计器。然后,

8hkLJZB - 图信号恢复:抽样策略的基本限制

  我们将支持文件中附录B中的引理1和理论4的证明合并。 主要思想来自于偏差方差折衷。 偏置项μ/(1 +κ2β)|| x || ^ 2来自高频分量,Tr(U(κ)WC V(κ))来自协方差。 定理4中的最后一个不平等来自放宽偏见项,省略常数,与抽样分数无关。 因此,优化采样分数的上限相当于优化精确的MSE。

  我们接下来研究基于均匀采样和实验设计采样的采样投影估计器的MSE。

  推论1:均匀采样的MSE上限为:

VzChXKv - 图信号恢复:抽样策略的基本限制

  上界只是指定了所有i的抽样分数为πi=1/N。对于实验设计的抽样,我们允许研究图形结构并设计样本索引。 在下面的推论中,我们通过最小化MSE的上限来显示采样投影估计器的一组最优抽样分数。

  推论2:具有带宽κ≥K的采样投影估计器的最佳抽样得分为

r1ttPx9 - 图信号恢复:抽样策略的基本限制

  MSE的相应上限为:

blmPv4g - 图信号恢复:抽样策略的基本限制

  证明:为了获得估计器的最优抽样分数,我们将定理4中给出的MSE最小化,并解决以下优化问题。

sfMZ0vf - 图信号恢复:抽样策略的基本限制

  目标函数是在定理4中导出的MSE的方差项。由于偏差项与采样分数无关,最小化方差项相当于最小化MSE。约束要求{πi} Ni = 1成为有效的概率分布。 拉格朗日函数是:

PWvjJjq - 图信号恢复:抽样策略的基本限制

  其中η0,ηi是拉格朗日乘数。 我们将拉格朗日函数的导数设为零

6JEOF5g - 图信号恢复:抽样策略的基本限制

  并获得最佳抽样分数

I8DHnnM - 图信号恢复:抽样策略的基本限制

  将最佳抽样得分Πi代入MSE(13)的上界,

bUWfxs8 - 图信号恢复:抽样策略的基本限制

  其中(a)从将最优抽样得分(14)代入MSE(13)的上限之后。

  我们看到最优采样得分包括信号和噪声之间的权衡。 实际上,我们不能访问x,因此需要近似每个xi和σ2之间的比率。 对于主动采样,我们可以收集反馈来近似每个信号系数xi; 对于实验设计的抽样,我们预先估计; 一种方法是使用图形结构来绘制x的形状。 我们首先使用柯西施瓦茨不等式来界定,

Fr4u73h - 图信号恢复:抽样策略的基本限制

  其中vi是V的第i行。因此,在上限中,我们在信号和噪声之间进行权衡:当信噪比(SNR) 2 /σ2小,近似最优抽样得分为

CmET6tI - 图信号恢复:抽样策略的基本限制

  这是V(K)的杠杆分数的平方根。 当SNR≤x≤ 2 /σ2大,近似最优抽样得分为

E25vF7B - 图信号恢复:抽样策略的基本限制

  对于近似的带限信号,当β大且μ小时,主能集中在第一K个频率分量中,vi2集中在vi(K)2中,其中vi,(K)是vi中的第一个K元素。 特别,

E3eWxjQ - 图信号恢复:抽样策略的基本限制

  在这种情况下,当SNR≤x≤ 2 /σ2大,近似最优抽样得分为

WcuETBd - 图信号恢复:抽样策略的基本限制

  这是V(K)的平均·分数。

六、 收敛的最优速率

  在本节中,我们介绍两种类型的图表,并表明提出的恢复策略在两者之间达到最佳收敛速度。 类型1图形模型规则图,其中相应的图形傅立叶基数不稀疏,元素具有相似的幅度; 示例是循环图和最近邻图[56]。 由于能量均匀地分布在图形傅里叶基础上,每个元素包含相似量的信息; 对于这样的图,实验设计的采样与均匀采样类似。 类型2图形模型不规则图形,其中相应的图形傅立叶基数是稀疏的,元素不具有相似的幅度; 示例是小世界图和无尺度图[3]。 由于能量集中在图形傅立叶基础中的几个元素,这些元素更有信息,应该被选择。 对于这样的图表,实验设计的抽样优于统一抽样。

   A. 1型图

  定义5:当它的图形傅立叶基数满足以下方程时时,图A∈RN×N是类型-1。

tctJEKf - 图信号恢复:抽样策略的基本限制

  对于1型图,V中的元素具有大致相似的幅度,即能量均匀分布在V上。

   B. 2型图

  `定义6`:当它的图形傅里叶基数满足以下形式时,图A∈RN×N是类型2

NrvzVXh - 图信号恢复:抽样策略的基本限制

  其中vi,T是V和T的第i列中的第T个最大元素 N是一些常数。

  类型2图表要求V的每个列向量近似稀疏。 当我们从V取几列形成一个子矩阵时,子矩阵中的能量集中在子矩阵的几行中。 这相当于抽样得分近似稀疏。 模拟显示,星形图,无尺度图和小世界图大致落入这种类型的图形中。

七、实验结果

  在本节中,我们在五个具体的图表中验证了提出的恢复策略:环形图,Erdo“ - Re'nyi图,随机几何图,小世界图和幂律图。 基于图形结构,我们粗略地将它们标记为1型或2型,然后对于每种类型,我们将基于均匀和实验设计的抽样对所提出的恢复策略的性能进行比较。 对于实验设计的抽样,我们使用V(K)的杠杆分数(在无噪声情况下约为最优)和V(K)的杠杆分数的平方根(在嘈杂的情况下约为最佳)。 在实验中,图形傅立叶基础是邻接矩阵的特征向量矩阵。 当图形傅立叶基数是图拉普拉斯矩阵的特征向量矩阵时,我们发现类似的结果。

   A. 仿真图形

  我们现在介绍在我们的实验中使用的五个图,每个图具有10,000个节点。

  具有k个最近邻居的环形图:环形图是每个节点连接到其k个最近邻居的图形。我们使用环形图,其中每个节点连接到正好四个最近的邻居。特征向量与离散余弦变换相似,能量均匀扩散到V中的每个元素[56];这是一个Type-1图。图。图3示出了环形图的一些性质:图3(a)显示了曲线图(为了简化可视化,仅显示20个节点,并且具有足够的缩放,可以清楚地看到每个节点连接到正好四个最近的邻居;图3(b)显示了集中在4,如图所示;图3(c)显示V(20)的杠杆分数的直方图,当SNR较大时,它们是最佳抽样得分注意,我们设置带宽K = 20,以显示图中傅立叶变换矩阵的低频带,我们看到杠杆分数集中在10-4左右,这意味着每个节点具有相同的可能性被选择,均匀采样大约是最优采样策略。

  Erdo˝s-Re'nyi图:Erdo˝s-Re'nyi图是一个随机图,其中每对节点以某种概率连接[3]。 我们使用一个图,其中每对节点以0.01的概率连接,也就是说,每个节点有100个邻居的预期。 图。 图4显示了Erdo“-Re'nyi图的一些属性。 图。 图4(a)显示了曲线图(为了简化可视化,仅显示了100个节点); 图。 4(b)显示了如预期的那样集中在100左右的度数的直方图; 和图。 图4(c)示出了V(20)的杠杆分数的直方图,其是SNR大时的最佳采样得分。 我们看到杠杆率集中在10-4左右; 这意味着每个节点具有相同的可能性,并且均匀采样近似是最佳采样策略,类似于环形图。 基于上述,Erdo˝s-Re'nyi图形大约是Type-1图形。

  随机几何图:随机几何图是一个空间图,其中每个节点在框[0,1] d中分配随机协调,当两个节点之间的距离在给定范围内时,边缘出现[57] 。我们使用位于框[0,1] 2中的图形,当欧几里德距离小于0.03时,两个节点连接。图。图5示出了随机几何图的一些性质:图5(a)为曲线图;图。图5(b)显示了按照预期集中在30左右的度数的直方图(这符合给定适当参数的前一个参数,随机几何图形的度数分布与Erdo“Re”相同) nyi图[57]);图。图5(c)示出了V(20)的杠杆分数的直方图,它们是SNR大时的最佳采样得分;和图。 5(d)显示了对数量表上的杠杆分数的直方图。我们看到杠杆分数的直方图是偏斜的;这意味着在采样期间,几个节点比其他节点更为重要,并且具有更高的可能性被选择。在[57]中,作者表明,随机几何图和Erdo“-Re'nyi图的聚类属性是不同的。提出的抽样分数通过图形邻接矩阵的分解来捕获这些群集属性。基于上述,随机几何图形大约是2型图。

  小世界图:一个小世界图是一个图,其中大多数节点不是彼此的邻居,而是可以通过少量跳数从任何其他节点到达(步骤)[2],[3]。众所周知,包括社交网络,互联网的连接性和基因网络在内的许多现实世界图都显示出小世界的图形特征。我们使用WattsStrogatz模型生成的图,其中首先构建环形图,然后以0.01%概率重新布线边缘。图6显示了小世界图的一些属性:图6(a)显示了图形图;图6(b)示出了集中在2附近的度数的直方图(由于重新布线,几个节点具有6个邻居);图6(c)显示了V(20)的杠杆分数的直方图,它是当SNR较大时的最佳抽样得分;图6(d)显示了对数量表的杠杆分数的直方图。我们看到杠杆分数的直方图是偏斜的;这意味着在采样过程中,几个节点比其他节点更重要,并且与随机几何图形类似,具有更高的可能性被选择。基于上述,小世界图大约是2型图。

  幂律图:幂律图是一个图,其中一个节点的连接越多,接收新链接的可能性越大,被称为优选附件图[2],[3]。众所周知,优先附件图的度数分布遵循幂律。我们使用从Baraba'si-Albert模型生成的图形,其中一个新的节点被添加到网络中。每个新节点以与现有节点已经具有的链路数成正比的概率连接到一个现有节点。图7示出了小世界图的一些属性:图7(a)显示了图形图;图7(b)显示了倾斜程度的直方图,明显地遵循幂律;图7(c)显示了V(20)的杠杆核心的直方图,它是SNR较大时的最佳抽样得分;图7(d)显示了对数量表的杠杆分数的直方图。我们看到杠杆分数的直方图是偏斜的;这意味着在采样过程中,几个节点比其他节点更为重要,并且具有更高的可能性,与随机几何图形和小世界图形类似。基于上述,幂律图近似为2型图。

  类型:基于我们对每个图的图形傅立叶变换矩阵的观察,环图和Erdo“-Re'nyi图近似满足作为1型图的要求,而随机几何图 小世界图和幂律图近似满足要求为2型图。 因此,我们预期实验设计的采样与环形图和Erdo“-Re'nyi图的均匀采样具有相似的性能,而优于随机几何图形,小世界图和功率的均匀采样 - 图表。

   B. 图信号仿真

  对于每个图A,我们通过以下两个步骤生成1,000个图形信号:我们首先生成图形频率分量

abEK3fq - 图信号恢复:抽样策略的基本限制

  然后我们将其归一化为具有单位范数,并获得x = V x。很明显,x∈ABLA(K,β,μ),其中K = 10和β变化为0.5和1.在采样期间,我们模拟噪声c〜 N(0,σ2)将样本大小m从1,000改变为20,000,并将σ2从低噪声水平10-4(x2 / c2 = 100)改变为高噪声水平0.02(x 2 / c 2 = 0.5)。 在恢复期间,我们按照建议设置带宽K = max(10,m1 /2β+ 1)

   C. 结果

  我们比较四个抽样策略,包括统一采样(蓝色),基于杠杆分数的抽样(橙色),基于杠杆分数的抽样平方根(纯粹)和基于度的抽样(红色)。 注意,最后三个采样策略都属于实验设计的采样,因为它们是基于图的结构设计的。 如第V-B节所示,当SNR较大时,基于乐观分数的抽样近似为最优,当SNR较小时,基于杠杆分数的抽样的平方根近似为最优。 我们还使用度数作为抽样分数,因为以前的作品表明邻接矩阵的最大特征向量通常将大部分质量定位在高度节点上[58],[59],这意味着学位和杠杆率之间的高度相关性。 我们通过使用MSE评估恢复性能,

IQs0KpW - 图信号恢复:抽样策略的基本限制

  其中x *是恢复的图形信号,x是原始图形信号。图8,9,10,11和12分别显示了环形图,Erdo“s-Re'nyi图,随机几何图,小世界图和幂律图的模拟结果。我们总结下面的重点。

  1. 所有采样策略在环形图和Erdo“-Re'nyi图上都是相似的,匹配推论4。
  2. 实验设计的抽样比随机几何图,小世界图和幂律图匹配推论6进行统一抽样。特别是对于小世界图和幂律图,均匀采样比实验设计抽样。
  3. 当噪声水平低时,杠杆分数取样优于所有其他采样策略。
  4. 当噪声水平较高时,基于杠杆分数的抽样的平方根超出了所有其他抽样策略。
  5. 基于度的抽样优于均匀抽样,因为它与基于杠杆分数的抽样相关,但对于小世界图,基于度的抽样仍然比基于杠杆分数的抽样差。
  6. 当β大时,恢复性能更好,因为对于大多数带状图形信号,较少的能量集中在高频带。
  7. 当σ2较小时,由于噪音较小,恢复性能较好。
  8. 度数分布不是实验设计抽样优于统一抽样的可靠指标。 Erdo“-Re'nyi图和随机几何图的度分布是相似的,但是实验设计的抽样仅在随机几何图上优于单一抽样。 这意味着在设计样本时提供的一阶信息是不够的。
   D. 讨论

  图形傅立叶基数对于理解图形结构至关重要。例如,给定图形傅立叶基础,理论3表明,主动采样不会从根本上超越实验设计的采样,而推论6显示,实验设计的采样在类型2图上基本上胜过均匀采样。换句话说,图形傅立叶基数对于选择样本至关重要。

  对于不规则(2型)图,使用实验设计的抽样来选择锚点可以从根本上辅助半监督学习(对于常规的第1类图形来说不是真实的),这是一种用于训练具有标记和未标记数据的分类器的技术。半监督学习假设未标记的数据可以提供分布信息来构建更强大的分类器[60]。半监督学习的许多算法基于从给定数据集[60]构建的图形,通常通过将每个节点建模为数据样本,并且如果其特征之间的距离在给定范围内,则通过边缘连接两个节点,这与几何图形的构建类似。基于相邻节点具有相似标签的假设,半监督学习从图形结构扩展标签数据到未标记数据的概率,并根据这些标签概率对未标记的数据进行分类。虽然在一些作品[61],[62]中训练数据被统一和随机地选择,但在其他方面,算法被设计为适应于结构[63],[64],这在理论上等同于我们提出的实验设计的抽样。换句话说,实验设计的抽样被隐含地使用,而不能清楚地表达何时和为什么它的工作;另一方面,本文提供了一个全面的解释,为什么实验设计的抽样通过显示三个抽样策略的下限和上限来帮助半监督学习。

八、结论

  为恢复新近提出的平滑图形信号,近似带宽信号,在均匀采样,实验设计采样和主动采样等方面概括了带状图信号的类别,构建了理论基础。我们表明,实验设计的采样和主动采样具有相同的基本限制,并且可以优于不规则图形上的均匀采样。我们提出一种恢复策略并分析其统计特性。我们表明,提出的恢复策略在两种特定类型的图表上达到最佳收敛速度。为了验证恢复策略,我们对五种特定类型的图进行测试:具有k个最近邻居的环形图,Erdo“ - Re'nyi图,随机几何图,小世界图和功率 - 法律图,并表明实验结果与拟议理论相符。这项工作还提供了一个全面的解释,为什么实验设计的抽样工作的半监督学习与图表,并显示图表傅里叶基础在分析图形结构的关键作用。