Chi Wang

Chi Wang

Auto-generated profile, based on publicly available information

Chi Wang

Google DeepMind, Redmond, Washington, USA

Research Focus & Metrics

Academic Career Length

14Years (2013-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 June 2021
Verified
Conference Paper
Open access
JQJiezhong Qiu
Jiezhong Qiu
LDLaxman Dhulipala
Laxman Dhulipala
JTJie Tang
Jie Tang
RPRichard Peng
Richard Peng
CWChi Wang
Chi Wang
We propose LightNE, a cost-effective, scalable, and high quality network embedding system that scales to graphs with hundreds of billions of edges on a single machine. In contrast to the mainstream belief that distributed architecture and GPUs are needed for large-scale network embedding with good quality, we prove that we can achieve higher quality, better scalability, lower cost and faster runtime with shared-memory, CPU-only architecture. LightNE combines two theoretically grounded embedding methods NetSMF and ProNE. We introduce the following techniques to network embedding for the first time: (1) a newly proposed downsampling method to reduce the sample complexity of NetSMF while preserving its theoretical advantages; (2) a high-performance parallel graph processing stack GBBS to achieve high memory efficiency and scalability; (3) sparse parallel hash table to aggregate and maintain the matrix sparsifier in memory; and (4) Intel MKL for efficient randomized SVD and spectral propagation.

1 May 2014
Verified
Conference Paper
Closed access
CWChi Wang
Chi Wang
EJEdmond Jonckheere
Edmond Jonckheere
Todd Andrew BrunTodd Andrew Brun
Todd Andrew Brun
The D-Wave quantum computer is designed to solve a specific class of problems - The Quadratic Unconstrained Binary Optimization (QUBO) problem. One of the key processes in this pathway to the solution consists in embedding the problem graph into a hardware graph. It is a nontrivial task to determine whether a problem graph is minor embeddable in a hardware graph. One method that singles out cases where minor embeddability fails requires calculation of the tree-width of both the problem and the hardware graphs. The latter computation is known to be NP-Complete. In this paper, we propose a novel, fast approximation to tree-width based on the differential geometric concept of Ollivier-Ricci curvature. This latter runs in linear time and thus could significantly reduce the overall complexity of determining whether a QUBO problem is solvable on the D-Wave architecture.

29 May 2024 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
XWXiaoying Wang
Xiaoying Wang
WWWentao Wu
Wentao Wu
CWChi Wang
Chi Wang
VNVivek Narasayya
Vivek Narasayya
SCSurajit Chaudhuri
Surajit Chaudhuri
Index tuning aims to find the optimal index configuration for an input workload. It is often a time-consuming and resource-intensive process, largely attributed to the huge amount of "what-if" calls made to the query optimizer during configuration enumeration. Therefore, in practice it is desirable to set a budget constraint that limits the number of what-if calls allowed. This yields a new problem of budget allocation, namely, deciding on which query-configuration pairs (QCP's) to issue what-if calls. Unfortunately, optimal budget allocation is NP-hard, and budget allocation decisions made by existing solutions can be inferior. In particular, many of the what-if calls allocated by using existing solutions are devoted to QCP's whose what-if costs can be approximated by using cost derivation, a well-known technique that is computationally much more efficient and has been adopted by commercial index tuning software. This results in considerable waste of the budget, as these what-if calls are unnecessary. In this paper, we propose "Wii," a lightweight mechanism that aims to avoid such spurious what-if calls. It can be seamlessly integrated with existing configuration enumeration algorithms. Experimental evaluation on top of both standard industrial benchmarks and real workloads demonstrates that Wii can eliminate significant number of spurious what-if calls. Moreover, by reallocating the saved budget to QCP's where cost derivation is less accurate, existing algorithms can be significantly improved in terms of the final configuration found.

28 October 2024
Verified
Conference Paper
Open access
SZShaokun Zhang
Shaokun Zhang
YWYiran Wu
Yiran Wu
Zhonghua ZhengZhonghua Zheng
Zhonghua Zheng
QWQingyun Wu
Qingyun Wu
CWChi Wang
Chi Wang
In this work, we propose a hyperparameter optimization method named HyperTime to find hyperparameters robust to potential temporal distribution shifts in the unseen test data. Our work is motivated by an important observation that it is, in many cases, possible to achieve temporally robust predictive performance via hyperparameter optimization. Based on this observation, we leverage the 'worst-case-oriented' philosophy from the robust optimization literature to help find such robust hyperparameter configurations. HyperTime imposes a lexicographic priority order on average validation loss and worst-case validation loss over chronological validation sets. We perform a theoretical analysis on the upper bound of the expected test loss, which reveals the unique advantages of our approach. We also demonstrate the strong empirical performance of the proposed method on multiple machine learning tasks with temporal distribution shifts. The algorihtm is available in ~https://microsoft.github.io/FLAML/.

12 September 2023 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
ABAlankrita Bhatt
Alankrita Bhatt
ZWZiao Wang
Ziao Wang
CWChi Wang
Chi Wang
LWLele Wang
Lele Wang
Motivated by the prevalent data science applications of processing large-scale graph data such as social networks and biological networks, this paper investigates lossless compression of data in the form of a labeled graph. Particularly, we consider a widely used random graph model, stochastic block model (SBM), which captures the clustering effects in social networks. An information-theoretic universal compression framework is applied, in which one aims to design a single compressor that achieves the asymptotically optimal compression rate, for every SBM distribution, without knowing the parameters of the SBM. Such a graph compressor is proposed in this paper, which universally achieves the optimal compression rate with polynomial time complexity for a wide class of SBMs. Existing universal compression techniques are developed mostly for stationary ergodic one-dimensional sequences. However, the adjacency matrix of SBM has complex two-dimensional correlations. The challenge is alleviated through a carefully designed transform that converts two-dimensional correlated data into almost i.i.d. submatrices. The sequence of submatrices is then compressed by a Krichevsky–Trofimov compressor, whose length analysis is generalized to identically distributed but arbitrarily correlated sequences. In four benchmark graph datasets, the compressed files from competing algorithms take 2.4 to 27 times the space needed by the proposed scheme.

1 December 2025 in Big Data and Earth System
Verified
Journal Article
Open access
JYJunjie Yu
Junjie Yu
Zhonghua ZhengZhonghua Zheng
Zhonghua Zheng
SLSarah Lindley
Sarah Lindley
LZLei Zhao
Lei Zhao
CWChi Wang
Chi Wang
KOKeith W. Oleson
Keith W. Oleson