Advanced search
1 file | 11.04 MB Add to list

Subjective interestingness of subgraph patterns

(2016) MACHINE LEARNING. 105(1). p.41-75
Author
Organization
Abstract
The utility of a dense subgraph in gaining a better understanding of a graph has been formalised in numerous ways, each striking a different balance between approximating actual interestingness and computational efficiency. A difficulty in making this trade-off is that, while computational cost of an algorithm is relatively well-defined, a pattern's interestingness is fundamentally subjective. This means that this latter aspect is often treated only informally or neglected, and instead some form of density is used as a proxy. We resolve this difficulty by formalising what makes a dense subgraph pattern interesting to a given user. Unsurprisingly, the resulting measure is dependent on the prior beliefs of the user about the graph. For concreteness, in this paper we consider two cases: one case where the user only has a belief about the overall density of the graph, and another case where the user has prior beliefs about the degrees of the vertices. Furthermore, we illustrate how the resulting interestingness measure is different from previous proposals. We also propose effective exact and approximate algorithms for mining the most interesting dense subgraph according to the proposed measure. Usefully, the proposed interestingness measure and approach lend themselves well to iterative dense subgraph discovery. Contrary to most existing approaches, our method naturally allows subsequently found patterns to be overlapping. The empirical evaluation highlights the properties of the new interestingness measure given different prior belief sets, and our approach's ability to find interesting subgraphs that other methods are unable to find.
Keywords
Maximum entropy modelling, Alternative clustering, Dense subgraph patterns, Community detection, Subjective interestingness, Maximum entropy, KNOWLEDGE DISCOVERY

Downloads

  • subgraph patterns.pdf
    • full text (Published version)
    • |
    • open access
    • |
    • PDF
    • |
    • 11.04 MB

Citation

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

MLA
van Leeuwen, Matthijs, et al. “Subjective Interestingness of Subgraph Patterns.” MACHINE LEARNING, vol. 105, no. 1, 2016, pp. 41–75, doi:10.1007/s10994-015-5539-3.
APA
van Leeuwen, M., De Bie, T., Spyropoulou, E., & Mesnage, C. (2016). Subjective interestingness of subgraph patterns. MACHINE LEARNING, 105(1), 41–75. https://doi.org/10.1007/s10994-015-5539-3
Chicago author-date
Leeuwen, Matthijs van, Tijl De Bie, Eirini Spyropoulou, and Cédric Mesnage. 2016. “Subjective Interestingness of Subgraph Patterns.” MACHINE LEARNING 105 (1): 41–75. https://doi.org/10.1007/s10994-015-5539-3.
Chicago author-date (all authors)
van Leeuwen, Matthijs, Tijl De Bie, Eirini Spyropoulou, and Cédric Mesnage. 2016. “Subjective Interestingness of Subgraph Patterns.” MACHINE LEARNING 105 (1): 41–75. doi:10.1007/s10994-015-5539-3.
Vancouver
1.
van Leeuwen M, De Bie T, Spyropoulou E, Mesnage C. Subjective interestingness of subgraph patterns. MACHINE LEARNING. 2016;105(1):41–75.
IEEE
[1]
M. van Leeuwen, T. De Bie, E. Spyropoulou, and C. Mesnage, “Subjective interestingness of subgraph patterns,” MACHINE LEARNING, vol. 105, no. 1, pp. 41–75, 2016.
@article{8087155,
  abstract     = {The utility of a dense subgraph in gaining a better understanding of a graph has been formalised in numerous ways, each striking a different balance between approximating actual interestingness and computational efficiency. A difficulty in making this trade-off is that, while computational cost of an algorithm is relatively well-defined, a pattern's interestingness is fundamentally subjective. This means that this latter aspect is often treated only informally or neglected, and instead some form of density is used as a proxy. We resolve this difficulty by formalising what makes a dense subgraph pattern interesting to a given user. Unsurprisingly, the resulting measure is dependent on the prior beliefs of the user about the graph. For concreteness, in this paper we consider two cases: one case where the user only has a belief about the overall density of the graph, and another case where the user has prior beliefs about the degrees of the vertices. Furthermore, we illustrate how the resulting interestingness measure is different from previous proposals. We also propose effective exact and approximate algorithms for mining the most interesting dense subgraph according to the proposed measure. Usefully, the proposed interestingness measure and approach lend themselves well to iterative dense subgraph discovery. Contrary to most existing approaches, our method naturally allows subsequently found patterns to be overlapping. The empirical evaluation highlights the properties of the new interestingness measure given different prior belief sets, and our approach's ability to find interesting subgraphs that other methods are unable to find.},
  author       = {van Leeuwen, Matthijs and De Bie, Tijl and Spyropoulou, Eirini and Mesnage, Cédric},
  issn         = {0885-6125},
  journal      = {MACHINE LEARNING},
  keywords     = {Maximum entropy modelling,Alternative clustering,Dense subgraph patterns,Community detection,Subjective interestingness,Maximum entropy,KNOWLEDGE DISCOVERY},
  language     = {eng},
  number       = {1},
  pages        = {41--75},
  title        = {Subjective interestingness of subgraph patterns},
  url          = {http://dx.doi.org/10.1007/s10994-015-5539-3},
  volume       = {105},
  year         = {2016},
}

Altmetric
View in Altmetric
Web of Science
Times cited: