在介绍图表示学习和图上深度学习的概念之前，有必要给出一些方法背景和背景知识。在这一章中，我们将对图上的传统方法（区别于深度学习）进行一个非常简短而有重点的回顾，并为更彻底地处理这些方法提供参考和指南。本背景章节还将从图分析中引入关键概念，为后面的章节奠定基础。
传统的基于图数据的分类方法遵循了深度学习出现之前流行的标准机器学习范式。在本节中，我们将首先介绍一些重要的节点级特征和统计量，然后，讨论如何将这些节点级别的统计量推广到图级别的统计量，并扩展到图上的核方法的设计。我们的目标将是引入各种启发式统计和图的属性，这些属性在应用于图的传统机器学习管道中经常被用作特征。
我们将用一个简单的社会网络——15 世纪佛罗伦萨婚姻网络（如下图）来激发我们对节点层面统计和特征的讨论。这一社会网络通常被来说明主导佛罗伦萨政治的美第奇家族（Medici，红色框）的权力上升。
原则上，我们下面讨论的属性和统计信息可以作为节点分类模型（例如，作为逻辑回归模型的输入）中的特征。
节点度（Node degree）
节点度通常用 d u d_u du 表示， u ∈ V u in mathcal{V} u∈V，其值为节点相关联的边数，也可以看作邻居数。
d u = ∑ v ∈ V A [ u , v ] d_u=sum_{v in mathcal{V}} mathrm{A}[u,v] du=v∈V∑A[u,v]
注意，在有向图和加权图的情况下，可以通过对上式中的行或列求和来区分不同的度数概念，如出度、入度。
在佛罗伦萨婚姻网络中，我们可以通过节点度来区分美第奇家族，因为他有最高的节点度（6）。然而它只比最接近它的家族（Strozzi，绿色）高出2，是否可能存在额外的或更有判别性的特征来帮助区分Medici家族和图的其他部分？让我们跟随后文的一探究竟。
节点中心度（Node centrality）
特征向量中心性（eigenvector centrality）考虑了节点邻居的重要程度，我们用递归的定义了节点的特征中心向量 e u e_u eu，其中节点的中心度与其邻居的中心度成正比。
e u = 1 λ ∑ v ∈ V A [ u , v ] e v , ∀ u ∈ V e_u = frac{1}{lambda}sum_{v in mathcal{V}} mathrm{A}[u,v]e_v,forall u in mathcal{V} eu=λ1v∈V∑A[u,v]ev,∀u∈V
其中， λ lambda λ 为常量，以 e 为节点中心度向量，将此方程改写为向量表示法，我们可以看到此回归式定义了邻接矩阵的标准特征向量方程：
λ e = A e lambda mathbf{e} = mathbf{A}mathbf{e} λe=Ae
特征向量中心性的一个观点是，它对一个节点在图上无限长的随机游走上被访问的可能性进行排序。这种观点说明可以通过考虑使用幂迭代来获得特征向量中心性值。也就是说，由于 λ lambda λ 是 A mathbf{A} A 的前导特征向量，我们可以通过幂迭代计算 e e e（为了简单起见，这里在幂迭代计算中忽略了归一化，但并不改变主要结果 ）：
e ( t + 1 ) = A e ( t ) mathbf{e^{(t+1)}} = mathbf{A}mathbf{e^{(t)}} e(t+1)=Ae(t)
如果我们从 e ( 0 ) = ( 1 , 1 , … , 1 ) T e^{(0)}=(1,1,ldots,1)^T e(0)=(1,1,…,1)T 开始幂迭代，我们可以看出在进行一次迭代后的 e ( 1 ) e^{(1)} e(1) 将包含所有节点的度。一般而言，当迭代次数 t ≥ 1 t≥1 t≥1 时， e ( t ) e^{(t)} e(t) 将包含到达每个节点的长度为 t 的路径数。因此，通过无限期地迭代这个过程，我们可以得到一个与节点在无限长路径上被访问的次数成正比的分数。 （在佛罗伦萨婚姻网络中，红色节点特征向量中心度的标准值为0.43，绿色为0.36。）
当然也有其他的中心性度量来刻画图的节点特征，例如介数中心度（betweeness centrality）——衡量一个节点在其他两个节点之间的最短路径上出现的频率，以及接近中心度（closeness centrality）——衡量的是一个节点与其他所有节点之间的平均最短路径长度，等等。
聚类系数（The clustering coefficient）
上面两个特征对于区分美第奇家族有明显作用，但对于其他节点呢？例如黑色框（节点度4，特征向量中心度0.29）和蓝色框（节点度3，特征向量中心度0.28）在这两种特征上非常相似，但这两个家族又有着明显区别（蓝色框分布在密集簇中，黑色框周围稀疏）。
这种重要的结构差异可以通过聚类系数的变化来衡量，聚类系数衡量了节点局部邻域中闭合三角形的比例。聚类系数的流行局部变体计算如下 [ Watts and Strogatz, 1998]：
c u = ∣ ( v 1 , v 2 ) ∈ E : v 1 , v 2 ∈ N ( u ) ∣ ( 2 d u ) c_u = frac{|(v_1,v_2)in mathcal{E}:v_1,v_2 in mathcal{N}(u)|}{(^{du}_2)} cu=(2du)∣(v1,v2)∈E:v1,v2∈N(u)∣
在佛罗伦萨婚姻图中，我们可以看到一些节点是高度聚集的，例如佩鲁齐（蓝色）节点的聚集系数为0.66，而其他节点如瓜达尼（黑色）节点的聚集系数为0。
闭合三角形，自我中心图和模体（Closed triangles, ego graphs, and motifs）
另一种看待聚类系数的方式（而不是作为局部聚类的度量）是统计每个节点的局部邻域内的闭合三角形的数量。更精确地说，聚类系数与一个节点的自我图（即包含该节点、它的邻居以及它的邻域内所有节点之间的边的子图）中，三角形的实际数量和三角形的总可能数量的比值有关。
这一思想可以推广到在节点的自我图中计算任意模体或图元的概念。也就是说，我们可以考虑更复杂的结构，比如特定长度的圈，而不是仅仅计算三角形，我们可以通过这些不同模体在他们的自我图中出现的次数来表征节点。事实上，通过这种方式考察节点的自我图，我们可以从本质上将计算节点级统计和特征的任务转换为图级任务。因此，我们现在将注意力转向这个图级别的问题。
上述提到的节点统计量和特征可用于节点分类任务，当我们要进行图级别的分类任务就需要考虑图核方法（为图设计特征或隐含核函数的方法）的一般分类。我们将只涉及这个大区域内的一小部分方法，重点关注提取显式特征表示的方法，而不是定义图之间的隐式核（相似性度量）的方法。
节点包（Bag of nodes）
定义图级特征最简单的方法就是聚合节点级统计信息。例如，可以根据图中节点的度、中心度和聚类系数计算直方图或其他汇总统计量。然后，这种聚合信息可以用作图级别的表示。这种方法的缺点是它完全基于局部节点级别的信息，并且会遗漏图中重要的全局属性。
威斯费勒-莱曼核（The Weisfeiler-Lehman kernel）
改进基本节点袋方法的一种方法是采用迭代的邻域聚合策略。这些方法的思想是提取节点级别的特征，这些特征包含的信息比它们的局部自我图更多，然后将这些更丰富的特征聚合成一个图级别的表示。 也许这些策略中最重要和最著名的是 Weisfeiler-Lehman (WL) 算法和 kernel [Shervashidze et al., 2011, Weisfeiler and Lehman, 1968]。WL 算法基本思想如下：
首先，为每个节点分配一个初始标签 l ( 0 ) ( v ) l^{(0)}(v) l(0)(v)。在大多数图中，这个标签只是简单的度，即 l ( 0 ) ( v ) = d v ∀ v ∈ V l^{(0)}(v)=d_v space forall v in V l(0)(v)=dv ∀v∈V。
接下来，通过对节点邻域内当前标签的多重集进行哈希，迭代地为每个节点分配一个新的标签：
l ( i ) ( v ) = H A S H ( { { l ( i − 1 ) ( u ) ∀ u ∈ N ( v ) } } ) l^{(i)}(v)=mathbf{HASH}({{l^{(i-1)}(u) space forall u in mathcal{N}(v)}}) l(i)(v)=HASH({{l(i−1)(u) ∀u∈N(v)}})
其中，"{{ }}"用来表示一个多重集，HASH 函数将每个唯一的多重集映射到一个唯一的新标签。
在运行 K K K 次重新标记（即步骤2）的迭代之后，我们现在为每个节点都有一个标签 l ( k ) ( v ) l^{(k)}(v) l(k)(v) 来概括其 K K K 跳邻域的结构。然后，我们可以计算这些标签上的直方图或其他汇总统计量作为图的特征表示。换句话说，WL 核是通过测量两个图的结果标签集合之间的差异来计算的。
基于图元和基于路径的方法 （Graphlets and path-based methods）
最后，正如在我们对节点级特征的讨论中，定义图上特征的一个有效且有力的策略是简单地统计不同小子图结构的出现情况，通常在这种情况下称为 Graphlets。形式上，Graphlet kernel 涉及枚举特定大小的所有可能的图结构，并统计它们在全图中出现的次数（下面是大小为 3 的各种图元示意图）。这种方法的挑战在于，计算这些 Graphlets 是一个组合困难的问题，尽管已经提出了许多近似方法。
除了枚举所有可能的图元外，另一种方法是使用基于路径的方法。在这些方法中，我们不是枚举图元，而是简单地检查图中出现的不同类型的路径，例如随机游走和最短路。
在上一节中，我们聚焦图的统计信息和核方法，这些信息对节点或图的分类任务是有用的，然而，它的局限性在于没有量化节点之间的关系。例如，上一节的统计量对于关系预测任务不是很有用，我们的目标是预测两个节点间是否存在边。如图 Figure2.3 所示（用于训练的全图和下采样图示意图。在训练模型或计算重叠统计量时，去除训练图中的虚边。该模型的评估是基于其预测这些滞留测试边存在的能力。）
在本节中，我们将考虑节点对之间邻域重叠的各种统计度量，这些度量量化了节点对之间的关联程度。 例如，最简单的邻域重叠度量只统计两个节点共享的邻居的数量：
S [ u , v ] = ∣ N ( u ) ∩ N ( v ) ∣ S[u,v]=|mathcal{N}(u) cap mathcal{N}(v)| S[u,v]=∣N(u)∩N(v)∣
其中， S ∈ R V × V S in R^{Vtimes V} S∈RV×V 表示汇总所有两两节点统计量的相似矩阵。给定一个邻域重叠统计量 S [ u , v ] S[ u , v] S[u,v]，一个常用的策略是假设一条边 ( u , v ) ( u , v) (u,v) 的可能性与 S [ u , v ] S[ u , v] S[u,v] 简单成正比：
P ( A [ u , v ] = 1 ) ∝ S [ u , v ] P(mathbf{A}[u,v]=1)propto S[u,v] P(A[u,v]=1)∝S[u,v]
因此，为了接近使用邻域重叠测度的关系预测任务，只需要设置一个阈值来确定何时预测边的存在。在图 2.3 中我们的希望是，在训练边上计算的节点-节点相似性度量将导致对测试边存在性的准确预测。
局部重叠统计量是两个节点共享的共同邻居数的简单函数， 即 ∣ N ( u ) ∩ N ( v ) ∣ |mathcal{N}(u) cap mathcal{N}(v)| ∣N(u)∩N(v)∣。例如，Sorensen 指数定义了节点-节点邻域重叠的矩阵 S S o r e n s o n ∈ R ∣ V ∣ × ∣ V ∣ mathbf{S}_{Sorenson}∈R^{| V | × | V |} SSorenson∈R∣V∣×∣V∣，其计算公式如下：
S S o r e n s o n [ u , v ] = 2 ∣ N ( u ) ∩ N ( v ) ∣ d u + d v mathbf{S}_{Sorenson}[u,v]=frac{2|mathcal{N}(u) cap mathcal{N}(v)|}{d_u+d_v} SSorenson[u,v]=du+dv2∣N(u)∩N(v)∣
它通过节点度的总和对共同邻居的计数进行归一化。某种类型的规一化通常是非常重要的；否则，对于度大的节点，重叠度量将高度偏向于预测边。 类似的方法还有 Salton 指数和 Jaccard 指数：
S S a l t o n [ u , v ] = 2 ∣ N ( u ) ∩ N ( v ) ∣ d u d v S J a c c a r d [ u , v ] = ∣ N ( u ) ∩ N ( v ) ∣ ∣ N ( u ) ∪ N ( v ) mathbf{S}_{Salton}[u,v]=frac{2|mathcal{N}(u) cap mathcal{N}(v)|}{sqrt{d_ud_v}}\ mathbf{S}_{Jaccard}[u,v]=frac{|mathcal{N}(u) cap mathcal{N}(v)|}{|mathcal{N}(u) cup mathcal{N}(v)} SSalton[u,v]=dudv 2∣N(u)∩N(v)∣SJaccard[u,v]=∣N(u)∪N(v)∣N(u)∩N(v)∣
还有一些方法超越了简单地计算共同邻居的数量，并试图以某种方式考虑共同邻居的重要性。 资源分配 (Resource Allocation，RA) 指数统计共同邻居的逆度，Adamic-Adar (AA) 指数使用度的倒对数进行类似的计算，计算方式如下：
S R A [ v 1 , v 2 ] = ∑ u ∈ N ( v 1 ) ∩ N ( v 2 ) 1 d u S A A [ v 1 , v 2 ] = ∑ u ∈ N ( v 1 ) ∩ N ( v 2 ) 1 log ( d u ) mathbf{S}_{RA}[v_1,v_2] = sum_{u in mathcal{N}(v_1)capmathcal{N}(v_2)} frac{1}{d_u}\ mathbf{S}_{AA}[v_1,v_2] = sum_{u in mathcal{N}(v_1)capmathcal{N}(v_2)} frac{1}{log (d_u)} SRA[v1,v2]=u∈N(v1)∩N(v2)∑du1SAA[v1,v2]=u∈N(v1)∩N(v2)∑log(du)1
这两种方法都赋予了度数较低的共同邻居更多的权重，直觉上共享度数较低的邻居比共享度数较高的邻居信息含量更高。
局部方法的局限性在于只考虑了局部节点邻域。例如，两个节点在其邻域内可能没有局部重叠，但在图中仍然是同一个社区的成员。全局重叠统计试图将这种关系考虑在内。
Katz index
Katz 指数是最基本的全局重叠统计量。我们简单统计一对节点之间所有长度的路径数来计算 Katz 指数：
S K a t z [ u , v ] = ∑ i = 1 ∞ β i A i [ u , v ] mathbf{S}_{Katz}[u,v] = sum^{infty}_{i=1} beta^i mathbf{A}^i [u,v] SKatz[u,v]=i=1∑∞βiAi[u,v]
其中， β ∈ R + β∈R^+ β∈R+是一个用户自定义的参数，用来控制短路径和长路径的权重。Katz 指数是矩阵几何级数（Geometric series of matrices）的一个例子，一个基本的矩阵几何级数的解由下面的定理 1给出： 设 X mathbf{X} X 是实值方阵， λ 1 mathbf{λ_1} λ1表示 X mathbf{X} X 的最大特征值，则
( I − X ) − 1 = ∑ i = 1 ∞ X i (mathbf{I}-mathbf{X})^{-1}=sum^{infty}_{i=1}mathbf{X}^i (I−X)−1=i=1∑∞Xi
当且仅当 λ 1 < 1 mathbf{lambda_1<1} λ1<1 且 ( I − X ) mathbf{(I-X)} (I−X) 非奇异。 基于上述定理，我们可以看到 Katz 指标的解为：
S K a t z = ( I − β A ) − 1 − I mathbf{S}_{Katz} = (mathbf{I}-beta mathbf{A})^{-1}-mathbf{I} SKatz=(I−βA)−1−I
其中， S K a t z ∈ R ∣ V ∣ × ∣ V ∣ mathbf{S}_{Katz}∈R^{| V | × | V |} SKatz∈R∣V∣×∣V∣ 是节点-节点相似度值的全矩阵。
Leicht, Holme, and Newman (LHN) similarity
Katz 指数的一个问题是它受节点度的影响很大。为了缓解这种情况，[Leicht et al., 2006] 通过考虑两个节点之间观察到的实际路径数与预期路径数之间的比率，提出了一种改进的度量：
A i E [ A i ] frac{mathbf{A^i}}{mathbb{E}[mathbf{A^i}]} E[Ai]Ai
即，两个节点之间的路径数量根据我们对随机模型下期望的路径数量的预期进行归一化。 E [ A i ] mathbb{E}[mathbf{A^i}] E[Ai] 的计算依赖于配置模型，它假设我们绘制一个与给定图具有相同度数的随机图。计算方式如下：
E [ A ( u , v ) ] = d u d v 2 m , m = ∣ E ∣ E [ A 2 ( v 1 , v 2 ) ] = d v 1 d v 2 2 m 2 ∑ u ∈ V ( d u − 1 ) d u mathbb{E}[mathbf{A}(u,v)]=frac{d_ud_v}{2m},m=|mathcal{E}|\ mathbb{E}[mathbf{A}^2(v_1,v_2)]=frac{d_{v_1}d_{v_2}}{2m^2}sum_{uin mathcal{V}} (d_u-1)d_u E[A(u,v)]=2mdudv,m=∣E∣E[A2(v1,v2)]=2m2dv1dv2u∈V∑(du−1)du
由于最大特征值可用于近似路径数量的增长，当路径长度 i > 2 i>2 i>2 时，定义 P i ∈ R ∣ V ∣ P^i in mathbb{R}^{|mathcal{V}|} Pi∈R∣V∣ 作为计算节点 u 和所有其他节点之间的长度为 i 的路径数量的向量，然后我们就可以得到：
A p i = λ 1 p i − 1 mathbf{Ap_i} = lambda_1mathbf{p_{i-1}} Api=λ1pi−1
因为 p i mathbf{p}_i pi 最终会收敛到图的主特征向量。这意味着每次迭代时两个节点之间的路径数量都会增长 λ 1 λ1 λ1 倍，其中 λ 1 λ1 λ1 是 A mathbf{A} A 的最大特征值。基于大 i i i 的近似值以及 i = 1 i = 1 i=1 的精确解，我们得到：
E [ A i ( u , v ) ] = d u d v λ i − 1 2 m mathbb{E}[mathbf{A}^i(u,v)]=frac{d_{u}d_{v}lambda^{i-1}}{2m} E[Ai(u,v)]=2mdudvλi−1
最后，将它们放在一起，我们可以获得 Katz 指数的标准化版本，我们将其称为 LNH 指数：
S L N H [ u , v ] = I [ u , v ] + 2 m d u d v ∑ i = 0 ∞ β i λ 1 i − 1 A i [ u , v ] mathbf{S}_{LNH}[u,v]=mathbf{I}[u,v]+frac{2m}{d_ud_v}sum_{i=0}^{infty}beta^ilambda_1^{i-1}mathbf{A}^i[u,v] SLNH[u,v]=I[u,v]+dudv2mi=0∑∞βiλ1i−1Ai[u,v]
其中 I mathbf{I} I 是和 A mathbf{A} A 具有一致索引的大小为 ∣ V ∣ × ∣ V ∣ mathcal{|V| times |V|} ∣V∣×∣V∣ 的单位矩阵。使用定理 1，矩阵级数的解（忽略对角项后）可以写为：
S L N H = 2 α m λ 1 D − 1 ( I − β λ 1 A ) − 1 D − 1 mathbf{S}_{LNH}=2 alpha mlambda_1mathbf{D}^{-1}(mathbf{I}-frac{beta}{lambda_1}mathbf A)^{-1}mathbf{D}^{-1} SLNH=2αmλ1D−1(I−λ1βA)−1D−1
其中 D mathbf D D 是对角线上具有节点度的矩阵。
随机游走方法（Random walk methods）
另一组全局相似性度量考虑随机游走，而不是图上路径的精确计数。比较经典的有 Personalized PageRank algorithm，它定义随机矩阵 P = A D − 1 mathbf{P = AD^{-1}} P=AD−1 并计算：
q u = c P q u + ( 1 − c ) e u mathbf{q}_u=cmathbf{P}mathbf{q}_u+(1-c)mathbf{e}_u qu=cPqu+(1−c)eu
在此等式中， e u e_u eu 是节点 u u u 的独热指示向量， q u [ v ] q_u[v] qu[v] 给出从节点 u u u 开始的随机游走访问节点 v v v 的平稳概率。这里， c c c 项决定了随机游走在每个时间步在节点 u u u 处重新开始的概率。如果没有这种重新启动概率，随机游走概率将简单地收敛到特征向量中心性的归一化变体。通过这种重新启动概率，我们可以获得特定于节点 u u u 的重要性度量，该过程表示及节点随机游走相似性度量定义如下：
q u = ( 1 − c ) ( I − c P ) − 1 e u S R W [ u , v ] = q u [ v ] + q v [ u ] mathbf{q}_u=(1-c)(mathbf I - cmathbf{P})^{-1}mathbf{e}_u\ mathbf S_{RW}[u,v] = mathbf{q}_u [v] + mathbf{q}_v [u] qu=(1−c)(I−cP)−1euSRW[u,v]=qu[v]+qv[u]
即一对节点之间的相似性与我们从另一个节点开始的随机游走到达每个节点的可能性成正比。
本节主要讨论图的节点聚类任务，引出节点低维嵌入任务，同时介绍一些重要的矩阵和谱图理论的基础知识。
Unnormalized Laplacian
非归一化拉普拉斯矩阵是最基本的拉普拉斯矩阵，定义如下：
L = D − A mathbf{L=D-A} L=D−A
其中 A 是邻接矩阵，D 是度矩阵。简单图的拉普拉斯矩阵具有许多重要的属性：
它是对称的 ( L ⊤ = L mathbf{L^{top}=L} L⊤=L) 和半正定的 ( x ⊤ L x > 0 , ∀ x ∈ R ∣ V ∣ mathbf{x^{top} Lx>0},forall xin mathbb{R}^{|mathcal{V}|} x⊤Lx>0,∀x∈R∣V∣)。
当时 ∀ x ∈ R ∣ V ∣ forall x in mathbb{R}^{|mathcal{V}|} ∀x∈R∣V∣时，以下向量恒等式成立：
x ⊤ L x = 1 2 ∑ u ∈ V ∑ v ∈ V A [ u , v ] ( x [ u ] − x [ v ] ) 2 = ∑ ( u , v ) ∈ E ( x [ u ] − x [ v ] ) 2 begin{aligned} mathbf{x}^{top} mathbf{L} mathbf{x} & =frac{1}{2} sum_{u in mathcal{V}} sum_{v in mathcal{V}} mathbf{A}[u, v](mathbf{x}[u]-mathbf{x}[v])^{2} \ & =sum_{(u, v) in mathcal{E}}(mathbf{x}[u]-mathbf{x}[v])^{2} end{aligned} x⊤Lx=21u∈V∑v∈V∑A[u,v](x[u]−x[v])2=(u,v)∈E∑(x[u]−x[v])2
L mathbf L L 有 ∣ V ∣ |V | ∣V∣ 个非负特征值： 0 = λ ∣ V ∣ ≤ λ ∣ V ∣ − 1 ≤ … ≤ λ 1 0=lambda_{|mathcal{V}|} leq lambda_{|mathcal{V}|-1} leq ldots leq lambda_{1} 0=λ∣V∣≤λ∣V∣−1≤…≤λ1。
定理 2：拉普拉斯 L 的 0 特征值的几何重数对应于图中连通分量的数量。
Normalized Laplacians
除了非标准化拉普拉斯算子之外，还有两种流行的标准化拉普拉斯算子变体。对称归一化拉普拉斯定义为：
L y s m = D − 1 2 L D − 1 2 mathbf{L_ysm=D^{-frac{1}{2}}LD^{-frac{1}{2}}} Lysm=D−21LD−21
而随机游走拉普拉斯定义为：
L R W = D − 1 L mathbf{L_RW=D^{-1}L} LRW=D−1L
这两个矩阵都具有与拉普拉斯矩阵相似的性质，但由于归一化，它们的代数性质存在小常数差异。
Graph cuts （图割）
为了激发拉普拉斯谱聚类方法，我们首先必须定义最佳聚类的含义。在此之前，我们先来了解什么是图的切割。给定图的划分为 K K K 个不重叠的子集 A 1 , . . . , A K A_1, ..., A_K A1,...,AK，我们将该划分的割值定义为：
cut ( A 1 , … , A K ) = 1 2 ∑ k = 1 K ∣ ( u , v ) ∈ E : u ∈ A k , v ∈ A ‾ k ∣ operatorname{cut}left(mathcal{A}_{1}, ldots, mathcal{A}_{K}right)=frac{1}{2} sum_{k=1}^{K}left|(u, v) in mathcal{E}: u in mathcal{A}_{k}, v in overline{mathcal{A}}_{k}right| cut(A1,…,AK)=21k=1∑K (u,v)∈E:u∈Ak,v∈Ak
换句话说，切割只是计算有多少条边穿过节点分区之间的边界。现在，将节点的最佳聚类定义为 K 个集群的一个选项是选择一个最小化此切割值的分区。这种方法的一个已知问题是它往往简单地创建由单个节点组成的集群。
因此，我们通常寻求最小化切割，同时强制分区都相当大，而不是简单地最小化切割。执行此操作的一种流行方法是最小化比率削减 (Ratio Cut) ：
RatioCut ( A 1 , … , A K ) = 1 2 ∑ k = 1 K ∣ ( u , v ) ∈ E : u ∈ A k , v ∈ A ‾ k ∣ ∣ A k ∣ operatorname{RatioCut}left(mathcal{A}_{1}, ldots, mathcal{A}_{K}right)=frac{1}{2} sum_{k=1}^{K} frac{left|(u, v) in mathcal{E}: u in mathcal{A}_{k}, v in overline{mathcal{A}}_{k}right|}{left|mathcal{A}_{k}right|} RatioCut(A1,…,AK)=21k=1∑K∣Ak∣ (u,v)∈E:u∈Ak,v∈Ak
这会惩罚选择小簇大小的解决方案。另一种流行的解决方案是最小化归一化剪切 (Normalized Cut, NCut) ：
NCut ( A 1 , … , A K ) = 1 2 ∑ k = 1 K ∣ ( u , v ) ∈ E : u ∈ A k , v ∈ A ‾ k ∣ vol ( A k ) operatorname{NCut}left(mathcal{A}_{1}, ldots, mathcal{A}_{K}right)=frac{1}{2} sum_{k=1}^{K} frac{left|(u, v) in mathcal{E}: u in mathcal{A}_{k}, v in overline{mathcal{A}}_{k}right|}{operatorname{vol}(mathcal{A}_{k})} NCut(A1,…,AK)=21k=1∑Kvol(Ak) (u,v)∈E:u∈Ak,v∈Ak
其中 vol ( A ) = Σ u ∈ A d u operatorname{vol}(mathcal{A}) = Σ_{u∈A} d_u vol(A)=Σu∈Adu。 NCut 强制要求所有簇都具有相似数量的与其节点相关的边。
Approximating the RatioCut with the Laplacian spectrum (用拉普拉斯谱近似 RatioCut)
我们的目标是利用拉普拉斯矩阵解决以下优化问题（这里简单的将节点分为两个集群）：
min A ∈ V RatioCut ( A , A ‾ ) min_{mathcal Ain mathcal V} operatorname{RatioCut}(mathcal{A},overline{mathcal{A}}) A∈VminRatioCut(A,A)
为了方便重写这个问题，我们定义如下向量 a ∈ R V a in mathbb{R}^{mathcal{V}} a∈RV：
a [ u ] = { ∣ A ‾ ∣ ∣ A ∣ if u ∈ A − ∣ A ∣ ∣ A ∣ if u ∈ A ‾ mathbf{a}[u]=left{begin{array}{ll} sqrt{frac{|overline{mathcal{A}}|}{|mathcal{A}|}} & text { if } u in mathcal{A} \ -sqrt{frac{|mathcal{A}|}{|mathcal{A}|}} & text { if } u in overline{mathcal{A}} end{array}right. a[u]=⎩ ⎨ ⎧∣A∣∣A∣ −∣A∣∣A∣ if u∈A if u∈A
将此向量与图拉普拉斯算子的属性相结合，我们可以看到：
a ⊤ L a = ∑ ( u , v ) ∈ E ( a [ u ] − a [ v ] ) 2 = ∑ ( u , v ) ∈ E : u ∈ A , v ∈ A ‾ ( a [ u ] − a [ v ] ) 2 = ∑ ( u , v ) ∈ E : u ∈ A , v ∈ A ‾ ( ∣ A ‾ ∣ ∣ A ∣ − ( − ∣ A ∣ ∣ A ‾ ∣ ) ) 2 = cut ( A , A ‾ ) ( ∣ A ∣ ∣ A ‾ ∣ + ∣ A ‾ ∣ ∣ A ∣ + 2 ) = cut ( A , A ‾ ) ( ∣ A ∣ + ∣ A ‾ ∣ ∣ A ‾ ∣ + ∣ A ∣ + ∣ A ‾ ∣ ∣ A ∣ ) = ∣ V ∣ RatioCut ( A , A ‾ ) . begin{aligned} mathbf{a}^{top} mathbf{L} mathbf{a} & =sum_{(u, v) in mathcal{E}}(mathbf{a}[u]-mathbf{a}[v])^{2} \ & =sum_{(u, v) in mathcal{E}: u in mathcal{A}, v in overline{mathcal{A}}}(mathbf{a}[u]-mathbf{a}[v])^{2} \ & =sum_{(u, v) in mathcal{E}: u in mathcal{A}, v in overline{mathcal{A}}}left(sqrt{frac{|overline{mathcal{A}}|}{|mathcal{A}|}}-left(-sqrt{frac{|mathcal{A}|}{|overline{mathcal{A}}|}}right)right)^{2} \ & =operatorname{cut}(mathcal{A}, overline{mathcal{A}})left(frac{|mathcal{A}|}{|overline{mathcal{A}}|}+frac{|overline{mathcal{A}}|}{|mathcal{A}|}+2right) \ & =operatorname{cut}(mathcal{A}, overline{mathcal{A}})left(frac{|mathcal{A}|+|overline{mathcal{A}}|}{|overline{mathcal{A}}|}+frac{|mathcal{A}|+|overline{mathcal{A}}|}{|mathcal{A}|}right) \ & =|mathcal{V}| operatorname{RatioCut}(mathcal{A}, overline{mathcal{A}}) . end{aligned} a⊤La=(u,v)∈E∑(a[u]−a[v])2=(u,v)∈E:u∈A,v∈A∑(a[u]−a[v])2=(u,v)∈E:u∈A,v∈A∑ ∣A∣∣A∣ −(−∣A∣∣A∣ ) 2=cut(A,A)(∣A∣∣A∣+∣A∣∣A∣+2)=cut(A,A)(∣A∣∣A∣+∣A∣+∣A∣∣A∣+∣A∣)=∣V∣RatioCut(A,A).
因此，我们可以看到 a 允许我们用拉普拉斯算子（最多为常数因子）来编写比率削减。此外，a还有另外两个重要的属性：
∑ u ∈ V a [ u ] = 0 , orequivalently , a ⊥ I , Iisthevectorofallones ∣ ∣ a 2 ∣ ∣ = ∣ V ∣ sum_{u in mathcal{V}} mathbf a[u]=0, operatorname{or equivalently},mathbf a space bot space mathbb I,operatorname{mathbb I is the vector of all ones}\ ||mathbf a^2|| = |mathcal V| u∈V∑a[u]=0,orequivalently,a ⊥ I,Iisthevectorofallones∣∣a2∣∣=∣V∣
将所有这些放在一起，我们可以将比率切割最小化问题重写为：
min A ⊂ V a ⊤ L a s . t . a ⊥ I ∣ ∣ a 2 ∣ ∣ = ∣ V ∣ [NP-Hard] min_{mathcal A subset mathcal V} mathbf{a^{top}La}\ s.t.\ mathbf a space bot space mathbb I\ ||mathbf a^2|| = |mathcal V|\ operatorname{[NP-Hard]} A⊂Vmina⊤a ⊥ I∣∣a2∣∣=∣V∣[NP-Hard]
总之，拉普拉斯算子的第二小特征向量是离散向量的连续近似，它给出了最佳聚类分配（相对于 RatioCut）。
通过检查拉普拉斯算子的 K 个最小特征向量，这个一般思想可以扩展到任意数量的 K 个簇。该一般方法的步骤如下：
谱聚类的一般原理非常强大。我们可以使用图拉普拉斯算子的频谱来表示图中的节点，并且这种表示可以作为最佳图聚类的原则近似。
在前面的章节中，我们看到了一些传统的图学习方法。 然而，本章所讨论的方法是有限的，特别是节点和图级统计，因为它们需要仔细的、手工设计的统计和措施。这些手工设计的特征是不灵活的，即它们不能通过学习过程来适应，并且设计这些特征可能是一个耗时且昂贵的过程。 本书后面的章节介绍了图学习的替代方法：图表示学习。我们将寻求学习编码图的结构信息的表示，而不是提取手工设计的特征。
Reference: Hamilton W L. Graph representation learning[M]. Morgan & Claypool Publishers, 2020.
本文发布于:2024-01-31 12:47:40，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170667646028625.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
