Medical image segmentation is crucial in the field of medical imaging, assisting healthcare professionals in analyzing images and improving diagnostic performance. Recent advancements in Transformer-based networks, which utilize self-attention mechanism, have proven their effectiveness in various medical problems, including medical imaging. However, existing self-attention mechanism in Transformers only captures pairwise correlations among image patches, neglecting non-pairwise correlations that are essential for performance enhancement. On the other hand, recently, graph-based networks have emerged to capture both pairwise and non-pairwise correlations effectively. Inspired by recent Hypergraph Neural Network (HGNN), we propose a novel hypergraph-based network for medical image segmentation. Our contribution lies in formulating novel and efficient HGNN methods for constructing Hyperedges. To effectively aggregate multiple patches with similar attributes at both feature and local levels, we introduce an improved adaptive technique leveraging the K-Nearest Neighbors (KNN) algorithm to enhance the hypergraph construction process. Additionally, we generalize the concept of Convolutional Neural Networks (CNNs) to hypergraphs. Our method achieves state-of-the-art results on two publicly available segmentation datasets, and visualization results further validate its effectiveness. Our code is released on Github: https://github.com/11yxk/AHGNN.