图 书 馆
FASTEN：用于图形挖掘的快速Sylvester方程求解器FASTEN: Fast Sylvester Equation Solver for Graph Mining |
|
| 课程网址: | http://videolectures.net/kdd2018_du_fasten_sylvester_equation/ |
| 主讲教师: | Boxin Du |
| 开课单位: | 亚利桑那州立大学 |
| 开课时间: | 2018-11-23 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | The Sylvester equation offers a powerful and unifying primitive for a variety of important graph mining tasks, including network alignment, graph kernel, node similarity, subgraph matching, etc. A major bottleneck of Sylvester equation lies in its high computational complexity. Despite tremendous effort, state-of-the-art methods still require a complexity that is at least quadratic in the number of nodes of graphs, even with approximations. In this paper, we propose a family of Krylov subspace based algorithms (FASTEN) to speed up and scale up the computation of Sylvester equation for graph mining. The key idea of the proposed methods is to project the original equivalent linear system onto a Kronecker Krylov subspace. We further exploit (1) the implicit representation of the solution matrix as well as the associated computation, and (2) the decomposition of the original Sylvester equation into a set of inter-correlated Sylvester equations of smaller size. The proposed algorithms bear two distinctive features. First, they provide the exact solutions without any approximation error. Second, they significantly reduce the time and space complexity for solving Sylvester equation, with two of the proposed algorithms having a linear complexity in both time and space. Experimental evaluations on a diverse set of real networks, demonstrate that our methods (1) are up to 10, 000× faster against Conjugate Gradient method, the best known competitor that outputs the exact solution, and (2) scale up to million-node graphs. |
| 关 键 词: | FASTEN; 图形挖掘; 快速Sylvester方程求解器; Kronecker Krylov子空间; Sylvester方程; 图挖掘任务 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2023-03-27：cyh |
| 最后编审: | 2023-05-19：liyy |
| 阅读次数: | 31 |