NDLI: The Complexity of Mining Maximal Frequent Subgraphs

Content Provider	ACM Digital Library
Author	Kolaitis, Phokion G. Kimelfeld, Benny
Copyright Year	2014
Abstract	A frequent subgraph of a given collection of graphs is a graph that is isomorphic to a subgraph of at least as many graphs in the collection as a given threshold. Frequent subgraphs generalize frequent itemsets and arise in various contexts, from bioinformatics to the Web. Since the space of frequent subgraphs is typically extremely large, research in graph mining has focused on special types of frequent subgraphs that can be orders of magnitude smaller in number, yet encapsulate the space of all frequent subgraphs. $\textit{Maximal}$ frequent subgraphs (i.e., the ones not properly contained in any frequent subgraph) constitute the most useful such type. In this article, we embark on a comprehensive investigation of the computational complexity of mining maximal frequent subgraphs. Our study is carried out by considering the effect of three different parameters: possible restrictions on the class of graphs; a fixed bound on the threshold; and a fixed bound on the number of desired answers. We focus on specific classes of connected graphs: general graphs, planar graphs, graphs of bounded degree, and graphs of bounded treewidth (trees being a special case). Moreover, each class has two variants: that in which the nodes are unlabeled, and that in which they are uniquely labeled. We delineate the complexity of the enumeration problem for each of these variants by determining when it is solvable in (total or incremental) polynomial time and when it is NP-hard. Specifically, for the labeled classes, we show that bounding the threshold yields tractability but, in most cases, bounding the number of answers does not, unless P=NP; an exception is the case of labeled trees, where bounding either of these two parameters yields tractability. The state of affairs turns out to be quite different for the unlabeled classes. The main (and most challenging to prove) result concerns unlabeled trees: we show NP-hardness, even if the input consists of two trees and both the threshold and the number of desired answers are equal to just two. In other words, we establish that the following problem is NP-complete: given two unlabeled trees, do they have more than one maximal subtree in common?
Starting Page	1
Ending Page	33
Page Count	33
File Format	PDF
ISSN	03625915
e-ISSN	15574644
DOI	10.1145/2629550
Volume Number	39
Issue Number	4
Journal	ACM Transactions on Database Systems (TODS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-12-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graph mining Enumeration complexity Maximal frequent subgraphs
Content Type	Text
Resource Type	Article
Subject	Information Systems

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The complexity of mining maximal frequent subgraphs

SPIN: Mining maximal frequent subgraphs from graph databases (2004)

Spin: mining maximal frequent subgraphs from graph databases.

Spin: Mining maximal frequent subgraphs from graph databases (2004)

Spin: mining maximal frequent subgraphs from graph databases (2004).

Time and space efficient discovery of maximal geometric subgraphs (2007).

Mining frequent subgraphs over uncertain graph databases under probabilistic semantics

MARGIN: Maximal frequent subgraph mining

Time and space efficient discovery of maximal geometric graphs.

The Complexity of Mining Maximal Frequent Subgraphs

Similar Documents

The complexity of mining maximal frequent subgraphs

SPIN: Mining maximal frequent subgraphs from graph databases (2004)

Spin: mining maximal frequent subgraphs from graph databases.

Spin: Mining maximal frequent subgraphs from graph databases (2004)

Spin: mining maximal frequent subgraphs from graph databases (2004).

Time and space efficient discovery of maximal geometric subgraphs (2007).

Mining frequent subgraphs over uncertain graph databases under probabilistic semantics

MARGIN: Maximal frequent subgraph mining

Time and space efficient discovery of maximal geometric graphs.

The Complexity of Mining Maximal Frequent Subgraphs