Da San Martino Giovanni, Navarin Nicolo, Sperduti Alessandro
IEEE Trans Neural Netw Learn Syst. 2018 Jul;29(7):3270-3276. doi: 10.1109/TNNLS.2017.2705694. Epub 2017 Jun 13.
The availability of graph data with node attributes that can be either discrete or real-valued is constantly increasing. While existing Kernel methods are effective techniques for dealing with graphs having discrete node labels, their adaptation to nondiscrete or continuous node attributes has been limited, mainly for computational issues. Recently, a few kernels especially tailored for this domain, and that trade predictive performance for computational efficiency, have been proposed. In this brief, we propose a graph kernel for complex and continuous nodes' attributes, whose features are tree structures extracted from specific graph visits. The kernel manages to keep the same complexity of the state-of-the-art kernels while implicitly using a larger feature space. We further present an approximated variant of the kernel, which reduces its complexity significantly. Experimental results obtained on six real-world data sets show that the kernel is the best performing one on most of them. Moreover, in most cases, the approximated version reaches comparable performances to the current state-of-the-art kernels in terms of classification accuracy while greatly shortening the running times.
具有可离散或实值节点属性的图数据的可用性正在不断增加。虽然现有的核方法是处理具有离散节点标签的图的有效技术，但它们对非离散或连续节点属性的适应性有限，主要是由于计算问题。最近，已经提出了一些专门针对该领域的核，这些核以预测性能换取计算效率。在本简报中，我们提出了一种用于复杂和连续节点属性的图核，其特征是从特定图访问中提取的树结构。该核在隐式使用更大特征空间的同时，设法保持与现有最先进核相同的复杂度。我们还提出了该核的一个近似变体，它显著降低了其复杂度。在六个真实世界数据集上获得的实验结果表明，该核在大多数数据集上表现最佳。此外，在大多数情况下，近似版本在分类准确率方面达到了与当前最先进核相当的性能，同时大大缩短了运行时间。
