svd算法的论文参考文献

姓名：刘保阔 学号： 转自： 【嵌牛导读】       奇异值分解（Singular Value Decomposition）是 矩阵论 中一种重要的 矩阵 分解，奇异值分解则是 特征 分解在任意矩阵上的推广。在 信号处理 、 统计学 等领域有重要应用。 【嵌牛正文】 一、奇异值与特征值基础知识：   特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。两者有着很紧密的关系，我在接下来会谈到，特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。先谈谈特征值分解吧：    1）特征值：     如果说一个向量v是方阵A的特征向量，将一定可以表示成下面的形式：     这时候λ就被称为特征向量v对应的特征值，一个矩阵的一组特征向量是一组正交向量。特征值分解是将一个矩阵分解成下面的形式：     其中Q是这个矩阵A的特征向量组成的矩阵，Σ是一个对角阵，每一个对角线上的元素就是一个特征值。我这里引用了一些参考文献中的内容来说明一下。首先，要明确的是，一个矩阵其实就是一个线性变换，因为一个矩阵乘以一个向量后得到的向量，其实就相当于将这个向量进行了线性变换。比如说下面的一个矩阵： 它其实对应的线性变换是下面的形式： 因为这个矩阵M乘以一个向量(x,y)的结果是： 上面的矩阵是对称的，所以这个变换是一个对x，y轴的方向一个拉伸变换（每一个对角线上的元素将会对一个维度进行拉伸变换，当值>1时，是拉长，当值<1时时缩短），当矩阵不是对称的时候，假如说矩阵是下面的样子： 它所描述的变换是下面的样子： 这其实是在平面上对一个轴进行的拉伸变换（如蓝色的箭头所示），在图中，蓝色的箭头是一个最主要的变化方向（变化方向可能有不止一个），如果我们想要描述好一个变换，那我们就描述好这个变换主要的变化方向就好了。反过头来看看之前特征值分解的式子，分解得到的Σ矩阵是一个对角阵，里面的特征值是由大到小排列的，这些特征值所对应的特征向量就是描述这个矩阵变化方向（从主要的变化到次要的变化排列）。 当矩阵是高维的情况下，那么这个矩阵就是高维空间下的一个线性变换，这个线性变化可能没法通过图片来表示，但是可以想象，这个变换也同样有很多的变换方向，我们通过特征值分解得到的前N个特征向量，那么就对应了这个矩阵最主要的N个变化方向。我们利用这前N个变化方向，就可以近似这个矩阵（变换）。也就是之前说的：提取这个矩阵最重要的特征。总结一下，特征值分解可以得到特征值与特征向量，特征值表示的是这个特征到底有多重要，而特征向量表示这个特征是什么，可以将每一个特征向量理解为一个线性的子空间，我们可以利用这些线性的子空间干很多的事情。不过，特征值分解也有很多的局限，比如说变换的矩阵必须是方阵。   2）奇异值：     下面谈谈奇异值分解。特征值分解是一个提取矩阵特征很不错的方法，但是它只是对方阵而言的，在现实的世界中，我们看到的大部分矩阵都不是方阵，比如说有N个学生，每个学生有M科成绩，这样形成的一个N * M的矩阵就不可能是方阵，我们怎样才能描述这样普通的矩阵呢的重要特征呢？奇异值分解可以用来干这个事情，奇异值分解是一个能适用于任意的矩阵的一种分解的方法： 假设A是一个N * M的矩阵，那么得到的U是一个N * N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个N * M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N * N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），从图片来反映几个相乘的矩阵的大小可得下面的图片 那么奇异值和特征值是怎么对应起来的呢？首先，我们将一个矩阵A的转置 * A，将会得到一个方阵，我们用这个方阵求特征值可以得到：这里得到的v，就是我们上面的右奇异向量。此外我们还可以得到： 这里的σ就是上面说的奇异值，u就是上面说的左奇异向量。奇异值σ跟特征值类似，在矩阵Σ中也是从大到小排列，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解：     r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子：     右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。 二、奇异值的计算：     奇异值的计算是一个难题，是一个O(N^3)的算法。在单机的情况下当然是没问题的，matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值，但是当矩阵的规模增长的时候，计算的复杂度呈3次方增长，就需要并行计算参与了。Google的吴军老师在数学之美系列谈到SVD的时候，说起Google实现了SVD的并行化算法，说这是对人类的一个贡献，但是也没有给出具体的计算规模，也没有给出太多有价值的信息。     其实SVD还是可以用并行的方式去实现的，在解大规模的矩阵的时候，一般使用迭代的方法，当矩阵的规模很大（比如说上亿）的时候，迭代的次数也可能会上亿次，如果使用Map-Reduce框架去解，则每次Map-Reduce完成的时候，都会涉及到写文件、读文件的操作。个人猜测Google云计算体系中除了Map-Reduce以外应该还有类似于MPI的计算模型，也就是节点之间是保持通信，数据是常驻在内存中的，这种计算模型比Map-Reduce在解决迭代次数非常多的时候，要快了很多倍。 Lanczos迭代 就是一种解对称方阵部分特征值的方法（之前谈到了，解A’* A得到的对称方阵的特征值就是解A的右奇异向量），是将一个对称的方程化为一个三对角矩阵再进行求解。按网上的一些文献来看，Google应该是用这种方法去做的奇异值分解的。请见Wikipedia上面的一些引用的论文，如果理解了那些论文，也“几乎”可以做出一个SVD了。     由于奇异值的计算是一个很枯燥，纯数学的过程，而且前人的研究成果（论文中）几乎已经把整个程序的流程图给出来了。更多的关于奇异值计算的部分，将在后面的参考文献中给出，这里不再深入，我还是focus在奇异值的应用中去。 三、奇异值与主成分分析（PCA）： 主成分分析在上一节里面也讲了一些，这里主要谈谈如何用SVD去解PCA的问题。PCA的问题其实是一个基的变换，使得变换后的数据有着最大的方差。方差的大小描述的是一个变量的信息量，我们在讲一个东西的稳定性的时候，往往说要减小方差，如果一个模型的方差很大，那就说明模型不稳定了。但是对于我们用于机器学习的数据（主要是训练数据），方差大才有意义，不然输入的数据都是同一个点，那方差就为0了，这样输入的多个数据就等同于一个数据了。以下面这张图为例子： 这个假设是一个摄像机采集一个物体运动得到的图片，上面的点表示物体运动的位置，假如我们想要用一条直线去拟合这些点，那我们会选择什么方向的线呢？当然是图上标有signal的那条线。如果我们把这些点单纯的投影到x轴或者y轴上，最后在x轴与y轴上得到的方差是相似的（因为这些点的趋势是在45度左右的方向，所以投影到x轴或者y轴上都是类似的），如果我们使用原来的xy坐标系去看这些点，容易看不出来这些点真正的方向是什么。但是如果我们进行坐标系的变化，横轴变成了signal的方向，纵轴变成了noise的方向，则就很容易发现什么方向的方差大，什么方向的方差小了。     一般来说，方差大的方向是信号的方向，方差小的方向是噪声的方向，我们在数据挖掘中或者数字信号处理中，往往要提高信号与噪声的比例，也就是信噪比。对上图来说，如果我们只保留signal方向的数据，也可以对原数据进行不错的近似了。     PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。    还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个m * n的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。     而将一个m * n的矩阵A变换成一个m * r的矩阵，这样就会使得本来有n个feature的，变成了有r个feature了（r < n)，这r个其实就是对n个feature的一种提炼，我们就把这个称为feature的压缩。用数学语言表示就是： 但是这个怎么和SVD扯上关系呢？之前谈到，SVD得出的奇异向量也是从奇异值由大到小排列的，按PCA的观点来看，就是方差最大的坐标轴就是第一个奇异向量，方差次大的坐标轴就是第二个奇异向量…我们回忆一下之前得到的SVD式子： 在矩阵的两边同时乘上一个矩阵V，由于V是一个正交的矩阵，所以V转置乘以V得到单位阵I，所以可以化成后面的式子 将后面的式子与A * P那个m * n的矩阵变换为m * r的矩阵的式子对照看看，在这里，其实V就是P，也就是一个变化的向量。这里是将一个m * n 的矩阵压缩到一个m * r的矩阵，也就是对列进行压缩，如果我们想对行进行压缩（在PCA的观点下，对行进行压缩可以理解为，将一些相似的sample合并在一起，或者将一些没有太大价值的sample去掉）怎么办呢？同样我们写出一个通用的行压缩例子： 这样就从一个m行的矩阵压缩到一个r行的矩阵了，对SVD来说也是一样的，我们对SVD分解的式子两边乘以U的转置U' 这样我们就得到了对行进行压缩的式子。可以看出，其实PCA几乎可以说是对SVD的一个包装，如果我们实现了SVD，那也就实现了PCA了，而且更好的地方是，有了SVD，我们就可以得到两个方向的PCA，如果我们对A’A进行特征值的分解，只能得到一个方向的PCA。 四、奇异值与潜在语义索引LSI： 潜在语义索引（Latent Semantic Indexing）与PCA不太一样，至少不是实现了SVD就可以直接用的，不过LSI也是一个严重依赖于SVD的算法，之前吴军老师在 矩阵计算与文本处理中的分类问题 中谈到：     “三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。”      上面这段话可能不太容易理解，不过这就是LSI的精髓内容，我下面举一个例子来说明一下，下面的例子来自LSA tutorial，具体的网址我将在最后的引用中给出： 这就是一个矩阵，不过不太一样的是，这里的一行表示一个词在哪些title中出现了（一行就是之前说的一维feature），一列表示一个title中有哪些词，（这个矩阵其实是我们之前说的那种一行是一个sample的形式的一种转置，这个会使得我们的左右奇异向量的意义产生变化，但是不会影响我们计算的过程）。比如说T1这个title中就有guide、investing、market、stock四个词，各出现了一次，我们将这个矩阵进行SVD，得到下面的矩阵： 左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程序，数字越大越重要。       继续看这个矩阵还可以发现一些有意思的东西，首先，左奇异向量的第一列表示每一个词的出现频繁程度，虽然不是线性的，但是可以认为是一个大概的描述，比如book是对应文档中出现的2次，investing是对应了文档中出现了9次，rich是对应文档中出现了3次；       其次，右奇异向量中一的第一行表示每一篇文档中的出现词的个数的近似，比如说，T6是，出现了5个词，T2是，出现了2个词。       然后我们反过头来看，我们可以将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到： 在图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。这样一减少我们的检索、存储量，因为这样压缩的文档集合和PCA是异曲同工的，二可以提高我们的用户体验，用户输入一个词，我们可以在这个词的近义词的集合中去找，这是传统的索引无法做到的。

动态图上的异常检测任务包括：发现异常的对象、关系、时点。动态图上的异常检测与静态图上的异常检测不同的地方在于：

本文首先将异常类型分为：anomalous vertices, edges, subgraphs, and events(or change)，将使用的方法分为：community detection, MDL(minimum description length) and compression, decompression, distance, probabilistic， 按每种方法使用的异常类型进行了文献学分类。各方法的主要参考文献见表1：

本文假设不同时点的节点和边都有唯一标签从而不会混淆，定义 为图序列，其中 为总时间步， ， 为节点集， 为边集， 时称 为图流。本文的主要记号见表2：

给定 ，节点集 ,打分函数 ，定义异常节点集为 ，使得对于 ， ，其中 为得分 的摘要式统计。

一个典型的异常节点如图1，其可由基于社区检测的方法识别，即： 其中 为节点所属的社会划分, 为异或操作。

给定 ，边集 ,打分函数 ，定义异常边集为 ，使得对于 ， ，其中 为得分 的摘要式统计。

一个典型的异常边如图2，可令 ，其中 为时间步 时 的权重,可以为边的概率。

给定 ，子图集 ,打分函数 ，定义异常集为 ，使得对于 ， ，其中 为得分 的摘要式统计。

两种典型的异常子图如图3,其中(a)为图的收缩，(b)为图的分裂。图的收缩可根据子图中的的数量衡量，即 ，图的分裂可由不同时间点社区的数量衡量。

与异常节点、边、子图检测不同，异常事件或异常突变检测检验的是时点。

给定 ,打分函数 ，若时点 满足: ， ，则称时点 为一个事件。

给定 ,打分函数 ，若时点 满足: ， ，则称时点 为一个突变。

通常的异常检测都使用两步法：第一步，基于特征的图表示；第二，基于机器学习的异常检测。

基于社区检测的方法关注的是社区和关联节点的演化过程，特征向量的生成亦基于图中的社区结构。不同社区检测方法的区别在于：（1）社区结构的领域，如社区内的连接性.单个节点在每一步所属的社区；(2)社区结构的定义，如基于概率的软社区定义.硬社区定义。基于社区检测的方法可用于异常定点、子图、突变的检测。

基于软社区匹配并单独考察每一个社区，我们可以在连续时间步内计算每个节点归属的平均变化，如果某个节点归属的平均变化显著异于其他节点，则称其为演化社区异常点。

节点社区归属的变化可以构造一个时间模式，称为软时序模式。一些文献使用了最小描述长度(MDL)结合非负矩阵分解的方法来自动检测节点角色及构造转移模型。多数文献通过抽取图中不同节点的共同模式，并比较每个节点与共同模式之间的差异来定义异常节点。部分文献使用了交替迭代优化替代常用的两步法。部分文献使用了corenet的概念，该概念不同于单纯使用density,modularity,hop-distance等概念，而是使用了节点间的加权路径，即一个节点的corenet包含该节点与权重大于给定阈值的两跳邻居。假设两个强连接的节点通常属于同一社区，则如果移除一个节点的两个邻居，一个邻域具有较高的边权重，另一个具有较低的边权重，则移除较高权重邻居的影响应更大，在每一步，每个节点首先被赋予一个异常得分，该得分衡量了其corenet的变化，异常得分较高的 各节点将被视为异常节点。

文献【69】定义了六种基于社区的异常：shrink, grow, merge, split, born, and vanish。其使用图和社区代表(representatives)进行比较以减少计算量，图代表为出现在t时刻，同时还出现在t-1、t+1或t+1与t-1时刻的节点集，社区代表是出现在其他社区最少的定点集合，基于社区代表和图代表，基于规则，判断社区是否落在六种异常中。

文献【73】定义了一种基于社区的异常：comet，周期性出现或消失的社区，演化图可表示为一个张量，然后基于低秩张量分解和MDL原则进行comet检测。

文献【3】基于多种信息源构造时序复网络，识别跨时间和网络的稳定社区结构。行为相似的网络可以用聚类或前验知识分组，如何一个社区结构在组内跨时间步稳定，但在组外没有对应社区，则该社区即为异常，如何两个社区共享一定比例的定点则称为对应。

社交网络可以根据特定时间窗口内的发文量定义事件，一个经历共同事件的组即构成一个异常子图。

通过划分图流为一致的分割来检测，分割是依据划分的相似性。

通过将最新图的顶点分区与当前增长分割中的图的分区进行比较，可以在线找到这些分割。【67】基于可返回随机的相关矩阵和modularity最大化来进行定点划分，当新图的划分与当前分割的划分有很大不同时，一个新段开始，并将新图的时间点输出为检测到的突变。两个划分的相似度使用Jaccard系数定义。GraphScope思路类似，但基于MDL来指导划分和分割。

基于MDL原则和基于该原则的压缩技术利用数据中的模式和规律性实现紧凑的图表示，其主要通过将图的邻接矩阵表示为一个二进制串，如果矩阵的行和列可以重新排列使矩阵的二进制字符串表示的熵最小化，那么压缩损失（也称为编码损失）就会最小化。数据指向的特征都来自于图或其特定子结构的编码代价；因此，异常被定义为抑制可压缩性的图或子结构（如边）

对于一条边和对应子图，如果包含该边的编码损失比不包含该边的编码损失高，则称该边为异常边。

【74】使用了一种两步交替迭代法进行节点的自动划分，当节点划分的熵收敛时，根据包含和不包含该边的编码损失，该方法也给出了边的异常度得分。

突变检测的主要思路是:连续时间步间的图是相似的，因而可以分为一组，从而降低压缩比。压缩比的上升表明新一个时间步的图与已有的图差异明显，因此是一个突变。

该方法将图集合表示为一个tensor，在该tensor上进行矩阵分解或降维，基于分解或降维后的图发现其模式和规律性，该方法可以融合更多属性信息，最常用的方法是SVD和PARAFAC（广义SVD）。

矩阵分解可用于计算每个节点的活跃（activity)向量，如果某个节点的活跃向量在连续时间步间变化明显，则称为异常节点。

【87】首先抽取每个节点的边相关矩阵 ，即该节点的每个邻域都有一行一列，对于节点 的矩阵中的一个entry 代表了边 和 间加权频率的相关性，加权频率由衰减函数获得，时间越近权重越高。M的最大特征值和对应特征向量即顶点的活跃向量的summary及边的相关性。通过寻找这些值的变化而形成的时间序列用于计算每个时间步长中每个顶点的分数，得分高于阈值的顶点将被输出为异常。

基于分解的异常事件检测有两种方法：（1）先基于分解方法来近似原始数据，然后以重建损失作为近似优劣的指标。如果某个子张量、切片或元素的重建损失很高，则即可以视其与周围数据不同特征不同，将其标记为异常事件、子图或节点。（2）跟踪奇异值和向量，以及特征值和特征向量，以检测异常顶点的显著变化。

为解决 intermediate blowup 问题（即计算中输入和输出张量超过内存限制），【81】提出了momery-efficient tucker（MET）分解方法，该方法源于Tucker分解，Tucker分解将高阶tensor用一个core tensor和每个mode(维度)矩阵表示。【80】使用了Compact Matrix Decomposition(CMD)，其可以用来计算给定矩阵的稀疏低秩矩阵。使用CMD对图流中的每个邻接矩阵进行分解，可得到重建值的时间序列，基于重建值序列可进程事件检测，典型应用有COLIBRI, PARCUBE，其中后者在斑点(spotting)异常中的表现更高效。

【84】使用了随机图模型进行基于概率模型的检测，其将真实图邻接矩阵和期望图的邻接矩阵间的差异构造为残差矩阵，对残差矩阵执行SVD，再使用线性Ramp滤波器，基于top奇异值即可进行异常时间窗口检测，通过检查正确的奇异向量来确定相应的顶点。

除以上方法，我们还可以基于分解空间的显著变化来识别事件。【77】通过对数据执行PCA，计算的特征向量可以分为正常和异常两个集合，方法是检验数据中的值映射到特征向量。在每个时间步，根据特征值对特征向量进程降序排列，第一个特征向量则包含一个在其余值的3个标准差之外的投影点，此后的每个特征向量，都构成了异常集。第二步即是将数据映射到正常和异常子空间，一旦完成了这些操作，当从上一个时间步长到当前时间步异常成分的修改超过一个阈值时，即将其视为一个事件。【83】扩展了该方法，提出了联合稀疏PCA和图引导的联合稀疏PCA来定位异常和识别对应的顶点。通过为异常集使用稀疏的成分集，可以更容易识别负责的顶点。顶点根据它们在异常子空间中对应行的值得到一个异常分数，由于异常分量是稀疏的，不异常的顶点得分为0。

图的活跃向量 为主成分，左奇异向量对应最大奇异值，奇异值和奇异向量通过对加权邻接矩阵进行SVD得到。当活跃向量大幅异于“正常活跃"向量时，即定义该时点为突变点，”正常活跃“向量由前序向量得到。

正常活跃向量 ，它是对最后W时间步中活动向量形成的矩阵进行SVD得到的左奇异向量。每个时点都定义一个得分 ,其代表了当前活跃向量与正常向量的差异。异常可以使用动态阈值方案在线发现，其中得分高于阈值的时间点被输出为变化。通过计算正常向量和活动向量之间的变化比率来找到负责的顶点，与变化最大的索引所对应的顶点被标记为异常，类似的方法也可以用于节点-节点相关矩阵的活跃向量，或基于邻居相似度的节点-节点相关矩阵。

基于距离的异常检测算法的不同点在于选择用于提取和比较距离度量，以及它们用于确定异常值和相应图的方法。

如果一些边的属性演化异于正常演化，则该边就是一个异常边。

边之间的权重使用衰减函数定义，在每个时间步长中，根据相似度得分的变化之和计算每条边的异常值得分，使用阈值或简单的 作为异常值标准。

将网络视为边的流，意味着网络没有固定的拓扑，一个边的频率和持久性可以用来作为其新颖性的指标，【48】定义了集合系统不一致性指标来度量频率和持久性，当一条边到达时，计算其差异，并与活动边集的平均不一致性值进行比较，如果边的加权不一致性大于平均不一致性的阈值水平，则声明该边为异常边，基于异常边，可以进一步识别其他异常图元素（如顶点，边，子图）。

具有许多“异常”边的子图即是异常的子图。

【52】将边的权重视为异常得分，每个时间步长上的每条边都有它自己的异常分数，给定了该边权值在所有图序列的分布，该分数表示在该特定的边上看到该特定权值的概率函数。或者，为网络中的边分配异常值分数的现有方法的输出可以用作为该方法的输入。后一种方法允许应用于任何能够为边分配异常值分数的网络，一旦完成每条边的异常打分，即可发现显著异常的区域（SARs），即一个窗口内的固定子图，其类似于HDSs。【112】提出了一种迭代算法，该算法首先固定子图发现最优时间窗口，然后固定时间窗口发现最优子图。【97】拓展了该方法，允许子图渐变，即在相邻时间步间增加或移除顶点。

定义函数 为测度图距离的函数，将其应用于连续图序列，即得到距离序列，基于该距离序列应用一些启发式算法（如基于移动平均阈值的 取值）即可得到异常事件。

称每个顶点及其egonet的特征为局部特征，整张图的特征为全局特征。每个顶点的局部特征可聚合为一个向量，基于该向量的各阶矩可构造signature向量，利用signature向量间的Canberra距离（归一化的曼哈顿距离）可构造图之间的距离函数【93】。【92】利用全局特征，定义了一种基于dK-2序列的距离测度，将高于阈值的特征视为异常点。

【96】使用了顶点亲和度（即一个顶点对另一个顶点的影响，可以用于快速信念传播）得分作为signature向量，其基于连续时间步技术顶点亲和度，基于马氏距离度量两个图的相似度，亲和度得分的变化反应并适应变化的影响水平，例如桥边的移除比正常边移除的得分更高。利用单个移动范围的质量控制，可以对相似度得分的时间序列设置一个移动阈值，如指数移动平均加权。

作为特征相似度的补充，我们也可以比较两个图的结构差异来度量突变的大小，这类方法致力于发现定义距离的函数而非发现特征向量。【88】计算了异常网络的10种距离函数，使用ARMA模型构造特征值的正常模型，然后基于正常模型计算时点的残差，残差超过给定阈值的时间即可标记为异常。10种距离函数中，基于最大共有子图的方法表现最好。【90】使用了五中得分函数（顶点/边重叠，顶点排序，向量相似度，序列相似度，signature相似度）来检测三种异常（子图缺失，顶点缺失，连通性变化），表现最好的方案是抽取每个顶点和边的特征构造signature向量，使用SimHash定义距离。

我们还可以通过计算每个图的稳健性序列来检测事件，稳健性序列是图连通性的测度，具有高稳健性的图即使在去除一些顶点或边的情况下，也能保持相同的一般结构和连通性，事件检测即发现稳健性值异常变化的时点【95】。【89】使用的是图半径的变体作为稳健性指标，图半径的定义是基于所有顶点的平均离心度，而非常用的最大离心度。

基于概率理论、分布、扫描统计学等方法可以构造“正常”样本的模型，偏离该模型的样本即视为异常，这类方法的主要区别在于构造方法、建模对象、离群值定义。

主要有两种方法：一，构造扫描统计时间序列并检测离均值若干标准差的点；二，顶点分类。

扫描统计常称为滑动窗口分析，其在数据的特征区域中发现测度统计量的局部最小或最大值。对某个特定图，扫描统计量可以是图不变特征的最大值，如边的数量。

【8】使用了一个适应测度统计量的变量，即每个节点的0-2度邻居数，然后对每个顶点的局部统计量使用近期值的均值和标准差进行标准化，图的扫描统计量即最大的标准化局部统计量。标准化可以解释每个顶点的历史信息，代表每个顶点的统计量只与自己的历史信息有关而与其他顶点无关。这保证测度的最大变化与变化的绝对量无关而与比例有关。基于扫描统计量标准化时间序列，将序列均值的五个标准差作为异常值。最负责的顶点被确定为为整个图的扫描统计值所选择的顶点。

类似于使用邻居进行扫描统计，我们还可以用Markov随机场（MRF）来发现节点的状态，并通过信念传播算法推断最大似然分配，其中，每个顶点标签取决于其邻居节点。【99】通过发现二部核来检测异常点（即犯），二部核定义为犯与从犯间的交互。利用边的插入或删除只影响局部子图这一事实，它在添加新边时逐步更新模型。在传播矩阵中，一个顶点可以处于三种状态之一：欺诈者、共犯者或诚实者。

边异常检测通常使用计数过程建模，统计上显著异于该模型的边标记为异常边。

【50】用贝叶斯离散时间计数过程来建模顶点间的通信次数（边权重），并根据新图更新模型。基于学习到的计数的分布，对新观测的边进行预测 值计算，基于 值标记异常顶点对。

首先用固定的子图，多重图，累积图来构造预期行为的模型，对模型的偏离可作为子图异常检测的依据。

【104】结合扫描统计量和隐马尔可夫模型（HMM）建模边行为，其使用的局部扫描统计量是基于两种图形状：k-path图和星型图，其将滑动窗口的扫描统计数据与其过去的值进行比较，并使用在线阈值系统识别局部异常，局部异常是所有统计上显著的子图(代表k个路径或恒星)的并集。

另一个建模动态图的方法是基于多重图，其中平行边对应于两个连续时间步顶点间的通信，初始的多重图可分解为多个针对每个时间窗口的叠套子图（TSG），TSG满足两个条件：（1）对于任何两个有共同点的边，首先开始通信的边最后完成通信；（2）存在一个根顶点r，它没有传入的边，并且有一条到TSG中每个顶点的路径。出现概率低的TSG视为异常子图。【102】

累积图即为包含直到当前时点的所有边的图，边权重依据衰减函数定义，通过识别“持久模式”来定义子图的正常行为。该持久模型识别模型如下：首先构造一种图，该图每个边根据时间来加权，然后基于该图迭代抽取最重连接成分来发现。随着累积图的发展，提取的子图将被监控，并将其当前活动与基于最近行为的预期活动进行比较来进行子图异常检测。【101】

事件检测可以基于偏离图似然模型或特征值分布的偏差来进行。

【103】提出了一种新的蓄水池抽样方法来抽取图流的结构摘要，这种在线抽样方法维持多个网络划分以构造统计上显著的摘要，当一个新图进入图流，每个边都根据不同分区的边生成模型计算出一种似然性，然后以这些似然性的几何均值作为全局图似然性。

【98】使用了类似的边生成模型，每个边 的概率都存储在矩阵 中，概率基于期望最大化估计，基于所有收发对的分布，然后为每个收发对给出潜在得分，基于所有边似然得分的均值即得到每个图的得分。

【100】计算了特征值和压缩特征等式的分布（而非计算收发对的分布），基于每个顶点都存在一个顶点局部特征时间序列的假设，可在每个时间步构造一个顶点-顶点相关矩阵，通过保留最大特征值和一组低维矩阵（每个顶点对应一个矩阵），可对相关矩阵的特征方程进行压缩，通过学习特征值和矩阵的分布，即可发现异常顶点和事件。当特征值偏离期望分布时，即认为发生了事件，当顶点的矩阵偏离矩阵分布时，可认为该顶点为异常顶点。