知识图谱与应用（脑图简化版）

1. 图谱基础

1.1 定义

知识图谱是一种通过图结构来表示知识的方式，主要由实体（节点）和实体之间的关系（边）构成。

1.2 组成部分

• 实体: 代表现实世界中的对象，如人、地点、事件、概念等。例如，用户、商品、书籍等。
• 关系: 描述实体之间的联系，如“购买”、“阅读”等。例如，用户购买了商品，用户阅读了书籍等。
• 属性: 实体的特征或描述信息，如用户的年龄、性别、地址；商品的价格、产地；书籍的分类、页码、体裁等。

1.3 特点

• 语义丰富: 知识图谱不仅存储了数据，还包含数据之间的语义关系，因此能够描述更丰富的信息。
• 可扩展性: 新的实体和关系可以动态添加，知识图谱可以不断更新和扩展。可以在原图谱的基础上直接添加新的实体和关系，而不必重新构建整个图谱。
• 推理能力: 通过图结构，可以进行推理，发现潜在的关系和知识。例如，通过图谱可以发现用户和商品之间的购买关系，以及商品和类别之间的关系。

1.4 构建流程

• 数据获取：从各种来源（如数据库、API、文件等）获取源数据。这些数据可以是文本，音频等，也可以是表格型数据。例如文本数据中通常会包含“李斯是秦国的宰相”这样的描述，音频数据可以直接转换为文本数据，而表格型数据如订单表中会记录用户A购买了商品B这样的信息。
• 实体识别：从源数据中提取实体，并给实体分配唯一的标识符。例如，文本数据中可能会出现“李斯”和“秦国”这两个实体，那么我们可以给它们分别分配唯一的标识符，如“李斯”和“秦国”。
• 关系识别：从源数据中提取关系，并给关系分配唯一的标识符。例如，文本数据中可能会出现“用户A购买了商品B”这样的描述，那么我们可以给它分配唯一的标识符，如“购买”。
• 属性识别：从源数据中提取属性，并给属性分配唯一的标识符。例如，文本数据中可能会出现“李斯是秦国的宰相”中的“宰相”这个属性，那么我们可以分配唯一的标识符，如“宰相”。
• 构建图谱：将实体、关系和属性按照图谱的结构进行组合，形成知识图谱。图谱中数据的结构是一个三元组合，如 <实体A，关系，实体B>。

注：实体识别和关系抽取是一门专门研究领域，这里不做介绍。

1.5 图谱的存储

• 关系型数据库：如mysql，hive等。建立一个实体关系表或实体连接边的表，表设计为src_id、dst_id、relationship、weight字段，然后建立实体属性表，设计为id、feature1，feature2…。如果有多种类型的实体，需要分别建立实体属性表。
• 图数据库：如Neo4j、OrientDB等。图数据库支持直接进行图查询，图计算和可视化分析。但图查询需要特定的语言，如Cypher。

2. 图谱能力

2.1 社区发现

2.1.1 Girvan-Newman算法

• 原理：基于边介数中心性（edge betweenness centrality），逐步移除中心性最高的边，直到图被分割成期望数量的社区。
• 优点：能够发现高质量的社区结构。
• 缺点：计算复杂度高，适合小规模图。

2.1.2 Kernighan-Lin算法

• 原理：通过交换两个子集中的节点来最小化子集之间的边数。
• 优点：适合中等规模的图。
• 缺点：需要初始划分，结果可能依赖于初始状态。

2.1.3 Louvain算法

• 原理：通过贪心算法最大化模块度（modularity），先将每个节点作为一个社区，然后逐步合并提高模块度的社区。
• 优点：高效，适合大规模图。
• 缺点：结果具有随机性，不同运行可能产生不同分区。

2.1.4 Leiden算法

• 原理：改进Louvain算法，解决了Louvain算法可能产生的低质量社区问题，进一步优化模块度。
• 优点：更稳定，适合大规模图。
• 缺点：与Louvain算法相比，计算复杂度稍高。

2.1.5 谱聚类算法

• 原理：利用图的拉普拉斯矩阵的特征值和特征向量进行聚类，通过对图的拉普拉斯矩阵进行特征分解，找到低维空间中的表示，然后使用K-means等聚类算法进行社区划分。
• 优点：能够处理复杂的社区结构。
• 缺点：计算复杂度高，适合中小规模图。

2.1.6 . Infomap算法

• 原理：利用随机游走过程，将图的节点划分为不同社区，目标是最小化随机游走过程中描述路径的编码长度。
• 优点：能够发现多层次的社区结构。
• 缺点：计算复杂度较高。

2.1.7 Label Propagation算法

• 原理：通过节点之间的标签传播，逐步收敛到稳定状态，每个节点被分配到最多邻居节点所属的社区。
• 优点：简单高效，适合大规模图。
• 缺点：结果具有随机性，可能存在多个稳定状态。

2.2 节点影响力计算

2.2.1 度中心性（Degree Centrality）

• 原理：度中心性是指一个节点的度（即连接到该节点的边的数量）。在无向图中，度中心性即节点的度数；在有向图中，度中心性分为入度和出度。
• 公式：对于节点$v$，其度中心性计算公式为：$C_d(v)={deg(v)}$,
• 优点：计算简单，直观。
• 缺点：只考虑直接相邻节点，忽略了全局网络结构。

2.2.2 介数中心性（Betweenness Centrality）

• 原理：介数中心性衡量一个节点在网络中作为其他节点对之间最短路径的桥梁的频率。具体来说，某节点的介数中心性是通过该节点的所有最短路径数量占所有最短路径数量的比例。
• 公式：对于节点$v$, 介数中心性计算公式为：$C_b(v)=\sum\limits_{s \neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$，其中$\sigma_{st}$表示节点$s$和节点$t$之间的最短路径个数，$\sigma_{st}(v)$表示节点$s$和节点$t$之间的最短路径中通过节点$v$的个数。
• 优点：考虑了全局网络结构，能识别关键节点。
• 缺点：计算复杂度高，适合中小规模图。

2.2.3 接近中心性（Closeness Centrality）

• 原理：接近中心性衡量一个节点到其他所有节点的平均最短路径长度。接近中心性高的节点能够更快地到达其他节点。
• 公式：对于节点$v$，接近中心性$C_{c}(v)$为$C_{c}(v) = \frac{1}{\sum\limits_{t} d(v,t)}$，其中$d(v,t)$是节点$v$和$t$之间最短路径长度。
• 优点：考虑了全局网络结构，能识别中心节点。
• 缺点：计算复杂度高，适合中小规模图。

2.2.4 特征向量中心性（Eigenvector Centrality）

• 原理：特征向量中心性衡量一个节点的影响力不仅基于其直接连接的节点数量，还基于其连接节点的影响力。即，一个节点的影响力越高，其连接的节点影响力也越高。
• 公式：对于节点$v$，特征向量中心性$x_{v}$为$x_{v} = \frac{1}{\lambda}\sum\limits_{u \in N{v}} x_{u}$，其中$\lambda$是特征值，$N{v}$是节点$v$的邻居节点集合。
• 优点：考虑了节点间的相互影响，能够识别重要节点。
• 缺点：计算复杂度高，需要迭代计算。

2.2.5 PageRank

• 原理：PageRank是特征向量中心性的变种，最初用于网页排名。它通过随机游走模型来衡量节点的重要性，考虑了节点的连接结构和节点间的相互影响。
• 公式：对于节点$v$，PageRank值$PR(v)$为：$PR(v) = \frac{1-d}{N} + d\sum\limits_{u \in N(v)} \frac{PR(u)}{deg(u)}$，其中$d$是阻尼因子（通常取0.85），$N$是节点总数，$N(v)$是节点$v$的邻居节点集合，$deg(u)$是节点$u$的度数。
• 优点：考虑了全局网络结构，广泛应用于网页排名和推荐系统。
• 缺点：计算复杂度高，需要迭代计算。

2.2.6 Katz中心性

• 原理：Katz中心性考虑了所有路径的影响，但对路径长度进行衰减。它衡量一个节点通过其邻居节点及其邻居的邻居等间接连接的影响力。
• 公式：对于节点$v$，Katz中心性$C_{K}(v)$为：$C_{K}(v) = \alpha \sum\limits_{u \in N(v)} C_{K}(u) + \beta$，其中$\alpha$是衰减因子，$\beta$是常数，$N(v)$是节点$v$的邻居节点集合。
• 优点：考虑了节点间的间接影响。
• 缺点：计算复杂度高，需要迭代计算。

2.2.7 HITS算法（Hyperlink-Induced Topic Search）

• 原理：HITS算法将节点分为“枢纽”（Hub）和“权威”（Authority），枢纽节点指向权威节点，权威节点被枢纽节点指向。算法通过迭代计算枢纽值和权威值来衡量节点的影响力。
• 公式: $A(v)=\sum\limits_{u \in B(v)} H(u)$, $H(v)=\sum\limits_{u \in F(v)} A(u)$，其中$A(v)$是节点$v$的权威值，$H(v)$是节点$v$的枢纽值，$B(v)$是指向$v$的节点集合，$F(v)$是$v$指向的节点集合。
• 优点：能够区分不同类型的节点（枢纽和权威）。
• 缺点：计算复杂度高，需要迭代计算。

2.3 图嵌入

2.3.1 DeepWalk

• 原理：DeepWalk通过在图上进行随机游走生成节点序列，然后使用Skip-gram模型（类似于Word2Vec）将这些节点序列嵌入到低维向量空间。
• 优点：能够捕捉局部和全局的图结冷启动处理策略
  节点特征初始化：利用节点的属性或特征进行初始化。
  局部结构信息：通过卷积操作聚合新节点的邻居节点特征生成嵌入。构信息，适用于无监督学习。
• 缺点：随机游走的效率较低，特别是在大规模图中，难以捕捉长距离的节点关系。
• 冷启动策略：使用新节点的邻居节点信息进行初始化嵌入。
• 是否支持异质图：不直接支持异质图。
• 是否支持不同关系类型：不直接支持不同关系类型。
• 能否处理边的权重：不直接支持边的权重。

2.3.2 Node2Vec

• 原理：Node2Vec是DeepWalk的改进版，通过调整随机游走策略，结合DFS（深度优先搜索）和BFS（广度优先搜索），生成更丰富的节点序列。
• 优点：灵活的随机游走策略，能够捕捉不同类型的节点关系，适用于无监督学习。
• 缺点：参数调优较复杂，需要根据具体应用场景调整深度和广度游走的参数$p$和$q$, 随机游走的效率较低。
• 冷启动策略：使用新节点的邻居节点信息进行初始化嵌入。
• 是否支持异质图：不直接支持异质图。
• 是否支持不同关系类型：不直接支持不同关系类型。
• 能否处理边的权重：不直接支持边的权重。

2.3.3 LINE (Large-scale Information Network Embedding)

• 原理：LINE直接在图的边上进行优化，分别考虑一阶和二阶相似性。一阶相似性即节点之间的直接连接关系；二阶相似性即节点的邻居节点之间的相似性。通过联合优化这两种相似性，将节点嵌入到低维向量空间。
• 优点：适合大规模图，计算效率较高，能够捕捉一阶和二阶相似性。
• 缺点：仅考虑局部结构信息，难以捕捉全局结构。
• 冷启动策略：利用新节点的直接邻居和二阶邻居信息进行初始化嵌入。
• 是否支持异质图：不直接支持异质图，但可以通过分层处理不同类型的节点。
• 是否支持不同关系类型：不直接支持不同关系类型。
• 能否处理边的权重：支持边的权重，可以在优化目标中直接考虑边的权重。

2.3.4 GraphSAGE (Graph Sample and Aggregate)

• 原理：GraphSAGE通过对节点的邻居节点进行采样和聚合，生成节点的嵌入表示。它有两个消息传递操作，即采样和聚合。采样是指从每个节点的邻居中随机采样固定数量的节点。聚合是指对采样的邻居节点进行聚合（如平均、LSTM、池化等），然后结合节点自身特征生成嵌入。
• 优点：能够处理大规模图，计算效率较高；适用于半监督学习；能够动态生成新节点的嵌入。
• 缺点：聚合函数的选择对结果有较大影响；采样策略可能导致信息丢失。
• 冷启动策略：节点特征初始化时利用节点的属性或特征进行初始化；通过采样和聚合新节点的邻居节点信息生成嵌入。
• 是否支持异质图：可以通过设计不同的聚合函数和采样策略来处理异质图。
• 是否支持不同关系类型：可以通过设计不同的聚合函数来处理不同关系类型。
• 能否处理边的权重：不直接支持边的权重，但可以在聚合时考虑边的权重。

2.3.5 GCN (Graph Convolutional Networks)

• 原理：GCN通过卷积操作对图中的节点进行特征聚合，生成节点的嵌入表示。它的实现基于图卷积实现，卷积操作是指对每个节点的特征和其邻居节点的特征进行加权聚合。然后通过多层卷积操作，逐步聚合更广泛的节点信息。
• 优点：能够捕捉图的局部和全局结构信息；适用于半监督学习和全监督学习。
• 缺点：计算复杂度较高，难以处理超大规模图；需要预设卷积层数和其他超参数。
• 冷启动策略：通过卷积操作聚合新节点的邻居节点特征生成嵌入。
• 是否支持异质图：不直接支持异质图，但可以通过扩展模型（如Heterogeneous GCN）来处理。
• 是否支持不同关系类型：不直接支持不同关系类型，但可以通过扩展模型（如R-GCN）来处理。
• 能否处理边的权重：支持边的权重，可以在卷积操作中直接考虑边的权重。

2.3.6 GAT (Graph Attention Networks)

• 原理：GAT引入注意力机制，对每个节点的邻居节点进行加权聚合，权重由注意力机制动态计算。注意力机制是指计算每个节点与其邻居节点之间的注意力权重。加权聚合是指根据注意力权重对邻居节点的特征进行加权聚合，生成节点嵌入。
• 优点：动态计算邻居节点的权重，能够捕捉重要的邻居节点信息；适用于半监督学习和全监督学习。
• 缺点：计算复杂度较高，难以处理超大规模图；需要预设注意力头数和其他超参数。
• 冷启动策略：通过注意力机制动态计算新节点的邻居节点权重，生成嵌入。
• 是否支持异质图：不直接支持异质图，但可以通过扩展模型（如Heterogeneous GAT）来处理。
• 是否支持不同关系类型：不直接支持不同关系类型，但可以通过扩展模型来处理。
• 能否处理边的权重：支持边的权重，可以通过注意力机制动态计算边的权重。

2.3.7 GAE（Graph Autoencoders)

• 原理：GAE通过编码器-解码器结构，将图中的节点嵌入到低维向量空间，并通过解码器重构图结构。编码器是指将节点的特征和图结构编码为低维嵌入。解码器是指从低维嵌入重构图结构，最小化重构误差。
• 优点：能够捕捉图的全局结构信息；适用于无监督学习。
• 缺点：计算复杂度较高，难以处理超大规模图；需要预设编码器和解码器的结构和超参数。
• 冷启动策略：通过编码器-解码器结构，将新节点的特征和邻居节点信息编码为嵌入向量。
• 是否支持异质图：不直接支持异质图。
• 是否支持不同关系类型：不直接支持不同关系类型。
• 能否处理边的权重：支持边的权重，可以在解码器中直接考虑边的权重。

2.3.8 特殊处理策略

对于不支持异质图、不同关系类型、边的权重处理的模型，可以以通过如下一些策略来处理。

2.3.8.1 异质图支持

• 预处理：将异质图转换为同质图，或为不同类型的节点和边添加特征。
• 分层处理：对不同类型的节点和边分别处理，然后融合结果。
• 扩展模型：设计专门处理异质图的扩展模型，如Heterogeneous GCN、Heterogeneous GAT等。

2.3.8.2 不同关系类型支持

• 多关系建模：为不同关系类型设计不同的处理机制，如不同的聚合函数或卷积核。
• 关系类型特征：为每种关系类型添加特征，并在模型中考虑这些特征。

2.3.8.3 边的权重支持

• 加权处理：在模型中直接考虑边的权重，如在随机游走、聚合、卷积等操作中加权。
• 权重特征：将边的权重作为特征输入模型，并在模型中进行处理。

3. 图谱应用

3.1 推荐系统-召回

3.1.1 召回方式

• u2i：用户到物品的推荐；
• i2i：物品到物品的推荐；
• u2u：即用户到用户的推荐；

3.1.2 实现方式

• 基于路径的推荐：通过在知识图谱中搜索用户与物品之间的路径，找到潜在的推荐物品。例如，从用户节点出发，经过其浏览过的物品节点，再找到与这些物品相关的其他物品节点。
• 嵌入表示：将知识图谱中的节点和边嵌入到低维向量空间，通过计算用户与物品的相似度进行推荐。
• 规则推理：利用知识图谱中的逻辑规则和关系进行推理，推荐符合这些规则的物品。

3.2 种子人群扩散

3.2.1 原理

• 原理：种子人群扩散是指通过知识图谱选择一组初始节点（种子节点），然后通过这些节点在网络中传播信息、影响其他节点的过程。

3.2.2 实现方式

• 节点影响力计算：利用知识图谱中的节点中心性指标（如度中心性、介数中心性、接近中心性等），选择影响力大的节点作为种子节点。
• 传播模型：定义信息在网络中传播的规则，如独立级联模型（IC）和线性阈值模型（LT），模拟信息从种子节点向其他节点传播的过程。
• 优化算法：利用贪心算法、CELF算法等优化种子节点的选择，最大化传播效果。

3.3 影响力分析

3.3.1 原理

• 原理：影响力分析是通过知识图谱中的结构信息和节点属性，评估节点在网络中的重要性和影响力。用于寻找核心用户和高质量内容。

3.3.2 实现方式

• 中心性指标：利用度中心性、介数中心性、接近中心性、特征向量中心性等指标，评估节点的影响力。
• PageRank算法：通过随机游走模型，评估节点在网络中的全局影响力。
• HITS算法：将节点分为“枢纽”和“权威”，分别评估节点作为信息传播者和信息源的影响力。

3.4 社区发现

3.4.1 原理

• 原理：社区发现是通过知识图谱中的节点和边的结构信息，识别图中的社区结构，即节点的聚集群。可以用于发现和分析人群的特征，或进行人群圈选。

3.4.2 实现方式

• 模块度优化：通过最大化模块度（Modularity），识别图中的社区结构。
• 谱聚类：通过图的拉普拉斯矩阵进行谱分解，识别图中的社区结构。
• 基于标签传播：通过节点之间的标签传播过程，识别图中的社区结构。