Dynamics of Nonlinear Feature Learning in Two-Layer GCNs on XOR-CSBM

Graph Convolutional Networks (GCNs) are widely used for graph-structured data, but their training dynamics are not well understood. We study nonlinear feature learning in a two-layer GCN through a minimal XOR Contextual Stochastic Block Model (XOR-CSBM), where successful prediction requires nonlinear feature formation. By analyzing the population-gradient dynamics, we derive a tractable difference equation for the relevant representation variables. This reveals that feature learning proceeds through two distinct phases and ultimately yields task-relevant nonlinear representations.