Yixin Chen

TAAS Journal 2025 Journal Article

Combining Personalized Federated Hypernetworks and Shared Residual Learning for Distributed QoS Prediction

• Guobing Zou
• Shiyi Lin
• Shaogang Wu
• Shengxiang Hu
• Song Yang
• Yanglan Gan
• Bofeng Zhang
• Yixin Chen

Connected vehicles due to the high mobility and dynamic network topologies of connected vehicles require accurate QoS that includes high throughput and low latency to assess satisfactory QoE. Existing methods mainly focus on centralized QoS prediction while paying little attention to distributed mobile QoS prediction, making it challenging to protect user privacy information when invoking Web services. Moreover, even though some advanced centralized methods can be transformed into federated architectures, they often face difficulty in capturing latent feature representations of users and services and learning personalized prediction layers between them due to the heterogeneity of the QoS dataset. To address the above issues, we propose a novel framework for distributed QoS prediction, called Combining Personalized Federated Hypernetworks and Shared Residual Learning for Distributed QoS Prediction (FHR-DQP). FHR-DQP adopts the federated averaging (FedAvg) to aggregate location-aware residual shared feature information across all clients. Additionally, a hypernetwork is leveraged to generate personalized networks for user-service QoS prediction in each client. These components are integrated as a hybrid framework that performs training using a federated approach and makes personalized QoS predictions within each client. Extensive experiments are conducted on a real-world benchmark QoS dataset called WS-DREAM, containing nearly 2,000,000 historical QoS invocation records. Compared with both centralized and federated competing baselines, the results demonstrate that FHR-DQP achieves the highest performance for distributed QoS prediction, when it provides privacy-preserving of users’ QoS invocations.

ICLR Conference 2025 Conference Paper

GOFA: A Generative One-For-All Model for Joint Graph Language Modeling

• Lecheng Kong
• Jiarui Feng
• Hao Liu 0057
• Chengsong Huang
• Jiaxin Huang 0001
• Yixin Chen
• Muhan Zhang

Foundation models, such as Large Language Models (LLMs) or Large Vision Models (LVMs), have emerged as one of the most powerful tools in the respective fields. However, unlike text and image data, graph data do not have a definitive structure, posing great challenges to developing a Graph Foundation Model (GFM). For example, current attempts at designing general graph models either transform graph data into a language format for LLM-based prediction or still train a GNN model with LLM as an assistant. The former can handle unlimited tasks, while the latter captures graph structure much better---yet, no existing work can achieve both simultaneously. In this paper, we first identify three key desirable properties of a GFM: self-supervised pretraining, fluidity in tasks, and graph awareness. To account for these properties, we extend the conventional language modeling to the graph domain and propose a novel generative graph language model GOFA. The model interleaves randomly initialized GNN layers into a frozen pre-trained LLM so that the semantic and structural modeling abilities are organically combined. GOFA is pre-trained on newly proposed graph-level next-word prediction, question-answering, structural understanding, and information retrieval tasks to obtain the above GFM properties. The pre-trained model is further instruction fine-tuned to obtain the task-solving ability. Our GOFA model is evaluated on various downstream datasets unseen during the pre-training and fine-tuning phases, demonstrating a strong ability to solve structural and contextual problems in zero-shot scenarios. The code is available at https://github.com/JiaruiFeng/GOFA.

TMLR Journal 2025 Journal Article

Graph Theory-Based Deep Graph Similarity Learning: A Unified Survey of Pipeline, Techniques, and Challenges

• Zhouyang LIU
• Ning Liu
• Yixin Chen
• Ziqing Wen
• Jiezhong He
• Dongsheng Li

Graph similarity computation, which measures the resemblance between graphs, is a crucial operation in fields such as graph search. Recent advances in graph neural networks have enabled the embedding of graphs into low-dimensional vector spaces, where the sim- ilarity or distance between graphs can be efficiently quantified. However, these methods are often tailored to specific tasks and function as black boxes, limiting both generalization and interpretability. To address these challenges, there is growing interest in incorporating domain-agnostic and interpretable concepts from graph theory—such as subgraph isomorphism, maximum common subgraph, and graph edit distance—into graph similarity learning as training objectives. This survey presents a comprehensive review of recent advancements in deep graph similarity learning, focusing on models that integrate these graph theory concepts. Despite the different training objectives of these approaches, they share significant commonalities in the training pipeline, techniques, and challenges. We analyze them within a unified lens referred to as graph theory-based deep similarity learning (GTDGSL) methods. We systematically compare existing GTDGSL methods alongside their common training pipeline, highlighting the technique trend and discussing key challenges, applications, and future research directions in this domain. We organize the papers included in this survey and their open-source implementations at https://github.com/liuzhouyang/Graph-Theory-Based-Deep-Graph-Similarity-Learning-Survey.

AAAI Conference 2025 Conference Paper

Large Language Model Meets Graph Neural Network in Knowledge Distillation

• Shengxiang Hu
• Guobing Zou
• Song Yang
• Shiyi Lin
• Yanglan Gan
• Bofeng Zhang
• Yixin Chen

While Large Language Models (LLMs) show promise for Text-Attributed Graphs (TAGs) learning, their deployment is hindered by computational demands. Graph Neural Networks (GNNs) are efficient but struggle with TAGs' complex semantics. We propose LinguGKD, a novel LLM-to-GNN knowledge distillation framework that enables transferring both local semantic details and global structural information from LLMs to GNNs. First, it introduces TAG-oriented instruction tuning, enhancing LLMs with graph-specific knowledge through carefully designed prompts. Next, it develops a layer-adaptive multi-scale contrastive distillation strategy aligning LLM and GNN features at multiple granularities, from node-level to graph-level. Finally, the distilled GNNs combine the semantic richness of LLMs with the computational efficiency of traditional GNNs. Experiments demonstrate that LinguGKD outperforms existing graph distillation frameworks, the distilled simple GNNs achieve comparable or superior performance to more complex GNNs and teacher LLMs, while maintaining computational efficiency. This work bridges the gap between LLMs and GNNs, facilitating advanced graph learning in resource-constrained environments and providing a framework to leverage ongoing LLM advancements for GNN improvement.

NeurIPS Conference 2024 Conference Paper

Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization

• Yixin Chen
• Ankur Nath
• Chunli Peng
• Alan Kuhnle

For constrained, not necessarily monotone submodular maximization, all known approximation algorithms with ratio greater than $1/e$ require continuous ideas, such as queries to the multilinear extension of a submodular function and its gradient, which are typically expensive to simulate with the original set function. For combinatorial algorithms, the best known approximation ratios for both size and matroid constraint are obtained by a simple randomized greedy algorithm of Buchbinder et al. [9]: $1/e \approx 0. 367$ for size constraint and $0. 281$ for the matroid constraint in $\mathcal O (kn)$ queries, where $k$ is the rank of the matroid. In this work, we develop the first combinatorial algorithms to break the $1/e$ barrier: we obtain approximation ratio of $0. 385$ in $\mathcal O (kn)$ queries to the submodular set function for size constraint, and $0. 305$ for a general matroid constraint. These are achieved by guiding the randomized greedy algorithm with a fast local search algorithm. Further, we develop deterministic versions of these algorithms, maintaining the same ratio and asymptotic time complexity. Finally, we develop a deterministic, nearly linear time algorithm with ratio $0. 377$.

NeurIPS Conference 2024 Conference Paper

PhyRecon: Physically Plausible Neural Scene Reconstruction

• Junfeng Ni
• Yixin Chen
• Bohan Jing
• Nan Jiang
• Bin Wang
• Bo Dai
• Puhao Li
• Yixin Zhu

We address the issue of physical implausibility in multi-view neural reconstruction. While implicit representations have gained popularity in multi-view 3D reconstruction, previous work struggles to yield physically plausible results, limiting their utility in domains requiring rigorous physical accuracy. This lack of plausibility stems from the absence of physics modeling in existing methods and their inability to recover intricate geometrical structures. In this paper, we introduce PHYRECON, the first approach to leverage both differentiable rendering and differentiable physics simulation to learn implicit surface representations. PHYRECON features a novel differentiable particle-based physical simulator built on neural implicit representations. Central to this design is an efficient transformation between SDF-based implicit representations and explicit surface points via our proposed Surface Points Marching Cubes (SP-MC), enabling differentiable learning with both rendering and physical losses. Additionally, PHYRECON models both rendering and physical uncertainty to identify and compensate for inconsistent and inaccurate monocular geometric priors. The physical uncertainty further facilitates physics-guided pixel sampling to enhance the learning of slender structures. By integrating these techniques, our model supports differentiable joint modeling of appearance, geometry, and physics. Extensive experiments demonstrate that PHYRECON significantly improves the reconstruction quality. Our results also exhibit superior physical stability in physical simulators, with at least a 40% improvement across all datasets, paving the way for future physics-based applications.

JAIR Journal 2024 Journal Article

Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint

• Yixin Chen
• Alan Kuhnle

We present combinatorial and parallelizable algorithms for the maximization of a submodular function, not necessarily monotone, with respect to a size constraint. We improve the best approximation factor achieved by an algorithm that has optimal adaptivity and nearly optimal query complexity to 1/6 − ε, and even further to 0.193 − ε by increasing the adaptivity by a factor of O(log(k)). The conference version of this work mistakenly employed a subroutine that does not work for non-monotone, submodular functions. In this version, we propose a fixed and improved subroutine to add a set with high average marginal gain, ThreshSeq, which returns a solution in O(log(n)) adaptive rounds with high probability. Moreover, we provide two approximation algorithms. The first has approximation ratio 1/6 − ε, adaptivity O(log(n)), and query complexity O(n log(k)), while the second has approximation ratio 0.193 − ε, adaptivity O(log(n) log(k)), and query complexity O(n log(k)). Our algorithms are empirically validated to use a low number of adaptive rounds and total queries while obtaining solutions with high objective value in comparison with state-of-the-art approximation algorithms, including continuous algorithms that use the multilinear extension.

JAIR Journal 2024 Journal Article

Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models

• Yixin Chen
• Tonmoy Dey
• Alan Kuhnle

Distributed maximization of a submodular function in the MapReduce (MR) model has received much attention, culminating in two frameworks that allow a centralized algorithm to be run in the MR setting without loss of approximation, as long as the centralized algorithm satisfies a certain consistency property – which had previously only been known to be satisfied by the standard greedy and continous greedy algorithms. A separate line of work has studied parallelizability of submodular maximization in the adaptive complexity model, where each thread may have access to the entire ground set. For the size-constrained maximization of a monotone and submodular function, we show that several sublinearly adaptive (highly parallelizable) algorithms satisfy the consistency property required to work in the MR setting, which yields practical, parallelizable and distributed algorithms. Separately, we develop the first distributed algorithm with linear query complexity for this problem. Finally, we provide a method to increase the maximum cardinality constraint for MR algorithms at the cost of additional MR rounds.

TMLR Journal 2023 Journal Article

A Modulation Layer to Increase Neural Network Robustness Against Data Quality Issues

• Mohamed Abdelhack
• Jiaming Zhang
• Sandhya Tripathi
• Bradley A Fritz
• Daniel Felsky
• Michael Avidan
• Yixin Chen
• Christopher Ryan King

Data missingness and quality are common problems in machine learning, especially for high-stakes applications such as healthcare. Developers often train machine learning models on carefully curated datasets using only high-quality data; however, this reduces the utility of such models in production environments. We propose a novel neural network modification to mitigate the impacts of low-quality and missing data which involves replacing the fixed weights of a fully-connected layer with a function of additional input. This is inspired by neuromodulation in biological neural networks where the cortex can up- and down-regulate inputs based on their reliability and the presence of other data. In testing, with reliability scores as a modulating signal, models with modulating layers were found to be more robust against data quality degradation, including additional missingness. These models are superior to imputation as they save on training time by entirely skipping the imputation process and further allow the introduction of other data quality measures that imputation cannot handle. Our results suggest that explicitly accounting for reduced information quality with a modulating fully connected layer can enable the deployment of artificial intelligence systems in real-time applications.

AAAI Conference 2023 Conference Paper

DASH: A Distributed and Parallelizable Algorithm for Size-Constrained Submodular Maximization

• Tonmoy Dey
• Yixin Chen
• Alan Kuhnle

MapReduce (MR) algorithms for maximizing monotone, submodular functions subject to a cardinality constraint (SMCC) are currently restricted to the use of the linear-adaptive (non-parallelizable) algorithm GREEDY. Low-adaptive algorithms do not satisfy the requirements of these distributed MR frameworks, thereby limiting their performance. We study the SMCC problem in a distributed setting and propose the first MR algorithms with sublinear adaptive complexity. Our algorithms, R-DASH, T-DASH and G-DASH provide 0.316 - ε, 3/8 - ε, and (1 - 1/e - ε) approximation ratios, respectively, with nearly optimal adaptive complexity and nearly linear time complexity. Additionally, we provide a framework to increase, under some mild assumptions, the maximum permissible cardinality constraint from O( n / ℓ^2) of prior MR algorithms to O( n / ℓ ), where n is the data size and ℓ is the number of machines; under a stronger condition on the objective function, we increase the maximum constraint value to n. Finally, we provide empirical evidence to demonstrate that our sublinear-adaptive, distributed algorithms provide orders of magnitude faster runtime compared to current state-of-the-art distributed algorithms.

NeurIPS Conference 2023 Conference Paper

Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman

• Jiarui Feng
• Lecheng Kong
• Hao Liu
• Dacheng Tao
• Fuhai Li
• Muhan Zhang
• Yixin Chen

Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Some works are inspired by $k$-WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) $k$-WL/FWL requires at least $O(n^k)$ space complexity, which is impractical for large graphs even when $k=3$; (2) The design space of $k$-WL/FWL is rigid, with the only adjustable hyper-parameter being $k$. To tackle the first limitation, we propose an extension, $(k, t)$-FWL. We theoretically prove that even if we fix the space complexity to $O(n^k)$ (for any $k \geq 2$) in $(k, t)$-FWL, we can construct an expressiveness hierarchy up to solving the graph isomorphism problem. To tackle the second problem, we propose $k$-FWL+, which considers any equivariant set as neighbors instead of all nodes, thereby greatly expanding the design space of $k$-FWL. Combining these two modifications results in a flexible and powerful framework $(k, t)$-FWL+. We demonstrate $(k, t)$-FWL+ can implement most existing models with matching expressiveness. We then introduce an instance of $(k, t)$-FWL+ called Neighborhood$^2$-FWL (N$^2$-FWL), which is practically and theoretically sound. We prove that N$^2$-FWL is no less powerful than 3-WL, and can encode many substructures while only requiring $O(n^2)$ space. Finally, we design its neural version named **N$^2$-GNN** and evaluate its performance on various tasks. N$^2$-GNN achieves record-breaking results on ZINC-Subset (**0. 059**), outperforming previous SOTA results by 10. 6\%. Moreover, N$^2$-GNN achieves new SOTA results on the BREC dataset (**71. 8\%**) among all existing high-expressive GNN methods.

IJCAI Conference 2023 Conference Paper

Improving Heterogeneous Model Reuse by Density Estimation

• Anke Tang
• Yong Luo
• Han Hu
• Fengxiang He
• Kehua Su
• Bo Du
• Yixin Chen
• Dacheng Tao

This paper studies multiparty learning, aiming to learn a model using the private data of different participants. Model reuse is a promising solution for multiparty learning, assuming that a local model has been trained for each party. Considering the potential sample selection bias among different parties, some heterogeneous model reuse approaches have been developed. However, although pre-trained local classifiers are utilized in these approaches, the characteristics of the local data are not well exploited. This motivates us to estimate the density of local data and design an auxiliary model together with the local classifiers for reuse. To address the scenarios where some local models are not well pre-trained, we further design a multiparty cross-entropy loss for calibration. Upon existing works, we address a challenging problem of heterogeneous model reuse from a decision theory perspective and take advantage of recent advances in density estimation. Experimental results on both synthetic and benchmark data demonstrate the superiority of the proposed method.

AAAI Conference 2023 Conference Paper

Learning Context-Aware Classifier for Semantic Segmentation

• Zhuotao Tian
• Jiequan Cui
• Li Jiang
• Xiaojuan Qi
• Xin Lai
• Yixin Chen
• Shu Liu
• Jiaya Jia

Semantic segmentation is still a challenging task for parsing diverse contexts in different scenes, thus the fixed classifier might not be able to well address varying feature distributions during testing. Different from the mainstream literature where the efficacy of strong backbones and effective decoder heads has been well studied, in this paper, additional contextual hints are instead exploited via learning a context-aware classifier whose content is data-conditioned, decently adapting to different latent distributions. Since only the classifier is dynamically altered, our method is model-agnostic and can be easily applied to generic segmentation models. Notably, with only negligible additional parameters and +2\% inference time, decent performance gain has been achieved on both small and large models with challenging benchmarks, manifesting substantial practical merits brought by our simple yet effective method. The implementation is available at https://github.com/tianzhuotao/CAC.

NeurIPS Conference 2023 Conference Paper

MAG-GNN: Reinforcement Learning Boosted Graph Neural Network

• Lecheng Kong
• Jiarui Feng
• Hao Liu
• Dacheng Tao
• Yixin Chen
• Muhan Zhang

While Graph Neural Networks (GNNs) recently became powerful tools in graph learning tasks, considerable efforts have been spent on improving GNNs' structural encoding ability. A particular line of work proposed subgraph GNNs that use subgraph information to improve GNNs' expressivity and achieved great success. However, such effectivity sacrifices the efficiency of GNNs by enumerating all possible subgraphs. In this paper, we analyze the necessity of complete subgraph enumeration and show that a model can achieve a comparable level of expressivity by considering a small subset of the subgraphs. We then formulate the identification of the optimal subset as a combinatorial optimization problem and propose Magnetic Graph Neural Network (MAG-GNN), a reinforcement learning (RL) boosted GNN, to solve the problem. Starting with a candidate subgraph set, MAG-GNN employs an RL agent to iteratively update the subgraphs to locate the most expressive set for prediction. This reduces the exponential complexity of subgraph enumeration to the constant complexity of a subgraph search algorithm while keeping good expressivity. We conduct extensive experiments on many datasets, showing that MAG-GNN achieves competitive performance to state-of-the-art methods and even outperforms many subgraph GNNs. We also demonstrate that MAG-GNN effectively reduces the running time of subgraph GNNs.

NeurIPS Conference 2023 Conference Paper

Retrieval-Augmented Multiple Instance Learning

• Yufei Cui
• Ziquan Liu
• Yixin Chen
• Yuchen Lu
• Xinyue Yu
• Xue (Steve) Liu
• Tei-Wei Kuo
• Miguel Rodrigues

Multiple Instance Learning (MIL) is a crucial weakly supervised learning method applied across various domains, e. g. , medical diagnosis based on whole slide images (WSIs). Recent advancements in MIL algorithms have yielded exceptional performance when the training and test data originate from the same domain, such as WSIs obtained from the same hospital. However, this paper reveals a performance deterioration of MIL models when tested on an out-of-domain test set, exemplified by WSIs sourced from a novel hospital. To address this challenge, this paper introduces the Retrieval-AugMented MIL (RAM-MIL) framework, which integrates Optimal Transport (OT) as the distance metric for nearest neighbor retrieval. The development of RAM-MIL is driven by two key insights. First, a theoretical discovery indicates that reducing the input's intrinsic dimension can minimize the approximation error in attention-based MIL. Second, previous studies highlight a link between input intrinsic dimension and the feature merging process with the retrieved data. Empirical evaluations conducted on WSI classification demonstrate that the proposed RAM-MIL framework achieves state-of-the-art performance in both in-domain scenarios, where the training and retrieval data are in the same domain, and more crucially, in out-of-domain scenarios, where the (unlabeled) retrieval data originates from a different domain. Furthermore, the use of the transportation matrix derived from OT renders the retrieval results interpretable at the instance level, in contrast to the vanilla $l_2$ distance, and allows for visualization for human experts. *Code can be found at \url{https: //github. com/ralphc1212/ram-mil*.

EAAI Journal 2023 Journal Article

Ultimate bearing capacity prediction method and sensitivity analysis of PBL

• Yixin Chen
• Yanke Huang
• Hao Liu
• Yongsheng Liu
• Ting Zhang

AIIM Journal 2022 Journal Article

Boosting lesion annotation via aggregating explicit relations in external medical knowledge graph

• Yixin Chen
• Xianbing Zhao
• Buzhou Tang

Predicting a comprehensive set of relevant labels on chest X-ray images faces great challenges towards bridging visual and textual modalities. Despite the success of Graph Convolutional Networks (GCN) on modeling label dependencies using co-occurrence matrix generated from dataset, they still suffer from inherent label imbalance in dataset and ignore the explicit relations among labels presented in external medical knowledge graph (KG). We argue that jointly exploiting both the label co-occurrence matrix in dataset and the label relations in external knowledge graph facilitates multi-label lesion annotation. To model relevant lesion labels more comprehensively, we propose a KG-augmented model via Aggregating Explicit Relations for multi-label lesion annotation, called AER-GCN. The KG-augmented model employs GCN to learn the explicit label relations in external medical KG, and aggregates the explicit relations into statistical graph built from label co-occurrence information. Specially, we present three approaches on modeling the explicit label correlations in external knowledge, and two approaches on incorporating the explicit relations into co-occurrence relations for lesion annotation. We exploit SNOMED CT as the source of external knowledge and evaluate the performance of AER-GCN on the ChestX-ray and IU X-ray datasets. Extensive experiments demonstrate that our model outperforms other state-of-the-art models.

NeurIPS Conference 2022 Conference Paper

Geodesic Graph Neural Network for Efficient Graph Representation Learning

• Lecheng Kong
• Yixin Chen
• Muhan Zhang

Graph Neural Networks (GNNs) have recently been applied to graph learning tasks and achieved state-of-the-art (SOTA) results. However, many competitive methods run GNNs multiple times with subgraph extraction and customized labeling to capture information that is hard for normal GNNs to learn. Such operations are time-consuming and do not scale to large graphs. In this paper, we propose an efficient GNN framework called Geodesic GNN (GDGNN) that requires only one GNN run and injects conditional relationships between nodes into the model without labeling. This strategy effectively reduces the runtime of subgraph methods. Specifically, we view the shortest paths between two nodes as the spatial graph context of the neighborhood around them. The GNN embeddings of nodes on the shortest paths are used to generate geodesic representations. Conditioned on the geodesic representations, GDGNN can generate node, link, and graph representations that carry much richer structural information than plain GNNs. We theoretically prove that GDGNN is more powerful than plain GNNs. We present experimental results to show that GDGNN achieves highly competitive performance with SOTA GNN models on various graph learning tasks while taking significantly less time.

NeurIPS Conference 2022 Conference Paper

How Powerful are K-hop Message Passing Graph Neural Networks

• Jiarui Feng
• Yixin Chen
• Fuhai Li
• Anindya Sarkar
• Muhan Zhang

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing---aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by the Weisfeiler-Lehman (1-WL) test. Recently, researchers extended 1-hop message passing to $K$-hop message passing by aggregating information from $K$-hop neighbors of nodes simultaneously. However, there is no work on analyzing the expressive power of $K$-hop message passing. In this work, we theoretically characterize the expressive power of $K$-hop message passing. Specifically, we first formally differentiate two different kernels of $K$-hop message passing which are often misused in previous works. We then characterize the expressive power of $K$-hop message passing by showing that it is more powerful than 1-WL and can distinguish almost all regular graphs. Despite the higher expressive power, we show that $K$-hop message passing still cannot distinguish some simple regular graphs and its expressive power is bounded by 3-WL. To further enhance its expressive power, we introduce a KP-GNN framework, which improves $K$-hop message passing by leveraging the peripheral subgraph information in each hop. We show that KP-GNN can distinguish many distance regular graphs which could not be distinguished by previous distance encoding or 3-WL methods. Experimental results verify the expressive power and effectiveness of KP-GNN. KP-GNN achieves competitive results across all benchmark datasets.

NeurIPS Conference 2022 Conference Paper

HUMANISE: Language-conditioned Human Motion Generation in 3D Scenes

• Zan Wang
• Yixin Chen
• Tengyu Liu
• Yixin Zhu
• Wei Liang
• Siyuan Huang

Learning to generate diverse scene-aware and goal-oriented human motions in 3D scenes remains challenging due to the mediocre characters of the existing datasets on Human-Scene Interaction (HSI); they only have limited scale/quality and lack semantics. To fill in the gap, we propose a large-scale and semantic-rich synthetic HSI dataset, denoted as HUMANISE, by aligning the captured human motion sequences with various 3D indoor scenes. We automatically annotate the aligned motions with language descriptions that depict the action and the individual interacting objects; e. g. , sit on the armchair near the desk. HUMANIZE thus enables a new generation task, language-conditioned human motion generation in 3D scenes. The proposed task is challenging as it requires joint modeling of the 3D scene, human motion, and natural language. To tackle this task, we present a novel scene-and-language conditioned generative model that can produce 3D human motions of the desirable action interacting with the specified objects. Our experiments demonstrate that our model generates diverse and semantically consistent human motions in 3D scenes.

NeurIPS Conference 2021 Conference Paper

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel

• Yixin Chen
• Tonmoy Dey
• Alan Kuhnle

For the problem of maximizing a monotone, submodular function with respect to a cardinality constraint $k$ on a ground set of size $n$, we provide an algorithm that achieves the state-of-the-art in both its empirical performance and its theoretical properties, in terms of adaptive complexity, query complexity, and approximation ratio; that is, it obtains, with high probability, query complexity of $O(n)$ in expectation, adaptivity of $O(\log(n))$, and approximation ratio of nearly $1-1/e$. The main algorithm is assembled from two components which may be of independent interest. The first component of our algorithm, LINEARSEQ, is useful as a preprocessing algorithm to improve the query complexity of many algorithms. Moreover, a variant of LINEARSEQ is shown to have adaptive complexity of $O( \log (n / k) )$ which is smaller than that of any previous algorithm in the literature. The second component is a parallelizable thresholding procedure THRESHOLDSEQ for adding elements with gain above a constant threshold. Finally, we demonstrate that our main algorithm empirically outperforms, in terms of runtime, adaptive rounds, total queries, and objective values, the previous state-of-the-art algorithm FAST in a comprehensive evaluation with six submodular objective functions.

NeurIPS Conference 2019 Conference Paper

D-VAE: A Variational Autoencoder for Directed Acyclic Graphs

• Muhan Zhang
• Shali Jiang
• Zhicheng Cui
• Roman Garnett
• Yixin Chen

Graph structured data are abundant in the real world. Among different graph types, directed acyclic graphs (DAGs) are of particular interest to machine learning researchers, as many machine learning models are realized as computations on DAGs, including neural networks and Bayesian networks. In this paper, we study deep generative models for DAGs, and propose a novel DAG variational autoencoder (D-VAE). To encode DAGs into the latent space, we leverage graph neural networks. We propose an asynchronous message passing scheme that allows encoding the computations on DAGs, rather than using existing simultaneous message passing schemes to encode local graph structures. We demonstrate the effectiveness of our proposed DVAE through two tasks: neural architecture search and Bayesian network structure learning. Experiments show that our model not only generates novel and valid DAGs, but also produces a smooth latent space that facilitates searching for DAGs with better performance through Bayesian optimization.

NeurIPS Conference 2019 Conference Paper

Deep Model Transferability from Attribution Maps

• Jie Song
• Yixin Chen
• Xinchao Wang
• Chengchao Shen
• Mingli Song

Exploring the transferability between heterogeneous tasks sheds light on their intrinsic interconnections, and consequently enables knowledge transfer from one task to another so as to reduce the training effort of the latter. In this paper, we propose an embarrassingly simple yet very efficacious approach to estimating the transferability of deep networks, especially those handling vision tasks. Unlike the seminal work of \emph{taskonomy} that relies on a large number of annotations as supervision and is thus computationally cumbersome, the proposed approach requires no human annotations and imposes no constraints on the architectures of the networks. This is achieved, specifically, via projecting deep networks into a \emph{model space}, wherein each network is treated as a point and the distances between two points are measured by deviations of their produced attribution maps. The proposed approach is several-magnitude times faster than taskonomy, and meanwhile preserves a task-wise topological structure highly similar to the one obtained by taskonomy. Code is available at \url{https: //github. com/zju-vipa/TransferbilityFromAttributionMaps}.

NeurIPS Conference 2019 Conference Paper

PerspectiveNet: 3D Object Detection from a Single RGB Image via Perspective Points

• Siyuan Huang
• Yixin Chen
• Tao Yuan
• Siyuan Qi
• Yixin Zhu
• Song-Chun Zhu

Detecting 3D objects from a single RGB image is intrinsically ambiguous, thus requiring appropriate prior knowledge and intermediate representations as constraints to reduce the uncertainties and improve the consistencies between the 2D image plane and the 3D world coordinate. To address this challenge, we propose to adopt perspective points as a new intermediate representation for 3D object detection, defined as the 2D projections of local Manhattan 3D keypoints to locate an object; these perspective points satisfy geometric constraints imposed by the perspective projection. We further devise PerspectiveNet, an end-to-end trainable model that simultaneously detects the 2D bounding box, 2D perspective points, and 3D object bounding box for each object from a single RGB image. PerspectiveNet yields three unique advantages: (i) 3D object bounding boxes are estimated based on perspective points, bridging the gap between 2D and 3D bounding boxes without the need of category-specific 3D shape priors. (ii) It predicts the perspective points by a template-based method, and a perspective loss is formulated to maintain the perspective constraints. (iii) It maintains the consistency between the 2D perspective points and 3D bounding boxes via a differentiable projective function. Experiments on SUN RGB-D dataset show that the proposed method significantly outperforms existing RGB-based approaches for 3D object detection.

AAAI Conference 2018 Conference Paper

An End-to-End Deep Learning Architecture for Graph Classification

• Muhan Zhang
• Zhicheng Cui
• Marion Neumann
• Yixin Chen

Neural networks are typically designed to deal with data in tensor forms. In this paper, we propose a novel neural network architecture accepting graphs of arbitrary structure. Given a dataset containing graphs in the form of (G, y) where G is a graph and y is its class, we aim to develop neural networks that read the graphs directly and learn a classification function. There are two main challenges: 1) how to extract useful features characterizing the rich information encoded in a graph for classification purpose, and 2) how to sequentially read a graph in a meaningful and consistent order. To address the first challenge, we design a localized graph convolution model and show its connection with two graph kernels. To address the second challenge, we design a novel SortPooling layer which sorts graph vertices in a consistent order so that traditional neural networks can be trained on the graphs. Experiments on benchmark graph classification datasets demonstrate that the proposed architecture achieves highly competitive performance with state-of-the-art graph kernels and other graph neural network methods. Moreover, the architecture allows end-to-end gradient-based training with original graphs, without the need to first transform graphs into vectors.

AAAI Conference 2018 Conference Paper

Beyond Link Prediction: Predicting Hyperlinks in Adjacency Space

• Muhan Zhang
• Zhicheng Cui
• Shali Jiang
• Yixin Chen

This paper addresses the hyperlink prediction problem in hypernetworks. Different from the traditional link prediction problem where only pairwise relations are considered as links, our task here is to predict the linkage of multiple nodes, i. e. , hyperlink. Each hyperlink is a set of an arbitrary number of nodes which together form a multiway relationship. Hyperlink prediction is challenging – since the cardinality of a hyperlink is variable, existing classifiers based on a fixed number of input features become infeasible. Heuristic methods, such as the common neighbors and Katz index, do not work for hyperlink prediction, since they are restricted to pairwise similarities. In this paper, we formally define the hyperlink prediction problem, and propose a new algorithm called Coordinated Matrix Minimization (CMM), which alternately performs nonnegative matrix factorization and least square matching in the vertex adjacency space of the hypernetwork, in order to infer a subset of candidate hyperlinks that are most suitable to fill the training hypernetwork. We evaluate CMM on two novel tasks: predicting recipes of Chinese food, and finding missing reactions of metabolic networks. Experimental results demonstrate the superior performance of our method over many seemingly promising baselines.

NeurIPS Conference 2018 Conference Paper

Link Prediction Based on Graph Neural Networks

• Muhan Zhang
• Yixin Chen

Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a ``heuristic'' that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel $\gamma$-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the $\gamma$-decaying theory, we propose a new method to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.

AAAI Conference 2015 Conference Paper

A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing

• Quan Zhou
• Wenlin Chen
• Shiji Song
• Jacob Gardner
• Kilian Weinberger
• Yixin Chen

Algorithmic reductions are one of the corner stones of theoretical computer science. Surprisingly, to-date, they have only played a limited role in machine learning. In this paper we introduce a formal and practical reduction between two of the most widely used machine learning algorithms: from the Elastic Net (and the Lasso as a special case) to the Support Vector Machine. First, we derive the reduction and summarize it in only 11 lines of MATLABTM. Then, we demonstrate its high impact potential by translating recent advances in parallelizing SVM solvers directly to the Elastic Net. The resulting algorithm is a parallel solver for the Elastic Net (and Lasso) that naturally utilizes GPU and multi-core CPUs. We evaluate it on twelve real world data sets, and show that it yields identical results as the popular (and highly optimized) glmnet implementation but is up-to two orders of magnitude faster.

AAAI Conference 2014 Conference Paper

Feature-Cost Sensitive Learning with Submodular Trees of Classifiers

• Matt Kusner
• Wenlin Chen
• Quan Zhou
• Zhixiang (Eddie) Xu
• Kilian Weinberger
• Yixin Chen

During the past decade, machine learning algorithms have become commonplace in large-scale real-world industrial applications. In these settings, the computation time to train and test machine learning algorithms is a key consideration. At training-time the algorithms must scale to very large data set sizes. At testing-time, the cost of feature extraction can dominate the CPU runtime. Recently, a promising method was proposed to account for the feature extraction cost at testing time, called Cost-sensitive Tree of Classifiers (CSTC). Although the CSTC problem is NP-hard, the authors suggest an approximation through a mixed-norm relaxation across many classifiers. This relaxation is slow to train and requires involved optimization hyperparameter tuning. We propose a different relaxation using approximate submodularity, called Approximately Submodular Tree of Classifiers (ASTC). ASTC is much simpler to implement, yields equivalent results but requires no optimization hyperparameter tuning and is up to two orders of magnitude faster to train.

EAAI Journal 2014 Journal Article

Situation-aware composition and execution in dynamic environments by automated planning

• Qiang Lu
• Justin Wilson
• Yixin Chen
• Christopher Gill
• Louis Thomas
• Gruia-Catalin Roman
• Guoliang Chen

TIST Journal 2013 Journal Article

A SAT-based approach to cost-sensitive temporally expressive planning

• Qiang Lu
• Ruoyun Huang
• Yixin Chen
• You Xu
• Weixiong Zhang
• Guoliang Chen

Complex features, such as temporal dependencies and numerical cost constraints, are hallmarks of real-world planning problems. In this article, we consider the challenging problem of cost-sensitive temporally expressive (CSTE) planning, which requires concurrency of durative actions and optimization of action costs. We first propose a scheme to translate a CSTE planning problem to a minimum cost (MinCost) satisfiability (SAT) problem and to integrate with a relaxed parallel planning semantics for handling true temporal expressiveness. Our scheme finds solution plans that optimize temporal makespan, and also minimize total action costs at the optimal makespan. We propose two approaches for solving MinCost SAT. The first is based on a transformation of a MinCost SAT problem to a weighted partial Max-SAT (WPMax-SAT), and the second, called BB-CDCL, is an integration of the branch-and-bound technique and the conflict driven clause learning (CDCL) method. We also develop a CSTE customized variable branching scheme for BB-CDCL which can significantly improve the search efficiency. Our experiments on the existing CSTE benchmark domains show that our planner compares favorably to the state-of-the-art temporally expressive planners in both efficiency and quality.

AAAI Conference 2013 Conference Paper

Goal-Oriented Euclidean Heuristics with Manifold Learning

• Wenlin Chen
• Yixin Chen
• Kilian Weinberger
• Qiang Lu
• Xiaoping Chen

Recently, a Euclidean heuristic (EH) has been proposed for A* search. EH exploits manifold learning methods to construct an embedding of the state space graph, and derives an admissible heuristic distance between two states from the Euclidean distance between their respective embedded points. EH has shown good performance and memory efficiency in comparison to other existing heuristics such as differential heuristics. However, its potential has not been fully explored. In this paper, we propose a number of techniques that can significantly improve the quality of EH. We propose a goal-oriented manifold learning scheme that optimizes the Euclidean distance to goals in the embedding while maintaining admissibility and consistency. We also propose a state heuristic enhancement technique to reduce the gap between heuristic and true distances. The enhanced heuristic is admissible but no longer consistent. We then employ a modified search algorithm, known as B0 algorithm, that achieves optimality with inconsistent heuristics using consistency check and propagation. We demonstrate the effectiveness of the above techniques and report un-matched reduction in search costs across several non-trivial benchmark search problems.

AAAI Conference 2012 Conference Paper

Towards Automated Choreographing of Web Services Using Planning

• Guobing Zou
• Yixin Chen
• You Xu
• Ruoyun Huang
• Yang Xiang

For Web service composition, choreography has recently received great attention and demonstrated a few key advantages over orchestration such as distributed control, fairness, data efficiency, and scalability. Automated design of choreography plans, especially distributed plans for multiple roles, is more complex and has not been studied before. Existing work requires manual generation assisted by model checking. In this paper, we propose a novel planning-based approach that can automatically convert a given composition task to a distributed choreography specification. Although planning has been used for orchestration, it is difficult to use planning for choreography, as it involves decentralized control, concurrent workflows, and contingency. We propose a few novel techniques, including compilation of contingencies, dependency graph analysis, and communication control, to handle these characteristics using planning. We theoretically show the correctness of this approach and empirically evaluate its practicability.

AAAI Conference 2010 Conference Paper

A Novel Transition Based Encoding Scheme for Planning as Satisfiability

• Ruoyun Huang
• Yixin Chen
• Weixiong Zhang

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from the STRIPS formalism. We introduce a novel SAT encoding scheme based on the SAS+ formalism. It exploits the structural information in the SAS+ formalism, resulting in more compact SAT instances and reducing the number of clauses by up to 50 fold. Our results show that this encoding scheme improves upon the STRIPS-based encoding, in terms of both time and memory efficiency.

TIST Journal 2010 Journal Article

Preface to special issue on applications of automated planning

• Yixin Chen

IJCAI Conference 2009 Conference Paper

• Yixin Chen
• Guohui Yao

Traditional AI search methods search in a state space typically modelled as a directed graph. Prohibitively large sizes of state space graphs make complete or optimal search expensive. A key observation, as exemplified by the SAS+ formalism for planning, is that most commonly a state-space graph can be decomposed into subgraphs, linked by constraints. We propose a novel space reduction algorithm that exploits such structure. The result reveals that standard search algorithms may explore many redundant paths. Our method provides an automatic way to remove such redundancy. At each state, we expand only the subgraphs within a dependency closure satisfying certain sufficient conditions instead of all the subgraphs. Theoretically we prove that the proposed algorithm is completeness-preserving as well as optimality-preserving. We show that our reduction method can significantly reduce the search cost on a collection of planning domains.

IJCAI Conference 2009 Conference Paper

• Yixin Chen
• You Xu
• Guohui Yao

Most planning problems have strong structures. They can be decomposed into subdomains with causal dependencies. The idea of exploiting the domain decomposition has motivated previous work such as hierarchical planning and factored planing. However, these algorithms require extensive backtracking and lead to few efficient general-purpose planners. On the other hand, heuristic search has been a successful approach to automated planning. The domain decomposition of planning problems, unfortunately, is not directly and fully exploited by heuristic search. We propose a novel and general framework to exploit domain decomposition. Based on a structure analysis on the SAS+ planning formalism, we stratify the sub-domains of a planning problem into dependency layers. By recognizing the stratification of a planning structure, we propose a space reduction method that expands only a subset of executable actions at each state. This reduction method can be combined with state-space search, allowing us to simultaneously employ the strength of domain decomposition and high-quality heuristics. We prove that the reduction preserves completeness and optimality of search and experimentally verify its effectiveness in space reduction.

AIJ Journal 2009 Journal Article

Long-distance mutual exclusion for planning

• Yixin Chen
• Ruoyun Huang
• Zhao Xing
• Weixiong Zhang

Mutual exclusion (mutex) is a powerful mechanism for search space pruning in planning. However, a serious limitation of mutex is that it cannot specify constraints relating actions and facts across different time steps. In this paper, we propose a new class of mutual exclusions that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same time step but also across multiple steps. As a generalization, londex is much stronger than mutex, and provides a general and effective tool for developing efficient planners. We propose two levels of londex. The first level, londex1, is derived from individual domain transition graphs (DTGs), and the second level, londex m, is derived from multiple DTGs by taking into account the interactions among them. Londex constraints provide stronger pruning power but also require a large amount of memory. To address the memory problem, we further develop a virtual realization mechanism in which only a small proportion of londex constraints are dynamically generated as needed during the search. This scheme can save a huge amount of memory without sacrificing the pruning power of londex. For evaluation purposes, we incorporate londex into SATPlan04 and SATPlan06, two efficient SAT-based planners. Our experimental results show that londex m can significantly improve over londex1 since the former exploits causal dependencies among DTGs. Our experimental results for various planning domains also show significant advantages of using londex constraints for reducing planning time.

AAAI Conference 2008 Conference Paper

Fast Planning by Search in Domain Transition Graph

• Yixin Chen

Recent advances in classical planning have used the SAS+ formalism, and several effective heuristics have been developed based on the SAS+ formalism. Comparing to the traditional STRIPS/ADL formalism, SAS+ is capable of capturing vital information such as domain transition structures and causal dependencies. In this paper, we propose a new SAS+ based incomplete planning approach. Instead of using SAS+ to derive heuristics within a heuristic search planner, we directly search in domain transition graphs (DTGs) and causal graphs (CGs) derived from the SAS+ formalism. The new method is efficient because the SAS+ representation is often much more compact than STRIPS. The CGs and DTGs provide rich information of domain structures that can effectively guide the search towards solutions. Experimental results show strong performance of the proposed planner on recent international planning competition domains.

IJCAI Conference 2007 Conference Paper

• Yixin Chen
• Zhao Xing
• Weixiong Zhang

The use of mutual exclusion (mutex) has led to significant advances in propositional planning. However, previous mutex can only detect pairs of actions or facts that cannot be arranged at the same time step. In this paper, we introduce a new class of constraints that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion londex can capture constraints over actions and facts not only at the same time step but also across multiple steps. Londex provides a powerful and general approach for improving planning efficiency. As an application, we have integrated londex into SATPLAN04, a leading optimal planner. Experimental results show that londex can effectively prune the search space and reduce the planning time. The resulting planner, MaxPlan, has won the First Place Award in the Optimal Track of the 5th International Planning Competition.

AIJ Journal 2006 Journal Article

Constraint partitioning in penalty formulations for solving temporal planning problems

• Benjamin W. Wah
• Yixin Chen

In this paper, we study the partitioning of constraints in temporal planning problems formulated as mixed-integer nonlinear programming (MINLP) problems. Constraint partitioning is attractive because it leads to much easier subproblems, where each is a significant relaxation of the original problem. Moreover, each subproblem is very similar to the original problem and can be solved by any existing solver with little or no modification. Constraint partitioning, however, introduces global constraints that may be violated when subproblems are evaluated independently. To reduce the overhead in resolving such global constraints, we develop in this paper new conditions and algorithms for limiting the search space to be backtracked in each subproblem. Using a penalty formulation of a MINLP where the constraint functions of the MINLP are transformed into non-negative functions, we present a necessary and sufficient extended saddle-point condition (ESPC) for constrained local minimization. When the penalties are larger than some thresholds, our theory shows a one-to-one correspondence between a constrained local minimum of the MINLP and an extended saddle point of the penalty function. Hence, one way to find a constrained local minimum is to increase gradually the penalties of those violated constraints and to look for a local minimum of the penalty function using any existing algorithm until a solution to the constrained model is found. Next, we extend the ESPC to constraint-partitioned MINLPs and propose a partition-and-resolve strategy for resolving violated global constraints across subproblems. Using the discrete-space ASPEN and the mixed-space MIPS planners to solve subproblems, we show significant improvements on some planning benchmarks, both in terms of the quality of the plans generated and the execution times to find them.

NeurIPS Conference 2005 Conference Paper

Size Regularized Cut for Data Clustering

• Yixin Chen
• Ya Zhang
• Xiang Ji

We present a novel spectral clustering method that enables users to incorporate prior knowledge of the size of clusters into the clustering process. The cost function, which is named size regularized cut (SRcut), is defined as the sum of the inter-cluster similarity and a regularization term measuring the relative size of two clusters. Finding a partition of the data set to minimize SRcut is proved to be NP-complete. An approximation algorithm is proposed to solve a relaxed version of the optimization problem as an eigenvalue problem. Evaluations over different data sets demonstrate that the method is not sensitive to outliers and performs better than normalized cut.

JMLR Journal 2004 Journal Article

Image Categorization by Learning and Reasoning with Regions

• Yixin Chen
• James Z. Wang

Designing computer programs to automatically categorize images using low-level features is a challenging research topic in computer vision. In this paper, we present a new learning technique, which extends Multiple-Instance Learning (MIL), and its application to the problem of region-based image categorization. Images are viewed as bags, each of which contains a number of instances corresponding to regions obtained from image segmentation. The standard MIL problem assumes that a bag is labeled positive if at least one of its instances is positive; otherwise, the bag is negative. In the proposed MIL framework, DD-SVM, a bag label is determined by some number of instances satisfying various properties. DD-SVM first learns a collection of instance prototypes according to a Diverse Density (DD) function. Each instance prototype represents a class of instances that is more likely to appear in bags with the specific label than in the other bags. A nonlinear mapping is then defined using the instance prototypes and maps every bag to a point in a new feature space, named the bag feature space. Finally, standard support vector machines are trained in the bag feature space. We provide experimental results on an image categorization problem and a drug activity prediction problem. [abs] [ pdf ][ ps.gz ][ ps ]