Arrow Research search

Author name cluster

Christian Borgs

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers
2 author rows

Possible papers

19

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

PDF Details

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.

Details

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 )

PDF Details

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.

PDF Details

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.

PDF Details

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.

Details

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

Details

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.

Details