1. 문제 (Problem)
그래프 데이터마이닝(Graph Data Mining), 특히 그래프 패턴 마이닝(Graph Pattern Mining) 은 대규모 그래프 데이터셋에서 빈번하게 등장하거나 의미 있는 구조적 패턴을 자동으로 발견하는 문제이다.
기존의 그래프 패턴 마이닝은 대부분 subgraph(부분 그래프) 를 패턴의 표현 언어로 사용해 왔다. 그러나 subgraph를 패턴 언어로 사용하는 접근법은 다음과 같은 표현력의 한계를 가진다.
- Rigid 값 일치 요구: Subgraph는 노드·엣지의 feature 값을 “동일한 값”으로만 매칭한다. “탄소 개수가 3~5개인 고리 구조”처럼 범위(range) 로 정의되는 패턴은 subgraph로 직접 표현할 수 없다.
- 폭발적인 패턴 수: 값이 다른 유사 패턴들이 모두 서로 다른 subgraph로 구분되어 집계된다.
- 실세계 패턴 누락: 의미 있는 패턴은 종종 feature 값의 범위와 위상(topology) 의 조합으로 기술되기 때문이다.
한편 다른 방향에서는 풍부한 제약을 가진 질의 언어(query language) 들이 발전해 왔다. Cypher, GQL, SPARQL, PGQL 등은 property 값에 대한 비교·범위 술어를 지원한다. 그러나 이들은 사용자가 수동으로 패턴을 지정하는 질의 목적이지, 데이터에서 자동으로 의미 있는 패턴을 발견하는 mining 목적이 아니다.
최근 PL4XGL이 제안한 GDL(Graph Description Language) 은 feature 값을 interval(구간) 로 기술할 수 있고, 위상 구조도 함께 표현할 수 있는 declarative 그래프 패턴 기술 언어이다. GDL은 classification 전용 evidence로만 활용되었을 뿐, 일반적인 그래프 데이터마이닝의 패턴 언어로서는 아직 탐구되지 않았다. PL4XGL 저자들 본인이 §8에서 “GDL is strictly more expressive than subgraphs; GDL can be employed in graph data mining” 이라고 명시적으로 제안하였다.
즉 다음 삼각의 교차점에 해당하는 연구 지형이 비어 있다:
- (a) 구조 중심 mining (gSpan, Peregrine, GraphPi) — discrete label만
- (b) 풍부한 술어의 querying (Cypher, GQL, SPARQL) — 자동 mining 부재
- (c) 제약 기반 mining (gPrune, weighted FSM) — 연속 feature interval 미지원
2. 목표 (Goal)
Subgraph 대신 GDL을 패턴 언어로 사용하는 그래프 데이터마이닝 프레임워크를 개발한다.
- 표현력 향상: feature 값의 구간 제약을 포함한 풍부한 패턴을 발견
- 일반화된 패턴 발견: 유사 패턴을 하나의 일반화된 GDL program으로 통합
- Compact한 패턴 집합: subgraph 기반에서 발생하는 중복·폭발 문제를 완화
- 확장성 확보: Peregrine/GraphPi/AutoMine 수준의 systems 성능 목표
- 근사 보장: ASAP/Arya 계열처럼
(ε, δ)-근사 지원 모드 제공