5190用于时间图切割的谱算法0加利福尼亚大学圣塔芭芭拉分校，CA，arlei@cs.ucsb.edu0加利福尼亚大学圣塔芭芭拉分校，CA，ambuj@cs.ucsb.edu0美国陆军研究实验室，阿德尔菲，MD，ananthram.swami.civ@mail.mil0摘要0最稀疏切割问题是识别一小组打破图的平衡顶点集的边的问题。归一化切割问题平衡的是结果集的总度数，而不是大小。图切割的应用包括社区检测和计算机视觉。然而，切割问题最初是针对静态图提出的，这个假设在许多现代应用中不成立，因为图是高度动态的。在本文中，我们引入了时间图中的最稀疏切割和归一化切割，通过强制时间上的切割的平滑性来推广它们的标准定义。我们提出了使用谱图理论、分治和低秩矩阵逼近计算时间切割的新颖表达式和算法。此外，我们将时间切割扩展到动态图信号，其中顶点具有属性。实验证明我们的解决方案准确可靠，能够发现动态社区和分析动态图过程。0CCS概念0• 信息系统 → 数据挖掘；0关键词0图挖掘；谱理论0ACM参考格式：Arlei Silva，Ambuj Singh和AnanthramSwami。2018。用于时间图切割的谱算法。在2018年万维网会议（WWW2018）论文集中。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318611801 引言0时间图表示图随时间的变化，在数据挖掘和Web应用中普遍存在。社交网络中的用户呈现出动态行为，导致社区的演化[3]。在博客等超链接环境中，新的主题驱动内容和链接结构的修改[26]。通信、流行病和移动性是其他场景，其中时间图可以帮助理解复杂过程。然而，许多静态图的关键概念和算法尚未推广到时间图[12,36]。本文重点研究时间图中的切割问题，即寻找一个小的边集（或切割），将图分割为小的顶点集。0本文根据知识共享署名4.0国际（CC BY4.0）许可发布。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW 2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31861180将图划分为平衡的顶点集的问题称为图切割问题。两个传统的图切割问题是最稀疏切割[18, 31]和归一化切割[9,40]。在最稀疏切割中，划分的结果在大小方面是平衡的，而在归一化切割中，平衡是指结果集的总度数（或体积）。图切割在社区检测、图像分割、聚类和VLSI设计等领域有应用。此外，基于图相关矩阵的特征向量计算图切割是谱图理论中最早的结果之一[9]，这个领域对信息检索[29]、图稀疏化[46]和机器学习[27]有着巨大的影响。我们研究这个新领域中的图切割的一个动机是新兴的图信号处理（SPG）领域[41]。SPG是一个用于分析驻留在图顶点上的数据的框架，是传统信号处理的一种推广。时间切割可以作为动态图上信号处理的基础。我们的贡献是，在图的一系列快照中提出了最稀疏切割和归一化切割的表达式。这个想法是在强制时间上的切割的平滑性（或稳定性）的同时扩展这些问题的经典定义。我们的表达式可以通过时间图的多重视图来理解，其中额外的边连接不同快照中的同一顶点。图1展示了一个学校网络的稀疏时间图切割[47]，其中根据接近程度连接了孩子们。顶点自然地组织成由班级产生的社区。然而，在班级之间有大量的互动（例如午餐时间）。在实验期间可以注意到联系网络发生了重大变化，导致几个顶点在分区之间移动-用顶点的形状/颜色来标识。时间切割能够捕捉到这种趋势，同时保持其余顶点的分配基本不变。传统的谱解法，即计算拉普拉斯矩阵的舍入特征向量的近似切割，不能推广到我们的设置中。因此，我们提出了新的算法，仍然在谱图理论的框架内，用于计算时间切割。我们进一步利用我们的表达式的重要属性，设计了将分治和低秩矩阵逼近相结合的高效近似算法来计算时间切割。为了也能够对嵌入在图顶点上的动态数据进行建模，我们将时间切割应用为数据驱动的小波基。我们的方法利用了空间和时间上的平滑性，展示了本文提出的技术为动态图的分析提供了一个强大而通用的框架。贡献总结。0•我们将最稀疏和归一化割推广到时间图，进一步将时间割推广到图信号。•我们通过谱图理论和分治法提出了高效的近似算法来解决时间割问题。•我们对我们的方法进行了广泛评估，将其应用于社区检测和图信号处理。0论文题目：社交网络分析和Web图算法WWW 2018，2018年4月23日至27日，法国里昂2TEMPORAL GRAPH CUTSW(ur ,vs ) =(1)σ (X ) = |(X,X )|(2)σ (X1, . . . Xm; β) =�mt=1 |(Xt,Xt )| + �m−1t=1 ∆(Xt,Xt+1)mt=1 |Xt ||Xt |(3)5200(a) 时间I (b) 时间II (c) 时间III0图1：捕捉网络交互中的主要变化的时间图割。图像在彩色下更清晰。0相关工作。计算图割是一个传统的问题[2,31]，具有各种应用，从图像分割[40]到社区检测[32]。本文侧重于最稀疏和归一化割问题，由于它们与拉普拉斯矩阵的谱、随机游走的混合时间、几何嵌入、有效电阻和图扩展器的联系而引起了特别的兴趣[9,18,46]。近年来，对于时间图中的社区检测引起了极大的兴趣。[8]提出了一种进化谱聚类技术。其思想是最小化一个成本函数α.CS +β.CT，其中CS是快照成本，CT是时间成本。FacetNet[34]和estrangement[21]在不同的聚类模型下应用了类似的方法。这些解决方案的一个重要局限性是它们以逐步方式执行社区分配，高度受局部最优解的影响。在增量聚类[7,38]中，主要目标是避免重新计算，而不是捕捉长期的结构变化。多视图聚类[5,50]结合了给定数据集中不同子集的特征（或视图），但不模拟对象随时间在群集之间的导航。与时空数据聚类[33,39]不同，我们不假设我们的数据嵌入在欧几里德空间中。在[37]中提出了一种同时使用多重图对快照进行分区的时间模块化的公式。类似的思想在[48]中应用于推广特征向量中心性。在本文中，我们通过研究多重图的谱特性[17,44]，提出了时间割问题的推广。作为我们的贡献之一，我们利用多重图和分块三对角矩阵之间的链接来高效地近似时间割[11,14]。虽然将谱图理论扩展到张量似乎是更自然的方法，但对于对称张量，特征向量的研究已经很充分[19]，而我们的情况并非如此，因为时间维度不同。我们对时间割的定义是非均匀割的一个特例[49] -第二个图是一系列断开的团，以强制在时间上进行割。与一般情况不同，一般情况需要更复杂（计算密集型）的方案[10]，时间割的松弛可以计算为两个矩阵的线性组合的特征向量（参见定理1）。图上的信号处理[41,42]是时间割的一个有趣应用。当信号嵌入到稀疏的不规则空间中时，传统的信号处理操作也是相关的。例如，在机器学习中，对象的相似性可以表示为图，标签可以表示为信号，以解决半监督学习任务[6,15]。在本文中，我们展示了如何将时间割应用为表示动态图信号的基础，即使图的结构随时间也发生变化。0本节介绍了时间割（第2.1节）和这些问题的谱算法（第2.2节）。更快的算法，使用分治法和低秩矩阵逼近，在第2.3节中介绍。我们还讨论了理论保证（第2.4节）和时间割的推广（第2.5节）。02.1 定义0时间图 G 是一个快照序列 � G 1 , G 2 , . . . G m �，其中 G t 是时间戳t 的快照。G t 是一个元组 ( V , E t , W t )，其中 V是一个固定的具有 n 个顶点的集合，E t是一个动态的无向边集合，W t : E t → R是一个边权重函数。我们将时间图建模为多重图，它连接来自不同图层的顶点。我们用 χ ( G ) = ( V , E , W ) 来表示 G的多重视图，其中 V = { v t | v ∈ V 且 t ∈ [1 , m ] } ( |V| = nm)，E = E 1 ∪ . . . E t ∪ { ( v t , v t + 1 ) | v ∈ V 且 t ∈ [1 , m− 1] }。因此，E 还包括节点 v t 和 v t + 1之间的“垂直”边。边权重函数 W : E → R 的定义如下：0W t ( u , v ) ，如果 ( u , v ) ∈ E t 且 r= t 且 s = t β，如果 u = v 且 | r - s | =10，否则0因此，每个顶点 v ∈ V 在 χ ( G ) 中有 m 个代表 { v 1 , . . . v m}。除了对应于每个快照的内部层边缘连接性的内部层边缘之外，连续版本的顶点 v 在不同层之间连接的时间边缘 ( v t , v t + 1 )称为对角耦合 [4]。内部层边缘的权重与 G中的相同，而层间边缘的权重设置为 β。02.1.1 最稀疏切割。图形切割 ( X , X ) 将 V分为两个不相交的集合：X � V 和 X = V - X。我们用切割的权重 | ( X, X ) | = � u ∈ X , v ∈ X W ( u , v ) 来表示。切割的稀疏度 σ是切割权重与集合大小的乘积的比值[31]：0在这里，我们将切割稀疏度的概念扩展到时间图。时间切割 � ( X 1 , X 1 ) , . . . ( X m , X m ) � 是一个图切割的序列，其中 ( X t , X t )是图快照 G t的切割。这个想法是，在时间图中，除了切割权重和分区大小之外，我们还关心切割在时间上的平滑性（即稳定性）。我们将时间切割的稀疏度 σ 形式化如下：0其中 ∆( X t , X t + 1 ) = β | ( X t , X t + 1 ) | 是从 X t 移动到 X t +1 的顶点数（或 | X t ∩ X t + 1 | ）乘以常数β，这允许给切割的平滑性赋予不同的权重。图2展示了一个时间图的两个备选切割（β =1）。切割I（图2a）是平滑的，因为没有顶点改变分区，它的权重为5。切割II（图2b）是一个更稀疏的时间切割，权重为3，只有一个顶点改变分区。请注意，如果将 β设置为2而不是1，切割I将比切割II更稀疏。我们将时间图中最稀疏的切割问题形式化如下。0论文集：社交网络分析和网络图算法，WWW 2018，2018年4月23日至27日，法国里昂G1G2G1G2G1G2arg minX1...Xmσ (X1, . . . Xm; β)ϕ(X ) =|(X,X )|(4)ϕ(X1, . . . Xm; β) =�mt=1 |(Xt,Xt )| + �m−1t=1 ∆(Xt,Xt+1)mt=1 vol(Xt )vol(Xt )(5)arg minX1...Xmϕ(X1, . . . Xm; β)L =������L1 + βIn−βIn0. . .0−βInL2 + 2βIn−βIn. . .0....... . .−βIn00. . .−βInLm + βIn������.x⊺Lx =(u,v)∈E(x[u] − x[v])2W (u,v)= 4|(Xt,Xt )| + 4∆(Xt,Xt+1)Track: Social Network Analysis and Graph Algorithms for the WebWWW 2018, April 23-27, 2018, Lyon, France5210(a) 时间切割I0(b) 时间切割II0(c) 多重切割II0图2：同一图形的两个时间切割和切割II的多重视图。对于β =1，切割I的稀疏度为(2 + 3 + 0) / (4 × 4 + 4 × 4) =0.16，而切割II的稀疏度为(2 + 1 + 1) / (4 × 4 + 5 × 3) =0.13。因此，II是一个更稀疏的切割。0定义1. 最稀疏时间切割。对于常数 β，时间图 G的最稀疏切割定义如下：0最稀疏时间切割是最稀疏切割问题的推广，因此也是NP难的[18]。多重模型的一个有趣特性是，在 G 中的时间切割变成了多重视图 χ ( G)中的标准（单一图形）切割。我们可以通过将原始公式（表达式2）应用于 χ ( G ) 来评估 G 中切割的稀疏度，因为在 χ ( G )中，既有边缘切割，又有分区变化。例如，我们在图2c中展示了切割II的多重视图。然而，请注意，并不是 χ ( G )中的每个标准切割都是有效的时间切割。例如，在标准公式中，切割所有时间边缘（即分离我们的示例中的两个快照）是允许的，但会导致稀疏度的未定义值，因为表达式3中的分母将为0。因此，我们不能直接将现有的最稀疏切割算法应用于 χ ( G ) ，并期望为 G实现稀疏的时间切割。时间切割与多重网络之间的联系是我们制定这个公式的主要动机之一。此外，方程3足够通用，可以捕捉到不同的动态行为，这取决于常数 β。具体而言，如果 β → ∞，则稀疏度 σ将在快照上的常数切割上最小化。另一方面，如果 β → 0，σ近似于单个快照切割的稀疏度。有趣的是，这两个极端情况在动态图上的随机游走的背景下已经得到了研究[13]。02.1.2 归一化切割。方程 2的一个限制是它更偏向于稀疏性而不是分区大小的平衡。在社区检测中，这经常导致“胡须社区” [ 28 , 32 ]。归一化切割 [ 40 ]考虑了分区的“体积”（即顶点度的总和），对这种效应不太敏感。切割稀疏性的归一化版本定义为：0其中 vol ( Y ) = � v ∈ Y deд ( v ) 且 deд ( v ) 是顶点 v的度。我们还将归一化稀疏度 ϕ 推广到时间图：0接下来，我们定义时间图的归一化切割问题。0定义 2. 归一化时间切割。对于常数 β ，图 G的归一化时间切割定义为：0计算最优的归一化时间切割也是 NP难的。下一节介绍了用于时间切割的谱方法。02.2 谱方法0与单个图的情况类似，我们还利用谱图理论来计算良好的时间图切割。设 A 是图 G ( V , E ) 的一个 n × n 加权邻接矩阵，其中 A u , v= W ( u , v ) if ( u , v ) ∈ E 或者 0，否则。度矩阵 D 是一个 n× n 对角矩阵，其中 D v , v = deд ( v ) ，对于 u � v ，D u , v =0。图 G 的拉普拉斯矩阵定义为 L = D − A。设 G t的图快照的拉普拉斯矩阵为 L t ，I z 是一个 z × z的单位矩阵。我们将时间图 G 的拉普拉斯定义为其多重视图 χ ( G )的拉普拉斯矩阵：0矩阵 L 还可以用克罗内克积的形式更紧凑地表示为 diag ( L 1 , . . . Lm ) + β ( L ℓ � I n ) ，其中 L ℓ是线图的拉普拉斯矩阵。类似地，我们定义 G 的度矩阵 D 为 diag (D 1 , D 2 . . . D m ) ，其中 D t 是 G t 的度矩阵。令 C = nI n −1 n × n 为具有 n 个顶点的团的拉普拉斯矩阵。我们定义另一个 nm× nm 的拉普拉斯矩阵 C = I m � C ，它是由 m个孤立团组成的图的拉普拉斯矩阵。这个矩阵将被用于强制执行 G的快照上的有效时间切割。此外，我们定义一个大小为 nm的指示向量 x ，其中每个顶点 v ∈ V 表示 m次，每个快照一次。如果 v t ∈ X t ，则 x [ v t ] = 1，如果 v t ∈ X t ，则 x [ v t ] = − 1。02.2.1 最稀疏切割。下面的引理展示了矩阵 L 和 C如何应用于计算时间切割的稀疏度。0引理 2.1. 时间切割的稀疏度 σ 等于 x � L x0证明。由于 L 是 χ ( G ) 的拉普拉斯矩阵：0m0m− 1x⊺Cx =(x[vt ] − x[ut ])2= 4|Xt ||Xt |5220关于分母：0m0m0□0根据引理2.1，我们可以通过广义特征值计算[16]在O(n^3m^3)的时间内获得稀疏时间割问题（定义1）的松弛解x ∈ [-1,1]nm，或者通过快速拉普拉斯线性系统求解器[24, 45]在O(n^2mlog2(n^2m))的时间内获得近似解。解决方案后来被舍入以符合原始（离散）约束x ∈ {-1,1}nm。下一个引理支持我们的松弛解的更高效解决方案。0引理2.2。矩阵C和L是可交换的。0证明。首先，我们证明C与任何Laplacian Lt可交换：0CLt = (nIn - 1n×n)Lt = nLt = LtC0使用Kronecker乘积符号（见第2.2节）：0CL = (Im � C)[diag(L1, ..., Lm) - β(Lℓ � In)]0= diag(CL1, ..., CLm) - β(ImLℓ) � (CI n)0= diag(L1C, ..., LmC) - β(LℓIm) � (InC)0= LC0□0可以基于矩阵C和L的线性组合计算稀疏时间割的松弛解。0定理1。可以通过以下两种方式计算稀疏时间割问题的松弛解：0y* = arg max y ∈ [-1, 1]2β)C - L] y0y � y (6)0即3(n + 2β)C - L的最大特征向量。0证明。C的谱的形式为(e1, λ1) = (1/n, 0)，λ2 = ... = λn = n，其中ei⊥ 1n。因此，C的谱的形式为λ1 = ... = λm = 0，λm + 1 = ... λnm= n，其中ei ⊥ span {e1, ...,em}。引理2.2暗示了C和L的任意线性组合具有与L相同的特征向量[20]。通过上界估计拉普拉斯矩阵的特征值[1]：00 ≤ y0y � y ≤ 2(n + 2β) (7)0这意味着：0(y*) � C (y*) (y*) � (y*) = n (8)0因为它保证了方程6中的严格正比率（即特征值）。根据方程8，我们可以将y*重新写为：0y* = arg min y ∈ [-1, 1]nm, y� Cy > 00y � Lx y � y (9)0此外，根据引理2.1：0x* = arg min x ∈ [-1, 1]nm, x� Cx > 00x � Lx x � Cx (10)0方程9和10分别与特征值问题和广义特征值问题相关，并可以写成如下形式：0Ly = λy, Lx = λ'Cx (11)0其中λ和λ'被最小化，y � Cy，x � Cx > 0。根据方程8，我们知道Cy =ny。因此，Ly =(λ/n)Cy是广义问题的相应解（相同的特征向量）。□0矩阵3（n + 2β）C -L是一个多重图的拉普拉斯矩阵，其中时间边的权重为w'(vt, vt+1) =-β，层内边的权重为w'(u, v) = 3(n + 2β) - w(u,v)。这导致了L的谱重新排序，其中仅包含时间边的割具有负相关的特征值，而每个Laplacian L_t的稀疏割变为新Laplacian [3(n +2β))C - L_t]的密集割。在复杂度方面，计算差异3(n + 2β)C -L需要O(n^2m)的时间，而[3(n + 2β)C -L]的最大特征向量可以在O(n^2m)内计算。与标准的O(n^3m^3)替代方案相比，这种结果的复杂度显著提高，特别是如果快照的数量很大。02.2.2归一化割。我们按照前一节的步骤计算归一化时间割。有关引理2.3和定理2的证明，请参见本文的扩展版本[43]。0引理2.3. 时态割的归一化稀疏度ϕ等于x�Lx0x�D^(1/2)CD0我们还为归一化割定义了定理1的等价形式。0定理2. 最稀疏时态割问题的松弛解可以用以下方式计算：0y* = arg max y ∈ [-1, 1] nm y�(D+)^(1/2)L(D+)^(1/2)]y0y�y (12)03(n+2β)C - (D+)^(1/2)L(D+)^(1/2)的最大特征向量。0矩阵3(n+2β)C -(D+)^(1/2)L(D+)^(1/2)的解释与最稀疏割的解释类似，其中时态边具有负权重。此外，计算这种矩阵的最大特征向量的复杂度也是O(n^2m)。对于较小的图来说，这种与图的规模的二次复杂度对于最稀疏割和归一化割问题来说是不可行的。下一节将专注于时态图割的更快算法。02.3 快速近似0根据定义，稀疏时态割在每个快照中都是稀疏的，并且在快照之间是平滑的。类似地，归一化时态割由一系列稳定的归一化快照割组成。这激发了计算时态割的分治方法，首先在每个快照上找到一个好的割（分割），然后将它们组合起来（征服）。如果征服步骤很快，这些解决方案的效率可能比基于定理1和定理2的解决方案高得多。然而，它们可能导致次优结果，因为最优时态割可能不是由每个快照的最佳割组成的。相反，更好的分割和征服方案可以在征服步骤中探索多个快照割。由于我们在谱域中工作，自然地采用M S =3(n+2β)C - L和M N = 3(n+2β)C -(D+)^(1/2)L(D+)^(1/2)的块的特征向量作为快照割的连续概念。这个策略得到了Laplacian矩阵的高阶特征向量与多路割的稀疏性之间的众所周知的联系的支持[30,35]。本节将描述我们的一般分割和征服方法。我们将重点讨论最稀疏割问题，然后简要介绍如何将其推广到归一化割。以下定理是我们算法的基础。0Track: Social Network Analysis and Graph Algorithms for the Web WWW 2018, April 23-27, 2018, Lyon, Franceconquer step to avoid local optima. Since we are working in thespectral domain, it is natural to take eigenvectors of blocks ofMS = 3(n + 2β)C − L and MN = 3(n + 2β)C − (D+)12 L(D+)12 ,as continuous notions of snapshot cuts. This strategy is supportedby the well-known connections between higher-order eigenvectorsof the Laplacian matrix and the sparsity of multiway cuts [30, 35].This section will describe our general divide-and-conquer ap-proach. We will focus our discussion on the sparsest cut problemand then briefly show how it can be generalized to normalized cuts.The following theorem is the basis of our algorithm.Algorithm 1 describes our divide-and-conquer approach for ap-proximating the sparsest temporal cut. Its inputs are the temporalgraph G, the rank r that controls the accuracy of the algorithm,and a constant β. It returns a cut ⟨(X1,X 1) . . . (Xm,Xm)⟩ that (ap-proximately) minimizes the sparsity ratio defined in Equation 3. Inthe divide phase, the top-r eigenvalues/eigenvectors of each matrixMt —related to the bottom-r eigenvalues/eigenvectors of Lt —arecomputed using Lemma 2.4 (steps 1-4). The conquer phase (steps5-9) consists of building the matrix Q—based on the blocks Qt,t+1adjacent to the diagonal—and then computing its largest eigenvec-tor as a relaxed version of a temporal cut. The resulting eigenvectoris discretized using a standard sweep algorithm (sweep) over thevertices sorted by their corresponding value of x*. The selectioncriteria for the sweep algorithm is the sparsity ratio (Equation 3).The time complexity of our algorithm is O(mr �mt=1 |Et | +mr3).The divide step has cost O(mr �mt=1 |Et |), which corresponds tothe computation of r eigenvectors/eigenvalues of matrices Lt withO(|Et |) non-zeros each. As snapshots are processed independently,this part of the algorithm can be easily parallelized. In the conquerstep, the most time consuming operation is computing m − 1 r × rmatrix products in the construction of Q, which takes O(r3m) time.Our algorithm has space complexity of O(r2m) due to the numberof non-zeros in the sparse representation of Q.We follow the same general approach discussed in this sectionto efficiently compute normalized temporal cuts. As in Theorem3, we can compute the eigenvectors of MN using divide-and-conquer. However, each block Mt will be in the form 3(n − 2β)C −+12+12 . Moreover, similar to Lemma 2.4, we can also com-5230定理3. 矩阵MS = 3(n+2β)C - L的特征值与矩阵Q的特征值相同：0Q = Λ - βI0I n - U�1U2 0 ... 0 - U�2U1 2 I n - U�2U3 ... 0 ... ... U�m-1Um ..U�mUm-1 I n0I0其中UtΛtU�t是Mt = (3(n+2β)C - Lt)的特征分解，Λ = diag(Λ1, ...,Λm)。M S的特征向量e j 可以计算为U.e Q j，其中U = diag(U1, ...,Um)，e Q j是Q的特征向量。0证明。我们证明M S和Q在基变换U�下是相似矩阵，因此M =(U�)^-1QU�。我们定义矩阵B = β(Lℓ�In)和M t = 3(n-2β)C -Lt。因为Lt是对称的，U^-1 =U�。对于一个特征向量矩阵U，UU�是一个nm×nm的单位矩阵I。我们将M S 重新写为：0MS = diag(M1, M2, ..., Mm) - B0= UΛU� - IBI0= UΛU� - UU�BUU�0= U(Λ - U�BU)U�0= (U�)^-1QU�0□0Q具有O(n^2m)个非零元素，渐进地与MS一样稀疏。然而，可以使用矩阵Mt的低秩近似对Q进行分块稀疏化。给定一个常数r≤n，我们将每个Mt近似为UtΛ′tU�t，其中Λ′i只包含Mt的前r个特征值。这种策略的好处如下：（1）计算Mt的特征分解的成本从O(n^3)降低到O(rn^2)；（2）特征向量矩阵的乘法成本从O(n^3)降低到O(r^3)；（3）Q中的非零元素数量从O(n^2m)减少到O(r^2m)。类似于一般的分块三对角矩阵的情况[14]，我们可以证明这种近似的误差被2λmax(r+1)所限制，其中λmax(r+1)是近似矩阵Mt的最大（r+1）-th特征值。我们通过加速矩阵Mt的特征分解来改进我们的方法。这个想法是在原始的LaplaciansLt上操作，这些Laplacians预计是稀疏的。具有|E|个非零元素的矩阵的特征分解可以在O(n|E|)的时间内完成，对于现实世界的图，|E|< 0。0证明。C的谱是(e 1，λ 1) = (1 n，0)和λ 2 = ... = λ n =n，对于任何与1 n ⊥的向量e i。由于M i也是Laplacian，因此得出λ1 = 0和e 1 = e L 1。另外，根据定义L . e L i = λ L i . e Li，因此（3(n + 2β)C - L）e L i = (3(n + 2β)n - λ i) e L i，对于i >0。□0基于(D + t) 1 2 L t (D + t) 1 2计算M t 的特征分解。02.4近似保证02.2节和2.3节中介绍的算法是基于松弛时序切割问题的特征向量计算。一个自然的问题是：它们是否提供了与问题的最优解的近似保证？请注意，对于前一节讨论的快速解决方案，算法1考虑的前r个特征值（r）给出了0跟踪：社交网络分析和Web WWW 2018的图算法，2018年4月23日至27日，法国里昂(13)5240对于近似的质量具有一定的控制。因此，我们专注于限制由引理2.1和2.3以及定理1和2描述的松弛和误差。我们的分析主要基于最近的Cheeger不等式[10，23]的一个推广，它将两个具有相同顶点集的图G和H上相同割的权重比与它们的拉普拉斯矩阵LG和LH之间的广义特征值联系起来。这个推广是证明下面关于我们稀疏时间割问题（定义1）的谱算法的引理的主要要素：0引理2.5。我们的松弛方法实现的时间稀疏比λ(G)满足：0λ(G) ≥ φ(χ(G)) min(σX1,...Xm(X1,...Xm; β))0x�Cx和φ(χ(G))是G的多重视图的（标准）传导率。0引理2.5直接来自[23，定理1]，将G设置为我们的时间图G，H设置为具有拉普拉斯矩阵C的团序列，因此省略了证明。类似于经典的Cheeger不等式[9]，其广义版本的证明也是构造性的，我们解决方案应用的舍入算法达到了这个界限。我们可以这样解释引理2.5。如果时间图G的稀疏度割比其多重视图χ(G)的传导率低，那么我们的松弛方法将找到一个好的近似（可能不同的）时间割。对于归一化的时间割（定义2），也存在类似的界限。02.5泛化0这里，我们简要介绍了几种增加这项工作适用性的时间割的泛化。任意交换成本：虽然我们假设交换成本β是均匀的，但将我们的公式推广到对于成对顶点(vt,vt+1)的任意（非负）交换成本是很容易的。多个割：可以基于我们的时间割矩阵的前k个特征向量来计算多个割，就像[40]中提出的那样。我们使用k-means来获得k路划分。03图上的信号处理0我们将图割应用于动态信号的数据驱动小波基。给定一个时间图G上的信号序列�f(1),...,f(m)�，其中f(i)∈Rn，我们的目标是发现一个稀疏、平滑且将具有不同信号值的顶点分开的时间割。先前的工作[42]已经证明了对于单个图快照的小波系数a的L2能量（或重要性）||a||2可以计算为：0(|X| ∑v∈X f[v] - |0|X||X| ∝ - x�CSCx0x�Cx (14)0其中x是一个指示向量，S u,v = (f[v] -f[u])^2。通过在方程14的分母上添加拉普拉斯正则化因子αx�Lx来实现稀疏性。这个公式支持计算图波尔兹的算法，我们将其扩展到动态信号。按照2.1节的方法，我们将多重图表示应用于计算动态小波系数的能量：0∑m t=1 Θ2t + ∑m-1 t=1 ΘtΘt+10在式(15)中，m t = 1 | X t || X t |0其中Θt = |Xt| ∑v∈Xt f[v] - |Xt| ∑u∈Xtf[u]。方程15的分子的第一项是对所有快照的方程14的分子求和。第二项作用于连续的快照，并强制分区在时间上保持一致，即Xt与大值或小值关联。直观上，能量在将不同值分开且大小平衡的分区中达到最大。下一个定理提供了动态小波能量的谱形式。0定理4. 动态小波的能量与 − x � CSC x 成正比0x � C x ，其中 S u , v = ( f [ u ] − f [ v ] ) 2，对于彼此相邻的两个快照中的值。0我们应用定理4（见[43]中的证明）来计算最优动态小波的一个松弛问题：0x � = arg min nm x � CSC x0x � C x + α x � L x (16)0其中 C 和 L是在第2.1节中定义的矩阵。可以应用[42]中讨论的优化方法来高效地近似方程16。得到的算法的复杂度为 O ( pn � t | E t | + qn 2 m 2 )，其中 p 和 q 是小常数。类似于算法1，我们应用扫描过程来获得从x � 得到的切割。04 实验 4.1 特征向量计算0我们应用Lanczos方法[16，25]来实现本文中讨论的算法1。然而，我们的算法也可以使用文献中的其他特征求解器来实现。04.2 数据集0School是一个联系网络，其中顶点代表小学的孩子，边是基于传感器检测到的接近性创建的[47]，具有242
我的内容管理
展开
