arXiv:2609.27278v1 cs.LG

희소 데이터를 위한 스펙트럴 연결성 사전분포 그래프 학습

Graph Learning with Spectral Connectivity Priors for Scarce Data

Mingxiao Liu (Tsinghua University, China), Bahar Oveisgharan (York University, Canada), Bingyan Zou (Tsinghua University, China), Gene Cheung (York University, Canada), H. Vicky Zhao (Tsinghua University, China), Feifei Gao (Tsinghua University, China)

제출 2026-09-24

한국어 초록

희소 데이터로부터 희소 그래프를 학습하는 것은 실용적으로 중요하지만 도전적이다. 익스팬더(expander) 유사 그래프가 보여 주는 국소 희소성과 강한 전역 연결성의 바람직한 결합에 영감을 받아, 라플라시안 스펙트럴 사전분포 계열을 통합해 전역 연결성을 명시적으로 촉진하는 spectral connectivity-regularized graph learning(SCoGL) 프레임워크를 제안한다. 구체적으로 SCoGL은 목표 인접 행렬 $\mathbf{W}$에 대한 combinatorial-Laplacian-constrained graphical lasso(GLASSO) 목적함수에, 라플라시안 고유값으로부터 계산한 일반적인 연결성 사전분포를 더한다. 여러 대표적 연결성 사전분포에 대한 그래디언트를 유도하고, $\mathbf{W}$를 효율적으로 최적화하기 위해 Armijo 백트래킹을 사용하는 투영 경사하강법(PGD) 알고리즘을 개발한다. 실험 결과, 제안한 SCoGL 변형들이 그래프 복원을 개선하며, 신호 관측이 희소할 때 그래프 신호 노이즈 제거와 같은 하류 과제에서도 성능을 향상시킨다.

원문 초록

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix $\mathbf{W}$ with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize $\mathbf{W}$. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

제출 이력

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

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

함께 살펴볼 논문

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

arXiv:2610.13765v1cs.LG공통 태그 Denoising, 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공통 태그 Denoising, 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)는 구조가 없는 그래프만을 생성합니다. 이러한 동작은 우리가 테스트한 모든 노드 크기에 걸쳐 유지됩니다.

arXiv:2609.24346v1cs.AI공통 태그 Denoising, Graph Learning

LADDER: 효율적 다중 홉 추론을 위한 그래프 가이드 확산 언어 모델

LADDER: Graph-Guided Diffusion Language Models for Efficient Multi-Hop Reasoning

그래프 검색-증강 생성(GraphRAG)은 구조화된 엔티티 토폴로지를 활용하여 복잡한 추론에서 대규모 언어 모델(LLM)의 성능을 크게 향상시켜 왔다. 그러나 기존 프레임워크는 표준 자기회귀(autoregressive) 언어 모델에 크게 의존하며, 본질적인 순차 생성 특성이 전체 추론 효율을 심각하게 저해한다. 연속적인 병렬 정제(refine-in-parallel) 디코딩을 통해 대규모 병렬성을 제공하는 확산 언어 모델(DLM)에서 영감을 받아, 우리는 이산 공간에서 GraphRAG를 가속하는 것을 목표로 한다. 그러나 두 가지 과제로 인해 이는 결코 사소하지 않다. 첫째, 부분적으로 디노이즈된 초안은 매우 동적이고 불확실하여 동적 그래프 그라운딩(grounding)이 쉽지 않다. 둘째, 원시 디노이즈 상태는 본질적으로 노이즈가 많고 불안정하여, 동기식 그래프 검색과 다중 홉 집계는 계산 비용이 과도하다. 이를 위해 우리는 그래프 가이드 병렬 디코딩을 통해 확산 언어 모델링과 GraphRAG를 연결하는 새로운 프레임워크 LADDER를 제안한다. 구체적으로, (i) 부분 디노이즈 상태에서 목표 엔티티의 88%가 조기에 등장하며 최종 확정(commitment)이 평균 5.7–9.6스텝 앞당겨진다는 핵심 통찰에 기반하여, 이벤트 기반 자체 클로킹(self-clocking) 검색을 제안한다. 이 메커니즘은 그래프 연결 가능(graph-linkable) 엔티티 집합이 확장될 때만 그래프 검색을 동적으로 트리거하여, 학습된 게이트나 휴리스틱 임계값을 우회하는 비동기 자체 클로킹 정책을 만든다. (ii) 불완전 쿼리(incomplete-query) 그래프 전파 모듈은 전문 그래프 파운데이션 모델을 사용하여 새로 등장하는 엔티티 쿼리를 처리하고, 다중 홉 증거를 지속적으로 집계하여 병렬 예측을 선명하게 하고 전체 디코딩 수렴을 가속하도록 설계되었다. 세 가지 도전적인 다중 홉 QA 벤치마크에 대한 광범위한 실험에서 LADDER는 평균 정확 일치를 39.6%에서 45.2%로 높이면서 지연(latency)을 4.1배 감소시킨다.

arXiv:2607.21634v1cs.LG공통 태그 Denoising, Graph Learning

MotifRole-Diff: 마스킹 분자 그래프 확산을 위한 위험 최적 역할 인식 손상

MotifRole-Diff: Risk-Optimal Role-Aware Corruption for Masked Molecular Graph Diffusion

분자 그래프 생성을 위한 마스킹 이산 확산(masked discrete diffusion)은 일반적으로 무손실 그래프-투-시퀀스(graph-to-sequence) 표현의 모든 토큰에 균일한 손상(corruption) 스케줄을 적용하며, 구조적으로 이질적인 분자 구성 요소를 재구성 난이도와 중요도가 동일한 것처럼 암묵적으로 취급한다. 그러나 서로 다른 분자 그래프 토큰 역할은 디노이징(denoising) 난이도와 디코딩된 분자에 미치는 영향에서 상당한 차이를 보이므로, 역할별 손상 전략이 필요하다. 본 논문은 MotifRole-Diff를 제안한다. 이는 경험적으로 측정된 디노이징 난이도와 그래프 수준 교란(perturbation) 영향에 따라 마스킹 비율을 할당하는 역할 인식 손상 과정으로, 모델 아키텍처, 깨끗한 시퀀스 공간, 무손실 분자 그래프 디코더는 그대로 유지한다. 우리는 스케줄 선택을 고정된 마스킹 예산을 토큰 역할 간에 위험 최적으로 할당하는 문제로 공식화한다. 우리의 정리는 모델링된 역할 가중 잔여 위험(role-weighted residual risk)에 대한 최적성을 특성화하며, 하류 생성 성능은 경험적으로 평가한다. 동일한 아키텍처, 학습 예산, 샘플링 연산량 하에서 MotifRole-Diff는 QM9에서 validity를 0.905에서 0.944로 향상시키고 FCD를 1.701에서 1.609로 감소시켰으며, MOSES에서는 validity를 0.920에서 0.938로 향상시키고 FCD를 2.125에서 1.850으로 감소시켰다. 역할별 진단은 분자 그래프 토큰 범주 전반에 걸친 재구성 개선을 추가로 보여준다. 종합하면, 이러한 동일 연산량 결과는 구조적으로 정보를 반영한 손상이 직렬화된 분자 그래프 확산에 있어 균일 스케줄보다 더 효과적인 마스킹 전략임을 시사한다.

arXiv:2607.21585v1cs.LG공통 태그 Denoising, Graph Learning

확장 Flow Map

Expanding Flow Maps

Flow 기반 생성 모델은 연속 및 이산 상태 공간 전반에서 빠르고 제어 가능한 생성의 놀라운 진전을 가능하게 해 왔지만, 기존 매개변수화는 고정 차원 또는 고정 시퀀스 길이로 제한된다. 본 연구에서는 조건부 노이즈로 상태를 보강하여 상태를 확장하는 확장 보간(expanding interpolant)을 따라 차원이 증가하는 분포들 사이의 flow를 정의하는 Expanding Generative Flows(EFlows)를 소개한다. 이 구성을 바탕으로, 확장 보간을 효율적인 소수 단계(few-step) 생성 모델로 증류(distillation)하는 flow map의 새로운 클래스인 Expanding Flow Maps(EFMs)를 제안한다. 각 EFM은 임의의 두 시간 단계 사이의 map을 두 가지 학습 가능한 연산으로 분해한다: 현재 상태를 조건으로 상태 공간에 새로운 좌표 또는 토큰(token)을 보강하는 확장 연산자(expand operator), 그리고 확장된 상태를 보간(interpolant)을 따라 앞으로 밀어주는 수송 map(transport map). 이 연산자들을 조합하면 상태를 동시에 확장하고 디노이징(denoise)하는 단일 map이 되며, 확장 연산자가 항등(identity)인 특수한 경우로 기존의 고정 캔버스(fixed-canvas) flow 및 flow map을 복원한다. 또한 프레임워크를 이산 심플렉스(discrete simplex)로 확장하여 가변 크기 그래프 생성과 가변 길이 시퀀스 생성을 가능하게 한다. 연속 및 이산 양식(modality) 모두에서, 출력 크기 자체가 학습 가능하고 제어 가능한 자유도인 설정을 위한 원칙적인 프레임워크로 EFlows와 EFMs를 확립한다.

arXiv:2607.21421v1cs.AI공통 태그 Denoising, Graph Learning

개연성과 허용 가능성 사이의 격차를 메우기: 동적 그래프 시스템을 위한 제약 인식 Flow Map

Bridging the Gap Between Plausibility and Admissibility: Constraint-Aware Flow Maps for Dynamic Graph Systems

생성 모델은 그럴듯한 미래 시스템 궤적의 앙상블을 생성함으로써 불확실성 하에서의 의사결정을 지원할 수 있지만, 통계적 개연성(statistical plausibility)이 구조적 실행 가능성(structural feasibility)을 보장하지는 않는다. 본 연구는 동적 그래프 구조 시스템에서 생성적 궤적 모델링의 신뢰성을 사후 샘플링(post-sampling) 기호적(symbolic) 제약이 개선할 수 있는지 조사한다. 조건부 확산 모델(conditional diffusion model)이 부분 관측으로부터 미래 그래프 상태 궤적을 생성하고, 외부 기호 층(symbolic layer)이 하드 필터링(hard filtering), 소프트 가중(soft weighting), 또는 투영 기반(projection-based) 복구(repair)를 적용한다. 이 프레임워크는 구조적 유효성, 샘플 효율성, 다양성, 견고성(robustness), 교정(calibration) 지표를 사용하여 두 가지 통제된 합성 체제—컴팩트 그래프와 중간 복잡도 의존성 그래프—에서 평가된다. 컴팩트 체제에서 모델은 0.002996의 무효 확률 질량(invalid probability mass)을 생성하며, 이는 거의 완전히 허용 가능한(admissible) 궤적 매니폴드를 나타낸다. 동일한 아키텍처와 학습 프로토콜 하에서, 중간 복잡도 체제에서는 무효 질량이 0.155929로 증가한다. 하드 필터링은 생성된 샘플의 84.4%를 보존하면서 보존된 모든 무효 궤적을 제거하는 반면, 소프트 가중은 유효 표본 크기(effective sample size)를 보존하지만 제한적인 유효성 향상만을 제공한다. 계열(family) 수준 분석은 의존성 제약(dependency constraints)이 관측된 거의 모든 비허용(inadmissibility)을 설명함을 보여준다. 이 결과는 통계적 개연성과 구조적 허용 가능성이 서로 다른 신뢰성 속성임을, 그리고 그래프 구조적 복잡도가 증가할수록 기호적 제약 처리가 더 가치 있어짐을 나타낸다.

토론

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