Detecting Trivariate Associations in High-Dimensional Datasets

Chuanlu Liu, Shuliang Wang, Hanning Yuan, Yingxu Dang, Xiaojia Liu

TL;DR

This paper introduces QOTIC, a novel method for detecting associations among three variables in high-dimensional datasets. QOTIC addresses the limitations of existing bivariate methods like MIC by offering improved generality and equitability, demonstrating higher accuracy and efficiency in experiments.

What Problem Does This Paper Address?

In today's data-rich world, identifying relationships between variables is crucial for data mining and knowledge discovery. While methods exist for finding associations between two variables (bivariate), detecting relationships involving three or more variables (multivariate), particularly trivariate associations, remains a significant challenge. Existing methods like the Maximal Information Coefficient (MIC) are excellent for bivariate analysis but struggle to extend to higher dimensions. This gap hinders our ability to uncover complex, multi-faceted dependencies hidden within high-dimensional datasets, which are common in fields like genomics, physics, and economics.

Methods

The core innovation of this paper is the Quadratic Optimized Trivariate Information Coefficient (QOTIC). QOTIC tackles the challenge of measuring trivariate dependence by introducing a novel quadratic optimization procedure. This procedure aims to achieve high accuracy and equitability in measuring the dependence among three variables.

Key aspects of the QOTIC method include:

  • Trivariate Mutual Information: It builds upon the concept of trivariate mutual information, which quantifies the shared information among three random variables.
  • Grid Partitioning: Similar to MIC, QOTIC uses a grid-based approach to analyze data. However, it extends this to a 3D space. The challenge lies in effectively partitioning this 3D space to capture complex relationships.
  • Quadratic Optimization: QOTIC employs a two-step dynamic partitioning strategy. First, it uses an adaptive equipartitioning of two axes (x and y) and then optimizes the third axis (z). Crucially, it then fixes the optimal partition on the z-axis and applies a quadratic optimization to the y-axis. This quadratic optimization step is key to improving accuracy and efficiency.
  • Generality and Equitability: The method is designed to be general, applicable to various data sizes and noise levels, and equitable, meaning it assigns similar scores to relationships of similar strength across different functional forms.

For comparison, the paper also defines and utilizes Exhaustive Search Trivariate Information Coefficient (ESTIC), which represents a more computationally intensive but potentially more accurate benchmark, and Trivariate Equipartition Information Coefficient (TEIC), which uses adaptive equipartitioning without the maximization step.

Datasets

The paper uses several datasets for evaluation:

  • Synthetic Datasets: A set of 12 functional relationships with varying degrees of complexity and noise levels were generated to test the generality and equitability of the proposed method against existing ones. These relationships are described in Table 1 and visualized in Figure 6.
  • Global Health Observatory (GHO) Dataset: This real-world dataset, collected from the World Health Organization (WHO) and the United Nations, contains 2938 samples across 18 columns related to life expectancy and its influencing factors. This dataset was used to demonstrate the practical application of QOTIC in exploring complex associations.

Key Insights and Ideas

  • The limitations of bivariate measures in multivariate contexts: The paper clearly illustrates how methods like MIC, while powerful for pairs, can miss crucial trivariate relationships. Figure 1 visually demonstrates how a strong trivariate association might be overlooked if only pairwise correlations are considered.
  • Equitability is crucial for reliable association detection: The research emphasizes the importance of equitability in correlation measures, ensuring that different types of relationships are assessed fairly. QOTIC's design prioritizes this.
  • Quadratic optimization offers a sweet spot between accuracy and efficiency: The core innovation of QOTIC lies in its quadratic optimization strategy. This approach allows for a more accurate capture of trivariate dependencies than simpler partitioning methods while being significantly faster than exhaustive search.
  • Real-world data reveals complex, non-obvious associations: The application to the GHO dataset highlights how QOTIC can uncover relationships that might not be apparent through simpler bivariate analyses, suggesting the presence of synergistic effects among multiple factors influencing life expectancy.

Key Results

  • Improved Equitability: Figures 3 and 8 demonstrate that QOTIC exhibits superior equitability compared to other methods like MTDIC, TEIC, Dcor, MIE, and NCIE, especially under varying noise levels and sample sizes. QOTIC's scores closely align with the coefficient of determination (R²) as noise decreases and sample size increases.
  • Higher Accuracy: Table 3 shows that QOTIC and ESTIC (the exhaustive search benchmark) achieve similar high correlation values across various functional relationships, outperforming MTDIC in many cases, especially with larger sample sizes.
  • Significant Time Efficiency: Table 4 and Figure 7 reveal that QOTIC is substantially faster than ESTIC. While MTDIC is the fastest, QOTIC achieves a 28% time reduction compared to ESTIC while maintaining comparable accuracy. This makes QOTIC a practical choice for analyzing large datasets.
  • GHO Dataset Findings: The analysis of the GHO dataset using QOTIC identified several strong trivariate associations, including those involving mortality factors and life expectancy, and immunization factors and life expectancy. Table 5 and Figure 9 provide specific correlation values for these relationships.

Limitations and Future Work

  • Trivariate Focus: A primary limitation acknowledged is that QOTIC is currently designed only for trivariate associations. Extending it to handle higher-dimensional data (multivariate associations) is a key area for future work.
  • Potential for Overestimation: The paper notes that selecting the maximum value in the trivariate characteristic matrix as the correlation measure might lead to overestimation, especially in the presence of noise. Future research aims to address this by proposing methods to detect and correct such overestimations.
  • Computational Cost for Higher Dimensions: While QOTIC is efficient for trivariate analysis, extending it to multivariate scenarios will likely introduce significant computational challenges that need to be addressed.

Summary updated

Abstract

Detecting correlations in high-dimensional datasets plays an important role in data mining and knowledge discovery. While recent works achieve promising results, detecting multivariable correlations especially trivariate associations still remains a challenge. For example, maximal information coefficient (MIC) introduces generality and equitability to detect bivariate correlations but fails to detect multivariable correlation. To solve the problem mentioned above, we proposed quadratic optimized trivariate information coefficient (QOTIC). Specifically, QOTIC equitably measures dependence among three variables. Our contributions are three-fold: (1) we present a novel quadratic optimization procedure to approach the correlation with high accuracy; (2) QOTIC exceeds existing methods in generality and equitability as QOTIC has general test functions and is applicable in detecting multivariable correlation in datasets of various sample sizes and noise levels; (3) QOTIC achieved both higher accuracy and higher time-efficiency than previous methods. Extensive experiments demonstrate the excellent performance of QOTIC.
BibTeX
@inproceedings{liu2022detecting,
  author = {Chuanlu Liu and Shuliang Wang and Hanning Yuan and Yingxu Dang and Xiaojia Liu},
  title = {{Detecting Trivariate Associations in High-Dimensional Datasets}},
  booktitle = {Sensors},
  year = {2022},
  url = {https://openreview.net/forum?id=BssGqUk2KL},
}
Figure