TED+: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database

Kai Huang, Yue Cui, Qingqing Ye, Yan Zhao, Xi Zhao, Yao Tian, Kai Zheng, Haibo Hu, Xiaofang Zhou

Abstract

With an exponentially growing number of graphs from disparate repositories, there is a strong need to analyze a graph database containing an extensive collection of small- or medium-sized data graphs (e.g., chemical compounds). Although subgraph enumeration and subgraph mining have been proposed to bring insights into a graph database by a set of subgraph structures, they often end up with similar or homogenous topologies, which is undesirable in many graph applications. To address this limitation, we propose the Top-k Edge-Diversified Patterns Discovery problem to retrieve a set of subgraphs that cover the maximum number of edges in a database. To efficiently process such query, we present a generic and extensible framework called $\textsc {Ted}^+$ which achieves a guaranteed approximation ratio to the optimal result. Three optimization strategies are further developed to improve the performance, and a lightweight version called TedLite is designed for even larger graph databases. Experimental studies on real-world datasets demonstrate the superiority of $\textsc {Ted}^+$ to traditional techniques.
BibTeX
@article{huang2024ted,
  author = {Kai Huang and Yue Cui and Qingqing Ye and Yan Zhao and Xi Zhao and Yao Tian and Kai Zheng and Haibo Hu and Xiaofang Zhou},
  title = {{TED+: Towards Discovering Top-k Edge-Diversified Patterns in a Graph Database}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2024},
  doi = {10.1109/tkde.2023.3312566},
}

Loading related content...

Figure