邻接矩阵的COO格式

我们知道，邻接矩阵通常是稀疏矩阵，而COO格式（Coordinate Format）是稀疏矩阵的一种存储方式，本文将简要介绍如何将无权无向图的邻接矩阵转化为COO格式。

顾名思义，COO格式即坐标格式，我们只需考虑邻接矩阵中不为零的元素的坐标。对于无权无向图，其邻接矩阵是对称阵并且元素非 $0$ 即 $1$，考虑下面的邻接矩阵：

[ 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 0 ] [0101101001001000]

⎣ ⎡​0101​1010​0100​1000​⎦ ⎤​

先考虑下三角部分，不为零的元素的坐标为 $(1,0),(2,1),(3,0)$，因此所有不为零的元素的坐标为 $(1,0),(0,1),(2,1),(1,2),(3,0),(0,3)$。将这六个坐标转置成列向量并沿列方向拼在一起即可得到此邻接矩阵的COO格式：

[ 1 0 2 1 3 0 0 1 1 2 0 3 ] [102130011203]

[10​01​21​12​30​03​]

容易看出，对于无权无向图，设它有 num_edges 条边，则邻接矩阵的COO格式的形状为 (2, num_edges * 2)。

⚠️ 在 PyG 中，一条无向边被视为两条有向边的组合，COO格式中的 num_edges 指的是有向边的个数，因此这种情况下无论是有向图还是无向图，形状均可统一为 (2, num_edges)。

numpy 实现：

import numpy as np


def adj2coo(adj):
    """Convert the adjacency matrix to its COO format

    Args:
        adj (ndarray): Adjacency matrix

    Returns:
        ndarray: COO format
    """
    return np.vstack(adj.nonzero())
1
2
3
4
5
6
7
8
9
10
11
12
13

例如：

a = np.array([[0, 1, 0, 1], 
			  [1, 0, 1, 0], 
			  [0, 1, 0, 0], 
			  [1, 0, 0, 0]])
print(adj2coo(a))
# [[0 0 1 1 2 3]
#  [1 3 0 2 1 0]]
1
2
3
4
5
6
7