My research is focused on algorithms and complexity results for problems arising in network analysis and data science. A recent focus of my work has been on algorithm design for hypergraph clustering.
My research is focused on algorithms for network analysis and data science. This broadly includes work in mathematical optimization, machine learning, matrix computations, and theoretical computer science. To date much of my research has involved the theory and application of clustering algorithms.
I have specifically worked on special variants of correlation clustering for partitioning signed datasets, flow-based methods for localized community detection, and fast solvers for convex relaxations of graph clustering objectives. My motivation is to bridge the gap between the best theoretical results and the most practical algorithms for problems in network science and data mining. An 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.
Publications
(Code for most of my papers can be found on my github page.)
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, (to appear, August 2020) preprint
Minimizing Localized Ratio Cut Objectives in Hypergraphs Nate Veldt, Austin Benson, Jon Kleinberg SIGKDD Conference on Knowledge Discovery and Data Mining, (to appear, August 2020) preprint
Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs Nate Veldt, Anthony Wirth, David Gleich SIGKDD Conference on Knowledge Discovery and Data Mining, (to appear, August 2020) preprint
Clustering in Graphs and Hypergraphs with Categorical Edge Labels Ilya Amburg, Nate Veldt, and Austin 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 Gleich SIAM Workshop on Combinatorial Scientific Computing, February 2020 paper
Metric-Constrained Optimization for Graph Clustering Algorithms Nate Veldt, David 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 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 Gleich Proceedings of the 2019 SIAM International Conference on Data Mining, May 2019 paper
Correlation Clustering Generalized David Gleich, Nate Veldt, and Anthony Wirth Proceedings of the 29th International Symposium on Algorithms and Computation, December 2018, paper
Low-Rank Spectral Network Alignment Huda Nassar, Nate Veldt, Shahin Mohammadi, Ananth Grama, David 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 Gleich Proceedings of the 26th International World Wide Web Conference, April 2017 paper
A Simple and Strongly Local Flow-Based Method for Cut Improvement Nate Veldt, David Gleich, and Michael Mahoney Proceedings of the 33rd Annual International Conference on Machine Learning, June 2016 paperConference Talk
Preprints
Augmented Sparsifiers for Generalized Hypergraph Cuts Austin Benson, Jon Kleinberg, Nate Veldt preprint
Fair Clustering for Diverse and Experienced Groups Ilya Amburg, Nate Veldt, and Austin Benson preprint
Hypergraph Cuts with General Splitting Functions Nate Veldt, Austin Benson, Jon Kleinberg preprint
Thesis
Optimization Frameworks for Graph Clustering Nate Veldt Purdue University PhD Thesis, 2019 Link
Teaching
Cornell University
In Fall 2020 I am teaching MATH 2210: Linear Algebra, in Cornell's Math Department
I frequently give local seminar talks on topics in network analysis and numerical linear algebra. Sometimes the talks are on a specific research project I'm working on. Often though I like to take a tool or technique that has been useful in my research and present it in
a way that can be more broadly applied to other projects and problems that people might be interested in. Here are some recorded talks on optimization techniques that have been useful in my work.
Totally Unimodular Matrices in Linear Programming
Solving Low-Dimensional Optimization Problems via Zonotope Vertex Enumeration
Efficiently Solving Linear Programs with Triangle Inequality Constaints