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 $\epsilon\in(0,1)$ similar to the original graph. Extensive experiments elucidate the efficacy of the proposed framework for real-world applications.
翻译:图表剖面是用来处理大比例图机器学习问题的一种广泛使用的维度减少技术。 在一张大图表中, 图形粗面旨在学习一个更小的可吸引的图表, 同时保存原图的特性。 图表数据包括节点特征和图形矩阵( 如相邻和拉平方)。 现有的图形粗面分析方法忽略了节点特征, 并仅仅依靠图表矩阵来简化图表。 在本文中, 我们引入了一个新的基于优化的图形维度减少框架。 拟议的框架在于统一图形学习和维度减少。 将图表矩阵和节点特性作为输入来学习, 并学习coarsen图形矩阵和coarsen特征矩阵, 同时确保理想属性。 拟议的优化配方是一个多块的非convelx优化问题, 这个问题通过利用块主要化- 最小化、 $\log 确定值、 dirichlet Energy 和正规化框架来有效解决。 提议的算法是: 图形学习的图形矩阵和节点矩阵, 并实际可适应到大量任务。 另外, 正在建立研拟的正价化模型。