For a graph representation of a dataset, a straightforward normality measure for a sample can be its graph degree. Considering a weighted graph, this corresponds to sum of rows in a similarity matrix. The measure is intuitive given the abnormal samples are usually rare and they are dissimilar to the rest of the data. In order to have an in-depth theoretical understanding, in this manuscript, we investigate the graph degree in spectral graph clustering based and kernel based point of views and draw connections to a recent kernel method for the two sample problem. We show that our analyses guide us to choose fully-connected graphs whose edge weights are calculated via universal kernels. We show that a simple graph degree based unsupervised anomaly detection method with the above properties, achieves leading accuracy compared to other unsupervised anomaly detection methods on average over 10 widely used datasets. We also provide an extensive analysis on the effect of the kernel parameter on the method's accuracy.

论文研究了基于图形数据集表示的正常样本度量方法，通过对频谱图和核方法进行分析和连接，证明了使用基于通用核的全连接图上的简单图度量方法，能够实现比其他无监督异常检测方法更高的准确率，并详细分析了核参数对方法准确性的影响。

图的度数作为无监督正常性测量的理论研究