기술 요약: 그래프 분할을 위한 신경 가속

문제 정의

그래프 분할, 특히 그래프 이분할 (Graph Bisection, GB) 은 과학적 컴퓨팅, VLSI 설계, 병렬 컴퓨팅에서 근본적인 NP-난제 (NP-hard problem) 입니다. 목표는 그래프의 정점 집합을 두 개의 서로소이며 크기가 대략 동일한 부분집합으로 나누되, 이들을 연결하는 간선의 수 (간선 컷) 를 최소화하는 것입니다.

스펙트럼 이분할 (Spectral Bisection, SB) 은 그래프 라플라시안의 두 번째로 작은 고유값에 해당하는 고유벡터인 피데르 (Fiedler) 벡터를 활용하여 고품질 분할을 생성하는 것으로 널리 인정받는 방법이지만, 심각한 계산 병목 현상을 겪습니다. 피데르 벡터를 계산하려면 밀집된 고유값 분해가 필요하며, 이는 높은 메모리 비용 ($O(|V|^2)$) 과 계산 오버헤드를 초래하여 대규모 희소 그래프에는 실용적이지 않습니다. 메타 (METIS) 와 같은 다단계 방법이나 기하학적 방법과 같은 기존 대안들은 종종 최적하지 않은 초기 분할을 생성하거나, 많은 실제 세계 그래프에 존재하지 않는 특정 좌표 데이터에 의존하는 휴리스틱에 의존합니다.

방법론

저자들은 계산 비용이 많이 드는 스펙트럼 분할의 고유값 계산을 경량 인공 신경망 (ANN) 으로 대체하여 피데르 벡터를 근사하는 신경 가속 (Neural Acceleration) 프레임워크를 제안합니다.

핵심 아키텍처

• 모델 유형: 단순한 지도 학습 1 은닉층 밀집 신경망.
• 입력: 평탄화된 $128 \times 128$ 그래프 라플라시안 행렬.
• 출력: 피데르 벡터를 근사하는 128 단위 벡터.
• 구성: 은닉층에는 편향과 $tanh$ 활성화 함수를 가진 512 단위가 포함됩니다. 모델에는 약 845 만 개의 학습 가능한 매개변수가 있습니다.
• 학습: 모델은 예측 벡터와 실제 피데르 벡터 간의 평균 절대 오차 (L1 손실) 를 최소화하기 위해 Adagrad 옵티마이저를 사용하여 GPU 에서 학습됩니다. 학습은 컴파일 시간에 완료되도록 설계되었습니다.

확장성 프레임워크

128 노드 크기의 학습 크기보다 큰 그래프를 처리하기 위해 저자들은 2 단계 축소 (coarsening) 워크플로우를 도입합니다:

1. 축소: 전통적인 무거운 간선 매칭 (HEM) 대신, 저자들은 인접 행렬에 적용되는 지역 이웃 필터 (Local Neighborhood Filter) (슬라이딩 윈도우 평균화) 를 사용합니다. 이 기술은 이미지 처리에서 영감을 받았으며, 신경 학습을 위해 HEM 보다 구조적 패턴을 더 잘 보존하면서 그래프 크기를 줄입니다.
2. 추론: 신경망은 축소된 그래프에 대한 피데르 벡터를 예측합니다.
3. 정제: 분할은 원래 그래프 크기로 보간된 후 간선 컷을 개선하기 위해 Fiduccia-Mattheyses (FM) 알고리즘을 사용하여 정제됩니다.

주요 기여

1. 스펙트럼 방법의 신경 근사: 이 논문은 단순한 밀집 신경망이 전통적으로 반복적 고유값 분해가 필요했던 피데르 벡터를 효과적으로 근사할 수 있음을 보여줍니다.
2. 효율적인 학습 및 추론: 밀집 텐서 연산을 위한 GPU 가속을 활용함으로써, 모델의 매개변수 수에도 불구하고 전통적인 솔버와 동등하거나 더 빠른 추론 시간을 달성합니다.
3. 새로운 축소 전략: 저자들은 인접 행렬에서 무작위 분포를 생성하는 표준 HEM 과 비교하여 신경망 학습을 위해 구조적 패턴을 더 효과적으로 보존한다고 주장하는 그래프 축소를 위한 지역 이웃 평균 필터를 제안합니다.
4. 정제와의 통합: 이 접근 방식은 표준 FM 정제와 결합될 때 전체 스펙트럼 이분할과 경쟁력 있는 결과를 산출하는 고품질 초기 분할을 제공하도록 설계되었습니다.

실험 결과

평가에는 SuiteSparse Matrix Collection 의 데이터셋이 사용되었으며, 학습/테스트를 위한 작은 그래프 (128 노드) 와 확장성 테스트를 위한 더 큰 실제 세계 그래프 (약 1,000 노드까지) 가 포함되었습니다.

• 분할 품질:
  • 정제 없이 (NN): 신경망 단독으로 생성한 분할은 전체 스펙트럼 이분할보다 약 1.56 배 더 나쁜 간선 컷을 보였습니다.
  • 정제 포함 (NN-FM): FM 정제와 결합되었을 때, 근사 비율은 스펙트럼 이분할 결과의 1.03 배로 개선되어 품질 면에서 거의 동등함을 나타냈습니다.
  • 비교: NN-FM 접근 방식은 무작위 분할보다 훨씬 우수한 성능을 보였으며, 특히 제안된 슬라이딩 윈도우 기술로 축소된 그래프에서 특정 사례에 대해 METIS 와 일치하거나 종종 초과했습니다.
• 성능 및 타이밍:
  • CPU: CPU 에서 전통적인 방법 (METIS, eigh) 은 신경 추론보다 빨랐습니다 (METIS 가 약 8.3 배 더 빠름).
  • GPU: GPU 에서 신경망 추론은 eigh 반복 솔버보다 4.5 배 더 빠르며 METIS 와 비슷했습니다.
• 메모리: 모델은 약 34 MB 의 메모리가 필요하며, 현대 GPU 메모리 용량에 비해 무시할 수 있을 정도로 작습니다.

중요성 및 주장

이 논문은 신경 가속이 메모리 및 계산 비용이 prohibitive 한 대규모 문제의 경우 전통적인 스펙트럼 분할에 대한 실현 가능한 대안을 제공한다고 주장합니다. 고비용의 고유값 분해 단계를 사전 학습된 신경망으로 대체함으로써 저자들은 다음을 달성합니다:

• 확장성: 무거운 계산을 GPU 로 오프로드하여 대규모 그래프를 처리할 수 있는 능력.
• 효율성: 반복 솔버에 비해 GPU 하드웨어에서 실행 시간을 크게 단축.
• 품질: 표준 정제 후 골드 스탠다드 스펙트럼 방법과 비교할 수 있는 품질의 초기 분할 생성.

저자들은 이 접근 방식이 이질적인 컴퓨팅 환경 (CPU-GPU) 을 더 잘 활용하면서 고품질 분할을 유지하면서 과학적 응용을 위한 스펙트럼 분할의 자동화를 가능하게 한다고 결론지었습니다. 그들은 이 방법이 축소 기술이 학습 데이터 분포와 일치할 때 (즉, HEM 대신 슬라이딩 윈도우 필터를 사용할 때) 가장 효과적임을 강조합니다.