Modularity maximization and community detection in complex networks through recursive and hierarchical annealing in the D-Wave Advantage quantum processing units

기술 요약: D-Wave에서의 재귀적 계층적 어닐링을 통한 모듈성 극대화 및 커뮤니티 탐지

문제 정의
복잡한 네트워크에서의 커뮤니티 탐지는 네트워크 과학의 근본적인 문제로, 일반적으로 모듈성 지수($Q$)를 극대화하는 문제로 정식화된다. 이 최적화 작업은 NP-hard 문제이다. 고전적인 휴리스틱 알고리즘(예: Louvain, Leiden)이 존재하지만, 이들은 전역 최적해(global optima)를 보장하지 못한다. 양자 어닐링(QA)은 에너지 지형의 전역 최솟값을 찾음으로써 이러한 NP-hard 문제를 해결할 수 있는 잠재적인 경로를 제공한다. 그러나 순수 QA를 커뮤니티 탐지에 적용하는 데 있어 주요한 장벽은 문제의 인코딩 방식에 있다. 표준적인 접근 방식은 $M$개의 커뮤니티를 표현하기 위해 $N \times M$개의 이진 변수를 사용하는 "원-핫(one-hot)" 인코딩에 의존하는 경우가 많다. 이는 하드 제약 조건(각 노드가 정확히 하나의 커뮤니티에 속해야 함)을 필요로 하며, 이는 일반적으로 라그랑주 승수(Lagrange multipliers)를 통해 강제된다. 이러한 승수의 페널티 가중치를 튜닝하는 것은 경험적으로 매우 어렵고 종종 문제별 추측을 필요로 하며, 이는 양자 프로세스를 가릴 수 있고 확장성을 제한할 수 있다. 또한, 기존의 하이브리드 양자-고전 솔루션들은 클래식 프로세서와 양자 프로세서 간의 역할 분담에 대한 투명성이 부족한 경우가 많다.

방법론
저자들은 D-Wave Advantage QPU 상에서 원-핫 인코딩이나 라그랑주 승수 없이 순수 양자 어닐링을 사용하여 모듈성 극대화를 설계한 새로운 알고리즘인 **계층적 어닐링(Hierarchical Annealing)**을 제안한다.

• 재귀적 이진 분해 (Recursive Binary Decomposition): 노드들을 동시에 $M$개의 커뮤니티로 할당하는 대신, 이 알고리즘은 네트워크를 재귀적으로 세분화한다. 전체 네트워크를 하나의 커뮤니티로 시작하여, 각 커뮤니티를 두 개의 하위 커뮤니티로 반복적으로 분할한다. 이는 문제를 일련의 제약 없는 이진 최적화 문제로 변환한다.
• QUBO 정식화:
  • **무방향 네트워크(Undirected networks)**의 경우, 커뮤니티 $k$를 $k_1$과 $k_2$로 분할할 때의 모듈성 이득은 QUBO 문제로 매핑된다. 비용 함수는 일반화된 모듈성 행렬 $B^k$로부터 유도되며, 여기서 목표는 음의 모듈성 변화량($p_k = -[Q(C_{k+1}) - Q(C_k)]$)을 최소화하는 것이다.
  • **유방향 네트워크(Directed networks)**의 경우, 저자들은 모듈성 행렬의 비대칭성을 해결하기 위해 대칭화된 선형 결합 $\frac{1}{2}(p_k + p^\top_k)$를 최적화한다. 이는 계층 구조의 첫 단계가 올바른 전역 함수를 최적화하도록 보장하며, 선형 항 없이 QUBO 정식화를 유지한다.
• 해상도 파라미터 ($\gamma$): 탐지된 커뮤니티의 규모를 제어하는 해상도 파라미터 $\gamma$는 일반화된 모듈성 행렬 계산에 직접 통합된다. 알고리즘은 최적화 구조 측면에서 $\gamma$로부터 형식적으로 독립적이므로, 이를 자유 파라미터로 취급할 수 있다.
• 실행 흐름 (Execution Flow): 프로세스는 재귀적으로 실행된다(알고리즘 1). 각 단계마다 일반화된 모듈성 행렬이 계산되고, QUBO가 구성되며, 캐시에서 클리크 임베딩(clique embedding)이 로드된다. D-Wave 샘플러는 이진 QA를 수행하여 최적의 분할을 찾는다. 분할이 개선을 가져오지 않거나(모듈성 변화가 0) 빈 집합을 생성할 경우 재귀는 중단된다.
• 구현: 저자들은 D-Wave 생태계와 인터페이스하는 파이썬 라이브러리인 Qommunity를 개발했다. 이들은 기본 체인 강도 전략과 끊어진 체인에 대한 다수결 투표를 사용하는 Advantage 시스템(Pegasus 토폴로지, 차수 16)을 활용했다.

주요 기여

1. 제약 없는 순수 양자 어닐링: 본 연구는 원-핫 인코딩과 그에 따른 라그랑주 승수 튜닝의 어려움을 우회하여, 순수 어닐러만을 사용하여 모듈성 극대화를 위한 전역 최적해를 찾는 체계적인 절차를 입증한다.
2. 일반화된 정식화: 저자들은 무방향, 유방향 및 가중치 네트워크를 단일 재귀 프레임워크 내에서 처리할 수 있도록 모듈성 극대화 정식화를 확장했다.
3. 해석 가능성: "블랙박스" 형태의 하이브리드 솔버와 달리, 이 알고리즘의 재귀적 특성은 중간 분할 과정을 보여주는 덴드로그램(dendrogram)을 생성한다. 이는 네트워크 구조가 다양한 해상도 수준에서 어떻게 펼쳐지는지를 보여주는 해석 가능한 뷰를 제공한다.
4. 확장성 및 효율성: 본 연구는 이 접근 방식이 최신 클래식 알고리즘(Louvain, Leiden)만큼 혹은 그 이상의 최적해를 제공하면서도 다룰 수 있는 계산 시간을 유지한다는 경험적 증거를 제공한다.

결과

• 벤치마킹: 알고리즘은 Erdős-Rényi, Barabási-Albert, power-law clustered 네트워크, 유방향 scale-free 네트워크를 포함한 다양한 네트워크 토폴로지에서 테스트되었다.
  • 단순 3-클리크 체인과 Zachary Karate Club 네트워크에서, 계층적 어닐링(H. Annealing)은 Louvain 및 Leiden과 동일하거나 약간 높은 모듈성 점수를 달aba achieved 했다.
  • 확률적 블록 모델(SBM)에서, 이 방법은 다양한 혼합 파라미터에 걸쳐 심어진(planted) 커뮤니티를 성공적으로 복구하였으며, 확률적 추론 방법들과 경쟁력 있는 성능을 보였다.
  • Scale-free 네트워크의 경우, 알고리즘은 견고한 성능을 보였으며, 특히 내재된 계층 구조가 존재할 때 모듈성 점수 측면에서 클래식 대응 모델을 능가하는 경우가 많았다.
• 해상도 민감도: 알고리즘은 해상도 파라미터 $\gamma$의 다양한 값에 대해 안정성을 유지했다. 유방향 네트워크에서 극단적인 $\gamma$ 값에 대해 성능이 약간 저하되기는 했으나, $\gamma=1$ 근처에서는 경쟁력을 유지했다.
• 계산 복잡도:
  • 클래식 전처리(모듈성 행렬 계산)는 $O(n^2)$로 스케일링된다.
  • 재귀적 트리 복잡도는 균형 잡힌 분할을 가정할 때 Akra-Bazzi 정리에 따라 $O(n \log n)$으로 추정된다.
  • 경험적으로, QPU 액세스 시간은 네트워크 크기에 따라 로그 함수적으로 스케일링되었다($t \propto \ln N$), 이는 양자 컴포넌트의 효율적인 스케일링을 시사한다.
  • 총 실행 시간은 QPU 실행 시간 자체보다는 통신 및 큐잉 오버헤드에 의해 결정된다.
• 실제 응용: 이 방법은 실제 뇌 구조 연결 네트워크(166개 노드)에 적용되었다. 결과로 도출된 커뮤니티 구조와 덴드로그램은 Louvain 및 Leiden과 매우 일치하였으며, 미세한 차이는 오직 고도로 연결된 전두-두정엽 경계에서만 나타났다.

의의 및 주장
본 논문은 이 작업을 "순수 양자 어닐링의 적용 가능한 실무적 사용을 향한 첫 걸음"으로 규정한다. 저자들은 순수 QA가 하이브리드 "블랙박스" 솔루션이나 복잡한 제약 조건 튜닝에 의존하지 않고도 커뮤니티 탐지 문제를 해결할 수 있음을 입증함으로써 네트워크 과학과 양자 컴퓨팅 사이의 간극을 메운다고 주장한다.

그 의의는 다음과 같다:

• 투명성: 단일한 평면적 분할이 아닌, 해석 가능한 재귀적 솔루션(덴드로그램)을 제공함으로써 뇌 네트워크와 같은 복잡한 시스템의 숨겨진 계층 구조를 밝히는 데 가치를 더한다.
• 실행 가능성: 현재의 양자 하드웨어(D-Wave Advantage)가 (Pegasus 토폴로지에 의해 제한되지만) 실용적인 크기(테스트된 약 166개 노드까지)의 커뮤니티 탐지 작업을 경쟁력 있는 성능으로 처리할 수 있음을 보여준다.
• 방법론적 전환: 페널티 가중치의 경험적 튜닝을 피하는 원-핫 인코딩의 대안을 제시하여, 양자 최적화를 네트워크 분석에 더욱 접근하기 쉽게 만든다.

저자들은 재귀적 과정이 전역 최적해를 보장하지는 않는다는 점(이는 모든 휴리스틱이 공유하는 NP-hard 문제의 한계임)을 인정하며 겸허한 태도를 유지한다. 또한, 매우 큰 네트워크로의 확장성을 위해서는 통신 오버헤드를 완화하기 위한 하이브리드 솔버나 로컬 QPU 액세스가 필요함을 언급하며, 이들이 모든 맥락에서 클래식 방법보다 우월하다고 주장하는 것이 아니라 특정 토폴로지 맥락에서 의미 있고 해석 가능한 최적의 솔루션을 제공할 수 있는 양자 어닐링의 잠재력을 강조하고 있음을 명시한다.