Exploring the Hidden Dimension in Graph Processing论文注释（待续。。）

不念不忘少年蓝@ 2022-07-05 15:05 186阅读 0赞

协同过滤基于一个给定的不完全的（用户，系统）率来评价错误率。这个原始的问题呗定义为以矩阵为中心的观点：给定一个大小为N\*M的稀疏矩阵R,目标是找到两个稠密矩阵P,Q其大小分别为N\*D M\*D，使得R=P\*Q(T)。在这个模型中N和M是用户和商品的个数，特别地，D的大小是特征向量的大小。在以图为中心的观点来看，P和Q的每一行可以看做是二部图的一个点，每个点都与一个大小为D的特征向量相关联。与此相反，矩阵R相当于对应边，对于每一个非零单元（u,v）在矩阵R中，代表一个联系P(U)和Q（v）的边，边的权重为R(U,V)

图中一个很明显的特效是每一个顶点都和一个可分割的向量有联系，是一个MLDM算法中普遍的部分（在处理图计算问题中）。另一个很明显的例子是稀疏矩阵的矩阵乘法

一个普遍的应用是让一个系数矩阵和密集矩阵乘法，SpMM主导了大多数基于小型网络的神经网络训练算法的执行时间。

实质上，在制定基于矩阵的应用程序时作为图形问题，顶点或边缘的属性是

通常是向量，而不是单个值。更加重要的是，在计算过程中，这些向量通常是进行的某种element-wise运算，这些运算能够很好的并行不需要通过额外的交流当不相交的矩阵的元素被分配给不同的节点。

图上的话（它只是一个子顶点，它只包含附加到顶点ID的下标的属性子集。）

由于特征向量的共同的特征以及它能并行的特性，这篇文章考虑一种任务划分的新维度，将相同属性的不相交元素分配到不同的节点。我们考虑到一个隐藏的维度在已经存在的1D/2D划分在之前的系统中 由于它们把每个特征都当做不可分割的部分。

注意理解一下这里的3D划分，1D划分是将每个顶点以及其入边分为一个node,入边外面连着一个虚的顶点，2D划分是将边均匀分给某个node，3D则是把每个顶点分为两层，每一层用2D划分

虽然3D划分会带来额外开销，我们对于编程者给出了额外的选择，让他们看哪种方式更好，而且3D划分不必保证所有的长的特征向量有效，试验结果显示64层后流量会减少90.6%

CUBE内部是用基于矩阵的数据结构来store和处理图，然而它提供了一系列以顶点为中心的API对用户，CUBE的设计实现了顶点编程的编程效率和基于矩阵的后端的高性能。

贡献：

1. 提出3D图划分方法，将一个特征向量的元素分到不同的节点？？有了很快的速度

2. 提出先的编程模型UPPS(更新，推，拉，水槽？？)对于3D划分设计的，

现有的面向图形的编程模型是不够的，因为它们隐含地假设单个顶点的整个属性作为不可分割的组件被访问。

3. ，。。。。

4. 。。。

1D模型，graphlab和pregel都采取了1D模型，它将不相联的一些顶点放到一个Node上，然后将所有相关的出边和入边都放在该node上，这样对于随机形成的图已经足够，但是对于现实生活中的图却有严重的弊端

2D模型，为了避免1D模型的缺点，有人提出了2D模型，在2D模型中，图中的边被均匀分到每一个Node上，为了保证通信设立了足够的顶点的复制品，并且这些副本的自动同步需要通信。不同的启发式优化被采用使得我们可以减少通信通过越来越少的副本的产生，举个例子，PowerLyra用了混合的图划分的算法，通过对高纬度的顶点和低纬度的顶点不同的处理，它有了很大的提升，然而即使这样hybrid-cut依然只是2D图划分方法的特例

3D模型 在许多MLDM问题中，一些向量是与每个顶点或者边有关的，因此关于特征是不可分的假定是不真实也不必要的。这关于任务划分的新的维度导出了3D划分。对于N-node的集群，3D划分用L层图拓扑结构的拷贝。每一层都是用2D划分方案，每一层都是N/L个node.另一方面关于图的向量数据被划分到不同的层中。在这种设定下，每一层有N/L个Node，同一层图中只包含原来向量的1/L的子集，对于每一层图用2D划分哦，因此每一个vertex被分为L个sub-vertices

3D partitioningreduces communication cost along edges (e.g., synchronizations

caused byelement-wise operators), because the graph is partitioned across fewer nodes ineach layer, thus each node in a layer could be assigned with more vertices

and edges. Thisessentially converts the otherwise internode communication to local dataexchanges.

一段原话，3D划分减少了边上的通信，因为图在每一层中被分区的Node少了，因此每个layer中的Node包含了更多的vertice和edge, 这实质上将其他节点间通信转换为本地数据交换。

下面一番比较，根据图2中的例子，发现3D划分后，整个图的副本顶点和1D划分以及2D划分一样，但是由于分为了2层，这两层可以并行，所以速度回快？而且对于每一层中的图中，每个Node连的边和顶点更多，也会传递更多的信息，也会更快？

The increasednumber of vertices and edges in each node (3 edges in each layer of Figure 2(d) compared to 1 or 2 edges in Figure 2 (b),(c)) translates to the reducednumber of replicas needed for each layer (3 replicas in Figure2 (d)) comparedto 6 in Figure 2 (b),(c)).

Although the totalnumber of replicas (3 replicas \_ 2 layers = 6 replicas) in all layers stays thesame, the size of each replica is halved, therefore, the network traffic neededfor replica synchronization is halved1. In essence, a 3D partitioning algorithmreduces the number of sub-graphs in each layer and hence reduces theintra-layer replica synchronization overhead

然而3D划分同时也带来了一种新的同步开销，就是在每一层内的子顶点和边的同步开销。因此要合理的调整参数layer来达到比较好的效果

编程模型 将GAS和3D划分方法合并 新生成UPPS方法

UPPS模型允许用户自定义数据的格式，与每个vertex/edge相关的数据被分为了两类

1） 不可以被分割的数据DShare被一个variable定义， 2）第二类数据是可以被分开的数据用DColle定义，作为一个向量被存储起来

用户可以根据需要定义Sc的大小， 来规范每一个DColle 向量的size.

当只有DShare关于边的数据被用到的时候，DColle关于边的可以被设置为NULL

但是当 DColle关于边和vertex的都要被用到，UPPS需要让它们的长度相等，这个约束避免了layer内部的关于某类操作的花费。还有一种情况，如果输入的图是无向的，那么会把其变为有向的，但是如果是许多二部图关于MLDM，只有一个方向是被需要的。

3D划分部分，通过明确的去耦掉可以分开的特征向量 在DColle中，和不可分开的部分在DShare部分，UPPS允许使用者把vertex和edge分为几个sub-vertex/edge使得每一个sub vertex都有DSshre的copy，和不相交的DColle部分。基于UPPS,3D分割方法首先根据layer层数将nodes分割成不同的层，然后每一层用2D分割方法分开，因此，3D分割方法可以描述为（P,L）

Specifically, weshould first guarantee that N is divisible by L. Then, the partitioner will 1) equallygroup the nodes into L layers so that each layer contains N=L nodes; 2)partition edge set E into N=L sub-sets with the 2D partitioner P; and

3) randomlyseparate vertex set V into N=L sub-sets. In the rest of this paper, we use Nodei;j to denote the jth node of the ith layer; Ej and Vj to denote the jth subset of E and V, respectively.

UPPS

Update方面 是垂直方向上的操作，是层与层之间信息的更新，即不同层之间的Node的更新，这些node是共享sub-vertex/edge的

Push Pull Sink操作 是水平方向上的更新操作，对于一条边E(u,v)， push操作是用u和边来更新v顶点，pull是用v和边来更新u顶点，sink操作是用u和v的数据来更新边

Push/Pull操作很像GAS中的操作，UPPS将每个特征向量给划分开了，在GAS通常是看作一个整体的，为了避免层与层之间的交流，做了一些规定，导致的结果就是Node(I,j)只能和Node(I,\*)交流

3.4 二部图

许多MLDM问题的输入图都是二部图，最近的研究表明二部图有独特的特性和某种需要，我们就添加了两种额外的API UpdateVertexU和UpdateVertexV.他们只更新二部图的顶点，对于二部图的2D划分，我们采取了bi-cut方式

下面说一下UPPS的用法

CF问题的定义， user item分别为用户，物品。

N用来标记user的数量 M用来标记item的数量

输入的是R(N\*M)，R(u,v)代表的是物品v对于用户u的一个满意率

输出是两个矩阵P和Q，分别为用户属性矩阵和物品属性矩阵

P（u）和Q（v）是特征向量对于用户u和物品v来说，他们的size都是D

这里来说一下我对CF问题的理解，首先是有一个大的矩阵R(N\*M)的，如上面说的，然后我们尝试生成两个矩阵，即把矩阵R拆成两个矩阵P和Q，怎么拆呢？自然不是数学的方法来拆，而是我们随机生成矩阵P1，Q1并且尝试对其参数优化使得P1，Q1越来越接近真实的P,Q. 然后我们的算法中就有了ERR（u,v）来代表一种误差，这个误差就是P1(u)\*Q1(T)(v)-R(u,v)如果P1和Q1达到了P,Q，那么ERR=0

我们要做的是最小化下面的那个公式

对于CF问题，有一个通常的解决方式是GD算法。它有着一个随机的初始化向量，然后通过不断的学习来提高它们的质量，该算法的参数以与梯度相反方向上的学习速率a成比例的幅度更新，这导致了

以下更新规则：

GD的程序正如上面图片提到的，+用sum来鄙视，为了简化，不展示无关的代码。Sc=D来表示size,因此每个vertex/edge’s DColle部分用长度为D的浮点向量表示。对于vertex,它是用来对用户和产品建模的，这些向量被用来存储user/item相关的特征向量。对于边来说，这些vector是临时的buffer来保留点乘的结果(注意这里其实DColle类型的结果，即不是共享的)。对于shared data, DShare部分对于每一条边edge(u,v)是pair of (doubleRate, double Err),代表着对于user u给item v的概率 和 当前Err，而DShare对于vertex来说是没有被用到的

在算法的第一步，算法1算出预测的error Err(u,v)对于每一条边通过下列步骤：

1） 使用Sink操作来计算每个对齐的要素元素的生成，并将结果存储在边的DColle向量中; 即每个layer中算出的一部分

2） 用UpdateEdge操作来求和每条边的DColle vector然后减去它乘以相应的Rate.即算出。在算完当前错误后要进行的更新操作可以通过上述的push pull模型来实现

ALS算法是另一个解决CF问题的算法。