使用稀疏和密集输入时，Scipy最小生成树结果不一致

Question

我有一个图的邻接矩阵，它是用稀疏的 scipy scr 矩阵存储的。当我调用 scipy.sparse.csgraph.minimum_spanning_tree 函数时，我生成的稀疏数组中非零值太少（少于 V-1）。

我在用更小的数据集做测试时（只是为了测试），发现当我把稀疏输入矩阵转换成密集矩阵时，这个函数能够计算出一棵树。

下面是我用来重现这个情况的代码，以及我的输入稀疏矩阵：

import scipy as sp
from scipy.sparse.csgraph import  minimum_spanning_tree
from scipy.sparse import csr_matrix
sparse_matrix = sp.sparse.load_npz('sparse_matrix.npz')

MST = minimum_spanning_tree(sparse_matrix)
print(f"weight of MST: {MST.data.sum()}")

print(f'non-zero edges {MST.size}')

dense_matrix = sparse_matrix.todense()

MST2 = minimum_spanning_tree(dense_matrix)

print(f"weight of MST2: {MST2.data.sum()}")

print(f'non-zero edges {MST2.size}')

sparse_from_dense = csr_matrix(dense_matrix)
MST3 = minimum_spanning_tree(sparse_from_dense)

print(f"weight of MST3: {MST3.data.sum()}")

print(f'non-zero edges {MST3.size}')

输出结果是：

weight of MST: 1399.3271604776382 
non-zero edges 459 
weight of MST2: 1653.5667477846146 
non-zero edges 698 
weight of MST3: 1653.5667477846146 
non-zero edges 698

有没有人知道发生了什么，以及如何解决这个问题？因为预期的顶点数量确实是 698，我相信密集输出是正确的。

我尝试寻找其他方法来稀疏表示矩阵并从稀疏输入计算最小生成树，但没有找到其他替代方案。

Answer 1

我们先来看看这个函数的文档，看看它是如何处理稠密矩阵和稀疏矩阵的不同之处。

在说明部分，它提到：

这个程序使用无向图作为输入和输出。也就是说，如果图中的 graph[i, j] 和 graph[j, i] 都是零，那么节点 i 和 j 之间没有连接。如果其中一个不为零，那么这两个节点之间是通过这两个值中最小的非零值连接的。

当用户输入稠密矩阵时，这个程序会失去一些精度。稠密矩阵中小于 1E-8 的元素会被四舍五入为零。为了避免这个问题，用户最好尽量输入稀疏矩阵。

一种可能性是这个稀疏矩阵中包含小于 1E-8 的数据值。我们来检查一下：

>>> sparse_matrix = sp.sparse.load_npz('sparse_matrix.npz')
>>> print(sparse_matrix.data[sparse_matrix.data < 1e-8])
[0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]

确实如此——它里面有一堆零。在稀疏矩阵中，隐式零和显式零是有区别的。隐式零是指那些没有出现的矩阵元素，而显式零是指那些存在且被设置为零的矩阵元素。

在 SciPy 的稀疏矩阵中，这两者在大多数情况下是等价的。但在 minimum_spanning_tree() 函数中，显式零和隐式零是有区别的。

• 隐式零表示两个节点之间没有边连接。
• 显式零表示两个节点之间有一条权重为零的边。

这给我们提供了一种解决问题的方法：使用 eliminate_zeros() 将显式零转换为隐式零。

import scipy as sp
from scipy.sparse.csgraph import  minimum_spanning_tree
sparse_matrix = sp.sparse.load_npz('sparse_matrix.npz')

sparse_matrix.eliminate_zeros()

MST = minimum_spanning_tree(sparse_matrix)
print(f"weight of MST: {MST.data.sum()}")
print(f'non-zero edges {MST.size}')

这样就能得到你想要的结果，而不需要先转换为稠密矩阵。