Systematically Exploring Associations among Multivariate Data

Lifeng ZhangAAAI 2020 · DOI

Abstract

Traditional correlation metrics often fail to capture complex, non-linear, or multivariate relationships. This paper introduces the neighbor correlation coefficient (nCor), a robust statistical tool that leverages local continuity through data reordering. By treating multivariate ordering as a Traveling Salesman Problem (TSP), nCor provides an intuitive, $R^2$-interpretable measure of association that excels in detecting interaction effects and non-linear patterns across high-dimensional datasets.

Introduction: Beyond Linear Correlation

In the era of "Big Data," identifying meaningful relationships within high-dimensional datasets is a primary challenge. While the Pearson correlation coefficient is a standard for linear associations, it is inadequate for curved, periodic, or interaction-based relationships. Newer methods like the Maximal Information Coefficient (MIC) and Distance Correlation (dCor) have made significant strides but often struggle with two major hurdles:

  1. Multivariate Complexity: Difficulty in scaling beyond pairs of variables.
  2. Interaction Blindness: An inability to distinguish between "main effects" (where a variable directly influences an outcome) and "interaction effects" (where the influence depends on another variable).

The nCor framework, proposed by Lifeng Zhang, seeks to provide a "one-stop-shop" metric that is computationally efficient, handles any functional form, and decomposes relationships into nonlinearity, interaction, and redundancy.

Methodology: Local Continuity through Reordering

The core innovation of nCor is the concept of local continuity. The fundamental hypothesis is that if a functional relationship exists between variables, points that are proximal in the predictor space ($x$) should also be proximal in the response space ($y$).

The Bivariate Intuition

For a single predictor $x$ and response $y$, nCor sorts the data by $x$ and measures the correlation between adjacent $y$ values in the resulting sequence. If a strong relationship exists, these "neighboring" $y$ values will be highly correlated, regardless of whether the global relationship is linear or highly non-linear, such as a sine wave.

Local continuity in a bivariate sinusoidal relationship.

The Multivariate Leap: TSP Reordering

Extending this logic to multivariate predictors requires a method to "sort" vectors. The nCor framework treats this as a Traveling Salesman Problem (TSP). It identifies a "short route" that visits every data point in the multi-dimensional $x$-space exactly once. By following this path, the algorithm creates an ordered sequence where neighbors in the path are neighbors in the $x$-space. This allows the calculation of local continuity for the response variable $y$ even in high-dimensional settings.

Multivariate extension using TSP paths (b) to order data points and capture complex interactions (a).

Derived Statistics for Structural Analysis

Beyond the base nCor score, the paper introduces three specialized metrics to characterize the nature of the association:

  • Coefficient of Interaction (COI): Measures how much of the association is due to variables working together.
  • Coefficient of Nonlinearity (CON): Quantifies the "bendiness" of the relationship compared to a linear model.
  • Coefficient of Essentialness (COE): Determines if a specific subset of variables is necessary to predict the outcome, helping identify redundant data.

Key Results and Real-World Application

The method was evaluated using complex simulated benchmarks and a massive real-world dataset from the World Health Organization and Gapminder (357 indicators across 202 countries).

  • Superior Detection: In simulated tests, nCor successfully identified relationships that state-of-the-art methods like MIC and dCor missed, particularly those involving complex interactions (e.g., $y = x_1x_2$).
  • $R^2$ Approximation: The nCor score consistently approximated the actual coefficient of determination ($R^2$) of underlying functions, providing a more interpretable result than raw mutual information scores.
  • Real-World Discovery: On Gapminder data, nCor and COI identified that "Industry Contribution to Economy" and "Gross National Income" have a strong interaction effect on health expenditure—a nuance that simpler correlation tests would overlook.

Conclusion

By using a Nearest Neighbor heuristic for the TSP, nCor maintains a computational complexity of $O(N^2)$, making it practical for large datasets. While performance depends on the quality of the TSP route, the method is robust to non-optimal reordering. Future work will explore more advanced path-finding algorithms to further improve accuracy in noisy, high-dimensional, and sparse data environments.

Summary updated

BibTeX
@inproceedings{zhang2020systematically,
  author = {Lifeng Zhang},
  title = {{Systematically Exploring Associations among Multivariate Data}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i04.6158},
}
Figure