데이터 과학으로
지식 그래프 보강하기

왜 그래프 알고리즘인가 — 구조가 말해 주는 것

그래프 알고리즘은 지식 그래프의 구조에 관한 인사이트를 낳는다. 그 인사이트는 소셜 그래프의 영향력 있는 사람일 수도, 철도망의 핵심 분기점일 수도, 사기꾼들의 세포 조직일 수도, 질병 경로의 공통 병원체일 수도 있다. 그래프 알고리즘의 설계와 구현은 전문 분야지만, 사용은 그렇지 않다 — 알고리즘의 목적과 지식 그래프 위에서 실행하는 문법만 이해하면 된다.

대학 시절 그래프 알고리즘을 (어쩌면 애정을 담아) 기억하는 독자도, 처음 접하는 독자도 있을 것이다. 이 장은 그래프에서 할 수 있는 데이터 처리의 종류를 개관하는 것으로 부드럽게 시작해, 흔한 알고리즘의 사용법으로 깊이 들어간다. 장이 끝날 즈음에는 Cypher 질의만큼이나 편안하게 큰 지식 그래프 위에서 그래프 알고리즘을 돌리게 될 것이다.

그래프 알고리즘의 분류 — 3대 범주와 5대 실용 범주

선택 가능한 그래프 알고리즘은 많고, 각각은 주어진 그래프 위에서 계산을 수행해 기저 토폴로지와 데이터로부터 인사이트를 생성한다. 상황에 맞는 알고리즘을 고르는 첫걸음은 범주로 분류해 어떤 종류의 인사이트를 계산할 수 있는지 조감하는 것이다. 지식 그래프 계산의 관점에서 알고리즘은 세 가지 광의의 범주로 나뉜다.

통계·분석 알고리즘 안에는 지식 그래프 사용 사례에 공통적인 다섯 개의 실용 범주가 있다.

GDS 연산 — 프로젝션, 실행, 그리고 되쓰기

Neo4j Graph Data Science는 Neo4j 그래프 데이터베이스와 편리하게 통합된 그래프 계산 프레임워크다. Neo4j에 저장된 지식 그래프에서 데이터를 프로젝션하고, (여러 CPU를 사용해) 그래프 알고리즘으로 분석을 계산하고, 결과를 검사·공유하거나 기저 지식 그래프에 되써서 보강할 수 있다. GDS와 데이터베이스의 긴밀한 통합은 많은 운영 부담을 제거하고, 알고리즘 실행에 집중하게 하며, 데이터 랭글링을 최소화한다.

질의의 네 요소: ① 프로젝션 이름은 그래프 카탈로그에 저장되어 후속 계산이 접근한다. ② 노드 질의는 프로젝션에 포함될 노드를 고른다 — 레이블로 고르는 방법 등 여러 방식이 있지만 가장 유연한 것은 Cypher 프로젝션이며, 노드 ID는 id 컬럼으로 반환해야 한다는 것이 계약이다. ③ 관계 질의는 포함될 관계를 고르며, 관계는 노드 프로젝션의 노드에 연결되어야 하고(아니면 실패) 시작·끝·타입을 source·target· type 컬럼으로 반환한다. ④ 실행에서 gds.betweenness.write는 결과를 그래프에 되쓴다 — 호출자에게 스트리밍하는 stream, 프로젝션만 보강하는 mutate와 구별된다.

매개 중심성(betweenness centrality)은 주어진 노드를 지나는 경로의 수를 계산해 그래프에서 노드의 중요도를 정한다. 3장의 작은 소셜 네트워크에 실행하면 Karl이 최고 매개 중심성을 갖는다 — Karl은 Rosa와 Fred를 잇는 연결 노드라서, 그가 없으면 소셜 네트워크 전체가 무너진다. Neo4j Bloom 시각화 도구에서는 속성 기반으로 노드의 크기(나 색)를 구성할 수 있어, 중심성이 높을수록 노드를 크게 그려 시각화를 훨씬 정보 풍부하게 만들 수 있다.

매개 중심성만이 아니다 — 경로 찾기, PageRank, Louvain 등 65개 이상의 알고리즘 중에서 고를 수 있고, 각각은 Example 6-1과 똑같이 실행되므로 도메인에 맞는 인사이트를 찾는 실험이 최소한 운영적으로는 단순하다.

Python으로 실험하기 — 영국 철도망 위에서

데이터 과학자의 일에는 실험이 포함된다. 그래프 데이터 과학을 배우려면 좋은 실험 습관 — 가설 위를 빠르게 반복하는 능력 — 도 배워야 한다. 그림 6-1의 아키텍처는 매우 데이터베이스 중심적이라, 알고리즘 실험이 목적일 뿐인데 복잡성에 길을 잃기 쉽다. 다행히 데이터베이스 세부를 추상화해 훨씬 높은 추상화 수준에서 일하게 해 주는 Python 도구가 있다 — 세상을 Python 객체로 보는 것이 데이터 과학자에게는 훨씬 관용적이다.

툴킷 구성: Neo4j와 GDS(당연히), Neo4j GDS Python 드라이버, 그리고 Jupyter Notebook(또는 유사 도구)이다. Python 3이 설치되어 있다면 pip install graphdatascience로 Pythonic API를, pip install notebook으로 Jupyter를 설치한다. 이후 예제는 모두 영국(Great Britain) 철도망에 기반한다 — 크지만 너무 크지 않고, 고도로 상호 연결되어 있으며, 지극히 현실적인 사용 사례라 그래프 데이터 과학 입문자가 탐험하기에 이상적이다. 실험용 소스 데이터는 https://github.com/jbarrasa/gc-2022 에서 받을 수 있다.

이 코드는 세 가지를 한다 — ① GraphDataScience 인스턴스 생성으로 인증된 DBMS 접근을 얻고, ② gds.run_cypher(임의의 Cypher를 실행하게 해 주는 메서드)로 4장과 같은 LOAD CSV를 돌려 이름(name)과 공식 고유 코드(crs)를 가진 Station 노드를 만들고, ③ crs 코드로 from·to 노드를 조회해 소수점 둘째 자리로 반올림된 distance 속성을 가진 TRACK 관계를 MERGE한다. 드라이버도, 세션도, 다른 기술적 데이터베이스 잡무도 다룰 필요가 없었다 — 그저 코드 속 Python 객체 하나를 썼을 뿐이다.

프로젝션과 최단 경로 — 버밍엄에서 에든버러까지

여행 네트워크에서 가장 흔한 질의는 두 역 사이의 최단(또는 최저 비용) 경로다. 먼저 철도 지식 그래프에서 프로젝션을 만든다 — 알고리즘 계산에 적합한 도메인 특화 인메모리 그래프다. 이 프로젝션은 원본과 위상적으로 유사하지만 노드는 더 적은 데이터(역 이름)만 담고 거리는 관계 속성으로 저장된다. 나중에 더 많은 데이터가 필요하면 더 풍부한 프로젝션을 새로 만들면 되고, 그것은 기존 프로젝션과 나란히 그래프 카탈로그에 추가된다.

find_node_id와 Cypher 표현식으로 버밍엄 뉴 스트리트(Birmingham New Street)와 에든버러(Edinburgh) 역 노드의 ID를 얻어 각각 bham·eboro에 담고, trains 프로젝션 위에서 Dijkstra를 실행한다. relationshipWeightProperty에는 경로 비용 계산에 쓸 distance 속성을 준다. 실행하면 최단 거리 298.0이 출력되고, Neo4j Browser에서 경로를 시각화할 수도 있다.

역 선택이 궁금한 독자를 위해 — 저자 중 한 명(Jim Webber)이 잉글랜드 버밍엄에서 자랐고, 에든버러는 그저 아름다운 도시다. 그런데 버밍엄은 지리적으로 흥미롭다(영국인들 사이에서는 지루하다는 부당한 평판이 있지만, 산업혁명의 심장으로서 당대의 실리콘밸리였고 그 유산이 많이 남아 있다). 잉글랜드 중앙에 있고, 버밍엄 뉴 스트리트는 에든버러와 교차하는 노선을 포함해 영국 전역의 노선을 서비스하는 분주한 허브 역이다. 그렇다면 버밍엄 뉴 스트리트가 영국 철도망에서 가장 핵심적인 역이라고 추측할 만하고, 그 추측에 근거해 역과 주변 선로에 대한 대규모 투자를 주창할 수도 있다. 그런데 그 추측이 틀렸다면? 다행히 직감을 빠르게 검증할 도구가 손안에 있다.

탬워스의 반전 — 알고리즘이 직감을 뒤집을 때

trains 프로젝션에는 분석에 필요한 모든 데이터가 있다. 버밍엄 뉴 스트리트의 중요성을 검증(또는 반증)하려면 중심성을 계산하면 된다.

실행 결과는 Tamworth(탬워스)다 — 시스템에 대한 비공식적 이해에서 기대한 답이 아니다. 실제로 탬워스의 중심성 점수는 1,967,643으로 버밍엄 뉴 스트리트의 254,706보다 거의 여덟 배 높다. 이제 장애 시 철도망에 가장 큰 영향을 미치는 곳은 버밍엄에서 몇 마일 떨어진 탬워스임을 안다. 철도 정책 담당자라면 거기서 시작할 것이다.

프로덕션 고려 사항 — 역할 분리와 인과적 장벽

실험 설정에 만족하고 프로젝션·알고리즘 선택이 끝나면 프로덕션으로 옮길 때가 온다. 이제 Python 객체와 Jupyter Notebook의 세계가 아니라 프로덕션 데이터 엔지니어링의 영역이다. 흔한 구성은 물리 서버를 역할별로 분리해 워크로드를 물리적으로 격리하는 것이다. Neo4j는 이를 위해 프라이머리(primary)와 세컨더리(secondary) 서버 개념을 지원한다.

프라이머리는 트랜잭션 처리를 담당하고 지식 그래프를 클러스터링해 규모와 내결함성을 확보하며, 대개 Cypher 질의도 서비스한다. 원칙적으로 프라이머리에서도 알고리즘을 돌릴 수 있지만, 알고리즘의 계산 워크로드와 진행 중인 데이터베이스 워크로드 사이에 경합이 생긴다. 대신 데이터 과학용 세컨더리 인스턴스 배치를 고려하라 — 세컨더리는 갱신을 트랜잭션이 아니라 비동기로 받으므로 갱신 시점 보장이 느슨한 대신, 트랜잭션 처리를 늦추지 않는다. 사이징도 다르게 한다 — 프라이머리는 큰 RAM과 높은 I/O에 적당한 CPU(데이터베이스 질의·트랜잭션은 CPU 바운드가 드물다), 세컨더리는 빠른 병렬 계산을 위한 다수의 빠른 CPU와 큰 RAM이다.

클러스터 인프라는 서버에 의도된 역할을 태깅하게 해 주므로 사용자는 작업을 가장 적절한 물리 서버로 보낸다. 이 모든 것이 단순하고 대부분 투명하다. 분명히 말하면, Neo4j는 지식 그래프를 위한 하이브리드 트랜잭션· 분석 처리(HTAP) 운영을 매우 단순하게 만든다 — 동일한 데이터를 가진 단일 클러스터이며, ETL도 OLAP 큐브도 다른 복잡한 데이터 엔지니어링도 필요 없다.

세컨더리의 신선도 보장 — 북마크와 인과적 장벽

그래프 알고리즘을 돌리기 전에 세컨더리의 신선도(freshness)를 보장받고 싶을 때가 있다. 3장에서 본 Neo4j의 선택적 인과적 장벽(causal barrier) — 광역 네트워크에 흩어진 서버에서도 사용자는 언제나 최소한 자신의 쓰기를 본다 — 은 프라이머리와 세컨더리 모두에, 트랜잭션 워크로드만큼이나 데이터 과학에도 적용된다.

지식 그래프 보강 — stream을 write로 바꾸는 순간

프로덕션 데이터 과학이 실험 국면과 달라지는 또 하나의 지점은 결과로 무엇을 하는가다. 실험에서는 노트(물리적이든 디지털이든)에 결과를 기록하는 것이 선호되지만, 프로덕션에서는 결과를 활용해 시스템을 개선해야 한다. Example 6-5에서 중심성 결과는 gds.betweenness.stream(graph)으로 Python 클라이언트에 스트리밍되어 콘솔에 출력되었다. 결과가 유용했다면 운영화할 수 있는 방식으로 포착하고 싶을 것이다. 방법은 간단하다 — stream 메서드를 mutate(프로젝션 갱신) 또는 write(기저 지식 그래프 보강 — 계산이 어디서 실행되었든)로 바꾸면 된다.

이 코드는 중심성 계산을 수행하되 결과를 콘솔에 보내는 대신 기저 지식 그래프에 되써서, ML을 위한 그래프 피처 엔지니어링 같은 미래의 사용 사례를 위해 그래프를 보강한다. 콘솔 메시지(2593개 역 전부에 betweenness 점수)로 보강을 검증할 수 있다. 탐색적 그래프 분석에서 데이터 과학으로, 실험 정제에서 프로덕션 준비로의 이동은 이처럼 직선적이다 — 훈련받은 데이터 과학자가 아닌 독자도 이 동선을 따라 충분히 전진할 수 있다.

요약 — 지루하기는커녕, 정량화된 인사이트

이 장에서 그래프 알고리즘을 배웠다(어쩌면 다시 배웠다). 지루하고 기계적인 것이기는커녕, 그래프 알고리즘을 이용한 실험은 정량화 가능한 인사이트를 표면화한다. 그리고 코딩이나 데이터 엔지니어링은 거의 필요하지 않다는 것도 보았다.