Directional Graph Networks

by신재민 2021.12.28 17:21

발표자	신재민
발표일자	2022-01-04
저자	Dominique Beaini, Saro Passaro
학회명	ICML 2021
논문지

Figure 1 -Overview.png

첨부 [2]

이지형

2022.01.04 19:16

directed graph를 위한 GNN에 대한 논문으로 우리가 조금 더 관심을 가져볼만한 논문임.

댓글
김호승

2022.01.04 19:47

Eigenvector와 관련하여 들으면서 생각을 정리해보았습니다. 논문이 어렵다 보니 제가 생각하는게 맞는지도 조금 헷갈리네요 ;
일단 먼저 논문은 아래 내용과 같이 진행된다고 생각하였습니다.

1) L 매트릭스는 대칭정규화되었기 때문에 대칭행렬이라고 할 수 있습니다.
이를 고유값대각화를 할 때 eigen decomposition을 적용한 것이 eigenvector를 이용하기 시작한 이유인데,

2) GCN을 할 때 filter g theta가 non-parametric이고, eigen decomposition에 대한 계산도가 복잡하여(n^3) Chebyshev 다항식을 이용하여 근사시키는 것으로 알고 있습니다.
그런데 이 방법을 이용한다면, directional 정보를 이용하지 않는다고 생각하고 대신하여 방향성 정보를 더 추가해줄 수 있는 새로운 방법을 사용하겠다라고 논문의 취지로 받아들였습니다. 그렇게 이 논문이 시작되어

3) (b)단계
여기서 표현가능한 다양한 eigenvector값들에 대하여 0 - k 개의 eigenvector값을 계산해주게 됩니다. 이 때 pi 1 = 노드 수 x feature 수의 행렬형태

4) (c) 단계
eigen vector값의 각 edge에 scalar weight을 부여하여 이를 F값(delta pi)값으로 만듭니다. * 그래서 i, j 가 사용되었는데, i와 j간의 edge를 표현한다고 생각이 됩니다.

5) (d) 단계
위의 F값을 이용하여 aggregation matrix B값을 새로 만들어 낸다.

6) 이 k개의 F값을 이용한 새로운 B값을 concat 하여 MLP로 학습한다.

이상의 내용으로 논문을 이해하였는데, 잘 이해하였는지 모르겠습니다. ;

궁금한 사항은 위 내용이 맞다면 pi 1 = 노드 수 x feature 수의 형태이고 K = 노드 수 x 노드 수의 형태로 생각이 되는데, delta pi ij = pi i - pi j로 계산하는게 맞는지 궁금합니다!
오늘도 좋은 논문소개 감사드립니다

댓글
신재민

2022.01.04 21:28

pi1은 eigenvector중 가장 큰 크기를 갖는 벡터입니다. 따라서 그 shape은 n x 1 입니다. (n: node 개수)

k는 몇 개의 eigenvector를 사용할지 사용자가 정하는 정수값입니다.

delta pi ij 는 소개해 드릴 때에도 말씀드렸지만 저자들이 표기를 혼란스럽게 해서 저도 이해하는데 애를 먹었습니다.
delta pi ij 는 pi1와 같은 eigenvector 끼리를 비교하기 위한 표현이 아니고 pi1과 같이 특정 내의 요소를 표기하는 것 입니다.
여기서의 ij는 각 요소에 대한 인덱스 입니다.
따라서 pi1이 n x 1 크기의 Vector라면 그 각 요소간의 차이값을 계산하여 delta pi1는 shape이 n x n이 나옵니다.

댓글
김호승

2022.01.04 23:37

이해하였습니다 감사합니다

댓글
신효정

2022.01.04 20:12

그래프 데이터에서 방향 정보를 추출하고 그 정보를 추가로 사용함으로써 모델의 성능을 개선하는 논문으로 이해했습니다. 이 논문에서 제안하고 있는 (그래프의) 방향정보가 시계열데이터 관점에서의 context로 해석되고 같은 로직으로 사용이 가능할지 고민해 볼 수 있도록 이끌어준 발표였습니다.

데이터에서 추가적인 정보를 추출는 새로운 방법론을 알 수 있어 굉장히 흥미로웠습니다.

댓글
신재민

2022.01.04 21:23

Overview 항목의 좌측 파란색 부분에 대한 추가 설명입니다.

a1) Graph Laplacian Matrix
Graph Laplacian Matrix를 계산하는데는 Degree Matrix와 Adjacency Matrix가 사용됩니다.
Degree Matrix의 대각 요소는 각 Node에 연결된 Edge의 개수를 나타내고 Matrix 크기는 자연스럽게 Graph에 들어있는 Node의 개수를 의미합니다.
Adjacency Matrix는 각 Node 간 연결되는 Edge를 나타내는데 일반적으로는 연결상태만을 나태내기 위하여 1로서 표현합니다. 역시 Matrix 크기는 자연스럽게 Graph에 들어있는 Node의 개수를 의미합니다.
여기서 1이라는 값은 연결 상태의 강도를 의미라는 가중치로 사용되기도 하여 정수 1이 아닌 실수로 표기하기도 합니다.
따라서 Graph Laplacian Matrix는 그래프 구조를 온전히 표현한다고 볼 수 있습니다.

b) Eigenvectors of Graph Laplacian Matrix
Graph Laplacian Matrix가 Graph의 구조를 표현하는 것이기에
Graph Laplacian Matrix의 Eigenvectors는 Graph의 구조의 각 Axis를 의미한다고 볼 수 있습니다.(n 차원 데이터에 대한 각 Axis)
Matrix의 기본 성질에서 임의의 n x n 정방형 Matrix에 대한 Eigenvectors는 n 개만큼 구할 수 있습니다.
물론 Eigenvectors가 항상 n개는 아니지만 여기서는 일반적인 상황에 대하여 이야기 합니다. (미지수가 3개 일 때 수식이 3개인 경우를 의미, 즉, Matrix의 Eigenvectors가 서로 독립이라는 가정)
저자는 여기서 모든 Eigenvectors를 사용하는 것은 아니고 가장 큰 크기를 가진 k 개의 Eigenvectors만 선택하여 사용합니다.
정리하지면 Graph의 구조를 표현하는 가장 대표적인 k개의 Axis를 의미하는 Eigenvectors만을 사용합니다.
이는 Vector이므로 방향과 크기를 가지고 있다는 점을 기억하시면 좋습니다.

c) The gradient of eigenvectors
k 개 만큼 선택한 Eigenvectors 각각에 대하여 그 크기가 n x 1 이라고 가정하면 (Node의 개수가 n),
원래 Graph 데이터를 표현하기 위하여 각 Node의 값이 Axis의 값을 의미한다는 것으로 가정한다면(n 차원의 데이터 표기법이라면)
특정 Eigenvector의 각 요소값은 원래 Graph 데이터의 위치를 표현하는 각 Axis의 기여도(가중치 또는 축에서의 위치)를 나타냅니다.
그래서 특정 Eigenvector를 각 요소별로 차이를 구해서 n x n 으로 만드는 것은
특정 Eigenvector를 표현하기 위한 Axis 간의 위치 차이를 (차분값) 의미합니다.
저자는 이 값을 F라는 Vector Field라고 정의하고 사용합니다.
따라서 F는 특정 Eigenvector에 대한 미분값으로 구성되어 있다고 볼 수 있습니다.(차이의 기준은 Node 간 차이)
정리하자면 특정 Eigenvector의 각 요소에 대한 차이를 Matrix로 만들어서 사용하는 것으로서,
Graph의 구조의 일부인 특정 Eigenvector를 직접 사용하지 않고 1차 미분값을 사용합니다.
(특정 Eigenvector를 구성하는 Axis 값의 변화량을 사용)
참고로 연결되어 있지 않은 Node 간에는 이러한 차이가 발생한다는 것이 모순이므로 각 요소 위치를 파악하여 0으로 강제 변환합니다.
이 처리는 미분값에 대한 오차를 발생시킬 수 있지만 실제 연결된 위치에 대한 미분값만을 남겨두므로 보다 정확한 표현이라고 생각합니다.

d) Aggregation Matrices
F가 특정 Eigenvector에 대한 미분값으로 구성되어 있는데
일반적으로 Graph를 표현하는 Matrix의 Row값은 특정 Node에 대한 연결된 Node들의 정보를 나타내므로, F를 row-wise로 정규화를하고 사용합니다.
이를 F(hat)으로 표기합니다.
F와 F(hat) 모두 대각 요소는 0인데 그 이유는 Adjacency Matrix의 대각 요소들을 모두 0으로 설정했기 때문입니다.
경우에 따라서는 Adjacency Matrix의 대각 요소가 0이 아닌 경우도 있지만,
이 논문은 각 요소간 차분을 계산해야 하는데 자기 자신과의 차분은 당연히 0이 나오므로 배재한 것으로 보입니다.

내용 전개로만 보면 F(hat) 만으로도 Graph의 방향성 정보는 이미 포함되어 있습니다.
여기서 저자들은 Aggregation Matrice로서 F(hat)를 사용하지 않고 Bav, Bdx 라고 한 번 더 계산을 합니다.
본문에 그 의도는 나와 있지 않지만 각각에 대한 의미를 Bav가 방향성 정보에 대한 amplitude라고 설명하고
Bdx를 차분에 대한 정보라고 설명하는 것으로 보아 F(hat)만으로는 충분한 성능이 나오지 않은 것으로 생각됩니다.
왜냐하면 F(hat)에서 Bav를 구할 때에는 절대값 연산을 하지만 Bdx를 구할 때에는 대각 요소에 F(hat)에 대한 column-wise sum을 부호를 반대로 하여 삽입해 주면서(빼기 연산)
방향이라는 것이 양방향이므로 이렇게 해야 양방향 처리에 대한 Balance를 보완한다고 설명합니다.
즉, F(hat)을 그냥 사용할 경우 방향성 데이터의 Balance에 문제가 발생하여 학습에 어떤 쏠림 현상이 발생한 것이 아닌가 추측해 봅니다.

댓글

2022

Text Smoothing : Enhance Various Data Augmentation Methods on Text Classification Tasks

2022.04.04

발표자: 김호승 발표일자: 2022-04-04 저자: Xing Wu, Chaochen Gao, Meng Lin, Liangjun Zang, Zhongyuan Wang, Songlin Hu 학회명: ACL 2020

Natural Attack for Pre-trained Models of Code

2022.03.28

발표자: 나철원 발표일자: 2022-03-28 저자: Zhou Yang, Jieke Shi, Junda He and David Lo 학회명: ICSE 2022

Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting

2022.03.28

발표자: 신재민 발표일자: 2022-03-28 저자: Giorgos Bouritsas 학회명: ICML 2020

DGCN: Diversified Recommendation with Graph Convolution Networks

2022.03.28

발표자: 양희윤 발표일자: 2022-03-28 저자: Yu Zheng, Chen Gao, Liang Chen, Depeng Jin, Yong Li 학회명: WWW ’21

Divergence-aware Federated Self-Supervised Learning

2022.03.22

발표자: 강용훈 발표일자: 2022-03-22 저자: Weiming Zhuang, Yonggang Wen, Shuai Zhang 학회명: ICLR 2022

Recurrent Auto-Encoder with Multi-Resolution Ensemble and Predictive Coding for Multivariate Time-Series Anomaly Detection(RAE-MEPC)

2022.03.22

발표자: 신효정 발표일자: 2022-03-22 저자: Heejeong Choi, Subin Kim, and Pilsung Kang 학회명: arXiv, 21 Feb 2022

Camouﬂaged Object Segmentation with Distraction Mining

2022.03.22

발표자: 임지영 발표일자: 2022-03-22

WIRING UP VISION:MINIMIZING SUPERVISED SYNAPTIC UPDATES NEEDED TO PRODUCE A PRIMATE VENTRAL STREAM

2022.03.23

발표자: 안재한 발표일자: 2022-03-22 저자: Franziska Geiger ~Franziska_Geiger1 , Martin Schrimpf, Tiago Marques, James J. DiCarlo 학회명: ICLR2022

Online Knowledge Distillation for Efficient Pose Estimation

2022.03.03

발표자: 배현재 발표일자: 2022-03-04 저자: Zheng Li¹ , Jingwen Ye², Mingli Song², Ying Huang1, Zhigeng Pan1 학회명: ICCV 2021

Input Complexity and Out-of-distribution Detection with Likelihood-based Generative Models

2022.03.04

발표자: 노순철 발표일자: 2022-03-04

Channelized Axial Attention – Considering Channel Relation within Spatial Attention for Semantic Segmentation

2022.03.04

발표자: 윤수현 발표일자: 2022-03-04 저자: Ye Huang, Di Kang, Wenjing Jin, *Xiangjian He, Liu Liu 학회명: AAAI 2022

FedBABU: Toward Enhanced Representation for Federated Image Classification

2022.03.04

발표자: 홍만수 발표일자: 2022-03-04 저자: Jaehoon Oh, Sangmook Kim, Se-Young Yun 학회명: ICLR 2022

Deep Learning for Symbolic Mathematics

2022.02.22

발표자: 고설준 발표일자: 2022-02-22 저자: Guillaume Lample, François Charton 학회명: ICLR2020

Semi-Supervised Learning of Visual Features by Non-Parametrically Predicting View Assignments with Support Samples

2022.02.22

발표자: 김유성 발표일자: 2022-02-22 저자: Mahmoud Assran et al. 학회명: ICCV 2021

Boosting the Performance of Semi-Supervised Learning with Unsupervised Clustering

2022.02.22

발표자: 김누리 발표일자: 2022-02-22 저자: Lerner, Boaz, Guy Shiran, and Daphna Weinshall 학회명: arXiv preprint arXiv:2012.00504 (2020)

Universal Domain Adaptation through Self-Supervision

2022.02.22

발표자: 이진섭 발표일자: 2022-02-22 저자: Kuniaki Saito , Donghyun Kim, Stan Sclaroff, Kate Saenko 학회명: NIPS 2020

GPipe: Easy Scaling with Micro-Batch Pipeline Parallelism

2022.02.22

발표자: 조영성 발표일자: 2022-02-22 저자: Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Mia Xu Chen, Dehao Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V. Le, Yonghui Wu, Zhifeng Chen 논문지: https://arxiv.org/abs/1811.06965