거대한 그래프보다
재현 가능한 핵심을 본다

non-tree constraint는 algebra로, injectivity는 local sampling으로

Source factCandidate-tree 기반 subgraph isomorphism counting은 tree edge는 효율적으로 처리하지만, non-tree edge constraint와 서로 다른 query vertex가 같은 data vertex로 매핑되지 않아야 하는 injectivity constraint 때문에 비용과 정확도가 악화될 수 있다.

ASC는 non-tree constraint를 candidate-tree 계산 내부에 matrix-based algebraic computation으로 직접 넣어 먼저 subgraph homomorphism count를 구하고, 이후 local sampling으로 injectivity를 보정한다. 즉 learning model 없이 algebra + sampling으로 문제를 분해한다.

첨부 자료는 기존 sampling의 sampling failure와 learning-based 접근의 supervision 의존성을 줄이는 점을 핵심 차별점으로 정리한다. 저자들은 billion-edge graph까지 확장했고, learning-based FlowSC와 비슷한 실행 효율에서 평균 정확도가 경우에 따라 한 자릿수 배 이상 높았다고 보고하며 코드도 공개했다.

M3 assessmentHigh. billion-edge scalability는 제외해야 하지만 핵심 contribution은 중소형 graph에서도 검증 가능하다. 예상 병목은 candidate generation, matrix computation, 복잡한 query pattern에서의 intermediate candidate 크기다.

Massive scale을 버려도 scaling behavior는 남길 수 있다

Source factScaling Up Density Decomposition on Massive Graphs는 공식 SIGMOD 목록에서 확인된 신규 graph decomposition 논문이다. 첨부 자료는 저자진이 최근 static/dynamic density decomposition, pseudoarboricity, densest-subgraph 계열을 지속적으로 발표해 온 그룹이며, 제목 자체가 density decomposition의 대규모 확장성을 직접 대상으로 한다고 정리한다.

Evidence boundary현재 공개 검색에서는 full paper나 code artifact를 찾지 못했기 때문에 구체 알고리즘이나 보고된 speedup은 평가하지 않는다.

M3 assessment잠정 High. GPU 학습보다 CPU graph primitive 중심이고, 원 논문의 “massive” scale을 축소하면 알고리즘의 scaling behavior를 작은 데이터에서도 볼 가능성이 높다.

Resistance distance를 core-periphery 구조로 index화한다

Resistance distance는 graph Laplacian 기반의 전역 관계를 측정하기 때문에 exact computation이 일반 shortest path보다 비싸다. Tree+DAG: An Efficient Index for Resistance Distance Computation on Core-Periphery Graphs는 제목상 core-periphery structure를 Tree + DAG representation으로 분해해 resistance-distance query를 index화하는 방향이다.

첨부 자료는 같은 연구진이 SIGMOD 2025에서 evolving graph용 effective-resistance index maintenance, SIGMOD 2026에서 small-treewidth graph의 exact resistance-distance labeling을 연구했기 때문에 이번 논문을 그 연속선상으로 본다.

Evidence boundaryfull paper/code가 공개 검색에서 확인되지 않아 Tree와 DAG를 정확히 어떻게 구성하는지는 추정하지 않는다.

M3 assessment잠정 High. 작은/중간 graph에서 index-build/query trade-off를 비교하기 좋다.

2시간 제한에서는 query count보다 timeout budget이 중요하다

Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs는 새로운 cohesive subgraph query 논문이다. 공식 제목에서 maximum connectivity와 quasi-clique 조건을 결합하는 문제임이 확인된다. 첨부 자료는 연구진의 SIGMOD 2026 temporal cohesive-subgraph querying 및 size-bounded community search와 직접 연결되는 graph-mining 계열로 본다.

Evidence boundary현재 preprint나 artifact가 확인되지 않아 pruning rule, complexity, dataset, speedup은 구체적으로 서술하지 않는다.

M3 assessment잠정 Medium. quasi-clique search는 threshold에 따라 candidate 공간이 급증할 수 있어 2시간 보장이 density decomposition보다 어렵다.

방법을 아는 척하지 않는 것이 현재로서는 더 정확하다

Effective Structurally Similar Community Search in Large Temporal Graphs는 이번 신규 목록에서 temporal graph와 community search를 직접 결합하는 논문이다.

Evidence boundary아직 full paper나 공개 코드가 검색되지 않아 temporal similarity definition, index 구조, incremental strategy는 확인할 수 없다. 첨부 자료는 이전 temporal-core/community 논문의 기법을 이번 논문의 방법이라고 추정해서는 안 된다고 명확히 선을 긋는다.

M3 assessment잠정 Medium. community-search query 자체는 중소형 temporal graph에서 실행 가능할 가능성이 높지만 similarity 계산이나 대규모 temporal index construction이 병목일 수 있다.

순차 dependency를 병렬화할 수 있는가

Break Iteration Barrier: Parallelize Priority-Based Graph Processing은 priority-based iterative graph processing의 순차 dependency를 깨고 병렬화하는 연구라는 점이 공식 목록에서 확인된다. 첨부 자료는 shortest path, core-like iterative processing, priority-driven propagation처럼 iteration ordering이 성능을 좌우하는 graph algorithm과 연결될 가능성을 언급하지만, full paper가 없으므로 구체 대상 알고리즘을 단정하지 않는다.

M3 assessment잠정 Medium. M3 CPU core로 parallel speedup 방향은 볼 수 있지만, 원 논문이 many-core x86을 목표로 한다면 절대 scaling은 재현하기 어렵다.

현재 조건에서의 실행 우선순위

1. ASC — High. 논문과 코드가 모두 공개되어 바로 실험 시작 가능.
2. Density Decomposition — High(잠정). CPU graph primitive 중심으로 축소 재현 가능성이 높지만 artifact를 기다려야 함.
3. Tree+DAG — High(잠정). build/query trade-off가 선명해 축소 benchmark에 적합하지만 세부 방법 미공개.
4. Temporal Structurally Similar Community Search — Medium(잠정). 관심축과 직접 맞지만 similarity/index 정의 공개가 우선.

첨부 자료가 제시하는 가장 중요한 두 연구 신호는 ASC와 Tree+DAG / Density Decomposition 계열이다.

AITTI는 graph-specific은 아니지만 temporal index 설계에 유용하다

SIGMOD 2027 공식 페이지에는 AITTI: Augmented Interval Tree for Temporal Indexing도 새로 올라와 있다. 첨부 자료에 따르면 이 논문은 2026년 9월 PACMMOD 4(4) 논문이며 C++/Boost artifact와 run.sh까지 공개되어 M3 재현성은 매우 높다.

다만 graph-specific 논문이 아니라 일반 temporal/versioned data index이므로 이번 graph watch 본 목록에서는 제외했다. temporal-graph interval index를 설계할 때는 인접 연구로 유용하다.

재현성은 scale을 줄이는 일이 아니라 주장 구조를 보존하는 일이다

이 watch가 제시하는 실험 전략은 공통적이다. 원 논문의 가장 큰 graph를 따라가는 대신 핵심 비교축을 유지하고, dataset·pattern·threshold·thread 수를 제한하며, wall-clock과 memory를 함께 측정한다.