논문명

• Controllable Multi-Interest Framework for Recommendation(KDD 2020)

요약

• Taobao 에서 사용하는 추천시스템 프레임 워크인 ComiRec를 소개
• Multi-Interest Extraction 모듈과 Aggregation 모듈을 이용해 실험 데이터, 자사의 산업 데이터셋에서 SOTA 달성
  • Multi-Interest Extraction 모듈: 순차적 추천 문제와 유저의 관심벡터를 포착하기 위한 전략으로 Dynamic Routing Method(캡슐 네트워크), Self-Attention Method를 제안
  • Aggregation 모듈: 추출한 관심 벡터로 부터 아이템 pool에서 추천 목록을 Aggregation하는 Module

2. Introduction

• 추천 시스템은 이커머스 회사의 기본적으로 사용되고 전통적인 추천 방법은 CF, 최근에는 뉴럴넷 기반의 방법론이 널리 사용됨

• 뉴럴넷 기반 추천 시스템은 사용자 및 아이템에 대한 다양한 표현을 생성하고 기존의 추천 성능을 능가함

• 그러나 대규모 사용자 및 아이템 데이터가 존재하므로 각 사용자의 쌍과 아이템 간의 클릭률을 직접 예측하는 모델을 사용하기는 어려움

• 기존 추천 방법론에서의 순차적 추천 방식 문제점이 있음을 주장

  GraphSAGE 기반의 그래프 임베딩 방법을 이용한 사용자, 아이템 표현 학습도 사용되나, 사용자 행동의 순차 정보가 잘 반영되지 않고 사용자 행동 간의 상관관계를 잘 표현할 수 없다고 주장

  기존 RNN기반 순차적 추천 문제점은 하나의 관심사만 포착한다는 것 따라서 해당 논문에서는 단순히 하나의 관심사가 아니라 여러 관심사를 나타내는 추천하는 방법론을 제시

• 이 논문에서는 ComiRec이라는 Controllable Multi-interest 추천이 가능한 프레임워크를 제안함

  • 1. Multi-Interest Extraction 모듈 사용자의 여러 관심을 포착 할 수 있고 이를 후보 아이템검색에 사용
  • 2. Aggregation 모듈 여러 관심사에서 추천에 사용할 최종 아이템 N개를 추리는 과정

    

  • 여러 관심사가 있는 이커머스 유저 Emma가 있고, Emma의 클릭 시퀀스 정보를 구성

  • Multi-interest Extraction 모듈은 해당 시퀀스 정보를 통해 보석, 메이크업, 핸드백 관심을 포착 할 수 있음

  • Nearest Neighbors 알고리즘을 통해 대규모 아이템 풀에서 유사 아이템을 뽑아 낼 수 있음

  • Aggregation 모듈은 서로 다른 관심사의 아이템을 결합하고 Emma에 대한 전체 상위 N 개 추천 아이템을 출력

  • Contribution

    • 제어 가능성과 다중 관심 요소를 통합하는 프레임 워크를 제안함
    • 제어가능성의 역할을 조사
    • 두 종류의 Real world challenging 데이터셋에서 SOTA 스코어를 달성

3. METHODOLOGY

Problem Formulation

• 각 사용자에 대해 일련의 사용자 과거 행동 시퀀스 $(e_1^{(u)}, e_2^{(u)}, ..., e_n^{(u)})$가 존재할 때 ($e_t^{u}$: 유저 u에 의한 t번째 아이템 인터렉션)
• 순차적 추천의 문제는 사용자가 상호 작용할 다음 아이템을 예측하는 것
• 산업 추천 시스템은 일반적으로 매칭 단계(상위 N개의 후보 아이템을 검색)와 순위 단계(후보 아이템의 랭킹을 정렬)의 두 단계로 이루어지나, 이 논문은 주로 매칭 단계에서 효율성을 높이는 데 중점을 둠

Multi-Interest Framework

임베딩 품질의 중요성

• 산업 추천 시스템의 아이템 풀은 수십억 개의 아이템으로 구성되기 때문에 매칭 단계는 추천 시스템에서 중요

• 매칭 모델은 사용자 클릭 시퀀스에서 사용자 임베딩을 계산 한 다음 임베딩 값을 기반으로 각 사용자에 대한 후보 아이템

  세트를 검색

• Nearest Neighbor 알고리즘으로 대규모 아이템 풀에서 가장 가까운 아이템을 선택하여 각 사용자에 대한 후보 집합을 생성

• 즉, 매칭 단계의 결정적인 요소는 사용자 과거 행동으로부터 추출된 사용자 임베딩의 품질이 관건

• Multi-Interest Extraction 모듈을 이용해 각 사용자 행동 시퀀스를 Input으로 하여 Multi-Interest를 생성할 수 있음

• Multi-Interest을 추출하기 위한 두 방법 제시

  • 다중 관심 추출 모듈로서 1)동적 라우팅 방법(dynamic routing method)과 2)Self-Attention 방법(self-attentive method)을 제시. 두 방법을 각각 ComiRec-DR, ComiRec-SA로 명명

• 전체 흐름

  • 아이템 ID로 구성된 사용자 행동 시퀀스 데이터가 존재하며, 각 아이템 ID는 아이템 임베딩 벡터로 변환시킴

  • Train 과정에서 Sampled Softmax Loss를 계산하기 위해 대상 임베딩에 가장 가까운 관심 임베딩이 선택

  • 서빙을 위해 각 관심사 임베딩은 가장 가까운 상위 N개 아이템을 독립적으로 검색한다음 집계 모듈에 넣어줌.

  • 집계모듈은 추천 정확도와 다양성의 균형을 고려해 상위 N개 아이템을 추천

    

Dynamic Routing Method

$\hat{e}{j|i}$$= W{ij}e_i$

• $e_i$ : primary layer의 캡슐 i, 즉 아이템 임베딩 값
• $\hat{e}_{j|i}$ : $e_i$를 기반으로 다음 레이어의 캡슐 j를 예측한 것

$c_{ij} = {exp(b_ij) \over \sum_k exp(b_{ik})}$

• $c_{ij}$는 Dynamic Routing 프로세스가 반복되며 결정되는 결합 계수
  • 캡슐 i와 다음 층에 있는 모든 캡슐 사이의 결합 계수의 합은 1이 됨
• $b_{ij}$는 캡슐 i와 j간의 연결 강도

$v_j = squash(s_j) = {||s_j||^2\over 1+||s_j||^2} {s_j\over||s_j||}$, $s_j = \sum_i{c_{ij}\hat{e}_{j|i}}$

• 비선형 squashing 함수는 짧은 벡터가 거의 제로 길이로 축소되고 긴 벡터는 1보다 약간 작은 길이로 축소되로록 보장하기 위해 제안
• $s_j$는 결합계수가 고려된 캡슐 j의 총 입력
• 사용자 u의 출력 관심 캡슐은 행렬 $V_u$ $= [v_1,...v_K]$$\in \R^{d\times K}$로 구성

Self-Attentive Method

• 사용자 u의 특정 관심사에 대한 것을 먼저 생각해보면, 사용자 행동 임베딩 $H \in \R^{d \times n}$(n은 사용자 시퀀스이 길이)이 주어졌을 때, self-attention 을 사용하여 아래의 벡터 a를 얻을 수 있음
• $a = softmax({w_2}^{T}tanh(W_1H))^T$
• 크기가 n인 벡터 a는 사용자 행동의 어텐션 가중치에 따라 사용자 행동의 임베딩을 합산하면 사용자 u에 대한 관심 벡터 $v_u$$=Ha$를 얻을 수 있음
• 사용자의 전체 관심사로 확장하기 위해, 행렬로 표현하면 아래의 Attention Matrix A로 표현됨
• $A = softmax(W{_2}^{T}tanh(W_1H))^T$
• 사용자 관심사 $V_u$의 최종 행렬은 다음과 같이 계산
  • $V_u = HA$

Model Training

• 사용자 관심 임베딩 행렬에 argmax하여 대상 item i 에 해당하는 임베딩 벡터를 선택
• $e_i$: 아이템 i의 임베딩, $V_u$: 사용자 관심 임베딩 행렬
• $v_u = V_u[:,argmax(V_u^Te_i)]$
• 사용자 u가 아이템 i와 상호작용할 가능성을 다음과 같이 구함
  • $P_{\theta}(i|u) = {{exp(v_u^Te_i)} \over {\sum_{k \in I}}exp(v_u^Te_k)}$
• 모델의 목적 함수는 다음과 같은 음의 로그 가능성을 최소화 하는 것
  • $loss = \sum_{u \in U}\sum_{i \in I_u}-logP_{\theta}(i|u)$
• 위의 계산 비용을 줄이기 위한 샘플링 소프트 맥스 테크닉을 이용

Online Serving

• 사용자의 각 관심 벡터는 nearest neighbor library(Faiss)를 사용해 대규모 아이템 항목 풀에서 상위 N 개 항목을 검색
• 여러 관심 분야에서 검색된 항목을 Aggregation Module의 Input으로 넘겨줌

Aggregation Module

Aggregation Module

• 추천시스템의 다양성을 고려하기 위한 요소를 고려한 함수를 정의
• $v_u^{(k)}$는 사용자 u의 K개의 관심 중, k번째 관심 임베딩이며, 계수 λ를 사용하여 추천의 정확성과 다양성의 균형을 맞춤

• inner production proximit을 토대로 아이템과 사용자 관심사의 유사도를 측정
• CATE (i)는 항목 i의 범주, δ (·)는 indicator 함수
• 가장 정확한 경우, 즉 λ=0의 경우 위의 간단한 방법을 사용하여 전체 항목을 얻음
• 가장 다양한 경우(예:λ=∞)의 경우 제어 가능한 모듈이 사용자를 위해 가장 다양한 항목을 찾음

Greedy Inference

• N:추천해 줄 아이템 갯수, M:후보 아이템 집합이 있을 때,
• 각 iteration 단계 마다 Q(u,S)함수를 최대화 하는 아이템 j를 최종 리턴할 결과 집합 S에추가 하는 알고리즘

4. EXPERIMENTS

실험 세팅

• 8:1:1의 비율로 훈련/검증/테스트 데이터 셋 분할
• 각 사용자 u의 행동 시퀀스는 $(e_1^{(u)}, e_2^{(u)}, ..., e_n^{(u)})$로 구성
• 모델은 유저 u의 k개 동작을 사용하여(k+1)번째 동작을 예측하는 문제를 풀게됨. K는1,2,...,(n−1)
• 아마존 Books, Taobao 데이터셋을 사용

• 논문에서 제안한 ComiRec-SA, ComiRec-DR 모델을 여러 최신 모델과 비교 • MostPopular, Youtube DNN, GRU4Rec, MIND

평가지표

Recall • 더 나은 해석을 위해 글로벌 평균 대신 사용자 당 평균을 사용 • $\hat{I}_{u,N}$은사용자 u에 대한 상위 N개 추천 아이템 집합. $\hat{I}_u$는 사용자 u에 대한 테스트 아이템 집합

Hit rate • 추천 아이템에 사용자가 상호 작용한 아이템이 적어도 하나 이상 포함되어있는 비율

Normalized Discounted Cumulative Gain • 랭킹기반 추천시스템에 주로 사용되는 평가지표 • $\hat{i}_{u,k}$는 사용자 u에 대한 k 번째 추천 아이템. Z는 정규화 상수

Quantitative Results

• 다른 모델과 공정하게 비교하기 위해 Aggregation 모듈에서 다양성과 관련된 계수 λ = 0로 설정

• 하이퍼 파라미터K(관심사)가 변경될 때 성능 평가

Controllable Study

다양성 평가

• 단조로움을 피하고 고객 경험을 개선하기 위한 목적으로 다양성에 대한 실험을 진행
• 항목 범주에 따라 다음과 같은 개인 다양성 정의를 사용

• CATE(i) 는 항목 i의 범주, $\hat{i}_{u,k}$는 사용자 u에 대한 j번째 추천 아이템, δ(·)는 지시 함수
• 표5는 다양성의 계수λ를 제어할 때 Amazon 데이터 세트의 모델 성능 평가표
• 계수 λ가 증가하면 추천 다양성이 크게 증가하고 재현율은 약간만 감소함

산업 데이터 셋에 대한 추가 실험

• 모바일 Taobao 앱에서 수집한 산업 데이터 세트에 대해 추가로 실험 진행
• 2,200만개의 아이템,1억4,500만명의 사용자,40억개의 행동이 포함
• 16GB NVIDIA Tesla P100 GPU 사용
• 논문에서 제안한 ComiRec-SA와 ComiRec-DR이 베이스라인인 MIND에 비해 Recall@ 50이 각각 1.39 %, 8.65 % 향상

5. CONCLUSION

• Multi-Interest Extraction 모듈을 사용하여 여러 사용자 관심사를 생성하고 Aggregation 모듈을 사용하여 전체 상위 N 개 항목을 얻을 수 있었음
• 두 종류 데이터 셋에 실험한 결과를 통해 제안한 모델 방식이 타 Baseline모델 보다 우수한 성능을 보임
• 해당 프레임 워크는 Alibaba 분산 클라우드 플랫폼에도 성공적으로 배포
• 실험용 데이터 셋 뿐만 아니라 추가적으로 대규모의 Taobao 산업 데이터 셋에서도 제안한 모델의 성능이 우수함
• 앞으로 메모리 네트워크를 활용한 사용자 모델링을 만들 계획

논문명

• Deep Entity Classification: Abusive Account Detection for Online Social Networks(USENIX Security 2021)

요약

• Facebook 에서의 다양한 Abuse를 탐지하기 위한 기계학습 탐지 시스템 설명
• 소셜 그래프 내에서의 인접노드 피쳐를 Aggregation하는 전략과 Human label과 Approximate label을 적절히 사용하는 모델링 프로세스를 통해 탐지 성능을 개선시킴

2. Introduction & Background

Online Social Network에서의 Abuse Detection 문제

• 매월 20억명이 넘는 활성 사용자가 콘텐츠를 공유하는 소셜 네트워크가 구성됨
• 이러한 방대한 규모로 인하여 경제적, 정치적, 개인적 이익을 위해 플랫폼을 악용하려는 적들이 존재함
• 이러한 적들은 가짜 계정(즉, 실제 사람을 대표하지 않는 계정)을 대량으로 생성해 가입
• 주어진 Online Social Network의 서면 정책 위반한 계정을 악성 계정으로 정의
• 악성 행위로는 스팸, 사기, 선정적인 사진, 폭력 및 테러를 비롯한 커뮤니티의 규범을 위반한 다양한 행위가 있음
• 따라서 확장 가능하고 정확도가 높은 방식으로 악성 계정을 탐지하는 것이 핵심 문제
  • 확장성을 위해서는 수십억명의 사용자, 수십억 건의 일일 행동을 추적해 다양한 부정 행위를 감지할 수 있는 방식이 필요
  • 악성 계정이 일반 고객에 비해 상대적으로 드물기 때문에 Precision을 우선시 하는 시스템이 필요 → 정밀도가 떨어지면 OSN상의 다수 계정에 잘못된 조치를 취하게 됨

기존 탐지 프로세스

Rule-based heurisitcs

• 일반적인 Attacker들이 사용하는 tool, 기술, 리소스를 식별하는 규칙 기반의 Heuristics을 사용
• 1차 방어선 역할
• 예를 들어, 특정 사용자 행동에 대한 Time interval을 측정
• 설계 및 평가가 쉬우나 임계값을 초과하는 경우 무용지물
• 오탐을 피하기 위해 보수적으로 세팅
• Precision이 높으나 Recall이 떨어짐

ML 시스템

• Recall이 개선되고 모델은 과거 레이블을 토대로 일반화가 가능함
• Ground truth 데이터가 많이 필요하고, 실제 일반 고객을 잘 흉내내는 고도화된 악성 계정이 여전히 존재함 → 실제 정상 유저와 활동 특성이 매우 유사한 유저

정리하면, 규칙 기반 휴리스틱 및 기존 ML 시스템은 대다수의 부정 행위를 탐지할 수 있지만, 분류가 어려운 나머지 계정(실제 사용자와 매우 유사하거나, 방어 시스템을 적극적으로 회피하는 계정)을 탐지하지는 못함

3. DEC System 소개

피쳐 추출 전략(DEC)

1. Direct Feature

• 연령, 그룹 구성원 수와 같이 특정 엔터티만의 특성을 나타낸 피쳐
• 다른 ML 분류기에서 효과적으로 활용되는 기능과 수동 조사 중에 유용한 것으로 확인된 기능을 사용
  • 사용자, 그룹, 장치, 사진, 상태 업데이트 및 그룹 게시물 등 Entity type별 Feature

• 모델링에서는 Direct feature를 그대로 사용하지 않는데 두 가지 이유가 있음
  1. 특정 Direct feature의 값이 탐지 결과의 지배적인 역할을 하는 것을 관찰했기 때문
     • 사용자가 글 작성 시 URL을 게시하는지 여부를 피쳐로 사용할 경우를 예시로 들 수 있음
     • 스패머는 일반 사용자보다 게시물에 URL을 포함하는 경우가 많기 때문에 모델의 편향을 일으킴
     • 이렇게 되면 URL을 게시하는 거의 모든 사용자를 악성 계정으로 분류하기 때문에 수많은 오탐이 발생
  2. Direct feature는 공격자의 우회가 쉬움
     • 예를 들어, 공격자는 "게시된 URL"이 Feature임을 알게 되면 탐지를 피하기 위해 URL을 직접 게시하는 것에서 사진에 오버레이로 URL을 넣는 것으로 전환할 수 있음

2. Deep feature

• 인접 노드(2-hop까지)의 Direct fearure를 Aggregation 한 feature를 말함

  • 예시 1. "대상 계정의 친구 들의 평균 나이"는 계정에 대한 Deep feature

  • 예시 2. 사진에 대한 Deep feature는 "사진에 태그가 지정된 사람들의 친구가 가입한 평균 그룹 수"가 될 수 있음

    

  • 그림 2는 Deep feature 추출의 예

    • 가운데 중앙에 위치한 노드(주황색)에서 2-hop 내의 인접 노드를 기반으로 피쳐 추출.
    • 두 노드 사이의 Edge은 친구 관계를 나타냄.
    • 2-hop 내 인접 노드에 대한 피쳐를 집계하므로 Direct feature에 비해 차원이 기하급수적으로 더 커짐

• Deep feature는 인접 노드를 고려한 소셜 그래프에서 대상 노드의 위치를 나타내므로 분류에 유용함

  • 예를 들어, 가짜 계정 탐지에서 딥 피처에 의해 드러날 수 있는 일반적인 패턴은 가짜 계정의 일괄 생성
  • 가짜 계정을 분류할 때 등록 IP 주소와 해당 IP 주소에서 생성된 다른 모든 계정의 Feature가 포함
  • 위 Feature을 사용하여 분류할 때 일괄 계정 등록의 스크립트된 활동을 쉽게 감지할 수 있음
  • 핵심 Idea는 대부분의 Direct feature는 엔터티를 제어하는 사람이 쉽게 변경할 수 있지만, Deep feature의 값은 공격자가 조작하기 어렵다는 것
    • 예를 들어, 계정 연령은 계정 소유자가 제어하고 그룹 구성원은 그룹 관리자가 제어할 수 있음(Direct feature)
    • 반대로 대상 계정과 연결된 엔터티에서 생성된 집계 기능은 변경하기가 훨씬 더 어려움
      • 예를 들어, 사용자의 모든 친구의 나이 평균값을 피쳐로 사용 → 이 값은 변경되기가 어렵고, 특히 친구 수가 많을수록 훨씬 어려워짐
      • 친구의 친구를 면밀히 조사하여 공격자가 그러한 정보를 변경하려고 하는 것은 거의 불가능

Aggregation 방법

• 표 2와 같이 수치적 특징과 범주적 특징에 대해 서로 다른 집계 방법을 사용.

• 연령과 같은 수치적 특성을 집계하기 위해 평균 및 백분위수와 같은 분포에 대한 통계를 계산
• 반면에 국가와 같은 범주형 피처의 경우 비율, entrory, disinct 카테고리 수를 집계
• 세번째 피쳐 타입은 범주형 특성에 대한 수치적 특성의 분포를 집계
  • 예를 들어, Feature는 장치가 Android 운영 체제를 사용하는 경우 대상 계정과 동일한 장치에서 로그인한 계정 수를 집계
• 계산 비용 이슈
  • 이상적으로는 Facebook에서 사용자 작업이 발생할 때마다 새로운 feature 추출 및 분류를 트리거하는 것이지만, 10억 사용자 규모에서는 불가능한 계산이고. (재)분류는 프로덕션에서 실시간으로 트리거되지만 기능 추출 및 집계는 Facebook에서 계정의 경험을 방해하지 않고 비동기식으로 계산됨
  • 특히 소셜 그래프에서 많은 연결이 있는 계정의 경우에는 사용할 인접 노드 수에 제한을 두고, 그 수가 제한 수(=50)를 넘으면 무작위로 샘플링 방법을 사용

라벨 확보 전략

두 가지 데이터 레이블 소스가 있음

Abuse 유형 선택

• Fake, compromised, spam, scam(4가지 유형)의 Abuse 행위를 고려

• 두 가지 이유로 Abuse 유형을 이 네 가지 범주로 나눔

  1. 탐지된 계정은 Facebook의 정책에 따라 각각 고유한 항소 절차를 사용하는 별도의 집행 시스템에서 조치를 취하게 됨

  2. 둘째, 다양한 Abuse 유형의 Positive 샘플은 본질적으로 동질적이지 않음

     예를 들어, 가짜 계정은 주로 스크립트 작성에 의해 구동되는 반면 compromised 계정은 일반적으로 맬웨어 또는 피싱으로 인해 발생

     이러한 계정의 행동 패턴과 사회적 연결은 각 Abuse 유형에 따라 다르므로 서로 다른 "Task"에 적합하다고 판단

1. Approximate label data

1. 사용자 신고

   • Facebook의 사용자는 다른 사용자를 욕설로 신고할 수 있음
   • 이 소스는 noise가 있지만 훈련의 첫 번째 단계에 대한 낮은 정밀도 레이블로 고려하기 적합

2. 규칙 기반 시스템

   • DEC 외에 Facebook에는 다른 기존의 Rule 패턴이 있음
   • 이 Rule 의해 적발된 사용자는 악용 유형별로 분류되어 추가적인 Approximate 라벨 소스로 분류
   • Rule에는 아래와 같은 예가 존재
     • 친구 요청을 너무 빠른 속도로 보내는 사용자
     • 스팸 탐지 시스템에 의해 삭제된 여러 콘텐츠 항목을 가진 사용자
     • 알려진 피싱 도메인에 대한 링크를 배포하는 사용자
   • 규칙 기반 시스템은 전체 악성 계정 레이블의 절반 이상을 차지

3. 발견된 공격

   • 맬웨어 또는 피싱 공격과 같이 OSN에 대한 스크립트 공격은 "wave"가 발생하는 것이 일반적임
   • 이러한 "wave"를 감지하면 관련된 계정의 서명을 식별하고 서명을 첫 번째 단계의 대략적인 레이블로 사용할 수 있음
   • 이 유형은 악성 계정 레이블의 약 10%를 차지

• 위 유형으로 식별된 계정은 대략적으로 악성 계정으로 분류된 것으로 간주. 각 계정의 abuse 유형에 따라 레이블을 또 여러 작업으로 나눕니다.
• 정상 샘플의 경우 검출되지 않은 계정을 무작위로 샘플링
• 접근 방식의 신뢰도 검증을 위해 2번을 통해 얻은 무작위 샘플을 수동 검수를(1번) 맡김 → 라벨링 정밀도는 90% ~ 95% 사이로 상당히 쓸만하다고 판단했음
• 샘플 수 3천만개 → 전체 유저 규모의 2% 미만

2. Human label data

• 1번 단계에서 검출되는 않은 유저를 대상으로 고용된 전문 레이블러가 수동으로 {악성, 정상}에 대한 레이블을 매김
• 이미 여러 단계의 Abuse detection 시스템을 통과한 유저 집합이기 때문에 분류하기에 가장 어려운 악성 계정이 포함되어 있음
• 각 계정에서 여러 신호를 보고 사람이 판단, 정확도는 높지만 비용이 많이 들기때문에 소량으로만 얻을 수 있음(Facebook 소셜 네트워크 계정 수에 비해)
• 샘플 수 24만개 → OSN 규모에 비해 매우 극소량

모델링 전략(MS-MTL)

악성 계정을 탐지 하기 위한 multi-stage 프레임워크를 사용

MS-MTL 프레임워크의 2단계 학습 흐름도

Stage 1: Low Precision Training

• 첫 단계의 목적은 집계된 raw deep feature 고차원 벡터를 저차원 임베딩 벡터로 줄이는 것
• 차원 축소는 approximate label data를 사용한 신경망 모델 학습을 통해 수행(512, 64, 32 hidden size를 갖는 뉴럴넷)
• 각 악성 계정의 하위 유형에 따라(task) 모델을 학습
• 훈련된 신경망의 마지막 은닉층의 출력을 학습된 저차원 임베딩로 사용
• Input
  • 그래프 내의 인접노드(2-hop)에 대한 엔터티 별 Feature를 Aggregation 한 결과(Deep feature)
• Label
  • Approximate label data

Stage 2: High Precision Training

• model : GBDT
• Input
  • 첫 단계에서 얻은 hidden layer의 출력을
• Label
  • human label

두 Step 으로 모델링 전략을 시도한 이유

1. 다양한 악용 유형을 동시에 지원

• abuse 유형은 다양하고 각 유형마다의 모델 학습을 통해 모델에 인코딩된 정보의 양을 늘림
• 기본 가정은 악성 계정과 일반 계정을 구별하는 feature가 abuse 유형 간 상관 관계가 있다는 것을 전제
• 결과적으로, 한 유형을 나타내는 계정이 다른 악성 행동을 보일 가능성이 더 높기 때문에 한 악성 유형에 대해 학습된 지식은 다른 악성 유형을 결정하는 데 도움이 될 수 있음
• 학대 유형에 따라 레이블이 지정된 데이터를 분할하고 각 유형에 대해 별도의 모델을 훈련하는 것과 비교하여 다중 작업 훈련은 관련된 모든 학대 행위를 집합적으로 살펴봄으로써 계정에 대한 전체 그림을 제공합니다. 작업 전반에 걸친 이러한 지식 공유를 통해 특히 소규모 작업의 경우 다중 작업 학습을 사용하여 더 나은 예측 정확도를 달성할 수 있을 것으로 기대합니다.

2. 고차원 특징 벡터를 활용

• 추출한 여러 Deep feature의 경우 차원의 크기가 매우 크므로 차원의 저주를 해결하기 위해 저차원으로 특징 벡터를 축소할 필요성이 있음
• 약 100개의 피쳐 사이즈로 줄였음

3. 레이블의 부족을 극복

• 레이블링 비용이 너무 비싸기 때문에 모든 샘플에 대해 검수를 하는 것은 불가능
• noisy한 레이블도 모델링에 활용했고 실험 결과 유용한 것으로 입증

전체 모델 프로세스 요약

1. Offline Component

• 오프라인 구성 요소에는 Model Train과 Label 처리가 포함
• DEC는 사람의 레이블 지정과 사용자 피드백 처리하는 작업을 모델 학습, 정책 실행 프로세스에 통합
• Facebook에 고용된 레이블링 전담 팀을 꾸림
• 사전 라벨링(proactive labeling) 작업에서는 전문가들은 다양한 감지 신호에 의해 탐지된 계정을 확인하고 샘플을 확보
• 반응적 라벨링(reactive labeling) 작업에서는 사용자가 이의 제기할 때 프로세스가 시작되며 전문가가 해당 계정을 조사하고 항소를 수락하거나(DEC의 관점에서 False Positive) 항소를 거부함(True Positive)
• 두 레이블링 결과는 통합되어 DEC 모델 Trainset으로 제공
• 오프라인 모델 학습은 Online component에서 추출된 Feature와 Offline component에서 얻은 레이블 데이터를 통해 이루어짐
• 테스트 후 업데이트된 모델을 프로덕션에 배포되며 정기적으로 재학습 진행

2. Online Component

• 대상 노드 및 샘플링된 인접 노드에 대한 feature 추출을 진행
• Feature 추출 후 배포된 모델 기반으로 각 계정에 대한 분류 결과를 생성
• 계정이 악의적인 것으로 분류되면 해당 계정에 대해 제재 정책을 시행

4. Evaluation

제안한 방식의 평가를 위해 서로 다른 3가지 모델 시도

1. 행동
   • 유저 행동에 대한 Direct Feature 특성(예: 친구 수)만을 기반으로 계정을 분류(특정 Abuse 유형에 관계 없이)
   • 행동 특징의 수가 상대적으로 적기 때문에 우리는 사람이 레이블을 붙인 데이터 세트로 모델을 훈련시킴
2. DEC-SS
   • Deep feature 추출하지만 MS-MTL 학습 접근 방식을 활용하지 않는 방식 → DEC만 사용
   • 활용 라벨로는 Approximate label 중 Abuse 항목에 하나라도 태깅되면 Postive로 태깅후 사용
3. DEC-MS-MTL
   • 제안한 모든 절차를 다 사용한 방식 → DEC 전용 접근 방식과 MS-MTL을 결합

1. ROC Curves

• 곡선의 모든 지점에서 행동 Direct 피쳐만을 사용한 방식 보다 우수(최대 0.2)
• ROC 관점에서 두 DEC 모델은 유사하게 작동
• 악성 계정의 경우와 같이 데이터 세트가 불균형한 경우(악용 계정보다 양성 계정이 훨씬 더 많음) ROC 곡선은 분류 시스템의 실제 운영 성능, 특히 정밀도, 남용 액세스의 중요한 측정값을 포착하지 못할 수 있음 → 두번째 실험 진행

2. Precision and Recall

• 그림 5는 모델의 정밀도와 재현율을 비교
• 행동 모델은 0.95 이상의 정밀도를 얻을 수 없음
• MS-MTL이 포함된 DEC는 고정밀 작동 지점에서 단일 단계 DEC에 비해 Recall이 0.3 높음

3. Quantiative Assessment: Area Under the (AUC) Curve and Precision / Recall

• 표 5는 세 모델 간의 Precision을 고정한 뒤 Recall을 비교한 것
• 정밀도는 성능 평가를 위한 일반적인 작동 지점인 0.95로 고정
• 행동 모델은 어떤 Recall에서도 0.95의 정밀도를 달성할 수 없어 NA표기
• 단일 단계와 MS-MTL 모델 모두 비슷한 AUC 성능을 갖지만 Recall 두 배 이상 차이남(각각 0.22, 0.50)

4. Results In Production Environment

• DEC(MSMTL 포함)의 설계 및 평가를 기반으로 Facebook의 프로덕션에 모델을 배포
• 배포된 모델의 실제 영향과 수명을 평가하기 위해 시간 경과에 따른 Precision, Recall의 안정성을 살펴봄.

시간이 지남에 따른 Precision 측정

• 모델 Precision에 대한 3일 이동 평균을 측정
• 이전 평가와 마찬가지로 DEC에서 악성으로 분류된 임의의 계정 샘플에 수동으로 사람이 레이블을 지정하여 evaluation dataset을 만듬
• precision이 0.97 아래로 떨어지지 않는 안정적이 성능을 보임을 확인

시간이 지남에 따른 Recall 측정

• FNR = 1-recall 을 고려한 평가
• DEC를 포함한 모든 Abuse 탐지 시스템을 사용했을 때와 DEC가 없었을 경우의 지표를 비교
• 평가 기간 동안 DEC가 없는 FNR은 5.2%인 반면 DEC를 포함한 결과는 3.8%로 27% 개선됨

5. Discussion & Conclusion

모델 운영 후 얻은 교훈과 한계점

Reducing Computational & Human Load

• Facebook 에서 2년 이상 배포하며 사용한 경험에서 여러 교훈과 제한 사항을 확인
• Facebook 규모에서 모든 활성 사용자의 그래프 피쳐를 추출하는 것은 계산적으로 많은 비용이 듬
• 그래프의 대상 노드에서 2-hop 내에서 피쳐 추출과 집계를 위해, 각 사용자마다 수백 또는 수천 개의 인접 노드에 도달해야 함
• DEC의 계산 부하는 Facebook의 글로벌 CPU 리소스의 0.7%에 해당
• 이 문제를 완화하기 위해 이전 기능 추출 결과를 가능한 한 많이 재사용하는 캐싱 전략을 개발
• DEC를 배포한 뒤 많은 양의 악성 계정을 탐지하고 제거하여 글로벌 CPU 사용량은 전보다 개선
• 또한 DEC의 배포는 악의적인 계정 감지에 필요한 총 검토 리소스를 15%에서 20% 사이로 줄였음

Segmentation and Fairness

• 연령 세그먼트, 다른 문화권에 따라서 특정 세그먼트의 오탐율이 높은 모델의 불공정 이슈가 있었음
• 이러한 변동을 줄이기 위한 조치로 Train dataset의 편향을 줄이는 노력을 시도
• 예를 들어, 계정 소유자의 나이를 특성으로 사용하는데 악성 계정의 경우 평균적으로 정상 계정에 비해 나이대가 어리다고 한다면, 이 경우 Train set에서 서로 다른 연령대의 세그먼트 비율을 조절하지 않을 경우 분류기는 청소년이 소유한 계정이 abuse 확률이 높다는 결론을 내려버림
• 이러한 모델의 bias를 방지하기 위해 첫 번째 단계로 우리는 모델에서 연령, 성별 및 국가를 포함한 모든 "직접적인" 사용자 인구통계학적 특징을 제거.
• 다음으로는 전체 소셜 네트워크의 분포와 최대한 가깝게 Train set을 구성하도록 계층 표집 방법을 사용했음
• 특정 대규모 군집을 다운 샘플링하는 것을 기반으로 진행
• 마지막 접근 방식은 Facebook은 오탐 샘플에 대한 주요 세그먼트 정보를 모니터링하고 오탐을 줄이기 위한 모델 개선 전략을 취함

Measuring in an Adversarial Setting

• Abuse Detection 시스템은 본질적으로 악성 계정들의 적대적인 환경(탐지 시스템을 우회하고 속이려는 행위)에서 작동하기 때문에, 모델 변경에 따른 영향을 측정하는 것은 매우 어려움
• 일반적으로 Adversarial adaptation하는 과정은 아래와 같음

1. 공격자는 Facebook을 악용하는 성공적인 방법을 찾습니다.
2. Facebook은 탐지 시스템을 조정하고 공격을 완화합니다.
3. 공격자는 (1)을 다시 달성하거나 리소스 비용이 너무 높아 중지될 때까지 반복합니다. 공격자와 Facebook의 지속적인 노력을 가정하면 위의 사이클은 결국 평형에 도달합니다.

• 공격자와 Facebook의 지속적인 노력을 가정하면 위의 사이클은 결국 평형에 도달합니다.

• 위 Cycle 때문에 배포 중 A/B 테스트를 사용하여 모델의 효과를 적절하게 측정하기가 어려움

  • 예를 들어, 실험 그룹이 너무 작으면 공격자가 변경할 동기가 없기 때문에 3단계에 도달하지 못함. 이 경우 모델의 측정 지표가 실험 그룹에서 좋아 보일 수 있지만 실제 더 광범위하게 출시되고 성능이 저하되면 다시 3단계에 도달하게 됨

• 이 문제를 완화하는 한 가지 방법은 기능 출시에 "홀드아웃 그룹"을 추가하는 것

• 홀드아웃 그룹은 모델에서 Abuse 할 것으로 예측되는 임의의 사용자 샘플

• 탐지 즉시 이러한 계정을 차단하는 대신, 예상대로 악용이 발생했는지 확인

• 모델 평가에는 도움이 되지만 홀드아웃 그룹의 추가 Abuse 행위로 이어질 수 있으므로 이 그룹이 발생시키는 잠재적 영향에 대해 신중하게 평가해야 함. 이러한 이유로 홀드아웃은 모든 유형의 Abuse에 사용되지는 않음

Limitations

DEC는 실제로 악의적인 계정을 감지하는 데 매우 효과적이었지만 개선해야할 사항이 있음.

1. 계산 비용 절감
   • DEC는 특히 인접노드의 Aggregation 계산 비용이 많이듬. 계산 비용을 더 줄이는 것은 적어도 모델 품질을 향상시키는 것만큼 많은 관심을 받고 있는 작업 영역
2. 신호가 약한 계정 탐지
   • DEC의 분류는 Facebook 그래프 내에서 계정의 위치와 연결을 기반 작동하기 때문에, 낮은 수준의 활동 또는 연결을 나타내는 계정은 DEC가 추론을 위해 활용할 신호가 제한적임
   • 그러나 이런 계정이 악용되더라도 본질적으로 Facebook과 사용자에게 미치는 영향은 적기 때문에 위험도는 적음
   • 이러한 저신호 계정을 더 잘 포착하는 기능을 포함하는 접근 방식을 모색하고 있음
3. 해석 가능성
   • DEC의 기계 학습 모델은 DNN의 hidden layer를 이용한 저차원 임베딩 값을 사용하기 때문에 해석 가능성이 부족
   • 이러한 특성으로 인해 DEC의 결정 이면에 있는 추론을 디버그하고 이해하기가 어렵고, 모델을 해석 가능하게 만드는 것을 연구
4. 라벨링 프로세스
   • DEC는 기계 학습 시스템과 마찬가지로 레이블의 품질에 크게 의존함.
   • 대규모의 부정확한 인간 라벨링을 유도하는 공격자는 DEC의 분류를 조작하거나 방해할 수 있음
   • 라벨링 프로세스를 개선하기 위해 지속적으로 노력하고 있음

결론

1. Deep feature를 이용해 Adversarial Adaption에 대응이 되고 효과적인 피쳐를 얻음
2. Human label, 근사 라벨을 2step으로 활용하는 모델 시스템으로 탐지 결과를 개선 시킴
3. 실제 프로덕션 환경에서도 안정적인 성능을 보였으며 2년 동안 수억개의 악성 계정을 탐지, 전체 제재한 27%를 DEC로 탐지하여 제재

CS224W의 Community Structruture in Networks 강의와 Spectral Clutering 강의 부분을 정리한 글입니다.

아래 4가지 알고리즘에 대한 내용을 알아봄

1. Louvain 알고리즘
2. BigCLAM
3. Spectral Clustering
4. Motif-based Spectral Clustering

1. Community Structruture in Networks

Granovetter Theory

• 커뮤니티 탐지는 서로 밀집하게(densely)하게 연결된 노드를 구분하는 것이 목적

Q. 사람들은 개인적인 소개로 구직 정보를 얻을 때 어떻게 정보를 얻을까?

→ 친구보다는 지인을 통해 정보 얻음

친한 친구보다 지인을 통해 직장을 찾는 것은 friendships에 두 가지 측면이 있다는 것을 말함

• (1) Structural : 링크가 어떤 부분을 연결하는가?
• (2) Interpersonal : 어떤 링크가 더 강하고 약한가?

Structural role : Triadic Closure(= High Clustering Coefficients)

a-c보다 a-b가 두 명의 공통 노드를 공유하기 때문에 더 연결될 가능성이 높은 edge 임

Granovetter의 설명(Granovetter Theory)

• 사회 구조의 edge가 연결되는 role은 구조적, 정보적 측면에서 정의
  • Structural
    • 구조적으로 가까운 edge들은 사회적으로도 강하게 연결
    • 서로 다른 네트워크를 연결하는 장거리 edge들은 사회적으로도 약하다
  • Information
    • 구조적으로 가까운 edge 들은 정보가 중복됨
    • 장거리 edge들이 다른 부분에서 새로운 정보를 얻게 해줌(지인)

2. Network Communities

Modularity

• Granovetter Theory에 따르면 Network는 강하게 연결된 노드의 집합

• Nework Communities

  • 내부적으로 연결된 많은 노드들과 몇개의 외부적인 노드들로 이ㅣ루어진 집합

• Modularity Q

  • 노드간의 연결성 나타내는 Metric, 네트워크가 커뮤니티로 얼마나 잘 나뉘어졌는지 측정하는 척도

    $Q = \sum(# of \quad degrees \quad within \quad groups) - (expected\quad #edges\quad within\quad groups)$

  • 위의 Expected term을 찾기 위해 Configure model(null model) 사용

  • Modularity 의 특징은 [-1,1] 구간 값을 가짐

  • 해석은 음수면 서로 상관 관계가 거의 없고, 0.3~0.7정도면 의미있는 커뮤니티 정보라 볼 수 있음

$Q(G,S) = {{1}\over{2m}}\sum_{s \in S} \sum_{i \in s} \sum_{j \in s}(A_{ij}- {{k_ik_j}\over{2m}})$

• 2m 은 normalize constant를 위한([-1,1] 구간으로 만들기 위한) 정규화 상수
• $A_{ij}$는 연결되어 있으면 ? 1 아니면 0

Modularity 는 아래 식으로 다시 나타낼 수 있음(증명 생략)

$Q = {{1}\over{2m}} \sum_{ij}(A_{ij}- {{k_ik_j}\over{2m}}) \delta(C_i,C_j)$

• $A_{ij}$ : 노드 i와 j 사이의 Edge weight
• $2m$ : 그래프 안의 모든 edge weight의 합
• $\delta(C_j,C_j)$ : 두 노드가 같은 커뮤니티면 1, 아니면 0

3. Louvain Algorithm

• 커뮤니티 탐지를 위한 greedy algorithm. 시간 복잡도 O(nlog(n))
• weighted graph에 사용하며 hierarchical community를 찾을 수 있다함
• Large graph 에서 성능이 잘 나온다함
• 두 phase로 이루어진 학습과정을 통해 greedy하게 modularity를 최대화 하는 알고리즘임

non-overlaps 알고리즘 설명

phase1

1) 각 노드가 single community라 생각

2) 노드 i를 어떤 이웃 j의 community에 넣으면 modularity값이 얼마나 증가하는 지 $\Delta Q$를 측정

3) 노드i를 가장 큰 $\Delta Q$를 발생시키는 community 로 이동 시킴

4) $\Delta Q$변화가 없을대까지 phase1를 반복

phase2

1) phase1의 결과 얻은 communities를 모아 single super node를 만듬

• super-node 사이에 하나의 edge라도 있으면 연결
• 두 sper-node 사이에 edge 가중치는 커뮤니티 간 모든 edge 가중치의 합

2) 다시 phase1으로 돌아가 한 개의 community 를 찾을 때 까지 과정을 반복함

4. Dectecting Overlapping Communities : BigCLAM

• 실제 real world graph는 overlapping communities의 형태를 갖는 경우가 많다.
• Overlapping의 경우 인전행렬 또한 겹치는 부분이 존재

overlaps 알고리즘 설명

STEP1.

• Node community affilations에 근거해 graph를 위한 generative model 정의
• Community Affiliation Graph Model(AGM)

STEP2.

• Graph G가 AGM을 통해 만들어졌다는 가정을 가짐
• generated 된 G을 가지도록 최적의 AGM을 찾음 → AGM이 G을 generative 하도록 모델 파라미터 학습
• 위의 과정을 통해 커뮤니티를 찾을 수 있으며 각 파라미터는 노드가 커뮤니티에 얼마나 속하는 지 알려줌

Generative process

• model parameter : $(V,C,N,P_c)$
• $P_c$ : community C의 노드가 각 노드와 연결될 확률
• $P(u,v) = 1- \prod_{c\in M_u and M_v}(1-P_c)$

모델 파라미터(F)가 주어질 때, 그래프(G)가 생성될 확률을 구하고, 이 Likelihood을 최대화 하는 F를 찾음

• $P(u,v)$ : 노드 u, v가 커뮤티티에 동시에 속할 확률
• MLE를 통해 $P$를 최대화하는 F의 파라미터를 찾음

5. Spectral Clustering

Spectral Clustering의 개요

알고리즘은 3단계로 구성

1) Pre-processing

• 그래프를 표현하는 matrix 생성(Degree Matrix, Adejacency Matrix, Laplacian Matrix)

2) Decomposition(행렬 분해)

• matrix의 eigen value와 eigen vector를 계산
• 행렬을 eigen value와 eigen vector 기반으로 저차원으로 mapping

3) Grouping

• 행렬 분해를 통해 얻은 새로운 representation(eigen vector)로 2개 이상 Cluster를 만들고, 각 data point들을 Cluster에 할당

Partitioning 에 대한 용어 및 개념 설명

Graph Partitioning

Q. 어떻게 그래프를 좋은 partition으로 나눌 것인가?

Q. 어떻게 효율적으로 partition을 정의할 것인가?

→ 그룹 내 노드간의 연결을 최대화 하면서 그룹 간 연결을 최소화 하는것이 좋은 Partitioning(일반 군집화 알고리즘의 클러스터링 평가와 일치하는 느낌)

Graph Cuts

• cut : set of edges with one endpoint in each
• $cut(A,B)=\sum_{i\in A, j \in B}W_{ij}$

• minimum-cut
  • 그룹들간의 연결 weight릃 최소화 함
  • cluster 외부의 연결에만 집중하고, 내부의 연결성은 고려하지 않은 문제점이 있음 → Conductance를 고려하여 해결

• Conductance
  • 군집 내부의 연결성을 고려(군집 내 Density를 반영)
  • 각 그룹간의 Density는 상대적이므로 Cut을 각 그룹의 Volume으로 나눠 구함
  • 따라서 더 균형을 갖춘 Partitioning을 할 수 있음
  • 그러나, 최적의 Conductance를 찾는 문제는 NP-Hard

따라서 Conductance를 구하는 과정에서 eigenvalue와 eigenvector를 이용하는 방법을 선택하는 것

Spectral Graph Partitioning

Q. A * X 의 의미?

• A * X의 선형변환은 노드 i의 이웃인 j의 라벨들의 합
• $y_i = \sum_{j=1}^{n}A_{ij}x_j = \sum_{(i,j) \in E}x_j$

Spectral Graph Theory는 Matrix Representing G의 Spectrum을 분석하는 방법

• spectrum : 그래프의 eigenvector $x_i$는 eigen value $\lambda_i$의 크기 순으로 정렬한 것

예시) d-regular graph(모든 노드가 동일 degree를 가진 그래프)

Q. $Ax = \lambda x$에서 $\lambda$와 $x$는 무엇인가?

• $x$를 (1, 1, ... , 1) 벡터라 하자.
• 그러면 $Ax = (d,d,...,d) = \lambda x$이 되고 $\lambda=d$가 됨
• $d$는 $A$의 가장 큰 eigen value이며, $A$가 n by n 행렬일 때, n개의 eigen vecor, value가 나오게 됨

Matrix Representations

• Degree matrix
• Adjacency matrix
• Lapacian matrix
  • eigen value가 음이 아닌 상수
  • eigen vector가 항상 orthogonal

Q. $x^TLx$의 의미?

• $x_i$와 $x_j$의 차이를 제곱한 값의 합

(증명 생략)

$\lambda_2$는 균형있게 파티셔닝 하기 위해 찾은 eigen value

→ 최적의 cut을 찾는 문제는 두 노드간의 차이를 최소화 하는 $y$를 찾는 문제로 바뀌게 됨

정리하면 $(y_i -y_j)^2$를 최소화하는 것이 최적 Cut을 찾는 일임

이는 Laplacian Matrix L의 $\lambda_2$를 찾는 것과 같음

즉, $min(f(y))=\lambda_2$를 만족하는 벡터 $y$는 eigen vector $x$임

→ $\lambda_2$와 eigen vector를 이용한 클러스터링이 conductance(cut criterion)을 최소화 하는 것을 입증한다 함

알고리즘 요약

Q. 어떻게 그래프의 좋은 Partitioning을 정의 할까?

→ 주어진 그래프의 cut criterion을 최소화

Q. 어떻게 Partitioning의 효율적인 구분이 가능할까?

→ 그래프의 eigen value와 eigen vector를 구해 근사정보를 활용한다

최적의 K를 찾는 것은 딱히 최적의 방법은 없고 eigen gap을 최대화 하는 지점을 찾는다함(elbow point 느낌)

Eigen gap : 두 연속적인 eigen value의 차이

$\Delta_k = |\lambda_k-\lambda_{k-1}|$

Motif-based Spectral Clustering

• motif 기반의 Spectral clustering 알고리즘
• motif : recurring, significant patterns of interconnections

motif의 Conductance를 찾는 것 또한 NP-Hard 문제

알고리즘

1. 주어진 그래프 G에서 motif M이 나타나는 edge의 갯수로 wighted graph W를 만듬

2. $W^{(m)}$에 대해 Laplacian Matrix를 구하고 eigen vector와 eigen value를 구함( $\lambda_2$를 구하는 것이 목표)

3. $x$값을 정렬하고 x축을 각 S집합, y축을 Conductance하는 plot을 그림. Conductance가 최소화 되는 지점은 휴리스틱하게 찾음

4. 알고리즘의 결과는 아래의 수식이 보장된다 함. 알고리즘을 통해 찾은 conductance값이 거의 최적 값에 가까움(near optimal)

Reference

https://jxnjxn.tistory.com/69

CS224W: Machine Learning with Graphs

1. Graph Isomorphism을 구분하는 문제

→ agg 과정에서 max pooling이나 mean pooling을 하게 되면, 두 그래프는 같은 결과 값이 나오게 됨

→ 이를 해결하기 위해, Injective function을 agg function으로 사용

injective function : 하나의 Output에 하나의 원소를 mapping하는 함수

→ node의 subtree가 다르면 representation이 달라지게 됨

즉, Injective function을 통해 동형 그래프라도 각 Node의 subtree가 다르면, node representation을 다르게 가져가겠다는 것.

*예시 1) GCN의 Not injective 예시 *

→ GCN은 multi-set을 적용하더라도 injective 하지 않음(mean pooling을 하기 때문)

*예시2) GraphSAGE의 Not injective 예시 *

→ max pooling이기 때문에 노드 개수가 의미 X

• Injective Multi-set function

*Graph Isomorphism Network(GIN) *

→ root에서 sub tree를 내리고 node의 색을 부여해 구분. 이를 통해 동형그래프를 판단. 개수만으로 결정 하는 것이기 때문에 node feature가 존재할 경우에는 큰 의미 없다?

• GIN의 Computation 예시. 아래 방식을 Weisflier-Lehman(WL) Graph Isomorphism Test라 함 → subtree 확인 후 동형그래프면 같은색 아니면 다른 색 부여함

• 그러나 모든 node가 같은 수의 subtree를 가진다면 WL로 구분 불가.
• 여러 task에서 SOTA성능을 보였다하며, node feature가 주어지면 타 알고리즘과 큰 차이가 없다.

2. Vulnrability of GNNs to noise ingraph data

• GNN은 그래프의 노이즈(node feature의 변화, edge 추가/삭제)에 robust 하지 못함

1. Direct attack : target node의 feature/connection 변경
2. Indirect attack : target node의 neighborhood feature/connection 변경

기타 한계 사항으로는 라벨링 데이터 부족, 실제 학습과 테스트의 분포가 다른 이슈가 있다함

3. Node의 Identift aware 문제

문제 1. 같은 이웃구조 → 같은 노드 임베딩 가져야 함 → position aware 문제

문제 2. 다른 이웃구조 가지면 다른 노드임베딩 가져야함

→ Cycle의 length를 고려하지 못하는 문제

즉, Node의 Identify aware task를 말하는 주제

문제 1에 대한 예시

• 노드 v1와 v2의 Computational Graph는 다름

• 노드 v1와 v2의 Computational graph가 같음 → 해결방법? Anchor node를 이용

• s1를 ahchor node로 고려한다면 relative distance를 계산할 수 있음
• 많은 anchor set은 더 정교한 position 정보를 줄 수 있음

Q. GNN은 structure-aware task에서 완벽히 작동? NO!

• Node level, Edge level, Graph level 에서 실패 케이스가 있음

같은 Computational graph 를 가져 structure aware 에 실패한 사례

*1) 사례(Node level) *

*2) 사례(Edge level) *

*3) 사례(Graph level) *

• Inductive Node Coloring을 이용해 structure-aware 문제 해결

• node level사례 외에도 graph, edge level 문제도 해결

Q. 그럼 node coloring 을 사용한 GNN을 어떻게 구축?

→ Heterogenous message passing을 사용(color에 따라)

(vanilla GNN의 경우 하나의 message passing을 사용)

Q. ID-GNN이 Vanilla GNN보다 나은점?

→ 주어진 노드에서 Cycle length가 고려된 임베딩이 가능해짐

→ 좀 더 심플 버전 ID-GNN의 경우, augmented node feature를 사용해(이걸 Cycle count에 사용한다 함) heterogenous message passing 이 필요 없고 연산 빨라짐

ID-GNN summary

1.어떠한 message passing GNNs에 적용가능(GCN, GIN, GraphSAGE)

2. GNN보다 표현력 우수(Cycle count 가능)

3. PyG, DGL등의 GNN 툴을 통해 쉽게 구현 되어있다함

4. Over-smoothing 문제

• GNN Layer를 많이 쌓는다 → receptive field 가 overlap 된다 → 노드 임베딩이 매우 유사해짐 → Over-smoothing 발생

가정 : Raw input graph은 computational graph와 같다 ** **But, 아래의 이유로 가정이 깨짐

1) Feature level

• Input graph의 피쳐 부족 → feature augmentation

*2) Structure level *

• The graph is too sparse → Message Passing 비효율 → Add virtual node/edge
• The graph is too dense → Message passing의 비용이 커짐 → sampling neighbors
• The graph is too large → 위와 비슷하게 cost 문제 발생 → sampling subgraph

feature augmentation

• 노드에 constant(1) 부여 하거나 One-hot 인코딩 하는 방법이 있음 (constant는 표현력의 한게가, one hot인코딩은 unseen node 대응이 안되는 문제가 있음)
• Cycle 정보를 count하기 위한 값을 부여
  • GNN으로 확실하게 학습하기 어려운 구조 정보를 추가(Clustering Coeffcient, Centrality, ...)

• Virtual edge 추가(sparse data일 경우)
  • Adjacency Matrix에 제곱항을 더함 $A+A^2$

5. Scaling up GNN (Large Graph에 GNN을 적용하는 이슈)

Why is it hard?

• 1) 일반적인 sgd학습 어려움 → tabular data와 달리 neighbor끼리 독립적이지 않음( 그냥 단순한 샘플링 불가)
• 2) full batch 처리도 어려움 → GPU의 한계 ;

두가지 방법이 존재

1) 각 mini-batch 안에서 subgraph 에 대한 message passing neighbors sampling cluster GCN

2) feature-preprocessing operation으로 GNN 단순화 시킴

• simplified GCN

K-layers GNN → k-hop neighborhood aggregation 연산

Neighbor Sampling

• 각 hop 에서 H개 이웃만 Sampling

ex) H가 2일때, 1번 하위 노드 끊음

• H의 크기에 따라 trade-off 존재
  • H가 작으면 neighbor agg는 효과적이나 training이 불안정해짐
• GNN layer가 커질수록 Computational cost가 exponential하게 증가하므로 여전히 문제
• random sampling이 쉽고 간편하나 optional 방법이 아님
  • 대안은 중요 노드 위주로 sample 을 선정하는 방법

Subgraph Sampling

• Large graph → sampled subgraph → Layer-wise node embedding

Q. GNN training에 subgraph가 어떤식으로 좋게 작용?

• GNN이 edge를 경유하는 message passing을 통해 동작하는 것처럼, Subgraph 또한 가능한 Original graph 구조의 edge 연결성을 보존하도록 설계됨

Q. 어떤 Subgraph 가 GNN학습에 좋을까?

• Left의 경우 커뮤니티 구조 정보가 남아있으므로 좋은 subgraph의 예시 → Good
• Right의 경우 각 node가 동떨어져 있고 연결 패턴이 사라짐 → Bad

Vanilla cluster-GCN

1. 커뮤니티 탐지 알고리즘으로 Subgraph 생성(Lovain, etc, ...) 단, 그룹간의 edge는 포함하지 않음
2. Layer-wise 노드 임베딩 업데이트

• Vanilla GCN의 한계점
  1. graph(각 subgraph)간의 연결이 제거됨
  2. 커뮤니티 탐지 알고리즘은 전체 노드 중 지엽적인 portion으로 묶어질 수 있음
  3. 샘플된 노드가 전체 그래프 구조를 표현 하는데 충분히 다양하지 않을 수 있음
  4. 단점을 보완한 알고리즘 Advanced Cluster GCN → 미니 배치당 multiple 노드 그룹을 sampling 하고 aggregation하는 방법(자세한 알고리즘 skip)
  5. neighbor sample 보다 Clustering GCN이 계산 효율성이 더 좋다함

Simplifying GCN

• GCN에서 Relu 함수 걷어냄
• 연산효율화는 되었으나 non-linearity 의 한계도 존재(상세 파악필요)
• 그럼에도 여러 GNN모델 못지않은 성능이 나오는데 graph homophily 때문일 것(연결된 노드는 같은 label을 갖는 경향)

GNN Prediction

Node level predction

• $\hat y_v = Head_{node}(h_v^{(L)}) = W^{(H)}h_v^{(l)}$

Edge level prediction

• u,v가 연결되어 있는지 두 가지 방법중 하나를 씀

  1) $\hat y_{uv}=Linear(concat(h_u^{(L)},h_v^{(L)}))$

  2) $\hat y_{uv}=(h_u^{(L)})^Th_v^{(L)})$ → 1-way 버전

  k-way 버전은 multi-head attention 사용

  $\hat y_{uv}=concat(\hat y_{uv}^{(1)}, \cdot \cdot \cdot, \hat y_{uv}^{(k)} )$

Graph level prediction

• $\hat y_G = Head_{graph}({h_v^{(L)} \in \R^d})$

  Head는 max, mean, sum이 될 수 있음(좀 무식한듯?)

  Hierachically하게 node 조합을 나눠 sum 하는 방식도 있음(Diffpool)

graph의 signal 종류

• supervised signals
  • 그래프 외부의 라벨 정보
• unsupervised signals
  • 그래프 안에서 찾을수 있는 정보(ex. link 연결 정보)
• self-supervision → unsupervision learning 에서 supervised learning을 하는 느낌
• 강의 advice로는 node, edge, graph level의 문제에서 좀 더 작은 단위를 먼저 접근하는 것을 추천 → node를 알면 graph에 대해 유추 가능하니

self-supervision 의 예측 요소( 외부 라벨없이)

1) node level : 노드 통계량(클러스터 계수, Pagerank)

2) edge level : link prediction(일부러 일부 노드 숨김)

3) graph level : 그래프 통계량( 두 그래프가 동형인가?)

Setting-up GNN Prediction tasks

Q. train/test/validation set 을 어떻게 나눌까?

random sampling X → 다른 데이터와 달리 샘플끼리 독립적이지 않음(message Passing으로 인해 영향을 미침)

1. Transductive Setting
   • Input 그래프를 전체 사용하고 node label만 split해서 사용
   • tran/test/valid on same graph
   • entire graph 모두 관측 가능(label 정보만 쪼개짐)
   • node/edge prediction에만 적용가능

2. Inductive Setting

• 그래프를 쪼개서 일부는 training 일부는 valid 로 사용
• train/test/valid set on different graph
• multiple 그래프 dataset 사용해야함
• node/edge/graph task 모두 가능

Setting up link prediction

1) 2타입의 edges를 정의

2) train/test/valid split

trainsductive method와 inductive method가 조금 다름

1. inductive split

• 독립 적인 3개의 그래프 안에서 message/supervision edge를 나눔

2.transductive split(link prediction task의 default 세팅임)

• 여러 edge type을 추가한 이유는 training 이후에 supervision edge는 알 수 있게 되므로 message passing에 사용되어야 함.
• 원래 링크 예측 세팅이 tricky하고 복잡하니 다른 paper도 참고하길 권장

Unseen node 처리 방식

1. Inductive learning
   • Ground truth 를 알고있는 data로 모델을 학습한 후, 전혀 새로운 graph에 대해 node와 edge를 추정하는 것
2. Transductive learning
   • Known data로 Supervised learning 하고 연결된 Unknown node와 edge를 Predict하는 방식

Spectral VS Spational 방식

• Spectral : eigenvector 기반 방식, 효율적으로 일반화하는 것이 어려움, 근간 이론은 탄탄, 무방향 그래프만 적용 가능

  → GCN

• Spational : Spatial관계를 고려한 학습(중심노드와 주변노드의 관계)

  → GAT, GraphSAGE, Diffusion을 이용한 알고리즘 다수(하나의 노드에서 이웃노드로 정보 전달할 때, 특정 확률 기반으로 전달)

Autoencoder

• Link prediction 방식등의 task를 부여해 representation learning?
• random walk 의 방법론도 있음

Self-supervised Learning

• Label 데이터 없이 그래프 내부에서 학습하는 SSL의 방법의 예는 아래와 같음
  • Node level : 클러스터링 계수, Pagerank 와 같은 node통계량 예측 문제를 풀게함
  • Edge level : 링크 연결 문제
  • Graph level : 그래프통계량, 두 그래프가 동형인지(구조적 정보)

Data split 이슈

• 일반적인 tabular data, 유클리드 공간에 정의된 data는 서로 독립된 개체 → 그냥 random index로 split해도 큰 상관 X
• 그러나, 그래프안의 노드는 독립적이지 않음(Message Passing에 참여)
  1. Transductive Setting
  2. Inductive Setting

Graph Design 방법

• Shallow Encoder는 Single layer(f)로 구성되어 있고, 이를 통해 node embedding 진행($u$ → $z_u)$, 유사도 계산($z_u^tz_v$)
• Lookup table 형식으로 노드 임베딩 값을 꺼내 사용

Shallow encoder의 한계(Node2vec)

1) 각 node끼리 파라미터 공유 X

• 각 node들은 unique 임베딩 값 가짐(#parameters = #nodes)

2) Inherently "transductive"

• unseen node를 generalize할 수가 없음

3) node attribute feature 사용 X

Deep Graph Encoder

• Shallow Encoder의 한계를 극복하고자, Multi layer로 구성된 Deepencoder를 고려

Encoder(u) = multiple layers of non-linear transformaties of graph structure

• 그냥 딥인코더라 하면 다른 도메인의 딥러닝 모델 구조를 때려박으면 되지않을까 하지만 아래 한계점이 존재함
  • Image/Text에 특화된 아키텍쳐이기 때문에 그래프구조에 적합한지 의문
  • Network의 복잡한 위상학적 구조를 반영하기에 기존 딥러닝 모델을 그대로 쓰기에 한계가 있음
  • Dynamic함

• GNN 개요
  • Input : Adjacency Matrix, Node feature matrix
  • Output : 노드 분류 결과
  • 알고리즘 : Aggregation(이웃 정보)와 Combine(내 정보)의 반복

[출처 : http://www.secmem.org/blog/2019/08/17/gnn/]

→ Agg함수를 이용해 이웃정보를 모으고, Combine하여 자신의 정보를 더해 다음 상태의 자신 임베딩 값을 만들겠다.

• Vanila GNN

  • Aggregation함수, Combine함수

    $h_v^0$: 노드 $v$의 초기 임베딩(=노드피쳐)

    $h_k^v = \sigma(W_k \sum_{{u,v} \in E} {{h_u^{k-1}} \over {|{u,v \in E}|)}} +B_kh_v^{k-1}$

    $W,B$: 학습 파라미터

    $W$에 해당하는 Term(Neighbors aggregation term) : 노드 $v$에 대한 이전 Layer의 이웃도의 임베딩 평균

    $B$에 해당하는 Term(Self-transform term) : 이전 layer의 $v$의 임베딩 벡터

• 여러 GNN모델은 이 Aggregation 함수의 차이가 있는 것

• representation learing?

  • 어떤 task 를 수행할 수 있는 표현을 만드는 것
  • 임베딩이 필요한 이유는 Adjacency Matrix 가 매우 sparse 하기 때문에 computation 측면에서 필요
  • 임베딩의 목적은 원본 Graph 의 유사도와 embedding space에서 유사도를 최대한 유사하도록 학습하는 것

• 임베딩 과정

  1) Define Encoder

  2) Define node similarity function

  3) Similarity(u, v) 최적화

Random walk

• node위를 랜덤하게 걷는 것(random sequence path를 만드는 것)

• $z_u^t z_v$: 네트워크 전체의 Random walk 에서 u와 v가 함께 발생할 확률

  1) node u에서 출발해 v에 방문할 확률 $P_R(v|u)$을 구함(근사 추정)

  2)$P_R(v|u)$을 인코딩하기 위한 임베딩 최적화

• 학습과정

  • node의 neighborhood를 예측하는 방향으로 feature representation을 학습하겠다.

    1) graph의 각 node에서 정해진 길이만큼 random walk 수행

    2) 각 노드의 neighborhood $N_R(u)$를 수집

    3) node u가 주어질 때, 그 node의 $N_R(u)$을 잘 예측하는 방향으로 노드 임베딩 수행

    → $max_z \sum_{u \in N_R(u)}logP(N_R(u)|z_u)$

    
    

• Loss Function

  $L = \sum_{u\in v}\sum_{v\in N_R(u)} -log(P(v|z_u))$

  → random walk 가 동시 발생할 likelihood를 maximize하는 방향으로 학습

  동시에 발생할 likelihood → ${exp(z_u^tz_u)} \over \sum{_n {exp(z_u^tz_n)}}$

  → 의미를 해석해보면 기준 노드 u와 아무 노드 n의 유사도 합 → 분모(작을수록 good)

  → 기준 노드 u와 아무 노드 v의 유사도 합 → 분자(높을수록 good)

  → 이 확률이 높아질수록 Loss가 낮아짐

  → node의 이웃을 잘 예측하고 있음

• 단점 두 노드의 structural role이 비슷하지만 멀리 떨어져 있는 경우, random walk는 fixed size조건으로 neighborhood node를 탐색하기 때문에 한계가 있음 → graph structure 정보를 활용하기 위해 node2vec제안

  
  ### Node2Vec

• random walk 를 일반화하여 탐색하는 알고리즘

• 네트워크 상에서 이웃놀드를 찾아내는 방법을 유연하게 정의해서 그래프 임베딩을 하겠다.

• global/local 구조 어디에 더 집중할 지, 2nd-order 랜덤 워크 사용

  • 1st-order random walk : node-node transition
  • 2nd-order random walk : edge-edge transition

• 그래프의 이웃을 찾는 두 방법

  • BFS : local 구조 중심
  • DFS : global 구조 중심
    • 두 파라미터 조정
      • p : 이전노드로 돌아온 정도
      • q : BFS와 DFS의 비율
        

• 알고리즘 과정

  1) 랜덤 워크 확률 구하기

  2) 각 노드에서 시작하는 길이 i의 랜덤워크를 r번 시행

  3) SGD를 통해 최적화

• 임베딩된 노드 당 $z_i$의 벡터를 아래 sub task에 활용

  • 클러스터링/커뮤니티 탐지 : $z_i$에 대해 클러스터링 적용
  • 노드 분류 : $z_i$를 바탕으로 $f(z_i)$의 target을 예측
  • 링크 예측 : $f(z_i, z_j)$를 바탕으로 (i, j)가 존재하는지 여부 예측, $f$: 임베딩 결과에 평균, 곱, 거리 등의 다양한 연산 적용한 결과
    

• 노드간 유사도를 구하는 방법

  1) Adjacency 기반

  2) Multi-hop 유사도

  3) 랜덤워크 기반(node2vec)

  해결하고자 하는 문제에 적합한 방식 선택하기

  • 노드 분류 문제 : node2vec
  • 링크예측 : multi-hop 유사도

Q. 그래프 전체를 임베딩 시키는 법?

• 크게 3가지 방법이 존재

  1) 각 노드를 임베딩하고, 전체그래프나 서브 그래프에 해당하는 노드들의 임베딩 값을 합하거나 평균 취함

  2) 서브그래프들의 노드들과 연결된 가상의 노드 만들고, 해당 노드를 임베딩

  3) Anonymous walk embedding

  • 가능한 모든 Anonymous walk 조합 구해, 확률분포 형태로 그래프 표현
  • 샘플링 통해 Anonymous walk 분포 근사
  • Anonymous walk 자체를 임베딩

노드 임베딩 학습과정 요약

1. 인코더 정의(네트워크 ↔ 임베딩 맵핑하는 함수)

   • 노드별 임베딩 결과를 담고 있는 행렬 Z를 학습하고, 특정 노드가 주어지면 Z에서 해당 노드의 임베딩 값을 가져오자(embedding lookup)
   • 임베딩 행렬 Z는 (노드 개수 X 임베딩 차원수) 행렬

2. 노드 간 유사도 함수를 정의

   • 예를들어, 얼마나 직접 연결되었는지?, 얼마나 동일한 이웃을 가졌는지?, 네트워크 구조상 비슷한 역할인지?, etc...

3. 원본 네트워크 상에서의 유사도와 임베딩 공간에서의 유사도가 비슷해지도록 모델 파라미터 학습

   → 임베딩 노드간의 $(z_uz_v)$사이 관계가 원본 네트워크 (u, v) 의 유사도를 가장 잘 표현하는 encoder를 찾자.

출처

• CS224W-7.Graph Representation Learning

• 통계적 의존성은 Weak supervision 에서 자연스럽게 발생함
• 그러나 사용자가 직접 상관성을 고려해 라벨함수를 작성하거나 좀 더 정확한 휴리스틱으로 다른 사용자를 강화하기 위해 의도적으로 설계된 라벨 함수를 작성하는 것은 문제
  • 아래의 세 가지 이유로 사용자가 직접 종속성을 지정하는 것은 실용적이지 못함
    1. 비전문가가 이러한 종속성을 지정하기 어려움
    2. 한 라벨 함수에서 많은 라벨을 태깅 하기 위해 조건을 완화하면 종속성 구조가 빠르게 변경될 수 있음
    3. 종속성 구조가 데이터 세트에 따라 다를 수 있음
• 따라서. Data Programming 논문에서의 결합확률 분포의 종속성 구조를 자동적으로 찾아주는 알고리즘

종속성 고려 알고리즘 제안

• 조건부 독립 모델은 각 $x_i, y_i$에 대한 여러 라벨 함수 출력을 연결하는 고차 요소를 포함하여 추가 종속성이 있는 factor graph 로 일반화 하겠다.

• 제시한 일반 모델의 형태는 아래와 같음

  • $P_{\theta}(\Lambda, Y) \propto exp(\sum_i^m\sum_{t\in T}\sum_{s\in S_t}\theta_s^t\phi_s^t(\Lambda_i, y_i))$

  • $T$: 관심 있는 종속성 유형의 집합 = {표준 종속성, 결합 종속성}

  • $S_t:t\in T$ 유형의 각 종속성 유형에 참여하는 label functions의 index number 집합

  • 종속성 정의

    • 1.표준 상관 종속성

      

    • 2.결합 종속성

      더 많은 변수를 포함하는 고차 종속성 고려

      

  • $P_{\theta}(\Lambda, Y)$의 구조를 추정하는 것은 Y가 latent value 이므로 어려움(train 중에도 관측 값으로 사용하지 않으므로 → 즉, ground truth가 없는 상태로 학습한다는 것)

  • 따라서 marginal likelihood $P_{\theta}(\Lambda)$을 구함, 또한 생성 모델의 매개 변수를 공동으로 학습하기 위해 Gibbs 샘플링 이용 → 결합 분포는 복잡하지만 완전 조건부 분포(Full conditional posterior distribution)를 구하기 쉬운 형태로 주어지는 경우 Gibbs 샘플링을 적용하기 용이

    • Gibbs 샘플링에 대한 간단한 설명
      • 즉, 사후 분포는 $P_{\theta}(Y)$인데 깁스샘플링을 통해 사후분포에서 생성 됐을만한 샘플을 만들 수 있음.
      • 샘플 생성은 주어진 데이터로부터 완전 조건부 분포를 통해 할 수 있다.
      • 예를 들어, 라벨 함수가 3개 이면 모수가 세 개 있을 것 $( \theta_1, \theta_2, \theta_3)$이고 아래의 결합 확률 분포로 나타낼 수 있음
      • $P(\theta_1,\theta_2,\theta_3,y) = P(y\ |\ \theta_1,\theta_2,\theta_3)P(\theta_1,\theta_2,\theta_3)$
      • 위 결합확률 분포로 부터 full conditional distribution을 찾는다.
      • $P(\theta_1 | \theta_2,\theta_3,y)$
      • $P(\theta_2 | \theta_1,\theta_3,y)$
      • $P(\theta_3 | \theta_1,\theta_2,y)$
      • 아래의 $t$를 10,000번 반복하면
        • $\theta_1^{\ t+1}$ ~ $P(\theta_1 | \theta_2^t,\theta_3^t,y)$
        • $\theta_2^{\ t+1}$ ~ $P(\theta_2 | \theta_1^{t+1},\theta_3^t,y)$
        • $\theta_3^{\ t+1}$ ~ $P(\theta_3 | \theta_1^{t+1},\theta_2^{t+1},y)$
      • 따라서 최종적으로 아래의 샘플을 얻는다.
      • ${\theta_1^t,\theta_2^t,\theta_3^t}_{t=1}^{10000}$ ~ $P(\theta_1,\theta_2,\theta_3 |\ y)$

  • 목표 함수 최적화 문제를 pseudolikelihood 형태로 나타내면 아래의 식을 최소화 하는 $\theta$를 찾는 문제로 변환

    • pseudolikelihood 정의

      • $given \ random \ variables \ X = x=(x_1,x_2,\cdot \cdot \cdot ,x_n)$
        • $logL(\theta) = \sum log P_\theta(x_i | x_j \ for \ j \ne i ) = \sum_i P_\theta(x_i|x_{-i})$
      • likelihood의 근사치를 구해 효율적 계산을 하고자 할 때 사용

    • pseudolikelihood 식에 $l_1$정규화 항 추가

    • $argmin_{\theta} \ -logP_{\theta}(\bar\Lambda_j \ | \ \bar\Lambda_{\setminus j }) \ + \epsilon||\theta||_1$

    • 위 식을 아래와 같이 전개하면

    • $argmin_{\theta} \ -\sum_{i=1}^m log \sum_{y_i} P_{\theta}(\bar\Lambda_{i,j},y_i \ | \ \bar\Lambda_{i\setminus j }) \ + \epsilon||\theta||_1$ $\quad \quad \quad \quad , \ where \ \ \epsilon \ \ is \ a \ hyperparameter.$

  • 위의 각 $log\sum_{y_i}P_{\theta}(\bar\Lambda_{i,j},y_i \ | \ \bar\Lambda_{i\setminus j })$ 항 에 대하여 아래의 기울기 계산 가능

    ${\partial log\sum_{y_i}P_{\theta}(\bar\Lambda_{i,j},y_i \ | \ \bar\Lambda_{i\setminus j }) \over \partial \theta_s^t } = \alpha - \beta$

    $where \ \ \alpha : = \sum_{i=1}^m\sum_{\Lambda_{i,j},\ y_i} P_{\theta}(\Lambda_{i,j},y_i \ | \ \bar\Lambda_{i\setminus j }) \ \phi_s^t((\Lambda_{i,j},\ \bar\Lambda_{i\setminus j } ),\ y_i)$

    , $\beta := \sum_i^m\sum_{y_i} P(y_i | \bar \Lambda_i) \ \phi_s^t(\bar \Lambda_i, y_i)$

  • 각 라벨 함수 $\lambda_j$에 대해 차례로 최적화하여 충분히 큰 매개변수가 있는 종속성을 선택하고 이를 추정된 구조에 추가하는 알고리즘을 수행

• 알고리즘

  • notation

    • Input
      • $\bar \Lambda \in {-1,0,1}^{m*n}$ : 관측 값
      • $\epsilon$ : threshold
      • 파라미터 $\theta$를 갖는 확률 분포 $P$, 초기 파라미터는 $\theta^0$
      • $\tau$ : epoch size
      • $\eta$ : step size
      • $K$ : truncation frequency
    • Output
      • $D$ :

    

• 같은 노드 사이에는 에지가 없고 가시-은닉 노드 사이에만 에지가 존재하는 무 방향 바이파 타이트 그래프

• 각 노드 마다 weight, bias항 존재
• $X = \left{ x_1, x_2, ... \ x_n \right}$ 에 속한 특징벡터는 높은 확률로 발생 시키고 아닌 것은 낮은 확률로 발생시키는 알고리즘
• RBM은 노드 값에 따라 에너지가 정해지고 에너지가 낮을 수록 발생 확률이 낮음
• 즉, RBM을 잘 학습시키면 원하는 특징 패턴을 높은 확률로 발생시킬 수 있음(원하는 샘플을 높은 확률로 생성할 수 있는 genarative model임)

용어 정의 및 가정

• 학습하고자 하는 매개변수 집합 $\Theta = \left{ W,, a\ ,b \ \right}$

• 모든 노드 값은 0 혹은 1 값을 가진다 가정(e.g. $x = (0, 1 ,1 )^T$, 추후 실수 범위로 확장한 논문도 나옴)

• RBM의 에너지 함수는 아래와 같음

  • $energy(x,h) = -\sum_{i=1}^d a_ix_i-\sum_{j=1}^m b_jh_j-\sum_{i=1}^d\sum_{j=1}^m x_iw_{ij}h_j$

    행렬 표현으로 나타내면 $-a^{T}X - -b^{T}h-X^{T}Wh$

• 위 에너지 식을 이용해 $x$와 $h$가 발생할 확률 계산

  • $P(x,h) = {1 \over Z }exp(-energy(x,h))$
  • Z는 위의 확률을 다 더하면 1이 되도록 하는 역할 $where , Z = \sum_{x}\sum_{h}exp(-energy(x,h))$

• $P(x,h)$의 결합 확률 분포를 이용해 확률 벡터 $x$가 발생할 확률을 아래와 같이 계산

  • $P(x) = \sum_{h}P(x,h) = {1 \over Z }\sum_{h}exp(-energy(x,h))$

• 즉, 알고리즘을 요약하면 RBM은 내부 상태 $\Theta = \left{ W,, a\ ,b \ \right}$ 의 값에 따라 에너지를 품고, 에너지는 샘플의 발생 확률을 규정. 따라서 어떤 샘플은 자주 발생하지만 다른 샘플은 희소하게 발생하게 할 수 있음(스토캐스틱 생성 모델)

학습 과정

• 목적 함수 정의

  • $J(\Theta) = \sum_{x\in X}logP(x)$, 로그의 합으로 표현하는 이유는 언더 플로 방지

    → $\hat \Theta = argmax {\Theta}^{} \sum{x\in X}logP(x)$

    위의 최적 매개 변수를 찾는 것이 목적이나 최적해 찾는 것이 어려움

    따라서 대조 발산 알고리즘을 사용해 근사 해를 구함

• 대조 발산 알고리즘

  • ${\partial logP(x) \over \partial w_{ij}} = \ \ {data} - {model}$

  • 훈련 집합이 이루는 KL-divergence 값과 모델이 이루는 KL-divergence 값의 차이를 근사 화 하는 것이 대조 발산 알고리즘

  • $w_{ij} = w_{ij} + \Delta{w_{ij} } \ \quad \quad = w_{ij} + \rho({data} - {model})$ $\quad , \rho : learning \ rate$ $\cdots (b)$

  • 위의 ${data} - {model}$는 RBM의 스토캐스틱 샘플 발생 능력을 활용해 구함, 샘플 발생 과정은 깁스 샘플링을 따름

    1. $X = (x_1, x_2, ... , x_d)^T$가 입력되었다 가정

    2. 은닉 노드의 값을 스토캐스틱하게 결정($X$가 주어졌다는 가정 하)

       → $P(h_j =1 \ | \ x) = sigmoid(b_j + \sum^d x_iw_{ij})$ $\cdots (ㄱ)$

    3. 아래 식에 따라 $h_j$를 0 또는 1로 결정(총 $m$개 )

       $h_j= \begin{cases} 1, \ \ if \ \ random() < P(h_j = 1 \ | \ x) \ 0, \ \ o.w\end{cases}$ $\cdots (ㄴ)$

    4. 3번에서 은닉 노드 값 $m$개를 샘플링 했다면, 반대로 샘플링 된 은닉 노드 값을 이용해 가시 노드 값 샘플링

       $P(x_i =1 \ | \ h) = sigmoid(a_i + \sum^m h_jw_{ij})$ $\cdots (ㄷ)$

       $x_i = \begin{cases} 1, \ \ if \ \ random() < P(x_i = 1 \ | \ h) \ 0, \ \ o.w\end{cases}$ $\cdots (ㄹ)$

    5. 위 한번 루프를 $CD_1$이라 하고 멈춤 조건에 따라 $n$회 반복 $CD_n$

    • 참고로 식 2, 3번처럼 확률 전개가 가능한 이유는 RBM의 그래프 구조상 같은 종류 노드 끼리는 서로 독립이기 때문

• 알고리즘 요약

  repeat

  for ($X$에 속한 샘플 $x_k$각각에 대해 아래 적용)

  식 (ㄱ), (ㄴ)으로 은닉 벡터 $h$를 샘플링

  식 (ㄷ), (ㄹ)으로 가시 벡터 $x^{'}$를 샘플링

  식 (ㄱ), (ㄴ)으로 은닉 벡터 $h^{'}$를 샘플링

  $x_k$와 $h$로 $_{data}$를 계산

  $x^{'}$와 $h^{'}$로 $_{model}$를 계산

  (b)식을 이용해 $w_{ij}$를 갱신

  until (멈춤 조건)

결론 요약

• RBM의 목적과 사용
  • 주어진 데이터 집합에 속한 특징 벡터는 높은 확률로 발생시키고 아닌 것은 낮은 확률로 발생
  • 차원 축소, 피쳐 임베딩, 오토 인코더 등으로 활용
• 깁스 샘플링, 대조 발산이 필요한 이유?
  • 확률 계산 표본 마다 전부 하게되면 $2^{md}$의 수행 시간이 필요(현실적 불가능)
  • 따라서 근사 해를 구하는 데 대조 발산 알고리즘을 사용한 것이고 이 과정에서 샘플 발생 전개 방법으로 깁스 샘플링을 사용한 것
• 확률 값의 의미?
  • 높은 확률 값은 원하는 샘플 분포를 높은 확률로 발생시킬 수 있다는 것을 의미
  • 따라서 확률을 최대화 하는 방향으로 매개변수 학습$( \hat \Theta = argmax {\Theta}^{} \sum{x\in X}logP(x))$을 진행하는 것
• 생성 모델이란?
  • 벡터 $x$에 대한 확률 분포를 추정하는 비지도 학습을 말함
  • 레이블 정보가 있다면 활용하고 무시해도 된다
  • 즉, $P(x), \ P(x\ |\ y), \ P(x,y)$에 대한 추정
  • 반대로 분별 모델은 지도 학습이며 벡터 $x$에 대한 확률 분포에 관심이 없고 단지 예측에 목적을 둠($P(y \ | \ x)$를 구하는 것)