Reconstruction and Learning in Complex Networks

Reconstruction and Learning in Complex Networks

Description:

The aim of this subproject is to develop algorithms for inference problems such as the patient-zero problem on complex networks, and to explore the information-theoretic limitations of such algorithms. We will conduct this investigation for belief propagation, a classic network dynamics that is central to numerous applications in artificial intelligence and information theory, and related dynamics for information dissemination. Over the past few years intriguing predictions on these problems have been made on the basis of analytic but non-rigorous physics calculations. The aim here is to seize upon the physics ideas to prove rigorous theoretical results. We expect that this challenging task will require the substantial extension of existing methods for the exact analysis of message passing algorithms, and perhaps the development of completely new techniques tailored to models of complex networks. Additionally, we will explore the impact of these new methods on learning problems. An example of such a problem is the Hopfield model, a simple model of a neural network for memorising patterns.

Staff:

Prof. Dr. Amin Coja-Oghlan (Main PI)
Dr. Max Hahn-Klimroth

Publications:

Yannick Gerstorfer, Lena Krieg and Max Hahn-Klimroth.
A Notion of Feature Importance by Decorrelation and Detection of Trends by Random Forest Regression.
CoRR abs/2303.01156, 2023.
URL BibTeX

@article{https://doi.org/10.48550/arxiv.2303.01156,
	%doi = "10.48550/ARXIV.2303.00043",
	url = "https://arxiv.org/abs/2303.01156",
	author = "Gerstorfer, Yannick and Krieg, Lena and Hahn-Klimroth, Max",
	title = "A Notion of Feature Importance by Decorrelation and Detection of Trends by Random Forest Regression",
	journal = "CoRR",
	year = 2023,
	volume = "abs/2303.01156"
}

Max Hahn-Klimroth, Dominik Kaaser and Malin Rau.
Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes.
CoRR abs/2303.00043, 2023.
URL BibTeX

@article{https://doi.org/10.48550/arxiv.2303.00043,
	%doi = "10.48550/ARXIV.2303.00043",
	url = "https://arxiv.org/abs/2303.00043",
	author = "Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin",
	title = "Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes",
	journal = "CoRR",
	year = 2023,
	volume = "abs/2303.00043"
}

Amin Coja-Oghlan, Mihyun Kang, Lena Krieg and Maurice Rolvien.
The $k$-XORSAT threshold revisited.
CoRR abs/2301.09287, 2023.
URL BibTeX

@article{toappear/nlpa4,
	author = "Coja-Oghlan, Amin and Kang, Mihyun and Krieg, Lena and Rolvien, Maurice",
	title = "The $k$-XORSAT threshold revisited",
	journal = "CoRR",
	volume = "abs/2301.09287",
	url = "https://arxiv.org/abs/2301.09287",
	year = 2023
}

Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser and Malin Rau.
On the Hierarchy of Distributed Majority Protocols.
In 26th International Conference on Principles of Distributed Systems (OPODIS 2022) 253. 2023, 23:1–23:19.
URL, DOI BibTeX

@inproceedings{berenbrink_et_al:LIPIcs.OPODIS.2022.23,
	author = "Berenbrink, Petra and Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin",
	title = "{On the Hierarchy of Distributed Majority Protocols}",
	booktitle = "26th International Conference on Principles of Distributed Systems (OPODIS 2022)",
	pages = "23:1--23:19",
	series = "Leibniz International Proceedings in Informatics (LIPIcs)",
	isbn = "978-3-95977-265-5",
	issn = "1868-8969",
	year = 2023,
	volume = 253,
	publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
	address = "Dagstuhl, Germany",
	url = "https://drops.dagstuhl.de/opus/volltexte/2023/17643",
	urn = "urn:nbn:de:0030-drops-176434",
	doi = "10.4230/LIPIcs.OPODIS.2022.23",
	annote = "Keywords: Consensus, Majority, Hierarchy, Stochastic Dominance, Population Protocols, Gossip Model, Strassen’s Theorem"
}

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg and Malin Rau.
Inference of a Rumor's Source in the Independent Cascade Model.
CoRR abs/2205.12125, 2022.
URL, DOI BibTeX

@article{DBLP:journals/corr/abs-2205-12125,
	author = "Petra Berenbrink and Max Hahn{-}Klimroth and Dominik Kaaser and Lena Krieg and Malin Rau",
	title = "Inference of a Rumor's Source in the Independent Cascade Model",
	journal = "CoRR",
	volume = "abs/2205.12125",
	year = 2022,
	url = "https://doi.org/10.48550/arXiv.2205.12125",
	doi = "10.48550/arXiv.2205.12125",
	eprinttype = "arXiv",
	eprint = "2205.12125",
	timestamp = "Mon, 30 May 2022 15:47:29 +0200",
	biburl = "https://dblp.org/rec/journals/corr/abs-2205-12125.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Oliver Gebhard, Max Hahn-Klimroth, Olaf Parczyk, Manuel Penschuck, Maurice Rolvien, Jonathan Scarlett and Nelvin Tan.
Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms.
IEEE Trans. Inf. Theory 68(5):3253–3280, 2022.
URL, DOI BibTeX

@article{DBLP:journals/tit/GebhardHPPRST22,
	author = "Oliver Gebhard and Max Hahn{-}Klimroth and Olaf Parczyk and Manuel Penschuck and Maurice Rolvien and Jonathan Scarlett and Nelvin Tan",
	title = "Near-Optimal Sparsity-Constrained Group Testing: Improved Bounds and Algorithms",
	journal = "{IEEE} Trans. Inf. Theory",
	volume = 68,
	number = 5,
	pages = "3253--3280",
	year = 2022,
	url = "https://doi.org/10.1109/TIT.2022.3141244",
	doi = "10.1109/TIT.2022.3141244",
	timestamp = "Wed, 18 May 2022 10:21:10 +0200",
	biburl = "https://dblp.org/rec/journals/tit/GebhardHPPRST22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser and Philipp Loick.
On the Parallel Reconstruction from Pooled Data.
In 2022 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2022, Lyon, France, May 30 - June 3, 2022. 2022, 425–435.
URL, DOI BibTeX

@inproceedings{DBLP:conf/ipps/GebhardHKL22,
	author = "Oliver Gebhard and Max Hahn{-}Klimroth and Dominik Kaaser and Philipp Loick",
	title = "On the Parallel Reconstruction from Pooled Data",
	booktitle = "2022 {IEEE} International Parallel and Distributed Processing Symposium, {IPDPS} 2022, Lyon, France, May 30 - June 3, 2022",
	pages = "425--435",
	publisher = "{IEEE}",
	year = 2022,
	url = "https://doi.org/10.1109/IPDPS53621.2022.00048",
	doi = "10.1109/IPDPS53621.2022.00048",
	timestamp = "Fri, 22 Jul 2022 11:43:23 +0200",
	biburl = "https://dblp.org/rec/conf/ipps/GebhardHKL22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick and Manuel Penschuck.
Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study.
In 20th International Symposium on Experimental Algorithms, SEA 2022, July 25-27, 2022, Heidelberg, Germany 233. 2022, 8:1–8:18.
URL, DOI BibTeX

@inproceedings{DBLP:conf/wea/Coja-OghlanHLP22,
	author = "Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Philipp Loick and Manuel Penschuck",
	title = "Efficient and Accurate Group Testing via Belief Propagation: An Empirical Study",
	booktitle = "20th International Symposium on Experimental Algorithms, {SEA} 2022, July 25-27, 2022, Heidelberg, Germany",
	series = "LIPIcs",
	volume = 233,
	pages = "8:1--8:18",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2022,
	url = "https://doi.org/10.4230/LIPIcs.SEA.2022.8",
	doi = "10.4230/LIPIcs.SEA.2022.8",
	timestamp = "Mon, 11 Jul 2022 15:33:19 +0200",
	biburl = "https://dblp.org/rec/conf/wea/Coja-OghlanHLP22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Max Hahn-Klimroth and Dominik Kaaser.
Distributed Reconstruction of Noisy Pooled Data.
In 2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS) (). 2022, 89-99.
URL, DOI BibTeX

@inproceedings{9912157,
	author = "Hahn-Klimroth, Max and Kaaser, Dominik",
	booktitle = "2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS)",
	title = "Distributed Reconstruction of Noisy Pooled Data",
	year = 2022,
	volume = "",
	number = "",
	url = "https://ieeexplore.ieee.org/abstract/document/9912157",
	pages = "89-99",
	doi = "10.1109/ICDCS54860.2022.00018"
}

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Alexander S Wein and Ilias Zadik.
Statistical and Computational Phase Transitions in Group Testing.
In Conference on Learning Theory, 2-5 July 2022, London, UK 178. 2022, 4764–4781.
URL BibTeX

@inproceedings{DBLP:conf/colt/Coja-OghlanGHWZ22,
	author = "Amin Coja{-}Oghlan and Oliver Gebhard and Max Hahn{-}Klimroth and Alexander S. Wein and Ilias Zadik",
	title = "Statistical and Computational Phase Transitions in Group Testing",
	booktitle = "Conference on Learning Theory, 2-5 July 2022, London, {UK}",
	series = "Proceedings of Machine Learning Research",
	volume = 178,
	pages = "4764--4781",
	publisher = "{PMLR}",
	year = 2022,
	url = "https://proceedings.mlr.press/v178/coja-oghlan22a.html",
	timestamp = "Tue, 12 Jul 2022 17:36:52 +0200",
	biburl = "https://dblp.org/rec/conf/colt/Coja-OghlanGHWZ22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Max Hahn-Klimroth and Noela Müller.
Near optimal efficient decoding from pooled data.
In Conference on Learning Theory, 2-5 July 2022, London, UK 178. 2022, 3395–3409.
URL BibTeX

@inproceedings{DBLP:conf/colt/Hahn-KlimrothM22,
	author = {Max Hahn{-}Klimroth and Noela M{\"{u}}ller},
	title = "Near optimal efficient decoding from pooled data",
	booktitle = "Conference on Learning Theory, 2-5 July 2022, London, {UK}",
	series = "Proceedings of Machine Learning Research",
	volume = 178,
	pages = "3395--3409",
	publisher = "{PMLR}",
	year = 2022,
	url = "https://proceedings.mlr.press/v178/hahn-klimroth22a.html",
	timestamp = "Tue, 12 Jul 2022 17:36:52 +0200",
	biburl = "https://dblp.org/rec/conf/colt/Hahn-KlimrothM22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Maximilian Grischa Hahn-Klimroth.
Large discrete structures : statistical inference, combinatorics and limits.
Doctoral Thesis, Universitätsbibliothek Johann Christian Senckenberg, 2021.
URL, DOI BibTeX

@phdthesis{HahnKlimroth2021,
	author = "Maximilian Grischa Hahn-Klimroth",
	title = "Large discrete structures : statistical inference, combinatorics and limits",
	type = "Doctoral Thesis",
	pages = 259,
	school = {Universit{\"a}tsbibliothek Johann Christian Senckenberg},
	url = "https://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/61061",
	doi = "10.21248/gups.61061",
	year = 2021
}

Amin Coja-Oghlan, Pu Gao, Max Hahn-Klimroth, Joon Lee, Noëla Müller and Maurice Rolvien.
The full rank condition for sparse random matrices.
CoRR abs/2112.14090, 2021.
URL BibTeX

@article{DBLP:journals/corr/abs-2112-14090,
	author = {Amin Coja{-}Oghlan and Pu Gao and Max Hahn{-}Klimroth and Joon Lee and No{\"{e}}la M{\"{u}}ller and Maurice Rolvien},
	title = "The full rank condition for sparse random matrices",
	journal = "CoRR",
	volume = "abs/2112.14090",
	year = 2021,
	url = "https://arxiv.org/abs/2112.14090",
	eprinttype = "arXiv",
	eprint = "2112.14090",
	timestamp = "Wed, 05 Jan 2022 17:44:28 +0100",
	biburl = "https://dblp.org/rec/journals/corr/abs-2112-14090.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Max Hahn-Klimroth, Olaf Parczyk and Yury Person.
Minimum degree conditions for containing an r-regular r-connected subgraph.
CoRR abs/2108.07601, 2021.
URL BibTeX

@article{DBLP:journals/corr/abs-2108-07601,
	author = "Max Hahn{-}Klimroth and Olaf Parczyk and Yury Person",
	title = "Minimum degree conditions for containing an r-regular r-connected subgraph",
	journal = "CoRR",
	volume = "abs/2108.07601",
	year = 2021,
	url = "https://arxiv.org/abs/2108.07601",
	eprinttype = "arXiv",
	eprint = "2108.07601",
	timestamp = "Fri, 20 Aug 2021 13:55:54 +0200",
	biburl = "https://dblp.org/rec/journals/corr/abs-2108-07601.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Dimitris Achlioptas, Amin Coja-Oghlan, Max Hahn-Klimroth, Joon Lee, Noëla Müller, Manuel Penschuck and Guangyan Zhou.
The number of satisfying assignments of random 2-SAT formulas.
Random Struct. Algorithms 58(4):609–647, 2021.
URL, DOI BibTeX

@article{DBLP:journals/rsa/AchlioptasCHLMP21,
	author = {Dimitris Achlioptas and Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Joon Lee and No{\"{e}}la M{\"{u}}ller and Manuel Penschuck and Guangyan Zhou},
	title = "The number of satisfying assignments of random 2-SAT formulas",
	journal = "Random Struct. Algorithms",
	volume = 58,
	number = 4,
	pages = "609--647",
	year = 2021,
	url = "https://doi.org/10.1002/rsa.20993",
	doi = "10.1002/rsa.20993",
	timestamp = "Thu, 14 Oct 2021 08:50:41 +0200",
	biburl = "https://dblp.org/rec/journals/rsa/AchlioptasCHLMP21.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noëla Müller, Konstantinos Panagiotou and Matija Pasch.
Inference and Mutual Information on Random Factor Graphs.
In 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, March 16-19, 2021, Saarbrücken, Germany (Virtual Conference) 187. 2021, 24:1–24:15.
URL, DOI BibTeX

@inproceedings{DBLP:conf/stacs/Coja-OghlanHLMP21,
	author = {Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Philipp Loick and No{\"{e}}la M{\"{u}}ller and Konstantinos Panagiotou and Matija Pasch},
	title = "Inference and Mutual Information on Random Factor Graphs",
	booktitle = {38th International Symposium on Theoretical Aspects of Computer Science, {STACS} 2021, March 16-19, 2021, Saarbr{\"{u}}cken, Germany (Virtual Conference)},
	series = "LIPIcs",
	volume = 187,
	pages = "24:1--24:15",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2021,
	url = "https://doi.org/10.4230/LIPIcs.STACS.2021.24",
	doi = "10.4230/LIPIcs.STACS.2021.24",
	timestamp = "Thu, 11 Mar 2021 17:44:44 +0100",
	biburl = "https://dblp.org/rec/conf/stacs/Coja-OghlanHLMP21.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth and Philipp Loick.
Optimal Group Testing.
In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] 125. 2020, 1374–1388.
URL BibTeX

@inproceedings{DBLP:conf/colt/Coja-OghlanGHL20,
	author = "Amin Coja{-}Oghlan and Oliver Gebhard and Max Hahn{-}Klimroth and Philipp Loick",
	title = "Optimal Group Testing",
	booktitle = "Conference on Learning Theory, {COLT} 2020, 9-12 July 2020, Virtual Event [Graz, Austria]",
	series = "Proceedings of Machine Learning Research",
	volume = 125,
	pages = "1374--1388",
	publisher = "{PMLR}",
	year = 2020,
	url = "http://proceedings.mlr.press/v125/coja-oghlan20a.html",
	timestamp = "Fri, 27 Nov 2020 16:13:27 +0100",
	biburl = "https://dblp.org/rec/conf/colt/Coja-OghlanGHL20.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Algorithms, Dynamics, and Information Flow in NetworksDFG Research Unit

Description:

Staff:

Publications:

Algorithms, Dynamics, and Information Flow in Networks
DFG Research Unit