A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs
Hypothesis testing is a statistical method used to draw conclusions about populations from sample data, typically represented in tables. With the prevalence of graph representations in real-life applications, hypothesis testing in graphs is gaining importance. In this work, we formalize node, edge, and path hypotheses in attributed graphs. We develop a sampling-based hypothesis testing framework, which can accommodate existing hypothesis-agnostic graph sampling methods. To achieve accurate and efficient sampling, we then propose a Path-Hypothesis-Aware SamplEr, PHASE, an m- dimensional random walk that accounts for the paths specified in a hypothesis. We further optimize its time efficiency and propose PHASEopt. Experiments on real datasets demonstrate the ability of our framework to leverage common graph sampling methods for hypothesis testing, and the superiority of hypothesis-aware sampling in terms of accuracy and time efficiency.
Code (1)
Tasks
Graph SamplingSimilar Papers 제목 키워드 기반
Hypothesis Stitcher for End-to-End Speaker-attributed ASR on Long-form Multi-talker Recordings
An end-to-end (E2E) speaker-attributed automatic speech recognition (SA-ASR) model was proposed recently to jointly perform speaker counting, speech recognition and speaker identification. The model achieved a low speake…
Automatic Speech RecognitionAutomatic Speech Recognition (ASR)FormSpeaker Identification+2Statistical Hypothesis Testing for Auditing Robustness in Language Models
Consider the problem of testing whether the outputs of a large language model (LLM) system change under an arbitrary intervention, such as an input perturbation or changing the model variant. We cannot simply compare two…
FairnessLarge Language ModelSemantic SimilaritySemantic Textual SimilarityEstablishment and Solution of a Multi-Stage Decision Model Based on Hypothesis Testing and Dynamic Programming Algorithm
This paper introduces a novel multi-stage decision-making model that integrates hypothesis testing and dynamic programming algorithms to address complex decision-making scenarios.Initially,we develop a sampling inspectio…
Decision MakingDeep Multi-Agent Reinforcement Learning for Decentralized Active Hypothesis Testing
We consider a decentralized formulation of the active hypothesis testing (AHT) problem, where multiple agents gather noisy observations from the environment with the purpose of identifying the correct hypothesis. At each…
Multi-agent Reinforcement Learningreinforcement-learningReinforcement LearningNull expectations and null hypothesis testing for the species abundance distribution
The number of elements (N) and types (S) sampled from an ecological system are among the most powerful constraints on observations of abundance, distribution, and diversity. Together, N and S determine sets of possible f…