Advanced search
1 file | 1.28 MB Add to list

Subjectively interesting connecting trees and forests

Florian Adriaens (UGent) , Jefrey Lijffijt (UGent) and Tijl De Bie (UGent)
Author
Organization
Abstract
Consider a large graph or network, and a user-provided set of query vertices between which the user wishes to explore relations. For example, a researcher may want to connect research papers in a citation network, an analyst may wish to connect organized crime suspects in a communication network, or an internet user may want to organize their bookmarks given their location in the world wide web. A natural way to do this is to connect the vertices in the form of a tree structure that is present in the graph. However, in sufficiently dense graphs, most such trees will be large or somehow trivial (e.g. involving high degree vertices) and thus not insightful. Extending previous research, we define and investigate the new problem of mining subjectively interesting trees connecting a set of query vertices in a graph, i.e., trees that are highly surprising to the specific user at hand. Using information theoretic principles, we formalize the notion of interestingness of such trees mathematically, taking in account certain prior beliefs the user has specified about the graph. A remaining problem is efficiently fitting a prior belief model. We show how this can be done for a large class of prior beliefs. Given a specified prior belief model, we then propose heuristic algorithms to find the best trees efficiently. An empirical validation of our methods on a large real graphs evaluates the different heuristics and validates the interestingness of the given trees.
Keywords
Data Science, Pattern Mining, Subjective Interestingness, Computer Science Applications, Subjective interestingness measures, Prior information, Pattern mining, Graphs, Networks

Downloads

  • Adriaens2019 Article SubjectivelyInterestingConnect.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 1.28 MB

Citation

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

MLA
Adriaens, Florian, Jefrey Lijffijt, and Tijl De Bie. “Subjectively Interesting Connecting Trees and Forests.” DATA MINING AND KNOWLEDGE DISCOVERY 33.4 (2019): 1088–1124. Print.
APA
Adriaens, Florian, Lijffijt, J., & De Bie, T. (2019). Subjectively interesting connecting trees and forests. DATA MINING AND KNOWLEDGE DISCOVERY, 33(4), 1088–1124.
Chicago author-date
Adriaens, Florian, Jefrey Lijffijt, and Tijl De Bie. 2019. “Subjectively Interesting Connecting Trees and Forests.” Data Mining and Knowledge Discovery 33 (4): 1088–1124.
Chicago author-date (all authors)
Adriaens, Florian, Jefrey Lijffijt, and Tijl De Bie. 2019. “Subjectively Interesting Connecting Trees and Forests.” Data Mining and Knowledge Discovery 33 (4): 1088–1124.
Vancouver
1.
Adriaens F, Lijffijt J, De Bie T. Subjectively interesting connecting trees and forests. DATA MINING AND KNOWLEDGE DISCOVERY. 2019;33(4):1088–124.
IEEE
[1]
F. Adriaens, J. Lijffijt, and T. De Bie, “Subjectively interesting connecting trees and forests,” DATA MINING AND KNOWLEDGE DISCOVERY, vol. 33, no. 4, pp. 1088–1124, 2019.
@article{8613039,
  abstract     = {Consider a large graph or network, and a user-provided set of query vertices between which the user wishes to explore relations. For example, a researcher may want to connect research papers in a citation network, an analyst may wish to connect organized crime suspects in a communication network, or an internet user may want to organize their bookmarks given their location in the world wide web. A natural way to do this is to connect the vertices in the form of a tree structure that is present in the graph. However, in sufficiently dense graphs, most such trees will be large or somehow trivial (e.g. involving high degree vertices) and thus not insightful. Extending previous research, we define and investigate the new problem of mining subjectively interesting trees connecting a set of query vertices in a graph, i.e., trees that are highly surprising to the specific user at hand. Using information theoretic principles, we formalize the notion of interestingness of such trees mathematically, taking in account certain prior beliefs the user has specified about the graph. A remaining problem is efficiently fitting a prior belief model. We show how this can be done for a large class of prior beliefs. Given a specified prior belief model, we then propose heuristic algorithms to find the best trees efficiently. An empirical validation of our methods on a large real graphs evaluates the different heuristics and validates the interestingness of the given trees.},
  author       = {Adriaens, Florian and Lijffijt, Jefrey and De Bie, Tijl},
  issn         = {1384-5810},
  journal      = {DATA MINING AND KNOWLEDGE DISCOVERY},
  keywords     = {Data Science,Pattern Mining,Subjective Interestingness,Computer Science Applications,Subjective interestingness measures,Prior information,Pattern mining,Graphs,Networks},
  language     = {eng},
  number       = {4},
  pages        = {1088--1124},
  title        = {Subjectively interesting connecting trees and forests},
  url          = {http://dx.doi.org/10.1007/s10618-019-00627-1},
  volume       = {33},
  year         = {2019},
}

Altmetric
View in Altmetric
Web of Science
Times cited: