图与矩阵

GNNs are quite a bit different from other neural networks in terms of computational demands and many of the architectures that do well for convolutional neural networks (CNNs), for example, aren’t a perfect fit. They need devices good at handling a lot of scatter-gather operations on sparse data with irregular access patterns. But for some use cases, graph neural networks are still the best option. Graph Neural Networks (GNNs) are a family of neural networks that learn node, edge, and graph embeddings. An “ego-network” around each node is used to learn an embedding that captures task-specific information. The embeddings use both the structure of the graph and the features of the nodes and edges. These embeddings are learned in an end-to-end fashion, the predictions are a function of the target node’s ego-network. * what stays on GPU and what has to train with both CPU and GPU in concert due to memory constraints. * “For GNNs sparse and dense operations are important and training methods matter,” he explains. “For full graph training, both sparse and dense operations account for 50 per cent of runtime. For mini-batch training, dense operations dominate computation. Mini-batch sampling, however, can cause significant overhead, especially in the case of mixed CPU/GPU training.

问题： irregular data access; high communication-to-computation ratio 有些解决方案： communication-avoiding; novel architecture

图可以用1）原始表示：点&边的抽象集合；2）矩阵表示

So 矩阵算法很有用。基于矩阵的图分析：adjacency matrix, incidence matrix的图表示。从这些概念可以得到一个形式化的矩阵定义。如何操作这个矩阵取决于它存储的值，以及这些值允许的运算。

邻接矩阵

给定一个邻接矩阵A，如果A(i,j) = 0， 那么i到j没有边。邻接矩阵可以有方向，这也意味着 A(i,j) != A(j,i)。邻接矩阵可以有边的权重，如果A(i,j) = a != 0，这说明从i到j的边权重为a。邻接矩阵是一个简单的表示一个图中点之间连接的方式。邻接矩阵通常情况下是正方形，这时外-点（out-vertices）和内点（in-vertices）是一套点。邻接矩阵可以是矩形，这时它们是不同的点的集合：这样的图经常叫做二分图。总得来说邻接矩阵可以表示多种图：有向、无向，带权重，二分图。

关联矩阵

关联矩阵/边矩阵使用行来代表图重每条边，用列来表示每个顶点。有些约定俗成的表示：Eout(k,i) = 1 and Ein(k,j) = 1来表示边k是i到j的一个连接。关联矩阵很有用，可以用来表示multi-graphs，hyper-graphs，和multipartite graphs。这些复杂的图很难用邻接矩阵表示。比如，一个多图（multi-graph）两个顶点之间可以有多条边。如果k‘是j到j的另一条边，这样的关系可以用关联矩阵表示：Eout(k’,i) = 1 and Ein(k’,j) = 1。【注意，另一种习惯是用+1和-1，这时得到的矩阵是graph Laplacian】。在超图（hyper-graph）中，边k连接从i到j和j’可以再把Ein(k, j’) = 1。此外，i, j, j’可以从不同顶点类 画出来。 E可以表示多分图（multipartite graph），只需要定义额外的关联数组E’in，并且设定E’in(k, j’) = 1。这就说明关联矩阵可以用来表示：有向，有权，多分，多边，和/或者超边图。

标量运算

元素加法，元素乘法：符合交换律，结合律，分配率； 可以用⊕和⊗来表示很多种运算： （1）⊕ ≡ + ⊗ ≡ × a, b, c ∈ R （2）⊕ ≡ max ⊗ ≡ + a, b, c ∈ {−∞ ∪ R} （3）⊕ ≡ max ⊗ ≡ min a, b, c ∈ {-∞ ∪ R≤0} （4）⊕ ≡ xor ⊗ ≡ and a, b, c ∈ {0, 1} （5）⊕ ≡ ∪ ⊗ ≡ ∩ a, b, c ⊂ Z 当然，⊕ 和 ⊗也可以用来表示不服从三律的其它运算，比如可以用来拉取其它数据（比如一个图顶点的索引）

矩阵属性

交换律，结合律和分配率可以用来构成可以组合的图算法，即运算可以重新排序而结果不变。可以组合的特点能够轻易创造非常多的图算法，而只使用几种函数。

给定矩阵A, B, C ∈ S m×n， 其中a = A(i, j) b = B(i, j) c = C(i, j)。交换律，结合律，分配率对于矩阵有如下的法则： （1）加法交换律可以通过矩阵元素加法实现图的互换或者合并。 a ⊕ b = b ⊕ a ⇒ A ⊕ B = B ⊕ A 此处元素加法：C(i, j) = A(i, j) ⊕ B(i, j) （2）乘法交换律可以通过矩阵元素乘法实现图的互换，取交，缩放。 a ⊗ b = b ⊗ a ⇒ A ⊗ B = B ⊗ A 此处元素乘法：C(i, j) = A(i, j) ⊗ B(i, j) （3）加法结合律可以通过矩阵元素加法实现图的组合。 (a⊕b)⊕c = a⊕(b⊕c) ⇒ (A⊕B)⊕C = A⊕(B⊕C) （4）乘法结合律可以通过矩阵元素乘法实现图的取交和缩放 (a⊗b)⊗c = a⊗(b⊗c) ⇒ (A⊗B)⊗C = A⊗(B⊗C) （5）元素分配率可以实现图取交且/或缩放，然后组合（或者反过来） a⊗(b⊕c) = (a⊗b)⊕(a⊗c) ⇒ A⊗(B⊕C) = (A⊗B)⊕(A⊗C) （6）矩阵乘法分配率可以通过矩阵乘法实现图的转换（transform）然后组合（或者反过来） a⊗(b⊕c) = (a⊗b)⊕(a⊗c) ⇒ A(B⊕C) = (AB)⊕(AC) 此处矩阵乘法：C = A⊕.⊗B = AB的实现是：C(i, j) = M l k=1 A(i, k) ⊗ B(k, j) A : S m×l B : S l×m C : S m×n （7）矩阵乘法结合律是标量分配率的一个引申，可以通过不同顺序的矩阵乘法实现图的变形 a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c) ⇒ (AB)C = A(BC) （8）矩阵乘法交换律和转置操作一起使用才能实现： (AB) T = B TAT 其中AT (j, i) = A(i, j)

0元素：没有边

稀疏矩阵在图中很重要。很多稀疏矩阵的实现都不存储0元素。在邻接矩阵中，0元素等价于row和col表示的顶点之间没有边。在关联矩阵中，0元素等价于row表示的边不包含col表示的顶点。多数情况下，0都是标准算术意义上的0，但有时候可以是别的值。非标准0在和⊕⊗运算一起使用有时候是有帮助的。比如有些时候0可以表示+∞, -∞, 或者 ∅。对0的任意值，如果0元素有一些和⊕⊗相关的属性，那么矩阵操作的戏属性可以很好的掌控。这些属性有： （1）加法不变：a 0 = a （2）乘0得0：a ⊗ 0 = 0 ⊕ 和 ⊗ 符合（1）和（2）的组合有： （1）实数域上标准算术运算(+.×) （2）在实数域上（并且有定义的最小元素 {-∞ ∪ R}）最大值-加 运算（max.+) （3）在实数域上（并且有定义的最大元素 {R ∪ ∞}）最小值-加 运算（min.+) （4）非负实数上的max-min （5）非正实数上的min-max （6）有最小值的非政实数上的max-min （7）有最大值的非负实数上的min-max （8）在｛0,1｝上的伽罗瓦域（xor.and） （9）任意整数子集Z上的幂集(∪.∩)] 上述只是一些常见例子。在保留圖操作的整體行為的同時更改標量值和運算符的能力是將矩陣用於圖算法的主要好處之一。

矩阵图运算

图的矩阵方法的主要好处是能够使用少量矩阵运算对不同类型的图执行广泛的图运算。 这些核心矩阵运算和它们支持的一些示例图运算如下： * 从行、列和值三元组构建稀疏矩阵，这对应于从一组外顶点、内顶点和边权重构建图 * 提取稀疏矩阵中非零元素对应的行、列和值元组，相当于从图的矩阵表示中提取图边 * 对稀疏矩阵的行和列进行转置，相当于交换图的出顶点和入顶点 * 使用矩阵乘法在图上执行单源广度优先搜索、多源广度优先搜索和加权广度优先搜索 * 从较大的矩阵中提取子矩阵相当于从较大的图中选择子图 * 将矩阵分配给较大矩阵中的一组索引会将子图插入图中 * 使用矩阵的元素相加和矩阵的元素相乘来执行图取并和交集以及边权重缩放和组合

A 构建矩阵：边列表->图 图数据通常可以表示为与稀疏矩阵中的非零元素对应的向量 i、j 和 v 的三元组。 从向量三元组构造一个 m×n 稀疏矩阵可以表示为 C = S m×n (i,j, v, ⊕) 此处 i : I l j : J l v : S l 都是 l 个元素向量。 可选的 ⊕ 操作定义了如何处理具有相同行和列的多个条目。

B 提取元组：图->顶点列表 从稀疏矩阵中提取非零元组可以在数学上表示为 (i,j, v) = A

C 转置：交换出顶点和入顶点 交换稀疏矩阵的行和列是改变图中顶点方向的常用工具（见图 6）。 转置表示为C = AT或者 C(j, i) = A(i, j)，此处 A : S m×n and C : S n×m。 转置也可以用三元组实现： (i,j, v) = A C = S n×m(j, i, v)

D 矩阵乘法：BFS和邻接矩阵的构建 矩阵乘法是最重要的矩阵运算，可用于实现多种图算法。 示例包括查找顶点的最近邻居（参见图 7）和从关联矩阵构建邻接矩阵（参见图 8）。 在最常见的形式中，使用标准算术加法和乘法的矩阵乘法由下式给出 C = AB 或者具体点 此处A : R m×l B : R l×n C : R m×n 矩阵乘法有许多重要的变体，包括非算术加法和乘法 此处A : S m×l B : S l×n C : S m×n，符号⊕.⊗明确表示⊕和⊗可以是其他函数。

矩阵乘法最常见的用途之一是根据图的关联矩阵表示构造邻接矩阵。 对于具有顶点外关联矩阵 Eout 和顶点内关联矩阵 Ein 的图，相应的邻接矩阵可以计算为 其中 A 中的各个值 E 提取：选择子图 选择子图是一种非常常见的图操作（见图 9）。 该操作通过从矩阵 A 中选择出顶点（行）和入顶点（列）来执行：Sm×n： ，或者 其中

以特定顺序选择特定的行和列集。 结果矩阵 C : SmC ×nC 可以大于或小于输入矩阵 A。此操作还可用于复制和/或置换矩阵中的行和列。 提取也可以通过矩阵乘法实现： 这里S(i)和S(j)是选择矩阵： F 分配：修改子图 修改子图是一种非常常见的图操作。 通过从矩阵 C : Sm×n 中选择出顶点（行）和入顶点（列）并从另一个稀疏矩阵为它们分配新值来执行此操作A : S mA×n，或者其中选择特定的行和列集。

G 元素加法，元素乘法：组合图、相交图和缩放图 可以通过对图的稀疏矩阵表示相加来完成图的组合以及添加它们的边权重其中A, B, C : S m×n 其中 i ∈ {1, ..., m}, and j ∈ {1, ..., n}

相交图以及缩放它们的边权重可以通过它们的稀疏矩阵表示的元素相乘来完成其中A, B, C : S m×n 或者其中 i ∈ {1, ..., m}, and j ∈ {1, ..., n}.

DGL

Node-wise parallelism 1. Fetch from feature matrix 2. Reduce fetched feature -> l2 cache miss rate high

Workload imbalance 1. Workload of center node is determined by neighbors Intensive function calls 1. Unpredictable memory access 2. Complex dependency

GAT by DGL 1. Get result for each thread 2. Store to global mem 3. Launch a new kernel & load from global memory LSTM 1. Dense ops to transform feats 2. Eltwise ops to activate feats 3. LSTMs are performed in multiple steps

拉普拉斯算子和拉普拉斯矩阵

谱聚类方法推导和对拉普拉斯矩阵的理解

如何理解 Graph Convolutional Network（GCN）？