FLEXIS: FLEXible Frequent Subgraph Mining using Maximal Independent Sets Article Swipe

PDF

Akshit Sharma , Sam Reinher , Dinesh Kumar Mehta , Bo Wu ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2404.01585

Frequent Subgraph Mining (FSM) is the process of identifying common subgraph patterns that surpass a predefined frequency threshold. While FSM is widely applicable in fields like bioinformatics, chemical analysis, and social network anomaly detection, its execution remains time-consuming and complex. This complexity stems from the need to recognize high-frequency subgraphs and ascertain if they exceed the set threshold. Current approaches to identifying these patterns often rely on edge or vertex extension methods. However, these strategies can introduce redundancies and cause increased latency. To address these challenges, this paper introduces a novel approach for identifying potential k-vertex patterns by combining two frequently observed (k - 1)-vertex patterns. This method optimizes the breadth-]first search, which allows for quicker search termination based on vertices count and support value. Another challenge in FSM is the validation of the presumed pattern against a specific threshold. Existing metrics, such as Maximum Independent Set (MIS) and Minimum Node Image (MNI), either demand significant computational time or risk overestimating pattern counts. Our innovative approach aligns with the MIS and identifies independent subgraphs. Through the "Maximal Independent Set" metric, this paper offers an efficient solution that minimizes latency and provides users with control over pattern overlap. Through extensive experimentation, our proposed method achieves an average of 10.58x speedup when compared to GraMi and an average 3x speedup when compared to T-FSM

Related Topics

Computer Science

Data Mining

Concepts

Computer science Data mining

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2404.01585
PDF: https://arxiv.org/pdf/2404.01585
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4393928614

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4393928614

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2404.01585

Digital Object Identifier
Title: FLEXIS: FLEXible Frequent Subgraph Mining using Maximal Independent Sets

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-04-02

Full publication date if available
Authors: Akshit Sharma, Sam Reinher, Dinesh Kumar Mehta, Bo Wu

List of authors in order
Landing page: https://arxiv.org/abs/2404.01585

Publisher landing page
PDF URL: https://arxiv.org/pdf/2404.01585

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2404.01585

Direct OA link when available
Concepts: Computer science, Data mining

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4393928614
doi	https://doi.org/10.48550/arxiv.2404.01585
ids.doi	https://doi.org/10.48550/arxiv.2404.01585
ids.openalex	https://openalex.org/W4393928614
fwci
type	preprint
title	FLEXIS: FLEXible Frequent Subgraph Mining using Maximal Independent Sets
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10538
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9904999732971191
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1710
topics[0].subfield.display_name	Information Systems
topics[0].display_name	Data Mining Algorithms and Applications
topics[1].id	https://openalex.org/T11063
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9750999808311462
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1703
topics[1].subfield.display_name	Computational Theory and Mathematics
topics[1].display_name	Rough Sets and Fuzzy Logic
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.4752499759197235
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C124101348
concepts[1].level	1
concepts[1].score	0.4190901815891266
concepts[1].wikidata	https://www.wikidata.org/wiki/Q172491
concepts[1].display_name	Data mining
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.4752499759197235
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/data-mining
keywords[1].score	0.4190901815891266
keywords[1].display_name	Data mining
language	en
locations[0].id	pmh:oai:arXiv.org:2404.01585
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2404.01585
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2404.01585
locations[1].id	doi:10.48550/arxiv.2404.01585
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2404.01585
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5101171739
authorships[0].author.orcid
authorships[0].author.display_name	Akshit Sharma
authorships[0].author_position	first
authorships[0].raw_author_name	Sharma, Akshit
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5094581151
authorships[1].author.orcid
authorships[1].author.display_name	Sam Reinher
authorships[1].author_position	middle
authorships[1].raw_author_name	Reinher, Sam
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5058003383
authorships[2].author.orcid	https://orcid.org/0000-0003-4908-7437
authorships[2].author.display_name	Dinesh Kumar Mehta
authorships[2].author_position	middle
authorships[2].raw_author_name	Mehta, Dinesh
authorships[2].is_corresponding	False
authorships[3].author.id	https://openalex.org/A5025476506
authorships[3].author.orcid	https://orcid.org/0000-0002-2861-2979
authorships[3].author.display_name	Bo Wu
authorships[3].author_position	last
authorships[3].raw_author_name	Wu, Bo
authorships[3].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2404.01585
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	FLEXIS: FLEXible Frequent Subgraph Mining using Maximal Independent Sets
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10538
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9904999732971191
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1710
primary_topic.subfield.display_name	Information Systems
primary_topic.display_name	Data Mining Algorithms and Applications
related_works	https://openalex.org/W2748952813, https://openalex.org/W2390279801, https://openalex.org/W2358668433, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W2382290278, https://openalex.org/W2478288626, https://openalex.org/W4391913857, https://openalex.org/W2350741829, https://openalex.org/W2530322880
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2404.01585
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2404.01585
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2404.01585
primary_location.id	pmh:oai:arXiv.org:2404.01585
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2404.01585
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2404.01585
publication_date	2024-04-02
publication_year	2024
referenced_works_count	0
abstract_inverted_index.-	103
abstract_inverted_index.a	14, 89, 137
abstract_inverted_index.(k	102
abstract_inverted_index.3x	216
abstract_inverted_index.To	82
abstract_inverted_index.an	183, 204, 214
abstract_inverted_index.as	143
abstract_inverted_index.by	97
abstract_inverted_index.if	52
abstract_inverted_index.in	23, 127
abstract_inverted_index.is	4, 20, 129
abstract_inverted_index.of	7, 132, 206
abstract_inverted_index.on	66, 119
abstract_inverted_index.or	68, 158
abstract_inverted_index.to	46, 60, 211, 220
abstract_inverted_index.FSM	19, 128
abstract_inverted_index.MIS	169
abstract_inverted_index.Our	163
abstract_inverted_index.Set	146
abstract_inverted_index.and	29, 38, 50, 78, 122, 148, 170, 189, 213
abstract_inverted_index.can	75
abstract_inverted_index.for	92, 114
abstract_inverted_index.its	34
abstract_inverted_index.our	200
abstract_inverted_index.set	56
abstract_inverted_index.the	5, 44, 55, 109, 130, 133, 168, 175
abstract_inverted_index.two	99
abstract_inverted_index.Node	150
abstract_inverted_index.Set"	178
abstract_inverted_index.This	40, 106
abstract_inverted_index.edge	67
abstract_inverted_index.from	43
abstract_inverted_index.like	25
abstract_inverted_index.need	45
abstract_inverted_index.over	194
abstract_inverted_index.rely	65
abstract_inverted_index.risk	159
abstract_inverted_index.such	142
abstract_inverted_index.that	12, 186
abstract_inverted_index.they	53
abstract_inverted_index.this	86, 180
abstract_inverted_index.time	157
abstract_inverted_index.when	209, 218
abstract_inverted_index.with	167, 192
abstract_inverted_index.(FSM)	3
abstract_inverted_index.(MIS)	147
abstract_inverted_index.GraMi	212
abstract_inverted_index.Image	151
abstract_inverted_index.T-FSM	221
abstract_inverted_index.While	18
abstract_inverted_index.based	118
abstract_inverted_index.cause	79
abstract_inverted_index.count	121
abstract_inverted_index.novel	90
abstract_inverted_index.often	64
abstract_inverted_index.paper	87, 181
abstract_inverted_index.stems	42
abstract_inverted_index.these	62, 73, 84
abstract_inverted_index.users	191
abstract_inverted_index.which	112
abstract_inverted_index.(MNI),	152
abstract_inverted_index.10.58x	207
abstract_inverted_index.Mining	2
abstract_inverted_index.aligns	166
abstract_inverted_index.allows	113
abstract_inverted_index.common	9
abstract_inverted_index.demand	154
abstract_inverted_index.either	153
abstract_inverted_index.exceed	54
abstract_inverted_index.fields	24
abstract_inverted_index.method	107, 202
abstract_inverted_index.offers	182
abstract_inverted_index.search	116
abstract_inverted_index.social	30
abstract_inverted_index.value.	124
abstract_inverted_index.vertex	69
abstract_inverted_index.widely	21
abstract_inverted_index.Another	125
abstract_inverted_index.Current	58
abstract_inverted_index.Maximum	144
abstract_inverted_index.Minimum	149
abstract_inverted_index.Through	174, 197
abstract_inverted_index.address	83
abstract_inverted_index.against	136
abstract_inverted_index.anomaly	32
abstract_inverted_index.average	205, 215
abstract_inverted_index.control	193
abstract_inverted_index.counts.	162
abstract_inverted_index.latency	188
abstract_inverted_index.metric,	179
abstract_inverted_index.network	31
abstract_inverted_index.pattern	135, 161, 195
abstract_inverted_index.process	6
abstract_inverted_index.quicker	115
abstract_inverted_index.remains	36
abstract_inverted_index.search,	111
abstract_inverted_index.speedup	208, 217
abstract_inverted_index.support	123
abstract_inverted_index.surpass	13
abstract_inverted_index."Maximal	176
abstract_inverted_index.Existing	140
abstract_inverted_index.Frequent	0
abstract_inverted_index.However,	72
abstract_inverted_index.Subgraph	1
abstract_inverted_index.achieves	203
abstract_inverted_index.approach	91, 165
abstract_inverted_index.chemical	27
abstract_inverted_index.compared	210, 219
abstract_inverted_index.complex.	39
abstract_inverted_index.k-vertex	95
abstract_inverted_index.latency.	81
abstract_inverted_index.methods.	71
abstract_inverted_index.metrics,	141
abstract_inverted_index.observed	101
abstract_inverted_index.overlap.	196
abstract_inverted_index.patterns	11, 63, 96
abstract_inverted_index.presumed	134
abstract_inverted_index.proposed	201
abstract_inverted_index.provides	190
abstract_inverted_index.solution	185
abstract_inverted_index.specific	138
abstract_inverted_index.subgraph	10
abstract_inverted_index.vertices	120
abstract_inverted_index.1)-vertex	104
abstract_inverted_index.analysis,	28
abstract_inverted_index.ascertain	51
abstract_inverted_index.challenge	126
abstract_inverted_index.combining	98
abstract_inverted_index.efficient	184
abstract_inverted_index.execution	35
abstract_inverted_index.extension	70
abstract_inverted_index.extensive	198
abstract_inverted_index.frequency	16
abstract_inverted_index.increased	80
abstract_inverted_index.introduce	76
abstract_inverted_index.minimizes	187
abstract_inverted_index.optimizes	108
abstract_inverted_index.patterns.	105
abstract_inverted_index.potential	94
abstract_inverted_index.recognize	47
abstract_inverted_index.subgraphs	49
abstract_inverted_index.applicable	22
abstract_inverted_index.approaches	59
abstract_inverted_index.complexity	41
abstract_inverted_index.detection,	33
abstract_inverted_index.frequently	100
abstract_inverted_index.identifies	171
abstract_inverted_index.innovative	164
abstract_inverted_index.introduces	88
abstract_inverted_index.predefined	15
abstract_inverted_index.strategies	74
abstract_inverted_index.subgraphs.	173
abstract_inverted_index.threshold.	17, 57, 139
abstract_inverted_index.validation	131
abstract_inverted_index.Independent	145, 177
abstract_inverted_index.challenges,	85
abstract_inverted_index.identifying	8, 61, 93
abstract_inverted_index.independent	172
abstract_inverted_index.significant	155
abstract_inverted_index.termination	117
abstract_inverted_index.redundancies	77
abstract_inverted_index.computational	156
abstract_inverted_index.breadth-]first	110
abstract_inverted_index.high-frequency	48
abstract_inverted_index.overestimating	160
abstract_inverted_index.time-consuming	37
abstract_inverted_index.bioinformatics,	26
abstract_inverted_index.experimentation,	199
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	4
citation_normalized_percentile