그래프 연산이나 저장 구조를 최적화할 때 빠지지 않고 등장하는 자료구조가 CSR(Compressed Sparse Row)입니다. 1977년 예일 대학교가 발표한 Yale Sparse Matrix Package 보고서에서 처음 소개되어 Yale Format이라고도 불리는데, 희소 행렬(sparse matrix)을 효율적으로 저장하고 처리하기 위해 고안되었습니다.
희소 행렬이란
희소 행렬은 대부분의 원소가 0인 행렬을 말합니다. 과학 계산, 그래프 이론, 머신러닝 등 현대 컴퓨팅의 거의 전 영역에서 마주치게 되는데, 현실의 데이터를 행렬로 옮기면 십중팔구 이런 모양이 됩니다. SNS를 예로 들면, 사용자가 100만 명이라 해도 한 사람의 친구 수는 보통 500명 안팎입니다. 그런데 이것을 그대로 행렬로 표현하려면 1조(10^12) 크기, 그러니까 7.3PB에 달하는 행렬이 필요해집니다. 실제 정보량에 비해 저장 공간이 터무니없이 커지는 셈입니다.
이런 희소 행렬의 대표적인 사례가 인접 행렬(Adjacency Matrix)입니다. 그래프 상에서 노드 사이의 연결 관계를 표현한 행렬로, 다음과 같은 간단한 그래프를 생각해보면 쉽게 이해할 수 있습니다.
0 ── 1
| |
3 ── 2
이 그래프를 인접 행렬로 옮기면 이렇게 됩니다.
노드0 노드1 노드2 노드3
노드0 [ 0 1 0 1 ]
노드1 [ 1 0 1 1 ]
노드2 [ 0 1 0 1 ]
노드3 [ 1 1 1 0 ]
노드가 늘어날수록 행렬의 크기는 노드 수의 제곱으로 커지는데, 실제로 채워지는 값은 대부분 0입니다. 그럼에도 인접 행렬은 특정 노드의 이웃을 빠르게 찾아야 하는 BFS나 Ego-Net 계산 같은 작업에 널리 쓰입니다. 문제는 이 행렬을 있는 그대로 저장하면 메모리 낭비가 너무 크다는 점이고, CSR은 바로 이 문제를 해결합니다.
CSR의 구조
CSR은 희소 행렬을 세 개의 배열만으로 표현합니다.
| 이름 | 크기 | 설명 |
|---|---|---|
values | NNZ (Number of Non-Zeros) | 0이 아닌 모든 원소 값을 행(row) 순서대로 저장 |
column_indices | NNZ | 각 값이 속한 열(column) 번호 |
row_pointers | Row Count + 1 | 각 행의 시작 위치를 values 배열의 인덱스로 저장 |
핵심 아이디어는 단순합니다. 0인 값은 어차피 아무 정보도 주지 않으니 아예 저장하지 않고, 0이 아닌 값(NNZ)의 실제 값과 위치만 남기자는 것입니다.
변환 과정 따라가 보기
앞서 본 인접 행렬을 값으로 구분해서 다시 그려보겠습니다.
노드0 노드1 노드2 노드3
노드0 [ 0 A 가 B ]
노드1 [ C 0 D E ]
노드2 [ 0 F 0 G ]
노드3 [ H I J 0 ]
먼저 0이 아닌 원소들을 행 순서대로 훑으면서 values 배열과, 각 값이 몇 번째 열에 있었는지를 담은 column_indices 배열을 만듭니다.
values: [A, B, C, D, E, F, G, H, I, J]
column_indices: [1, 3, 0, 2, 3, 1, 3, 0, 1, 2]
다음으로 각 행이 values 배열에서 어디서부터 어디까지를 차지하는지를 기록합니다. 0번 행은 2개, 1번 행은 3개, 2번 행은 2개, 3번 행은 3개의 원소를 갖고 있으니, 이 경계값들을 누적해서 row_pointers 배열을 만듭니다.
row 0: column_indices[0:2] # 2개의 원소가 NNZ
row 1: column_indices[2:5] # 3개의 원소가 NNZ
row 2: column_indices[5:7] # 2개의 원소가 NNZ
row 3: column_indices[7:10] # 3개의 원소가 NNZ
row_pointers: [0, 2, 5, 7, 10]
이렇게 완성된 세 배열이 곧 CSR 표현입니다.
values: [A, B, C, D, E, F, G, H, I, J]
column_indices: [1, 3, 0, 2, 3, 1, 3, 0, 1, 2]
row_pointers: [0, 2, 5, 7, 10]
4×4 행렬 하나를 표현하는 데 원래 16칸이 필요했지만, CSR은 NNZ 10개에 대한 값과 열 정보, 그리고 행 개수만큼의 포인터만 있으면 충분합니다. 행렬이 커지고 희소성이 높아질수록 이 격차는 훨씬 더 벌어집니다.
CSR이 실제로 쓰이는 곳
희소 행렬-벡터 곱셈 (SpMV)
CSR이 가장 효과적으로 작동하는 영역은 희소 행렬-벡터 곱셈, 즉 $y = Ax$ 연산입니다. 행렬을 있는 그대로 곱하면 행렬의 열 크기와 벡터 길이에 비례하는 연산이 필요하지만, CSR로 표현된 행렬을 곱할 때는 실제로 값이 존재하는 원소, 즉 NNZ 개수만큼만 연산하면 됩니다. 0을 곱하고 더하는 무의미한 연산을 애초에 건너뛰는 셈입니다.
그래프 연산 최적화
row_pointers 배열이 있으면 특정 노드의 이웃을 아주 빠르게 뽑아낼 수 있습니다. n번째 노드의 이웃은 column_indices[row_pointers[n] : row_pointers[n+1]]로 슬라이싱하기만 하면 됩니다. 게다가 이 저장 구조는 연속된 메모리 공간에 값이 나란히 놓이기 때문에 cache locality가 매우 높고, 그만큼 CPU 캐시 라인 활용도 최적화됩니다. BFS나 Ego-Net 계산처럼 이웃 탐색이 빈번한 그래프 연산이 CSR 위에서 유독 빠르게 동작하는 이유가 여기에 있습니다. 이런 이점 때문에 많은 그래프 처리 프레임워크가 CSR을 기본 저장 포맷으로 채택하고 있습니다.
CSR의 한계
물론 공짜는 없습니다. CSR은 배열 기반 저장 구조이기 때문에 값을 수정하는 작업에는 취약합니다. 노드 사이에 새로운 엣지 하나를 추가하려면 values와 column_indices 배열 중간에 값을 끼워 넣어야 하는데, 배열의 특성상 이는 뒤따르는 모든 원소를 한 칸씩 밀어야 하는 비용이 큰 작업입니다. 그래서 CSR은 그래프나 행렬이 자주 바뀌지 않는, 읽기 위주의 워크로드에 특히 적합합니다.