arXiv:2609.27209v1 cs.LG

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

Scalable Subgraph Sampling via Resistance Curvature

Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li

제출 2026-09-24

한국어 초록

서브그래프 샘플링은 대규모 그래프 신경망(GNN)의 학습 비용을 줄이지만, 샘플링 기준은 엣지의 기하학적 역할을 간과할 수 있다. 우리는 대규모 그래프용 곡률 근사 방법인 ERC-LG 위에 구축한 저항 곡률(resistance curvature) 유도 샘플링 프레임워크를 제안한다. ERC-LG는 Johnson-Lindenstrauss 투영과 정규화된 다중 GPU 배치 공액 그래디언트(conjugate gradient) 솔버를 결합하여, 명시적인 라플라시안 의사역행렬(pseudoinverse) 계산과 전체 임베딩 저장을 피한다. 이렇게 얻은 곡률은 GNN 학습 서브그래프를 구성하기 위한 노드 및 엣지 샘플링 확률을 결정하는 데 활용된다. 실험 결과, 의사역행렬 기반 곡률과 수치적으로 일치하며 CG만 사용한 계산 대비 실행 시간이 감소한다. ERC-LG 기반 샘플링 변형은 다운스트림 노드 분류에서 7개 실세계 데이터셋 중 6개에서 최고 평균 정확도를 달성한다.

원문 초록

Subgraph sampling reduces the training cost of large-scale graph neural networks, but sampling criteria may overlook the geometric roles of edges. We propose a resistance-curvature-guided sampling framework built on ERC-LG, a curvature approximation method for large-scale graphs. ERC-LG combines Johnson-Lindenstrauss projections with regularized multi-GPU batched conjugate gradient solvers, avoiding explicit Laplacian pseudoinverse computation and full embedding storage. The resulting curvature informs node- and edge-sampling probabilities for constructing GNN training subgraphs. Experiments show numerical agreement with pseudoinverse-based curvature and reduced runtime compared with CG-only computation. ERC-LG-based sampling variants achieve the highest mean accuracy on six of seven real-world datasets in downstream node classification.

제출 이력

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

  1. arXiv:2609.27209v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2609.26855v3cs.LG공통 태그 Node Classification, Graph Neural Network, Graph Learning

QUARTET: 관계 그래프에서 트랜스포머를 강화하기 위한 4분기 교차 어텐션과 랜덤 워크 트레이스

QUARTET: Quad-branch cross-Attention and Random-walk Traces for Enhancing Transformers on Relational Graphs

관계 심층 학습(RDL)은 다중 테이블 데이터베이스를 이종 시간 그래프로 모델링하며, 그래프 트랜스포머는 RelBench와 같은 벤치마크에서 현재 최첨단 성능을 달성한다. 그러나 현재 선두 모델인 RelGT는 두 가지 핵심 한계가 있다. 무작위 로컬 샘플러가 느슨하게 연결된 부분 그래프를 만들어 메시지 전달을 방해하고, 전역 어텐션 모듈이 단일한 시드 특징 기반 메모리에만 의존해 더 넓은 거시적 수준의 역학을 놓친다. 이 한계를 극복하기 위해, 로컬 부분 그래프에 전체 셀프 어텐션을 적용하고 교차 어텐션 분기로 전역 문맥을 풍부히 하는 표현력 있는 그래프 트랜스포머 아키텍처 QUARTET을 제안한다. 구체적으로 QUARTET은 최근성 절단 개인화 PageRank(PPR)에 기반한 인과적 랜덤 워크(CRW) 샘플러로, 시간적 누출 없이 간결하고 허브-강건하며 밀집 연결된 로컬 부분 그래프를 추출한다. 동시에 4분기 교차 어텐션 모듈은 시드 특징, 시드 위상, 시간적 역학, 협력적 역학이라는 네 가지 상보적 관점에서 전역 문맥을 통합한다. RelBench v1 분류 과제 전반에서 QUARTET은 현재 최첨단 그래프 트랜스포머 기준선(HGT 및 RelGT)과 지속적으로 동등하거나 더 나은 성능을 보인다. 절제 연구는 CRW 샘플러가 로컬 이웃 품질을 크게 향상시키고, 전역 분기가 과제별로 필수적인 예측 이득을 제공함을 확인한다.

arXiv:2609.25149v2cs.LG공통 태그 Computational Efficiency, Graph Neural Network, Graph Learning

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

arXiv:2609.27092v1cs.LG공통 태그 Node Classification, Graph Neural Network, Graph Learning

학습된 GNN에서의 지역적 증거 및 기하학적 리드아웃 복구

Local Evidence and Geometric Readout Repair in Trained GNNs

많은 노드(node) 분류(classification) GNN은 로컬 메시지의 비음수 혼합에 선형 분류기를 적용합니다. 오류는 부적절한 혼합 가중치를 반영하거나, 도달 가능한 로짓(logit) 집합이 분류기에 적합하지 않게 배치되었음을 나타낼 수 있습니다. 본 연구에서는 정확한 질량(exact-mass) 선형 계획법과 두 가지 학습된 사후(post-hoc) 복구를 통해 이러한 원인들을 분리합니다. 모든 재가중치화(reweighting)된 예측은 동등한 중심화된 로짓 평행이동(translation)을 가지지만, 메시지로 유도된 변위 집합 내의 평행이동만이 재가중치화를 통해 실현 가능합니다. 8개의 데이터셋(dataset), 8개의 GNN 백본, 10개의 분할에 걸쳐 동결된 모델의 평균 정확도는 62.6%에서 재가중치화 적용 시 63.8%, 집합 조건부 평행이동 적용 시 65.3%로 상승합니다. 매개변수(parameter)가 일치된 노드 전용 평행이동기는 64.6%에 도달하여, 평행이동이 성능 향상의 대부분을 설명하는 반면 메시지 집합은 더 작은 추가적 이점을 제공함을 보여줍니다. 오라클(oracle) 재가중치화는 많은 오류를 수정할 수 있지만, 라벨 없는(label-free) 재가중치화는 이러한 잠재력을 거의 활용하지 못합니다. 즉, 로컬 증거는 종종 존재하지만 선택하기 어려우며, 증거 제약을 완화하는 것이 해당 제약 내에서 학습하는 것보다 더 효과적입니다.

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.13635v1cs.LG공통 태그 Node Classification, Graph Neural Network

PANDA: 사전 지식 기반 어텐션 이중 경로 아키텍처

PANDA: Prior-guided Attentional Dual-path Architecture

쌍별 상호작용(pairwise interaction)을 넘어 고차 관계(higher-order relation)를 모델링하기 위해 설계된 하이퍼그래프 신경망(Hypergraph Neural Network, HNN)은 일반적으로 고정된 구조적 가중치 또는 정규화된 어텐션에 의존한다. 고정 가중치는 이질적(heterophilic) 환경에서 잘못된 정보를 전파할 수 있으며, 정규화는 메시지 전달(message-passing) 프레임워크에서 하나의 송신자(sender)의 가중치를 높이면 동일한 집계 집합(aggregation set) 내 다른 송신자들의 가중치를 반드시 낮춰야 한다는 의미에서 어텐션 계수를 경쟁적으로 만든다. 본 연구의 주요 기여는 무방향 및 방향 설정 모두에 적용 가능한 2단계 메시지 전달 HNN을 위한 플러그인인 PANDA(Prior-guided AttentioNal Dual-path Architecture, 사전 지식 기반 어텐션 이중 경로 아키텍처)의 도입이다. 메인 경로(main path)는 학습된 수신자 정규화 어텐션과 구조적 인시던스(incidence) 사전 지식(prior) 사이를 보간(interpolate)하며, 비경쟁적인(정규화되지 않은) 보조 경로(auxiliary path)는 각 송신자가 자신만의 변환된 정보를 기여할 수 있도록 한다. 또한 고정된 구조적 계수를 사용할 경우, PANDA가 이전 연구들에서 채택된 특정 복소수 값 합성곱 연산자를 복원함을 보인다. 방향 및 무방향 설정에서 공간적(spatial) 및 스펙트럴(spectral) 방법을 포괄하는 네 가지 HNN에 걸쳐, PANDA를 적용하면 8개의 실세계 벤치마크 데이터셋에서 평균 5.18퍼센트포인트의 성능 향상을 얻는다. 코드는 https://github.com/jainris/panda 에서 확인할 수 있다.

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)를 제공함을 보여줍니다.

토론

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