사라진 데이터 타입을 찾는 추적

 (hillelwayne.com)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 그래프는 의존성, 웹 링크, 모델 체커의 상태 공간, 관계형 DB의 외래 키처럼 소프트웨어 곳곳에 있지만, 주류 프로그래밍 언어에는 내장 타입이나 표준 라이브러리 지원이 거의 없음
  • 내장 그래프 타입을 만들기 어려운 첫 이유는 방향·무방향, 단순·멀티, 하이퍼그래프처럼 그래프 종류가 많고, 특정 성질이 알고리듬 선택과 성능을 크게 바꾸기 때문임
  • 엣지 리스트, 인접 리스트, 인접 행렬, 참조 구조체 등 표현 방식마다 메모리와 조회 성능이 달라 하나의 범용 표현으로 모든 사용 사례를 만족시키기 어려움
  • 그래프 알고리듬은 구현이 어렵고 큰 입력에서 실행되는 경우가 많아, Nosey Parker와 Gecode 사례처럼 문제 맞춤형 표현과 순회가 범용 라이브러리보다 중요해질 수 있음
  • 표준 라이브러리에 그래프가 드문 이유는 타입·표현·알고리듬·성능 트레이드오프와 유지보수 부담이 크기 때문이며, 서드파티 라이브러리도 제한적이거나 느릴 수 있음

그래프는 흔하지만 언어 지원은 부족함

  • 그래프는 노드와 엣지로 구성되며, 노드와 엣지에는 데이터가 들어갈 수 있음
  • 소프트웨어 엔지니어링에서 그래프는 여러 형태로 등장함
    • 패키지 의존성과 모듈 import는 방향 그래프를 이룸
    • 인터넷은 웹페이지 사이 링크 그래프임
    • 모델 체커는 가능한 모든 설정의 상태 공간을 탐색하며, 노드는 상태이고 엣지는 유효한 전이임
    • 관계형 데이터베이스는 레코드를 노드, 외래 키를 엣지로 볼 수 있음
    • 그래프는 연결 리스트, 이진 트리, 해시 테이블의 일반화로 볼 수 있음
  • 비즈니스 로직에서도 논문 인용 관계, 교통망 경로, 소셜 네트워크 연결 같은 그래프가 자주 등장함
  • 그래프는 자주 필요하지만, 주류 언어 대부분은 그래프를 내장 타입으로 제공하지 않고 표준 라이브러리에 포함한 경우도 드묾
  • 많은 생태계에는 견고한 서드파티 그래프 라이브러리도 부족해 직접 구현해야 하는 경우가 많음

그래프 타입 설계에는 선택지가 너무 많음

  • 그래프에는 방향 그래프와 무방향 그래프 외에도 여러 변형이 있음
    • 두 노드 사이 엣지가 최대 하나인 단순 그래프와 여러 엣지를 허용하는 멀티그래프
    • 하나의 엣지가 3개 이상의 노드를 연결하는 하이퍼그래프
    • 엣지가 다른 엣지를 가리킬 수 있는 우버그래프
  • 각 변형마다 추가 설계 결정이 따라붙음
    • 엣지에도 ID를 줄지, 노드에만 줄지 정해야 함
    • 노드와 엣지에 어떤 데이터를 저장할지도 결정해야 함
  • 모든 그래프를 “방향 하이퍼우버멀티그래프” 같은 범용 타입으로 제공하고 사용자가 제한하게 할 수도 있지만, 곧바로 두 가지 문제가 생김
    • 연산 결과가 단일 값인지 리스트인지처럼 인터페이스가 달라짐
    • 특수한 그래프 성질을 활용하지 못하면 알고리듬 성능이 나빠짐
  • 예를 들어 maximum weight matching은 그래프가 이분 그래프임을 알면 빠른 알고리듬을 쓸 수 있지만, 일반 그래프에는 더 느리고 범용적인 알고리듬이 필요함
  • 어떤 문제 P, 그래프 G, 알고리듬 A·B·C가 있을 때 어떤 알고리듬을 실행할지 고르는 알고리듬 디스패치 문제도 생김
  • 완벽한 그래프 라이브러리는 많은 그래프 종류를 지원해야 하지만, 그만큼 실제 사용자가 원하는 알고리듬 구현에 쓸 시간이 줄어듦
  • 그래프 알고리듬은 구현 난도가 높음
    • Python 창시자가 작성한 find_shortest_path 알고리듬은 이후 다섯 차례 수정됨
    • Nicole은 비교한 PageRank 구현이 모두 틀렸다고 말함
    • NetworkX는 약 500개의 그래프 알고리듬을 제공하며, 알고리듬 코드만 거의 60,000줄임
    • Python 표준 라이브러리 전체는 약 300개 패키지, 600,000줄 미만임
  • 표준 라이브러리 관리자는 어떤 그래프 타입, 어떤 위상 특수 처리, 어떤 알고리듬을 포함할지 결정해야 하므로 유지보수 부담이 큼
  • Python도 “batteries included”로 알려져 있지만 PEP 594로 20개 표준 라이브러리 모듈을 제거하는 흐름에 있음

그래프 표현 방식도 하나로 정하기 어려움

  • 가장 단순한 방향 그래프만 생각해도 내부 표현은 여러 가지가 가능함
    • 엣지 리스트: [[a, b], [b, c], [c, a], [c, b]]
    • 인접 리스트: [[b], [c], [a, b]]
    • 인접 행렬: [0 1 0; 0 0 1; 1 1 0]
    • 서로 참조하는 구조체 집합
  • 표현 방식에 따라 연산 성능이 달라짐
    • 노드 100개, 엣지 200개인 그래프를 인접 행렬로 표현하면 100×100 행렬에 1은 200개, 0은 9,800개가 들어감
    • 같은 그래프를 엣지 리스트로 표현하면 노드 쌍 200개만 필요함
    • 언어와 최적화 수준에 따라 메모리 차이가 20배 이상 날 수 있음
  • 반대로 노드 100개, 엣지 8,000개인 그래프에서 노드 0과 93 사이 엣지를 찾는 경우는 결과가 달라짐
    • 인접 행렬은 graph[0][93]로 O(1) 조회 가능함
    • 엣지 리스트는 8,000개 엣지를 순회해야 하므로 O(|edge|) 시간이 걸림
  • 엣지가 적은 그래프는 희소 그래프이고, 거의 모든 엣지가 있는 그래프는 밀집 그래프임
  • 외부 데이터에서 그래프를 구성하는 프로그램은 처음에는 희소 그래프였다가 나중에 밀집 그래프가 될 수 있어, 내부 표현에 “항상 좋은 선택”은 없음
  • 노드 데이터, 엣지 데이터, 여러 종류의 노드와 엣지를 지원하면 구현 복잡도는 더 커짐
  • 서드파티 라이브러리는 대체로 두 방향 중 하나를 택함
    • 모든 사용 사례를 포괄하는 풍부한 단일 타입을 제공하되 효율성을 희생함
    • 표현 방식별 그래프 타입을 따로 제공하고, 노드·엣지 데이터 관리는 사용자에게 맡김

NetworkX와 Petgraph가 보여주는 트레이드오프

  • NetworkX는 노드와 엣지에 임의 데이터를 붙일 수 있도록 그래프를 dict의 dict의 dict 구조로 저장함
  • 다른 표현으로 변환하는 함수는 제공하지만, 해당 표현 자체로 직접 작업하는 방식은 제공하지 않음
  • Rust의 대표 그래프 라이브러리 Petgraph는 graph, graphmap, matrix_graph처럼 사용 사례별 타입을 제공함
  • Bradford는 git 저장소 전체 이력에서 secret을 찾는 보안 도구 Nosey Parker에서 Petgraph를 사용함
    • 벤치마크 그래프는 CPython이며, 250,000개 commit과 1,300,000개 object를 포함함
    • commit 노드당 엣지는 몇 개뿐이어서 인접 리스트를 선택함
  • 여러 표현을 지원하면 알고리듬 추가 비용이 커짐
    • 표현마다 별도 알고리듬을 작성하면 유지보수 부담이 3~4배로 늘어남
    • 다형 타입 위의 범용 추상화로 작성하면 성능이 낮아짐
  • 한 인터뷰이는 직접 작성한 그래프 알고리듬이 범용 알고리듬보다 20배 이상 빠를 수 있다고 추정함

성능 제약이 그래프 라이브러리의 핵심 문제임

  • 그래프 알고리듬에는 NP-complete 또는 그보다 어려운 문제가 많음
    • Karp의 21개 canonical NP-complete 문제 중 14개가 그래프 문제임
  • 그래프 문제는 매우 큰 입력에서 실행될 수 있어, 표현 방식과 구현 세부사항이 실행 가능성을 좌우함
  • Bradford는 Nosey Parker에서 각 commit마다 파일시스템 스냅샷을 재구성하기 위해 object graph를 순회해야 했음
    • Petgraph의 네 가지 그래프 walker는 해당 사용 사례에 맞게 확장되지 않았음
    • 즉석에서 “semi-novel” graph traversal algorithm을 설계했고, 메모리 사용량을 1,000분의 1로 줄임
  • Zayenz는 그래프가 너무 커서 전체를 다룰 수 없는 사례로 15 puzzle을 들음
    • 해법 탐색은 상태 공간에서 A* search를 실행하는 방식임
    • 상태 공간은 20조 개가 넘는 상태를 가짐
    • 모든 노드를 생성하면 이미 실패한 상태가 됨
  • Zayenz가 관여한 Gecode 제약 솔버의 그래프 추가 연구 프로젝트에서도, 범용 그래프 타입은 문제에 맞춘 표현 선택과 경쟁할 수 없었음
  • 그래프 데이터베이스도 복잡한 그래프 알고리듬 실행을 위해 설계됐지만 성능 문제가 남아 있음
    • Nicole에 따르면 순회 시 깊이를 제한하지 않으면 전체 그래프를 방문하게 됨
    • “3단계 밖으로 나가 경로가 있으면 찾기” 같은 깊이 탐색도 많은 데이터를 방문하게 됨
  • Nicole은 그래프 쿼리 성능 컨설팅에서 그래프 데이터베이스를 떠나는 마이그레이션을 주로 수행함
    • 한 프로젝트에서는 하나의 계산만 그대로 두고 나머지를 MapReduce 절차로 다시 작성함
    • 이해하기는 더 어려웠지만, 밤사이에 실제로 완료될 수 있었음

왜 표준 라이브러리에 그래프가 드문가

  • 광범위한 그래프 지원이 드문 이유는 여러 요인이 겹치기 때문임
    • 그래프 종류가 많음
    • 각 그래프 종류마다 표현 방식이 많음
    • 그래프 알고리듬 종류가 많음
    • 알고리듬 성능이 표현과 구현 세부사항에 민감함
    • 사람들은 매우 큰 그래프에서 매우 비싼 알고리듬을 실행함
  • 언어 표준 라이브러리는 너무 많은 설계 결정과 트레이드오프, 유지보수 부담을 떠안아야 함
  • 프로그래머가 서드파티 그래프 라이브러리를 피하는 이유도 있음
    • 라이브러리가 너무 제한적일 수 있음
    • 범용 라이브러리가 성능 요구를 만족하지 못할 수 있음
  • 그래프는 시스템 분석에는 유용하지만, 구현 단계에서는 데이터 표현과 알고리듬 선택을 직접 통제해야 하는 경우가 많음

부록: 그래프 타입을 제공하는 언어와 관련 도구

  • 그래프 질의 언어(GQL)는 그래프 데이터베이스에서 SQL에 해당하는 역할을 함
    • 널리 쓰이는 표준은 없지만, 대표적으로 SPARQL과 Neo4j의 Cypher가 있음
    • 여기서 GQL은 개발 중인 GQL 표준 언어와 혼동하지 않아야 함
  • GraphQL은 그래프 질의 언어가 아니며, 이름은 Facebook Graph Search와의 연결에서 비롯됨
  • GQL과 SQL의 주요 차이는 관계, 즉 “join”이 일급 엔티티라는 점임
    • 영화와 사람 데이터셋에서 SQL은 “출연”, “감독”, “제작” 관계를 각각 many-to-many 테이블로 구현함
    • SPARQL에서는 관계가 엣지이므로 “영화 Y에서 어떤 역할이든 맡은 사람과 그 역할”을 쉽게 질의할 수 있음
  • GQL은 엣지 반전, 합성, 추이 폐쇄 같은 엣지 조작도 지원할 수 있음
    • SPARQL은 경로 길이나 경로 중 계산, 예를 들어 두 배우를 잇는 영화 체인 수집은 제공하지 못함
    • 이를 지원하는 GQL은 훨씬 복잡해짐
  • 형식 명세 언어 Alloy는 relation 데이터 타입에 유용한 그래프 순회 primitive를 갖고 있어, 그래프 표현을 다루기가 일반 프로그래밍 언어보다 쉬움
    • 다만 이 primitive들은 라벨이 있는 엣지에 기반하며 다른 그래프 표현에는 맞지 않을 수 있음
  • Python은 2020년에 graphlib을 추가함
    • TopologicalSorter 외의 메서드는 없음
    • 그래프는 노드 dict로만 받음
    • a -> b 그래프를 {b: [a]}처럼 반대 방향 dict로 표현함
  • 2023년 기준 CPython 내부에서는 graphlib가 사용되지 않음
    • GitHub에서 graphlib를 참조하는 파일은 900개 미만임
    • 같은 해 추가된 zoneinfo는 6,000개 이상 파일에서 등장함
    • def topological_sort(라는 표현은 4,000개 파일에서 등장함
    • 직접 구현된 topological sort들은 graphlib와 다른 그래프 표현을 쓰는 경우가 많아 변환하기 어려움
  • 표준 라이브러리에 그래프 타입이 있는 다른 사례로 Erlang과 SWI-Prolog가 있음
  • “모든 것이 그래프”인 프로그래밍 언어도 있음
    • 예로 GP2와 Grape가 있음
    • 현재는 매우 학술적인 영역임
  • Mathematica, MATLAB, Maple 같은 수학 소프트웨어 언어도 어떤 형태로든 그래프 라이브러리를 갖고 있음
  • 2024년 3월 18일 업데이트로, 글에 대한 일부 댓글이 별도 페이지에 모였음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Graphviz에는 다른 프로젝트가 쓰지 않는 자체 기초 그래프 라이브러리가 있고, 장단점이 모두 있음
    그 경험을 바탕으로 우리도 전형적인 두 번째 시스템 증후군을 겪었음. 모듈식이고, 타입 안전하며, 효율적인 그래프 라이브러리를 만들고 싶었는데, 결국 “좋고 빠르고 싸게 — 둘만 고르라”의 변형이었을 가능성이 큼
    모듈식이라는 건 그래프 알고리즘 라이브러리 묶음을 독립적으로 개발하고 컴파일할 수 있기를 원했다는 뜻이고, 타입 안전하다는 건 “노드에 color 속성이 없다” 같은 런타임 오류 대신 컴파일 또는 늦어도 링크 시점에 프로그래밍 오류를 잡고 싶었다는 의미였음
    효율적이라는 건 그래프 속성 접근 비용이 C 구조체 필드 접근만큼 싸야 한다는 뜻이었고, 외부 해시 테이블을 들고 다니거나 문자열 변환을 많이 하는 방식은 원치 않았음
    이 목표들이 대가를 치를 만한지, 말이 되는지는 논쟁 가능하지만 당시 우리가 원한 건 그랬음. 연구소에 유명한 C++ 창시자들이 있었고 C++에 다시 기회를 줄 생각도 있었음
    인턴이었다가 계속 함께 일한 Gordon Woodhull은 뛰어난 프로그래머였고, 템플릿 C++로 이런 그래프 라이브러리 구현을 작성했음. 소스도 https://www.dynagraph.org/에 올라가 있음
    나머지 사람들은 그 코드가 어떻게 동작하는지 끝내 이해할 수 있을지 확신이 없어서 유명 C++ 발명가들과 코드 리뷰를 했고, 수많은 코드 화면과 침묵 끝에 “아마 동작할 것”이라는 결론이 나왔음. 그때 이미 복잡도의 절벽을 넘어섰을 수 있음을 알았음
    컴파일 타임 템플릿 오류는 한 오류가 화면 전체를 채우고 C++ 발명가만 사랑할 만한 세부사항을 쏟아냈음. 잘못은 우리에게 있었고, Gordon은 계속 밀고 나가 동적 그래프 레이아웃까지 Microsoft OLE에서도 동작하게 만들었음
    돌이켜보면 우리만의 Project Xanadu였던 셈이고, 우리가 거기에 길을 잃는 동안 Gephi(Java), NetworkX, NetworKit(Python) 같은 것들이 나왔음. Graphviz 일부를 작성한 뛰어난 소프트웨어 엔지니어 John Ellson은 본류 작업을 다시 살려냈음

    • Graphviz dot 문법을 NetworkX로 파싱해서 비싼 도구 실행 계획을 세우고, 그래프 구조 덕분에 자동 병렬화할 수 있음

  • 그래프 작업을 많이 해본 입장에서 “왜 프로그래밍 언어에는 내장 그래프 자료형이 없나?”라는 질문을 수도 없이 받았음
    이제는 “잘 만들기가 정말 어렵다”는 말을 믿어달라고만 하지 않고, 이 글처럼 더 깊이 있는 분석을 가리킬 수 있어 반가움

    • 그 질문에서 조금 웃긴 점은 대부분의 언어에 트리 자료구조조차 없다는 사실을 놓친다는 것임
      대부분의 언어가 구조적 타입으로 제공하는 건 정적 배열, 동적 배열, 연결 리스트 정도가 전부임. 이진 탐색 트리나 해시 테이블 같은 건 밑바탕 구조의 일부 능력을 숨기는 의미적 추상화이지, 순수한 구조 표현은 아님
    • 그래프는 요구사항에 따라 표현 방식이 크게 달라지는 넓은 자료구조라서, 도메인 수준에서 구현하는 편이 더 합리적이라고 생각했었음
      글의 “구현 선택지가 너무 많다”는 부분도 같은 얘기를 함. 그러다 Petgraph [0]를 보고 처음으로 범용 그래프 라이브러리를 제대로 살펴봤고 꽤 흥미로웠지만, 여전히 그래프는 도메인 수준에서 구현해 왔음
      [0] https://github.com/petgraph/petgraph
    • 반대 경험도 있었음. Tcl에서 처음 해보는 그래프 작업을 하면서 표준 라이브러리에 그래프 알고리즘이 없을 거라고 당연히 생각했는데, 알고 보니 있었고 덕분에 바퀴를 다시 만들지 않아도 됐음
      https://core.tcl-lang.org/tcllib/doc/trunk/embedded/md/tclli...
    • “잘 만들기가 정말 어렵다”보다 더 중요한 건 트레이드오프가 많다는 점임
      거의 모든 언어는 해시 맵을 제공하고, 특정 상황에서 직접 구현하면 더 빠르게 만들 수는 있어도 기본 구현이 대체로 잘 동작함. 그래프는 그렇게 하기가 어렵고, 가능하다면 여러 그래프 타입을 제공해야 할지도 모름
      덧붙이면 Java의 HashMap은 다른 대부분의 언어와 달리 부하율을 조정할 수 있다는 점이 조금 특이함
    • 아주 순진한 생각일 수 있지만, 포인터가 사실상 네이티브 그래프 타입이라고 봄
      사람들이 원하는 건 그래프 타입 자체가 아니라 그래프를 순회하는 도구에 가까움

  • 그래프는 자료구조나 자료형이라기보다 추상화라고 생각함
    근본적으로 그래프를 정의하는 데 필요한 건 정점 집합 v \in V와 함수 Neighbors(v)뿐이고, 기초적인 그래프 알고리즘 대부분에는 정말 그 정도면 충분함
    나머지는 사례별 제약임. A->B가 B->A를 의미하는지, 노드 집합이 특정 제약하에 분할 가능한지, 색이나 레이블이 있는지 같은 것들임
    더 일반화하면 하이퍼그래프까지 올라갈 수 있고, 이 경우 정점 집합과 정점 집합들의 집합만 있으면 됨. 관심사에 따라 수많은 방식으로 표현할 수 있으며, 일반 그래프는 그 특수한 경우일 뿐임
    데이터베이스 관점에서는 질의 최적화와 인덱싱 문제로 볼 수도 있음. 그래프에 어떤 질문을 던지고 싶은지에 따라 더 잘 답할 수 있는 표현 방식이 달라짐. “테이블”이라는 추상화를 표현하는 방식이 하나가 아니듯 “그래프”도 하나의 방식으로 끝나지 않음

    • 그래프가 어디에나 있는 이유는 그만큼 추상적이기 때문임
      순수한 숫자와 같은 추상화 수준에 있음. 유용한 “수치” 라이브러리가 있듯 유용한 “그래프적” 라이브러리도 있다고 말할 수는 있지만, “숫자” 라이브러리나 “그래프” 라이브러리는 별로 없음. 그런 개념은 API를 만들기엔 너무 추상적임
    • 정점 집합과 Neighbors(v)만으로도 이미 제약이 심함. 같은 이웃으로 가는 다중 간선을 허용하지 않기 때문임
    • 하이퍼그래프가 정점 집합과 정점 집합들의 집합이라면, 파일 시스템과도 조금 비슷하게 들림
      파일이 정점이고, 디렉터리가 중첩 가능한 정점 집합인 셈임

  • 핵심 장애물은 두 가지임
    단순하고 작은 그래프 문제는 벡터의 벡터로 만든 인접 리스트를 직접 짜도 충분히 쉽고, 복잡하고 거대한 그래프 문제는 풀려는 문제의 세부사항에 맞춰 그래프 구현을 맞춤 제작해야만 성능이 나옴
    그래서 어떤 언어 지원이 도움이 될지 잘 보이지 않음. 코드를 분석해서 인접 리스트, 행렬, 3차원 배열 등 무엇이 최적인지 판단하는 초영리 컴파일러 정도가 아니라면 어려움. 그런 최적화는 한동안 컴파일러에서 보기 힘들 것임
    Stroustrup이 본 현상의 또 다른 예임. 우리는 벡터 같은 작은 것과 운영체제 같은 큰 것의 코드 공유는 잘하지만, 중간 크기 문제는 잘 공유하지 못함

    • 작은 것도 정말 잘 공유한다고 보긴 어려움. 프로그래밍 언어마다 벡터 구현이 따로 있기 때문임
      한 언어 생태계 안에서는 벡터 API가 작고, 그래서 공유가 쉬운 것 같음. 운영체제는 내부 복잡도에 비해 API가 상대적으로 작고, 수치 계산 라이브러리도 마찬가지라 공유가 잘 됨
      반면 복잡한 자료구조처럼 더 많이 맞춤화하려 할수록 API가 복잡해지고 공유가 어려워짐. 결국 공유 가능성은 공유 대상의 표면적, 즉 API의 상대적 크기에 좌우되는 듯함
    • 추상 그래프 타입을 대상으로 작성된 알고리즘을 보고, 특정 알고리즘에 맞게 구현을 채워 넣어 최적화하는 일은 코드 특화 LLM의 영역에 꽤 잘 맞아 보임

  • Electric Clojure는 Clojure 자체의 s-표현식을 그래프 작성 문법으로 쓰고, 매크로로 반응형 클라이언트/서버 시스템의 데이터 흐름을 구체화함
    여기서는 풀스택 사용자 인터페이스가 사용 사례지만 아이디어는 일반화 가능함. https://github.com/hyperfiddle/electric 창업자임
    “그래프 타입은 다 어디 갔나?”에 대한 답은, 그래프 작성 DSL이 스코프, 제어 흐름, 추상화를 표현해야 하며, 그러면 사실상 평가 모델에서 해방된 프로그래밍 언어와 동형이 된다는 것이라고 봄. Python과 TypeScript에서는 완전한 프로그래밍 언어를 끼워 넣기가 꽤 어렵다
    블로그 글 “Four problems preventing visual flowchart programming from expressing web applications”도 참고할 만함
    https://www.dustingetz.com/#/page/four%20problems%20preventi...

  • 이 글은 주로 “왜 프로그래밍 언어가 그래프 알고리즘을 더 잘 지원하지 않는가”에 답하고 있으며, 일반적인 그래프 지원보다는 “빅데이터” 그래프 처리에 더 초점을 둔 것 같음
    그래프 지원 전반을 보면 “왜 OGM(Object Graph Mapper)은 ORM만큼 인기가 없나”, “왜 JSON은 널리 쓰이는데 RDF나 다른 저수준 그래프 직렬화는 그렇지 않나” 같은 더 넓은 질문도 포함됨
    결국 역사적 이유가 크다고 봄. RDF는 조금 너무 일찍 나왔고 제대로 진화하지 못했으며, 끔찍한 학술 표준과 구현 생태계를 쌓아버렸음. 여기에 그래프는 구현과 학습 곡선에서 본질적으로 조금 더 복잡해서 많은 개발자에게 잘 확장되지 않음
    글의 “Graph Querying Language” 부분에는 너무 큰 비중을 두지 않겠음. Neo4J나 SPARQL 열성 사용자가 제품을 실제로 만들어보지 않고 쓴 마케팅 문구처럼 읽히는 부분이 있음
    “모든 GQL과 SQL의 주된 차이는 조인, 즉 관계가 일급 엔티티라는 점”이라고 하지만, SQL에서도 조인은 일급 엔티티임. 심지어 JOIN이라는 키워드도 있음
    그래프 질의 언어의 더 낮은 계층으로 내려가 질의 계획을 보면 SQL 기반 질의와 의미 있는 차이가 별로 없음. GQL[0] 표준화가 SQL 확장으로 진행된다는 점이 그 증거임
    SPARQL은 정확한 경로 순회가 필요할 때는 쉽지만, 웹앱 백엔드에서 할 법한 조금 더 복잡한 일을 하려 하면 바인딩되지 않은 값과의 조인처럼 결과 집합 전체를 실수로 날려버리는 함정에 금방 부딪힘
    [0]: https://en.wikipedia.org/wiki/Graph_Query_Language

    • 자체 키워드가 있다는 건 오히려 어떤 것이 일급 객체가 아니라는 강한 증거에 가까움
      예를 들어 Haskell의 타입 클래스는 일급이 아니고, 대부분의 프로그래밍 언어에서 제어 흐름도 일급이 아님
    • JOIN, 특히 RECURSIVE 질의의 조인은 그래프 데이터베이스의 핵심이라 SQL 관계형 데이터베이스도 대체로 잘 처리함
      다만 문법적 지름길이 없을 뿐이고, 그래프 질의 언어는 본질적으로 그 지름길을 추가하는 데 초점이 있음

  • 그래프 그리기 도구도 꽤 실망스러움. 작은 그래프에서는 잘 동작하지만 노드가 500개쯤 넘어가면 출력이 완전히 이해 불가능하거나 보기 매우 어려워짐
    그래프를 계층 구조로 자동 정리하고 탐색하기 좋은 인터페이스를 제공하는 능력이 부족함. 우리 주변의 모든 것을 어느 정도 계층 구조로 보는 데 익숙하다는 점을 생각하면, 범용 그래프 자료형을 만들 때도 같은 종류의 문제가 풀려야 할 것 같음
    이런 일은 컴파일러 수준에서 구현되어 범용 그래프 알고리즘이 생성된 구조 계층에 맞게 적응해야 할 수도 있음. 여기에 정리 증명기를 더해 특정 부분 그래프가 항상 특정 구조를 가진다는 점을 확인할 수 있다면 해당 절차는 정적으로 생성하고, 나머지 상위 그래프에 대해서는 런타임에 동적으로 생성할 수 있음
    따라서 범용 그래프 그리기 문제를 푸는 사람은 이 문제를 구현할 능력이나 통찰도 갖게 될 것임

    • 그래프 그리기는 어렵다
      Graphviz류의 범용 그래프 그리기 라이브러리로, 더 많은 옵션과 제어를 제공함
      https://eclipse.dev/elk/
      Kiel University에서 ELK 개발팀이 진행한 실험
      https://github.com/kieler/KLighD
      Kieler 프로젝트 위키
      https://rtsys.informatik.uni-kiel.de/confluence/display/KIEL...
      제약 기반 그래프 그리기 라이브러리
      https://www.adaptagrams.org/
      JavaScript 구현
      https://ialab.it.monash.edu/webcola/
      흥미로운 자료로 HOLA: Human-like Orthogonal Network Layout
      https://ialab.it.monash.edu/~dwyer/papers/hola2015.pdf
      Confluent Graphs 데모는 간선을 더 읽기 쉽게 만들어줌
      https://www.aviz.fr/~bbach/confluentgraphs/
      Stress-Minimizing Orthogonal Layout of Data Flow Diagrams with Ports
      https://arxiv.org/pdf/1408.4626.pdf
      Improved Optimal and Approximate Power Graph Compression for Clearer Visualisation of Dense Graphs
      https://arxiv.org/pdf/1311.6996v1.pdf
    • 어떤 알고리즘은 이 문제를 더 잘 다루지만, 일반적인 경우 “그래프의 좋은 다이어그램을 만들라”는 건 지능 완전 문제에 가까움
      구조적으로 같은 그래프라도 두 사람이 데이터의 다른 측면을 강조하려고 완전히 다르게 렌더링할 수 있음. 이는 “범용 그래프 알고리즘”과 “범용 그래프 자료구조” 문제와도 비슷함
      그래프는 코드와 데이터의 경계에 걸쳐 있음. 예를 들어 어떤 프로그램에도 호출 그래프가 있으므로, 어떤 의미에서는 “범용 그래프 알고리즘”이 곧 계산 그 자체임
    • 이상적인 것들은 대개 트리처럼 보이지만, 현실 세계의 구조는 잘 정돈되어 있더라도 보통 방향 비순환 그래프임
      수십 개 노드만 넘어가도 평면적으로 만들거나, 교차를 적게 하고 관련 노드를 잘 묶어 거의 평면처럼 보이게 만드는 일은 보통 어렵다
    • 우리가 모든 것이 계층적이라고 믿는 환상에 익숙한 게 더 큰 문제라고 봄
      실제로는 거의 계층적이지 않은 것들을 그래프 그리기가 화해시켜야 하고, 어디까지를 계층으로 볼지 수학적으로 엄밀하게 선을 긋기가 어렵다. underlying 그래프 구조에 대해 연결성, 순환 여부, 희소성 같은 가정을 덜 할수록 이 문제는 더 나빠짐
      실무에서 그래프와 상호작용하는 UI를 만들 때는 보통 한두 단계의 메타 계층을 정하거나 강제해 클러스터링할 수 있고, 그러면 hairball 노드가 레이아웃을 망치는 영향을 줄이고 노드 수를 줄여 렌더링 성능도 개선할 수 있음. 레이아웃에는 fCOSE를 쓸 수 있고 Cytoscape.js 구현도 있음
    • 신경망 그림을 보면 대규모 그래프 시각화가 얼마나 완전히 이해하기 어려워지는지 잘 드러남

  • 핵심 관찰인 “구현 선택지가 너무 많다”는 완전히 맞지는 않다고 봄
    실제로 라이브러리는 적절한 그래프 표현을 모두 구현하고, 각 표현에서 성능이 가장 좋은 알고리즘을 제공하며, 표현 간 변환을 제공할 수 있음. 이 변환은 표현 수에 비례하고 구현도 사용도 단순해서 유지보수자와 사용자 모두에게 꽤 합리적인 부담임
    덤으로 표준 라이브러리 자료형과 관용구로부터 가져오기/내보내기 변환도 제공할 수 있음. 메모리와 변환 비용은 싸고, 사용 사례의 99%는 RAM과 CPU 양쪽에서 데이터 변환 오버헤드를 무시할 수 있을 가능성이 큼
    “Google에서 일하는 가혹한 진실은 결국 protobuf를 한 곳에서 다른 곳으로 옮기고 있다는 것이다”라는 말도 떠오름
    https://news.ycombinator.com/item?id=20132880

    • 그렇게 하면 거대한 라이브러리가 될 것 같고, 내 일에서는 쓸지 확신이 없음. 나는 그래프를 많이 쓰지만 경험은 글쓴이가 인터뷰한 사람들과 비슷함
      결국 그래프를 늘 다시 구현하게 됨. 성능이 중요하고, 내가 본 기성 그래프 라이브러리는 우리 데이터셋의 규칙성을 활용하지 못했음. 예를 들어 우리는 append-only DAG를 쓰는데 거의 모든 노드가 마지막으로 추가된 항목을 가리키는 간선 하나만 있어서 내부적으로 런 길이 부호화가 가능함
      필요한 질의를 지원하는 범용 그래프 라이브러리도 보지 못했음. 특히 큰 건 부분 그래프 diff 함수임
      게다가 맞춤 구현은 그리 일이 많지 않음. 그래프는 B-tree보다 훨씬 다시 구현하기 쉽고, 단순한 구현은 수십 줄이면 됨. 지원 알고리즘까지 포함한 고도로 최적화된 우리 라이브러리도 몇백 줄 정도임
      데이터를 표준 형식으로 내보내는 방법은 있으면 편하겠지만, 우리 사용 사례에서는 라이브러리를 끌어들이는 게 해결보다 문제를 더 늘릴 것 같음

  • 자주 떠올린 빠진 애플리케이션은 그래프용 Excel임
    표 형식 데이터용 Excel처럼 RAM에 들어갈 정도의 데이터, 즉 컴퓨터는 필요하지만 데이터센터까지는 필요 없는 규모를 다루고, 많은 알고리즘과 시각화를 “충분히 괜찮게” 구현하며, 프로그래밍 지식 없이도 쓸 수 있는 도구임
    글에서 말하듯 현실의 많은 문제는 그래프 문제인데, 왜 프로그래머만 그 문제를 풀 도구를 가져야 하는가

    • 글이 결론을 너무 빨리 낸 느낌임. 다른 많은 문제도 요구사항을 추가하면 얼마든지 복잡하고 어렵게 만들 수 있음
      그래도 대부분의 사용 사례에 충분히 맞는 자료구조와 표준 라이브러리는 존재하고, 특별히 매운 요구가 있으면 맞춤 솔루션을 만들면 됨
      글은 그래프가 너무 큰 경우가 많다고 하지만, 그래프 알고리즘을 실제로 다루는 사람들에게 물으면 그런 경험을 하기 쉬움. 대부분의 프로그래머와 사용자는 아마 정말 작은 그래프만 다룰 것임
    • 프로그래머와 수학자만 이런 문제를 그래프로 모델링한다고 봄
      일반 사용자가 무작위 현실 문제에서 그래프를 본다고는 생각하지 않음. 대기업에서 일하며 배운 건, 충분히 노력하면 모든 것은 Excel 스프레드시트가 될 수 있다는 점임
    • 정확히 요청한 것은 아니지만, https://gephi.org/는 많은 그래프 시각화 알고리즘을 구현함
      https://strlen.com/treesheets/는 트리 데이터용 Excel에 가까움
    • 글은 “많은 현실 문제가 그래프 문제”라는 점을 제대로 뒷받침하지 못함
      예를 들어 인터넷을 그래프로 모델링할 수 있다고 하지만, 맞는 말이어도 그래서 뭐가 되는지는 불명확함. 인터넷은 여러 방식으로 표현할 수 있고, 그래프로 표현하는 것이 일반적으로 유용한 공학적 함의를 가진다는 점은 분명하지 않음
      유용한 정보를 얻기 위한 이상적 표현은 오히려 임의 입력을 일관된 출력으로 매핑하는 블랙박스 행렬 인코딩 함수, 즉 신경망이라고 해도 비슷하게 설득력 있음
      Google 같은 곳에는 수십억 달러짜리 아이디어일 수도 있지만, 인터넷 전체가 많은 사람에게 그래프 문제인 것은 아니고 그래프로 표현한다고 많은 것이 해결되지는 않음
      현실 문제를 종이에 그래프로 풀고 있는 사람은 드묾. 표는 늘 쓰임. 그래프는 흔하지만 그래프 문제는 흔하지 않음
    • 여기에 핵심은 VR이라고 봄
      다른 댓글에서도 그래프 시각화가 어렵다고 했지만, 3D 인터페이스는 훨씬 더 많은 공간을 줌. VR 붐이 시작됐을 때 “VR의 Excel은 뭘까?”라고 생각했는데, Microsoft의 답은 “3D 공간에 떠 있는 2D 스프레드시트”였음. 말도 안 된다고 봄. 나는 그래프라고 생각함
      함께 탐구하고 싶은 사람이 있으면 내 사용자명 at gmail.com으로 메일해도 됨

  • 그래프 타입은 꽤 오래전부터 있었음
    Erlang에는 https://www.erlang.org/doc/man/digraph.html와 https://www.erlang.org/doc/man/digraph_utils가 있고, 집합론적인 작업을 하고 싶다면 https://www.erlang.org/doc/man/sofs.html도 있음

    • 글 끝부분에서 Erlang이 짧게 다뤄짐
      “그래프 타입이 있는 다른 두 언어로 Erlang과 SWI-Prolog를 찾았다. 둘 다 잘 모르기 때문에 언제 추가됐는지는 말할 수 없지만, Erlang은 적어도 2008년 전에는 있었다. Erlang 핵심 언어 위원회 사람에게 연락했지만 답을 받지는 못했다”는 내용임
    • Elixir에도 꽤 괜찮은 그래프 라이브러리가 있음: https://hexdocs.pm/libgraph/api-reference.html
      작업 순서를 정하기 위한 의존성 해결에 써본 적이 있음
    • 그게 다양한 상황에서 얼마나 유연하고 성능이 잘 나오는지가 궁금함
답변달기