Statistical Guarantees for Link Prediction using Graph Neural Networks
원문 초록
This paper derives statistical guarantees for the performance of Graph Neural Networks (GNNs) in link prediction tasks on graphs generated by a graphon. We propose a linear GNN architecture (LG-GNN) that produces consistent estimators for the underlying edge probabilities. We establish a bound on the mean squared error and give guarantees on the ability of LG-GNN to detect high-probability edges. Our guarantees hold for both sparse and dense graphs. Finally, we demonstrate some of the shortcomings of the classical GCN architecture, as well as verify our results on real and synthetic datasets.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Open-World Social Event Classification
EasySpider: A No-Code Visual System for Crawling the Web
Patient Subtyping via Time-Aware LSTM Networks
Cross view link prediction by learning noise-resilient representation consensus
GRATE: 게이트 회전 어텐션을 통한 귀납적 지식 그래프 파운데이션 모델의 시간적 확장
GRATE: Temporal Extensions for Inductive KG Foundation Models via Gated Rotary Attention
Ultra, Trix와 같은 지식 그래프 파운데이션 모델은 관계 그래프 표현을 학습함으로써 미지의 개체 및 관계로 강력한 귀납적 전이를 달성한다. 이러한 전이 가능성을 시간적 지식 그래프(TKG)로 확장하는 것은 여전히 어려운 과제이다. 기존의 시간적 모델은 파라미터가 데이터셋 고유의 개체, 관계, 또는 타임스탬프에 고정되어 있어 어휘가 서로 다른 TKG로의 전이를 위해 설계되지 않았다. 우리는 학습 가능한 파라미터를 추가하지 않으면서 시간을 인코딩하는 개체 측 메시지 함수인 GRATE(Gated Rotary Attention for Temporal Encoding)를 제안한다. GRATE는 각 엣지 메시지를 쿼리와의 시간 간격에 따라 회전시켜 상대적 시간 차이를 인코딩하고, 쿼리 조건부 게이트를 적용하여 시간적으로 관련된 신호를 선택한다. GRATE는 구조적 전이 가능성을 유지하면서 NBFNet 방식의 지식 그래프 파운데이션 모델에 통합된다. 기존 TKG 벤치마크는 학습/테스트 어휘를 공유하는 환경에서만 평가하므로 데이터셋 간 시간적 전이를 직접 테스트하기 어렵다. 이를 위해 우리는 보간(interpolation)과 외삽(extrapolation) 모두를 아우르며 개체, 관계, 타임스탬프가 분리된 귀납적 전이 벤치마크 스위트인 GDELTIndT와 WIKIIndT를 구축하였다. 이 벤치마크들과 홀드아웃 예측 데이터셋 전반에 걸쳐, 단일 공동 사전학습 GRATE 체크포인트는 대부분의 설정에서 정적 베이스 모델을 능가한다.
미관측 교란 변수에 강건한 위험 점수 학습
Learning Risk Scores Robust to Unobserved Confounders
미관측 교란의 영향을 받는 역사적 관찰 데이터로부터, 희소 자원이나 개입 대상 개인의 우선순위를 정하기 위한 위험 점수를 학습하는 문제를 다룬다. 누가 희소 자원을 받을지에 대한 결정은 설문 응답과 같이 기록된 특성에 기반한 위험 점수에 의해 종종 안내된다. 이러한 위험 점수는 개인의 특성, 배분 결정, 결과에 대한 역사적 기록인 관찰 데이터로부터 직접 학습되는 경우가 점점 늘고 있다. 역사적 배분 정책이 도입한 바이어스를 보정하는 역 성향 가중치(inverse propensity weighting, IPW)와 같은 표준 방법은, 역사적 결정 과정이 기록된 특성으로 완전히 설명될 수 있다면 정확한 위험 점수를 학습하는 데 사용될 수 있다. 그러나 실무에서는 역사적 결정이 종종 기록되지 않은 정보에 의존하여, 학습된 위험 점수가 과거 우선순위를 이끌었던 기록되지 않은 상황을 가진 개인들을 정확히 체계적으로 과소 우선순위화하게 만든다. IPW를 기반으로, 이러한 종류의 미관측 교란에 강건한 위험 점수를 학습하는 방법을 제안한다. 미관측 교란 하에서는 성향 가중치를 신뢰할 수 있게 추정할 수 없으므로, 대신 관측 가능한 데이터와 교란 정도에 대한 도메인 정보 기반 추정치로 결정되는 불확실성 집합에 속하는 것으로 취급하며, 인과 추론(causal inference)의 민감도 분석(sensitivity analysis)과 Wasserstein 분포적 강건 최적화(Wasserstein distributionally robust optimization)를 결합한다. 그 결과 강건 위험 점수 학습 문제는 표본 기반 근사를 허용하며, 이를 기성 솔버와 호환되는 지수 원뿔 프로그램(exponential cone program)으로 재공식화한다. UCI Machine Learning Repository의 데이터셋에서 파생된 반합성(semi-synthetic) 데이터에서 접근법의 효과를 입증한다. 제안 방법은 다른 지표를 손상하지 않으면서, 전통적 벤치마크 대비 보정(calibration)을 최대 29.2%까지, 최신(state of the art) 대비 최대 11.1%까지 개선한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.