Graph Theory 图论

Laplacian matrix

Categories of graphs:

• directed/undirected.
• homogeneous/heterogeneous.
• static/dynamic. A dynamic graph is a graph whose topology varies with time.

It is a matrix representation of a graph.

It can be used:
(1) to construct low dimentional graph node embeddings.
(2) to find sparsest /(K/) subgraphs of a graph through the /(K/) smallest eigenvalue of its laplacian matrix.
(3) to calculate the number of spanning trees.
(4) …

Given a simple graph /(G/) with vertices /(V/) , the Laplacian matrix /(L/in/R^{|V|/times |V|}/) of /(G/) is given by

/[L := D-A
/]

, where /(D/) is the degree matrix, which is diagonal with entries /(D_{ii}/) the degree of node /(i/) , and /(A/) is the adjacency matrix. Since /(G/) is a simple graph, /(A/) only contains 1 or 0 and its diagonal elements are all 0s.

(Symmetric) normalized Laplacian matrix

/[L_{/rm sym} := D^{-/frac12}LD^{-/frac12} = I-D^{-/frac12}AD^{-/frac12}
/]

The elements of /(L_{/rm sym}/) are given by

/[L_{/rm sym}[i,j] :=
/begin{dcases}
1 & /text{ if } i=j /wedge /deg(i)/ne 0 //
-/frac{1}{/sqrt{/deg(i)/deg(j)}}& /text{ if } i/ne j /text{ and i is adjacent to j} //
0 & /text{ otherwise}
/end{dcases}
/]

Random Walk normalized Laplacian matrix

/[L_{/rm rw}[i,j] := D^{-1}L = I- D^{-1}A
/]

The elements of /(L_{/rm rw}/) are given by

/[L_{/rm rw}[i,j] :=
/begin{dcases}
1 & /text{ if } i=j /wedge /deg(i)/ne 0 //
-/frac{1}{/deg(i)}& /text{ if } i/ne j /text{ and i is adjacent to j} //
0 & /text{ otherwise}
/end{dcases}
/]

Properties of Laplacian matrix

• /(/forall /bm x/in /R^{|V|}: /bm x^T L /bm x=/sum_{i,j}^{|V|} A_{ij}/|x_i-x_j/|^2/)
• /(L/) is symmetric, positive semi-definite, diagonally dominant.
• /(L/) is a M-matrix (its off-diagonal entries are non-positive, and the eigenvalues are non-negative ( on real parts for complex numbers).
• The smallest eigenvalue is /(0/) , and the corresponding eigenvector is /(/bm 1/) (all elements are 1s).
• /(L/) has non-negative eigenvalues, /(0/le /lambda_1 /le /lambda_2 /le … /le /lambda_n/) .

Considerations of Graph Representation Learning

1. Permutation Invariance. Permutation invariance means that the function does not depend on the arbitary ordering of the row/columns vectors of the matrix.

/[f(PAP^T)=f(A) /implies /text{ Permutation Invariance}

f(PAP^T)=Pf(A) /implies /text {Permutation Equivariance}
/]

where /(P/) is a permutation matrix.
2.