$\mathcal{G=\{V,E\}}$, node set $\mathcal{V}=\{v_1, ..., v_n\}$ and the undirected edge set $\mathcal{E}=\{e_1, ..., e_m\}$.

Cause edge is undircted, for edge $e=(i,j)$, we let $i < j$.

adjacency matrix $\bold{A}$, graph Laplacian matrix $\bold{L}$. incidence matrix $\Delta$ as $m\times n$, define as if $e_{\ell}=(i,j)$ ($i < j$), then $\ell$-th row is:

From node $i$ to node $j$, edge $\ell$ leaves node $i$, and enters node $j$.

Then

Proof

• If $i = j$, then $\bold{L}_{ij}= \sum_{k=1}^m \Delta_{ki}^2$, since $\Delta_{ki}=-1$ if edge $k$ leaves node $i$, $\Delta_{ki}=1$ if edge $k$ enters node $i$, $\bold{L}_{ij}$ is degree of node $i$
• If $i \not= j$, and there is an edge $k$ from node $i$ to node $j$, then $\Delta_{ki}=-1$, $\Delta_{kj}=1$, thus $\bold{L}_{ij}=-1$
• If $i \not= j$, and there is no edge from node $i$ to node $j$, for any edge $k$, at least one of $\Delta_{ki}$ and $\Delta_{kj}$ is 0, thus $\bold{L}_{ij}=0$

For a one-to-one transformation,

From​

Probability and Statistics Basics, Notes

本文是为了解释 OGB LSC 中使用 DGL 实现 GCNconv 的代码。

GCN​

$A$ 邻接矩阵， $\tilde{A}=A+I$，$\tilde{D}$ 是对角度矩阵， $\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}$，

要在 GCN 中加入边信息, 对于单个节点的更新

假设传入的图 g 是无向图并且没有加入自环（例如，ogb smile2graph 中将分子从SMILES转化为分子图时，没有加入自环）。如下的代码表示 $\tilde{D}$，为了节省内存，实际上就是度向量，而且我们没有向 g 中加入自环（当然也可以这样做）。这样每个节点的度至少为1，不会出现 1 / degs 为 inf 的情况。

degs = (g.out_degrees().float() + 1).to(x.device)

接下来对度矩阵取-1/2幂，

deg_inv_sqrt = torch.pow(degs, -0.5).unsqueeze(-1)  # (N, 1)
g.ndata["norm"] = deg_inv_sqrt

使用 apply_edges 为边增加特征 norm，

g.apply_edges(fn.u_mul_v("norm", "norm", "norm"))

我们不更新边的特征，在每层对原始的边特征做嵌入。节点 $j$ 传递到节点 $i$ （$j \rightarrow i$）传递的消息为，

边的嵌入，根据原始边特征的表示方式可以有两种方案：

• one-hot + nn.Linear
• index + nn.Embedding

x = self.linear(x)
g.ndata["x"] = x
g.apply_edges(fn.copy_u("x", "m"))
g.edata["m"] = g.edata["norm"] * F.relu(
    g.edata["m"] + edge_embedding)

加下来只需要聚合函数更新节点特征，

g.update_all(fn.copy_e("m", "m"), fn.sum("m", "new_x"))

接下来我们还需要两个操作，

• 第一个是由于我们没有加入自环，所以上述操作不会聚合自己上一层的信息.
• 在消息传递过程中，我们加入了边的信息，若想等价于先加入自环再作用GCN的效果，我们同时需要传递自环的信息（自环本身就是边），因此为自环设置一个单独的 embedding root_emb = nn.Embedding(1, emb_dim).

out = g.ndata["new_x"] + F.relu(
    x + self.root_emb.weight
) / degs.view(-1, 1)

Self-loop feature​

设置 root_emb 可以看成是自环的替代方案，否则需要为边的特征加入一维表示该边是否为自环，这种方法，从实现层面可以有两种。

one-hot​

如果边的特征使用 one-hot 向量表示的，DGLlife中的 BondFeaturizer 是这样表示的。例如若第一个特征有3个取值，第2个特征有2个取值，对于两条边表示如下

  [1, 0, 0, | 0, 1]
  [0, 0, 1, | 1, 0]

则可以这样加入自环，

  [1, 0, 0, | 0, 1, | 0]
  [0, 0, 1, | 1, 0, | 0]
  [0, 0, 0, | 0, 0, | 1]

之后在 GCNconv 的每层对边特征接一个 nn.Linear，可达到相同的效果。

index​

边的特征还可以是由每一个特征对应的 index 表示， 这样可以减少内存的消耗，例如对于上面的例子，边的特征可以表示为

[0, 1]
[2, 0]

通常后面接 nn.Embedding 得到边的嵌入。OGB 中 smiles2graph 是这样得到 边特征 的。 若是加入自环，则可以这样表示加入的自环: 将原始的 index + 1，即每个维度的取值个数都+1，并加入是否自环这一特征，

[1, 2, 0]
[3, 1, 0]
[0, 0, 1]

这样每一维中 index=0 就表示 padding 的特征，设置 nn.Embedding(padding_idx=0) ，对应的 index=0 的向量为0，这样原来图中有的边既不会增加额外信息，又为自环这一特征做了嵌入，达到相同的效果。

Comment​

第二种方案需要把 ogb 的涉及到上面的代码 copy 过来做修改，并且又要加入自环，具有额外的空间开销，我想它们是想避免这个问题从而使用相同效果的 root_emb的，可以参考 root_emb issue 中大佬对这个问题的的回复。

Code​

代码来自 OGB LSC GCNconv DGL，并稍作修改。BondEncoder 是直接得到分子图中键的嵌入。

class GCNConv(nn.Module):
    def __init__(self, emb_dim):
        """
        emb_dim (int): node embedding dimensionality
        """
        super(GCNConv, self).__init__()

        self.linear = nn.Linear(emb_dim, emb_dim)
        self.root_emb = nn.Embedding(1, emb_dim)
        self.bond_encoder = BondEncoder(emb_dim=emb_dim)

    def forward(self, g, x, edge_attr):
        with g.local_scope():
            x = self.linear(x)
            edge_embedding = self.bond_encoder(edge_attr)

            # Molecular graphs are undirected
            # g.out_degrees() is the same as g.in_degrees()
            degs = (g.out_degrees().float() + 1).to(x.device)
            deg_inv_sqrt = torch.pow(degs, -0.5).unsqueeze(-1)  # (N, 1)
            g.ndata["norm"] = deg_inv_sqrt
            g.apply_edges(fn.u_mul_v("norm", "norm", "norm"))

            g.ndata["x"] = x
            g.apply_edges(fn.copy_u("x", "m"))
            g.edata["m"] = g.edata["norm"] * F.relu(
                g.edata["m"] + edge_embedding
            )
            g.update_all(fn.copy_e("m", "m"), fn.sum("m", "new_x"))
            out = g.ndata["new_x"] + F.relu(
                x + self.root_emb.weight
            ) / degs.view(-1, 1)

            return out

Reference​

• Write your own GNN module — DGL 1.0.3 documentation
• GraphConv — DGL 1.0.3 documentation
• OGB LSC GCNconv PyG

Unconditional model​

假设有观测变量 $\bold{x}$, 真实分布 $p(\bold{x})$ 是未知的，我们想用模型 $p_{\boldsymbol{\theta}}(\bold{x})$ 去近似这个未知分布，参数为 $\boldsymbol{\theta}$ :

TODO: 最大化极大似然 最大化对数似然 ML = 最小化 KL ML and MAP

我们可以使用最大似然 (Maximum Likelihood) 去找到参数为 $\boldsymbol{\theta}$ ，从而得到我们的模型 $p_{\boldsymbol{\theta}}(\bold{x})$。

但是我们不知道 $p(\bold{x})$ 是什么样的，例如如果其分布符合多元高斯分布，则可以比较容易的求出。但真实的 $p(\bold{x})$ 往往是非常复杂的，$\bold{x}$ 可以是文本，图片，甚至是graph。

我们知道神经网络模型 (Neural Network, NN) 能够表示复杂的模型，如果使用NN 表示 $p_{\boldsymbol{\theta}}(\bold{x})$，NN 的参数为 $\boldsymbol{\theta}$。下面以一个样本为例，

• 假设 $\bold{x}_i \sim p(\bold{x})$ 是一个样本，我们想要最大似然 $p_{\boldsymbol{\theta}}(\bold{x}_i)$，在 NN 中我们使用梯度下降优化目标函数
• 我们想要求 $p_{\boldsymbol{\theta}}(\bold{x}_i)$ 的梯度，去更新 NN 的参数，从而达到最大似然的目的
• 将已知样本 $\bold{x}_i$ 作为 NN 输入，$\boldsymbol{\theta}$ 作为 NN 参数，输出为一个预测的概率值，但是我们没有监督信息，无法设计损失函数

因此 $p_{\bold{\theta}}(\bold{x})$ is intractable.

Deep Latent Variable Models​

For the intractbility of $p_{\bold{\theta}}(\bold{x})$，我们引入隐变量 $\bold{z}$，对于无条件的观测变量 $\bold{x}$ ，加入隐变量 $\bold{z}$，得到联合分布 $p_{\bold{\theta}}(\bold{x}, \bold{z})$，称为隐变量模型，此时 $p_{\bold{\theta}}(\bold{x})$ 可用边际分布来表示：

也称为 marginal likelihood 或 model evidence。这种在 $\bold{x}$ 上隐式的分布非常灵活。

我们知道对于隐变量模型：

$p_{\boldsymbol{\theta}}(\bold{z})$ 称为先验分布 (prior distribution)，$p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})$ 是条件分布 (conditional distribution)。

• 若 $\bold{z}$ 是离散的，且 $p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})$ 是高斯分布，则 $\bold{x}$ 是有限混合高斯分布
• 若 $\bold{z}$ 是连续的，且 $p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})$ 是高斯分布，则 $\bold{x}$ 是无限混合高斯分布

若用 NN 表示 $p_{\boldsymbol{\theta}}(\bold{x}, \bold{z})$，$\boldsymbol{\theta}$ 是 NN 的参数，我们称其为 deep latent variable model (DLVM)。即先验或者条件分布足够简单，例如将 $p_{\boldsymbol{\theta}}(\bold{z})$ 表示为高斯分布，$p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})$ 表示为伯努利分布。则得到的边际分布 $p_{\bold{\theta}}(\bold{x})$ 仍然足够复杂，模型具有很强的表达能力。

Example DLVM for multivariate Bernoulli data​

假设 $D$ 维二元数据 $\bold{x} \in \{0,1\}^D$，我们让先验的 PDF 为 $p_{\boldsymbol{\theta}}(\bold{z}) = N(\bold{z};0,\bold{I})$，我们可以把 $\boldsymbol{\theta}$ 去掉，因为没有参数。让 $\text{log}p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})$ 是一个多元伯努利分布，每一维独立，其概率使用 NN 从 $\bold{z}$ 计算出，

其中 Decoder 的最后一层接了一个 sigmoid 函数，$\forall p_j \in \bold{p}: 0 \leq p_j \leq 1$，$\bold{x}$ 是一个样本，我们要最大如下的对数似然：

$p_{\boldsymbol{\theta}}(x_j | \bold{z})$ 是一个二元的伯努利分布，

使用统一形式可以表示为，

带入 $(6)$ 中可以得到，

因此对于 $p_{\boldsymbol{\theta}}(\bold{x}, \bold{z}) = p_{\boldsymbol{\theta}}(\bold{z}) p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})=p(\bold{z}) p_{\boldsymbol{\theta}}(\bold{x} | \bold{z})$ 是可以求梯度的，我们最大其对数似然，

因此 $p_{\boldsymbol{\theta}}(\bold{x}, \bold{z})$ is tractable。

根据上述假定，

之前我们知道 $p_{\bold{\theta}}(\bold{x})$ intractable，但是如果我们引入 DLVM，只要能够对 $(11)$ 积分，我们就可以得到 $p_{\bold{\theta}}(\bold{x})$ 的梯度，从而使得 $p_{\bold{\theta}}(\bold{x})$ tractable。

Intractabilities​

但 $p_{\boldsymbol{\theta}}(\bold{x}, \bold{z})$ 是一个 NN 模型，无法对其求积分，因此 $(11)$ 中的积分没有解析解，我们就无法计算梯度。 此外，the intractability of $p_{\bold{\theta}}(\bold{x})$ 与 后验分布 (Posterior Distributiion) $p_{\bold{\theta}}(\bold{z}|\bold{x})$ 的 intractability 有关，

联合分布 $p_{\boldsymbol{\theta}}(\bold{x} , \bold{z})$ 由之前的例子我们已经可以算出，tractable 的posterior $p_{\bold{\theta}}(\bold{z}|\bold{x})$ 会导致 tractable 的 marginal likelihood $p_{\bold{\theta}}(\bold{x})$，反之亦然。

为了将 DLVM intractable的后验和学习问题转化为tractable问题，我们引出下面的 inference model。

Encoder or Approximate Posterior​

我们引入一个参数推断模型 (inference model) $q_{\boldsymbol{\phi}}(\bold{z}|\bold{x})$ 去近似后验，这个模型也称为 encoder，$\boldsymbol{\phi}$ 是推断模型的参数，称为 变分参数 (variational parameters)，

我们会解释，这种对后验的近似会帮助最大化 marginal likelihood $p_{\boldsymbol{\theta}}(\bold{x})$。

类似于DLVM，可以使用 NN 表示 $q_{\boldsymbol{\phi}}(\bold{z}|\bold{x})$，$\boldsymbol{\phi}$ 是 NN 的参数，例如

$\boldsymbol{\sigma}$ 为标准差 $\geq 0$，让 NN 输出为总是 $\geq 0$ 是困难的，因此加入 $\log \boldsymbol{\sigma}$ 使得 NN 输出不受限制。

Evidence Lower Bound (ELBO)​

下面推导，加入 inference model $q_{\boldsymbol{\phi}}(\bold{z}|\bold{x})$ 的好处，对于 marginal likelihood 我们有：

由上可知，

当 $q_{\boldsymbol{\phi}}(\bold{z|x})$ 等于 true posterior distribution 时，上式为0. $(16)$ 中的第一项称为 variational lower bound，或 evidence lower bound (ELBO):

由于 KL divergence的非负性，ELBO 是 log-likehood 的 low bound:

如果我们可以最大化 ELBO，则

• 它会近似最大化 marginal likelihood $p_{\boldsymbol{\theta}}(\bold{x})$，这是我们的目标，意味者我们的生成模型会边得更好
• 它会最小化我们对 true posterior $p_{\boldsymbol{\theta}}(\bold{z|x})$ 和近似分布 $q_{\boldsymbol{\phi}}(\bold{z|x})$ 之间的距离，所以 $q_{\boldsymbol{\phi}}(\bold{z|x})$ 会变的更好

SGD on the ELBO​

最大化 ELBO 等价于最小化负的 ELBO，如果我们能够求出 ELBO 的梯度，则可以使用 SGD 来优化参数 $\boldsymbol{\phi}$ 和 $\boldsymbol{\theta}$。ELBO 相对于 generative model parameters $\boldsymbol{\theta}$ 的梯度为：

最后一行我们使用 Monte Carlo 模拟去估计第3行的期望，其中 $\bold{z}$ 是一个 random sampple from $q_{\boldsymbol{\phi}}(\bold{z|x})$。这是 $\nabla_{\boldsymbol{\theta}} \mathcal{L}_{\boldsymbol{\theta}, \boldsymbol{\phi}}(\bold{x})$ 的一个无偏梯度估计（只需要从下到上证明即可）。

对于 varational parameters $\boldsymbol{\phi}$ 无偏梯度，由于 ELBO 是对 $q_{\boldsymbol{\phi}}(\bold{z|x})$ 求期望，而其又是 $\boldsymbol{\phi}$ 的函数：

在连续隐变量情况下，我们可以使用下面要介绍的重参数化技巧来得到 ELBO $\boldsymbol{\phi}$ 的无偏梯度。

Reparameterization Trick​

Change of variables​

$(21)$ 式中对 后验 $q_{\boldsymbol{\phi}}(\bold{z|x})$ 求期望， 要对随机变量 $\bold{z}$ given $\bold{x}$ 求多元积分，而 $\bold{z}$ 是 通过 NN 得到的，是 $\boldsymbol{\phi}$ 和 $\bold{x}$ 的函数，由于 NN 的灵活性，我们可以认为 $\bold{z}$ 是在 $\bold{x}$ 和 $\boldsymbol{\phi}$ 给定情况下，由另外一个随机变量 $\boldsymbol{\epsilon} \sim p(\boldsymbol{\epsilon})$ 经过可微和可逆的变换 $\bold{g}$ 得到的，

这一操作称为 Reparameterization. 忽略 $\bold{x}$ 和 $\boldsymbol{\phi}$ ，因为它们都是给定的。则 $\bold{z} = \bold{g}(\boldsymbol{\epsilon}) = (g_1(\epsilon_1, ..., \epsilon_n), ..., g_n(\epsilon_1, ..., \epsilon_n))$。 由于 $\bold{g}$ 可逆，因此 存在逆映射 $\boldsymbol{\epsilon}=(\epsilon_1, ..., \epsilon_n) = (h_1(z_1, ..., z_n), ..., h_n(z_1, ..., z_n))=\bold{h}(\bold{z})$，因此我们有 $\bold{z} = \bold{g} (\bold{h}(\bold{z}))$，根据链式法则：

等式左边是单位矩阵 $\boldsymbol{I}$，我们对两边取行列式，则有

$q_{\boldsymbol{\phi}}(\bold{z|x})$ 是随机变量函数的概率密度函数，则有

对 $d\bold{z}$ 做变量替换 $\bold{z} = \bold{g}_{\boldsymbol{\phi}}(\boldsymbol{\epsilon}, \bold{x})$，则有

因此

Gradient under change of variables​

在使用了上面的变量替换之后，对于任何一个随机变量函数 $\boldsymbol{f}(\bold{z})$，我们有

我们可以使用简单的 Monte Carlo 模拟，去估计这个期望的梯度：

Gradient of ELBO​

根据上面的重参数化，我们可以把 ELBO 写成如下形式：

其中 $\bold{z} = \bold{g}_{\boldsymbol{\phi}}(\boldsymbol{\epsilon}, \bold{x})$。 因从我们可以使用一个简单的 Monte Carlo 模拟估计 ELBO，从 noise $p(\boldsymbol{\epsilon})$ 中采样 $\boldsymbol{\epsilon}$:

之后我们求出其梯度，利用 minibatch SGD 优化。

Reference​

• 随机变量的函数的分布
• Multiple Random Variables
• An Introduction to Variational Autoencoders
• Auto-Encoding Variational Bayes

提高收敛速度。

Batch Normalization​

批量归一化 (Batch Normalization)，对于一个DNN，第 $l$ 层的净输入为 $\boldsymbol{z}^{(l)}$ 经过仿射变换 (Affine Transformation) $=\boldsymbol{W}\boldsymbol{a}^{(l-1)}+\boldsymbol{b}$，激活函数 $f(·)$，

In practice，BN before Affine Transformation, after activation function. 对一个中间层的单个神经元进行归一化，使用 Standardization 将净输入 $\boldsymbol{z}^{l}$

Layer Normalization​

层归一化 (Layer Normalization) 对一个中间层的所有神经元进行归一化， 在RNN中，净输入 $\boldsymbol{z}_t$ 由于会累加前一时刻的状态，会随着时间慢慢变大或变小，从而导致梯度爆炸或者消失，LN可以缓解。

$K$ 个样本的 mini-batch $\boldsymbol{Z}^{(l)}=[\boldsymbol{z}^{(1,l)};...;\boldsymbol{z}^{(K,l)}]$，其中每个样本的特征向量用列向量表示，BN 是对矩阵的 $\boldsymbol{Z}^{(l)}$ 的每一行进行归一化，LN是对矩阵的每一列进行归一化。

Weight Normalization​

不对净输入进行归一化，对权重进行归一化。

zsh是功能更强大的命令解释器，linux默认的命令解释器是bash。

zsh下载​

查看系统中安装的shell有哪些：

cat /etc/shells

若没有则下载zsh:

sudo apt install zsh

oh-my-zsh​

oh-my-zsh是一个已经配置文件，帮助我们配置zsh.

下载​

1. 把 oh-my-zsh 项目clone到用户目录

   git clone https://github.com/robbyrussell/oh-my-zsh.git ~/.oh-my-zsh
   

2. 复制模板到用户目录下的.zshrc文件

   cp ~/.oh-my-zsh/templates/zshrc.zsh-template ~/.zshrc
   

3. 更改默认的shell

   chsh -s /bin/zsh
   

之后.zshrc就替换掉了原来的.bashrc

主题配置​

使用VSCode或者Vim编辑~./zshrc文件，更改主题只需替换ZSH_THEME​​

conda命令补全​

1. 下载对应插件到.oh-my-zsh​文件夹下：

   git clone https://github.com/esc/conda-zsh-completion $ZSH_CUSTOM/plugins/conda-zsh-completion
   

2. 修改.zshrc​文件

   在初始化 oh-my-zsh​ 命令前加入

   fpath+=$ZSH_CUSTOM/plugins/conda-zsh-completion
   

   

最后在文件末尾中加入

compinit conda

‍ conda命令现在感觉有bug... 不是很好用，我又取消了，还是手动打吧。

参考 zsh & oh-my-zsh 的配置与使用 - 知乎 (zhihu.com)

默认向量都是列向量。求和符号可以简写。

拉普拉斯矩阵​

定义​

无向图$G=(V,E)$，$A \in \mathbb{R}^{n \times n}$ 为邻接矩阵，其元素

$N(i)$为结点$v_i$的邻居，$D \in \mathbb{R}^{n \times n}$为度矩阵，对角矩阵，其元素

定义拉普拉斯矩阵 (Laplacian matrix) $L=D-A$，其元素

正则化表达形式 (symmetric normalized laplacian) $L_{\mathrm{sym}}=D^{-1/2}LD^{-1/2}$，其元素

总变差​

定义向量$\boldsymbol{x}=[x_1,x_2,···,x_n]^T$，可认为是图信号。则

分量 $\sum _{j=1}^{n}a_{ij}(x_i-x_j)$ 可写成 $\sum _{j\in N(i)}(x_i-x_j)$，由此可知，拉普拉斯矩阵是反映图信号局部平滑度的算子。

接着我们利用上式定义二次型，

调换$i,j$符号，求和顺序保持不变，我们得到

将等式左右两边相加，于是

由公式可以看出，二次型 $\boldsymbol{x}^TL\boldsymbol{x}$ 能刻画图信号的总体平滑度，称为总变差。

来源​

拉普拉斯矩阵的定义来源于拉普拉斯算子，$n$维欧式空间中的一个二阶微分算子：$\Delta f=\sum_{i=1}^n \frac{\partial ^2 f}{\partial x_i^2}$。将该算子退化到离散二维图像空间就是边缘检测算子：

图像处理中通常被当作模板的形式：

拉普拉斯算子用来描述中心像素与局部上、下、左、右四邻居像素的总的差异，这种性质经常也被用来当作图像上的边缘检测算子。

Laplacian Eigenmaps​

假设图 $G=(V,E)$ 中有 $n$ 个节点，嵌入维度为 $d$，可得到如下 $n \times d$ 矩阵 $Y$，

$n$ 维行向量 $\boldsymbol{y}_k=[y_k^{(1)},y_k^{(2)}, ..., y_k^{(d)}]$，可表示一个节点的Embedding。

拉普拉斯特征映射（Laplacian Eigenmaps）用于图嵌入中，在图中邻接的节点，在嵌入空间中距离应该尽可能的近。可将其作为一阶相似性的定义，因此可以定义如下的loss function:

$n$ 维列向量 $\boldsymbol{y}^{(k)} = [y_1^{(k)}, y_2^{(k)}, ···,y_n^{(k)}]^T$，对应图中所有节点的第 $k$ 维的值，可指一组图信号。因此可以得到，

$tr(·)$ 指矩阵的迹 (trace)。

总变差的另一种推导​

对任意$n$维列向量 $\boldsymbol{y}=[y_1, y_2, ..., y_n]^T$，展开可得到，