제3장 완전한 KG 위 심볼릭 추론

SECTION 3.1

서론 — 왜 근사 서브그래프 매칭인가

(근사) 서브그래프 매칭은 데이터 마이닝, 데이터베이스, 정보 검색, 컴퓨터 비전, 자연어 처리에 이르는 여러 분야의 핵심 프리미티브(core primitive)다.

DATA MINING

빈발 패턴 발견

근사 서브그래프 동형사상으로 빈발 패턴을 찾는다[4].

DB / IR

상호 연관 논문 검색

상호 연관된 연구 논문 집합을 찾는 질의를 서브그래프 매칭 문제로 취급한다[55].

COMPUTER VISION

기호·객체 인식

객체 겹침·분할 오류에 따른 노드 병합·분할 허용 근사 매칭으로 정식화한다[95].

NLP

패러프레이즈

어휘 자원의 단어를 노드로, 관계를 간선으로 보면 패러프레이즈는 그래프 매칭이 된다[106].

기존 연구는 정확(exact) 매칭과 비정확(inexact) 매칭의 두 범주로 나뉘며, 각각 뚜렷한 장단점을 지닌다.

정확 매칭 [9, 10, 34, 119]

핵심 아이디어는 거짓 후보의 조기 가지치기와 유망 후보에 대한 인덱스 구축이다. 효과적인 가지치기 조건으로 탐색 공간을 크게 줄일 수 있다.

그러나 실제 그래프의 상당수는 잡음이 있고 불완전하여, 관측된 데이터 그래프에 정확 매칭이 아예 존재하지 않을 수 있다. 이 경우(정확 매칭의 존재 여부를 알 수 없는 상황) 인덱스 기반 정확 매칭은 인덱스의 모든 가능한 후보를 순회하며 지수 시간 복잡도를 소모한 끝에 아무것도 반환하지 못할 수 있다. 또한 점진적 탐색[5, 16]처럼 사용자가 정확히 무엇을 찾는지 모르는 경우, 정확 매칭이 존재하더라도 바람직하지 않을 수 있다.

비정확 매칭 [141, 142, 144]

휴리스틱으로 중요한 시드(seed) 노드를 식별한 뒤, 시드의 이웃으로 점진적으로 확장한다. 보통 비교적 짧은 시간에 근사 매칭 서브그래프를 반환할 수 있다.

그러나 부분 매칭을 단계별로 확장하는 탐욕(greedy) 전략은 최적이 아닌 탐색 경로로 쉽게 이탈한다. 아래 예시가 이 함정을 보여준다.

FIG 3.1 재구성 — 탐욕 확장의 함정 (시드 v0에서 시작)

탐욕 확장 (예: [142, 144]) — v1이 u1에 완벽히 대응되므로 v1을 다음 후보로 선택하고, 이어 v4, v5로 확장하여 최종적으로 (v0, v1, v4, v5, v8)이 유도하는 서브그래프를 반환한다. 국소적으로는 최선이지만 전역적으로는 차선의 결과다.

데이터 그래프의 잡음·불완전성과 질의 그래프의 불확실성 때문에 정확 매칭 서브그래프는 존재하지 않거나 바람직하지 않을 수 있다. 따라서 이 장은 근사 서브그래프 매칭에 집중하며 (제안 알고리즘은 정확 매칭도 찾을 수 있다), 새로운 알고리즘 G-Finder를 제안한다. 핵심 아이디어는 질의 그래프 구조에 따라 데이터 그래프에 인덱스를 구축하여 매칭 정확도를 높이는 것이다. 기존 비정확 매칭과 비교해 G-Finder는 (1) 새로운 보조 자료구조 Lookup-Table(LTB)과 이웃 확장(neighborhood expansion) 기법을 결합해 질의 노드의 후보 정점을 색인하면서 질의 그래프의 위상 구조를 유지하고, (2) LTB로 질의 노드의 거짓 양성 후보를 효과적으로 가지치기하여 효과적인 매칭 순서를 계산한다. 다양한 실제 데이터셋 실험에서 G-Finder는 F1-Score 기준 최고 베이스라인보다 최대 30% 우수하며, 특히 풍부한 속성 정보를 가진 데이터 그래프에서 데이터 그래프와 질의 그래프 크기 모두에 대해 준선형(near-linear)으로 확장된다.

SECTION 3.2

문제 정의

명확성을 위해 질의 그래프 Q의 원소는 노드(node)·에지(edge)로, 데이터 그래프 𝒢의 원소는 정점(vertex)·링크(link)로 부른다. u, û는 질의 노드를, v, v̂는 데이터 정점을 가리킨다. 그래프는 튜플 {V, E, L}로 표기하며 L은 노드/정점·에지/링크를 속성값에 대응시키는 속성 함수다.

기호	정의	기호	정의
Q = {V_Q, E_Q, L_Q}	속성 질의 그래프	N(u)	질의 노드 u의 이웃
𝒢 = {V_G, E_G, L_G}	속성 데이터 그래프	C(u)	질의 노드 u의 후보 집합
H_i / Q_i	i개 노드의 부분 매칭 / 부분 질의 그래프	LTB(u)	질의 노드 u의 Lookup-Table
m(u_i) = v_i	매칭 함수	LTBG	모든 LTB가 이루는 Lookup-Table-Graph
u, û / v, v̂	질의 노드 / 데이터 정점	f(Q, H)	손실 함수

DEFINITION 3.1 · 정확 서브그래프 매칭 (서브그래프 동형사상) [158]

단사 함수 m(): V(Q) → V(𝒢)로서 다음을 만족한다.

(1) ∀ u ∈ V(Q): m(u) ∈ V(𝒢) ∧ L(u) = L(m(u))
(2) ∀ (u_a, u_b) ∈ E(Q): (m(u_a), m(u_b)) ∈ E(𝒢) ∧ L(u_a, u_b) = L(m(u_a), m(u_b))

근사 매칭이 허용하는 세 가지 불일치

정확 매칭과 달리, 근사 서브그래프 매칭은 일부 누락 질의 노드·누락 질의 에지·중간 데이터 정점을 허용한다. 나머지 비누락 질의 노드와 비중간 데이터 정점 중 매핑 함수 m()을 만족하는 쌍은 매칭 쌍(matching pair)이라 한다.

MISSING QUERY NODE (MN)

누락 질의 노드

u ∈ V(Q)이지만 m(u) ∉ V(𝒢)인 노드 u.

MISSING QUERY EDGE (ME)

누락 질의 에지

(u_a, u_b) ∈ E(Q)이지만 (m(u_a), m(u_b)) ∉ E(𝒢)인 에지.

INTERMEDIATE VERTEX (IN)

중간 데이터 정점

에지 (u_a, u_b) ∈ E(Q)가 데이터에 없지만, (m(u_a), v_i)와 (v_i, m(u_b))가 모두 E(𝒢)에 존재할 때의 v_i.

DEFINITION 3.2 · 선형 손실 함수

질의 그래프 Q와 결과 매칭 서브그래프 ℋ에 대해:

f(Q, ℋ) = w₁ × MN + w₂ × ME + w₃ × IN

MN은 누락 질의 노드 수, ME는 누락 질의 에지 수, IN은 중간 데이터 정점 수다. 가중치 w₁, w₂, w₃를 조정해 각 불일치 유형에 대한 허용치를 제어한다 — w₁이 작으면 더 많은 누락 노드를 허용하고, w₂ = ∞이면 누락 에지를 전혀 허용하지 않는다. 정확 매칭 서브그래프가 존재하면 손실 비용은 0이다.

DEFINITION 3.3 · 노드-정점 유사도

정확 매칭에서는 u의 모든 이웃이 v의 이웃에 대응되어야만 u를 v에 매핑할 수 있으나, 근사 매칭에서는 이 강한 제약이 완화된다. G-Finder는 (1) 동일한 속성값, (2) 높은 노드-정점 유사도, (3) 이웃들 또한 높은 노드-정점 유사도를 만족하면 매핑을 허용한다.

sim(v_i, u_i) = |( m(N(u_i)) ∩ N(v_i) )| / |N(u_i)|

N(v_i)는 v_i의 이웃, m(N(u_i)) ∩ N(v_i)는 N(u_i) 중 N(v_i)로 매핑된 노드들이다. 예컨대 u₂→v₆, u₃→v₇로 매핑 가능하면 sim(v₃, u₁) = 2/3이다.

REMARKS 손실 함수와 노드-정점 유사도에는 대안이 존재한다 — 그래프 편집 거리[44], 그래프 커널[128], 임베딩 기반 그래프 유사도[110], 행렬 기반 노드 유사도[5], GNN 기반 유사도[50] 등. G-Finder는 원칙적으로 이들 대안을 수용할 수 있으나, 이 장에서는 효율성을 고려해 상대적으로 단순한 두 형태를 사용한다.

기존 방법과의 성질 비교 (Table 3.2)

방법	노드 속성	에지 속성	정확 매칭	누락 노드	누락 에지	중간 노드	인덱스 기반	조기 가지치기	멀티그래프
G-Finder	✓	✓	✓	✓	✓	✓	✓	✓	✓
CFL	✓	✗	✓	✗	✗	✗	✓	✓	✗
G-Ray	✓	✗	✗	✓	✓	✓	✗	✗	✗
FIRST	✓	✓	✗	✓	✓	✓	✗	✗	✗
MAGE	✓	✓	✗	✓	✓	✓	✗	✗	✗
FilM	✗	✗	✓	✗	✗	✗	✗	✓	✓
NeMa	✓	✓	✓	✓	✓	✓	✓	✓	✗

PROBLEM 3.1 · Top-k 근사 서브그래프 매칭

주어진 것 — (1) 속성 데이터 그래프 𝒢, (2) 속성 질의 그래프 Q, (3) 원하는 매칭 서브그래프 수 k, (4) 손실 함수 f().
찾을 것 — 질의 그래프 Q에 가능한 한 잘 매칭되는(손실 함수 비용이 가장 작은) k개의 근사 매칭 서브그래프.

SECTION 3.3

방법 개요 — 네 단계 프레임워크

G-Finder의 전체 프레임워크는 네 개의 주요 단계로 구성된다(Fig 3.2, Algorithm 1).

루트 선택 (Root Selection)

ALGORITHM 1, LINES 3–4

매칭 과정을 시작할 루트 노드를 질의 그래프에서 선택한다. 바람직한 루트는 (1) 후보가 가능한 한 적고, (2) 탐색 공간의 지름을 최소화하도록 질의 그래프의 중심에 있어야 한다[9]. 이를 위해 질의 그래프를 코어-포레스트 구조로 분해한 뒤(코어: 모든 노드가 이웃을 2개 이상 갖는 최대 서브그래프[10], 나머지는 포레스트), 코어 구조에서 u_r ← argmin_u |C(u)| / deg(u)인 노드를 루트로 선택한다. |C(u)|는 데이터 그래프 내 u의 후보 집합 크기, deg(u)는 질의 그래프 내 u의 차수다.

Lookup-Table-Graph 구축

ALGORITHM 1, LINE 7

질의 그래프를 노드 단위로 순회하며 인덱스를 구축한다. 핵심은 후보 정점의 정보를 저장하는 새로운 자료구조 Lookup-Table(LTB)이다. 질의 그래프의 각 노드 u가 대응하는 LTB(u)를 가지며, 모든 LTB는 질의 그래프와 동일한 위상을 공유하는 그래프, 즉 Lookup-Table-Graph(LTBG)를 이룬다.

BFS 트리 순회 — 여러 정확 매칭 방법이 사용하는 일반적 전략[9, 10]. BFS 트리와 질의 그래프 모두에 존재하는 에지는 트리 에지(TE), 질의 그래프에만 존재하는 에지는 비트리 에지(NTE)다.
BFS의 한계 — 어떤 질의 노드(예: u₇)가 데이터 그래프에 후보가 없으면 LTB(u₇)가 비고, 그 자식들(u₅, u₆)까지 무시되어 결과 품질이 나빠진다. 근사 매칭에는 부적합할 수 있다.
힙 기반 동적 순회(Dynamic-Tree) — 처리 중인 LTB를 힙에 저장하고, 매번 |C(u)|/deg(u)가 가장 작은 LTB를 꺼내 미방문 이웃의 LTB를 재귀적으로 구축·삽입한다. 질의 그래프의 모든 노드가 처리될 때까지 반복한다.

매칭 순서 결정 (Matching Identification)

ALGORITHM 1, LINE 8

매칭 순서는 LTBG의 후보들을 질의 노드에 매칭시키는 질의 노드 시퀀스다. 예컨대 순서가 (u₀, u₁, u₂, u₃)이면, LTB(u₀)에서 좋은 후보 v₀를 고르고, v₀에 연결된 LTB(u₁)의 후보 v₁, 이어 v₀·v₁ 모두에 연결된 LTB(u₂)의 후보 v₂, v₀·v₂에 연결된 LTB(u₃)의 후보 v₃를 차례로 선택한다. 최소 빈도 경로 우선[169], 탐욕적 경로 정렬[10], 최소 빈도 노드 우선[127] 등 여러 방법이 있으며, 공통 아이디어는 후보 정점이 가장 적은 노드/경로를 먼저 선택해 탐색 공간을 압축하는 것이다. G-Finder에서는 이들의 매칭 정확도가 유사하여, 계산 효율을 위해 탐욕적 경로 정렬을 사용한다.

서브그래프 열거 (Subgraph-Enumeration)

ALGORITHM 1, LINE 9

Step 3의 매칭 순서에 따라 LTBG의 후보를 탐색하여, 손실 함수 비용이 가장 작은 Top-k 근사 매칭 서브그래프를 찾는다. 매칭 과정 동안 지금까지의 k개 최선 결과를 저장하는 힙을 유지하고, 더 좋은 결과를 찾으면 힙을 갱신한다.

SECTION 3.4

방법 상세 — LTBG 구축과 서브그래프 열거

G-Finder에서 가장 복잡한 두 단계인 Lookup-Table-Graph 구축과 서브그래프 열거의 세부를 제시하고, 시간·공간 복잡도를 분석한다.

A — Lookup-Table 구조

LTB는 후보 정점의 정보, 즉 후보 집합, 부모-자식 관계, 중간 정점 수(IVN), 노드-정점 유사도(SIM)를 저장한다. LTB 간에는 부모-자식 관계(트리 에지에 의한)와, 비트리 에지에서 비롯되는 선방문 이웃(prior-visited neighborhood) 관계가 존재한다 — 예컨대 u₃와 u₄ 사이에 비트리 에지가 있고 LTB(u₃)가 LTB(u₄)보다 먼저 구축되면 두 LTB 사이에 선방문 이웃 관계가 생긴다. 데이터 그래프 후보 정점들 사이의 부모-자식 관계도 함께 기록된다. LTB 구축 시 후보 정점은 IVN과 SIM으로 정렬되며, 매칭 과정에서 SIM이 높고 IVN이 작은 정점을 먼저 선택하여 선형 손실 함수 비용을 작게 만든다.

B — LTB 구축과 Neighbor-Expander

루트 선택 후, 데이터 그래프를 동적으로 탐사하며 각 질의 노드의 후보를 고른다. 이때 노드-정점 유사도, 중간 정점 수, 누락 노드/에지 허용치라는 정제·필터링 전략으로 유망하지 않은 후보를 가지치기하여 후보 크기를 최소화한다. 직관적으로, 부분 매칭 H_i가 있고 다음 노드 u_j의 매칭 정점을 찾을 때, v_j가 좋은 후보라면 Q_i ∩ N(u_j)의 각 노드 u_n에 대해 그 후보 v_n과 인접해야 한다. 그러나 근사 매칭에서는 누락 노드/에지를 허용한다면 이 강한 제약을 만족하지 않아도 된다.

STRATEGY · Neighbor-Expander (Algorithm 2의 핵심)

u_p가 u_j의 부모이고 대응 데이터 정점이 v_p라 하자.

① v_p의 t-홉 이웃 중 속성이 L(u_j)인 정점을 모두 골라 집합 M에 추가한다
② 각 v_m ∈ M에 대해 노드-정점 유사도를 계산 — sim(v_m, u_j) ≥ s(사전 정의 임계값)이면 좋은 후보로 취급
③ 각 v_m이 H_i의 정점 몇 개와 연결되는지 계산 — |N(u_j)| − d보다 크면 좋다고 판정 (d는 허용할 누락 에지 수)

이 장에서 근사 매칭의 t = 2이며, 사용자는 다른 t를 선택할 수 있다. 예컨대 v₃는 v₀의 2-홉 이웃이고 sim(v₃, u₁) = 2/3이므로 s = 0.5일 때 좋은 후보다.

단일 LTB는 선방문 이웃들의 LTB 정보를 활용하여 구축한다(Algorithm 2). u_i의 방문된 이웃 집합을 N_visited(u_i)라 하면, u_i의 후보는 N_visited(u_i)의 후보 집합들로부터 생성된다: 각 u_j ∈ N_visited(u_i)의 후보 v_j ∈ C(u_j)마다 Neighbor-Expander로 sim(v, u_i) ≥ s인 좋은 후보를 골라 집합 S에 넣는다(Lines 4–6). 이어서 부모 후보 C(u_p)의 각 정점 v_n에 대해 S 내의 t-홉 이웃을 LTB(u_i).adj[v_n]에 저장하여 데이터 그래프 상의 공통 부모 관계를 기록하고, 마지막으로 중간 정점 수를 기록한다(Line 12). 예컨대 LTB(u₄)는 LTB(u₂)·LTB(u₃)로부터 구축되며 — C(u₂) = (v₄, v₆), C(u₃) = (v₅, v₇), 이들의 2-홉 이웃 중 속성 L(u₄)를 갖는 정점은 각각 (v₁, v₈), (v₃, v₉), (v₁), (v₃, v₉)이고, s = 1/4이면 S = (v₁, v₈, v₃, v₉)가 모두 좋은 후보다. 부모가 u₂이므로 LTB(u₄).adj[v₄] = (v₈, v₁), LTB(u₄).adj[v₆] = (v₃, v₉)가 된다.

C — LTBG 구축 (Algorithm 3)

LTBG 구축의 또 다른 핵심은 질의 그래프 Q에 대한 구축 순서 선택이다. 최소 힙(min heap)으로 현재 처리 중인 노드들의 LTB를 저장하며 동적으로 구축한다 — 먼저 루트 노드의 LTB를 만들어 힙에 넣고(Lines 4–5), 매번 힙에서 LTB 하나를 꺼내 미방문 자식들의 LTB를 구축한 뒤(Lines 7, 9) 자식 LTB를 힙에 넣는다(Line 11). 질의 그래프의 모든 노드가 처리될 때까지 반복한다. 다음에 꺼낼 LTB는 |C(u)|/deg(u)가 최소인 것을 선택하는데, 이 값이 작은 LTB의 자식일수록 후보 정점이 적을 가능성이 높기 때문이다.

서브그래프 열거와 조기 종료 (Algorithm 4)

Top-k 탐색에서는 지금까지 본 최선의 k개 답을 저장하는 Top-k 최대 힙(max heap)을 유지한다. 탐색 중 부분 질의 그래프 Q_i와 부분 매칭 그래프 H_i 사이의 현재 선형 손실 함수 비용을 계산하고, 힙 내 최대 손실 비용과 비교한다. 현재 비용이 힙의 최대 비용보다 높으면 해당 부분 매칭의 확장을 중단하여 조기 종료를 가능하게 한다.

EXAMPLE · FIG 3.5 매칭 순서가 <u₀, u₁, u₇, u₂, u₃, u₄, u₅, u₆>이고 부분 매칭 H₅ = (v₀, v₂, v₃, v₆, v₇), 대응 부분 질의 그래프 Q₅ = (u₀, u₁, u₂, u₃, u₇)일 때, w₁ = w₂ = w₃ = 1이면 중간 데이터 정점 v₂ 하나와 누락 질의 노드 u₇ 하나로 손실 비용은 2다. 이것이 최대 힙의 최대 손실보다 크면 확장을 멈추고, 아니면 계속 확장한다.

복잡도 분석

LTBG-BUILDER (STEP 2)

공간 O(|V(Q)| × |E(𝒢)|)
시간 O(|E(Q)| × |E(𝒢)| × |V(𝒢)|)

질의 Q와 데이터 그래프 𝒢에 대한 최악의 경우 복잡도다.

SUBGRAPH-ENUM (STEP 4) — 최악/최선

최악 O(∏_i=0^|V(Q)|−1 |V(𝒢) − i|)
최선 O(|V(Q)|)

최악은 데이터 그래프가 완전 그래프일 때뿐이며 실제 그래프에서는 극히 드물다. 최선은 모든 노드의 속성이 서로 다를 때다.

평균 (속성 D개일 때) & 경험적

O(∏_i=0^|V(Q)|/D ∏_j=0^D−1 ||V(𝒢)|/D − j|)

경험적으로, 속성 정보가 풍부한 데이터 그래프에서 총 실행 시간은 데이터·질의 그래프 노드 수에 대해 준선형으로 확장된다.

SECTION 3.5

실험 — 효과성과 효율성

실험은 두 질문에 답하도록 설계됐다. Q1 (효과성) — G-Finder의 서브그래프 매칭은 얼마나 정확한가? Q2 (효율성) — G-Finder는 얼마나 빠르고 확장 가능한가?

+30%

DBLP에서 최고 베이스라인(MAGE) 대비 F1-Score 우위 (질의 노드 7·9·13개)

6–8×

IMDB에서 NeMa 대비 실행 시간 우위 (동일 매칭 결과·동일 F1)

>0.8

대부분의 경우에서 G-Finder-Dynamic의 F1-Score

≈ 선형

데이터·질의 그래프 노드 수에 대한 준선형 확장성

실험 설정

데이터셋 — 8개의 실세계 데이터셋을 사용한다(Table 3.3). Human·HPRD는 단백질-단백질 상호작용 네트워크[10], DBLP는 저자-논문 관계, Flickr·LastFm은 사용자 관계, AMiner는 공저 관계의 학술 소셜 네트워크(노드 속성 벡터는 출판 논문 수에서 추출), PNNL-V4는 Pacific Northwest National Laboratory 제작, IMDB는 NeMa[64]와 동일한 영화 데이터셋이다. 베이스라인 — G-Ray[144], MAGE[114], FIRST[5], FilM[34], NeMa[64] 5종(원저자 제공 소스 코드). 제안 알고리즘은 순회 전략에 따라 G-Finder-BFS와 G-Finder-Dynamic의 두 변형을 평가한다. 지표 — 매칭 정확도는 F1-Score, 효율성은 총 실행 시간(인덱스 구축 시간은 질의 시간보다 작다). 선형 손실 함수, MAGE·FIRST의 % Extra nodes, FIRST의 % Exact Matching Nodes 등 대안 지표에서도 G-Finder가 베이스라인을 능가하나 지면 제약으로 F1-Score만 보고한다. 재현성 — C++ 구현, Intel Core-i7 3.20GHz CPU·32GB 메모리 머신에서 수행.

데이터셋	노드 수	에지 수	속성 위치	속성 수
Human	4,674	86,282	노드	44
HPRD	9,460	37,081	노드	307
DBLP	9,143	16,338	노드	29
Flickr	12,974	16,149	노드	3
LastFm	136,421	1,685,524	노드	3
AMiner	1,274,360	4,756,194	노드	300
PNNL-V4	22,154	460,196	에지	259,917
IMDB	2,932,657	11,040,263	노드 & 에지	노드 수 + 에지 수

효과성 결과

질의 그래프는 데이터 그래프의 연결 유도 서브그래프를 뽑아(정확 매칭이 최소 1개 존재하도록) 이를 정답으로 삼고, 에지 삭제·노드 속성 변경·데이터 그래프에 없는 여분 노드 추가 등 다양한 잡음을 주입하여 생성한다. 주요 파라미터는 k = 10, w₁ = w₂ = w₃ = 1(편향 없음)이다. Human·HPRD·DBLP·Flickr·LastFm·AMiner 6개 데이터셋에서 G-Finder-Dynamic은 세 베이스라인(G-Ray·MAGE·FIRST)을 모든 경우에 일관되게 능가했다 — DBLP에서는 최고 베이스라인 MAGE보다 30% 우수했다. 두 변형 사이에서는 G-Finder-Dynamic이 거의 모든 경우 승리하거나 유사한 높은 점수를 얻었으며, 예외는 (1) HPRD 질의 노드 7개, (2) LastFm 9개, (3) AMiner 10개의 세 경우뿐이다.

WHY BFS FAILS Human에서 G-Finder-BFS의 상대적으로 낮은 F1은, 잡음 노드가 루트에 가까울 때 BFS 트리로 변환하면 해당 노드들이 데이터 그래프에 후보를 갖지 못하고 그 자식 노드들까지 무시되기 때문이다. 정확 매칭에서 널리 쓰이는 BFS-트리 순회가 근사 매칭에서는 차선일 수 있으며, 제안한 Dynamic-Tree가 훨씬 효과적인 순회 전략이라는 3.2절의 분석과 일치한다.

정확 매칭 모드 — FilM·NeMa와의 비교

G-Finder는 근사 매칭용으로 설계됐지만, (1) t = 1로 설정(LTBG에서 직접 이웃만 고려)하고 (2) 선형 손실 값이 0인 매칭만 남기면 정확 매칭에도 사용할 수 있다. PNNL-V4에서 FilM[34]은 각 질의 노드에 잠재적 거짓 양성을 포함한 후보 집합을 반환하여 결과 매칭 서브그래프가 100개를 넘지만(후보 수의 곱), 실제 정확 매칭은 단 하나뿐이라 FilM의 F1-Score는 0에 가깝다. 반면 G-Finder-Dynamic은 각 질의 노드에 정확히 하나의 후보를 생성하여 유일한 정확 매칭을 정밀하게 찾아내며, 총 실행 시간도 더 빠르다(134초 vs 199초). NeMa와의 비교에서는 공정성을 위해 NeMa와 동일한 IMDB 데이터셋·노드 추가 잡음 질의를 사용하고 IMDB의 각 속성값을 정수로 매핑했다. 데이터·질의 그래프 모두 고유 속성값을 가지므로 두 알고리즘은 같은 매칭을 찾아 F1이 동일하지만, G-Finder-Dynamic이 6–8배 빠르다.

효율성 결과

실행 시간-정확도 트레이드오프(각 방법당 5개 지점)에서 G-Ray·MAGE·G-Finder가 가장 빨라 짧은 시간 안에 매칭 결과를 찾지만, G-Finder-Dynamic의 매칭 정확도는 다른 방법보다 월등히 높아 대부분의 경우 F1-Score가 0.8을 넘는다. 확장성 실험에서는 G-Finder-Dynamic의 실행 시간이 데이터 그래프와 질의 그래프 노드 수 모두에 대해 준선형으로 확장됨을 확인했다.

SECTION 3.6

논의

이 장은 질의 그래프를 반복적으로 순회하며 데이터 그래프에서 답을 찾는 심볼릭 서브그래프 매칭 방법을 소개했다. 질의 구조에 기반해 매칭 순서를 계산하고 그에 따라 답을 검색한다.

심볼릭 접근의 강점

뉴럴 네트워크 기반 방법과 달리, 심볼릭 접근은 더 정확하고 설명 가능하다.

남는 한계와 다음 과제

질의 그래프의 심볼릭 관계 수가 늘어날수록 시간 소모가 커진다. 추론 과정을 가속하기 위해 심볼릭 추론과 뉴럴 방법을 통합하는 것이 앞으로 해결해야 할 중요한 과제다.

FN1데이터 그래프와 질의 그래프는 멀티그래프일 수 있다. 이해를 돕기 위해 이 장은 주로 노드 속성을 가진 그래프에 집중한다.

FN2그래프 Q의 코어 구조는 모든 노드가 최소 2개의 이웃을 갖는 Q의 최대 서브그래프다[10]. 나머지 부분은 Q의 포레스트 구조라 부른다.

FN3실제로 Fig 3.1에서 G-Finder는 u₄를 루트로 선택하지만, 설명을 위해 이 장의 모든 예시는 u₀를 루트로 가정한다. 루트 노드는 누락 정점일 수 없다.

FN4이 장에서 근사 서브그래프 매칭의 t = 2이며, 사용자는 다른 t를 선택할 수 있다.

FN5인덱스 구축 시간은 질의 실행 시간에 비해 작다.

FN6w₁ = w₂ = w₃ = 1은 G-Finder에 편향이 없음을 의미한다. 예컨대 w₁이 크면 더 많은 결과 노드를 찾으려 하지만 결과 그래프에 중간 노드가 많이 포함될 수 있다.

FN7G-Finder-Dynamic은 FilM보다 빠르다(총 실행 시간 134초 vs 199초). PNNL 데이터셋에는 질의 그래프가 하나뿐이다.