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.

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

This paper reviews some main results and progress in distributed multi-agent coordination from a graph Laplacian perspective. Distributed multi-agent coordination has been a very active subject studied extensively by the systems and control community in last decades, including distributed consensus, formation control, sensor localization, distributed optimization, etc. The aim of this paper is to provide both a comprehensive survey of existing literature in distributed multi-agent coordination and a new perspective in terms of graph Laplacian to categorize the fundamental mechanisms for distributed coordination. For different types of graph Laplacians, we summarize their inherent coordination features and specific research issues. This paper also highlights several promising research directions along with some open problems that are deemed important for future study.

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.

Model Change Active Learning in Graph-Based Semi-supervised Learning

Active learning in semi-supervised classification involves introducing additional labels for unlabelled data to improve the accuracy of the underlying classifier.A challenge is to identify which points to label to best improve performance while limiting the number of new labels."Model Change"active learning quantifies the resulting change incurred in the classifier by introducing the additional label(s).We pair this idea with graph-based semi-supervised learning(SSL)methods,that use the spectrum of the graph Laplacian matrix,which can be truncated to avoid prohibitively large computational and storage costs.We consider a family of convex loss functions for which the acquisition function can be efficiently approximated using the Laplace approximation of the posterior distribution.We show a variety of multiclass examples that illustrate improved performance over prior state-of-art.

Bipartite Graphs with the First and Second Largest Laplacian Spectral Radius

Let Bn^k be the class of bipartite graphs with n vertices and k cut edges. The extremal graphs with the first and the second largest Laplacian spectral radius among all graphs in Bn^K are presented. The bounds of the Laplacian spectral radius of these extremal graphs are also obtained.

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.

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.

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.

一些由它的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种知名聚类算法做了对比,结果显示该算法具有良好的聚类效果。

合成图的Laplacian特征值(英文)

给出了任意两个图的合成图的Laplacian特征值和特征向量 ,同时得到了合成图的生成树的数目 .

由Laplacian谱确定的单圈图

利用同Laplacian谱图的线图及有相同生成树数目的特点证明了2类特殊的单圈图,即C(n2,2n)(n=4k,kN)和C(r,n-r+1)(nN),由它们的Laplacian谱确定.