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:
- Multivariate Complexity: Difficulty in scaling beyond pairs of variables.
- 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.
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.
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