Publications

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: July 13, 2026

Peer-reviewed Publications

1. Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
   N Veldt, Thomas Stanley, Min Priest, Trevor Steil, Keita Iwabuchi, TS Jayram, Grace J Li, Geoffrey Sanders
   ICLR 2026

2. An Improved Combinatorial Algorithm for Edge-Colored Clustering in Hypergraphs
   Seongjune Han, Nate Veldt
   Web Conference 2026

3. A Simple and Fast (3+\varepsilon)-approximation for Constrained Correlation Clustering
   Nate Veldt
   SOSA 2026

4. The Densest SWAMP problem: subhypergraphs with arbitrary monotonic partial edge rewards.
   Bengali, V., Tatti, N., Kumpulainen, I., Adriaens, F., & Veldt, N.
   ECML-PKDD 2025
5. Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
   Alex Crane, Thomas Stanley, Blair D. Sullivan, Nate Veldt
   ICML 2025
6. 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
7. Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
   Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt
   ICML 2024
8. Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods
   Yufan Huang, David F. Gleich, Nate Veldt
   WebConf 2024
9. Overlapping and Robust Edge-Colored Clustering in Hypergraphs
   Alex Crane, Brian Lavallee, Blair D. Sullivan, Nate Veldt
   WSDM 2024
10. Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
    Nate Veldt
    SOSA 2024
11. 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
12. Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
    Vedangi Bengali, Nate Veldt
    CIKM 2023
13. Optimal LP Rounding and Fast Combinatorial Algorithms for Clustering Edge-Colored Hypergraphs
    Nate Veldt
    ICML 2023
    
14. Augmented Sparsifiers for Generalized Hypergraph Cuts
    Austin R. Benson, Jon Kleinberg, Nate Veldt,
    JMLR, 2023
15. Cut-matching Games for Generalized Hypergraph Cuts
    Nate Veldt
    Proceedings of the 2023 World Wide Web Conference, May 2023
    Preprint
16. Combinatorial characterizations and impossibilities for higher-order homophily
    Nate Veldt, Austin R. Benson, Jon Kleinberg
    Science Advances, 2023 
    Paper, arXiv preprint
17. Hypergraph Cuts with General Splitting Functions
    Nate Veldt, Austin R. Benson, Jon Kleinberg
    SIAM Review, 2022
    Paper, arXiv Preprint
18. 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
19. 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
20. 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
21. 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
22. The Generalized Mean Densest Subgraph Problem
    Nate Veldt, Austin R. Benson, Jon Kleinberg
    SIGKDD Conference on Knowledge Discovery and Data Mining, August 2021
    Paper
23. Generative hypergraph clustering: from blockmodels to modularity
    Philip S. Chodrow, Nate Veldt, Austin R. Benson
    Science Advances, July 2021
    Paper 
24. 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
25. 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
26. 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
27. 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
28. 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
29. 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
30. 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
31. 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
32. 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
33. 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
34. 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
35. 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
36. 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
37. 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

1. Optimization Frameworks for Graph Clustering
   Nate Veldt
   Purdue University PhD Thesis, 2019
   pdf, Video Presentation