The present study is a preliminary attempt to use graph theory for deriving distinct features of resting-state functional networks in young adults with autism spectrum disorder (ASD). Networks modeled neuromagnetic signal interactions between sensors using three alternative interdependence measures: (a) a non-linear measure of generalized synchronization (robust interdependence measure [RIM]), (b) mutual information (MI), and (c) partial directed coherence (PDC). To summarize the information contained in each network model we employed well-established global graph measures (average strength, assortativity, clustering, and efficiency) as well as graph measures (average strength of edges) tailored to specific hypotheses concerning the spatial distribution of abnormalities in connectivity among individuals with ASD. Graph measures then served as features in leave-one-out classification analyses contrasting control and ASD participants. We found that combinations of regionally constrained graph measures, derived from RIM, performed best, discriminating between the two groups with 93.75% accuracy. Network visualization revealed that ASD participants displayed significantly reduced interdependence strength, both within bilateral frontal and temporal sensors, as well as between temporal sensors and the remaining recording sites, in agreement with previous studies of functional connectivity in this disorder.