图 书 馆
第一:快速交互式属性子图匹配FIRST: Fast Interactive Attributed Subgraph Matching |
|
| 课程网址: | http://videolectures.net/kdd2017_du_attributed_subgraph/ |
| 主讲教师: | Boxin Du |
| 开课单位: | 视频讲座网 |
| 开课时间: | 2017-10-09 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | Attributed subgraph matching is a powerful tool for explorative mining of large attributed networks. In many applications (e.g., network science of teams, intelligence analysis, finance informatics), the user might not know what exactly s/he is looking for, and thus require the user to constantly revise the initial query graph based on what s/he finds from the current matching results. A major bottleneck in such an interactive matching scenario is the efficiency, as simply re-running the matching algorithm on the revised query graph is computationally prohibitive. In this paper, we propose a family of effective and efficient algorithms (FIRST) to support interactive attributed subgraph matching. There are two key ideas behind the proposed methods. The first is to recast the attributed subgraph matching problem as a cross-network node similarity problem, whose major computation lies in solving a Sylvester equation for the query graph and the underlying data graph. The second key idea is to explore the smoothness between the initial and revised queries, which allows us to solve the new/updated Sylvester equation incrementally, without re-solving it from scratch. Experimental results show that our method can achieve (1) up to 16 times speed-up when applying on networks with 6M+ nodes; (2) preserving more than 90% accuracy compared with existing methods; and (3) scales linearly with respect to the size of the query graph as well as the data graph. |
| 关 键 词: | 属性网络; 网络科学; 属性匹配 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2022-11-24：chenxin01 |
| 最后编审: | 2022-11-24：chenxin01 |
| 阅读次数: | 17 |