As the field of brain monitoring is evolving rapidly, there is an increasing demand of finding innovative ways to handle relevant signals. Especially electroencephalogram (EEG) signals provide a non-invasive way of diagnostic inference of brain’s functionality. Nevertheless, EEG signals are often corrupted by impulsive noise, thus prior denoising is required for accurate analysis and decision making. On the other hand, EEG signals admit naturally a representation in the form of graphs, with the electrodes corresponding to the nodes of the graph and the edges expressing the connectivity strength. To this end, graph signal processing (GSP) is a versatile tool, which enables the representation and analysis of graph-structured signals, whose interdependencies are encoded in the form of an appropriate adjacency matrix. To address the denoising of graph-structured signals, under impulsive noise conditions, this work introduces a regularized graph filtering scheme based on fractional lower order moments, coupled with distinct adjacency matrices inspired both by statistical approaches and visibility graphs that are better capable of capturing the topological and functional connectivity between the distinct nodes. The experimental evaluation on real EEG signals recorded in epileptic and non-epileptic seizures, reveals the effects of the adjacency matrix choice on the denoising performance.