Node Embeddings and Matrix Factorization

연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.

 

유튜브 강의 링크는 다음과 같다.

 

https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn 

Stanford CS224W: Machine Learning with Graphs

 

 

목차

 

 

 

 

바로 이전 글에서 feature 표현을 위한 node embedding과 graph embedding을 구성하는 방법을 알아보았다.

 

Embedding Matrix

 

Embedding matrix는 위와 같았다. 이때 비슷한 두 노드\(u, v\)의 inner product \(\mathbf{z}_v^\top \mathbf{z}_u\)를 최대화하여 노드의 feature를 표현했다.

 

이번에는 이렇게 matrix를 활용해서 node similarity(node embedding)를 어떻게 표현할 수 있는지 알아보자.

 

 

 

 

 

Matrix Factorization

 

두 노드가 비슷할 조건 중 가단 간단한 것은 node \(u, v\)가 edge로 연결되어있으면 비슷하다고 보는 것이었다.

이를 vector와 matrix로 표현하면 다음과 같다.

 

\( \mathbf{z}_v^\top \mathbf{z}_u = \mathbf{A}_{u, v} \)

 

여기서 \(\mathbf{A}\)는 adjacency matrix이다.

 

Factorization of Adjacency Matrix

 

이를 모든 노드로 확장해보면, 위 그림과 같이 embedding matrix의 dot product로 adjacency matrix 전체를 나타낼 수 있다. (node가 연결되어있으면 1, 연결되어있지 않으면 0)

 

하지만 \(\mathbf{Z}\)의 size는 dimension \(d\) × number of nodes \(n\)로, 일반적으로 dimension이 node 개수보다 훨씬 적기 때문에 \(\mathbf{A} = \mathbf{Z}^\top \mathbf{Z}\)와 같이 정확하게 factorization하는 것은 거의 불가능하다.

따라서 다음의 objective로 \(\mathbf{Z}\)를 근사하여 학습한다.

 

\( \underset{Z}{\min} \lVert \mathbf{A} - \mathbf{Z}^\top \mathbf{Z} \rVert_2 \)

 

위 식을 만족시키는 \(\mathbf{Z}\)를 최적화하여 \(\mathbf{A} - \mathbf{Z}^\top \mathbf{Z} \)의 L2 norm을 최소화하도록, 즉 \(\mathbf{A}\)와 \(\mathbf{Z}^\top \mathbf{Z}\)가 최대한 가까워지도록 하는 것이다. L2 norm은 2차원 거리의 개념이다.

정리하자면, edge 연결 여부로 node similarity를 정의할 때, inner product decoder는 adjacency matrix의 factorization과 같다.

 

 

 

 

 

Random Walk-based Similarity

 

Deep walk와 node2vec의 경우, 앞선 경우보다 node similarity의 정의가 훨씬 복잡하다.

Deep walk는 다음 식으로 표현되는 transformed adjacency matrix의 factorization이다.

 

\( \log{\left( vol(G) \left( \cfrac{1}{T} \sum\limits_{r=1}^T (\mathbf{D}^{-1} \mathbf{A})^r \right) \mathbf{D}^{-1} \right)} - \log{b} \)

 

각 항에 대한 설명을 하자면 다음과 같다.

• \(\mathbf{D^{-1} \mathbf{A}^r \) : Normalize된 adjacency matrix를 \(r\)번 제곱한 term이다.
  • \(D_{u,u} = \operatorname{deg} (u)\) : node의 degree를 나타내는 diagonal matrix이다.
• \(vol(G)\) : graph의 volume, 즉 (2 × edge의 총 개수)이다.
  • \(vol(G) = \sum\limits_{i} \sum\limits_{j} \mathbf{A}_{i,j}\)
• \( T \) : Context window size(length)이다. (이전 글을 참조하자)
  • \(T = \lvert N_R(u) \rvert\), 즉 optimization 과정에서 \(T\)번의 random walk를 수행한다.
• \( \log{b}\) : negative sample의 개수이다.

 

Simplest 방식과 마찬가지로, deep walk를 위 식으로 구한 transformed matrix와 inner product decoder가 서로 최대한 가깝게 만들어서 행렬로 표현한다.

 

Node2vec도 같은 방식으로 행렬로 표현할 수 있다. (여기서 식을 다루지는 않겠다.)

 

 

 

 

 

 

 

Limitations

 

그런데, node embedding과 random walk를 행렬로 표현하는 것에는 여러 가지 한계가 존재한다.

1. Training set에 없는 노드, 즉 새로 추가되는 노드는 임베딩을 구할 수 없다.
   • 만약 그래프가 계속 바뀐다(예를 들어, 노드가 추가된다)고 가정하면, 행렬로 표현한 deep walk나 node2vec을 통해 추가된 노드에 대한 임베딩을 구할 수 없다.
   • 노드가 추가될 때마다 행렬 자체가 바뀌기 때문에 모든 노드에 대한 임베딩을 다시 계산해주어야 한다.
2. 행렬로 표현한 node embedding은 구조적인 similarity를 반영할 수 없다.
   • 예를 들어, 다음 그래프를 살펴보자.
   • 
   • 1번 노드와 11번 노드는 삼각형의 일부이고, degree가 2라는 구조적 공통점을 갖고 있다.
   • 하지만 embedding 결과 두 노드는 행렬에서 완전히 다르게 나타날 것이다. (두 embedding vector의 dot product가 transformed adjacency matrix의 해당 요소와 다르게 나타날 것이다.)
3. Node feature, edge feature, graph feature를 활용할 수 없다.
   • Node, edge, graph는 해당하는 graph 내에서의 feature 이외에도 다른 그래프와의 연관성 등을 가질 수 있는데, deepwalk와 node2vec은 이와 같은 feature와 상호작용할 수 없다.
   • 이는 Deep Representation Learning과 Graph Neural Network를 통해 해결한다.

 

 

 

 

 

Application

 

이렇게 그래프를 행렬로 표현하는 관점은 다음과 같은 알고리즘에서 중요한 역할을 한다.

• PageRank
  • 초창기 구글의 검색 알고리즘으로 유명하다.
  • graph 내에서 노드의 importance를 측정한다. → Adjacency matrix의 power iteration으로 효율적인 계산이 가능하다.
• Personallized PageRank (PPR)
  • 노드 각각 또는 노드 셋(set)에 대해 importance를 측정한다.
  • Random walk로 효율적으로 계산할 수 있다.