arXiv:1401.1137

Sparse graphs using exchangeable random measures

François Caron, Emily B. Fox

제출 2014-01-06

원문 초록

Statistical network modeling has focused on representing the graph as a discrete structure, namely the adjacency matrix, and considering the exchangeability of this array. In such cases, the Aldous-Hoover representation theorem (Aldous, 1981;Hoover, 1979} applies and informs us that the graph is necessarily either dense or empty. In this paper, we instead consider representing the graph as a measure on $\mathbb{R}_+^2$. For the associated definition of exchangeability in this continuous space, we rely on the Kallenberg representation theorem (Kallenberg, 2005). We show that for certain choices of such exchangeable random measures underlying our graph construction, our network process is sparse with power-law degree distribution. In particular, we build on the framework of completely random measures (CRMs) and use the theory associated with such processes to derive important network properties, such as an urn representation for our analysis and network simulation. Our theoretical results are explored empirically and compared to common network models. We then present a Hamiltonian Monte Carlo algorithm for efficient exploration of the posterior distribution and demonstrate that we are able to recover graphs ranging from dense to sparse--and perform associated tests--based on our flexible CRM-based formulation. We explore network properties in a range of real datasets, including Facebook social circles, a political blogosphere, protein networks, citation networks, and world wide web networks, including networks with hundreds of thousands of nodes and millions of edges.

함께 살펴볼 논문

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

arXiv:2410.01432v3cs.LG공통 태그 Efficient Exploration공식 코드 · Papers with Code

상각 샘플러를 위한 적응형 교사

Adaptive teachers for amortized samplers

상각 추론(Amortized inference)은 신경망과 같은 매개변수 모델을 학습시켜, 정확한 샘플링이 불가능한 주어진 비정규화 밀도(unnormalized density)의 분포를 근사하는 작업이다. 샘플링이 순차적 의사결정 과정으로 구현될 때, 생성 플로우 네트워크(generative flow networks)와 같은 강화학습(RL) 방법을 사용하여 샘플링 정책을 학습시킬 수 있다. 오프-정책 강화학습 학습은 다양하고 보상이 높은 후보를 발견하는 데 도움이 되지만, 기존 방법들은 효율적인 탐험에서 여전히 어려움을 겪는다. 우리는 적응형 학습 분포(\teacher)를 사용하여 주된 상각 샘플러(\student)의 학습을 안내할 것을 제안한다. 보조 행동 모델인 \teacher는 \student의 손실이 큰 영역에서 샘플링하도록 학습되며, 아직 탐험되지 않은 모드들로 일반화할 수 있어 효율적인 학습 커리큘럼을 제공함으로써 모드 커버리지(mode coverage)를 향상시킨다. 우리는 탐험 과제를 제시하도록 설계된 합성 환경, 두 가지 확산 기반 샘플링 과제, 그리고 네 가지 생화학적 발견 과제에서 이 접근법의 효과를 검증하며, 샘플 효율성과 모드 커버리지를 개선할 수 있음을 보인다. 소스 코드는 https://github.com/alstn12088/adaptive-teacher 에서 확인할 수 있다.

토론

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