On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs
One of the important tasks in a graph is to compute the <i>similarity</i> between two nodes; link-based similarity measures (in short, similarity measures) are well-known and conventional techniques for this task that exploit the relations between nodes (i.e., links) in the graph. Graph...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-12-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/11/1/162 |
| _version_ | 1797543469359562752 |
|---|---|
| author | Masoud Reyhani Hamedani Sang-Wook Kim |
| author_facet | Masoud Reyhani Hamedani Sang-Wook Kim |
| author_sort | Masoud Reyhani Hamedani |
| collection | DOAJ |
| description | One of the important tasks in a graph is to compute the <i>similarity</i> between two nodes; link-based similarity measures (in short, similarity measures) are well-known and conventional techniques for this task that exploit the relations between nodes (i.e., links) in the graph. Graph embedding methods (in short, embedding methods) convert nodes in a graph into vectors in a low-dimensional space by <i>preserving</i> social relations among nodes in the original graph. Instead of applying a similarity measure to the graph to compute the similarity between nodes <i>a</i> and <i>b</i>, we can consider the <i>proximity</i> between corresponding vectors of <i>a</i> and <i>b</i> obtained by an embedding method as the similarity between <i>a</i> and <i>b</i>. Although embedding methods have been analyzed in a wide range of machine learning tasks such as link prediction and node classification, they are <i>not</i> investigated in terms of similarity computation of nodes. In this paper, we investigate <i>both</i> effectiveness and efficiency of embedding methods in the task of similarity computation of nodes by comparing them with those of similarity measures. To the best of our knowledge, this is the first work that examines the application of embedding methods in this special task. Based on the results of our <i>extensive</i> experiments with five well-known and publicly available datasets, we found the following observations for embedding methods: (1) with all datasets, they show <i>less</i> effectiveness than similarity measures except for one dataset, (2) they <i>underperform</i> similarity measures with all datasets in terms of efficiency except for one dataset, (3) they have more parameters than similarity measures, thereby leading to a <i>time-consuming</i> parameter tuning process, (4) increasing the number of dimensions does <i>not</i> necessarily improve their effectiveness in computing the similarity of nodes. |
| first_indexed | 2024-03-10T13:46:00Z |
| format | Article |
| id | doaj.art-eb22039b3cd8437a9ceb6d4c6ba9f0d4 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T13:46:00Z |
| publishDate | 2020-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-eb22039b3cd8437a9ceb6d4c6ba9f0d42023-11-21T02:40:13ZengMDPI AGApplied Sciences2076-34172020-12-0111116210.3390/app11010162On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in GraphsMasoud Reyhani Hamedani0Sang-Wook Kim1Department of Computer and Software, Hanyang University, Seoul 04763, KoreaDepartment of Computer and Software, Hanyang University, Seoul 04763, KoreaOne of the important tasks in a graph is to compute the <i>similarity</i> between two nodes; link-based similarity measures (in short, similarity measures) are well-known and conventional techniques for this task that exploit the relations between nodes (i.e., links) in the graph. Graph embedding methods (in short, embedding methods) convert nodes in a graph into vectors in a low-dimensional space by <i>preserving</i> social relations among nodes in the original graph. Instead of applying a similarity measure to the graph to compute the similarity between nodes <i>a</i> and <i>b</i>, we can consider the <i>proximity</i> between corresponding vectors of <i>a</i> and <i>b</i> obtained by an embedding method as the similarity between <i>a</i> and <i>b</i>. Although embedding methods have been analyzed in a wide range of machine learning tasks such as link prediction and node classification, they are <i>not</i> investigated in terms of similarity computation of nodes. In this paper, we investigate <i>both</i> effectiveness and efficiency of embedding methods in the task of similarity computation of nodes by comparing them with those of similarity measures. To the best of our knowledge, this is the first work that examines the application of embedding methods in this special task. Based on the results of our <i>extensive</i> experiments with five well-known and publicly available datasets, we found the following observations for embedding methods: (1) with all datasets, they show <i>less</i> effectiveness than similarity measures except for one dataset, (2) they <i>underperform</i> similarity measures with all datasets in terms of efficiency except for one dataset, (3) they have more parameters than similarity measures, thereby leading to a <i>time-consuming</i> parameter tuning process, (4) increasing the number of dimensions does <i>not</i> necessarily improve their effectiveness in computing the similarity of nodes.https://www.mdpi.com/2076-3417/11/1/162graph embeddingfeature representation learninglink-based similarity measuresnode–pairs similarity |
| spellingShingle | Masoud Reyhani Hamedani Sang-Wook Kim On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs Applied Sciences graph embedding feature representation learning link-based similarity measures node–pairs similarity |
| title | On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs |
| title_full | On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs |
| title_fullStr | On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs |
| title_full_unstemmed | On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs |
| title_short | On Investigating Both Effectiveness and Efficiency of Embedding Methods in Task of Similarity Computation of Nodes in Graphs |
| title_sort | on investigating both effectiveness and efficiency of embedding methods in task of similarity computation of nodes in graphs |
| topic | graph embedding feature representation learning link-based similarity measures node–pairs similarity |
| url | https://www.mdpi.com/2076-3417/11/1/162 |
| work_keys_str_mv | AT masoudreyhanihamedani oninvestigatingbotheffectivenessandefficiencyofembeddingmethodsintaskofsimilaritycomputationofnodesingraphs AT sangwookkim oninvestigatingbotheffectivenessandefficiencyofembeddingmethodsintaskofsimilaritycomputationofnodesingraphs |