Graph의 Spectral Filtering (스펙트럴 필터링)

Graph의 Spectral Filtering에 대해 알아보자. loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $G$의 normalized Laplacian matrix를 $L^{norm}$ 이것의 대각화 표현을 $L^{norm}=U \Lambda U^T$이라고 하자 (참고글: Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유). 지난 글 (Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의)에서 봤듯이 $L^{norm}$의 eigen value는 인접한 vertex들의 차이가 얼마나 … Read more

Graph Convolution (그래프 컨볼루션)에 대하여

이번 글에서는 Graph Convolution (그래프 컨볼루션)에 대해 알아보자. Graph convolution에 대해 알아보기전에 아래의 글들을 이해하고 오길 바란다. Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의 Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유 그러면 이제 Graph Convolution에 대해 알아보자. Graph convolution의 정의 loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $L^{norm}$은 $G$의 … Read more

Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의

이번 글에서는 Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의에 대해 알아보도록 하자. 오늘의 글을 본격적으로 진행하기 전에 몇가지를 정의하고 시작하자. loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $D$를 $G$의 degree matrix라고 정의하고 $A$를 $G$의 adjacency matrix라고 정의하자. 그리고 $L^{norm}$을 $G$의 normalized laplacian matrix라고 정의하자. (참고글: Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 … Read more

Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유

이번 글에서는 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 이것의 eigen value가 0과 2사이라는 사실을 설명해보겠다. Normalized Laplacian matrix에 대해 알아보기 전에 Normalized adjacency matrix를 정의하고 그것으로 부터 Normalized Laplacian matrix를 정의한 이 후 글을 이어가겠다. Normalized Laplacian matrix 알아보기 그래프 $G=(V,E)$가 있다고 하자. $V=\{1,2,…,n\}$이라고 편하게 표시하자. Nomralized Adjacency matrix 정의 Normalized Laplacian matrix에 대해 알아보기전에 … Read more

Graph의 Laplacian matrix(라플라시안 행렬)와 Laplacian matrix의 eigenvalue

이번 글에서는 그래프 (graph)의 Laplacian matrix (라플라시안 행렬)과 Laplacian matrix의 성질들을 알아보겠다.  Laplacian matrix는 positive definite matrix이고 이에 따라 eigen value가 0보다 크거나 같으며 Laplacian matrix의 eigen value에는 무조건 0이 있다는 것까지 알아보자. Laplacian matrix의 정의 방향이 없는 undirected simple graph $G=(V,E)$가 있다고 하자. 편하게 $V=\{1,2,3,…,n\}$이라 표현하겠다. $\mathbf{D}$를 이 graph $G$의 degree matrix라 하고 $\mathbf{A}$를 … Read more

[Graph Theory problem solving]Let G be a connected 3-regular plane graph in which every vertex lies on one face of length 4, one face of length 6, and one face of length 8. (a) In terms of n(G), determine the number of faces of each length. (b) Use Euler’s Formula and part(a) to determine the number of faces of G.

I will solve a graph theory problem: Let G be a connected 3-regular plane graph in which every vertex lies on one face of length 4, one face of length 6, and one face of length 8. (a) In terms of n(G), determine the number of faces of each length. (b) Use Euler’s Formula and … Read more

[Graph Theory problem solving]For n ≥ 1, let Gn = Pn□K2 ; this is the graph with 2n vertices and 3n − 2 edges shown below. Determine χ(Gn; k). (You should simplify your answer by factoring the polynomial

I will solve a graph theory problem: For n ≥ 1, let Gn = Pn□K2 ; this is the graph with 2n vertices and 3n − 2 edges shown below. Determine χ(Gn; k). (You should simplify your answer by factoring the polynomial Graph Theory Problem Solving: $G_n$ is a bipartite graph. Therefore, it should be … Read more

[Graph Theory problem solving] Prove that if G is a color-critical graph, then the graph G′ generated from it by applying Mycielski’s construction is also color-critical. (If χ(H) < χ(G) for every proper subgraph H of G, then G is called color-critical.)

I will solve a graph theory problem: Prove that if G is a color-critical graph, then the graph G′ generated from it by applying Mycielski’s construction is also color-critical. (If χ(H) < χ(G) for every proper subgraph H of G, then G is called color-critical.) Graph Theory Problem Solving: Let $V(G) = \{v_1,v_2,…,v_n\}$ and $V(G^\prime) … Read more

[Graph Theory problem solving] Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G).

I will solve a graph theory problem: Prove that a graph G is m-colorable if and only if α(G□Km) ≥ n(G). Graph Theory Problem Solving: ($\Rightarrow$) Since $G$ is m-colorable, there exists a proper m-coloring $f:V(G) \to \{1,2,…,m\}$. For each $i=1,2,3,…,m$, let $I_i = \{ v \in V(G) \mid f(v) =i \}$. $I_i$ is an … Read more

[Graph Theory problem solving] Deduce that $e(T_{n,k}) = \left \lfloor \left(\frac{k-1}{2k} \right) n^2\right \rfloor$ for all $k < 8$

I will solve a graph theory problem: Deduce that $e(T_{n,k}) = \left \lfloor \left(\frac{k-1}{2k} \right) n^2\right \rfloor$ for all $k < 8$ I recommend that you read this post, first. Graph Theory Problem Solving: Since $k<8$, $-\frac{k}{8} > -1$. Therefore, $\frac{n^2(k-1)}{2k} – \frac{k}{8} >\frac{n^2(k-1)}{2k} -1$ and $ \left \lceil \frac{n^2(k-1)}{2k} – \frac{k}{8}\right \rceil  \geq \left … Read more