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)
Lena Krieg

Publications:

Amin Coja-Oghlan, Lena Krieg, Johannes Christian Lawnik and Olga Scheftelowitsch.
Bad local minima exist in the stochastic block model.
CoRR abs/2407.17851, 2024.
URL, DOI BibTeX

@article{cojaoghlan2024badlocalminimaexist,
	title = "Bad local minima exist in the stochastic block model",
	author = "Amin Coja-Oghlan and Lena Krieg and Johannes Christian Lawnik and Olga Scheftelowitsch",
	year = 2024,
	eprint = "2407.17851",
	journal = "CoRR",
	volume = "abs/2407.17851",
	doi = "10.48550/arXiv.2407.17851",
	archiveprefix = "arXiv",
	primaryclass = "math.ST",
	url = "https://arxiv.org/abs/2407.17851"
}

Abdou Majeed Alidou, Júlia Baligács, Max Hahn-Klimroth, Jan Hazla, Lukas Hintze and Olga Scheftelowitsch.
Inevitability of Polarization in Geometric Opinion Exchange.
CoRR abs/2402.08446, 2024.
URL, DOI BibTeX

@article{DBLP:journals/corr/abs-2402-08446,
	author = "Abdou Majeed Alidou and J{\'{u}}lia Balig{\'{a}}cs and Max Hahn{-}Klimroth and Jan Hazla and Lukas Hintze and Olga Scheftelowitsch",
	title = "Inevitability of Polarization in Geometric Opinion Exchange",
	journal = "CoRR",
	volume = "abs/2402.08446",
	year = 2024,
	url = "https://doi.org/10.48550/arXiv.2402.08446",
	doi = "10.48550/ARXIV.2402.08446",
	timestamp = "Mon, 19 Feb 2024 15:25:43 +0100",
	biburl = "https://dblp.org/rec/journals/corr/abs-2402-08446.bib"
}

Amin Coja-Oghlan, Max Hahn-Klimroth, Lukas Hintze, Dominik Kaaser, Lena Krieg, Maurice Rolvien and Olga Scheftelowitsch.
Noisy group testing via spatial coupling.
CoRR abs/2402.02895, 2024.
URL, DOI BibTeX

@article{DBLP:journals/corr/abs-2402-02895,
	author = "Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Lukas Hintze and Dominik Kaaser and Lena Krieg and Maurice Rolvien and Olga Scheftelowitsch",
	title = "Noisy group testing via spatial coupling",
	journal = "CoRR",
	volume = "abs/2402.02895",
	year = 2024,
	url = "https://doi.org/10.48550/arXiv.2402.02895",
	doi = "10.48550/ARXIV.2402.02895",
	timestamp = "Mon, 12 Feb 2024 13:36:38 +0100",
	biburl = "https://dblp.org/rec/journals/corr/abs-2402-02895.bib"
}

Amin Coja-Oghlan, Mihyun Kang, Lena Krieg and Maurice Rolvien.
The k-XORSAT Threshold Revisited.
Electron. J. Comb. 31(2), 2024.
URL, DOI BibTeX

@article{DBLP:journals/combinatorics/CojaOghlanKKR24,
	author = "Amin Coja{-}Oghlan and Mihyun Kang and Lena Krieg and Maurice Rolvien",
	title = "The k-XORSAT Threshold Revisited",
	journal = "Electron. J. Comb.",
	volume = 31,
	number = 2,
	year = 2024,
	url = "https://doi.org/10.37236/11815",
	doi = "10.37236/11815",
	timestamp = "Wed, 08 May 2024 16:26:04 +0200",
	biburl = "https://dblp.org/rec/journals/combinatorics/CojaOghlanKKR24.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser and Philipp Loick.
Information-theoretic and algorithmic aspects of parallel and distributed reconstruction from pooled data.
J. Parallel Distributed Comput. 180:104718, 2023.
URL, DOI BibTeX

@article{DBLP:journals/jpdc/GebhardHKL23,
	author = "Oliver Gebhard and Max Hahn{-}Klimroth and Dominik Kaaser and Philipp Loick",
	title = "Information-theoretic and algorithmic aspects of parallel and distributed reconstruction from pooled data",
	journal = "J. Parallel Distributed Comput.",
	volume = 180,
	pages = 104718,
	year = 2023,
	url = "https://doi.org/10.1016/j.jpdc.2023.104718",
	doi = "10.1016/J.JPDC.2023.104718",
	timestamp = "Fri, 18 Aug 2023 08:46:39 +0200",
	biburl = "https://dblp.org/rec/journals/jpdc/GebhardHKL23.bib"
}

Max Hahn-Klimroth and Dominik Kaaser.
On Reconstructing the Patient Zero from Sensor Measurements.
In 43rd IEEE International Conference on Distributed Computing Systems, ICDCS 2023, Hong Kong, July 18-21, 2023. 2023, 1–11.
URL, DOI BibTeX

@inproceedings{DBLP:conf/icdcs/HahnKlimrothK23,
	author = "Max Hahn{-}Klimroth and Dominik Kaaser",
	title = "On Reconstructing the Patient Zero from Sensor Measurements",
	booktitle = "43rd {IEEE} International Conference on Distributed Computing Systems, {ICDCS} 2023, Hong Kong, July 18-21, 2023",
	pages = "1--11",
	year = 2023,
	url = "https://doi.org/10.1109/ICDCS57875.2023.00065",
	doi = "10.1109/ICDCS57875.2023.00065",
	timestamp = "Tue, 07 May 2024 20:07:22 +0200",
	biburl = "https://dblp.org/rec/conf/icdcs/HahnKlimrothK23.bib"
}

Yannick Gerstorfer, Max Hahn-Klimroth and Lena Krieg.
A Notion of Feature Importance by Decorrelation and Detection of Trends by Random Forest Regression.
Data Sci. J. 22, 2023.
BibTeX

@article{DBLP:journals/datascience/GerstorferHK23,
	author = "Yannick Gerstorfer and Max Hahn{-}Klimroth and Lena Krieg",
	title = "A Notion of Feature Importance by Decorrelation and Detection of Trends by Random Forest Regression",
	journal = "Data Sci. J.",
	volume = 22,
	year = 2023
}

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg and Malin Rau.
Inference of a rumor's source in the independent cascade model.
In Uncertainty in Artificial Intelligence, UAI 2023, July 31 - 4 August 2023, Pittsburgh, PA, USA 216. 2023, 152–162.
URL BibTeX

@inproceedings{DBLP:conf/uai/BerenbrinkHKKR23,
	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",
	booktitle = "Uncertainty in Artificial Intelligence, {UAI} 2023, July 31 - 4 August 2023, Pittsburgh, PA, {USA}",
	series = "Proceedings of Machine Learning Research",
	volume = 216,
	pages = "152--162",
	year = 2023,
	url = "https://proceedings.mlr.press/v216/berenbrink23a.html",
	timestamp = "Tue, 07 May 2024 20:09:01 +0200",
	biburl = "https://dblp.org/rec/conf/uai/BerenbrinkHKKR23.bib"
}

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"
}

Amin Coja-Oghlan, Jane Gao, Max Hahn-Klimroth, Joon Lee, Noëla Müller and Maurice Rolvien.
The Full Rank Condition for Sparse Random Matrices.
In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, September 11-13, 2023, Atlanta, Georgia, USA 275. 2023, 54:1–54:14.
URL, DOI BibTeX

@inproceedings{DBLP:conf/approx/Coja-OghlanGHLM23,
	author = {Amin Coja{-}Oghlan and Jane 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",
	booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, {APPROX/RANDOM} 2023, September 11-13, 2023, Atlanta, Georgia, {USA}",
	series = "LIPIcs",
	volume = 275,
	pages = "54:1--54:14",
	year = 2023,
	url = "https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.54",
	doi = "10.4230/LIPICS.APPROX/RANDOM.2023.54",
	timestamp = "Tue, 07 May 2024 20:12:27 +0200",
	biburl = "https://dblp.org/rec/conf/approx/Coja-OghlanGHLM23.bib"
}

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
}

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