Complete Mining of Frequent Patterns from Graphs: Mining Graph Data View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2003-03

AUTHORS

Akihiro Inokuchi, Takashi Washio, Hiroshi Motoda

ABSTRACT

Basket Analysis, which is a standard method for data mining, derives frequent itemsets from database. However, its mining ability is limited to transaction data consisting of items. In reality, there are many applications where data are described in a more structural way, e.g. chemical compounds and Web browsing history. There are a few approaches that can discover characteristic patterns from graph-structured data in the field of machine learning. However, almost all of them are not suitable for such applications that require a complete search for all frequent subgraph patterns in the data. In this paper, we propose a novel principle and its algorithm that derive the characteristic patterns which frequently appear in graph-structured data. Our algorithm can derive all frequent induced subgraphs from both directed and undirected graph structured data having loops (including self-loops) with labeled or unlabeled nodes and links. Its performance is evaluated through the applications to Web browsing pattern analysis and chemical carcinogenesis analysis. More... »

PAGES

321-354

References to SciGraph publications

  • 1998-06. Collective dynamics of ‘small-world’ networks in NATURE
  • 1999. Basket Analysis for Graph Structured Data in METHODOLOGIES FOR KNOWLEDGE DISCOVERY AND DATA MINING
  • 1997-09. Discovery of Frequent Episodes in Event Sequences in DATA MINING AND KNOWLEDGE DISCOVERY
  • 1995. Strong lower bounds on the approximability of some NPO PB-complete maximization problems in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 1995
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1021726221443

    DOI

    http://dx.doi.org/10.1023/a:1021726221443

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1016532456


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Osaka University", 
              "id": "https://www.grid.ac/institutes/grid.136593.b", 
              "name": [
                "Institute for Scientific and Industrial Research, Osaka University, 567-0047, Osaka, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Inokuchi", 
            "givenName": "Akihiro", 
            "id": "sg:person.011426107721.30", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011426107721.30"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Osaka University", 
              "id": "https://www.grid.ac/institutes/grid.136593.b", 
              "name": [
                "Institute for Scientific and Industrial Research, Osaka University, 567-0047, Osaka, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Washio", 
            "givenName": "Takashi", 
            "id": "sg:person.013400233105.62", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013400233105.62"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Osaka University", 
              "id": "https://www.grid.ac/institutes/grid.136593.b", 
              "name": [
                "Institute for Scientific and Industrial Research, Osaka University, 567-0047, Osaka, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Motoda", 
            "givenName": "Hiroshi", 
            "id": "sg:person.016251026775.26", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016251026775.26"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/a:1009748302351", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005237640", 
              "https://doi.org/10.1023/a:1009748302351"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60246-1_129", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007344334", 
              "https://doi.org/10.1007/3-540-60246-1_129"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/321921.321925", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008268655"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48912-6_56", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008497289", 
              "https://doi.org/10.1007/3-540-48912-6_56"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.286.5439.509", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010080128"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/jgt.3190010410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036378895"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(94)00066-a", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040019795"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/30918", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041985305", 
              "https://doi.org/10.1038/30918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1038/30918", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041985305", 
              "https://doi.org/10.1038/30918"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(95)00050-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049718767"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1021/jm00106a046", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1055935291"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/69.683753", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061213668"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/icde.1995.380415", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094007712"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1613/jair.43", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1105538456"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2003-03", 
        "datePublishedReg": "2003-03-01", 
        "description": "Basket Analysis, which is a standard method for data mining, derives frequent itemsets from database. However, its mining ability is limited to transaction data consisting of items. In reality, there are many applications where data are described in a more structural way, e.g. chemical compounds and Web browsing history. There are a few approaches that can discover characteristic patterns from graph-structured data in the field of machine learning. However, almost all of them are not suitable for such applications that require a complete search for all frequent subgraph patterns in the data. In this paper, we propose a novel principle and its algorithm that derive the characteristic patterns which frequently appear in graph-structured data. Our algorithm can derive all frequent induced subgraphs from both directed and undirected graph structured data having loops (including self-loops) with labeled or unlabeled nodes and links. Its performance is evaluated through the applications to Web browsing pattern analysis and chemical carcinogenesis analysis.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1021726221443", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1125588", 
            "issn": [
              "0885-6125", 
              "1573-0565"
            ], 
            "name": "Machine Learning", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "50"
          }
        ], 
        "name": "Complete Mining of Frequent Patterns from Graphs: Mining Graph Data", 
        "pagination": "321-354", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4ec5ac08a0a7a4a70d53531f4d543d703093aa129c71dc4e6a9d8f280eb6d36a"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1021726221443"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1016532456"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1021726221443", 
          "https://app.dimensions.ai/details/publication/pub.1016532456"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19:07", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8678_00000504.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023%2FA%3A1021726221443"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1023/a:1021726221443'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1023/a:1021726221443'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1021726221443'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1021726221443'


     

    This table displays all metadata directly associated to this object as RDF triples.

    118 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1021726221443 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N67060baa00a54cfa98f13ab2f24809bd
    4 schema:citation sg:pub.10.1007/3-540-48912-6_56
    5 sg:pub.10.1007/3-540-60246-1_129
    6 sg:pub.10.1023/a:1009748302351
    7 sg:pub.10.1038/30918
    8 https://doi.org/10.1002/jgt.3190010410
    9 https://doi.org/10.1016/0004-3702(94)00066-a
    10 https://doi.org/10.1016/0004-3702(95)00050-x
    11 https://doi.org/10.1021/jm00106a046
    12 https://doi.org/10.1109/69.683753
    13 https://doi.org/10.1109/icde.1995.380415
    14 https://doi.org/10.1126/science.286.5439.509
    15 https://doi.org/10.1145/321921.321925
    16 https://doi.org/10.1613/jair.43
    17 schema:datePublished 2003-03
    18 schema:datePublishedReg 2003-03-01
    19 schema:description Basket Analysis, which is a standard method for data mining, derives frequent itemsets from database. However, its mining ability is limited to transaction data consisting of items. In reality, there are many applications where data are described in a more structural way, e.g. chemical compounds and Web browsing history. There are a few approaches that can discover characteristic patterns from graph-structured data in the field of machine learning. However, almost all of them are not suitable for such applications that require a complete search for all frequent subgraph patterns in the data. In this paper, we propose a novel principle and its algorithm that derive the characteristic patterns which frequently appear in graph-structured data. Our algorithm can derive all frequent induced subgraphs from both directed and undirected graph structured data having loops (including self-loops) with labeled or unlabeled nodes and links. Its performance is evaluated through the applications to Web browsing pattern analysis and chemical carcinogenesis analysis.
    20 schema:genre research_article
    21 schema:inLanguage en
    22 schema:isAccessibleForFree true
    23 schema:isPartOf N6411b688ea9d488f8093ddc8ea8d9c2f
    24 N9d8cc23ed3eb4aff8793f423042d576c
    25 sg:journal.1125588
    26 schema:name Complete Mining of Frequent Patterns from Graphs: Mining Graph Data
    27 schema:pagination 321-354
    28 schema:productId N059f592f5d4c4ea384546112c6abedcd
    29 N91c18dac11a14398a99441a3209e569c
    30 Ne94a115cef344d15af1374bdcc6dae6c
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016532456
    32 https://doi.org/10.1023/a:1021726221443
    33 schema:sdDatePublished 2019-04-10T19:07
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Nd4ca54202e76424aba145711b5bcc60a
    36 schema:url http://link.springer.com/10.1023%2FA%3A1021726221443
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset articles
    39 rdf:type schema:ScholarlyArticle
    40 N059f592f5d4c4ea384546112c6abedcd schema:name readcube_id
    41 schema:value 4ec5ac08a0a7a4a70d53531f4d543d703093aa129c71dc4e6a9d8f280eb6d36a
    42 rdf:type schema:PropertyValue
    43 N3874ab7aff3e48d98b89f4f97da3583e rdf:first sg:person.013400233105.62
    44 rdf:rest N86cbde7f3fef4f8a8c185f8d67c714b5
    45 N6411b688ea9d488f8093ddc8ea8d9c2f schema:issueNumber 3
    46 rdf:type schema:PublicationIssue
    47 N67060baa00a54cfa98f13ab2f24809bd rdf:first sg:person.011426107721.30
    48 rdf:rest N3874ab7aff3e48d98b89f4f97da3583e
    49 N86cbde7f3fef4f8a8c185f8d67c714b5 rdf:first sg:person.016251026775.26
    50 rdf:rest rdf:nil
    51 N91c18dac11a14398a99441a3209e569c schema:name doi
    52 schema:value 10.1023/a:1021726221443
    53 rdf:type schema:PropertyValue
    54 N9d8cc23ed3eb4aff8793f423042d576c schema:volumeNumber 50
    55 rdf:type schema:PublicationVolume
    56 Nd4ca54202e76424aba145711b5bcc60a schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 Ne94a115cef344d15af1374bdcc6dae6c schema:name dimensions_id
    59 schema:value pub.1016532456
    60 rdf:type schema:PropertyValue
    61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    62 schema:name Information and Computing Sciences
    63 rdf:type schema:DefinedTerm
    64 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    65 schema:name Artificial Intelligence and Image Processing
    66 rdf:type schema:DefinedTerm
    67 sg:journal.1125588 schema:issn 0885-6125
    68 1573-0565
    69 schema:name Machine Learning
    70 rdf:type schema:Periodical
    71 sg:person.011426107721.30 schema:affiliation https://www.grid.ac/institutes/grid.136593.b
    72 schema:familyName Inokuchi
    73 schema:givenName Akihiro
    74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011426107721.30
    75 rdf:type schema:Person
    76 sg:person.013400233105.62 schema:affiliation https://www.grid.ac/institutes/grid.136593.b
    77 schema:familyName Washio
    78 schema:givenName Takashi
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013400233105.62
    80 rdf:type schema:Person
    81 sg:person.016251026775.26 schema:affiliation https://www.grid.ac/institutes/grid.136593.b
    82 schema:familyName Motoda
    83 schema:givenName Hiroshi
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016251026775.26
    85 rdf:type schema:Person
    86 sg:pub.10.1007/3-540-48912-6_56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008497289
    87 https://doi.org/10.1007/3-540-48912-6_56
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/3-540-60246-1_129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007344334
    90 https://doi.org/10.1007/3-540-60246-1_129
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1023/a:1009748302351 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005237640
    93 https://doi.org/10.1023/a:1009748302351
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1038/30918 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041985305
    96 https://doi.org/10.1038/30918
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1002/jgt.3190010410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036378895
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0004-3702(94)00066-a schema:sameAs https://app.dimensions.ai/details/publication/pub.1040019795
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/0004-3702(95)00050-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1049718767
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1021/jm00106a046 schema:sameAs https://app.dimensions.ai/details/publication/pub.1055935291
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1109/69.683753 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213668
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1109/icde.1995.380415 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094007712
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1126/science.286.5439.509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010080128
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/321921.321925 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008268655
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1613/jair.43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105538456
    115 rdf:type schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.136593.b schema:alternateName Osaka University
    117 schema:name Institute for Scientific and Industrial Research, Osaka University, 567-0047, Osaka, Japan
    118 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...