Christian Borgs

NeurIPS Conference 2023 Conference Paper

Symmetry-Informed Geometric Representation for Molecules, Proteins, and Crystalline Materials

• Shengchao Liu
• Weitao Du
• Yanjing Li
• Zhuoxinran Li
• Zhiling Zheng
• Chenru Duan
• Zhi-Ming Ma
• Omar Yaghi

Artificial intelligence for scientific discovery has recently generated significant interest within the machine learning and scientific communities, particularly in the domains of chemistry, biology, and material discovery. For these scientific problems, molecules serve as the fundamental building blocks, and machine learning has emerged as a highly effective and powerful tool for modeling their geometric structures. Nevertheless, due to the rapidly evolving process of the field and the knowledge gap between science ({\eg}, physics, chemistry, & biology) and machine learning communities, a benchmarking study on geometrical representation for such data has not been conducted. To address such an issue, in this paper, we first provide a unified view of the current symmetry-informed geometric methods, classifying them into three main categories: invariance, equivariance with spherical frame basis, and equivariance with vector frame basis. Then we propose a platform, coined Geom3D, which enables benchmarking the effectiveness of geometric strategies. Geom3D contains 16 advanced symmetry-informed geometric representation models and 14 geometric pretraining methods over 52 diverse tasks, including small molecules, proteins, and crystalline materials. We hope that Geom3D can, on the one hand, eliminate barriers for machine learning researchers interested in exploring scientific problems; and, on the other hand, provide valuable guidance for researchers in computational chemistry, structural biology, and materials science, aiding in the informed selection of representation techniques for specific applications. The source code is available on \href{https: //github. com/chao1224/Geom3D}{the GitHub repository}.

SODA Conference 2022 Conference Paper

Algorithms Using Local Graph Features to Predict Epidemics

• Yeganeh Alimohammadi
• Christian Borgs
• Amin Saberi

STOC Conference 2020 Conference Paper

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures

• Christian Borgs
• Jennifer T. Chayes
• Tyler Helmuth
• Will Perkins 0001
• Prasad Tetali

For d ≥ 2 and all q ≥ q 0 ( d ) we give an efficient algorithm to approximately sample from the q -state ferromagnetic Potts and random cluster models on the torus (ℤ / n ℤ ) d for any inverse temperature β≥ 0. This stands in contrast to Markov chain mixing time results: the Glauber dynamics mix slowly at and below the critical temperature, and the Swendsen–Wang dynamics mix slowly at the critical temperature. We also provide an efficient algorithm (an FPRAS) for approximating the partition functions of these models.

FOCS Conference 2018 Conference Paper

Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation

• Christian Borgs
• Jennifer T. Chayes
• Adam Smith 0006
• Ilias Zadik

Motivated by growing concerns over ensuring privacy on social networks, we develop new algorithms and impossibility results for fitting complex statistical models to network data subject to rigorous privacy guarantees. We consider the so-called node-differentially private algorithms, which compute information about a graph or network while provably revealing almost no information about the presence or absence of a particular node in the graph. We provide new algorithms for node-differentially private estimation for a popular and expressive family of network models: stochastic block models and their generalization, graphons. Our algorithms improve on prior work [15], reducing their error quadratically and matching, in many regimes, the optimal nonprivate algorithm [37]. We also show that for the simplest random graph models (G(n, p) and G(n, m)), node-private algorithms can be qualitatively more accurate than for more complex models-converging at a rate of 1/ε 2 n 3 instead of 1/ε 2 n 2. This result uses a new extension lemma for differentially private algorithms that we hope will be broadly useful.

JMLR Journal 2018 Journal Article

Sparse Exchangeable Graphs and Their Limits via Graphon Processes

• Christian Borgs
• Jennifer T. Chayes
• Henry Cohn
• Nina Holden

In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in $\mathbb{R}_+$. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over $\sigma$-finite measure spaces, we can model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a $\sigma$-finite measure space $(S,\mathcal{S},\mu)$ and the connection probabilities by an integrable function $W\colon S\times S\to [0,1]$, we construct a random family $(G_t)_{t\geq 0}$ of growing graphs such that the vertices of $G_t$ are given by a Poisson point process on $S$ with intensity $t\mu$, with two points $x,y$ of the point process connected with probability $W(x,y)$. We call such a random family a graphon process. We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on $\mathbb{R}_+$ equipped with Lebesgue measure. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

NeurIPS Conference 2017 Conference Paper

Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation

• Christian Borgs
• Jennifer Chayes
• Christina Lee
• Devavrat Shah

The sparse matrix estimation problem consists of estimating the distribution of an $n\times n$ matrix $Y$, from a sparsely observed single instance of this matrix where the entries of $Y$ are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filtering-style algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to $0$ at the rate of $O(d^2 (pn)^{-2/5})$ as long as $\omega(d^5 n)$ random entries from a total of $n^2$ entries of $Y$ are observed (uniformly sampled), $\E[Y]$ has rank $d$, and the entries of $Y$ have bounded support. The maximum squared error across all entries converges to $0$ with high probability as long as we observe a little more, $\Omega(d^5 n \ln^5(n))$ entries. Our results are the best known sample complexity results in this generality.

NeurIPS Conference 2015 Conference Paper

Private Graphon Estimation for Sparse Graphs

• Christian Borgs
• Jennifer Chayes
• Adam Smith

We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members. Given a sparse input graph $G$, our algorithms output a node-differentially private nonparametric block model approximation. By node-differentially private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If $G$ is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon $W$, our model guarantees consistency: as the number of vertices tends to infinity, the output of our algorithm converges to $W$ in an appropriate version of the $L_2$ norm. In particular, this means we can estimate the sizes of all multi-way cuts in $G$. Our results hold as long as $W$ is bounded, the average degree of $G$ grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.

SODA Conference 2014 Conference Paper

Maximizing Social Influence in Nearly Optimal Time

• Christian Borgs
• Michael Brautbar
• Jennifer T. Chayes
• Brendan Lucier

Diffusion is a fundamental graph process, underpinning such phenomena as epidemic disease contagion and the spread of innovation by word-of-mouth. We address the algorithmic problem of finding a set of k initial seed nodes in a network so that the expected size of the resulting cascade is maximized, under the standard independent cascade model of network diffusion. Runtime is a primary consideration for this problem due to the massive size of the relevant input networks. We provide a fast algorithm for the influence maximization problem, obtaining the near-optimal approximation factor of, for any ∊ > 0, in time O (( m + n )∊ −3 log n ). Our algorithm is runtime-optimal (up to a logarithmic factor) and substantially improves upon the previously best-known algorithms which run in time Ω( mnk · POLY(∊ −1 )). Furthermore, our algorithm can be modified to allow early termination: if it is terminated after O ( β ( m + n ) log n ) steps for some β < 1 (which can depend on n ), then it returns a solution with approximation factor O ( β ). Finally, we show that this runtime is optimal (up to logarithmic factors) for any β and fixed seed size k.

SODA Conference 2013 Conference Paper

Finding Endogenously Formed Communities

• Maria-Florina Balcan
• Christian Borgs
• Mark Braverman
• Jennifer T. Chayes
• Shang-Hua Teng

SODA Conference 2011 Conference Paper

Fast Convergence of Natural Bargaining Dynamics in Exchange Networks

• Yash Kanoria
• Mohsen Bayati
• Christian Borgs
• Jennifer T. Chayes
• Andrea Montanari

STOC Conference 2008 Conference Paper

The myth of the folk theorem

• Christian Borgs
• Jennifer T. Chayes
• Nicole Immorlica
• Adam Tauman Kalai
• Vahab Mirrokni
• Christos H. Papadimitriou

A well-known result in game theory known as "the Folk Theorem" suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any (approximate) Nash equilibrium for a three-player infinitely-repeated game is computationally intractable (even when all payoffs are in {-1,0,1}), unless all of PPAD can be solved in randomized polynomial time. This is done by showing that finding Nash equilibria of (k+1)-player infinitely-repeated games is as hard as finding Nash equilibria of k-player one-shot games, for which PPAD-hardness is known (Daskalakis, Goldberg and Papadimitriou, 2006; Chen, Deng and Teng, 2006; Chen, Teng and Valiant, 2007). This also explains why no computationally-efficient learning dynamics, such as the "no regret" algorithms, can be "rational" (in general games with three or more players) in the sense that, when one's opponents use such a strategy, it is not in general a best reply to follow suit.

TCS Journal 2007 Journal Article

Degree distribution of the FKP network model

• Noam Berger
• Béla Bollobás
• Christian Borgs
• Jennifer Chayes
• Oliver Riordan

Power laws, in particular power-law degree distributions, have been observed in real-world networks in a very wide range of contexts, including social networks, biological networks, and artificial networks such as the physical internet or abstract world wide web. Recently, these observations have triggered much work attempting to explain the power laws in terms of new ‘scale-free’ random graph models. So far, perhaps the most effective mechanism for explaining power laws is the combination of growth and preferential attachment. In [A. Fabrikant, E. Koutsoupias, C. H. Papadimitriou, Heuristically optimized trade-offs: A new paradigm for power laws in the internet ICALP 2002, in: LNCS, vol. 2380, pp. 110–122], Fabrikant, Koutsoupias and Papadimitriou propose a new ‘paradigm’ for explaining power laws, based on trade-offs between competing objectives. They also introduce a new, simple and elegant parametrized model for the internet, and prove some kind of power-law bound on the degree sequence for a wide range of scalings of the trade-off parameter. Here we shall show that this model does not have the usual kind of power-law degree distribution observed in the real world: for the most interesting range of the parameter, neither the bulk of the nodes, nor the few highest degree nodes have degrees following a power law. We shall show that almost all nodes have degree 1, and that there is a strong bunching of degrees near the maximum.

STOC Conference 2007 Conference Paper

First to market is not everything: an analysis of preferential attachment with fitness

• Christian Borgs
• Jennifer T. Chayes
• Constantinos Daskalakis
• Sébastien Roch

The design of algorithms on complex networks, such as routing, ranking or recommendation algorithms, requires a detailed understanding of the growth characteristics of the networks of interest, such as the Internet,the web graph, social networks or online communities. To this end, preferential attachment, in which the popularity (or relevance) of a node is determined by its degree, is a well-known and appealing random graph model, whose predictions are in accordance with experiments on the web graph and several social networks. However, its central assumption, that the popularity of the nodes dependsonly on their degree, is not a realistic one, since every node has potentially some intrinsic quality which can differentiate its attractiveness from other nodes with similar degrees.

STOC Conference 2006 Conference Paper

Graph limits and parameter testing

• Christian Borgs
• Jennifer T. Chayes
• László Lovász 0001
• Vera T. Sós
• Balázs Szegedy
• Katalin Vesztergombi

FOCS Conference 2006 Conference Paper

The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels

• Christian Borgs
• Jennifer T. Chayes
• Elchanan Mossel
• Sébastien Roch

We establish the exact threshold for the reconstruction problem for a binary asymmetric channel on the b-ary tree, provided that the asymmetry is sufficiently small. This is the first exact reconstruction threshold obtained in roughly a decade. We discuss the implications of our result for Glauber dynamics, phylogenetic reconstruction, noisy communication and the so-called "replica symmetry breaking" in spin glasses and random satisfiability problems

SODA Conference 2005 Conference Paper

On the spread of viruses on the internet

• Noam Berger
• Christian Borgs
• Jennifer T. Chayes
• Amin Saberi

SODA Conference 2003 Conference Paper

Directed scale-free graphs

• Béla Bollobás
• Christian Borgs
• Jennifer T. Chayes
• Oliver Riordan

STOC Conference 2001 Conference Paper

Sharp threshold and scaling window for the integer partitioning problem

• Christian Borgs
• Jennifer T. Chayes
• Boris G. Pittel

FOCS Conference 1999 Conference Paper

Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics

• Christian Borgs
• Jennifer T. Chayes
• Alan M. Frieze
• Jeong Han Kim
• Prasad Tetali
• Eric Vigoda
• Van H. Vu

Studies two widely used algorithms, Glauber dynamics and the Swendsen-Wang (1987) algorithm, on rectangular subsets of the hypercubic lattice Z/sup d/. We prove that, under certain circumstances, the mixing time in a box of side length L with periodic boundary conditions can be exponential in L/sup d-1/. In other words, under these circumstances, the mixing in these widely used algorithms is not rapid; instead it is torpid. The models we study are the independent set model and the q-state Potts model. For both models, we prove that Glauber dynamics is torpid in the region with phase coexistence. For the Potts model, we prove that the Swendsen-Wang mixing is torpid at the phase transition point.