통합 다중 그래프 신경망

1. 통일된 관점에서 본 GNN

1. 기존 GNN 전파 패러다임

GNN은 어떻게 영공에서 전파되나요? 아래 그림과 같이 노드 A를 예로 들어 보겠습니다.

먼저 이웃 노드 N(A)의 정보를 하나로 집계합니다. h _{N( A)}⁽¹⁾을 거쳐 A의 상위 레이어 표현 h_N(A)⁽¹⁾ 과 결합하여 통과했습니다. 변환 함수(예: 공식의 Trans(·))를 통해 A h_N(A)⁽²⁾의 다음 수준 표현을 얻습니다. 이것이 가장 기본적인 GCN 전파 패러다임이다.

또한 분리된 전파 프로세스가 있습니다:

모직물 두 가지 방법의 차이점은 무엇인가요? 분리된 전파 패러다임에서는 특징 추출기, 즉 변환 함수를 먼저 사용하여 초기 특징을 추출한 다음 추출된 특징을 집계 함수에 넣어서 집계하는 것을 볼 수 있습니다. 추출과 집합이 분리되는 것, 즉 디커플링(decoupling)이 이루어지는 것이다. 이것의 장점은

• 이전 변환 기능을 자유롭게 디자인하고 어떤 모델이든 사용할 수 있습니다.
• 장거리 연결 정보를 얻기 위해 Aggregation 중에 많은 레이어를 추가할 수 있지만 Aggregation 함수에는 최적화해야 할 매개변수가 없기 때문에 과잉 매개변수화의 위험에 직면하지 않습니다.

위는 두 가지 주요 패러다임이며, 노드의 임베딩 출력은 네트워크의 마지막 레이어 또는 중간 레이어의 잔여 레이어를 사용할 수 있습니다.

위의 검토를 통해 GNN에는 두 가지 기본 정보 소스가 있음을 알 수 있습니다.

• 네트워크의 토폴로지 구조: 일반적으로 그래프 구조의 다양한 정보 속성을 캡처할 수 있습니다.
• 노드의 특성: 일반적으로 노드의 저주파 및 고주파 신호가 포함됩니다.

2. 통합 최적화 프레임워크

GNN의 전파 메커니즘을 기반으로 기존 GNN에는 두 가지 공통 목표가 있음을 알 수 있습니다.

• 노드의 특성에서 유용한 정보를 인코딩합니다.
• 토폴로지의 평활화 기능을 사용하세요.

그러면 이 두 가지 목표를 설명하기 위해 수학적 언어를 사용할 수 있을까요? 누군가 다음 공식으로 표현된 GNN 최적화 통합 프레임워크를 제안했습니다.

최적화 목표의 첫 번째 항목:

은 기능 피팅 용어입니다. 학습된 노드 표현 Z를 원래 특성 H에 최대한 가깝게 만드는 것이 목표이며, F₁, 자유롭게 설계할 수 있는 그래프 컨볼루션 커널입니다. 컨볼루션 커널이 항등 행렬 I인 경우 전체 통과 필터와 동일하며, 컨볼루션 커널이 0 행렬인 경우 저역 통과 필터이고, 컨벌루션 커널이 라플라시안 행렬 L인 경우는 다음과 같습니다. 하이패스 필터. 최적화 목표의 두 번째 항은 공식적으로 행렬의 추적이며, 그 기능은 그래프의 정규항입니다. 실제로 두 번째 항은

형식으로 확장됩니다. 그 의미는 그래프에서 인접한 두 노드 사이의 특징 차이 정도를 포착하는 것입니다. 그래프. 이 목표를 최소화하는 것은 나와 내 이웃을 더 유사하게 만드는 것과 같습니다.

3. 기존 GNN을 이해하려면 통합 최적화 프레임워크를 사용하세요

GNN은 대부분 이 목표를 최적화하고 있습니다.

When 매개변수: When

, 최적화 목표는 다음과 같습니다:

편도함수를 얻습니다:

상단을 두자 얻은 결과는 다음과 같습니다. 다음을 얻기 위해 더 확장됩니다:

이는 K번째 레이어의 모든 노드 표현이 인접 행렬에서 K-1번째 레이어의 노드 표현의 전파 프로세스와 동일하다는 것을 의미하며, 파생 이후에는 끝까지, W* 특성 변환을 완료한 후 인접 행렬에서 초기 특성 X가 K번 전파되는 것과 동일하다는 것을 알 수 있습니다. 실제로 이것은 비선형 레이어가 제거된 GCN 또는 SGC 모델입니다.

매개변수 F1=F

2

=I, ζ=1, ξ=1/α-1, α∈(0,q]인 경우 전체 통과 필터를 선택하여 최적화합니다. 목표는 다음과 같습니다:

이때 최적화 목표의 폐쇄형 솔루션을 얻기 위해 Z의 편도함수를 찾고 편도함수를 0으로 설정합니다.

결과를 약간 변형하면 다음과 같은 공식을 얻을 수 있습니다.

위 공식은 PPNP 모델인 개인화된 PageRank에서 노드 기능이 전파되는 과정을 나타내는 것을 알 수 있습니다.

도 그러한 모델입니다. 경사하강법을 사용하여 이를 찾고 단계 크기를 b로 설정하면 반복 항은 시간 k-1에서 목적 함수의 편도함수입니다. Z에 대한 존중입니다.

얻을 때:

이것은 APPNP 모델입니다. APPNP 모델이 등장한 배경은 PPNP 모델에서 행렬의 역연산이 너무 복잡하기 때문에 APPNP는 이를 해결하기 위해 반복 근사법을 사용합니다. APPNP와 PPNP가 모두 동일한 프레임워크에서 나오므로 PPNP로 수렴할 수 있다는 것도 이해할 수 있습니다.

4. 새로운 GNN 프레임워크

새로운 피팅 용어를 디자인하는 한

O

fit

해당 그래프 정규화 항을 설계합니다. Oreg, 그리고 새로운 솔루션 프로세스를 통해 새로운 GNN 모델을 얻을 수 있습니다. ① 예시 1: all-pass filtering에서 low-pass filtering으로 앞서 언급한 것처럼 all-pass filter 아래의 컨볼루션 커널

F

1

= F₂=I _{, 컨볼루션 커널이 라플라시안 행렬 L인 경우 고역 통과 필터입니다. 이 두 상황에 가중치를 적용하여 얻은 GNN이 저역 통과 정보를 인코딩할 수 있는 경우:} when

는 정확한 해결책을 얻을 수 있습니다:

마찬가지로, 반복적으로 해결할 수 있습니다:

5. Elastic GNN

통합 프레임 앞에서 언급한 정규항은 L2 정규항과 동일하며, 이는 그래프에서 임의의 두 점 사이의 차이 정보를 계산하는 것과 같습니다. 일부 연구자들은 L2 정규화가 너무 전역적이어서 전체 그래프의 부드러움이 동일해지는 경향이 있어 현실과 완전히 일치하지 않는다고 생각합니다. 따라서 L1 정규항을 추가하는 것이 그래프의 상대적으로 큰 변화에 불이익을 줄 것이라고 제안되었습니다.

L1 정규 학기 부분은 다음과 같습니다.

요컨대, 위의 통합 프레임워크는 다음과 같습니다.

• A를 사용할 수 있습니다. GNN을 이해하기 위한 더 거시적인 관점
• 우리는 이 통합 프레임워크에서 새로운 GNN

을 설계할 수 있습니다. 그러나 이 통합 프레임워크는 동종 그래프 구조에만 적용할 수 있습니다. 보다 일반적인 다중 관계 다이어그램의 구조.

2. 관계형 GNN 모델

1, RGCN

소위 다중 관계 그래프는 아래 그림과 같이 간선 유형이 1보다 큰 그래프를 말합니다.

이런 종류의 다중 관계 다이어그램은 현실 세계에 매우 널리 퍼져 있습니다. 예를 들어 화학 분자의 여러 유형의 분자 결합, 사회 관계 다이어그램의 사람들 간의 다양한 관계 등이 있습니다. 이러한 그래프의 경우 관계형 그래프 신경망을 사용하여 모델링할 수 있습니다. 주요 아이디어는 N개의 집계 결과를 얻기 위해 N개의 관계가 있는 그래프를 개별적으로 집계한 다음 N개의 결과를 집계하는 것입니다.

수식으로 표현하면 다음과 같습니다.

먼저 모든 관계 R 중에서 관계 r을 선택합니다. , 그리고 집계를 위해 이 관계 Nr 을 포함하는 모든 노드를 찾습니다. 여기서 Wr ^{은 다양한 관계에 가중치를 부여하는 데 사용되는 가중치입니다. 따라서 그래프의 관계 수가 증가할수록 가중치 행렬} Wr ^{도 증가하게 되어 과잉 매개변수화(Over-parameterization) 문제가 발생함을 알 수 있다. 또한, 토폴로지 관계 다이어그램을 관계에 따라 분할하면 지나치게 평활화될 수도 있습니다.}

2. CompGCN

과다 매개변수화 문제를 해결하기 위해 CompGCN은 N 관계형 행렬을 대체하기 위해 벡터화된 관계형 인코더를 사용합니다. 세 방향의 자체 루프 관계:

관계 삽입도 각 반복마다 업데이트됩니다.

그러나 이러한 경험적 설계와 파라메트릭 인코더는 과도한 매개변수화를 유발할 수도 있습니다. 그러면 위의 고려 사항을 바탕으로 최적화 목표 관점에서 보다 안정적인 GNN을 설계하는 동시에 기존 GNN의 문제를 해결할 수 있는지 작업의 출발점을 얻습니다.

3. 통합 다중 관계 그래프 신경망

올해 EMR GNN이 공개되었습니다. 다음으로 다중 관계 그래프에 적합한 GCN을 설계하는 방법을 다음 세 가지 측면에서 주로 논의하겠습니다.

적절한 통합 최적화 알고리즘 설계 방법

메시지 전달 메커니즘
GNN 모델 설계 방법
1. 통합 최적화 알고리즘
• 이 최적화 알고리즘은 두 가지 요구 사항을 충족해야 합니다.

그래프에서 동시에 여러 관계를 캡처할 수 있어야 합니다.

그래프에서 다양한 관계의 중요성을 모델링할 수 있어야 합니다.
• We 다중 관계 그래프에서 제안하는 통합 다중 관계 그래프 정규항은 다음과 같습니다.

이 정규항은 그래프 신호의 평활화 능력을 포착하기 위한 것이기도 하며, 하지만 이 인접 행렬은 캡처된 관계 r을 기반으로 하며 정규화 제약 조건이 적용되는 매개 변수

μ

r은 특정 관계. 두 번째 항은 계수 벡터의 두 번째 정규형 정규화로, 계수 벡터를 더욱 균일하게 만드는 것입니다. oversmoothing 문제를 해결하기 위해 원래의 특징 정보가 손실되지 않도록 피팅 항을 추가했습니다. 피팅 항과 정규 항의 합은 다음과 같습니다.

이전 장에서 언급한 통합 프레임워크와 비교하여 여기서 설계한 목적 함수에는 두 개의 노드 수정 Z와 관계 행렬 매개변수 μ가 포함됩니다. 변하기 쉬운. 따라서 이러한 최적화 목표를 기반으로 메시지 전파 메커니즘을 도출하는 것도 어려운 과제입니다.

2. 메시지 전달 메커니즘의 파생

여기서 반복 최적화 전략을 채택합니다.

• 먼저 노드 표현 Z를 수정한 다음 매개변수 μ
• 을 최적화합니다. 이전 반복의 결과 μ는 노드 표현 Z

을 최적화하는 데 사용됩니다. 노드 표현 Z가 고정되면 전체 최적화 목표는 μ에만 관련된 목적 함수로 변질되지만 이는 제한적입니다. 목적 함수. 해결하다. 먼저 상수를 찾은 다음 각 관계에서 가중치 계수를 업데이트합니다. 전체 업데이트 프로세스는 지수 경사 하강 알고리즘과 유사합니다.

관계 계수 μ를 수정하여 Z를 업데이트합니다. 이때 최적화 목표는 다음과 같은 형태로 변질됩니다. Z의 목적 함수 의 부분 도함수를 0으로 설정하면 다음을 얻을 수 있습니다.

그러면 Z의 폐쇄 형식 해는 다음과 같습니다.

마찬가지로 반복 방법을 사용하여 대략적인 솔루션을 얻을 수 있습니다. 이 프로세스는 다음과 같이 표현할 수 있습니다.

파생된 메시지 전달 메커니즘에서 설계가 과도한 스무딩과 과도한 매개변수화를 피하세요. 아래에서 증명 과정을 살펴보겠습니다.

원래 다중 관계 PageRank 행렬은 다음과 같이 정의됩니다.

맞춤형 다중 관계 PageRank 행렬은 이를 기반으로 자체 노드를 반환할 확률을 추가합니다.

위의 순환 방정식을 풀면 다중 관계 맞춤형 PageRank 행렬을 얻을 수 있습니다.

얻을 수 있습니다:

이것은 우리가 제안한 솔루션으로 얻은 폐쇄형 솔루션입니다. 즉, 우리의 전파 메커니즘은 노드의 개인화된 PageRank 매트릭스에서 기능 H의 전파와 동일할 수 있습니다. 이러한 전파 메커니즘에서는 노드가 일정 확률로 자신의 노드로 돌아올 수 있기 때문에 정보 전송 과정에서 자신의 정보가 손실되지 않으므로 과잉 평활화 문제를 방지할 수 있습니다.

또한 우리 모델은 수식에서 볼 수 있듯이 각 관계에 대해 학습 가능한 계수가 하나만 있기 때문에 과잉 매개변수화 현상도 완화합니다. μ _r , 이전 인코더 또는 가중치 행렬 w_r과 비교하면 매개변수 수에 비해 매개변수의 크기는 거의 무시할 수 있습니다. 다음 그림은 우리가 설계한 모델 아키텍처를 보여줍니다.

여기서 RCL은 매개변수 학습 단계이고 Pro 단계는 기능 전파 단계입니다. 이 두 단계가 함께 메시징 계층을 형성합니다. 그렇다면 추가 매개변수를 추가하지 않고 어떻게 메시징 계층을 DNN에 통합할 수 있을까요? 우리는 또한 디커플링 설계 아이디어를 따릅니다. 먼저 MLP를 사용하여 입력 특징을 추출한 다음 우리가 설계한 여러 레이어의 메시지 전달 레이어를 통과해도 지나치게 평활화되지 않습니다. 최종 전송 결과는 MLP에 의해 처리되어 노드 분류를 완료하고 다운스트림 작업에 사용될 수 있습니다. 위의 과정은 다음과 같은 수식으로 표현된다.

f(X;W)는 MLP를 통해 입력특징을 추출한다는 의미이고, 다음 EnMP(K)는 추출결과를 의미한다. K 레이어를 통과합니다. 메시지 전달 θ_{은 분류된 MLP를 나타냅니다.} 역전파에서는 두 MLP의 매개변수만 업데이트하면 되며, 순방향 전파 프로세스 중에 EnMP의 매개변수를 학습할 필요가 없습니다. .

우리는 EMR-GNN의 매개변수가 주로 전후의 두 MLP와 관계 계수에서 나온다는 것을 알 수 있습니다. 레이어 수가 3보다 클 경우 EMR-GNN의 매개변수 수가 GCN보다 적고 다른 이종 그래프보다 훨씬 적음을 알 수 있습니다.

이렇게 적은 수의 매개변수로도 우리 EMR-GNN은 다음과 같이 다양한 노드 분류 작업에서 여전히 최고 수준에 도달할 수 있습니다.

또한 레이어 수가 증가한 후 다양한 네트워크 구조의 분류 정확도 변화를 비교했습니다. 아래 그림에서 볼 수 있듯이 레이어 수가 64개로 증가해도 모델은 여전히 ​​높은 정확도를 유지할 수 있습니다. 레이어 수가 16개 이상으로 증가하면 원본 RGCN의 메모리가 부족해지며 더 많은 레이어를 중첩할 수 없습니다. 이는 매개변수가 너무 많기 때문입니다. GAT 모델의 성능은 과도한 스무딩으로 인해 저하됩니다.

또한 EMR-GNN은 더 작은 데이터 크기에서 전체 샘플의 분류 정확도를 달성할 수 있는 반면 RGCN은 많이 떨어지는 것을 발견했습니다.

EMR-GNN에서 학습한 관계 계수 μr이 정말 의미가 있는지도 분석했는데, 무엇이 의미가 있을까요? 우리는 관계 계수가 중요한 관계에 더 큰 가중치를 부여하고 중요하지 않은 관계에 더 적은 가중치를 부여하기를 원합니다. 분석 결과는 아래 그림과 같습니다. 녹색 히스토그램은 특정 관계에서 분류 정확도가 더 높을 경우 이 관계를 나타냅니다. 중요하게 여겨질 수 있습니다. 파란색 열은 EMR-GNN에서 학습한 관계 계수를 나타냅니다. 청록색 비교를 통해 관계 계수가 관계의 중요성을 반영할 수 있음을 알 수 있습니다.

마지막으로 아래 그림과 같은 시각적 디스플레이도 만들었습니다.

EMR-GNN으로 훈련된 노드 임베딩이 다음과 같은 구조화된 정보를 전달할 수 있음을 알 수 있습니다. 동일한 유형의 노드를 더욱 응집력 있게 만들고, 서로 다른 유형의 노드를 최대한 분리하며, 다른 네트워크보다 분할 경계를 더 명확하게 만들 수 있습니다.

4. 요약

1. GNN을 이해하기 위해 통일된 관점을 사용합니다

① 이러한 관점에서 보면 기존 GNN에 어떤 문제가 있는지 쉽게 알 수 있습니다

② 통일된 관점은 GNN을 재설계할 수 있는 기반을 제공할 수 있습니다

2. 목적 함수 관점에서 새로운 다중 관계형 GNN을 설계하려고 합니다

① 먼저 통합 최적화 프레임워크를 설계합니다

② 이러한 최적화 프레임워크를 기반으로 메시지 전달 메커니즘을 파생했습니다.

③ 적은 수의 매개변수를 사용하는 이 메시지 전달 메커니즘을 간단히 MLP와 결합하여 EMR-GNN을 얻습니다

3. EMR-GNN의 장점은 무엇인가요?

① 신뢰할 수 있는 최적화 목표에 의존하므로 얻은 결과도 신뢰할 수 있고 기본 원리를 수학적으로 설명할 수 있습니다.

② 기존 Relation GNN의 과도한 평활화 문제를 해결할 수 있습니다

③ 매개변수화 문제 해결

④ 학습이 쉽고, 더 작은 매개변수로 더 나은 결과를 얻을 수 있습니다.

5. Q&A 세션

Q1: 관계 계수 학습과 주의 메커니즘 간에 차이가 있나요?

A1: 여기서의 관계 계수 학습은 최적화 프레임워크를 통해 파생된 업데이트 프로세스인 반면, Attention은 역전파를 기반으로 학습해야 하는 프로세스이므로 둘은 최적화 측면에서 본질적으로 다릅니다.

Q2: 대규모 데이터 세트에 대한 모델의 적용 가능성은 어떻습니까?

A2: 부록에서 모델의 복잡성을 분석했습니다. 복잡성 측면에서는 RGCN과 동일한 수준이지만 매개변수 수가 RGCN보다 작으므로 우리 모델이 더 적합합니다. 대규모 데이터 세트.

Q3: 이 프레임워크에 에지 정보를 통합할 수 있나요?

A3: 피팅학기나 정규학기에 통합될 수 있습니다.

Q4: 이런 수학 기초는 어디서 배워야 하나요?

A4: 일부는 이전 작업을 기반으로 하며, 최적화와 관련된 수학적 이론의 다른 부분은 좀 더 고전적인 최적화 논문에서도 사용됩니다.

Q5: 관계 다이어그램과 이종 다이어그램의 차이점은 무엇인가요?

A5: 관계형 그래프는 이종 그래프이지만 우리는 일반적으로 이종 그래프를 노드 유형이나 간선 유형이 1보다 큰 그래프라고 생각합니다. 관계도에서 우리는 특히 1보다 큰 관계범주에 관심을 갖는다. 후자가 전자를 포함하는 것으로 이해될 수 있다.

Q6: 미니 배치 훈련을 지원할 수 있나요?

A6: 지원합니다.

Q7: GNN의 향후 연구 방향은 휴리스틱 설계보다는 엄격하고 해석 가능한 수학적 파생에 더 기울어져 있습니까?

A7: 우리는 엄격한 해석이 가능한 수학적 유도가 신뢰할 수 있는 설계 방식이라고 생각합니다.

위 내용은 통합 다중 그래프 신경망의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!