ICML Workshop | 使用 Spanning Trees 的实际随机树生成

题目：Practical Random Tree Generation using Spanning Trees: Entropy and Compression 作者：Anonymous 来源：ICML Workshop 2023 文章地址：https://openreview.net/forum?id=o2gIz8GBPS 内容整理：杨晓璇 树状结构出现在许多与学习相关的问题中，其中最重要的是在图神经网络中。使用随机树生成器可以对这些数据结构进行建模。然而，关于能捕捉网络动态的随机模型的研究却很少。本文作者引入了随机 spanning trees 模型，它是一种基于已有网络拓扑生成树的随机树生成器。然后分析了该模型的香农熵，并找到了其上限。作者引入了一种通用方法来压缩使用 spanning trees 模型生成的树。文中证明，所提出的压缩方法会引入冗余，而对于较大的树来说，冗余趋近于零。

引言

尽管树的应用范围很广，但随机生成树的模型却很少。一个好的随机树生成模型可以用来建模和模拟现实世界中的许多现象，尤其是在学习应用中。现有的树模型非常有限，而且大多数模型仅依赖于树之间的均匀分布。其他模型只关注特定类型的树，如二叉树。关于随机树最详细的研究之一见（Drmota，2009），其中介绍并分析了几种随机树模型，分析的模型包括波利亚树、加尔顿-沃森树和简单生成树模型。然而，这些模型都有各自的缺点。例如，生成树中节点的数量可以无限增长，所需的树的大小不能通过模型中的参数来设定。

基于这些原因，在本文中作者引入了一种新型随机树生成器。作者将引入的模型称为 spanning trees 模型，它是根据实际应用中通常发生的情况建立的。随机树通常由底层网络拓扑结构生成。底层网络拓扑的 spanning trees 在机器学习中的决策树和随机森林分类器等领域有着广泛的应用。引入的模型不仅基于实际场景，而且非常灵活，可以模拟不同的情况，因为它的不同参数可以调整，以适应现实世界的许多场景。

在介绍了随机树的来源之后，接着研究其信息理论参数。之所以要进行这项分析，是因为随着节点数量的增加，树和一般图形数据结构都会变得过于复杂。因此，需要量化引入源的复杂性。此外，在实际应用中，这些树需要通过通信通道进行存储和/或通信。因此，还需要将研究上述树的最佳压缩方法。本文将研究单棵树的压缩，而不是树序列的压缩，特别是当节点数量增加时。这是因为在实际场景中，更经常面对的是单棵树而不是一串树，而当复杂性随着节点数量的增加而增加时，压缩是必要的。

本文接下来的内容安排如下。第 2 节介绍 spanning trees 模型。第 3 节，研究了 spanning trees 模型的熵边界。第 4 节提出了一种压缩方法。最后，本文得出结论并提出了未来的研究方向。

Spanning Trees 模型

在本节中，一种名为 spanning trees 模型的新型随机树生成模型将被介绍。在实际应用中，所使用的树通常是网络的生成树。网络路由就是一个例子。路由表通常用来存储网络中任意节点到其他节点的最短路径。可以看出，网络中一个节点的路由表本质上是一棵有根的树，根节点就是原节点。还可以看出，如果网络构成一个连通图，那么这棵有根树就是底层网络的生成树。因此，选择底层网络的随机生成树可以作为生成随机树的实用模型。本节将介绍提出的随机树生成器，即 spanning trees 模型。为此，将使用以下定义：

定义 2.1

随机图源：随机图源由一个集合

和一个定义在集合

上的概率分布

组成，前者包含了图源可能生成的所有图形，后者则显示了图源生成单个图形的概率。

定义 2.2

随机树源：随机树源由一个集合

和一个定义在集合

上的概率分布

组成，前者包括树源可能生成的所有树，后者显示了树源生成单个图形的概率。

假设有一个随机图源

。第一步是根据

的分布创建一个图

，然后

将有若干 spanning trees（也可以为零）。然后，从 g 的 spanning trees 中随机选择一棵生成树。这种随机选择可以根据任意分布进行，也可以取决于 g。图 1 显示了 spanning trees 模型的步骤。

图 1 Spanning trees 模型的步骤

很明显，spanning trees 模型是一个非常通用的模型，因为随机图生成器和生成树的选择方式都可以根据想要模拟的网络进行选择。为了很好地说明如何选择这些参数，作者引入了 ER 随机生成树。对于该模型的随机图生成器，本文使用 ER 模型。ER 模型是众所周知的最简单、最有效的随机图生成器之一。它在模拟现实世界中的流行病和进化冲突等现象时非常有效。

Spanning Trees 模型的熵

在本节中，将使用香农熵量化 spanning trees 模型的熵。所有对数都以二进制计算，因此得出的熵是以比特为单位的。将在计算中使用以下符号。

：随机图源的熵

：spanning trees 模型源的熵

本节的目标是求出

，假设

已知或可以轻松计算。可以写出下面的方程来求

：

假设输出树是从图的 spanning trees 中均匀选择的，那么可以写出下面的计算公式：

其中，总和取自使用随机图形生成器可以生成的所有连通图形，

表示图源的概率分布，

表示图

的 spanning trees 数量。要定义

，至少要有一棵 spanning tree，因此需要图形具有连通性。

以上公式表明，要计算 spanning trees 模型的熵，需要了解网络拓扑的基本分布以及每个图的 spanning trees 数量。不幸的是，一个图的 spanning trees 数量（通常称为其树数）并不容易找到。熵还取决于生成底层图拓扑的模型，而这个模型并不总是已知的。由于这些局限性，将重点讨论上一节介绍的 ER Spanning Trees。

在 ER Spanning Trees中，底层网络拓扑是通过 ER 模型创建的。在 ER 图中，每条边出现的概率为

，与其他边无关。由于 ER 模型不保证连通性，因此有些图甚至没有 spanning trees。此外，在给定一个图的节点和边的数量的情况下，没有封闭式公式可以计算该图的 spanning trees 数量。由于这些原因，找到的是 ER 图的 spanning trees 熵的上限，而不是其实际值。考虑有

个节点、参数为

的 ER 图。可以很容易地看出，使用这个模型创建的图的熵可以用下面的公式计算出来:

其中，

此外，假设一旦创建了 ER 图，就会选择以统一的方式选取其中的一棵 spanning tree。如果图中没有任何 spanning trees，则干脆不选择 spanning trees。为了找到以这种方式创建的 spanning trees 的熵的上限，使用格里米特上限公式。格里米特公式给出了图

的 spanning trees 数量上限。

利用这一上限，可以证明以下命题

命题 3.1：根据下面的不等式，ER spanning trees 的熵是有上界的。

命题 3.1 给出了使用 ER Spanning Trees 模型创建的树的熵的上限。图 2 展示了这一熵，并将其与图的熵和树的最大熵进行了比较。最大熵是根据均匀分布能使熵最大化这一事实计算得出的，

个节点上存在

个可能的标记树。对 100 个节点的 ER 图进行了模拟，并绘制了熵与 ER 参数

的函数关系图。然而，当

值较低时，上述公式提供了更严格的上限。

图 2 100 节点图的 ER 生 熵上限与 ER 参数 p 的函数关系

ER Spanning Trees 的压缩

在本节中，介绍 ER Spanning Trees 模型的通用和最优压缩算法。在此之前，需要定义一下这些方法中的通用性和最优性的含义。

最优性：香农曾指出，随机变量的熵为压缩该随机变量的平均代码长度提供了一个下限。因此，需要正在寻找一种压缩算法，其平均码字长度与手头随机树源的熵值足够接近。

通用性：生成随机树的模型需要设置特定的参数。例如，在使用引入 spanning trees 模型时，需要设置随机图生成器及其参数。通过为特定的随机树系列寻找通用压缩算法，实质上是在寻找无论模型参数如何都能达到最佳性能的压缩算法。例如，如果为 ER 随机生成树开发一种通用压缩算法，那么无论 ER 参数

如何，它都能达到最佳性能。

所有现有通用压缩算法的理念都是，由于分布参数未知，因此需要通过某种方式从数据中学习分布。例如，著名的 Lempel-Ziv 压缩算法系列使用字典来存储和学习随机变量可能出现的最常见模式。不过，这需要有一个随机变量序列，这样才能学习到最常见的模式。而在本文中，受关注的是压缩单棵树，而不是压缩一串树。在这种情况下，最优性转化为所有可能树的平均码字长度要足够接近源的熵。如果用

来表示有

个节点的树的预期码字长度，用

来表示有

个节点的树的树源熵，那么目标就是让压缩器满足以下条件:

为确保当

以及压缩需求增长时，压缩算法在单棵树上是渐进最优的。为了达到上述公式中的条件，同时又能使用通用压缩算法，主要方法是将每棵单棵树分解成随机变量的序列，然后对这些序列应用现有的通用压缩算法。作者提出了以下 ER Spanning Trees 编码方法。将编码过程分为两个步骤：从树的邻接矩阵中提取某些比特，然后压缩提取的比特序列。下面介绍比特提取过程。

比特提取：首先查看树的邻接矩阵，从节点 1 的连接对应行开始。这一行由 n-1 个比特（

）组成，其中每个比特表示节点 1 与树中其他节点之间存在连接。在提取过程中，提取所有这些比特。这样，知道了节点 1 在树中的所有连接。用随机变量

来表示这些连接的数量。这些

边中的每一对都会消除树中另一条边的可能性。例如，如果节点 1 同时连接到节点 i 和 j，那么树中就不可能存在 i 和 j 之间的连接。因此，有了节点 1 的连接，就无需在树的邻接矩阵中包含

位，能准确知道是哪些位。在描述了节点 1 的连接后，按照节点 1 的标签顺序来查看节点 1 所连接的节点。继续写下与这些行相对应的邻接矩阵的行，但不包括之前已经描述过的连接或由于所述的边消除过程而已知其状态的连接。这样，第二个节点与节点 1 的其他相邻节点连接的可能性就小于不可能性。继续这样做，解释每个节点的剩余连接，直到树中的所有节点都被覆盖。请注意，位提取可以应用于任何简单图，而不仅仅是 ER 图。用

展示从一棵树

中提取比特的过程。

使用

提取出邻接矩阵的某些比特后，只需将其输入通用压缩算法，如 Lempel-Ziv-Welch 算法。

命题 4.1：当 n 变为无穷大时，拟议压缩算法的冗余度趋于零。

无论

值和随机生成树的选择方式如何，它都趋向于零。因此，可以说所提出的方法是通用的，因为它不依赖于 ER 参数或随机生成树的选择过程。需要注意的是，所提出的压缩算法还可以通过比特提取过程的通用化来进一步推广。例如，该过程不一定需要从节点 1 开始，DFS 遍历也可以。目标是在未来研究一种可用于此目的的遍历方法的通用化。

结论

本文讨论了在涉及树数据结构的实际场景中使用新型随机树生成器的必要性。本文介绍了随机 spanning trees 模型，作为生成随机树的一种简单而实用的方法。本文还展示了如何通过选择适当的随机图生成模型和随机生成树的概率分布，使该模型适用于不同的场景。然后，介绍了 ER Spanning Trees，ER 模型在网络科学中有许多实际应用。接着，作者分析了所提模型的熵，并测量了它们的复杂度。在计算了 ER Spanning Trees 模型的熵作为其压缩的下限之后，接着介绍了该树族的通用压缩算法。结果表明，本文提出的压缩算法将使大型树的冗余度为零，而这正是需要对这些结构进行压缩的原因。为了继续这项工作，首先要考虑位提取过程中的其他树遍历算法，从而设计出一种保留查询的压缩算法。此外，作者还打算研究建议的压缩方法在网络路由协议中的应用。