Background
그래프에서 특징 학습
Representation Learning이란 Node Embedding으로 벡터화를 의미한다.
노드를 벡터로 표현하면 다양한 머신러닝 기법에 활용할 수 있다.
노드 간 유사도가 곧 연결 강도로 이어진다.
그래프에서 특징 학습의 목표는 저차원 벡터 공간에 노드를 잘 표현하는 것이다.
벡터화된 노드끼리 비슷한 구조라면 가까운 위치에 있어야 한다.
벡터로 표현한 노드는 이상 탐지, 속성 예측, 클러스터링, 링크 예측 등에 사용된다.
그래프 Embedding의 중요성
예시 1
예를 들어 공공 의료 분야의 경우, 그래프 임베딩으로 단백질 구조를 예측한다.
단백질의 뉴클레오타이드의 서열을 그래프로 표현하고, 그 관계를 그래프 임베딩으로 벡터화하는 것이다.
예시 2
추천 시스템 분야의 경우, 유저와 아이템을 이중 그래프로 표현한다.
그래프 임베딩을 통해 유저-아이템 간 관계를 벡터화하고, 이를 기반으로 추천을 생성한다.
예시 3
네비게이션 시스템 분야의 경우, 도로망을 그래프로 표현한다.
각 노드는 교차로를, 각 엣지는 도로를 의미한다.
각 도로의 상태를 임베딩하여 벡터로 표현하고, 이 벡터는 교통 예측 모델에 입력되어 혼잡도 예측 등에 활용된다.
❌ 그래프 표현의 어려움
그래프는 복잡하다는 문제점이 있다.
이미지는 고정된 행렬로 표현이 가능하고, 텍스트는 순차적인 시퀀스로 표현이 가능하다.
반면 그래프는 노드 번호의 의미가 없고, 구조가 매우 복잡하고 유동적이여서 벡터화하거나 딥러닝에 활용하기가 어렵다.
🛠️ 해결 방법
그래프를 표현하는 가장 단순한 표현 방법은 인접 행렬로 표현하는 것이다.
하지만 문제는 노드 수가 많아지면 행렬의 크기도 커지며 메모리 부담이 커진다는 것이다.
그래서 우리는 차원이 낮은 벡터로 임베딩 하려고 하는 것이다.
직관적인 설명
직관적으로 생각하여 그래프 구조를 벡터 공간에 담는다.
엣지도 연결된 노드들은 벡터 공간에서도 가깝게, 엣지로 연결되지 않은 노드들은 머리 떨어지도록 하는 것이다.
즉, 임베딩 벡터가 원래 그래프의 구조적 의미를 잘 보존해야 한다는 것이다.
그래야 머신러닝이나 딥러닝에서 의미있는 예측이 가능해지기 때문이다.
node2vec : Gro16, KDD
목적함수
Node2vec은 그래프의 노드들을 단어처럼 벡터로 임베딩하는 기법이다.
Node2vec의 목표는 각 노드 u에 대해 이웃 노드들이 주변에 나타날 확률을 최대화하는 것이다.
(실제로는 Skip-Gram 모델 활용)
Ns(u) : 노드 u 주변 이웃들
f(u) : 노드 u의 벡터 표현
📍 Skip-gram 모델
단어 임베딩을 학습하기 위해 널리 사용되는 신경망 기반 아키텍처
문장 내에서 하나의 중심 단어를 기준으로, 그 주변에 위치한 문맥 단어를 예측
📍 데이터 샘플링
Positive Sample : 실제 엣지가 있는 노드 쌍
Negative Sample : 연결되지 않은 노드 쌍
학습 방법
노드 간 skip-gram 모델은 어떻게 만들까?
바로 랜덤 워크를 사용하는 것이다!
→ 노드에서 시작해서 주변을 걸어다니며 시퀀스 생성
여기서 BFS/DFS 전략을 선택적으로 섞어 사용한다.
BFS : 너비 우선 탐색으로 지역 이웃의 구조를 반영한다.
DFS : 깊이 우선 탐색으로 전역 구조를 반영한다.
딥러닝에서 그래프
CNN이나 GAN같은 딥러닝 기법을 그래프에 어떻게 적용할 수 있을까?
GCN : Kip17, ICLR
목적 함수
GCN은 Graph Convolution Network로 라벨이 있는 노드의 분류 성능을 높이기 위해 사용된다.
즉, 그래프에서 노드를 분류하는 데 특화된 딥러닝 모델이다.
: 라벨이 있는 노드들
: 노드 u의 실제 레이블
: 예측 확률 (소프트맥스 출력)
📍 특징
그래프 구조와 노드의 특성을 결합하여 분류한다.
조정 대상
1. 학습 가능한 가중치
오차를 줄이기 위해 조정된다.
2. 노드 임베딩
주변 노드들로부터 정보를 집계하기 위하여 사용된다.
주변 정보를 모으는 방법
핵심 개념은 Message Passing이다.
각 노드는 이웃 노드들의 정보를 받아 자기 임베딩을 갱신한다.
주변 노드들의 특성을 평균이나 합으로 모아서 학습하는데, 이과정을 반복하며 멀리 있는 노드의 정보까지 통합하게 되는 것이다.
즉, GCN은 CNN의 필터처럼 이웃 노드 정보를 받아 내 정보로 만드는 것이다.
ABC : Kan21, ICDM
모델 개요
ABC 모델은 Signed Network (부호 있는 네트워크)에서 커뮤니티 구조를 탐지한다.
균형 이론을 활용해 커뮤니티를 나눈다.
Intra-connection - 같은 커뮤니티 : 연결이 밀도 높고 긍정적인 (+)
Inter-connection - 다른 커뮤니티 : 연결이 드물고 부정적인 (-)
균형 삼각형 : Balanced Triangle
삼각형 구조에서 부호의 일관성을 체크한다.
3개의 노드가 연결된 삼각형 구조에서, 세 노드가 이루는 관계가 이론적으로 예측되는 부호와 일치하면 된다.
일치되면 이 관계를 신뢰할 수 있는 연결이라고 할 수 있는 것이다.
불균형 삼각형 : Unbalanced Triangle
이상한 조합을 찾아서 노이즈 엣지로 판단한다.
세 노드가 삼각형을 이루는데, 예측되는 부호와 실제 부호가 불일치하면 불균형 상태가 되는 것이다.
이런 엣지는 신뢰도가 낮거나, 노이즈일 가능성이 높다.
ABC는 이런 엣지를 제거하거나 무시함으로써 성능을 향상시킨다.
목적 함수
ABC 모델은 생성자와 판별자를 활용한 균형 삼각형 기반 학습 모델이다.
🔸 생성자 G
가상의 균형 삼각형을 만들어내는 역할을 한다.
세 노드가 있다고 가정할 때, 이 세 노드로 구성된 삼각형이 균형 잡힌 관계인지를 스코어로 계산한다.
각각의 경우는 삼각형 내에서의 부호 패턴에 따라 나뉜다.
→ 모두 긍정, 두 긍정 + 하나 부정, 모두 부정 등
→ 이 판별 함수는, 입력된 삼각형의 실제 구조가 이론적으로 균형잡힌 구조인지 판별하는 도구이다.
📍 조정 대상
긍정 쌍 , 부정 쌍
🔸 학습 목표
생성자는 진짜처럼 보이는 균형 삼각형을 생성하는 것이 목표이다.
판별자는 가짜와 진짜 삼각형을 구별하는 것이 목표이다.
생성자와 판별자가 서로 경쟁하며 더 좋은 임베딩을 학습하게 된다.
즉, ABC는 그래프 내의 노이즈 엣지를 줄이고, 커뮤니티 구조를 명확하게 인식하도록 훈련되는 모델이다.
TriCL : Lee23, AAAI
세상에는 pairwise관계 즉, 두 개로 짝 지어진 관계만 있는것이 아니다.
오히려 groupwise 즉, 그룹 기반 관계가 더 많다.
일반적인 그래프는 이런 관계를 표현하기 어렵다.
하이퍼 그래프란?
하이퍼 그래프는 일반 그래프의 확장판이라고 생각하면 된다.
일반 그래프는 엣지 하나에 두 노드만 연결이 되는데, 하이퍼 그래프는 하이퍼엣지 하나가 여러 노드를 한번에 연결한다.
즉, 하이퍼 엣지를 이용하면 그룹 관계 자체를 표현할 수 있는 것이다.
TriCL은 이걸 이용해서 학습한다.
기존 하이퍼그래프 딥러닝 HNN의 한계
1. 라벨링 비용이 높다.
지도 학습 기반으로 동작하기 때문에 무조건 학습 데이터에 라벨링이 되어있어야 한다.
2. 데이터 과적합 위험이 있다.
라벨이 적은데 너무 학습하면 테스트 성능이 떨어지는 과적합이 발생한다.
3. 노이즈에 민감하다.
Negative Sample 즉, 거짓도 학습하는데 이 데이터 하나가 잘못들어오면 결과가 크게 흔들린다.
하이퍼그래프 증강
모델은 하이퍼 엣지를 다양한 형태로 증강해서 contrastive 학습을 한다.
여기서 contrastive learning이란 자가 지도 학습에서 유명한 개념으로, 비슷한 건 가깝게, 다른 건 멀게 만드는 학습 방식이다.
1. Node Feature Masking
노드의 속성 일부를 숨겨서 학습한다.
노드 특성 행렬 X에서 일부 특성을 통채로 0으로 만들어서, 마치 이 노드의 정보가 일부 빠졌다고 가정하고 학습을 하는 것이다.
노드 정보가 불완전해도 의미 있는 표현을 만들게 하기 위해서 진행된다.
2. Membership Masking
노드가 어떤 하이퍼엣지에 속했는지 일부 지워서 학습한다.
incidence 행렬 (인시던스 행렬 - 노드와 엣지 사이의 연결관계를 0과 1로 표현한 행렬) H에서 일부 연결을 끊는다.
즉, 0으로 만들어서 얘가 원래 이 그룹에 있었지만, 지금은 빠진 것처럼 보이게 하기 위해 사용된다.
하이퍼엣지 구조 정보가 불완전해도 잘 학습할 수 있도록 하기 위해 사용된다.
이렇게 두 가지 방식으로 만들어진 두개의 뷰를 가지고 같은 노드는 같은 벡터가 되도록, 다른 노드는 다른 벡터가 되도록 학습한다.
목적 함수
Contrastive Learning을 노드 레벨+그룹 레벨로 동시에 한다.
Node-level Contrast
동일한 노드와 다른 노드를 구분한다.
Group-level Contrast
동일한 하이퍼엣지와 다른 하이퍼엣지를 구분한다.
'CS > 기계학습' 카테고리의 다른 글
| [기계학습] GML - 추천 시스템 (0) | 2025.06.16 |
|---|---|
| [기계학습] GML - Ranking (2) | 2025.06.16 |
| [기계학습] Generative ML (2) | 2025.06.14 |
| [기계학습] RNN (5) | 2025.06.14 |
| [기계학습] 대표적인 CNN 모델 (2) | 2025.06.13 |