本节课继续讨论Community Detection算法，讲解的是谱聚类（Spectral Clustering）算法，最后还会与前面第3节课学习的
motif知识关联起来，讲解一种基于Motif的谱聚类算法。
谱聚类算法
上面给出了谱聚类的”三步曲”，在正式讲解“三步曲”之前，我们先来定义一下谱聚类要解决什么问题？
Part 1 问题定义
给定一个图$G=(V,E)$，如下图所示，我们要在这个图上做bi-partition任务（后面的讲解是基于二簇划分问题的，当然谱聚类可以用于多簇划分），希望把下图划分成两个不相交的群体A，B，让组内尽可能相似，组间差异尽可能大。
- 那么怎么定义一个“好”的划分？怎样快速找到这样的划分呢？
Part 2 评价指标
- 在第四节课中，我们有介绍度量聚类效果的指标
modularity，这里我们使用一种新的聚类度量指标conductance； - 同样，我们之前的目标是最大化
modularity，因此在本节课我们的目标是最大化conductance。
对于一个好的划分，一个很自然的想法，直觉上就是最大化组内连接数，最小化组间连接数：
我们其实可以很形象地将图上的聚类划分问题，看做一个切割的过程：
cut：这里的cut是一个名词，它有全新的意义。它是定义在两个簇共享的边集的sum值。
但是如果我们想最小化cut有一个问题，如上图所示，当有一个节点度数为1时，切割这一条边可最小化cut，即cut=1，但是很显然这并不是最优化的划分结果，直觉上看，最优化的划分应该为蓝色线所示。
正是由于前面讲的那种degenerate case，我们需要进一步对度量指标
cut进行归一化来考虑group内的connectivity信息——conductance:我们想
conductance变小，所以我们就会想让vol(A)和vol(B)都能变得尽可能大，从而避免前一张PPT上的极端情况。由
conductance计算公式的含义我们知道它能够产生相对均匀划分；但是求解一个这样的最优的conductance是一个NP-hard问题。根据我们的机器学习经验，我们需要寻找一个近似解
这个近似解就是谱聚类
Part 3 谱图划分
重新理解$Ax$的意义——聚合邻居的信息
- 之前我们重新审视了$Ax$，现在让我们结合重新审视的$Ax$来回想一个啥是eigenvector，eigenvalue？
these are special vectors assigned to nodes such that when you sum up the value from your neighbors you get the same value as you had you just scaled miraculous！！！
spectrum：频谱，需要注意的是spectrum里面的特征值是严格按照从小到大的顺序排列的！这其实与电路与信号里面的傅里叶变换联系起来了，这里的频率就是特征值。
Example: d-Regular Graph
d-regular graph
Example: Graph on 2 Components
这里
eigenvalue：$d$的multiplicity是2，也就是是说它由两个eigenvector。在这种类型的图中，the max eigenvalue的multiplicity可以告诉我们有多少的components。$\lambda_n = \lambda_{n-1}$是因为multiplicity的大小
关于almost disconnected的时候，$\lambda_{n-1}$会非常接近$\lambda_n$的原因将会在后面学到。
Eigenvectors are orthogonal的原因在于Adjacency Matrix为对称矩阵！
it means some coordinates should be higher than 0，一些会小于0；
再次提醒，老师这里举例子是2个partition的问题；
Adjacency Matrix
- 这里的n个real eigenvalues可能有重复的。
Degree Matrix
Laplacian Matrix
- 0是我们这个问题中最小的eigenvalue（？）
- Laplacian Matrix$L$是一个半正定矩阵，详细证明如下：
注意是对于每一个symmetric matrix都有这样一个fact！
optimization problem
$x^TLx$就是二次型的定义，所以要回顾一下二次型才是~
只遍历边（i,j），所以需要乘以2。
再观察一下，我们的$x_i^2$一共计算了$D_{ii}$次，也就是度的次数，于是我们根据它的边来拆分$D_{ij}$次，可以得到一个完全平方式。
- eigenvector的长度为1，这个是可以Normalize的
- restate之前的equation
- 我们可以想象$x$向量代表的是label，那么0两端的话，值会很大。
- 因为sum要为1，我们尽量让两端的点的数量相等。
- 如上所示，$\lambda_2$有着非常神奇的eigenvector；
Fiedler的这个想法和我们之前得到的那个restate其实是差不多的，但是他的这个严格性太强了！这个最终结果会统计横跨0左右两端的数量。- 在前一页PPT里面我们不会去enforce两个集合相等
- 我们称这里的vector为Fiedler vector
- a spectral term spectral graph theory
- 同样是之前的那个式子，这里是enforce其中的向量的总和为0，然后y的长度为1.
这里的证明展示了这种基于图的Laplacian矩阵的spectral clustering会给你一个近似最优解
它会小于最优解的两倍，说明还是很有用的
前面是mathematical intuition，接下来是实打实的算法~
老师说 how beautifully it captures the graph structure~左图和右图完美匹配。
如果有四个类别怎么办？
如上所示，我们依然使用之前的方法得到$x_2$，虽然它是用于二分类问题的，但是你可以发现，在0以上和0以下，依然还可以在划分为两个类别。
如何$\lambda_2$和$\lambda_1$是相等的，老师说自己的理论就会不成立。那么为什么不连通的图，他的两个就是相等的呢？好像我可以分析出来。
这里k的数量不等于最后聚类的数量。
Why Use Multiple Eigenvectors？
- emphasize cohesive clusters
- well-separated space
- amplified 放大
- attenuate 减弱
注意是降序的。。。
如果我们的图是disconnected，那么$\lambda_1$和$\lambda_2$就是相等的了，如果是近似disconnected，那么$\lambda_1$和$\lambda_2$就应该是差不多大小。
for a general graph，the maximum eigenvalue will correspond to the density of the graph，now we create the graph laplacian that kind of flipped the spectrum around，so the largest eigenvalue D mapped to the trivial eigenvalue of 0。
基于motif的谱聚类算法
接下来，介绍一种super exciting extension of the spectral clustering method：
能否基于motif进行聚类？
划分出上图红圈中的cluster。
将前面提到的cut和volume的概念迁移到motif上：
- motif cut=1
- motif volume=10
next,how do i automatedly find good cuts,how do I find clusters of motifs?
$W^{M}$的值随着$M$的不同而变化。
要将其变成无向图
尽管我们最后变成了无向图，看起来有点像edge cut，但是实际上还是原来的motif cut
分情况寻找划分的点。
sweep procedure：扫描过程
aquatic layer
