Graph Data Mining with GDL

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 계열처럼 (ε, δ)-근사 지원 모드 제공

3. 기본 접근 방법 (Basic Approach)

기존의 subgraph 기반 패턴 마이닝을 GDL program 공간으로 lift하는 것이 핵심 아이디어이다.

(1) GDL 패턴 공간의 정의

GDL program P = (δ_V, δ_E, τ): 노드/엣지 기술 + target symbol τ
패턴의 semantics를 target에 따라 정의
Generality order P₁ ⊑ P₂ — PL4XGL의 합성 알고리즘이 이용하는 핵심 관계
Canonical form: gSpan의 DFS code를 interval-augmented 형태로 확장

(2) GDL 패턴 마이닝 알고리즘

Candidate generation:
- Top-down synthesis [PL4XGL §5.2]: 가장 일반적인 program으로부터 시작 → specializing
- Bottom-up synthesis [PL4XGL §5.3]: 가장 구체적 program으로부터 시작 → generalizing
Interval generalization: 서로 다른 feature 값을 가진 유사 패턴들을 하나의 interval 제약으로 일반화
Pattern growth: gSpan의 rightmost-extension을 GDL 공간에 이식
Support / frequency 정의: 일반화된 support 계산. MNI support 정의도 interval 공간으로 확장
Pruning:
- Anti-monotonic pruning: GDL 패턴 간의 subsumption 관계를 활용
- Closedness / maximality: CloseGraph 스타일의 closed GDL pattern 개념 도입
- Symmetry breaking: GraphZero 계열의 자동 동형성 제거 기법 적용
Essential-only mining: PL4XGL의 관찰에 따르면 실제 classification에 사용된 program은 전체의 ~5% 에 불과

(3) 패턴 품질 평가 및 선택

Coverage: 데이터셋을 얼마나 설명하는가
Diversity: 패턴 간 semantic overlap (pairwise Jaccard diversity)
Precision / Discriminativeness: label이 있는 경우 특정 클래스에 대한 판별력
Interpretability: 패턴 크기, interval 폭 등

(4) 확장성

Approximate mode: ASAP / Arya 계열의 color-coding + neighborhood sampling을 interval 패턴으로 확장
Systems 수준 최적화: AutoMine 스타일 query-to-code compilation, Pangolin 스타일 GPU 병렬화

4. 후보 벤치마크 (Candidate Benchmarks)

Graph-level 패턴 평가

MUTAG, PTC (MR), NCI1, NCI109, Mutagenicity, BBBP, BACE, PROTEINS, DD, ENZYMES
OGB-MolHIV, OGB-MolPCBA, ZINC
HIV — PL4XGL이 training timeout으로 실패한 데이터

Node-level 패턴 평가

BA-Shapes, Tree-Cycles — 합성 데이터, 명시된 motif
Wisconsin, Texas, Cornell
Cora, Citeseer, Pubmed
BA-2Motifs

Frequent subgraph mining 전통 벤치마크

Mico, Patents, Youtube, CiteSeer, Yeast
AIDS, DBLP, Cora
PubChem, ChEMBL — 수백만~수천만 규모
LDBC Social Network Benchmark (SNB)
GMark, GraphChallenge

소셜 / 웹 대규모 그래프

SNAP: LiveJournal, Orkut, Friendster, Pokec, Reddit
OGBN-Arxiv / Products / Papers100M

프로그램 분석 / 보안

Devign, Big-Vul, Reveal, VulDeePecker
Joern / CPG
Android malware call-graph datasets

사기 / 금융

Elliptic Bitcoin, YelpChi, Amazon Fraud, DGraph-Fin
AML synthetic

5. 후보 베이스라인 (Candidate Baselines)

5.1 Classical Frequent Subgraph Mining

AGM [Inokuchi, Washio & Motoda, PKDD 2000]
FSG [Kuramochi & Karypis, ICDM 2001]
gSpan [Yan & Han, ICDM 2002] — DFS code + rightmost extension의 고전
CloseGraph [Yan & Han, KDD 2003]
FFSM [Huan, Wang & Prins, ICDM 2003]
Gaston [Nijssen & Kok, KDD 2004]
MoFa [Borgelt & Berthold, ICDM 2002]

5.2 Scalable / Parallel / Distributed Systems

Arabesque [Teixeira et al., SOSP 2015]
RStream [Wang et al., OSDI 2018]
Fractal [Dias et al., SIGMOD 2019]
AutoMine [Mawhirter & Wu, SOSP 2019]
Peregrine [Jamshidi, Mahadasa & Vora, EuroSys 2020] — 가장 중요한 modern baseline
Pangolin [Chen et al., VLDB 2020]
GraphZero [Mawhirter et al., MICRO 2021]
GraphPi [Shi et al., SC 2020] — 최고 속도
Sandslash [Chen, Prountzos et al., ICS 2021]
GraphINC [Hussein et al., SIGMOD 2023]
GraphMini / G2Miner / SumPA (2022–2023)

5.3 Approximate & Sampling-Based Mining

ASAP [Iyer et al., OSDI 2018]
Arya [Arpaci-Dusseau et al., arXiv 2024]
Motivo [Bressan, Leucci, Panconesi, VLDB 2019]
MOSS-5 [Wang et al., IEEE TKDE 2018]
GUISE / MFinder

5.4 Motif / Graphlet Counting

Network motifs [Milo et al., Science 2002]
ESU / FANMOD [Wernicke, Bioinformatics 2006]
ORCA [Hočevar & Demšar, Bioinformatics 2014]
PGD [Ahmed et al., IEEE TKDE 2016]
ESCAPE [Pinar, Seshadhri, Vishal, WWW 2017]

5.5 Neural / Learning-Based Pattern Mining

SPMiner [Ying et al., NeurIPS 2020] — 가장 중요한 neural baseline
NeuroMatch [Ying et al., arXiv 2020]
GNN-based subgraph counting [Chen et al., NeurIPS 2020]
GSN [Bouritsas et al., IEEE TPAMI 2023]
ID-GNN [You et al., AAAI 2021]

5.6 Pattern Languages Beyond Plain Subgraphs

Cypher [Francis et al., SIGMOD 2018]
GQL [ISO/IEC 39075:2024]
SPARQL 1.1
RPQ / CRPQ
PGQL [van Rest et al., GRADES 2016]

5.7 Constraint-Based / Quantitative Mining

gPrune [Zhu, Yan, Han, Yu, VLDB 2007] — GDL의 직접적 선행 연구
Weighted / Quantitative FSM
SUBDUE [Holder & Cook, 1994–2009]

5.8 GDL/Declarative 기반 (직접 비교 대상)

PL4XGL [Jeon, Park, Oh, PLDI 2024] — GDL 언어의 원출처. 저자들이 “GDL can be employed in graph data mining” 을 직접 제안. 그러나 mining이 classification 목적으로 특화되어 있고, 일반 FSM의 frequency/support/closedness 개념은 없음

평가 지표

Coverage / Support
Diversity (pairwise Jaccard)
Compression ratio: subgraph 대비 패턴 수 감소
Downstream task accuracy
Runtime / Scalability
Approximation error
Interpretability

연구 지형 요약 (Research Landscape Summary)

축	대표 연구	한계
(a) 구조 중심 exact mining	gSpan, Peregrine, GraphPi, AutoMine	discrete label만, 값 범위 불가
(b) 풍부한 술어 querying	Cypher, GQL, SPARQL	자동 mining 부재
(c) 제약 기반 mining	gPrune, weighted FSM	연속 feature interval native 미지원
(d) Approximate mining	ASAP, Arya, Motivo	주로 counting, pattern language는 subgraph
(e) Neural mining	SPMiner, NeuroMatch	discrete label 중심, 해석성 제한
(f) GDL symbolic classification	PL4XGL	classification 전용, 일반 mining 개념 없음

GDL 기반 mining은 (a)·(b)·(c)의 교집합에 해당하는 영역을 겨냥한다.

GDL 확장 방향

Homophily / heterophily 기술
Aggregate 술어: “oxygen 개수 > chlorine 개수”, “이웃 degree 합 ≥ k”
Recursive / path 패턴: RPQ 스타일의 경로 술어
수치 비교: 두 노드 변수 간 feature 값 비교 (x.f ≤ y.f)