我不确定您的问题是否容易回答，但我会尝试提供一种直觉。我不是非负矩阵分解的专家，所以我无法解释那里的联系。

让我们将注意力限制在具有个顶点我假设低秩是指邻接矩阵的低秩。这些属性是从这里得出的这是一个表征低秩图：$G$$n$

• 没有顶点的图是唯一排名为 0 的图
• 完全二分图是唯一具有秩 2 的连通图
• 完整的三方图是唯一具有秩 3 的连通图

已知秩在子图之间保留如下：

• 如果 H 是 G 的诱导子图，则。$rank(H) \leq rank(G)$
• 令，其中是 G 的连通分量，则$G = G1 \cup G2 \cup··· \cup G_n$$G_1, G_2,...,G_n$$rank(G) = \sum_i^n rank(G_i)$

由于完整的图具有秩，因此它遵循。$n$$largest \_clique(G) \leq rank(G)$

平均图表的排名是多少？考虑这个简单的随机图模型：为每一对顶点翻转一个公平的硬币以确定它们之间是否存在边。已经表明具有非常高的等级​​的概率。$G$$G$$n$

这向我表明，低秩图是局部稀疏的或具有密集连接的组件但有很多孤立的顶点。然而，随机选择的图可能是满秩的。