论文标题
具有光学随机特征的快速图内内核
Fast Graph Kernel with Optical Random Features
论文作者
论文摘要
Graphlet内核是图形分类的经典方法。但是，由于其中包括的同构测试，它遭受了高计算成本。作为通用代理，总的来说，以丢失一些信息为代价，该测试可以通过计算各种图形特征的用户定义映射有效地代替。在本文中，我们建议在图形框架中利用内核随机特征，并建立具有平均内核度量的理论链接。如果对于通常的随机特征仍然可以过高的成本，那么我们将合并可以在恒定时间内计算的光随机特征。实验表明，所得算法的数量级比相同或更好的准确性的图形内核快。
The graphlet kernel is a classical method in graph classification. It however suffers from a high computation cost due to the isomorphism test it includes. As a generic proxy, and in general at the cost of losing some information, this test can be efficiently replaced by a user-defined mapping that computes various graph characteristics. In this paper, we propose to leverage kernel random features within the graphlet framework, and establish a theoretical link with a mean kernel metric. If this method can still be prohibitively costly for usual random features, we then incorporate optical random features that can be computed in constant time. Experiments show that the resulting algorithm is orders of magnitude faster that the graphlet kernel for the same, or better, accuracy.
