Modeling Higher-Order Interactions in Graphs Through Combinatorial Arc-Transitive Structure Using Graph Convolutional Network

The analysis of networks, including social, citation, biological, and traffic networks, has become a critical research area, enabling deeper insights into complex systems across diverse fields. Traditional Graph Convolutional Networks (GCNs) have demonstrated success in graph representation learning, particularly in homophilic networks where nodes share similar features. However, these models struggle in heterophilic networks, where connected nodes exhibit dissimilar properties, leading to performance degradation due to ineffective feature propagation. Existing approaches have attempted to address these limitations by incorporating higher-order neighborhood aggregation and signed message passing, yet they often fail to preserve network topology while maintaining computational efficiency. This research addresses the fundamental challenge of learning robust representations in heterophilic graphs by introducing Higher-Order Graph Convolutional Network (HiGCN), a novel framework that effectively models both homophilic and heterophilic interactions through a structured Petal-Complex (PC) model. The proposed approach employs a two-step random walk mechanism between core and petal regions, facilitating bidirectional information transfer while preserving the inherent graph structure. Furthermore, adaptive spectral filters across distinct Petal-Complex Laplacian spectral domains enable the effective capture of both localized and global structural patterns in combinatorial arc-transitive complexes. Our experimental evaluations on various benchmark graph datasets—including both homogeneous and heterogeneous structures—demonstrate that HiGCN significantly outperforms state-of-the-art models in node classification and graph classification tasks, particularly in domains such as bioinformatics, social networks, and recommendation systems. The findings highlight HiGCN’s potential to enhance higher-order graph learning, making it a promising solution for complex relational modeling in diverse applications.