对于图表$G=(V,E)$，回想一下未加权的拉普拉斯算子是$L:=D^\top D$， 在哪里$D\in\{-1,0,1\}^{|E|\times|V|}$ 是将相邻顶点值减去到边上的图形“梯度”算子。

我正在编写一种算法，可以一次向图形添加/删除边。在每次迭代中，我需要申请$L^+$到几个向量，其中$L^+$是的 Moore-Penrose 伪逆$L$对于当前图表。我可以重新计算$L$及其在每次迭代中的伪逆，但这在计算上是昂贵的！

添加/删除边缘$E$将等级 1 更改为$L$. 所以，看起来我们可以更新一个稀疏分解（Cholesky？LDLT？）$L$并以此来加速应用$L^+$. 是否有易于使用的算法？

笔记：

我一直在努力应用标准的 Matlab 调用。挑战包括以下事实：$L$总是有一个空空间（常量函数），$G$可能不是连通图，删除边是 rank-1 但减法更新。

如果你有一个指向现有代码库的指针，那就加分吧！

本文展示了在添加边时如何更新拉普拉斯算子的伪逆。但它没有显示删除边缘时要做什么（也许这是一个简单的扩展，但我没有看到它！），并且伪逆是我想避免存储的密集矩阵。