Homophily as a Lossy Channel: Decomposing Information in Graphs and Graph Neural Networks
Vivek Kothari ⋅ Nic Lane
Abstract
Many GNN analyses reduce graph structure to label agreement (homophily), but in annotated graphs, edges often \emph{gate} how neighbor information is interpreted. We model the directed edge as a computational channel relating a target label $X$, neighbor label $Z$, and edge annotation $Y$. We introduce the \textbf{Adjusted Information Profile} $\rho(P)=(\sigma^\ast,\rho_Y^\ast,\phi^\ast)$, which decomposes the information provided by the neighborhood into redundancy, unique information, and synergy. Crucially, we normalize these atoms by \emph{structural channel capacities}, yielding bounded ratios comparable across diverse graphs. Leveraging a causal generative model that separates information emission from edge selection, we uncover the phenomenon of \emph{Topological Masking}: we show that homophilous selection acts as a causal collider, driving observed synergy toward zero even when the underlying mechanism is highly synergistic. Across controlled synthetic sweeps and annotated benchmarks-including text-enriched citation and protein interaction networks-the profile accurately predicts the ``Information Simplex'' regime, distinguishing datasets where topological smoothing suffices from where edge-conditioned relational architectures are required.
Chat is not available.
Successful Page Load