Yongchao Wang

Hongyi Li, Junxiang Wang, Yongchao Wang

Massive Multiple-Input Multiple-Out (MIMO) detection is an important problem in modern wireless communication systems. While traditional Belief Propagation (BP) detectors perform poorly on loopy graphs, the recent Graph Neural Networks (GNNs)-based method can overcome the drawbacks of BP and achieve superior performance. Nevertheless, direct use of GNN ignores the importance of edge attributes and suffers from high computation overhead using a fully connected graph structure. In this paper, we propose an efficient GNN-inspired algorithm, called the Edge Graph Neural Network (EGNN), to detect MIMO signals. We first compute graph edge weights through channel correlation and then leverage the obtained weights as a metric to evaluate the importance of neighbors of each node. Moreover, we design an adaptive Edge Drop (ED) scheme to sparsify the graph such that computational cost can be significantly reduced. Experimental results demonstrate that our proposed EGNN achieves better or comparable performance to popular MIMO detection methods for different modulation schemes and costs the least detection time compared to GNN-based approaches.

Yongchao Wang, Yang Ding, Jiansheng Yang et al.

Let $p$ be an odd prime. The factorization of the polynomial $x^{p+1}-1$ over the integer residue ring $\mathbb{Z}_{p^e}$ is pivotal for constructing cyclic codes with Hermitian symmetry, a critical resource for Linear Complementary Dual (LCD) codes and Entanglement-Assisted Quantum Error-Correcting Codes (EAQECC). Traditionally, lifting factorizations relies on the generic Hensel's Lemma, masking the underlying algebraic structure. In this paper, we establish a structural isomorphism between the lifting process and the roots of a special auxiliary polynomial $V(x)$, unveiling a deterministic link to Dickson polynomials. Based on this theory, we develop \texttt{Dickson-Engine}, a linear-time algorithm ($O(ep)$) that outperforms standard libraries by orders of magnitude. Applying this engine to $\mathbb{Z}_{169}$, we explicitly construct a family of classical LCD codes of length $n=182$ via the isometric Gray map. Our search reveals codes with parameters (e.g., $[182, 1, 168]_{13}$ and $[182, 2, 144]_{13}$) that are \textbf{near-optimal} with respect to the theoretical Griesmer Bound. Notably, we discover a ``robustness plateau'' starting from non-trivial dimensions ($k=4$), where the minimum distance remains stable ($d=120$) even as the dimension triples ($k=4 \rightarrow 12$). These codes provide exceptional resources for post-quantum cryptography and quantum error correction without entanglement consumption ($c=0$).

Qingkai Shi, Yongchao Wang, Charles Zhang

Many context-sensitive data flow analyses can be formulated as a variant of the all-pairs Dyck-CFL reachability problem, which, in general, is of sub-cubic time complexity and quadratic space complexity. Such high complexity significantly limits the scalability of context-sensitive data flow analysis and is not affordable for analyzing large-scale software. This paper presents \textsc{Flare}, a reduction from the CFL reachability problem to the conventional graph reachability problem for context-sensitive data flow analysis. This reduction allows us to benefit from recent advances in reachability indexing schemes, which often consume almost linear space for answering reachability queries in almost constant time. We have applied our reduction to a context-sensitive alias analysis and a context-sensitive information-flow analysis for C/C++ programs. Experimental results on standard benchmarks and open-source software demonstrate that we can achieve orders of magnitude speedup at the cost of only moderate space to store the indexes. The implementation of our approach is publicly available.

Junxiang Wang, Hongyi Li, Zheng Chai et al.

While Graph Neural Networks (GNNs) are popular in the deep learning community, they suffer from several challenges including over-smoothing, over-squashing, and gradient vanishing. Recently, a series of models have attempted to relieve these issues by first augmenting the node features and then imposing node-wise functions based on Multi-Layer Perceptron (MLP), which are widely referred to as GA-MLP models. However, while GA-MLP models enjoy deeper architectures for better accuracy, their efficiency largely deteriorates. Moreover, popular acceleration techniques such as stochastic-version or data-parallelism cannot be effectively applied due to the dependency among samples (i.e., nodes) in graphs. To address these issues, in this paper, instead of data parallelism, we propose a parallel graph deep learning Alternating Direction Method of Multipliers (pdADMM-G) framework to achieve model parallelism: parameters in each layer of GA-MLP models can be updated in parallel. The extended pdADMM-G-Q algorithm reduces communication costs by introducing the quantization technique. Theoretical convergence to a (quantized) stationary point of the pdADMM-G algorithm and the pdADMM-G-Q algorithm is provided with a sublinear convergence rate $o(1/k)$, where $k$ is the number of iterations. Extensive experiments demonstrate the convergence of two proposed algorithms. Moreover, they lead to a more massive speedup and better performance than all state-of-the-art comparison methods on nine benchmark datasets. Last but not least, the proposed pdADMM-G-Q algorithm reduces communication overheads by up to $45\%$ without loss of performance. Our code is available at \url{https://github.com/xianggebenben/pdADMM-G}.

Beiduo Chen, Wu Guo, Bin Gu et al.

Cross-language pre-trained models such as multilingual BERT (mBERT) have achieved significant performance in various cross-lingual downstream NLP tasks. This paper proposes a multi-level contrastive learning (ML-CTL) framework to further improve the cross-lingual ability of pre-trained models. The proposed method uses translated parallel data to encourage the model to generate similar semantic embeddings for different languages. However, unlike the sentence-level alignment used in most previous studies, in this paper, we explicitly integrate the word-level information of each pair of parallel sentences into contrastive learning. Moreover, cross-zero noise contrastive estimation (CZ-NCE) loss is proposed to alleviate the impact of the floating-point error in the training process with a small batch size. The proposed method significantly improves the cross-lingual transfer ability of our basic model (mBERT) and outperforms on multiple zero-shot cross-lingual downstream tasks compared to the same-size models in the Xtreme benchmark.

Hongyi Li, Junxiang Wang, Yongchao Wang et al.

The Graph Convolutional Network (GCN) has been successfully applied to many graph-based applications. Training a large-scale GCN model, however, is still challenging: Due to the node dependency and layer dependency of the GCN architecture, a huge amount of computational time and memory is required in the training process. In this paper, we propose a parallel and distributed GCN training algorithm based on the Alternating Direction Method of Multipliers (ADMM) to tackle the two challenges simultaneously. We first split GCN layers into independent blocks to achieve layer parallelism. Furthermore, we reduce node dependency by dividing the graph into several dense communities such that each of them can be trained with an agent in parallel. Finally, we provide solutions for all subproblems in the community-based ADMM algorithm. Preliminary results demonstrate that our proposed community-based ADMM training algorithm can lead to more than triple speedup while achieving the best performance compared with state-of-the-art methods.