Upper Bounds for the Laplacian Graph Eigenvalues

We first apply non-negative matrix theory to the matrix K=D+A,where D and A are the degree-diagonal and adjacency matrices of a graph G,respectively,to establish a relation on the largest Laplacian eigenvalue λ_1(G)of G and the spectral radius ρ(K)of K.And then by using this relation we present two upper bounds for λ_1(G)and determine the extremal graphs which achieve the upper bounds.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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)

基于Laplacian图谱的短文本聚类算法

提出基于词频处理的Laplacian图谱聚类算法,以解决短文本数据维数高、特征稀疏等问题.首先采用词频-逆文本频率指数TF-IDF(Term Frequency-Inverse Document Frequency)方法,将短文本数据集映射到文本向量空间得到词频权值矩阵;其次利用Laplacian矩阵的图谱聚类特性,对词频权值矩阵进行数据降维处理;然后依据Laplacian矩阵的特征值表示文本相似度的特点,选择前K个特征值对应的特征向量作为初始聚类中心,以减少聚类过程的迭代次数.在SSC、20 News Group及Microblog PCU数据集上进行相关实验,结果表明Laplacian图谱聚类算法比传统聚类算法,不仅具有更优的聚类结果与更快的收敛速度,而且受噪声点影响较小,有很好的鲁棒性.

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

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

一些由它的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矩阵特征值之间的本征间隙自适应确定聚类数目,并结合K-means聚类方法实现模型的自动结构识别与分割.实验结果表明,在同一类模型的结构特征提取与统一分割应用中,该方法是高效、鲁棒的,对于实现模型的高层次语义描述、模型配准以及模型检索具有重要的意义.

图的Laplacian谱半径界的可达性

设G为n阶连通的简单图 ,ρ(G)为图G的邻接谱半径 ,μ(G)表示G的Laplacian谱半径。(d1,d2 ,… ,dn) (其中d1≥d2 ≥…≥dn)为G的顶点度序列 ,令r=max{d(u) +d(v) ｜ (u ,v) ∈E(G) } =d(x) +d(y) ,s=max{d(u) +d(v)｜ (u ,v) ∈E(G) - (x ,y) }。该文证明了μ(G)上下界的可达性 :μ(G) =μ≤ 2 + ρ(LG) ,等式成立当且仅当G是偶图。μ(G)≤ 2 + (r- 2 ) (s- 2 ) ,成立等式当且仅当G为半正则偶图或P4 。μ(G)≥d1+ 1,成立等式当且仅当d1=n- 1。

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

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