💻 computer science

Learning Primality from Modular-Inverse Graphs

이 논문은 GCN이 특정 메시지 전달의 한계로 인해 이러한 차이를 포착하는 데 실패하는 반면, GraphSAGE는 모듈로 역 그래프(modular-inverse graphs)의 구조적 차이를 학습함으로써 소수와 합성수를 구별하는 데 있어 완벽에 가까운 정확도를 달성할 수 있음을 입증한다.

원저자: Tal Weissblat

게시일 2026-09-24

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Tal Weissblat

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

숫자는 수학의 구성 요소이며, 그중에서도 소수는 특별한 위치를 차지합니다. 소수는 1보다 큰 정수로서, 오직 1과 자기 자신에 의해서만 나누어떨어지는 수를 말합니다. 다른 수로 나누어떨어지는 수들은 합성수라고 불립니다. 수 세기 동안 수학자들은 이 두 종류의 수를 구별하는 효율적인 방법을 찾아왔으며, 이 과업은 현대 암호학과 컴퓨터 보안에 있어 여전히 매우 중요합니다. 전통적인 방식이 복잡한 산술 계산에 의존하는 반면, 새로운 연구 방향은 기계가 숫자를 단순한 값이 아닌 하나의 '형태'로 바라봄으로써 이러한 패턴을 인식할 수 있는지 묻습니다. 이 접근 방식은 숫자 안에 숨겨진 관계를 하나의 지도로 취급하며, 그 지도의 형태가 숫자 자체의 본질을 드러내기를 기대합니다.

최근 연구에서 연구자 탈 바이스블랫(Tal Weissblat)은 인공지능이 이러한 수학적 지도를 조사함으로써 소수와 합성수를 구별하는 법을 학습할 수 있는지 탐구했습니다. 연구자는 컴퓨터에 숫자 자체를 입력하지 않았습니다. 대신, 모든 숫자를 '모듈러 역 그래프(modular-inverse graph)'라고 불리는 고유한 도표로 변환했습니다. 이 도표를 만들기 위해, 연구자는 특정 숫자를 가져와 그 숫자로 만들 수 있는 모든 더 작은 정수들을 나열했습니다. 그런 다음, 이 작은 숫자들의 쌍을 곱했을 때 그 결과가 원래의 숫자로 나누었을 때 나머지가 1이 되는 경우에만 두 숫자 사이에 선을 그었습니다. 이 규칙은 소수든 합성수든 상관없이 모든 숫자에 대해 정확히 동일하게 적용되었으며, 컴퓨터에게 어떤 숫자가 무엇인지 알려주지 않았습니다. 목표는 결과로 나타난 형태가 숫자의 유형에 따라 자연스럽게 다르게 보이는지 확인하는 것이었습니다.

연구는 이러한 형태들의 이면에 있는 이론을 깊이 있게 살펴보는 것으로 시작되었습니다. 분석 결과, 소수의 도표와 합성수의 도표 사이에는 명확한 구조적 차이가 있음이 드러났습니다. 소수의 경우, 도표는 특정한 방식으로 완전히 연결되어 있습니다. 즉, 0을 제외한 모든 점은 적어도 하나의 다른 점과 연결됩니다. 홀로 떠 있는 외로운 점은 존재하지 않습니다. 반면, 합성수의 도표에는 고립된 점들, 즉 아무런 연결도 없는 숫자들이 포함되어 있습니다. 더욱이, 소수는 서로 다른 점들 사이에 가능한 최대치의 연결을 만들어내는 반면, 합성수는 더 적은 연결과 더 많은 외로운 점들을 가집니다. 이러한 이론적 발견은 컴퓨터가 단순히 연결 횟수를 세거나 고립된 점을 포착하는 것만으로도 차이를 식별할 수 있음을 시사했습니다.

이를 테스트하기 위해, 연구자는 2부터 10,001까지의 10,000개 정수 데이터셋을 사용하여 두 가지 서로 다른 유형의 인공지능 모델을 훈련시켰습니다. 데이터는 모델이 작은 숫자들을 통해 학습한 뒤, 한 번도 본 적 없는 더 큰 숫자들을 테스트하도록 분할되었습니다. GraphSAGE라고 알려진 한 모델은 도표 내 각 점의 국소적 이웃(local neighborhood)에 주목하도록 설계되었습니다. 또 다른 모델인 그래프 합성곱 신경망(Graph Convolutional Network)은 이웃으로부터 정보를 평균 내는 다른 방식을 사용했습니다. 결과는 극명하게 달랐습니다. GraphSAGE 모델은 놀라운 정밀도로 과업을 학습하여, 보지 못한 테스트 세트에서 소수와 합성수를 거의 99.9%의 정확도로 정확히 식별해 냈습니다. 이 모델은 작은 숫자로부터 학습한 패턴을 훨씬 더 큰 숫자로 성공적으로 일반화했습니다.

그러나 두 번째 모델은 완전히 실패했습니다. 이 모델은 무작위 추측보다 나을 것이 없는 정확도 50%를 기록했습니다. 이론적 분석은 왜 이런 일이 발생했는지 설명해 줍니다. GraphSAGE 모델은 연결된 점과 홀로 서 있는 점을 구분할 수 있었고, 소수 도표에서 발견된 결정적인 구조적 차이를 보존했습니다. 반면, 정보를 평균 내는 방식을 사용하는 다른 모델은 이러한 차이를 뭉개버렸습니다. 이 모델은 연결된 점과 고립된 점을 마치 같은 것처럼 취급하여, 소수를 구별해 주는 바로 그 특징을 효과적으로 지워버렸습니다. 이러한 실패는 오류가 아니라, 이 유형의 수학적 그래프에 적용되었을 때 나타나는 해당 방식의 근본적인 한계였습니다.

연구는 이러한 그래프로부터 소수 판별 능력을 학습하는 것이 전적으로 머신러닝 모델의 아키텍처에 달려 있다고 결론지었습니다. GraphSAGE 아키텍처는 소수의 미묘한 구조적 특징을 포착할 수 있었던 반면, 다른 흔한 아키텍처는 그러지 못했습니다. 연구에는 모델이 실제로 숫자를 암기하는 것이 아니라 그래프 구조를 사용하고 있는지 확인하는 검증 과정도 포함되었습니다. 그래프 처리 계층을 제거하자 모델의 성능은 다시 무작위 추측 수준으로 떨어졌습니다. 이는 성공의 원인이 숨겨진 수치적 속임수가 아니라 연결의 형태를 분석하는 데서 왔음을 확인시켜 주었습니다. 이 연구 결과는 산술적 특성이 그래프 구조로 인코딩될 수 있으며, 기계가 차이를 볼 수 있는 적절한 도구를 갖추고 있다면 이를 학습할 수 있다는 것을 보여줍니다.

기술적 요약: 모듈로 역 그래프를 통한 소수성 학습

문제 정의
본 연구는 그래프 신경망(GNN)이 숫자의 그래프 기반 표현으로부터 학습하여 소수(prime)와 합성수(composite)를 구별할 수 있는지 조사한다. 정수 $n$ 을 모델에 직접 입력하는 대신, 각 정수 $n$ 을 "모듈로 역 그래프(modular-inverse graph)"로 인코딩한다. 이 표현에서 정점은 요소 $\{0, 1, \dots, n-1\}$ 에 대응하며, 두 정점 $a$ 와 $b$ 사이에 에지(edge)가 존재한다는 것은 $a$ 와 $b$ 가 법(modulo) $n$ 에 대해 곱셈 역원 관계( $a \cdot b \equiv 1 \pmod n$ )임을 의미한다. 결정적으로, 그래프 구축 규칙은 모든 정수에 대해 동일하게 적용되며 소수성 레이블을 명시적으로 포함하지 않는다. 핵심 과제는 GNN이 분류를 위해 활용할 수 있는 체계적인 구조적 차이가 이러한 산술적 관계로부터 자연스럽게 발생하는지 여부를 결정하는 것이다.

방법론
본 연구는 이론적 특성화, 아키텍처 분석, 그리고 경험적 평가라는 세 가지 접근 방식을 채택한다.

이론적 특성화: 저자는 먼저 모듈로 역 그래프의 구조를 설명하는 수학적 기초(정리 1)를 확립한다. 저자는 다음을 증명한다:
- 소수 ( $n=p$ ): 그래프는 서로 다른 비제로(nonzero) 정점들을 연결하는 가능한 최대 수의 에지를 가지며, 비제로 정점이 고립되어 있지 않다. 모든 비제로 요소는 가역적이다.
- 합성수 ( $n$ ): 그래프는 서로 다른 정점들을 연결하는 더 적은 수의 에지를 가지며, 고립된 비제로 정점을 포함한다(구체적으로 $n - 1 - \phi(n)$ 개의 정점, 여기서 $\phi$ 는 오일러 피 함수).
- 이 구분은 고립된 비제로 정점의 존재 여부에 달려 있다.
아키텍처 분석 (메시지 전달 메커니즘): 본 논문은 두 가지 특정 GNN 아키텍처인 GraphSAGE와 그래프 합성곱 신경망(GCN)이 이러한 구조적 차이를 어떻게 처리하는지 이론적으로 분석한다:
- GraphSAGE: 루트 특징(root features)과 이웃 특징(neighbor features)을 분리하는 GraphSAGE의 집계 메커니즘이 고립된 정점과 고립되지 않은 정점에 서로 다른 표현을 할당할 수 있음을 입증한다. 전역 평균 풀링(global mean pooling)을 통해 이 국소적 구분이 그래프 수준에서 보존되며, 이론적으로 모델이 소수와 합성수 사이의 고립된 정점 비율 차이를 감지할 수 있게 한다.
- GCN: 반대로, GCN의 정규화된 집계(셀프 루프 포함)는 고립된 정점과 고립되지 않은 정점이 첫 번째 단계 이후 동일한 표현을 갖게 함을 보여준다. 결과적으로, 정리 1에서 식별된 구조적 구분이 소실되며, 이는 이론적으로 GCN이 클래스를 구별하는 것을 방해한다.
실험 설정:
- 데이터셋: 2에서 10,001 사이의 정수 10,000개.
- 파티셔닝: 데이터는 연속적이고 중복되지 않는 세트인 훈련(2–4,000), 검증(4,001–7,000), 테스트(7,001–10,001)로 분할되었다. 이 설계는 작은 정수에서 더 크고 미지의 정수로의 일반화 능력을 테스트한다.
- 모델: GraphSAGE와 GCN을 다양한 은닉층 구성(예: 1-8-8, 1-16-16)과 함께 평가하였다.
- 지표: 클래스 불균형(소수가 합성수보다 적음)을 고려하여, **균형 정확도(Balanced Accuracy, BA)**를 주요 지표로 사용하였다.

주요 결과

GraphSAGE 성능: 선택된 GraphSAGE 아키텍처(1-8-8)는 세 번의 무작위 시드에 대해 평균 검증 균형 정확도 **99.97%**와 평균 테스트 균형 정확도 **99.89%**를 달s성했다. 테스트 세트에 있는 329개의 소수를 모두 올바르게 분류했다(재현율 100%). 오분류는 합성수(반소수, semiprimes)를 소수로 잘못 레이블링한 소수의 사례로 제한되었다.
GCN 성능: 이와 극명하게 대조적으로, GCN은 모든 구성과 시드에서 50.00%의 균형 정확도를 기록했으며, 이는 우연 수준의 성능에 해당한다.
절제 연구(Ablation Study): GraphSAGE 모델에서 두 개의 GNN 레이어를 모두 제거하면 성능이 50% BA로 감소하여, 그래프 메시지 전달 메커니즘이 과업에 필수적임을 확인했다. 레이어를 하나 제거했을 때는 성능 저하가 미미했다.
오류 분석: GraphSAGE가 범한 오류는 배타적으로 거짓 양성(합성수를 소수로 예측)이었으며, 주로 특정 인수 패턴(예: 소수의 제곱 또는 두 서로 다른 소수의 곱)을 가진 숫자들과 관련되었고, 예측 확률은 결정 임계값 근처에 머물렀다.

주요 기여

그래프 표현: 소수성 레이블을 명시적으로 사용하지 않고도 정수의 산술적 특성을 그래프 토폴로지로 변환하는 모듈로 역 그래프 표현을 도입하였다.
이론적 정당화: 소수와 합성수의 그래프 사이에 체계적인 구조적 차이(특히 고립된 비제로 정점과 관련하여)를 확립하는 수학적 증명을 제공하였다.
아키텍처 통찰: 특정 그래프 표현으로부터 소수성을 학습하는 능력은 결정적으로 GNN의 메시지 전달 메커니즘에 의존한다는 것을 이론적 및 경험적으로 입증하였다. 본 연구는 GraphSAGE는 필요한 구조적 구분을 보존할 수 있는 반면, 표준 GCN의 정규화는 이를 파괴한다는 것을 보여준다.
일반화 증거: 적절한 아키텍처를 사용할 때 모델이 더 작고 미지의 정수로부터 학습하여 더 큰 정수로 일반화할 수 있다는 경험적 증거를 제시하였다.

의의 및 주장
본 논문은 그래프 표현 학습을 통해 수론적 특성을 조사하기 위한 수학적으로 근거 있는 프레임워크를 제공한다고 주장한다. 소수성과 관련된 산술 정보가 순수하게 그래프 구조에 인코딩될 수 있으며, 적절한 GNN을 통해 효과적으로 학습될 수 있음을 보여준다. 이 연구는 GNN 아키텍처의 선택이 단순히 하이퍼파라미터 튜닝의 문제가 아니라, 특정 구조적 정보(고립된 정점의 존재 여부와 같은)를 활용할 수 있는지 여부를 결정하는 근본적인 결정 요인임을 강조한다. 결과는 메시지 전달 메커니즘에 대한 이론적 분석과 관찰된 학습 행동을 일치시키며, GCN의 실패와 GraphSAGE의 성공이 모듈로 역 그래프의 특정 토폴로지를 처리하는 방식의 직접적인 결과임을 시사한다.

한계점
저자는 본 연구가 10,01까지의 정수로 제한되어 있어, 훨씬 더 큰 범위에서의 동작은 검증되지 않았음을 언급한다. 또한, 본 분석은 모듈로 역 그래프 표현과 소수성 판별이라는 이진 분류 과업에 특화되어 있으며, 다른 수론적 특성이나 그래프 표현에 대해서는 즉각적인 주장을 하지 않는다.

기술적 요약: 모듈로 역 그래프를 통한 소수성 학습

유사한 논문