변화하는 그래프,
재현 가능한 연구

2026년 9월 28일 기준으로 의미 있는 업데이트가 있다. 지난 확인에서는 ICDE 2027 Round 1 결과 발표일(9월 10일)은 지났지만 공식 accepted-paper 목록이 공개되지 않아 graph 논문을 확정하지 못했는데, 이번에는 저자·연구실 공개 페이지를 통해 ICDE 2027 채택이 확인되는 graph 논문들이 나타났다. ICDE 공식 일정상 Round 1 결과는 9월 10일, camera-ready는 10월 10일이며, 현재 공식 홈페이지에는 아직 전체 accepted-paper 목록이 게시되지 않았다.

이번 실행에서 가장 중요한 신규 연구 신호다. CUHK-Shenzhen SDS Theory Group이 이 논문의 ICDE 2027 채택을 공식적으로 공개했고, 저자 개인 페이지에서도 ICDE 2027 논문으로 확인된다.

문제는 기존 maximum quasi-clique 알고리즘이 대부분 정적 graph를 가정한다는 점이다. edge가 계속 삽입·삭제되는 상황에서 매 update마다 quasi-clique를 처음부터 다시 찾으면 비용이 지나치게 크다. 이 논문은 이를 **Dynamic Maximum Quasi-Clique Problem(DMQCP)**으로 처음 명시적으로 정의하고, edge insertion/deletion 이후 최대 \(\alpha\)-quasi-clique를 근사적으로 유지한다.

핵심 방법 DMI는 두 가지 update-friendly MinHash, 즉 \(l\)-buffered \(k\)-MinHash와 Bottom-\(k\) MinHash를 이용해 vertex neighborhood similarity signature를 증분 유지한다. 각 edge update에서 관련 vertex의 hash signature와 degree만 갱신하고 candidate quasi-clique 목록을 수정하며, 누적 오차와 bias를 막기 위해 일정 주기마다 batch reconstruction을 수행한다. 별도의 neighbor-search 기반 NSF도 비교 framework로 제안한다. 저자들은 real/synthetic graph에서 static baseline 대비 최대 4 orders of magnitude의 속도 향상을 보고하면서 solution quality를 유지한다고 밝혔다.

기존 연구 대비 가장 중요한 기여는 단순히 quasi-clique 탐색을 빠르게 만든 것이 아니라, static quasi-clique extraction을 fully evolving graph maintenance 문제로 전환한 최초의 체계적 framework라는 점이다. 논문 자체도 기존 dynamic clique 연구와 달리 dynamic \(\alpha\)-quasi-clique maintenance는 다뤄지지 않았다고 명시한다.

코드는 이미 공개돼 있다. 논문 본문이 공개 artifact를 직접 연결한다.
논문 원문 — arXiv
공개 코드 artifact

M3 128GB 재현 가능성: High. 이 방법의 핵심은 GPU 학습이 아니라 hash signature, neighborhood update, candidate maintenance이므로 Apple Silicon과 구조적으로 잘 맞는다. 예상 병목은 고차수 vertex의 neighborhood signature 갱신과 주기적인 candidate-list reconstruction이다.

2시간 축소 실험은 real graph 1–2개만 사용해 initial edge의 5–10%를 update stream으로 분리하고, static recomputation → NSF → DMI/Buffered-MinHash → DMI/Bottom-k를 비교하는 것이 좋다. \(\alpha=\{0.8,0.9\}\), update batch 크기 2–3종, 1–5만 edge insertion/deletion 정도면 충분하다. 측정 항목은 update latency, total throughput, 반환 quasi-clique 크기·density, reconstruction 횟수, peak RSS다. 목표 budget은 대략 60–100분으로 잡을 수 있다.

이 논문에서 바로 파생되는 유망 주제는 Adaptive Reconstruction DMI다. 고정된 update 횟수마다 rebuild하지 않고, MinHash signature drift와 candidate-quality degradation을 추정해 reconstruction 시점을 결정하는 방식이다. 이 경우 “정확도–update 비용–rebuild 비용”이라는 명확한 DB/graph systems trade-off를 만들 수 있다.

Hao Zhang의 publication page에서 ICDE 2027 to appear 논문으로 새로 확인된다. SQL/PGQ는 SQL 안에서 property-graph pattern을 질의하기 위한 표준 방향이므로, 이 논문은 관심 연구축인 graph query optimization과 매우 직접적으로 연결된다.

현재 공개 검색에서는 아직 full paper나 artifact를 찾지 못했다. 따라서 알고리즘의 내부 구조나 성능수치를 추측하지 않는 것이 정확하다. 제목에서 안전하게 확인할 수 있는 핵심은 relational SQL 연산과 PGQ graph 연산을 분리된 두 단계로 최적화하는 대신, cost-based 방식으로 interleaved plan을 생성하는 문제를 대상으로 한다는 점이다. 이는 graph–relational hybrid query에서 intermediate-result explosion을 줄일 수 있는 중요한 문제 설정이다.

M3 재현 가능성: 잠정 High. query optimizer 연구는 보통 최대 데이터 규모보다 plan quality와 intermediate cardinality가 핵심이므로 작은/중간 graph에서도 contribution을 검증할 수 있기 때문이다. 가장 큰 불확실성은 아직 implementation/artifact가 공개되지 않았다는 점이다.

artifact 공개 후에는 graph dataset 2개, mixed SQL/PGQ query 10–20개만 사용해 separated planning ↔ interleaved planning을 비교하면 좋다. 각 query는 30초 timeout을 두고 planning time, execution time, intermediate tuple/cardinality, chosen join ordering을 기록한다. 전체 60–90분 실험으로 충분히 논문의 핵심 optimizer 주장을 검증할 가능성이 높다.

ICDE 2027 publication record — Hao Zhang

같은 publication page에서 Vora도 ICDE 2027 to-appear 논문으로 새로 확인됐다. 제목상 핵심 문제는 subgraph query processing을 vector-based execution + GPU acceleration으로 확장하는 것이다.

그러나 아직 full paper나 public code가 검색되지 않았으므로 어떤 candidate-filtering, join ordering, GPU kernel structure를 사용하는지는 현재 단계에서 단정할 수 없다.

M3 128GB 재현 가능성: Low — 원 논문 방식의 faithful reproduction 기준. 이유는 RAM이 아니라 GPU backend portability다. 논문 구현이 CUDA/NVIDIA 전용이면 M3 GPU에서 실행 자체가 불가능하며, Metal/MPS로 다시 구현하면 그것은 원 artifact 재현보다 porting 연구에 가깝다.

artifact가 portable backend를 제공할 경우에만 triangle, 4-cycle, house 등 작은 pattern과 수백만 edge 이하 graph를 사용해 CPU → vector CPU → portable GPU의 세 구성을 30–60분 정도 비교하는 것이 현실적이다. CUDA-only이면 M3에서는 CPU reference execution만 확인하고 재현성은 Low로 유지하는 것이 타당하다.

Vora publication record — Hao Zhang

PolyU ASTAPLE Lab이 2026년 9월 11일 ICDE 2027 채택을 발표했으며, 저자 Qingqing Ye의 publication page에서는 저자가 Xinyue Li, Qingqing Ye, Haibo Hu임이 확인된다.

제목에서 확인되는 연구문제는 시간에 따라 진화하는 graph에서 community detection을 수행하면서 Local Differential Privacy를 보장하는 것이다. 이는 dynamic graph 구조가 변할 때 매 snapshot마다 독립적으로 privacy noise를 넣으면 utility가 급격히 저하될 수 있다는 문제와 연결된다. 다만 아직 abstract/full paper가 공개되지 않아 “evolution-aware”가 어떤 statistic이나 incremental mechanism을 사용하는지는 현재로서는 확인할 수 없다.

M3 재현 가능성: 잠정 Medium. GPU가 필수라는 증거는 없고 community detection 자체는 CPU에서 가능하지만, privacy-budget sweep × snapshots × baselines의 조합이 많아지면 2시간을 쉽게 넘을 수 있다.

논문 공개 후에는 중소 dynamic graph 1–2개, snapshot 10–20개, privacy budget \(\epsilon\) 3개 정도로 제한하고 community quality(NMI/modularity 계열), runtime, temporal stability, peak memory만 비교하는 구성이 적합하다. 전체 실험을 60–110분으로 제한할 수 있을 가능성이 있다.

LG-DCD 채택 발표
저자 publication record

이번 확인의 핵심은 ICDE 2027 Round 1에서 M3 친화적인 graph-algorithm 축이 실제로 나타나기 시작했다는 점이다. 특히 Dynamic Quasi-clique Detection은 논문과 코드가 모두 공개되어 있기 때문에 현재 즉시 실험 가능한 신규 후보이며, M3 128GB·2시간 조건에서는 이번 주 최우선 후보로 평가한다.

반면 SIGMOD 2027 공식 accepted-paper 페이지는 현재도 공개 검색상 Round 1 목록 중심이며, 지난 실행에서 다룬 ASC, density decomposition, Tree+DAG, temporal community 등의 기존 항목 외에 이번 실행에서 새로 추가해 보고할 graph-specific 논문은 확인하지 못했다. VLDB/PVLDB 2026 역시 9월 4일 종료된 공식 프로그램에서 지난 실행 이후 새 graph paper 추가는 확인되지 않았고, IEEE TKDE에서도 이번 기간에 사용자가 우선 지정한 graph systems/algorithms 범주에서 새로 보고할 만한 항목은 확인되지 않았다.