Multi-hop Attention Graph Neural Networks

의의 : 1-hop만 고려하던 기존의 GAT를 multi-hop으로 확장

방법 : Diffusion 개념을 이용하여 1-hop attention matrix를 multi-hop attention matrix로 변환

 

 

Reviewer1

Summary:

전통적인 GNN은 직접적인 이웃들을 통한 aggregate를 반복함으로써 multihop의 정보를 encoding하여 학습한다. Self-Attention module은 이웃의 정보를 선택적으로 aggregate한다. 하지만 현재의 self-attention mechanism은 직접적으로 연결된 neighbor만 고려한다는 한계점이 있다. 본 논문에서는 이러한 문제를 해결하기 위해 간접적으로 연결된 neighbor들의 attention score도 계산하는 모델을 제안한다.

message passing은 인접 행렬의 거듭제곱을 직접 계산하는 것이 scalable 하지 않기 때문에 GNN에서 일반적으로 사용된다. indirect neighbor에 대한 attention score를 얻으려는 task에도 동일한 문제가 있다.
따라서 이 문제를 해결하기 위해 저자는 학습된 attention score를 1-hop neighbor에서 multiple hop neighbor로 diffusion하여 노드에서 도달할 수 있는 indirect neighbor에 대한 attention score를 직접 얻을 수 있는 방법을 제안한다.

 

Q1: immediate neighbor에서 multiple hop 떨어진 neighbor로 attention score를 전파하는 데 사용되는 유사한 diffusion이 어떻게 더 강력할지 명확하지 않습니다.

 

R1: 리뷰어는 GAT가 멀리 떨어진 노드에 대한 attention을 위해 레이어를 여러 개 쌓을 수 있다고 지적합니다. 다층 GAT가 MAGNA만큼 강력하지 않은 두 가지 이유가 있습니다. 첫째, GAT를 쌓으면 우리 논문의 서론에서 설명한 것처럼 oversmoothing 됩니다. 둘째, GAT는 각 레이어에서 학습 가능한 가중치 행렬을 사용하고 더 큰 범위의 이웃을 capture하려면 더 많은 학습 가능한 parameter가 필요하므로 경험적으로 과적합이 발생합니다. 그림 3에서 알 수 있듯이 GAT는 shallow 할 때 더 잘 수행되며, 이 경우 멀리 떨어진 노드에 대한 attention를 capture할 수 없습니다.

대조적으로, single layer에서 MAGNA는 feature aggregation을 위한 multiple hop 정보를 수집합니다. diffusion 과정은 multiple-hop attention weight에 대한 사전 역할을 하며 위의 문제를 해결합니다. 그림 3은 MAGNA가 레이어가 증가함에 따라 성능이 향상되어 GAT를 훨씬 능가함을 보여줍니다.

 

Q2: LayerNorm 및 feed forward로 인해 얼마나 개선되었는지 명확하지 않습니다.

R2: ablation table에 대한 misunderstanding을 지적하고 싶습니다. diffusion이 없으면(table 1의 no-diffusion line) 성능이 LayerNorm/feedforward가 있는 GAT와 매우 유사하여 확산이 중요한 요소임을 나타냅니다. 나머지는 중요하지 않은 요소입니다. 그러나 명확성을 위해 layerNorm 및 feed forward를 제거하여 ablation study에 대한 추가 실험을 추가했습니다(표 1의 다음 마지막 행 참조).

 

 

Reviewer2

Summary:

본 논문은 주로 최단 경로(인접 행렬의 거듭제곱)를 통해 더 멀리 떨어진 노드의 정보를 통합하여 attention 기반 edge coefficient를 학습하는 것을 제안합니다. 또한 저자는 제안된 알고리즘의 스펙트럼 속성과 PPR와의 동등성을 보여줍니다.

Weak points:
The multi-hop attention network 연구들은 이전에 수행되었습니다. (see below). The novelty는 spectral analysis와 the page rank equivalence에 있다.

 

Q1: Isufi et al, 2020년 "EdgeNets'' 논문과의 비교.

R1: “EdgeNets”의 관련 논문을 지적해 주신 리뷰어께 감사드립니다.  본 논문의 41, 42는 또한 Attention 메커니즘을 통한 노드 feature 학습을 위해 multi-hop 정보를 사용합니다. 그러나 EdgeNet은 다음과 같이 MAGNA와 다릅니다. 첫째, 행렬의 거듭제곱에 대한 attention 계산이 다릅니다. "EdgeNets"에서 다른 parameter가 있는 노드 feature을 기반으로 A, A^2, A^3, ... 각각(Eqs, 41, 42에 따라)에 대한 attention score를 계산합니다(Eq. 41의 e_k 참조).

이에 비해 MAGNA는 먼저 노드 feature을 기반으로 1 hop attention matrix A를 계산한 다음 A를 기반으로 A^2 및 A^3의 attention score를 유추합니다. 따라서 (1) A2, A3, 에 대한 attention 계산을 위해 더 많은 parameter가 필요 없기 때문에 우리의 방법은 더욱 parameter 측면에서 효율적입니다. 그리고 (2) Eq. (3)에 의해 계산된 multi-hop attention matrix은 one-hop attention matrix A와 동일한 eigen-vector를 가집니다: 이는 one-hop attention matrix A와 비교하여 lower-pass filter의 효과를 보장하는데 중요합니다. 요약하면, 제안한 MAGNA가 EdgeNets과 비교하여 더 나은 spectral property를 보여줄뿐만 아니라 parameter 효율성도 뛰어납니다.

따라서 (1) 우리의 방법은 A^2, A^3, … 그리고 (2) Eq. (3) 1홉 어텐션 매트릭스 A와 동일한 고유 벡터를 가짐: 이는 1홉 어텐션 매트릭스 A와 비교하여 저역 통과 필터링의 효과를 보장하는 데 중요합니다. 요약하면 제안한 MAGNA가 더 나은 것을 보여줄 뿐만 아니라 EdgeNet과 비교하여 스펙트럼 속성뿐만 아니라 매개변수 효율성도 더 높습니다.

또한 Attention 메커니즘을 제외하고 보다 효과적인 GNN 모델 구조(attention diffusion + layernorm + feedforward)를 설계하고 효율적인 구현 및 이론적 분석도 제공합니다. 오픈 소스 코드가 없기 때문에 표준 벤치마크에서 EdgeNet의 평가를 실행하지 않았습니다. 그러나 우리는 이미 많은 multi-hop 아키텍처(Diffusion-GCN, JK-Net, APPNP)를 포함하여 본 논문에서 20개의 baseline과 비교했습니다.

 

Q3: 학습된 필터가 실제로 그래프에서 low-pass filter인지 어떻게 알 수 있습니까?

R3: 여기서 우리는 misunderstanding을 분명히 하고 싶다: low-pass filter의 결론은 원래의 adjacency matrix이 아니라 학습된 one-hop attention matrix(즉, GAT의 attention matrix)과 multi-hop diffusion matrix을 비교하는 것에 기반합니다. attention matrix와 비교하는 것은 많은 task에서 attention이 그래프 학습을 향상시킨다는 것을 이미 알고 있기 때문에 여기서 더 관련이 있습니다. 우리는 one-hop attention matrix에 기반하여 multi-hop attention matrix를 추론하였습니다. 즉, multi-hop attention matrix는 one-hop attention matrix의 서로 다른 거듭제곱의 linear combination이며 linear coefficient는 Eq. (3)의 theta에서 정의되었습니다. 이는 low-pass conclusion으로 이어집니다.

 

Reviewer3

제안된 방법은 각각의 레이어의 receptive field를 증가시키고 더 넓은 범위의 receptive field를 가지기 위해 더 적은 수의 레이어가 요구됩니다. 또한 제안된 방법으로 두 노드 사이의 attention coefficient는 단순히 두 노드의 function뿐만 아니라 그들의 이웃들의 function이기도 합니다. 제안된 MAGNA method는 GCN에 사용된 유사한 접근 방식(Diffusion-GCN)에 따라 계산된 attention coefficient 에 diffusion step을 도입하는 GAT 네트워크의 확장입니다.

==== Pros: ====

• 제안된 방법은 GAT layer를 model parameter 수를 증가시키지 않고 multi-hop receptive field를 갖게 합니다.
• 본 논문의 두개의 main building block (Graph Attention and Graph Diffusion)은 novel하지 않지만, 그들의 combination은 novel 하고 두가지 다른 task에서 최신의 성능을 달성하였습니다.
• 두 개의 다른 task와 standard benchmark를 사용한 MAGNA와 이전 접근법의 평가가 잘 이루어졌습니다.

Cons:

• The proposed method MAGNA seems to be similar to the APPNP method proposed in [Klicpera 2019a] that also uses diffusion to increase the neighbourhood around each node in a GCN layer (without attention). However the two models are not compared and the later is not included in the Related Work section, even though it is cited previously.
• 제안된 MAGNA는 [Klicpera 2019a]에서 제안된 APPNP와 유사해보입니다. 이 방법 또한 GCN layer의 각각의 노드 주위의 이웃의 범위를 증가시키기 위해 (attention 없이)diffusion을 사용하였습니다. 하지만 두 모델은 비교되지 않았고 이전에 cited 되었음에도 Related work에 포함되지 않았습니다.
• ablation study는 좋은 idea 였지만 어떻게 이뤄졌는지 명확하지 않습니다.

Q3: The motivation behind including layer normalization and deep aggregation or why they are useful isn’t entirely clear.

Q3: layer normalization과 deep aggregation을 포함시킨 동기 또는 그것들이 왜 유용한지가 전체적으로 명확하지 않습니다.

R3: The motivation of these two components is as follows. For ‘‘deep aggregation”, we can view it as a learnable activation function compared to elu activation in GAT. 두가지 구성요소의 동기는 다음과 같습니다. "deep aggregation"에서 우리는 GAT의 elu activation과 비교해서 학습가능한 activation function 으로 볼 수 있습니다. 그 이유는 ‘two layer MLP’가 다양한 function을 근사(please refer: Pinkus, Allan. "Approximation theory of the MLP model in neural networks." Acta numerica 8.1 (1999): 143-195.)할 수 있기 때문입니다. 그러므로 GAT의 'shallow'한 elu와 비교해서 우리는 MLP를 학습가능한 deep aggregation 방법으로 볼 수 있습니다. 

"Layer normalization"의 경우, 우리는 recursive 방식(multiple multiplication)으로 attention matrix를 사용하여 diffused attention을 계산합니다(Eq. 5 참조). Layer normalization은 recurrent computation procedure에서 hidden state dynamics을 안정화하는데 매우 효과적이므로 학습 절차를 안정화하는 데 도움이 됩니다(참조: Ba, JL, Kiros, JR, & Hinton, G.E. (2016). Layer normalization. arXiv preprint arXiv :1607.06450). 우리는 논문에 demonstrate을 포함시켰습니다.

Q5: MAGNA는 GAT와 동일한 수의 attention value를 계산한 후에 diffuse하지 않습니까? diffusion이 사용될 때 layer normalization이 왜 중요한지 그것 없이는 안 되는지에 대한 생각은 있습니까?

R5: 우리는 GAT에서 동일한 수의 attention value를 계산합니다. 우리는 recursive 방식(multiple multiplication)으로 attention matrix를 사용하여 attention diffusion을 완료합니다. Layer normalization은 recurrent computation procedure에서 hidden state dynamics을 안정화하는데 매우 효과적입니다(참조: Ba, JL, Kiros, JR, & Hinton, G.E. (2016). Layer normalization. arXiv preprint arXiv :1607.06450). 

 

Reviewer4

저자들은 최신의 attetion 기반 GNN인 MAGNA를 제안하였습니다. main contribution은 일반적인 one hop대신 multi-hop을 고려함으로써 receptive field를 상당히 증가시킨데에 있습니다. 기술적인 문제는 효율적인 방법으로 모든 관련 노드에 대한 attention score를 얻는 것으로 구성됩니다. MAGNA는 geometric distribution와 결합된 diffusion 기반 기술을 사용하여 이 문제를 해결합니다. 저자는 근사치를 추가로 허용하고 흥미로운 이론적 통찰력을 제공한다는 것을 보여줍니다(예: page rank와의 관계 표시).

 

Q3: Diffusion process가 어떻게 모델의 일반화를 보장합니까?

R3: 첫째, Diffusion 과정은 GAT와 비교하여 attention 계산에서 동일한 parameter 효율성을 갖습니다. 더욱이, diffusion 과정의 spectral analysis은 그러한 diffusion이 lower-pass filter로 볼 수 있음을 보여줍니다(큰 그래프 구조에 초점을 맞추고 noise가 많은 그래프에 더 robust 함).