Learning Stance Embeddings from Signed Social Graphs

본 문서에서는 WSDM에 게재된 Learning Stance Embeddings from Signed Social Graphs 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. 

• Title: Learning Stance Embeddings from Signed Social Graphs
• Authors: John Pougué-Biyong, Akshay Gupta, Aria Haghighi, Ahmed El-Kishky
• Conference: Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining (WSDM) 2023

Stance in Signed Graphs

그래프(graph)는 노드(node)로 표현되는 객체 간의 관계를 표현하는 방식이며, 실세계의 많은 데이터가 그래프로 표현될 수 있습니다. 예를 들어 소셜 네트워크에서 사용자 간 친구 관계, 가상화폐 거래 내역, 논문 인용 정보를 그래프로 나타낼 수 있습니다. 그래프는 간선의 종류에 따라 분류될 수 있는데 객체들의 관계가 + 또는 - 로 부호를 갖는 부호(Signed) 그래프, 부호 그래프와 달리 간선의 종류가 긍정적이다와 같은 한 종류의 관계만을 의미하는 부호 없는(Unsigned) 그래프가 있습니다. 부호 그래프에서의 +는 객체간의 긍정적인(positive) 관계를, -는 객체 간의 부정적인(negative) 관계를 나타냅니다. 긍정적인 관계의 예로는 신뢰, 친구, 팔로우, 부정적인 관계의 예로는 불신, 적대, 친구가 아님을 생각할 수 있습니다.

그림 1. 여러 주제에 대해 관계를 갖는 예시 그래프.

지금까지의 그래프 연구는 부호 없는 그래프를 중심으로 발전해 왔고, 부호 그래프에 대한 연구에서는 간선의 관점보다는 연결된 노드의 임베딩을 이용해 부호를 획일적인 긍정적, 부정적 성격으로 해석했습니다. 하지만, 실세계 상황에서는 객체와 간선이 기존 그래프에서 표현되는 것 이상의 복잡한 의미를 가집니다. 구체적으로, 객체는 어떤 주제(topic)에 대한 입장(stance)을 취합니다. 예를 들어, 국회의원은 다양한 안건에 대해 찬성/반대 의견을 표명합니다. 의원 A와 의원 B가 새로운 환경 정책에 대해 의견이 일치하지만, 개정된 세금 정책에 대해서는 서로 반대되는 입장을 취할 수 있고, 교육 정책에 대해 동일한 입장을 취할 수 있습니다. 이러한 상황을 그림 1과 같이 나타낼 수 있고, 이러한 그래프를 부호 주제 그래프(signed topic graph)라 명명합니다. 지금까지의 부호 그래프 연구에서는 노드 간의 + 또는 - 로 표현되는 간선의 다양한 관점을 고려하지 못했고, 주제에 대해 고려하지 않은 상태로 노드 간의 간선 부호를 이진 분류하는 방식이 주를 이루었습니다. 그래프의 객체 간 관계를 보다 세밀하고 다방면에서 분석함으로써, 유사한 주제에 대한 노드 간의 관계를 유추할 수 있고, 이러한 연구를 통해 실세계 문제를 더욱 잘 해결할 수 있습니다.

본 논문에서는 이처럼 그래프를 주제별로 분할하고, 이에 대한 유저들의 관계성을 노드를 연결하는 간선 관점에서 분석합니다. 또한, 주제 간의 유사도를 통해 기존에 학습하지 않은 주제에 대해서도 유저들의 입장을 예측할 수 있습니다. 구체적인 문제 정의는 다음과 같습니다.

• 주어진 정보
• 부호 그래프 (signed graph): 정점과 간선의 집합
• 정점들의 특징 정보
• 간선의 주제와 부호
• 선택사항: 간선의 방향

• 목표
• 특정 주제의 그래프에서 간선들의 임베딩을 학습

본 논문에서는 그래프의 간선에 부호와 주제 정보가 담겨있는 부호 주제 그래프를 사용합니다. 노드 간에는 다양한 주제에 대한 여러 개의 간선이 존재할 수 있고, 이들의 부호는 + 또는 - 를 갖습니다. 이를 바탕으로 각 주제에 해당하는 간선들만을 이용한 부분 그래프를 추출할 수 있습니다.

Proposed Method

본 논문에서는 주제별 그래프를 통해 각 주제와 간선의 특징 벡터를 학습하는 Stance Embeddings Model(SEM)을 제안합니다. SEM의 핵심 아이디어는 다음과 같이 요약될 수 있습니다.

• SEM은 간선의 부호에 더해 주제라는 새로운 간선 특징을 도입해 사용합니다. 전체 그래프의 노드 간 관계가 주제별로 다를 수 있음을 반영하기 위해 전체 그래프에서 각 주제의 간선만을 남겨, 주제별 부분 그래프를 생성합니다.
• SEM은 random walk를 사용해 소스(source) 노드와 문맥(context) 노드들을 정의합니다. Walk를 통해 선정한 문맥 노드와 소스 노드가 연결되어 있지 않다면, 이들의 관계가 긍정적인지, 부정적인지 균형 이론(balance theory)을 통해 정의합니다. 
• SEM은 노드의 특징 벡터 관점에서 단일한 주제에 대해 간선의 부호를 예측해 온 기존 연구들과 달리, 간선 자체의 임베딩을 구해 간선의 부호는 물론 다른 주제에서의 노드 관계를 유추하는 것을 목표로 합니다. 소스 노드의 임베딩, 주제의 임베딩을 학습하고 균형 이론을 통해 정의된 부호에 맞게 이를 타겟 노드 임베딩과 연산해 간선의 임베딩으로 사용합니다. 또한, 주제에 대한 임베딩이 학습을 통해 얻어지므로 서로 다른 주제들간의 연관성, 서로 다른 주제에 대한 노드들의 입장은 물론 처음 보는 주제에 대한 노드들의 관계성도 예측해 볼 수 있습니다.

다음으로는, 예시 그래프를 통해 SEM 의 제안 방법을 살펴보겠습니다.

1. Edge-attributed graphs에 random walk 수행

그림 2. SEM(Stance Embeddings Model)의 random walk.

 그림 2 오른쪽 그래프는 전체 그래프 중 어떤 주제 t에 대한 간선을 모두 나타낸 부분 그래프입니다. SEM은 각 주제별 부분 그래프를 생성하고 간선의 가중치, 부호를 고려하지 않고 random walk를 수행합니다. random walk는 소스 노드를 기준으로 노드 간의 거리에 따라 다른 확률을 부여해 문맥 노드를 선택하는 과정입니다. 이에 대한 자세한 확률은 논문에 소개되어 있습니다. 위 예시는 소스 노드 B를 기준으로 길이가 2인 random walk를 수행한 결과로, 문맥 노드는 C,A,F,D 로 정의됩니다.

2. 부호가 있는 문맥 노드 관계 생성

그림 3. SEM(Stance Embeddings Model)의 간선 부호 결정.

SEM은 균형 이론을 이용해 직접적인 간선이 존재하지 않는 노드들 간의 관계를 정의합니다. 균형 이론에 대해 간략하게 설명하면 "친구(+)의 친구(+)는 나의 친구(+)", "친구(+)의 적(-)은 나의 적(-)", " 적(-)의 적(-)은 나의 친구(+)"로 표현할 수 있습니다. 이 때, 친구란 서로 + 간선을 통해 연결되어 있는 관계를, 적은 - 간선을 통해 연결되어 있는 관계를 지칭합니다. 그림 2의 그래프 상에서 소스 노드인 B와 문맥 노드 C의 거리는 2로, B와 C 사이의 직접적인 간선이 존재하지 않습니다. 하지만, B와 C를 잇는 최단 경로 B - A - C 를 통해 B와 A는 친구이고 A와 C는 적이므로 C는 B의 관점에서 "친구의 적"이 됩니다. 균형 이론에 따라 B와 C의 관계를 최종적으로 적(-)으로 정의할 수 있습니다. 

3. 노드와 주제 임베딩 학습

그림 4. SEM(Stance Embeddings Model)의 임베딩 학습.

학습 시 소스 노드 u의 임베딩, 주제 t의 임베딩, (문맥 노드, 소스-문맥 노드간의 부호) 로 구성된 문맥 노드 집합을 사용합니다. 그림 4 와 같이 소스 노드 u의 임베딩과 주제 t에 대해 덧셈 혹은 요소 별(element-wise) 곱셈을 수행합니다. 이를 통해 소스 노드와 주제의 특징이 모두 반영된 주제 t에 대한 노드 u의 임베딩을 얻고, 문맥 노드들 c 와의 유사도를 연산합니다. 결과적으로 학습이 끝난 후, 특정 주제 t에 대한 부분 그래프 상에서 노드간의 관계를 표현하는 임베딩은 물론, 주제 t에 대한 일반화된 임베딩을 얻을 수 있습니다. 

Experiments

본 논문은 제안하는 모델과 더불어 두 가지의 새로운 실세계 그래프 데이터를 제안합니다. TwitterSG는 200개의 주제에 대해 75만 트위터 유저들을 노드로, 트위터 상 이들 간의 상호작용을 약 1억 3천만개의 간선으로 표현한 그래프 데이터이며 현존하는 가장 큰 그래프 데이터 Epinions 보다 약 6배 가량 큰 규모입니다. 또한, BirdwatchSG는 트위터의 게시글에 대해 사람들이 misleading 하다고 판단하거나 추가적인 메모를 남길 수 있는 Birdwatch의 약 3000명의 사용자들을 노드로, 44만개의 상호작용을 간선으로 표현한 그래프 데이터 입니다.

표 1. 논문에서 새롭게 공개한 BirdwatchSG, TwitterSG와 기존 공개 그래프 데이터들.

본 논문은 제안하는 모델 SEM의 우수한 성능을 입증하기 위해 두 가지 실험 결과를 제시합니다. 첫 번째 실험은 각 모델에서 만든 임베딩을 바탕으로 kNN과 Logistic Regression(LR)을 적용해 주어진 간선의 부호를 예측하는 것입니다. 표 2는 SEM와 경쟁 방법들의 간선 부호 예측(signed edge prediction) 성능을 비교합니다. 모든 경우에 SEM이 경쟁 방법들보다 좋은 결과를 보였습니다. 이는 SEM이 경쟁 방법들 보다 부호가 있는 간선을 예측하기에 좋은 임베딩을 학습한다는 것을 의미합니다.

표 2. SEM와 경쟁 방법들의 간선 부호 예측(signed edge prediction) 성능 비교.

두번째 실험은 cold-start 상황 즉, 기존에 특정 주제에 대해 상호작용이 없던 노드들 간의 입장을 확인하는 것입니다. 다시 말하면, 학습 시 사용한 그래프 상에서 주제 t에 대해 유저 u 와 v의 간선이 존재하지 않았는데, 만약 존재한다면 긍정적일지(+), 부정적일지(-)  예측하는 문제입니다. 표 3은 SEM와 경쟁 방법들의 간선 부호 예측 성능을 비교합니다. 모든 경우에 SEM 경쟁 방법들보다 좋은 결과를 보였습니다. 이는 SEM이 다른 주제에서도 동의, 부정에 대한 노드들의 상호작용을 효과적으로 학습한다는 것을 의미합니다. 

표 3. Cold-start 상황에서 SEM와 경쟁 방법들의 간선 부호 예측(signed edge prediction) 성능 비교.

Conclusion

본 문서에서는 WSDM 23에 게재된 Learning Stance Embeddings from Signed Social Graphs 논문을 소개하였습니다. 해당 논문은 그래프에서 주제별 그래프를 생성하고 간선 관점에서 그래프 임베딩을 생성하는 SEM(Stance Embeddings Model) 모델을 제안하였습니다. SEM는 실세계 데이터에서 경쟁 방법들보다 더 정확하게 간선의 부호를 예측하였습니다. 본 논문은 실세계 다양한 그래프 구조 데이터에 적용할 수 있습니다. 보다 구체적으로, 소셜 네트워크 서비스 상에서 사용자들이 의견을 표명하는 주제를 기반으로 그래프를 생성하면 이와 유사한 새로운 주제에 대한 유저들의 의견을 예측할 수 있습니다. 지역 축구팀을 응원하는 사람들은 국가대표 축구팀 또한 함께 응원할 가능성이 높다는 예측이 그에 대한 예시입니다. 또, 전혀 관련이 없어보이는 주제들 간에도 유저들의 반응을 기반으로 어떠한 연관성이 있을지 파악하는데 도움이 됩니다. 이에 대한 예시로, 동물 실험을 반대하는 사람들은 채식에 대해 비슷한 의견을 취할 가능성이 높은 상황을 생각할 수 있습니다. 이처럼 본 논문은 실세계 그래프 기반의 데이터에서 다양한 시각으로 그래프를 분석하고 작업을 더 정확하게 수행하는데 활용될 수 있을 것으로 기대됩니다. 본 논문에 대해 더 자세한 정보는 다음 링크에서 확인할 수 있습니다 (링크)