IEEE Trans Neural Netw Learn Syst. 2013 Jun;24(6):977-89. doi: 10.1109/TNNLS.2013.2248093.
The aim of this paper is to explore the use of backtrackless walks and prime cycles for characterizing both labeled and unlabeled graphs. The reason for using backtrackless walks and prime cycles is that they avoid tottering, and can increase the discriminative power of the resulting graph representation. However, the use of such methods is limited in practice because of their computational cost. In this paper, we present efficient methods for computing graph kernels, which are based on backtrackless walks in a labeled graph and whose worst case running time is the same as that of kernels based on random walks. For clustering unlabeled graphs, we construct feature vectors using Ihara coefficients, since these coefficients are related to the frequencies of prime cycles in the graph. To efficiently compute the low order coefficients, we present an O(|V|(3)) algorithm which is better than the O(|V|(6)) worst case running time of previously known algorithms. In the experimental evaluation, we apply the proposed method to clustering both labeled and unlabeled graphs. The results show that using backtrackless walks and prime cycles instead of random walks can increase the accuracy of recognition.
本文旨在探索使用无回溯遍历和素循环来描述有标签和无标签的图。选择无回溯遍历和素循环的原因是它们可以避免摇晃，并提高生成图表示的辨别能力。然而，由于计算成本，这种方法在实践中受到限制。在本文中，我们提出了基于有标签图中的无回溯遍历的计算图核的有效方法，其最坏情况运行时间与基于随机游走的核相同。对于无标签图的聚类，我们使用 Ihara 系数构造特征向量，因为这些系数与图中的素循环的频率有关。为了有效地计算低阶系数，我们提出了一种 O(|V|(3))的算法，其运行时间优于以前已知算法的 O(|V|(6))最坏情况运行时间。在实验评估中，我们将所提出的方法应用于有标签和无标签图的聚类。结果表明，使用无回溯遍历和素循环而不是随机游走可以提高识别的准确性。
