GraphTravel

그래프 튜토리얼 9화 : Graph RNN

Graph RNN 이해
Sequential & Auto Regressive

안녕하세요, GUG 여러분! 그래프 튜토리얼의 가이드 Erica에요 🌏

9번째 여행에서는 GraphRNN 모델을 다룰 거에요. GRU와 LSTM의 아이디어를 Graph에 적용해 만들어진 아키텍처라고 할 수 있죠.
그래프 데이터의 생성, 예측, 분류 등 다양한 작업에 사용될 수 있지만 그 중에서도 특히 Graph Generation Task에 효과적이랍니다!

📢 가독성을 위해 본문에는 코드 전문을 임포트하지 않았어요.
튜토리얼 코드 전체를 한번에 실행해 볼 수 있는 .ipynb 파일은 아래 링크에 있습니다.

Graph Travel 튜토리얼이 도움이 되고 있다면,
꾸준한 업로드의 원동력이 되도록 STAR🌟를 눌러주세요~!

GraphRNN?

GraphRNN은 노드와 엣지를 순차적으로 추가하며 그래프를 생성합니다. 이전 상태 정보를 유지하며 새 Node, Edge를 추가하는 Autoregressive한 특성을 지녔죠.

그래프 전반적인 구조를 유지하면서 그래프의 복잡한 구조를 잠재 공간에 표현하기에, 다양한 동적 그래프 생성 task에 특화되어 있어요. 이 모델에 대해 이해하려면 먼저 순차성, 의존성, 자기회귀에 대해 이해해야 한답니다!

sequential & Auto Regressive해야 하는 이유

의존성(Dependency):

그래프 내의 노드들과 엣지들은 상호 의존적이에요. 예를 들어, 소셜 네트워크에서 한 사람의 연결망은 다른 사람의 연결망과 관련이 있기 마련이죠.
이처럼 그래프 안에 있는 노드들과 엣지들은 서로 독립적인 포인트들이 아니라, 서로 연관이 있는 dependent한 관계에 있기 때문에 그래프를 만들 때에도 이러한 관계를 고려해야 합니다.

AutoRegressive한 접근:

그래프를 자기회귀적(autoregressive)으로 생성하는 것은 이미 만들어진 노드와 엣지를 고려하여 새로운 노드와 엣지를 추가하는 방식입니다. 이 방법은 노드들 사이의 의존 관계를 반영하여 더 정확하고 현실적인 그래프 구조를 생성할 수 있게 해주죠.
이미 만들어진 노드와 엣지를 고려하며 새 노드와 엣지를 추가하는 방식으로 그래프를 generate함으로써 구성 요소들 사이의 dependent한 관계까지 고려할 수 있게 돼요.

GraphRNN의 접근 방식

그래프를 순차적 시퀀스로 표현:
그래프 G는 노드와 엣지의 추가를 나타내는 시퀀스(sequence) Sπ로 표현됩니다. 여기서 π는 노드의 순서(ordering)를 의미하며, 이는 그래프를 표현하는 데 중요한 요소죠.
다시 말해 가장 먼저, 노드의 시퀀스(초기 상태 포함)를 생성합니다. 여기서 RNN은 전체 그래프의 구조를 단계적으로 구축하는 과정을 수행해요.
자기회귀적 생성 모델 구축:
그 다음에는 그래프 G의 분포를 다양한 시퀀스 Sπ의 분포로 간주하여 학습합니다. 이는 앞서 만들어진 노드의 인접 벡터를 바탕으로 현재 노드의 인접 벡터가 갖는 조건부 분포의 곱으로 표현됩니다.그리고 sequence에 대해 autoregressive한 generative model을 만들게 됩니다.
이 단계에서 RNN은 새로운 노드가 기존 노드들과 어떻게 연결될지를 예측해요. 새로 추가된 각 노드에 대한 연결 여부를 예측한다고 이해하면 되죠.

여기서 포인트는 그래프 G를 노드와 엣지로 이루어진 시퀀스 Sπ로 표현하는 거에요.

그래프를 sequence 형태로 표현함으로써 우리는 graph generation 문제를 sequence generation 문제로 바꿔서 볼 수 있게 되고, p(G)를 학습하는 것이 아니라 p(Sπ)를 학습하는 것을 task로 두게 됩니다.

따라서 그래프 G의 분포는 그래프 G를 나타낼 수 있는 모든 sequence의 분포의 합으로 표현할 수 있습니다. 이건 다시 말해 앞선 노드의 adjacency vector를 현재 노드의 adjacency vector의 conditional distribution의 곱으로 표현할 수 있다는 것이죠.

Autoregressive generative models

한 단계에 하나씩. sequence 형태로 그래프를 표현함으로써 우리는 autoregressive한 형태로 그래프를 generate할 수 있게 됩니다.

이때 RNN은 2개의 RNN을 사용하게 됩니다.

graph-level RNN : 새 노드를 생성하며, Edge-level RNN의 input으로 사용되는 초기 상태(initial state)를 만드는 역할을 합니다.
edge-level RNN : Graph-level RNN에 의해 생성된, 새로운 Node에 대한 Edge(adjacency vector)를 생성합니다. 더 쉽게 이야기하자면 '새로운 노드가 기존에 만들어진 노드들과 어떻게 연결되어 있는지'를 표시하는 adjacency vector를 만드는 것이죠. 여기서 생성된 새 Node는 행렬에 새로운 행과 열을 추가하며, 이들은 edge-level RNN에 의해 0과 1로 채워집니다.

Generate Graph

그리고 그래프가 만들어지는 과정은 두 RNN을 반복하며 진행됩니다.

새 Node 추가 : Graph-level RNN을 통해 새로운 노드를 하나 만듭니다. graph-level RNN이 그래프를 초기화하고, 그 출력은 edge-level RNN에 입력됩니다.
새 Edge 추가: Edge-level RNN을 통해 1에서 만들어진 새로운 노드를 위한 엣지들을 만듭니다. edge-level RNN은 새 노드가 이전 노드들과 연결되어 있는지를 예측합니다.
이 과정을 반복하여 그래프가 확장되다가, Edge-level RNN이 모든 노드들에 대해 0. 즉 EOS(End Of Sequence)를 출력하면 그래프 생성을 종료합니다.

다시 말해 edge-level RNN은 graph-level RNN의 hidden state를 input으로 받아, 그 결과를 자신의 output으로 사용합니다. 두 RNN은 adjacency matrix를 완성하는 역할을 합니다.

Code

class Graph_RNN_structure(nn.Module):
    def __init__(self, hidden_size, batch_size, output_size, num_layers, is_dilation=True, is_bn=True):
        super(Graph_RNN_structure, self).__init__()
        
        # Model configuration
        self.hidden_size = hidden_size
        self.batch_size = batch_size
        self.output_size = output_size
        self.num_layers = num_layers
        self.is_bn = is_bn

        # Model layers
        self.relu = nn.ReLU()

이제 코드를 확인해볼까요?
Graph_RNN_structure라는 클래스는 hidden_size, batch_size, output_size, num_layers, is_dilation, is_bn 등의 매개변수를 받고, 초기화 후 모델의 구성 요소들을 클래스 변수로 설정합니다. 활성화 함수로 ReLU를 사용해요.

        if is_dilation:
            self.conv_block = nn.ModuleList([nn.Conv1d(hidden_size, hidden_size, kernel_size=3, dilation=2**i, padding=2**i) for i in range(num_layers-1)])
        else:
            self.conv_block = nn.ModuleList([nn.Conv1d(hidden_size, hidden_size, kernel_size=3, dilation=1, padding=1) for i in range(num_layers-1)])
        
        self.bn_block = nn.ModuleList([nn.BatchNorm1d(hidden_size) for i in range(num_layers-1)])
        self.conv_out = nn.Conv1d(hidden_size, 1, kernel_size=3, dilation=1, padding=1)

        self.linear_transition = nn.Sequential(
            nn.Linear(hidden_size, hidden_size),
            nn.ReLU()
        )

        self.hidden_all = []

is_dilation을 보면, 값에 따라 다양한 딜레이션(dilation) 값을 가진 컨볼루션 레이어를 생성하도록 되어 있어요. 이를 통해 모델이 입력 데이터의 다양한 범위를 고려할 수 있죠.
배치 정규화 레이어와 출력을 위한 conv layer, 선형 변환과 ReLU 활성화 함수를 포함하는 sequential 레이어를 정의한 다음, hidden state를 저장할 리스트를 초기화합니다.

        # Initialize weights
        for m in self.modules():
            if isinstance(m, nn.Linear) or isinstance(m, nn.Conv1d):
                init.xavier_uniform_(m.weight, gain=nn.init.calculate_gain('relu'))
            if isinstance(m, nn.BatchNorm1d):
                m.weight.data.fill_(1)
                m.bias.data.zero_()

    def init_hidden(self, length=None):
        if length is None:
            return Variable(torch.ones(self.batch_size, self.hidden_size, 1)).cuda()
        else:
            return [Variable(torch.ones(self.batch_size, self.hidden_size, 1)).cuda() for _ in range(length)]

    def forward(self, x, teacher_forcing, temperature=0.5, bptt=True, bptt_len=20, flexible=True, max_prev_node=100):
        hidden_all_cat = torch.cat(self.hidden_all, dim=2)
        
        # ... (코드 전문은 github에서 확인하세요!)
        return x_pred, x_pred_sample

Linear 및 Conv layer에는 Xavier 초기화를, Batch 정규화 레이어에는 특정 값으로 초기화를 수행합니다.
init_hidden 함수는 hidden state를 초기화합니다. 이 함수는 특정 길이의 숨겨진 상태 벡터 또는 벡터의 리스트를 반환해 줄 거에요. forward 함수에서는 입력 데이터 x와 다양한 매개변수를 받아 처리한 후, 결과를 반환합니다.

GraphRNN은 그래프 생성 task에 특히 적합한 모델입니다. 그래프 구조를 시퀀스 데이터로 만들고, 그것을 통해 순차적으로 그래프를 Generation해가며 이전 state의 상태에서 조금씩 더 그래프를 넓혀가는 방법이에요.

그래프 복원을 통해 누락된 Edge나 미래의 Edge를 예측하는 Link Prediction task에 특히 뛰어난 모델이랍니다.

🎫 LSTM?

그런데 RNN하면 생각나는 게 하나 더 있지 않나요? 맞아요. Sequence에 대해 LSTM을 빼고 이야기할 수는 없죠!

GraphLSTM은 LSTM의 메커니즘을 Graph data에 적용한 거에요. LSTM은 RNN의 한 형태로, 장기 의존성 문제를 해결하기 위해 고안되었으며, GraphLSTM은 이를 그래프 구조에 차용해 더 정교한 시퀀스 정보를 모델링한답니다.

다음 여행에서는 GraphLSTM으로 떠나봅시다!