  Deciphering the associations between network connectivity and nodal
attributes is one of the core problems in network science. The dependency
structure and high-dimensionality of networks pose unique challenges to
traditional dependency tests in terms of theoretical guarantees and empirical
performance. We propose an approach to test network dependence via diffusion
maps and distance-based correlations. We prove that the new method yields a
consistent test statistic under mild distributional assumptions on the graph
structure, and demonstrate that it is able to efficiently identify the most
informative graph embedding with respect to the diffusion time. The methodology
is illustrated on both simulated and real data.
