레이블이 없는 임의 그래프의 상관관계 테스트

우리는 n개의 레이블이 없는 노드를 가진 두 임의 그래프 간의 엣지 상관관계를 탐지하는 문제를 연구합니다. 이는 귀무가설 하에서 두 그래프가 독립적으로 생성되고, 대립가설 하에서는 두 그래프가 어떤 잠재적 노드 대응에 따라 엣지 상관관계를 가지지만 귀무가설과 동일한 주변 분포를 가진다고 형식화됩니다. 가우시안 가중 완전 그래프와 엣지 확률 n^-o(1)을 가진 조밀한 Erdős-Rényi 그래프에 대해, 우리는 최적 검사 오류 확률이 n에 따라 제로에서 일로 단계 전환하는 날카로운 한계를 결정합니다. 엣지 확률 n^-Ω(1)을 가진 희소한 Erdős-Rényi 그래프의 경우, 우리는 상수 계수 내에서 경계 값을 결정합니다. 불가능성 결과의 증명은 조건부 제곱모멘트 방법의 적용으로, 우리는 관찰된 두 그래프의 엣지를 포함하는 교차 그래프의 전형적인 행동에 주의 깊게 조건 설정하여 우도 비율의 잘린 두 번째 모멘트를 경계합니다. 특히 희소 영역에서는 서브크리티컬 Erdős-Rényi 그래프의 의사 숲 구조와 엣지 순열의 짧은 궤도로부터 조립할 수 있는 서브 의사 숲을 신중하게 열거함으로써 이를 달성합니다.