Advanced search
1 file | 4.77 MB Add to list

SIAS-miner : mining subjectively interesting attributed subgraphs

Author
Organization
Abstract
Data clustering, local pattern mining, and community detection in graphs are three mature areas of data mining and machine learning. In recent years, attributed subgraph mining has emerged as a new powerful data mining task in the intersection of these areas. Given a graph and a set of attributes for each vertex, attributed subgraph mining aims to find cohesive subgraphs for which (some of) the attribute values have exceptional values. The principled integration of graph and attribute data poses two challenges: (1) the definition of a pattern syntax (the abstract form of patterns) that is intuitive and lends itself to efficient search, and (2) the formalization of the interestingness of such patterns. We propose an integrated solution to both of these challenges. The proposed pattern syntax improves upon prior work in being both highly flexible and intuitive. Plus, we define an effective and principled algorithm to enumerate patterns of this syntax. The proposed approach for quantifying interestingness of these patterns is rooted in information theory, and is able to account for background knowledge on the data. While prior work quantified the interestingness for the cohesion of the subgraph and for the exceptionality of its attributes separately, then combining these in a parameterized trade-off, we instead handle this trade-off implicitly in a principled, parameter-free manner. Empirical results confirm we can efficiently find highly interesting subgraphs.
Keywords
EFFECTIVE COMMUNITY SEARCH, DISCOVERY, PATTERN, SET, Graphs, Attributed graphs, Subjective interestingness, Subgraph mining

Downloads

  • DS284.pdf
    • full text (Published version)
    • |
    • open access
    • |
    • PDF
    • |
    • 4.77 MB

Citation

Please use this url to cite or link to this publication:

MLA
Bendimerad, Anes, et al. “SIAS-Miner : Mining Subjectively Interesting Attributed Subgraphs.” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 34, 2020, pp. 355–93.
APA
Bendimerad, A., Mel, A., Lijffijt, J., Plantevit, M., Robardet, C., & De Bie, T. (2020). SIAS-miner : mining subjectively interesting attributed subgraphs. DATA MINING AND KNOWLEDGE DISCOVERY, 34, 355–393.
Chicago author-date
Bendimerad, Anes, Ahmad Mel, Jefrey Lijffijt, Marc Plantevit, Celine Robardet, and Tijl De Bie. 2020. “SIAS-Miner : Mining Subjectively Interesting Attributed Subgraphs.” DATA MINING AND KNOWLEDGE DISCOVERY 34: 355–93.
Chicago author-date (all authors)
Bendimerad, Anes, Ahmad Mel, Jefrey Lijffijt, Marc Plantevit, Celine Robardet, and Tijl De Bie. 2020. “SIAS-Miner : Mining Subjectively Interesting Attributed Subgraphs.” DATA MINING AND KNOWLEDGE DISCOVERY 34: 355–393.
Vancouver
1.
Bendimerad A, Mel A, Lijffijt J, Plantevit M, Robardet C, De Bie T. SIAS-miner : mining subjectively interesting attributed subgraphs. DATA MINING AND KNOWLEDGE DISCOVERY. 2020;34:355–93.
IEEE
[1]
A. Bendimerad, A. Mel, J. Lijffijt, M. Plantevit, C. Robardet, and T. De Bie, “SIAS-miner : mining subjectively interesting attributed subgraphs,” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 34, pp. 355–393, 2020.
@article{8637777,
  abstract     = {Data clustering, local pattern mining, and community detection in graphs are three mature areas of data mining and machine learning. In recent years, attributed subgraph mining has emerged as a new powerful data mining task in the intersection of these areas. Given a graph and a set of attributes for each vertex, attributed subgraph mining aims to find cohesive subgraphs for which (some of) the attribute values have exceptional values. The principled integration of graph and attribute data poses two challenges: (1) the definition of a pattern syntax (the abstract form of patterns) that is intuitive and lends itself to efficient search, and (2) the formalization of the interestingness of such patterns. We propose an integrated solution to both of these challenges. The proposed pattern syntax improves upon prior work in being both highly flexible and intuitive. Plus, we define an effective and principled algorithm to enumerate patterns of this syntax. The proposed approach for quantifying interestingness of these patterns is rooted in information theory, and is able to account for background knowledge on the data. While prior work quantified the interestingness for the cohesion of the subgraph and for the exceptionality of its attributes separately, then combining these in a parameterized trade-off, we instead handle this trade-off implicitly in a principled, parameter-free manner. Empirical results confirm we can efficiently find highly interesting subgraphs.},
  author       = {Bendimerad, Anes and Mel, Ahmad and Lijffijt, Jefrey and Plantevit, Marc and Robardet, Celine and De Bie, Tijl},
  issn         = {1384-5810},
  journal      = {DATA MINING AND KNOWLEDGE DISCOVERY},
  keywords     = {EFFECTIVE COMMUNITY SEARCH,DISCOVERY,PATTERN,SET,Graphs,Attributed graphs,Subjective interestingness,Subgraph mining},
  language     = {eng},
  pages        = {355--393},
  title        = {SIAS-miner : mining subjectively interesting attributed subgraphs},
  url          = {http://dx.doi.org/10.1007/s10618-019-00664-w},
  volume       = {34},
  year         = {2020},
}

Altmetric
View in Altmetric
Web of Science
Times cited: