图优算法笔记¶

动态图的流式处理实践：概念、模型和系统
- 图相关背景知识
  - 图模型：边集、点集、边权、度
  - 图的表示：邻接表、邻接矩阵、边列表和稀疏压缩行(CSR算法)
  - 图的访问：图的查询和更新
- 相关概念澄清
  - 动态图和流图的应用
    - 流图、动态图和时间演化图
      - “动态”是指代正在修改的图数据集、“流"是指传入图访问或更新的形式、“批处理”是指一次摄取一定数量的图更新。
    - 图形数据库和NoSQL 存储
    - 历史图处理
    - 时间图算法
    - 通用数据流和流系统
  - 动态图和流图的理论
    - 流图算法
      - 流图算法中，从一空白的图开始，在每个算法步骤中，将新的边插入到图中，或者删除现有的边。
      - 通过空间复杂度、更新时间、查询时间、计算结构属性的准确性和预处理时间来对算法进行评估。
      - 目标是开发最小化不同参数值的算法，特别关注最小化图形数据结构的存储。
      - 虽然空间复杂性是主要关注点，但大量的工作致力于优化流传输算法的运行时间，特别是处理边缘更新的时间以及恢复最终解的时间。
      - 实用设置中的适用性当对保留处理后的图形所允许的最大空间有严格限制并且需要非常快速地更新每条边时，可以使用流式处理算法。
      - 这些算法中的大多数都预先假设了某些结构图的属性，最常见的是顶点数n。
    - 草图算法和动态图形流
      - HYPERLOGLOG 来对图进行压缩，用压缩后的图的连通性、割点割边和最短路等属性来近似原有图的属性。
    - 动态图算法
      - 在边插入和删除下近似感兴趣的输入图的组合属性（例如连通性、最短路径距离、切割、光谱属性）；尽量减少进行图形更新的时间。
      - 并行动态图算法
        
        一个图是通过批量更新来修改的。批处理大小通常是n 的函数，例如log n 或√n。每个批中的更新可以并行地应用于一个图。
        
        使用批处理的动机有两个：将并行性纳入摄取更新；降低每次更新的成本。
        
        MPC（大规模并行计算）动态算法：结合MapReduce 等分布式动态框架和并行批处理动态图算法。
- 框架分类标准
  - 获取更新、维护历史数据、动态图展示、增量更新、编程API和模型
  - 动态图表示的框架结构
    - 基本图的表示：AL、EL、CSR 和AM 基本图形表示方法与一些其他基于树的数据表示（用于加速动态查询）
    - 区块划分和区块间联系：通过结合CSR 和AL 的方式，既保留了AL 便于修改的优点，又保留了CSR 局部性较好的优点。
    - 支持的顶点和边数据类型：边权和点权、边更新时间戳。
    - 索引结构：增加相关查询索引来加快图结构、数据和历史相关数据的查询。
  - 图存储架构和突变
    - 并发查询和更改
      - 粗粒度同步：快照技术，更新和查询通过在图数据的两个不同副本(快照) 上执行而相互隔离；在某些时候，这些快照被合并在一起。写时复制、墓碑机制；分批接收更新并且赋予ID 进行排序。
      - 细粒度同步：更新一到达就被合并到主数据集中，通常与查询交织，使用基于细粒度锁或原子操作的同步协议。差分数据流设计操作的是带有时间戳和增量值的键值对集合。它将动态数据视为输入集合的添加或删除，并使用逻辑时间跟踪它们的演变。
    - 图查询和图更新可能非并发执行，而是交替执行，这种类型的体系结构可以实现高比率的更新消化，无需考虑图一致性。
    - 事务支持：能够隔离并发访问并从潜在故障中正确恢复的工作单元，并非所有系统都支持ACID（原子性、一致性、隔离性和持久性）事务管理。
  - 历史数据维护框架
    - 存储历史快照，通过保存快照本身或者维护对图的更改来保存历史数据；保存快照的方式存储开销较大，维护对图的更改会导致构建耗时较高。
    - 历史图更新可视化，快照模式、滑动窗口模式和边缘衰减模型，pf (e) = f(t − t(e)) 非递减衰减函数。
  - 增量计算架构
    - 流式框架采用一种称为“增量更改”的方法，以加快图形算法的收敛速度。
    - 增量变化背后的关键观察是，后续的图表更新不一定会导致派生的页面排名值发生大的变化。
    - 离线模式的增量修改是通过重新计算更新分析结果；在线模式的增量修改则是跟踪修改值之间的依赖关系（即时），并使用这些依赖关系从值受到影响的点开始简单地调整必须更新的值，而无需重新启动计算。
      - 这里类似于kickstat图修建算法，通过在边插入时计算依赖关系；在删除边时查找依赖关系并进行更新，直至图收敛。
  - 编程支持的API 和模式
    - 图更新API 包括基本功能（边的插入）、复杂功能（合并两张图）、特定更新时发生的触发事件的API 和访问操作等待中的图更新。
    - 图分析API 是用于在维护的图之上运行图计算的函数，包括控制图的算法如PageRank、处理图形快照、控制在过去的快照之上运行的此类计算和增量处理的相关API 与模型。
  - 框架的一般特征
    - 图数据的存储位置内存/显存
    - 分布式
    - 目标硬件架构CPUs/GPUs
    - 通用系统/图形分析专用系统
- 框架分析
  - 图存储架构和突变
    - 大多数框架采用快照机制，墓碑机制、写时复制等技术
    - 某些框架采用细粒度锁机制，这导致仅在精细读取方面支持更新和读取查询的交错，不能在全局查询过程中并行摄入更新。
    - 更新调度策略，系统使用通过专门调度程序增强的细粒度同步，该调度程序操纵应用传入更新的顺序和时间以最大化吞吐量和最小化延迟。
    - 更新的摄取与查询信息的传输重叠，例如通过PCIe。
    - 只有少数框架支持ACID 事务，性能和高读取速率高于系统健壮性。
  - 历史数据维护框架
    - Tegra 采用分布式快照索引技术将保存快照和维护图更改结合起来使用，优化性能，无需存储从开始到某一时刻的快照。
    - STINGER 或ZipG 等系统支持维护图突变的时间戳，这有助于在选定的时间点上获得图状态，无相应的API。
    - 保留过去快照的系统通常采用一些额外的形式来跨快照重用图形结构，以减少内存开销。
    - GraphTau 和Tegra 系统支持滑动窗口模型，这些系统可以保存快照并且获得快照之间的差异。
    - Kineograph 唯一支持更新可见性指数衰减模型的系统。
  - 图表示的框架结构
    - CSR+EL：EL 用于存储历史数据。
    - AL：图更新灵活性，但局部性较差。
    - CSR 分块：局部性和更新时间进行权衡；块越小，更新图就越容易，但同时遍历顶点邻域需要更多的随机内存访问。较大的块可以改善遍历的局部性，但需要更多时间来更新图形结构。
    - 少数框架采用基于树的图存储方式，例如PMA。
    - 在更通用的基础设施之上构造的框架使用底层系统提供的表示；框架由通用处理系统或数据库利用的数据表示。
    - 索引结构，基于CSR 的框架的标准设计等。
    - 流式框架与图数据库不同，它更多地关注图结构，而不是丰富的附加数据。
  - 增量计算体系结构分析
    - 近半数的框架提供增量更改的支持，并且大多数是基于离线模式，通过一定机制来确定那些顶点需要重新计算来更新分析结果，以反映最近的图突变。
    - Tegra 为过去快照合并进行增量计算，来保存和分析历史数据。
    - 有一些系统是在线模式。例如GraphBolt 和KickStarter 都跟踪正在计算的顶点值与边修改之间的关系。在许多图形算法中，顶点值只是从一个单一的传入边中选择的。改进版本：DZiG、GraphInc 和RisGraph。
    - 几乎所有支持增量变化的系统都关注于单调图算法，即计算属性(例如顶点距离) 一致地增加或减少的算法。GraphBolt、DZiG 和Tegra 也涵盖了非单调算法。如信念传播、协同训练期望最大化或协同过滤。
  - 提供的编程API 和模型的分析
    - 图更新
      - 所有图框架均支持一简单API 来完成对图的基本操作，例如添加和删除边。
      - Concerto 编程触发事件，事件在某些特定的图形修改后自动发生。
      - DeltaGraph 合并不同图形的函数。
      - GraphOne 支持访问和分析仍在等待被摄取到主图形结构中的更新，可用于预处理/分析。
    - 图分析
      - 大部分框架不支持动态的图分析，其他图框架提供处理主快照的相关API 函数，大多利用现有的编程模型例如BSP。
      - Tegra 也提供了用于在这些快照上运行分析的api，需要用户指定特定过去的快照。
      - 部分框架提供增量处理的相关API，主要包括识别那些顶点需要重新计算并筛选出的顶点进行重新计算聚合。
      - Tegra 两个函数，diff 和expand，前一个返回前后快照的差值，后者对子图进行1 邻域扩展。
      - 补充BSP 相关概念：计算、同步、交换，重复上述三个过程，减少竞争。
  - 支持的图形更新类型
    - 边的插入与删除，顶点的插入与删除；给定顶点与其相邻边一起被移除。
  - 分布式设计
    - 流框架依赖于底层分布式来支持更大的数据集以及增加吞吐量。
  - 计算和存储比较
    - 不同框架关注点可能不同，例如计算和存储。
- 框架的选择和讨论
  - 大体浏览了一遍，暂未做笔记
- 参考链接
KickStarter：通过修剪近似对流图进行快速准确的计算
- KickStarter算法是一种图修剪算法，主要要实现的是在动态图删除边时快速完成对图边权点权的收敛计算，由于图在删除边时点权会较多点的点权受到影响，如果为了计算精确结果而对所有点权进行计算则时间复杂度较高；为此提出了KickStarter算法，KickStarter算法通过动态跟踪图插入边并动态更新点权依赖关系，在删除边时只需要查询相关依赖被破坏的点并计算即可，从而达到降低时间复杂度的效果。
- kcikstarter主要利用了单调性原理来减少边删除后更新点权的计算次数。
- KickStarter支持两种修剪方法。第一种方法使用标记机制识别可能受边缘删除影响的顶点集，该标记机制还利用算法洞察力。
- 在第二种方法中，KickStarter在计算发生时在线跟踪顶点之间的动态相关性（即，哪个顶点的值对给定顶点的值的计算有贡献）。寻找安全的近似值（消除循环，寻找不包含在闭包依赖中传入边，维护等级）；何时停止（一旦为顶点找到安全值，KickStarter 就会检查该值是否会破坏单调性）
GraphOne：用于实时分析进化图的数据存储
- 批分析和流分析执行不同类型的数据访问，即前者访问整个图，而后者侧重于时间窗口内的数据。
- 边缘日志以边缘列表格式保留最新更新，旨在加速数据摄取。同时，邻接存储以邻接列表格式保存旧数据的快照，这些快照会定期从边缘日志中移动，并针对批处理和流分析进行了优化。
- GRAPHONE 使用边日志的时间特性强制数据排序，并在邻接存储中保持每个顶点的边到达顺序不变。然后，双版本控制技术利用边缘列表格式的细粒度版本控制和邻接列表格式的粗粒度版本控制来创建实时版本。
- 两种优化技术，缓存行大小的内存分配和幂律图的高度顶点的特殊处理，以减少版本化邻接存储的内存需求。
- 支持两种类型的 GraphView：(1) 静态视图提供最新数据的实时版本控制，用于批量分析； (2) 流视图支持具有最新更新的流分析。这些视图在两个粒度级别提供数据更新的可见性以进行分析，其中边缘日志用于在边缘级别提供它，而邻接存储以粗粒度的更新提供相同的信息。
- 使用边缘列表格式创建细粒度快照。图形分析和查询在执行期间需要最新数据的不可变快照。边缘列表格式为细粒度快照创建提供了自然支持，而无需创建物理快照，因为它具有时间特性，因为跟踪快照只是记住边缘列表中的偏移量。同时，邻接列表格式通过其粗粒度快照功能 [54, 26] 用于补充边列表。
- 在混合存储中同时使用边缘列表和邻接列表。边缘列表格式保留了数据到达顺序并为快速更新提供了良好的支持，因为每次更新都简单地附加到列表的末尾。另一方面，邻接表保留了源顶点索引的顶点的所有邻居，这为图形分析提供了高效的数据访问。因此，它允许 GRAPHONE 实现高性能图形计算，同时支持细粒度更新。
GraphBolt：流图的依赖驱动同步处理
- 算法示意图，需要维护历史值和依赖关系网
- 增量算法旨在通过重用图结构发生变化之前计算的结果来最小化冗余计算。
- 虽然增量处理使系统响应更快，但直接重用中间值通常会导致算法产生不正确的结果。此外，这些不正确的结果成为执行后续增量处理的基础，这会导致随着时间的推移越来越不准确。
- GraphIn 和 KickStarter 等解决方案增量转换中间结果，首先使它们与更新的图形一致，然后使用转换后的结果计算最终答案。此类转换通常基于单调收敛（路径长度或组件 ID）等算法属性，这使得它们适用于图算法的选定子类（例如，单调）
- BSP语义，即批量同步并行；BSP包含三个阶段：计算，同步和交换。
- 差分数据流 [25] 通过差异（或更改）反映流中变化的影响来增量处理广义流。它的优势在于它的微分运算符可以捕获并直接计算差异，并且足够通用以支持任何迭代增量计算。
- 水平修剪是通过在某些迭代后直接停止对聚合值的跟踪来实现的。
- 垂直修剪在顶点级别进行操作，并且通过不保存已稳定的聚合值来执行。
STINGER：流图的高性能数据结构
- 数据结构基于块的链表。通过添加额外的顶点和边块，顶点和边的数量可以随时间增长。顶点和边都有类型，一个顶点可以有多种类型的入射边。
- 入射到给定顶点的边存储在边块的链表中。边表示为相邻顶点 ID、类型、权重和两个时间戳的元组；给定块中的所有边都具有相同的边类型；该块包含元数据，例如最低和最高时间戳以及块内有效边缘的高水位线。
- 边缘类型数组 (ETA) 是指向给定类型的所有边缘块的二级索引。在边缘并行的连接组件等算法中，这种访问数据结构的附加模式允许在并行 for 循环中探索所有边缘块。/ STINGER 提供了边缘类型数组（ETA）索引数据结构。 ETA 包含指向具有给定类型边缘的所有块的指针，以加速在特定边缘类型上运行的算法。
- STINGER 必须能够响应新的和更新的边缘。提供了并行插入、删除、递增和接触边缘的功能；可以查询图的入度和出度，以及图中顶点和边的总数。
- 通过批处理、细粒度锁来并行处理，加快处理速度。
- DISTINGER是STINGER的分布式版本；cuSTINGER扩展了CUDA GPU的STINGER。
- STINGER官方文档： http://www.stingergraph.com/index.php?id=documentation
Tornado：一个对不断变化的数据进行实时迭代分析的系统
- 怀疑下列公式打错了，
- 在主循环中，我们不断收集传入数据并在当前时刻近似计算结果。令 ∆Si 为第 i 次迭代中收集的输入，为第 i 次迭代中的近似值，则我们有，其中 g 是近似函数。
- 随机梯度下降 (SGD) 通过使用观察实例的无偏采样来近似梯度，从而避免了昂贵的梯度计算。无偏抽样通常通过随机抽样来完成。
- 迭代模型
- 分布式快照算法: Chandy-Lamport 算法
使用压缩纯函数树的低延迟图流
- C Tree
- 图一是普通的图、图二为边树、图三为CTree优化的边树。
控制有状态流图处理的内存占用（主要对GraphBolt进行优化）
- 在每次迭代中与顶点相关的值方面的中间状态。每个中间值由聚合值（增量合并差异）和顶点值（计算输出差异）组成。
- 无状态迭代模型 & 有状态迭代模型 ( KickStarter(只保留一次中间状态), GraphBolt(保留从开始到结束的中间状态))
- 选择性有状态迭代模型
  - 只选择其中一部分顶点来记录其中间状态（跟踪顶点和未跟踪顶点），减少内存开销。
  - 跟踪排名最高的前 k 个顶点的中间状态，利用大顶堆维护。
  - 应该跟踪多少个顶点？k是跟踪状态的顶点数、state_size是中间顶点状态的大小、mem_budget是可用内存容量、base_size是其他消耗的内存系统中的数据结构
  - 优化布局，未跟踪顶点和跟踪顶点分别单独存储
  - 如果目标顶点未被跟踪，则旧值（来自图突变之前）和新值（由图突变产生）都沿着边传播。
  - 对于跟踪的顶点，中间状态随着迭代处理的进行而逐步细化。而对于未跟踪的顶点，随着处理通过迭代进行（类似于从头开始计算，没有中间状态），单个向量被维护以保存它们的最新值。在每次迭代中，跨边传播的值基于目标顶点是被跟踪还是未被跟踪，如图 6b 所示。如果跟踪目标顶点，则值的差异将沿着其传入边传播，类似于传统的依赖驱动增量处理。
  - 根据目标顶点是被跟踪（突出显示）还是未被跟踪传播的值。未跟踪的顶点接收旧值和新值，而跟踪的顶点直接接收值的差异
- 最小状态迭代模型
  - 专门针对某些算法进行增量处理，例如PageRank等，此类算法可以根据顶点的传入值变化直接计算给定顶点的传出值变化（新颖的分布式更新属性）。
  - 针对某些图形算法的增量处理来积极消除中间状态的跟踪。
  - ⊕是将传入值组合到顶点的聚合函数，S是将源值转换为聚合的函数，A是使用聚合结果
  - 分布式更新属性指出顶点值的计算可以作为子计算分布在其传入邻居的值上；γ 和 α 是从 A 派生的函数
  - 在每次迭代时不计算中间状态的情况下传播差异，但这些差异需要以某些基础为基础。
RisGraph：一个用于进化图的实时流系统，以百万次操作/秒的速度支持亚毫秒级每次更新分析（主要对KickStarter进行优化）
- 本地化数据访问
  - 本地化数据访问背后的基本原理是增量计算只需要访问部分顶点，但不正确的数据结构将需要部分计算来访问整个图。系统应该使用适当的数据结构来避免不必要的操作。
  - 稀疏数组和密集数组、位图，使用稀疏数组跟踪活动顶点和更新结果，以消除扫描所有顶点的冗余开销
  - 边并行和点并行策略，普遍结论点并行优于边并行，局部性更好
  - 索引邻接列表
- 并行处理更新
  - 一种特定于域的并发控制机制，以低开销支持多个更新之间的并行性，从而提高吞吐量。它利用增量模型和中间数据结构在处理它们之前识别非冲突更新。
  - 不改变任何结果的更新命名为安全更新。相应地，不安全的更新会修改结果或依赖树。
  - 三种安全状态
    - (1) ins_vertex(v) 或 del_vertex(v) 对于任何顶点𝑣。该操作仅在𝑣为孤立顶点时有效（用户在删除𝑣之前必须先删除与𝑣相关的所有边），因此不会影响单调算法的结果[77]。
    - (2) del_edge(e) for 𝑒 ∉ 𝐸𝑇 ，比如边⟨𝑣2，𝑣3⟩。这些删除不会修改依赖树，因此不会改变任何结果。相反，删除⟨𝑣1、𝑣2⟩或⟨𝑣1、𝑣3⟩将分别使𝑣2或𝑣3的状态无效。
    - (3) ins_edge(e) for 𝑒 = ⟨𝑣𝑠 , 𝑣𝑡 ⟩ 当 need_upd(vt, vt.data, gen_next(e, vs.data)) 为假时。以边插入⟨𝑣0，𝑣2⟩为例，我们首先从源𝑣0和新边𝑒计算出目标𝑣2的新结果。如果 𝑒 不能产生比 𝑣2 的当前结果更好的结果，则插入是安全的。
  - RisGraph 将更新分为安全 (S)、不安全 (U) 和下一纪元 (N)。不安全更新后，同一会话中的所有更新都是下一纪元更新，这意味着它们应该在下一个纪元中重新分类，因为任何不安全操作都可能修改结果并更改其背后更新的分类。 RisGraph 并行处理多个安全更新，利用更新间并行性。
  - 如果某些会话持续产生安全更新，RisGraph 将使不安全的更新处于饥饿状态，RisGraph 的调度器控制每个 epoch 的大小，并尽可能满足用户期望的尾部延迟。
Ligra：用于共享内存的轻量级图形处理框架
- EDGEMAP 和 VERTEXMAP 函数
使用动态图神经网络的动态网络的基础和建模：一项调查
GraphBolt代码阅读
- GraphBolt相关函数
  - GraphBolt 框架的一个关键设计决策是确保应用程序代码保持对 GraphBolt 内部微妙之处的无视，同时仍然提供快速性能。
  - 因此，应用程序代码只需要使用以下函数来表达其计算。
  - AggregateValue 和 VertexValue 初始化：
    - initializeAggregationValue()
    - initializeVertexValue()
    - aggregationValueIdentity()
      - 返回聚合值的标识值。对于求和，标识值为 0。对于求积，标识值为 1。
    - vertexValueIdentity()
      - 返回顶点值的标识值。对于求和，标识值为 0。对于求积，标识值为 1。
    - GraphBolt 以聚合值的形式存储每个顶点的信息。因此，首先，用户应该确定算法的聚合值和顶点值。例如在 PageRank 中，顶点值是其 pagerank (PR)，聚合值是其所有 inNeighbors 的 (PR[u]/out_Degree[u]) 值之和。
  - 为给定的迭代激活顶点/计算顶点：
    - forceActivateVertexForIteration()
      - 用于确定在给定迭代中是否应强制顶点处于活动状态。例如，在 PageRank 中，所有顶点在第一次迭代中都应该处于活动状态。在 CF (ALS) 中，在第一次迭代中，所有 partition2 顶点都应该处于活动状态，在第二次迭代中，所有 partition1 顶点都应该处于活动状态
    - forceComputeVertexForIteration()
      - 默认情况下，所有从其 inNeighbor 接收到一些变化的顶点都将计算它的值。对于某些算法，我们需要计算顶点的值，而不管该顶点是否在该次迭代中收到任何更改。此函数用于在给定迭代中强制计算顶点。
    - shouldUseDelta()
      - 通常，对于第一次迭代，顶点将整个值传播到它的 outNeighbor。例如，此函数应为 iter=1 返回 false，并为其他迭代返回 true。对于 CF，我们有 2 个分区。因此，函数应该为 iter=1 或 iter=2 返回 true。使用此函数自定义何时应执行基于增量的增量计算
    - 在迭代图算法中，在给定的迭代 i 中，一组顶点会将一些值推送到它们的 outNeighbors。这些是该迭代的活动顶点。收到这些值的 outNeighbors 将计算它们的更新值。提供以下函数以强制顶点在给定迭代中处于活动状态/计算状态。例如，在 Label Propagation 中，所有顶点都应在每次迭代中计算它们的值，而不管它们是否在该迭代中从其 inNeighbors 接收到任何新更改（请参阅 apps/LabelPropagation.C）。
  - 添加到聚合或从聚合中删除：
    - addToAggregation()
    - addToAggregationAtomic()
    - removeFromAggregation()
    - removeFromAggregationAtomic()
    - 这些是用于向聚合值添加值或从聚合值中删除某些值的函数。对于 sum，它只是简单地从传递的聚合值中添加和减去值。请注意，addToAggregationAtomic() 和 removeFromAggregationAtomic() 将由多个线程在同一聚合值上调用。因此，应该使用 CAS 以原子方式执行更新。
  - 边缘功能：
    - sourceChangeInContribution()
      - 对于边 (u,v)，边函数分 3 个步骤执行：(1) 源顶点贡献的变化，它处理特定于该源顶点的计算，(2) edgeFunction 合并了特定的计算到那条边，以及 (3) 使用 addToAggregationAtomic 将边 (u, v) 的最终 change_in_contribution 聚合到 v 的 aggregate_value 中。
      - 对于顶点 u，给定它在当前迭代和先前迭代中的值，计算 change_in_contribution。对于 PageRank 中的顶点 v，相同的值 (PR[v]/out_degree[v]) 必须被推送到它的所有 outNeighbors。在基于增量的计算的情况下，它推出 (PR_curr[v] -PR_prev[v])/out_degree[v]。注意：change_in_contribution 可以直接就地更新。更新 u_change_in_contribution 不需要 LOCKS/CAS
    - edgeFunction()
      - 对于顶点 u，给定其在当前迭代中的值及其计算的 change_in_contribution，更新给定边 (u, v) 的 change_in_contribution。例如，在Label Propagation中，(u, v)的edge_data乘以每个factor的change_in_contribution。如果来自 u 的值不应包含在 v 的聚合值中，则返回 false。否则返回 true。注意：对 change_in_contribution 的更改应该到位。更新 u_change_in_contribution 不需要 LOCKS/CAS
    - edgeFunctionDelta()
    - 边缘操作分为 3 个阶段：
      - 确定源贡献 - 此处执行仅依赖于源值的给定顶点的计算。例如，在 PageRank 中，顶点 u 将值 PR[u]/out_degree[u] 添加到其所有 outNeighbors 的聚合值。由于 PR[u]/out_degree[u] 的计算对于处理 u 的所有 outEdges 是常见的，我们可以只计算一次这个值（源顶点的贡献）并对所有 outEdges 执行加法。
      - 根据边数据转换贡献 - 在此步骤中，源顶点贡献由边属性转换。例如在加权页面排名中，贡献将乘以边缘权重。
      - 使用 addToAggregationAtomic() 聚合对聚合值的贡献。
      - 请注意，这些函数不需要 CAS 或锁。在复杂聚合的情况下，必须定义一个额外的 edgeFunctionDelta()。有关这些函数的更多详细信息，请参阅 apps/GraphBoltEngine.h、apps/GraphBoltEngine_complex.h。
  - 顶点计算函数并确定计算结束：
    - computeFunction()
    - notDelZero()
    - 给定一个聚合值，computeFunction() 计算对应于该聚合值的顶点值。为了确定收敛条件，使用 notDelZero() 来确定顶点的值与其之前的值相比是否发生了显着变化。这两个函数都不需要 CAS 或锁，因为它们将以顶点并行方式调用。
  - 确定边缘更新如何影响源/目标：
    - hasSourceChangedByUpdate()
      - 对于给定的边添加 (u, v)，定义它如何影响第一次迭代中的源顶点。 activateInCurrentIteration 定义源顶点是否在第一次迭代中处于活动状态。例如，在 PageRank 中，如果 u 的 out_degree 发生了变化，那么推送到其所有 outNeighbors 的 u 的值也会发生变化。因此，如果更新图中的 out_degree(u) 不等于其在先前版本图中的 out_degree，则返回 true。否则，返回假。注意：确保将给定图形版本所需的相关信息（用于算法/应用程序）存储在 global_info 对象中。示例：必须为给定图形存储所有顶点的出度。 forceComputeInCurrentIteration 定义源顶点是否必须在第一次迭代中重新计算。例如，在 COEM 中，如果顶点的 inWeights 总和发生变化，则应在第一次迭代中为该顶点调用 computeFuntion()。
    - hasDestinationChangedByUpdate()
      - 对于给定的边添加 (u, v)，定义目标顶点是否已更改。 activateInCurrentIteration 定义目标顶点是否在第一次迭代中处于活动状态。注意：确保将给定图形版本所需的相关信息（用于算法/应用程序）存储在 global_info 对象中。示例：必须为给定图形存储所有顶点的出度。 forceComputeInCurrentIteration 定义是否必须在第一次迭代中重新计算目标顶点。
    - 这些函数用于定义边更新如何影响源和目标顶点，即是否应在第一次迭代中激活顶点或重新计算其值（使用 computeFuntion()）。例如，在 PageRank 中，如果一个顶点的 out_degree 发生变化，那么它将在第一次迭代中处于活动状态。而在 COEM 中，如果一个顶点的 inWeights 之和发生变化，那么它的值应该在第一次迭代中计算。
  - 计算函数
    - compute()
    - 这是应用程序的起点。 GraphBolt 引擎在此处使用所需的配置进行初始化并启动。
    - 除了这些功能之外，该算法还需要定义一个 Info 类，其中包含该应用程序所需的所有全局变量/常量。它应该实现以下功能：
    - copy()
    - processUpdates()
    - cleanup()
  - frontier_curr & changed 的前后变化
    - frontier_curr初始化为false，changed数组初始化为false
    - hasSourceChangedByUpdate判断前后度是否变化来对于frontier_curr进行初始化
    - 如果frontier_curr[source]和frontier_curr[destination]为激活则changed[source]值为true
    - 激活顶点向邻居发送增量更新，同时如果edgefunction为true则置changed数组为true，强制其在本轮迭代中计算顶点值
    - 清空frontier_curr并根据changed数组进行聚合值收集并修改顶点值
    - 判断是否要在下一次迭代中必须激活更新front_curr数组
    - 判断前后权值变化是否超过阈值判断是否要激活front_curr数组
    - 遍历增加的边和删除的边重复更新changed数组
  - vertex_value_old_curr、vertex_value_old_prev 一点更新时疑惑？
- KickStarter相关函数
  - KickStarter 引擎用于流式传输基于路径的/单调图算法，如 SSSP、BFS 等。
  - 与GraphBolt引擎类似，KickStarter引擎也提供了表达算法的函数。
  - 顶点值初始化：
    - initializeVertexValue()
  - 为第一次迭代激活顶点/计算顶点：
    - frontierVertex()
  - 与 GraphBolt 引擎不同，我们只需要知道哪些顶点在第一次迭代中处于活动状态。
  - 边缘功能：
    - edgeFunction()
    - 对于边 (u, v)，根据 u 的值计算 v 的值。如果来自 u 的值不应用于更新 v 的值，则返回 false。否则返回 true。
  - 传播：
    - shouldPropagate ()
    - shouldPropagate 条件用于确定顶点的单调性是否保持给定的 2 个值，具体取决于算法。
  - 计算函数
    - compute()
    - 应用程序的起点。 KickStarter 引擎在此处使用所需的配置进行初始化并启动。
- 传统增量计算模型
  - 复制，复制上一次迭代的顶点值、聚合值和增量
  - 如果为第一次迭代则计算所有活跃点的聚合值
    - 根据上次迭代的顶点活跃情况和聚合值更新状况判断是否需要聚合值更新是否要加入到最终更新 EdgeFunction
  - 将聚合值更新加入到顶点并根据顶点值前后变化情况判断是否加入下一次活跃顶点并计算相应聚合值用于下次计算
  - 判断活跃点集是否为空和最大迭代上限判断是否要退出迭代
- 相关输入输出函数
  - -s ：指示使用对称（无向）图的可选参数。
  - -streamPath：输入流文件或管道的路径（有关输入格式的更多信息，请参见第 2.4 节）。
  - -numberOfUpdateBatches ：可选参数，用于指定要进行的边缘更新的数量。默认值为 1。
  - -nEdges：给定更新批次中要处理的边缘操作数。
  - -outputFile ：用于打印给定算法输出的可选参数。
  - 输入图形文件路径
- 输入输出文件格式
  - SNAP 边表格式和AdjacencyGraph邻接格式
  - SNAP 边表格式：由一系列边组成
  - AdjacencyGraph格式
    - AdjacencyGraph
    - 顶点个数
    - 边个数
    - 边偏移量
    - 对应边
- 流输入文件应该在单独的行上进行边缘操作（添加/删除）。边缘操作的格式应为[d/a] source destination，其中d表示边缘删除，a表示边缘添加。
- 边缘操作可以使用 tools/generators/streamGenerator.C 通过管道流式传输。它接受以下命令行参数：
  - -edgeOperationsFile：包含上述格式的边缘操作的输入文件。
  - -outputPipe ：边缘流式传输到的输出管道的路径。
- 带权重的图 SNAP和AdjacencyGraph相同，SNAP在边后面附有边权，AdjacencyGraph在对应边后面增加对应权值
- 流摄取器 FIFO 由 -streamPath 指定。可以将边沿操作写入该 FIFO。 -nEdges 指定可以在单个批次中传递给 GraphBolt 引擎的边操作的最大数量。 GraphBolt 引擎将继续从流摄取器接收边缘批次，直到流关闭（当 FIFO 不再有写入器时）或超过 -numberOfBatches 时。如果FIFO的写端没有打开，GraphBolt引擎（也就是读端）会阻塞等待，直到打开。
- 有一些可选标志可以影响行为并确定传递给命令行参数 -streamPath 的边缘操作的有效性：
  - -fixedBatchSize：可选标志，以确保严格遵守批量大小。如果 FIFO 不包含足够的边缘，摄取器将阻塞，直到它接收到由 -nEdges 指定的足够边缘或直到流关闭。
  - -enforceEdgeValidity：可选标志，以确保批处理中的所有边操作都有效。例如，只有当要删除的边存在于图中时，边删除操作才有效。在简单图的情况下（如下所述），仅当图中当前不存在该边时，边添加操作才有效。在计算批处理中的边数时，无效边将被丢弃并且不包括在内。
  - -simple：用于确保输入图保持简单图（即没有重复边）的可选标志。检查输入图以删除所有重复边。批处理中不允许重复边，并且检查边添加以确保要添加的边在图中尚不存在。
  - -debug：可选标志，用于打印被确定为无效的边缘。
Tegra：进化图的高效临时分析
- 实体扩展增量计算
  - 虚线圆圈表示重新计算的顶点，双圆圈表示需要出现在子图中以计算正确答案但不重新计算状态的顶点。
  - 四个阶段
    - 初始执行
      - 当算法第一次执行时，ICE 存储顶点（和边，如果算法要求它）作为图中的属性。在每次迭代结束时，图表的快照都会添加到时光倒流中。 ID 是使用图的唯一 ID、算法标识符和迭代次数的组合生成的。
    - 引导
      - 当要在新的快照上执行计算时，ICE 需要引导增量计算。直观地，必须在引导程序中参与计算的子图由图的更新以及受更新影响的实体组成。
      - 例如，应包括任何新添加或更改的顶点。类似地，边修改将导致源和/或目标顶点被包括在计算中。
      - 然而，受影响的实体本身并不足以确保结果的正确性。这是因为在图并行执行中，图实体的状态取决于其邻居的集体输入。因此，ICE 还必须包括受影响实体的一跳邻居，因此自举子图由受影响实体及其一跳邻居组成。 ICE 为此目的使用扩展 API。
    - 迭代
      - 在每次迭代中，ICE 都需要找到正确的子图来执行计算。 ICE 利用了这样一个事实，即图并行抽象的性质限制了迭代中更新的传播距离。直观地，在任何迭代中可能具有不同状态的图实体将包含在 ICE 已经从上次迭代开始执行计算的子图中。
      - 在初始引导程序之后，ICE 可以通过检查前一次迭代对子图的更改（使用 diff）并扩展到受影响实体的单跳邻域（使用 expand）来在给定迭代中找到新子图。
      - 对于没有重新计算状态的顶点/边，ICE 只是从时光倒流中复制状态（使用合并）。
    - 终止
      - 与初始执行相比，对图形的修改可能会导致更多（或更少）的迭代次数。与普通的图并行计算不同，ICE 不一定会在子图收敛时停止。如果在初始执行的延时中存储了更多迭代，ICE 需要检查是否必须复制图中未更改的部分。反之，如果子图还没有收敛，没有更多对应的迭代，ICE就需要继续。为此，它只需从该点切换到正常（非增量）计算。
      - ICE 仅在子图收敛时收敛，并且没有实体需要从时光倒流中存储的快照复制其状态。
  - 优化
    - ICE 的设计让我们克服了这种低效率。由于 ICE 在每次迭代中生成与完全重新执行相同的中间状态，因此它可以在任何时候切换到完全重新执行；在迭代边界处（即，在执行期间的迭代开始处），训练一个简单的随机森林分类器来预测，在迭代开始时，与继续增量执行相比，从该点切换到完全重新执行是否会更快。
    - 参与计算的顶点数、活动顶点的平均度数、活动分区数、生成的消息数每个顶点、每个顶点接收到的消息数、通过网络传输的数据量以及完成迭代所需的时间
使用灵活的记忆自动化增量图形处理
- 关键公式
  - $\begin{aligned} m_v^i & =\mathcal{H}\left(M_v^{i-1}\right), \\ x_v^i & =\mathcal{U}\left(x_v^{i-1}, m_v^i\right) \\ m_{v, w}^i & =\mathcal{G}\left(x_v^i, m_v^i, P_E(v, w)\right) \quad(\forall w \in \operatorname{Nbr}(v)) \end{aligned}$
  - 其中M为一聚合值集合，m为聚合值收集操作函数，x代表点权， $m_{v, w}^i$ 代表 v 在第 i 轮发送给 w 的消息。
  - 无效消息。在原始图 G 上运行期间传输的旧消息如果其值对于新图 G ⊕ ΔG 变得过时或由于输入更新 ΔG 断开用于传递消息的链接，则称为无效。
  - 消息丢失。在 G ⊕ ∆G 上传输的新消息如果是关于 G 的旧消息的修订版本或者与 ∆G 中新添加的边相关联，则称为丢失。
- 四种内存策略
  - 免记忆 (MF)。该策略根本不记录任何旧消息。相反，增量算法应该直接处理无效和丢失消息对前一批运行的收敛状态（即最终结果）的影响。这对于执行可追踪聚合的一类以顶点为中心的算法是可行的，其中多个消息的效果可以“组装”到单个消息的效果中。此外，旧的无效消息的影响可以通过传播它们的逆版本来“消除”。使用 MF 策略，增量算法首先从先前的收敛状态生成取消和补偿消息的汇总版本。然后使用批处理算法的相同功能处理它们，以取消（resp. 补偿）无效消息（resp. 丢失消息）的影响。
  - 记忆路径 (MP)。该策略只记录一小部分有效的旧消息。事实上，在一些具有可追踪聚合的以顶点为中心的计算中，最终状态 xv 仅依赖于发送到顶点 v 的消息子集，这些消息可以称为有效消息并形成一组路径。以 SSSP 为例。最短距离 w.r.t. 的值v 由从 v 的邻居接收到的最小消息确定，这些邻居位于距源顶点的最短路径上。因此，无需处理无效消息的影响。在此策略下，增量算法存储有效消息的路径以处理无效消息。丢失的消息可以像在免记忆策略中那样处理。
  - 记忆顶点（MV）。记忆化顶点策略跟踪状态 w.r.t。以逐步的方式跨越批处理计算的不同轮次的顶点。这是基于一些以顶点为中心的算法直接将顶点状态作为消息传输的观察结果。因此，记住顶点状态（聚合结果）就足够了，从中可以很容易地在增量算法中发现无效和丢失的消息。尽管每个顶点都会保留多个值，但它减少了从边到顶点的比例的空间成本。
  - 记忆边缘 (ME)。当批处理的以顶点为中心的算法无法使用上述三种策略中的任何一种进行增量化时，增量化应继续使用记忆化边缘策略。这里会记住所有先前运行的旧消息，以识别和处理无效和丢失的消息。因此，增量算法只是简单地在接收进化消息的受影响区域上重放计算。使用 ME 策略，我们可以处理第 2 节的以顶点为中心的模型中的任何算法。
SYNC 或 ASYNC：融合分布式图并行计算的时间
- 同步（Sync），它在每次迭代（即超步）中对一组活动顶点进行同步计算，并将更新传播到其他顶点批处理中每次迭代的结束。一个顶点只能在迭代结束后看到来自其相邻顶点的更新
- 异步（Async），它不提供明确的同步点，但允许一个顶点的状态尽快对其相邻顶点可见
- 在 PowerSwitch 上获得最佳性能的关键是确定模式切换的正确时间。本节首先介绍用于表征不同模式下性能的最终指标，然后说明如何在同步和异步模式下预测此类指标。最后，通过比较预测的和最佳的切换点来验证预测的准确性。
CommonGraph：对不断变化的数据进行图形分析
- 将删除转换为添加
  - 通过创建 CommonGraph 𝐺𝑐，我们可以通过独立执行边添加 Δ𝑖 + 和 Δ𝑖 − 来增量更新 𝐺𝑐 的查询结果，以获得 𝐺𝑖 和 𝐺𝑖+1 的结果。
  - 如何构建 CommonGraph Gc？
- 大量快照的工作共享
  - 三角网格 (TG) 的新结构，通过重用快照子集共享的边添加来实现快照子集之间的进一步工作共享
  - 如何构建 TG 网络？
- 用于评估查询的进化图表示
  - 引入了一种新的表示形式，可以显着减少变异开销。除了 CommonGraph 的压缩稀疏行 (CSR) 表示之外，我们还创建了一批边的 CSR 表示，这些边对应于 TG 中从一个节点过渡到另一个节点的边
- 直接跳跃算法
  - 通过 Gc 来通过加边直接计算
- 基于三角网格的最大工作共享查询评估算法
  - 构建三角网络中间状态
  - 查询评估计划，不同的方案查询数目不同，共享部分添加边的计算量
  - 斯坦纳树问题？最小化权值
优化方案
- 可行的优化方案
  - tegra 增量计算 & graphbolt增量计算 & 从头开始三者的一个自动切换
  - graphbolt做优化的那篇关于减少内存开销的论文，里面提到的两种优化方法也可以做，你实现出来以后也可以加个切换优化什么的
  - graphbolt那个切换论文里面说的是因为记录的中间结果进行了剪枝，分为水平的和垂直的两种，比如水平的是只记录了前k次迭代的中间结果，对于第k次迭代之后的由于没有中间结果所以无法增量计算，因此就会切换到从头算，但这个过程需要注意的是如何保证切换时活跃点集的正确性
  - tegra的增量计算方法就是说和graphbolt一样，也要记录每一次迭代的中间结果，但是它的增量计算方法不是在历史结果上进行修正，而是说对于不受更新影响的顶点的中间结果就直接copy，而受影响的那些顶点就采用传统的计算方法（就是基于上一轮迭代的值来算当前迭代的值）
  - 论文IncGraph An Improved Distributed Incremental Graph Computing Model and Framework Based on Spark GraphX提出了四种内存策略MF、MP、MV和ME四种记忆策略，用于增量计算中信息传递量，目前还在学习，读了一遍没读懂。
- Tegra & GraphBolt & Tradtional 算法对比
  - Tegra
    - 初始化，对base图进行传统从零开始计算并存储相关历史值和聚合值
    - 当发生边的插入和删除时将顶点进行激活并对比一跳邻居的值是否发生变化并增大活跃点集
    - 未发生变化的值拷贝历史值
    - 当没有边发生变化后达到收敛状态
  - GraphBolt
    - 初始化，对base图进行传统从零开始计算并存储相关历史值和聚合值
    - 当发生边的插入和删除时将顶点进行激活修改聚合值
    - 未发生变化的值拷贝历史值
  - 传统从零开始计算
    - 计算流程
      - 1、根据front_curr和聚合值信息来传播更新
      - 2、目标顶点接收更新并根据聚合值信息来更新自己的顶点权值
      - 3、根据目标顶点变化情况是否超过一定阈值来判断是否要在下一次激活
    - 从零开始计算，所有顶点均为活跃点集并计算
  - 两者主要对比
    - GraphBolt的增量计算更新主要和历史数据进行对比，即根据历史数据前后的变化移除错误的数据并更正为正确的数据。
    - 传统的增量计算只根据本次迭代和上次迭代权值变更情况进行更新传播。
    - 这个重要吗？增量计算迭代的次数和传统计算迭代次数应该相同？顶点的收敛快慢？对部分顶点采用Tegra的从零开始计算，对部分顶点采用GraphBolt来进行计算？二者快慢比较？阿巴阿巴
  - 两者切换的标准
    - 活跃点集数目
    - 活动点集的平均度数
    - 完成迭代所需的时间
    - 每次迭代的变化情况
    - GraphBolt给出的解决方案为比较单次迭代时间，通过估算传统增量计算单次迭代的时间和当前增量计算的时间来做决定是否切换。
- 关于并行的优化方案
  - 什么是并行和串行？
  - 并行性优化，目前GraphBolt的计算是基于BSP同步运算的，能否改用其他并行计算或者细粒度锁方案，降低同步所需时间。
- 关于拓扑排序的解决方案？
  - 拓扑排序允许并行运行
- 关于内存优化的解决方案？
  - 减少跟踪点的数目
  - 内存优化：借鉴Controlling Memory Footprint of Stateful Streaming Graph Processing论文中的只跟踪部分顶点的思想来做优化。
- IncGraph 优化解决方案
  - 论文IncGraph An Improved Distributed Incremental Graph Computing Model and Framework Based on Spark GraphX提出了四种内存策略MF、MP、MV和ME四种记忆策略，用于增量计算中信息传递量，目前还在学习，读了一遍没读懂。
毕业设计论文笔记
- changed数组这一块可做优化？但是改进意义不大，原因是BSP模型，以最慢的为标准等待，统一changed数组，还是有点意义的，减少整体计算量，可以考虑（可选）
- 内存限制加入？加入vertex_tmp数组，来进一步提升内存性能
- 进行GraphBolt和Tegra进行结合，受直接影响的顶点直接进行重新计算，受间接影响的顶点进行增量修正？需要对算法进行重新评估？这个受顶点度数的影响，两者各有优劣，有没有可能我没有发现GraphBolt比Tegra性能好的时候？
- BSP模型，时间限制为跑的最慢的一个模型，so 尝试把parallel_for进行合并？
- 提高Cache命中率，改进内存模型？可参考PageRank改进那一篇论文，（TODO）
- 对Tegra尝试进行性能建模？但是切换复杂度会上升，情况复杂度++，（可选）
- 尝试删除changed数组？Tegra和GraphBolt（TODO）
- 尝试改进Tegra和GraphBolt支持LabelPropagation算法（本周完成)
- 机器学习预测真实图（TODO）
- 标签要进行归一化处理？
- 归一化会不会损失信息？
- Tegra那种重新进行收集和计算是否会受到影响？
- 还是我过度计算了？归一化后再归一化？结果无影响？还是识别受影响的顶点识别错误？还是误判了？
To push or To pull论文
- 主要贡献：
  - 我们将推拉二分法应用于各类图算法，并获得了中心性方案、遍历、计算最小生成树、图着色和三角形计数的详细公式。我们还表明，推拉二分法中包含了几种现有的图处理方案。
  - 我们使用PRAM 分析推和拉，并得出所考虑算法的两种变体中同步和通信量的差异。
  - 我们分析了代表胖内存节点和超级计算机的SM 和DM 系统的推式和拉式算法的性能。结合了各种编程模型，包括针对各种类型的图的线程、消息传递（MP）和远程内存访问（RMA）[25]。为了获得详细的见解，我们使用 PAPI 计数器收集性能数据（例如，缓存未命中或问题分支和原子指令）。
  - 我们采用策略来减少推送中的同步量和拉取中的内存访问量，并说明它们可以加速各种算法。
  - 我们提供可用于增强图形处理引擎或库的性能见解。
  - 最后，我们讨论推拉二分法是否适用于图算法的代数表述
- 概念
  - 并行随机存取机 PRAM。并行随机存取机是并行计算机的著名模型。有 𝑃 处理器通过访问大小为 𝑀 单元的共享内存的单元来交换数据。它们以紧密同步的步骤进行：在所有处理器完成指令 𝑖 之前，没有处理器执行指令 𝑖 + 1。指令可以是本地计算或从存储器读取/向存储器写入。我们使用𝑆和𝑊表示时间和工作：最长的执行路径和总指令数。
  - BC 定义没看懂？https://qa.1r1g.com/sf/ask/1631861031/
  - 最小生成树 Boruvka 算法，并行算法