Publications

This page doesn’t get updated very regularly so it may be somewhat outdated. See my CV or google scholar page for updated information.

Peer-reviewed Publications

1. Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
   Nate Veldt
   SOSA 2024
2. Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
   Vedangi Bengali, Nate Veldt
   CIKM 2023
3. Optimal LP Rounding and Fast Combinatorial Algorithms for Clustering Edge-Colored Hypergraphs
   Nate Veldt,
   ICML 2023
   
4. Augmented Sparsifiers for Generalized Hypergraph Cuts
   Austin R. Benson, Jon Kleinberg, Nate Veldt,
   JMLR, 2023
5. Cut-matching Games for Generalized Hypergraph Cuts
   Nate Veldt
   Proceedings of the 2023 World Wide Web Conference, May 2023
   Preprint
6. Combinatorial characterizations and impossibilities for higher-order homophily
   Nate Veldt, Austin R. Benson, Jon Kleinberg
   Science Advances, 2023 
   Paper, arXiv preprint
7. Hypergraph Cuts with General Splitting Functions
   Nate Veldt, Austin R. Benson, Jon Kleinberg
   SIAM Review, 2022
   Paper, arXiv Preprint
8. 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
9. 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
10. 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
11. 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
12. The Generalized Mean Densest Subgraph Problem
    Nate Veldt, Austin R. Benson, Jon Kleinberg
    SIGKDD Conference on Knowledge Discovery and Data Mining, August 2021
    Paper
13. Generative hypergraph clustering: from blockmodels to modularity
    Philip S. Chodrow, Nate Veldt, Austin R. Benson
    Science Advances, July 2021
    Paper 
14. 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
15. 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
16. 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
17. 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
18. 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
19. 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
20. 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
21. 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
22. 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
23. 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
24. 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
25. 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
26. 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
27. 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