用快速映射生成图嵌入，加速多个AI图问题求解
Revisiting FastMap: New Applications
- 将FastMap扩展到图数据，近线性时间生成欧氏嵌入
- 在图顶点上逼近图距离函数，用于设施选址等任务
- 结合SVM用于约束满足与地震波分类，效果优异
FastMap最初由数据挖掘领域提出，用于生成复杂对象的欧几里得嵌入。本文首次将FastMap用于图结构数据，在近线性时间内生成顶点的欧氏嵌入，使嵌入距离逼近预设的图基距离函数。随后，将该图版FastMap应用于多个人工智能中重要且复杂的图论问题：包括设施选址、前K位中心性计算、社区发现与块建模、以及图凸包计算。此外，提出一种新学习框架FastMapSVM，结合FastMap与支持向量机。该框架被用于预测约束满足问题的可满足性，以及在地震科学中对地震波形进行分类。
原文摘要 · Abstract (English)
FastMap was first introduced in the Data Mining community for generating Euclidean embeddings of complex objects. In this dissertation, we first present FastMap to generate Euclidean embeddings of graphs in near-linear time: The pairwise Euclidean distances approximate a desired graph-based distance function on the vertices. We then apply the graph version of FastMap to efficiently solve various graph-theoretic problems of significant interest in AI: including facility location, top-K centrality computations, community detection and block modeling, and graph convex hull computations. We also present a novel learning framework, called FastMapSVM, by combining FastMap and Support Vector Machines. We then apply FastMapSVM to predict the satisfiability of Constraint Satisfaction Problems and to classify seismograms in Earthquake Science.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。