Abram Magner

Assistant professor, Department of Computer Science, University at Albany, SUNY

Email: amagner at albany.edu
Education: Ph.D. in computer science, Purdue University (2015).

An image of Abram Magner in front of a whiteboard.

(1/31/2024) -- I was unable to update my webpage for approximately a year, due to some server configuration issue. I plan to eventually update it, now that access is restored. As of this posting, I have only updated it somewhat.

(6/12/2025) -- Update: I have updated this page but have not yet updated other pages, including "Papers" and "Recent talks".

Research interests

My research is theoretical machine learning and probabilistic inference problems involving graphs. In particular, I am interested in fundamental information-theoretic limits of learning/statistical inference and data compression/representation problems, generally involving networks, as well as efficient algorithms to achieve those limits. My recent work has concerned various notions of learning the mechanisms underlying the evolution of dynamic graphs, as well as formulating information theoretic limits of graph convolutional networks for graph representation learning. I also work on problems involving symmetry and learning, as well as quantum learning theory.

I am looking for a PhD student.

If you're interested in pursuing a PhD in any of the areas described in my research interests, please feel free to send me an email, including your CV, transcripts, and any other information you think might be useful. I am particularly seeking students with mathematical maturity and an interest in applying mathematical methods to machine learning and graph problems. You should have a solid understanding of probability and the ability to write formal theorems and proofs.

Papers (not yet updated)

Recent talks (not yet updated)

Abridged CV -- My full CV is signed and dated.

Funding

NSF CAREER: Theoretical Foundations for Learning Network Dynamics. CCF 2338855

NSF Collaborative Research: CIF: Medium: Foundations of Robust Deep Learning via Data Geometry and Dyadic Structure. CCF 2212327

NSF Collaborative Research: NSF-ANR QISE: QUANTINT: Quantum Information and Network Theory: Algorithms and Performance Limits. FET 2545353

Teaching

ICSI 529: Probability and computing (Fall 2025, Fall 2024)

World of Computer Science/World of Engineering and Applied Science Living and Learning Community Seminar (Fall 2025, Fall 2024, Fall 2023)

ICSI 521: Discrete mathematics with applications (Spring 2025, Spring 2024, Spring 2020)

ICSI 501: Numerical linear algebra (Spring 2022, Spring 2021, Fall 2019)

ICSI 401: Numerical methods (Spring 2023, Fall 2021, Fall 2020, Fall 2019)

ICSI 210: Discrete structures (Fall 2023, Fall 2022)

At UIUC: Analytic combinatorics, with applications (half semester, Spring 2017)

News

(6/1/2025) -- MS thesis advisee Arka Prabha Das has graduated with a thesis on quantum learning theory. Congratulations!

(3/1/2025) -- Featurized Models of Network Averaging Dynamics: Identifiability and Sample Complexity submitted (conference).

(3/1/2025) -- Generalizing and Enforcing Continuous Symmetries for Image Data using Vector Fields submitted (conference).

(3/1/2025) -- Multi-Dictionary Learning for Low-Rank Sparse Coding submitted (conference).

(11/15/2024) -- My Ph.D. student, Amith K. Singh, has passed his oral qualifying exam. Congratulations!

(11/1/2024) -- Symmetry Discovery Beyond Affine Transformations accepted to Neurips 2024 (conference).

(10/1/2024) -- Fat shattering, joint measurability, and PAC learnability of POVM hypothesis classes accepted to Springer Quantum Information Processing (journal).

(8/1/2024) -- Low Rank Multi-Dictionary Selection at Scale accepted to ACM KDD (conference).

(6/1/2024) -- Empirical Risk Minimization and Uniform Convergence for Probabilistically Observed and Quantum Measurement Hypothesis Classes accepted to IEEE ISIT 2024 (conference).

(12/31/2023) -- I am grateful to have received an NSF CAREER award! Link

(8/1/2023) -- Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information-Theoretic Measures accepted to IEEE Access (journal).

(11/1/2022) -- Fast and Accurate Spreading Process Temporal Scale Estimation accepted to Transactions on Machine Learning Research (journal). Link

(4/22/2022) -- Local Limit Theorems for Approximate Maximum Likelihood Estimation of Network Information Spreading Models accepted to ISIT 2022 (conference).

(1/18/2022) -- Sample Complexity Bounds for PAC Learning of Quantum Measurement Classes accepted to AISTATS 2022 (conference).

(11/9/2021) -- Fundamental Limits of Deep Graph Convolutional Networks for Graph Classification accepted to IEEE Transactions on Information Theory (journal).

(10/18/2021) -- Submitted a paper on sample complexity of PAC learning in a quantum setting (conference).

(10/4/2021) -- Local Central Limit Theorems for Approximate Maximum Likelihood Estimation of Network Information Spreading Models submitted (conference). This is a sole author paper.

(10/4/2021) -- Temporal Scale Estimation for Oversampled Network Cascades: Theory, Algorithms, and Experiments (https://arxiv.org/abs/2109.10937) submitted (conference).

(5/4/2021) -- On Dimension in Graph Convolutional Networks for Distinguishing Random Graph Models accepted to ISIT 2021 (conference).

(4/28/2020) -- Struct2Graph: A graph attention network for structure based predictions of protein-protein interactions submitted (journal).

(3/31/2020) -- The Power of Graph Convolutional Networks to Distinguish Random Graph Models (short version) accepted to ISIT 2020 (conference).

(3/11/2020) -- Compression of Dynamic Graphs Generated by a Duplication Model accepted to Algorithmica (journal).

(2/13/2020) -- The Role of Dimension in Graph Convolutional Networks submitted (conference).

(1/15/2020) -- The Power of Graph Convolutional Networks to Distinguish Random Graph Models (short version) submitted (conference).

(12/18/2019) -- A Deep Learning Architecture for Metabolic Pathway Prediction accepted to Bioinformatics (Oxford University Press) (journal).

(11/25/2019) -- Toward Universal Testing of Dynamic Network Models accepted to Algorithmic Learning Theory 2020 (conference).

(10/15/2019) -- The Power of Graph Convolutional Networks to Distinguish Random Graph Models submitted (journal).

(9/24/2019) -- A Deep Learning Architecture for Metabolic Pathway Prediction submitted (journal).

(9/20/2019) -- Toward Universal Testing of Dynamic Network Models submitted (conference).

(4/5/2019) -- Compression of Preferential Attachment Graphs accepted to ISIT 2019 (conference).

(1/30/2019) -- Goodness of Fit Testing for Dynamic Networks submitted (conference).

(1/14/2019) -- Inferring Temporal Information from a Snapshot of a Dynamic Network accepted to Nature Scientific Reports (journal).

(11/16/2018) -- Asymmetry and Structural Information in Preferential Attachment Graphs accepted to Random Structures and Algorithms (journal).

(10/1/2018) -- I will be joining the Department of Electrical Engineering and Computer Science at the University of Michigan as a research fellow.

(8/6/2018) -- Compression of Dynamic Graphs Generated by a Duplication Model accepted to the 2018 Allerton Conference on Communication, Control, and Computing.

(8/6/2018) -- Network Archaeology via Epidemic Processes: The Case of Growing Trees accepted to the 2018 Allerton Conference on Communication, Control, and Computing.

(7/12/2018) -- Entropy and Optimal Compression of Some General Plane Trees accepted to ACM Transactions on Algorithms (journal).

(7/8/2018) -- Network Archaeology via Epidemic Processes: The Case of Growing Trees submitted (conference).

(7/8/2018) -- Compression of Dynamic Graphs Generated by a Duplication Model submitted (conference).

(6/4/2018) -- Lossless Compression of Binary Trees with Correlated Vertex Names accepted to IEEE Transactions on Information Theory (journal).

(1/18/2018) -- Asymmetric Renyi Problem accepted to Combinatorics, Probability, and Computing (journal).

(12/22/2017) -- TIMES: Temporal Information Maximally Extracted from Structure accepted to WWW 2018, Lyon, France.

(11/8/2017) -- Gave an invited talk in the Purdue University Statistics Department probability seminar.

(11/3/2017) -- Gave an invited talk in the University of Michigan Computer Science and Engineering theory seminar.

(9/19/2017) -- Entropy and Optimal Compression of Some General Plane Trees submitted (journal).

(9/14/2017) -- Gave an invited talk in the Johns Hopkins Applied Mathematics and Statistics departmental seminar.

(9/7/2017) -- Large Deviations for Increasing Subsequences of Permutations and a Concurrency Application accepted to IFIP Performance 2017 (conference).

(7/25/2017) -- Submitted Large Deviations for Increasing Subsequences of Permutations and a Concurrency Application (conference version of the Sigmetrics MAMA workshop paper).

(7/12/2017) -- Submitted Structural Information and Compression of Scale-Free Graphs (conference version of Asymmetry and Structural Information in Preferential Attachment Graphs; contains more results on optimal compression algorithms).

(5/31/2017) -- Submitted Asymmetry and Structural Information in Preferential Attachment Graphs (journal paper).

(5/18/2017) -- Submitted TIMES: Temporal Information Maximally Extracted from Structure (conference paper).

(5/13/2017) -- Large Deviations for Increasing Subsequences of Permutations and a Concurrency Application accepted for presentation at the Sigmetrics Mathematical performance Modeling and Analysis (MAMA) workshop.

(4/27/2017) -- Large Deviations for Increasing Subsequences of Permutations and a Concurrency Application (extended abstract) submitted.

(4/1/2017) -- Entropy of Some General Plane Trees accepted to ISIT 2017.

(4/1/2017) -- Recovery of Vertex Orderings in Dynamic Graphs accepted to ISIT 2017.

(1/6/2017) -- Submitted Recovery of Vertex Orderings in Dynamic Graphs (conference paper).

(1/3/2017) -- Submitted Entropy of Some General Plane Trees (conference paper).

(11/20/2016) -- I will be teaching a half-semester course on analytic combinatorics and applications, starting March 2017.

(11/7/2016) -- Fundamental Bounds for Sequence Reconstruction from Nanopore Sequencers to appear in IEEE Transactions on Molecular, Biological, and Multi-Scale Communications, Special Issue on Biological Applications of Information Theory

(11/5/2016) -- Profiles of PATRICIA Tries accepted to Algorithmica, 76(4), 1--67.