링크 예측을 위한 조기 종료 그래프 신경망
Early-Exit Graph Neural Networks for Link Prediction
한국어 초록
그래프 신경망(GNN)은 다양한 네트워크 형태 구조에서 링크 예측에 매우 효과적이지만, 속도와 품질 간의 트레이드오프에 대한 연구는 거의 이루어지지 않았다. 실무에서는 작은 벤치마크에서 추론에 걸리는 시간이 크게 중요하지 않지만, 지연 시간은 대규모 도메인에서의 적용 가능성을 제한한다. 본 연구에서는 링크 예측 문제를 더 빠르게 해결하기 위해 그래프 신경망에 적용할 수 있는 조기 종료(early-exiting) 전략을 탐구한다. 조기 종료를 강제하기 위한 보조 손실(auxiliary loss)은 사용하지 않으며, 이를 아키텍처의 암묵적 특성으로 드러나게 한다. 여러 설정에서 본 방법이 조기 종료를 가능하게 하고, GCN 및 SAS-GNN 백본에 대해 HeaRT 벤치마크에서 파레토 프론티어(Pareto frontier)를 이동시킴을 보인다. 연구 결과, 많은 링크 예측 문제에서 GNN의 추론 속도를 개선할 수 있으며, 예측 품질 측면에서는 거의 손실이 없거나 오히려 더 나아질 수 있음을 보여준다. 코드는 다음 저장소에서 제공된다: https://github.com/knyazer/link_prediction.
원문 초록
Graph Neural Networks are great for link prediction in various network-like structures; however, the question of their speed/quality tradeoff has been barely studied. While in practice the time it takes to do inference matters little for small benchmarks, the latency does limit applicability in large-scale domains. In this work, we explore early-exiting strategies that can be applied to Graph Neural Networks to solve the problem of link-prediction faster. We use no auxiliary losses to enforce early exiting, allowing it to emerge as an implicit property of the architecture. We show that our method enables early exiting in several setups, moving the Pareto frontier on the HeaRT benchmark for GCN and SAS-GNN backbones. Our findings show that inference speed of GNNs on many link-prediction problems can be improved, while losing little, or even winning in terms of prediction quality. The code is available in our repository: https://github.com/knyazer/link_prediction.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.22167v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
NEMORA: 장거리 원자론적 학습을 위한 신경 등변 다중극 연산자
NEMORA: Neural Equivariant Multipole Operators for Long-Range Atomistic Learning
등변 그래프 신경망(Equivariant Graph Neural Network)은 머신러닝 기반 원자 간 포텐셜(interatomic potential)의 핵심 아키텍처로 부상하여, 계산 비용의 일부만으로도 양자 화학 수준의 정확도에 근접하고 있습니다. 이러한 모델들은 국소 원자 환경을 정확하게 기술하지만, 유한한 공간적 컷오프(cutoff)로 인해 장거리 정보 흐름이 단절되며, 메시지 전달 계층을 깊게 쌓으면 지나친 평활화(over-smoothing) 및 과도한 압축(over-squashing)이 발생할 수 있습니다. 기존의 장거리 확장 기법들은 고정된 해석적 전파 커널(propagation kernel)을 규정하거나, 장거리 통신을 스칼라 또는 차수 보존 채널로 제한하거나, 근사적으로만 등변성을 만족하거나, 초선형(super-linear) 계산 비용을 초래합니다. 대규모 시스템에 대해 효율적인 스케일링(scaling) 및 다중 스케일 다체 표현력과 함께 학습 가능한 장거리 등변 수송을 결합하는 것은 여전히 핵심 과제로 남아 있습니다. 본 논문에서는 장거리 텐서 표현 학습을 위해 고속 다중극 방법(Fast Multipole Method, FMM)을 신경 등변 방식으로 확장한 NEMORA(Neural Equivariant Multipole Operators)를 소개합니다. NEMORA는 적응형 공간 계층 구조상에서 FMM의 해석적 다중극 전개 및 변환 연산자를 학습 가능한 등변 연산자로 일반화합니다. 이 연산자들은 각도 차수를 결합하고 다양한 길이 스케일에 걸쳐 다체 상호작용을 형성하며, 데이터 의존적인 장거리 결합을 학습하는 동시에 FMM의 계층적 구조와 해석적 방사형 인자를 물리적 귀납 편향(inductive bias)으로 유지합니다. NEMORA는 선형 시간 및 메모리 복잡도로 평가되므로 수십만 개의 원자에 달하는 대규모 시스템을 다른 장거리 방식보다 효율적으로 다룰 수 있으며, 대칭 제약이 있는 백본 및 제약이 없는 단거리 백본 모두를 보강합니다. 비국소(non-local) 벤치마크에서 단거리 백본 대비 힘(force) 및 에너지 오차를 각각 1자릿수(order of magnitude) 이상, 최대 3자릿수까지 줄여, 정확도 측면에서 기존의 장거리 확장 기법보다 우수하거나 경쟁력 있는 성능을 보입니다.
최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정
Dual-GNN Multilevel Coarsening for Maximum Independent Set
최대 독립 집합(maximum independent set, MIS) 문제는 스케줄링, 자원 할당, 네트워크 분석 등에 응용되는 기본적인 NP-hard 조합 최적화(combinatorial optimization) 문제이다. 정확 솔버(exact solver)는 고품질 해 또는 최적성 증명(optimality certificate)을 제공할 수 있으나, 계산 비용은 그래프 크기에 따라 급격히 증가한다. 반면 수작업 휴리스틱(hand-crafted heuristic)은 보장을 희생하는 대신 확장성(scalability)을 개선한다. 학습 기반 방법은 그래프 인스턴스 간 구조적 패턴을 활용하는 대안을 제공하지만, 독립 집합을 직접 예측하면 대규모 그래프에서 전역 조율(global coordination)이 어려워질 수 있다. 우리는 대신 학습을 이용해 다중 수준 그래프 조 정(multilevel graph coarsening)을 안내하고, 최종 의사 결정에는 조합 탐색(combinatorial search)을 유지한다. Dual-GNN 다중 수준 조 정 프레임워크는 Partition GNN으로 후보 수축(contraction)을 점수화하고, Representative GNN으로 각 최종 클러스터에 대해 상위 k개의 지역 독립 집합 상태를 선택한다. 최대 2,000개 정점(vertex)을 갖는 Erdős–Rényi 그래프 실험에서 유리한 품질–실행 시간 트레이드오프(quality–runtime trade-off)를 보여준다. 인증된 최적해가 있는 500정점 인스턴스에서, 본 방법은 평균 독립 집합 크기 19.20을 달성하며 이는 최적값 19.30의 99.5%에 해당한다. 정확 해법의 평균 벽시계 시간(wall-clock time) 643.57초를 3.41초로 줄여 약 189배 속도 향상(speedup)을 얻는다. 1,000 및 2,000 정점의 더 큰 그래프에서는 평가된 모든 방법 중 최고의 평균 해 품질을 달성한다. 또한 가장자리 확률(edge probability) $p=0.35$인 Erdős–Rényi 그래프에서만 학습했음에도, 학습된 조 정 정책은 보지 못한 그래프 밀도와 구조적으로 다른 그래프 계열 모두에 효과적으로 일반화(generalize)된다.
저항 곡률 기반 확장 가능한 서브그래프 샘플링
Scalable Subgraph Sampling via Resistance Curvature
서브그래프 샘플링은 대규모 그래프 신경망(GNN)의 학습 비용을 줄이지만, 샘플링 기준은 엣지의 기하학적 역할을 간과할 수 있다. 우리는 대규모 그래프용 곡률 근사 방법인 ERC-LG 위에 구축한 저항 곡률(resistance curvature) 유도 샘플링 프레임워크를 제안한다. ERC-LG는 Johnson-Lindenstrauss 투영과 정규화된 다중 GPU 배치 공액 그래디언트(conjugate gradient) 솔버를 결합하여, 명시적인 라플라시안 의사역행렬(pseudoinverse) 계산과 전체 임베딩 저장을 피한다. 이렇게 얻은 곡률은 GNN 학습 서브그래프를 구성하기 위한 노드 및 엣지 샘플링 확률을 결정하는 데 활용된다. 실험 결과, 의사역행렬 기반 곡률과 수치적으로 일치하며 CG만 사용한 계산 대비 실행 시간이 감소한다. ERC-LG 기반 샘플링 변형은 다운스트림 노드 분류에서 7개 실세계 데이터셋 중 6개에서 최고 평균 정확도를 달성한다.
대규모 교통 예측을 위한 국소 이질성 및 지역 간 컨텍스트 학습
Learning Local Heterogeneity and Cross-Region Context for Large-Scale Traffic Forecasting
교통 흐름 예측은 지능형 교통 시스템에 필수적이다. 대규모 교통 예측은 국소 공간적 의존성과 지역 간 컨텍스트를 공동으로 모델링해야 한다. 지리적으로 인접한 노드 간 공간적 의존성은 도로 유형과 이동 방향의 차이로 인해 이질적이며, 모든 노드 쌍 상호작용을 통해 전역 정보를 획득하는 것은 상당한 계산 비용을 초래한다. 따라서 국소 이질성을 포착하면서 장거리 컨텍스트를 효율적으로 획득하는 것은 대규모 교통 예측에서 여전히 중요한 과제로 남아 있다. 이러한 과제를 해결하기 위해, 우리는 노드 이웃과 도로 네트워크 지역이라는 두 가지 상보적 세분성에서 공간적 의존성을 모델링하는 Local-Region Spatial Temporal(LoReST) 네트워크를 제안한다. 구체적으로, 관계 인지 국소 집계는 도로 및 방향별 특징 변환을 통해 지리적 이웃 내 이질적 의존성을 포착한다. 지역 간 상호작용은 평균 풀링을 통해 지역 표현을 구성하고, 지역 간 어텐션을 통해 장거리 컨텍스트를 교환한 뒤 이를 노드로 다시 전파한다. 국소 정보 집계와 지역 간 상호작용을 통합함으로써 LoReST는 대규모 도로 네트워크에서 공간적 의존성 학습을 효과적으로 수행할 수 있다. LargeST 벤치마크의 네 개 데이터셋에 대한 실험은 MAE, RMSE, MAPE에서 각각 평균 상대 감소율 4.78%, 3.60%, 5.75%를 보여준다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
부호 그래프 사전학습 및 프롬프트 학습
Signed Graph Pre-Training and Prompt Learning
부호 그래프(signed graph)는 엣지가 양수이거나 음수일 수 있으며 방향성을 가질 수도 있는 신뢰-불신 네트워크, 금융 상관관계 시스템, 생물학적 상호작용 그래프 및 기타 여러 도메인에서 발생합니다. 부호 그래프 신경망이 특정 태스크에 특화된 학습(training)을 향상시켰지만, 부호 그래프에서의 그래프 전이학습(transfer learning)은 여전히 미진한 상태입니다. 본 논문에서는 부호 그래프를 위한 선구적인 위상학 기반 그래프 사전학습(pre-training) 및 프롬프트(prompt) 학습 프레임워크인 TopoSIGN을 소개합니다. TopoSIGN은 자기 부호 라플라시안(magnetic signed Laplacian)을 기반으로 구축된 구조적 인코더와 Dowker 복합체 지속성 이미지(Dowker-complex persistence images)를 통해 부호 위상을 요약하는 새로운 지속성 호몰로지(persistent-homology) 브랜치를 결합합니다. 융합된 임베딩(embedding)은 이후 프롬프트 학습 함수로 전달됩니다. 합성 및 실제 데이터셋(dataset)에 대한 실험 결과는 부호 그래프에서 유용한 구조적 정보를 추출하는 TopoSIGN의 효능뿐만 아니라, 제안된 일반 프레임워크의 적응성과 유연성을 입증합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.