用拓扑和标签属性做图分类

图分类是一种重要的数据挖掘任务，在这一领域内，各种基于图的核函数方法被提出用于解决这一任务。该方法的有效性已经得到验证，但是，它们通常伴随着较高的计算开销。在这篇文章中，作者提出了一种基于全局拓扑属性以及全局标签特征构造特征向量的图分类方法。这种方法的核心思想是属于同一类别图的拓扑和标签属性应该是相似的。该方法简单易于实现，并通过在真实基准数据集上的详细比较显示，基于拓扑和标签特征的方法提供了更好的或具有竞争力的分类准确率，同时在计算效率上远超其他图核函数。这种图分类方法对于大型的无标签图来说是最有效的。 文档中提到的“random walk kernel”和“shortest path kernel”是图核方法的两种主要技术。Random walk kernel基于随机游走算法，通过图中路径的相似性来进行分类。它可以在图的不同部分之间建立联系，而不需要明确的节点对应关系。Shortest path kernel通过考虑所有节点对之间的最短路径来进行图的比较。这些方法可以捕捉到图结构的复杂特征，但如前所述，它们的计算代价很高。 图分类的应用领域广泛，从化学信息学到生物信息学，从电信网络到社交网络。在化学信息学中，可以用来区分对某个特定目标具有活性或无活性的化合物。在生物信息学中，它可以用于将蛋白质分类到不同的家族，或将组织样本进行分类。在电信领域，它可以通过客户的呼叫行为进行客户分类。在社交网络分析中，它可以通过用户在Twitter、Facebook等社交平台上的动态来进行用户分类。 图分类问题可以这样描述：有一组图Gi，i=1,...,N，其中每个图Gi=(Vi,Ei)，由顶点Vi的集合和边Ei的集合构成。每个图Gi可能在节点和边上有一些标记，这些标记来自数据集D的共同标记集Σ。每个图Gi都有一个对应的分类yi，yi属于一个分类集合C，C={1,...,k}。图分类的目标是学习一个模型：D→C，这个模型能够预测任何图的分类标签。 目前，在大型图数据集上进行有效图分类的挑战之一是如何处理庞大的图结构和潜在的计算复杂性。这通常需要算法具有高度的可伸缩性和鲁棒性，并且能够有效处理图数据的异质性和动态变化。通过使用拓扑和标签属性，可以提取出有助于分类的关键信息，从而减小了计算复杂性，并改善了分类效果。