Covariance Kernels on Unordered Pair Spaces: Theory and Applications to Network-Valued Data

Many scientific problems are fundamentally relational: the quantity of interest is a connection between two objects, while the information that describes similarity is available for the objects themselves. This mismatch arises in brain networks, molecular interactions, and other high-dimensional systems. We develop a covariance framework for unordered relationships that transfers object-level geometry to the relations they form while preserving endpoint identity and invariance to ordering. Building on symmetric pairwise-kernel representations, we develop an inferential treatment for the loop-free domains used in undirected networks. The theory shows how removing self-pairs changes the relational spectrum and how that spectrum governs regularization. It also provides an exact measure of the inferential error introduced by spectral truncation. We further show how uncertainty in the underlying object geometry propagates through the pair covariance to the resulting estimator. Simulations illustrate when structured borrowing improves estimation and how that benefit can weaken under geometric misspecification. We then apply the framework to autism neuroimaging using resting-state functional-connectivity data from the Autism Brain Imaging Data Exchange (ABIDE). The analysis considers a 116-region brain parcellation, yielding 6670 unique functional connections. Despite this large nominal dimension, the induced relational covariance can be much lower dimensional. The application also shows that retaining a high proportion of covariance variation does not necessarily preserve the behavior of the shrinkage operator induced by the full covariance. These results illustrate how biologically meaningful information defined at the brain-region level can organize dependence among connections while retaining the connection itself as the inferential unit. The framework provides a principled foundation for covariance and regularization when the statistical units are unordered relationships.