챕터
•
Limitations of GNN
•
Positional-aware GNN
•
Identity-aware GNN
•
Robustness of GNN
•
Perfect GNN model 이란 같은 neighbor를 가지는 node는 같은 embedding을가지고, 다른 neighbor를 가지는 node는 다른 embedding을 가지는 것이다.
•
같은 neighbor를 가지지만 position에 따라서 다르게 embedding해야 되는 경우 문제가 생김
•
다른 neighbor를 가지지만 computational graph가 같은 경우 같은 embedding으로 잡히기 때문에 문제가 생김 (v1, v2 둘다 neighbor가 2개, 하위 노드도 neighbor가 2개 여서 computational graph가 같다고 말한다고 이해함)
•
Structure-aware 와 position-aware task 로 두가지 GNN 종류가 있다.
•
Structure-aware의 경우 v1과 v2를 구분할 수 있어서 기존 GNN을 그대로 사용하면 된다.
•
Position-aware task의 경우 computational graph 가 동일하기 때문에 구분할 수 없다.
•
position 에 대한 정보를 나타내는 방법으로 여러개의 anchor를 뽑아 anchor로부터의 distance를 측정한다.
•
Anchor-set을 만들어서 상대적인 거리를 측정하기도 한다.
•
이렇게 해서 구한 position encoding을 각각의 node embedding으로 사용한다.
•
Augmented node feature라 생각할 수도 있다!
•
다른 node이지만 같은 computational graph를 가져서 같은 embedding으로 계산되는 문제가 있다.
•
해결방법은 root node에 대해서 colorize하고 computational graph에서 나타낸다.
•
Graph 구조가 다르다면, computational graph에서 colorize 되는 부분이 달라지기 때문에 구별할 수 있다.
•
edge level과 graph level에 대해서도 똑같이 적용할 수 있다.
•
GNN에 대해서 바로 적용하려면, node에 따라서 다른 network를 사용하면 된다.
•
다른 종류 (color)의 node에 대해서 다른 network로 aggregate 한다면 computation graph가 같아도 다른 embedding을 만들어낼 수 있을 것이다.
•
ID-GNN을 사용하면 cycle 수도 구할 수 있다.
→ colorize 된 root node가 몇 번째 level에서 몇 개 등장하는지 센다
•
Attack의 종류에는 attacker가 target node를 직접 조작할 수 있는 direct attack과 간접적으로 node, edge등을 조작하는 indirect attack이 있다.
•
Direct attack 과 indirect attack에 대한 예시
•
Adversarial attack을 할 수 있도록 graph를 바꾸려면 어떻게 해야 할까?
•
원래 가장 높은 확률로 예측되는 class에 대한 확률을 줄이고, 다른 class에 대한 확률을 높이면 된다.
•
원래 graph에서 adjacency matrix나 feature matrix에서 조금만 조작을 가한다.
•
이때 이 변화가 크면 attack이 일어난 것을 알 수 있으므로 차이는 거의 없어야 함
•
target node에 대한 class prediction 과 graph manipulate 이후 target node에 대한 class prediction이 다르면 된다.
•
새로운 class로 분류될 확률을 증가시키고, 원래 class로 분류될 확률을 감소시키도록 학습한다.
•
위의 델타 값이 최대가 되로고 학습한다.
•
2800 개의 node, 8000의 edge가 있는 graph에서 target node와 붙어있는 5개의 edge를 바꿨더니 예측하는 class가 완전히 달라짐
•
Direct attack이 가장 효과적인 결과를 낸다.
•
figure에서 classification margin이 작을수록 잘못 classfiy 된 아이템들이 가지는 prediction probability가 큰 것이다.
•
다행(?)인 것은 GCN은 indirect attack에 대해서 robust하다는 점
•
개인적인 의견
◦
실제 recommendation system의 경우 target node에 direct attack을 가하는 것이 쉽지는 않기 때문에 그나마 긍정적인 결과이다.
◦
하지만 특정 사람이 의도적으로 특정 아이템을 추천 알고리즘 상에 노출시키고자 반복, 지속적으로 아이템을 view하거나 click한 아이템을 DB에 넣는다면, 충분히 상위에 올라갈 수 있지 않을까?
◦
예를들면 A라는 아이템이 있을 때, 임의로 A→B→A, A→C→A, A→D→A 등의 sequence를 만든다면, 모든 아이템과 A라는 아이템이 graph edge로 연결될 것이며, 최종 추천 결과에서 등장할 확률이 높아질 것