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.

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.

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.

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.

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.

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.

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.

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)

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

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

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

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

二部图性质的谱刻画

为了刻画二部图的性质,研究了图的邻接矩阵、邻接特征多项式、线图、关联矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵等。用图的谱性质刻画了二部图的特征,并得到了以下结论:二部图G的奇数阶谱矩为0,邻接谱在实数轴上关于原点对称,–2是线图l(G)的重数为m−n+1的特征值,拉普拉斯矩阵和无符号拉普拉斯矩阵有相同的谱,最小无符号拉普拉斯特征值等于0,最大拉普拉斯特征值等于最大无符号拉普拉斯特征值。

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

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

基于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矩阵的谱性质,并着重讨论了单圈图的代数连通度。