환경구성

MongoDB

docker-compose.yaml 파일을 작성합니다.

version: '3.8'
services:
  mongodb:
    image: mongo
    container_name: mongodb
    restart: always
    ports:
      - 27017:27017
    volumes:
      - ./mongodb:/data/db
    environment:
      - MONGO_INITDB_ROOT_USERNAME=root
      - MONGO_INITDB_ROOT_PASSWORD=1234 
      - MONGO_INITDB_DATABASE=mydb

docker로 local mongodb 실행합니다.

docker-compose up -d

Python

python package pymongo 설치합니다.

pip install pymongo

pymongo DB connection

import pymongo

client = pymongo.MongoClient(
    host="0.0.0.0",
    port=27017,
    username="root",
    password="1234",
)
db = client.get_database("mydb")
collection = db.get_collection("test")

data 조회합니다.

items = collection.find()
[item for item in items]  # 결과 []

Insert Data

데이터 조회를 위해 랜덤 데이터를 생성해서 적재합니다.

import datetime
import random

n = 1000000
names = ["mongo", "python", "docker", "async"]
actions = ["create", "read", "update", "delete"]

base_timestamp = datetime.datetime(2023, 7, 1, 13, 52, 0)
timegaps = list(range(n))
random.shuffle(timegaps)

docs = []
for timegap in timegaps:
    doc = {
        "name": random.choice(names),
        "action": random.choice(actions),
        "value": random.randint(1, 30),
        "timestamp": base_timestamp + datetime.timedelta(seconds=timegap)
    }
    docs += [doc]

results = collection.insert_many(docs)

collection.find_one()
# {'_id': ObjectId('64c50f6340cd550aa4275422'),
#  'name': 'async',
#  'action': 'update',
#  'value': 25,
#  'timestamp': datetime.datetime(2023, 7, 6, 0, 55, 18)}

Find Data

sync/async 데이터 조회를 비교합니다.

sync

(sync) mongo cliect를 선업합니다.

import pymongo

client = pymongo.MongoClient(
    host="0.0.0.0", port=27017, username="root", password="1234"
)
db = client.get_database("mydb")
collection = db.get_collection("test")

name 기반으로 데이터를 조회하는 find_by_name 함수를 작성합니다.

def find_by_name(name):
    items = collection.find(
        {"name": name}, sort=[("timestamp", -1)]
    )
    return list(items)

name 을 list 로 받아 데이터를 조회합니다.

def main(names):
    started_at = time.time()
    for name in names:
        items = find_by_name(name)
    print(f"finished: {time.time() - started_at}")

main(["aync"])
# finished: 1.4455139636993408
main(["aync", "python", "mongo"])
# finished: 4.6754419803619385

async

python에서 mongo async를 지원하는 package motor 설치합니다.

pip install motor

주피터 노트북 환경에서 async 실행시 아래 코드를 먼저 실행합니다.

import nest_asyncio
nest_asyncio.apply()

(async) mongo cliect를 선업합니다.

from motor.motor_asyncio import AsyncIOMotorClient

async_client = AsyncIOMotorClient("mongodb://root:1234@0.0.0.0:27017")
async_db = async_client.get_database("mydb")
async_collection = async_db.get_collection("test")

name 기반으로 데이터를 조회하는 find_by_name 함수를 작성합니다. 아래 두가지 방식 가능

async def find_by_name_async(name):
    cursor = async_collection.find(
        {"name": name}, sort=[("timestamp", -1)]
    )
    docs = []
    async for doc in cursor:
        docs += [doc]
    return docs

async def find_by_name_async(name):
    cursor = async_collection.find(
        {"name": name}, sort=[("timestamp", -1)]
    )
    docs = []
    for doc in await cursor.to_list(length=None):
        docs += [doc]
    return docs

name 을 list 로 받아 asyncio 방식으로 데이터를 조회합니다.

import asyncio

async def main_async(names):
    started_at = time.time()
    await asyncio.gather(
        *[find_by_name_async(name) for name in names]
    )
    print(f"finished: {time.time() - started_at}")

await main_async(["async"])
# finished: 2.0516769886016846
await main_async(["async", "mongo", "python"])
# finished: 4.005278825759888

pymongo find 동작 방식으로는 sync/async 조회 시간에 차이가 없어 보입니다. 추가 내용을 다음에 확인해보겠습니다.

기존 DockerFile

공식 파이썬 이미지를 베이스 이미지로 사용합니다.

FROM python:3.9

이미지 내에서 작업 경로로 이동합니다.

WORKDIR /app

프로젝트에서 사용할 소스 코드를 이미지내 작업 경로로 이동합니다.

COPY . .

프로젝트 파일 실행을 위한 패키지를 설치합니다.

RUN pip3 install -r requirements.txt

앱 파일을 실행합니다.

CMD ["python", "app.py"]

최종 Dockerfile

FROM python:3.9

WORKDIR /app

COPY . .
RUN pip3 install -r requirements.txt

CMD ["python", "app.py"]

비효율적인 순서

소스 코드를 수정하고 이미지를 새롭게 생성하면서 비효율적인 부분이 있었습니다.

대부분의 소스 코드 수정은 전체 코드의 일부 작동 코드를 수정하는 것으로 끝납니다. 이때 동일한 패키지 사용을 유지하면서 일부 수정된 소스코드를 이용해 도커 이미지를 빌드할 때에도 계속해서 requirements.txt를 새롭게 설치하게 됩니다.

Dockerfile 에서 한 줄의 실행으로 하나의 Image Layer를 생성합니다. 이때 Layer의 변화가 없다면 이전에 빌드한 Image Layer 캐시를 재사용해 빌드 시간을 줄일 수 있습니다. Layer에 변경된 부분이 있다면 다음(아래) Layer 부터 캐시 사용 없이 새롭게 실행하게 됩니다.

Layer에 변화 여부를 판단하는 기준은 기본적으로 Dockerfile의 도커 명령어와 다음 인자의 "문자열"을 기준으로 하지만, "ADD" 와 "COPY" 명령어는 추가 또는 복사되는 내용물의 차이를 확인합니다.

기존 Dockerfile에서는 소스 코드가 수정된 후 소스 코드를 이미지 내로 복사하는 COPY . . 실행에서 부터 캐시된 Layer를 사용할 수 없게되면서 이후에 실행 되는 RUN pip3 install -r requirements.txt 부분이 계속해서 재실행되게 됩니다.

수정된 Dockerfile

Dockerfiled의 작은 추가와 간단한 순서 변경으로 해당 문제를 해결할 수 있습니다.

초반은 동일하게 설정합니다.

FROM python:3.9

WORKDIR /app

코드 전체를 옮기는 것이 아닌 requirements 파일만 먼저 이동합니다.

COPY requirements.txt .

프로젝트 파일 실행을 위한 패키지를 설치합니다.

RUN pip3 install -r requirements.txt

패키지 설치 후 프로젝트 파일을 복사합니다.

COPY . .

앱 파일을 실행합니다.

CMD ["python", "app.py"]

최종 Dockerfile

FROM python:3.9

WORKDIR /app

COPY requirements.txt .
RUN pip3 install -r requirements.txt

COPY . .

CMD ["python", "app.py"]

다음 도커 이미지 빌드 부터 requirements 파일 수정이 없다면 기존에 캐싱된 Layer를 이용해 Image가 빌드되어 이미지 생성 시간을 단축할 수 있습니다.

참고자료

• Build your Python image - 공식
• Docker Cache를 통해 build 최적화 하기

CTR 예측에서 사용자의 관심에 대한 연구는 중요한 부분을 차지합니다. 사용자의 관심은 관점에 따라 여러가지고 나뉘는데, 해당 논문에서는 사용자의 리타겟팅 관심에 대해 다룹니다. 리타겟팅 관심이란, 사용자가 이전에 클릭했던 상품들과 같거나 유사한 새로운 타겟 상품에 대한 관심을 의미합니다.

해당 논문에서는 리타겟팅 관심도를 모델링 하는 SRN(Soft Retargeting Network)을 제안합니다. 타겟 삼품과 사용자의 히스토리 상품(클릭된) 사이 유사도를 계산하고, 유사도를 이용해 타겟 상품에 대한 사용자의 클릭을 예측합니다. 이러한 SRN을 통해 성능 향상을 이뤘습니다.

1. Introduction

사용자가 클릭한 히스토리 상품들은 대부분 두 가지 방법으로 추천되었습니다. 사용자가 이전에 방문 페이지를 기반으로 리마인드 시켜주는 리타겟팅 서비스에 의해 추천되었거나 히스토리 행동을 바탕으로 비슷한 상품을 추천해주는 온라인 광고 시스템을 통해 추천된 상품들 입니다. 이렇게 사용자의 최신 관심을 바탕으로 관련도가 높은 상품들을 추천하는 것은 온라인 광고에서 높은 성적을 보입니다. 일반 광고보다 평균적으로 10배 높은 CTR을 보이고, 알리바바에서도 다른 상품들보다 리타겟팅된 상품들이 2배 높은 CTR 성적을 갖습니다. 하지만 일반적인 모델들은 리타겟팅 상품 구분이 불가능해 리타겟팅된 상품들의 CTR이 저평가 되어 클릭과 매출 기회를 잃기 쉽습니다. 해당 논문은 사용자의 리타겟팅 관심을 이용해 CTR 예측 모델링에 사용하는 방법을 제안합니다.

2. Proposed approach

2.1 Hard Retargeting Network

사용자의 리타겟팅 관심을 모델링하는 단순한 방법을 먼저 소개합니다.

리타겟된 상품에 대한 사용자의 관심을 측정하기 위해서, HRN는 단순히 사용자기 이 아이템을 그동안 클릭한 횟수를 이용합니다. 클릭 횟수가 사용자의 관심을 표현하며, 많이 클릭할 수록 높은 관심을 의미합니다. 클릭 횟수를 카테고리컬 피처로 이용해 CTR 예측의 입력값으로 사용합니다.

• target item: $t$
• historical item: $b_j$
• user behavior sequence: $B = {b_1, b_2, …, b_n}$
• similarity weight between target item and historical item: $s(t,b_j) \in [0,1]$
  • $s(t, b_j) = \begin{cases} 1, \ if t=b_j \ 0, \ else. \end{cases}$
• sequence of similarity weights: $S_t = {s(t, b_1), s(t, b_2), … , s(t, b_n)}$

target item: 4
user behavior history: [1, 2, 0, 4, 2, 4, 0, 4, 1, 0]
sequence of similarity weights: [0, 0, 0, 1, 0, 1, 0, 1, 0, 0]

sequence of similarity weights는 타겟 상품에 대한 사용자의 클릭 기록으로 볼 수 있습니다. $S_t$에 Sum Pooling 을 적용해 $N_S$값을 계산합니다. $N_S$는 히스토리 내에서 타겟 아이템을 클릭한 횟수와 같습니다. $N_S$을 binning* 적용을 통해 카테고리 성분인 $FEA_{I_S} = binning(N_S,1)$ 을 만들고, 임베딩 레이어를 통해 $FEA_{I_S}$를 CTR예측 모델의 입력값으로 사용합니다. 이렇게 정의한 HRN 동작은 단순해 보이지만 e-commerce 상황에서 좋은 성능을 보여줍니다.

*binning(x, z): 구간화, 구간 크기가 z가 되도록 x를 이산적으로 나눔

$N_S$: 4
$FEA_{I_S}$: “5”

2.2 Soft retargeting network

HRN에서는 타겟 상품이 이전에 클릭한 상품과 ‘같은’ 경우만 리타겟으로 여기게 되는데 이때 리타겟팅 비율은 매우 제한되어 성능 항상이 제한되는 문제가 생깁니다. 해당 논문에서 제안하는 SRN은 리타겟 상품의 범위를 넓은 레벨로 확장해 위 문제를 해결할 수 있습니다.

SRN의 기본적인 아이디어는 HRN과 유사하며, SRN은 sequence of similarity weights를 먼저 계산하고, 이를 결합해 사용자의 리타겟팅 관심도를 표현합니다. SRN의 주요 컴포넌트는 다음과 같습니다.

Graph Embedding Layer

사용자-상품 상호작용 데이터를 이용해 Pre-train한 그래프 네트워크로 상품에 대한 그래프 임베딩 딕셔너리를 구축합니다.

Similarity Gate Layer

그래프 임베딩 벡터를 이용해 타겟 상품과 행동 상품 사이의 코사인 유사도 $cosine(t, b_j) \in [-1, 1]$를 계산합니다. 하지만 유사도 웨이트는 유저가 느끼는 상품의 유사 정도로 코사인 유사도와 상관관계가 높지만 다를 수 있습니다. 또한 $s(t, b_j) \in [0, 1]$로 코사인 유사도에 변환$F$을 통해 유사도 웨이트를 정의합니다.

$$ s(t, b_j) = F(cosince(t, b_j)) = \frac{\sigma (w * consine(t, b_j) - b)}{\sigma(w-b)} $$

• $F$의 조건
  • 1. $cosine(t, b_j) = 1.0$, 유사도 가중치도 1
  • 2. $cosine(t, b_j) \le T$, 유사도 가중치는 0에 가까움
  • 3. $T < cosine(t, b_j) < 1.0$, 유사도 가중치는 0과 1 사이의 큰 값

경험상 ($w=10, b=9$)가 좋은 초기값이고, CTR 모델이 $F$를 최적화 하도록 학습합니다.

Weight Aggregation Layer

SRN에서는 HRN보다 더 넓은 범위의 리타겟된 상품을 정의할 수 있고, 이후 HRN과 동일한 과정(Sum Pooling과 binning)을 통해 사용자의 리타겟팅 관심을 모델링 할 수 있습니다. 하지만, binning은 미분이 불가능해 유사도 게이트 레이어의 학습을 막게 됩니다.

SRN은 코사인 유사도에 binning을 적용해 카테고리 피쳐인 $FEA_j^{ripple}=binnig(cosine(t, b_j), 0.01)$ 를 정의하고, 임베딩 레어이를 이용해 사용자의 리타겟팅 관심을 표현합니다. (HRN은 $s(t, b_j)$의 Sum Pooling 결과인 $N_S$에 binning 적용) 이는 F의 선형 표현 한계를 보완해 줄 수 있습니다.

$$ I_S = \sum s(t, b_j) * e_j^{ripple} $$

Retargeting Evolution Layer

사용자의 리타겟팅 관심은 시간에 따라 변화합니다. 유사도 가중치가 $S_1$={0.1, 0.5, 0.9} 인 경우와 $S_2$={0.9, 0.5, 0.1} 인 경우를 비교해보면, $S_1$은 타겟 상품에 대한 관심이 증가하고 $S_2$는 관심이 감소하는 차이가 있습니다. 유사도 가중치 시퀀스를 단순히 결합하게 되면 차이가 없기 때문에 이러한 변화를 잡을 수 있도록 ripple 임베딩입력을 받는 GRU 네트워크를 사용합니다.

CTR Prediction Layer

웨이크 어그리게이션 결과와 이볼루션 결과를 결합해 CTR예츨 MLP의 인풋으로 사용 합니다.

3. Experiments

3.1 Setup

데이터 셋

클릭 예측에 적용할 수 있는 데이터를 사용하기 위해 Taobao dataset, Alimama dataset, Industrial dataset 세가지를 이용했습니다.

그래프 구성

각각의 데이터에 대해 HAN (Heterogeneous graph Attention Network)를 Link Prediction 문제로 정의해 Pre-train 임베딩을 구축했습니다. (자세한 설정은 논문 참고)

파라미터

최대 길이를 100으로 하는 시퀀스 데이터 사용하였고, CTR 임베딩은 8차원, 그래프 임베딩은 32차원의 데이터를 이용했습니다.

평가 지표

AUC, Logloss

3.2 performance evaluation

HRN이 DNN 계열보다 견고하고, SRN이 HRN 보다 좋은 성능을 보였습니다. SRN이 더 좋은 성능을 갖는 이유는 리타겟팅 상품으로 판단된 상품 비율이 HRN보다 확실히 많아 성능을 올렸을 것으로 보입니다. 이 후 온라인 A/B 테스트에서도 좋은 결과를 보였습니다.

4. Conclusion

해당 논문에서는 사용자의 리타겟팅 관심을 모델링하는 Soft Retargeting Network를 제안함으로 의미있는 성능 향상을 이뤘습니다.

[2.1 Graph 통계량]과 [2-2. Graph 이웃관계]에 이어서 이후 장들의 기초가 되는 배경지식과 고전적인 Graph ML 방법을 소개합니다. (추가로 수식 전개보다는 결과 성질에 초점을 맞춰 다룰 예정입니다.)

2.3 Graph Laplacians and Spectral Methods

이번 장에서는 Graph에 속한 Node들의 클러스터를 학습하는 방법을 다룹니다. Node들을 저차원 공간으로 임베딩할 수 있는 학습 방법의 기초가 됩니다. 우선 Graph를 푱현하는 여러 중요한 행렬의 정의와 Spectral Graph Theory 스펙트럼 Graph 이론을 간략하게 소개합니다.

2.3.1 Graph Laplacians

Adjacency 인접행렬은 Graph의 정보를 그대로 표현할 수 있습니다. 하지만 Laplacians 이라 불리는 인접행렬을 변형한 다른 행렬 표현방식이 존재합니다.

Unnormalized Laplacian

가장 기초적인 Laplacian 행렬은 Unnormalized Laplacian입니다. $$D$$는 대각선이 각 행 Node의 자유도를 나타내는 자유도 행렬입니다. $$A$$는 인접해렬을 나타냅니다.

$$ L = D - A

L_{i, j} = \begin{cases} d_{v_i}, & \text{if } i = j \ -1 & \text{if } i \neq j \text{ and } (v_i, v_j) \in E \ 0 & \text{otherwise} \end{cases} $$

이 Laplacian 행렬을 중요한 속성을 갖고 있습니다. Positive semi-definite 행렬이고, N개의 음이 아닌 고유값을 가집니다. 중요 속성을 이용하면 다음 정리를 얻을 수 있습니다.

Theoram 2. Laplacian의 고유값 0의 개수는 Graph 안에 연결된 컴포넌트 수와 같습니다.

연결된 컴포넌트에 속한 Node들은 고유벡터의 값이 모두 동일합니다. Fully Connected Graph (완전 Graph)라면 고유값이 0인 경우는 한 가지이며, 이때의 고유벡터는 모든 값이 1인 벡터입니다.

여러 분리된 컴포넌트를 가지는 Graph의 Laplacian 행렬은 원래 Graph 내에서 K개의 Fully Connected Subgraph들의 Laplacian 행렬로 나눌 수 있습니다. 이 경우 고유값 0에 해당하는 고유벡터를 Subgraph의 수 K개 만큼 갖게 되고, 각 고유벡터는 각 컴포넌트의 Indicator가 됩니다.

아래 Graph1에 대해 고유값과 고유벡터를 이용해 컨포넌트 개수를 확인하는 과정의 코드르 추가합니다.

import numpy as np
import networkx as nx

# Graph를 할당합니다.
A = np.array([
    [0, 1, 1, 1, 0, 0],
    [1, 0, 1, 0, 0, 0],
    [1, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0],
])

labels={0: "A", 1: "B", 2: "C", 3: "D", 4:"AA", 5: "BB"}

G = nx.Graph(A)

# Degree Matrix를 할당합니다.
n = A.shape[0]

D = np.zeros((n, n))
for label, degree in G.degree:
    D[label, label] = degree

print(D)
# array([[ 3., -1., -1., -1.,  0.,  0.],
#        [-1.,  2., -1.,  0.,  0.,  0.],
#        [-1., -1.,  2.,  0.,  0.,  0.],
#        [-1.,  0.,  0.,  1.,  0.,  0.],
#        [ 0.,  0.,  0.,  0.,  1., -1.],
#        [ 0.,  0.,  0.,  0., -1.,  1.]])

우선 Graph1을 networkx를 이용해 만들고, Laplacian 행렬을 정의 합니다.

# numpy를 이용해 고유값과 고유벡터를 계산합니다.
eig_value, eig_vector = np.linalg.eig(L)

# float64를 보기 편하게 3자리 소수점으로 반올림합니다.
eig_value = eig_value.round(3)
eig_vector = eig_vector.round(3)

# 고유값을 기준으로 오름차순으로 정렬합니다.
sortidx = np.argsort(eig_value)

eig_value = eig_value[sortidx]
eig_vector = eig_vector[:, sortidx]

numpy를 이용해 Laplacian 행렬의 고유갑과 고유벡터를 계산하고, 고유값이 작은 순서로 정렬합니다. 이때 eig_value[i]에 해당하는 고유벡터는 eig_vector[:. i]로 찾을 수 있습니다.

print(eig_value)
# array([0., 0., 1., 2., 3., 4.])

[Graph1]의 이미지에서 컴포넌트가 2개임을 알 수 있고, 고유값이 0인 경우가 2번인 것도 확인 가능합니다.

print(eig_vector)
# array([[-0.5  ,  0.   , -0.   ,  0.   ,  0.   ,  0.866],
#        [-0.5  ,  0.   , -0.408,  0.   , -0.707, -0.289],
#        [-0.5  ,  0.   , -0.408,  0.   ,  0.707, -0.289],
#        [-0.5  ,  0.   ,  0.816,  0.   , -0.   , -0.289],
#        [ 0.   ,  0.707,  0.   ,  0.707,  0.   ,  0.   ],
#        [ 0.   ,  0.707,  0.   , -0.707,  0.   ,  0.   ]])

각 고유값에 해당하는 고유벡터입니다. 첫번째 열은 0 ~ 3번 행인 Node (A, B, C, D)에 대해 값을 가져 4개의 Node가 하나의 컴포넌트임을 알 수 있습니다. 두번째 열은 4 ~ 5번 행인 Node (AA, BB)에 대해 값을 가져 2개의 Node가 하나의 컴포넌트임을 알 수 있습니다. 위에서 고유값이 0인 경우 원소가 1인 고유벡터를 갖는 다고 했지만, numpy 내에서 벡터의 길이가 1이 되도록 정규화를 하기 때문에 다른 값을 가지게 됩니다.

Normalized Laplacian

정규화를 적용한 Laplacian 행렬도 있습니다.

먼저 Symmetric Normalized Laplacian 입니다.

$$ L_{sym} = D^{-\frac{1}{2}} L D^{-\frac{1}{2}} $$

또 다른 Random Walk Laplacian입니다.

$$ L_{RW} = D^{-1} L $$

2.3.2 Graph Cuts and Clustering

2.3.2에서 고유값 0에 해당하는 고유벡터가 연결된 컴포넌트의 Indicator임을 다뤘습니다. 하지만, 이렇게 연결된 컴포넌트끼리 하나의 클러스터라고 하는 것은 의미가 없습니다. 이번 장에서는 Fully Connected된 하나의 Graph내에서 Node들을 최적으로 클러스터링하는 방법을 소개합니다.

Graph Cuts

가장 먼저 최적 클러스터가 무엇인지 정의해야 합니다. 이를 정의하기 위해 먼저 Graph의 cut을 먼저 정의합니다.

$$A$$는 전체 Node의 부분집합입니다. 이때 $$\bar{A}$$는 $$A$$의 여집합에 해당합니다. Graph의 Node들을 겹치지 않는 K개의 부분 집합인 $$A_1, ... A_K$$로 먼저 정의하겠습니다.

$$ cut(A_1, ... A_K) = \frac{1}{2} \sum^{K}_{k=1} | (u,v) \in E : u \in A_k, v \in \bar{A_k}| $$

cut 이란 단순히 Node 집합들 사이 경계에 걸려 있는 Edge의 수 입니다. 최적 클러스터는 이 cut 의 값을 최소화 하는 것입니다.

하지만 이렇게 할 경우, 하나의 클러스터에 대해 하나의 Node만 남도록 최적화될 수 있습니다. cut 을 최소화 하면서 클러스터의 크기가 적당히 크도록 적용한 것이 RatioCut입니다. 다시말해 클러스터의 크기가 작은 경우 패널티를 부여합니다.

$$ RatioCut(A_1, ... A_K) = \frac{1}{2} \sum^{K}_{k=1} \frac{| (u,v) \in E : u \in A_k, v \in \bar{A_k}|}{|A_k|} $$

다른 방식으로 Nomalized Cut(NCut)이 있습니다. 부분집합에 속한 Node들의 자유도 합이 비슷해지도록 패널티를 부여합니다.

$$ NCut(A_1, ... A_K) = \frac{1}{2} \sum^{K}{k=1} \frac{| (u,v) \in E : u \in A_k, v \in \bar{A_k}|}{vol(A_k)}, vol(A) = \sum{u \in A}d_u $$

위에서 정의한 3가지의 cut 를 최소화하는 것이 최적 클러스터라 할 수 있습니다.

Approximating the RatioCut with the Laplacian Spectrum

Laplacian Spectrum을 이용해 RatioCut 최소화하는 클러스터를 찾는 과정을 근사시킬 수 있습니다.

가장 먼저 Fully Connected Graph를 단순히 두 개의 클러스터 $$A$$, $$\bar{A}$$로 나누는 경우 입니다.

이때는 Laplacian 행렬의 두번째로 작은 고유벡터를 이용합니다. (n번째로 작은 고유벡터란, n번째로 작은 고유값에 해당하는 고유벡터를 의미합니다.) 두번째로 작은 고유벡터를 이용하는 이유는 가장 작은 고유값은 언제나 1이고 고유벡터의 원소들은 모두 동일하기 때문입니다.

두번째로 작은 고유벡터 $$a$$ 에서 원소가 0이상인 Node를 하나의 클러스터, 0보다 작은 Node를 하나의 클러스터로 볼 수 있습니다.

$$ \begin{cases} u \in A, & \text{if } a[u] \ge 0 \ u \in \bar{A} & \text{if } a[u] < 0 \ \end{cases} $$

위 과정을 아래 Graph2에 적용해 보겠습니다.

A = np.array([
    [0, 1, 1, 1, 0, 0],
    [1, 0, 1, 0, 0, 0],
    [1, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0, 1],
    [0, 0, 0, 1, 1, 0],
])

G = nx.Graph(A)

새로운 Graph2를 할당합니다. Laplacian 행렬 생성 과정을 생략하겠습니다.

print(L)
# array([[ 3., -1., -1., -1.,  0.,  0.],
#        [-1.,  2., -1.,  0.,  0.,  0.],
#        [-1., -1.,  2.,  0.,  0.,  0.],
#        [-1.,  0.,  0.,  3., -1., -1.],
#        [ 0.,  0.,  0., -1.,  2., -1.],
#        [ 0.,  0.,  0., -1., -1.,  2.]])

정렬된 고유값과 고유벡터 계산 과정도 생략하겠습니다. Graph2는 완전Graph로 고유값 0을 같는 경우는 한가지 입니다.

print(eig_value)
# array([0.   , 0.438, 3.   , 3.   , 3.   , 4.562])

두번째로 작은 고유벡터 second_smallest_eig_vector 는 아래와 같이 찾을 수 있습니다.

second_smallest_eig_vector = eig_vector[:, 1]
print(second_smallest_eig_vector)
# array([ 0.261,  0.465,  0.465, -0.261, -0.465, -0.465])

클러스터1은 second_smallest_eig_vector가 0 이상인 Node (0, 1, 2)번째에 해당하는 Node (A, B, C)입니다. 클러스터2는 second_smallest_eig_vector가 0 보다 작은 Node (3, 4, 5)번째에 해당하는 Node (D, AA, BB)입니다.

cluster_1 = np.where(second_smallest_eig_vector >= 0)[0]
cluster_2 = np.where(second_smallest_eig_vector < 0)[0]

print(cluster_1)
# array([0, 1, 2]

print(cluster_2)
# array([3, 4, 5])

2.3.3 Generalized spectral clustering

이번에는 위 과정을 확정해 임이의 숫자 K개로 클러스터링 하는 과정을 소개합니다. 이때는 K번째 까지 작은 고유 벡터를 이용합니다.

1. 먼저 가장 작은 벡터를 제외하고 K번째 작은 벡터를 찾습니다.

   K = 3
   k_smallest_eig_vector = eig_vector[:, 1: K]

2. 1번에서 찾은 K-1개의 고유벡터를 이용해 $$U \in R^{|V|\times (K-1)}$$ 행렬을 구성합니다.

   print(k_smallest_eig_vector.shape)
   # (6, 2)
   
   print(k_smallest_eig_vector)
   # [[ 0.261  0.577]
   #  [ 0.465 -0.289]
   #  [ 0.465 -0.289]
   #  [-0.261  0.577]
   #  [-0.465 -0.289]
   #  [-0.465 -0.289]]

3. 각 Node를 행렬 $$U$$의 행들로 표현합니다. $$z_u = U[u], \forall u \in V$$

   node_0 = k_smallest_eig_vector[0]
   
   print(node_0)
   # array([0.261, 0.577])

4. 할당된 $$z_u$$를 이용해 K-means 클러스터링에 적용합니다.

이렇게 Graph 내에 있는 Node들을 클러스터링 하는 과정을 다뤘습니다. 마지막 과정은 Node 차원 축소의 모티브로 이후 강의에서 더 다룰 예정입니다.

2.1 Graph 통계량에 이어서 이후 장들의 기초가 되는 배경지식과 고전적인 Graph ML 방법을 소개합니다.

2.2 Neighborhood Overlap Detection

Graph Statistics에서 각 Node / Graph의 Feature 추출을 다루었습니다. 해당 Feature들은 많은 Classification 문제들에 유용합니다. 하지만 Node들 사이의 관계를 나타내기에는 부족해 두 Node 사이에 Edge 유무를 예측하는 Relation Prediction 등의 Task에는 부적절합니다.

이번장에서는 Node 쌍이 연관성을 정량적으로 나타내는 이웃유사도 Neighborhood Overlap과 관련된 통계값을 다루겠습니다.

가장 단순히 두 Node가 공유하는 이웃 Node 수로 판단할 수 있습니다.$$N(u)$$는 Node u의 이웃 Node 집합을 의미합니다. 이때 $$S \in R^{|V| \times |V|}$$ 는 Pairwise Node 통계량을 요약하는 Similarity Matrix라고 합니다. $$Edge(u, v)$$의 가능도는 $$S[u,v]$$에 비례합니다.

$$ S[u,v] = |N(u) \cap N(v)| $$

ML 문제로 Setting하는 과정은 다음과 같습니다. 학습 시에 전체 Edge 셋의 일부만 알고 있다고 가정해 학습합니다. 나머지 보지않은 Edge를 이용해 모델의 성능을 평가합니다.

2.2.1 Local Overlap Measures

Local Overlap은 단순히 두 Node의 공통 이웃 Node 수를 이용합니다. 정규화 과정을 통해 자유도가 큰 Node에 편향을 줄여주는 것이 필요합니다.

Sorensen Index

Sorensen Index는 각 Node의 자유도의 합으로 나눠 정규화할 수 있습니다.

$$ S_{Sorensen}[u,v] = \frac{2|N(u) \cap N(v)|}{d_u + d_v} \in R^{|V| \times |V|} $$

Salton Index

Salton Index는 각 Node의 자유도의 곱으로 정규화 합니다. 두 Node가 모두 같은 Node만을 이웃으로 가질 경우 Similarity는 1이 됩니다.

$$ S_{Salton}[u,v] = \frac{2|N(u) \cap N(v)|}{\sqrt{d_u d_v}} \in R^{|V| \times |V|} $$

Jaccard Overlap

Jaccard Overlap은 두 Node의 이웃 Node 합집합의 수로 나눠줍니다.

$$ S_{Jaccard}[u,v] = \frac{|N(u) \cap N(v)|}{|N(u) \cup N(v)|} \in R^{|V| \times |V|} $$

Resource Allocation Index

앞의 Index들은 대상이 되는 Node의 자유도로 인한 편향을 줄였습니다. 공유하는 공통 이웃 Node의 Inportance도 고려해야합니다. 예를 들어, Social Network에서 A와 B가 공통적으로 연에인을 팔로우하고, A와 다른 C는 일반인 D를 같이 팔로우 하는 경우를 생각해 보겠습니다. A와 B일 가능성보다 A와 C가 친구일 가능성이 더 높다고 볼 수 있습니다. 이처럼 자유도가 클 수록 낮은 중요도를 반영하는 것이 Resource Allocation Index 입니다.

보편적인 정보들보다 특별한 한가지 정보가 더 강력할 수 있습니다.

$$ S_{RA}[v_1,v_2] = \sum_{u \in N(v_1) \cap N(v_2)} \frac{1}{d_u} $$

Adamin-Adar Index

log를 취해서 반영할 수도 있습니다.

$$ S_{AA}[v_1,v_2] = \sum_{u \in N(v_1) \cap N(v_2)} \frac{1}{log(d_u)} $$

2.2.2 Global Overlap Measures

Local Overlap은 매우 효과적인 통계량입니다. 하지만, Local Overlap은 오직 주변 Node의 이웃만 고려한다는 제약이 있습니다. 예를 들어, 아래 [Graph1]에서 Node A와 Node F는 꽤 연결성이 높아 보이지만 앞의 Local Overlap은 0ㅇ이됩니다. 이런 상황을 반영하기 위한 Global Overlap 통계량을 소개합니다.

Katz Index

Katz Index는 가장 기본 Global Overlap Measures 입니다. 단순히 두 Node 사이를 연결하는 모든 길이의 경로의 개수를 계산합니다. 예를 들어, [Graph1]에서 Node A와 F를 생각해 보겠습니다.

1. 길이가 1인 경로: 0
2. 길이가 2인 경로: 0
3. 길이가 3인 경로: 3 (A-D-E-F, A-B-E-F, A-C-E-F)
4. 길이가 4인 경로: 0

위 과정을 길이가 0 부터 무한대까지 모두 계산합니다. Node u와 v사이의 거리가 l 인 경로의 수는 Graph의 인접행렬 A의 l 제곱 행렬 $$A^{l}$$의 $$[u, v]$$와 동일합니다. (관련한 증명 또는 구체적인 설명은 이후에 추가하겠습니다.)

Katz Index는 다음과 같이 표현할 수 있습니다. 이때 $$\beta$$는 양의 실수입니다. 1보다 작은 숫자일 경우 경로의 길이가 길어질 수록 중요도를 낮춤을 의미합니다.

$$ S_{Katz}[u, v] = \sum_{i=1}^{\infty}\beta^{i}A^{i}[u,v] $$

위 무한까지의 합산 과정을 등비급수 수식을 빌려와 정리하면 다음과 같습니다.

$$ S_{Katz}[u, v] = (I - \beta A)^{-1} - I \in R^{|V| \times |V|} $$

# python
import numpy as np

beta = 0.9
A = np.array([
    [0, 1, 1, 1, 0, 0],
    [1, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 1, 0],
    [1, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0, 1],
    [0, 0, 0, 0, 1, 0],
])
I = np.identity(A.shape[0])

np.linalg.inv(I - beta * A) - I

Graph Representation Learning Book의 Chapter2을 번역, 요약, 정리했습니다. 내용에 맞춰 파이썬 패키지 networkx 사용 예시를 추가했습니다.

Graph Representation Learning과 Deep Learning을 소개하기 전에, 이후 장들의 기초가 되는 배경지식과 고전적인 Graph ML 방법을 소개합니다.

Node와 Graph 분류 문제에 사용할 수 있는 기초 그패트 통계과 Kernel 방법을 먼저 다룹니다. 이후 이웃 Node 사이에 얼만큼 Overlap 겹치는지 나타는 방법을 다루고, 마지막으로 Graph Community Detection 방법으로 유명한 Spectal Clustering을 소개하겠습니다.

2.1 Graph Statistics and Kernel Methods

Machine Learning의 입력으로 사용되는 통계량과 Feature가 필요합니다. Node Level에서 보편적으로 사용하는 통계량에 대해 소개합니다.

2.1.1 Node-level Statistics and Features

Logistic Regression과 같은 Node 분류 모델에 사용될 수있는 통계값과 속성들이 있습니다. 이런 속성값들은 Node들을 구분짓는 값들로 고려돼야 합니다.

2.1.1.1 Node Degree

Node Degree는 하나의 Node를 지나는 Edge의 개수로 자유도라 불리는 가장 명확 값입니다. Node-level ML task에서 가장 의미있는 속성값 중 하나입니다.

$u \in V$의 자유도는 $d_u$로 표현합니다. [이전 장]({% post_url 2021-07-25-GraphML1-introduction %})에서 설명한 인접 행렬에서 $u$에 대한 하나의 열 또는 행의 합산과 같습니다. (Undirected Graph 기준)

$$ d_u = \sum_{v \in V}A[u, v] $$

에를 들어, 아래 Graph에서 Node A의 자유도는 2 입니다.

$$ \text{[Graph1]} $$

아래와 같은 파이썬 코드로도 확인 할 수 있습니다.

import networkx as nx
import numpy as np

adjacency = np.array([
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
])

labels={0: "A", 1: "B", 2: "C", 3: "D"}

G = nx.Graph(adjacency)  # matrix로 Undirected Graph 정의
G = nx.relabel_nodes(G, labels)  # Node 이름 변경
G.degree()
# >>> DegreeView({'A': 2, 'B': 2, 'C': 2, 'D': 2})

2.1.1.2 Node Centrality

Node 자유도는 단순해 표현하기 좋지만 Graph 내에서 Node의 중요도 Importance를 표현하기에는 부족합니다. Node Centrality 중심성으로 알려진 속성값을 고려해야합니다.

1. Eigenvector Centrality
2. Betweenness Centrality
3. Closeness Centrality

가장 많이 알려진 Eigenvector Centrality가 있습니다. Node 주변에 있는 이웃 Node들의 중요도를 이용해 표현합니다. Node $v$의 Eigenvector Centrality는 $e_v$로 표현하고, 이웃 Node들의 평균 Centrality입니다. 이웃 Node의 Centrality가 클 경우, 해당 Node의 Centrality도 커지게 됩니다.

$$ e_u = \frac{1}{\lambda} \sum_{v \in V} A [u, e]e_v \forall u \in V. $$

$\lambda$ 는 하나의 상수값입니다. 모든 Node의 Centrality 벡터 $e$는 아래 처럼 행령식으로 표현할 수 있습니다. 행렬식으로 표현할 경우 Centrality는 $A$의 고유벡터 Eigenvector임을 알 수 있습니다. 가장 큰 고유값 Eigenvalue $\lambda_{\text{max}}$ 에 해당하는 Eigenvector $e_{\text{max}}$를 이용해 Centrality 를 표현합니다.

$$ \lambda e = A e. $$

nx.eigenvector_centrality(G)
# >>> {'A': 0.5, 'B': 0.5, 'C': 0.5, 'D': 0.5}

Betweenness Centrality는 다른 Node들의 최단 경로에 많이 속할 수록 중요함을 나타냅니다.

$$ c_v = \sum_{s \neq v \neq t} \frac{\text{number of shorted paths between s and t that contain v}}{\text{number of shorted paths between s and t}} $$

아래 [Graph1]에서 Node A에 대해서 계산해보겠습니다. A외에 Node는 B, C, D가 있습니다. B-C 사이에 최단 경로는 B-C 하나이고 이중에 A를 지나는 경우는 없어 0입니다. 마찬가지로 C-D 사이에 최단 경로는 C-D 하나이고 이중에 A를 지나는 경우는 없어 0입니다. B-D 사이에 최단 경로는 B-A-C 와 B-C-D 두 개이고 이중에 A를 지나는 경우는 하나로 1/2 입니다. 이 3가지 경우의 합산인 0.5가 A Node의 Betweenness Centrality가 됩니다.

$$ \text{[Graph1]} $$

nx.betweenness_centrality(G, normalized=False)
# >>> {'A': 0.5, 'B': 0.5, 'C': 0.5, 'D': 0.5}

Closeness Centrality는 모든 Node까지의 최단 거리가 짧을 수록 중요함을 나타냅니다. 아래 수식의 분자는 CS224W에서는 1로 되어 있습니다. networkx의 결과와 맞추기 위해 "총 Node 수(n) - 1"로 표현했습니다. 참고

$$ c_v = \frac{n - 1}{\sum_{u \neq v} \text{shortest path length between u and v}} $$

위 [Graph1]에서 Node A에 대해서 계산해보겠습니다. A-B 까지 최단거리 1, A-C 까지 최단 거리 2, A-D 까지 최단 거리 1로 모든 Node에 대한 최단거리 합은 총합 4입니다. 최종 Closeness Centrality 3/4입니다.

nx.closeness_centrality(G)
# >>> {'A': 0.75, 'B': 0.75, 'C': 0.75, 'D': 0.75}

2.1.1.3 Clustering Coefficient

앞의 두 지표는 Node 주변의 Local Structure를 나타내기에는 부족합니다. 예를 들어, 아래 [Graph2]에서 Node $v$는 모두 4개의 다른 Node와 연결되어 있습니다. 하지만 연결된 Node 사이에서 연결된 정도가 다릅니다. 이웃 Node가 서로서로 모두 이웃 Node 일때 Clustering Coefficient는 1이 됩니다.

$$ \text{[Graph2] 출처: CS224W ch2.} $$

아래 수식에서 $N(u) = {v \in V: (u,v)\in E}$는 Node $u$의 이웃 Node Set을 나타냅니다. 아웃 Node들의 전체 연경 경우의 수 대시 실제 연결된 개수를 의미합니다.

$$ c_v = \frac{|(v_1,v_2) \in E: v_1, v_2 \in N(u)|}{d_v \choose 2} $$

아래 [Graph1]은 모든 Node에 대해 이웃 Node끼리 연결되지 않아 0을 갖습니다.

$$ \text{[Graph1]} $$

nx.clustering(G)
# >>> {'A': 0, 'B': 0, 'C': 0, 'D': 0}

2.1.1.4 Closed triangles, ego graphs, and motifs.

Clustering Coefficient 를 보는 또 다른 방법은 각 Node의 Local Neighborhood안에 있는 닫힌 삼각관계의 개수를 보는 것 입니다. Node의 Local Neighborhood는 Ego Graph라고 하기도 합니다.1-Hop Network로 한 층의 Edge로만 연결된 부분 Graph입니다. 닫힌 삼각관계란 Social Network에서 나의 친구가 있고, 친구의 친구가 나와도 친구인 상황입니다.

nx.triangles(G)

삼각관계를 더 일반적으로 표현하면 Graphlet또는 Motifs라고 합니다. 다르게 연결된 Subgraph들로 5개의 Node 연결 종류는 [그림2]와 같습니다.

$$ \text{[그림2] Graphlets 출처: CS224W ch2.} $$

Node가 각 Graphlet에 해당하는 경우의 수를 나열한 벡터인 Graphlet Degree Vector(GDV)로도 표현될 수 있습니다.

이를 좀더 확장하면 Graph Level에서 더 표현하는 방법으로 사용 될 수 있습니다.

1. Degree: 연결된 Edge의 개수
2. Clustering Coefficient: 연결된 삼각관계의 개수
3. GDV: 각 Graphlet의 개수 벡터

2.1.2 Graph-level Features and Graph Kernels

이번에는 하나의 Graph에 대해서 Feature를 추출하는 방식을 소개하겠습니다. Graph Level에서는 Feature Vector 대신 Graph Kernel Method를 주로 사용합니가.

2.1.2.1 Bag of Nodes

가장 간단한 벙법은 Node Level의 통게값을 Aggregation 통합하는 것입니다. 단순히 전체 노도의 개수로 표현할 수 있고, (자유도가 1인 Node의 개수, 2인 Node의 개수, 3인 Node의 개수,,,)처럼 벡터로 표현할 수 있습니다.

이 방법은 Node Level의 Local 정보만 반영해서 만들어지기 때문엔 Grobal 속성 정보는 놓치기 쉽습니다.

2.1.2.2 The Weisfeiler-Lehman Kernel

Bag of Nodes을 이웃 정보를 반복적으로 통합하는 방식으로 발전시켜 사용할 수 있습니다. Ego Graph의 좁은 영역보다 많은 정보를 갖는 Node Level Feature를 발전시켜 Graph Level Feature로 사용합니다.

1. 각 Node의 초기 레이블 $l^{(0)}(v)$을 설정합니다. 단순히 $l^{(0)}(v) = d_v \forall v \in V$ 와 같이 자유도로 할당할 수 있습니다.
2. 새로운 레이블은 이웃 Node의 현재 레이블을 이용해 표현합니다. 이때 현레 레이블 집합으로 Hashing한 새로운 값을 사용합니다. $$ l^{(i)}(v) = HASH({{ l^{(i-1)}(u) \forall u \in N(v) }}) $$
3. Step 2를 K번 반복해 $l^{(K)}(v)$를 할당합니다.

이때 K는 상황에 맞게 직접 설정합니다. $l^{(K)}(v)$는 K-hop(K 거리 만큼 떨어진) 이웃 정보를 요약하게 됩니다. 최종 레이블 값의 분포나 요양 정보를 통해 Graph를 표현하는 데 사용할 수 있습니다. Weisfeiler-Lehman Kernel을 이용해 두개의 Graph에 대해 각각 표현하고, 표현 정보를 이용해 두 Graph의 유사도를 측정할 수 있습니다.

[Graph2]에 대해 1, 2과정을 구체적으로 예시를 들어 보겠습니다. (2, 3, 2)와 (3, 3)은 각각 새로운 값인 4와 5로 할당해주는 과정이 Hashing과정입니다.

$$ \text{[Graph2]} $$

1. $l^{(0)}(A) = 3, l^{(0)}(B) = 2, l^{(0)}(C) = 3, l^{(0)}(D) = 2$
2. $$l^{(1)}(A) = (l^{(0)}(B), l^{(0)}(C), l^{(0)}(D)) = (2, 3, 2) = 4 \l^{(1)}(B) = (l^{(0)}(A), l^{(0)}(C)) = (3, 3) = 5 \l^{(1)}(C) = (l^{(0)}(A), l^{(0)}(B), l^{(0)}(D)) = (3, 2, 2) = 4 \l^{(1)}(D) = (l^{(0)}(A), l^{(0)}(C)) = (3, 3) = 5$$

[Graph2]에 대한 K 1 Weisfeiler-Lehman Kernel의 결과를 WLKernel-1([Graph2]) = (1:0, 2:2, 3:2, 4:2, 5:2) 처럼 표현할 수 있습니다.

2.1.2.3 Graphtlets and Path-based Methods

Node Level을 넘어 Graph Level에서도 Graphlet이라 불리는 Subgraph들의 개수를 이용해 Feature를 만들 수 있습니다. 하나의 Full Graph 안에 각각의 Graphlet이 속한 개수를 이용합니다. 히지만 이 방법은 계산하기 어렵다는 문제가 있어 대략적으로 근사시키는 방법이 사용되기도 합니다.

모든 Graphlet을 세는 대신 Path-based Method를 사용할 수 있습니다. Graph에서 발생할수 있는 경로의 종류로 단순화한 방법입니다. Random Walk Kernel과 Shortest Path Kernel이 이에 속합니다. 해당 방법에 대해서는 3장에서 구체적으로 다룰 예정입니다.

Graph Representation Learning Book의 Chapter1을 번역, 요약했습니다.

Graph는 점과 점을 연결해 관계를 표현할 수 있습니다. 예를 들어, Social Network에서 사람을 하나의 점 Node로, 두 사람이 친구 관계임을 Edge로 표현할 수 있습니다. 생물학에서는 단백질을 하나의 Node, 단백질 사이의 생물학적 상호관계를 Edge로 표현가능 합니다. Graph는 이렇게 각각의 점들의 속성보다는 점들 사이의 관계를 중심으로 합니다.

최근에 많은 Graph Data가 공개되었고, 이 데이터 내에 존재하는 잠재 정보를 밝혀내기 위한 연구가 진행되고 있습니다. 여러 연구 방법 중 한 가지로 Machine Learning을 이용한 방법을 다룰 예정입니다.

1.1 Graph란?

Graph Data는 Node의 집합인 $N$와 Edge의 집합인 $E$를 이용해 $G = (N, E)$로 표현합니다. 하나의 Graph에 속한 Node의 수는 $|N|$, Edge의 수는 $|E|$로 표현합니다. Edge $(u, v) \in E$는 Node $u \in N$에서 Node $v \in N$로 연결됐다는 의미를 가집니다.

인접행렬 Adjacency Matrix $A \in R^{|V|\times|V|}$로 Graph를 표현할 수 있습니다. 모든 Node를 Column과 Row에 나열시키고 연결되어 있으면 1, 연결되지 않은 경우 0으로 표현합니다. 아래 그림처럼 오른쪽 Graph를 왼쪽 행렬과 같이 나타낼 수 있습니다.

import networkx as nx
import numpy as np

adjacency = np.array([
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0],
])

labels={0: "A", 1: "B", 2: "C", 3: "D"}

G = nx.DiGraph(adjacency)
nx.draw(G, labels=labels, node_size=500)

Graph의 Edge가 Undirected인 경우 핸열 $A$는 대칭 행렬 Symmetric Matrix 입니다. 출발 Node와 도착 Node가 구분된 Directed인 경우 대칭일 필요는 없습니다. Weighted Edge인 경우 행렬값은 0과 1 대신 실수값을 갖습니다. 두 Node의 연결 강도를 표현할 경우 사용합니다.

1.1.1 Multi-Relational Graphs

Undirected, Directed, Weighted Edge로 구분하는 것과 별개로 Edge는 여러 종류를 가질 수 있습니다. 예를 들어, 두가지 약 사이의 부작용 관계를 표현할 때 구토, 설사, 고열 등과 같이 여러 종류의 관게를 표현할 수 있습니다. 이 때 Multi-relational Graphs 라고 합니다. Multi-relational Graphs의 일부로 "Heterogeneous Graph"와 "Multiplex Graph"가 있습니다.

Heterogeneous Graph는 Node가 여러 종류로 나뉘는 경우 입니다. 예를 들어, 단백질에 속하는 Node들, 약에 속하는 Node들, 질병에 속하는 Node들로 Graph가 표현되는 경우 입니다. 이때 약 Node와 질병 Node는 "치료" 관계 Edge를 가지고, 약 Node들 사이에는 부작용 관계를 가질 수 있습니다.

Heterogeneous Graph의 일부로 Multipartite Graph가 있습니다. Multipartite Graph는 Bipartite Graph의 확장입니다. Bipartite Graph는 이분 Graph로 Node들이 두 가지 종류로 나뉘고, 같은 종류의 Node들과는 연결되지 않는 Graph입니다. 예를 들어, "유저가 본 영화" 관계 Graph에서 유저와 영화 사이에만 Edge가 있고 영화와 영화를 연결하거나 유저와 유저를 연결하는 Edge는 없습니다. Node의 종류가 세 가지 이상으로 나뉘는 경우 Multipartite Graph라고 합니다.

Multiplex Graph는 Graph가 여러 Layer로 분해될 수 있는 경우 입니다. 예를 들어, 대중 교통 Graph를 생각해 보겠습니다. 출발지와 목적지가 되는 위치 Node들이 있습니다. 위치 Node들 사이에 버스 또는 지하철 등의 Edge가 있을 수 있습니다. 이때 위치를 연결하는 버스 Edge Layer와 지하철 Edge Layer로 나눌 수 있고, 이 경우 Multiplex Graph라고 합니다.

1.1.2 Feature Information

Graph와 관련된 속성 Attribute / Feature 정보를 가질 수 있습니다. 약 Node라면 주요 성분 등이 속성 정보가 될 수 있습니다. Heterogeneous Graph인 경우 종류가 다른 Node라면 다른 종류의 속성값을 갖을 거라고 예상할 수 있습니다.

1.2 Machine Learning on Graphs

Machine Learning은 어떤 문제를 해결하고 싶은지에 따라 모델이 달라집니다. 기본적으로 입력 데이터에 따라 목표하는 결과를 예측하도록하는 Supervised Task와 데이터의 클러스터를 찾는 것과 같은 Unsupervised Task인 경우로 구분할 수 있습니다.

GraphML도 일반적인 방법과 비슷하지만 Supervised인지 Unsupervised인지 별로 중요하지 않습니다. 주로 Supervised 문제이지만, 전통적인 방법 사이에 경계가 모호합니다.

GraphML의 Task는 크게 4가지 단계로 나눌 수 있습니다.

1. Node Level
2. Edge Level
3. Subgraph/Community Level
4. Graph Level

이 중 Classic Graph ML Task를 소개하겠습니다.

1.2.1 Node Classification

Node Level의 한 종류인 Node Classification의 목표는 Node의 Label을 예측하는 것입니다. Label은 어떤 종류인지, 카테고리 인지, 속성인지 등이 해당합니다. 예를 들어, 백만 유저를 가진 Social Network가 있을 때 실제 유저가 아닌 Bot을 분류해 내는 문제가 이에 속합니다. 일부 유저 데이터을 Labeling하고 이를 학습해 전체 유저에 대해 예측할 수 있습니다.

딥마인드에서 개발된 Protein Foldling 문제해결을 위한 AlphaFold가 Node Level 접근의 다른 예시입니다. 단백질 속에 있는 Amino acid들이 Node, Node 사이의 가까움 정도를 Edge로 표현합니다. 그리고 각 Node의 새로운 Position를 예측하고 이를 이용해 3D형태의 단백질 구조를 예측합니다.

표준 Supervised Learning과의 차이점이 있습니다. 가장 중요한 차이점은 Graph의 Node들이 서로 독립이 아니라는 점입니다. iid Set을 가정하고 모델링 하는 대신 Node들 사이의 상호연결을 모델링합니다. 또 다른 차이점은 모델을 학습할 때 Label되지 않은 Test Node들을 사용해 Semi-supervised로 여길 수 있습니다. 하지만 기존 Semi-supervised도 각 Sample에 대해 iid 가정을 하기 때문에 차이가 있습니다.

1.2.2 Relation Prediction

Edge Level의 한 종류로 Relation Prediction이 있습니다. Relation Prediction은 누락된 Relationship 정보를 예측하는 것입니다. 다른 말로 Link Prediction, Graph Completion, Relational Inference로 불리기도 합니다. 우리가 일부 단백질 사이의 관계만을 알고 있을 떄, 누락된 관계를 예측할 때 사용할 수 있습니다. 추가로, 친구들 사이의 Friendship "정도" 예측으로 접근할 수 있고, 약들 사이의 부작용 중 구토, 섩사, 고열 중 "어디에 속하는지" 예측하는 것으로 접근할 수 있습니다.

1.2.3 Clustering and Community Detection

Clustering and Community Detection은 Subgraph Level의 Unsupervised Clustering 방법입니다. 한 개의 입력 Graph $G = (N, E)$가 주어졌을 때, 내부에서 여러 Subgraph로 클러스터링합니다. 유전 작용 네트워크에서 기능별 모듈로 분류하거나, 금융 네트워크에서 사기 단체를 찾아내는 것을 예로 들 수 있습니다.

또 다른 Subgraph Level예시로, Traffic Predition이 있습니다. 전체 교통상황 중 일부인 출발지부터 목적지까지를 하나의 Subgraph로 여길 수 있습니다. 이때 목적지까지 도착하는데 걸리는 시간 ETA를 예측하는 Task입니다.

1.2.4 Graph Classification, Regression, and Clustering

하나의 Graph 안에서 각각의 Component에 대해 예측하는 대신 각각의 Graph에 대해서 독립적으로 예측하는 Graph Level이 있습니다. Graph Classification과 Regression은 하나의 Graph에 대해 목표값을 예측합니다. Graph Clustering은 Graph 쌍 사이의 유사도를 계산해 Grouping합니다. Graph Level에서는 각 Graph를 독립적으로 보기 때문에 표준 ML과 더 유사하다고 할 수 있습니다.