请教ChebNets具有K局部性的引理证明及求和式含义

一、引理背景与核心结论 #

在谱图卷积学习中，ChebNets采用切比雪夫多项式定义图滤波器，替代传统卷积方式。支撑其K局部性的引理核心结论为：图拉普拉斯矩阵L的k阶切比雪夫多项式Tₖ(L)对应的图滤波器具有k局部性——即对任意顶点v，滤波器输出仅与距离v不超过k的顶点特征相关。

二、引理的证明过程 #

切比雪夫多项式的递推定义为：

• T₀(x) = 1
• T₁(x) = x
• Tₖ(x) = 2xTₖ₋₁(x) - Tₖ₋₂(x)

将其映射到图拉普拉斯矩阵L上，用数学归纳法证明局部性：

1. 基例验证：
   • k=0时，T₀(L)=I（单位矩阵），仅顶点自身特征参与计算，局部性为0；
   • k=1时，T₁(L)=L，图拉普拉斯矩阵的非零元素仅对应相邻顶点，局部性为1，符合结论。
2. 归纳假设：假设k-1阶和k-2阶切比雪夫多项式Tₖ₋₁(L)、Tₖ₋₂(L)分别具有k-1和k-2的局部性。
3. 归纳推导：根据递推式Tₖ(L)=2LTₖ₋₁(L)-Tₖ₋₂(L)，L与Tₖ₋₁(L)相乘等价于对Tₖ₋₁(L)的结果做邻域扩展（局部性从k-1延伸至k），再减去局部性为k-2的Tₖ₋₂(L)，最终Tₖ(L)的局部性不会超过k，即满足k局部性。

三、关键求和式的推导与含义 #

你提到的证明中的求和式（形式为\sum_{m=0}^k \binom{k}{m} \binom{k+m}{m} (-1)^m）：

推导逻辑 #

该求和式源自切比雪夫多项式的展开化简，结合生成函数与二项式定理推导：
切比雪夫多项式的生成函数为：
\frac{1 - xt}{1 - 2xt + t²} = \sum_{k=0}^∞ Tₖ(x) tᵏ

将生成函数按幂级数展开，通过系数匹配或递推化简，可得到该求和式是k阶切比雪夫多项式的另一种系数表达形式——本质是对递推过程中各阶邻域贡献的权重进行合并计算。

核心含义 #

这个求和式直接对应图滤波器中不同邻域距离的顶点权重：每一项\binom{k}{m} \binom{k+m}{m} (-1)^m代表距离顶点v为m的顶点的权重系数，求和后得到Tₖ(L)矩阵中对应位置的元素值。由于当m>k时系数为0，因此只有距离不超过k的顶点会对输出产生贡献，这从数值层面佐证了切比雪夫多项式的k局部性。

内容的提问来源于stack exchange，提问作者Maryam Riazi