Testing Statistical Dependence in Labeled Graphs under Mismatches

Many real-world systems—ranging from protein structures to financial networks—are naturally represented as labeled graphs, where both topology and node attributes carry critical information. A fundamental question in analyzing such data is whether two graphs (or subgraphs) exhibit statistical dependence, which may indicate shared generative mechanisms or latent interactions. Unlike classical dependence testing, the graph setting introduces unique challenges: dependence can manifest through structural similarity, label correlation, or their interplay, potentially reinforcing or obscuring each other. We propose a novel and practical framework for dependence testing in labeled graphs via mutual information over a structure-weighted joint label distribution. This approach jointly captures topological and attribute-based signals while remaining robust to imperfect or noisy node alignments. We provide theoretical guarantees with explicit error bounds and validate our method on both synthetic and real-world datasets, including protein structures from the lipocalin family, and recurring motifs in the Cora citation network. Our results demonstrate that the proposed test is a statistically sound and an effective tool for uncovering nontrivial dependencies in graph data.