![Graph RAG: 知识图谱结合 LLM 的检索增强](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/share/2023.38th%20banner_%E7%94%BB%E6%9D%BF%201.jpg)

本文为大家揭示 NebulaGraph 优先提出的 Graph RAG 方法，这种结合知识图谱、图数据库作为大模型结合私有知识系统的最新技术栈，是 LLM+ 系列的第三篇，加上之前的图上下文学习、Text2Cypher 这两篇文章，目前 NebulaGraph + LLM 相关的文章一共有 3 篇。

# Graph RAG

在[第一篇关于上下文学习的博客中](https://discuss.nebula-graph.com.cn/t/topic/13624)我们介绍过，RAG（Retrieval Argumented Generation）这种基于特定任务/问题的文档检索范式中，我们通常先收集必要的上下文，然后利用具有认知能力的机器学习模型进行上下文学习（in-context learning），来合成任务的答案。

借助 LLM 这个只需要”说话“就可以灵活处理复杂问题的感知层，只需要两步，就能搭建一个基于私有知识的智能应用：

- 利用各种搜索方式（比如 Embedding 与向量数据库）从给定的文档中检索相关知识。
- 利用 LLM 理解并智能地合成答案。

而这篇博客中，我们结合最新的探索进展和思考，尝试把 Graph RAG 和其他方法进行比较，说得更透一点。此外，我们决定开始用 Graph RAG 这个叫法来描述它。

> 实际上，[Graph RAG](https://siwei.io/talks/graph-rag-with-jerry/)，是最先由我和 Jerry Liu 的[直播研讨会讨论](https://www.youtube.com/watch?v=bPoNCkjDmco)和[相关的讨论的 Twitter Thread](https://twitter.com/wey_gu/status/1673362774930628608) 中提到的，差不多的内容我在 [NebulaGraph 社区直播](https://www.bilibili.com/video/BV1Pp4y157nt) 中也用中文介绍过。

# 在 RAG 中知识图谱的价值

这部分内容我们在第一篇文章中阐述过，比如一个查询：“告诉我所有关于苹果和乔布斯的事”，基于乔布斯自传这本书进行问答，而这个问题涉及到的上下文分布在自传这本书的 30 页（分块）的时候，传统的“分割数据，Embedding 再向量搜索”方法在多个文档块里用 TOP-K 去搜索的方法很难得到这种分散，细粒的完整信息。而且，这种方法还很容易遗漏互相关联的文档块，从而导致信息检索不完整。

除此之外，在之后一次技术会议中，我有幸和 [leadscloud.com](https://www.leadscloud.com/) 的徐旭讨论之后（他们因为有知识图谱的技术背景，也做了和我们类似的探索和尝试！），让我意识到**知识图谱可以减少基于嵌入的语义搜索所导致的不准确性**。徐旭给出的一个有趣的例子是“保温大棚”与“保温杯”，尽管在语义上两者是存在相关性的，但在大多数场景下，这种通用语义（Embedding）下的相关性常常是我们不希望产生的，进而作为错误的上下文而引入“幻觉”。

这时候，保有领域知识的知识图谱则是非常直接可以缓解、消除这种幻觉的手段。

# 用 NebulaGraph 实现 Graph RAG

一个简单的 Graph RAG 可以如下去简单实现：

1. 使用 LLM（或其他）模型从问题中提取关键实体
2. 根据这些实体检索子图，深入到一定的深度（例如，2）
3. 利用获得的上下文利用 LLM 产生答案。

对应的伪代码可能是这样：

```python
# 伪代码

def _get_key_entities(query_str, llm=None ,with_llm=True):
    ...
    return _expand_synonyms(entities)

def _retrieve_subgraph_context(entities, depth=2, limit=30):
    ...
    return nebulagraph_store.get_relations(entities, depth, limit)

def _synthesize_answer(query_str, graph_rag_context, llm):
    return llm.predict(PROMPT_SYNTHESIZE_AND_REFINE, query_str, graph_rag_context)

def simple_graph_rag(query_str, nebulagraph_store, llm):
    entities = _get_key_entities(query_str, llm)
    graph_rag_context = _retrieve_subgraph_context(entities)
    return _synthesize_answer(
        query_str, graph_rag_context, llm)
```

然而，有了像 LlamaIndex 这样方便的 LLM 编排工具，开发者可以专注于 LLM 的编排逻辑和 pipeline 设计，而不用亲自处理很多细节的抽象与实现。

所以，用 LlamaIndex，我们可以轻松搭建 Graph RAG，甚至整合更复杂的 RAG 逻辑，比如 [Graph + Vector RAG](https://gpt-index.readthedocs.io/en/latest/examples/index_structs/knowledge_graph/KnowledgeGraphIndex_vs_VectorStoreIndex_vs_CustomIndex_combined.html)。

![](https://github.com/siwei-io/talks/assets/1651790/f783b592-7a8f-4eab-bd61-cf0837e83870)

在 LlamaIndex 中，我们有两种方法实现 Graph RAG：

- `KnowledgeGraphIndex` 只用来对任何私有数据从零构建知识图谱（基于 LLM 或者其他语言模型），再 4 行代码进行 Graph RAG：

```
graph_store = NebulaGraphStore(
    space_name=space_name,
    edge_types=edge_types,
    rel_prop_names=rel_prop_names,
    tags=tags,
)
storage_context = StorageContext.from_defaults(graph_store=graph_store)

# Build KG
kg_index = KnowledgeGraphIndex.from_documents(
    documents,
    storage_context=storage_context,
    max_triplets_per_chunk=10,
    space_name=space_name,
    edge_types=edge_types,
    rel_prop_names=rel_prop_names,
    tags=tags,
)

kg_query_engine = kg_index.as_query_engine()
```

- `KnowledgeGraphRAGQueryEngine` 则可以在任何已经存在的知识图谱上进行 Graph RAG。不过，我还没有完成这个 [PR](https://github.com/jerryjliu/llama_index/pull/7204)。

```
graph_store = NebulaGraphStore(
    space_name=space_name,
    edge_types=edge_types,
    rel_prop_names=rel_prop_names,
    tags=tags,
)
storage_context = StorageContext.from_defaults(graph_store=graph_store)

graph_rag_query_engine = KnowledgeGraphRAGQueryEngine(
    storage_context=storage_context,
)
```

最后，我做了[一个 Streamlit 的 Demo](https://www.siwei.io/demos/graph-rag/)来比较 Graph RAG 与 Vector RAG，从中我们可以看到 Graph RAG 并没有取代 Embedding、向量搜索的方法，而是增强了/补充了它的不足。

![](https://www-cdn.nebula-graph.com.cn/nebula-blog/graph-rag/demo.gif)

# Text2Cypher

基于图谱的 LLM 的另一种有趣方法是 Text2Cypher。这种方法不依赖于实体的子图检索，而是将任务/问题翻译成一个面向答案的特定图查询，和我们常说的 Text2SQL 方法本质是一样的。

## 在 NebulaGraph 上进行 Text2Cypher

在之前的文章中我们已经介绍过，得益于 LLM，实现 Text2Cypher 比传统的 ML 方法更为简单和便宜。

比如，[LangChain: NebulaGraphQAChain](https://python.langchain.com/docs/use_cases/more/graph/graph_nebula_qa) 和 [Llama Index: KnowledgeGraphQueryEngine](https://gpt-index.readthedocs.io/en/latest/examples/query_engine/knowledge_graph_query_engine.html) 让我们 3 行代码就能跑起来 Text2Cypher。

## 比较 Text2Cypher 和 (Sub)Graph RAG

这两种方法主要在其检索机制上有所不同。Text2Cypher 根据 KG 的 Schema 和给定的任务生成图形模式查询，而 SubGraph RAG 获取相关的子图以提供上下文。

两者都有其优点，为了大家更直观理解他们的特点，我做了这个 Demo 视频：

我们可以看到两者的图查询模式在可视化下是有非常清晰的差异的。

![](https://www-cdn.nebula-graph.com.cn/nebula-blog/graph-rag/demo2.gif)

## 结合 Text2Cypher 的 Graph RAG

然而，两者并没有绝对的好与坏，不同场景下，它们各有优劣。

在现实世界中，我们可能并不总是知道哪种方法更有效（用来区分应该用哪一种），因此，我倾向于考虑同时利用两者，这样获取的两种检索结果作为上下文，一起来生成最终答案的效果可能是最好的。

具体的实现方法在[这个 PR](https://github.com/jerryjliu/llama_index/pull/7204)中已经可以做到了，只需要设置 `with_text2cypher=True`，Graph RAG 就会包含 Text2Cypher 上下文，敬请期待它的合并。


# 结论

通过将知识图谱、图存储集成到 LLM 技术栈中，Graph RAG 把 RAG 的上下文学习推向了一个新的高度。它能在 LLM 应用中，通过利用现有（或新建）的知识图谱，提取细粒度、精确调整、领域特定且互联的知识。

请继续关注图谱和 LLM 领域的更深入的探索和进一步的发展。

----
**谢谢你读完本文**(///▽///)

如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> [GitHub](https://github.com/vesoft-inc/nebula)；如果你有更高的性能、易用性、运维实施等方面的需求，你也可以随时 [联系我们](https://www.nebula-graph.com.cn/contact)，获取进一步的帮助哦~

本文为大家揭示 NebulaGraph 优先提出的 Graph RAG 方法，这种结合知识图谱、图数据库作为大模型结合私有知识系统的最新技术栈，是 LLM+ 系列的第三篇。

Graph RAG: 知识图谱结合 LLM 的检索增强

本文记录了 NebulaGraph 的研发人员使用 GPT-4 将 Slack channel 消息同步到其他 IM 的全过程，希望对你有帮助。

AI 协助办公 ｜记一次用 GPT-4 写一个消息同步 App

本文整理自 NebulaGraph 布道师 wey 在「夜谈 LLM」主题分享上的演讲，主要包括 LLM 和Graph RAG、知识抽取、Text2Cypher 等技术介绍及未来规划。

关于 LLM 和图、图数据库的那些事

高效建模、快速导入、性能优化——应该怎么做？

使用秘籍 ｜你可能不知道的 NebulaGraph 最佳性能姿势

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-website-5.0/images/blogs/2023.12th%20banner_%E7%94%BB%E6%9D%BF%201.jpg) 

在进行各种图处理、图计算、图查询的时候，内存或是硬盘中如何存储图结构是一个影响性能的关键因素。本文主要分析了几种常见的内存图结构，及其时间、空间复杂度，希望对你有所启发。

通常来说，对于图结构的几种常见的基础操作：

1. 插入一个点
2. 插入一个边
3. 删除一个边
4. 删除一个点的全部邻边
5. 找到一个点的全部邻边
6. 找到一个点的另一个邻点
7. 全图扫描
8. 获取一个点的入度或者出度

这些图相关的操作，除了要关心时间复杂度之外，需要考虑空间占用的问题。

对于大多数实时读写型的系统，增删改查的性能问题会比较重要，它们比较关注上面 1-6 的操作；对于部分密集计算的系统，对批量读取的性能会比较重视，侧重上面 5-8 的操作。

不过遗憾的是，无论是常规的图查询，还是进阶的图计算，根据 RUM 猜想[1]，读快、写快、又省空间这样”既要又要也要”的好事是不存在的。

下面，我们介绍几个数据结构并给出少量的定量分析。

我们先从三个典型的方案（邻接矩阵、压缩稀疏矩阵和邻接表）说起，再介绍几种近几年的研究的变种结构 PCSR、VCSR、CSR++。

# 邻接矩阵 Adjacency Matrix

用矩阵来表示图结构是大学里数据结构课程中都学过的知识，也是一种非常直观的办法。

点 i 与点 j 之间有一条边，等价对应于矩阵上 $M_{ij}$ 为 1。当然，这里的点 ID 是需要连续排列无空洞。

用矩阵来表示图结构有明显的好处，可以复用大量线性代数的研究成果：比如图上模式匹配类的问题等价于矩阵的相乘。

下面是一个模式匹配问题，它的大体意思是在全图上寻找这样一种图结构：

```shell
Match (src)-[friend * 2..4]->(fof)
WHERE src.age > 30
RETURN fof
```

对于这样一个问题可以直接对应右边的矩阵操作：

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image1.jpg)

比如，2 跳遍历等价于矩阵 F 自乘；2 - 4 跳遍历分别等价于 F^2、F^3、F^4；取属性等价于乘以一个过滤矩阵。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image2.png)

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image3.png)

更进一步，由于矩阵操作是天生可以分块并行加速，这在性能上有极大的优势。

下面，我们对邻接矩阵操作进行一个简单的定量分析

|操作|时间复杂度|备注|
|----|----|----|
|插入一个点|O(n^2)|对于矩阵来说，增加一个点意味着整个矩阵的维度增加，通常需要另外开辟一块空间|
|插入一个边|O(1)|增加一个边只是将对应的位置置 1|
|删除一个边|O(1)|置0|
|删除一个点的全部邻边|O(n)|对于某个点所有出边的删除对应某一行的置0。入边对应某一列，可以批量操作|
|找到一个点的全部邻边|O(n)||
|找到一个点的给定邻点|O(1)||
|全图扫描|O(n^2)||

其中，n=|V|，m=|E|。

优化上，批量操作（CPU Cache/SSD block）可以线性增加性能，例如 O(n) 可以降低到 O(n/B)，但不影响定量分析。

**由于绝大多数图结构是极其稀疏的，因此简单用邻接矩阵来表示图结构，其内存会有夸张的浪费**。更为严重的是，当有多种边类型时，每种边类型各需要一个邻接矩阵。这使得裸用矩阵在实际情况中只能处理很小数据量的场景。当然，对于现代服务器动辄几百 G 的内存，如果只有几亿点边的数据量，像是 twitter2010，这并不会是很严重的问题。但大多数情况下，条件允许的话，大家还是希望找到一些更加经济的结构。

# 压缩稀疏矩阵 CSR/CSC

压缩稀疏矩阵是一种非常流行和紧凑的图结构表示方式，大多数图计算系统都采用 CSR。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image5.png)

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image4.png)

这里简单介绍一下 CSR 的结构：

对于点 IDx，取邻居 ID 就是 F[N[x]] 到 F[N[x+1]-1]。

例如，查找点 ID2 的邻居，对应为 F[N[2]] 到 F[N[2+1]-1]，对应到上图也即 1 6 8。查找点 ID7 的邻居，对应为 F[N[7]] 到 F[N[7+1]-1]，也就是 2 和 4。 

另外，CSR 记录的仅是出边的信息，如果要考虑入边就使用 CSC，其原理是类似的。

|操作|时间复杂度|备注|
|----|----|----|
|插入一个点|O(1)|在点矢量尾部增加|
|插入一个边 <u,v>|O(m+n)|边矢量，从 u 对应的邻居开始，都向后移动一位；点矢量，从 u 对应位置开始每个值加 1|
|删除一个边|O(m+n)|插入边的逆过程|
|删除一个点 v 的全部邻边|O(m+n)|边矢量移动 deg(v) 位，点矢量 u 对应位置置 0|
|找到一个点的全部邻边|O(deg(v))||
|找到一个点的给定邻点|O(log(deg(v)))|deg(v) 内的排序查找|
|全图扫描|O(m+n)||

CSR 的空间占用是 O(|V|+|E|)，**在空间节省和顺序查找上是极其高效的**。但**在大量插入时，压缩稀疏矩阵和邻接矩阵一样，需要重新开辟空间，效率很低**。所以，它适合于计算密集场景但不适合增改频繁的场景。

CSR 还有一个显著的优点是可以快速获取每个点的出入度，只要计算 N[x+1]-N[x]，这在判断一些点是否为超级节点时很方便。如果不是稀疏矩阵的话，通常会用另外一个单独的结构来记录出入度。

此外，CSR 不容易实现并发修改，其每次插入都需要对两个矢量进行位移，这并不高效。

这里推荐两个相关的开源项目，可以进一步了解下 CSR 的使用：

* [https://github.com/DrTimothyAldenDavis/GraphBLAS](https://github.com/DrTimothyAldenDavis/GraphBLAS)
* [https://github.com/GraphBLAS/LAGraph](https://github.com/GraphBLAS/LAGraph)

# 邻接链表 Adjacency List

和基于矩阵的方式不同，邻接链表 AL 空间上有优势，但对于边的读写上会略微慢一点（指针在内存中不能连续移动）。AL 的做法是把邻边（出边）用 list 或者有序 list 的方式串连起来。由此延伸的一个变种是邻边从 list 改为 array。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image7.png)

|操作|时间复杂度|备注|
|----|----|----|
|插入一个点|O(1)|尾插入|
|插入一个边 <u,v>|O(log(deg(u))) |有序 list|
|删除一个边 |O(log(deg(u)))||
|删除一个点 v 的全部邻边 |O(1)||
|找到一个点的全部邻边|O(deg(u))||
|找到一个点的给定邻点|O(log(deg(u)))||
|全图扫描 |O(n+m)||

AL 相比 CSR 通常不能直接获得点的出入度，可以通过可以单独维护一个字段实现该功能。

此外，邻接表并不需要 ID 连续排布，对于频繁增删点的场景特别友好。AL 对于并发修改的支持也更友好，天然在点级别有并行度。当然，对于超级节点，直接用 list 的方式，还是会有些性能的问题要考虑；优化上可能会进一步改造成 Blocked list 的方式，可以带来更好的数据局部性和细颗粒度。

由于 ID 不用严格连续排布，AL 的一个常见变种就是 Tree。

# Tree

在这种结构中，一个点和其所有的邻边被建模成了 key-value，key 是点 ID，value 是所有邻边的编码。Key 通过 Tree 的方式组织在一起。这里的树可以是 B-Tree 等各变种 Tree。虽然本文没有讨论图属性，但 value 中也是可以存放 value。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image6.png)

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image9.png)


|操作|时间复杂度|备注|
|----|----|----|
|插入一个点 |O(log(n))||
|插入一个边 <u,v>|O(deg(u) log(n))||
|删除一个边|O(deg(u) log(n))||
|删除一个点 v 的全部邻边|O(log(n))||
|找到一个点的全部邻边|O(deg(u) log(n))||
|找到一个点的给定邻点|O(log(n deg(u))||
|全图扫描|O(n+m)||

为了控制访问颗粒度，每个叶子通常会被限定为固定的大小（页）。这就是在数据库类系统里面最常见的办法 B-tree。为了增改方便，也可以把每页的 in-place update 改成 Copy-On-Write 的方式；一个典型的代表就是 LLAMA[2]，但这种多版本的读取通常会需要更多的空间，并且当有大量累积修改时，需要定期的多版本合并以降低跨快照读。某种程度上，它和 LSM-Tree 的思路有些接近。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image8.png)

# 基于 CSR 的变种 PCSR 和 VCSR

由于 CSR 在空间和读性能上有很大的优势，但在插入时的耗时和空间上都很弱，因此本节几个变种的主要目的都是为了改善其弱项，大体思路都是分块和 buffer。

在 CSR 的边矢量进行增删时可以注意到，主要耗时是在对于矢量的元素位移上。因此，一个直观的思路是预留一些插入空白位，在删除时也不立刻回收这些空白。

而分块思想，是指将一些局部数据放在同一个分块内，例如 Tree 中每个 page 就是一种分块的方式。与此对应的是，buffer 空白之间的连续区域。

## PCSR

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image12.png)

PCSR [3]的基本思想是：对于点矢量，其元素从一个值改为对应边矢量中对应邻边位置的 `<起点,终点>`。而对于边矢量，在这些分块所对应边界放置哨兵 sentinel，上图中的 S，上图的 “-“ 对应预留插入位置留空。

事实上，原文中，对于边矢量，其本质是实现为一个 B-Tree，本文先简化成一个 Array。  

|操作|时间复杂度|备注|
|----|----|----|
|插入一个点| O(1)| 直接在点矢量和边矢量的尾插入|
|插入一个边 <u,v>| O(log(deg(u))| 边矢量对应分片的二分+空位查找|
|删除一个边| O(log(deg(u))||
|删除一个点v的全部邻边 |O(1) |边矢量对应分片置空，点矢量对应 ID 位置置空|
|找到一个点的全部邻边| O(deg(u))||
|找到一个点的给定邻点| O(log(deg(u))||
|全图扫描| O(n+m)||

可以看到，PCSR 的预留位置多少都是需要重平衡，不能过多也不能不足。特别是大批量增删时，对预留位置的处理会是一个较重的操作。

此外，如果把 PMA 的 B-Tree 以及需要 rebalance 的本质考虑进去，其和前述 Tree 方式的区别并不是很大。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image10.png)
 
## VCSR 

VCSR[4]主要是对 PCSR 的一个改进，其朴素思想是 PCSR 的留空是均匀的，而大多数图结构的出入度，是存在 20-80 这样的幂率特征，而 PCSR 的一个主要痛点是频繁的 rebalance。VCSR 的做法是为每个分块预留空间正比于其分块内的点的数量，即：边矢量中，一个分块内，如果点的数量多，就多预留一些空位。在直觉上，点数量多时，其分块对应的边插入会更多一些，这样可以减少 rebalance 的频率。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image11.png)

此外，VCSR 还有些版本号之类的优化。

## CSR++

事实上，CSR++[5]在设计上其实更接近一种 AL/Tree 的变种，而不是 CSR。它主要有三个方面的优化：

第一，对于 Vertex Array 再分段，将一个大的 Array 拆成多段，这样可以有更细的读写颗粒度。通过 `段 ID + 点 ID` 来定位每个点和其邻边。
第二，Vertex Array 中每个元素，**除了记录点 ID 之外，对于邻边数量很少的点，直接把邻居 ID 也对齐地塞 inline 进去**。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/csr++format.png)

对于大多数的点，其邻边就不需要单独的 Edge Array 来存储了。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/csr++format-link-edge.png)

可以看到这种方式在图比较稀疏的时候，对于 CPU Cache 扫描是很友好的。

第三，对于每个点的邻边，采用copy-on-write、标记删除等常见的优化办法，构建成类似 `std::vector` 结构。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image13.png)

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image14.png)

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/image15.png)

# 小结

最后，由于在图查询、图存储和图计算不同场景下，对于图结构的读写扫描和生命周期都有些不同的要求，不同的数据结构也有不同的优劣。

当然，本文只是讨论了图结构可以放在内存中的情况。当不得不把部分数据放在硬盘上时，问题就完全不同了。当然本文也没有讨论不同 CPU 对于不同距离内存的性能差异 NUMA，或者跨进程通信带来的影响。

# 延伸阅读

最后，我们来了解下在图计算/图算法上的图操作。

## 图算法中的图操作

在图计算中，存在多种图结构算法，可能会涉及多种基础操作。

中心性 Centrality Algorithms，一种衡量一个节点在整个网络图中所在中心程度的算法，包括：度中心性、接近中心性、介数中心性等，会涉及“找到一个点的全部邻边”、“找到一个点的另一个邻点”、“全图扫描”的操作组合。

* 度中心性通过节点的度数，即关联的边数来刻画节点的受欢迎程度，这将会要求找到一个点的所有邻边。
* 接近中心性，通过计算每个节点到全图其他所有节点的路径和来刻画节点与其他所有节点的关系密切程度，这将会要求进行全图扫描，查找点和图中所有点的路径信息。
* 介数中心性，则用于衡量一个顶点出现在其他任意两个顶点对之间最短路径上的次数，从而来刻画节点的重要性，这将会要求进行全图扫描，找到一个点和它的邻点及路径信息

PageRank，又称网页排名、谷歌左侧排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术作为网页排名的要素之一的排名方法。它以 Google 公司创办人拉里·佩奇 Larry Page 之姓来命名。Google 用它来体现网页的相关性和重要性，在搜索引擎优化操作中是经常被用来评估网页优化的成效因素之一。一般来说，PageRank 的值越高，表示其被很多其他网页链接到，说明它的重要性很高；而如果一个 PageRank 很高的网页链接到其他网页，被链接的网页的 PageRank值也会随之提高。PageRank 的计算过程如下：

假设由 4 个网页组成的集合：A、B、C、D，每个页面的初始 PageRank 值相同，为了满足概率值为 0-1 之间，假设这个值为 0.25。

如果所有页面都只链接至 A，如下图，则 A 点的值将是 B、C、D 的 PageRank 值的和。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/pagerank-links.png)

倘若是下图这种图结构：

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/abcd-relations.png)

B 链接到 C，D 链接到 B 和 C，A 点的值计算的方式如下：

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/pagerank-a-pr.png)

这里的 2、1、3，分别是 B 点对外链接的 2 条边，C 点对外链接的 1 条边，D 点对外链接的 3 条边。

换句话说，算法将根据每个页面连出总数平分该页面的 PR 值，并将其加到其所指向的页面：

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/pagerank-formula.png)

最后，所有这些 PR 值被换算成百分比形式再乘上一个修正系数。

由于“没有向外链接的网页”传递出去的 PR 值会是0，这时候如果递归的话，会导致指向它的页面的 PR 值的计算结果同样为零，所以 PageRank 会赋给每个页面一个最小值。

因此，一个页面的 PR 值直接取决于指向它的的页面。如果在最初给每个网页一个随机且非零的 PR 值，经过重复计算，这些页面的 PR 值会趋向于某个定值，也就是处于收敛的状态，即最终结果。

简单来说，大多数迭代图计算模型都是基于“找到一个点的全部邻边”、“找到一个点的另一个邻点”操作。

# AIGC 小课堂

在 AIGC 小课堂部分，我们会用 NebulaGraph 接入的 aibot 来讲解下文中的部分概念。你如果对 chatgpt 或者是 aibot 有兴趣，可以来 [https://discuss.nebula-graph.com.cn/](https://discuss.nebula-graph.com.cn/) 向 aibot 提出你的要求。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/what-is-csr.png)

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/graph-data-structure-in-memory/csr-case1.png)

# 参考文献

1. Athanassoulis, M., Kester, M. S., Maas, L. M., et al. (2016). Designing Access Methods: The RUM Conjecture. In EDBT (pp. 461-466).
2. Macko, P., Marathe, V. J., Margo, D. W., et al. (2015). Llama: Efficient Graph Analytics Using Large Multiversioned Arrays. In 2015 IEEE 31st International Conference on Data Engineering (pp. 363-374). IEEE.
3. Wheatman, B., & Xu, H. (2018). Packed Compressed Sparse Row: A Dynamic Graph Representation. In 2018 IEEE High Performance Extreme Computing Conference (HPEC) (pp. 1-7). IEEE.
4. Islam, A. A. R., Dai, D., & Cheng, D. (2022). VCSR: Mutable CSR Graph Format Using Vertex-Centric Packed Memory Array. In 2022 22nd IEEE International Symposium on Cluster, Cloud and Internet Computing (CCGrid) (pp. 71-80). IEEE.
5. Firmli, S., Trigonakis, V., Lozi, J. P., et al. (2020). CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. In 24th International Conference on Principles of Distributed Systems (OPODIS'20).

在进行各种图处理、图计算、图查询的时候，内存或是硬盘中如何存储图结构是一个影响性能的关键因素。本文主要分析了几种常见的内存图结构，及其时间、空间复杂度，希望对你有所启发。

NebulaGraph 专栏：走进图数据世界，解析内存中的高性能图结构

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/nebula-llm-kg-banner.jpg)

LLM 如火如荼地发展了大半年，各类大模型和相关框架也逐步成型，可被大家应用到业务实际中。在这个过程中，我们可能会遇到一类问题是：现有的哪些数据，如何更好地与 LLM 对接上。像是大家都在用的知识图谱，现在的图谱该如何借助大模型，发挥更大的价值呢？

在本文，我便会和大家分享下如何利用知识图谱构建更好的 In-context Learning 大语言模型应用。

此文最初以[英文](https://www.siwei.io/en/graph-enabled-llama-index/)撰写的，而后我麻烦 ChatGPT 帮我翻译成了英文。下面是翻译的 prompt：

“In this thread, you are a Chinese Tech blogger to help translate my blog in markdown from English into Chinese, the blog style is clear, fun yet professional. I will paste chapters in markdown to you and you will send back the translated and polished version.”

# LLM 应用的范式

作为认知智能的一大突破，LLM 已经改变了许多行业，以一种我们没有预料到的方式进行自动化、加速和启用。我们每天都会看到新的 LLN 应用被创建出来，我们仍然在探索如何利用这种魔力的新方法和用例。

将 LLM 引入流程的最典型模式之一，是要求 LLM 根据专有的/特定领域的知识理解事物。目前，我们可以向 LLM 添加两种范式以获取这些知识：**微调——fine-tune** 和 **[上下文学习](https://en.wikipedia.org/wiki/In-context_learning_(natural_language_processing))—— in-context learning**。

微调是指对 LLM 模型进行附加训练，以增加额外的知识；而上下文学习是在查询提示中添加一些额外的知识。

据观察，目前由于上下文学习比微调更简单，所以上下文学习比微调更受欢迎，在这篇论文中讲述了这一现象：[https://arxiv.org/abs/2305.16938](https://arxiv.org/abs/2305.16938)。

下面，我来分享 NebulaGraph 在上下文学习方法方面所做的工作。

# Llama Index：数据与 LLM 之间的接口

## 上下文学习

上下文学习的基本思想是**使用现有的 LLM（未更新）来处理特定知识数据集的特殊任务**。

例如，要构建一个可以回答关于某个人的任何问题，甚至扮演一个人的数字化化身的应用程序，我们可以将上下文学习应用于一本自传书籍和 LLM。在实践中，应用程序将使用用户的问题和从书中"搜索"到的一些信息构建提示，然后查询 LLM 来获取答案。

```asciiarmor
┌───────┐         ┌─────────────────┐         ┌─────────┐
│       │         │ Docs/Knowledge  │         │         │
│       │         └─────────────────┘         │         │
│ User  │─────────────────────────────────────▶   LLM   │
│       │                                     │         │
│       │                                     │         │
└───────┘                                     └─────────┘
```

在这种搜索方法中，实现从文档/知识（上述示例中的那本书）中获取与特定任务相关信息的最有效方式之一是利用嵌入（Embedding）。

## 嵌入（Embedding）

嵌入通常指的是将**现实世界的事物映射到多维空间中的向量的方法**。例如，我们可以将图像映射到一个（64 x 64）维度的空间中，如果映射足够好，两个图像之间的距离可以反映它们的相似性。

嵌入的另一个例子是 word2vec 算法，它将每个单词都映射到一个向量中。例如，如果嵌入足够好，我们可以对它们进行加法和减法操作，可能会得到以下结果：

`vec(apple) + vec(pie) ≈ vec("apple apie")`，或者向量测量值 `vec(apple) + vec(pie) - vec("apple apie")` 趋近于 0：

`|vec(apple) + vec(pie) - vec("apple apie")| ≈ 0`

类似地，"pear" 应该比 "dinosaur" 更接近 "apple"：`|vec(apple) - vec(pear)| < |vec(apple) - vec(dinosaur)|`

有了这个基础，理论上我们可以搜索与给定问题更相关的书籍片段。基本过程如下：

- 将书籍分割为小片段，为每个片段创建嵌入并存储它们
- 当有一个问题时，计算问题的嵌入
- 通过计算距离找到与书籍片段最相似的前 K 个嵌入
- 使用问题和书籍片段构建提示
- 使用提示查询 LLM

```asciiarmor
                  ┌────┬────┬────┬────┐                  
                  │ 1  │ 2  │ 3  │ 4  │                  
                  ├────┴────┴────┴────┤                  
                  │  Docs/Knowledge   │                  
┌───────┐         │        ...        │       ┌─────────┐
│       │         ├────┬────┬────┬────┤       │         │
│       │         │ 95 │ 96 │    │    │       │         │
│       │         └────┴────┴────┴────┘       │         │
│ User  │─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─▶   LLM   │
│       │                                     │         │
│       │                                     │         │
└───────┘    ┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐  └─────────┘
    │          ┌──────────────────────────┐        ▲     
    └────────┼▶│  Tell me ....., please   │├───────┘     
               └──────────────────────────┘              
             │ ┌────┐ ┌────┐               │             
               │ 3  │ │ 96 │                             
             │ └────┘ └────┘               │             
              ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ 
```

## Llama Index

Llama Index 是一个开源工具包，它能帮助我们以最佳实践去做 in-context learning：

- 它提供了各种数据加载器，以统一格式序列化文档/知识，例如 PDF、维基百科、Notion、Twitter 等等，这样我们可以无需自行处理预处理、将数据分割为片段等操作。
- 它还可以帮助我们创建嵌入（以及其他形式的索引），并以一行代码的方式在内存中或[向量数据库](https://github.com/openai/openai-cookbook/blob/main/examples/vector_databases/Using_vector_databases_for_embeddings_search.ipynb)中存储嵌入。
- 它内置了提示和其他工程实现，因此我们无需从头开始创建和研究，例如，[《用 4 行代码在现有数据上创建一个聊天机器人》](https://twitter.com/jerryjliu0/status/1663213212932902913)。

# 文档分割和嵌入的问题

嵌入和向量搜索在许多情况下效果良好，但在某些情况下仍存在挑战，比如：丢失全局上下文/跨节点上下文。

想象一下，当查询"请告诉我关于作者和 foo 的事情"，在这本书中，假设编号为 1、3、6、19-25、30-44 和 96-99 的分段都涉及到 foo 这个主题。那么，在这种情况下，简单地搜索与书籍片段相关的前 k 个嵌入可能效果不尽人意，因为这时候只考虑与之最相关的几个片段（比如 k = 3），会丢失了许多上下文信息。

```asciiarmor
┌────┬────┬────┬────┐
│ 1  │ 2  │ 3  │ 4  │
├────┴────┴────┴────┤
│  Docs/Knowledge   │
│        ...        │
├────┬────┬────┬────┤
│ 95 │ 96 │    │    │
└────┴────┴────┴────┘
```

而解决、缓解这个问题的方法，在 Llama Index 工具的语境下，可以创建[组合索引](https://gpt-index.readthedocs.io/en/latest/how_to/index_structs/composability.html)和[综合索引](https://gpt-index.readthedocs.io/en/latest/guides/primer/index_guide.html)。

其中，向量存储（VectorStore）只是其中的一部分。除此之外，我们可以定义一个摘要索引、树形索引等，以[将不同类型的问题路由到不同的索引](https://gpt-index.readthedocs.io/en/latest/guides/tutorials/unified_query.html)，从而避免在需要全局上下文时错失它。

然而，借助知识图谱，我们可以采取更有意思的方法：

# 知识图谱

知识图谱这个术语最初由[谷歌在 2012 年 5 月提出](https://blog.google/products/search/introducing-knowledge-graph-things-not/)，作为其增强搜索结果，向用户提供更多上下文信息的一部分实践。知识图谱旨在理解实体之间的关系，并直接提供查询的答案，而不仅仅返回相关网页的列表。

知识图谱是一种以图结构形式组织和连接信息的方式，其中节点表示实体，边表示实体之间的关系。图结构允许用户高效地存储、检索和分析数据。

它的结构如下图所示：

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/knowledge-demo.png)

现在问题就来了，上面说过知识图谱能帮忙搞定文档分割和嵌入的问题。那么，知识图谱到底能怎么帮到我们呢？

# 嵌入和知识图谱的结合

这里的基本实现思想是，作为信息的精炼格式，知识图谱可切割的数据颗粒度比我们人工的分割的更细、更小。将知识图谱的小颗粒数据与原先人工处理的大块数据相结合，我们可以更好地搜索需要全局/跨节点上下文的查询。

下面来做个题：请看下面的图示，假设提问同 `x` 有关，所有数据片段中有 20 个与 `x` 高度相关。现在，除了获取主要上下文的前 3 个文档片段（比如编号为 1、2 和 96 的文档片段），我们还从知识图谱中对 `x` 进行两次跳转查询，那么完整的上下文将包括：

- 问题："Tell me things about the author and x"
- 来自文档片段编号 1、2 和 96 的原始文档。在 Llama Index 中，它们被称为节点 1、节点 2 和节点 96。
- 包含 "x" 的知识图谱中的 10 个三元组，通过对 `x` 进行两层深度的图遍历得到：
  - x -> y（来自节点 1）
  - x -> a（来自节点 2）
  - x -> m（来自**节点 4**）
  - x <- b-> c（来自**节点 95**）
  - x -> d（来自节点 96）
  - n -> x（来自**节点 98**）
  - x <- z <- i（来自**节点 1 和节点 3**）
  - x <- z <- b（来自**节点 1 和节点 95**）

```asciiarmor
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┐
│ .─.       .─.    │  .─.       .─.   │            .─.   │  .─.       .─.   │
│( x )─────▶ y )   │ ( x )─────▶ a )  │           ( j )  │ ( m )◀────( x )  │
│ `▲'       `─'    │  `─'       `─'   │            `─'   │  `─'       `─'   │
│  │     1         │        2         │        3    │    │        4         │
│ .─.              │                  │            .▼.   │                  │
│( z )◀────────────┼──────────────────┼───────────( i )─┐│                  │
│ `◀────┐          │                  │            `─'  ││                  │
├───────┼──────────┴──────────────────┴─────────────────┼┴──────────────────┤
│       │                      Docs/Knowledge           │                   │
│       │                            ...                │                   │
│       │                                               │                   │
├───────┼──────────┬──────────────────┬─────────────────┼┬──────────────────┤
│  .─.  └──────.   │  .─.             │                 ││  .─.             │
│ ( x ◀─────( b )  │ ( x )            │                 └┼▶( n )            │
│  `─'       `─'   │  `─'             │                  │  `─'             │
│        95   │    │   │    96        │                  │   │    98        │
│            .▼.   │  .▼.             │                  │   ▼              │
│           ( c )  │ ( d )            │                  │  .─.             │
│            `─'   │  `─'             │                  │ ( x )            │
└──────────────────┴──────────────────┴──────────────────┴──`─'─────────────┘
```

显然，那些（可能很宝贵的）涉及到主题 `x` 的精炼信息来自于其他节点以及跨节点的信息，都因为我们引入知识图谱，而能够被包含在 prompt 中，用于进行上下文学习，从而克服了前面提到的问题。

# Llama Index 中的知识图谱进展

最初，[William F.H.](https://github.com/jerryjliu/llama_index/pull/433)将知识图谱的抽象概念引入了 Llama Index，其中知识图谱中的三元组与关键词相关联，并存储在内存中的文档中，随后[Logan Markewich](https://github.com/jerryjliu/llama_index/pull/487)还增加了每个三元组的嵌入。

最近的几周中，我一直在与 Llama Index 社区合作，致力于[将 "GraphStore" 存储上下文引入 Llama Index](https://github.com/jerryjliu/llama_index/pull/2581)，从而引入了知识图谱的外部存储。首个知识图谱的外部存储是对接开源分布式图数据库 NebulaGraph，目前在我的努力下已经实现了。

在实现过程中，还引入了遍历图的多个跳数选项以及在前 k 个节点中收集更多关键实体的选项，用于在知识图谱中搜索以获得更多全局上下文。上面提到的这些变更还在陆续完善中。

在大模型中引入 GraphStore 后，还可以从现有的知识图谱中进行上下文学习，并与其他索引结合使用，这也非常有前景。因为知识图谱被认为具有比其他结构化数据更高的信息密度。

本文作为开篇，讲述了一些知识图谱和 LLM 的关系。在后续的文章中，将会偏向实操同大家分享具体的知识图谱和 LLM 的应用实践。  

一文了解如何利用知识图谱构建更好的 In-context Learning 大语言模型应用。

知识图谱驱动的大语言模型 Llama Index

> nebula_dart_gdbc，是访问 NebulaGraph 的 Dart 语言客户端，在 dart_gdbc 的规范下进行开发。

> dart_gdbc 是一套使用 Dart 语言定义的图数据库标准数据接口，整体思路参考了 JDBC 的规范。目前已经实现了对 NebulaGraph 的支持。

在先前写 GraphDesk 的过程中，曾使用过 nebula-java（Socket）+ Spring Boot（HTTP）的方式实现了 Flutter 应用对 NebulaGraph 的访问。这无异于一辆可以高速行驶的汽车（Socket），进出家门的时候非要用人推（HTTP）的方式，这一点很难让人接受。而使用 Dart Socket 访问图数据库无疑是 Flutter 应用一个不错的选择。不过，因为 Dart 相比其他编程语言来说，目前相对小众，需求量小，并且是个偏前端的语言，纵观现有的图数据库生态，它们都不支持 Dart。

于是，dart_gdbc 与 nebula_dart_gdbc 应运而生。

随着 Dart 客户端的打通，对于拥有图数据库的朋友来说，**通过 Dart 在手机上，甚至嵌入式平台上进行 NebulaGraph 的图探索，已经成为可能**。而对于 Flutter 开发者来说，可以试试创建自己的图数据库，使用 nebula_dart_gdbc 直连数据库来实现自己的应用，也是一种奇妙体验。虽然，数据库的常规操作还是经过服务端做数据转发合理一点，但不影响大家尝试这种新玩法。

如果一切顺利的话，Dart 这一环节补上之后，之前我做的 GraphDesk，将会有以下变化：

- 从程序启动来看，将挣脱 Java 环境的束缚，不再需要等待本地 Java 服务的启动过程，运行体验上会有一个质的变化；
- 从查询性能的角度上来看，也会更加流畅；
- 条件允许的情况下，未来将推出 App 版本。

意义层面的内容就说到这，接下来聊聊 nebula_dart_gdbc 的诞生历程，下文带有很强的技术色彩，非业内人士可以选择性跳过。

# nebula_dart_gdbc 的设计实现

nebula_dart_gdbc 的大概实现思路同其他语言的客户端一致，按照了下面这个步骤：

1. 通过 thrift 文件，生成 NebulaGraph 数据访问接口；
2. 将生成的数据访问接口与 Thrift 结合，完成对 NebulaGraph 的访问；
3. 封装数据库连接。

显然，真正的开发并没有这么简单。在实际的过程中，我遇到了很多问题，也做了很多尝试，最终才有了现在的 nebula_dart_gdbc。下面来记录下开发一个 Dart 客户端，有哪些操作步骤以及相关问题的解决方案。

## 生成 NebulaGraph 数据访问接口

第一步，先下载数据接口的 thrift 文件，这是 NebulaGraph 给出的链接：[https://github.com/vesoft-inc/nebula/tree/master/src/interface](https://github.com/vesoft-inc/nebula/tree/master/src/interface)，包含下面这些文件：

- common.thrift
- graph.thrift
- meta.thrift
- storage.thrift

注意：下载完之后，需要往文件添加对应的包名，如：namespace dart nebula.graph

第二步，下载完接口所需的 NebulaGraph thrift 文件之后，我们再来下载 Thrift，这是 Thrift 的官方下载地址：[https://thrift.apache.org/download](https://thrift.apache.org/download)，这里使用的是最新版本 0.18.1（如果你阅读本文的时候，0.18.1 不是最新版本，下载最新版本即可）。

第三步，逐个文件生成 Dart 代码。使用下面的命令就行：

```shell
thrift --gen dart common.thrift
thrift --gen dart graph.thrift
thrift --gen dart meta.thrift
thrift --gen dart storage.thrift
```
这个过程中，我们会遇到一些问题，这里记录了它们的解决方法。

- 问题 1：文件会遇到“非语言中立性的标记编译”问题；
    - 解决方案：按报错将文件中的语言标记删除即可。
- 问题 2：这里使用的 Dart 版本是 2.19.0，由 thrift-0.18.1 生成的 Dart 代码与现今的版本语法并不兼容，而且版本差异很大。报错如下图所示，当然这只是当中的一部分，实际报错的文件有 300 个左右。
- ![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/dart-nebulagraph/error-screenshot.jpg)
- （这是一张散户欢呼，码农落泪的图）
    - 解决方案：根据编辑器的报错，逐个文件改。可能是最笨的办法，花了好几个小时。更好的方式，应该是让 thrift 的 compiler 支持最新的 Dart 版本，但这个办法可能需要花费更多的时间，而且不一定能成功。（退堂鼓震天响，退散...）

第四步，将生成的 Dart 代码，放到项目中。

至此，完成“通过 thrift 文件，生成 NebulaGraph 数据访问接口”。

## 数据访问接口与 Thrift 结合

这里，先插播一条广告（请耐心读下去）。

> 给大家介绍一家的烧烤摊。这家店的特点是，一个服务员有一个托盘，并且这个服务员只服务一桌。服务员很庄重地用托盘，端着一张空白的纸来到顾客面前，由顾客们轮流写上自己喜欢的牛肉串、烤面筋、烤花菜...，再选择调料黑胡椒、孜然...等信息。将纸放到托盘中后，由服务员送到烧烤师傅手中，烧烤师傅按照纸上的要求，烤好后将菜品装到碟子里，放在原来的托盘上。由服务员再端到顾客面前，顾客们分别拿走自己点的菜品。
> 这家烧烤摊名字叫：Thrift。

这可能是一段迄今为止对 Thrift 最奇怪的比喻。Thrift 是一个 RPC 框架，可将接口的参数转换成二进制数据。下面，介绍 Thrift 两个重要的接口：TProtocol 跟 TTransport。以刚刚烧烤摊为例子，大致可以有以下对应关系（可能有些许不恰当）：

- `TProtocol`：可以有很多不同的顾客，负责写内容
- `TTransport`：托盘 + 服务员，负责传递内容
- TSocketTransport：服务员
- THeaderTransport：托盘
- Socket 连接的 IP 跟端口：桌号
- 传递给服务器的输出流：纸
- 调用接口的入参：纸上的内容
- 传递给客户端的输入流：碟子
- 调用接口的返回值：牛肉串、烤面筋、烤花菜...黑胡椒、孜然...
- 服务器：烧烤师傅

好了，广告结束。相信机智的你看到这里，对 Thrift 有了一定的了解。下面继续我们的 Dart 之旅：

首先要参考 nebula-java 源码，对 GraphServiceClient 进行调用。

这个环节我遇到了两个问题：

- 问题 1：nebula-java 使用的是 fbthrift，而 fbthrift 并没有 Dart 的实现。
    - 解决方案：使用 Apache Thrift 的 Dart 实现。
- 问题 2：两个实现方案有着比较大的差异，比如说 Apache Thrift 没有 THeaderTransport，共同之处是，都有 Socket 的方式。 
    - 解决方案：这里先埋个雷，建立用 Socket 连接再说。

搞定上面两个问题后，我们可以通过 Dart Socket 连接，实现对 NebulaGraph 的访问。

这个步骤怎么说呢？就好像又来了一桌，现在两桌，一桌顾客和服务员都只会闽南语，一桌顾客和服务员都只会普通话。而烧烤师傅啥也不管，只看菜单。新来的这桌只有一个要求，跟隔壁桌点的要一模一样...在两桌语言不通的情况下，没有意外的话，这里要出意外。

好的，我们现在遇到了几个问题：

- 问题 1：返回了空数据，报错信息无从得知  
    - 解决思路：先使用 nebula-java，并对 Socket 发送数据的位置进行断点，将数据拷贝下来，通过 Dart Socket 直接发送，卒。到这个地方，我意识到不得不建立一个可以调试的环境。根据我朴素的直觉，客户端跟服务端应该是一个类似湖面倒影的结构。于是，参考过 nebula-java 客户端的代码后，我决定开了个小灶，建立了一个服务端 Mock，并使用返回伪造数据的方式，实现了 GraphService 接口。此时，服务端就具备了调试的条件。
- 问题 2：怎么确定 Mock 的结构是正确的？
    - 解决思路：使用 nebula-java 客户端，连接 Mock 服务端，看看是否能够正常返回数据。如果能够正常返回数据，Mock 的结构上的准确性也就可以确定。这边调试使用的是不需要太多条件的 verifyClientVersion 接口。

至此，建立如图所示的结构：

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/dart-nebulagraph/arch-demo.jpg)

- 对应关系如下：
  - C1：nebula-java
  - S1：NebulaGraph 数据库
  - C2：nebula_dart_gdbc
  - S2：Mock 测试
- 整体思路如下：
  - L1 是可靠的，可以发送准确数据，也能接收准确数据；
  - L2 可以发送准确数据，用 L2 的连通性来确保 S2 的准确性；
  - 通过 L3 对 C2 进行调试，当 L2 跟 L3 返回的数据一样时，说明此时的 C2 发送的数据是正确；
  - 执行 L4，当 L4 跟 L1 返回的数据一样时，说明 C2 通过 Socket，连接到了数据库。

基本思路确定之后，开始了漫长的翻译（Java 代码变 Dart 代码）、调试，再翻译、再调试...，在 L2 跟 L3 中反复横跳。每个环节的数据表现形式都是纯数字数组，数组长度、下标对应的值错一个都可能功亏一篑。这里需要细心跟耐心。特别是数字操作上涉及到反码、补码、移位的操作，不同的参数有不同的字节长度，按位读写。以下，再列几个 L2、L3 反复横跳的过程中几个让人比较头大的问题：

- 问题 1：Apache 的 Thrift 版本，相比 fbthrift 版本缺了很多类，这里就不一一列举。
    - 解决方案：将缺失的类，从 nebula-java 中的 fbthrift 中翻译，连同所依赖的第三方类也要跟着翻译（所幸依赖的并不多，只有 IO 相关的几个类。所幸做数据压缩的 zip 包有依赖，但实际没用到）。
- 问题 2：结构一样了，但发送的数据还是不一样，Apache 版本中，包括 Socket，用来写数据的容器是 Uint8List，所有放进去的数字都会被强行转成正数，但 fbthrift 中的数据是带正负号的。
    - 解决方案：对所有类型进行修改，全部使用 Int8List 声明跟传输，包括 thrift 生成的类。
- 问题 3：在 Dart 中并没有 byte、short、int、long 的区分，所有的整型都是 int。
    - 解决方案：同样是整数型，需要特别注意，根据实际的情况手动降低整型精度，从而达到与 Java 中声明类型后赋值时自动舍弃精度的效果。

到这里，L3 已经走通，C1 跟 C2 访问 S2，返回的数据一致，拿下模拟考！继续迎接挑战：

- 问题 4：调用 L4，通过 C2 连接到 S1，返回的数据还是空数据，明明 L2 跟 L3 从 S2 拿到的数据都是一样的，这让人很费解。
    - 解决方法 1：改写 Apache 版本下 Socket 的机制，放弃使用创建时就指定消息回调，直接使用 async/await 的方式，使得调试更符合顺序思维。然后，对返回结果进行等待读取。虽然读到的数据依然是空的，不过在 Socket 使用方式上还是保留了这个写法。
    - 解决方法 2：后来，我发现这个问题的原因是，Java Socket 跟 Dart Socket 之间写入的方式不同。在 nebula-java 中，接口间的数据传输使用了 THeaderTransport，数据会分为两段发送的，不确定是不是断点的位置不对，服务端拿到的都是一份两段合并后的数据。而 Dart 中的做法是将两个 `List<int>` 拼接成一段合并发送，在 S2 的表现完全一致，这个问题就很隐蔽，过了相当长一段一行代码不写还不得不保持干活状态的时间。到最后改成在 Dart Socket 的一次传输中，强行将两个 `List<int>` 剥离，使用两个 Stream 进行传输。至此，L4 成功，连通性问题解决，说实话，最后这点带有一丝运气成分。
  
## 封装数据库连接

在这个环节，实现思路中断的情况比较少碰到，整体算流畅，比较花时间的是结果集的处理。

nebula_dart_gdbc，并没有沿用 NebulaGraph 其他客户端的写法。而是整体上参考了 JDBC 的思路，将数据库连接、执行、结果集等进行了封装，形成 dart_gdbc。在这套接口标准下，对 nebula_dart_gdbc 进行实现。

熟悉 JDBC 的朋友，对以下流程就不陌生了，dart_gdbc 的调用流程如下：

- 注册驱动
- 获取连接
- 创建语句
- 执行语句
- 处理结果集
- 关闭连接

以下是 nebula_dart_gdbc 在 dart_gdbc 的规范下的代码示例：

```dart
import 'package:nebula_dart_gdbc/nebula_dart_gdbc.dart';

void main() async {
  // 注册驱动
  DriverManager.registerDriver(NgDriver());

  // 获取连接
  var conn = await DriverManager.getConnection(
    'gdbc.nebula://127.0.0.1:9669/?space=test',
    username: 'root', // username is optional
    password: 'nebula', // password is optional
  );
  
  // 创建语句
  var stmt = await conn.createStatement();
  // 执行语句
  var rs = await stmt.executeQuery(gql: 'SHOW SPACES;');
  // 打印结果
  print(rs);
  // 关闭连接
  conn.close();
}
```

就目前而言，拿到结果集之后，还需要自行按数组下标位进行数据组装。结果集的结构采用“头部数组”+“数据数组”的形式。在实际的开发中，处理上可能会麻烦一些。目前，我正在考虑在 dart_gdbc 未来的版本中，加入对象图映射的埋点回调。或者再开一个 OGM 的项目。关于这一点，目前只是一个还不太成熟的想法。

# 结尾

在文章结束部分，跟大家分享下写这个项目的心路历程。

起初，我对工作量大有一定的心理准备，铁了心想试一试。上手之后，才意识到并不仅仅是语法翻译一下这么简单，特别是不同语言的生态不同，引用的第三方也就随之不同，即使是相同的功能，运行机制也有所不同，这一部分的工作量会比想象中的要大。

再一个就是没有办法对数据库直接断点调试，算是一种黑盒调用，如同凭借着微弱的光线在黑夜中前行，对毫无头绪的问题有时候会产生一种无力感，只能凭借着经验做一些猜测，然后一点点去验证。但当连上实际的数据库，并拿到数据的那一刻，即使多年来已经习惯了被 bug 吊打再消灭 bug 的流程，但还是激动了一下。当开始着手建立 dart_gdbc 规范的时候，在《序》里写到的“责无旁贷”在脑海里回荡。直到今天发布第一个版本，这份热情算多了一份实实在在的兑现。

最后，当然是希望这个项目能够对基础软件生态有所帮助。个人也会不断修复 bug，完善功能，希望能够成为一个稳定可靠的项目。对项目感兴趣的话，欢迎参与开发。另外，dart_gdbc 与 nebula_dart_gdbc 目前收录在【图社区】([https://github.com/graph-cn](https://github.com/graph-cn))，以后有新的关于图的开源项目，也会在这里发布，欢迎围观。

最后的最后，这篇文章及项目的背后有思为和想念小鱼干的清蒸两位老师的帮助，感谢。

# 传送门

- dart_gdbc：[https://github.com/graph-cn/dart_gdbc](https://github.com/graph-cn/dart_gdbc)
- nebula_dart_gdbc：[https://github.com/graph-cn/nebula_dart_gdbc](https://github.com/graph-cn/nebula_dart_gdbc)
- fbthrift: [https://github.com/dudu-ltd/fbthrift](https://github.com/dudu-ltd/fbthrift)

本文带你了解如何使用 nebula_dart_gdbc 在移动设备玩图数据库

用 nebula_dart_gdbc 在移动设备玩图数据库，泰酷辣！

> 本文整理自社区第 7 期会议中 13‘21″ 到 44’11″ 的 Python ORM 的分享，视频见 [https://www.bilibili.com/video/BV1s8411N7Cw](https://www.bilibili.com/video/BV1s8411N7Cw)

在做业务开发时，NebulaGraph Python ORM 项目作者：Sword Elucidator（下文简称：Hao）发现图数据库在某些场景下有比较不错的应用实践，而 NebulaGraph 是他觉得不错、较为先进的一款图数据库产品。在 Hao 的开发过程中，他发现：虽然[图数据库被应用在多个业务场景](https://discuss.nebula-graph.com.cn/c/blog/47-category/47)中，但对于像是 App 开发之类的 ISO/OSI 高层实践的话，nebula-python 之类的客户端就略显笨重。

而 ORM 作为一个能简化 CURD 操作、免去繁琐的查询语句编写的存在，是被广大的 Web 开发者所熟知。但是，目前 NebulaGraph 社区有 Golang 版本的 ORM [norm](https://github.com/zhihu/norm)、Java ORM [NGBatis](https://github.com/nebula-contrib/ngbatis) 和 [graph-ocean](https://github.com/nebula-contrib/graph-ocean) 唯独没有 Hao 所熟悉的 Python 语言的 ORM。

于是，做一个 NebulaGraph Python ORM 的想法便诞生了。

# NebulaGraph Python ORM

## Nebula Carina 名字的由来

NebulaGraph Python ORM，又名 [nebula-carina](https://github.com/nebula-contrib/nebula-carina)，虽然目前只是一个雏形，但是已经基本上具备了一个 ORM 的基础功能。在命名 Python ORM 项目之时，Hao 先想到了 nebula-model，见名便知这是一个 ORM，搞了一些封装。但它不够优雅（~~cool~~），所以 nebula-carina 便诞生了。

Carina 船底座，/kəˈriːnə/，意为龙骨，是南半球可见最大的星云。而一个组件能成为一个 Nebula（星云）还挺酷的。

## Python ORM 功能设计

Nebula Carina 是用 Python 开发的针对 NebulaGraph + Python 的 ORM 框架。在设计上没有局限于 Web 框架，因此可以被应用在 Django、FastAPI 和 Flask 等主流框架上。

目前，Nebula Carina 包含了常规的 schema 定义、对象管理器 object manager（雏形）、Model Builder（雏形），以及常见的图语言、MATCH 语句封装。雏形的意思是，这些功能具备了，但是暂时只有一、两个方法在里面，欢迎阅读本文的你一起来完善。除了基础功能之外，Nebula Carina 还支持了简单的 migration 功能，能够自动计算 schema model 结构与 DB schema 的差异，并同步 schema 到当前 space。但相较于其他成熟的 ORM 项目，例如：Django ORM，Nebula Carina 缺少可回溯性及树状结构来支持 migration 包含依赖、merge 数据。所以，Nebula Carina 未来考虑设计和支持包含依赖关系的 migration 系统。如果你对此有兴趣的话，欢迎来项目：[https://github.com/nebula-contrib/nebula-carina](https://github.com/nebula-contrib/nebula-carina) issue 区交流下。

## Python ORM 的神奇之处

上面简单说了下 Nebula Carina 是什么，有什么功能。在这里，我们来解决下“为什么要用 Nebula Carina”的问题。

**Nebula Carina 首要应对的问题是快速解决轻量级 App 开发的常规需求**，虽然 NebulaGraph 具有极好的性能，诸如美团、快手等大企业都在使用。但大企业和小公司不同，大企业用图数据库会用非常重，像美团就直接开发了个图平台对接集团上百的业务线。而小公司的轻量级应用来说，它需要一个快速地生成简洁 schema。小公司的 Web 开发人员能非常容易地定义常用的、供于业务逻辑使用的 schema，再一键快速将 schema 同步到 space，而不需要去写些 SQL（这里指的是查询语句）来处理这些事项。此外，应对小公司的轻量级 App 开发需求，还需要支持 JSON 序列化和逆序列化来简化接口，不需要在接口处封装各类东西。最后，也是最重要的，为什么不用 Golang 之类的语言 ORM。Nebula Carina 采用了易于使用的 Python Data Model。Python 使用人员可以方便地用 Python 来调用、控制程序，像是打印，或者是在 Python Model 里面将 Dictionary 展开时拥有的 fields 都可以符合标准 Python 规范进行使用。

此外，除了适用于任何的 Python Web Framework，Nebula Carina 也适用于裸 Python 开发，可与 AI 行业快速集成。毕竟像是 Machine Learning 之类的，十有八九是 Python 语言搞的，Nebula Carina 就可以轻松应用在 GNN、NLP 这些用图数据比较多的技术领域。

总之，Nebula Carina 让 Python 开发者使用 NebulaGraph 时能把更多精力运用在业务/模型上，而非繁琐的数据库操作。

## Python ORM 设计实现

目前，Carina 的实现比较简单粗暴，由 4 个部分组成：**settings**、**nGQL 层**、**model 层**和**其他**。

![](https://nebula-website-cn.oss-cn-hangzhou.aliyuncs.com/nebula-blog/nebula-carina-feature.png)

**settings**，搞环境变量。

**nGQL 层**，有 connection、query、record、schema 和 statement：
* query，主要是 condition / match / … 语句封装
* record，主要是 vertex / edge 语句封装
* schema，封装了 Data Types、schema 语句、space 语句封装
* statements，主要是 Order By、Limit、Edge 定义、Edge Value、TTL、Alter 等 statements 的语句封装，statement 的意思是 state 某类行为；

**model 层**，主要是调用 nGQL 层的封装的 class 和当中的方法，来解决一些具体上层的问题。它包括 nebula-python 的 vertex / edge 转成 Carina 的 vertex model / edge model 的 **protocol**，以及 field 和 model（schema model & data model）的封装，同绝大数编程语言的 ORM 类似，定义成某类语言常见的 class 进行封装，参见下方 Figure 类的示例说明；

```python
class Figure(models.TagModel):
    name: str = _(data_types.FixedString(30), ..., )
    age: int = _(data_types.Int16, ..., )
    valid_until: int = _(data_types.Int64, None, )
    hp: int = _(data_types.Int16, 100, )
    style: str = _(data_types.FixedString(10), 'rap', )
    is_virtual: bool = _(data_types.Bool, True)
    created_on: datetime = _(data_types.Datetime, data_types.Datetime.auto)
    some_dt: datetime = _(data_types.Datetime, datetime(2022, 1, 1))
```

上述示例代码，用 Figure class 继承 TagModel，在当中定义 tag 所需的这些 field，比如：name、age…Carina 就是采用这种方式来处理 NebulaGraph 中 Schema 结构；

model 层中的 model builder 则是位于 nGQL 和纯 model 层之间的桥梁。它可以用来描述高层和低层之间的某种行为，比如说，下面的代码就定义了一个全局 MATCH 语句，而所有的 MATCH 语句都会走这样一个函数同 nGQL 层交互：

```python
def match(
    pattern: str, to_model_dict: dict[str, Type[NebulaConvertableProtocol]],
    *, distinct_field: str = None,
    condition: Condition = None, order_by: OrderBy = None, limit: Limit = None
) -> Iterable[SingleMatchResult]:  # should be model
    output = ', '.join(
    ("DISTINCT " if key == distinct_field else "") + key
    for key in to_model_dict.keys()
)
results = match(pattern, output, condition, order_by, limit)
return (
    SingleMatchResult({
        key: to_model_dict[key].from_nebula_db_cls(value.value)
        for key, value in zip(results.keys(), row.values) if key in to_model_dict
    }) for row in results.rows()
) 
```

而 model 层的 object manager 会根据应用场景，基于 schema 为出发点，对 model builder 具体 match 语句进行操作，对这些操作行为搞了个高级封装；migrations 则负责封装 schema model 的变更并同步给数据库；

在**其他模块**，则是 Django 适配的 apps 和 setting。因为要支持 Django，它的思路同 FastAPI 不同，所以需要做适配来让 Carina 无缝衔接 Django；

# Nebula Carina 使用

下面举些例子来让大家了解下 Carina 的使用，主要还是摘录自 Carina 的 README：[https://github.com/nebula-contrib/nebula-carina](https://github.com/nebula-contrib/nebula-carina)

## 安装 Nebula Carina

一句命令搞定

```shell
pip install nebula-carina
```

如果你用的是 Django，那么需要将 nebula_carina 添加到 INSTALLED_APPS，像是这样：

```shell
INSTALLED_APPS = [
    ...
    'nebula_carina',
    ...
]
```

再在 `settings.py` 文件中设置 CARINA_SETTINGS，主要配置一些同 NebulaGraph 有关的信息。像是这样：

```shell
CARINA_SETTINGS = {
    "auto_create_default_space_with_vid_desc": "FIXED_STRING(20)", #创建默认图空间
    "default_space": "main", #图空间名
    "max_connection_pool_size": 10, #连接数大小
    "model_paths": ["nebula.carina"], #model 路径
    "user_name": "root", #登陆 NebulaGraph 的用户名
    "password": "1234", #登陆 NebulaGraph 的密码
    "servers": ["192.168.31.248:9669"], # NebulaGraph graphd 服务所在服务器信息，可配置多个
    "timezone_name": "UTC", #服务器所用时区
}
```

目前 Carina 只有支持上述信息，后续会再增加其他字段。

如果你用的是 FastAPI 之类的，用环境变量即可，具体的话可以参考项目文档：[https://github.com/nebula-contrib/nebula-carina#by-environment-variables](https://github.com/nebula-contrib/nebula-carina#by-environment-variables)。

## 图空间创建

你可以通过下面 Python 语句来创建 Space，当然你也可以像上面 CARINA_SETTINGS 一样，用 `"auto_create_default_space_with_vid_desc": "FIXED_STRING(20)"` 自动创建一个默认图空间。

```python
from nebula_carina.ngql.schema.space import create_space, show_spaces, VidTypeEnum

main_space_name = "main"

if main_space_name not in show_spaces():
    create_space(main_space_name, (VidTypeEnum.FIXED_STRING, 20))
```

## 点边 schema 定义

同点 vertex 不同，一条边只有一个 edgetype，而一个点可以拥有多个 tag。所以在 Carina 中，Model 层的封装，`models.py` 文件里引入了 `VirtualCharacter` 的概念，在 `VirtualCharacter` 类里，定义这个点拥有那些 tag。

```python
class VirtualCharacter(models.VertexModel):
    figure: Figure
    source: Source
```

一个 `figure` 就是一个 tag，`source` 是另外一个 tag 的名字。这里 Figure 和 Source 都是具体的某个 tag 在 Carina 中的映射类名，在示例中，它就叫 Figure、Source。

## 点边数据操作

上文提过 `VirtualCharacter` 的概念，在 Data Model Mathod 里，像下面这种代码：

```
VirtualCharacter(
    vid='char_test1', figure=Figure(
        name='test1', age=100, is_virtual=False, some_dt=datetime(2021, 3, 3, 0, 0, 0, 12)
    ), source=Source(name='movie1')
).save()
```

是定义了一个 VID（唯一标识）为 char_test1 的点，它拥有个名为 Figure 的 tag，这个 tag 中有 name、age、is_virtual 之类的属性。此外，它还有一个 tag Source，Source tag 的属性 name 是 movie1。而 .save() 则是保存这段代码。

同点类似，边的定义是这样的：

```python
EdgeModel(src_vid='char_test1', dst_vid='char_test2', ranking=0, edge_type=Love(way='gun', times=40)).save()
```

这个语句主要表达了一条边的起点是 char_test1，终点是 char_test2，边的 rank 是 0，类型是 Love。而 Love 边类型有 2 个属性 way 和 times，😂 也许这是一对相杀相爱的恋人，滚了 40 次。

# Nebula Carina 再升级

因为个人能力有限，在这里希望借助大家的力量。对 Nebula Carina 的未来规划，主要集中在这些方面

* connection pool (v3.3.0)
* Indexes
* Go / Fetch /  Lookup statements封装
* Bulk操作封装
* Generic Vertex Model
* advanced migrations
…

nebula-python 在 v3.3.0 中对 connection pool 做了原生支持，希望在未来 Carina 能结合这块内容更加完善。

再者就是索引，上面其实提到过，Carina 目前就封装了 MATCH 语句，后续将会对 LOOKUP、GO、FETCH 之类的 statement 字句进行封装。

然后是 Bulk 操作的封装，可以处理一次性创建大量数据。

Generic Vertex Model 则是再抽象 vertex，用户不需要告诉程序它想得到什么样的 vertex，它的结构是如何的。直接通过虚拟结构进行定义，像是上面提到的 Figuer 和 Source，现在我不定义了，Generic Vertex Model 可以把这块抽象好，自己就搞定了。

最后，之前也提到过的 advanced migrations，树状的 migration 可以搞定依赖关系。
 
以上，便是 Hao 贡献的 NebulaGraph Python ORM 的简单介绍。如果你有改进、优化它的 idea，欢迎来 Carina issue 和 pr 区交流哟 [https://github.com/nebula-contrib/nebula-carina/issues/new](https://github.com/nebula-contrib/nebula-carina/issues/new)~

---

**谢谢你读完本文** (///▽///)

NebulaGraph Desktop，Windows 和 macOS 用户安装图数据库的绿色通道，10s 拉起搞定海量数据的图服务。通道传送门：http://c.nxw.so/c0svX

想看源码的小伙伴可以前往 GitHub 阅读、使用、(^з^)-☆ star 它 -> [GitHub](http://c.nxw.so/8yTlk)；和其他的 NebulaGraph 用户一起交流图数据库技术和应用技能，留下[「你的名片」](http://c.nxw.so/9jvQN)一起玩耍呢~  

本文介绍了 NebulaGraph Python ORM 项目的技术原理及实践。

连接 Python，NebulaGraph ORM 项目 Carina 简化 Web、AI 开发

![权力的游戏](https://www-cdn.nebula-graph.com.cn/nebula-blog/game-of-thrones-01.png)

在[上一篇](https://nebula-graph.com.cn/posts/game-of-thrones-relationship-networkx-gephi-nebula-graph/)[1]中，我们通过 NetworkX 和 Gephi 展示了<权力的游戏>中的人物关系。在本篇中，我们将展示如何通过 NetworkX 访问图数据库 [NebulaGraph](https://github.com/vesoft-inc/nebula)。

## NetworkX

NetworkX [2] 是一个用 Python 语言开发的图论与复杂网络建模工具，内置了大量常用的图与复杂网络分析算法，可以方便地进行复杂网络数据分析、仿真建模等工作，功能丰富，简单易用。

在 NetworkX 中，图是由顶点、边和可选的属性构成的数据结构。顶点表示数据，边是由两个顶点唯一确定的，表示两个顶点之间的关系。顶点和边也可以拥有更多的属性，以存储更多的信息。

NetworkX 支持 4 种类型的图：

- Graph：无向图
- DiGraph: 有向图
- MultiGraph: 多重无向图
- MultiDiGraph: 多重有向图

在 NetworkX 中创建一个无向图：
```python
import networkx as nx
G = nx.Graph()
```
添加顶点：
```python
G.add_node(1)
G.add_nodes_from([2,3,4])
G.add_node(2,name='Tom',age=23)
```
添加边：
```python
G.add_edge(2,3)
G.add_edges_from([(1,2),(1,3)])
g.add_edge(1, 2, start_year=1996, end_year=2019)
```

在上一篇文章（一）中，我们已经演示了 NetworkX 的 Girvan-Newman 社区发现算法。

## 图数据库 NebulaGraph

NetworkX 通常使用本地文件作为数据源，这在静态网络研究的时候没什么问题，但如果图网络经常会发生变化——例如某些中心节点已经不存在(Fig.1)或者引入了重要的网络拓扑变化(Fig.2)——每次生成全新的静态文件再加载分析就有些麻烦，最好整个变化过程可以持久化在一个数据库中，并且可以实时地直接从数据库中加载子图或者全图做分析。本文选用 NebulaGraph [3]作为存储图数据的图数据库。

![权力的游戏](https://www-cdn.nebula-graph.com.cn/nebula-blog/tv-game-thrones.png)
Fig. 1

![权力的游戏](https://www-cdn.nebula-graph.com.cn/nebula-blog/tv-game-thrones-02.png)
Fig. 2

NebulaGraph 提供了两种方式来获取图结构：

1. 编写一个查询语句，拉取一个子图；
1. 全量扫描底层存储，获取一个完整的全图。

第一种方式适合在一个大规模的图网络中通过精细的过滤和剪枝条件来获取符合需求的若干个点和边。第二种方式更适合于全图的分析，这通常是在项目前期对全图进行一些启发式探索，当有进一步认知后再用第一种方式做精细的剪枝分析。

分析完 NebulaGraph 两种获取图结构方式后，下面来查看 NebulaGraph 的 Python 客户端代码，nebula-python/nebula/ngStorage/StorageClient.py 与 nebula-python/nebula/ngMeta/MetaClient.py 就是和底层存储交互的 API, 里面有扫描点、扫描边、读取一堆属性等等一系列丰富的接口。

下面两个接口可以用来读取所有的点、边数据：

```python
def scan_vertex(self, space, return_cols, all_cols, limit, start_time, end_time)
def scan_edge(self, space, return_cols, all_cols, limit, start_time, end_time)
```

1. 初始化一个客户端，和一个 scan_edge_processor。scan_edge_processor 用来对读出来的边数据进行解码：
```python
meta_client = MetaClient([('192.168.8.16', 45500)])
meta_client.connect()
storage_client = StorageClient(meta_client)
scan_edge_processor = ScanEdgeProcessor(meta_client)
```
2. 初始化 scan_edge 接口的各项参数：
```python
space_name = 'nba' # 要读取的图空间名称
return_cols = {} # 要返回的边（或点）及其属性列
return_cols['serve'] = ['start_year', 'end_year']
return_cols['follow'] = ['degree']
allCols = False # 是否返回所有属性列，当该值为 False 时，仅返回在 returnCols 里指定的属性列，当为 True 时，返回所有属性列
limit = 100 # 最多返回的数据条数
start_time = 0 
end_time = sys.maxsize
```

3. 调用 scan_part_edge 接口，该接口会返回一个 scan_edge_response 对象的迭代器：
```python
scan_edge_response_iterator = storage_client.scan_edge(space_name, return_cols, all_cols, limit, start_time, end_time)
```

4. 不断读取该迭代器所指向的 scan_edge_response 对象中的数据，直到读取完所有数据：
```python
while scan_edge_response_iterator.has_next():
    scan_edge_response = scan_edge_response_iterator.next()
    if scan_edge_response is None:
        print("Error occurs while scaning edge")
        break
    process_edge(space, scan_edge_response)
```
其中，process_edge 是自定义的一个处理读出来边数据的函数，该函数可以先使用 scan_edge_processor 对 scan_edge_response 中的数据进行解码，解码后的数据可以直接打印出来，也可以做一些简单处理，另作他用，比如：将这些数据读入计算框架 NetworkX 里。

5. 处理数据。在这里我们将读出来的所有边都添加到 NetworkX 中的图G 里：
```python
def process_edge(space, scan_edge_response):
    result = scan_edge_processor.process(space, scan_edge_response)
    # Get the corresponding rows by edge_name
    for edge_name, edge_rows in result.rows.items():
        for row in edge_rows:
            srcId = row.default_properties[0].get_value()
            dstId = row.default_properties[2].get_value()
            print('%d -> %d' % (srcId, dstId))
            props = {}
            for prop in row.properties:
                prop_name = prop.get_name()
                prop_value = prop.get_value()
                props[prop_name] = prop_value
            G.add_edges_from([(srcId, dstId, props)]) # 添加边到 NetworkX 中的图G
```

读取顶点数据的方法和上面的流程类似。

此外，对于分布式的一些图计算框架[4]来说，NebulaGraph 还提供了根据分片 (partition) 并发地批量读取存储的功能，这会在之后的文章中演示。

## 在 NetworkX 中进行图分析

当我们把所有点和边数据都按照上述流程读入 NetworkX 后，我们还可以做一些基本的图分析和图计算：

1. 绘制图：
```python
nx.draw(G, with_labels=True, font_weight='bold')
import matplotlib.pyplot as plt
plt.show()
plt.savefig('./test.png')
```

绘制出来的图：

![NetworkX 绘制的图](https://www-cdn.nebula-graph.com.cn/nebula-blog/game-of-thrones-networkx.png)

2. 打印出图中的所有点和边:
```python
print('nodes: ', list(G.nodes))
print('edges: ', list(G.edges))
```
    输出的结果：
```python
nodes:  [109, 119, 129, 139, 149, 209, 219, 229, 108, 118, 128, 138, 148, 208, 218, 228, 107, 117, 127, 137, 147, 207, 217, 227, 106, 116, 126, 136, 146, 206, 216, 226, 101, 111, 121, 131, 141, 201, 211, 221, 100, 110, 120, 130, 140, 150, 200, 210, 220, 102, 112, 122, 132, 142, 202, 212, 222, 103, 113, 123, 133, 143, 203, 213, 223, 104, 114, 124, 134, 144, 204, 214, 224, 105, 115, 125, 135, 145, 205, 215, 225]
edges:  [(109, 100), (109, 125), (109, 204), (109, 219), (109, 222), (119, 200), (119, 205), (119, 113), (129, 116), (129, 121), (129, 128), (129, 216), (129, 221), (129, 229), (129, 137), (139, 138), (139, 212), (139, 218), (149, 130), (149, 219), (209, 123), (219, 130), (219, 112), (219, 104), (229, 147), (229, 116), (229, 141), (229, 144), (108, 100), (108, 101), (108, 204), (108, 206), (108, 214), (108, 215), (108, 222), (118, 120), (118, 131), (118, 205), (118, 113), (128, 116), (128, 121), (128, 201), (128, 202), (128, 205), (128, 223), (138, 115), (138, 204), (138, 210), (138, 212), (138, 221), (138, 225), (148, 127), (148, 136), (148, 137), (148, 214), (148, 223), (148, 227), (148, 213), (208, 127), (208, 103), (208, 104), (208, 124), (218, 127), (218, 110), (218, 103), (218, 104), (218, 114), (218, 105), (228, 146), (228, 145), (107, 100), (107, 204), (107, 217), (107, 224), (117, 200), (117, 136), (117, 142), (127, 114), (127, 212), (127, 213), (127, 214), (127, 222), (127, 226), (127, 227), (137, 136), (137, 213), (137, 150), (147, 136), (147, 214), (147, 223), (207, 121), (207, 140), (207, 122), (207, 134), (217, 126), (217, 141), (217, 124), (217, 144), (106, 204), (106, 212), (106, 113), (116, 141), (116, 126), (116, 210), (116, 216), (116, 121), (116, 113), (116, 105), (126, 216), (136, 210), (136, 213), (136, 214), (146, 202), (146, 210), (146, 215), (146, 222), (146, 226), (206, 123), (216, 144), (216, 105), (226, 140), (226, 112), (226, 114), (226, 144), (101, 100), (101, 102), (101, 125), (101, 204), (101, 215), (101, 113), (101, 104), (111, 200), (111, 204), (111, 215), (111, 220), (121, 202), (121, 215), (121, 113), (121, 134), (131, 205), (131, 220), (141, 124), (141, 205), (141, 225), (201, 145), (211, 124), (221, 104), (221, 124), (100, 125), (100, 204), (100, 102), (100, 113), (100, 104), (100, 144), (100, 105), (110, 204), (110, 220), (120, 150), (120, 202), (120, 205), (120, 113), (140, 114), (140, 214), (140, 224), (150, 143), (150, 213), (200, 142), (200, 104), (200, 145), (210, 124), (210, 144), (210, 115), (210, 145), (102, 203), (102, 204), (102, 103), (102, 135), (112, 204), (122, 213), (122, 223), (132, 225), (202, 133), (202, 114), (212, 103), (222, 104), (103, 204), (103, 114), (113, 104), (113, 105), (113, 125), (113, 204), (133, 114), (133, 144), (143, 213), (143, 223), (203, 135), (213, 124), (213, 145), (104, 105), (104, 204), (104, 215), (114, 115), (114, 204), (134, 224), (144, 145), (144, 214), (204, 105), (204, 125)]
```

3. 常见的，可以计算两个点之间的最短路径:
```python
p1 = nx.shortest_path(G, source=114, target=211)
print('顶点 114 到顶点 211 的最短路径: ', p1)
```
    输出的结果：
```shell
顶点 114 到顶点 211 的最短路径:  [114, 127, 208, 124, 211]
```

4. 也计算图中每个点的 PageRank 值，来看各自的影响力：
```python
print(nx.pagerank(G))
```
    输出的结果：
```shell
{109: 0.011507076520104863, 119: 0.007835838669313514, 129: 0.015304593799331218, 139: 0.007772926737873626, 149: 0.0073896601012629825, 209: 0.0065558926178649985, 219: 0.014100908598251508, 229: 0.011454115940170253, 108: 0.01645334474680034, 118: 0.01010598371500564, 128: 0.01594717876199238, 138: 0.01671097227127263, 148: 0.015898676579503977, 208: 0.009437234075904938, 218: 0.0153795416919104, 228: 0.005900393773635255, 107: 0.009745182763645681, 117: 0.008716335675518244, 127: 0.021565565312365507, 137: 0.011642680498867146, 147: 0.009721031073465738, 207: 0.01040504770909835, 217: 0.012054472529765329, 227: 0.005615576255373405, 106: 0.007371191843767635, 116: 0.020955704443679106, 126: 0.007589432032220849, 136: 0.015987209357117116, 146: 0.013922108926721374, 206: 0.008554794629575304, 216: 0.011219193251536395, 226: 0.013613173390725904, 101: 0.016680863106330837, 111: 0.010121524312495604, 121: 0.017545503989576015, 131: 0.008531567756846938, 141: 0.014598319866130227, 201: 0.0058643663430632525, 211: 0.003936285336338021, 221: 0.009587911774927793, 100: 0.02243017302167168, 110: 0.007928429795381916, 120: 0.011875669801396205, 130: 0.0073896601012629825, 140: 0.01205992633948699, 150: 0.010045605782606326, 200: 0.015289870550944322, 210: 0.017716629501785937, 220: 0.008666577509181518, 102: 0.014865431161046641, 112: 0.007931095811770324, 122: 0.008087439927630492, 132: 0.004659566123187912, 142: 0.006487446038191551, 202: 0.013579313206377282, 212: 0.01190888044566142, 222: 0.011376739416933006, 103: 0.013438110749144392, 113: 0.02458154500563397, 123: 0.01104978432213578, 133: 0.00743370900670294, 143: 0.008011123394996112, 203: 0.006883198710237787, 213: 0.020392557117890422, 223: 0.012345866520333572, 104: 0.024902235588979776, 114: 0.019369722463816744, 124: 0.017165705442951484, 134: 0.008284361176173354, 144: 0.019363506469972095, 204: 0.03507634139024834, 214: 0.015500649025348538, 224: 0.008320315540621754, 105: 0.01439975542831122, 115: 0.007592722237637133, 125: 0.010808523955754608, 135: 0.006883198710237788, 145: 0.014654713389044883, 205: 0.014660118545887803, 215: 0.01337467974572934, 225: 0.009909720748343093}
```

此外，也可以和上一篇中一样，接入Gephi [5]来得到更好的图可视化效果。

本文的代码可以参见[6].

## Reference
[1] [https://nebula-graph.com.cn/posts/game-of-thrones-relationship-networkx-gephi-nebula-graph/](https://nebula-graph.com.cn/posts/game-of-thrones-relationship-networkx-gephi-nebula-graph/)

[2] [https://networkx.github.io/](https://networkx.github.io/)

[3] [https://github.com/vesoft-inc/nebula](https://github.com/vesoft-inc/nebula)

[4] [https://spark.apache.org/graphx/](https://spark.apache.org/graphx/)

[5] [https://gephi.org/](https://gephi.org/)

[6] [https://github.com/vesoft-inc/nebula-python/pull/31](https://github.com/vesoft-inc/nebula-python/pull/31)


喜欢这篇文章？来来来，给我们的 [GitHub](https://github.com/vesoft-inc/nebula-graph) 点个 star 表鼓励啦~~ 🙇‍♂️🙇‍♀️ [手动跪谢]

交流图数据库技术？加入 Nebula 交流群请先[填写下你的 Nebula 名片](https://wj.qq.com/s2/8321168/8e2f/)，Nebula 小助手会拉你进群~~

> 作者有话说：Hi，我是王杰，是图数据 NebulaGraph 研发工程师，希望本次的经验分享能给大家带来帮助，如有不当之处也希望能帮忙纠正，谢谢~

# 推荐阅读

- [用图机器学习探索 A 股个股相关性变化](https://nebula-graph.com.cn/posts/stock-interrelation-analysis-jgrapht-nebula-graph/)
- [用 NetworkX + Gephi + NebulaGraph 分析<权力的游戏>人物关系（上篇）](https://nebula-graph.com.cn/posts/game-of-thrones-relationship-networkx-gephi-nebula-graph/)


上篇介绍了如何借助可视化工具—— Gephi 来可视化分析《权力的游戏》中的复杂的人物图谱关系，本文侧重展示如何通过 NetworkX 访问图数据库 NebulaGraph。

用 NetworkX + Gephi + NebulaGraph 分析<权力的游戏>人物关系（下篇）

![权力的游戏](https://www-cdn.nebula-graph.com.cn/nebula-blog/game-of-thrones-01.png)

我们都知道《权利的游戏》在全世界都很多忠实的粉丝，除去你永远不知道剧情下一秒谁会挂这种意外“惊喜”，当中复杂交错的人物关系也是它火爆的原因之一，而本文介绍如何通过 [NetworkX](https://networkx.github.io/) 访问开源的分布式图数据库 [NebulaGraph](https://github.com/vesoft-inc/nebula)，并借助可视化工具—— [Gephi](https://gephi.org/) 来可视化分析《权力的游戏》中的复杂的人物图谱关系。

# 数据集

本文的数据集来源：冰与火之歌第一卷(至第五卷)[1]

- 人物集 (点集）：书中每个角色建模为一个点，点只有一个属性：姓名
- 关系集（边集）：如果两个角色在书中发生过直接或间接的交互，则有一条边；边只有一个属性：权重，权重的大小代表交互的强弱。

这样的点集和边集构成一个图网络，这个网络存储在图数据库 [NebulaGraph](https://github.com/vesoft-inc/nebula) [2]中。

# 社区划分——Girvan-Newman 算法

我们使用 NetworkX [3] 内置的社区发现算法 Girvan-Newman 来为我们的图网络划分社区。

以下为「社区发现算法 Girvan-Newman」解释：

> 网络图中，连接较为紧密的部分可以被看成一个社区。每个社区内部节点之间有较为紧密的连接，而在两个社区间连接则较为稀疏。社区发现就是找到给定网络图所包含的一个个社区的过程。
> 

> Girvan-Newman 算法即是一种基于[介数](https://zh.wikipedia.org/wiki/%E4%BB%8B%E6%95%B0%E4%B8%AD%E5%BF%83%E6%80%A7)的社区发现算法，其基本思想是根据边介数中心性（edge betweenness）从大到小的顺序不断地将边从网络中移除直到整个网络分解为各个社区。因此，Girvan-Newman 算法实际上是一种分裂方法。
> 

> Girvan-Newman 算法的基本流程如下：
> （1）计算网络中所有边的边介数；
> （2）找到边介数最高的边并将它从网络中移除；
> （3）重复步骤 2，直到每个节点成为一个独立的社区为止，即网络中没有边存在。

概念解释完毕，下面来实操下。

1. 使用 Girvan-Newman 算法划分社区。NetworkX 示例代码如下

```python
comp = networkx.algorithms.community.girvan_newman(G)
k = 7
limited = itertools.takewhile(lambda c: len(c) <= k, comp)
communities = list(limited)[-1]
```

2. 为图中每个点添加一个 community 属性，该属性值记录该点所在的社区编号

```python
community_dict = {}
community_num = 0
for community in communities:
    for character in community:
        community_dict[character] = community_num
        community_num += 1
        nx.set_node_attributes(G, community_dict, 'community')
```

# 节点样式——Betweenness Centrality 算法

下面我们来调整下节点大小及节点上标注的角色姓名大小，我们使用 NetworkX 的 Betweenness Centrality 算法来决定节点大小及节点上标注的角色姓名的大小。

> 图中各个节点的重要性可以通过节点的中心性（Centrality）来衡量。在不同的网络中往往采用了不同的中心性定义来描述网络中节点的重要性。Betweenness Centrality 根据有多少最短路径经过该节点，来判断一个节点的重要性。

1. 计算每个节点的介数中心性的值
```python
betweenness_dict = nx.betweenness_centrality(G) # Run betweenness centrality
```

2. 为图中每个点再添加一个 betweenness 属性

```python
nx.set_node_attributes(G, betweenness_dict, 'betweenness')
```

# 边的粗细

边的粗细直接由边的权重属性来决定。

通过上面的处理，现在，我们的节点拥有 name、community、betweenness 三个属性，边只有一个权重 weight 属性。

下面显示一下：

```python
import matplotlib.pyplot as plt
color = 0
color_map = ['red', 'blue', 'yellow', 'purple', 'black', 'green', 'pink']
for community in communities:
    nx.draw(G, pos = nx.spring_layout(G, iterations=200), nodelist = community, node_size = 100, node_color = color_map[color])
    color += 1
plt.savefig('./game.png')
```

emmm，有点丑…

![NetworkX 可视化](https://www-cdn.nebula-graph.com.cn/nebula-blog/networkx.png)

虽然 NetworkX 本身有不少可视化功能，但 Gephi [4] 的交互和可视化效果更好。

# 接入可视化工具 Gephi

现在将上面的 NetworkX 数据导出为 game.gephi 文件，并导入 Gephi。

```python
nx.write_gexf(G, 'game.gexf')
```

![Gephi 界面](https://www-cdn.nebula-graph.com.cn/nebula-blog/gephi-01.jpeg)

# Gephi 可视化效果展示

在 Gephi 中打开刚才导出的 `game.gephi` 文件，然后微调 Gephi 中的各项参数，就以得到一张满意的可视化：

1. 将布局设置为 Force Atlas, 斥力强度改为为 500.0， 勾选上 `由尺寸调整` 选项可以尽量避免节点重叠：

Force Atlas 为力引导布局，力引导布局方法能够产生相当优美的网络布局，并充分展现网络的整体结构及其自同构特征。力引导布局即模仿物理世界的引力和斥力，自动布局直到力平衡。

![Gephi 界面](https://www-cdn.nebula-graph.com.cn/nebula-blog/gephi-02.png)

2. 给划分好的各个社区网络画上不同的颜色：

在外观-节点-颜色-Partition 中选择 community（这里的 community 就是我们刚才为每个点添加的社区编号属性）

![Gephi 界面](https://www-cdn.nebula-graph.com.cn/nebula-blog/gephi-03.png)

3. 决定节点及节点上标注的角色姓名的大小：

在外观-节点-大小-Ranking 中选择 betweenness（这里的 betweenness 就是我们刚才为每个点添加的 betweenness 属性)

![Gephi 界面](https://www-cdn.nebula-graph.com.cn/nebula-blog/gephi-04.png)

4. 边的粗细由边的权重属性来决定：

在外观-边-大小-Ranking 中选择边的权重

![Gephi 界面](https://www-cdn.nebula-graph.com.cn/nebula-blog/gephi-05.png)

5. 导出图片再加个头像效果

![权力的游戏](https://www-cdn.nebula-graph.com.cn/nebula-blog/game-of-thrones-02.png)

![权力的游戏](https://www-cdn.nebula-graph.com.cn/nebula-blog/game-of-thrones-03.png)

大功告成，一张权力游戏的关系谱图上线 :) 每个节点可以看到对应的人物信息。

# 下一篇

本篇主要介绍如何使用 NetworkX，并通过 Gephi 做可视化展示。下一篇将介绍如何通过 NetworkX 访问图数据库 [NebulaGraph](https://github.com/vesoft-inc/nebula) 中的数据。

本文的代码可以访问[5]。

**致谢：本文受工作 [6] 的启发**

# Reference

[1] [https://www.kaggle.com/mmmarchetti/game-of-thrones-dataset](https://www.kaggle.com/mmmarchetti/game-of-thrones-dataset)

[2] [https://github.com/vesoft-inc/nebula](https://github.com/vesoft-inc/nebula)

[3] [https://networkx.github.io/](https://networkx.github.io/)

[4] [https://gephi.org/](https://gephi.org/)

[5] [https://github.com/jievince/nx2gephi](https://github.com/jievince/nx2gephi)

[6] [https://www.lyonwj.com/2016/06/26/graph-of-thrones-neo4j-social-network-analysis/](https://www.lyonwj.com/2016/06/26/graph-of-thrones-neo4j-social-network-analysis/)

喜欢这篇文章？来来来，给我们的 [GitHub](https://github.com/vesoft-inc/nebula-graph) 点个 star 表鼓励啦~~ 🙇‍♂️🙇‍♀️ [手动跪谢]

交流图数据库技术？加入 Nebula 交流群请先[填写下你的 Nebula 名片](https://wj.qq.com/s2/8321168/8e2f/)，Nebula 小助手会拉你进群~~

> 作者有话说：Hi，我是王杰，是图数据 NebulaGraph 研发工程师，希望本次的经验分享能给大家带来帮助，如有不当之处也希望能帮忙纠正，谢谢~

# 推荐阅读

- [用图机器学习探索 A 股个股相关性变化](https://nebula-graph.com.cn/posts/stock-interrelation-analysis-jgrapht-nebula-graph/)
- [用 NetworkX + Gephi + NebulaGraph 分析<权力的游戏>人物关系（下篇）](https://nebula-graph.com.cn/posts/game-of-thrones-relationship-networkx-gephi-nebula-graph-part-two/)


本文介绍如何通过 NetworkX 访问开源的分布式图数据库 NebulaGraph，并借助可视化工具—— Gephi 来可视化分析《权力的游戏》中的复杂的人物图谱关系。

用 NetworkX + Gephi + NebulaGraph 分析 <权力的游戏>人物关系（上篇）

在海量数据、企业云、混合云的复杂基础设施运维场景下，利用图数据库图算法的能力做高效的辅助运维工作是一个十分值得的尝试与技术投资。NebulaGraph 作为高性能、开源、分布式的新一代云原生图数据库，是一个很值得考虑的图基础设施选型目标。

运维如何提效？手把手教你用 NebulaGraph 图技术搞定复杂运维系统

一文带你了解 NebulaGraph 的图技术是怎样应用在附近好友、时空交集等常见社交网络场景中的。

标签