Graph Laplacian Matrix Learning from Smooth Time-Vertex Signal

In this paper,we focus on inferring graph Laplacian matrix from the spatiotemporal signal which is defined as“time-vertex signal”.To realize this,we first represent the signals on a joint graph which is the Cartesian product graph of the time-and vertex-graphs.By assuming the signals follow a Gaussian prior distribution on the joint graph,a meaningful representation that promotes the smoothness property of the joint graph signal is derived.Furthermore,by decoupling the joint graph,the graph learning framework is formulated as a joint optimization problem which includes signal denoising,timeand vertex-graphs learning together.Specifically,two algorithms are proposed to solve the optimization problem,where the discrete second-order difference operator with reversed sign(DSODO)in the time domain is used as the time-graph Laplacian operator to recover the signal and infer a vertex-graph in the first algorithm,and the time-graph,as well as the vertex-graph,is estimated by the other algorithm.Experiments on both synthetic and real-world datasets demonstrate that the proposed algorithms can effectively infer meaningful time-and vertex-graphs from noisy and incomplete data.

Lateral interaction by Laplacian‐based graph smoothing for deep neural networks

Lateral interaction in the biological brain is a key mechanism that underlies higher cognitive functions.Linear self‐organising map(SOM)introduces lateral interaction in a general form in which signals of any modality can be used.Some approaches directly incorporate SOM learning rules into neural networks,but incur complex operations and poor extendibility.The efficient way to implement lateral interaction in deep neural networks is not well established.The use of Laplacian Matrix‐based Smoothing(LS)regularisation is proposed for implementing lateral interaction in a concise form.The authors’derivation and experiments show that lateral interaction implemented by SOM model is a special case of LS‐regulated k‐means,and they both show the topology‐preserving capability.The authors also verify that LS‐regularisation can be used in conjunction with the end‐to‐end training paradigm in deep auto‐encoders.Additionally,the benefits of LS‐regularisation in relaxing the requirement of parameter initialisation in various models and improving the classification performance of prototype classifiers are evaluated.Furthermore,the topologically ordered structure introduced by LS‐regularisation in feature extractor can improve the generalisation performance on classification tasks.Overall,LS‐regularisation is an effective and efficient way to implement lateral interaction and can be easily extended to different models.

A CASCADIC MULTIGRID ALGORITHM FOR COMPUTING THE FIEDLER VECTOR OF GRAPH LAPLACIANS

In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalne. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.

Distributed coordination in multi-agent systems： a graph Laplacian perspective

本综述从图拉普拉斯视角回顾多智能体系统分布式协调控制中的主要成果和进展。在过去几十年,多智能体分布式协调控制被系统与控制领域视为十分具有吸引力的一个课题。利用多智能体分布式协调控制可以解决分布式一致性控制、编队控制、传感器定位、分布式最优化等问题。除回顾广泛的多智能体分布式协调控制文献外,本文还提供一个全新的角度,即图拉普拉斯,对众多的分布式协调控制基于基本机制进行分类。对于不同类型的图拉普拉斯,分别总结其内在协调特性以及相应的研究课题。文章最后着重介绍具有发展前景的研究方向以及对未来有重大研究意义的开放性问题。

Some notes on the spectral perturbations of the signless Laplacian of a graph

Let G be a simple graph and let Q（G） be the signless Laplacian matrix of G. In this paper we obtain some results on the spectral perturbation of the matrix Q（G） under an edge addition or an edge contraction.

Sharp upper bounds for the adjacency and the signless Laplacian spectral radius of graphs

Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has at least one common adjacent vertex. Our results improve some known upper bounds. The main tool we use here is the Lagrange identity.

Signless Laplacian Characteristic Polynomials of Complete Multipartite Graphs

For a simple graph G,let matrix Q(G)=D(G) + A(G) be it's signless Laplacian matrix and Q G (λ)=det(λI Q) it's signless Laplacian characteristic polynomial,where D(G) denotes the diagonal matrix of vertex degrees of G,A(G) denotes its adjacency matrix of G.If all eigenvalues of Q G (λ) are integral,then the graph G is called Q-integral.In this paper,we obtain that the signless Laplacian characteristic polynomials of the complete multi-partite graphs G=K(n_1,n_2,···,n_t).We prove that the complete t-partite graphs K(n,n,···,n)t are Q-integral and give a necessary and sufficient condition for the complete multipartite graphs K(m,···,m)s(n,···,n)t to be Q-integral.We also obtain that the signless Laplacian characteristic polynomials of the complete multipartite graphs K(m,···,m,)s1(n,···,n,)s2(l,···,l)s3.

ON GRAPHS WITH THREE DISTINCT LAPLACIAN EIGENVALUES

In this paper, an equivalent condition of a graph G with t （2≤ t ≤n） distinct Laplacian eigenvalues is established. By applying this condition to t = 3, if G is regular （necessarily be strongly regular）, an equivalent condition of G being Laplacian integral is given. Also for the case of t = 3, if G is non-regular, it is found that G has diameter 2 and girth at most 5 if G is not a tree. Graph G is characterized in the case of its being triangle-free, bipartite and pentagon-free. In both cases, G is Laplacian integral.

Laplacian Energies of Regular Graph Transformations

Let LE(G) denote the Laplacian energy of a graph G. In this paper the xyz-transformations G^(xyz) of an r-regular graph G for x,y,z∈{0,1, +,-} are considered. The explicit formulas of LE(G^(xyz)) are presented in terms of r,the number of vertices of G for any positive integer r and x,y,z∈{ 0,1},and also for r = 2 and all x,y,z∈{0,1,+,-}. Some Laplacian equienergetic pairs of G^(xyz) for r = 2 and x,y,z∈{0,1, +,-} are obtained. This also provides several ways to construct infinitely many pairs of Laplacian equienergetic graphs.

On the Signless Laplacian Spectral Radius of C4-free k-cyclic Graphs

A k-cyclic graph is a connected graph of order n and size n + k-1. In this paper, we determine the maximal signless Laplacian spectral radius and the corresponding extremal graph among all C_4-free k-cyclic graphs of order n. Furthermore, we determine the first three unicycles and bicyclic, C_4-free graphs whose spectral radius of the signless Laplacian is maximal. Similar results are obtained for the(combinatorial)

The Signless Laplacian Spectral Radius of Some Special Bipartite Graphs

This paper mainly researches on the signless laplacian spectral radius of bipartite graphs Dr(m1,m2;n1,n2). We consider how the signless laplacian spectral radius of Dr(m1,m2;n1,n2)?changes under some special cases. As application, we give two upper bounds on the signless laplacian spectral radius of Dr(m1,m2;n1,n2), and determine the graphs that obtain the upper bounds.

基于图拉普拉斯正则化的PET图像核重建方法

正电子发射断层成像(Positron Emission Tomography,PET)在很多疾病的早期诊断中有重要的作用,PET图像重建的难点之一是如何在保持重建图像中病灶边缘特性的同时具有良好的去噪性能.针对此问题,本文提出了一种结合图拉普拉斯正则化和深度图像先验的PET图像核重建方法 .设计了改进的U-net神经网络,将PET前向投影模型中的核系数表示为神经网络的输出;通过先验图像构建图拉普拉斯矩阵,重建问题被建模为基于神经网络的带图拉普拉斯正则化项的最大似然函数优化问题.利用优化转移方法导出了收敛的迭代重建算法,每一次迭代包括由核重建方法更新图像和利用神经网络更新核系数两个步骤.仿真和临床实验结果表明,本文提出的方法在不同的指标下都有更好的重建效果,优于已有核重建方法以及最新的基于深度系数先验的重建方法 .

非平衡符号双圈图的拉普拉斯谱半径的排序

研究了非平衡符号双圈图的第一到第六大的拉普拉斯特征值的分布规律,完善了现有结论中一些不准确的情况,推广了现有的结果,并给出了取得极值情况的图例。

采用多任务特征融合的脑电情绪识别方法

特征选择与融合是提升脑电信号情绪解码精度的重要手段之一。然而,当前脑电情绪解码中的特征选择方法常忽略了脑电信号内在数据结构的隐含信息。该文提出一种基于近邻传播聚类的多任务特征融合方法,通过L_(2,1)范数约束实现稀疏特征选择,同时利用图拉普拉斯正则化保持不同子类间的潜在关系。该算法在不揭示真实样本标签的情况下,在子任务空间有效融合脑网络空间拓扑结构信息和微分熵信息,为高精度脑电信号情绪解码提供具有更高情绪表征能力的特征。DEAP和SEED数据集以及本实验室数据集的分析结果表明,该文提出的方法能显著提高脑电情绪解码的精度。

一些由它的Laplacian谱确定的树

探讨了“哪些图由它的Laplacian谱确定?”的问题.利用同谱图的线图的特点,证明了一些特殊结构的树,如梳图,烷的一个同分异构体的分子图,恰有两个Laplacian特征值大于2的树(包括双星图)等,各自由它们的Laplacian谱确定.

单圈图的Laplacian谱(英文)

G是一个图,A(G),D(G)分别是G的邻接矩阵和顶点度序列对角矩阵,则矩阵L(G)=D(G)-A(G)称为G的Laplacian矩阵。作者考察了单圈图的Laplacian矩阵的谱性质,并着重讨论了单圈图的代数连通度。

稀疏分解和图拉普拉斯正则化的图像前景背景分割方法

针对现有图像前景背景分割方法的分割结果存在孤立像素点的问题,利用图信号处理理论和稀疏分解模型,提出新的图像前景背景分割方法.将图像的内在结构建模为图,通过图模型有效地刻画像素之间的内在关联性.将图像的像素强度建模为图信号,其中图像背景作为平滑分量,由一组图傅里叶变换基函数线性表示,叠加在背景上的前景为稀疏分量,前景像素间的连通性可由图拉普拉斯正则化项进行刻画.将图像前景背景分割问题归结为包含稀疏分解模型和图拉普拉斯正则化项的约束优化问题,采用交替方向乘子法对该优化问题进行求解.实验结果表明,与现有的其他方法相比,所提方法具有更好的分割效果.

图Laplacian半监督特征加权用于高光谱波段选择

提出一种利用图Laplacian实现半监督波段选择的方法.该方法首先将标记样本类别信息引入图Laplacian,接着通过广义特征值求解确定投影变换矩阵,最后采用载荷因子对变换矩阵进行系数分析,对波段重要性赋以权值并排序.实验比较了多种波段选择算法,结果表明算法能更好地利用标记样本的类别信息和大量非标记样本中的局部结构信息,性能优于多种波段选择方法.

给定阶与边独立数的树和单圈图的Laplacian矩阵的最大特征值

得到了给定顶点数和边独立数的树与单圈图的Laplacian矩阵的最大特征值的精确上界 。

基于Laplacian中心性的密度聚类算法

聚类分析是一种重要的数据挖掘工具,可以衡量不同数据之间的相似性,并把它们分到不同的类别中,在模式识别、经济学和生物学等领域有着广泛的应用。文中提出了一种新的聚类算法。首先,把待分类的数据集转换成一个加权的完全图,每个数据点为一个节点,两个数据点之间的距离为相应两个节点之间边的权值。然后,用Laplacian中心性来计算和评价该网络每个节点的局部重要性,聚类中心为局部的密度中心,它具有比周围的邻居节点更高的Laplacian中心性,并且与具有更高Laplacian中心性的节点之间的距离也较大。新算法是一种真正的无参数聚类方法,不需要任何先验参数便可以自动地对数据集进行分类。在6种数据集中将其与9种知名聚类算法做了对比,结果显示该算法具有良好的聚类效果。