Impaired brain development has been observed in newborns with congenital heart disease (CHD). We performed graph theoretical analyses and network-based statistics (NBS) to assess global brain network topology and identify subnetworks of altered connectivity in infants with CHD prior to cardiac surgery. Fifty-eight infants with critical/serious CHD prior to surgery and 116 matched healthy controls as part of the developing Human Connectome Project (dHCP) underwent MRI on a 3T system and high angular resolution diffusion MRI (HARDI) was obtained. Multi-tissue constrained spherical deconvolution, anatomically constrained probabilistic tractography (ACT) and spherical-deconvolution informed filtering of tractograms (SIFT2) was used to construct weighted structural networks. Network topology was assessed and NBS was used to identify structural connectivity differences between CHD and control groups. Structural networks were partitioned into core and peripheral nodes, and edges classed as core, peripheral, or feeder. NBS identified one subnetwork with reduced structural connectivity in CHD infants involving basal ganglia, amygdala, hippocampus, cerebellum, vermis, and temporal and parieto-occipital lobe, primarily affecting core nodes and edges. However, we did not find significantly different global network characteristics in CHD neonates. This locally affected sub-network with reduced connectivity could explain, at least in part, the neurodevelopmental impairments associated with CHD.