skip to main content
10.1145/1150402.1150506acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
Article

Coherent closed quasi-clique discovery from large dense graph databases

Published: 20 August 2006 Publication History

Abstract

Frequent coherent subgraphs can provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databases has been witnessed several applications and received considerable attention in the graph mining community recently. In this paper, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the downward-closure property no longer holds. By fully exploring some properties of quasi-cliques, we propose several novel optimization techniques, which can prune the unpromising and redundant sub-search spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of only closed quasi-cliques. We also develop a coherent closed quasi-clique mining algorithm, <B>Cocain</B>1 Thorough performance study shows that Cocain is very efficient and scalable for large dense graph databases.

References

[1]
R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. VLDB'94.
[2]
V. Boginski, S. Butenko, P. M. Pardalos. On structural properties of the market graph. In A. Nagurney (editor), Innovations in Financial and Economic Networks, Edward Elgar Publishers, Apr. 2004.
[3]
H. Hu, X. Yan, Y. Hang, J. Han, X. Zhou. Mining coherent dense subgraphs across massive biological network for functional discovery. Bioinformatics, Vol. 21, Suppl. 1, 2005.
[4]
J. Pei, D. Jiang, A. Zhang. On mining cross-graph quasi-cliques. SIGKDD '05.
[5]
J. Wang, Z. Zeng, L. Zhou. CLAN: An Algorithm for Mining Closed Cliques From Large Dense Graph Databases. ICDE'06.
[6]
X. Yan, X. Zhou, J. Han. Mining closed relational graphs with connectivity constraints. SIGKDD '05.

Cited By

View all
  • (2025)Efficient Maximum s-Bundle Search via Local Vertex ConnectivityProceedings of the ACM on Management of Data10.1145/37096873:1(1-27)Online publication date: 11-Feb-2025
  • (2024)Contigra: Graph Mining with Containment ConstraintsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629589(50-65)Online publication date: 22-Apr-2024
  • (2024)Efficient Maximal Temporal Plex Enumeration2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00240(3098-3110)Online publication date: 13-May-2024
  • Show More Cited By

Index Terms

  1. Coherent closed quasi-clique discovery from large dense graph databases

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining
    August 2006
    986 pages
    ISBN:1595933395
    DOI:10.1145/1150402
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 20 August 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. coherent subgraph
    2. graph mining
    3. quasi-clique

    Qualifiers

    • Article

    Conference

    KDD06

    Acceptance Rates

    Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

    Upcoming Conference

    KDD '25

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)11
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 18 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Efficient Maximum s-Bundle Search via Local Vertex ConnectivityProceedings of the ACM on Management of Data10.1145/37096873:1(1-27)Online publication date: 11-Feb-2025
    • (2024)Contigra: Graph Mining with Containment ConstraintsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629589(50-65)Online publication date: 22-Apr-2024
    • (2024)Efficient Maximal Temporal Plex Enumeration2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00240(3098-3110)Online publication date: 13-May-2024
    • (2024)FocusCore Decomposition of Multilayer Graphs2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00218(2792-2804)Online publication date: 13-May-2024
    • (2024)On Searching Maximum Directed $(k, \ell)$-Plex2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00202(2570-2583)Online publication date: 13-May-2024
    • (2023)gCore: Exploring Cross-Layer Cohesiveness in Multi-Layer GraphsProceedings of the VLDB Endowment10.14778/3611479.361151916:11(3201-3213)Online publication date: 24-Aug-2023
    • (2023)Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design ApproachProceedings of the ACM on Management of Data10.1145/36173311:3(1-26)Online publication date: 13-Nov-2023
    • (2023)Maximal Quasi-Cliques Mining in Uncertain GraphsIEEE Transactions on Big Data10.1109/TBDATA.2021.30933559:1(37-50)Online publication date: 1-Feb-2023
    • (2022)Mining Stable Quasi-Cliques on Temporal NetworksIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2021.307172152:6(3731-3745)Online publication date: Jun-2022
    • (2022)Enumerating Maximum Cliques in Massive GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.303601334:9(4215-4230)Online publication date: 1-Sep-2022
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media