The decoding of conscious experience, based on non-invasive measurements, has become feasible by tailoring machine learning techniques to analyse neuroimaging data. Recently, functional connectivity graphs (FCGs) have entered into the picture. In the related decoding scheme, FCGs are treated as unstructured data and, hence, their inherent format is overlooked. To alleviate this, tensor subspace analysis (TSA) is incorporated for the parsimonious representation of connectivity data. In addition to the particular methodological innovation, this work also makes a contribution at a conceptual level by encoding in FCGs cross-frequency coupling apart from the conventional frequency-specific interactions. Working memory related tasks, supported by networks oscillating at different frequencies, are good candidates for assessing the novel approach. We employed surface EEG recordings when the subjects were repeatedly performing a mental arithmetic task of five cognitive workload levels. For each trial, an FCG was constructed based on phase interactions within and between Frontal (θ) and Parieto-Occipital (α2) neural activities, which are considered to reflect the function of two distinct working memory subsystems. Based on the TSA representation, a remarkably high correct-recognition-rate (96%) of the task difficulties was achieved using a standard classifier. The overall scheme is computational efficient and therefore potentially useful for real-time and personalized applications.