资料内容：
1.5.1图特征选择
现实世界中的数据通常是高维度的，并且存在嘈杂的、不相关和多余的特征（或
维度），尤其是在考虑给定任务时。特征选择旨在自动地选择一小部分特征，这些子
集具有最小的冗余度，但与学习目标（例如在监督学习中的类标签）有最大相关性。
在许多应用中，原始特征对于知识提取和模型解释至关重要。例如，在用于研究癌
症的遗传分析中，除了区分癌组织，鉴定诱导癌发生的基因（即原始特征）更重要。
在这些应用中，特征选择是优先考虑的，因为它可以保留原始特征，并且它们的语
义通常为学习问题提供关键的见解和解释。传统特征选择假定数据实例是独立同分
布的（i.i.d.）。然而，许多应用中的数据样本都鼠人在图上，因此它们在本质上不是
独立同分布的，这推动了图特征选择的研究领域。给定图g = {v,£},其中V是节
点集，是边集，假设每个节点最初都与一组维度为d的特征T =
相关联。图特征选择旨在从尸中选择K个特征，其中K " 首先，在有监督的
情况下对该问题进行了研究【5, 6】。这些方法使用线性分类器将所选特征映射到类别标
签，并引人图正则化项，以捕获结构信息来选择特征。特别地，该正则项旨在确保具
有所选特征的连接的节点可以映射到相似的标签中。然后，在无监督的情况下对问题
进行了进一步研究【7，&9j。在文献［9］中，它首先从结构信息中提取伪标签，然后用伪
标签充当监督信息指导特征选择过程。在文献⑺中，假定节点内容和结构信息都是
从一组高质量的特征中生成的，而这些特征可以通过最大化生成过程获得。在后续的
工作中，问题从简单图扩展到复杂图，例如动态图【1。}、多维图皿］、有符号图2.13］
和属性图网。第1章绪论
1.5.2图表示学习
与图特征选择不同，图表示学习是学习一组新的节点特征，它已经被深入研究了
数十年，并且通过深度学习得到了极大的加速。本节将简要回顾从浅层模型到深层模
型的历史过程。
在早期阶段，图表示学习已经在谱聚类【15, 16｝、基于图的降维［17,18,19］和矩阵分
解［0 18. 19］的背景下进行了研究。在谱聚类中，数据点被视为图的节点，然后聚类
问题变成了将图划分为节点社区。谱聚类的关键一步是谱嵌入，它旨在将节点嵌入低
维空间中，在该空间中可以将传统的聚类算法（如K-Means ）应用于识别聚类。基
于图的降维技术可以直接应用于学习节点表示。这些方法通常基于数据样本的原始特
征，使用预定义的距离（或相似度）函数构建亲和度图，然后通过保留该亲和度图的
结构信息学习节点表示。例如，IsoMap网通过测地线保留全局几何，而LLEP9】和
eigenmap阿保留亲和图中的局部邻域信息。因为前述方法经常需要在亲和矩阵（邻
接矩阵或拉普拉斯矩阵）上进行特征分解，所以它们通常具有很高的计算复杂度。矩
阵是表示图（例如邻接矩阵和拉普拉斯矩阵）最流行的方法之一。矩阵分解可以自然
地应用于学习节点表示。使用邻接矩阵来表示图作为示例，矩阵分解的目的是将节点
嵌入低维空间中，在该空间中可以利用新的节点表示重建邻接矩阵。文档语料库可以
表示以文档和单词为节点的二分图，如果一个单词出现在某个文档中，贝9单词和对应
的文档之间存在一条边。LSI已采用截断奇异值分解（truncated SVD）学习文档和
单词的表示形式网。在推荐系统中，用户和商品之间的交互可以表示为二分图。矩
阵分解既被用于推荐系统学习用户和商品的表示⑵】，也被用于节点分类【22, 23］、链接
预测【2」,2切和社区检测｛26｝等任务学习节点表示。实际上，后文介绍的一系列最新的
图嵌入算法也可以归为矩阵分解【27］。
