In this study, the degree of connectivity for each voxel, which is the unit element of functional Magnetic Resonance Imaging (fMRI) data, with its neighboring voxels is estimated. The neighborhood system is defined by spatial connectivity metrics and a local mesh of variable size is formed around each voxel using spatial neighborhood. Then, the mesh arc weights, called Mesh Arc Descriptors (MAD), are used to represent each voxel rather than its own intensity value measured by functional Magnetic Resonance Images (fMRI). Finally, the optimal mesh size of each voxel is estimated using various information theoretic criteria. fMRI measurements are obtained during a memory encoding and retrieval experiment performed on a subject who is exposed to the stimuli from 10 semantic categories. Using the Mesh Arc Descriptors (MAD) having the variable mesh sizes, a k-NN classifier is trained. The classification performances reflect that the suggested variable-size Mesh Arc Descriptors represent the cognitive states better than the classical multi-voxel pattern representation and fixed-size Mesh Arc Descriptors. Moreover, it is observed that the degree of connectivities in the brain greatly varies for each voxel.