arXiv:2510.04440v2 cs.LG

소규모 학습 샘플 크기에서의 준지도 그래프 학습을 위한 분수 열 커널

Fractional Heat Kernel for Semi-Supervised Graph Learning with Small Training Sample Size

Farid Bozorgnia, Vyacheslav Kungurtsev, Shirali Kadyrov, Mohsen Yousefnezhad

제출 2025-10-06

한국어 초록

우리는 비지역적(nonlocal) 전파와 지속적인 레이블 정보를 결합한, 준지도 그래프 학습을 위한 소스 기반(source-driven) 분수 열 커널(fractional heat-kernel) 프레임워크를 개발한다. 라플라시안(Laplacian) 널 공간(null space)과 양립 가능한 고정된 0이 아닌 레이블 소스는 해당 공간으로의 점근적 붕괴(collapse)를 방지하여, 긴 확산 시간에서 과평활화(oversmoothing)를 완화하는 메커니즘을 제공한다. 분수 차수(fractional order)는 상대적 모드 감쇠와 지속 응답의 스펙트럼 가중치를 제어하며, 확산 시간은 전파 범위(propagation horizon)를 설정한다. 우리는 정규화된 그래프와 비연결 그래프에서의 보존 법칙과 평형 상태를 규명하고, 널 공간 디플레이션(null-space deflation)을 개발하며, 전파 연산자(propagator)의 근사를 분석한다. Two-Moon에서는 분수 차수가 소스 없는 전파를 개선하며, 양립 가능한 소스 기반 확산은 차수 0.8과 1에서 클래스당 학습 레이블 1개로 평균 정확도 96%를 초과한다. Cora와 CiteSeer에서는 소스 기반 파이프라인이 클래스당 학습 레이블 1개에서 GAT보다 평균 정확도를 각각 9.2%p와 8.0%p 향상시키며, 500개의 레이블된 검증 노드에서 모델을 선택하고 고전적 파이프라인 구성과 분수 파이프라인 구성이 서로 근접하게 비교 가능하다; PubMed에서는 GAT와 동등한 성능을 보이며, Cora에서 클래스당 레이블 10개와 20개에서는 GAT보다 낮은 성능을 보인다. GraphHeat 내에서는 공통 확산 시간에서 검증 기반 지수 선택이 클래스당 레이블 1개에서 1.45%p의 짝비교(paired) 성능 향상을 가져온다.

원문 초록

We develop a source-driven fractional heat-kernel framework for semi-super\-vised graph learning that combines nonlocal propagation with sustained label information. A fixed nonzero label source compatible with the Laplacian null space prevents asymptotic collapse into that space, providing a mechanism for mitigating oversmoothing at long diffusion times. The fractional order controls the relative modal attenuation and the spectral weighting of the sustained response, while the diffusion time sets the propagation horizon. We characterize conservation laws and equilibria on normalized and disconnected graphs, develop a null-space deflation, and analyze the approximation of the propagators. On Two-Moon, fractional orders improve source-free propagation, while compatible source-driven diffusion exceeds $96\%$ mean accuracy with one training label per class at orders $0.8$ and $1$. On Cora and CiteSeer, the source-driven pipeline improves mean accuracy over GAT by $9.2$ and $8.0$ percentage points at one training label per class, with model selection on $500$ labeled validation nodes and closely comparable classical and fractional pipeline configurations; it matches GAT on PubMed and trails it at ten and twenty labels per class on Cora. Within GraphHeat, validation-based exponent selection at a common diffusion time yields a paired gain of $1.45$ percentage points at one label per class.

제출 이력

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

  1. arXiv:2510.04440v2

함께 살펴볼 논문

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

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

적응형 상보적 강화를 통한 이질성 환경에서 조정 기반 GNN 학습의 개선

Remedying Coarsening-Based GNN Training under Heterophily via Adaptive Complementary Enhancement

그래프 신경망(GNN)의 조정(coarsening) 기반 학습, 즉 원본 대규모 그래프 대신 조정된 그래프에서 학습하는 방식은 대규모 그래프로 GNN을 확장하는 유망한 방향이 되었다. 그러나 선행 연구는 거의 전적으로 동질성(homophilic) 그래프에서만 평가되어, 더 도전적인 이질성(heterophilic) 설정은 충분히 탐구되지 않았다. 우리는 경험적·이론적으로 기존 조정 기반 학습 방법이 조정 과정에서 불가피한 그래프 정보 손실로 인해 이질성 그래프에서 상당한 성능 저하를 겪는다는 것을 보인다. 이를 해결하기 위해, 조정 과정에서 버려진 정보를 재통합하는 플러그 앤 플레이, 모델 무관 전략인 적응형 상보적 강화(Adaptive Complementary Enhancement, ACE)를 제안한다. ACE는 원본 노드 특징을 재구성하는 투영기(projector)를 학습하고, 국소 이질성을 임베딩하기 위해 이방성 구조 정규화(anisotropic structural regularization)를 적용한다. 또한 동분산 불확실성 가중(homoscedastic uncertainty weighting)을 채택하여, 이질성 인식 투영기가 재구성한 증강 노드 특징을 사용한 전체 그래프 보조 손실과 주 조정 그래프 학습 손실로 구성된 결합 학습 목표를 적응적으로 균형 조정한다. 광범위한 실험에서 ACE는 최소한의 계산 오버헤드로 동질성 그래프에서 경쟁력 있는 결과를 유지하면서 이질성 벤치마크에서 일관된 성능 향상을 달성함을 보여준다. 코드는 GitHub 저장소 https://github.com/vasile-paskardlgm/ACE 에서 제공된다.

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

엔트로피 곡률을 통한 그래프 신경망의 국소-전역 기하학적 통찰

Local-Global Geometric Insights for Graph Neural Networks via Entropic Curvature

그래프에서의 곡률 개념, 특히 Ollivier-Ricci 곡률과 Forman 곡률은 oversmoothing과 oversquashing 같은 그래프 신경망(GNN)의 근본적 문제를 해결하는 강력한 도구로 부상했지만, 거의 전적으로 국소적 엣지 수준의 비교에 의존하기 때문에 정보가 실제로 장거리에 걸쳐 어떻게 전파되는지를 보증하지 못한다. 우리는 Wasserstein 측지선을 따라 엔트로피의 변위 볼록성(displacement convexity)을 통해 Lott-Sturm-Villani 프레임워크를 그래프로 확장하여 얻은 전역적·운송 기반 곡률인 Entropic Curvature(엔트로피 곡률)를 도입한다. 전역 엔트로피 곡률의 하한을 제공하는 계산 가능한 Weak Entropic Curvature(약 엔트로피 곡률) 프록시를 정의하고, 이로부터 (i) oversmoothing을 제어하는 Poincaré형 부등식, (ii) 운송-엔트로피 일반화 bound, (iii) 대규모 그래프에서 희소성, 강한 스펙트럴 확장, 양의 엔트로피 곡률이 공존할 수 없음을 보여 주는 확장 역설을 도출하며, oversmoothing과 oversquashing을 단일 곡률 스펙트럼의 양 극단으로 통합한다. 이 이론을 E-Gate 집계기, ENT 구조 인코딩, Midpoint-Completion Rewiring(MCR)의 세 가지 실용적 메커니즘으로 구현하고, SDRF, FoSR, BORF, LCP, Graph Ricci Flow와 비교하여 6개 노드 분류 벤치마크와 그래프 분류에서 벤치마크한다.

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

GNN의 정확한 Aumann-Shapley 어트리뷰션을 위한 다항식 아키텍처-어트리뷰션 공동 설계 프레임워크

A Polynomial Architecture-Attribution Co-Design Framework for Exact Aumann-Shapley Attribution in GNNs

그래프 신경망(GNN)에 대한 특징 수준 및 노드 수준 설명을 Aumann-Shapley 어트리뷰션 관점에서 연구한다. Integrated Gradients와 같은 경로 적분(path-integral) 방법은 어트리뷰션에 대한 공리적 공식화를 제공하지만, 심층 GNN에서의 실용적 사용은 일반적으로 경로 적분에 대한 유한 표본 수치 근사에 의존하며, 구적(quadrature) 오차와 계산 비용 사이의 트레이드오프가 필요하다. 본 논문은 다항식 GNN 아키텍처 하에서 어트리뷰션 적분을 정확히 계산 가능하게 만드는 모델-어트리뷰션 공동 설계 프레임워크인 APEX를 제안한다. 핵심 구성 요소는 PolyGIN으로, 메시지 전달(message-passing), 정규화, 및 변환 연산이 사전 소프트맥스 로짓과 같은 스칼라 모델 점수에 대해 유계 다변량 다항식 형태를 보존하는 GIN 스타일 그래프 네트워크이다. PolyGIN이 $L$개의 다항식 변환 블록을 갖는 경우, 어트리뷰션 경로를 따른 도함수의 차수는 최대 $2^L-1$임을 보인다. 따라서 Gauss-Legendre 구적은 $2^{L-1}$개의 결정적 평가 지점으로 Aumann-Shapley 경로 적분을 부동소수점 정밀도까지 정확히 계산할 수 있다. 이렇게 얻은 어트리뷰션은 특징 수준에서 계산한 뒤 완전성(completeness)을 유지하면서 노드 수준 점수로 집계할 수 있다. 합성 및 실세계 그래프 벤치마크에 대한 실험은 PolyGIN이 경쟁력 있는 예측 성능을 유지함을 보여주며, 완전한 APEX 프레임워크는 비교 기준선(baseline) 대비 더 높은 어트리뷰션 충실도를 달성하고 경로 적분에 필요한 평가 횟수를 크게 줄인다.

토론

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