4 Search Results for "Baden, Christian"

Document
DOI: 10.4230/LIPIcs.SEA.2022.5
Parallel Flow-Based Hypergraph Partitioning

Authors: Lars Gottesbüren, Tobias Heuer, and Peter Sanders

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

Abstract
We present a shared-memory parallelization of flow-based refinement, which is considered the most powerful iterative improvement technique for hypergraph partitioning at the moment. Flow-based refinement works on bipartitions, so current sequential partitioners schedule it on different block pairs to improve k-way partitions. We investigate two different sources of parallelism: a parallel scheduling scheme and a parallel maximum flow algorithm based on the well-known push-relabel algorithm. In addition to thoroughly engineered implementations, we propose several optimizations that substantially accelerate the algorithm in practice, enabling the use on extremely large hypergraphs (up to 1 billion pins). We integrate our approach in the state-of-the-art parallel multilevel framework Mt-KaHyPar and conduct extensive experiments on a benchmark set of more than 500 real-world hypergraphs, to show that the partition quality of our code is on par with the highest quality sequential code (KaHyPar), while being an order of magnitude faster with 10 threads.
Cite as

Lars Gottesbüren, Tobias Heuer, and Peter Sanders. Parallel Flow-Based Hypergraph Partitioning. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.SEA.2022.5,
  author =	{Gottesb\"{u}ren, Lars and Heuer, Tobias and Sanders, Peter},
  title =	{{Parallel Flow-Based Hypergraph Partitioning}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.5},
  URN =		{urn:nbn:de:0030-drops-165393},
  doi =		{10.4230/LIPIcs.SEA.2022.5},
  annote =	{Keywords: multilevel hypergraph partitioning, shared-memory algorithms, maximum flow}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.48
Deep Multilevel Graph Partitioning

Authors: Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, and Daniel Seemaier

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
Partitioning a graph into blocks of "roughly equal" weight while cutting only few edges is a fundamental problem in computer science with a wide range of applications. In particular, the problem is a building block in applications that require parallel processing. While the amount of available cores in parallel architectures has significantly increased in recent years, state-of-the-art graph partitioning algorithms do not work well if the input needs to be partitioned into a large number of blocks. Often currently available algorithms compute highly imbalanced solutions, solutions of low quality, or have excessive running time for this case. This is due to the fact that most high-quality general-purpose graph partitioners are multilevel algorithms which perform graph coarsening to build a hierarchy of graphs, initial partitioning to compute an initial solution, and local improvement to improve the solution throughout the hierarchy. However, for large number of blocks, the smallest graph in the hierarchy that is used for initial partitioning still has to be large. In this work, we substantially mitigate these problems by introducing deep multilevel graph partitioning and a shared-memory implementation thereof. Our scheme continues the multilevel approach deep into initial partitioning - integrating it into a framework where recursive bipartitioning and direct k-way partitioning are combined such that they can operate with high performance and quality. Our integrated approach is stronger, more flexible, arguably more elegant, and reduces bottlenecks for parallelization compared to existing multilevel approaches. For example, for large number of blocks our algorithm is on average at least an order of magnitude faster than competing algorithms while computing partitions with comparable solution quality. At the same time, our algorithm consistently produces balanced solutions. Moreover, for small number of blocks, our algorithms are the fastest among competing systems with comparable quality.
Cite as

Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz, and Daniel Seemaier. Deep Multilevel Graph Partitioning. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gottesburen_et_al:LIPIcs.ESA.2021.48,
  author =	{Gottesb\"{u}ren, Lars and Heuer, Tobias and Sanders, Peter and Schulz, Christian and Seemaier, Daniel},
  title =	{{Deep Multilevel Graph Partitioning}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{48:1--48:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.48},
  URN =		{urn:nbn:de:0030-drops-146298},
  doi =		{10.4230/LIPIcs.ESA.2021.48},
  annote =	{Keywords: graph partitioning, graph algorithms, multilevel, shared-memory, parallel}
}
Document
DOI: 10.4230/DagMan.9.1.43
Diversity in News Recommendation (Dagstuhl Perspectives Workshop 19482)

Authors: Abraham Bernstein, Claes de Vreese, Natali Helberger, Wolfgang Schulz, Katharina Zweig, Christian Baden, Michael A. Beam, Marc P. Hauer, Lucien Heitz, Pascal Jürgens, Christian Katzenbach, Benjamin Kille, Beate Klimkiewicz, Wiebke Loosen, Judith Moeller, Goran Radanovic, Guy Shani, Nava Tintarev, Suzanne Tolmeijer, Wouter van Atteveldt, Sanne Vrijenhoek, and Theresa Zueger

Published in: Dagstuhl Manifestos, Volume 9, Issue 1 (2021)

Abstract
News diversity in the media has for a long time been a foundational and uncontested basis for ensuring that the communicative needs of individuals and society at large are met. Today, people increasingly rely on online content and recommender systems to consume information challenging the traditional concept of news diversity. In addition, the very concept of diversity, which differs between disciplines, will need to be re-evaluated requiring an interdisciplinary investigation, which requires a new level of mutual cooperation between computer scientists, social scientists, and legal scholars. Based on the outcome of a interdisciplinary workshop, we have the following recommendations, directed at researchers, funders, legislators, regulators, and the media industry: - Conduct interdisciplinary research on news recommenders and diversity. - Create a safe harbor for academic research with industry data. - Strengthen the role of public values in news recommenders. - Create a meaningful governance framework for news recommenders. - Fund a joint lab to spearhead the needed interdisciplinary research, boost practical innovation, develop reference solutions, and transfer insights into practice.
Cite as

Abraham Bernstein, Claes de Vreese, Natali Helberger, Wolfgang Schulz, Katharina Zweig, Christian Baden, Michael A. Beam, Marc P. Hauer, Lucien Heitz, Pascal Jürgens, Christian Katzenbach, Benjamin Kille, Beate Klimkiewicz, Wiebke Loosen, Judith Moeller, Goran Radanovic, Guy Shani, Nava Tintarev, Suzanne Tolmeijer, Wouter van Atteveldt, Sanne Vrijenhoek, and Theresa Zueger. Diversity in News Recommendation (Dagstuhl Perspectives Workshop 19482). In Dagstuhl Manifestos, Volume 9, Issue 1, pp. 43-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{bernstein_et_al:DagMan.9.1.43,
  author =	{Bernstein, Abraham and de Vreese, Claes and Helberger, Natali and Schulz, Wolfgang and Zweig, Katharina and Baden, Christian and Beam, Michael A. and Hauer, Marc P. and Heitz, Lucien and J\"{u}rgens, Pascal and Katzenbach, Christian and Kille, Benjamin and Klimkiewicz, Beate and Loosen, Wiebke and Moeller, Judith and Radanovic, Goran and Shani, Guy and Tintarev, Nava and Tolmeijer, Suzanne and van Atteveldt, Wouter and Vrijenhoek, Sanne and Zueger, Theresa},
  title =	{{Diversity in News Recommendation (Dagstuhl Perspectives Workshop 19482)}},
  pages =	{43--61},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2021},
  volume =	{9},
  number =	{1},
  editor =	{Bernstein, Abraham and de Vreese, Claes and Helberger, Natali and Schulz, Wolfgang and Zweig, Katharina and Baden, Christian and Beam, Michael A. and Hauer, Marc P. and Heitz, Lucien and J\"{u}rgens, Pascal and Katzenbach, Christian and Kille, Benjamin and Klimkiewicz, Beate and Loosen, Wiebke and Moeller, Judith and Radanovic, Goran and Shani, Guy and Tintarev, Nava and Tolmeijer, Suzanne and van Atteveldt, Wouter and Vrijenhoek, Sanne and Zueger, Theresa},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.9.1.43},
  URN =		{urn:nbn:de:0030-drops-137456},
  doi =		{10.4230/DagMan.9.1.43},
  annote =	{Keywords: News, recommender systems, diversity}
}
Document
DOI: 10.4230/OASIcs.LDK.2019.8
Exploiting Background Knowledge for Argumentative Relation Classification

Authors: Jonathan Kobbe, Juri Opitz, Maria Becker, Ioana Hulpuş, Heiner Stuckenschmidt, and Anette Frank

Published in: OASIcs, Volume 70, 2nd Conference on Language, Data and Knowledge (LDK 2019)

Abstract
Argumentative relation classification is the task of determining the type of relation (e.g., support or attack) that holds between two argument units. Current state-of-the-art models primarily exploit surface-linguistic features including discourse markers, modals or adverbials to classify argumentative relations. However, a system that performs argument analysis using mainly rhetorical features can be easily fooled by the stylistic presentation of the argument as opposed to its content, in cases where a weak argument is concealed by strong rhetorical means. This paper explores the difficulties and the potential effectiveness of knowledge-enhanced argument analysis, with the aim of advancing the state-of-the-art in argument analysis towards a deeper, knowledge-based understanding and representation of arguments. We propose an argumentative relation classification system that employs linguistic as well as knowledge-based features, and investigate the effects of injecting background knowledge into a neural baseline model for argumentative relation classification. Starting from a Siamese neural network that classifies pairs of argument units into support vs. attack relations, we extend this system with a set of features that encode a variety of features extracted from two complementary background knowledge resources: ConceptNet and DBpedia. We evaluate our systems on three different datasets and show that the inclusion of background knowledge can improve the classification performance by considerable margins. Thus, our work offers a first step towards effective, knowledge-rich argument analysis.
Cite as

Jonathan Kobbe, Juri Opitz, Maria Becker, Ioana Hulpuş, Heiner Stuckenschmidt, and Anette Frank. Exploiting Background Knowledge for Argumentative Relation Classification. In 2nd Conference on Language, Data and Knowledge (LDK 2019). Open Access Series in Informatics (OASIcs), Volume 70, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kobbe_et_al:OASIcs.LDK.2019.8,
  author =	{Kobbe, Jonathan and Opitz, Juri and Becker, Maria and Hulpu\c{s}, Ioana and Stuckenschmidt, Heiner and Frank, Anette},
  title =	{{Exploiting Background Knowledge for Argumentative Relation Classification}},
  booktitle =	{2nd Conference on Language, Data and Knowledge (LDK 2019)},
  pages =	{8:1--8:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-105-4},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{70},
  editor =	{Eskevich, Maria and de Melo, Gerard and F\"{a}th, Christian and McCrae, John P. and Buitelaar, Paul and Chiarcos, Christian and Klimek, Bettina and Dojchinovski, Milan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.LDK.2019.8},
  URN =		{urn:nbn:de:0030-drops-103723},
  doi =		{10.4230/OASIcs.LDK.2019.8},
  annote =	{Keywords: argument structure analysis, background knowledge, argumentative functions, argument classification, commonsense knowledge relations}
}
  • Refine by Author
  • 2 Gottesbüren, Lars
  • 2 Heuer, Tobias
  • 2 Sanders, Peter
  • 1 Baden, Christian
  • 1 Beam, Michael A.
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 1 Applied computing → Economics
  • 1 Applied computing → Psychology
  • 1 Applied computing → Sociology
  • 1 Computing methodologies → Neural networks
  • Show More...

  • Refine by Keyword
  • 1 News
  • 1 argument classification
  • 1 argument structure analysis
  • 1 argumentative functions
  • 1 background knowledge
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2021
  • 1 2019
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact