사전학습 언어 모델(PLM)의 미세조정은 최근 지식 그래프 완성(KGC)을 향상시킬 잠재력이 있는 것으로 나타났다. 그러나 대부분의 PLM 기반 방법은 텍스트 정보의 인코딩에만 초점을 맞추며, 지식 그래프의 장꼬리(long-tailed) 특성과 그에 따른 다양한 위상 구조—예를 들어 부분그래프, 최단 경로, 차수—를 충분히 고려하지 못한다. 우리는 이것이 KGC에 대한 PLM의 더 높은 정확도를 달성하는 데 있어 주요 장애물이라고 주장한다. 이를 위해 본 연구는 KGC를 위한 부분그래프 인지 학습 프레임워크(Subgraph-Aware Training framework for KGC, SATKGC)를 제안하며, 두 가지 아이디어를 포함한다. (i) 하드 네거티브 샘플링을 유도하고 학습 중 엔티티 등장 빈도의 불균형을 완화하기 위한 부분그래프 인지 미니 배칭, 그리고 (ii) 지식 그래프의 구조적 성질 관점에서 더 어려운 배치 내 네거티브 트리플과 더 어려운 포지티브 트리플에 주목하도록 하는 새로운 대조 학습이다. 우리가 아는 한, 본 연구는 지식 그래프의 구조적 귀납적 편향을 PLM 미세조정에 포괄적으로 반영한 최초의 연구이다. 세 가지 KGC 벤치마크에 대한 광범위한 실험은 SATKGC의 우수성을 입증한다. 우리의 코드는 제공된다.https://github.com/meaningful96/SATKGC

k-결함 결합(clique)은 전통적인 결합 정의를 완화하여 최대 k개의 누락된 간선을 허용하는 개념이다. 이러한 완화는 링크 예측, 커뮤니티 탐지, 소셜 네트워크 분석 등 다양한 실제 응용에서 중요하다. 최대 k-결함 결합을 열거하고 최대 k-결함 결합을 탐색하는 문제들이 광범위하게 연구되어 왔음에도, 기존 알고리즘은 작은 부분해들의 조합적 폭발과 비최적 탐색 공간과 같은 한계를 겪는다. 이러한 한계를 해결하기 위해, 우리는 먼저 결합을 생성한 뒤 누락된 간선을 추가하는 새로운 결합-우선 분기한정(branch-and-bound) 프레임워크를 제안한다. 또한, 입력 그래프에서 정점의 수가 n일 때 탐색 공간 크기가 O(3^{n/3} • n^k)임을 달성하는 새로운 피벗팅(pivoting) 기법을 도입한다. k가 상수일 때 최대 k-결함 결합의 최악의 경우 개수가 Ω(3^{n/3} • n^k)임을 증명함으로써, 우리의 알고리즘의 탐색 공간이 최악의 경우 최적인 것을 확립한다. 결함 결합의 지름-2(diameter-two) 성질을 활용하여, 탐색 공간 크기를 O(n • 3^{δ/3} • (δΔ)^k)로 추가로 감소시킨다. 여기서 δ는 퇴화도(degeneracy)이고 Δ는 입력 그래프의 최대 차수이다. 우리는 또한 제안한 분기한정을 기반으로 최대 k-결함 결합 탐색을 위한 효율적인 프레임워크를 제시하며, 탐색 공간을 줄이기 위한 실용적인 기법들도 함께 제안한다. 100만 개 이상의 간선을 포함하는 실제 세계 벤치마크 데이터셋에 대한 실험 결과, 최대 k-결함 결합 열거와 최대 k-결함 결합 탐색을 위한 각 제안 알고리즘이 처리 시간 측면에서 해당하는 최첨단 알고리즘을 최대 4자릿수(orders of magnitude)까지 능가함을 보여주었다.

거대 언어 모델(Large Language Models, LLMs)은 강력한 추론 능력을 보이지만 환각(hallucinations) 문제와 제한된 투명성에 어려움을 겪는다. 최근에는 지식 그래프(Knowledge Graphs, KGs)를 통합하는 KG 강화 LLM들이 특히 복잡하고 지식 집약적인 과제에서 추론 성능을 향상시키는 것으로 보고되었다. 그러나 이러한 방법들은 여전히 부정확한 검색과 추론 실패를 포함한 중대한 도전에 직면해 있으며, 이는 관련 정보가 가려지는 긴 입력 컨텍스트나, 서로 다른 질문 유형에 필요한 보다 풍부한 논리적 방향성을 포착하기 어려운 컨텍스트 구성에 의해 종종 악화된다. 또한 많은 접근법이 LLM에게 KGs로부터 증거를 직접 검색하도록 하고, 그 증거의 충분성에 대해 스스로 평가하게 하는데, 이 과정에서 조기 또는 부정확한 추론이 발생하는 경우가 흔하다. 검색 및 추론 실패를 해결하기 위해, 우리는 복잡한 질문을 하위 질문으로 분해하고 각 하위 질문에 답함으로써 부분적 추론 경로를 점진적으로 확장하는 다중 홉 지식 그래프 질의응답(KGQA) 프레임워크인 ProgRAG을 제안한다. 각 단계에서 외부 검색기들이 후보 증거를 수집하고, 이후 LLM이 불확실성 인지 기반 가지치기(uncertainty-aware pruning)를 통해 이를 정제한다. 마지막으로, 하위 질문 답변으로부터 얻은 부분적 추론 경로들을 구성하고 재배열함으로써 LLM 추론을 위한 컨텍스트를 최적화한다. 세 가지 잘 알려진 데이터셋에 대한 실험 결과, ProgRAG은 다중 홉 KGQA에서 기존의 기준 방법들을 능가하며, 향상된 신뢰성과 추론 품질을 제공함을 확인하였다.

사전학습 언어 모델(PLM)의 미세조정은 최근 지식 그래프 완성(KGC)을 향상시킬 잠재력이 있는 것으로 나타났다. 그러나 대부분의 PLM 기반 방법은 텍스트 정보의 인코딩에만 초점을 맞추며, 지식 그래프의 장꼬리(long-tailed) 특성과 그에 따른 다양한 위상 구조—예를 들어 부분그래프, 최단 경로, 차수—를 충분히 고려하지 못한다. 우리는 이것이 KGC에 대한 PLM의 더 높은 정확도를 달성하는 데 있어 주요 장애물이라고 주장한다. 이를 위해 본 연구는 KGC를 위한 부분그래프 인지 학습 프레임워크(Subgraph-Aware Training framework for KGC, SATKGC)를 제안하며, 두 가지 아이디어를 포함한다. (i) 하드 네거티브 샘플링을 유도하고 학습 중 엔티티 등장 빈도의 불균형을 완화하기 위한 부분그래프 인지 미니 배칭, 그리고 (ii) 지식 그래프의 구조적 성질 관점에서 더 어려운 배치 내 네거티브 트리플과 더 어려운 포지티브 트리플에 주목하도록 하는 새로운 대조 학습이다. 우리가 아는 한, 본 연구는 지식 그래프의 구조적 귀납적 편향을 PLM 미세조정에 포괄적으로 반영한 최초의 연구이다. 세 가지 KGC 벤치마크에 대한 광범위한 실험은 SATKGC의 우수성을 입증한다. 우리의 코드는 제공된다.https://github.com/meaningful96/SATKGC

k-결함 결합(clique)은 전통적인 결합 정의를 완화하여 최대 k개의 누락된 간선을 허용하는 개념이다. 이러한 완화는 링크 예측, 커뮤니티 탐지, 소셜 네트워크 분석 등 다양한 실제 응용에서 중요하다. 최대 k-결함 결합을 열거하고 최대 k-결함 결합을 탐색하는 문제들이 광범위하게 연구되어 왔음에도, 기존 알고리즘은 작은 부분해들의 조합적 폭발과 비최적 탐색 공간과 같은 한계를 겪는다. 이러한 한계를 해결하기 위해, 우리는 먼저 결합을 생성한 뒤 누락된 간선을 추가하는 새로운 결합-우선 분기한정(branch-and-bound) 프레임워크를 제안한다. 또한, 입력 그래프에서 정점의 수가 n일 때 탐색 공간 크기가 O(3^{n/3} • n^k)임을 달성하는 새로운 피벗팅(pivoting) 기법을 도입한다. k가 상수일 때 최대 k-결함 결합의 최악의 경우 개수가 Ω(3^{n/3} • n^k)임을 증명함으로써, 우리의 알고리즘의 탐색 공간이 최악의 경우 최적인 것을 확립한다. 결함 결합의 지름-2(diameter-two) 성질을 활용하여, 탐색 공간 크기를 O(n • 3^{δ/3} • (δΔ)^k)로 추가로 감소시킨다. 여기서 δ는 퇴화도(degeneracy)이고 Δ는 입력 그래프의 최대 차수이다. 우리는 또한 제안한 분기한정을 기반으로 최대 k-결함 결합 탐색을 위한 효율적인 프레임워크를 제시하며, 탐색 공간을 줄이기 위한 실용적인 기법들도 함께 제안한다. 100만 개 이상의 간선을 포함하는 실제 세계 벤치마크 데이터셋에 대한 실험 결과, 최대 k-결함 결합 열거와 최대 k-결함 결합 탐색을 위한 각 제안 알고리즘이 처리 시간 측면에서 해당하는 최첨단 알고리즘을 최대 4자릿수(orders of magnitude)까지 능가함을 보여주었다.

거대 언어 모델(Large Language Models, LLMs)은 강력한 추론 능력을 보이지만 환각(hallucinations) 문제와 제한된 투명성에 어려움을 겪는다. 최근에는 지식 그래프(Knowledge Graphs, KGs)를 통합하는 KG 강화 LLM들이 특히 복잡하고 지식 집약적인 과제에서 추론 성능을 향상시키는 것으로 보고되었다. 그러나 이러한 방법들은 여전히 부정확한 검색과 추론 실패를 포함한 중대한 도전에 직면해 있으며, 이는 관련 정보가 가려지는 긴 입력 컨텍스트나, 서로 다른 질문 유형에 필요한 보다 풍부한 논리적 방향성을 포착하기 어려운 컨텍스트 구성에 의해 종종 악화된다. 또한 많은 접근법이 LLM에게 KGs로부터 증거를 직접 검색하도록 하고, 그 증거의 충분성에 대해 스스로 평가하게 하는데, 이 과정에서 조기 또는 부정확한 추론이 발생하는 경우가 흔하다. 검색 및 추론 실패를 해결하기 위해, 우리는 복잡한 질문을 하위 질문으로 분해하고 각 하위 질문에 답함으로써 부분적 추론 경로를 점진적으로 확장하는 다중 홉 지식 그래프 질의응답(KGQA) 프레임워크인 ProgRAG을 제안한다. 각 단계에서 외부 검색기들이 후보 증거를 수집하고, 이후 LLM이 불확실성 인지 기반 가지치기(uncertainty-aware pruning)를 통해 이를 정제한다. 마지막으로, 하위 질문 답변으로부터 얻은 부분적 추론 경로들을 구성하고 재배열함으로써 LLM 추론을 위한 컨텍스트를 최적화한다. 세 가지 잘 알려진 데이터셋에 대한 실험 결과, ProgRAG은 다중 홉 KGQA에서 기존의 기준 방법들을 능가하며, 향상된 신뢰성과 추론 품질을 제공함을 확인하였다.

주가 추세 예측(stock trend prediction)은 과거의 특징 시퀀스로부터 미래의 주가 추세를 예측하는 과제로, 금융시장의 복잡하고 역동적인 특성 때문에 여전히 매우 도전적이다. 실제로 주식은 시장 상황이 변화함에 따라 전통적인 업종 경계를 넘어 다양한 관계를 형성한다. 즉, 동일한 업종의 주식이라도 서로 다른 추세를 보일 수 있는 반면, 서로 다른 업종의 주식들은 종종 유사한 움직임을 보인다. 그러나 대부분의 기존 주가 예측 방법은 미리 정의된 정적 관계에 의존하여, 변화하는 시장 동학에 적응할 수 있는 유연성을 결여하고 있다. 또한 선행연구에서 널리 사용된 목적함수(objectives)들은 주식시장 데이터의 복잡한 패턴과 관계를 포착하는 데 한계가 있다. 이러한 한계를 해결하기 위해 우리는 DYCOR라는 새로운 주가 추세 예측 방법을 제안하며, 이는 두 가지 핵심 혁신을 통합한다. (i) 동적 주식 클러스터링(dynamic stock clustering)은 미리 정의된 관계 데이터에 의존하지 않고 잠재된 주식 관계를 적응적으로 발견함으로써 시장 특성을 포착하며, (ii) 상관 인식 학습(correlation-aware training)은 예측된 주가 추세와 정답(ground-truth) 주가 추세를 그 상관관계를 세밀한 수준에서 반영하여 정렬(alignment)한다. 우리는 기존 연구에서 널리 사용되는 세 가지 데이터셋인 NASDAQ, NYSE, S&P 500에서 DYCOR를 평가하였고, 본 방법은 상관 기반 및 검색 기반 지표(correlation-based 및 retrieval-based metrics) 전반에서 최신(state-of-the-art) 기준(baseline) 방법들에 비해 우수한 성능을 보이면서도 경쟁력 있는 실행 시간 효율(runtime efficiency)을 유지한다.

검토 기반 추천 시스템(Review-Based Recommendation System, RBRS)의 목표는 사용자-아이템 상호작용뿐만 아니라 리뷰 텍스트를 활용하여 사용자와 아이템의 표현을 효과적으로 학습하는 것이다. 추천 시스템에서 널리 사용되는 사용자-아이템 상호작용 그래프를 기반으로, 최근의 그래프 신경망(Graph Neural Networks, GNN) 활용 RBRS 방법들은 사용자와 아이템 사이의 각 간선을 해당 아이템에 대한 사용자의 리뷰 정보와 연관시켜 표현을 획득한다. 그러나 이러한 GNN 기반 RBRS 방법에는 두 가지 주요 문제가 있다. (1) 각 리뷰 텍스트를 가중치, 즉 간선의 단일 값으로 변환함으로써 리뷰에 내재된 사용자와 아이템에 대한 풍부한 정보를 상실한다는 점과, (2) 각 사용자에 대해 단 하나의 일반 표현만을 생성함으로써 사용자가 상호작용한 아이템에 대한 평점에서 좋아함과 싫어함이 미치는 개별적 효과를 표현할 수 없다는 점이다. 이러한 문제를 해결하기 위해, 본 연구에서는 사용자-사용자 그래프와 아이템-아이템 그래프를 포함하는 동질 그래프(homogeneous graphs)를 활용하여 일반적인 사용자 및 아이템 표현과 더불어 사용자의 좋아함 및 싫어함 표현을 학습하는 새로운 GNN 기반 RBRS인 LETTER를 제안한다. LETTER는 제안된 동질 그래프를 활용함으로써 리뷰 정보를 손실하지 않고 사용자와 아이템 표현을 학습할 수 있다. 또한 LETTER는 좋아함과 싫어함 표현이 사용자의 평점에 미치는 영향을 명시적으로 설계하여 정확한 평점 예측을 수행한다. 여섯 개의 데이터셋에 대한 실험을 통해, 제안된 LETTER가 최대 23.1%까지 아홉 개의 최신 RBRS보다 우수함을 검증하였다. 본 연구의 소스 코드는 https://github.com/Bigdasgit/LETTER 에서 제공된다.

사용자-아이템 상호작용 외에도 아이템의 다중모달 특징을 활용하는 것에 더해, 최근 멀티미디어 추천 시스템에서는 대조학습(Contrastive Learning, CL)을 이용하여 데이터 희소성 문제를 크게 완화하기 위한 연구가 추가로 이루어졌다. CL 기반 방법은 각 인스턴스에 대해 최소 두 개의 임베딩(즉, 뷰)을 생성하고, 이러한 뷰들을 통해 다양한 관점에서 각 인스턴스의 정보를 풍부하게 함으로써 데이터 희소성 문제를 완화한다. 따라서 CL 기반 방법들은 하위 과제에서 각 인스턴스의 특성을 효과적으로 나타내는 뷰를 생성하는 데 초점을 두어 왔다. 마찬가지로 CL 기반 멀티미디어 추천 시스템 역시 아이템의 다중모달 특징을 활용하여 사용자/아이템 뷰를 효과적으로 생성하려는 노력을 기울여 왔다. 그러나 우리는 뷰 생성 과정에서 간과된 다음 두 가지 한계를 지적한다: (1) 아이템의 각 모달리티 특징이 사용자-아이템 상호작용에 미치는 영향을 식별하려고 시도하지 않았거나, 무작위 마스킹 또는 상호작용 드롭을 통해 이를 식별한 경우가 있으며, (2) 미래에 상호작용으로 이어질 가능성이 높은 비상호작용을 식별하려고 시도하지 않았다. 이러한 한계를 극복하기 위해, 우리는 모달리티 인식 그래프 정제(modality-aware graph refiNEment)와 contraSTive leARning을 활용한 새로운 멀티미디어 추천 프레임워크 STARLINE을 제안한다. 5개의 실제 데이터셋에 대한 광범위한 실험은 STARLINE의 효과성과 타당성을 검증하며, 특히 가장 우수한 경쟁 방법 대비 최대 13.24%까지 일관되게 더 높은 정확도를 보임을 확인하였다.

대규모 언어 모델(LLM)은 사실과 부합하지 않는 출력을 생성하는 경향이 있으므로, LLM만을 활용할 때 발생하는 이러한 단점을 완화하기 위한 핵심 수단으로 검색 증강 생성(retrieval-augmented generation, RAG)이 상당한 주목을 받아 왔다. 그러나 단일 및 다중 홉 질문응답(QA)을 위한 기존 RAG 방법들은 여전히 부정확한 검색과 환각에 취약하다. 이러한 한계를 해결하기 위해, 우리는 질문응답 과제를 위한 새로운 RAG 프레임워크인 CoopRAG를 제안한다. CoopRAG는 검색기(retriever)와 LLM이 유용한 지식을 상호 교환함으로써 서로 협력하도록 하며, 또한 검색기 모델의 초기 및 후기 계층이 서로 협력하여 주어진 질의와 관련된 검색 문서를 정확하게 순위화하도록 설계되었다. 이 프레임워크에서 우리는 (i) 불확실한 위치가 마스킹된 추론 체인과 하위 질문들로 질문을 분해하고, (ii) 하위 질문 및 추론 체인이 결합된 형태로 질문에 관련된 문서를 검색하며, (iii) 검색기(retriever)의 서로 다른 계층들을 대조하여 문서를 재순위화하고, (iv) LLM을 통해 마스킹된 위치를 채워 추론 체인을 재구성한다. 우리의 실험 결과, CoopRAG는 검색 성능과 QA 성능 모두에서 3개의 다중 홉 QA 데이터셋뿐 아니라 단순 QA 데이터셋에서도 기존의 최신 QA 방법들보다 일관되게 더 우수함을 보여준다. 우리의 코드는 공개되어 있다.