This page may not be updated. See my CV or google scholar page for updated information.
Last update: April 2, 2025
Peer-reviewed Publications
- 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