Cold-Start Link Prediction via Weighted Symmetric Nonnegative Matrix Factorization with Graph Regularization

Link prediction has attracted wide attention among interdisciplinaryresearchers as an important issue in complex network. It aims to predict the missing links in current networks and new links that will appear in future networks.Despite the presence of missing links in the target network of link prediction studies, the network it processes remains macroscopically as a large connectedgraph. However, the complexity of the real world makes the complex networksabstracted from real systems often contain many isolated nodes. This phenomenon leads to existing link prediction methods not to efficiently implement the prediction of missing edges on isolated nodes. Therefore, the cold-start linkprediction is favored as one of the most valuable subproblems of traditional linkprediction. However, due to the loss of many links in the observation network, thetopological information available for completing the link prediction task is extremely scarce. This presents a severe challenge for the study of cold-start link prediction. Therefore, how to mine and fuse more available non-topologicalinformation from observed network becomes the key point to solve the problemof cold-start link prediction. In this paper, we propose a framework for solving thecold-start link prediction problem, a joint-weighted symmetric nonnegative matrixfactorization model fusing graph regularization information, based on low-rankapproximation algorithms in the field of machine learning. First, the nonlinear features in high-dimensional space of node attributes are captured by the designedgraph regularization term. Second, using a weighted matrix, we associate the attribute similarity and first order structure information of nodes and constrain eachother. Finally, a unified framework for implementing cold-start link prediction isconstructed by using a symmetric nonnegative matrix factorization model to integrate the multiple information extracted together. Extensive experimental validationon five real networks with attributes shows that the proposed model has very goodpredictive performance when predicting missing edges of isolated nodes.

Improved Non-negative Matrix Factorization Algorithm for Sparse Graph Regularization

Aiming at the low recognition accuracy of non-negative matrix factorization(NMF)in practical application,an improved spare graph NMF(New-SGNMF)is proposed in this paper.New-SGNMF makes full use of the inherent geometric structure of image data to optimize the basis matrix in two steps.A threshold value s was first set to judge the threshold value of the decomposed base matrix to filter the redundant information in the data.Using L2 norm,sparse constraints were then implemented on the basis matrix,and integrated into the objective function to obtain the objective function of New-SGNMF.In addition,the derivation process of the algorithm and the convergence analysis of the algorithm were given.The experimental results on COIL20,PIE-pose09 and YaleB database show that compared with K-means,PCA,NMF and other algorithms,the proposed algorithm has higher accuracy and normalized mutual information.

Two-level Bregmanized method for image interpolation with graph regularized sparse coding

A two-level Bregmanized method with graph regularized sparse coding （TBGSC） is presented for image interpolation. The outer-level Bregman iterative procedure enforces the observation data constraints, while the inner-level Bregmanized method devotes to dictionary updating and sparse represention of small overlapping image patches. The introduced constraint of graph regularized sparse coding can capture local image features effectively, and consequently enables accurate reconstruction from highly undersampled partial data. Furthermore, modified sparse coding and simple dictionary updating applied in the inner minimization make the proposed algorithm converge within a relatively small number of iterations. Experimental results demonstrate that the proposed algorithm can effectively reconstruct images and it outperforms the current state-of-the-art approaches in terms of visual comparisons and quantitative measures.

Signed total domination in nearly regular graphs

A function f： V（ G）→{1,1} defined on the vertices of a graph G is a signed total dominating function （STDF） if the sum of its function values over any open neighborhood is at least one. An STDF f is minimal if there does not extst a STDF g： V（G）→{-1,1}, f≠g, for which g （ v ）≤f（ v ） for every v∈V（ G ）. The weight of a STDF is the sum of its function values over all vertices. The signed total domination number of G is the minimum weight of a STDF of G, while the upper signed domination number of G is the maximum weight of a minimal STDF of G, In this paper, we present sharp upper bounds on the upper signed total domination number of a nearly regular graph.

Extracting Sub-Networks from Brain Functional Network Using Graph Regularized Nonnegative Matrix Factorization

Currently,functional connectomes constructed from neuroimaging data have emerged as a powerful tool in identifying brain disorders.If one brain disease just manifests as some cognitive dysfunction,it means that the disease may affect some local connectivity in the brain functional network.That is,there are functional abnormalities in the sub-network.Therefore,it is crucial to accurately identify them in pathological diagnosis.To solve these problems,we proposed a sub-network extraction method based on graph regularization nonnegative matrix factorization(GNMF).The dynamic functional networks of normal subjects and early mild cognitive impairment(eMCI)subjects were vectorized and the functional connection vectors(FCV)were assembled to aggregation matrices.Then GNMF was applied to factorize the aggregation matrix to get the base matrix,in which the column vectors were restored to a common sub-network and a distinctive sub-network,and visualization and statistical analysis were conducted on the two sub-networks,respectively.Experimental results demonstrated that,compared with other matrix factorization methods,the proposed method can more obviously reflect the similarity between the common subnetwork of eMCI subjects and normal subjects,as well as the difference between the distinctive sub-network of eMCI subjects and normal subjects,Therefore,the high-dimensional features in brain functional networks can be best represented locally in the lowdimensional space,which provides a new idea for studying brain functional connectomes.

Graph Regularized Sparse Coding Method for Highly Undersampled MRI Reconstruction

The imaging speed is a bottleneck for magnetic resonance imaging( MRI) since it appears. To alleviate this difficulty,a novel graph regularized sparse coding method for highly undersampled MRI reconstruction( GSCMRI) was proposed. The graph regularized sparse coding showed the potential in maintaining the geometrical information of the data. In this study, it was incorporated with two-level Bregman iterative procedure that updated the data term in outer-level and learned dictionary in innerlevel. Moreover,the graph regularized sparse coding and simple dictionary updating stages derived by the inner minimization made the proposed algorithm converge in few iterations, meanwhile achieving superior reconstruction performance. Extensive experimental results have demonstrated GSCMRI can consistently recover both real-valued MR images and complex-valued MR data efficiently,and outperform the current state-of-the-art approaches in terms of higher PSNR and lower HFEN values.

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.

Two-Level Bregman Method for MRI Reconstruction with Graph Regularized Sparse Coding

In this paper, a two-level Bregman method is presented with graph regularized sparse coding for highly undersampled magnetic resonance image reconstruction. The graph regularized sparse coding is incorporated with the two-level Bregman iterative procedure which enforces the sampled data constraints in the outer level and updates dictionary and sparse representation in the inner level. Graph regularized sparse coding and simple dictionary updating applied in the inner minimization make the proposed algorithm converge with a relatively small number of iterations. Experimental results demonstrate that the proposed algorithm can consistently reconstruct both simulated MR images and real MR data efficiently, and outperforms the current state-of-the-art approaches in terms of visual comparisons and quantitative measures.

On λ-harmonic graphs

A λ harmonic graph G, a λ-Hgraph G for short, means that there exists a constant A such that the equality λd（ui） = ∑（vi,vj）∈E（G） d（vj） holds for all i = 1, 2,…, ｜V（G）｜, where d（vi） denotes the degree of vertex vi. In this paper, some harmonic properties of the complement and line graph are given, and some algebraic properties for the λ-Hgraphs are obtained.

Search algorithm on strongly regular graphs based on scattering quantum walks

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs（SRGs） with parameters（N, k, λ, μ） achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm＇s performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O（√N） time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.

REGULAR k-COVERED GRAPHS

A graph G is k-covered if each edge of G belongs to a k-factor of G. We determine some valuee of k for which every r-regular graph with edge-connectivity λ is k-covered.

A Note on Strongly Regular Self-complementary Graphs

Koetzig put forward a question on strongly-regular self-complementary graphs, that is, for any natural number k, whether there exists a strongLy-regular self- complementary graph whose order is 4k ＋ 1, where 4k ＋ 1 = x^2 ＋ y^2, x and y are positive integers; what is the minimum number that made there exist at least two non-isomorphic strongly-regular self-complementary graphs. In this paper, we use two famous lemmas to generalize the existential conditions for strongly-regular self-complementary circular graphs with 4k ＋ 1 orders.

Generalized Krein Parameters of a Strongly Regular Graph

We consider the real three-dimensional Euclidean Jordan algebra associated to a strongly regular graph. Then, the Krein parameters of a strongly regular graph are generalized and some generalized Krein admissibility conditions are deduced. Furthermore, we establish some relations between the classical Krein parameters and the generalized Krein parameters.

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.

Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted τ c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound. Also, we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.

Clique-Transversal Sets in 4-Regular Claw-Free Graphs

A clique-transversal set D of a graph C is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by To（G）, is the minimum cardinality of a clique- transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.

Smallest Close to Regular Bipartite Graphs without an Almost Perfect Matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.

Weak Internal Partition of Regular Graphs

An(s,t)-partition of a graph G=(V,E)is a partition of V=V 1∪V 2 suchthatδ(G[V_(1)])≥s andδ(G[V_(2)])≥t.Ithasbeenconjecturedthat,forsufficiently large n,every d-regular graph of order n has a(d/2,d/2)-partition(called an internal partition).Inthispaper,weprovethateveryd-regulargraphofordern hasa(d/2,d/2)partition(called a weak internal partition)for d≤9 and sufficiently large n.

Pentavalent symmetric graphs of order 2p^3

A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p^3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p^3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p^3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p^3 are all regular covers of the dipole Dip5 with covering transposition groups of order p^3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.

A family of generalized strongly regular graphs of grade 2

A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values.For any vertex u of a generalized strongly regular graph of grade 2 with parameters(n,k;a_(1),a_(2);c_(1),c_(2)),if the number of the vertices that are adjacent to u and share ai(i=1,2)common neighbours with u,or are non-adjacent to u and share c,(i=1,2)common neighbours with is independent of the choice of the vertex u,then the generalized strongly regular graph of grade 2 is free.In this paper,we investigate the generalized strongly regular graph of grade 2 with parameters(n,k;k-1,a_(2);k-1,c_(2))and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.