PuzzleTensor: A Method-Agnostic Data Transformation for Compact Tensor Factorization

 본 문서에서는 KDD 2025 학회에 발표된 "PuzzleTensor: A Method-Agnostic Data Transformation for Compact Tensor Factorization" 논문을 소개합니다. 논문에 대한 상세한 정보는 다음과 같습니다.

• Title: PuzzleTensor: A Method-Agnostic Data Transformation for Compact Tensor Factorization
• Authors: Yong-chan Park, Kisoo Kim, and U Kang
• Conference: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) 2025

Tensor Decomposition

효율적인 고차원 데이터 표현은 데이터 마이닝, 머신러닝, 추천 시스템, 신호 처리, 과학 계산 등 다양한 응용 분야에서 매우 중요합니다. CANDECOMP/PARAFAC(CP), Tucker, Tensor-Train(TT)과 같은 텐서 분해 알고리즘은 이러한 분야에서 핵심적인 도구로 자리 잡고 있으며, 계산 효율성과 데이터의 근본적인 구조에 대한 통찰을 제공합니다. 그러나 이러한 방법을 원시 다차원 데이터에 직접 적용하면 높은 목표 랭크가 요구되거나, 재구성 정확도가 낮아지거나, 계산 효율성이 저하되는 문제가 발생할 수 있습니다. 이는 실제 세계의 텐서가 많은 분해 기법들이 의존하는 엄격한 저랭크 또는 희소성 가정을 잘 따르지 않기 때문입니다. 

예시로 그림 1을 살펴보겠습니다. 여기서 $X$는 원본 데이터를, $\hat{X}$은 그것의 랭크-1 근사를 나타내며, 이 경우 비교적 큰 오차가 발생합니다. 그러나 $X$의 각 열(column)을 일정한 크기만큼 위로 이동시키면, 더 잘 정렬된 행렬 $Z$를 얻을 수 있고, 이에 따라 랭크-1 근사 오차가 크게 줄어듭니다. 중요한 통찰은, 텐서의 랭크가 그 슬라이스(slices)와 모드(modes)가 공간적으로 어떻게 배열되어 있는가와 밀접하게 연관되어 있다는 점입니다. 실제 데이터에서는 높은 랭크가 종종 데이터의 불일치나 이질성에서 비롯되며, 이는 국소적인 패턴들이 모드 간에 자연스럽게 정렬되지 않기 때문입니다. 이러한 맥락에서 근본적인 질문이 제기됩니다. 어떻게 하면 데이터를 체계적으로 변환하여 공통 구조가 자연스럽게 정렬되도록 하고, 정확도를 희생하지 않으면서도 저랭크 분해를 가능하게 만들 수 있을까요?

그림 1. 데이터 정렬이 저랭크 근사를 개선하는 예시 
원본 데이터 $X$의 경우, 랭크-1 근사 $\widehat{X}$이 큰 오차를 보입니다. 그러나 각 열을 정렬하여 $Z$를 구성하면, 그 랭크-1 근사 $\widehat{Z}$은 현저히 낮은 오차를 달성합니다. 이는 데이터를 재구성함으로써 원본 형태에서는 드러나지 않던 저랭크 구조가 드러날 수 있음을 보여줍니다.

Proposed Method

본 논문에서는 PuzzleTensor라는 모델 독립적(model-agnostic) 데이터 변환 기법을 제안합니다. 퍼즐 조각을 재배치하여 하나의 완성된 그림을 만드는 아이디어에서 착안하여, PuzzleTensor는 텐서의 하이퍼슬라이스(hyperslice)를 이동시켜 구조를 변환함으로써 훨씬 낮은 목표 랭크로도 정확한 분해가 가능하도록 합니다(그림 2).

그림 2. (a) PuzzleTensor의 개요 
주어진 $D$-모드 텐서에 대해, 모든 축을 따라 각각의 $(D-1)$-차원 하이퍼슬라이스를 이동시켜 더 낮은 목표 랭크로 정확한 분해가 가능하도록 합니다.

(b) axis=1에 대해 첫 번째 하이퍼슬라이스를 이동시키는 예시
하이퍼슬라이스는 $(D-1)$개의 가능한 이동 방향을 가지며, 경계를 넘어서는 인덱스는 순환 방식으로 처음으로 되돌아갑니다. 또한 각 하이퍼슬라이스는 서로 다른 크기만큼 이동할 수 있습니다.

본 연구의 핵심 과제와 아이디어는 다음의 세 가지 측면으로 요약됩니다.

1. 이산적 이동 연산 학습: 텐서의 특정 축을 따라 하이퍼슬라이스를 이동시키는 연산은 본질적으로 이산적(discrete) 성격을 가지므로, 경사 기반 최적화(gradient-based optimization)와의 결합이 어렵습니다. 이를 해결하기 위해 본 논문은 푸리에 변환(Fourier transform)의 성질을 활용합니다. 푸리에 변환을 통해 이산적 이동 연산을 실수 영역에서 연속적인 연산으로 완화할 수 있으며, 이를 주파수 영역에서 다시 정의함으로써 미분 가능성을 확보하고 표준 최적화 기법과 호환되도록 합니다.

2. 저랭크 구조 변환: PuzzleTensor의 중요한 목표 중 하나는 입력 텐서를 저랭크 분해가 용이한 구조로 변환하는 것입니다. 하지만 텐서의 랭크를 직접 계산하는 것은 NP-hard 문제이므로, 이는 계산적으로 불가능합니다. 이를 극복하기 위해 본 논문은 텐서의 행렬화(matricization) 표현을 기반으로 한 새로운 목적 함수를 제안합니다. 이 목적 함수는 본질적인 저랭크 특성을 포착하도록 설계되었으며, 이 함수를 최적화할 경우 랭크를 최소화함을 이론적으로 보장합니다. 본 논문의 접근법은 저랭크 구조를 유도하는 변환을 학습하기 위한 원리적이고 계산 효율적인 방법을 제공합니다.

3. 대규모 텐서를 위한 확장성: 입력 텐서가 매우 클 경우, 직접적으로 이동 연산을 학습하는 것은 메모리와 실행 시간 제약으로 인해 현실적으로 어렵습니다. 이러한 확장성 문제를 해결하기 위해 본 논문은 서브블록 분해(sub-block decomposition) 방법을 제시합니다. 이 방법에서는 입력 텐서를 작은 서브블록으로 나누고, 각 블록에 대해 독립적으로 이동 연산을 적용합니다. 서브블록 분해는 병렬 처리에 자연스럽게 적합하며, 각 블록이 독립적으로 이동 및 처리되기 때문에 대규모 텐서 환경에서 실행 시간을 크게 줄일 수 있습니다.

푸리에 기반 이동 연산 (Fourier-Based Shift Operation) 

텐서의 하이퍼슬라이스를 이동시키는 과정은 본질적으로 이산적(discrete)이기 때문에, 경사 기반 최적화 기법에 상당한 어려움을 초래합니다. 실제로, 정수 값으로 정의된 이동 파라미터는 그래디언트의 흐름을 막아 표준 역전파(backpropagation)를 통해 최적의 이동을 학습하기 어렵게 만듭니다. 이러한 한계를 극복하기 위해 본 논문은 푸리에 변환의 성질을 활용합니다. 푸리에 변환을 이용하면 이산적 이동을 주파수 영역에서 연속적 변환으로 다룰 수 있습니다. 이를 통해 정수 이동 파라미터를 실수 값으로 완화함으로써 연산을 미분 가능하게 만들고, 기존 최적화 기법과 호환되도록 할 수 있습니다(그림 3).

그림 3. 푸리에 기반 이동 연산
입력 텐서는 모드-$k$ 하이퍼슬라이스에 대해 푸리에 변환을 통과한 뒤, 학습 가능한 위상 텐서(phase tensor)와의 원소별 곱을 거쳐 역 푸리에 변환을 통해 처리됩니다.

저랭크 구조를 위한 최적화 (Optimization for Low-Rank Structures)

PuzzleTensor의 핵심 목표 중 하나는 입력 텐서를 자연스럽게 저랭크 근사가 가능하도록 재구성하는 것입니다. 그러나 $n > 2$인 $n$-모드 텐서의 정확한 랭크를 결정하는 것은 NP-hard 문제로 알려져 있으며, 이로 인해 직접적인 랭크 최소화 접근법은 계산적으로 실행 불가능합니다. 이를 해결하기 위해 본 논문은 텐서의 행렬화(matricization) 표현에 기반한 새로운 목적 함수를 제안합니다 (그림 4). 이 목적 함수는 본질적인 저랭크 특성을 포착하도록 설계되었으며, 이론적으로 타당한 기준에 의해 정당화됩니다. 특히, 본 논문은 변환된 텐서에 대한 각 행렬화 표현의 핵노름(nuclear norm)을 최소화하면, 해당 고차원 특이값 분해(HOSVD)의 코어 텐서에서 희소성이 유도됨을 이론적으로 증명합니다. 이러한 희소성은 결과적으로 원본 텐서를 더 낮은 목표 랭크에서 정확도를 유지하면서 근사할 수 있도록 합니다.

그림 4. 행렬화 기반 최적화
PuzzleTensor의 목적 함수는 입력 텐서 $X$를 변환하여 텐서 $Z$를 얻은 후 이를 각 모드에 대해 행렬화하여 핵노름의 가중합으로 설계됩니다.

서브블록 변환 (Sub-Block Shifting)

매우 큰 규모의 텐서에 대해 전체 데이터셋에 걸쳐 이동 연산을 적용하는 것은 막대한 메모리 요구량과 긴 실행 시간으로 인해 비현실적입니다. 이러한 문제를 해결하기 위해, 본 논문은 입력 텐서를 더 작고 효율적으로 관리 가능한 서브블록(sub-block)으로 분할하여 각 블록 내에서 독립적으로 이동 연산을 수행할 수 있도록 합니다. 이 전략은 계산 복잡도를 줄일 뿐만 아니라, 각 서브블록이 독립적으로 처리되므로 병렬 처리가 가능해져 대규모 텐서 환경에서도 효율적인 실행을 가능하게 합니다 (그림 5).

그림 5. 서브블록 변환
각 서브블록에 대한 이동 양은 다른 서브블록과 공유되지 않으며, 각 블록의 이동은 독립적으로 학습됩니다. 따라서 이동 연산이 병렬적으로 계산될 수 있으며, 이로 인해 대규모 데이터의 전체 실행 시간이 크게 단축됩니다.

Experiments

표 1은 서로 다른 압축 크기에서 PuzzleTensor의 재구성 성능을 평가합니다. 각 데이터셋에 대해 여러 목표 압축 크기를 지정하고, 다양한 분해 방법을 적용하여 해당 재구성 오차를 측정합니다. 압축 크기는 PuzzleTensor의 파라미터 수와 분해 자체의 파라미터 수를 합산하여 계산합니다. 일반적으로 압축 크기가 커질수록 더 높은 랭크를 허용할 수 있으며, 이로 인해 정확도가 향상됩니다. 표 1에서 볼 수 있듯이 PuzzleTensor를 결합하면 모든 경우에서 재구성 오차가 줄어들며, 이는 하이퍼슬라이스 이동이 더 압축적이고 정밀한 표현을 인자분해가 포착할 수 있도록 돕는다는 점을 시사합니다. 더 나아가, 이러한 성능 향상은 서로 다른 텐서 분해 계열 전반에 걸쳐 일관되게 나타납니다.

표 1. PuzzleTensor의 복원 정확도

다음으로 입력 텐서의 크기가 증가함에 따라 PuzzleTensor의 실행 시간을 측정하여 확장성을 평가합니다. 그림 6은 CP, Tucker, TT 분해에 대해 PuzzleTensor 적용 여부에 따른 실행 시간을 다양한 입력 텐서 크기에서 비교한 결과를 보여줍니다. PuzzleTensor가 추가적인 이동 연산을 도입하긴 하지만, 서브블록 전략에 의해 전체 계산 비용은 PuzzleTensor를 사용하지 않은 기존 분해 방법과 거의 동일하게 유지됩니다. 

그림 6. PuzzleTensor의 확장성 평가

그림 7은 간단한 예시 입력에 대해 PuzzleTensor가 하이퍼슬라이스 이동을 학습하여 데이터의 랭크를 효과적으로 낮추는 과정을 시각적으로 보여줍니다. 이 예시는 데이터의 구조가 재정렬됨에 따라 보다 압축적이고 저랭크 구조가 드러나는 원리를 직관적으로 설명합니다.

그림 7. PuzzleTensor 학습 과정의 시각화

Conclusion

본 문서에서는 KDD 2025에 발표된 “PuzzleTensor: A Method-Agnostic Data Transformation for Compact Tensor Factorization” 논문을 소개하였습니다. 해당 논문은 텐서의 하이퍼슬라이스를 이동시키는 PuzzleTensor 기법을 제안하며, 이를 통해 기존 분해 알고리즘과 결합 시 더 낮은 랭크에서 정확한 분해를 가능하게 합니다. PuzzleTensor는 푸리에 변환을 활용하여 이산적 이동 연산을 연속적으로 완화함으로써 최적화 가능성을 확보하였고, 새로운 목적 함수를 통해 저랭크 구조를 유도하며, 서브블록 분해 전략으로 대규모 텐서에도 확장성을 보장합니다. 실험 결과, PuzzleTensor는 CP, Tucker, TT 등 다양한 텐서 분해 계열 전반에서 일관된 성능 향상을 보였으며, 동일한 압축 크기 기준으로 재구성 오차를 크게 줄였습니다. 본 논문은 데이터 마이닝, 머신러닝, 추천 시스템, 신호 처리, 과학 계산 등 다양한 분야에서 활용되는 텐서 분해의 효율성과 정확성을 동시에 향상시킬 수 있는 새로운 방법론을 제안합니다. 제안된 방법을 통해 대규모 고차원 데이터 분석의 효율성을 높이고, 더 나아가 실제 응용 환경에서의 활용 가능성을 넓힐 수 있을 것으로 기대됩니다. 본 논문에 대한 자세한 정보는 [링크]에서 확인할 수 있습니다.