15. Chi tết hơn về Graph - GCN-GraphSage

Mở đầu

Ta đi sâu vào chi tiết hơn về Graph và những vấn đề liên quan, tham khảo chính từ https://viblo.asia/p/deep-learning-graph-neural-network-a-literature-review-and-applications-6J3ZgP0qlmB

Ví dụ ta sử dụng mô hình CNN cho bài toán phân loại ảnh chó mèo, các kernel đóng vai trò như những cửa sổ trượt rút đặc trưng từ ảnh. Thực chất kernel chính là trọng số của mô hình CNN được training với backpropagation. Mỗi kernel sẽ có giá trị riêng, tác dụng khác nhau

Trong thực tế cũng rất nhiều bài toán dùng non-euclidean data, nếu các filter sử dụng các pixel lân cận thì Graph tổng hợp các degree, và các node không có tình thứ tự

Các biểu diễn đơn giản nhất cho các nút và cạnh trên đồ thị là các vactor embedding. Từ đó các nút trên đồ thị được ánh xạ f qua 1 không gian vector mới mà 2 nút u và v là tương đồng nếu khoảng cách vector embedding zu và zv trên không gian mới nhỏ

thêm 1 tí lí thuyết graph:

- Self-loop: nút có cạnh nối chính nó

- Multi-graph: có nhiều hơn 1 cạnh nối 2 đỉnh

- Homogeneous graph: đồ thị đơn, mỗi nút và cạnh biểu diễn 1 object

- Heterogrneous graph/multi-model graph: nút và cạnh thể hiện nhiều mối liên kêt -> knowledge graph

- Bi-partite graph: đồ thị lưỡng cực

- adjacency matrix: (ma trận thể hiện nối) thường là thưa (sparse matrix). Ngoài ra còn adjacency list cho tiện

1 số ứng dụng:

- link predict

- node classificate

- clustering, community detection

Node Embedding

Nói về Graph-based Learning, đầu tiên nói về Graph-based Embedding, gồm 2 nhóm chính:

- Vertex Embedding (Node embedding): ánh xạ mỗi nút sang 1 letent space khác với D-dims

- Graph Embedding: ánh xạ 1 graph/sub-graph thành 1 vector duy nhất (ví dụ cấu trúc phân tử) -> bài toán graph/sub-graph classidication

Thường các giải thuật về graph-based learning (graph-based embedding, graph neural network) đều dựa trên giả định rằng các nút gần nhau sẽ có đặc trưng về feature giống nhau. Tuy nhiên 2 nút không kề nhau vẫn có thể có những đặc điểm giống nhau

Random walk

Nhớ lại mô hình word2vec: ý tưởng đơn giản là xây dựng 1 mô hình có khả năng ánh xạ các từ sang 1 không gian vector mô tả các từ thường xuất hiện cùng nhau, cùng 1 context sẽ có các embedding vector gần nhau (euclide distance, cosine distance) gồm 2 mô hình chính:

- CBOW: sử dụng context word để predict target word ở giữa

- skip-gram: sử dụng target word để predict context word xxung quanh

Deep walk

Dựa trên ý tưởng chủ đạo từ Word2Vec (skip-gram). Thuật ngữ Graph sampling là chỉ sử dụng random walk( hay đi ngẫu nhiên trên đồ thị, kể cả đi ngược lại bước trước đó) -> Biến đồ thị thành sequence 1D, các nút thành từ trong word2vec với độ dài câu(số bươc của random walk) không cố định

mỗi nút được biểu diễn bằng 1 embedding vector (128D). Sử dụng các thuật toán dimension reduce để hiểu

Node2Vec

Dựa trên ý tưởng DeepWlk và Word2Vec. Điểm khác là ngoại trừ Random walk còn thêm 2 thông số P và Q để điều chỉnh các bước đi ngẫu nhiên:

- P: return parameter - khả năng quay lại nước trước đó

- Q: in-out parameter - khả năng "gần" hay "xa" hơn nút ban đầu. Với q > 1thì có xu hướng đi quanh nút ban đầu, nếu q <1 thì ngược lại

1 số mô hình Vertex Embedding: LINE (Line Large-scale Information Network Embedding), HOPE, ...

Hạn chế nói chung:

- DeepWalk và Node2Vec đều dựa trên ý tưởng Word2Vec. Nếu bài toán có domain hẹp và ít có vấn đề, nhưng với các nút/liên kết mới thì chưa có biểu diễn

- Chỉ dựa vào thông tin các nút kề nhau, chưa dùng đến node feature hay thuộc tính từng độ thị -> không có khả năng adapt, generalization trên unseen data-> chia thành tranductive learning method và inductive learning method

Spectral vs Spatial Graph Neural Network
Spectral Graph Neural Network: liên quan các vấn đề phân tách ma trận eigen-decomposition, eigenvector, eigenvalues. Thường có chi phí tính toán lơn tên thay bới spacttal-based

Spatial Graph neural network: dựa vào ý tưởng xây dựng các node embedding phụ thộc vào cá node lân cận

GCN 2015 Graph Convolution Network

Semi-Supervised Classification
Ta định nghĩa 1 mô hình GCN:

- 1 đồ thị G = (V,E)

- 1 adjacency matrix A nxn

- X thuộc R[nxd] là feature matrix ứng các nút, n là tổng số nút, d là số chiều feature node

Ví dụ:

- Mỗi nút là 1 trọng số
- Giả sử các nút kề nhau gần giống nhau. Tính giá trị pi = mean(giá trị các nút lân cận + giá trị vi). Các nút khác tương tự

-> Ta có kết quả mới

Thực hiện tương tự nhiều lần:

- Có thể thấy giá trị càng ngày càng san đều hơn, những nút gần nhau sẽ có giá trị gần nhau hơn (giống Gaussian Blur Kernel của CNN), những nút có cấu trúc liên kết giống nhau sẽ nhận giá trị giống nhau

- Giả sử ta thế A qua 2 bước -> giá trị của A bị ảnh hưởng bởi các nút trong phmaj vi 2 bước từ A

- Phép toán mean có thể thay thế bằng 1 phép toán khác, gọi chung là aggregation function (xem GraphSage).

Tóm lại:

Với N(v) là tập các nút lân cận của v

Cấu trúc GCN:

- Mỗi hidden layer có thể biểu diễn:

Mỗi Hi có kích thước N x Fi với Fi thể hiện số feature đầu ra của từng nút

- init H0 = X là trọng số khởi tạo luôn là node feature của từng nút
- Hàm f có thể viết thành:

Wi là ma trận trọng số của layer i, delta là activation function, ví dụ là ReLU
- Đến đây có 2 hạn chế:

+ Việc dot product với A có giá trị các node kề nhưng chưa bao gồm A -> A = A + I (identity matrix)

+ Những nút có degree cao gây ảnh hưởng lớn hơn. Đồng thời các khoảng giá trị chưa được normalize, dễ dẫn tới vanishing/exploding gradient trong quá trình backpropagation -> normalize A bằng cách D-1A với D là degree matrix (lấy trung bình feature các nút kề)

- Ta sử dụng Symmetric Normalization thì thành

Hạn chế:

- memory requirement: mỗi epoch cập nhật full-batch gradient descent (vì mô hình dựa vào toàn bộ tróng số và adjacency matrix A) thay vì mini-batch gradient descent

- Directed edges and edges feature: chưa được nghĩ tới (hiện adj matrix A là binary matrix)

- Limiting assumption: là đặt ngang hàng vi và các nút lân cận (A = A + I) -> có thể thêm lambda A = A + lambdaI

- Transductive setting: kém khi mô hình có thay đổi với việc thêm những nút mới

GraphSage 2017
Tổng quan:

- Inductive learning method có khả năng tổng quát hóa tốt hơn với unseen data

- Ý tưởng vẫn là dựa trên các node lân cận. Có thêm hàm aggrerate để tổng hợp lại thông tin
- Mini-batch update gradient descent và là 1 spatial GNN method (khắc phục hạn chế lớn nhất của GCN về full-batch gradient descent)

Chi tiêt thuật toán:

- h0v = xv, tổng hợp các thông tin từ lân cận u ta có vector biểu diễn hkN(v). Các hàm aggre có thể là mean, pooling,... hoặc các mạng như LSTM

- concat hkN(v) với thông tin tại v ở step trước đó k-1

- đưa vector sau concat qua 1 fully connected layer với activation function như ReLU. Sau đó normalize

- Sau K lần (K aggre function), ta có feature vector zv = hKv

- Có thể stack nhiều aggre function với mong muốn học sâu hơn và được nhiều các abstract feature. Tuy nhiên việc này không đem lại nhiều kết quả, thậm chí ảnh hưởng performance. Thường 1,2 aggre là đủ

- Với việc có aggre function, model có khả năng tổng quát tốt hơn (better generalization) với các dữ liệu mới (unseen node). Dữ liệu mới chỉ cần được tính trong phạm vi chính nó và lân cận, không cần tính lại toàn bộ

Aggregator function

Mục đích: tổng hợp các thông tin lân cận
Dạng đồ thị không thứ tự, vị trí tương đối như sequence, image nên cần tính symmetric (ít bị ảnh hưởng bởi tính hoán vị của các nút lân cận) như mean, pooling, LSTM
- Mean aggregator: là 1 non-parametric và symmetric, là việc lấy trung bình vector tại mỗi vị trí (element wise mean operation). Việc thực hiện concat 2 vector gần tương tự như 1 "skip-connection" trong residual network

- LSTM aggregator: parametric, thiết kế cho dạng sequence, non symmetric. Tuy nhiên vẫn dùng được trong trương hợp hoán vị ngẫu nhiên từ input là các nút lân cận

- Pooling aggregator: vừa parametric vừa symmetric. Với delta là activation function, max là toán tử -> element-wise max-pooling operation. Trong thực nghiệm thì kết quả tốt nhất

Loss function
- Với bài toán supervised learning, đầu ra là các feature embedding zv, ta có thể thêm các layer đơn giản như 1 mạng fully connected layer với số node là số class, lấy hàm loss là cross entropy

- Với bài toán unsupervised learning, mặc dù không có label nhưng có thể xài node embedding cho các downstream task. Từ đó hàm loss được định nghĩa:

u, v là 2 node kề trong random walk, Q là tập các cặp negative sample ( 2 node không kề), delta là sigmoid function. Việc tính loss dựa vào các node kề ngẫu nhiên giúp model tổng quát hơn. Là sự khác biệt lớn nhất với các model dạng DeepWalk hay Node2Vec

Ví dụ ứng dụng:

- PinSage (Recommender Systems): Pinterest Engineer

- UberEat ( user-based recommender engine): tuy nhiên có 2 bipartite graph (user-dish và user-restaurant) -> các node thay vì 2 thực thể pin-board thì thành user-dish-restaurant nên có initial embeding với số chiều khác nhau -> Thêm 1 mạng MLP ứng từng node để quy về 1 node embedding với số chiều cố định. Vì 1 user có thể đặt 1 món nhiều lần hoặc thường xuyên từ 1 nhà ahngf nên loss function cũng sửa đổi để re-ranking

- Decagon (Heterogeneous Drug Side-Effect): ví dụ bài toán về chuẩn đoán tác dụng phụ khi sử dụng nhiều loại thuốc cùng lúc -> nhiều loại nút: xanh là tên thuốc, cam là thnahf phần cấu tạo kèm node embedding ứng từng thành phần, các cạnh là drug-gên, gên-gene và các side-efect giữa các loại

- GCPN (Goal-directed generation) là graph generation (sinh các node/edge mới). Ví dụ hình thành cấu trúc phân tử dựa trên 1 số mục tiêu và điều kiện/quy tắc cho trước -> Áp dụng Reinforcement Learning cho Graph Neural Network

Hạn chế và lưu ý
- Non-injective neighbor aggregation and injective neighbor aggregation: Nhiều trường hợp, các aggre func như mean, max làm mất tính riêng biệt của các cấu trúc khác nhau (non-injective aggre function) -> Graph Isomorphism Network 2019 để có injective aggre function

- Adversarial Attack: Việc tấn công/giả mạo các node hoặc edge để sai lệch kết quả (credit card fraud detection, social recommendation, product recommendation, ....) . Thường gặp là modify edge, node injection, modify feature

Implement

Cho Simple Node classification GNN
https://viblo.asia/p/simple-node-classification-gnn-RnB5pbdJZPG
phần implement cho GCN cũng có ở dưới trong link

GNN in CV

Video có thể biểu diễn dưới dạng spatio- temporal graph, với mỗi node là 1 tập interest point (image) và edge là liên hệ của chúng.

Representing Vision as Graph

Visual node Representation

Có 3 cách để biểu diễn node trong image X (R[hxwxc]) hoặc video X (R[fxhxwxc]) (h: height, w: width, c: số channel, f: số frame)

- Cách 1: chia thành các grid cell (p,p), mỗi grid là 1 vertex (node) rồi appy neural netword để embedding

- Cách 2: một vài pre-processed có thể trực tiếp sử dụng để biểu diễn node. Object detection như Fast RCNN, YOLO,... thì huyển về cùng dimensional features và feed cho next step. Graph generation thì bản thân đã là 1 graph với vertex và edges đầy đủ. Skeleton cũng là 1 graph

- Cách 3: một vài task sử dụng thông tin ngữ nghĩa làm node. Ta có thể coi đó như những pixels hoặc group pixels. Dùng convolution để trích xuất feature, dùng như point cloud (tập 3D point). Mục đích là xây dựng cấu hình topological

Visual edge Representation
Phụ thuộc vào node, thường với 2D image thì dạng spatial relations ( quan hệ không gian). Hay với clip và video thì có thêm temporal relation (quan hệ thứ tự/thời gian). Có thể train bằng GNNs, trở thành learning to learn relations (thông qua dynamic relation) càng ngày càng được chú ý

Spatial Edge: để sử dụng spatial relations, thường dùng fully connected graph (completed graph) để biểu diễn node và khoanh vùng (union region) chúng để biểu diễn edge feature. Đồng thời, self-attention là 1 lựa chọn tốt, được ý tưởng từ transformer trong NLP. KHi các cạnh đã được biểu diễn, ta có thể chọn spatial-base hoặc spectral-based GNNs

Temporal Edge: hay dùng KNN để xây dựng temporal relation giữa các frame. Đặc biệt là cách dùng Markov chain và Random walk bởi dynamic adjustment với node là image patch và edge là affinities (feature space) giữa node và các frame liền kề. Hoặc dùng IoU (Intersection of Union) làm weight adges

Case Study 1: Image

Object Detection: chia làm 2 loại là generic object detection và salient object detection. Loại thứ 1 tập trung vào những object phổ biến và pre-defined. Loại thứ 2 tập trung vào những thứ riêng biệt. Deep learning-based method hiện đang chiếm thế chủ đạo (Faster RCNN và Yolo), ý tưởng thường là khoanh vùng và predict xác xuất của từng class. Mặc dù thành công nhưng chúng xử lí từng object một cách riêng biệt, nên giảm hiệu suất với trường hợp không điển hình/không lí tưởng (ví dụ như heavy long-tail data distributions hay plenty of confusing). GNN xử lí vấn đề này bằng cách tận dụng correlations giữa các region để hiệu suất tốt hơn -> SGRN 2019 (Spatial Aware Graph Relation Network)

https://openaccess.thecvf.com/content_CVPR_2019/papers/Xu_Spatial-Aware_Graph_Relation_Network_for_Large-Scale_Object_Detection_CVPR_2019_paper.pdf

SGRN có thể chia làm 2 modules: sparse graph học graph structure khi training và spatial-aware graph embedding tận dụng cấu trúc thông tin graph đã học và biểu diễn graph. Cụ thể hơn:

Hầu hết GNN method hiện tại tệ với fully-connected graph -> KNN để làm graph sparse

Image Classification:
Mặc dù có những thành công như ResNet. CNN-based models có những hạn chế nhất định, đặc biệt là về relations. Trong task này, GNN tập trung vào fine-grained region correlations để cải tiến classification performance, tổng hợp labeled và unlabeled image thành semi-supervised image classification

Case Study 2: Video

Video Action Recognition: mục đích là phát hiện hành động xuất hiện trong video và phân loại nó. Ở quá khứ, chúng ta hay sử dụng spatio-temporal model làm core (ví dụ như Hand-crafted Improved Dense Trajectory, two-Stream ConvNets, C3D và I3D). Trong trường hợp longer-term temporal information, có tích hợp thêm RNNs vào frame squence. Dù vậy, conventional deep learning chỉ tập trung vào extracting feature chứ không phải relationship.

Ví dụ: ta muốn recognize "mở sách", thì temporal dynamic có liên quan đến human-object và object-object, ta cần temporally link khu vực sách qua thời gian, xác định góc cạnh và xác định sự thay đổi của chúng
-> Spatial-temporal graph neural network: lấy dense object làm node và học relations giữa chúng.

Temporal Action Localization: predict vùng và loại hành động trong untrimmed videos.Hầu hết method hiện tại là two-stage pipeline: sinh 1 tập 1D temoral proposal sau đó classification và temporal coundry regression với mỗi cá nhân proposal. Cho proposal-proposal relations, P-GCN 2019 dùng GCN: đầu tiên là xây 1 action proposal graph, nơi mỗi proposal là node, sau đó liên kêt với GCN để cải thiện biểu diễn. Cuối cùng, cập nhật node dựa vào boundaries và classificion score based trong established proposal-proposal dependencies.

Other Related Case: Cross-media

Visual Caption: tự động sinh biểu diên từ ngữ cho image hoặc video. Phương hướng là image2text (CNN hoặc Region-based CNN (RCNN) để encode 1 image và decoder dựa vào (RNN) bới attention dùng để generate sentence

Graph Convolutional Network + Long Short-Term Memory (GCN-LSTM) cũng được sinh ra để giải quyết vấn đề này (mô hình hóa tương tác object/region để làm phong phú thêm biểu diễn region-level rồi feed cho sentence decoder). Đặt biệt là có 2 loại relationship (semantic và spatial correlation)

Visual Question Answering VQA: xây dựng 1 hệ thống tự động trả lời ngôn ngữ về thông tin visual (trực quan). Thử thách ở chỗ cần sự hiểu biết lẫn nhau về lí luận trên các phương thức khác nhau. Gần đay nhất là dựa vào sự kết hợp của latent subspace chung, encoder-decoder framework và attention

-> knowledge graph và Relation-aware Graph Attention Network (ReGAT) để model multi-type object relations với question adaptive attention mechanism. Faster RCNN được dùng để sinh 1 tập object region proposal, và 1 question encoder dùng để question embedding. Convolutional và bouding-box feature của mỗi region sau đó được cho vào relation encoder để học relation-aware, question-adaptive và biểu diễn region-level. Sau đó relation-aware visual features và question embedding được đưa vào multimodal fusion module để có 1 joint representation mà dùng cho answer prediction module để tạo 1 câu trả lời

Cross-Media Retrieval: (image-text retrieval task): keypoint là relationship giữa objects trong multi-modal data

Network trên lấy cả irregular graph structure textual và regular vector structured visual làm thành 1 jointly learn couple feature và common latent sematic space (không gian latent ngữ nghĩa chung). Ngoài ra, ta có Scene Graph Matching (SGM) model, khi 2 graph encoder riêng encode visual scene graph và text scene graph vào feature graph. Sau đó cả object-level và relationship-level được học tại mỗi graph, 2 feature graph ứng 2 bên dữ liệu cuối cùng có thể match nhau tại 2 cấp độ hợp lí hơn

Frontiers for GNN on Computer Vision
(biên giới)
Advanced GNN for Computer Vision:

Ý tưởng chính của GNN trong CV là biểu diễn trực quan thông tin dưới dạng graph (pixels, object bounding boxes, image frames như node và xây 1 homogeneous graph để model relations). Ngoài ra còn 1 vài ý tưởng mới

- Person Feature Patches 2020: xây spatial temporal graph cho person re-identification (Re-ID). Horizontally partition (phân vùng ngang hàng) mỗi person feature map thành patches (bản vá) và dùng patches như node. GCN dùng relation giữa các body part qua frames

- Irregular Clustering Region 2020: bipartite GNN cho mammogram mass detection. KNN forward nối các phần image feature map đến irregular regions. Sau đó features trong irregular region được làm node. Bipartite node sets được xây dựng bởi cross-view images, khi mỗi edge học các ràng buộc hình học và sự tương đồng

- NAS Cells 2020: graph-guilded Neural Architecture Search (NAS) algorithm. Biểu diễn mỗi operation cells là 1 node và dùng GCN để tìm relationship giữa các cells

Broader Area of GNN on CV:
- Point Cloud Analysis: recognize tập point trong hệ thống tọa độ. Mỗi point là 1 tọa độ + 1 vài features. Dùng CNN để chuyển point cloud thành regular grid như image và voxel. Sau đó 1 chuỗi hành động biểu diễn iregular graph. GCN dùng cùng mục đích với CNN trong image processing cho aggregating local information. Có 1 hierachical graph network structure cho 3D object detection trong poit cloud. Với learnable GCN kernel và 3D graph max pooling nhận KNN nodes. -> Coverage-Aware Grid Query va Grid Context Aggregation tăng tốc 3D scene segmentation. Point-GNN được thiết kế với cơ chế tự động phát hiện nhiều đối tượng trong 1 lần chụp

- Low Resource Learning: học từ tập data rất nhỏ. Knowledge graph cung cấp thêm thông tin cho zero-short image classification (ZLE). Mỗi node ứng 1 class và lấu word embedding của node làm input cho predict classifier của các class khác nhau. Sự tương đồng giữa các images trong dataset sẽ rất có ích (xây dựng metric trương đồng và model như 1 label propagating hay edge-labeling problem)

- Face Recogntion: dùng face clustering task như 1 link prediction problem. Dùng GCN để học likelihood của các cặp subgraph