Author name cluster

Qizheng He

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.

3 papers

1 author row

ICLR Conference 2023 Conference Paper

Logical Entity Representation in Knowledge-Graphs for Differentiable Rule Learning

Chi Han
Qizheng He
Charles Yu
Xinya Du
Hanghang Tong
Heng Ji 0001

Probabilistic logical rule learning has shown great strength in logical rule mining and knowledge graph completion. It learns logical rules to predict missing edges by reasoning on existing edges in the knowledge graph. However, previous efforts have largely been limited to only modeling chain-like Horn clauses such as R1(x; z) ^ R2(z; y) ) H(x; y). This formulation overlooks additional contextual information from neighboring sub-graphs of entity variables x, y and z. Intuitively, there is a large gap here, as local sub-graphs have been found to provide important information for knowledge graph completion. Inspired by these observations, we propose Logical Entity RePresentation (LERP) to encode contextual information of entities in the knowledge graph. A LERP is designed as a vector of probabilistic logical functions on the entity’s neighboring sub-graph. It is an interpretable representation while allowing for differentiable optimization. We can then incorporate LERP into probabilistic logical rule learning to learn more expressive rules. Empirical results demonstrate that with LERP, our model outperforms other rule learning methods in knowledge graph completion and is comparable or even superior to state-of-the-art black-box methods. Moreover, we find that our model can discover a more expressive family of logical rules. LERP can also be further combined with embedding learning methods like TransE to make it more interpretable.

Details

SODA Conference 2022 Conference Paper

Dynamic Geometric Set Cover, Revisited

Timothy M. Chan
Qizheng He
Subhash Suri
Jie Xue 0003

Geometric set cover is a classical problem in computational geometry, which has been extensively studied in the past. In the dynamic version of the problem, points and ranges may be inserted and deleted, and our goal is to efficiently maintain a set cover solution (satisfying certain quality requirement) for the dynamic problem instance. In this paper, we give a plethora of new dynamic geometric set cover data structures in 1D and 2D, which significantly improve and extend the previous results. Our results include the following: The first data structure for (1 + ∊ )-approximate dynamic interval set cover with polylogarithmic amortized update time. Specifically, we achieve an update time of O (log 3 n/∊ ), improving the O ( n δ / ∊ ) bound of Agarwal et al. [SoCG'20], where δ > 0 denotes an arbitrarily small constant. A data structure for O (1)-approximate dynamic unit-square set cover with amortized update time, substantially improving the O ( n 1/2+ δ ) update time of Agarwal et al. [SoCG'20]. A data structure for O (1)-approximate dynamic square set cover with O ( n 1/2+ δ ) randomized amortized update time, improving the O ( n 2/3+ δ ) update time of Chan and He [SoCG'21]. A data structure for O (1)-approximate dynamic 2D halfplane set cover with O ( n 17/23+ δ ) randomized amortized update time. The previous solution for halfplane set cover by Chan and He [SoCG'21] is slower and can only report the size of the approximate solution. The first sublinear results for the weighted version of dynamic geometric set cover. Specifically, we give a data structure for (3 + o (1))-approximate dynamic weighted interval set cover with amortized update time and a data structure for O (1)-approximate dynamic weighted unit-square set cover with O ( n δ ) amortized update time.

Details

SODA Conference 2018 Conference Paper

The Complexity of Distributed Edge Coloring with Small Palettes

Yi-Jun Chang
Qizheng He
Wenzheng Li
Seth Pettie
Jara Uitto

The complexity of distributed edge coloring depends heavily on the palette size as a function of the maximum degree Δ. In this paper we explore the complexity of edge coloring in the LOCAL model in different palette size regimes. Our results are as follows. • We simplify the round elimination technique of Brandt et al. [9] and prove that (2Δ – 2)-edge coloring requires Ω(log Δ log n ) time w. h. p. and Ω(log Δ n ) time deterministically, even on trees. The simplified technique is based on two ideas: the notion of an irregular running time (in which network components terminate the algorithm at prescribed, but irregular times) and some general observations that transform weak lower bounds into stronger ones. • We give a randomized edge coloring algorithm that can use palette sizes as small as, which is a natural barrier for randomized approaches. The running time of the algorithm is at most O (log Δ · T LLL ), where T LLL is the complexity of a permissive version of the constructive Lovász local lemma. • We develop a new distributed Lovász local lemma algorithm for tree-structured dependency graphs, which leads to a (1 + ∊ )Δ-edge coloring algorithm for trees running in O (log log n ) time. This algorithm arises from two new results: a deterministic O (log n )-time LLL algorithm for tree-structured instances, and a randomized O (log log n )-time graph shattering method for breaking the dependency graph into independent O (log n )-size LLL instances. • A natural approach to computing (Δ + 1)-edge colorings (Vizing's theorem) is to extend partial colorings by iteratively re-coloring parts of the graph, e. g. , via “augmenting paths. ” We prove that this approach may be viable, but in the worst case requires recoloring subgraphs of diameter Ω(Δ log n ). This stands in contrast to distributed algorithms for Brooks’ theorem [32], which exploit the existence of O (log Δ n )-length augmenting paths.

Details