Graphs and Uncertainty

Graphes et incertitude

Silviu Maniu (1)

1 LaHDAK - Données et Connaissances Massives et Hétérogènes - LISN

In many domains, graphs are one of the most intuitive ways of representing data, and many im- portant tasks can be translated into graph queries and combinatorial problems on graphs. In most real-world scenarios, graph data or models have some uncertainty attached. In this manuscript, we discuss two aspects of challenges that occur when graph data or models are uncertain. First, we discuss how querying the graph changes when edges become uncertain; for this, we introduce the concept of tree decompositions for query processing on uncertain graphs. Moreover, we make the link between query efficiency and the concept of treewidth. In the second part of the manuscript, we discuss how to solve a well-known graph problem – social influence maximization – in the case where little is known about the underlying graph over which influence is performed. We discuss how approaches such as multi- armed-bandits can be applied.

Dans de nombreux domaines, les graphes sont l’un des moyens les plus intuitifs de représenter les données, et de nombreuses tâches importantes peuvent être traduites en requêtes de graphes et en problèmes combinatoires sur les graphes. Dans la plupart des scénarios du monde réel, les données ou les modèles de graphes comportent une certaine incertitude. Dans ce manuscrit, nous abordons deux aspects des défis qui se présentent lorsque les données ou les modèles de graphes sont incertains. Tout d’abord, nous discutons de la façon dont les requêtes sur le graphe changent lorsque les bords deviennent incertains ; pour cela, nous introduisons le concept de décompositions d’arbres pour le traitement des ces requêtes. De plus, nous faisons le lien entre l’efficacité des requêtes et le concept de largeur d’arbre. Dans la deuxième partie du manuscrit, nous discutons de la manière de résoudre un problème de graphe bien connu - la maximisation de l’influence sociale - dans le cas où l’on sait peu de choses sur le graphe sous-jacent sur lequel l’influence est exercée. Nous discutons de la manière dont des approches telles que les bandits manchots peuvent être appliquées.

Mots clés: graph data mining; probabilistic data; multi-armed bandits

Mots clés: fouille données graphe; données incertaines; bandit manchots

Domaines: Recherche d'information [cs.IR]

Silviu Maniu. Graphs and Uncertainty. Information Retrieval [cs.IR]. Université Paris Saclay, 2022. ⟨tel-04443792⟩