Nate Veldt

News

Recent Coverage of our Science Advances article on Hypergraph Homophily

Posted on by

In celebration of the 25th anniversary of Watts and Strogatz’s seminal paper on small world networks, Nature Reviews Physics recently published a collection of six Research Spotlight articles on advances in network analysis (see 25 years of small-world network theory).

One of those six spotlights is a summary of my paper recently published in Science Advances (joint with Jon Kleinberg and Austin Benson) on higher-order measures of homophily. You can read the spotlight here: Measuring Similarities Within Groups. The original paper is here: Combinatorial characterizations and impossibilities for higher-order homophily

Our research findings on hypergraph homophily were also previously covered in an article on Phys.org, and an article in the Communications of the ACM.

 

SIAM ACDA Early Career Prize

Posted on by

I am honored to have been selected for the 2023 SIAM Activity Group on Applied and Computational Discrete Algorithms Early Career Prize. This prize is given every two years to an early career researcher for “distinguished contributions to the field in the six calendar years prior to the award year.”

I have been a member of the ACDA Activity Group since early 2020, and have greatly enjoyed all the opportunities I have had to attend ACDA events and interact with other members. I look forward to giving a talk on my research at the upcoming 2023 ACDA conference.

Article Published in Science Advances

Posted on by

My recent work on measures of homophily in group settings (joint work with Austin Benson and Jon Kleinberg) has just been published in Science Advances. I gave a brief overview of this research in an interview for a recent article that was published in a Communications of the ACM article.

Paper: https://www.science.org/doi/full/10.1126/sciadv.abq3200

Data: https://zenodo.org/record/7086798#.Y9CGkOzMIq0

Code: https://github.com/nveldt/HypergraphHomophily

Abstract

Homophily is the seemingly ubiquitous tendency for people to connect and interact with other individuals who are similar to them. This is a well-documented principle and is fundamental for how society organizes. Although many social interactions occur in groups, homophily has traditionally been measured using a graph model, which only accounts for pairwise interactions involving two individuals. Here, we develop a framework using hypergraphs to quantify homophily from group interactions. This reveals natural patterns of group homophily that appear with gender in scientific collaboration and political affiliation in legislative bill cosponsorship and also reveals distinctive gender distributions in group photographs, all of which cannot be fully captured by pairwise measures. At the same time, we show that seemingly natural ways to define group homophily are combinatorially impossible. This reveals important pitfalls to avoid when defining and interpreting notions of group homophily, as higher-order homophily patterns are governed by combinatorial constraints that are independent of human behavior but are easily overlooked.

New paper at NeurIPS on Decomposable Submodular Function minimization

Posted on by

Our paper “Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components” was just accepted for publication at NeurIPS (joint work with Austin Benson and Jon Kleinberg). The paper applies new sparsification techniques for solving a common class of decomposable submodular function minimization problems. This is motivated by applications to hypergraph clustering, but solves a more general problem. 

Preprint available at https://arxiv.org/abs/2110.14859

Hypergraph research featured in Quanta magazine

Posted on by

Some of my work on hypergraph cuts was recently featured in the Quanta magazine article How Big Data Carried Graph Theory Into New Dimensions.

The article covers a number of recent advances in higher-order data analysis, and in particular recent generalizations of graph theory problems to the hypergraph setting. My co-author Austin Benson was interviewed for the article, and describes our work on generalized notions of the hypergraph s-t cut problem in the section on “Hypergraphs in the Wild.”

New Fauci-email JSON dataset released, with accompanying analysis

Posted on by

Back in June of this year a 3000+ page pdf of Anthony Fauci’s emails were released in an effort to understand the United States government response to the COVID-19 pandemic. (See https://www.buzzfeednews.com/article/nataliebettendorf/fauci-emails-covid-response for the original Buzzfeed article). I had the privilege of collaborating with Austin Benson (Cornell University) and David Gleich (Purdue University) on a recent data analysis project where we (i) extracted, cleaned, and stored the data in an easy-to-use JSON format for future studies, and (ii) analyzed the data using a number of graph, hypergraph, and tensor-based data analysis tools.

Here’s a look at the community structure in a network where edges indicate email correspondence. Most clusters in the network include one or more government agency heads and task leaders, who have high centrality scores in the network.

All of our code and derived datasets are accessible on my github page: https://github.com/nveldt/fauci-email

Our manuscript can be viewed as a data manual, and also includes a number of interesting findings from our initial analysis. https://arxiv.org/abs/2108.01239

Paper Published at Science Advances

Posted on by

Our paper Generative hypergraph clustering: from blockmodels to modularity was just published at Science Advances. Joint work with Phil Chodrow and Austin Benson.

Abstract. Hypergraphs are a natural modeling paradigm for networked systems with multiway interactions. A standard task in network analysis is the identification of closely related or densely interconnected nodes. We propose a probabilistic generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. Approximate maximum likelihood inference in this model leads to a clustering objective that generalizes the popular modularity objective for graphs. From this, we derive an inference algorithm that generalizes the Louvain graph community detection method, and a faster, specialized variant in which edges are expected to lie fully within clusters. Using synthetic and empirical data, we demonstrate that the specialized method is highly scalable and can detect clusters where graph-based methods fail. We also use our model to find interpretable higher-order structure in school contact networks, U.S. congressional bill cosponsorship and committees, product categories in copurchasing behavior, and hotel locations from web browsing sessions.

Paper Accepted at KDD 2021

Posted on by

Our paper on The Generalized Mean Densest Subgraph Problem. was accepted to KDD 2021. Join work with Austin Benson and Jon Kleinberg.

The paper covers a generalized framework for dense subgraph detection, that unifies previous objectives such as the k-core problem and the densest subgraph problem. We prove polynomial time algorithms for a certain regime of the problem, as well as faster approximation algorithms based on a generalized “peeling” method.

 

New preprint on Hypergraph Homophily

Posted on by

New preprint: Higher-order Homophily is Combinatorially Impossible! Joint work with Austin Benson and Jon Kleinberg.

Abstract: Homophily is the seemingly ubiquitous tendency for people to connect with similar others, which is fundamental to how society organizes. Even though many social interactions occur in groups, homophily has traditionally been measured from collections of pairwise interactions involving just two individuals. Here, we develop a framework using hypergraphs to quantify homophily from multiway, group interactions. This framework reveals that many homophilous group preferences are impossible; for instance, men and women cannot simultaneously exhibit preferences for groups where their gender is the majority. This is not a human behavior but rather a combinatorial impossibility of hypergraphs. At the same time, our framework reveals relaxed notions of group homophily that appear in numerous contexts. For example, in order for US members of congress to exhibit high preferences for co-sponsoring bills with their own political party, there must also exist a substantial number of individuals from each party that are willing to co-sponsor bills even when their party is in the minority. Our framework also reveals how gender distribution in group pictures varies with group size, a fact that is overlooked when applying graph-based measures.