그래프 데이터마이닝(Graph Data Mining), 특히 그래프 패턴 마이닝(Graph Pattern Mining) 은 대규모 그래프 데이터셋에서 빈번하게 등장하거나 의미 있는 구조적 패턴을 자동으로 발견하는 문제이다. 신약 개발, 소셜 네트워크 분석, 프로그램 분석, 사기 탐지 등 다양한 도메인에서 핵심 기법으로 활용된다.
기존의 그래프 패턴 마이닝은 대부분 subgraph(부분 그래프) 를 패턴의 표현 언어로 사용해 왔다. 예를 들어 frequent subgraph mining (gSpan, FSG, Gaston, CloseGraph 등), motif discovery (ESU/FANMOD), graphlet counting (ORCA, ESCAPE) 등은 모두 subgraph를 기본 단위로 한다. 최근의 대규모·분산 시스템들 (Arabesque, Peregrine, AutoMine, GraphPi, Pangolin, Sandslash) 또한 subgraph 표현 위에서 속도와 확장성을 개선해 왔다.
그러나 subgraph를 패턴 언어로 사용하는 접근법은 다음과 같은 표현력의 한계를 가진다.
한편 다른 방향에서는 풍부한 제약을 가진 질의 언어(query language) 들이 발전해 왔다. Cypher [Francis et al., SIGMOD 2018], GQL [ISO/IEC 39075:2024], SPARQL, PGQL 등은 property(속성) 값에 대한 비교·범위 술어를 지원한다. 그러나 이들은 사용자가 수동으로 패턴을 지정하는 질의 목적이지, 데이터에서 자동으로 의미 있는 패턴을 발견하는 mining 목적이 아니다. 제약 기반 마이닝 연구(gPrune [Zhu et al., VLDB 2007], 가중치 FSM) 또한 구조적·카테고리형 제약 중심이며, 연속형 feature에 대한 interval 술어를 native하게 다루는 마이닝 알고리즘은 부재하다.
최근 PL4XGL[Jeon, Park, Oh, PLDI 2024]이 제안한 GDL(Graph Description Language) 은 feature 값을 interval(구간) 로 기술할 수 있고, 위상 구조도 함께 표현할 수 있는 declarative 그래프 패턴 기술 언어이다. GDL program은 노드 기술 node x <φ>, 엣지 기술 edge (x,y) <φ>, 그리고 target symbol $\tau \in {\texttt{node }x, \texttt{edge }(x,y), \texttt{graph}}$ 로 구성되어, 노드·엣지·그래프 수준의 패턴을 모두 기술할 수 있다. Interval은 [lb, ub] / [-∞, ub] / [lb, ∞]와 같은 open bound를 포함한다. 이는 subgraph가 가질 수 없는 “degree $\geq 12$인 노드”와 같은 패턴을 자연스럽게 표현 가능하게 한다. 예를 들어 BA-Shapes 데이터셋에서 GDL program [12, ∞] — [-∞, ∞] — [12, ∞]는 Barabási–Albert 그래프의 노드를 precision 99%, recall 97%로 기술하는데, 이러한 degree-range 패턴은 subgraph 표현으로는 불가능하다 [PL4XGL §8].
GDL은 classification 전용 evidence로만 활용되었을 뿐, 일반적인 그래프 데이터마이닝의 패턴 언어로서는 아직 탐구되지 않았다. 흥미롭게도 PL4XGL 저자들 본인이 논문의 Related Work (§8)에서 “GDL is strictly more expressive than subgraphs; GDL can be employed in graph data mining” 이라고 명시적으로 제안하였다. 그러나 이 가능성을 실제로 구현한 연구는 아직 없다. 즉 다음 삼각의 교차점에 해당하는 연구 지형이 비어 있다:
Subgraph 대신 GDL을 패턴 언어로 사용하는 그래프 데이터마이닝 프레임워크를 개발한다. 구체적으로 다음을 달성한다.