Graph Research Under a Two-Hour Budget

Abstract · why this watch matters

그래프 연구에서 큰 장비는 편리하다. 그러나 좋은 연구 질문까지 대신 만들어 주지는 않는다. 오히려 120분이라는 단단한 예산을 걸어두면 무엇을 계산해야 하고 무엇을 버려야 하는지가 또렷해진다.

2026년 8월 24일 기준으로 SIGMOD·VLDB/PVLDB·ICDE·TKDE 공식 목록에 직전 24시간 동안 새로 추가된 그래프 논문은 확인되지 않았다. 대신 이번 추적에서는 이전 요약에서 충분히 다루지 못했던 여섯 편을 다시 포착했다. temporal BGP join, version-aware storage, streaming flow, structure-informed sampling, durable community, densest flow라는 서로 다른 문제들이지만 공통점이 있다. 대규모 학습보다 자료구조, 샘플링, 증분 처리, 질의 실행 전략이 성능을 결정한다.

M3 128GB에서 두 시간 안에 끝나는 실험은 ‘축소판 연구’가 아니다. 계산 예산 자체를 알고리즘 설계와 평가의 일부로 만들면, 그것은 재현성 높은 시스템 연구의 조건이 된다.

이 글의 High/Medium 평가는 원 논문이 보고한 공식 등급이 아니라, 공개 코드·데이터·명령어 집합 의존성·예상 계산량을 종합한 engineering assessment다. 실제 시간은 첫 10분 pilot benchmark로 보정해야 한다.

Part I · What changed

새 논문은 없었지만, 연구 후보는 늘었다

‘새로 발표되었다’와 ‘새롭게 연구 가치가 보였다’는 같은 말이 아니다.

이번 실행에서 중요한 사실은 의외로 단순하다. 8월 23일 이후 하루 동안 네 venue의 공식 프로그램에 의미 있는 신규 그래프 논문이 추가된 정황은 없었다. 그렇다고 추적의 가치가 사라지는 것은 아니다. 연구 문헌은 발표일에만 움직이지 않는다. 코드가 공개되고, artifact가 정리되고, preprint가 갱신되고, conference session이 확정되면서 재현 가능성의 판단이 달라진다.

그래서 이번 추적에서는 ‘논문 수’를 늘리는 대신 MacBook Pro M3 128GB 한 대에서 핵심 실험을 두 시간 안에 끝낼 수 있는가라는 질문으로 후보를 다시 걸렀다. 이 기준을 통과한 주제는 대체로 GPU를 많이 쓰지 않는다. 대신 query execution, temporal indexing, streaming maintenance, graph sampling처럼 계산 구조 자체를 바꾼다.

연구 장비가 작을수록 좋은 주제는 더 선명해진다. 전체 그래프를 더 빨리 훑는 것보다, 애초에 훑지 않아도 되는 부분을 찾아내는 쪽이 유리하다.

또 하나의 일정상 변화가 있다. VLDB 2026은 8월 31일부터 9월 4일까지 Boston에서 열리며, 9월 2일에는 R34 “Temporal Graph Analytics”, 9월 3일에는 R48 “Dynamic Graphs and Graph Learning” 세션이 예정되어 있다. 따라서 다음 추적에서는 발표 슬라이드, code release, artifact 수정이 나오는지 확인할 가치가 높다.

Part II · Six papers

이번에 다시 봐야 할 여섯 편

각 논문은 ‘좋은 논문인가’보다 ‘작은 단일 머신에서 핵심 주장을 얼마나 깨끗하게 검증할 수 있는가’로 읽었다.

Paper	Venue / status	Core contribution	Code / data	M3 ≤2h	Compact experiment
Worst-Case Optimal BGPs on Temporal Graphs	PVLDB 19(11), 2026	O(N) 공간 temporal index + temporal Leapfrog Triejoin. snapshot/version/order-relation query를 같은 index에서 처리.	이번 추적에서 공개 구현 확인 못함	Medium	1–5M edges, 20–50 BGP, index-build/query latency
TVA	PVLDB 19(10), 2026	version metadata와 property value 분리, temporal table, hopscotch hashing, version-skipping.	공개 GitHub artifact	Medium	mgBench 10K vertices / 121K edges, 1-hop/2-hop scan
ABFlow	SIGMOD 2026	alert bursting flow를 정의하고 suffix-flow + incremental streaming optimization으로 실시간 이상 흐름 탐색.	공개 C++20 구현	High	sample + 1 transaction stream, update/window 3×3
AGIS	PVLDB 19(2), VLDB 2026	pattern structure가 만든 sampling distribution으로 approximate pattern mining을 가속하고 sampling overhead까지 판단.	공개 artifact	High	3 graphs × 3–4 patterns, error–runtime curve
Effective Durable Community Search	PVLDB 19(2), VLDB 2026	query vertex를 포함하며 가장 오래 유지되는 temporal durable community를 탐색. binary-search online + 2 indexes.	공개 artifact	High	3 temporal graphs, q=50–100, k=3–6
Efficient Densest Flow Queries	TKDE 38(7), 2026-07-01	S–T densest-flow를 정의하고 divide-and-conquer CONAN + approximate flow-peeling 제안.	공식 code artifact 미확인	Medium	synthetic + small NFT graph, exact-small/peeling/CONAN-style

Part III · M3 feasibility

High와 Medium을 가르는 것은 논문 난이도가 아니다

재현성은 알고리즘보다 종종 implementation contract에 의해 결정된다.

Code availability

공개 코드가 있고 build path가 단순할수록 두 시간 실험은 안정적이다. ABFlow의 C++20 구조는 이 점에서 유리하다.

Runtime knob

sampling budget, window size, query count처럼 비용을 직접 조절할 수 있으면 시간 제한을 실험 설계에 포함할 수 있다. AGIS가 대표적이다.

Architecture friction

x86 AVX2/AVX512에 강하게 묶인 구현은 Apple Silicon에서 그대로 재현하기 어렵다. TVA가 좋은 예다.

\(T_{build}+T_{baseline}+T_{proposed}+T_{ablation}+T_{repeat}\;\leq\;120\text{ minutes}\)

이 식은 논문의 성능식을 흉내 낸 것이 아니다. 실험 관리 규칙이다. 두 시간 예산을 만족하려면 main result만이 아니라 baseline, ablation, 반복 측정까지 모두 예산 안에 들어와야 한다. ‘한 번 빨리 실행됐다’는 것은 재현 가능한 실험이 아니다.

핵심 판단: 이번 실행에서 우선순위가 가장 올라간 것은 AGIS와 ABFlow다. AGIS는 sample budget이 곧 runtime knob이고, ABFlow는 공개 C++20 구현이 간결하며 GPU 의존성이 없다. 반대로 TVA는 논문 아이디어는 강하지만 AVX2/AVX512 중심 구현 때문에 M3에서는 drop-in reproduction보다 ARM-friendly redesign이 더 흥미로운 후속 연구가 된다.

Part IV · Deep read

논문별로 무엇을 검증해야 하는가

원 논문의 모든 표를 복제하지 않는다. contribution을 가장 적은 실험으로 공격한다.

01 / BGP

Worst-Case Optimal BGPs on Temporal Graphs

PVLDB 19(11) · 2026 · arXiv 2026-07-22

Source factTemporal labeled graph의 BGP를 O(N) 공간 index와 temporal Leapfrog Triejoin으로 평가하고, snapshot·version·order-relation query를 같은 index에서 지원한다.

Analysis핵심 병목은 계산량보다 구현 재현성이다. 공개 구현을 확인하지 못했기 때문에 새 시스템을 처음부터 구현해야 할 가능성이 있다.

M3 experiment1–5M edge temporal RDF를 만들고, 20–50개 BGP에 대해 단순 time-filter+join과 temporal LFTJ형 구현을 비교한다. index build와 query latency만 보면 Medium 수준으로 가능하다.

02 / TVA

TVA: A Version-aware Temporal Graph Storage System for Real-time Analytics

PVLDB 19(10) · 2026

Source factversion metadata와 property value를 분리하고 temporal table, hopscotch hashing, version-skipping을 결합한다. 원 논문은 최대 9.9× query-latency 개선을 보고한다.

Analysis공개 artifact는 강점이지만 Ubuntu와 AVX2/AVX512를 전제로 한 구현은 Apple Silicon에서 그대로 실행하기 어렵다. 여기서 portability가 연구 변수가 된다.

M3 experimentSIMD를 비활성화하거나 NEON으로 치환하고 mgBench 10K vertices, 121K edges만 사용해 version lookup과 1-hop/2-hop scan을 비교한다. full reproduction보다 ARM-aware redesign이 더 가치 있다.

03 / ABF

ABFlow: Alert Bursting Flow Query in Streaming Temporal Flow Networks

SIGMOD · 2026

Source factS–T flow의 값과 지속시간의 비율로 burstiness를 정의하고, suffix-flow 문제와 incremental streaming optimization으로 실시간 이상 흐름을 찾는다. 공개 C++20 구현과 sample data가 있다.

Analysis이 유형은 M3에 잘 맞는다. 학습 단계가 없고, query/update workload가 명시적이며, 구현 자체가 단순한 compiler toolchain으로 닫힌다.

M3 experimentsample과 공개 transaction stream 하나를 택해 update-rate 3수준 × window 3수준을 만들고 baseline/incremental을 3회 반복한다. 30–70분짜리 compact benchmark로 설계할 수 있다.

04 / AGIS

AGIS: Fast Approximate Graph Pattern Mining with Structure-Informed Sampling

PVLDB 19(2) · VLDB 2026 Research Track

Source factuniform sampling 대신 pattern structure에서 유도한 sampling distribution을 사용하고, 비균일 sampling을 언제 쓰는 편이 이득인지 overhead–convergence trade-off까지 판단한다. 원 논문은 평균 28.5× speedup을 보고한다.

Analysis이번 주 가장 실험하기 좋은 후보다. 계산비용을 sample 수로 직접 통제하면서 accuracy–runtime curve를 만들 수 있기 때문이다.

M3 experiment100K–5M edge급 graph 3개와 triangle, 4-cycle, 4-clique 등 3–4 pattern을 골라 uniform vs structure-informed sampling을 비교한다. 45–90분의 실험 예산으로도 핵심 메시지를 검증할 수 있다.

05 / DUR

Effective Durable Community Search in Large Temporal Graph

PVLDB 19(2) · VLDB 2026

Source fact일반 temporal k-core가 ‘얼마나 오래 유지되는가’를 충분히 반영하지 못한다는 문제에서 출발한다. query vertex를 포함하면서 지속시간이 최대인 Temporal Durable Community를 정의하고 binary-search online algorithm과 두 종류의 index를 제안한다.

Analysisindex build는 한 번만 수행하고 query를 많이 던질 수 있기 때문에 단일 머신의 짧은 실험에 유리하다.

M3 experimentCollegeMsg, Email, MathOverflow급 세 데이터에서 query vertex 50–100개, k=3–6을 sweep한다. index build를 amortize하면 두 시간 조건과 잘 맞는다.

06 / FLOW

Efficient Densest Flow Queries in Transaction Flow Networks

IEEE TKDE 38(7) · 2026-07-01

Source factS–T densest-flow를 정의하고 NP-hard 문제에 divide-and-conquer CONAN과 approximate flow-peeling을 적용한다. 금융사기와 NFT flow 분석을 사례로 사용한다.

Analysis반복 max-flow가 병목이며, 공식 code artifact는 이번 추적에서 확인하지 못했다. 따라서 원 논문 full reproduction은 두 시간 조건에 불리하다.

M3 experimentsynthetic graph와 공개 NFT 중소 graph만 사용하고 k를 3수준으로 제한한다. exact-small, peeling, CONAN-style 세 방식만 비교해 핵심 아이디어를 검증한다.

Part V · Research opportunity

가장 좋은 후속 주제는 AGIS와 temporal motif 사이에 있다

sampling을 빠르게 만드는 데서 멈추지 말고, 사용 가능한 시간 자체를 질의 조건으로 취급한다.

이번 추적을 연구주제로 바꿀 때 가장 매력적인 후보는 Budget-Aware Structure-Informed Temporal Graph Pattern Sampling이다. AGIS의 structure-informed sampling을 temporal motif 또는 partial-order motif로 확장하고, 사용자가 전체 계산예산을 지정하면 confidence bound가 만족되는 순간 sampling을 종료하게 만든다.

핵심은 ‘120분 안에 끝내기’가 실험실 운영 편의가 아니라 algorithmic objective가 된다는 점이다. 동일한 pattern이라도 graph density, temporal burstiness, motif selectivity에 따라 좋은 sampling distribution과 종료 시점이 달라진다. 그러므로 시스템은 실행 중에 분산과 cost를 추정해 다음 sample의 가치를 판단해야 한다.

Research question

부분순서 temporal motif를 total-order expansion으로 전개하지 않고 structure-aware sampling으로 직접 추정할 수 있는가?

Systems question

정확도–시간–메모리의 3-way cost model로 sample allocation과 early stopping을 함께 결정할 수 있는가?

Evaluation

uniform sampling, AGIS-style sampling, temporal-tree sampling을 error–runtime–memory 관점에서 비교한다.

M3 advantage

대규모 GPU 없이도 sampling budget을 통해 모든 실험의 총 wall-clock을 강하게 통제할 수 있다.

판단: AGIS는 ‘무엇을 더 자주 샘플링할 것인가’를 다루고, temporal motif 연구는 ‘어떤 시간 순서가 의미 있는가’를 다룬다. 둘 사이에는 아직 계산 예산을 1급 제약으로 다루는 빈 공간이 있다. 이 공간이 M3 128GB 연구의 약점이 아니라 차별점이 될 수 있다.

Part VI · Next watch

다음 추적에서 봐야 할 것

논문 제목보다 artifact와 발표자료가 연구 가능성을 더 크게 바꿀 수 있다.

VLDB 2026이 바로 이어지는 시점이므로 다음 추적에서는 R34 “Temporal Graph Analytics”와 R48 “Dynamic Graphs and Graph Learning” 발표 이후의 변화를 우선 확인할 필요가 있다. 특히 논문 저자들이 slide, code, benchmark configuration, reproducibility artifact를 추가 공개하는지가 중요하다.

또한 TVA와 같이 x86 SIMD에 의존하는 시스템은 Apple Silicon에서 단순히 ‘재현이 어렵다’고 끝내기보다, ARM NEON 또는 architecture-neutral bitset/columnar representation으로 옮겼을 때 어떤 성능 특성이 나타나는지 보는 편이 더 생산적이다. portability 자체가 system design의 연구 질문이 될 수 있기 때문이다.

ABFlow는 반대로 코드가 단순하다는 사실이 장점이다. compact experiment를 먼저 수행하고 workload-adaptive window, burst score calibration, approximate suffix-flow 같은 작은 변형을 붙이면 짧은 주기로 아이디어를 검증할 수 있다. AGIS는 sample budget과 error bound를 직접 조절할 수 있어 2시간 제약을 가장 자연스럽게 흡수한다.

다음 논문을 기다리는 것보다, 이미 공개된 논문에서 ‘어디까지가 원 논문의 결과이고 어디부터가 우리가 검증할 수 있는 새 질문인가’를 가르는 일이 더 중요하다.

Part VII · References