GraphAGI 첫 걸음, Graph Foundation model 알아보기 (KDD24' Review)

1. Graph AGI 의 핵심 Graph Foundation Model 이란?

1.1. Graph , NLP Foundation model

자연어 처리(NLP) 분야에서의 Foundation model:

그래프 분야에서의 Foundation model:

1.2. 각 분야별 Graph Foundation Models 현황

• GFM(Graph Foundation Model)은 다양한 분야에서 활용되고 있습니다. 그 중 대표적인 케이스가 위 그림에서 각각 다른 색으로 표현된 각각의 7가지 분야이구요.

• Small Molecules , ML Potentials 그리고 Protein LMs 까지는 주로 다른 분야의 도메인에 속한 화합물, 분자 그래프 데이터를 학습하는 GFM 카테고리에 속하고, 그 밑의 Algorithmic Reasoning, Link Prediction , KG reasoning 그리고 Node Classification는 일반적인 상식들을 그래프 형태로 변환하고 이를 학습하는 GFM 카테고리라고 할 수 있습니다.

• 위 Task들 중 Algorithmic Reasoning 과 KG Reasoning 의 차이에 대해 잠깐 언급해보자면, Algorithmic Reasoning은 특정 절차나 공식(수학적 알고리즘)을 따라 문제를 해결하는 데 중점을 두고, KG Reasoning은 데이터 간(지식 그래프 탐색)의 관계를 바탕으로 의미 있는 결론을 도출합니다.

• 이처럼, GFM을 만들기 위해선 사전에 목적 및 데이터를 기획하고, 이에 따라 Domain-specific 일지, Task-specific 일지를 분별합니다. 그리고나서 데이터를 수집하고 정제 그리고 학습 및 검증 과정을 거쳐 Foundation model이 탄생하게 됩니다.

1.3. Graph Foundation Model 이 만들어지는 과정

• GFM을 만들기 위한 과정은 기존 Graph Deep Learning 에서의 End-to-End 과정과 유사한 부분이 있습니다. 바로, Downstream Task를 수행한다는 과정이 유사합니다. 하지만, GFM은 Graph Data Generalization 기능을 위해 좀 더 광범위한 Task를 수행합니다.

• GFM의 핵심 기술은 크게 두 개로 분류할 수 있습니다. 1. Pre-training , 2. Adaptation. 우선 Pre-training은 저희가 익히 알고있는 전이학습과 유사한 맥락입니다. Large dataset을 준지도 학습 관점으로 학습하는거죠. 다만, 기존 데이터와는 달리 구조적 정보, 관계, 그리고 그래프 내 다양한 패턴을 분류하고 이를 추가로 학습한다는 점에서 차이가 있습니다.

• 다음은 Adapation는 Large dataset에서 다양한 정보들을 모델이 학습했다면, 특정 downstream task나 domain task에서 성능 개선을 위해 모델을 적응하는 2차 과정입니다. 흔히 알고있는, Fine-tuning , PEFT(Parameter-efficent FT) 그리고 Prompt-tuning이 이 카테고리에 속합니다.

1.4. Graph Deep Learning 대표적인 3가지 Task

• 노드 분류(Node Classification): 주어진 그래프에서 각 노드에 라벨을 할당하는 작업입니다. 예를 들어, 소셜 네트워크에서 사람들의 직업이나 관심사 등을 분류할 수 있습니다.

• 노드 예측(Node Prediction): 노드의 속성이나 상태를 예측하는 작업입니다. 예를 들어, 추천 시스템에서 특정 사용자가 어떤 상품을 구매할 가능성이 있는지 예측할 수 있습니다.

• 링크 예측(Link Prediction): 그래프 내에서 두 노드가 연결될 가능성을 예측하는 작업입니다. 예를 들어, 소셜 네트워크에서 두 사용자가 친구가 될 가능성을 예측하거나, 추천 시스템에서 사용자가 특정 상품을 구매할 가능성을 예측할 수 있습니다.

• 엣지 분류(Edge Classification): 두 노드 간의 관계 유형을 분류하는 작업입니다. 예를 들어, 지식 그래프에서 두 엔티티 사이의 관계를 분류할 수 있습니다(예: "사람이 회사에 다닌다" vs "사람이 책을 쓴다").

• 그래프 분류(Graph Classification): 전체 그래프를 특정 카테고리로 분류하는 작업입니다. 예를 들어, 화학에서 분자의 구조를 기반으로 약물의 효과를 예측하거나, 소셜 네트워크에서 커뮤니티의 성향을 분류할 수 있습니다.

• 그래프 회귀(Graph Regression): 그래프의 속성에 대한 연속적인 값을 예측하는 작업입니다. 예를 들어, 분자의 구조를 기반으로 특정 물리적 특성(녹는점, 용해도 등)을 예측할 수 있습니다.

2. Graph Foundation Model 의 Challenging

• Model , Data 그리고 Hardware 관점에서

2.1. Model-Centric ; Generalization을 위한 Graph Training

Graph of Relations 그리고 Knowledge Graph Embedding

2.2. Data-Centric ; Foundation model vocabulary 구축을 위해 고려해야할 Graph TSD(Type, Scale, Diversity)

• Data Size에 맞춰 Hardware resource도 고려해야함.

• 이미 ‘관계’가 자연스레 형성되어 있는 그래프 데이터도 있지만, ‘관계’를 직접 형성해주고 이를 그래프로 변환해주는 데이터가 현실에서 대다수임.

• 주로 Table 간 FK-PK 를 활용해 그래프로 변환함. 이 과정중에 발생하는 연산들이 상당하기에, 이를 어떻게 다룰지를 고민해보아야함.

Graph Isomorphism

1. 그래프 구조 인식의 어려움: 그래프 데이터는 자연어 텍스트나 이미지 데이터처럼 명확한 순서나 구조가 존재하지 않습니다. 동일한 구조의 두 그래프가 있을 때, 이를 같은 그래프로 인식하는 것은 간단하지 않습니다. 특히 그래프 신경망(GNN) 같은 모델들이 노드 간의 연결성만을 학습하는 경우, 두 그래프가 이름이 다르거나 노드의 순서가 다를 경우에도 구조적으로는 같은 그래프임을 인식하기 어려울 수 있습니다. 이것이 바로 Graph Isomorphism 문제입니다.

2. 모델의 제한된 표현력: 많은 그래프 신경망(GNN) 모델들은 그래프 동형성 문제를 완벽하게 해결하지 못합니다. 대표적인 예로, Message Passing Neural Networks (MPNN)은 두 그래프가 동형인지 정확히 구분하는 데에 한계가 있습니다. 즉, GNN이 그래프의 노드 및 엣지 정보를 학습하여도, 두 그래프가 동형인지 여부를 정확하게 구별하지 못할 수 있습니다. 이는 GNN의 표현력에 제한이 있음을 의미하며, 그래프 동형성 문제를 해결할 수 없는 이유 중 하나입니다.

3. 그래프 동형성 문제의 복잡성: 그래프 동형성을 해결하는 문제는 NP 문제로 알려져 있습니다. 즉, 그래프의 크기가 커질수록 동형성을 확인하는 데 시간이 기하급수적으로 증가할 수 있습니다. 이는 대규모 그래프에서 효율적인 모델을 개발하는 데 큰 도전 과제가 됩니다.

4. 동형 그래프의 구별 필요성: 많은 실제 응용에서는 그래프 동형성을 구분하는 것이 중요합니다. 예를 들어, 분자 구조를 기반으로 약물의 효능을 예측할 때, 구조가 동일한 분자들은 동일한 효능을 가질 가능성이 큽니다. 하지만 그래프 모델이 이 구조를 정확히 인식하지 못하면, 예측의 정확도가 떨어질 수 있습니다.

Type

• 그래프는 노드와 엣지의 범주에 따라 동질 그래프와 이질 그래프로 나뉩니다.

• 이질 그래프는 여러 유형의 노드와 관계를 포함하며, 이를 처리하기 위해서는 메타-패스 기반 접근법이 사용될 수 있습니다.

• 동질 및 이질 그래프 외에도 동적 그래프와 하이퍼그래프 같은 복잡한 그래프 유형이 존재하여 추가적인 어려움을 줍니다.

Scale

Diversity

2.3. Hardware 리소스 문제 , 데이터 처리와 학습 그리고 Fetching을 어떻게 효율적으로 할 것인가?

Raw data 를 Graph data로 만들기

Graph Traversal , 유저 질의를 그래프 형태로 응답 하기위해 거쳐야 하는 연관 있는 데이터 발견 및 추출 과정

• Query Plan
• Database Query 연산

• Embedding Space
• Embedding 연산

3. Challenging 을 위한 노력들

3.1. Graph Mixture of Experts

• MoE란, Mixture of Expert 의 약어로써 데이터가 학습을 위해 모델로 주입될 때 관련있는 데이터를 판별하는 게이트가 작동되고 해당 게이트와 연결되어 있는 Expert layer를 통해 데이터가 학습되는 알고리즘을 의미합니다.

• 기존 모델은 각 데이터 별로 모든 레이어가 학습되어 가중치가 갱신되었다면, MoE 는 관련 있는 데이터들만 학습되기 때문에 보다 효율적으로 학습을 할 수 있다는 이점이 있습니다.

• 효율적으로 학습을 하기 위해 MoE 알고리즘 추가된 요소가 있는데요. 바로 Gating network, Expert choice 입니다. 직관적으로 생각해보시기에도, '데이터' 와 '관련 있는 게이트'를 판별하는게 핵심이라 생각하실 수 있습니다. 또한, 몇 개의 Expert 를 선정해야할지 또한 고려해야할 파라미터 중 하나라고 할 수 있는데요. 이 두 가지 관점에 대해 조금 더 깊게 이야기 해보겠습니다.

• 입력 기반 선택: 게이트 네트워크는 일반적으로 입력 데이터를 받아서 각 전문가에 대한 확률 분포를 예측하는 작은 신경망입니다.

• 희소 선택: 모든 전문가를 선택하는 대신, 게이트 메커니즘은 일반적으로 소수의 전문가만을 선택하여 입력을 처리하게 합니다. 이러한 희소 선택은 모델이 데이터의 관련 부분에만 집중할 수 있게 합니다.

• 가중치 출력: 게이트 네트워크가 전문가를 선택한 후, 그들의 출력은 가중치 합으로 결합됩니다. 이 가중치는 게이트 네트워크의 확률 분포에서 얻어집니다.

• Softmax: Softmax 레이어는 일반적으로 전문가들에게 확률을 할당하는 데 사용됩니다.

• Top-k 선택: 모든 전문가를 활성화하지 않기 위해 "top-k" 함수가 적용되며, 가장 높은 확률을 가진 상위 k개의 전문가만 선택됩니다.

• Load balance: 일부 고급 구현에서는 전문가들 간의 작업 부하가 고르게 분배되도록 추가 제약을 적용하여 특정 전문가만 과도하게 사용되는 것을 방지합니다.

• 모델 유형: 각 전문가는 소형 피드포워드 신경망, 합성곱 신경망(CNN), 순환 신경망(RNN) 등 문제 도메인에 적합한 모델일 수 있습니다.

• 크기와 복잡도: 각 전문가의 복잡성은 달라질 수 있습니다. 선형 모델처럼 간단할 수도 있고, 심층 신경망처럼 복잡할 수도 있습니다. 전문가의 크기를 적절히 조정하는 것이 중요합니다. 너무 크면 계산 비용이 증가하고, 너무 작으면 유용한 특징을 학습할 수 없을 수 있습니다.

• 전문화: 전문가들은 데이터 분포의 다른 부분에 특화되도록 설계될 수 있습니다. 학습 과정에서 게이트 네트워크는 각 입력에 적합한 전문가를 할당하는 방법을 배우며, 이는 전문가들이 서로 다른 작업이나 데이터 영역에 특화되도록 유도합니다.

• 전문가가 너무 적을 경우: 전문가 수가 너무 적으면 모델이 작업의 복잡성을 충분히 처리할 수 없을 수 있습니다. 이 경우 각 전문가가 여러 기능을 담당해야 하므로 전문화의 이점이 감소합니다.

• 전문가가 너무 많을 경우: 반대로 전문가 수가 너무 많으면 모델이 효율성을 유지하기 어렵습니다. 게이트 네트워크가 적절한 전문가를 선택하기 어려워질 수 있으며, 모든 전문가를 관리하는 데 더 많은 계산 자원이 필요합니다. 또한 일부 전문가가 제대로 활용되지 않을 수 있습니다.

• 적절한 수 찾기: 적절한 전문가 수를 찾는 것이 중요합니다. 모델은 데이터의 다양성을 처리할 수 있을 만큼 충분한 전문가가 필요하지만, 너무 많아져서 게이트 네트워크가 효과적으로 관리하지 못하는 상황은 피해야 합니다. 이는 개발 중 실험과 튜닝을 통해 조정할 필요가 있습니다.

• 이러한 여러 고려 요소들이 필요함에도 불구하고, 왜 MoE를 사용할까요?

• 대용량 데이터들을 다루게 될 때, 하드웨어 리소스가 풍부하다면 이 모든 데이터들을 모두 학습하면 좋을텐데 이를 모두 학습하기엔 제한이 있습니다.

• 때문에 주어진 환경속에서 효율적인 학습이 필요할텐데, 이 효율적인 학습을 위해 '적절한' 학습을 하게끔 선별하고 학습되는 MoE layer가 사용됩니다.

• 잠깐, 라우팅 알고리즘을 언급해보자면 라우팅 알고리즘은 크게 두 방식으로 나뉜다고 할 수 있는데요. 데이터 주입시, 사전에 설정해놓은 Domain-specific 을 활용할지 혹은 사전에 룰을 설정해놓지 않았으나 데이터 분포와 같은 데이터에 좀 더 치중한 w/o Domain-specific 으로 나눌 수 있습니다.

• MoE (Mixture of Experts) 모델은 모든 네트워크 레이어를 거치지 않고, 입력에 따라 선택된 몇몇 전문가(Expert Layer)만을 활성화함으로써 효율적으로 학습이 가능합니다. 이는 계산 자원을 절약하면서도 큰 모델의 성능을 유지할 수 있도록 돕습니다.

• NVIDIA의 블로그에 따르면, 일반적으로 매개변수가 많은 모델은 더 큰 용량을 가지며, MoE는 기존 모델의 전체 네트워크를 활성화하지 않고 전문가 하위 네트워크로 대체함으로써 효율적으로 용량을 확장합니다. 즉, MoE 레이어는 기존 레이어와 동일한 크기를 유지하면서도 더 많은 전문가를 추가해 모델의 표현력을 증가시킵니다.

• 예를 들어, GPT와 같은 트랜스포머 모델에서 MoE를 적용하면, 기존 모델에 비해 학습하는 매개변수의 양은 줄어들지만, 선택된 전문가들이 적절히 동작하여 더 많은 데이터 패턴을 학습할 수 있습니다. 이는 대규모 모델을 구축할 때 특히 유리합니다.

• MoE 모델은 특정 입력에 대해서만 소수의 전문가를 활성화시키기 때문에, 모든 가중치를 사용하는 대신 일부 가중치만 사용하여 효율적인 계산을 할 수 있습니다. 이로 인해 플롭(FLOP, 부동소수점 연산) 효율이 높아져, 계산 비용을 절감할 수 있습니다.

• 구체적으로, 게이트 메커니즘은 입력에 따라 가장 관련성이 높은 전문가를 선택하여 활성화하고, 나머지 전문가들은 비활성 상태로 유지됩니다. 예를 들어, 기존 모델에서는 모든 레이어의 모든 가중치가 활성화되지만, MoE에서는 오직 선택된 전문가의 가중치만 계산되므로 모델의 계산 비용을 줄일 수 있습니다.

• 이 방식은 클라우드 환경에서 큰 규모의 모델을 배포할 때 특히 유리하며, 트레이닝 또는 추론에 필요한 연산 자원을 절감하는 데 효과적입니다.

• 기존 MoE와 다르게 Graph MoE는 structure & feature 를 잘 선별해 적절한 Expert 에게 보내는게 핵심입니다. GFM 의 학습을 위해 필요한 GNN 알고리즘의 대다수가 Message Passing 을 기반으로 가중치가 학습되고, 이 가중치를 학습하기 위해 연결된 주변 이웃 N개를 기반으로 aggregation 하기때문에 적절한 N개의 이웃을 선별해야하기 때문이죠.

• 타 데이터 대비 Graph 데이터는 '연결' 되어 있는 데이터들을 기반으로 가중치가 갱신되기 때문에, 어떤 데이터와 연결되어 있는지 그리고 해당 데이터의 연결이 유의미한지를 판별하는게 핵심이라 할 수 있습니다. 이러한 관점에서 Graph MoE는 그래프 구조가 유의미한 구조인지 판별 기능에 특화된 Expert 가 있다는게 기존 MoE 와의 차이점이라 할 수 있겠습니다.

3.2. ULTRA

3.3. OpenGraph

3.4. Position

node , edge 그리고 graph 형태마다 발생하는 Expressiveness 와 stability 를 다룬 논문. 또한 GFM 구축시 고민할 Neural Scaling Law 를 data , model 관점에서 언급함.

3.5. GraphAny

4.끝으로