Lossy compression of weighted graph adjacency matrices by transform coding

당신이 거대하고 복잡한 도시 지도를 친구에게 보내려고 하는데, 인터넷 연결 속도가 너무 느려서 한 번에 전체를 보낼 수 없다고 상상해 보세요. 이것은 그래프 신호 처리(Graph Signal Processing) 분야에서 일하는 과학자들이 매일 직면하는 종류의 퍼즐입니다. 이 분야에서 "그래프"란 점(노드)들과 그 점들을 연결하는 선(엣지)들의 네트워크를 뜻하는 멋진 용어일 뿐이며, 이는 소셜 네트워크의 친구 관계, 뇌의 뉴런, 혹은 도시의 교차로와 같습니다. 보통 이러한 선들은 단순히 연결되어 있는 것에 그치지 않고 "가중치(weights)"를 가집니다. 이 가중치는 연결의 강도, 두 점 사이의 거리, 또는 두 지점 사이의 교통량 등을 나타내는 숫자와 같습니다.

문제는 이러한 지도들이 매우 거대해질 수 있다는 점입니다. 모든 연결의 아주 작은 세부 사항까지 포함하여 전체 지도를 보내는 것은 많은 공간과 시간을 차지합니다. 과학자들은 지도의 '형태'(점들과 그 점들을 연결하는 선들)를 완벽하게 보내는 방법은 오래전부터 알고 있었지만, 그 선들에 적힌 '숫자'(가중치)를 보내는 것은 까다로운 일입니다. 만약 이 숫자들을 너무 많이 줄이려 한다면, 중요한 세부 정보를 실수로 지워버리거나 지도의 형태를 바꾸어 그림을 망칠 수도 있기 때문입니다. 핵심적인 질문은 이것입니다: 지도의 진정한 구조를 잃어버리거나 숫자를 너무 뭉툭하게 만들어 쓸모없게 만들지 않으면서, 어떻게 하면 선 위의 숫자들을 압축할 수 있을까?

"변환 코딩을 이용한 가중치 그래프 인접 행렬의 손실 압축(Lossy compression of weighted graph adjacency matrices by transform coding)"이라는 제목의 이 논문은 이 문제를 해결하기 위한 영리한 새로운 방법을 제안합니다. 저자인 야나기야 켄타(Kisa Yanagiya)와 그의 팀은 두 단계 전략을 제시합니다. 첫째, 지도의 뼈대(연결 구조)를 오류 없이 완벽하게 보냅니다. 둘째, 선 위의 숫자들을 무작위 목록이 아니라 지도 위를 흐르는 하나의 '패턴'으로 취급합니다. 이 숫자들이 서로 이웃한 숫자들과 어떻게 연관되어 있는지 파악함으로써, 이들은 숫자를 훨씬 더 작은 파일로 압축할 수 있습니다.

"선 그래프(Line Graph)" 마술

이들의 해결책을 이해하기 위해, 당신이 편지를 배달하는 집배원이라고 상상해 보세요. 보통 당신은 주소(노드) 목록을 보고 각 집을 찾아갑니다. 하지만 이 논문에서 저자들은 집을 보는 대신 '도로(edge)'를 보기로 결정합니다. 그들은 지도를 뒤집어 생각합니다.

그들의 방법에서는 모든 도로(엣지)가 새로운 가상의 지도인 선 그래프(Line Graph) 내에서 하나의 "집(노드)"이 됩니다. 만약 원래의 도시에서 두 도로가 한 교차로에서 만난다면, 그 두 "도로-집"은 새로운 지도에서 서로 연결됩니다. 갑자기, 도로 위의 숫자들(가중치)은 이 새로운 '도로의 지도'를 통해 흐르는 하나의 신호가 됩니다.

이것이 왜 도움이 될까요? 현실 세계에서 인접한 도로들은 종1종 유사한 교통량이나 거리를 가지는 경우가 많기 때문입니다. 이 새로운 "선 그래프" 안에서, 이러한 유사한 숫자들은 바로 옆에 위치하게 되어 매끄럽게 흐르는 패턴을 만들어냅니다. 저자들은 만약 패턴이 매끄럽다면, 무작위적인 숫자 목록보다 훨씬 더 잘 압축할 수 있다는 사실을 깨달았습니다. 이것은 마치 잔잔한 푸른 하늘 사진(색상이 천천히 변하므로 압축이 쉬움)을 압축하는 것과 TV의 노이즈 화면(픽셀이 무작위로 변하므로 어려움)을 압축하는 것의 차이와 같습니다.

압축 기계

연구팀은 고성로한 체(sieve)처럼 작동하는 압축 기계를 만들었습니다. 그들은 도로 숫자 목록을 **그래프 필터 뱅크(Graph Filter Bank)**라고 불리는 특수 필터에 통과시킵니다. 이 필터를 "매끄럽고 천천히 변하는" 데이터와 "들쭉날쭉하고 빠르게 변하는" 데이터를 분리하는 일련의 체라고 생각하면 됩니다.

데이터가 매끄럽기 때문에(선 그래프 덕분에), 중요한 정보의 대부분은 압축하기 쉬운 "매끄러운" 더미에 모이게 됩니다. 보통 노이즈나 중요하지 않은 세부 사항인 "들쭉날쭉한" 부분들은 훨씬 더 작게 짓눌러 압축될 수 있습니다. 필터링을 거친 후, 그들은 표준 기술을 사용하여 숫자를 더욱 축소(양자화)하고 촘촘하게 패킹(엔트로피 코딩)합니다.

수신 측에서는 친구가 완벽한 지도 뼈대와 압축된 숫자를 받게 됩니다. 그들은 숫자를 다시 도로 위에 얹습니다. 그러면 짠! 원래의 지도와 거의 똑같은 복사본을 갖게 되지만, 이를 보내는 데는 훨씬 적은 공간이 들었습니다.

실제로 효과가 있을까?

저자들은 단순히 이 방법이 작동할 것이라고 추측만 한 것이 아니라, 다양한 지도를 통해 테스트했습니다. 그들은 500개의 점이 있는 가짜 지도와 시카고, 상하이, 상파울루와 같은 실제 도시의 지도, 그리고 칠레의 전력망 지도를 만들었습니다.

테스트에서 그들은 자신들의 방식이 데이터를 줄이는 다른 방법들과 비교했을 때 어떤지 검증했습니다. 그 결과, 그들의 방식이 일관되게 더 우수하다는 것을 발견했습니다. 동일한 크기로 데이터를 압축하려고 했을 때, 그들의 버전은 다른 방식보다 훨씬 더 정확하게 숫자를 유지했습니다. 도로 위의 숫자들이 매우 무질서하고 예측하기 어려운 경우에도, 그들의 방법은 다른 방법들보다 더 잘 버텨냈습니다.

또한 그들은 도로의 "매끄러움"에 대해 흥식한 사실을 발견했습니다. 그들은 이웃한 도로들 사이에서 숫자가 얼마나 변하는지를 측정하는 특별한 점수를 만들었습니다. 숫자가 많이 변하면(높은 변동성) 지도는 압축하기 어려웠고, 숫자가 비슷하면(매끄러우면) 쉬웠습니다. 그들은 이 점수가 압축 성능을 정확하게 예측할 수 있다는 것을 발견했습니다. 즉, 지도를 압축하기도 전에 이 점수를 보고 훌륭한 결과가 나올지 아니면 엉망인 결과가 나올지 미리 알 수 있다는 것입니다.

이것이 왜 중요한가

이 논문은 기존의 많은 방법이 도로를 삭제하거나 병합하여 지도의 형태를 단순화하려고 시도한다고 주장합니다. 저자들은 이렇게 말합니다. "아니요, 모양은 정확히 그대로 유지하세요!" 지도의 뼈대를 완벽하게 보존하고 숫자만을 압축함으로써, 그들은 나중에 이 지도를 사용하는 어떤 컴퓨터 프로그램(예: 교통량을 예측하거나 전력 흐름을 분석하는 프로그램)도 사라진 도로 나 끊어진 연결 때문에 혼란을 겪지 않도록 보장합니다.

또한 그들은 이 방법이 실제 작업에 도움이 된다는 것을 보여주었습니다. 그들이 압축된 지도를 사용하여 노이즈가 섞인 교통 데이터를 정제했을 때, 그 결과는 다른 압축 방법을 사용했을 때보다 원래의 완벽한 데이터에 훨씬 더 가까웠습니다. 이는 지도의 구조를 온전히 유지하면서 숫자를 줄이는 것이 승리하는 전략임을 시사합니다.

요약하자면, 이 논문은 복잡한 네트워크를 담아내는 더 스마트하고 새로운 방법을 제시합니다. 도로를 집으로 바꾸고 매끄러운 패턴을 찾아냄으로써, 저자들은 중요한 세부 사항을 잃지 않고도 거대한 지도를 보낼 수 있는 방법을 찾아냈습니다. 이것은 마치 거대하고 정교한 종이접기 학을 너무나 완벽하게 접어서 주머니에 쏙 들어가게 만들었지만, 펼쳤을 때는 모든 주름이 정확한 위치에 있게 만드는 것과 같습니다.