Trajectory User Linking (TUL) focuses on linking anonymous trajectories with the users who generated them. It is essential for understanding and modeling human mobility patterns. Despite significant advancements in this field, existing studies primarily neglect the high-order inter-trajectory relationships—complex associations among multiple trajectories, often revealed through co-occurrence across multiple locations. Furthermore, they fail to consider the variable influence of Points of Interest (POIs) on different trajectories, as well as the user class imbalance problem caused by disparities in user activity levels and check-in frequencies. To address these limitations, we propose a novel HyperGraph-based Trajectory User Linking model (HGTUL). Our model learns trajectory representations from both relational and spatio-temporal perspectives: (1) It models high-order trajectory associations via a hypergraph and incorporates an attention mechanism to learn the variable impact of POIs; (2) It encodes spatio-temporal characteristics by feeding the temporal and spatial features of each trajectory into a sequential encoder. Furthermore, we introduce a data balancing method to mitigate user class imbalance, and experimentally validate its significance in TUL. Extensive experiments on three real-world datasets show that HGTUL outperforms state-of-the-art baselines, achieving improvements of 2.57% \(\sim \) 20.09% in ACC@1 and 5.68% \(\sim \) 26.00% in Macro-F1 scores. The code is available at https://github.com/changfengjie3003/HGTUL.