基于傅里叶变换反推连通图热扩散初始顶点的技术问询

核心结论 #

存在可反推t=0时刻热扩散起始位置的方法（可构造对应函数），但可行性依赖于图的结构和热扩散模型的特性，傅里叶变换（图傅里叶变换）是有效的解决工具之一。

离散图上的热扩散模型 #

首先明确连通图上的离散热扩散方程：
$$\dot{u}(t) = -L u(t)$$
其中：

• $u(t) \in \mathbb{R}^n$是n个顶点的温度向量
• $L$是图的拉普拉斯矩阵（对称半正定矩阵）

若t=0时热扩散从第$i$个顶点起始，初始温度向量为$u(0) = e_i$（第i位为1，其余为0的单位向量），则时刻$T$的温度分布为：
$$u(T) = e^{-LT} e_i$$
这里$e^{-LT}$是矩阵指数，由拉普拉斯矩阵的特征分解推导而来。

基于图傅里叶变换的反推思路 #

利用图傅里叶变换（GFT）的特性，拉普拉斯矩阵可分解为$L = U \Lambda U^T$，其中：

• $U$是正交特征向量矩阵（列向量为L的特征向量）
• $\Lambda$是特征值对角矩阵（对角元为L的特征值$\lambda_1 \leq \lambda_2 \leq ... \leq \lambda_n$）

矩阵指数可表示为：
$$e^{-LT} = U e^{-\Lambda T} U^T$$

反推步骤：

1. 对已知的时刻$T$温度向量$u(T)$做图傅里叶变换：
   $$\hat{u}(T) = U^T u(T)$$
2. 利用矩阵指数的逆操作，计算初始向量的傅里叶变换：
   $$\hat{e}_i = e^{\Lambda T} \hat{u}(T)$$
   这里$e^{\Lambda T}$是对角矩阵，对角元为$e^{\lambda_k T}$
3. 对$\hat{e}_i$做逆图傅里叶变换，得到$e_i$：
   $$e_i = U \hat{e}_i$$
4. $e_i$中非零元素对应的顶点即为起始顶点。

关键限制与实际处理 #

• 图的对称性问题：若图存在对称性（如完全图、环图），不同顶点起始的热扩散在时刻$T$可能产生完全相同的温度分布，此时无法唯一确定起始顶点。
• 噪声干扰：实际数据存在噪声时，无法得到精确的$e_i$，需通过最小二乘法寻找最匹配的起始顶点：
  $$i = \arg\min_j | u(T) - e^{-LT} e_j |_2$$
• 构造反推函数：可直接将上述过程封装为函数$f(u_T)$，输入时刻$T$的温度向量，输出最可能的起始顶点索引。

内容的提问来源于stack exchange，提问作者Radwa Adel