本文原创作者知乎链接为 https://www.zhihu.com/people/he-he-he-he-77-19-21
非常nice的一本传统的图算法的系统性介绍的神书，开头介绍了图领域的一些基础知识包括图的分类、图数据库、图在不同领域的应用等等，然后是系统性分门别类的介绍了不同方向的传统的图算法：
这块儿的算法没有研究完，太多了，后续慢慢搬上来，感兴趣的话大家可以看看这位大佬的文章：（顾鹏：https://www.zhihu.com/people/gupeng.nju），算法的基本介绍这位大佬基本讲完了，下面要介绍的是书的后半部分，也是我觉得对我来说帮助最大的一部分，关于探讨如何使用图算法来提高机器学习的效率和性能。
（下文为原作的翻译以及加入个人的一些理解和看法）
机器学习不是人工智能（AI），而是实现 AI 的一种方法，ML 通过具体的样本使用算法来训练模型，并在预期的基础上逐步改进，训练过程包括向模型提供大量数据，并使其能够学习如何处理和纳入这些信息。从这个意义上说，机器学习意味着算法迭代，不断进行更改，以接近目标，例如不断减少在训练数据集上的分类错误。ML 是动态的，提供更多的数据，它有能力继续改善和优化，这可以在在离线的时候进行，也可以在线学习。
为了提高机器学习的准确性和泛化性能，我们需要结合很多“上下文”信息，就像人们应该使用“上下文”来做出更好的决策一样。人们不仅仅使用直接的数据点，还使用周围的环境来确定情况中的基本内容，上下文可以帮助我们改善预测。（这里所说的 contextual information 不仅仅指是狭义的文本问题中的上下文，而是指代时间结构和空间结构上的一种共先关系，比如 word2vec 中的上下文的概念，时间序列中的事件发生的先后顺序，图结构中的近邻关系等）
机器学习算法擅长处理静态的、特定的信息，但是难以处理不断变化的信息，例如文本分类中词的上下文关系，如果要抽取出词的共先关系为新特征，则需要更多的更加准确细致的规则，比如词附近的 n 个单词，或者是时间序列中使用时间窗口来抽取不同时间区间的特征，比如过去一个月 XXX ，过去三个月 XXX 之类的统计特征，然而实际情况要复杂的多，我们难以仅仅通过一些特定的规则来对这类不断变化的信息进行充分的提取，这个时候，我们就需要借助于其它的手段。
下面举一个生动形象的例子：
来自 2012 年的论文 “A 61-Million-Person Experiment in Social Influence and Political Mobilization”.
facebook 的一次投票活动中发现，有 60M 的用户进行了投票，有趣的是，这 60M 的用户的朋友里，有 1.4% 比例的朋友被影响也加入了投票，从而带动增加了 886k 的投票者，而这 886k 的投票者的朋友，即原始参与者的朋友的朋友，也被带动了，从而又增加了 1M 的投票者。
因此，通过增加图特征和上下文信息，可以改善模型的性能，尤其是在这些特征和信息特别重要的领域，例如，零售公司不仅使用历史数据而且使用有关客户相似性和在线行为的上下文数据来个性化产品推荐。亚马逊的 Alexa 使用了多层上下文信息，证明可以获得精度更高的模型。在2018年，亚马逊还引入了 “context carryover”，以在回答新问题时将先前的参考文献纳入对话系统的构建中。
不幸的是，如今的许多机器学习方法都无法考虑到丰富的上下文信息。这是因为 ML 依赖从原始数据构建的输入数据，从而遗漏了大量预测关系和网络数据。此外，上下文信息并不总是容易获得，或者很难访问和处理。甚至对于传统方法而言，找到四度或更远的连接可能是一个挑战。但是使用图算法，我们可以更轻松地获取和得到这类数据。（实际上这一段不仅仅在图数据中存在，在文本和图像中也是一样存在，比如早期我们处理文本问题直接进行 onehot 展开，破坏了文本的序列相关性；对图像，针对像素点进行 onehot 展开，破坏了空间结构信息，但是传统的机器学习算法比如 lr、svm、gbdt 只能接受二维的特征矩阵，因此也是没有办法）
然后就自然而然引入了主要话题，如何通过图算法来提高机器学习算法的质量，答案是特征抽取和特征选择（评估）。
Connected features 的提取和评估
1. 一些basic的方法
连接信息的特征提取，这些特征可以从围绕节点的部分图进行局部图查询，也可以从图全局查询中使用图算法根据连接特征进行特征提取。除此之外，我们也可以使用图算法来进行特征评估与选择，例如我们可以将样本映射为图中的节点，基于相似的样本创建关联关系，然后计算特征的中心性，可以通过保留数据点的簇密度的能力来衡量特征的好坏。（ K. Henniab，N。Mezghani和C. Gouin Vallerand在 “Unsupervised Graph-Based Feature Selection Via Subspace and PageRank Centrality”,中使用具有高维和低样本量的数据集描述了此方法。）
2. graph embedding
图嵌入 graph embedding 就是相对最为知名的图数据的特征抽取的方法.
图嵌入使用的图形数据与 connected features 的特征提取略有不同。它使我们能够以表格形式的数据用于机器学习任务的数字格式以表示整个图数据结构。这对于无监督学习尤其有用，在无监督学习中，由于通过关系获取了更多上下文信息，因此未对数据进行分类。图形嵌入对于数据探索，计算实体之间的相似度以及减小维数以帮助进行统计分析也很有用。（其功能类似 word embedding，通过 word embedding 对文本向量化然后接普通的 ML 算法解决文本分类问题，通过 graph embedding 将图数据向量化然后接普通的 ML 算法解决节点或者边分类等问题）。经典的图嵌入算法包括了：node2vec、struct2vec、GraphSAGE, DeepWalk, and DeepGL.
3. graph features
图特征包括关于图的任何与连接相关的度量，例如进入或离开节点的关系数（出度和入度），潜在三角形的数量以及共同的邻居。在我们的示例中，我们将从这些度量开始，因为它们很容易收集并且可以很好地检验早期假设。实际上可以很容易的类别到传统的机器学习任务中，其实就是关于图数据的eda分析和一些基本的统计指标，就好像我们常常统计某个用户的平均收入水平、平均支出之类的，这里所提到的 graph features 就是指关于图、节点、边等的这些基本的统计特征，和第一点有部分重复的地方。
4. Graph Algorithm Features
我们还可以使用图算法来提取所需的特征，这些特征我们不知道确切的模式。举例来说，假设我们知道某些类型的社区分组表明存在欺诈行为；可能存在关系的原型密度或层次结构。在这种情况下，我们需要一个灵活且具有全局相关性的结构。在我们的示例中，我们将使用社区检测算法来提取关联的要素，但中心度算法（例如 PageRank）也经常被应用。
（这里的意思实际上可以类比 tfidf，比如在文本分类中，我们希望算法能够更多的关注对于每个句子重要的词而忽略语气词、代词等不重要的词，但是这种模式是相对抽象的，如何去表达出来，tfidf 通过统计计算的方法将这种模式抽象成稠密矩阵的形式，这里也是类似的意思，通过图算法将一些结构信息抽取成矩阵的形式，实际上和 graph embedding 的思路是类似的，可以类比于文本中的 tfidf 和 word embedding）
此外，使用多种图算法进行特征抽取的效果有时候要好于仅仅使用一种。例如，我们可以将连接的功能与通过 Louvain 算法找到的社区以及使用 PageRank 的有影响力的节点以及在三度时已知欺诈者的度量为基础的指标相结合，以预测欺诈行为。（因为这些基础算法没有深入研究，所以这里其实我是没什么体会的，但是感觉还是可以和文本类比起来，word2vec 和 glove，bert、xlnet 等等虽然有交叉，但也有不同，从不同的层面去做特征的提取，然后合并起来得到更加完整的潜在信息的表示）。
下图展示了一种组合方法，其中作者将诸如PageRank和Coloring之类的图形算法与诸如入度和出度的图形度量进行了组合。此图摘自S. Fakhraei等人的论文 “Collective Spammer Detection in Evolving Multi-Relational Social Networks”。
可以看到，进行特征抽取之后，模型效果的提升非常惊人。
作者发现从多种类型的关系中提取关联特征比仅添加更多特征更具预测性。报告子图部分显示了如何将图特征转换为特征ML模型可以使用的特性。通过在图形增强的ML工作流程中组合多种方法，作者能够改进先前的检测方法，并以90％的准确性对70％以前需要手动标记的垃圾邮件发送者进行分类。
即使我们提取了关联功能，也可以通过使用 PageRank 之类的图形算法对影响力最大的功能进行优先级排序。这使特征能够充分代表我们的数据，同时消除嘈杂的变量避免噪声特征降低结果质量或降低处理速度。有了这类信息，我们还可以识别高共现特征以通过特征选择进一步减少噪声特征对模型的伤害。（这方面可以参考：研究论文 “Using PageRank in Feature Selection”）
图算法增强 ML 的典型场景是在 “link prediction” 中，link prediction 是一种估计将来建立关系的可能性的方法，或者它是否应该已经存在于我们的图中但由于数据不完整而丢失。由于网络是动态的并且可以快速增长，因此能够预测即将添加的链接，例如产品推荐、药物重新定向甚至推断犯罪关系。
图的连接特征通常使用基本图特征以及从中心度和社区算法中提取的特征来改善 link prediction。基于节点接近度或相似度的 link prediction 也是常见的做法；在论文 “The Link Prediction Problem for Social Networks” 中 D. Liben-Nowell 和 J.Kleinberg 提到仅网络结构就可以包含足够的潜在信息，以检测节点的接近程度并胜过更直接的措施。
其它的一些算法：
许多算法可以用于图数据。在本书中，我们重点介绍了最能代表经典图算法和最常用于应用程序开发人员的算法。某些算法（例如着色和启发式算法）已被省略，因为它们在学术案例中更为有趣，或者可以轻松得出。
其他算法（例如基于边缘的社区检测）很有趣，但尚未在 Neo4j 或 Apache Spark 中实现（主要介绍了自家实现的，不过也已经够全了感觉）。我们期望随着图分析的使用增长，两个平台中使用的图算法列表也会增加。图中也使用了一些算法，但实际上并不是严格意义上的图形。例如，我们在第8章中研究了机器学习环境中使用的一些算法。另一个要注意的领域是相似性算法，通常用于推荐和链接预测。相似度算法通过使用各种方法比较诸如节点属性之类的项目，找出哪些节点最相似。
实际上这本书配套了很多类似于机器学习入门的 iris、titanic 之类的运行代码demo，后续有时间整理整理。