Stochastic Block Models with Multiple Continuous Attributes
원문 초록
The stochastic block model (SBM) is a probabilistic model for community structure in networks. Typically, only the adjacency matrix is used to perform SBM parameter inference. In this paper, we consider circumstances in which nodes have an associated vector of continuous attributes that are also used to learn the node-to-community assignments and corresponding SBM parameters. While this assumption is not realistic for every application, our model assumes that the attributes associated with the nodes in a network's community can be described by a common multivariate Gaussian model. In this augmented, attributed SBM, the objective is to simultaneously learn the SBM connectivity probabilities with the multivariate Gaussian parameters describing each community. While there are recent examples in the literature that combine connectivity and attribute information to inform community detection, our model is the first augmented stochastic block model to handle multiple continuous attributes. This provides the flexibility in biological data to, for example, augment connectivity information with continuous measurements from multiple experimental modalities. Because the lack of labeled network data often makes community detection results difficult to validate, we highlight the usefulness of our model for two network prediction tasks: link prediction and collaborative filtering. As a result of fitting this attributed stochastic block model, one can predict the attribute vector or connectivity patterns for a new node in the event of the complementary source of information (connectivity or attributes, respectively). We also highlight two biological examples where the attributed stochastic block model provides satisfactory performance in the link prediction and collaborative filtering tasks.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정
Near-optimal node-private community estimation in polynomial-time
이 논문에서 우리는 Klopp & Zadik (2026)의 미해결 문제를 해결하여, 확률적 블록 모델(stochastic block model)에서의 정확 복원(exact recovery)에 대해 그들의 지수 시간 노드-프라이빗 알고리즘의 성능에 근접하는, 높은 확률을 보장하는 다항 시간 노드-프라이빗 알고리즘을 제시한다. 우리의 결과는 페널티 가능도 함수에 대해 명시적으로 구성된 립시츠 대리 함수(Lipschitz surrogate)와, 다항 시간 내에 지수 메커니즘(exponential mechanism)으로부터 커뮤니티 레이블을 샘플링하는 신중하게 고안된 수용-기각 알고리즘(accept-reject algorithm)을 포함한다. 우리는 제안 알고리즘의 프라이버시, 실행 시간, 유용성을 엄밀하게 분석하며, 커뮤니티 수 K가 노드 수 n에 대해 로그 수준으로 증가하는 경우에도 프라이버시 매개변수 epsilon이 log(n)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.
$\sqrt{n}$보다 많은 커뮤니티를 가진 확률적 블록 모델의 상전이
Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities
통계 물리학의 예측은 고정된 개수 $K$의 커뮤니티를 가진 확률적 블록 모델(SBM)에서 커뮤니티 복구가 Kesten-Stigum (KS) 임계값보다 위에서만 다항 시간 내에 가능하다고 가정합니다. 이 추측은 KS 임계값 위의 SBM에서 자명하지 않은 커뮤니티 복구가 실제로 가능하다는 것을 증명하는 풍부한 연구로 이어졌습니다. 관측된 그래프의 노드 수를 $n$이라 할 때, $K\ll \sqrt{n}$인 한 KS 임계값 아래에서 저차 다항식(LDP)의 실패 또한 증명되었습니다. $K\geq \sqrt{n}$일 때, Chin et al.(2025)은 최근 희소(sparse) 영역에서 비역행 경로(non-backtracking paths)를 계수함으로써 KS 임계값 아래에서도 다항 시간 내 커뮤니티 복구가 가능하다는 것을 증명했습니다. 이 획기적인 발견은 그들이 $K\geq \sqrt{n}$인 다중 커뮤니티 영역에 대한 새로운 임계값을 가정하게 이끌었습니다. 본 연구에서는 그들의 추측을 뒷받침하는 증거를 제시합니다: 1- 임의의 그래프 밀도에 대해, Chin et al.(2025)이 가정한 임계값 아래에서 LDP가 커뮤니티를 복구하는 데 실패함을 증명합니다; 2- LDP 분석에서 영감을 받은 특정 모티프(motifs)의 발생 횟수를 계수함으로써, Chin et al.(2025)에서 고려된 희소(sparse) 영역뿐만 아니라 중간 희소(moderately sparse) 영역에서도 가정된 임계값 위에서 다항 시간 내 커뮤니티 복구가 가능함을 증명합니다. 특히, 비역행 연산자(Non-Backtracking operator)에 기반한 스펙트럴 알고리즘(spectral algorithms)과 밀접하게 관련된 길이 $\log(n)$의 자기 회피 경로(self-avoiding paths) 계수는 희소 영역에서만 최적입니다. 더 조밀한 영역에서는 사이클의 확대(blow-up)에 기반한 더 복잡한 모티프를 고려해야 합니다.
Hypergraph Contrastive Learning for Drug Trafficking Community Detection
metapath2vec: Scalable Representation Learning for Heterogeneous Networks
Cross view link prediction by learning noise-resilient representation consensus
대규모 언어 모델에서 진실의 트릴레마
The Trilemma of Truth in Large Language Models
일반 대중은 대규모 언어 모델(LLM)에 인간과 유사한 특성을 부여하며, LLM이 특정 정보를 '알고' 있다고 가정하는 경우가 많다. 실제로 LLM은 학습 중 보존된 정보를 내부적 확률적 지식으로 인코딩한다. 본 연구는 해당 지식의 진위를 탐칭(probing)하는 기존 방법들을 검토하고, 세 가지 결함 있는 근본 가정을 밝힌다. 이러한 결함을 해결하기 위해, 다중 인스턴스 학습(MIL)과 conformal prediction을 결합한 다중 클래스 탐칭 프레임워크인 sAwMIL(Sparse-Aware Multiple-Instance Learning)을 제안한다. sAwMIL은 LLM의 내부 표현(representation)을 활용하여 진술을 참, 거짓, 또는 둘 다 아님으로 분류한다. 우리는 새롭게 구축한 세 개의 데이터셋을 사용하여, 기본형 및 채팅 기반 변형을 포함한 16개의 오픈소스 LLM에 대해 sAwMIL을 평가한다. 결과는 (1) 일반적인 탐칭 방법은 신뢰할 수 있고 전이 가능한(transferable) 진위 방향을 제공하지 못하며, 일부 설정에서는 제로샷(zero-shot) 프롬프팅(prompting)보다 성능이 낮음을, (2) 진실과 거짓은 대칭적으로 인코딩되지 않음을, (3) LLM이 참과 거짓 모두와 구별되는 제3의 유형의 신호를 인코딩함을 보여준다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.