스탠포드 강의를 듣고 정리한 내용입니다.
지난 포스팅에서는 노드 임베딩의 Matrix Factorization에 대해서 알아봤습니다.
이번 포스팅에서는 노드 분류를 위해 노드 간의 의미 교환은 어떻게 하는지 알아보겠습니다.
Node Classification
앞의 강의에 노드를 임베딩 하는 방법 또는 그래프를 임베딩하는 방법에 대해서 배웠습니다. 이제 여기서 조금 더 나아가면 각 노드가 어떤 라벨을 가지는지 분류하는 node classification를 생각해 볼 수 있습니다.
node classification이란 위와 같이 그래프가 있을때, 각 노드에 라벨이 존재하는 것을 뜻합니다. 왼쪽 그래프에서 빨간색, 초록색이 라벨이고, 회색은 라벨이 없는 노드입니다. 즉, 위의 라벨이 있는 노드로부터 라벨이 없는 노드를 예측하는 semi-supervised node classification이라고 할 수 있습니다.
그렇다면 우리에게는 몇몇의 라벨이 있는 노드와 전체 그래프가 주어집니다. 이제 라벨이 없는 노드를 예측해야하는데 어떻게 해야할까요?
네트워크 내에는 닮은 노드끼리 연결되어있는 상관관계가 존재하고, 이를 이용하여 최종적으로 노드를 예측하게 됩니다.
이를 위한 3가지 방법을 이번 5챕터에서 살펴볼 예정입니다.
- Relational classification
- Iterative classification
- Belief propagation
네트워크 내의 상관관계
위에서 "네트워크 내에는 상관관계가 존재하고"라고 말씀드렸는데요. 노드 끼리의 상관관계란 무엇일까요?
위의 그래프를 보고 느껴지시는게 있나요?
바로! 비슷한 노드는 비슷한 노드 끼리 뭉쳐있죠? 이처럼 서로 근접한 노드를 찾을 수 있다면 라벨이 없는 노드들도 주변 노드로 부터 힌트를 얻어 라벨을 예측할 수 있게 됩니다.
어떤 근거로 비슷한 노드가 뭉쳐있다고 하는건가요? 그래프를 그냥 저렇게 그린거잖아요!
라는 생각이 드실 수 있는데요. 근거가 있기에 저렇게 그릴 수 있었습니다!
노드 간의 상관 관계에는 Homophily, Influence 라는 두 개념이 존재합니다.
Homophily
이 개념은 "비슷한 특성을 가진 사람들은 서로 연결된다."라는 개념입니다. 예를 들어 비슷한 연구를 하는 사람들은 같은 학회 참석하고, 커뮤니티에서 대화를 나눌 확률이 커지고, 자연스레 연결이 됩니다.
위의 그래프는 어느 고등학교의 social network를 나타낸 것입니다. 여기서 노드는 사람들(학생들), 링크는 친분, 노드 색깔은 운동, 미술 등의 관심사입니다. 딱 보기에도 비슷한 관심사를 가진 사람들끼리 잘 뭉쳐져있는 것을 알 수 있습니다.
Influence
위와는 반대되는 개념인데요. "뭉쳐있으면 영향을 받아 비슷해진다."라는 개념입니다. 예를 들어서 친구에게 음악을 추천받으면 나도 그 장르를 좋아하게 될 확률이 높아진 다는 것이죠.
위의 두 개념을 근거로 "비슷한 사람은 뭉치고, 뭉쳐져 있으면 비슷해진다."라고 할 수 있습니다. 이 현상들은 주변에서 많이 느끼고 계실텐데요. 아주 흔하고 강력합니다.
그럼 이제 본격적으로 node classification을 어떻게 하는지 알아보도록 합시다.
우리는 앞의 두 가지 이유로 내트워크 내에 비슷한 노드는 가까이 존재하거나 직접적으로 연결되어 있다는 것을 알 수 있었습니다. 이것을 바로 Guilt-by-association이라고 합니다. 즉, 위의 그래프에서 노드 9가 라벨이 아직 없는데, 그와 연결된 노드 7이 label 1이기 때문에 노드 9가 label 1일 확률이 높다는 것입니다.
위와 같이 분류하는데 사용되는 정보는 아래와 같습니다.
- 노드 v의 특징
- 노드 v의 이웃 노드 라벨들
- 노드 v의 이웃 노드 특징들
한가지 예를 보겠습니다.
먼저 입력으로는 위의 그림과 같이 라벨을 가진 몇몇의 노드들과 라벨이 없는 노드로 이루어진 그래프가 주어집니다.
우리의 목적은 회색 노드가 빨간색 혹은 초록색 라벨을 가지게 하는 것이었죠!
실제 입력으로는
- 노드가 n개인 adjacency matrix A
- 노드 라벨 벡터 Y(여기서는 이진 분류이기 때문에 0 또는 1)
가 들어갑니다.
collective classification
collective classificaiton은 노드간의 상관관계와 구조적인 특징을 모아서 분류를 하게 됩니다. 이 때, markov chain을 이용하는데, 하나의 노드 v의 라벨 Yv는 이웃 노드들 Nv의 라벨에 의존한다는 것입니다.
collective classification은 총 3가지 과정을 거칩니다.
1. Local Classification
노드 초기화를 위한 단계입니다. 라벨이 없는 노드들을 위해 진행하는 단계이고, 초기 라벨로 할당해줍니다.
노드의 특성을 기반으로 라벨을 예측합니다. 여기서는 네트워크 정보를 사용하지 않고, 고전적인 분류와 동일합니다.
2. Relational Classification
노드의 상관관계를 이용하여 분류합니다. 이 때, 이웃 노드의 라벨과 변수를 기반으로 분류기를 학습합니다. 이 때는 이웃 노드를 이용하기 때문에 네트워크 정보를 사용합니다.
3. Collective Inference
이 과정은 노드 간의 불일치가 최소화 될 때까지 계속해서 반복합니다. 위에서 나온 markov chain을 떠올리시면 됩니다.
위에서 언급한 세 가지 방법론이 바로 collective classification의 방법론들입니다.
다음 포스팅에서 자세히 알아보도록 하겠습니다.
