2023 [ nach oben ]

Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Gawendowicz, Hans; Klodt, Nicolas; Lenzner, Pascal; Skretas, George Temporal Network Creation GamesInternational Joint Conference on Artificial Intelligence (IJCAI) 2023: 2511–2519
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.
@inproceedings{bilo2023temporal, abstract = {Most networks are not static objects, but instead they change over time. This observation has sparked rigorous research on temporal graphs within the last years. In temporal graphs, we have a fixed set of nodes and the connections between them are only available at certain time steps. This gives rise to a plethora of algorithmic problems on such graphs, most prominently the problem of finding temporal spanners, i.e., the computation of subgraphs that guarantee all pairs reachability via temporal paths. To the best of our knowledge, only centralized approaches for the solution of this problem are known. However, many real-world networks are not shaped by a central designer but instead they emerge and evolve by the interaction of many strategic agents. This observation is the driving force of the recent intensive research on game-theoretic network formation models. In this work we bring together these two recent research directions: temporal graphs and game-theoretic network formation. As a first step into this new realm, we focus on a simplified setting where a complete temporal host graph is given and the agents, corresponding to its nodes, selfishly create incident edges to ensure that they can reach all other nodes via temporal paths in the created network. This yields temporal spanners as equilibria of our game. We prove results on the convergence to and the existence of equilibrium networks, on the complexity of finding best agent strategies, and on the quality of the equilibria. By taking these first important steps, we uncover challenging open problems that call for an in-depth exploration of the creation of temporal graphs by strategic agents.}, author = {Bilò, Davide and Cohen, Sarel and Friedrich, Tobias and Gawendowicz, Hans and Klodt, Nicolas and Lenzner, Pascal and Skretas, George}, booktitle = {International Joint Conference on Artificial Intelligence (IJCAI)}, keywords = {georgeskretas hansgawendowicz ijcai nicolasklodt pascallenzner sarelcohen tobiasfriedrich year2023}, pages = {2511–2519}, title = {Temporal Network Creation Games}, year = 2023 }

2021 [ nach oben ]

Berger, Julian; Böther, Maximilian; Doskoč, Vanja; Gadea Harder, Jonathan; Klodt, Nicolas; Kötzing, Timo; Lötzsch, Winfried; Peters, Jannik; Schiller, Leon; Seifert, Lars; Wells, Armin; Wietheger, Simon Learning Languages with Decidable HypothesesComputability in Europe (CiE) 2021: 25–37
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In \emph{language learning in the limit}, the most common type of hypothesis is to give an enumerator for a language, a \(W\)-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely \emph{programs for characteristic functions} (called \(C\)-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal \(C\)-index. In this first analysis of learning with \(C\)-indices, we give a structured account of the learning power of various restrictions employing \(C\)-indices, also when compared with \(W\)-indices. We establish a hierarchy of learning power depending on whether \(C\)-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation. Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.
@inproceedings{berger2021learning, abstract = {In \emph{language learning in the limit}, the most common type of hypothesis is to give an enumerator for a language, a \(W\)-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely \emph{programs for characteristic functions} (called \(C\)-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal \(C\)-index. In this first analysis of learning with \(C\)-indices, we give a structured account of the learning power of various restrictions employing \(C\)-indices, also when compared with \(W\)-indices. We establish a hierarchy of learning power depending on whether \(C\)-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation. Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.}, author = {Berger, Julian and Böther, Maximilian and Doskoč, Vanja and Gadea Harder, Jonathan and Klodt, Nicolas and Kötzing, Timo and Lötzsch, Winfried and Peters, Jannik and Schiller, Leon and Seifert, Lars and Wells, Armin and Wietheger, Simon}, booktitle = {Computability in Europe (CiE)}, keywords = {arminwells cie jannikpeters jonathangadeaharder julianberger larsseifert leonschiller maximilianboether nicolasklodt simonwietheger timokoetzing vanjadoskoc winfriedloetzsch year2021}, pages = {25-37}, title = {Learning Languages with Decidable Hypotheses}, year = 2021 }

Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, Arthur A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved HeuristicsKnowledge Discovery and Data Mining (KDD) 2021: 882–891
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), motivated by real-world applications from data-mining, social networks and bioinformatics. We give theoretical as well as practical contributions to the study of CCC. Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015]. While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances. Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and extend our results to this model.
@inproceedings{casel2021colorblind, abstract = {Chromatic Correlation Clustering (CCC) models clustering of objects with categorical pairwise relationships. The model can be viewed as clustering the vertices of a graph with edge-labels (colors). Bonchi et al. [KDD 2012] introduced it as a natural generalization of the well studied problem Correlation Clustering (CC), motivated by real-world applications from data-mining, social networks and bioinformatics. We give theoretical as well as practical contributions to the study of CCC. Our main theoretical contribution is an alternative analysis of the famous Pivot algorithm for CC. We show that, when simply run color-blind, Pivot is also a linear time 3-approximation for CCC. The previous best theoretical results for CCC were a 4-approximation with a high-degree polynomial runtime and a linear time 11-approximation, both by Anava et al. [WWW 2015]. While this theoretical result justifies Pivot as a baseline comparison for other heuristics, its blunt color-blindness performs poorly in practice. We develop a color-sensitive, practical heuristic we call Greedy Expansion that empirically outperforms all heuristics proposed for CCC so far, both on real-world and synthetic instances. Further, we propose a novel generalization of CCC allowing for multi-labelled edges. We argue that it is more suitable for many of the real-world applications and extend our results to this model.}, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Klodt, Nicolas and Seifert, Lars and Zahn, Arthur}, booktitle = {Knowledge Discovery and Data Mining (KDD)}, keywords = {sys:relevantfor:ae arthurzahn davisissac katrincasel kdd larsseifert nicolasklodt tobiasfriedrich year2021}, pages = {882–891}, publisher = {ACM}, title = {A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved Heuristics}, year = 2021 }