\[\renewcommand{\V}[1]{\mathbf{#1}}\]

신경 알고리즘 분야의 또 다른 일반주의 학습자 (Ibarz et al., 2022) 가 나왔다.

Abstract

신경 알고리즘 추론의 핵심은 분포 밖에서 일반화하는 방식으로 알고리즘 과제를 해결하는 능력에 있다. 최근 몇 년 동안 이 분야에서 방법론적 개선이 급증했지만, 대부분은 전문가 모델을 구축하는 데 집중했다. 전문가 모델은 하나의 알고리즘 또는 동일한 제어 흐름 구조를 가진 알고리즘 모음을 신경적으로 실행하는 데 학습할 수 있다. 여기서는 대신, 일반주의 신경 알고리즘 학습자를 구축하는 데 집중한다. 이는 정렬, 검색, 동적 프로그래밍, 경로 찾기, 기하학과 같은 다양한 알고리즘을 실행하도록 학습할 수 있는 단일 그래프 신경망 프로세서다. 우리는 CLRS 벤치마크를 활용하여, 지각 분야의 최근 성공과 마찬가지로, 지식을 “통합”함으로써 일반주의 알고리즘 학습자를 구축할 수 있다는 것을 실증적으로 보여준다. 즉, 단일 과제 체제에서 잘 실행할 수 있도록 학습한다면, 다중 과제 방식으로 알고리즘을 효과적으로 학습할 수 있다. 이에 동기를 얻어, CLRS에 대한 입력 표현, 훈련 체제, 프로세서 구조의 일련의 개선을 제시하며, 이전 예술 대비 평균 단일 과제 성능을 20% 이상 향상시켰다. 그런 다음 이러한 개선을 활용하는 다중 과제 학습자에 대한 철저한 제거 연구를 수행했다. 우리의 결과는 전문가 모델에 의해 포착된 지식을 효과적으로 통합하는 일반주의 학습자를 보여준다.

단일 과제 실험

CLRS 벤치마크 (Veličković et al., 2022) 에서의 각 알고리즘은 입력, 힌트, 출력의 숫자로 정의된다. 주어진 샘플에서 입력과 출력은 고정되어 있으며, 힌트는 알고리즘의 중간 상태를 시간 순서대로 나타낸다. 특정 과제에 대한 각 샘플은 GNN이 알고리즘을 실행할 때 노드의 숫자인 \(n\)의 크기를 가진다.

알고리즘의 모든 샘플은 그래프로 표현되며, 각 입력, 출력, 힌트는 노드, 엣지 또는 그래프 자체에 위치하며, 따라서 각각의 형태는 배치 차원과 힌트의 시간 차원을 제외하고 \(n \times f\), \(n \times n \times f\), 또는 \(f\)가 된다. 여기서 \(f\)는 유형에 따라 다른 특성의 차원이다. CLRS 벤치마크는 scalar, categorical, mask, mask_one, pointer의 다섯 가지 유형의 특성을 정의하며, 각각의 인코딩과 디코딩 전략 및 손실 함수를 가진다. 예를 들어 scalar 유형은 단일 선형 계층에 의해 직접 인코딩 및 디코딩되며 평균 제곱 오차를 사용하여 최적화된다. 자세한 내용은 CLRS 벤치마크 논문 (Veličković et al., 2022) 을 참조한다.

기본 모델

인코더.

CLRS 벤치마크 (Veličković et al., 2022) 에서 제시된 인코딩-프로세싱-디코딩 패러다임 (Hamrick et al., 2018) 을 채택한다. 특정 과제 \(\tau\) (예: 삽입 정렬)의 각 시간 단계 \(t\)에서, 과제 기반 인코더 \(f_\tau\)는 각 입력과 힌트에 대한 선형 인코더로 구성되며, 입력과 현재 힌트를 고차원 벡터로 임베딩한다. 노드에 위치한 입력과 힌트의 임베딩은 동일한 차원을 가지며 더해진다; 엣지와 그래프에 위치한 힌트와 입력도 마찬가지다. 실험에서는 노드, 엣지, 그래프 임베딩에 동일한 차원인 \(h=128\)을 사용한다. 따라서 알고리즘의 시간 단계 \(t\)에서 인코딩 단계가 끝나면, 단일 임베딩 세트 \(\Big \{ \V x_i^{(i)}, \V e_{ij}^{(t)}, \V g^{(t)} \Big \}\) , 형태 \(n \times h\), \(n \times n \times h\), \(h\)를 노드, 엣지 및 그래프에서 각각 얻는다. 이것은 특정 알고리즘의 입력과 힌트의 수와 유형에 독립적이며, CLRS의 모든 30개 알고리즘에 이 잠재 공간을 공유할 수 있게 한다. 또한, 각 단계에서 입력 인코딩은 이 임베딩에 직

접 공급된다; 이 회상 메커니즘은 모델의 장기 경로에 대한 견고함을 크게 향상시킨다 (Bansal et al., 2022) .

프로세서.

임베딩은 프로세서 \(P\)로 공급되며, 프로세서는 한 단계의 계산을 수행한다. 프로세서는 입력 노드, 엣지, 그래프 임베딩을 처리된 노드 임베딩 \(\V h_i^{(t)}\)로 변환한다. 중요하게도, 동일한 프로세서 모델은 모든 크기의 그래프에서 작동할 수 있다. 기본 모델로 \(\max\) 집계를 사용하고 완전 연결 그래프에서 메시지를 전달하는 메시지 전달 신경망 [ (Gilmer et al., 2017) , MPNN]을 활용한다. MPNN은 다음과 같이 처리된 임베딩을 계산한다.

\[\V z^{(t)} = \V x_i^{(t)} \| \V h_i^{(t-1)} \qquad \V m_i^{(t)} = \max_{1\le j\le n} f_m \left ( \V z_i^{(t)}, \V z_j^{(t)}, \V e_{ij}^{(t)}, \V g^{(t)} \right) \qquad \V h_i ^{(t)} = f_r \left ( \V z_i^{(t)}, \V m_i^{(t)} \right)\]

여기서 \(\|\)는 연결을 나타내며, \(f_m : \R^{2h} \times \R^{2h} \times \R^h \times \R^h \rightarrow \R^h\)은 메시지 함수(세 계층 MLP와 ReLU 활성화를 사용)이며, \(f_r: \R^{2h} \times \R^h \rightarrow \R^h\)은 리드아웃 함수(ReLU 활성화가 있는 선형 계층을 사용)이다. \(\max\) 집계의 사용은 이전 연구 (Veličković et al., 2022) (Veličković et al., 2019) 에 의해 잘 근거되어 있으며, 완전 연결 그래프를 사용함으로써 입력 그래프 구조가 최적이 아닐 경우 모델이 이를 극복할 수 있도록 한다. 계층 정규화 (Ba et al., 2016) 는 \(\V h_i^{(t)}\)에 적용된다. MPNN 프로세서에 대한 자세한 내용은 Veličković et al. (Veličković et al., 2022) 에서 찾을 수 있다.

디코더.

처리된 임베딩은 마지막으로 과제 기반 디코더 \(g_\tau\)로 디코딩되어 다음 단계의 힌트와 최종 단계의 출력을 예측한다. 인코더와 유사하게, 과제 기반 디코더는 주로 각 힌트와 출력에 대한 선형 디코더에 의존하며, 필요한 경우 노드 간 유사성을 계산하는 메커니즘을 포함한다. 구체적으로, pointer 유형 디코더는 각 노드 쌍에 대한 점수, \(s_{ij}\),를 계산하고, 그런 다음 노드 \(i\)의 포인터를 \(\arg\max_j s_{ij}\) 또는 \(\mathrm{softmax}_j s_{ij}\) (하드 또는 소프트 예측을 사용하는지에 따라)를 사용하여 선택한다.

손실.

훈련 중에는 타입별로 분류된 해석된 힌트와 결과들을 사용해 손실을 계산한다 (Veličković et al., 2022) . 각 배치의 샘플에 대해, 힌트 예측 손실은 힌트와 시간에 걸쳐 평균되며, 결과 손실은 결과물에 걸쳐 평균된다 (대부분의 알고리즘은 하나의 결과를 가지지만, 일부는 두 개의 결과를 가짐). 힌트 손실과 결과 손실은 함께 더해진다. 또한, 각 시간 단계에서의 힌트 예측은 다음 단계의 입력으로 되먹임되며, 교사 강요가 사용될 경우 훈련 시에는 예외가 될 수 있다. (“데이터셋 및 훈련” 섹션 참조)

모델은 \(n\le 16\) 크기의 샘플에 대해 훈련되며, 주기적으로 \(n=16\) 크기의 분포 내 샘플에 대해 평가된다. 또한, 주기적으로 지금까지 분포 내 평가 점수가 가장 높은 모델을 \(n = 64\) 크기의 OOD 샘플에 대해 평가한다. 다음에서는 이러한 OOD 평가 점수만 보고할 것이다. 모델, 훈련 및 평가 하이퍼파라미터의 전체 세부 사항은 부록 A에서 찾을 수 있다.

모델 개선

이전에 논의된 바와 같이, 특히 학습 안정성 측면에서 단일 과제 개선은 다중 과제 알고리즘 학습에 잘 전달될 것이다. 이제 CLRS의 모든 30개 과제에서 평균적으로 20% 이상의 절대적인 개선을 이끈 모델의 모든 변경 사항을 점진적으로 설명한다.

데이터셋 및 훈련

교사 강요 제거.

평가 시, 모델은 데이터셋의 단계별 힌트에 접근할 수 없으며, 자체 힌트 예측에 의존해야 한다.

훈련 데이터 증가.

고정된 CLRS 훈련 데이터셋 (Veličković et al., 2022) 의 통계에 모델이 과적합되는 것을 방지하기 위해, 의도된 예시를 깨지 않고 훈련 데이터를 세 가지 주요 방법으로 증가시켰다.

부드러운 힌트 전파.

훈련 중 예측된 힌트가 입력으로 되먹임될 때, 그라디언트가 흐를 수도 있고 안 할 수도 있다.

정적 힌트 제거.

CLRS¹의 열한 알고리즘은 노드 포인터 힌트를 통해 모든 샘플에 공통된 고정된 노드 순서를 지정하며, 이는 궤적을 따라 변하지 않는다.

인코더 초기화와 그라디언트 클리핑으로 훈련 안정성 개선: 스칼라 힌트는 원칙적으로 무한한 값을 가질 수 있으며, 평균 제곱 오차를 사용하여 최적화되므로, 예측 오류가 증가함에 따라 그라디언트가 빠르게 커질 수 있다.

인코더 및 디코더

임의화된 위치 스칼라.

데이터셋의 모든 알고리즘에는 노드 인덱스를 따라 0에서 1 사이에 선형적으로 배치된 값으로 노드를 고유하게 색인하는 위치 스칼라 입력이 존재한다. 훈련 중 이러한 선형적으로 배치된 값에 대한 과적합을 피하기 위해, 이들을 [0, 1] 범위에서 균일하게 샘플링된 임의의 값으로 대체하고, 선형적으로 배치된 값에 의해 암시된 초기 순서와 일치하도록 정렬했다. 이 변경의 이점은 문자열 매칭과 같이 이 위치에 쉽게 과적합될 수 있는 알고리즘에서 주목할 만하다. 즉, 모델은 항상 \(n\) 문자열 내에서 \(m\) 문자 패턴을 찾을 것이라고 가정하여 모든 계산을 기반으로 할 수 있지만, 테스트 시에는 \(m\)과 \(n\)이 네 배 증가할 것이다.

순열 디코더 및 싱크혼 연산자.

정렬 알고리즘(삽입 정렬, 버블 정렬, 힙 정렬, 퀵 정렬)은 항상 입력 노드의 순열을 출력한다. CLRS 벤치마크에서, 이 순열은 각 노드가 정렬 순서에서 자신의 이전 노드를 가리키는 포인터로 인코딩된다(첫 번째 노드는 자기 자신을 가리킴); 이것은 각 행이 하나의 핫 벡터인 \(n \times n\) 행렬 \(\V P\)로 표현되며, 여기서 요소 \((i, j)\)는 노드 \(i\)가 노드 \(j\)를 가리킬 때 1이다. 모든 종류의 포인터와 마찬가지로, 이러한 순열 포인터는 무제한 디코더 출력(로그)에 대한 행별 소프트맥스를 사용하여 예측할 수 있으며, 교차 엔트로피로 훈련된다( (Veličković et al., 2022) 에서처럼). 그러나 이것은 포인터가 순열을 인코딩한다는 사실을 명시적으로 활용하지 않으며, 대신 모델이 학습해야 한다. 초기 실험에서 모델은 종종 OOD에서 유효한 순열을 예측하는 데 실패하는 것으로 나타났다.

따라서, 정렬 알고리즘의 출력 디코더에 순열 유도 편향을 적용한다. 우선, 첫 번째 노드를 마지막 노드에 연결하도록 출력 표현을 수정하여 \(\V P\)를 순열 행렬로 변환한다, 즉, 행 과 열이 원-핫 벡터인 행렬이다. 첫 번째 노드를 지정하는 크기 \(n\)의 원-핫 벡터를 표현에 추가하여 이 정보를 잃지 않게 한다; 이 벡터는 일반적인 mask_one 기능처럼 처리된다. 둘째, 비제약 디코더 출력 \(\V Y\)에서 일반적인 행별 소프트맥스 대신 싱크혼 연산자 \(\mathcal{S}\) [ (Sinkhorn, 1964) , (Sinkhorn & Knopp, 1967) , (Santa Cruz et al., 2017) , (Mena et al., 2017) , (Mena et al., 2018) ]를 사용하여 순열 행렬 \(\V P\)를 예측한다. \(\mathcal{S}\)는 임의의 정사각 행렬 \(\V Y\)를 이중 확률 행렬 \(\mathcal{S}(\V Y)\)(행과 열의 합이 1인 음이 아닌 행렬)로 투영한다. 특히, \(\mathcal{S}\)는 다음과 같이 정의된다:

여기서 \(\exp\)는 요소별로 작용하며, \(\mathcal{T}_r\) 및 \(\mathcal{T}_c\) 는 각각 행 및 열 정규화를 나타낸다. 비록 싱크혼 연산자가 순열 행렬이 아닌 이중 확률 행렬을 생성하지만, 온도 매개변수 \(\tau > 0\) 을 도입하고 \(\V P = \lim_{\tau\to0^+}\mathcal{S}(\V Y / \tau)\) 을 취함으로써 순열 행렬을 얻을 수 있다; \(\V Y\) 의 요소에 동점이 없는 한, \(\V P\) 는 순열 행렬이 되는 것이 보장된다 [ (Mena et al., 2017) , 정리 1].

실제로, 우리는 고정된 반복 횟수 \(l_{\max}\) 를 사용하여 싱크혼 연산자를 계산한다. 소실 및 폭발 그라데이션을 제한하기 위해 훈련 시 더 작은 반복 횟수 \(l_{\max} = 10\) 를 사용하고, 평가 시에는 \(l_{\max}= 60\) 를 사용한다. 실험적으로 고정된 온도 \(\tau=0.1\)은 수렴 속도와 동점 처리 사이에서 좋은 균형을 이루는 것으로 나타났다. 또한, 어떤 노드도 자신을 가리키지 않는다는 사실, 즉, \(\V P\)의 모든 대각 요소가 0이어야 한다는 사실을 인코딩하기 위해 \(\V Y\)의 대각 요소를 \(-\infty\)로 설정한다. 동점을 피하기 위해, 훈련 중에만 싱크혼 연산자를 적용하기 전에 \(\V Y\)의 요소에 검벨 노이즈를 주입하는 Mena et al. (Mena et al., 2018) 을 따른다. 마지막으로, 예측된 행렬 \(\V P\)와 첫 번째 요소를 가리키는 mask_one을 CLRS가 사용하는 원래 포인터 표현으로 변환한다.

프로세서 네트워크

게이팅 메커니즘.

\[\V g_i^{(t)} = f_g \left ( \V z_i^{(t)}, \V m_i^{(t)} \right )\]

여기서 \(f_g : \R^{2h} \times \R^h \to \R_h\)는 게이팅 함수로, 우리는 은닉층에 ReLU 활성화 함수와 출력에 로지스틱 시그모이드 활성화 함수를 사용하는 2층 MLP를 사용한다. 중요하게, \(f_g\)의 최종 레이어 편향은 -3으로 초기화되어, 필요하지 않는 한 네트워크가 자신의 표현을 업데이트하지 않도록 편향된다. 처리된 게이팅 임베딩, \({\widehat {\V h}_i^{(t)}}\),은 다음과 같이 계산된다:

\[\widehat {\V h}_i^{(t)} = \V g_i^{(t)} \odot \V h_i^{(t)} + (1 - \V g_i^{(t)}) \odot \V h_i^{(t-1)}\]

그리고 이는 후속 단계에서 \(\V h_i^{(t)}\) 대신 사용되며, Eq. 1의 \(\V z^{(t)}\)를 \(\V z^(t) = \V x_i ^{(t)} \| \widehat{\V h}_i^{t-1}\)로 대체한다.

트리플리트 추론.

CLRS-30 내의 여러 알고리즘은 간선 기반 추론을 명시적으로 요구한다 — 여기서 간선은 값을 저장하고 다른 간선의 값에 따라 업데이트한다. 이의 예는 Floyd-Warshall 알고리즘 (Floyd, 1962) 으로, 가중 그래프에서 모든 쌍의 최단 경로를 계산한다. 노드 \(i\)에서 \(j\)까지의 최상의 거리에 대한 추정치인 \(d_{ij}\)에 대한 업데이트 규칙은 \(d_{ij} = \min_k d_{ik} + d_{kj}\)로, 대략적으로 “i에서 j로 가는 최선의 방법은 최적의 중간 지점 \(k\)를 찾아, i에서 k로, 그리고 k에서 j로 이동하는 것”이라고 말한다. 이와 유사한 규칙들은 CLRS-30 알고리즘, 특히 동적 프로그래밍에서 만연하다. 위 업데이트에는 노드 표현이 없지만, 우리의 모든 프로세서는 노드 표현 \(\V h_i\) 간의 메시지 전달에 중점을 둔다.

이 상황을 바로잡기 위해, 우리는 프로세서를 강화하여 간선으로 메시지 전달을 수행한다. \(d_{ij}\)에 대한 업데이트를 다시 참조할 때, 중간 노드를 선택한 다음 가능한 모든 선택에 대해 집계하여 간선 표현이 업데이트된다는 점을 주목한다. 따라서, Dudzik과 Veličković (Dudzik & Veličković, 2022) 가 이전에 관찰한 바와 같이, 우리는 트리플리트 추론을 도입한다: 첫째, 노드의 삼중체에 대한 표현을 계산한 다음, 하나의 노드를 줄여 간선 잠재 변수를 얻는다:

\[\V t_{ijk} = \psi_t (\V h_i, \V h_j, \V h_k, \V e_{ij}, \V e_{ik}, \V e_{kj}, \V g) \qquad \V h_{ij} = \phi_t(\max_k \V t_{ijk})\]

여기서, \(\psi_t\)는 모든 관련 표현을 노드 삼중체의 단일 벡터로 매핑하는 트리플리트 메시지 함수이고, \(\phi_t\)는 각 간선에 대해 집계된 삼중체를 변환하는 간선 리드아웃 함수이다. CLRS 벤치마크 (Veličković et al., 2022) 에 대한 이전 발견에 따라, 우리는 간선 표현을 얻기 위해 최대 집계를 사용한다. 계산된 \(\V h_{ij}\) 벡터는 그 후에 간선 기반 추론 작업에 사용될 수 있으며, 실제로는 우리가 처음에 예상하지 못했던 작업에서도 상당한 이점이 있다는 것이 입증되었다. 예를 들어, Kruskal의 최소 신장 트리 알고리즘 (Kruskal, 1956) 에서는 트리플리트 추론이 모델이 간선을 무게에 따라 더 쉽게 정렬하고, 각 단계에서 신장 숲을 확장하는 방법을 선택하는 데 도움이 되었다고 추정한다.

트리플리트 임베딩의 발자국을 가능한 한 가볍게 유지하기 위해, \(\psi_t\)에서는 단 8차원의 특징만을 계산한다. \(\phi_t\)는 그 후에 집계된 간선 특징을 다시 128차원으로 확대하여 나머지 아키텍처와 호환되게 한다. 우리의 초기 실험에서 \(\psi_t\)의 출력 차원이 하류 성능에 크게 영향을 미치지 않는 것으로 나타났다. 삼중체 표현을 계산하는 것은 일반 GNN 설계에서 유용한 접근 방식이었다 (Morris et al., 2018) — 그러나 주로 일정 입력 특징에 대한 GNN의 맥락에서 연구되었다. 우리의 연구는 잘 정의된 초기 특징을 가진 추론 작업에서 그들의 유용성을 확인하는 최초의 연구 중 하나이다.

추가 읽을 자료

NeuralExecuter++ (Xhonneux et al., 2021)

참고문헌

1. Ibarz, B., Kurin, V., Papamakarios, G., Nikiforou, K., Bennani, M., Csordás, R., Dudzik, A., Bošnjak, M., Vitvitskyi, A., Rubanova, Y., Deac, A., Bevilacqua, B., Ganin, Y., Blundell, C., & Veličković, P. (2022). A Generalist Neural Algorithmic Learner. arXiv. doi: 10.48550/ARXIV.2209.11142 https://arxiv.org/abs/2209.11142
2. Veličković, P., Badia, A. P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., & Blundell, C. (2022). The CLRS Algorithmic Reasoning Benchmark. arXiv. doi: 10.48550/ARXIV.2205.15659 https://arxiv.org/abs/2205.15659
3. Hamrick, J. B., Allen, K. R., Bapst, V., Zhu, T., McKee, K. R., Tenenbaum, J. B., & Battaglia, P. W. (2018). Relational inductive bias for physical construction in humans and machines. arXiv. doi: 10.48550/ARXIV.1806.01203 https://arxiv.org/abs/1806.01203
4. Bansal, A., Schwarzschild, A., Borgnia, E., Emam, Z., Huang, F., Goldblum, M., & Goldstein, T. (2022). End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking. arXiv. doi: 10.48550/ARXIV.2202.05826 https://arxiv.org/abs/2202.05826
5. Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural Message Passing for Quantum Chemistry. In D. Precup & Y. W. Teh (Eds.), Proceedings of the 34th International Conference on Machine Learning (Vol. 70, pp. 1263–1272). PMLR. https://proceedings.mlr.press/v70/gilmer17a.html
6. Veličković, P., Ying, R., Padovano, M., Hadsell, R., & Blundell, C. (2019). Neural Execution of Graph Algorithms. arXiv. doi: 10.48550/ARXIV.1910.10593 https://arxiv.org/abs/1910.10593
7. Ba, J. L., Kiros, J. R., & Hinton, G. E. (2016). Layer Normalization. arXiv. doi: 10.48550/ARXIV.1607.06450 https://arxiv.org/abs/1607.06450
8. Sinkhorn, R. (1964). A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices. The Annals of Mathematical Statistics, 35(2), 876–879. doi: 10.1214/aoms/1177703591 https://doi.org/10.1214/aoms/1177703591
9. Sinkhorn, R., & Knopp, P. (1967). Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathematics, 21, 343–348.
10. Santa Cruz, R., Fernando, B., Cherian, A., & Gould, S. (2017, July). DeepPermNet: Visual Permutation Learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
11. Mena, G., Belanger, D., Muñoz, G., & Snoek, J. (2017). Sinkhorn Networks: Using Optimal Transport Techniques to Learn Permutations.
12. Mena, G., Belanger, D., Linderman, S., & Snoek, J. (2018). Learning Latent Permutations with Gumbel-Sinkhorn Networks. doi: 10.48550/ARXIV.1802.08665 https://arxiv.org/abs/1802.08665
13. Floyd, R. W. (1962). Algorithm 97: Shortest path. Communications of the ACM, 5, 345.
14. Dudzik, A., & Veličković, P. (2022). Graph Neural Networks are Dynamic Programmers. arXiv. doi: 10.48550/ARXIV.2203.15544 https://arxiv.org/abs/2203.15544
15. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48–50. doi: 10.1090/s0002-9939-1956-0078686-7 https://app.dimensions.ai/details/publication/pub.1018477579
16. Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., & Grohe, M. (2018). Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. arXiv. doi: 10.48550/ARXIV.1810.02244 https://arxiv.org/abs/1810.02244
17. Xhonneux, L.-P. A. C., Deac, A., Veličković, P., & Tang, J. (2021). How to transfer algorithmic reasoning knowledge to learn new algorithms? In A. Beygelzimer, Y. Dauphin, P. Liang, & J. W. Vaughan (Eds.), Advances in Neural Information Processing Systems. https://openreview.net/forum?id=q2JWz371le
18. Bentley, J. (1986). Programming Pearls. Association for Computing Machinery.
19. Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1974). The design and analysis of computer algorithms. In The design and analysis of computer algorithms. Addison-Wesley.
20. Gavril, F. (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM J. Comput., 1, 180–187.
21. Lawler, E. L. (1985). The traveling salesman problem: a guided tour of combinatorial optimization. In The traveling salesman problem: a guided tour of combinatorial optimization.
22. Knuth, D. E., Morris, J. H., Jr., & Pratt, V. R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing, 6(2), 323–350. doi: 10.1137/0206024 https://doi.org/10.1137/0206024
23. Jarvis, R. A. (1973). On the Identification of the Convex Hull of a Finite Set of Points in the Plane. Inf. Process. Lett., 2(1), 18–21. http://dblp.uni-trier.de/db/journals/ipl/ipl2.html#Jarvis73

---

Footnotes

1. Binary Search, Minimum, Max Subarray (Bentley, 1986) , Matrix Chain Order, LCS Length, Optimal BST (Aho et al., 1974) , Activity Selector (Gavril, 1972) , Task Scheduling (Lawler, 1985) , Naïve String Matcher, Knuth-Morris-Pratt (Knuth et al., 1977) and Jarvis’ March (Jarvis, 1973) ↩