A Graph Embedding Technique for Weighted Graphs Based on LSTM Autoencoders

( Minji Seo ),( Ki Yong Lee ) 한국정보처리학회 2020 Journal of information processing systems Vol.16 No.6

A graph is a data structure consisting of nodes and edges between these nodes. Graph embedding is to generate a low dimensional vector for a given graph that best represents the characteristics of the graph. Recently, there have been studies on graph embedding, especially using deep learning techniques. However, until now, most deep learning-based graph embedding techniques have focused on unweighted graphs. Therefore, in this paper, we propose a graph embedding technique for weighted graphs based on long short-term memory (LSTM) autoencoders. Given weighted graphs, we traverse each graph to extract node-weight sequences from the graph. Each node-weight sequence represents a path in the graph consisting of nodes and the weights between these nodes. We then train an LSTM autoencoder on the extracted node-weight sequences and encode each nodeweight sequence into a fixed-length vector using the trained LSTM autoencoder. Finally, for each graph, we collect the encoding vectors obtained from the graph and combine them to generate the final embedding vector for the graph. These embedding vectors can be used to classify weighted graphs or to search for similar weighted graphs. The experiments on synthetic and real datasets show that the proposed method is effective in measuring the similarity between weighted graphs.

스타 그래프와 팬케익, 버블정렬 그래프 사이의 임베딩 알고리즘

김종석 ( Jong Seok Kim ),이형옥 ( Hyeong Ok Lee ),김성원 ( Sung Won Kim ) 한국컴퓨터교육학회 2010 컴퓨터교육학회 논문지 Vol.13 No.5

스타 그래프는 노드 대칭성, 최대 고장 허용도, 계층적 분할 성질을 갖고, 하이퍼큐브보다 망 비용이 개선된 널리 알려진 상호 연결망이다. 본 연구에서는 스타 그래프와 그의 변형된 그래프들 상호 간의 임베딩 방법을 제안한다. 버블정렬 그래프가 팬케익 그래프와 스타 그래프에 각각 연장율 3, 확장율 1로 임베딩 가능함을 보이고, 팬케익 그래프가 버블정렬그래프에 임베딩 하는 연장율 비용이 O(n2)임을 보인다. 그리고 스타 그래프가 팬케익 그래프에 연장율 4, 확장율 1로 임베딩 가능함을 보인다. 또한 스타그래프를 버블정렬 그래프에, 팬케익 그래프를 스타 그래프에 임베딩 하는 연장율 비용이 각각 O(n)임을 보인다. Star graph is a well-known interconnection network to further improve the network cost of Hypercube and has good properties such as node symmetry, maximal fault tolerance and strongly hierarchical property. In this study, we will suggest embedding scheme among star graph and pancake graph, bubblesort graph, which are variations of star graph. We will show that bubblesort graph can be embedded into pancake and star graph with dilation 3, expansion 1, respectively and pancake graph can be embedded into bubblesort graph with dilation cost O(n2). Additionally, we will show that star graph can be embedded into pancake graph with dilation 4, expansion 1. Also, with dilation cost O(n) we will prove that star graph can be embedded into bubblesort graph and pancake graph can be embedded into star graph.

Embedding Algorithm among Half Pancake, Pancake, and Star Graphs

Jung-hyun Seo,HyeongOk Lee 보안공학연구지원센터 2016 International Journal of Software Engineering and Vol.10 No.3

The star graph is an attractive alternative to hypercube. The pancake graph has n! nodes and generates edge using exchange of a symbol that composes a node address like star graph. The half pancake graph is a new network where the network cost of pancake graph is reduced by half. We suggest embedding algorithm among these networks. The half pancake HPn was embedded on pancake Pn with dilation 1 and congestion 1. The half pancake Pn was embedded on star graph Sn with dilation 1.5n-2, average dilation about 0.25n+4, and congestion 6. The pancake Pn was embedded on star graph Sn with dilation 1.5n. All the three of embedding were one-to-one embedding with expansion 1.

질의문과 지식 그래프 관계 학습을 통한 지식 완성 시스템

김민성,이민호,이완곤,박영택 한국정보과학회 2021 정보과학회논문지 Vol.48 No.6

The knowledge graph is a network comprising of relationships between the entities. In a knowledge graph, there exists a problem of missing or incorrect relationship connection with the specific entities. Numerous studies have proposed learning methods using artificial neural networks based on natural language embedding to solve the problems of the incomplete knowledge graph. Various knowledge graph completion systems are being studied using these methods. In this paper, a system that infers missing knowledge using specific queries and knowledge graphs is proposed. First, a topic is automatically extracted from a query, and topic embedding is obtained from the knowledge graph embedding module. Next, a new triple is inferred by learning the relationship between the topic from the knowledge graph and the query by using Query embedding and knowledge graph embedding. Through this method, the missing knowledge was inferred and the predicate embedding of the knowledge graph related to a specific query was used for good performance. Also, an experiment was conducted using the MetaQA dataset to prove the better performance of the proposed method compared with the existing methods. For the experiment, we used a knowledge graph having movies as a domain. Based on the assumption of the entire knowledge graph and the missing knowledge graph, we experimented on the knowledge graph in which 50% of the triples were randomly omitted. Apparently, better performance than the existing method was obtained. 지식 그래프는 개체들 사이의 관계로 구성된 네트워크를 뜻한다. 이러한 지식 그래프에서 특정 개체들에 대한 관계가 누락되거나 잘못된 관계 연결과 같은 문제로 불완전한 지식 그래프의 문제점이 존재한다. 불완전한 지식 그래프의 문제를 해결하기 위한 많은 연구는 자연어 임베딩 기반으로 인공 신경망을 이용한 학습 방법들을 제안했다. 이러한 방법들로 다양한 지식 그래프 완성 시스템들이 연구되고 있는데 본 논문에서는 특정 질의와 지식 그래프를 활용해 누락된 지식을 추론하는 시스템을 제안하였다. 먼저 의문형의 Query로부터 topic을 자동으로 추출하여 해당 topic 임베딩을 지식 그래프 임베딩 모듈로부터 얻는다. 그 다음 Query 임베딩과 지식 그래프 임베딩을 활용하여 지식 그래프로부터의 topic과 질의문 사이의 관계를 학습하여 새로운 트리플을 추론한다. 이와 같은 방식을 통해 누락된 지식들을 추론하고 좋은 성능을 위해 특정 질의와 관련된 지식 그래프의 술어부 임베딩을 같이 활용하였고 기존 방법보다 더 좋은 성능을 보임을 증명하기 위해 MetaQA 데이터셋을 사용하여 실험을 진행하였다. 지식 그래프는 영화를 도메인으로 갖는 지식 그래프를 사용하였다. 실험 결과로 지식 그래프 전체와 누락된 지식 그래프를 가정하여 트리플들을 임의로 50% 누락시킨 지식 그래프에서 실험하여 기존 방법보다 더 좋은 성능을 얻었다.

A Flexible Translation-Based Knowledge Graph Embedding Adapting Unobserved Entities

A-Yeong Kim,Seong-Bae Park,Sang-Jo Lee 보안공학연구지원센터 2016 International Journal of Software Engineering and Vol.10 No.11

This paper proposes a flexible translation-based knowledge graph embedding that learns unobserved entities by moving positions of embedding vectors from existed embedding space. To reflect unobserved entities, previous methods tend to learn knowledge graphs all over again. This process causes high cost of calculation. Thus, this paper introduces an adjusting method which moves positions of learned embedding vectors according to unobserved entity. This idea is based on TransE model that is a one of translation-based methods. According to experiments, the proposed method shows the plausibility at link prediction task and triple classification task. These experimental results prove that reducing learning cost is a crucial issue for embedding knowledge graphs.

행렬스타 그래프와 하프 팬케익 그래프 사이의 일대일 사상 알고리즘

김종석(Jong-Seok Kim),유남현(Nam-Hyun Yoo),이형옥(Hyeong-Ok Lee) 한국지능시스템학회 2014 한국지능시스템학회논문지 Vol.24 No.4

행렬스타 그래프와 하프팬케익 그래프는 스타 그래프의 변형으로 노드 대칭성과 허용도 등 여러 가지 좋은 성질을 갖는다. 본 연구에서는 행렬스타 그래프와 하프팬케익 그래프 사이의 임베딩을 분석한다. 연구 결과로 행렬스타 그래프 MS2,n는 하프팬케익 그래프 HP2n에 연장율 5, 확장율 1에 임베딩 가능하다. 또한 하프팬케익 그래프 HP2n는 행렬스타 그래프 MS2,n 에 임베딩하는 연장율 비용이 O(n)임을 보인다. 이러한 결과는 스타 그래프에서 개발된 여러 가지 알고리즘을 하프팬케익 그래프에서 상수의 추가적인 비용으로 시뮬레이션 할 수 있음을 의미한다. 왜냐하면 스타 그래프 Sn은 행렬스타 그래프 MS2,n의 부분 그래프이기 때문이다. Matrix-star and Half-Pancake graphs are modified versions of Star graphs, and has some good characteristics such as node symmetry and fault tolerance. This paper analyzes embedding between Matrix-star and Half-Pancake graphs. As a result, Matrix-star graphs MS2,n can be embedded into Half-Pancake graphs HP2n with dilation 5 and expansion 1. Also, Half Pancake Graphs, HP2n can be embedded into Matrix Star Graphs, MS2,n with the expansion cost, O(n). This result shows that algorithms developed from Star Graphs can be applied at Half Pancake Graphs with additional constant cost because Star Graphs, Sn is a part graph of Matrix Star Graphs, MS2,n.

인접성 벡터를 이용한 트리플 지식 그래프의 임베딩 모델 개선

조새롬(Sae-rom Cho),김한준(Han-joon Kim) 한국전자거래학회 2021 한국전자거래학회지 Vol.26 No.3

그래프 표현 학습을 위한 노드 임베딩 기법은 그래프 마이닝에서 양질의 결과를 얻는 데 중요한 역할을 한다. 지금까지 대표적인 노드 임베딩 기법은 동종 그래프를 대상으로 연구 되었기에, 간선 별로 고유한 의미를 갖는 지식 그래프를 학습하는 데 어려움이 있었다. 이러한 문제를 해결하고자, 기존 Triple2Vec 기법은 지식 그래프의 노드 쌍과 간선을 하나의 노드로 갖는 트리플 그래프를 학습하여 임베딩 모델을 구축한다. 하지만 Triple2Vec 임베딩 모델은 트리플 노드 간 관련성을 단순한 척도로 산정하기 때문에 성능을 높이는데 한계를 가진다. 이에 본 논문은 Triple2Vec 임베딩 모델을 개선하기 위한 그래프 합성곱 신경망 기반의 특징 추출 기법을 제안한다. 제안 기법은 트리플 그래프의 인접성 벡터(Neighborliness Vector)를 추출하여 트리플 그래프에 대해 노드 별로 이웃한 노드 간 관계성을 학습한다. 본 논문은 DBLP, DBpedia, IMDB 데이터셋을 활용한 카테고리 분류 실험을 통해, 제안 기법을 적용한 임베딩 모델이 기존 Triple2Vec 모델보다 우수함을 입증한다. The node embedding technique for learning graph representation plays an important role in obtaining good quality results in graph mining. Until now, representative node embedding techniques have been studied for homogeneous graphs, and thus it is difficult to learn knowledge graphs with unique meanings for each edge. To resolve this problem, the conventional Triple2Vec technique builds an embedding model by learning a triple graph having a node pair and an edge of the knowledge graph as one node. However, the Triple2 Vec embedding model has limitations in improving performance because it calculates the relationship between triple nodes as a simple measure. Therefore, this paper proposes a feature extraction technique based on a graph convolutional neural network to improve the Triple2Vec embedding model. The proposed method extracts the neighborliness vector of the triple graph and learns the relationship between neighboring nodes for each node in the triple graph. We proves that the embedding model applying the proposed method is superior to the existing Triple2Vec model through category classification experiments using DBLP, DBpedia, and IMDB datasets.

개체 유형 정보를 활용한 지식 그래프 임베딩

공승환,정찬영,주수헌,황지영 한국정보과학회 2022 정보과학회논문지 Vol.49 No.9

Knowledge graph embedding represents entities and relationships in the feature space by utilizing the structural properties of the graph. Most knowledge graph embedding models rely only on the structural information to generate embeddings. However, some real-world knowledge graphs include additional information such as entity types. In this paper, we propose a knowledge graph embedding model by designing a loss function that reflects not only the structure of a knowledge graph but also the entity-type information. In addition, from the observation that certain type constraints exist on triplets based on their relations, we present a negative sampling technique considering the type constraints. We create the SMC data set, a knowledge graph with entity-type restrictions to evaluate our model. Experimental results show that our model outperforms the other baseline models. 지식 그래프 임베딩은 그래프의 구조적 특성을 반영하여 개체와 관계를 특성 공간에 나타내는 기술이다. 대부분의 지식 그래프 임베딩 모델은 그래프 구조 이외의 정보를 가정하지 않고 특징 벡터를 생성한다. 하지만 실생활과 밀접한 지식 그래프는 개체의 유형 정보 등 추가적인 정보를 얻을 수 있다. 본 논문에서는 개체의 유형이 클러스터의 역할을 수행할 수 있다는 점에 착안하여, 유형 정보를 반영할 수 있는 손실 함수를 통한 지식 그래프 임베딩 모델을 제시한다. 또한, 지식 그래프 내 관계의 주어/술어에 해당하는 유형이 제한적이라는 관찰을 토대로 개체 유형 제한에 특화된 네거티브 샘플링 기법을 제시한다. 본 논문에서 제시한 모델에 대한 링크 예측을 평가하기 위해 개체 유형 제한을 가진 지식 그래프인 SMC 데이터 셋을 생성하여 실험을 진행하였다. 링크 예측 결과는 본 모델이 네 개의 베이스라인 모델과 비교해서 뛰어난 성능을 보이는 것을 확인하였다.

그래프 임베딩과 관련된 이항 트리에서의 Q-에지 번호매김에 관한 연구

김용석,Kim Yong-Seok 대한전자공학회 2005 電子工學會論文誌-CI (Computer and Information) Vol.42 No.1

본 논문에서는 그래프 임베딩 문제와 관련된 이항트리에서의 Q-에지 번호매김 방법을 제안한다. 이러한 연구결과는 신뢰성이 높은 통신망을 설계하는 최적화 문제인 "n 개의 노드와 e 개의 에지를 가지면서 연결도가 최대인 그래프를 구성하라."를 해결한 Harary 그래프의 일반화인 원형군 그래프(circulant graph)의 점프열로 Q-에지번호들을 이용하면 연결도가 최대인 신뢰성이 높은 새로운 상호연결망(interconnection networks)의 위상을 설계할 수 있다. 그리고 이러한 위상은 이항트리를 스패닝 트리로 가지므로 최적방송이 가능하다. In this paper, we propose the Q-edge labeling method related to the graph embedding problem in binomial trees. This result is able to design a new reliable interconnection networks with maximum connectivity using Q-edge labels as jump sequence of circulant graph. The circulant graph is a generalization of Harary graph which is a solution of the optimal problem to design a maximum connectivity graph consists of n vertices End e edgies. And this topology has optimal broadcasting because of having binomial trees as spanning tree.

THE BOUNDARIES OF DIPOLE GRAPHS AND THE COMPLETE BIPARTITE GRAPHS K_2,n

Kim, Dongseok The Honam Mathematical Society 2014 호남수학학술지 Vol.36 No.2

We study the Seifert surfaces of a link by relating the embeddings of graphs with induced graphs. As applications, we prove that every link L is the boundary of an oriented surface which is obtained from a graph embedding of a complete bipartite graph $K_{2,n}$, where all voltage assignments on the edges of $K_{2,n}$ are 0. We also provide an algorithm to construct such a graph diagram of a given link and demonstrate the algorithm by dealing with the links $4^2_1$ and $5_2$.