学习总结超图理论第一章——基本概念我最早产生必须把超图理论认真啃一遍的念头是在做社交网络分析的时候。当时我用普通图建模用户之间的关注关系图里的每条边表达的都是两个人之间有联系可现实里的关系很少这么干净——比如一个微信群组十几个人因为同一个项目聚在一起这种一对多甚至多对多的群体连接用普通图表达起来就非常别扭得引入星型节点、超边模拟之类的各种绕路操作。后来我翻到一本讲超图理论的旧教材才意识到这个领域其实一百多年前就有了框架只是这些年随着超图神经网络、高阶关系分析重新火了起来。这篇就把第一章节的基础概念做个梳理给同样从图论转过来的朋友当个引子。超图Hypergraph简单说就是普通图的推广。普通图里一条边只能连接两个顶点超图里一条边可以连接任意多个顶点。这个概念本身不复杂但它的数学结构、表示方式、分类方法以及引申出来的各种变体都是后续所有算法和应用的基础。不管你是做图神经网络、组合优化、数据库查询优化还是研究社会网络里的群组行为第一章的内容都是绕不开的底层逻辑。1. 为什么学完普通图论还不够超图解决的恰好是多元关系问题1.1 普通图的表达瓶颈在哪里先回想一下普通图Graph的定义一个图 G (V, E)V 是顶点集合E 是边的集合其中每条边 e {u, v} 恰好连接 V 中的两个顶点。这个定义之所以统治了计算机科学这么久是因为它足够简洁也足够契合大量二元关系的场景——比如路网里两个路口相连、社交网络里两个人互相关注、电路里两个元件相连接。但问题恰恰出在恰好两个这个约束上。真实世界里的关系经常是多元的、群体性的。拿我们最熟悉的引文网络打比方一篇论文引用另一篇论文这个是二元关系没错可用普通图去表达一篇论文同时引用了多篇论文构成的文献集合这个集合本身有什么内部关联普通图就表达不出来了。再拿线下活动举例一场研讨会可能同时有十个人参加这十个人之间未必两两认识但他们共同参与了同一个事件这个共同参与的群体关系普通图根本没办法直接建模。1.2 超图定义的核心动作把边从二元变成任意元超图理论做的其实是一个非常自然的推广动作把一条边只能连接两个顶点这个限制去掉允许一条边连接任意数量的顶点。形式化定义如下超图 H (V, E)其中 V 是一个非空有限集合称为顶点集E {e₁, e₂, ..., eₘ} 是 V 的非空子集构成的集合称为超边集或简称为边集。这里的每一个 eᵢ 可以称为一条超边hyperedge。普通图里 e {u, v} 是一个二元子集超图里 e {v₁, v₂, ..., vₖ} 是一个 k 元子集其中 k ≥ 2也可以允许 k 1后面细说单点边的特殊含义。你可以把边这个字重新理解为联系或者连接而不再是一条线段。我自己的理解方式是普通图的边描述的是两两配对的关系超图的边描述的是一组人共同参与某件事的关系。1.3 第一个例子一个最简单的超图长什么样为了后面所有概念能落地我先固定一个小例子贯穿全文。设V {v₁, v₂, v₃, v₄, v₅}E {e₁, e₂, e₃}其中e₁ {v₁, v₂, v₃}e₂ {v₂, v₃}e₃ {v₄, v₅}这个超图里e₁ 连接了三个顶点e₂ 连接了两个顶点e₃ 连接了两个顶点。注意它依然可以包含二元超边也就是说普通图其实是超图的一个特殊情况——当所有超边大小都为 2 时超图就退化成了普通图。这个退化关系请务必记牢很多超图算法在设计时都会先验证在普通图上的表现其实就是利用了这种包含关系。提示我建议刚开始学时就在纸上画一画超图。画法是用一个大圈或一条闭合曲线把所有属于同一条超边的顶点圈在一起而不是像普通图那样画一条线。这种视觉差异不是随意的它在后续理解关联矩阵、对偶结构时能提供很直观的支撑。2. 超图的基本参数阶、尺寸、秩、度该怎么看刚接触超图的人最容易犯的错是把图论里度的定义直接套过来。普通图里顶点度就是邻居数量超图里没这么简单。这一节我按我自己的记忆次序把最常用的几组参数列清楚。2.1 顶点数与超边数阶和尺寸超图的**阶order**就是顶点数记作 |V| n**尺寸size**指超边集合的大小记作 |E| m。这两个参数和普通图里的 node count / edge count 对应没什么玄机但是要注意很多教材里size这个词指代的不是超图整体大小而是单条超边里包含的顶点个数。为了避免混淆我更建议用阶指顶点总数用超边数指 |E|用超边大小指 |eᵢ|。2.2 秩与反秩描述超边大小的两极定义超图的**秩rank**为所有超边大小的最大值记作 r(H) maxᵢ |eᵢ|**反秩anti-rank**是所有超边大小的最小值记作 a(H) minᵢ |eᵢ|。还是拿上面的例子三条超边的大小分别是 3、2、2所以 r(H) 3a(H) 2。如果 a(H) r(H) k那说明所有超边大小都一样这种超图叫k-均匀超图k-uniform hypergraph。这个参数后续非常重要因为很多高斯随机超图模型、超图神经网络里的消息传递算子都默认研究 k-均匀超图通常取 k3目的是保持运算复杂度可控。普通图其实就是 2-均匀超图。2.3 度顶点在多少条超边里出现过超图里顶点 v 的**度degree**定义为包含 v 的超边数量d(v) |{ e ∈ E : v ∈ e }|。这个定义和普通图的邻居数量最大的区别在于超图里一条超边无论包含多少个顶点对其中每个顶点来说都只贡献 1 的度。所以在我们的例子里d(v₁) 1只出现在 e₁d(v₂) 2出现在 e₁ 和 e₂d(v₃) 2d(v₄) 1d(v₅) 1。注意超图里还有另一个叫邻居的概念即顶点的所有直接邻居的集合。在超图里如果两个顶点至少共同出现在一条超边里它们就互为邻居。但一个人可以有 50 个共同群组成员超图并不会因为你们在一个 50 人超边里就给你记 50 个邻居而对度只记 1。这个差异是很多人做图神经网络时踩过的坑后面我们讲邻接矩阵时还要再回来看它。2.4 两个基础恒等式度与超边大小的关系超图里最基础的一个恒等式是所有顶点的度之和等于所有超边的大小之和即∑_{v∈V} d(v) ∑_{e∈E} |e|这个式子的直观理解就是数两遍左边按顶点数它出现在几条边里右边按边数它包含几个顶点本质是在统计同一个顶点-超边二分关联关系的条目总数。这个式子虽然是常识级别但后面推导超图拉普拉斯矩阵、做谱聚类时你会发现它就是很多矩阵分解公式的底层支撑。还有一个常用的参数是平均超边大小即 (1/m) ∑|eᵢ|。在超图神经网络论文里经常看到处理高基数超边超大群组时效果变差其实就是平均超边大小太大导致消息传递过程过于平滑顶点特征相互平均过度差异性消失了。3. 用矩阵装下超图关联矩阵、邻接矩阵与对偶光在纸上画圈讲概念是不够的做研究、写代码、跑算法都得把超图送进矩阵里。第一章里最重要的三个表示方法我个人认为值得花整整一个下午去彻底弄清楚因为它们就是后续所有计算的入口。3.1 关联矩阵超图最诚实的画像设 H (V, E)顶点数为 n超边数为 m。定义n × m 的关联矩阵incidence matrixA其中的元素为A_{ij} 1如果顶点 vᵢ ∈ 超边 eⱼ否则 A_{ij} 0。沿用我们的例子关联矩阵长这样e₁e₂e₃v₁100v₂110v₃110v₄001v₅001注意这个矩阵的每一列实际上就是一条超边在顶点集合上的指示向量。每一行则刻画了一个顶点参与了哪些超边。这种列是边、行是点的布局直接引出了超图与二分图的天然联系把 m 条超边当作 m 个边顶点那么每个顶点与它所属的超边之间形成二分连接。所以有人会说超图的关联矩阵和一个二分图的邻接矩阵是同构的。3.2 邻接矩阵两种定义千万别混超图里邻接的定义有两种常见版本我当年看书时差点被绕晕。版本一顶点级邻接构造 n × n 矩阵 BB_{ij} 顶点 vᵢ 和 vⱼ 共同出现的超边数量。这个矩阵和普通图的邻接矩阵共享相同维度可以直接喂给很多现成谱聚类工具。但问题在于它丢失了高阶结构信息——它只记录两两共现频次却不再保留三个人同时在一组的群体信息。版本二超图拉普拉斯视角将超图视为加权普通图两条超边之间如果共享顶点就视为有连接权重用共享顶点的某种重叠函数计算。这种方式在超图分割问题里很常见。本质上是对超图做了一次投影降级从超图投影到普通图代价是信息丢失。我从实用角度给个建议如果做的是超图神经网络或者谱分析更推荐从关联矩阵出发构造归一化拉普拉斯而不是先投影成普通图——因为一旦投影高阶信息就回不来了。很多论文里对比实验显示保留了高阶关系的超图方法显著优于投影后的普通图方法很大一部分原因正是在这里。3.3 对偶超图把边和点的角色互换接下来是对偶这是超图理论里特别漂亮、也特别容易被忽略的一个构造。给定超图 H (V, E)它的对偶超图dual hypergraphH* (V*, E*) 定义如下V* E即对偶超图的顶点就是原超图的超边E* {e*ᵥ : v ∈ V}即原超图的每个顶点对应对偶超图的一条超边这条超边包含原超图中所有包含该顶点的超边。用通俗的话讲把关联矩阵的行和列互换行变成列列变成行得到的新关联矩阵对应的就是原超图的对偶。仍然拿例子说明原超图里 e₁ {v₁, v₂, v₃}e₂ {v₂, v₃}e₃ {v₄, v₅}。换过来以后对偶超图 H* 的顶点是 e₁、e₂、e₃超边是 v₁* {e₁}v₂* {e₁, e₂}v₃* {e₁, e₂}v₄* {e₃}v₅* {e₃}。对偶为什么重要因为现实里有很多问题天然是从边为中心视角出发的。比如数据库查询计划里一张表对应超图的一条边其实反过来更常见一条查询规则连接了多张表那你把表当成顶点、查询规则当成超边是一种建模把查询规则当成顶点、表当成超边是它的对偶建模。两类建模各有优势但对偶关系告诉我们它们本质上是同一个结构的两个观察视角。3.4 关联矩阵的瘦身加权超图怎么表示很多实际问题里顶点和超边的关联不只有属于/不属于两种状态。比如推荐系统里一个用户加入了一个兴趣小组但参与度有高有低这时可以在关联矩阵里把 1 换成权重值 w_{ij}比如参与次数、活跃程度。这就是加权超图weighted hypergraph。加权情况下度定义调整为 d(v) ∑_{e∋v} w(e)超边大小调整为 |e| ∑_{v∈e} w(v)。这一套在后续超图学习算法里几乎全是默认配置。4. 超图的分类命名均匀、简单、线性到底谁更常见接触超图文献时你会看到各种形容词k-uniform、simple、linear、conformal 等等。这不是术语堆砌它们是用来刻画不同场景下的结构假设的。这一节我把最重要的几个讲透。4.1 均匀超图k-uniform研究最充分的一类前面提过k-均匀超图的每条超边恰好包含 k 个顶点。从抽样的角度看它对应的是每个群体成员规模一致的理想化假设。为什么理论界偏爱均匀超图因为很多组合计数、随机化算法在超边大小固定的前提下才能给出漂亮的界限。比如著名的超图匹配问题在 k3 时的复杂度分析就比任意超边大小的情况清晰得多。普通图是 2-均匀超图这个前面说过。此外如果 k1那么每条超边都是单点集实际上就是一堆孤立顶点这个退化情况在某些覆盖问题里会作为边界条件出现。4.2 简单超图不允许包含关系和重复边**简单超图simple hypergraph**定义为不存在两条超边 eᵢ、eⱼ 满足 eᵢ ⊆ eⱼ 且 i ≠ j。换句话说没有任何一条超边是另一条超边的子集。为什么要加这个限制因为如果 e₁ ⊆ e₂那么在组合优化里越小的超边往往已经提供了更紧的约束大的超边在很多时候是冗余的。简单超图能避免很多理论分析里的退化情况同时也贴合很多实际数据清洗后的状态。注意简单超图不允许重复边同一条超边出现两次因为重复边本身是子集关系的一种特例。在项目里如果数据产生了重复超边建议先做去重否则后面度计算和拉普拉斯矩阵都会出现偏差。4.3 线性超图超边之间至多重合一个点**线性超图linear hypergraph**是比简单超图更强的一类它要求任意两条超边至多共享一个顶点。说起来有点绕举例子最清楚我们的例子中 e₁ {v₁, v₂, v₃} 和 e₂ {v₂, v₃} 共享了两个顶点 v₂ 和 v₃所以它不是线性超图。线性超图在很多场景下对应群体之间几乎没有重叠成员的结构比如会议室预订里每个会议超边参加的参会人集合之间只能有一个共同人比如协调员。谱聚类里线性性带来稀疏性计算效率会高很多。4.4 conformal 与 Helly 性质做了才知道的需求还有两个更进阶的术语在第一章通常是提一嘴但我会建议至少记住名字conformal 超图满足任意一组两两相交的超边都有公共顶点Helly 性质是凸分析与组合几何里非常经典的概念超图满足 Helly 性质指任意一组两两相交的超边集合它们的交集非空。这个概念在计算几何、覆盖问题和生物信息学里会反复出现学到后面章节回头看这两个定义你会感谢自己当初做了标记。5. 子结构视角部分超图、子超图与同构第一章后半部分通常会把注意力从单个超图转移到超图之间的关系。这一节我也不想简单罗列定义而是把几个容易混淆的概念放在一起比较。5.1 部分超图从边出发的子集部分超图partial hypergraph的定义最简单从 E 中选出一个子集 E ⊆ E那么 H (V, E) 就是 H 的部分超图。注意顶点集不变只删边不删点。这种结构在处理子集选择类问题时很自然——比如你有全部群组想挑出其中一部分来观察这些群组涉及的成员仍然全部保留在顶点集里。5.2 子超图从点出发但边的处理有讲究子超图subhypergraph的定义则要求先选顶点子集 V ⊆ V然后构造超边集 E { e ∈ E : e ⊆ V }即只保留那些完全包含在 V 里的超边。换句话说如果你选了一条跨越 V 边界的大超边那它在子超图里就直接被剔除了而不是被裁剪成只包含 V 内顶点的部分。这个细节特别重要。很多从普通图转过来的人会习惯性地以为子图就是保留部分顶点、同时把跨边切成内部边因为普通图里你总能这么干——一条边的两个端点要么都保留要么都不保留不存在一个端点在里面一个在外面时边还能半保留的情况。但超图里超边跨了边界你要么全要要么全扔这就是子超图定义的严格性。与子超图相对的概念是诱导子超图induced subhypergraph给定顶点子集 W ⊆ V诱导子超图 H[W] 的超边集是 E 中所有完全包含在 W 内的超边。它本质上是顶点集合 W 在 H 中的封闭投影。5.3 同构结构意义上的相同两个超图 H₁ (V₁, E₁) 和 H₂ (V₂, E₂) 称为同构isomorphic如果存在一个双射 f : V₁ → V₂使得对于任意超边 e ∈ E₁它的像集 f(e) { f(v) : v ∈ e } 都是 H₂ 里的一条超边反之亦然即映射 f 保持了顶点-超边隶属关系。划重点同构不要求顶点编号一致也不要求超边编号一致只要求结构一致。如果你把超图画在纸上能通过旋转、翻转、拉伸不撕裂超边集合变成另一个的样子它们大概率就是同构的。判断同构在算法上是困难问题超图同构的复杂度很高连判定普通图同构都还没找到多项式时间算法呢但第一章只需要理解它的定义和直觉。5.4 不变量判断两个超图不一样的快速方法和同构相伴的概念是不变量invariant即凡同构的超图必然共享的数值特征。最常见的不变量包括阶 n、超边数 m、秩 r(H)、度序列按降序排序后必须一致、超边大小多重集合比如有三条大小为 3 的超边。为什么要关心不变量实践中你不需要证明两个超图同构但你需要快速排除它们不同构的情况。比如你拿到两个超图一个的阶是 10另一个是 12那根本不用做同构测试直接判定不同构。在很多模式匹配、子图搜索系统里先用不变量做筛选能砍掉大量无效计算。6. 从基本概念回看应用为什么一块纯数学硬骨头这么有用第一章很容易给人一种这只是在推广图论的错觉。我自己的经验是学过基本概念后一定要立刻去应用场景里晃一圈哪怕只是表面看看也能帮助你把概念真正焊在脑子里。6.1 社交网络与群组检测社交网络里一个典型的超图建模方式把用户当顶点把微信群聊、讨论组、共同参与的线下活动分别当超边。一个人同时属于多个群组他在超图里的度就是参加群组数。这时候你想挖掘紧密社区就不能只看两两互关而是要看哪些群组之间的成员高度重叠。超图聚类、超图割这类算法的输入正是我们前面定义的关联矩阵。6.2 生物信息学里的复合物与通路蛋白质互相结合形成蛋白复合物一个复合物里往往有多个蛋白质它们之间不需要两两全都结合但作为一个功能单元共同出现。把蛋白质当顶点、每个复合物当超边这是超图在系统生物学里的经典用法。在这个场景下线性超图性质往往近似成立——同一个蛋白质很少同时出现在大量复杂复合物里这让算法可以大幅简化。6.3 超图神经网络中的消息传递这几年最热的方向之一。超图神经网络把顶点特征沿着超边做聚合一条超边内的所有顶点特征汇总成边级表示再分发回各个顶点。你注意一下这个过程里计算的核心就是关联矩阵 A 以及它的归一化版本。理解了第一章里顶点度和超边大小的定义再看下面的更新公式就不慌了X⁽ˡ⁺¹⁾ σ( D⁻¹ A W B⁻¹ Aᵀ X⁽ˡ⁾ )其中 D 是顶点度矩阵B 是超边大小矩阵A 是关联矩阵W 是超边权重矩阵。这个公式的每一部分其实就是把我们讲的度超边大小关联矩阵三个概念串在了一起。6.4 数据库查询优化中的超图建模一条 SQL 里 join 了多张表你可以把每张表看成一个顶点把一次 join 操作涉及的所有表看成一条超边于是整个查询计划就变成了一个超图。查询优化器需要在这个超图上做规划判断哪些 join 可以合并、哪些子表达式可以被共享。这时候第 5 节讲的子超图、部分超图概念会非常直观地展示出来因为查询优化里就是要反复做选取部分超边和在部分顶点上投影的操作。很多经典查询优化算法的理论基础其实都能在超图理论第一章里找到影子。7. 学习路上的几个坑与实用建议最后分享几个我实际学习过程中踩过的坑希望能帮你少走一点弯路。第一个坑是把超图投影成普通图后直接跑图算法。不是说不能这么做而是很多情况下一旦投影高阶信息就彻底丢了。如果你原本的问题是三个蛋白质共同形成复合物投影成普通图后你只能看到两两共现三个人到底是不是在同一复合物里就看不出来了。我的建议是优先保留超图结构只有在算法复杂度实在不可控时才做投影并明确记录丢失了什么信息。第二个坑是混淆超边的大小和顶点的度。在超图里它们是两个方向的统计大小是一条边里有多少顶点度是一个顶点在多少条边里。很多人做归一化时把这两个概念搞混写出的拉普拉斯矩阵和公式里的对不上号结果聚类效果差得离谱。每次用关联矩阵之前先写清楚哪个轴是顶点、哪个轴是超边可以省很多调试时间。第三个坑是忽略对偶视角。初学者大多只看顶点在中心的那一套定义可一旦你遇到以边为主体的问题比如规则集合、群组集合从对偶视角重新建模很多看似复杂的结构会变得清爽。我的习惯是每学一个新概念都问自己一句对偶视角下这是什么用不了几次你就会发现理解深刻了不少。第四个建议动手画、动手算。超图的视觉和矩阵表示之间有很强的对应关系我强烈建议你至少把这一节里的每张矩阵手算一遍不要只盯着公式看。结合 3.1 节的关联矩阵例子把它的行和列互换写出对偶超图再画出来看看比纯背诵定义有用得多。这一步做完后面学超图拉普拉斯、超图卷积完全是另一个难度。关于教材和参考资料我个人的体会是不要一上来就啃大部头的论文或者英文专著先找一找关于超图的基础讲义把定义、术语、矩阵表示过一遍做到看见一个超图能画出关联矩阵、能说出它的秩和度分布再到论文里查具体算法就顺了。这篇笔记对应的就是超图理论第一章最核心的内容可以作为你第一个下午的入门材料结合手边的编程环境边试边验证效果会更好。