DeepFM

2021-01-31

Algorithm

wide & deep

Wide & Deep Learning for Recommender Systems. 2016

wide指的是形如LR的这种特征较为稀疏的比较“宽”的模型，这类模型的特点是计算简单、可解释性优秀（有比较好的记忆能力）；deep指的是各种NN类型的，将“宽”的输入转化为embedding，然后对embedding做处理，优点是不需要手工处理特征，且有较强的泛化能力。

wide&deep模型就是要将wide和deep联合起来，取各自的长处，其图示如下：

wide&deep model

模型的输出为：

$f(x|\theta)=\sigma(W_{wide}^Tx+W_{deep}^Tx+b)$

实现中，wide部分可以考虑人工加入组合特征，以提升模型效果。

两部分模型需要联合在一起进行训练

wide部分用FTRL进行优化，辅以L1正则项
deep部分用了adagrad，当然也可以用adam这些方法

DeepFM

DeepFM: A Factorization-Machine based Neural Network for CTR Prediction. 2017

在推荐系统中，轻量模型一般用FM而不用LR，因为FM中考虑了特征交叉且对稀疏数据比较友好。DeepFM就从这个角度出发，将wide&deep模型中的LR换成了FM，其主要结构如下图

deepfm model

可以看到FM有两部分，加法是一阶特征的加权求和，乘法是利用隐向量内积计算出来的组合特征的部分；

deep网络部分则是使用特征的embedding作为输入，对于每个field，将其转化为一个dense embedding（这里搞个field的概念是防止映射矩阵太大，按field进行映射可以有效降低参数数量），然后将所有的embedding作为深度网络的输入。那么embedding怎么来的呢，embedding是由原始特征通过以FM的隐向量为参数的映射得到，如下图所示。

deepfm embedding

多说一句，数值类特征直接使用数值，非数值类特征转成one-hot。模型输出公示如下：

$y=\sigma(y_{NN}+y_{FM})$

最后输出的结果可以作为ctr预估的结果。

因为FM、DEEP两个部分共享参数，也就是特征的隐向量，所以这部分可以一起训练。

实际应用中，这种混合模型可能会出现问题，因为两边的训练速度不一致，所以收敛速度不一致。应用中可能需要调整两边的学习率。

Monotonous Sequence

2021-01-02

单调序列结构，这里不仅仅指的是数组，指的是用于加速检索结果的线性数据结构（vector、队列、栈等）。
用例题解释~

Minimum Number in Sliding Window

有一个长为 n 的序列 nums，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值

这里介绍一个O(n)复杂度的算法。

我们可以把关键的数据存储起来，利用第 i 个位置的信息计算第 i+1 位置的任务。方法如下：

建立一个队列，这个队列需要满足：
- 新进入队列的数要大于等于队尾的数字，也就是说任何时刻队列都是单调递增的
- 所以如果当前数小于等于队尾的数据，队尾的数据就不可能是窗口最小值。【等于是考虑了位置，位置约靠后越好】
对于当前的位置，如果大于k，需要将队列中不满足窗口位置的从队头去掉
- 所以队列中存储的应该是下标志，而不是元素本身
然后将队尾大于当前数字的元素pop出去
这时候队头的元素就是当前窗口中的最小值

代码实现如下：

// #include <deque>

vector<int> function(const vector<int>& nums, int k) {
    vector<int> ret;
    if (nums.size() == 0 || k < 1) {
        return ret;
    }
    deque<int> qu; // monotonous queue
    for (int i = 0; i < nums.size(); ++i) {
        if (qu.size() > 0 && i - qu.front() == k) { // window size
            qu.pop_front();
        }
        while(qu.size() > 0) {
            // 队尾大于当前数字的元素pop出去, 保持递增
            if (nums[i] <= nums[qu.back()]) {
                qu.pop_back();
            }
        }
        qu.push_back(i); // 入队
        ret.push_back(nums[qu.front()]); // 对头是最小值
    }
    return ret;
}

时间复杂度：因为每个元素入队、出队只有一次，所以整体的复杂度是O(N).

右侧大数

有一个长为 n 的整数序列 nums，对于每个元素找到这个元素右侧第一个大于它的值（不存在就-1），返回这个值序列

如果当前元素小于下一个，那么直接就有结果了。如果不是，将当前元素的位置存到栈里面，所以在搜索到新位置时也需要看栈顶元素。所以整体的步骤如下：

初始化结果数组ret，新建一个栈stack
对于位置i
- while(nums[i] > nums[stack.top()]):
  - 更新stack.top()位置的值: ret[stack.top()] < nums[i]
  - 栈顶pop：这能保证堆栈从上到下是递增的（栈顶最小）
  - i入栈

// #include<stack>

vector<int> function(const vector<int>& nums) {
    vector<int> ret(nums.size(), -1);
    if (nums.size() < 2) {
        return ret;
    }
    stack<int> st;
    st.push(nums[0])
    for (int i = 1; i < nums.size(); ++i) {
        while(!st.empty() && nums[st.top()] < nums[i]) {
            ret[st.top()] = nums[i];
            st.pop();
        }
    }
    return ret;
}

最长递增子序列

有一个长为 n 的整数序列 nums，找到这个序列中最长的递增序列，返回长度

DP思路的复杂度为O(N^2)，下面介绍一个复杂度为O(N*logN)的算法

维护一个数组vec，位置i的元素表示长度为i的递增子序列最后一个元素值的最小值，也就是子序列最大值中的最小值。这样一个数组有一个特点：数组的元素是递增的，证明就反证法就好

对于nums中的一个新元素num，我们可以找到vec中m的位置k满足

vec[k] < num <= vec[k+1]，表示最优子序列中，长度k子序列的最大值小于num，但是长度k+1子序列的最大值不小于num，所以我们更新k+1子序列的最大值为num，但是k+2及以后的不行
上述操作可以线性搜索，但是因为vec数组是有序的，所以可以通过二分搜索的思想来做

int function(const vector<int>& nums) {
    if (nums.size() < 2) {
        return nums.size();
    }
    vector<int> vec;
    for (int i = 0; i < nums.size(); ++i) {
        // vec[k] < num <= vec[k+1]，找到位置
        auto idx = upper_bound(vec.begin(), vec.end(), nums[i]);
        if (idx == vec.end()) {
            vec.push_back(nums[i]);
        } else {
            *idx = nums[i];
        }
    }
    return vec.size();
}

Largest Rectangle in Histogram

见Largest Rectangle in Histogram

Factorization Machines

2021-01-02

Algorithm

machine learning, recommendation

FM

Factorization Machines. 2010

FM（Factorization Machine）是推荐系统常用典算法之一

LR（或者线性回归）是个简单的线性模型，可解释性好。LR假设所有的特征都是独立存在的，所以一个其明显的缺陷是不能的考虑组合特征。SVM的核函数（多项式函数$K(x_i,x_j)=(\gamma x_i^Tx_j+d)^n$可以考虑到特征组合的情况）,但是

LR也可以显示地加入组合特征，会导致要学习的参数数量增大。特征多的时候，总有部分特征是比较稀疏的，这时候组合特征就更稀疏了，在有限训练数据的条件下，组合特征的参数很可能学习得不充分。

FM解决了这个问题，下面介绍这个算法：

形式：

$y=\sum_i^n w_i x_i + \sum_i^n\sum_{j>i}^nv_i^Tv_jx_ix_j, \tag{1}$

这里，我们给每个特征一个隐向量（长度为$k<n$），交叉特征的权重由对应特征的隐向量内积表示，这样我们需要学习的参数就是$w,v$了，因为交叉特征的权重不再独立，参数学习也简单了许多，泛化能力也变强了（比如$x_i,x_k$的组合在训练数据这没出现过，依旧可以表示其系数$v_i^Tv_k$，如果赋予组合特征独立的参数，且就训练数据中不存在这样的的组合，那么其参数就学不到了）。

关于特征处理：

数值特征：对应一个隐向量
非数值特征：换成one-hot形式，对应多个隐向量

公式(1)的计算复杂度是比LR要高的，为平方复杂度，考虑隐向量的长度，复杂度为O(kn^2)，可以通过变换降低其复杂度：

$f(x)=\sum_i^n w_i x_i + \frac{1}{2}\sum_{f=1}^k\left[(\sum_i^n v_{i,f}x_i)^2-\sum_i^nv_{i,f}^2x_i^2\right]$

复杂度降为O(kn)。

训练就采用SGD即可，训练和预测都可以在线性时间完成。

FM中的隐向量可以看成是深度模型中的embedding，也就是每个特征的embedding，可以和NN结合构建深层网络。

FFM

Field-aware Factorization Machine. 2014

FFM（Field-aware Factorization Machine）是FM的进阶，通过引入field的概念，FFM把相同性质的特征归于同一个field。比如商品的末级品类编码生成了550个特征，这550个特征都是说明商品所属的品类，因此它们也可以放到同一个field中。

实现上，每一维特征$xi$，针对其它特征的每一种field$f_j$，都会学习一个隐向量$v_{i,fj}$，其中$f_j$是$j$个特征的field。因此，隐向量不仅与特征相关，也与field相关！算法形式如下：

$f(x)=\sum_i w_ix_i + \sum_i\sum_{j>i}v_{i,f_j}^Tv_{j,f_i}x_ix_j$

从上式可以看出来，较FM而言FFM参数数量变大，训练也更加耗时。

FFM将问题定义为分类问题，使用的是logistic loss（label为1、-1），同时加入了正则项,训练优化目标为：

$\min_{\theta}\sum_i \log\left(1+\exp\{-y^if(x^i,\theta)\}\right)+\frac{\lambda}{2}||w||^2$

部分开源实现的FFM忽略了一次项，只保留了二次项。

Python Functions

2020-09-01

Dev

python

常用的python函数

sort

python的sort函数有两种

L.sort

原地排序

1 2	l=[3, 2, 4, 1, 5] l.sort(comp, key, reverse=False)

其中

comp是列表元素的比较函数
key指定排序的键值，可以是一个函数。指定key的方法比comp快
dict没有这个函数，需要通过items()方法转换为list才行

sorted

返回一个排好序的列表，这是稳定排序方法

1
2
3

new_list = sorted(iterable, cmp=None, key=None, reverse=False)

sorted(dict.items(), key=lambda d: d[0], reverse=True)

其中

iterable是可迭代的类型，比如list，dict等

在python3中，去掉了自定义比较函数cmp，这时可以将比较函数转化为key

1	sorted(iterable, cmp_to_key(my_comp))

enumerate

enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中

定义

1	enumerate(sequence, [start=0])

sequence — 一个序列、迭代器或其他支持迭代对象。
start — 下标起始位置

示例

seasons = ['Spring', 'Summer', 'Fall', 'Winter']
list(enumerate(seasons))
> [(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]

list(enumerate(seasons, start=1)) # 下标从1开始
> [(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

for i, season in enumerate(seasons):
    print(i, season)

groupby

itertools.groupby函数用于对按照key排好序多字段列表进行分组，返回一个分组后的key和一个迭代器对象，迭代器对象包含对应key值的所有对象

定义

1	groupby(sequence, key=itemgetter())

sequence是列表：其元素可以是列表、或者字典
key是分组的key，列表需要指示是哪个，dict需要指出是哪个属性。可以用itemgetter指定

示例

from operator import itemgetter
from itertools import groupby

x = [[1, 'b', 3], [2, 'a', 4], [1, 'b', 5]]
# sort first
x.sort(key=itemgetter(1))
for key, iter in groupby(x, itemgetter(1)):
    for lst in iter:
        print(key, lst)

> ('a', [2, 'a', 4])
  ('b', [1, 'b', 3])
  ('b', [1, 'b', 5])


# apply for dict
y = [{'a': 'm', 'b': 2}, {'a': 'n', 'b': 1}, {'a': 'm', 'b': 3}]
y.sort(key=itemgetter('a'))
for key, iter in groupby(y, itemgetter('a')):
    for dict in iter:
        print(key, dict)

> ('m', {'a': 'm', 'b': 2})
  ('m', {'a': 'm', 'b': 3})
  ('n', {'a': 'n', 'b': 1})

Bounds in Binary Search

2020-09-01

Binary Search

二叉搜索的理念比较简单，不赘述，这里说的是在循环处理、边界条件上的内容。

循环条件：包含的是有必要继续进行搜索的区间，如果没有必要继续计算了，把循环条件放开
边界处理：初始的范围应该覆盖所有可能的取值
边界缩进：判断时，把可能找到最终结果的条件放在一起；缩进边界的时候要保证可能的结果依旧在新的边界范围中，也就是考虑要不要多移一位

naive

先从原始的二叉搜素开始;

边界范围：就是数组的序号边界
循环条件：算法需要精确到单个长度的区间（l=r），即l<=r，因为查询目标可能不存在

边界缩进：比较明显

int binarySearch(int[] nums, int l, int r, int target) {
    while (l <= r) {//[l....r]闭区间查询，l > r 时候形成不了闭区间了，说明没有找到
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) {//找到
            return mid;
        } else if (nums[mid]target){
            //说明中间位置太大了，所以要在[l.....mid-1]中继续查找
            r = mid - 1;
        } else {
            //说明中间位置太小了，所以要在[mid+1 ....r]中继续查找
            l = mid + 1;
        }
    }
    return -1; //跳出循环了没有找到 返回-1
}

upper bound和lower bound

upper bound是要找有序序列中第一个大于target的值，而lower bound是要找有序序列中第一个不小于target的值。

在STL中，基本定义如下

1 2	Iterator lower_bound(Iterator first, ForwardIterator last, const T& val, Compare comp); Iterator upper_bound(Iterator first, ForwardIterator last, const T& val, Compare comp);

其中，右边界是序列最后一个的下一个位置，因为target可能比最后一个元素还大

upper bound

边界范围：因为target可能比最后一个元素还大，所以合理的边界是[0, n]，假设n是序列长度
循环条件：并不要求元素一定要存在，不需要判断这个元素是否存在，就算是不存在，我们只需要知道“假设target存在，它应该在的位置”,当l=r时候(最终肯定有l=r)，[l,r]正好能够得到一个唯一的位置，就是我们需要的结果，所以满足l<r让循环一直执行即可
边界缩进：当中间值大于target，则当前这个中间值可能就是结果，所以r变化时要保留mid；中间值小于等于target的情况则可以放在一起，因为都没可能是结果，l变化时不用保留mid值

int upperBound(int[] num, int l, int r,int target) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (num[mid] > target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

lower bound

边界范围：因为target可能比最后一个元素还大，所以合理的边界是[0, n]，假设n是序列长度
循环条件：同upper bound
边界缩进：当中间值大于等于target（大于等于都可能是最终结果），则当前这个中间值可能就是结果，所以r变化时要保留mid；中间值小于target的情况下，因为都没可能是结果，所以l变化时不用保留mid值

int lowerBound(int[] nums, int l, int r, int target) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

BM25

2020-09-01

Algorithm

BM25是一种经典的搜索基础相关性算法，用以计算query和doc的相关性

对于用户query $q$和doc $d$，BM25操作如下：

对$q$分词，得到分词token：$t_1, t_2, …, t_k$
令$R(t_i,d)$是$t_i, d$之间的相关性，$w_i$是token$t_i$的权重

则基于BM25的相关性分数为：

$S(q, d)=\sum_i w_i\cdot R(t_i,d)$

首先看一下$w_i$，其计算方式可以是多种多样，一般是基于idf的思想

$w_i=\log\frac{N-N(t_i)+0.5}{N(t_i)+0.5}$

其中$N(t_i)$表示包含$t_i$的文档数量，$N$表示所有文档的数量。

再看$R(t_i,d)$，计算方法如下：

$R(t_i,d)=(k_1+1)\frac{f_d(t_i)}{f_d(t_i)+K}\times(k_2+1)\frac{f_q(t_i)}{f_q(t_i)+k_2} K=k_1\times (1-b+b\times \frac{l_d}{l_{avg}})$

其中$f_d(t_i)$表示$t_i$在$d$中出现的频率，$f_q(t_i)$表示$t_i$在$q$中的频率，$l_d$表示文档$d$的长度，$l_{avg}$表示文档集合的平均长度；$k_1,k_2,d$则是可以调节的参数。

参数$b$用来控制文档长度敏感度，一般有$f_q(t_i)=1$，如果取$k_2=0$则有$R(t_i,d)=(k_1+1)\frac{f_d(t_i)}{f_d(t_i)+K}$。通常会设置

$k_1=2,\ b = 0.75$

Similarity and Relativity Metrics

2020-09-01

Math

相似度度量出现在很多机器学习应用中，比如query-query相似度、排序等等，今天介绍一下常用的几个相似度衡量标准

闵可夫斯基距离

定义如下

$d(A,B)=\sqrt[p]{\sum_i|A_i-B_i|^p}$

根据p值的不同，可以是

$p=1$: $d=\sum_i|A_i-B_i|$，曼哈顿距离
$p=2$: $d=\sqrt{\sum_i|A_i-B_i|^2}$，欧几里得距离
$p\to\infty$: $d=\max_i|A_i-B_i|$，切比雪夫距离

汉明距离

对比对象二进制表示的差异，即二进制表示对应位不同的个数。

编辑距离

允许增、删、改操作的序列距离，可用动态规划的方式求解，动态方程为

$d(i,j)=\left\{ \begin{aligned} d(i-1,j-1), & & A[i]==B[j] \\ \min\left\{d(i-1,j-1), d(i-1,j), d(i,j-1)\right\}+1, & & else \end{aligned} \right.$

余弦相似度

$\cos(\theta)=\frac{A\cdot B}{|A||B|}$

Jaccard系数

给定两个集合$A,B$，Jaccard系数定义为

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$

也就是集合的交集大小比上集合的并集大小。Jaccard系数的取值范围是[0, 1]，两个集合都是空集，Jaccard系数=1。

与Jaccard系数对应的是Jaccard距离，其计算方式是： Jaccard距离=1-Jaccard系数，距离越大，样本相似度越低

pearson系数

两个连续变量$(X,Y)$的pearson相关性系数$(Px,y)$定义如下：

$P(x,y)=\frac{cov(X,Y)}{\sigma_X\cdot \sigma_Y}=\frac{E(XY)-E(X)E(Y)}{\sqrt{E(X^2)-E^2(X)}\sqrt{X(Y^2)-E^2(Y)}}=\frac{\sum_i(X_i-\mu_X)(Y_i-\mu_Y)}{\sqrt{\sum_i(X_i-\mu_X)^2}\sqrt{\sum_i(Y_i-\mu_Y)^2}} \tag{1}$

pearson系数取值总是在-1.0到1.0之间，越靠近0表示相关性越低，数值的正负表示正相关还是负相关.

注意公示1可以发现，pearson相关性系数也就是把数据先正规化到均值为0、方差为1，然后求这两组数据的cosine夹角

Entropy and Related Metrics

2020-09-01

Math

熵

首先说香农信息量（也叫自信息self-information），其定义为

$\log\frac{1}{p}=-\log p$

熵的本质是香农信息量的期望，即

$H(p)=-\sum_ip(i)* \log p(i)$

表示混乱程度，熵越大越混乱。

交叉熵

现有关于样本集的2个概率分布$p$和$q$，其中$p$为真实分布，$q$非真实分布。用分布$q$来表示来自分布$p$的平均编码长度的期望(即平均编码长度)为：

$H(p,q)=-\sum_{i}^{} p(i)*\log q(i)$

其中，$H(p,q)$就叫做交叉熵。

举个例子，有集合$S=(A,B,C,D)$，真实分布$p=(1/2,1/2,0,0)$，即$A,B$出现的概率都是1/2。现在用分布$q$来编码分布$p$，则有：

假设$q=(1/2,1/2,0,0)$，即真实分布，根据上式计算$H(p,q)=1$，即只需要1位编码就可以识别$A,B$
假设$q=(1/4,1/4,1/4,1/4)$，计算得$H(p,q)=2$，则需要2位编码就可以识别集合$S=(A,B,C,D)$

非真实分布编码所需长度大于真实分布编码所需长度，即存在

$H(p,q) \ge H(p,p)=H(p)$

当且仅当$p=q$时等号成立。所以交叉熵作为损失函数时，可以表示两个分布之间的相似性，越相似交叉熵越小。

KL散度（相对熵）

定义：设真实分布为$p$，由分布$q$得到的平均编码长度比由$p$得到的平均编码长度多出的bit数称为“相对熵”，写作

$D(p||q) = H(p,q)-H(p)=\sum_{i}^{} p(i)*\log \frac{p(i)}{q(i)}$

相对熵也叫KL散度（Kullback–Leibler divergence），表示2个函数或概率分布的差异性，差异越大则相对熵越大，相同时KL散度为0。注意，KL散度是非对称的。

TD-IDF算法就可以理解为相对熵的应用：词频在整个语料库的分布与词频在具体文档中分布（$\log \frac{|N|}{|N_t|}$）之间的差异性

JS散度

KL散度的一种变形，定义如下：

$JS(P||Q)=\frac{1}{2}KL\left( P(x)||\frac{P(x)+Q(x)}{2} \right) + \frac{1}{2}KL\left( P(x)||\frac{Q(x)+Q(x)}{2} \right)$

JS散度有如下特性：

对称性
值域范围是[0,1]，相同则是0，相反为1

TextGCN

2020-09-01

Algorithm

Graph, NLP, deep learning

GNN在NLP上的应用

Text GCN

Graph Convolutional Networks for Text Classification. AAAI. 2019

给定文章若干，目标是基于GCN搞一个分类器。

图的构建方法，邻接矩阵为

$A_{i,j}=\left\{ \begin{aligned} PMI(i,j), & & both\ words \\ TF-IDF_{i,j}, & & word\ \&\ doc \\ 1, & & i=j \\ 0, & & otherwise \end{aligned} \right.$

其中PMI是point-wise mutual information，计算方式如下

$PMI(i,j)=\log\frac{p(i,j)}{p(i)p(j)}$

概率的计算可以使用滑动窗口统计出现次数，分母是corpus中所有的滑动窗口数量。PMI反应了节点之间的关系，负数表示相关度低，所以只把PMI>0的节点添加边。这里，doc和doc之间没有边相连，但是在图上通过一跳就可以达到，所以网络层数应该大于1，论文的实验也说明了这点，layer=2明显好于1.

以这个图为基础，构建一个2层的GCN，最后的结果经过softmax做分类

$Z=\rm{softmax}\left( \tilde{A}\ \mathcal{ReLU}(\tilde{A}XW_0)W_1 \right) \tilde{A}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$

损失函数就用交叉熵即可。

试验结果显示，TextGCN表现优秀，但是在短文本和情感分析等这种对word-order比较敏感或者可建模的边数量较少的任务上不够好。

本方法还有一个固然的缺陷：无法处理未见过的文档，因为不在图里

Graph Convolutional Networks

2020-09-01

Algorithm

Graph, deep learning

GCN是GNN中比较常用的一种网络结构，其主要思想是将卷积操作迁移到图结构上以提取图的结构特征。

研究GCN的原因如下：

图是一种定义拓扑关系的广义结构，可以表达丰富的结构特征
CNN的方法不能对图做卷积，图中每个顶点的相邻顶点数目都可能不同，无法用一个同样尺寸的卷积核来进行卷积运算

网络结构

图上的卷积操作大体上有如下两种思路

spatial domain

这里是将卷积做了一个概念上的泛化。这里有两个概念

aggregation：用邻居的特征更新当前节点下一层的hidden state
readout
- 单个节点的表征
- 聚合所有节点的特征，得到整个图的表征

根据aggregation和readout的不同，就有不同的算法

NN4G（Neural Networks for Graph. 2009）

aggregation：节点$v$的第$k$隐层节点值为

$h_v^{(k)}=f\left(x_vW_{k}+\sum_{u\in N(v)}h_u^{(k-1)}W_{k,k-1}\right)$

其中，$x_v$为节点$v$的原始特征。

readout：将每一层的hidden state求均值，然后加权求和作为整个图的表征

DCNN（Diffusion-Convolution Neural Network. 2016）

DCNN将迭代看成是图上的扩散过程，每一层相当于在上一层的基础上再进行一跳。
aggregation：

$h_v^{(k)}=f\left( W_{k,v}\cdot MEAN(d(v,.)=k)\right)$

其中，$MEAN(d(v,.)=k)$表示与点$v$距离为$k$的节点的原始特征（$x$）的均值，这里注意不是用$k-1$层的hidden state，而是原始特征。

readout：将每一层的hidden state拼成矩阵，所有的矩阵就是图的表征；单个节点对应的所有hidden state拼一起就是单个节点的表征

DGC（Diffusion Graph Convolution）

整体上与DCNN类似，唯一不同的是在readout阶段，表征不再用各个hidden state拼接的结果，而是用相加的结果

MoNet（Mixture Model Network. 2017）

aggregation：

考虑了邻居的权重，不再使用邻居的简单相加，而是使用加权求和
节点$x,y$的边权重定义为：$u(x,y)=(\frac{1}{\sqrt{\deg(x)}},\frac{1}{\sqrt{\deg(y)}})^T$，其中$\deg()$表示节点的度函数

readout：-

GAT（Graph Attention Network. 2017）

MoNet将权重写死了，GAT通过attention机制计算出邻居节点的权重。这是较为常用的一种方法

GIN（Graph Isomorphism Network. How Powerful are Graph Neural Networks?. 2019）

主要思想如下

aggregation的时候不要使用mean或者max pooling操作，而是使用sum。因为max、mean操作会丢失掉一些图的结构信息，比如3个2和4个2的均值、最大值都是2，但是和不一样
aggregation按如下公示计算

$h_v^{(k)}=MLP^{(k)}\left( (1+\epsilon^{(k)})h_v^{(k-1)}+\sum_{u\in N_{v}}h_{u}^{(k-1)} \right)$

spectrum domain

结论：

信号在时域上的卷积等价于其在频域上的乘法

所以，这种方法的思想是将图信号上的卷积操作转换到频域上的乘法操作，最后再逆转回去

谱图理论(vertex domain -> spectral domain)

给定包含$N$个节点的图，定义$A,D$分别为图的邻接矩阵和度矩阵。
定义图上的拉普拉斯矩阵：$L=D-A$，对称，半正定。有如下特性

对称矩阵一定N个线性无关的特征向量
半正定矩阵的特征值一定非负
对阵矩阵的特征向量相互正交

对这个矩阵做SVD分解得到$L=U\Lambda U^T$（这里$U^T=U^{-1}$且$UU^T=E$），其中$\Lambda=diag(\lambda_0,…,\lambda_{N-1})$，$U=[u_0,…,u_{N-1}]$为包含正交向量（列向量）的特征矩阵。$\lambda_l$可以看成频率概念，而$u_l$则是对应的基（basis）。[这里频率概念的解释可以参考文献1中的视频解释]

图傅立叶变换：给定信号$x$，经过图傅立叶变换后得到(这里其实和PCA很像了)

$\hat{x}=U^Tx$

其中$U$是上述的特征矩阵。图傅立叶逆变换则如下：

$x=U\hat{x}$

有了经过图傅立叶变换的信号$\hat{x}$后，我们可以在频域上对信号做一个变换（滤波），简单的做法是做对应位相乘，引入参数$\theta$。为了表述统一，令$g_{\theta}(\Lambda)$为对角矩阵的对角$\theta$（参数写成$\Lambda$只是为了和频率对上）。所以有

$\hat{y}=g_{\theta}(\Lambda)\hat{x}=g_{\theta}(\Lambda)U^Tx$

再将频域信号转换到时域（或者说vertex domain），有

$y=U\hat{y}=Ug_{\theta}(\Lambda)U^Tx=g_{\theta}(U\Lambda U^T)x=g_{\theta}(L)x$

所以，要学$g_{\theta}()$函数。这个函数的选取需要考虑两个方面

参数规模：上述推导的参数规模是$N$，不希望这么大
局部视野特性：我们不希望当前节点能看到所有节点，所以函数不能分解成无限多项（因为矩阵$L$的$N$次方表示当前节点可以看到任何连通节点的信息）

ChebNet

$g_{\theta}(L)=\sum_{k=0}^K\theta_kL^k$

优点：

参数规模：O(K)
局部视野特性：K-localized
缺陷：
复杂度问题：矩阵乘法复杂度为O(N^2)，K次方下计算量大

根据Chebyshev多项式，满足

$T_0(\hat{\Lambda})=I, I\ is\ identity\ matrix \\ T_1(\hat{\Lambda})=\hat{\Lambda} \\ T_k(\hat{\Lambda})=2xT_{k-1}(\hat{\Lambda})-T_{k-2}(\hat{\Lambda})$

其中$\hat{\Lambda}=\frac{2\Lambda}{\lambda_{max}}-I, \hat{\lambda}\in[-1, 1]$。这个公式可以利用推倒结构，以

$y=\sum_{k=0}^K\theta'_kT_k(\hat{L})x \tag{1}$

代替原来的计算方式，降低计算复杂度。
每组$\theta$等价于一个filter，可以有多个filter，当作多个特征提取工具。

GCN是在公示1的基础上再做简化

令K=1，即只考虑两项
$\hat{L}\approx L-I$，如果$L$是normalized laplacian，有$\lambda_{max} \approx2$，又$\hat{L}=\frac{2L}{\lambda_{max}}-I$
根据Symmetric normalized Laplacian定义有$L=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$
再次简化模型，令：$\theta=\theta’_0=-\theta’_1$
- $y=\theta(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x$
再次trick，$I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \to \hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}$
- $\hat{A}=A+I$
- $\hat{D}_{ii}=\sum_j\hat{A}_{ij}$，参考原paper
- $H^{(l+1)}=\sigma(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$，这里$W$对应$\theta$

上面重写一下(邻域要包含自己)：

$h_v=f\left( \frac{1}{|N(v)|}\sum_{u\in N(v)}Wx_u+b \right)$

[1]. https://www.bilibili.com/video/BV1G54y1971S?p=2

[2]. SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS