이번 세미나에서는 그래프 기반 인공신경망에 대한 간단한 소개를 시작으로 Subgraph를 활용하여 그래프의 표현력을 향상시키는 아이디어가 소개되었습니다. 처음 접하는 내용들이 많았었기에 신기하다고 느껴진 점도 있었습니다. 덕분에 그래프에서의 isomorphic 하다는 의미를 이해할 수 있었고 Weisfeiler-Lehman kernel과 같이 그래프에 커널을 적용하고 WL Test 값을 구하는 과정에 Hash, Bag-of-Color 등의 개념이 사용된 사실이 인상깊었습니다. 첫 번째 순서에 소개하신 방법론인 DropGNN의 경우 dropout을 평가 단계에서도 적용하는 이유는 궁금점으로 남습니다. 두 번째 순서에 소개된 ESAN 방법론을 통해 그래프 상의 equivariance에 대해서 처음 접하게 되었습니다. Subgraph를 구성하는 방법을 달리하여 Subgraph variants를 구성하게 되는데 이 부분에서 또 다른 방법을 혹여나 추가하거나 교체한다면 결과가 어떻게 될지 궁금합니다. 기회가 된다면 그래프 네트워크가 실제 활용되는 사례를 소개해주신다면 너무나 재미있을 것 같습니다. 좋은 발표 감사합니다.

최근 그래프 네트워크 관련해서 GNN 이 가지는 power 가 1-WL TEST 의 Upper bound 를 가지고 있단 한계점이 강조되고 있습니다. 이를 해결하기 위해 많은 연구들이 진행되는데 그 중 sub-graph 를 통한 해결책이 큰 방향 중 하나 인 것 같습니다. 첫 논문에서는 Drop gnn 으로 sub graph를 구성하게되고 r 번 반복을 통해 인코딩을 하게되는데, 이는 앙상블 방법과 유사한 효과를 가지는 것 같습니다. 그러나 large graph 혹은 sparse graph 에서는 sub graph 의 표현력 혹은 구성 자체에 문제점이 많기 때문에 한계점이 분명히 존재 할 것 같습니다. 두번째 논문인 ESAN 은 비슷한 아이디어지만 Permute adjacency matrix 를 활용해서 같은 접근을 했습니다. 이 또한 adjacency matrix 자체를 저장해야하는 구조라 complexity 가 상당히 높습니다. 그러나 연산자체는 가볍기 때문에, r 번의 반복연산은 수행하지 않아도 될 것 같습니다. 또한 permute 된 matrix 를 합치는 과정을 통해 1-WL 의 한계를 극복하려고 했던 것 같습니다. 앞서 언급한 sclae issue 를 제외하면, 상당히 재밌는 방법론 이였습니다. 감사합니다.

GNN의 여러 Task 중 두 그래프가 동일한 형태를 갖고 있는지(Isomorphic)를 판단하는 과제가 있으며 이는 Weisfeiler-Lehman Test가 있습니다. 이런 Test로 두 그래프의 동형성을 판단할 수 있지만 일부의 경우에서 완벽한 정답을 내놓지 않는 것이 단점입니다. 확실히 다른 그래프를 구분하지 못하는 것은 Graph 자체의 Expressiveness가 부족하다는 뜻이며 본 세미나에선 이를 풍부하기 위한 두 가지 논문을 소개하였습니다. GNN에서 개별 그래프의 표현력이 감소하는 이유는 단훈히 이웃의 정보들을 취합하는 MPNN 때문이며, DropGNN 같은 경우는 Dropout node를 통해 매번 다른 perturbated variants를 통해 학습하여 그래프 내의 수많은 Subgraph를 생성하여 표현력 향상을 목표로 합니다. Dropout과 같은 방식으로 Subgraph를 구성하는 첫번째 논문과 다르게 두 번째 논문에서는 DS / DSS로 대표되는 Subgraph encoding을 통해 GNN 표현력 향상을 달성했으며, Siam Network 구조를 통해 Permutation된 각 subgraph 정보를 공유하는 Layer를 구성합니다. 그래프의 관심이 떨어질때마다 충전해주시는 세미나 해주셔서 감사합니다.

본 세미나에서는 "DropGNN : Random Dropouts Increase the Expressiveness of Graph Neural Networks"와 "EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS"에 대해서 살펴 보았습니다. 논문을 살펴보기에 앞서서 그래프의 동형을 파악할 수 있는 Weisfeiler-Lehman Test에 대해서 말씀해주셨습니다. 개인적으로 처음 보는 개념이라 신기한 부분들이 많았고 그만큼 그래프의 동형성을 파악하는 것이 중요하다는 것을 알게되었습니다. 그리고 WL test가 일치하더라도 항상 isomorphic한 것이 아니라는 설명을 듣고는 동형이 아님을 확실하게 파악하는것이 동형임을 파악하는 것 보다 중요하구나 라는 것도 알게 되었습니다. 소개해주신 두 논문 모두 구체적인 방법론은 다르지만 컨셉 자체는 일종의 subgraph를 통하여 이러한 문제를 해소하고 있습니다. 개인적으로는 그래프에서 노드나 엣지를 임의로 제거하는 형태가 정말 맞는지에 대한 의문이 계속 들었습니다. dropout 방식이 딥러닝에서는 매우 일반적이지만 그래프는 데이터의 특성상 노드-엣지의 정보가 매우 중요할 것 같은데 본 논문을 포함하여 이런 아이디어를 제안하는 논문들의 실험 결과가 항상 좋아서 신기했습니다. 감사합니다.

이번 세미나는 그래프의 expressiveness를 증대하기 위한 두 방법론을 주제로 진행되었습니다. 두 그래프 사이에 서로 isomorphic한지 판단하는 Weisfeiler-Lehman Test에 대해서 설명해주시고, 이 WL Test으로 두 그래프가 isomorphic한지 정확히 판단하기 어렵다는 한계점에 대해서 설명해주셨습니다. 첫 번째 방법론인 DropGNN의 경우 원 그래프의 노드를 확률적으로 제거하여 다양한 sub-graph를 구성함으로써 다양한 representation을 학습하게 하였습니다. 두 번째 방법론인 ESAN은 사전에 정의된 방식으로 equivariant sub-graph를 구성하도록 policy를 제안하였습니다. DS, DSS 두 가지 방식을 제안하여 다양한 sub-graph variants를 구성하도록 하였습니다. 최근 여러 분야에서 다양한 representation을 학습하기 위한 연구들이 많이 진행되는 것 같습니다. 그래프에서도 이러한 연구 흐름에 대해 들을 수 있는 좋은 기회였습니다. 좋은 발표 감사합니다.

오늘 세미나는 subgraph를 활용하여 structure encoding을 함으로써 graph representation의 표현력을 높이기 위한 두 가지 방법에 대해서 진행되었습니다. 초반부에 weisfeiler-lehman test를 설명해주셨는데 이는 두 그래프가 isomorphic한지 판단하는 test이지만 이것만으로는 isomorphic 여부를 완벽히 알 수 없다는 것을 알게 되었습니다. 이는 graph가 충분히 expressive하지 않다고 해석할 수 있고, 이를 해결하기 위한 방법으로 오늘 소개해주신 두 논문이 있습니다. 특히 DropGNN은 node를 dropout하여 풍부한 subgraph를 구성함으로써 representation의 다양성을 높이고자 하였습니다. 그래프에서 node를 dropout하는 것이 오히려 원 그래프의 정보를 왜곡하지는 않을까 생각되었는데 실험 결과를 보면 효과가 있다고 보여 인상 깊었습니다. 좋은 발표 감사합니다.

금일 세미나는 "More Expressive GNNs with subgraphs"라는 주제로 진행되었습니다. 본 발표에서는 GNN의 표현력을 높이고자 하는 다양한 연구들이 소개되었습니다. 먼저 발표에서는 이러한 방법론들이 나오게 된 배경이 설명되었습니다. GNN은 주변 이웃 노드들의 정보를 반영한 node representation 업데이트에 한계를 가지기 때문에 Weisfeiler Lehman test와 같은 문제를 해결하지 못한다는 한계점을 가지고 있습니다. 따라서 이를 해결하기 위해 다양한 방식의 subgraph를 활용한 sturucture encoding 방식들이 제안되었고 subgraph를 구성하고 학습하는 방법에 따라 다양한 연구들이 제안되었습니다. 오늘 소개된 DropGNN은 각 노드별로 독립적으로 일정 확률로 노드를 제거하여 다양한 subgraph를 구성하였고, 반복적으로 서로 다른 subgraph를 학습함으로써 다양한 subgraph embedding을 학습하였습니다. 해당 모델은 이러한 방식을 통해 기존 GNN의 표현력 및 연산 효율성을 향상시켰습니다. 두번째로 소개된 ESAN은 node deletion, edge deletion, ego-nets와 같이 사전에 정의된 방식으로 그래프를 subgraph 집합으로 표현하였습니다. 개인적으로 그래프는 생소한 분야인데 세미나를 통해 접할 수 있어서 좋았습니다. 좋은 발표 감사합니다.

이번 세미나는 More Expressive GNNs with subgraphs를 주제로 두 가지 논문을 소개해주셨습니다. 첫번째 논문인 DropGNN은 그래프 간의 동형을 확인하는 WL test에 대해 문제를 제기하는데, WL test가 일치하는 것이 항상 동형을 의미하는 것이 아니라고 언급합니다. 따라서 node나 edge를 일정 확률로 제거한 subgraph를 구성하여 다양한 subgraph representation을 학습하고 aggregation을 하여 이웃정보를 잘 반영하며 WL test에 의해 동형으로 잘못 판단되곤 했던 문제를 해결하였습니다. 두번째 논문인 ESAN은 여러가지selection policy에 의해 그래프를 하위그래프의 집합으로 표현하여 permutation에 equivariance한 encoder layer를 통해 representation을 학습하고자 했습니다. 개인적으로 두번째 논문에서 equivariance 개념을 사용한 것이 dropGNN보다 설득력 있었고 흥미로웠습니다. 좋은 발표 감사합니다.

이번 세미나 주제는 “More Expressive GNNs with subgraphs”로 최근 다양한 방식의 subgraph를 활용한 structure encoding 방식을 제안하여 GNN의 표현력을 높이고자 하는 2가지 연구들에 대하여 소개해 주셨습니다.
[1] DropGNN : Random Dropouts Increase the Expressiveness of Graph Neural Networks
본 논문은 그래프상의 노드들을 Dropout 기법을 통하여 다양한 subgraph를 구성하고, 이를 통해 GNN의 Expressiveness을 증대하고자 하였습니다. 저는 해당 방법이 일종의 augmentation이라고 느껴졌는데요. Dropout node를 통해 매번 다른 perturbated variants 을 통해 학습을 수행한다는 개념이 재밌다고 느껴졌습니다.
[2] ESAN : Equivariant Subgraph Aggregation Networks
본 논문은 다양한 subgraph들의 집합셋으로 Graph를 표현을 수행하고자 하였으며, 이때 EN, ND, EGO 등의 subgraph를 구성하는 방식에 따라 다양한 variant들을 구성하였습니다. 뿐만 아니라 Siamese Network 구조를 통해 permutation 된 각 subgraph의 정보를 공유하는 equivariant layer를 구성하였습니다.

이번 세미나는 subgraph를 활용하여 그래프 기반 네트워크의 표현력을 높인 연구를 다룬 두 논문 DropGNN : Random Dropouts Increase the Expressiveness of Graph Neural Networks와 EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS를 주제로 진행되었습니다. 소개해주신 첫 논문의 경우 기존 GNN 연구의 한계로 지적되어 왔던 그래프의 동형성 문제를 해결하기 위하여 그래프 상의 노드를 dropout하는 방식으로 subgraph를 구축하고 서로 다른 subgraph를 반복 학습하여 다양한 subgraph 임베딩을 학습하고자 하였습니다. 이를 통해 런타임마다 매번 다른 구조의 subgraph를 학습하여 최종적으로 r개의 node representation을 취합하여 예측을 수행합니다. real-world 데이터셋과 synthetic benchmark dataset을 활용한 실험에서 기존 방법론 대비 성능 향상을 이루어냈습니다. 두번째 논문 ESAN의 경우, subgraph를 구성하는 방식을 달리 하여 다양한 subgraph variants를 구축하였고 이를 통해 다양한 subgraph들의 집합으로 그래프를 표현하고자 하였습니다. 또한, siam network 구조를 활용하여 permutation된 각 subgraph의 정보를 공유하는 층을 구성하였습니다. 그래프 계열의 연구는 개인적으로 낯설게 느껴지는 분야였는데 발표자분께서 초반 문제 정의부터 명확히 해주신 덕에 차근차근 따라갈 수 있었습니다. 유익한 발표 진행해주셔서 감사합니다.

그래프의 isomorphic 여부를 판단하는 고전적인 방법인 Weisfeiler-Lehman kernel은 두 그래프의 노드 및 edge 연결 정보를 확인하는 방법입니다. Hop의 크기에 따른 WL-test를 하는 것이 정확하겠지만 연산량이 많다는 이유로 이루어지지 못하였는데, graph substructure network의 count 기반 structural encoding을 통해 이 문제를 완화하였습니다. 이후 DropGNN에서는 dropout을 통해 다양한 subgraph를 구성합니다. 평가 단계에서도 dropout을 통한 subgraph를 만들어 end task에서의 다양성을 보장하는 것이 특징입니다. ESAN 논문은 동일 주변 노드로부터 학습에 필요한 정보가 제공되기 때문에 표현력이 제한됨을 지적하며 non-isomorphic graph를 구분할 수 없는 상황을 보입니다. Graph kernel 같은 휴리스틱한 방법으로 구분이 가능하지만 이 역시 특정 분자구조 그래프를 구분하는 데 어려움이 있기 때문에 subgraph를 구성하면 몇 가지 variant를 제안합니다. 꼼꼼하게 설명해주셔서 감사합니다.

이번 세미나에서는 GNN의 expressiveness에 대해 다룬 두 가지 연구에 대해 소개되었습니다. GNN은 Weisfeiler Lehman test를 풀 수 없다는 한계를 가지고 있는데 이는 이웃 노드들로부터 전달받은 정보로 해당 노드의 representation을 업데이트하는 Message-passing 방식을 사용하기 때문입니다. 소개된 두 논문에선 이 부분에 대한 해결방식을 제시하고 있는데, 첫 번째 논문인 DropGNN에선 그래프에 dropout을 사용하여 여러 subgraph를 구축하는 방식을 제시하고, prediction 단계에서도 dropout을 통해 구한 여러 예측값을 취합하는 형태를 사용합니다. 두 번째 논문 ESAN에선 다양한 subgraph 들을 집합셋으로 그래프 representation을 학습할 수 있는 구조를 제안하고, 이러한 방식은 DropGNN대비 tractable한 computation cost를 가진다는 장점이 있습니다. GNN representation 관련 연구로 소개된 두 논문은 모두 생소한 연구였지만, 기존의 한계이자 풀고자 했던 문제에 대해 먼저 잘 정리해주시고 설명해주셔서 세미나 내용을 따라가는 데 많은 도움이 되었던 것 같습니다. 좋은 발표 감사합니다.

이번 세미나에서는 GNN과 관련된 두가지 논문에 대해 소개해주셨습니다. 배경으로서는, 우선 GNN이 그래프 동형성에 대한 Weisfeiler Lehman test를 풀 수 없다는 한계점을 제시해주셨고, 이는 GNN이 메시지 패싱 기반으로 업데이트를 수행해 노드의 표상을 학습하기 때문입니다. 이러한 점을 해결하기 위한 두 논문의 내용을 세미나를 통해 말씀해주셨는데, 우선 첫번째 논문은 Subgraph를 노드 상의 Dropout을 통해 구축하고, 이를 통해 전체적인 네트워크의 표현력을 증진시키는 방법론을 제안합니다. 추론 시에도 dropout을 활용한다는 점에서 의아했는데, random forest의 가지구성 방식으로 예를 들어서 설명해주셔서 이해가 잘 되었습니다. 두번째 논문은 ESAN(Equivariant Subgraph Aggregation Networks)을 제안하며, 앞서와 마찬가지로 subgraph를 통해 처음 제시된 문제점을 극복하고자 합니다. 이는 Subgraph를 구성하는 방법을 달리하여 Subgraph Variants를 여럿 구축하는 방식으로 그래프 구성을 진행합니다. 그래프는 아직도 난해한 분야인데, 차근차근 설명해주시는 덕에 나름대로 잘 이해하고 있는 것 같습니다. 좋은 발표 감사합니다.

이번 세미나는 More Expressive GNNs with subgraphs을 주제로 진행되었습니다. 현존하는 데이터들의 관계성을 모델링할 수 있다면 새로운 관점으로 데이터의 특징을 학습할 수 있다는 점에서 Graph domain은 매우 중요하다 생각합니다. 먼저 Weisfeiler-Lehman Test에 대해 논의하였습니다. 이는 주어진 두 그래프가 Isomorphic한지 판단하는 것이며 해당 방법론으로는 완벽히 isomorphic 여부를 정의하기에 어려움이 존재합니다. 따라서 두가지 방법론을 소개키셔주셨습니다. DropGNN은 Subgraph를 활용하여 문제점을 해결하며, drop node를 통해 반복적으로 서로 다른 subgraph를 학습합니다. 두번째 방법론인 ESAN은 다양한 subgraph encoding을 활용하여 GNN의 expressiveness를 풍부하게 만들어주었습니다. 즉, 두가지 방법론은 subgraph의 variant를 생성하여 좋은 representation을 생성하는 방법을 통해 좋은 성능을 기록하였습니다. 발표 감사합니다.

이번 세미나는 GNN에 대해서 다루어주셨습니다. 여러번의 세미나를 통해 설명해주셨듯이 그래프 데이터는 다른 데이터와 다르게 해당 데이터의 구조적 특징을 feature 표현하는 것이 유독 어렵다고 느껴집니다. 이번에는 그래프의 동형을 확인하기 위한 기존 기법인 weisfeiler lehamn test를 소개해주셨고, 해당 기법이 가지는 한계점을 알 수 있었습니다. 오늘 소개해주신 논문들에서는 해당 한계점을 지적하고, 이를 해결하기 위한 해결책을 제시한 논문들이었는데, drop-out을 통해 문제를 해결한 부분이 인상 깊었습니다. 또한 test 단계에서도 drop-out을 적용한다는 부분이 신선했습니다. GNN 관련 연구는 난이도가 매우 높은 연구라고 생각하는데 문제점을 잘 정리해주셔서 연구 흐름을 파악하는데 도움이 되는 것 같습니다. 좋은 발표 감사드립니다.

오늘 소개해주신 내용은 subgraph를 사용하여 기존 GNN의 학습 방식을 개선한 연구 사례입니다. 기존 GNN의 학습 방식은 message passing을 기반으로 neural network를 학습하여 node representation을 구성하는 방법입니다. 하지만 해당 방법은 over-smoothing 문제로 인해 aggregation이 반복되는 과정에서 node 간 representation이 유사해지는 문제가 있습니다. 또한 주어진 두 그래프가 서로 isomorphic 한지 여부를 판단하기 위한 Weisfeiler-Lehman 평가가 어렵다는 문제가 있습니다. 이번 세미나에서는 이러한 문제를 해결할 수 있도록 drop-out 방식을 활용한 DropGNN과 최근 ICLR 2022에 submission 된 EQUIVARIANT라는 방법에 대해 소개해 주셨습니다. 이전 세미나에서는 주로 over-smoothing 문제를 개선한 연구에 대해 알 수 있었는데, 이번 세미나에서는 또다른 문제를 개선한 graph 연구 사례를 볼 수 있어서 graph 분야의 흐름을 파악할 수 있던 시간이었습니다. 오늘도 좋은 발표 감사합니다.

금일 세미나는 More Expressive GNNs with subgraphs에 대해 진행되었습니다. 본 연구는 graph내 node 정보들의 representation을 학습하는 부분에 관한 내용을 다루고 있는 것으로 이해했습니다. 2가지 연구를 소개해주셨습니다. 첫 번째 연구는DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks으로서, node를 Dropout하며 graph를 다양한 sub-graph로 나눠주는 방식을 적용합니다. 이러한 과정이 반복되다 보면, sub-graph는 stochastic하게 다양한 내용을 담게되고, 자연스레 학습과정에서도 다양한 representation을 접하고 학습할 수 있게 됩니다. 비교적 간단한 dropout 방법을 적용해 이러한 성능 향상을 이룰 수 있다는 점이 인상적이었습니다. dropout은 수단이고, 핵심은 Representation learning을 위해 다양한 representation(sub-graph)를 만들어낸다는 점인 것 같습니다. 두 번째 연구는 EQUIVARIANT SUBGRAPH AGGREGATION NETWORKS였습니다. 이 논문 역시 representation learning을 위해 sub-graph를 활용했습니다. 어렵게만 느껴지는 graph 분야인데, 이렇게 자세하게 설명해주셔서 분야에 대한 이해를 높일 수 있었습니다. 좋은 발표 감사드립니다.

금일 세미나는 GNN의 표현력을 높이기 위한 방법론들을 소개하는 내용으로 진행되었습니다. 먼저 첫번째 논문에서는 그래프에 dropout을 적용하여 여러 subgraph를 만들어서 표현력을 높이는 아이디어를 제안했으며, 이후 subgraph들의 정보를 readout처럼 aggregation하여 node representation을 학습합니다. 두번째 논문에서는 동일 이웃으로부터 전달받은 정보로 학습되어 aggregation과 combination에 사용되는 정보 자체가 한계를 가지는 점을 지적하면서 subgraph를 구성하는 DS-GNN과 DSS-GNN 방식을 제안합니다. 같은 graph로부터 서로 다른 정보를 전달할 수 있는 subgraph를 구성하여 실험적으로도 좋은 성능을 얻었다는 점에서 굉장히 유익한 기법이라고 생각했습니다. 좋은 발표 감사합니다.