A Generalized Neural Diffusion Framework on Graphs

AAAI 2023

작성자 : 배지훈

paper link

Background

• Graph Diffusion 논문들을 읽어보면, 중요하게 언급하고 있는 공통적인 사실은 그래프 학습 메커니즘과 확산 방정식 사이의 긴밀한 관계성이 존재한다는 것이며, 실제로 Message Passing을 기반으로 중심 노드의 정보 확산을 수학적으로 모델링하여 Generalization할 수 있음을 직관적으로 이해해볼 수 있습니다.
• 위의 인사이트를 바탕으로, Graph Diffusion Convolutional Networks들이 많이 제안되어졌으며 기존 GCNs 계열 모델들을 쉽게 대체할 수 있음도 입증되었습니다. ( GDC , GRAND ..)
• 하지만, 다음 네트워크들의 공통적인 Assumption으로 입력 그래프의 Homophily함이 보장되어있어야 하며, 그로부터 1차 확산 방정식을 기반으로 구축된 학습 메커니즘을 차용하여 Local Neighbors을 위주로 고려하게 됩니다.
• 다음은 Inductive bias 측면에서 적절한 메커니즘으로 생각해볼 수 있겠으나, Long Range Dependency 혹은 Heterophily한 속성이 강한 그래프를 고려할 경우 해당 네트워크의 성능적인 Limitation이 존재할 수 밖에 없을 것입니다.
• 위의 사실로부터 자연스럽게 떠오를 수 있는 질문은 다음과 같습니다.

그래프 타입에 상관없이 기존 Graph Diffusion Process를 잘 통합시키고 그 장점을 극대화시킬 수 있는 Frameworks 혹은 학습 메커니즘은 없을까?

Introduction

• GRAND 논문에서 위의 질문에 대한 해답을 찾기 위해 GCN 및 GAT 모델을 baseline으로 하여 확산 프로세스에 이들의 학습 메커니즘을 통합하려는 시도가 있었습니다.
• 본 논문의 저자들은 한정된 GNNs을 너머 넓은 스펙트럼의 GNNs (SGC, APPNP, AMP, DAGNN ..)에서 공용적으로 적용될 수 있는 확산 프로세스를 연구하는 데 관심을 두었습니다.
• 구체적으로, 1-hop 이웃 노드 사이에 놓인 Homophily Assumption을 너머 그 이상의 고차원적인 관계성들을 포함하고자 하였으며, 그로써 더 풍부한 Context 정보를 모델 학습에 제공하여 수많은 schemes를 도입하고자 하였습니다.
• 다음 아이디어를 수학적으로 모델링하기 위해 1차 및 2차 확산 프로세스를 모두 통합하고, 그 사이의 불일치성을 최소화하는 방향으로 전체 확산 방정식을 정규화함으로써 설계되어진 새로운 모델, HiD-Net (High-order Graph Diffusion Network)을 제안합니다.
• 저자들은 이론적으로 제안 모델 HiD-Net이 2차 랜덤워크와 필연적인 관계를 가지고 있음을 보이며, 레이어 수가 증가하더라도 학습되어진 그래프 표현 정보들이 동일한 벡터로 수렴하지 않으며 랜덤워크의 Limit Distribution으로 수렴하는 Guarantee를 주장합니다. 즉 Oversmoothing의 문제로부터 쉽게 벗어날 수 있음을 강조합니다.

Methodology

• 기존의 1차 확산 프로세스 기반의 Graph Diffusion Networks의 문제점을 다음과 같이 언급합니다.

" Oversmoothing "

• 식 5에서 기존 1차 확산 방정식은 1-hop 이웃 노드 j들의 차이에만 의존하여 중심 노드 i의 정보가 업데이트 되는 사실을 알 수 있습니다.
• 즉, 그 차이의 크기에 비례하여 업데이트되는 정보의 크기 또한 크게 변동되어지기 때문에 만약 Heterophily한 그래프 상에서의 다음 확산 프로세스는 Training Oscillation으로 인한 수렴의 불확실성 및 Oversmoothing 문제에 쉽게 노출될 수 있습니다.
• 저자들은 중심 노드 그 자신 정보와 변동량 사이의 관계성이 존재할 수 있다는 가정을 기반으로 (similar to self-loop) fidelity term을 추가하여 식 5의 확산 방정식을 다음과 같이 수정합니다.

• 논문의 Proposition 1 ~ 5을 통해 식 6으로부터 다양한 GNNs의 확산 프로세스를 쉽게 Generalize할 수 있다는 사실을 설명합니다. 자세한 설명은 해당 논문을 참고해주시기 바랍니다.

" High-order diffusion "

• 위에서 언급하였듯이, 기존 Graph Diffusion Networks는 1차 확산 프로세스 기반의 1-hop 이웃 노드들만 고려합니다.
• 다음은 Diffusion 관점에서 Fig 2와 같이, 노드 i, j로부터 흘러나가는 방향의 노드는 3개로 동일하지만 해당 노드들이 속한 그래프의 구조는 다른 Isomorphic한 그래프 경우 추가적인 정보를 제공하여 이들을 더욱 Discriminative하도록 만들어줄 필요가 있습니다.
• 저자들은 간단한 실험을 통해, 2-hop 이웃들이 레이블 정보가 Monolphily property (즉, Homophily 및 Heterophily graph 모두로부터 발견될 수 있음)을 갖는다는 것과, 결과적으로 1-hop 노드 보다 2-hop 노드 사이에서 더욱 유사한 정보를 가지는 경향을 발견하였습니다.
• 따라서, 2-hop 노드들에 더욱 집중할 수 있는 DMP (Diffusion-based Message Passing) Scheme을 활용하여 다음과 같은 2가지 이점을 얻어내도록 합니다.

1. 1-hop 이웃 노드 사이에 비연관된 정보가 존재하더라도, 그 노드들의 이웃 노드인 2-hop 노드들을 직접 고려하게 됨으로써 그래프 상의 Local Environment을 포착할 수 있으며, 다음 사실은 그래프 학습 프로세스의 강건성을 부여한다.
2. 2-hop 이웃 노드들의 Monophily property로부터 추가적인 Correlationship을 제공할 수 있기 때문에, 1-hop 이웃 노드만을 고려하는 경우보다 더 좋은 예측결과를 만들어낼 수 있다.

• 이러한 특성들을 갖는 HiD-Net 모델은 더 넓은 스펙트럼의 노드 정보를 풍부하게 활용하면서 기존 모델들의 성능을 쉽게 능가할 수 있었으며, 입력 그래프 type의 제약적인 assumption을 벗어나 agnoistic하게 활용할 수 있는 장점을 취할 수 있었습니다.

Experiment

• Node classification을 중심으로 진행된 실험에서 저자들은 HiD-Net의 2-hop 이웃들의 정보들을 적극 활용함으로써 1-hop 이웃 노드들에 직접적인 변화를 주었을 때의 강건성을 중심으로 검증하였습니다
• 구체적으로 1차 이웃 노드들의 Edge & Feature attack (e.g. edege delect or adding, feature perturbation ..)을 통한 Accuracy의 변화를 관찰하였습니다.

• 결과적으로 모든 데이터셋 상에서의 다른 baseline GCN & GDCs 보다 강건함을 가지고 가장 좋은 성능을 유지할 수 있었음을 확인해볼 수 있습니다.

• Fig 7에서는 깊은 레이어에서의 고질적인 Oversmoothing 문제를 해결할 수 있는 HiD-Net의 성능을 보여주고 있습니다.

Conclusion

• 해당 논문은 기존 Graph Diffusion Networks의 1차 확산 프로세스 기반 1-hop 이웃 노드와의 관계만을 고려함으로부터 생기는 한계점 (Oversmoothing, Homophily constraint .. )들을 고차원 관계성까지 고려하여 더 넓은 범위의 확산 프로세스를 기반으로 입력 그래프의 종류에 상관없이 강건한 성능을 보여주는 Generalized된 High-order Graph Diffusion Network, HiD-Net을 제안하였습니다.
• 기존 Diffusion process 관점에서 2-hop 노드의 Monophily property를 갖는 새로운 발견을 토대로 여러가지 고질적인 문제점들을 쉽게 해결하였으며, 식 6로 정의된 Generalized Diffusion Equation의 파라미터 변경을 통하여 손쉽게 기존 GNNs를 일반화할 수 있다는 사실이 흥미로웠습니다.
• 자세한 설명 및 본 오마카세에서 생략한 HiD-Net의 수학적 정의 등이 궁금하신 분들은 추가 Appendix를 포함한 전체 논문을 읽어보시는 것을 강력 추천드립니다.

[Contact Info]

Gmail : jhbae7052@gmail.com / jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn

GraphER: A Structure-aware Text-to-Graph Model for Entity and Relation Extraction

작성자 : 정이태

Paper link : https://arxiv.org/pdf/2404.12491

기존 NLP에서 주로 진행하던 Information Extraction 작업에 Graph 관점을 접목하면 어떤 영향이 있을지 궁금하셨던 분들.

핵심

• 기존 방법론 Span-based , table-filling , autoregressive 방법론들을 보완하기 위한 관점으로 본 아이디어 GraphER 이 진행됨.
• 우선, 그래프 구조를 만들기 위해 텍스트 단위를 span으로 나누고 이를 엔티티 노드로 간주함. Span 단위 마다 유의미함을 측정하기 위해 가중치와 활성화 함수를 활용해 가지치기를 함. 관계들 또한 가지치기를 위해 fully connected graph 내에서 가중치와 활성화 함수를 통해 가지치기를 함.
• 그래프를 임베딩하기 위해 트랜스포머 인코더를 활용함. 이 때, Graph 마다 노드,엣지를 토큰으로 간주하여 인코더 입력 값으로 주입. 인코더 결과값인 정량화 값을 활용해 나온 값들을 검증하기 위해 Graph Editing 을 적용하여 그래프 구조가 유의미함을 추가 검증함.
• 최종 검증 값인 노드 그리고 엣지를 기반으로 개체명 , 개체명 간 관계 학습 및 추론하는 방식으로 작동함.
• NER(named entity recognition) 과제의 평가 방식인 span-level 을 활용하여 구체적으로 REL(Boundary Evaluation) , REL+(STrict Evaluation)을 두 가지 지표로 측정함. 결과적으로 GraphER이 우수함을 비교군(NER SOTA Baseline 모델들)과의 실험을 통해 입증함.
• GSL(Graph Structural Learning) 측면도 비교함. Transformer(ours) , GCN , GAT , SAGE 4가지 군을 비교하여 측정한 결과 대다수 Transformer가 우수하였으나, 특정 Task 에서는 GCN이 Transformer 를 넘은 결과도 보임. Message Passing 디자인이 왜 중요함을 간접적으로 보여주는 결과.

기존 방법론 및 한계점

• Span-based approach
  • 스팬 기반 접근법은 텍스트에서 개체로 표현될 수 있는 모든 가능한 텍스트 범위(스팬)를 식별하고 각 스팬을 개체 유형별로 분류하는 방법입니다. 이 접근법은 스팬의 맥락을 고려할 수 있는 딥러닝 모델을 활용합니다.
• Table-filling approach
  • 테이블 채우기 접근법에서는 행렬이나 테이블을 사용하며, 각 셀은 텍스트 내 두 토큰 간의 가능한 관계를 나타냅니다. 모델은 이 테이블을 다양한 유형의 관계 확률로 채우는 방법을 학습합니다.
• Autoregressive approaches
  • 자동회귀 접근법은 연속적으로 개체 태그를 생성하는 방법으로, 각 태그는 이전에 생성된 태그를 조건으로 하여 생성됩니다. 이는 RNN이나 변환기(트랜스포머)와 같이 순차 데이터를 자연스럽게 처리할 수 있는 모델을 사용하여 구현될 수 있습니다.

상세 기술

• 재료 준비 , Graph Modeling
  • Span Representation
    • 문장에서 Span 을 추출하기 위한 과정입니다. Span 이라 함은 텍스트 범위를 의미하며, 문장 내 텍스트 범위를 산정하여 하나의 Span으로 가정합니다. Span 의 시작점 , 끝점 그리고 해당 Span 값 (텍스트 범위) 는 각각 FFN(feed forward network) , Pretrained transformer encoder를 통해 임베딩하여 정량화 해줍니다.
  • Graph Construction
    • 앞선 과정에서 Span 이 만들어졌다면, 이번 과정에서는 해당 Span 이 유효한지를 검증하고 검증된 Span 을 노드 그리고 Span 간 연결성 판단하여 엣지로 만들어준뒤 최종 Graph 형태로 변형해주는 단계입니다.
    • Node selection
      • learnable parameter 과 해당 span embedding 를 행렬곱 해준뒤, 활성화 함수를 통해 선정 여부를 판단합니다.
    • Edge selection
      • learnable parameter 와 해당 span embedding 간 연결관계를 행렬 곱 해준뒤, 활성화 함수를 통해 선정 여부를 판단합니다.
• 재료를 가공하는 단계 , Structure Learning
• 왜 TokenGT를 사용했는지에 대한 이야기. 각기 다른 토큰 , 토큰간 관계들을 학습해야하기에 이에 특화된 모델을 찾아야 했음. 다시말해서, 데이터 특성상 noisy 와 heterogeneous 한 데이터들이 대다수인데 이를 기존 GNN 구조를 차용하면 over-smoothing 과 over-squashing 문제가 필연적으로 발생하여 성능 감소가 발생할 것으로 생각하였음. 그렇기에, 이에 robust한 모델이 필요했고, 토큰간 의존성이 상대적으로 낮아 앞선 문제들을 개선할 수 있다는 측면에서 TokenGT가 적절하다 판단하여 TokenGT를 임베딩 모델로 선택함.
  • Graph Representation learning
  • TokenGT 아키텍쳐를 활용하기 위해 graph를 token 형태의 값으로 변형해주는 단계입니다. 간단하게, 각각의 span 값들을 각각의 node 고유식별자로 맵핑해준뒤 token 형태로 변형해주고 Transformer encoder 에 입력합니다.
  • Graph editing
  • Graph 를 keeping 혹은 dropping 하며 유의미한 Graph 를 선정하는 단계입니다. 이전에 span을 순서에 의존하여 span node 형태로 그래프를 만들어서 독립적으로 그래프 구조를 검증했다면, 이번 단계에서는 TokenGT를 통해 structural learning 이 적용된 후 나온 결과를 기반으로 검증했다는 점을 차이점이라 할 수 있겠습니다.
• 분류 단계 , Classification
  • 그래프 내 각각의 노드 그리고 엣지마다의 정답 값을 기반으로 분류하는 단계입니다.
• 학습 단계 , Training
  • 총 4개의 손실 함수를 통해 GraphER은 학습합니다. 1. node selection loss 2. edge selection loss 3. edit losses 4. final node/edge classification losses 총 4개의 손실 함수를 통해 structural learning 전 / 후 그리고 마지막 최종 FFN을 활용해 변형된 node , edge 값을 학습에 활용합니다.

실험 결과

메인 결과

• 서두에 설명한 NER SOTA baseline 기존 방법론들 대비 대다수 outperform 한 결과들을 보입니다. 이를 통해, structural learning 이 NER 에서 유의미한 결과를 보임을 확인할 수 있습니다.

Comparison with Message Passing GNN

• High heterogeneous 와 noisy 가 많은 데이터에서 over-squashing, over-smoothing 이 염려될 때 참조하면 좋을 결과라고 생각합니다.

Recap

• 기존 entity 와 relation extraction 단계적 혹은 병렬적으로 진행한 프로세스를 GraphER은 jointly optimization & end-to-end 형태로 진행합니다. 그렇기에, Entity 추출과 entity 간 관계를 최적화하는 과정에서 단어 span 을 노드 그리고 span 간 관계를 그래프로 표현한다는 점에서 신선한 접근법이라 할 수 있습니다.
• 기존 NER에서 진행한 방식인 개체간 완전 연결형 네트워크 형태에서 NER를 수행했던 관점을 네트워크를 최적화하는 graph edit operation 을 활용해 유의미한 구조만을 추출하여 과제를 수행하기에 상대적으로 가벼워진다는게 핵심이라 할 수 있습니다.
• 4개의 loss 의 여부에 따라 성능 차이가 어떻게 변하는지 Ablation study 가 없어 아쉬운 연구였습니다. Structural learning 이 어느 부분에서 특히 유의미한지를 판단하기 위한 실험 결과로써 많이 유용했을 것 같은데 말이죠. 아쉽지만 Attention analysis 를 통해 각 Span 간 어떤 상관관계가 있는지를 유추하는 것으로 이 호기심을 대체해야할 것 같네요