Publications

See my CV or google scholar for updated information.

Preprints

1. Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
   Nate Veldt, 2022
   Preprint

2. Optimal LP Rounding and Fast Combinatorial Algorithms for Clustering Edge-Colored Hypergraphs
   Nate Veldt, 2022
   Preprint

3. Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization
   Austin R. Benson, Jon Kleinberg, Nate Veldt, 2020
   Preprint

Peer-reviewed Publications

1. Cut-matching Games for Generalized Hypergraph Cuts
   Nate Veldt
   Proceedings of the 2023 World Wide Web Conference, May 2023 (to appear)
   Preprint
2. Combinatorial characterizations and impossibilities for higher-order homophily
   Nate Veldt, Austin R. Benson, Jon Kleinberg
   Science Advances, 2023 
   Paper, arXiv preprint
3. Hypergraph Cuts with General Splitting Functions
   Nate Veldt, Austin R. Benson, Jon Kleinberg
   SIAM Review, 2022
   Paper, arXiv Preprint
4. 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
5. 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
6. 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
7. 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
8. The Generalized Mean Densest Subgraph Problem
   Nate Veldt, Austin R. Benson, Jon Kleinberg
   SIGKDD Conference on Knowledge Discovery and Data Mining, August 2021
   Paper
9. Generative hypergraph clustering: from blockmodels to modularity
   Philip S. Chodrow, Nate Veldt, Austin R. Benson
   Science Advances, July 2021
   Paper 
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. 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
21. 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
22. 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
23. 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