(23S) [CS471] Graph Machine Learning and Mining

구명규·2023년 3월 21일

Lecture Outline

Lecture Notes

목록 보기

2/5

Chapter 1. Basic Concepts

Graph의 구성 요소 및 종류에 대한 용어: Node/Edge, Directed/Undirected, Induced Subgraph, Ego-Network, (Maximal) Clique, (Strongly) Connected Component, (Local) Bridge
Graph에 대한 측정 요소: Degree(undirected)/In-Degree/Out-Degree/Total Degree/Average Degree, Clustering Coefficient, Span
Graph를 나타내는 방법: Adjacency Matrix, Edge List, Adjacency List

Chapter 2. Centrality Measures

복잡한 graph 상에서 하나의 node 혹은 edge의 중요도를 정의하고, 계산하는 것이 중요. 그 대상에 따라 1) Node-Centrality와 2) Edge-Centrality measures로 나뉨.

Node-Centrality

Degree, Betweenness, Closeness Centrality
: 각각 연결된 node의 수, 임의의 두 node 간 최소 경로에 놓이는 횟수, 모든 node와의 평균 거리에 해당.
Hubs & Authorities
: Authority score $a$ 와 hub score $h$ 를 번갈아가며 계산, normalize 해가며 수렴값 도출 $\rarr$ HITS algorithm
: $A=U\Sigma V^T$ , $U=[u_1 u_2 ... u_m]$ , $V^T=[v_1v_2...v_n]^T$ 로 SVD된 경우, $h^{(k)}=(AA^T)^kh^{(0)}$ 는 $u_1$ 의 방향으로, $a^{(k)}=(A^TA)^{(k-1)}A^Th^{(0)}$ 는 $v_1$ 의 방향으로 수렴.
PageRank
: 매 iteration마다 각 node의 PageRank 값을 연결된 node에 균일하게 분배. 'Sink'로 인해 PageRank 값이 발산하는 경우를 대비해 $(1-\alpha)$ 의 확률로 임의의 node로 이동 $\rarr$ Random Walk $x^{(k+1)}=P^Tx^{(k)} \text{ } \rarr \text{ } P^Tx=x \text{ }\text{ }\text{ } (P_{ij}=\frac{1}{|F_i|}, (i, j)\in E)$ $x_v^{(k+1)}=\alpha\sum_{w\in S_v}\frac{x_w^{(k)}}{|T_w|}+\frac{(1-\alpha)}{n} \text{ } \rarr \text{ } x=\alpha P^Tx+\frac{(1-\alpha)}{n}e$ : Worklist 활용해 효율적으로 연산(Data-driven PageRank).
$\rarr$ Nonnegative residual $r_v^{(k)}=x_v^{(k+1)}-x_v^{(k)}$ 가 계속 감소함을 통해 convergence 증명.
*Power method: Matrix의 거듭제곱 형태로 새로운 벡터 값을 얻어내는 방법

Chapter 3. Closeness Measures

임의의 두 node 간, 혹은 특정 node 집합과 나머지 node 간의 연관성을 제시하는 여러 closeness measures.

Neighborhood Overlap (Edge-centrality measure로도 고려 가능)
Personalized PageRank (PPR)
: $(1-\alpha)$ 의 확률에 대해 predefined set으로 jump $\rarr$ Predefined nodes와의 closeness에 대한 measure $x=\alpha P^Tx+\frac{(1-\alpha)}{n_q}e_q$
Katz Measure
$P_{\text{ Katz}}=\sum_{i=1}^\infin\beta^iA^i$
: Adjacency matrix의 $n$ -거듭제곱이 특정 두 node 간 길이 $n$ 의 경로의 수를 의미한다는 것에 착안, attenuation factor $\beta$ 를 활용해 정의. Link prediction에 활용.
- Low-Rank Approximation
  : Adjacency matrix의 거듭제곱의 많은 연산량을 특정 개수의 eigenvalue에 대해서만 Eigenvalue decomposition을 수행함으로써 완화.

A=VDV^T \text{ } \rarr \text{ } A^k=VD^kV^T \cdots \text{ Eigenvalue decomposition}

(\text{cf. } A=U\Sigma V^T \text{ } \rarr \text{ } (AA^T)^k=U(\Sigma\Sigma^T)^kU^T) \cdots \text{ Singular value decomposition}

Chapter 4. Graph Clustering

내부적으로 많은 연결을 포함하고 있는 cluster로의 graph clustering 기법.

Community = Cluster = Module
Girvan-Newman Algorithm ( $\larr$ edge betweenness)
: Edge betweenness가 높은 between-clusters edge를 찾아 삭제.
Modularity $Q=\frac{1}{2m}\sum_{i, j}[A_{ij}-\frac{k_ik_j}{2m}]\delta(c_i, c_j)$ : Cluster quality 정량화, clustering의 stopping criteria 역할 수행. 'Random configuration model보다 within-cluster edge의 개수가 얼마나 많은가?'
Louvain Method ( $\larr$ modularity)
: 모두 서로 다른 community로 초기화한 후 greedy하게 modularity를 높여나가는 알고리즘.

Graph clustering에 앞서 살펴보는 Data clustering의 기본 개념.

K-Means Clustering $\min\sum_{c=1}^K\sum_{x_i\in\Pi_c}||x_i-m_c||^2, \text{ }\text{ }m_c=\frac{\sum_{x_i\in\Pi_c}x_i}{|\Pi_c|}$ : 각 node와 cluster center간의 거리를 최소화하는 방식으로 업데이트 $\rarr$ Hyperplane으로 dataset을 나눈다는 단점.
Weighted Kernel K-Means Algorithm $\min\sum_{c=1}^K\sum_{x_i\in\Pi_c}w_i||x_i-m_c||^2, \text{ }\text{ }m_c=\frac{\sum_{x_i\in\Pi_c}w_ix_i}{\sum_{x_i\in\Pi_c}w_i}$ : Linear boundary를 사용할 수 있게 해주는 kernel function $\phi(x)$ 자체는 구하기 어려우므로, inner product form의 kernel matrix $K=\phi(x)^T\phi(x)$ 를 대신 사용하는 kernel trick. 각 node의 importance에 따라 서로 다른 weight 부여. $\text{Maximize } \sum_{c=1}^k\frac{u_c^TWKWu_c}{u_c^TWu_c}, \text{ }\text{ }K(x_i, x_j)=\phi(x_i)^T\phi(x_j) : \text{Kernel matrix}$
Weighted Kernel NEO-K-Means Algorithm
: Non-Exhaustive(outlier 존재), Overlapping( $\harr$ Disjoint). Parameter $\alpha, \beta$ 로 overlap과 non-exhaustiveness 조절. 기존의 objective function에 $\alpha, \beta$ 에 대한 constraints 추가, 알고리즘에 additional assignment 할당하는 step 추가.

이제 Graph clustering.

Graph Cut
: Cluster간 size balance를 조절하며 between-cluster edge(=cut)를 최소화하는 것이 핵심. 고정된 크기의 cluster간 node swap만으로 greedy하게 cut을 줄이는 Kernighan-Lin heuristic(too strict).
Ratio Cut / Normalized Cut
: Cluster간 size balance를 각각 cluster의 크기와 degree 값으로 조절.
$RC(G)=\min\sum_{c=1}^k\frac{\text{Cut}(V_c, V\V_c)}{|V_c|}=\min\sum_{c=1}^k\frac{y_c^TLy_c}{y_c^Ty_c}, L=D-A$ $NC(G)=\min\sum_{c=1}^k\frac{\text{Cut}(V_c, V\V_c)}{deg(V_c)}=\min{(k-\sum_{c=1}^k\frac{y_c^TAy_c}{y_c^TDy_c})}$ $\therefore\text{ } NC(G)=\max\sum_{c=1}^k\frac{y_c^TAy_c}{y_c^TDy_c}$
*Overlapping clustering에 대해서도 between-cluster edge가 두 번씩 포함되던 기존 방식이기에 일반화 가능(마찬가지로 constraint $\alpha, \beta$ 만 추가).
$\Rarr$ Weighted Kernel NEO-K-Means와 Normalized Cut for NEO Graph Clustering의 objective function은 수학적으로 동치. 동일한 heuristic 활용 가능!
Multilevel Graph Clustering: Super node로 다수의 node를 합치는 coarsening $\rarr$ 임의의 efficient heuristic으로 base clustering $\rarr$ Base cluster로부터 각 scale에 weighted kernel NEO-K-means를 반복적으로 적용하여 refinement.
둘 이상의 node를 연결하는 hyperedge 개념이 추가된 hypergraph. Incidence matrix $A$ , Hyperedge degree $\text{deg}(e_j)$ , Degree diagonal matrix $D_v, D_e$ , Weight diagonal matrix $F$ .
: Adjacency matrix $A$ 대신 nodes x nodes similarity matrix $\hat{A}=AFD_e^{-1}A^T$ 를 대입하면 마찬가지로 data clustering heuristic 사용 가능!
Evaluation: Graph clustering의 성능을 정량적으로 측정하는 여러 metric - Confusion matrix(precision, recall, F1-measure, macro F1), NMI(normalized mutual information)

Chapter 5. Graph Embedding: A Classical Approach

임의의 graph를 low dimensional space로 변환하는 graph embedding $\rarr$ 높은 similarity를 갖는 node일수록 비슷한 feature vector를 갖도록 하는 방법은?

Random walk 기반의 고전적인 node embedding 방법.

DeepWalk: Graph에서의 random walk sequence가 자연어와 같이 Power-Law를 따르는 유사점을 이용해 NLP의 Skip-Gram 모델 활용 (Random walk sequence에서 co-occur하는 node들은 서로 비슷하다고 가정). Skip-Gram의 Word2Vec의 아이디어를 그래프에 적용한 Node2Vec (DeepWalk에서 random walk의 방법을 확장). $\max_f\sum_{u\in V}\log P(N_R(u)|z_u)=\min_f\sum_{u\in V}\sum_{v\in N_R(u)}-\log(P(v|z_u))$ $, P(v|z_u)=\frac{\exp(z_u^Tz_v)}{\sum_{w\in V}exp(z_u^Tz_w)}$ : $P(v|z_u)$ 의 normalizing term을 $k$ 개의 random negative samples(degree 값에 비례하게 sampling)에 대해서만 계산, $\exp$ 함수를 $\text{sigmoid}$ 로 변경.
Node2Vec: BFS(homophily)와 DFS(structural equivalence)를 동시에 고려하는 2nd order random walk로 $N_R(u)$ sampling (DeepWalk의 일반화, $N_R(u)$ 를 정의하는 방법만 서로 다름).
: Random walk의 transition probability에 return parameter $p$ , walk-away parameter $q$ 로 구성된 search bias 부여.

Chapter 6. Graph Embedding: A Deep Learning Approach

단순히 $n$ 개의 node를 $d$ -dimension의 vector로 embedding하여 $n\times d$ matrix로 나타내는 shallow encoder는 node간 상관관계에 대한 정보가 담기지 않고 unseen node에 대한 inference가 불가능.

GCN 기본 개념.

인접 node로 뻗어나가는 computation graph 구성 후 neural network로 정보 aggregate. $\rarr$ GCN(Graph Convolutional Network)
$\Rarr$ 매 layer마다 neighborhood aggregation과 self transformation 진행. $h_v^{(l+1)}=\sigma(W_l\sum_{u\in N(v)}\frac{h_u^{(l)}}{|N(v)|}+B_lh_v^{(l)})$ $H^{(l+1)}=\sigma(\tilde{A}H^{(l)}W_l^T+H^{(l)}B_l^T), \text{ }\tilde{A}=D^{-1}A$
비슷한 node의 embedding 값이 유사하도록 학습시키는 unsupervised 학습과 주어진 class로 분류되도록 학습시키는 supervised 학습으로 구분.
각 layer에 대한 parameter는 임의의 node에 대해 general하게 적용될 수 있으며, unseen node나 unseen graph에도 적용 가능(Inductive capability).

Aggregator의 종류에 따른 여러 모델. (결국 incoming node feature를 어떻게 message로 변환하고, 이들을 어떻게 aggregate할 것인지에 대한 방식의 차이)

GraphSAGE - Mean aggregator(본래 node의 feature를 concat한다는 점에서 GCN과 차별됨)뿐만 아니라, LSTM(random permutation), max-pooling(elementwise) aggregator 등으로 특정 weight 부여 가능.
$h_v^{(l+1)}=\sigma(W_l[\text{AGG}(\{h_u^{(l)}, \forall u\in N(v)\}), h_v^{(l)}])$
PinSage - Pin과 board 간 bipartite graph로 구성된 Pinterest에서 query item(pin)에 대한 related-pin recommendation.
1) Max-Margin-Based Loss Function - Positive example에 대한 inner-product 값이 negative example에 대한 값보다 특정 margin $\Delta$ 이상 차이나도록 유도
$L(z_q, z_i)=E_{n_k\sim P_n(q)}\max(0, z_q\cdot z_{n_k}-z_q\cdot z_i+\Delta)$
2) Importance Pooling - Source node로부터 PPR을 진행해 상위 $T$ nodes로 computation graph 구성. PPR score로 weight 부여.
3) Curriculum Learning - 학습 과정에서 hard negative samples(query item에 대해 PPR score 순위가 2000-5000 정도에 드는 items)을 점차 추가.
Graph Attention Network (GAT) - 각 node pair에 대한 weighting factor $\alpha_{vu}$ 를 implicit하게 학습.
$h_v^{(l)}=\sigma(\sum_{u\in N(v)}\alpha_{vu}W_lh_u^{(l-1)})$ $e_{vu}=\sigma(a^T(W_lh_u^{(l-1)}, W_lh_v^{(l-1)})), \text{ }\alpha_{vu}=\frac{\exp(e_{vu})}{\sum_{k\in N(v)}\exp(e_{vk})}$
: $K$ 개의 independent attention mechanism을 두어 Multi-head attention 구현.
$h_v^{(l)}[i]=\sum_{u\in N(v)}\alpha_{vu}^iW_lh_u^{(l-1)} \rarr h_v^{(l)}=\text{AGG}(h_v^{(l)}[1], \cdots, h_v^{(l)}[k])$
Query node에 따라 attention coefficient의 ranking을 다르게 하는 Dynamic attention( $\harr$ Static attention). Weight vector $a$ 와 nonlinearity layer의 순서 및 concatenation의 위치를 바꾸어 구현.
$e_{vu}=a^T\sigma(\hat{W}[h_u, h_v]) \text{ }\text{ } \text{ (cf.}e_{vu}=\sigma(a^T[Wh_u, Wh_v])\text{)}$

GNN에도 적용 가능한 DNN Techniques + Over-Smoothing Problem의 해결.

Activation function, Batch normalization, Dropout, Skip connection
GNN의 layer가 깊어질수록 그래프 상 대부분의 node를 aggregate(receptive field의 겹침)하여 모든 embedding vector의 값이 비슷해지는 Over-Smoothing Problem.
: Layer를 얇게 하되 하나의 layer를 multi-layer MLP로 구성하거나 GNN 앞뒤에 pre/post-processing MLP를 추가해 expressive power 개선.
: 그럼에도 깊은 layer가 필요한 경우 skip connection 활용 가능.

Node의 feature 구성하기.

별도의 attributes 없이 adjacency matrix만 존재하다면 constant features 혹은 one-hot vectors로 설정 가능.

	Constant Features	One-Hot Vectors
Expressive Power	Medium	High
Inductive Learning	High	Low
Computational Cost	Low	High
Usage	Any graph, inductive settings	Small graph, transductive settings

Node가 구성하고 있는 cycle의 cycle length(computational graph로는 학습 불가능) 등 centrality measure로 feature augmentation 가능.

Sparse graph는 virtual nodes or edges를 적절히 추가하여 학습의 효율을 높이고, Dense graph는 neighbor sampling을 통해 computation cost를 낮춤.

지금까지 node embedding을 수행했다면, 해당 정보를 기반으로 prediction task를 수행: Node/Edge/Graph-Level prediction.

$\text{Node-Level: }\text{ }\hat{y}_v=W^{(H)}h_v^{(L)}$

\text{Edge-Level: }\text{ }\hat{y}_{uv}=W_{k\times2d}[h_u^{(L)}, h_v^{(L)}] \text{ or } \hat{y}_{uv}=[(h_u^{(L)})^TW_{d\times d}^{(1)}h_v^{(L)}, ...\text{ }, (h_u^{(L)})^TW_{d\times d}^{(k)}h_v^{(L)}]

$\text{Graph-Level: }\text{ }\hat{y}_G=\text{AGG}(\{h_v^{(L)}\in R^d, \forall v\in V\})$

Node-Level: Node embedding vector를 k-way prediction vector로 mapping.
Edge-Level: Edge를 구성하는 두 node embedding vector을 concat하거나 inner product한 뒤 k-way prediction vector로 mapping.
Graph-Level: 모든 node embeddings를 pooling하여 k-way prediction 수행. Mean/max/sum pooling 등을 적용해볼 수 있으며, hierarchical pooling(clustering assignment GNN을 별도로 두어 동시에 학습)을 통해 정보의 손실량 최소화.
Supervised(ex. node category, fraudulent edge detection, druglikeness) vs. Unsupervised
Classification(cross entropy) vs. Regression(L2 loss)

Chapter 7. Graph Anomaly Detection

Anomaly와 non-anomaly 간의 GNN-based classification task.
ex) Fake news/reviews, malware, financial frauds 탐색

고전적으로는 unusual pattern을 찾는 방법을 사용했으나 anomaly가 majority의 feature를 camouflage하는 경우 사용하기 어려움.
$\rarr$ VAE와 GNN을 접목한 Variational Graph Auto-Encoder(VGAE)를 통해 graph reconstruction 진행, 이 때 재생성되지 않는 anomaly 검출.

Graph convolutional encoder + (structure reconstruction decoder + attribute reconstruction decoder)의 구성.
DOMINANT: Latent feature 간 similarity가 threshold를 넘기면 edge를 형성하는 structure reconstruction decoder의 error 성분과 다시 high-dimensional attribute로 복원하는 attribute reconstruction decoder의 error 성분을 모두 고려.

Chapter 8. Knowledge Graph Embedding

Knowledge graph: Entity, Relation, Triplet(head entity, relation, tail entity)으로 구성. (기존 graph의 edge에 feature가 추가된 형태)

Knowledge graph에 대한 고전적인 embedding 방법.

Entity들을 latent space 상의 vector로 표현, relation을 두 vector의 차로 근사하는 Translational Distance Models (Distance-based scoring functions) $\rarr$ Minimize DISTANCE!
1) TransE : 단일 space에서 $h+r\approx t$ 를 만족하도록 embedding. 1-to-N, N-to-1, N-to-N relation에 대한 한계점 존재.
2) TransH : 단일 space에서 Hyperplane of relation $r$ 에 entity를 projection하여 $h_\perp+r\approx t_\perp$ 를 만족하도록 embedding. Relation에 따라 반영되는 entity vector 값이 달라짐.
3) TransR : 아예 Relation-specific space를 두어 $M_rh+r\approx M_rt$ ( $M_r$ : projection matrix)를 만족하도록 embedding. Expressive power 개선.
4) RotatE : Complex vector space에서, relation을 rotation vector로 두어 $h\circ r\approx t$ 를 만족하도록 embedding. Symmetric relation 구현.
각 relation을 entity vector를 입력받는 matrix로 정의하여 relation plausibility of facts를 계산하는 Semantic Matching Models (Similarity-based scoring function) $\rarr$ Maximize SIMILARITY!
1) RESCAL : Entity vector의 pairwise interaction을 계산하는 relation matrix. $\rarr f_r(h, t)=h^TM_rt$
2) DistMult : Entity vector의 weighted inner product를 계산하는 relation matrix(symmetric relations에 한정). $\rarr f_r(h, t)=h^T\text{diag}(r)t$
3) HolE : Entity vector를 circular correlation operation으로 계산하는 relation matrix. $\rarr f_r(h, t)=h^T\star t$

Knowledge graph embedding model의 학습을 위해 negative sampling을 수행할 때 just missing true fact가 생성될 수도 있음.
$\rarr$ 1-to-N, N-to-1 relation일 경우 각각 head, tail을 바꾸거나 self-adversarial negative sampling 등을 통해 해결. $\min_\theta\sum_{\tau\in E}\sum_{\tau^-\in E^-}\max(0, \gamma-f_r(h, t)+f_{r'}(h', t'))$ $(\tau': \text{negative examples}, \gamma: \text{margin value})$

Knowledge graph에 대한 GNN 기반 embedding 방법: Relational GCN(RGCN).

h_v^{(l+1)}=\sigma(\sum_{r\in R}\sum_{u\in N_v^r}\frac{1}{c_{v,r}}W_r^{(l)}h_u^{(l)}+W_0^{(l)}h_v^{(l)}), \text{ }c_{v, r}=|N_v^r|

Relation type에 따라 서로 다른 weight matrix 사용. 하지만 relation의 종류에 따라 parameter의 수가 크게 늘어남. $\rarr$ Block-diagonal decomposition, Basis decomposition 등으로 크기 축소 가능.

Knowledge graph embedding 결과를 활용한 tasks.

Link prediction: RGCN을 encoder로, DistMult를 decoder로 활용. 각 edge를 1)Training Message, 2)Training Supervision, 3)Validation, 4)Test edges로 분류하여 self-supervised training 진행(validation/test edges는 학습 과정에서 없는 것으로 간주. 이에, false-negative sample이 생성될 수 있으나 이를 줄이기 위한 technique도 존재).
$l=\max\{h_v^TM_{r_i}h_{v_n}-h_v^TM_{r_i}h_{v_p}+\gamma, 0\}$ $, \text{ }(v, r_i, v_n): \text{Negative edges}, \text{ }(v, r_i, v_p): \text{Training supervision edges}$
: Message edges 기반으로 Supervision edges를 embedding, 해당 triplet의 score function(DistMult)을 최대화. Negative edge에 대한 값은 최소화. (Margin-based ranking loss 적용)

: Negative edges 중에서 validation/test edges의 ranking 계산하여 Mean Rank(MR), Mean Reciprocal Rank(MRR), Hit $@N$ 등으로 evaluate. Multiple answer를 갖는 경우 filtered metric 사용.
Triplet Classification: 새로운 triplet $(h, r, t)$ 에 대해, $f_r(h, t)>\delta_r$ 일 경우 true fact로 예측.
Question Answering: 임의의 question을 structured format으로 변환, missing value prediction.
Recommender Systems: $m$ users의 $n$ items에 대한 preference를 known ratings로부터(collaborating) 예측(filtering)하는 $m\times n$ matrix $R$ . User와 item에 대한 latent factors matrix $U, M$ 의 곱으로 표현 가능(matrix factorization). 각 matrix를 alternating minimization으로 학습.
$R_{m\times n}\approx U_{m\times k}M_{n\times k}^T, \text{ }U, M: \text{latent features for users/items}$ $\min_{u_i's, m_j's}\sum_{(i, j)\in S}(R_{ij}-u_i^Tm_j)^2+\lambda\sum_i||u_i||_2^2+\lambda\sum_j||m_j||_2^2 \\= ||W\odot (R-UM^T)||_F^2+\lambda(||U||_F^2+||M||_F^2)$ $W_{ij}=1 \text{ if }(i, j)\in S\text{ (known ratings)}$
: Collaborative knowledge base embedding을 통해 item의 semantic representation 추출, 복합적인 item latent vector (structural + textual + visual) 형성 가능. Pairwise preference $u_i^Tm_j$ 에 대한 ranking optimization 진행.

Chapter 9. Graph Models in Various Applications

Course Summary 및 Bioinformatics, CV&Graphics, NLP 등에서의 활용 사례.

Chapter 10. Advanced Topics

교수님 논문 두 가지.

[Learning Representations of Bi-Level Knowledge Graphs for Reasoning beyond Link Prediction] - BiVE
- Base-level triplet 간의 relationship을 나타내는 higher-level triplet 개념 추가. $\Rarr$ Bi-Level Knowledge Graph. $\hat{G}=(V, R, E, \hat{R}, H), \text{ }H=\{<T_i, \hat{r}, T_j>:T_i\in E, \hat{r}\in\hat{R}, T_j\in E\} \\(\hat{R}: \text{Set of higher-level relations}, \text{ }H: \text{Set of higher-level triplets})$
- Triplet Prediction: <Triplet, Relationship between triplets, ?> $F_{tp}(X)=f(T_i, \hat{r}, X)$
- Conditional Link Prediction: <Triplet, Relationship between triplets, (Head, Relation, ?)> $F_{clp}(x)=f(h_j, r_j, x)+\lambda_1\cdot f(T_i, \hat{r}, W[h_j;r_j;x])$
- Bi-Level knowledge graph에서 Random walk를 수행하여 새로운 triplet augmentation 적용.
  : Random walk를 통해 얻어낸 relation sequence $p_k=(r_0, r_i, \hat{r}, r_j)$ 에 대해, 임의의 relation $r$ 에 대한 confidence score $c(p_k, r)$ 계산
- Base-level triplet, higher-level triplet, augmented triplet 각각에 대해 loss 정의. ( $E_{\text{train}}', H_{\text{train}}', S'$ : set of corrupted triplets) $L_{\text{base}}=\sum_{(h, r, t)\in E_{\text{train}}}g(-f(h, r, t))+\sum_{(h', r', t')\in E_{\text{train}}'}g(f(h',r',t'))$ $L_{\text{high}}=\sum_{(T_i, \hat{r}, T_j)\in H_{\text{train}}}g(-f(T_i, \hat{r}, T_j))+\sum_{(T_i', \hat{r}', T_j')\in H_{\text{train}}'}g(f(T_i', \hat{r}', T_j'))$ $L_{\text{aug}}=\sum_{(h, r, t)\in S}g(-f(h, r, t))+\sum_{(h', r', t')\in S'}g(f(h', r', t'))$ $g(x)=\log(1+\exp(x)), \text{ }\text{ }f(\cdot): \text{scoring function}$
- $<T_i, \hat{r}, ?>$ 를 완성하는 triplet prediction과 $<T_i, \hat{r}, (h_j, r_j, ?)>$ 를 완성하는 conditional link prediction 수행
[Semantic Grasping Via a Knowledge Graph of Robotic Manipulation: A Graph Representation Learning Approach] - roboKG
- 특정 물체와 목적에 대해, 로봇이 적합한 gripper를 택해 적절한 방식으로 물체를 쥐도록 하는 task.
- Object를 파악하는 Recognition Module + 이를 바탕으로 1) GripperType, 2) ComponentClass, 3) GraspingForce에 대한 link prediction을 진행하는 Knowledge Graph Embedding + Robotic Manipulation