정확한 위상 준수: 영속성 동등 그래프 생성

영속적 호몰로지(Persistent homology)는 그래프의 위상학적 진화를 영속성 다이어그램(PDs, persistence diagrams)으로 요약합니다. 목표 기술자(target descriptor)와 위상이 일치하는 그래프를 생성하는 것은 점점 더 중요해지고 있지만, 기존의 위상 인식 생성 모델들은 소프트 정규화(soft regularization)에 의존하여 PD가 근사적으로만 유사한 그래프를 생성하는 경향이 있습니다. 우리는 이 생성 문제에 대한 원칙적인 조사를 시작합니다: 목표 PD를 정확하게 실현하는 그래프를 생성하는 것입니다. 우리는 목표 PD가 부과하는 암묵적 국소 및 전역 제약 조건에 의해 안내되는 두 가지 접근 방식을 제안합니다. 국소적 접근 방식은 차수 기반(degree-based)의 PD 동등 그래프를 반복적으로 구축하며, 모든 출력물이 목표 PD를 실현하고 모든 차수 기반 PD 동등 그래프가 도달 가능하다는 것을 증명합니다. 하지만 이후에 보여주듯이, 국소적 생성은 표본 다양성(sample diversity)과 비실현 가능한 상태에 도달하는 것 사이에서 필연적으로 상충 관계를 가집니다. 따라서 우리는 생성을 완전한 인코딩을 가진 전역 제약 만족 문제(global constraint satisfaction problem)로 재구성하며, 이는 현대의 제약 프로그래밍 솔버(constraint programming solvers)로 해결할 수 있습니다. 이는 모든 정점 기반 순열 동변 필터링 방식(vertex-based permutation equivariant filtration scheme)에 적용 가능하며 차수 필터링 하에서 최소입니다. 네 가지 표준 그래프 생성 벤치마크에서의 실험은 두 방법 모두가 목표 PD를 정확하게 실현함을 확인시켜 줍니다. 종합적으로, 우리의 방법들은 엄격한 위상 준수 그래프 생성에 대한 원칙적인 처리를 제공합니다. 코드는 https://github.com/Aalto-QuML/ExactCompliance에서 이용 가능합니다.