The Hunt For the Missing Data Type에 대해 많은 반응을 받았다. 그중 가장 흥미로운 것들을 아래에 소개한다.

반응 블로그

• The “missing” graph datatype already exists. It was invented in the ‘70s — datalog에 관한 글이다.

이메일과 댓글

인용 부호 안의 내용은 모두 원문 그대로이다.

GraphBLAS

제 이름은 Michel Pelletier이며, GraphBLAS API 표준과 Python 바인딩의 기여자 중 한 명입니다.

블로그 글이 HN 메인에 오른 것을 축하드립니다. 질문에 도움이 될 만한 정보를 댓글로 남기긴 했는데, 토론에 묻혀 잘 보이지 않더군요. 메일로 연락해도 된다고 하시길래 직접 보내드리기로 했습니다.

당신이 찾고 있는 그래프 자료형은 이미 언급하신 행렬입니다. 블로그 글에서 인접 행렬을 언급하긴 했지만, 거기서는 그래프 자체가 아니라 저장 형식으로만 다루고 있습니다. 하지만 그래프와 행렬은 개념적으로나 대수적으로 동형입니다. 모든 그래프, 나아가 모든 복합 자료구조는 수학적으로 행렬이며, 모든 행렬은 그래프입니다. 하이퍼그래프와 멀티그래프는 “Incidence Matrices”로 표현하는데, 이는 두 개의 직사각형 행렬을 이용해 노드-간선, 간선-노드 인접성을 나타내는 방식입니다.

MIT 링컨 연구소 슈퍼컴퓨팅 센터 소장인 Jeremy Kepner 박사를 중심으로 한 대규모 연구진이 쓴, 입문용으로 정말 훌륭한 논문은 다음과 같습니다:

https://arxiv.org/pdf/1606.05790.pdf

그래프를 행렬로 생각할 때 컴퓨터에서 생기는 문제는 대부분의 그래프가 희소(sparse)한 반면, 대부분의 행렬 라이브러리(예: numpy)는 밀집(dense) 행렬을 다룬다는 점입니다. 밀집 행렬에서는 대부분의 공간이 0으로 채워지기 때문에 인접 행렬을 쓰는 비용이 매우 커집니다. 이는 극도로 비효율적이며 폰 노이만 아키텍처 특유의 캐시 계층 구조를 제대로 활용하지 못하게 합니다. 이 두 세계는 아직 완전히 융합되지 않았습니다.

다만 효율적인 희소 행렬 연산, 즉 희소 그래프 분석에 대한 연구와 개발은 활발히 이루어지고 있습니다. 서로 달라 보이지만 사실 이 둘은 같은 것입니다. 행렬 곱셈은 그래프에서의 너비 우선 탐색 한 단계와 같습니다. 이것이 두 개념이 동형인 이유 중 하나입니다. 많은 머신러닝과 인공지능 연구가 희소 행렬과 그래프를 함께 다루며, 두 패러다임의 성능을 개선하는 연구는 상당 부분 통합되어 있습니다.

이 주제에 대해 자주 받는 질문은 “왜”입니다. 왜 노드와 간선을 순회하는 함수를 쓰는 대신 선형대수 공식을 쓰느냐는 것이죠. 가장 중요한 이유 중 하나는 거대한 그래프에서의 병렬화입니다. 그래프가 정말로 커져서 간선이 수십억, 수조 개에 이르면 알고리즘의 작업을 효율적으로 나눠야 합니다. 어떻게 나눌 건가요? 간선마다 fork를 할 건가요? 스레드 풀을 쓸 건가요? 작업을 어떻게 스케줄링하고 그래프를 효율적으로 분할할 건가요? 이제 이걸 CUDA에서 해보라고 하면, 가장 뛰어난 프로그래머에게도 거의 불가능한 문제가 됩니다.

GraphBLAS에서는 그래프 연산이 선형대수 공식, 즉 일련의 행렬 곱셈으로 분해됩니다. Ax = b 같은 식만 쓰면, 하부 라이브러리가 특정 대상 아키텍처에서 작업을 가장 효율적으로 수행하는 방법을 알아서 찾아냅니다. 크롬북에서 돌리든 슈퍼컴퓨터에서 돌리든 코드는 바뀌지 않고, 더 큰 그래프를 처리할 수 있는 기계의 용량만 달라집니다. GraphBLAS는 기반 아키텍처뿐만 아니라 입력하는 문제의 형태와 유형에 따라 “JIT” 컴파일될 수 있는 언어라고 생각하면 됩니다. 선형대수(LA)는 수학, 과학, 공학의 공통 언어이므로, 이 기법은 기존의 많은 작업에 자연스럽게 적용될 수 있습니다.

그래서 이 내용을 전해드리고 싶었습니다. 앞으로의 탐구에 행운을 빕니다. 더 알고 싶으시면 언제든 대화 나눌 준비가 되어 있습니다. C API 위원회 위원으로서 이런 주제를 알리는 것도 제 일의 일부이고, 즐겁게 하고 있습니다.

감사합니다!

Gremlin

이 글의 초안에서는 Apache의 그래프 컴퓨팅 프레임워크인 TinkerPop과 그 질의 언어인 Gremlin에 대해 다루었다. 최종본에서는 그 부분을 뺐는데, 여러 독자가 그 내용이 빠진 것을 알아챘다. 그중 한 분의 답변은 다음과 같다.

Cypher는 언급하셨지만 Neo4j/TinkerPop용으로 표현력이 뛰어난 그래프 질의 언어인 Gremlin에 대해서는 다루지 않으셨더군요:

https://tinkerpop.apache.org/

이 언어는 ShiftLeft에 인수된 Joern SAST 도구를 구동하는 데 쓰였고, 금융권에서도 많이 사용되는 것으로 알고 있습니다.

저는 마지막으로 Maven의 모든 소프트웨어 패키지와 그 상호 의존성을 그래프로 만드는 데 사용했습니다.

프로그래밍 언어 바인딩도 잘 되어 있습니다. 저는 Python Gremlin을 사용해 익숙한 스크립트 언어로 다룰 수 있었는데, 기본 REPL/스크립트가 제가 그다지 익숙하지 않은 Groovy였기 때문입니다.

Gremlin으로 그래프를 질의하는 작업과 Python에서 일반적인 명령형 스크립팅을 번갈아 가며 하고, 그 결과로 다시 질의를 이어갈 수 있었습니다. 꽤 자연스럽게 느껴졌습니다.

전체 그래프 알고리즘 지원이 어느 정도인지는 잘 모르겠습니다. 저는 항상 중심성 같은 전체 그래프 통계보다는 탐색 기반 질의에 관심이 있었거든요.

루빅스 큐브

CodeProject 뉴스레터에 링크되어 있어 그래프용 소프트웨어 라이브러리에 대한 글을 보게 되었습니다. 정말 훌륭한 글이었습니다. 글을 쓰실 때 자문을 구하신 분들과 같은 수준은 아니지만, 그래도 그래프용 범용 소프트웨어 라이브러리를 만드는 어려움에 대한 사례를 하나 더 보태고 싶었습니다. 저는 수년간 컴퓨터를 이용해 루빅스 큐브의 수학을 연구해 온 아주 비공식적인 모임의 일원입니다.

루빅스 큐브의 바탕이 되는 수학은 군론(group theory)이라고 하며, 군을 가지고 할 수 있는 일 중 하나는 케일리 그래프(Cayley graph)라는 그래프로 그 구조를 시각화하는 것입니다. 잘난 체하는 구글은 이를 다음과 같이 설명합니다: “케일리 그래프는 군의 추상적인 구조를 그래프 형태로 표현함으로써 쉽게 시각화하는 데 자주 사용된다. 군 G의 크기나 생성자 수 같은 속성은 G를 케일리 그래프로 표현했을 때 훨씬 쉽게 살펴볼 수 있다.” 특히, 가능한 모든 루빅스 큐브 배치는 케일리 그래프의 노드로 표현할 수 있으며, 인접한 노드는 정확히 한 번의 움직임으로 도달할 수 있는 배치들이다. 글에서 15 퍼즐을 언급하셨는데, 마침 루빅스 큐브 연구자 중 한 명이 15 퍼즐을 위한 완전하고 매우 빠른 솔버를 작성한 바 있다. 그리고 15 퍼즐의 크기는 루빅스 큐브의 케일리 그래프 크기에 비하면 조족지혈에 불과하다는 사실도 밝혀졌다.

어쨌든 저는 1985년부터 루빅스 큐브를 연구하기 위해 코드를 작성해 왔다. 이는 단순히 루빅스 큐브를 “푸는” 것이 목적이 아닌데, 그건 사실 꽤 쉽다. 오히려 거의 10^20에 달하는 각 배치마다 큐브를 푸는 데 필요한 최소 이동 횟수를 결정하는 것이 목적이다. 이 문제는 단지 규모가 너무 커서 아직 풀리지 않았다. 한 번의 움직임을 무엇으로 세느냐에 따라 모든 배치가 20수 혹은 26수 안에 풀린다는 것은 밝혀졌다. 하지만 이는 가능한 모든 배치에 대해 최소 횟수의 해법을 찾는 것과는 같은 일이 아니다.

어쨌든 많은 경험을 통해, 이 문제를 실질적으로 다루려면 루빅스 큐브에 매우 특화된 자료구조를 직접 개발해야 한다는 것을 알게 되었다. 핵심 문제는 (여기서 당신의 글을 인용하자면) Performance Is Too Important라는 점이다. 필요한 기능을 해주는 라이브러리를 찾을 수 없어서 직접 만들었다.

훌륭한 글 감사합니다,

Jerry

“20수 혹은 26수”가 무엇을 의미하는지, 그리고 그가 사용하는 자료구조에 대해 더 자세히 공유해 줄 수 있는지 물었다. 그의 답변은 다음과 같다:

짐작하신 대로, 180도 회전 한 번을 한 수로 칠지 두 수로 칠지가 ‘한 수’를 무엇으로 셀지에 대한 대표적인 예입니다. 90도 회전만 한 수로 치면 이를 쿼터 턴 지표(quarter turn metric)라고 하며, 이 지표에서는 모든 배치가 26수 안에 풀립니다. 90도 회전이든 180도 회전이든 한 수로 치면 이를 페이스 턴 지표(face turn metric)라고 하며, 이 지표에서는 모든 배치가 20수 안에 풀립니다. 하지만 한 수를 세는 방법은 이 외에도 여러 가지가 있습니다. 루빅스 큐브는 어느 방향으로든 세 개의 층이 있습니다. 보통은 윗면이나 아랫면 같은 바깥쪽 층의 움직임만 한 수로 치고, 윗면과 아랫면 사이의 중간층이나 오른쪽과 왼쪽 사이의 중간층은 세지 않습니다. 하지만 때로는 그 중간층의 움직임을 한 수로 세는 것도 흥미롭습니다. 또 다른 변형은 축이 고장 난 문제(stuck axle problem)로, 한 축이 고장 났다고 가정하는 것입니다. 예를 들어 윗면은 움직이지 않고 큐브의 나머지 다섯 면의 층만 움직이는 식입니다. 이 변형에서도 모든 가능한 배치에 도달할 수는 있지만, 케일리 그래프는 어느 축도 고장 나지 않았을 때와 같은 대칭성을 갖지 않습니다. 또한 축이 고장 난 큐브를 푸는 데는 표준적인 20수나 26수보다 훨씬 더 많은 수가 필요할 수 있습니다.

루빅스 큐브를 위한 표준 자료구조가 있다고 생각하지 않습니다. 큐브를 연구하는 사람마다 각자 자신만의 자료구조를 가지고 있습니다. 다만 큐브를 충실히 표현하는 자료구조라면 서로 어느 정도 동형이어야 한다는 것은 자명합니다. 큰 구분 중 하나는 자료구조가 위치(position)만으로 이루어져 있는지, 아니면 위치와 움직임(move)을 모두 포함하는지입니다. 예를 들어 앞면을 시계 방향으로 90도씩 두 번 연속으로 돌린 결과는 앞면을 반시계 방향으로 90도씩 두 번 연속으로 돌린 결과와 같은 배치가 됩니다. 케일리 그래프에서는 이런 움직임 수열을 계속 이어가면 루프가 됩니다. 그 루프는 네 수짜리 사이클(4-cycle)입니다. 그렇다면 움직임과 위치를 함께 저장할 것인가, 아니면 위치만 저장할 것인가?

다른 사람들의 자료구조가 이런 문제를 어떻게 처리하는지는 정말 잘 모릅니다. 제 경우에는 케일리 그래프 전체를 명시적으로 저장하지 않습니다. 대신 위치들을 저장하고, 각 위치마다 그 위치에서 가능한 각 움직임에 대해 그 움직임이 풀린 상태에서 더 멀어지는지 아니면 더 가까워지는지를 나타내는 1비트씩을 저장합니다. 쿼터 턴 지표에서는 각 위치마다 이런 비트가 12개, 페이스 턴 지표에서는 18개가 있습니다. 그 비트들이 암시적으로 케일리 그래프를 정의하지만, 저는 그래프를 명시적으로 저장하지는 않습니다. 이 문제를 연구하는 다른 사람들은 표준 움직임 수열(canonical sequences)을 사용한다고 이야기합니다. 예를 들어 앞면을 시계 방향으로 두 번 연속 돌리는 것은 허용하지만 반시계 방향으로 두 번 연속 돌리는 것은 허용하지 않는 식입니다. 저도 비트를 이용해 비슷하지만 완전히 같지는 않은 방식을 쓰고 있습니다.

또 다른 문제는 트리 구조가 필요했다는 점인데, 트리는 그래프의 특수한 경우로 볼 수 있습니다. 즉, 트리란 하나의 노드를 루트 노드로 지정하고 그래프에 루프가 없는 그래프일 뿐입니다. 저는 직접 트리 구조를 만들어야 했습니다. 제가 필요로 했던 트리 구조는 다음과 같이 생겨납니다. 표준 루빅스 큐브에는 54개의 색 스티커가 있습니다. 표준 수학적 모델에서는 각 면의 중앙 스티커는 움직이지 않으므로 움직이는 스티커는 48개가 남습니다. 그 48개 중 24개는 3x3 면의 모서리에 있고 24개는 모서리(엣지)에 있습니다. 코너 스티커와 엣지 스티커는 서로 겹치지 않으므로, 저는 각 코너 스티커에 A부터 X까지의 문자를, 각 엣지 스티커에도 A부터 X까지의 문자를 붙여 큐브 배치를 표현합니다. 그러면 각 배치는 24개의 문자로 이루어진 단어가 두 개인 순서쌍이 되며, 각 단 words에는 각 문자가 정확히 한 번씩만 나타납니다.

그렇다면 왜 트리가 필요할까요? 이 단어들을 매우 빠르게 찾을 수 있어야 하기 때문입니다. 맞춤법 검사 사전에서 단어를 매우 빠르게 찾는 것과 같습니다. 명목상 트리의 각 노드는 트리의 다른 노드를 가리키는 24개의 포인터가 필요합니다. 그런데 실제 맞춤법 사전의 실제 단어와 달리, 각 단어에서는 각 문자가 단 한 번만 나타날 수 있습니다. 그래서 트리의 잎 노드 쪽으로 갈수록 각 노드는 대부분 null 포인터로 이루어지게 되며, 이는 매우 소중한 메모리를 크게 낭비하는 일입니다. 그래서 저는 빠른 검색을 위해 위치 저장을 수용할 수 있는 트리 구조를 직접 만들어야 했습니다. 표준 라이브러리 루틴 중에는 충분히 빠르고 메모리를 절약하는 것이 없었습니다.

그래서 본질적으로 저는 두 개의 자료구조를 겹쳐서 가지고 있습니다. 하나는 비트 스위치를 이용해 큐브의 케일리 그래프를 정의하고, 다른 하나는 맞춤법 검사 사전 스타일의 트리를 이용해 특정 위치를 매우 빠르게 찾습니다. 그리고 트리는 그저 그래프의 특수한 경우일 뿐입니다.

질문에 대한 답이 되었는지 모르겠지만, 도움이 되었길 바랍니다.

Jerry

그래프와 지식 데이터베이스

Hillel — 그래프 표현에 대한 탐구를 명쾌한 설명과 함께 공유해 주셔서 감사합니다. 왜 뚜렷한 승자가 없는지에 대한 설명도 잘 보았습니다. 당신이 언급한 문제들이 실행 가능한 대안을 배제할 만큼 그리 크지는 않은지 궁금합니다.

저는 우선 Smalltalk 프로그래머로서, 그리고 Wiki의 창시자로서 이 문제에 접근합니다. 둘 다 조각조각 조립되어 지속적으로 사용되는 그래프와 유사한 구조를 가지고 있습니다. 제가 최근에 만든 위키 구현을 둘러싼 작은 커뮤니티는 문단, 이미지, 개요, 표와 함께 페이지에 그래프를 추가하려는 동기가 매우 강합니다. 우리는 이를 Dot을 마크업으로 사용하는 Graphviz로 부분적으로 해결했습니다. 하지만 이는 yaml이나 csv 파일에서 얻는 것과 같은 연산과 공유로 이어지지는 않습니다.

우리는 최근에 (예를 들어 JavaScript에서) 그래프를 노드와 관계(rels) 배열을 가진 객체로 표현하는 방식을 채택했습니다. 빈 그래프는 다음과 같습니다:

{nodes:[], rels:[]}

노드와 관계 자체는 타입을 나타내는 문자열과 속성을 위한 추가 객체, 그리고 이들을 서로 연결하는 일부 관리되는 인덱스를 가진 객체입니다. 이렇게 하면 (루프가 없는) JSON으로 편리하게 직렬화되며, 이 형식은 널리 쓰이고 킬로바이트 단위로 측정되는 그래프에는 충분합니다.

이 그래프들은 우리가 상당한 경험을 가진 Neo4j 객체로 쉽게 변환됩니다. 더 자주 우리는 위키 자체 외에 별도의 데이터베이스를 유지하지 않습니다. 비록 소규모 Cypher 인터프리터를 만들기도 했지만 그다지 유용하다고 느끼지는 못했습니다. 우리는 놀랍게도 하나의 거대한 Neo4j 그래프를 만들고 필요한 그래프를 질의로 추출하기보다, 당면한 문제를 해결하는 하나의 그래프로 많은 작은 그래프들을 병합할 가능성이 더 높다는 것을 발견했습니다.

최근에는 문제 공간의 횡단 관심사(cross-cutting concerns)에 기반해 문제를 “관점(aspects)”으로 나누게 되었습니다. 이런 그래프가 수십 개, 심지어 수백 개가 될 수도 있습니다. 우리는 이를 위키를 탐색하듯 탐색하는데, 위키 링크에 해당하는 것은 아직 포함되지 않은 그래프에 동일한 노드가 나타나는 것을 인식하는 데서 옵니다. 이는 “추천” 과정이며, 질의는 추천을 선택하고 해제하는 것으로 대체되고, 진행 중인 작업은 브라우저에서 실행되는 Graphviz로 즉시 렌더링됩니다.

원래 이 이메일에서 우리의 그래프 추상화에 대해 더 완전한 설명으로 시작하려 했지만, 우리의 경험이 흥미로울지 확신이 서지 않아 물러섰습니다. 이 방식이 유용하게 쓰인 애플리케이션, 보통 커뮤니티 내 협업 문제를 다루는 사례에 대해서도 설명할 수 있습니다.

관심사가 겹친다고 생각하시면 연락 나누고 싶습니다.

감사합니다 — Ward

그의 코드는 문서 및 예제와 함께 여기에서 볼 수 있다. 후속 이메일:

Hillel — 우리는 더 큰 문제의 관점을 나타내는 작은 그래프들을 찾고 있습니다. 유럽 패턴 컨퍼런스에 제출될 논문을 읽어 달라는 요청을 받았을 때, 아주 꼼꼼히 읽으며 패턴 안의 모든 “관계적” 문장을 매핑한 사례가 있습니다. 다음은 관점들 사이의 예상치 못한 겹침을 노란색으로 표시한 그림입니다.

이 특정 그래프 뷰어는 굴곡진 역사를 가지고 있습니다. 위키 페이지의 스크립트로 시작해, 온라인 협업을 위해 Croquet 위에서 독립형 웹 앱으로 추출되었다가, 다시 위키로 돌아오는 1인용 “솔로” 애플리케이션이 되었습니다. 아직 그 자체로 자명하지는 않습니다. 하지만 이런 종류의 탐구에 관심을 공유하는 공동 검토자와 협력한 위키 페이지의 마지막 문단에 있는 “open” 링크로 열어볼 수 있습니다. http://ward.dojo.fed.wiki/aspects-of-pattern-relations.html

서로 다른 “관점” 가능성을 보여주는 비슷한 프로젝트 두 가지가 더 있습니다: 1년 치 최근 변경 사항을 잘게 나누는 작업, 그리고 검색 엔진 소스 코드를 노드-관계 주석으로 달고 GitHub Actions로 그래프 파일로 추출하는 작업입니다.