Chris H. Q. Ding

ICML Conference 2024 Conference Paper

Learning Graph Representation via Graph Entropy Maximization

• Ziheng Sun
• Xudong Wang
• Chris H. Q. Ding
• Jicong Fan 0001

Graph representation learning aims to represent graphs as vectors that can be utilized in downstream tasks such as graph classification. In this work, we focus on learning diverse representations that can capture the graph information as much as possible. We propose quantifying graph information using graph entropy, where we define a probability distribution of a graph based on its nodes’ representations and global-graph representation. However, the computation of graph entropy is NP-hard due to the complex vertex-packing polytope involved in its definition. To address this challenge, we provide an approximation method leveraging orthonormal representations for graph entropy maximization. The proposed method is implemented via graph neural networks, resulting in informative node-level and graph-level representations. Experimental results demonstrate the effectiveness of our method in comparison to many baselines in unsupervised learning and semi-supervised learning tasks. The code of our method is available at https: //github. com/MathAdventurer/GeMax.

ICLR Conference 2024 Conference Paper

Neuron-Enhanced AutoEncoder Matrix Completion and Collaborative Filtering: Theory and Practice

• Jicong Fan 0001
• Rui Chen
• Zhao Zhang 0001
• Chris H. Q. Ding

Neural networks have shown promising performance in collaborative filtering and matrix completion but the theoretical analysis is limited and there is still room for improvement in terms of the accuracy of recovering missing values. This paper presents a neuron-enhanced autoencoder matrix completion (AEMC-NE) method and applies it to collaborative filtering. Our AEMC-NE adds an element-wise autoencoder to each output of the main autoencoder to enhance the reconstruction capability. Thus it can adaptively learn an activation function for the output layer to approximate possibly complicated response functions in real data. We provide theoretical analysis for AEMC-NE as well as AEMC to investigate the generalization ability of autoencoder and deep learning in matrix completion, considering both missing completely at random and missing not at random. We show that the element-wise neural network has the potential to reduce the generalization error bound, the data sparsity can be useful, and the prediction performance is closely related to the difference between the numbers of variables and samples. The numerical results on synthetic data and benchmark datasets demonstrated the effectiveness of AEMC-NE in comparison to many baselines.

ICML Conference 2012 Conference Paper

An Iterative Locally Linear Embedding Algorithm

• Deguang Kong
• Chris H. Q. Ding
• Heng Huang 0001
• Feiping Nie 0001

ICML Conference 2011 Conference Paper

Cauchy Graph Embedding

• Dijun Luo
• Chris H. Q. Ding
• Feiping Nie 0001
• Heng Huang 0001

ICML Conference 2007 Conference Paper

Adaptive dimension reduction using discriminant analysis and K -means clustering

• Chris H. Q. Ding
• Tao Li 0001

We combine linear discriminant analysis (LDA) and K -means clustering into a coherent framework to adaptively select the most discriminative subspace. We use K -means clustering to generate class labels and use LDA to do subspace selection. The clustering process is thus integrated with the subspace selection process and the data are then simultaneously clustered while the feature subspaces are selected. We show the rich structure of the general LDA-Km framework by examining its variants and their relationships to earlier approaches. Relations among PCA, LDA, K -means are clarified. Extensive experimental results on real-world datasets show the effectiveness of our approach.

ICML Conference 2006 Conference Paper

R 1 -PCA: rotational invariant L 1 -norm principal component analysis for robust subspace factorization

• Chris H. Q. Ding
• Ding Zhou
• Xiaofeng He
• Hongyuan Zha

ICML Conference 2004 Conference Paper

K -means clustering via principal component analysis

• Chris H. Q. Ding
• Xiaofeng He

Principal component analysis (PCA) is a widely used statistical technique for unsupervised dimension reduction. K -means clustering is a commonly used data clustering for performing unsupervised learning tasks. Here we prove that principal components are the continuous solutions to the discrete cluster membership indicators for K -means clustering. New lower bounds for K -means objective function are derived, which is the total variance minus the eigenvalues of the data covariance matrix. These results indicate that unsupervised dimension reduction is closely related to unsupervised learning. Several implications are discussed. On dimension reduction, the result provides new insights to the observed effectiveness of PCA-based data reductions, beyond the conventional noise-reduction explanation that PCA, via singular value decomposition, provides the best low-dimensional linear approximation of the data. On learning, the result suggests effective techniques for K -means data clustering. DNA gene expression and Internet newsgroups are analyzed to illustrate our results. Experiments indicate that the new bounds are within 0.5-1.5% of the optimal values.

ICML Conference 2004 Conference Paper

Linearized cluster assignment via spectral ordering

• Chris H. Q. Ding
• Xiaofeng He