본 논문은 신경망이 알고리즘적 추론을 학습하는 방식을 이해하고자, 효과적인 학습 알고리즘의 충실도와 신경망이 효과적인 알고리즘을 학습하지 못하는 이유라는 두 가지 질문에 답하고자 한다. 이를 위해, 소스 알고리즘을 신경망 매개변수에 직접 인코딩하여 신경망이 알고리즘을 정확하게 계산할 수 있도록 하는 신경 컴파일(neural compilation) 기법을 사용한다. 이를 통해 컴파일된 매개변수와 기존에 학습된 매개변수, 중간 벡터, 동작을 비교할 수 있다. 본 연구는 데이터에서 복잡한 알고리즘을 강력하게 학습하는 신경망을 개발하는 데 중요하다. 분석은 알고리즘 추론 작업과 자연스럽게 정렬되는 그래프 신경망(GNN)에 초점을 맞추며, 효과적, 충실적, 비효과적 학습 알고리즘의 스펙트럼을 포괄하는 BFS, DFS, Bellman-Ford 알고리즘을 선택한다. 일반적으로 알고리즘 추론 학습은 기저 진실 알고리즘에 의해 생성된 입력, 추적 및 출력에 대해 매개변수화된 모델을 훈련하는 합성 데이터에 대한 귀납으로 구성된다. 대조적으로, 본 논문은 훈련을 우회하여 GNN에 대한 신경 컴파일 방법을 소개한다. GNN에 초점을 맞추는 것은 알고리즘 추론과의 정렬, 광범위한 알고리즘 귀납 문헌, 그리고 GNN에 대한 신경 컴파일의 새로운 적용을 활용한다. 전반적으로, 본 논문은 알고리즘 추론 학습의 근본적인 단점인 표현 가능성-훈련 가능성 간극을 특징짓는 것을 목표로 한다. 본 논문은 귀납적 학습이 계산 클래스 NC에 포함된 병렬 알고리즘에 가장 효과적이라고 가정한다.
