Is star complexity a proxy for information based complexity of graphs?

기술 요약: 그래프의 정보 기반 복잡도에 대한 대리 지표로서의 스타 복잡도(Star Complexity)

문제 정의
본 논문은 그래프의 구조적 척도인 "스타 복잡도(star complexity)"가 "정보 기반 복잡도(Information-Based Complexity, IBC)"의 실용적인 대리 지표(proxy) 역할을 할 수 있는지 조사한다. IBC는 분류기를 통해 주어진 객체로 매핑되는 특정 언어 내 기술(description)의 비율로 정의되는 형식적 복잡도 척도이다. 이론적 IBC(유니버설 튜링 머신 기반)는 인코딩 언어와 점근적으로 독립적이지만, 본 논문은 서로 다른 인코딩 체계에서 유도된 실용적 IBC 측정치들 또한 점근적으로 동등할 것이라는 가설을 세운다. 구체적으로, 본 연구는 에지 리스트(edge list)를 통해 그래프를 인코딩하고 오토모피즘(automorphism)에 의해 분류하는 표준 그래프 IBC 측정치($C$)와, 기초적인 "스타(star)"들의 합집합 및 교집합 연산을 사용하여 그래프를 구축하는 데 필요한 최소 연산 횟수로 정의되는 스타 복잡도를 비교한다.

연구 방법론
본 연구는 두 가지 구별되는 복잡도 척도를 사용하는 비교 경험적 접근 방식을 채택한다:

1. 그래프 복잡도 ($C$): $C(x) = \ell - \log_2 \omega(x)$ 공식을 사용하여 계산된다. 여기서 $\ell$은 에지 리스트 인코딩의 길이이며, $\omega$는 동일한 그래프로 매핑되는 해당 길이의 문자열 개수이다(Nauty 라이브러리를 사용한 그래프 오토모피즘 알고리즘을 통해 결정됨).
2. 스타 복잡도 ($Star(G)$): 기초적인 스타(하나의 허브 정점이 나머지 모든 정점과 연결된 형태)의 집합 연산(합집합/교집합)을 통해 그래프를 생성하는 데 필요한 최소 연산 횟수로 정의된다.
3. 스타 기반 IBC ($C^*$): 스타 복잡도로부터 특별히 유도된 IBC 측정치이다. 이는 정점 수, 스타 수, 그리고 연산의 역 폴란드 표기법(Reverse Polish Notation, RPN) "레시피"를 저장하여 그래프를 인코딩한다. $C^*$는 동일한 그래프에 대해 동등한 레시피의 개수인 $\omega$를 차감함으로써 이 레시피의 비트 길이를 조정한다.
4. 상한 추정치 ($\overline{Star}(G)$): 정확한 $Star(G)$를 계산하는 것은 가능한 모든 연산 시퀀스를 탐색해야 하므로 계산적으로 불가능하기 때문에, 저자들은 알고리즘적 상한을 도입한다. 이 알고리즘은 최대 차수(maximum-degree) 정점들을 스타로 덮고(covering), 남은 에지들을 쌍별 교집합으로 덮은 후, 집합 결합 법칙(set associativity)을 사용하여 식을 최적화하여 그래프를 구축한다.

실험 실행
본 연구는 단일 스레드 CPU 처리 대비 23배의 가속을 달ach하기 위해 Intel Xe 그래픽에 최적화된 GPU 실행용 EcoLab 패키지를 활용하였다. 실험은 다음과 같이 진행되었다:

• 소규모 전수 조사: 스타 복잡도가 8 이하인 10개 및 22개 정점을 가진 모든 그래프를 생성하였다. 이를 통해 $C$, $Star(G)$, 그리고$C^*$(동등한 레시피의 수$\omega$ 포함)를 정확하게 계산할 수 있었다.
• 대규모 샘사플링: $C$와 쉽게 계산 가능한 상한 $\overline{Star}(G)$ 사이의 관계를 테스트하기 위해 1,000개의 정점을 가진 1,000개의 에르되시-레니(Erdős-Rényi) 무작위 그래프를 생성하였다.

주요 결과

• 소형 그래프 (10 및 22개 정점): 표준 복잡도 $C$와 가공되지 않은 스타 복잡도 $Star(G)$사이의 상관관계는 미미한 것으로 나타났다(상관계수$\rho \approx 0.08$및$-0.04$). 마찬가지로,$C$와 스타 유도 IBC인 $C^*$ 사이의 상관관계도 약했다($\rho \approx 0.14$ 및 0에 근접).
• 측정치 간의 상관관계: 그러나 $Star(G)$와$C^*$는 중간 정도의 양의 상관관계($\rho \approx 0.6$)를 보였으며, 추정된 상한$\overline{Star}(G)$는 정확한$Star(G)$와 강한 상관관계($\rho \approx 0.85$)를 보였다.
• 대형 그래프 (1,000개 정점): 가장 중요한 발견은 대규모 샘플링에서 나타났다. 쉽게 계산 가능한 상한 $\overline{Star}(G)$와 정보 기반 복잡도 $C$ 사이에 강하지만 비선형적인 관계가 관찰되었다.

의의 및 주장
본 논문은 소규모 전수 데이터셋에서 스타 복잡도가 정보 기반 복잡도와 선형적으로 상관관계가 있지는 않지만, 더 큰 규모의 그래프에서는 두 척도가 동일한 기저 속성을 측정하고 있을 가능성이 높다고 결론짓는다. 쉽게 계산 가능한 스타 복잡도의 상한 $\overline{Star}(G)$와 표준 IBC($C$) 사이의 강한 경험적 관계는 스타 복잡도가 실질적인 시나리오에서 유효한 대리 지표로 기능함을 시사한다. 저자들은 이것이 서로 다른 실용적 IBC 인코딩 체계들이 점근적으로 동등하다는 광범위한 가설을 뒷받침한다고 주장한다. 결과적으로, 대형 그래프에 대해 전체 IBC 계산보다 계산적으로 다루기 쉬운 스타 복잡도는 그래프 복잡도를 위한 신뢰할 수 있는 추정치로 사용될 수 있다.