论文标题
一个统一的基于优化图形的框架
A Unified Framework for Optimization-Based Graph Coarsening
论文作者
论文摘要
图形粗化是一种广泛使用的维度缩小技术，用于接近大规模的图形机器学习问题。鉴于一个大图，图形粗化的目的是在保留最初给定的图的属性的同时学习较小的图形。图数据由节点特征和图矩阵（例如，邻接和拉普拉斯人）组成。现有的图形粗化方法忽略了节点特征，而仅依靠图矩阵来简化图形。在本文中，我们介绍了一个新型的基于优化的框架，用于降低图维数。提出的框架在于统一图和降低维度的统一。它同时将图形矩阵和节点特征作为输入，并在确保所需属性的同时，共同学习Coarsen Graph矩阵和Coarsen特征矩阵。提出的优化公式是多块非凸优化问题，通过利用块大型化最小化，$ \ log $ declatigals，dirichlet Energy和正则化框架来有效解决。所提出的算法被证明是收敛的，并且实际上可以接受许多任务。还确定，所学的粗糙图为$ε\ in（0,1）$类似于原始图。广泛的实验阐明了所提出的现实应用程序框架的功效。
Graph coarsening is a widely used dimensionality reduction technique for approaching large-scale graph machine learning problems. Given a large graph, graph coarsening aims to learn a smaller-tractable graph while preserving the properties of the originally given graph. Graph data consist of node features and graph matrix (e.g., adjacency and Laplacian). The existing graph coarsening methods ignore the node features and rely solely on a graph matrix to simplify graphs. In this paper, we introduce a novel optimization-based framework for graph dimensionality reduction. The proposed framework lies in the unification of graph learning and dimensionality reduction. It takes both the graph matrix and the node features as the input and learns the coarsen graph matrix and the coarsen feature matrix jointly while ensuring desired properties. The proposed optimization formulation is a multi-block non-convex optimization problem, which is solved efficiently by leveraging block majorization-minimization, $\log$ determinant, Dirichlet energy, and regularization frameworks. The proposed algorithms are provably convergent and practically amenable to numerous tasks. It is also established that the learned coarsened graph is $ε\in(0,1)$ similar to the original graph. Extensive experiments elucidate the efficacy of the proposed framework for real-world applications.
