Please see my CV or google scholar page for updated information about my publications.
This page contains some information and links that may be useful to keep around, but is usually not up to date.
This page last updated: December 12, 2025
Peer-reviewed Publications
- A Simple and Fast (3+\varepsilon)-approximation for Constrained Correlation Clustering
Nate Veldt
SOSA 2026 - The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards.
Bengali, V., Tatti, N., Kumpulainen, I., Adriaens, F., & Veldt, N.
ECML-PKDD 2025 - Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Alex Crane, Thomas Stanley, Blair D. Sullivan, Nate Veldt
ICML 2025 - Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Tree
N Veldt, T Stanley, BW Priest, T Steil, K Iwabuchi, TS Jayram, G Sanders
ICML 2025 - Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt
ICML 2024 - Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
Yufan Huang, David F. Gleich, Nate Veldt
WebConf 2024 - Overlapping and Robust Edge-Colored Clustering in Hypergraphs
Alex Crane, Brian Lavallee, Blair D. Sullivan, Nate Veldt
WSDM 2024 - Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
Nate Veldt
SOSA 2024 - Seven open problems in applied combinatorics
Sinan G. Aksoy, Ryan Bennink, Yuzhou Chen, Jos´e Fr´ıas, Yulia R. Gel, Bill Kay, Uwe Naumann, Carlos Ortiz Marrero, Anthony V. Petyuk, Sandip Roy, Ignacio Segovia-Dominguez, Nate Veldt, Stephen J. Young
Journal of Combinatorics, April 2023
Paper - Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
Vedangi Bengali, Nate Veldt
CIKM 2023 - Optimal LP Rounding and Fast Combinatorial Algorithms for Clustering Edge-Colored Hypergraphs
Nate Veldt
ICML 2023
- Augmented Sparsifiers for Generalized Hypergraph Cuts
Austin R. Benson, Jon Kleinberg, Nate Veldt,
JMLR, 2023 - Cut-matching Games for Generalized Hypergraph Cuts
Nate Veldt
Proceedings of the 2023 World Wide Web Conference, May 2023
Preprint - Combinatorial characterizations and impossibilities for higher-order homophily
Nate Veldt, Austin R. Benson, Jon Kleinberg
Science Advances, 2023
Paper, arXiv preprint - Hypergraph Cuts with General Splitting Functions
Nate Veldt, Austin R. Benson, Jon Kleinberg
SIAM Review, 2022
Paper, arXiv Preprint - Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds
Nate Veldt
Proceedings of the 2022 International Conference on Machine Learning, July 2022
Paper, arXiv preprint - fauci-email: a json digest of Anthony Fauci’s released emails
Austin R. Benson, Nate Veldt, David Gleich
International Conference on Web and Social Media, June 2022
Paper , arXiv preprint, dataset, 5-minute video - Hypergraph Clustering for Diverse and Experienced Groups
Ilya Amburg, Nate Veldt, and Austin R. Benson
SIAM International Conference on Data Mining, April 2022
Paper, arXiv preprint - Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
Nate Veldt, Austin R. Benson, Jon Kleinberg
Advances in Neural Information Processing Systems, December 2021
Paper - The Generalized Mean Densest Subgraph Problem
Nate Veldt, Austin R. Benson, Jon Kleinberg
SIGKDD Conference on Knowledge Discovery and Data Mining, August 2021
Paper - Generative hypergraph clustering: from blockmodels to modularity
Philip S. Chodrow, Nate Veldt, Austin R. Benson
Science Advances, July 2021
Paper - Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning
Meng Liu, Nate Veldt, Haoyu Song, Pan Li, and David F. Gleich
Proceedings of the 2021 World Wide Web Conference, May 2021
Paper, arXiv preprint - Graph Clustering in All Parameter Regimes
Junhao Gan, David F. Gleich, Nate Veldt, Anthony Wirth, Xin Zhang
International Symposium on Mathematical Foundations of Computer Science, August 2020
Paper, arXiv preprint - Minimizing Localized Ratio Cut Objectives in Hypergraphs
Nate Veldt, Austin R. Benson, Jon Kleinberg
SIGKDD Conference on Knowledge Discovery and Data Mining, August 2020
Preprint, Three minute video, Video Presentation - Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs
Nate Veldt, Anthony Wirth, David F. Gleich
SIGKDD Conference on Knowledge Discovery and Data Mining, August 2020
Preprint, Three-minute Video, Behind-the-scenes video - Clustering in Graphs and Hypergraphs with Categorical Edge Labels
Ilya Amburg, Nate Veldt, and Austin R. Benson
Proceedings of the 2020 World Wide Web Conference, May 2020
Paper - A Parallel Projection Method for Metric-Constrained Optimization
Cameron Ruggles, Nate Veldt, and David F. Gleich
SIAM Workshop on Combinatorial Scientific Computing, February 2020
Paper - Metric-Constrained Optimization for Graph Clustering Algorithms
Nate Veldt, David F. Gleich, Anthony Wirth and James Saunderson
SIAM Journal on Mathematics of Data Science, June 2019
Paper - Learning Resolution Parameters for Graph Clustering
Nate Veldt, David F. Gleich, and Anthony Wirth
Proceedings of the 2019 World Wide Web Conference, May 2019
Paper - Flow-Based Local Graph Clustering with Better Seed Set Inclusion
Nate Veldt, Christine Klymko, and David F. Gleich
Proceedings of the 2019 SIAM International Conference on Data Mining, May 2019
Paper - Correlation Clustering Generalized
David F. Gleich, Nate Veldt, and Anthony Wirth
Proceedings of the 29th International Symposium on Algorithms and Computation, December 2018
Paper, Full Version - A Correlation Clustering Framework for Community Detection
Nate Veldt, David F. Gleich, and Anthony Wirth
Proceedings of the 27th International World Wide Web Conference, April 2018
Paper, Full Version - Low-Rank Spectral Network Alignment
Huda Nassar, Nate Veldt, Shahin Mohammadi, Ananth Grama, David F. Gleich
Proceedings of the 27th International World Wide Web Conference, April 2018
Paper - Correlation Clustering with Low-Rank Matrices
Nate Veldt, Anthony Wirth, and David F. Gleich
Proceedings of the 26th International World Wide Web Conference, April 2017
Paper, Full Version - A Simple and Strongly Local Flow-Based Method for Cut Improvement
Nate Veldt, David F. Gleich, and Michael Mahoney
Proceedings of the 33rd Annual International Conference on Machine Learning, June 2016
Paper, Video Presentation
PhD Thesis
- Optimization Frameworks for Graph Clustering
Nate Veldt
Purdue University PhD Thesis, 2019
pdf, Video Presentation