arXiv:2609.25149v2 cs.LG

최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정

Dual-GNN Multilevel Coarsening for Maximum Independent Set

Tianfeng Chen, Xianyue Li

제출 2026-09-24

한국어 초록

최대 독립 집합(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)된다.

원문 초록

The maximum independent set (MIS) problem is a fundamental NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, and network analysis. Exact solvers can provide high-quality solutions or optimality certificates, but their computational cost grows rapidly with graph size, while hand-crafted heuristics improve scalability at the expense of guarantees. Learning-based methods offer an alternative by exploiting structural patterns across graph instances, yet directly predicting independent sets can make global coordination difficult on large graphs. We instead use learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making. Our Dual-GNN Multilevel Coarsening framework uses a Partition GNN to score candidate contractions and a Representative GNN to select top-k local independent-set states for each final cluster. Experiments on Erd\H{o}s--R\'enyi graphs with up to 2,000 vertices demonstrate a favorable quality--runtime trade-off. On 500-vertex instances with certified optima, our method achieves an average independent-set size of 19.20, corresponding to 99.5\% of the optimal value of 19.30, while reducing the mean wall-clock time from 643.57 seconds for exact solving to 3.41 seconds, yielding an approximately 189$\times$ speedup. On larger graphs with 1,000 and 2,000 vertices, our method achieves the best mean solution quality among all evaluated methods. Moreover, although trained only on Erd\H{o}s--R\'enyi graphs with edge probability $p=0.35$, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.25149v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.27209v1cs.LG공통 태그 Computational Efficiency, Graph Neural Network, Graph Learning

저항 곡률 기반 확장 가능한 서브그래프 샘플링

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개에서 최고 평균 정확도를 달성한다.

arXiv:2609.28085v1cs.LG공통 태그 Computational Efficiency, Combinatorial Optimization, Graph Neural Network

잡 샵 스케줄링을 위한 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시간 절약했다.

arXiv:2609.25722v3cs.LG공통 태그 Graph Neural Network, Graph Learning

부호 그래프 사전학습 및 프롬프트 학습

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의 효능뿐만 아니라, 제안된 일반 프레임워크의 적응성과 유연성을 입증합니다.

arXiv:2610.13689v1cs.LG공통 태그 Graph Neural Network, Graph Learning

VQIL: 그래프 상의 섭동 반응 순위화를 위한 가시적 양자 간섭 학습

VQIL: Visible Quantum Interference Learning for Perturbation Response Ranking on Graphs

국소적 섭동(perturbation)이 네트워크에 미치는 영향을 학습하는 것은 시스템의 반응을 유발하거나 흡수하는 구성 요소를 식별하는 데 중요합니다. 본 연구에서는 이를 시드 조건부 반응 순위화(seed-conditioned response ranking) 문제로 정의합니다. 즉, 하나의 시드 노드(node)에서 섭동이 발생했을 때 다른 모든 노드를 반응 강도에 따라 순위화하는 것입니다. 이는 모델(model)에 상호작용 토폴로지만 주어지고 섭동이 전파되는 방식을 지배하는 메커니즘을 데이터로부터 학습해야 할 때 특히 어렵습니다. 본 논문에서는 시드 조건부 순위화를 위한 학습 가능한 세게디 양자 워크(Szegedy quantum walk)인 VQIL(Visible Quantum Interference Learning)을 제안합니다. 워크 연산자가 학습(training) 전반에 걸쳐 유니터리(unitary) 상태를 유지하는 동안, 에지 가중치, 링크 위상, 노드별 위상 회전이 역전파(backpropagation)를 통해 엔드투엔드로 최적화됩니다. 노드 점수는 양자 워크 진폭의 기하학적 감쇠 코히런트 합(coherent sum)에서 얻어지며, 이를 통해 최종 제곱 노름(squared-norm) 판독 전에 양자 간섭이 가능해집니다. 학습된 각 매개변수(parameter)는 명명된 에지 또는 노드에 연결되어 있으므로, 학습된 모델은 전파 메커니즘에서 개별 그래프 구성 요소의 역할에 대해 직접 검사 가능한 가설을 제공합니다. 전기적 매개변수를 모델에 제공하지 않은 6개 송전망에 대한 교류 조류(AC power-flow) 섭동 실험에서, VQIL은 스피어만 순위 상관계수를 학습되지 않은 워크의 0.147에서 0.831로 향상시켰으며 동일하게 학습된 무작위 워크 모델의 성능을 능가했습니다. Perturb-seq 지도 신호가 있는 5개 단백질-단백질 상호작용 네트워크에 대한 유전자 섭동 실험에서 VQIL은 순위 상관계수를 0.171에서 0.620으로 향상시켜 가장 강력한 고전적 및 신경망 기반 학습 베이스라인들을 능가했습니다. 이러한 결과는 학습 가능한 양자 워크 간섭이 그래프 상에서 시드 조건부 반응 순위를 학습하기 위한 확장 가능하고 해석 가능한 귀납적 바이어스(inductive bias)를 제공함을 보여줍니다.

arXiv:2610.13765v1cs.LG공통 태그 Graph Neural Network, Graph Learning

엣지 독립성이 실패할 때: 잠재 사회성 사전분포를 이용한 결합 그래프 디퓨전

When Edge Independence Fails: Joint Graph Diffusion with Latent Sociability Priors

이산 그래프 디퓨전 모델은 마르코프 노이즈 모델을 사용한 독립적인 엣지(edge) 업데이트를 통해 그래프 구조를 손상시킨다. 출력 분포에 대한 교환가능성(exchangeability) 요구 조건과 결합되면, 터미널 사전분포(prior)는 필연적으로 에르되시-레니(Erdős–Rényi, E-R) 랜덤 그래프가 된다. 이는 노드 특징(feature) 없는 비조건부 그래프 생성에 근본적인 결과를 초래한다: 큰 그래프의 극한에서, E-R 그래프에 적용된 모든 GNN 디노이저(denoiser)는 대략적으로 E-R 그래프를 출력하여, 효과적인 디노이징(denoising)을 어렵게 만든다. 실제로, 생성된 그래프는 의미 있는 노드 이질성(heterogeneity)과 고차 구조(higher-order structure)를 복원하지 못한다. 이전 모델들은 이를 보완하기 위해 전문화된 노드 특징을 도입했으며, 이를 표현력(expressivity) 문제로 간주했지만, 사전분포의 역할은 검토되지 않은 채로 남아 있었다. 우리는 대신 잠재 사회성 사전분포(Latent Sociability Prior, LSP)와, 잠재 노드 사회성(sociability) 변수와 그래프 구조를 함께 진화시키는 결합(joint) 디퓨전 프로세스를 도입하여 근본 원인을 해결하며, 교환가능성을 유지하면서 엣지 독립성을 제거한다. 기존의 잠재 그래프 디퓨전 방법들과 달리, 사회성 메커니즘은 복잡한 인코더(encoder)를 필요로 하지 않는다: 그 유일한 역할은 엣지 업데이트를 안내하고 궤적(trajectory) 전체에서 노드 이질성을 보존하는 것이다. 우리는 여러 그래프 생성 데이터셋에서 접근법을 검증하고, 제안된 프레임워크가 노드 특징이 없는 기준선(baseline) 방법들보다 그래프 분포를 더 정확하게 포착함을 보인다.

arXiv:2610.13786v1cs.LG공통 태그 Graph Neural Network, Graph Learning

이산 그래프 확산 모델은 은밀하게 암기하고 있다

Your Discrete Graph Diffusion Model is Secretly Memorizing

이산 그래프 확산 모델(Discrete graph diffusion models, GDM)은 마르코프(Markovian) 노이즈 모델 하에서 노드(node)와 에지에 독립적으로 노이즈를 추가하여 그래프 구조를 손상시킵니다. 노드 특징이 없는 무조건부 설정에서, 단일 그래프로 학습(training)된 등변 노이즈 제거기(equivariant denoiser)는 새로운 그래프를 생성할 수 있으며 에지 겹침(edge overlap) 및 WL 커널(kernel) 유사도와 같은 샘플 수준의 지표에서는 암기의 증거를 찾을 수 없습니다. 본 연구에서는 이러한 관점에 이의를 제기하고, 그래프 확산 모델이 실제로 암기 현상을 보인다는 점을 최초로 입증합니다. 2-블록 확률적 블록 모델(stochastic block models, SBM)로 학습된 GDM의 역방향 확산 궤적(reverse diffusion trajectory)을 분석한 결과, 강력한 학습 데이터 바이어스(bias)를 발견했습니다. 즉, 모델(model)은 제외된 테스트 그래프에 비해 손상된 학습 그래프를 거의 완벽하게 복원합니다. 이러한 현상은 역방향 궤적이 손상된 학습 그래프에 조건화될 때만 나타나고 추론(inference) 중에는 드러나지 않으므로, 우리는 이를 조건부 암기(conditional memorization)라고 명명합니다. 이는 제외된 그래프에서의 손실(loss)이 악화되는 반면 학습 손실은 개선되는 일반화 격차(generalization gap)의 확대와 일치하며, 조기 종료(early stopping)로도 완화할 수 없습니다. 암기의 시작은 항상 생성된 그래프에서 커뮤니티 구조의 출현보다 앞서 발생하므로, 그보다 앞선 모든 체크포인트(checkpoint)는 구조가 없는 그래프만을 생성합니다. 이러한 동작은 우리가 테스트한 모든 노드 크기에 걸쳐 유지됩니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.