Nate Veldt


I am a postdoctoral associate in the Center for Applied Mathematics at Cornell University, working under the supervision of Professors Austin Benson and Jon Kleinberg.

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.

Curriculum vitae

Email: nveldt--at--cornell--dot--edu

Githubhttps://github.com/nveldt

Twitterhttps://twitter.com/n_veldt

 

    Research

    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.)

    1. 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
      preprint
    2. A Parallel Projection Method for Metric-Constrained Optimization
      Cameron Ruggles, Nate Veldt, and David Gleich
      SIAM Workshop on Combinatorial Scientific Computing (accepted, to appear February 2020)
      preprint
    3. 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
    4. Learning Resolution Parameters for Graph Clustering
      Nate Veldt, David Gleich, and Anthony Wirth
      Proceedings of the 2019 World Wide Web Conference, May 2019
      paper
    5. 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
    6. Correlation Clustering Generalized
      David Gleich, Nate Veldt, and Anthony Wirth
      Proceedings of the 29th International Symposium on Algorithms and Computation, December 2018,
      paper
    7. A Correlation Clustering Framework for Community Detection
      Nate Veldt, David Gleich, and Anthony Wirth
      Proceedings of the 27th International World Wide Web Conference, April 2018
      paper
    8. full version
    9. 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
    10. 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
    11. full version
    12. 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
      paper Conference Talk

     Preprints

    1. Localized Flow-Based Clustering in Hypergraphs
      Nate Veldt, Austin Benson, Jon Kleinberg
      preprint

    2. Parameterized Objectives and Algorithms for Clustering Bipartite Graphs and Hypergraphs
      Nate Veldt, Anthony Wirth, David Gleich
      preprint

    3. Hypergraph Cuts with General Splitting Functions
      Nate Veldt, Austin Benson, Jon Kleinberg
      preprint

    4. Graph Clustering in All Paramter Regimes
      Junhao Gan, David F. Gleich, Nate Veldt, Anthony Wirth, Xin Zhang
      preprint

     Thesis

    1. Optimization Frameworks for Graph Clustering
      Nate Veldt
      Purdue University PhD Thesis, 2019
      Link

    Teaching

    This semester I am teaching the Short Course in Matlab in Cornell's CS Department

    Here's a list of previous courses I taught while at Purdue University.

    In Fall of 2015 I received the Purdue Mathematics Department Excellence in Teaching Award:

    Purdue Math Department Excellence in Teaching Award 2015

    Recorded Talks

    I defended my PhD on April 16, 2019. If you're intersted to hear more about my work, there's a recording of my PhD defense on YouTube.

    Optimization Frameworks for Graph Clustering -- Nate Veldt, PhD Oral Defense

    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