http://snap.stanford.edu/class/cs224w-2019/slides/05-spectral.pdf
三个步骤：预处理（变成矩阵形式）、分解（特征值和特征向量，并且通过特征向量的分量得到低维表示）、分组（用刚才得到的低维表示聚类）
问题定义：将图进行划分（Partitioning），一个好的划分可以最大化每组内的连接，最小化组间的连接。划分可以被表示为边切割（edge cut），$cut(A,B)$是端点不在同一个组内的边数目。直接按照$cut(A,B)$作为评判标准并不一定会有好的效果，因为没有考虑内部的连接最大化。
可以使用Conductance作为判断的标准，大概是组之间的连接 除以 组内密度，公式是：
数学基础
为了进行划分，先了解邻接矩阵A和一个向量x相乘的含义，代表每个节点聚集了邻居的信息。
在此使用特征值和特征向量，对于一个所有节点度数都是d的图（d-regular graph），d为一个特征值，(1,1,…,1)为一个特征向量，这是最大特征值。如果是不连通的，两部分的度数都是d，则会有两个对应的特征向量(1,1,1,…,1,0,0,…,0)和(0,0,0,…,0,1,1,…,1)，对应同样的特征值d。也就是说，这时候$\lambda_n=\lambda_{n-1}$。如果中间连接着但连接的量很小，则$\lambda_n\approx \lambda_{n-1}$
如果是d-regular graph，则第二大的特征值对应的特征向量$x_{n-1}$的分量之和为0（因为特征值$\lambda_n\ne \lambda_{n-1}$，而$x_n=(1,1,…,1)$），所以可以有正有负，自然分成两类。
Laplacian matrix(L)：是D-A，如：
所以不管矩阵是什么样子，(1,1,1…,1)是一个特征向量，对应的特征值为0（这是最小的）。第二小的特征值是$\lambda_{2}=\min {x: x^{T} w{1}=0} \frac{x^{T} M x}{x^{T} x}$。
而在这里，可以发现$x^{T} L x=\sum_{i, j=1}^{n} L_{i j} x_{i} x_{j}=\sum_{i, j=1}^{n}\left(D_{i j}-A_{i j}\right) x_{i} x_{j}$
$=\sum_{i} D_{i i} x_{i}^{2}-\sum_{(i, j) \in E} 2 x_{i} x_{j}$
$=\sum_{(i, j) \in E}\left(x_{i}^{2}+x_{j}^{2}-2 x_{i} x_{j}\right)=\sum_{(i, j) \in E}\left(x_{i}-x_{j}\right)^{2}$（这里E中不包括重复的无向边，比如$(i,j)$在里面则$(j,i)$不会在其中），所以就是每条边的节点的数之差。将x调整为单位向量后，$\lambda_2$刚好就是$x^TLx$，所以要尽量让每条边的节点对应数字接近一些，所以其实就是在做聚类。
想要进行最小化，$\lambda_{2}=\min {\begin{array}{c}\text { All labolings } \ \text { of nades }i \text{ so } \ \text { that }\Sigma x{i}=0\end{array} }{\frac{\sum_{i=0}\left(x_{i}-x_{j}\right)^{2}}{\sum_{i} x_{i}^{2}}}$
故最好平衡一下正负两部分，让每一部分内部尽量接近。
最后会有一个近似度，如：
谱分解算法
还是预处理、分解、分组三步。可以按照第二小的特征值对应的向量根据正负进行分解，也可以分别计算每一个上进行分解时候的conductance，找到最小的一个。
在找到特征向量后，可以根据最小的几个特征值对应的特征向量进行划分，把这几个特征向量里面对应的几个数值拿出来作为低维特征进行聚类。也可以一直用第二小的特征值，用二分的方法进行分割。
在选择选用的特征向量数目k的时候，可以找到$\max \Delta_{k}=\left|\lambda_{k}-\lambda_{k-1}\right|$
基于motif的谱聚类
找到一个motif在图中的匹配，留下来有匹配的边，边权重是这个边被匹配到的次数。同时可以扩展之前的cut、vol、conductance的概念，如：
在此会有一个$vol_M(S)$代表的是每个motif里面在S中的节点的个数，每被匹配一次就会计算一次。比如节点1在三个motif的instance中，就会在$vol_M(S)$中贡献3。
Group的时候，可以用查找最小conductance的方法，如图：
这样做可以保证一个近似度：
$\phi_{M}(S) \leq 4 \sqrt{\phi_{M}^{*}}$
这样的方法可以用不同motif进行，找到一个最好的motif。
