Combinatorial correlation test

• Hypothesis testing for the correlation between the structure and data in a Graph:
  • “Data with structural information.”
  • Example: Investigating whether there is a correlation in the changes of population among prefectures with graph structure.
    • Specifically, examining if there is a correlation in the changes between neighboring prefectures.
  • Example: Geographical data of COVID-19 cases by region with graph structure.
• Scan statistic $K(x)$: The maximum of observed values below a certain threshold.
• P-value of K(x)=k: The probability of observing K(x)>=k under the null hypothesis.
  • The height of the P-value determines whether to reject the null hypothesis (no correlation) if there is a correlation.
• Utilizing Binary Decision Diagrams (BDD) to simplify computationally challenging aspects according to the patterns of Discrete Structure Processing techniques. (Expert in computer science)