Skip to main content

Data Mining Lab. Blog

Search This Blog

Pages

Posts

Signed random walk diffusion for effective representation learning in signed graphs

Posted by Data Mining Lab. 날짜: 5/02/2022

DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors

Posted by Data Mining Lab. 날짜: 4/01/2022

Model-Agnostic Augmentation for Accurate Graph Classification

Posted by Data Mining Lab. 날짜: 3/06/2022

Multi-EPL: Accurate Multi-Source Domain Adaptation

Posted by Data Mining Lab. 날짜: 2/02/2022

Compressing Deep Graph Convolution Network with Multi-staged Knowledge Distillation

Posted by Data Mining Lab. 날짜: 1/02/2022

Unsupervised Multi-Source Domain Adaptation with No Observable Source Data

Posted by Data Mining Lab. 날짜: 12/12/2021

Transfer Alignment Network for Blind Unsupervised Domain Adaptation

Posted by Data Mining Lab. 날짜: 11/03/2021

Accurate Graph-Based PU Learning without Class Prior

Posted by Data Mining Lab. 날짜: 10/26/2021

Fast and Accurate Partial Fourier Transform for Time Series Data

Posted by Data Mining Lab. 날짜: 9/01/2021

Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion

Posted by Data Mining Lab. 날짜: 8/02/2021

Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries

Posted by Data Mining Lab. 날짜: 7/01/2021

Data Mining Lab.

Go to DMLAB Website

본 블로그에서는 서울대학교
컴퓨터공학부 데이터마이닝

연구실에서 진행하고 있는

최신 연구를 소개합니다.

Archive

2022 5

2021 12
2020 12
2019 1
- December 2019 1

Show more Show less

Popular Posts

D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors

본 문서에서는 ICDE 2020에서 발표된 " D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Jun-Gi Jang et al., D-Tucker: Fast and Memory-Efficient Tucker Decomposition for Dense Tensors , ICDE 2020 Tucker Decomposition 동영상 (가로, 세로, 시간), 기상 데이터 (오염물질, 위치, 시간) 등과 같이 다양한 데이터들이 밀도 높은 텐서 (Dense tensor)로 표현됩니다. 터커 분해 (Tucker Decomposition) 은 텐서 데이터를 분석하는 가장 유명한 모델 중 하나이며 차원 축소, 클러스터링, 추천 시스템 등과 같이 다양한 응용들에서 활용하고 있습니다. 그림 1. 3차원 텐서에 대한 터커 분해 예시 터커 분해는 그림 1의 예시와 같이 주어진 텐서를 각 차원의 저계수 요인행렬 (low-rank factor matrix)과 관계간의 강도를 표현하는 코어 텐서 (core tensor)로 분해합니다. 터커 분해는 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와 입력 텐서간의 차이를 줄이는 방향으로 요인 행렬들과 코어 텐서를 학습합니다. ALS (Alternating Least Square) 는 터커 분해의 요인 행렬들과 코어 텐서를 학습할 때 사용하는 접근법 중 하나입니다. 해당 방법은 임의의 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하며, 요인 행렬들을 순서대로 업데이트합니다. 그림 1의 예에서는 행렬 B와 C를 고정시키고 A를 업데이트합니다. 그 다음, A와 C를 고정시키고 B를 업데이트하며, C도 마찬가지로 A와 B를 고정시켜 업데이트합니다. 요인 행렬들과 코어 텐서로 복원한 재복원 텐서와

DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors

본 문서에서는 ICDE 2022에서 발표될 " DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors Authors: Jun-Gi Jang and U Kang Conference: 38th IEEE International Conference on Data Engineering (ICDE), 2022 PARAFAC2 Decomposition 센서 데이터 (시간, 위치, 센서타입), 주식 데이터 (시간, 피쳐, 종목) 등과 같이 다양한 데이터들이 밀도 높은 불규칙 텐서 (irregular dense tensor)로 표현됩니다. 불규칙 텐서는 행의 크기가 서로 다른 행렬들의 모음으로도 볼 수 있습니다. PARAFAC2 Decomposition 은 불규칙 텐서 데이터를 분석하는 가장 유명한 방법 중 하나이며 차원 축소, 고장 탐지, 표현형 발견(phenotype discovery) 등과 같이 다양한 응용들에서 활용되고 있습니다. 그림 1. PARAFAC2 Decomposition PARAFAC2 Decomposition 은 그림 1의 예시와 같이 주어진 불규칙 텐서를 요인행렬(factor matrix)들로 분해합니다. ALS (Alternating Least Square) 는 PARAFAC2 Decomposition의 요인행렬들을 구할 때 사용하는 접근법 중 하나입니다. 해당 방법은 요인 행렬 하나를 제외한 나머지 모두를 고정시키고, 고정되지 않은 하나의 요인 행렬을 업데이트하는 방식으로 요인 행렬들을 순서대로 업데이트합니다. 요인 행렬들은 재복원한 텐서와 입력 텐서 간의 차이가 충분히 작아질 때까지 업데이트가 됩니다. Limitations

Attention-Based Autoregression for Accurate and Efficient Multivariate Time Series Forecasting

본 문서에서는 데이터 마이닝 분야의 SDM 2021 학회에서 발표될 예정인 Attention-Based Autoregression for Accurate and Efficient Multivariate Time Series Forecasting 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Attention-Based Autoregression for Accurate and Efficient Multivariate Time Series Forecasting Authors: Jaemin Yoo and U Kang Conference: SIAM International Conference on Data Mining (SDM) 2021 Multivariate Time Series Forecasting 시계열 예측(time series forecasting)은 기계 학습 및 데이터 마이닝 분야에서 활발히 연구되고 있는 문제로서, 많은 수의 실세계 데이터가 시계열 형태로 모델링되기 때문에 주가 예측, 날씨 예측, 전력 수요 예측 등 다양한 실세계 문제와 밀접히 연관되어 있습니다. 그중에서도 다변수(multivariate) 시계열 예측은 서로 연관되어 있는 여러 개의 시계열 변수를 동시에 예측하는 상황을 의미합니다. 위에서 언급한 시계열 예측 문제의 예시는 모두 다변수 예측에 해당됩니다. 즉, 예측 대상이 되는 주식 종목간 관계, 지역간 관계, 그리고 도시 구획별 관계를 모델링함으로써 시계열 예측 정확도를 크게 향상시킬 수 있습니다. 하지만, 각 변수에서 관측되는 패턴과 여러 변수간 관계를 동시에 고려하다 보니 다변수 시계열 예측을 위한 기존 모델은 지나치게 많은 파라미터를 갖는 경향을 보였습니다. 학습 데이터의 양이 충분하지 않고 과거 시점의 데이터에 과적합(overfitting)되기 쉬운 시계열 데이터의 특성상 파라미터 수가 많아질 경우 성능 재현과 하이퍼파라미터 튜닝(hyperparameter tuning)이 무척 어려워집니다.

Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries

본 문서에서는 데이터 마이닝 분야 학회 중 하나인 KDD 2021에서 발표될 " Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries " 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title: Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries Authors: Jun-Gi Jang and U Kang Conference: The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( KDD ), 2021 Temporal Dense Tensor 실세계에 존재하는 많은 데이터가 시간 밀도 텐서 (temporal dense tensor)로 표현될 수 있습니다. 시간 밀도 텐서는 한 차원이 시간과 관련이 있으며, 대부분의 값들이 관측된 데이터입니다. 예를 들어, 여러 위치에 설치된 센서들에서 매 시간마다 측정값들을 얻을 수 있습니다. 해당 데이터는 3차원 시간 밀도 텐서로 표현할 수 있습니다. 이 외에도, 주식 데이터, 비디오 데이터, 교통량 데이터 등도 시간 밀도 텐서로 표현할 수 있습니다. 그림 1. 시간 밀도 텐서 예시. 센서 데이터, 주식 데이터, 비디오 데이터, 교통량 데이터 등 다양한 실세계 데이터가 시간 밀도 텐서로 표현할 수 있다. 이렇듯 실세계에 존재하는 많은 데이터가 시간 밀도 텐서로 표현될 수 있으며 여러 차원을 가지는 텐서 특성상 데이터의 크기는 매우 큽니다. 그러므로, 시간 밀도 텐서를 효율적이고 효과적으로 분석하는 방법을 개발하는 것은 매우 중요합니다. Tucker Decomposition 터커 분해 (Tucker decomposition) 는 주어진 텐서를 분석할 수 있는 가장 핵심적인 도구 중 하나입니

Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion

본 문서에서는 데이터 마이닝 분야 학회인 KDD 2021에서 발표 예정인 논문 " Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion "을 소개합니다. 논문의 상세한 정보는 아래와 같습니다. Title : Learning to Walk across Time for Interpretable Temporal Knowledge Graph Completion Authors : Jaehun Jung, Jinhong Jung and U Kang Conference : The 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ( KDD ), 2021 Temporal Knowledge Graph Completion 통상적인 지식 그래프(knowledge graph)는 현실 세계의 다양한 개체들을 정점(node)로, 개체들 사이의 관계를 간선(edge)로 표현하는 그래프를 일컫습니다. 이들 지식 그래프는 요컨대 (Joe Biden, is_president_of, United States) 등과 같이 다양한 개체들에 대한 관계적 지식을 트리플(triple)로 표현할 수 있어 추천 시스템, 지식 기반 AI 등 여러 분야에서 활용됩니다. 다만, 기존의 지식 그래프는 개체들 사이의 관계를 실제 시간적인 유효성과 관계없이 영속적인 것으로 간주하기 때문에 현실의 지식을 온전히 표현하기 어렵다는 한계가 있습니다. 이러한 단점을 보완해 근래 새로 등장한 지식 저장 형태가 시간 지식 그래프(temporal knowledge graph)입니다. 시간 지식 그래프는 개체들 간의 관계에 더해 그 관계가

Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks

본 문서에서는 데이터 마이닝 분야의 ICDM 2017 학회에서 발표된 Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks 논문을 소개합니다. 논문의 상세한 정보는 다음과 같습니다. Title: Supervised Belief Propagation: Scalable Supervised Inference on Attributed Networks Authors: Jaemin Yoo, Saehan Jo, and U Kang Conference: IEEE International Conference on Data Mining (ICDM) 2017 Node Classification 정점 분류(node classification)는 그래프 내의 각 정점(node)을 분류하는 문제입니다. 예를 들어 넷플릭스 같은 스트리밍 서비스에서 그림 1과 같이 사용자들이 컨텐츠를 소비한 내역을 그래프로 모델링한 다음 영화나 드라마를 분류하는 작업 등을 생각해볼 수 있습니다. 최근에 그래프 신경망에 대한 연구가 활발히 이루어지면서 함께 주목을 받고 있는 문제이기도 한데, 데이터간 관계가 그래프 형태로 주어져 있는 경우 정점 분류를 통해 학습 데이터가 부족한 반지도 학습(semi-supervised learning) 상황을 해결할 수 있기 때문입니다. 그림 1. 스트리밍 서비스에서 사용자와 컨텐츠간 관계를 나타내는 그래프. 만약 그래프의 각 정점이 고유한 피처 벡터를 가지고 있다면 그래프는 피처간 관계를 나타내는 보조적인 정보로서 사용됩니다. 이런 경우에는 각 정점의 피처 벡터와 그래프 구조를 동시에 고려하여 그 관계를 학습하는 것이 중요합니다. 반면, 본 논문에서는 피처 벡터가 주어지지 않고 그래프 구조 및 간선 정보가 정점 분류를 위한 유일한 정보라고 가정합니다. 따라서, 정점 피처를 인위적으로 생성해야 하는 그래프 신경망 모델을 바로 적용하기 어렵고, 그래프 구조를 최대한 활용하여

Time-Aware Tensor Decomposition for Missing Entry Prediction

본 문에서는 Arxiv에 기재된 Time-Aware Tensor Decomposition for Missing Entry Prediction 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: Time-Aware Tensor Decomposition for Missing Entry Prediction Authors: Dawon Ahn, Jun-Gi Jang, U Kang Arixv: https://arxiv.org/pdf/2012.08855.pdf CANDECOMP/PARAFAC (CP) Decomposition 그림 1. 3차원 시간 텐서의 CP 분해 다차원 배열을 의미하는 텐서는 시간에 따라 변화하는 다중적인 관계를 표현할 수 있습니다. 예를 들어, 센서에서 수집된 대기 오염 데이터는 오염 물질의 측정 값을 포함하는 3차원 시간 텐서(장소, 오염 물질, 시간)로 표현됩니다. 텐서 분해(Tensor Decomposition)는 텐서 데이터를 효과적으로 분석하는 방법으로, 클러스터링 및 이상 탐지를 포함한 다양한 응용 프로그램에서 광범위하게 활용되고 있습니다. CANDECOMP / PARAFAC (CP) 분해는 가장 대표적인 텐서 분해 모델 중 하나로, 그림 1과 같이 텐서를 각 차원의 벡터들의 외적의 합으로 나타낼 수 있습니다. 위와 같은 시간 텐서에는 대표적인 특성 2가지를 관측할 수 있습니다. 첫번째는 텐서의 시간 차원은 인접한 값들끼리는 서로 연관성이 있는 특징이 있습니다. 예를 들어, t번째 시간에서 관측된 오염 데이터는 t-1, t+1번째 시간에서 관측된 오염 데이터와 비슷한 값을 갖을 것입니다. 두번째로는 데이터를 수집하는 센서 및 기계 오류 및 고장으로 인해 텐서는 많은 결측치로 포함하고, 이는 시간 조각(Time Slice) 별로 다른 희소성(혹은 밀도)을 갖게 합니다. 그러나 표준적인 CP 분해 방법을 포함한 기존 분해 방법들은 위 두 가지 특성 모두 고려하지 않았습니다. 본 논문의 목표는 결측치 예측을 위

Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference

본 문서에서는 WSDM 2020에서 발표된 Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference 논문을 소개합니다. 논문에 대한 상세 정보는 다음과 같습니다. Title: Sampling Subgraphs with Guaranteed Treewidth for Accurate and Efficient Graphical Inference Authors: Jaemin Yoo, U Kang, Mauro Scanagatta, Giorgio Corani, and Marco Zaffalon ACM International Conference on Web Search and Data Mining (WSDM) 2020 Graph Sampling 그래프 샘플링(graph sampling)은 어떤 그래프가 주어졌을 때 해당 그래프의 특성을 보존하는 작은 서브그래프(subgraph)를 생성하는 문제입니다. 본 연구에서는 그래프 샘플링 중에서도 정점 집합을 유지하면서 간선 집합의 일부만을 선택하는 간선 샘플링(edge sampling) 문제를 다룹니다. 예를 들어 사용자간 관계를 설명하는 소셜 네트워크가 주어져 있다고 할 때, 간선 샘플링은 각 사용자의 정보는 유지한 채 사용자간 관계 정보만을 제거하여 서브그래프를 생성합니다. 간선 샘플링이 잘 이루어지면 그림 1 과 같은 결과를 생성하게 됩니다. 그림에 나타난 그래프는 여러 개의 블로그와 블로그간 하이퍼링크를 나타내는 웹 그래프로, 각 정점의 색은 블로그의 정치 성향을 나타냅니다. 이때, 그림 왼쪽의 그래프는 동일한 성향의 블로그끼리 간선을 생성하는 동종 친화성(homophily) 특성을 보이는데, 이 특성이 그림 오른쪽의 서브그래프에서도 잘 보존되는 것을 확인할 수 있습니다. 이렇게 생성된 서브그래프는 실제 그래프의 특성을 보다 효율적으로 파악하기 위해 사용될 수 있습니다. 그림 1.

FALCON: Lightweight and Accurate Convolution

본 문서에서는 FALCON: Lightweight and Accurate Convolution 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title: FALCON: Lightweight and Accurate Convolution Authors: Jun-Gi Jang, Chun Quan, Hyun dong Lee, U Kang Arxiv: https://arxiv.org/pdf/1909.11321.pdf 모델 압축 (Model Compression) 딥러닝 기술은 컴퓨터 비전, 자연어 처리, 고장 예측, 추천 시스템 등 다양한 응용들에서 활용되고 있습니다. 특히, 최근 딥러닝 모델은 GPU나 TPU와 같이 강력한 컴퓨팅 자원을 활용할 수 있어 모델의 크기 및 계산량을 증가시켜 높은 성능을 내고 있습니다. 하지만, 컴퓨팅 자원이 제한되어 있는 세팅에서는 기존의 큰 모델들을 그대로 사용할 수가 없습니다. 그래서 스마트폰이나 자율주행차에서 딥러닝 모델을 사용하기 위해서는 기존의 딥러닝 모델들을 경량화하는 모델 압축 방법은 필수입니다. 모델 압축 작업의 목표는 1) 파라미터 수를 줄이고, 2) 계산량을 줄이고, 3) 기존 모델과 압축 모델간의 성능 (e.g., 정확도) 차이를 최소화하는 것입니다. 최근 스마트폰 혹은 자율주행차에서 이미지 분류, 객체 탐지, 이미지 생성 등 다양한 응용들이 CNNs (Convolutional Neural Networks)을 활용합니다. 제한된 컴퓨팅 자원에서 CNN 모델을 잘 활용하기 위해서는 기본 모듈이 되는 기존 합성곱 (standard convolution)을 효율적으로 만들 필요가 있습니다. 효율적인 기존 합성곱을 위해 가지치기 (pruning), 양자화 (quantization), 저차원 근사 (low-rank approximation)와 같은 다양한 기법들이 활용되고 있습니다. 또한, 기존 합성곱을 대신하여 깊이별 분리 합성곱 (depthwise separable convolution)을

BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks

본 문서에서는 EDBT 2020에서 발표될 " BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks " 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다. Title : BalanSiNG: Fast and Scalable Generation of Realistic Signed Networks Authors : Jinhong Jung , Ha-Myung Park , and U Kang Conference : International Conference on Extending Database Technology (EDBT) 2020 Signed Network and Network Generation 부호화된 네트워크 (signed network)란 정점 간의 신뢰 관계를 + (양, 신뢰) 또는 - (음, 불신뢰)의 부호가 붙은 간선으로 표현하는 네트워크를 말하며, Epinions와 같은 온라인 소셜 서비스는 각 사용자에게 다른 사용자에 대한 신뢰를 표현할 수 있게 하여 자연스럽게 부호화된 네트워크를 형성합니다 ( 참고 ). 이와 같이 부호화된 네트워크는 정점 간의 신뢰 관계를 기반으로 링크 예측, 정점 랭킹, 정점 분류, 이상현상 탐지 등의 다양한 그래프 응용에 활용되고 있습니다. 그림 1. 부호화된 네트워크의 예시. 그러나 부호화된 네트워크는 광범위하게 활용되고 있음에 비해, 어떻게 해야 실제 부호화된 네트워크와 비슷한 성향을 가지며 새로운 형태의 다른 부호화된 네트워크를 생성할 수 있는지에 대한 연구는 많이 진행되지 않았습니다. 네트워크 생성 (network generation) 문제는 실세계 그래프 형성의 이해에 대한 중요한 문제로, 네트워크 생성 문제는 다음과 같은 방안으로 많이 활용되고 있습니다. 확장성 테스트 (scalability evaluation) : 확장성 테스트는 개발한 알고리즘이 얼마나 큰 데이터를 처