부분그래프 카운팅은 그래프 구조화 데이터의 이해와 분석에 있어 근본적인 문제이지만, 계산적으로 매우 어렵다. 이에 따라 질의 그래프의 모든 동형 임베딩(isomorphic embeddings) 개수를 데이터 그래프에서 추정하는 부분그래프 차수(Subgraph Cardinality Estimation)를 위한 정확하고 효율적인 알고리즘이 요구된다. 우리는 (1) 표본 공간(sample space)을 크게 줄이기 위한 강력한 필터링 기법, (2) 정확하고 효율적인 추정을 위한 적응형 트리 샘플링(adaptive tree sampling) 알고리즘, (3) 어려운 인스턴스에 대한 최악의 경우(worst-case) 최적화된 층화 그래프 샘플링(stratified graph sampling) 알고리즘을 결합한 새로운 알고리즘 FaST est 를 제안한다. 실제 세계 데이터셋에 대한 광범위한 실험 결과, FaST est 는 정확도 측면에서 기존의 샘플링 기반 최신 방법을 최대 2자릿수(orders of magnitude)까지, 그리고 GNN 기반 방법을 최대 3자릿수까지 능가하는 것으로 나타났다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.