Questions tagged [graph-laplacian]

A simple graph has a symmetric matrix L = D - A associated with it called the Laplacian matrix, where D is the diagonal matrix of degrees and A is the adjacency matrix, often studied for its spectrum (eigenvalues).

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

Spectral Clustering: Finding the normalized minimum cut using the laplacian

I am trying to prove that finding the min $Ncut(A,B)$ for a edge weight graph $W$ with the diagonal matrix of edge degrees $D$ is equivalent to solving for $f \in \{a,b\}^n$ with the constraint that $...
bluesquare's user avatar
0 votes
0 answers
15 views

Do Adjacency and Laplacian cospectral graphs always have the same degree sequence?

I know that the spectrum of the adjacency matrix enumerates the number of closed walks, and the spectrum of the reduced laplacian enumerates the number of spanning trees. Does being both adjacency and ...
Luke Green's user avatar
0 votes
0 answers
16 views

Relation between graph Laplacians and covariance matrices

In the "Future challenges" section of the article Dittrich, Thomas, and Gerald Matz. "Signal processing on signed graphs: Fundamentals and potentials." IEEE Signal Processing ...
Fernando's user avatar
0 votes
0 answers
34 views

How to compute eigenvalues of graph laplacian?

I know there are various ways to compute eigenvalues, and they are generally not very efficient for large matrices. Graph Laplacians are symmetric and positive (except on the diagonal, which is ...
lady gaga's user avatar
  • 2,035
0 votes
1 answer
49 views

What's the conditions for equality of Cheeger inequality?

I have learnt the Cheeger inequality for a graph $G$: $$\lambda_2/2\le h(G)\le\sqrt{2\lambda_2}.$$ But does the equality hold? For a non-connected graph, it is obvious. But for a connected graph, I ...
Fresh's user avatar
  • 11
1 vote
0 answers
44 views

Is there an information-theoretic motivation for heat kernel weights on adjacency graph?

I am learning about the laplacian eigenmap algorithm for finding a lower dimensional representation of a dataset. An important step in this algorithm is assigning weights to the adjacency graph for ...
marutator's user avatar
0 votes
0 answers
46 views

Prove that Laplacian of a undirected, connected graph is positive definite

Problem: Prove that Laplacian matrix $L$ of an undirected, connected graph $G$ ($G$ finite with $n$ vertices) is positive definite. Using the following property to prove $$L = D-A,$$ where $D$ is the ...
Tung Nguyen's user avatar
  • 1,280
0 votes
1 answer
88 views

Heat kernel on graphs

Let $V$ denote a finite set $(v_1, \ldots, v_n)$ and $G=$ $(V, E)$ denote a non-oriented connected graph, i.e., $E \subset V \times V$ and $(v, v^{\prime}) \in E \implies (v^{\prime}, v) \in E$ and ...
Pipnap's user avatar
  • 381
1 vote
1 answer
116 views

How many spanning trees of $K_9$ have exactly one vertex of degree 5?

Given the complete graph $K_9$, how would you find the number of spanning trees that have exactly one vertex with degree 5? I am a first-year student studying CS. This question was discussed in our ...
Kapish Singla's user avatar
1 vote
0 answers
55 views

max-cut from Graph Laplacian

Given a weighted graph with $n$ vertices and weights $w_{ij}\geq 0$, the max-cut problem is equivalent to $$ \max_{x \in \mathbb{R}^n} \sum_{i,j} w_{ij} (1-x_i x_j) \quad \mbox{s.t.} \quad x_i \in \{-...
Thomas's user avatar
  • 199
0 votes
0 answers
85 views

Help understanding a portion of research paper (Matern kernel, graph Laplacian)

I am trying to read this paper, and I don't seem to have some of the assumed mathematical background. I am trying to understand a certain section (the beginning of 3.1), which I will reproduce here. ...
caitlin's user avatar
  • 125
0 votes
0 answers
68 views

Laplacian matrix and its eigenvectors and eigenvalues

I am reading paper written by Newman on finding community structure in a network. I came across with the Laplacian matrix. And there is one equation derived from some others. Before diving into that, ...
Ilhom Sadriddinov's user avatar
0 votes
0 answers
26 views

Intuition eigenvectors graph Laplacian for weighted graph

Is there some interpretation for the eigenvectors of the Laplacian of a (directed) weighted graph? Normally, the spectrum of a Laplacian informs us about connectives, is this also the case for a ...
Jeff Martin's user avatar
2 votes
2 answers
110 views

Laplace matrix for undirected graph

So Laplacian matrix can be calculated by the following equations according to wiki: $L=BB^{T}$ where $L$ is the Laplacian matrix and $B$ is the incidence matrix. However, the incidence matrix for an ...
liaoming999's user avatar
1 vote
1 answer
76 views

Are all Laplacian eigenvalues always non-increasing when an edge is deleted?

Consider the Laplacian $L$ of some simple graph $G$ with at least one edge. As usual, $L=D-A$ where $D$ is the diagonal matrix with elements $D_{ii}=d_i$ where $d_i$ is the degree of node $i$ and ...
Kiro's user avatar
  • 305
0 votes
0 answers
45 views

Numerical method for calculating large discrete harmonic function

I am working on a problem, and for testing purposes, I want to do the following. Let be given a sparse graph $G(V,E)$ with edge weight matrix $W$, and $|V|$ large (anywhere from $10^3$ to $10^6$). We ...
blomp's user avatar
  • 529
4 votes
0 answers
104 views

Diagonalizability of Laplacian Matrices in Graphs

The adjacency matrix of a simple labeled graph is the matrix $A$ with $A_{[i, j]}$ or 0 according to whether the vertex $v_j$, is adjacent to the vertex $v_j$ or not. For simple graphs without self-...
Mark's user avatar
  • 7,861
1 vote
0 answers
85 views

Trace of power of Laplacian matrix of a graph

It is well known that, for symmetric matrices, the trace the product of three matrices $A$, $B$, $C$ is the same, independent of the order of $A$, $B$, $C$, that is, $$\operatorname{tr}(ABC) = \...
ChibiPeew's user avatar
1 vote
1 answer
251 views

Why do the "important" eigenvectors of a graph Laplacian have small-magnitude eigenvalues?

In spectral clustering, one computes sample-sample similarities, then from this computes a graph Laplacian matrix. (Typically, one uses the symmetrically normalized Laplacian matrix, but the pattern I'...
calmcc's user avatar
  • 251
0 votes
1 answer
135 views

About the notation of $2$D Laplace operator

I’m reading a paper on $2$D discrete Laplace operator, and perhaps because it’s an old paper, the notation in it really bothers me a lot. So can someone please explain it to me? For example, the ...
Ili a's user avatar
  • 19
0 votes
1 answer
78 views

Eigenvalues after setting rows of matrix to zero

I am studying the effect on the eigenvalues of a known Laplacian matrix $L$ when the first $p$ rows (wlog the top rows) are set to $0$. For those not familiar with a Laplacian matrix, all you need to ...
Landuros's user avatar
  • 2,781
0 votes
0 answers
44 views

Laplacian quadratic form and effective resistance

Consider a graph $G=(V,E)$ with positive edge weights. For simplicity, in my question, you can also assume unweighted graph. I am trying to show that the Laplacian quadratic form of the graph ...
emelie's user avatar
  • 409
0 votes
0 answers
142 views

Quadratic form involving graph Laplacian

I have a connected undirected graph of $n$ nodes. Each node $i$ has a vector ${\bf x}_i$ and is connected to $d_i$ neighbours. Let $\tilde{{\bf L}} := {\bf L} \otimes {\bf I}_n$, where $\bf L$ is the ...
Chao's user avatar
  • 105
0 votes
1 answer
128 views

Closed form of the eigenvalues of a specific tridiagonal matrix

Hello I would like to know if someone has an idea of how to compute the eigenvalues (in a closed form) of the following matrix in order to implement it for fast calculations. The matrix is the ...
user1378851's user avatar
2 votes
1 answer
47 views

Smallest eigenvalue of a variant of the line graph Laplacian

I would like to calculate a lower bound on the minimum eigenvalue of the matrix $$M = e_1 e_1^\top + L$$ where $L$ is the Laplacian of the line graph on $T$ vertices: $$1 -2 -3 -4-\ldots -T $$ and $...
Chinmay Nirkhe's user avatar
1 vote
1 answer
74 views

How to understand the potential energy cost function based on cotan Laplacian operator in 3D mesh deformation

Suppose I have a source triangle mesh surface $S^0 = (V,E)$. $V,E$ are sets of $n$ vertices and $m$ edges of the mesh, respectively. $S^1,S^2,S^3, \ldots, S^l$ is denoted as a sequence of meshes after ...
Wasabi's user avatar
  • 11
0 votes
1 answer
54 views

Calculating the diagonal entry of the adjugate of the Laplacian matrix of a complete graph.

I am trying to directly calculate the adjugate of the Laplacian of the complete graph from which I know is given by $\tau(G) = n^{n-2}$ where $\tau(G)$ is the number of spanning trees of $K_n$. I ...
Smirniy007's user avatar
0 votes
0 answers
25 views

Eigenvalue corresponding to the highest eigenvalue multiplicity of normalized Laplacian spectrum

Suppose we have an undirected weighted graph (more specifically, a scale-free network). When I plot its normalized graph Laplacian spectrum, I get something like this: Normalized Laplacian Spectrum, ...
KAMYAR M. ROUDAKIAN's user avatar
0 votes
0 answers
80 views

What does the notation subscript *L and a circle with a dot in it represent?

I was recently reading this arxiv paper, in the context of Machine Learning, and I was wondering what the notation $\odot$ and $\square^\ast_L$ are supposed to mean under section 3. I had read ...
Brayden Alexander Rudisill's user avatar
0 votes
0 answers
61 views

How can the relationship between two nodes be captured using the Laplacian matrix?

I am new to spectral graph theory, so I apologize if there are any mistakes in my writing. If I make an error, please kindly point it out and guide me in the right direction. Now let me clearly state ...
Anmol Gupta's user avatar
0 votes
0 answers
88 views

Eigenvector of normalized graph Laplacian

I’m reading a paper and they make a claim about the eigenvector of a graph Laplacian that seems wrong and I wanted to check with the larger community if I’m missing something obvious. Let $G = (V,E,W)$...
WedgeAntilles's user avatar
0 votes
0 answers
38 views

Generalizing the sum of squared second differences to graphs?

Suppose I have a sequence of numbers $x = (x_1, x_2, \dots x_n)$. I’m interested in the sum of squared differences: $$\sum_{i=1}^{n-1} (x_{i+1} - x_i)^2.$$ I can treat the sequence as a function on ...
user357269's user avatar
1 vote
0 answers
63 views

Is there a graph which has this matrix as its Laplacian?

I have been reading this paper https://arxiv.org/abs/1307.6864 which is concerned with matrix completion problems of the following form: Suppose we know that $A=xx^*$ is the outer product of a vector $...
mrry0's user avatar
  • 51
0 votes
0 answers
58 views

Can the Laplacian matrix of an undirected weighted graph be decomposed in the form of the Hadamard product ?

I want to rewrite an incidence matrix M of an undirected weighted graph G into $ M = W \circ A$ where W is the weight matrix, and $\circ$ denotes a Hadamard product. Now can someone tell me the factor ...
Entropy Aran's user avatar
1 vote
0 answers
120 views

Analogy between graph Laplacian and continuous Laplacian

The graph Laplacian is ussually defined as $L=D-A$, where $D$ is the degree matrix and $A$ the adjacency matrix. It gets its name from being the discrete analog of the Laplacian operator from calculus....
PabloVD's user avatar
  • 11
1 vote
1 answer
90 views

Positive definiteness of graph Laplacian

Consider the proof at page 2 found here: https://people.orie.cornell.edu/dpw/orie6334/Fall2016/lecture7.pdf I can’t wrap my head around the second and third line: \begin{align} &= \sum_{i \in V}x(...
user1001020202's user avatar
1 vote
0 answers
91 views

Find the Degree matrix $D$ using the Adjacency matrix $A$ and (half of) the coordinates of a graph.

Say, we have a graph $G$ with 6 points of which 3 are given. The coordinates of the other 3 points are unknown at this point. I got the (full) adjacency matrix and the 3 coordinates. How do I ...
Gerald's user avatar
  • 11
3 votes
0 answers
49 views

Extract metric of graph Laplacian

As written here and here: given a graph $G=(V,E)$ there is a connection between its Laplacian , $L$ to the continuous Laplace-Beltrami operator $\Delta_g$ defined on a Riemannian manifold $(M,g)$ . ($...
Benny K's user avatar
  • 173
0 votes
1 answer
42 views

Number of Spanning Trees in $Q_n$ via isomorphism to Cartesian product of $K_2$

I'm trying to calculate (or, show) the number of spanning trees in the hypercube $Q_n$. I know I must come to $$\tau(Q_n) = \prod^{n}_{i=2} (2i)^{\begin{pmatrix} n \\ i\end{pmatrix}}$$ I thought it ...
user avatar
2 votes
1 answer
105 views

Why does the condition $\sum_{x\in\Lambda}f_x=0$ imply the discrete Laplacian is invertible?

I'm studying statistical physics these days and have newly learnt the concept discrete Laplacian. For a finite graph $G$ with vertices $\Lambda\subset\mathbb{Z}^d,$ consider the discrete Laplacian ...
Chang's user avatar
  • 187
0 votes
1 answer
153 views

Why can a similarity matrix be used instead of a Laplace matrix when using spectral clustering methods?

When we are using spectral clustering methods, we often construct similarity matrices $S$ between data, and use the similarity matrix to derive the Laplacian matrix $L$ for further clustering. But in ...
Haoyi Lei's user avatar
1 vote
0 answers
107 views

Graph diffusion: finding the steady state current

Consider a quantity $x$ diffusing on a graph according to $$\frac{\Bbb dx}{\Bbb dt}=-Lx+a,$$ where $L$ is the graph Laplacian and $a$ encodes sources and sinks. In the steady state, $x_0=L^{-1}a$. How ...
Nichola's user avatar
  • 203
1 vote
1 answer
122 views

laplacian and signless laplacian matrix

Let $L(G)$ and $Q(G)$ be the Laplacian matrix and Signless laplacian matrix for a graph $G$. By definition, $L(G) = D(G)-A(G)$ and $Q(G) = D(G) + A(G)$, where $D(G)$ is the degree matrix for $G$ and $...
Mohanaphriya's user avatar
1 vote
0 answers
41 views

Why is the dirichlet energy bounded by the 2nd smallest eigenvalue of the graph laplacian?

There is a proof in a paper (Link) that shows that the dirichlet energy of any matrix X gets reduced when the adjacency matrix $\tilde{A}=\tilde{D}^{-0.5}(A + I_n)\tilde{D}^{-0.5}$ is applied: $$E(\...
Andreas's user avatar
  • 11
1 vote
0 answers
151 views

Normalized Laplacian Proof

I'm reading a lecture on clustering (https://www.math.ucdavis.edu/~strohmer/courses/180BigData/180lecture_clustering.pdf) And I was wondering about the proofs for Theorem 3.3 and 3.4. That is, For two ...
Jayden Rice's user avatar
0 votes
1 answer
117 views

Difference between Symmetrically normalized Laplacian matrix versus graph laplacian matrix

I am trying to understand the graph laplacian matrix in Graph Convolution networks. To get a basic understanding of graph laplacian matrix I am referring to this https://mbernste.github.io/posts/...
Jose_Peeterson's user avatar
0 votes
1 answer
61 views

Missing eigenvectors of the ring graph Laplacian

Spielman has some notes where he explains that the eigenvectors of the Laplacian of the ring graph are $$ x_k(u) = \sin(\frac{2\pi ku}{n})\\y_k(u) = \cos(\frac{2\pi ku}{n}) $$ for $1 \leq k \leq n/2$ ...
Apodictic Apple Juice's user avatar
1 vote
1 answer
72 views

Determining the Laplacian for a signed graph

I was reading the paper: On the Laplacian Eigenvalues of Signed Graphs, when I had this question. When we determine the Laplacian of a signed graph, why do we take the unsigned degree matrix D, but ...
B2VSi's user avatar
  • 1,005
0 votes
0 answers
197 views

Graph Laplacian for weight matrix with negative edges

How can I normalize my weight matrix to get a positive semi-definite Laplacian, if I am using a weight matrix with negative edges?
Radwa Adel's user avatar
0 votes
0 answers
95 views

Eigenvalues of graph laplacian question

I need some guidance on solving the following question I am stuck on: Let L be a graph Laplacian matrix of a graph G = (V, E) with n vertices. Denote the eigenpairs of L by {λi,ψi} for every i=1..n, ...
Yep's user avatar
  • 11

1
2 3 4 5 6