@def rss = """ Graft.jl - Julia 的通用图形分析 | 这篇博文描述了我对 Graft.jl (https://github.com/pranavtbhat/Graft.jl) 的工作，这是一个用于 Julia 的通用图形分析包。对于那些不熟悉图形算法的人来说，一个快速介绍 (https://www.cl.cam.ac.uk/teaching/1011/PrincComm/slides/graph_theory_1-11.pdf) 可能会有所帮助.... """ @def title = "Graft.jl - Julia 的通用图形分析" @def authors = """<a href="https://github.com/pranavtbhat">Pranav Thulasiram Bhat</a>"""
这篇博文描述了我对 Graft.jl 的工作，这是一个用于 Julia 的通用图形分析包。对于那些不熟悉图形算法的人来说，一个快速的 介绍 可能会有所帮助。
我的提案，名为 ParallelGraphs，是开发一个并行/分布式图形算法库。然而，在第一个月左右，我们决定转向一个更通用的框架，该框架支持对网络（具有定义在顶点和边上的属性的图形）进行数据分析。我们改变方向的主要动机是
与分布式图形计算相关的挑战。 这 篇博文是一个启发。
只有非常大的图形，大小为 TB 或 PB 级，才需要分布式执行。大多数有用的图形可以在单个计算节点上进行分析。
多线程正在积极开发中，我们决定等待完整的多线程编程模型可用。
当我们查看公共数据集时，我们认为将图形理论分析与现实世界数据相结合的能力是 Julia 中缺失的部分。 LightGraphs.jl 已经为大多数图形算法提供了快速实现，因此我们决定将目标定为图形数据分析。
修改后的提案可以概括为开发一个支持以下功能的包：
顶点和边元数据：顶点和边的键值对。
顶点标记：允许顶点通过任意 Julia 类型在外部进行引用。
SQL 类似的边数据和元数据查询。
与 LightGraphs 的兼容性
ParallelGraphs 实际上是一个错误的名称，因为我们正在转向一个更通用的数据分析框架。因此，我们选择了名称 Graft，它是图形工具包的缩写。以下部分详细介绍了 Graft 的功能
图形通常是现实世界实体及其之间关系的表示。这些实体（及其关系）通常带有附加数据。虽然存储顶点数据相当简单（一个简单的表格就足够了），但存储边及其数据非常棘手。数据应该以源顶点和目标顶点为结构，应该支持随机访问，并且应该为了查询而向量化。
起初我们尝试将边数据放在 SparseMatrixCSC 中。事实证明这是一个坏主意，因为稀疏矩阵是为数值存储而设计的。一个更简单的解决方案是将边元数据存储在 DataFrame 中，并使用 SparseMatrixCSC 将边映射到 DataFrame 的索引。这种策略需要更少的代码，基准测试也更有希望。然而，诸如添加或删除顶点和边的修改变得更加复杂。
大多数图形库不支持顶点标记。通过其（通常很长）的整数标识符来引用顶点可能会非常令人困惑。在包的实现中使用非整数标签在计算上也是很昂贵的（任何此类实现都将涉及字典）。然而，用户没有理由在外部使用整数标签。Graft 支持两种顶点标记模式。默认情况下，顶点由其内部标识符标识。用户可以分配任何任意 Julia 类型的标签来标识顶点，从而覆盖内部标识符。我们认为，这种策略在用户体验和性能之间取得了合理的折衷。
如果顶点标签在内部实现中使用，图形数据结构可能看起来像这样
Dict(
"Alice" => Dict(
"age" => 34,
"occupation" => "Doctor",
"adjacencies" => Dict("Bob" => Dict("relationship" => "follow")))
),
"Bob" => Dict(
"age" => 36,
"occupation" => "Software Engineer",
"adjacencies" => Dict("Charlie" => Dict("relationship" => "friend"))
),
"Charlie" => Dict(
"age" => 30,
"occupation" => "Lawyer",
"adjacencies" => Dict("David" => Dict("relationship" => "follow"))
),
"David" => Dict(
"age" => 29,
"occupation" => "Athlete",
"adjacencies" => Dict("Alice" => Dict("relationship" => "friend"))
)
)显然，在内部使用标签是一个非常糟糕的主意。任何形式的数据访问都会触发多个字典查找。相反，如果可以使用双向映射将标签转换为顶点标识符并反过来，则可以将字典查找次数减少到一次。数据也将更好地构建以进行查询处理。
# Label Map to resolve queries
LabelMap(
# Forward map : labels to vertex identifiers
Dict("Alice" => 1, "David" => 4, "Charlie" => 3, "Bob" => 2),
# Reverse map : vertex identifiers to labels
String["Alice", "Bob", "Charlie", "David"]
)
# Vertex DataFrame
4×2 DataFrames.DataFrame
│ Row │ age │ occupation │
├─────┼─────┼─────────────────────┤
│ 1 │ 34 │ "Doctor" │
│ 2 │ 36 │ "Software Engineer" │
│ 3 │ 30 │ "Lawyer" │
│ 4 │ 29 │ "Athlete" │
# SparseMatrixCSC : maps edges onto indices into Edge DataFrame
4×4 sparse matrix with 4 Int64 nonzero entries:
[4, 1] = 1
[1, 2] = 2
[2, 3] = 3
[3, 4] = 4
# Edge DataFrame
4×1 DataFrames.DataFrame
│ Row │ relationship │
├─────┼──────────────┤
│ 1 │ "follow" │
│ 2 │ "friend" │
│ 3 │ "follow" │
│ 4 │ "friend" │Graft 的查询表示法借鉴了 Jplyr。@query 宏用于简化查询语法，并接受由管道运算符 |> 分隔的一系列抽象。这些阶段通过抽象来描述
接受一个表达式，该表达式在每个顶点上运行。顶点属性可以使用点表示法来表示。一些保留属性是 v.id、v.label、v.adj、v.indegree 和 v.outdegree。示例
# 检查用户是否已覆盖默认标签 julia> @query(g |> eachvertex(v.id == v.label)) |> all # 基尔霍夫定律 :P julia> @query(g |> eachvertex(v.outdegree - v.indegree)) .== 0
接受一个表达式，该表达式在每条边上运行。符号 s 用于表示边的源顶点，t 用于表示边的目标顶点。符号 e 用于表示边本身。边属性可以通过点表示法来表示。一些保留属性是 e.source、e.target、e.mutualcount 和 e.mutual。示例
# 对边、源和目标属性进行算术运算 julia> @query g |> eachedge(e.p1 - s.p1 - t.p1) # 检查组成顶点是否具有相同的出度 julia> @query g |> eachedge(s.outdegree == t.outdegree) # 计算每条边中源顶点和目标顶点之间的“共同朋友”数量 julia> @query g |> eachedge(e.mutualcount)
接受顶点或边表达式，并计算具有顶点子集、边子集或二者兼有的子图。示例
# 删除属性 p1 等于属性 p2 的顶点 @query g |> filter(v.p1 != v.p2) # 从图形中删除自环 @query g |> filter(e.source != e.target)
返回具有顶点属性子集、边属性子集或二者兼有的子图。示例
# 保留顶点属性 p1、p2，而不保留其他属性 @query g |> select(v.p1, v.p2) # 保留顶点属性 p1 和边属性 p2 @query g |> select(v.p1, e.p2)
我们希望用 Graft 支持的典型工作流程是
从内存中加载图形
使用查询抽象来构建新的顶点/边属性或获取子图。
在子图上运行复杂的查询，或将数据导出到 LightGraphs 并在那里运行计算量大的算法。
将数据作为新属性重新带入 Graft，或使用它来修改图形结构。
以下示例应该演示这种工作流程
以及一个信任网络。生成的数据非常荒谬，但很好地展示了 Graft 可以运行的定量查询。
图形 IO：支持更多图形文件格式。
改进查询界面：当前基于管道的宏语法具有学习曲线，宏本身在运行时执行了一些 eval。我们希望转向更干净的可组合语法，该语法将作为常规 Julia 命令传递。
新的抽象，例如分组、排序和表格输出。
数据库后端：可以使用 RDBMS 代替 DataFrames。或者 Graft 可以作为 Neo4j 等 GraphDB 的包装器。
与 ComputeFramework 集成，以进行内核外处理。支持并行 IO、遍历和查询。
更多信息可以在 这里 找到
这项工作是在导师的指导下，作为 Google Summer of Code 计划的一部分进行的：Viral B Shah 和 Shashi Gowda。