Autism spectrum disorder (ASD) is associated with altered patterns of over- and under-connectivity of neural circuits. Age-related changes in neural connectivities remain unclear for autistic children as compared with normal children. In this study, a parts-based network-decomposition technique, known as non-negative matrix factorization (NMF), was applied to identify a set of possible abnormal connectivity patterns in brains affected by ASD, using resting-state electroencephalographic (EEG) data. Age-related changes in connectivities in both inter- and intra-hemispheric areas were studied in a total of 256 children (3–6 years old), both with and without ASD. The findings included the following: (1) the brains of children affected by ASD were characterized by a general trend toward long-range under-connectivity, particularly in interhemispheric connections, combined with short-range over-connectivity; (2) long-range connections were often associated with slower rhythms ( δ and θ ), whereas synchronization of short-range networks tended to be associated with faster frequencies ( α and β ); and (3) the α -band specific patterns of interhemispheric connections in ASD could be the most prominent during early childhood neurodevelopment. Therefore, NMF would be useful for further exploring the early childhood developmental functional connectivity of children aged 3–6 with ASD as well as with typical development. Additionally, long-range interhemispheric alterations in connectivity may represent a potential biomarker for the identification of ASD.