My research is focused on algorithms and optimization techniques for network analysis and data science. This broadly includes contributions in mathematical optimization, machine learning, network science, data mining, and theoretical computer science. In past and ongoing research, I have developed new optimization tools and frameworks for graph clustering, hypergraph-based algorithms for higher-order data analysis, and fast algorithms for locally exploring and mining large datasets. I aim to contribute both to the theory and application of algorithms for data science, bridging the existing gap between the two whenever possible. Often this involves taking a theoretical method and making it more practical for real world use, without sacrificing theoretical guarantees. In other cases, it involves developing a deeper theoretical understanding of a useful technique that previously came with no formal theoretical guarantees. My overarching goal is to develop methods that are fast, satisfy strong approximation guarantees, and explicitly take into account important features of the real-world networks and datasets they operate on.

Peer-Reviewed Publications

  1. Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning
    Meng Liu, Nate Veldt, Haoyu Song, Pan Li, and David F. Gleich,
    To appear in Proceedings of the 2021 World Wide Web Conference, May 2021
    Preprint
  2. Graph Clustering in All Paramter Regimes
    Junhao Gan, David F. Gleich, Nate Veldt, Anthony Wirth, Xin Zhang
    International Symposium on Mathematical Foundations of Computer Science, August 2020
    Preprint
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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

 Preprints

  1. Higher-order Homophily is Combinatorially Impossible
    Nate Veldt, Austin R. Benson, Jon Kleinberg
    Preprint
  2. Hypergraph clustering: from blockmodels to modularity
    Philip S. Chodrow, Nate Veldt, Austin R. Benson
    Preprint
  3. Augmented Sparsifiers for Generalized Hypergraph Cuts
    Austin R. Benson, Jon Kleinberg, Nate Veldt
    Preprint
  4. Hypergraph Clustering for Diverse and Experienced Groups
    Ilya Amburg, Nate Veldt, and Austin R. Benson
    Preprint
  5. Hypergraph Cuts with General Splitting Functions
    Nate Veldt, Austin R. Benson, Jon Kleinberg
    Preprint

 Thesis

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