Finding a Concise, Precise, and Exhaustive Set of Near Bi-Cliques in Dynamic Graphs

Hyeonjeong Shin, Taehyung Kwon, Neil Shah, and Kijung Shin

WSDM 2022: International Conference on Web Search and Data Mining 2022

Abstract: A variety of tasks on dynamic graphs, including anomaly detection, community detection, compression, and graph understanding, have been formulated as problems of identifying constituent (near) bi-cliques (i.e., complete bipartite graphs). Even when we restrict our attention to maximal ones, there can be exponentially many near bi-cliques, and thus finding all of them is practically impossible for large graphs. Then, two questions naturally arise: (Q1) What is a “good” set of near bi-cliques? That is, given a set of near bi-cliques in the input dynamic graph, how should we evaluate its quality? (Q2) Given a large dynamic graph, how can we rapidly identify a high-quality set of near bi-cliques in it? Regarding Q1, we measure how concisely, precisely, and exhaustively a given set of near bi-cliques describes the input dynamic graph. We combine these three perspectives systematically on the Minimum Description Length principle. Regarding Q2, we propose CutNPeel, a fast search algorithm for a high-quality set of near bi-cliques. By adaptively re-partitioning the input graph, CutNPeel reduces the search space and at the same time improves the search quality. Our experiments using six real-world dynamic graphs demonstrate that CutNPeel is (a) High-quality: providing near bi-cliques of up to 51.2% better quality than its state-of-the-art competitors, (b) Fast: up to 68.8x faster than the next-best competitor, and (c) Scalable: scaling to graphs with 134 million edges. We also show successful applications of CutNPeel to graph compression and pattern discovery.

2 1

THyMe+: Temporal Hypergraph Motifs and Fast Algorithms for Exact Counting

Geon Lee and Kijung Shin

ICDM 2021: IEEE International Conference on Data Mining 2021

Abstract: Group interactions arise in our daily lives (email communications, on-demand ride sharing, comment interactions on online communities, to name a few), and they together form hypergraphs that evolve over time. Given such temporal hypergraphs, how can we describe their underlying design principles? If their sizes and time spans are considerably different, how can we compare their structural and temporal characteristics?

In this work, we define 96 temporal hypergraph motifs (TH-motifs), and propose the relative occurrences of their instances as an answer to the above questions. TH-motifs categorize the relational and temporal dynamics among three connected hyperedges that appear within a short time. For scalable analysis, we develop THyMe+, a fast and exact algorithm for counting the instances of TH-motifs in massive hypergraphs, and show that THyMe+ is at most 2,163X faster while requiring less space than baseline. Using it, we investigate 11 real-world temporal hypergraphs from various domains. We demonstrate that TH-motifs provide important information useful for downstream tasks and reveal interesting patterns, including the striking similarity between temporal hypergraphs from the same domain.

 

1

김성민교수 연구팀,대규모 사물인터넷(IoT) 동시 통신 개발로 MobiSys 2022 Best paper award 수상

[왼쪽부터 김성민교수, 배강민 박사과정(1저자)]
 
최근 모바일 시스템 분야의 최고 권위 국제 학술대회인 `ACM 모비시스(ACM MobiSys)’ 2022에 발표한 논문이 최우수논문상을 수상했습니다. 
작년 KAIST 전기및전자공학부에서 아시아 대학 최초로 MobiSys 최우수논문상을 받은 이후 연속된 수상입니다. 
 
연구성과 : 전기및전자공학부 김성민 교수 연구팀, 천 개 ~ 수천만 개 이상의 대규모 사물인터넷(IoT) 동시 통신 기술 최초 개발
 – 밀리미터파 후방산란 시스템 기술로 초저전력 대규모 통신 설계 성공
 – 기존에는 다양한 장애물과 반사체가 설치된 환경에서 제대로 작동하지 않았던 문제점을 해결 
 – 2035년까지 1조 개 이상의 사물인터넷 기기가 생산될 전망에서 높은 실용성 및 확장성으로 초연결 시대를 위한 핵심 역할 기대
 
전기및전자공학부 김성민 교수 연구팀이 세계 최초로 천 개에서 수천만 개에 이르는 대규모 사물인터넷(IoT) 동시 통신을 위한 `밀리미터파 후방산란 시스템’을 개발했다고 28일 밝혔다.
KAIST 전기및전자공학부 배강민 박사과정이 제1 저자로 참여한 이번 연구는 모바일 시스템 분야의 최고 권위 국제 학술대회인 `ACM 모비시스(ACM MobiSys)’ 2022에 이번 6월 발표됐으며, 최우수논문상을 수상했다.
 (논문명: OmniScatter: extreme sensitivity mmWave backscattering using commodity FMCW radar). 
이는 작년 KAIST 전기및전자공학부에서 아시아 대학 최초로 ACM 모비시스 2021 최우수논문상을 받은 이후 연속된 수상으로 더욱 의미가 깊다.
 
연구팀의 후방산란 기술은 10마이크로와트(μW) 이하의 초저전력으로 작동해 코인 전지 하나로 40년 이상 구동 가능해 설치 및 유지보수 비용을 크게 줄일 수 있다.
이번 성과는 5G/6G 등 차세대 통신에서 요구하는 네트워크 밀도를 훨씬 웃도는 연결성을 자랑한다. 이에, 이번 시스템은 향후 도래할 초연결 시대를 위한 디딤돌 역할을 할 수 있을 것으로 기대된다.
김성민 교수는 “밀리미터파 후방산란은 대규모로 사물인터넷 기기들을 구동할 수 있는 꿈의 기술이며 이는 기존 어떠한 기술보다도 더욱 대규모의 통신을 초저전력으로 구동할 수 있다ˮ라며 ” 이 기술이 앞으로 도래할 초연결 시대에 사물인터넷의 보급을 위해 적극적으로 활용되길 기대한다ˮ라고 말했다.

이번 연구는 삼성미래기술육성사업과 정보통신기획평가원의 지원을 받아 수행됐다.

 
mage
[연구성과도 1. 대규모 IoT 통신을 위한 태그(붉은색 삼각형). 1100개 태그 신호가 충돌없이 동시 통신]
 
 
image
[수상 행사 사진]
 
 
관련 언론 기사링크 : 전자신문 등
https://www.etnews.com/20220728000090
http://vip.mk.co.kr/news/view/21/21/3550810.html

심현철교수 연구팀, 현대차 자율주행 챌린지 우승

우리학부 심현철교수 연구팀이 2021년 현대차그룹 자율주행 챌린지에서 우승을 차지하여 많은 언론에 보도되었습니다.
 

 

1

[심현철교수 사진]

심현철교수연구팀(팀명 : KI- ROBOTICS) 자율주행차가 29일 서울 상암동 MBC 광장 일대에서 열린 ‘2021 현대차그룹 자율주행 챌린지’에서 우승을 차지했다. 

이번 대회는 예전과 달리 상암동 실제 도로에서 다른 참가팀 차들과 동시에 주행하는 방식으로 진행되어 실제 도로에서의 자율주행 기술에 더욱 다가섰다는데 큰 의의가 있다.
연구팀은 GPS(위성항법장치) 장치 없이 카메라와 라이다 센서만을 활용한 자율주행차로 1위를 기록해 주목을 받았다.

본대회 예선 23개팀 중 본선 6팀이 선발되었으며, 본선 우승한 심현철교수 연구팀에게는 상금 1억원과 북미 견학의 혜택이 주어진다. 

심현철교수는 17개월간 이대규 전기및전자공학부 박사과정학생을 중심으로 대회를 준비하며, 국내 최초의 전기차기반 자율주행 챌린지에서 우승한 팀원들의 노력이 빛을 발했으며, 대회준비 및 우승경험이 향후 관련 기술 발전에 많은 기여를 할 것이라 전했다. 

 

 

[2021 현대차그룹 자율주행 챌린지에서 우승을 차지한 KAIST’ 연구팀]

관련 링크 :
데일리카 : http://www.dailycar.co.kr/content/news.html?type=view&autoId=41811
한국경제신문 : https://www.hankyung.com/economy/article/202111291999g

황의종 교수 연구팀, 정확하고 공정한 머신러닝 모델을 위한 선택적 데이터 수집 기법 개발

전기및전자공학부 황의종 교수님 연구실 태기현 박사과정생이 정확하고 공정한 머신러닝 모델을 위한 선택적 데이터 수집 기법을 개발했습니다.

머신러닝이 현대 사회에 폭넓게 사용되면서 책임 있는 인공지능의 필요성이 대두되고 있습니다. 높은 정확도를 넘어서 책임 있는 인공지능의 목표에는 공정성(fairness), 강건성(robustness), 설명가능성(explainability) 등이 포함되어 있습니다. 특히, Google, Microsoft, IBM 등의 회사에서 책임있는 인공지능을 강조하고 있습니다.

본 연구에서는 인공지능 공정성에 초점을 맞추고 불공정한 인공지능의 근원이 편향된 훈련 데이터에 있다는 점에 착안하여, 데이터 수집 단계에서부터 인공지능 모델의 정확도와 공정성을 함께 고려한 프레임워크인 Slice Tuner를 제안하였습니다. Slice Tuner는 데이터양에 따라 모델의 손실을 추정할 수 있는 학습 곡선(learning curve)을 효율적이고 신뢰할 수 있도록 관리하고, 이를 활용하여 정확하고 공정한 모델을 위한 최적의 데이터 수집 방법을 제시합니다.

연구팀은 해당 기술이 데이터 수집단계에서 부터 책임 있는 인공지능을 실현하기 위한 중요한 첫 단추가 될 수 있다고 설명했습니다. 또한, 본 연구 성과는 데이터베이스 최고 권위 학회인 ACM SIGMOD (International Conference on Management of Data) 2021 에서 발표되었습니다.

자세한 연구 내용은 하단의 링크에서 확인하실 수 있습니다.

 

3

Figure 1. Slice Tuner architecture

 

 

[논문 정보]

논문명: Slice Tuner: A Selective Data Acquisition Framework for Accurate and Fair Machine Learning Models

저자: 태기현, 황의종(지도교수)

논문 링크: https://arxiv.org/abs/2003.04549

논문 슬라이드: https://docs.google.com/presentation/d/1thnn2rEvTtcCbJc8s3TnHQ2IEDBsZOe66-o-u4Wb3y8/edit?usp=sharing

학회 발표 영상: https://youtu.be/QYEhURcd4u4?list=PL3xUNnH4TdbsfndCMn02BqAAgGB0z7cwq

 

황의종 & 서창호 교수 연구팀, 공정한 머신러닝 모델 학습을 위한 새로운 배치 선택 기법 개발

전기및전자공학부 황의종 교수님과 서창호 교수님 연구팀에서 공정한 머신러닝 모델 학습을 위한 새로운 배치 선택 기법을 개발했습니다. 본 연구는 노유지 박사과정(지도교수 황의종)이 주저자로 참여했고, 위스콘신 매디슨 전기컴퓨터공학부 이강욱 교수님과의 공동 연구로 진행되었습니다.

 

인공지능 기술이 인간에게 단순히 편리성을 가져다주던 단계에서, 이제는 사회 전반에 걸쳐 광범위하게 활용되며 인간의 삶에 많은 영향을 미치고 있습니다. 최근 인공지능의 긍정적인 효과 이면에 머신러닝 모델이 특정 개인 혹은 집단을 차별하는 사례가 다수 발견되었고, 이에 따라 공정성(fairness)을 고려한 머신러닝 학습의 필요성에 대한 사회적인 공감이 커지고 있습니다.

 

본 연구팀은 공정한 머신러닝 모델 학습을 위한 새로운 배치 선택(batch selection) 기법인 FairBatch를 제안합니다. 기존의 공정성을 위한 머신러닝 기법들은 학습 데이터 혹은 알고리즘 자체에 큰 수정이 요구되었는데, 이와는 달리 FairBatch는 데이터를 샘플링하는 배치 선택 단계에서 한 줄의 코드 변경만으로 높은 정확도와 공정성을 효과적으로 달성합니다. 또한 FairBatch는 이중수준 최적화를 통한 해석을 기반으로 하며, 다양한 시나리오에서 폭 넓게 활용이 가능함을 보였습니다.

 

연구팀은 FairBatch가 높은 성능을 달성함과 동시에 실제 머신러닝 파이프라인에 쉽게 적용될 수 있다는 장점을 가졌기에, 해당 학습 기법을 다양한 어플리케이션에 적용할 수 있을 것이라고 설명했습니다. 또한 공정한 머신러닝 시스템에 대한 사회적 요구가 더욱 커짐에 따라, 이에 대한 활발한 후속 연구가 진행될 것으로 예상됩니다. 본 연구 성과는 머신러닝 최고 권위 학회인 ICLR (International Conference for Learning Representations) 2021에서 발표되었습니다.

 

자세한 연구 내용은 하단의 링크에서 확인하실 수 있습니다.

1

Figure 1. A scenario that shows how FairBatch adaptively adjusts batch ratios in model training for fairness.

2

Figure 2.  PyTorch code for model training where FairBatch is used for batch selection. Only a single-line code change is required to replace an existing sampler with FairBatch, marked in blue.

 

Title: FairBatch: Batch Selection for Model Fairness

Authors: Yuji Roh (KAIST EE), Kangwook Lee (Wisconsin-Madison Electrical & Computer Engineering), Steven Euijong Whang (KAIST EE), and Changho Suh (KAIST EE)

Paper: https://openreview.net/forum?id=YNnpaAKeCfx

Source code: https://github.com/yuji-roh/fairbatch

Slides: https://docs.google.com/presentation/d/1IfaYovisZUYxyofhdrgTYzHGXIwixK9EyoAsoE1YX-w/edit?usp=sharing

머신러닝 기반의 차량용 신뢰성 플래시 메모리 및 스토리지 시스템 개발

SW컴퓨팅산업원천기술개발사업

정명수 교수 연구팀 2021 년도 SW컴퓨팅산업원천기술개발사업 신규 선정

우리 학부 정명수 교수 연구팀이 제안한 “초연결사회를 위한 ICT향 지능형 스토리지 시스템”이 과학기술정보통신부와 정보통신기획평가원(IITP)이 주관하는 SW컴퓨팅산업원천기술개발 사업공모에서 신규 지원 대상으로 선정되었다. 정명수 교수 연구팀은 본 과제에서 단독으로 4년간 총 16억원의 연구비 지원을 받게 되었다.
제안하는 과제는 머신러닝을 통해 자율주행차량의 장애 예방 및 수명 연장에 핵심적인 스토리지 시스템의 신뢰성을 강화하는 내용을 담고 있다. 연구진은 본 연구에서 머신러닝 알고리즘, 하드웨어 자동화 기술, 스토리지 아키텍처를 아우르는 통합적인 기술을 개발할 것이다. IITP는 과제 선정 배경에 본 과제를 통해 국제 수준의 지능형 스토리지 원천기술 확보가 가능할 것으로 판단했다고 밝혔다.우리 학부 정명수 교수 연구팀이 제안한 “초연결사회를 위한 ICT향 지능형 스토리지 시스템”이 과학기술정보통신부와 정보통신기획평가원(IITP)이 주관하는 SW컴퓨팅산업원천기술개발 사업공모에서 신규 지원 대상으로 선정되었다. 정명수 교수 연구팀은 본 과제에서 단독으로 4년간 총 16억원의 연구비 지원을 받게 되었다.

IITP는 SW컴퓨팅산업원기술개발사업을 통해 미래 SW 기술을 주도할 유망분야에 대하여 SW의 지능화, 고성능화에 필요한 세계적 수준의 SW 원천핵심기술개발을 지원하고 있다.

4 0
5 0

TensorPRAM: Designing a Scalable Heterogeneous Deep Learning Accelerator with Byte-addressable PRAMs

이상원, 박규영, 정명수 (지도교수)

12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2020, Poster

https://www.usenix.org/conference/hotstorage20/presentation/lee

본 연구진은 확장 가능한 심층학습 가속기인 TensorPRAM을 제안한다. 이 가속기는 심층학습 연산을 수행하기 위한 연산 배열 형태로 구성할 수 있다. TensorPRAM은 행렬 곱셈 및 합성곱 연산을 수행할 수 있는 시스톨릭 배열 가속기를 포함하고 있다. 또한, 호스트와 가속기간 불필요한 데이터 이동을 줄이기 위해 TensorPRAM의 메모리를 바이트 단위 입출력이 가능한 비휘발성 메모리인 PRAM으로 대체하였다. 단일 FPGA 보드에 범용 프로세서, PCIe, PRAM 컨트롤러 및 시스톨릭 배열을 넣어 TensorPRAM prototype을 구현하였으며, PCIe 버스에 여러 개의 TensorPRAM을 연결하여 확장 가능하도록 구성하였다. 실제 시스템에서 평가한 결과, 다양한 DNN 워크로드에서 범용 프로세서 기반 가속기 및 시스톨릭 배열 기반 가속기 대비 평균 99%, 48% 빠른 연산 성능을 보였다.

3 0

그림1. 시스템 개요

Platform-Agnostic Lightweight Deep Learning for Garbage Collection Scheduling in SSDs

장준혁, 국동현, 신진우 (AI대학원 석좌교수), 정명수 (지도교수)

12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2020, Poster

https://www.usenix.org/conference/hotstorage20/presentation/jang

가비지 컬렉션(GC)은 솔리드 스테이드 드라이브(SSD)의 성능이 저하되는 주 요인 중 하나이다. 따라서 학계 및 산업계에서는 GC로 인한 성능 저하를 줄이기 위해 노력해왔다. 이를 위한 한가지 방식으로, 사용자가 SSD를 사용하지 않는 유휴 시간에 GC를 수행하고자 하는 연구들이 있었다. 백그라운드 GC라 불리는 이 기법은 큰 성능 개선을 얻을 수 있으나, 사용자가 SSD에 요청을 보내는 시점을 예측하기 어렵다는 새로운 문제점이 발생한다.

본 연구진은 심층학습 알고리즘을 사용하여 다음 입출력 요청이 오는 시간을 예측하고, 이를 통해 얻은 정확한 유휴시간을 기반으로 백그라운드 GC를 수행하여 사용자가 GC로 인한 성능 저하를 경험할 수 없도록 하는 새로운 GC 스케줄링 기법을 제안한다. 한편, 기존 DNN알고리즘은 학습하는데 수 십 시간에서 수 일이 걸리기 때문에 가변적인 입출력 요청 도착 시간 패턴의 예측에 적용하기 어렵다. 이를 위해, 본 연구진은 SSD에서 실시간으로 수집된 적은 양의 데이터로 DNN을 학습할 수 있는 가벼운 온라인 학습 알고리즘을 적용하여, 실시간으로 변하는 입출력 패턴을 SSD 내에서 언제나 높은 정확도로 예측할 수 있도록 했다. 제안된 GC스케줄러를 사용했을 때, 기존 알고리즘과 DNN기반 알고리즘에 비해 입출력 요청의 처리지연시간이 각각 82.4%, 67.9% 감소하였으며, 다양한 워크로드에서 DNN기반 알고리즘에 비해 16.9% 높은 예측 정확도를 보였다.

1 0

그림1. 시스템 개요

2 0

그림2. 고정된 모델과 온라인 학습이 적용된 모델의 예측 정확도 비교

 

Hai Tran, Sumyeong Ahn, Taeyoung Lee, and Yung Yi "Enlarging Discriminative Power by Adding an Extra Class in Unsupervised Domain Adaptation" ICPR (International Conference on Pattern Recognition), 2020.

본 연구는 레이블이 존재하는 소스 도메인 데이터와 레이블이 없는 타깃 도메인 데이터를 활용하여 타깃 도메인에 대한 예측 모델을 얻는 것을 목표로 하는 비지도 학습 도메인 어댑테이션 문제를 해결한다.

최근, 양쪽의 도메인에 대해 불변한 특징 및 타깃 도메인에서 클래스별로 차별성이 높은 특징들을 추출하는 아이디어를 기반으로 한 연구들이 많이 제안되어왔고, 본 연구는 새로운 인공 클래스를 추가하고 GAN으로부터 생성된 인공 클래스의 샘플과 함께 학습 데이터에 대한 모델을 훈련함으로써 도메인에 대한 차별성을 향상하는 방법을 제안한다.

새로운 클래스 샘플을 기반으로 훈련된 모델은 타깃 도메인에서 클래스의 데이터를 재배치하여 특성 공간에서 대상 클러스터 사이의 거리를 늘림으로써보다 차별적인 특성을 추출 할 수 있다.

본 연구에서 제안하는 방법은 일반적인 방법론이므로 DANN, VADA 및 DIRT-T와 같은 기존의 많은 방법과 호환이 가능하며 비지도 도메인 어댑테이션 성능 평가에 사용되는 표준 데이터를 사용한 다양한 실험을 통해 본 연구에서 제안한 방법이 기존 연구 대비 가장 높은 성능을 냄을 확인하였다.

 

3 0