스탠포드 강의를 듣고 정리한 내용입니다.
지난 포스팅에서는 대략적으로 Node Classification을 하기 위해 어떤 과정이 필요한지 알아보았습니다.
이번 포스팅에서는 앞의 포스팅에서 언급한 Relational Classification, Iterative Classification에 대해서 알아보겠습니다.
Relational Classification
relational classification의 기본 아이디어는 노드 v의 라벨 확률인 Yv는 그 노드의 주변 노드들 확률의 가중 평균을 내는 것입니다.
여기서 노드는 v, 초기화 된 라벨은 Yv, 정답 라벨은 Yv*라고 하겠습니다.
라벨이 없는 노드는 초기 Yv = 0.5가 됩니다.(여기서는 이진 분류로 가정하겠습니다.) 즉, 두 라벨 중 어떤것도 될 수 있는 확률인거죠!
이후에 계속적으로 주변 노드들로부터 확률을 받아 확률이 수렴될 때까지 계속 반복합니다.
여기서는 라벨과 그래프 자체의 구조만 사용하고, 노드의 속성(임베딩된 노드 등등)을 사용하지는 않습니다.
먼저 수식을 한번 보겠습니다.
여기서 v는 각 노드들, c는 라벨을 뜻합니다.
P(Yv = c)는 노드 v가 라벨 c를 가질 확률, A 자체는 Adjacency matrix를 뜻합니다. Av,u는 이웃 노드와 연결된 degree만큼 가중치를 주는 것 입니다. 이 부분은 예를 통해서 이해해보도록 합시다!
1. 노드 초기화 단계
앞에서도 언급했듯이, 이 task는 이진 분류 문제이고, Pyv는 v노드의 라벨이 초록색일 확률을 뜻합니다.
보시면 라벨이 없는 회색 노드들은 모두 0.5로 초기화가 되고, 초록색은 1, 빨간색은 0으로 설정되어있습니다.
2. 반복 단계
이제 첫 번째로 업데이트를 진행할 것인데요. 먼저 노드 3을 보시면 각 노드들의 라벨 확률을 얻고, degree로 나눠주는 것을 확인할 수 있습니다. 앞에서 언급한 "Av,u는 이웃 노드와 연결된 degree만큼 가중치를 주는 것"이 바로 이부분인데요. 쉽게 말하면 내 주변에 있는 라벨의 확률 평균을 받겠다! 라는 것입니다.
위는 각각 노드 4, 5에 대한 업데이트 결과이고, 모든 노드들을 업데이트하면 아래와 같아집니다.
3. 수렴
이후 무한히 반복하면 아래와 같이 수렴하는 시기가 옵니다. 여기서는 4번 정도 반복하니 아래와 같은 결과를 얻을 수 있었습니다.
확률이 0.5이상이면 초록색, 0.5미만이면 빨간색입니다. 따라서 4, 5, 8, 9는 초록색, 3은 빨간색 라벨을 가지게 됩니다.
위의 과정은 두 가지 문제점이 있는데요.
첫 번째는 수렴이 보장되지 않는 다는 것이고, 두 번째는 노드의 특징이 사용되지 않는다는 것입니다.
Iterative Classification
위의 방법에서는 먼저 노드 특징이 사용되지 않았었죠. Iterative Classification에서는 노드의 특징 fv, 주변 이웃 노드들 Nv의 라벨 Zv를 사용합니다.
입력으로는 하나의 그래프가 들어가고, 노드 v의 특징과 몇몇의 노드 v의 라벨 Yv가 들어갑니다.
이 방법론에서는 두 가지 학습을 합니다.
- ϕ1(fv) : 노드 특징 fv로 부터 노드 라벨을 예측
- ϕ2(fv, zv) : 노드 특징 fv와 이웃 노드 라벨을 요약한 zv를 이용하여 노드 라벨을 예측
여기서 나오는 주변 노드를 요약한 zv란 무엇일까요?
여기서 파란색 노드를 v라고 했을 때, 주변에 있는 초록색, 빨간색 노드에 대한 정보를 담는 것을 뜻하며, 예를 들어 "내 주변은 초록 2, 빨강 1이 있어" 혹은 "내 주변은 초록이 약 66%, 빨강이 약 33%로 구성되어있어"와 같이 정보를 담는다고 생각하시면 됩니다. 구체적으로는 예시를 통해 확인해봅시다.
예시는 web page 데이터입니다.
- Input : 웹페이지 그래프
- Node : 웹페이지
- Edge : 웹페이지 간의 하이퍼링크
- Node Features : 웹페이지 정보(여기서는 2차원의 바이너리 피쳐)
- Task : 웹페이지의 topic 예측
1. 학습
여기서 학습 데이터에는 노드 라벨이 있다고 가정합니다.
1.1 ϕ1(fv)학습
앞에서 학습은 총 2번을 한다고 말씀드렸는데요. 바로 노드의 특징으로만 분류하는 첫 번째 학습입니다.
위의 그래프를 한번 보시면 임베딩된 각 노드들 fv가 있는데요. 여기서는 구체적으로 말은 안했지만 tf-idf 등등의 알고리즘이 그 예시입니다. 혹은 앞 챕터에서 배웠던 node embedding 방법론들을 떠올리시면 됩니다.
이 단계에서는 위의 fv만 이용하여 각각의 노드를 분류합니다. (분류기도 설정하기에 따라 다르겠죠?! linear classifier 등등을 생각해 주시면 됩니다.)
위의 예시를 보시면 1인데 0으로 잘못 예측한 것을 확인할 수 있습니다.
1.2 ϕ2(fv, zv)학습
데이터 세팅
위의 설명에 앞서 몇 가지 개념을 정의해 보겠습니다.
I : 나에게로 들어오는 라벨의 정보
O : 내가 내보내는 라벨의 정보
I0 = 1이라고 하면 0 라벨을 가지는 적어도 하나의 페이지로 부터 선택을 받고 있다는 것을 뜻합니다. 예를 들어서 라벨이 0인 노드로부터 선택을 받고 있다면 I는 [1, 0], 라벨이 1인 노드로 부터 선택을 받고 있다면 [0, 1], 둘 모두로 부터 선택을 받고 있다면 [1, 1]이 됩니다.
O는 반대로 생각해주시면 됩니다. 내가 라벨 1인 노드를 선택하고 있다면 [0, 1]이 됩니다.
위와 동일하게 이 정보를 가지고 분류기를 학습시킵니다.
2. 테스트
학습된 ϕ1로 부터 테스트 데이터에 대한 노드 라벨을 부여해줍니다.
위의 라벨로 Zv를 모두 업데이트 해줍니다.
이후 분류를 수행하게 됩니다.
이후 Zv값이 변하게 되죠? 다시 반복적으로 위의 과정을 수행하게 됩니다.
이 과정은 종료 조건에 도달할 때까지 반복적으로 진행합니다. 보통 10, 50, 100회 진행한다고 합니다.
