Digital Library[ Search Result ]
An Efficient Algorithm for Diversified Top-k Subgraph Querying
http://doi.org/10.5626/JOK.2024.51.2.103
Subgraph matching is a core and important problem in graph analysis. The subgraph matching problem is to find all embeddings of the query graph in the data graph. However, the output results from previously proposed algorithms often overlap with each other, and thus interesting results are often missed. For this purpose, the diversified top-k subgraph querying problem is proposed. The diversified top-k subgraph querying problem is to find k embeddings that have the highest coverage among embeddings of the query graph in the data graph. In this paper, we present an algorithm for the diversified top-k subgraph querying problem and demonstrate that it finds diversified top-k results efficiently compared to existing algorithms.
Deep k-Means Node Clustering Based on Graph Neural Networks
http://doi.org/10.5626/JOK.2023.50.12.1153
Recently, graph node clustering techniques using graph neural networks (GNNs) have been actively studied. Notably, most of these studies use a GNN to embed each node into a low-dimensional vector and then cluster the embedding vectors using the existing clustering algorithms. However, since this approach does not consider the final goal of clustering when training the GNN, it is difficult to say that it produces optimal clustering results. Therefore, in this paper, we propose a deep k-means clustering method that iteratively trains a GNN considering the final goal of k-means clustering and performs k-means clustering on the embedding vectors generated by the trained GNN. The proposed method considers both the similarity between nodes and the loss of k-means clustering when training a GNN. Experimental results using real datasets confirmed that the proposed method improves the quality of k-means clustering results compared to the existing methods.
Online Opinion Fraud Detection Using Graph Neural Network
Woochang Hyun, Insoo Lee, Bongwon Suh
http://doi.org/10.5626/JOK.2023.50.11.985
This study proposed a graph neural network model to detect opinion frauds that undermine the of information and hinder users" decision-making on online platforms. The proposed method uses methods on a graph of relationships between online reviews to produce relational representations, are then combined with the characteristics of the center nodes to predict fraud. Experimental results on a real-world dataset demonstrate that this approach is more accurate and faster than existing state-of-art methods, while also providing interpretability for key relations. With the help of this study, practitioners will be able to utilize the analytical results in decision-making and overcome the general drawback of neural network-based models" lack of explainability.
C3DSG: A 3D Scene Graph Generation Model Using Point Clouds of Indoor Environment
http://doi.org/10.5626/JOK.2023.50.9.758
To design an effective deep neural network model to generate 3D scene graphs from point clouds, the following three challenging issues need to be resolved: 1) to decide how to extract effective geometric features from point clouds, 2) to determine what non-geometric features are used complementarily for recognizing 3D spatial relationships between two objects, and 3) to decide which spatial reasoning mechanism is used. To address these challenging issues, we proposed a novel deep neural network model for generating 3D scene graphs from point clouds of indoor environments. The proposed model uses both geometric features of 3D point cloud extracted using Point Transformer and various non-geometric features such as linguistic features and relative comparison features that can help predict the 3D spatial relationship between objects. In addition, the proposed model uses a new NE-GAT graph neural network module that can apply attention to both object nodes and edges connecting them to effectively derive spatial context between objects. Conducting a variety of experiments using 3DSSG benchmark dataset, effectiveness and superiority of the proposed mode were proven.
Learning Functional Characteristics of Malware Attacks with Graph Transformer based on Control Flow
http://doi.org/10.5626/JOK.2023.50.8.633
To minimize false negatives in malware classification, it is important to capture local characteristics of a program, such as the control flow between operation blocks and memory-register addresses. However, existing methods that optimize the loss function of a classifier without considering the functional characteristics of malware have limitations in recall due to new attack paths and complex control flow graphs. In this paper, we propose a method that explicitly samples and embeds the control flow graphs to learn functional characteristics, such as API calls, rootkit DLL installation, and specific virtual memory access, and improve recall. To model the functional patterns of malware from the control flow graphs, we sample attack paths from the control flow of the malware and classify the types of malware using a graph embedding function based on the transformer. We evaluate the proposed method using a real-world malware benchmark dataset, Microsoft Challenge. By explicitly learning the control flow of the malware, we achieved a recall of 97.89% and significantly improved the accuracy (99.45%) compared to the latest and most advanced method"s classification accuracy (97.89%).
Performance Improvement of Distributed Parallel Graph Data Processing in InfiniBand Networks
Hyeongjong Kim, Myeong-Seon Gil, Yang-Sae Moon
http://doi.org/10.5626/JOK.2023.50.4.359
Graph data, which values the relationship of each object, is widely used for new rules or association analysis that cannot be found in relational databases. However, there is a limit to high-speed processing due to its complex structure and massive data size. In this paper, we propose PIGraph (Pregel and InfiniBand-based Graph processing engine) to improve the processing performance of graph data. PIGraph is an advanced graph processing engine based on Pregel, which is a representative graph processing model. PIGraph supports the distributed parallel structure using InfiniBand and RDMA (Remote Direct Memory Access) technology to reduce the management complexity of distributed graph processing. In particular, PIGraph improves the processing performance of graph data by optimizing the RDMA communication with segment-based transmissions. Experimental results show that PIGraph improves the processing time by up to 190% compared to Apache Giraph.
Integrating Domain Knowledge with Graph Convolution based on a Semantic Network for Elderly Depression Prediction
Seok-Jun Bu, Kyoung-Won Park, Sung-Bae Cho
http://doi.org/10.5626/JOK.2023.50.3.243
Depression in the elderly is a global problem that causes 300 million patients and 800,000 suicides every year, so it is critical to detect early daily activity patterns closely related to mobility. Although a graph-convolution neural network based on sensing logs has been promising, it is required to represent high-level behaviors extracted from complex sensing information sequences. In this paper, a semantic network that structuralizes the daily activity patterns of the elderly was constructed using additional domain knowledge, and a graph convolution model was proposed for complementary uses of low-level sensing log graphs. Cross-validation with 800 hours of data from 69 senior citizens provided by DNX, Inc. revealed improved prediction performance for the suggested strategy compared to the most recent deep learning model. In particular, the inference of a semantic network was justified by a graph convolution model by showing a performance improvement of 28.86% compared with the conventional model.
A Study of Metric and Framework Improving Fairness-utility Trade-off in Link Prediction
Heeyoon Yang, YongHoon Kang, Gahyung Kim, Jiyoung Lim, SuHyun Yoon, Ho Seung Kim, Jee-Hyong Lee
http://doi.org/10.5626/JOK.2023.50.2.179
The advance in artificial intelligence (AI) technology has shown remarkable improvements over the last decade. However, sometimes, AI makes biased predictions based on real-world big data that intrinsically contain discriminative social factors. This problem often arises in friend recommendations in Social Network Services (SNS). In the case of social network datasets, Graph Neural Network (GNN) is utilized for training these datasets, but it has a high tendency to connect similar nodes (Homophily effect). Furthermore, it is more likely to make a biased prediction based on socially sensitive attributes, such as, gender or religion, making it ethically more problematic. To overcome these problems, various fairness-aware AI models and fairness metrics have been proposed. However, most of the studies used different metrics to evaluate fairness and did not consider the trade-off relationship that existed between accuracy and fairness. Thus, we propose a novel fairness metric called Fairβ-metri which takes both accuracy and prediction into consideration, and a framework called FairU that shows outstanding performance in the proposed metric.
Graph Neural Networks with Prototype Nodes for Few-shot Image Classification
http://doi.org/10.5626/JOK.2023.50.2.127
The remarkable performance of deep learning models is based on a large amount of training data. However, there are a number of domains where it is difficult to obtain such a large amount of data, and in these domains a large amount of resources must be invested for data collection and refining. To overcome these limitations, research on few-shot learning, which enables learning with only a small number of data, is being actively conducted. In particular, among meta learning methodologies, metric-based learning which utilizes similarity between data has the advantage that it does not require fine-tuning of the model for a new task, and recent studies using graph neural networks have shown good results. A few-shot classification model based on a graph neural network can explicitly process data characteristics and the relationship between data by constructing a task graph using data of a given support set and query set as nodes. The EGNN(Edge-labeling Graph Neural Net) model expresses the similarity between data in the form of edge labels and models the intra-class and inter-class similarity more clearly. In this paper, we propose a method of applying a prototype node representing each class to few-shot task graph to model the similarity between data and class-data at the same time. The proposed model provides a generalized prototype node that is created based on task data and class configuration, and it can perform two different few-shot image classification predictions based on the prototype-query edge label or the Euclidean distance between prototype-query nodes. Comparing the 5-way 5-shot classification performance on the mini-ImageNet dataset with the EGNN model and other meta-learning-based few-shot classification models, the proposed model showed significant performance improvement.
Effective Importance-Based Entity Grouping Method in Continual Graph Embedding
http://doi.org/10.5626/JOK.2025.52.7.627
This study proposed a novel approach to improving entity importance evaluation in continual graph embeddings by incorporating edge betweenness centrality as a weighting factor in a Weighted PageRank algorithm. By normalizing and integrating betweenness centrality, the proposed method effectively propagated entity importance while accounting for the significance of information flow through edges. Experimental results demonstrated significant performance improvements in MRR and Hit@N metrics across various datasets using the proposed method compared to existing methods. Notably, the proposed method showed enhanced learning performance after the initial snapshot in scenarios where new entities and relationships were continuously added. These findings highlight the effectiveness of leveraging edge centrality in promoting efficient and accurate learning in continual knowledge graph embeddings.
Search
Journal of KIISE
- ISSN : 2383-630X(Print)
- ISSN : 2383-6296(Electronic)
- KCI Accredited Journal
Editorial Office
- Tel. +82-2-588-9240
- Fax. +82-2-521-1352
- E-mail. chwoo@kiise.or.kr