Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the mi...Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the minimum cardinality of transversals.In 2021,Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most 2m+1/3,that is,τ(H)≤2m+1/3, where m is the size of H.Moreover,they gave the necessary and sufficient conditions to reachthe upper bound,namely τ(H)≤2m+1/3,if and only if H is a hypertreewitha 3 perfect matching.In this paper,we investigate the transversal number of connected kunifom hypergraphs for k≥3.We confrm that τ(H)≤(k-1)m+1/k for any k-unifom hypegraphH with size m.Furthermore,we show that τ(H)≤(k-1)m+1/k if and only if H is a hypertree with a perfect matching,which generalizes the results of Diao.展开更多
Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪...Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪ S2 or e S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. （1） For any n ≥ 2k2 - k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent （k - 1）-sets equal to 2n - 4（k - 1）, contains no perfect matching; （2） Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd＋ （k- 2）k. If the degree sum of any two middle independent （k- 1）-subsets is larger than 2（d- 1）, then H contains a d-matching; （3） For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent （k - 1）-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.展开更多
This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh ...This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh principle and the perturbation of the spectral radius under moving the edge operation,and the extremal hypergraphs are characterized for both supertree and unicyclic hypergraphs.The spectral radius of the graph is generalized.展开更多
Due to self-occlusion and high degree of freedom,estimating 3D hand pose from a single RGB image is a great challenging problem.Graph convolutional networks(GCNs)use graphs to describe the physical connection relation...Due to self-occlusion and high degree of freedom,estimating 3D hand pose from a single RGB image is a great challenging problem.Graph convolutional networks(GCNs)use graphs to describe the physical connection relationships between hand joints and improve the accuracy of 3D hand pose regression.However,GCNs cannot effectively describe the relationships between non-adjacent hand joints.Recently,hypergraph convolutional networks(HGCNs)have received much attention as they can describe multi-dimensional relationships between nodes through hyperedges;therefore,this paper proposes a framework for 3D hand pose estimation based on HGCN,which can better extract correlated relationships between adjacent and non-adjacent hand joints.To overcome the shortcomings of predefined hypergraph structures,a kind of dynamic hypergraph convolutional network is proposed,in which hyperedges are constructed dynamically based on hand joint feature similarity.To better explore the local semantic relationships between nodes,a kind of semantic dynamic hypergraph convolution is proposed.The proposed method is evaluated on publicly available benchmark datasets.Qualitative and quantitative experimental results both show that the proposed HGCN and improved methods for 3D hand pose estimation are better than GCN,and achieve state-of-the-art performance compared with existing methods.展开更多
This paper focuses on the problem of traffic flow forecasting,with the aim of forecasting future traffic conditions based on historical traffic data.This problem is typically tackled by utilizing spatio-temporal graph...This paper focuses on the problem of traffic flow forecasting,with the aim of forecasting future traffic conditions based on historical traffic data.This problem is typically tackled by utilizing spatio-temporal graph neural networks to model the intricate spatio-temporal correlations among traffic data.Although these methods have achieved performance improvements,they often suffer from the following limitations:These methods face challenges in modeling high-order correlations between nodes.These methods overlook the interactions between nodes at different scales.To tackle these issues,in this paper,we propose a novel model named multi-scale dynamic hypergraph convolutional network(MSDHGCN)for traffic flow forecasting.Our MSDHGCN can effectively model the dynamic higher-order relationships between nodes at multiple time scales,thereby enhancing the capability for traffic forecasting.Experiments on two real-world datasets demonstrate the effectiveness of the proposed method.展开更多
Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to cert...Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to certain conditions.This paper is to generalize the coprime labelings of graph to hypergraph.We give the definition of coprime labelings of hypergraph.By using Rosser-Schoenfeld's inequality and the coprime mapping theorem of Pomerance and Selfridge,we prove that some linear hypergraphs are prime.展开更多
Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities a...Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities are widespread and significantly influence collective dynamics.Here,we extend the synchronization alignment function framework to hypergraphs of arbitrary order by leveraging the multi-order Laplacian matrix to encode higher-order interactions.Our findings reveal that the upper bound of synchronous behavior is determined by the maximum eigenvalue of the multi-order Laplacian matrix.Furthermore,we decompose the contribution of each hyperedge to this eigenvalue and utilize it as a basis for designing an eigenvalue-based topology modification algorithm.This algorithm effectively enhances the upper bound of synchronous behavior without altering the total number of higher-order interactions.Our study provides new insights into dynamical optimization and topology tuning in hypergraphs,advancing the understanding of the interplay between higher-order interactions and collective dynamics.展开更多
Hypergraphs can accurately capture complex higher-order relationships,but it is challenging to identify their important nodes.In this paper,an improved PageRank(ImPageRank)algorithm is designed to identify important n...Hypergraphs can accurately capture complex higher-order relationships,but it is challenging to identify their important nodes.In this paper,an improved PageRank(ImPageRank)algorithm is designed to identify important nodes in a directed hypergraph.The algorithm introduces the Jaccard similarity of directed hypergraphs.By comparing the numbers of common neighbors between nodes with the total number of their neighbors,the Jaccard similarity measure takes into account the similarity between nodes that are not directly connected,and can reflect the potential correlation between nodes.An improved susceptible–infected(SI)model in directed hypergraph is proposed,which considers nonlinear propagation mode and more realistic propagation mechanism.In addition,some important node evaluation methods are transferred from undirected hypergraphs and applied to directed hypergraphs.Finally,the ImPageRank algorithm is used to evaluate the performance of the SI model,network robustness and monotonicity.Simulations of real networks demonstrate the excellent performance of the proposed algorithm and provide a powerful framework for identifying important nodes in directed hypergraphs.展开更多
Unlike traditional video cameras,event cameras capture asynchronous event streams in which each event encodes pixel location,triggers’timestamps,and the polarity of brightness changes.In this paper,we introduce a nov...Unlike traditional video cameras,event cameras capture asynchronous event streams in which each event encodes pixel location,triggers’timestamps,and the polarity of brightness changes.In this paper,we introduce a novel hypergraph-based framework for moving object classification.Specifically,we capture moving objects with an event camera,to perceive and collect asynchronous event streams in a high temporal resolution.Unlike stacked event frames,we encode asynchronous event data into a hypergraph,fully mining the high-order correlation of event data,and designing a mixed convolutional hypergraph neural network for training to achieve a more efficient and accurate motion target recognition.The experimental results show that our method has a good performance in moving object classification(e.g.,gait identification).展开更多
Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers...Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers are focusing on the centrality problem in hypergraphs.Specifically,researchers are tackling the challenge of utilizing higher-order structures to effectively define centrality metrics.This paper presents a novel approach,LGK,derived from the K-shell decomposition method,which incorporates both global and local perspectives.Empirical evaluations indicate that the LGK method provides several advantages,including reduced time complexity and improved accuracy in identifying critical nodes in hypergraphs.展开更多
Traffic flow prediction is a crucial element of intelligent transportation systems.However,accu-rate traffic flow prediction is quite challenging because of its highly nonlinear,complex,and dynam-ic characteristics.To...Traffic flow prediction is a crucial element of intelligent transportation systems.However,accu-rate traffic flow prediction is quite challenging because of its highly nonlinear,complex,and dynam-ic characteristics.To address the difficulties in simultaneously capturing local and global dynamic spatiotemporal correlations in traffic flow,as well as the high time complexity of existing models,a multi-head flow attention-based local-global dynamic hypergraph convolution(MFA-LGDHC)pre-diction model is proposed.which consists of multi-head flow attention(MHFA)mechanism,graph convolution network(GCN),and local-global dynamic hypergraph convolution(LGHC).MHFA is utilized to extract the time dependency of traffic flow and reduce the time complexity of the model.GCN is employed to catch the spatial dependency of traffic flow.LGHC utilizes down-sampling con-volution and isometric convolution to capture the local and global spatial dependencies of traffic flow.And dynamic hypergraph convolution is used to model the dynamic higher-order relationships of the traffic road network.Experimental results indicate that the MFA-LGDHC model outperforms current popular baseline models and exhibits good prediction performance.展开更多
现有的电子健康记录(electronic health records,EHR)的图表示学习方法多依赖单个患者的局部信息,忽视了群体患者在疾病演化和诊疗路径上的潜在关联,从而限制了模型的泛化性与鲁棒性.针对这一问题,本文提出一种混合多层级图神经网络(hyb...现有的电子健康记录(electronic health records,EHR)的图表示学习方法多依赖单个患者的局部信息,忽视了群体患者在疾病演化和诊疗路径上的潜在关联,从而限制了模型的泛化性与鲁棒性.针对这一问题,本文提出一种混合多层级图神经网络(hybrid multi-level graph neural network,H-MGNN)模型,并将其应用于重症监护室(intensive care unit,ICU)患者的死亡预测.该模型通过构建宏观层面的患者关系图(patient-patient graph,P-P)、微观层面的分类-笔记-词汇超图(taxonomy-note-word hypergraph,T-N-W),结合超图的时序依赖关系,实现多尺度上的患者特征融合.同时,本文设计了融合算法(hybrid embedding,Hybrid-E),用于提取和整合患者嵌入的潜在特征,以提升预测准确性.实验结果表明,H-MGNN在MIMIC-Ⅲ(medical information mart for intensive care Ⅲ)数据集上的住院死亡率预测等任务中显著优于现有方法,验证了其在复杂EHR数据挖掘中的有效性和先进性.展开更多
基金supported by the National Natural Science Foundation of China(No.12171089).
文摘Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the minimum cardinality of transversals.In 2021,Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most 2m+1/3,that is,τ(H)≤2m+1/3, where m is the size of H.Moreover,they gave the necessary and sufficient conditions to reachthe upper bound,namely τ(H)≤2m+1/3,if and only if H is a hypertreewitha 3 perfect matching.In this paper,we investigate the transversal number of connected kunifom hypergraphs for k≥3.We confrm that τ(H)≤(k-1)m+1/k for any k-unifom hypegraphH with size m.Furthermore,we show that τ(H)≤(k-1)m+1/k if and only if H is a hypertree with a perfect matching,which generalizes the results of Diao.
基金Supported by National Natural Science Foundation of China(Grant No.11771247)
文摘Let SI and S2 be two （k- 1）-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E（H） such that S1 ∩ e≠ 0 and S2 ∩ e ≠0 or e S1 ∪ S2 or e S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. （1） For any n ≥ 2k2 - k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent （k - 1）-sets equal to 2n - 4（k - 1）, contains no perfect matching; （2） Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd＋ （k- 2）k. If the degree sum of any two middle independent （k- 1）-subsets is larger than 2（d- 1）, then H contains a d-matching; （3） For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent （k - 1）-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n.
基金Supported by Natural Science Foundation of HuBei Province(2022CFB299).
文摘This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh principle and the perturbation of the spectral radius under moving the edge operation,and the extremal hypergraphs are characterized for both supertree and unicyclic hypergraphs.The spectral radius of the graph is generalized.
基金the National Key Research and Development Program of China(No.2021ZD0111902)the National Natural Science Foundation of China(Nos.62172022 and U21B2038)。
文摘Due to self-occlusion and high degree of freedom,estimating 3D hand pose from a single RGB image is a great challenging problem.Graph convolutional networks(GCNs)use graphs to describe the physical connection relationships between hand joints and improve the accuracy of 3D hand pose regression.However,GCNs cannot effectively describe the relationships between non-adjacent hand joints.Recently,hypergraph convolutional networks(HGCNs)have received much attention as they can describe multi-dimensional relationships between nodes through hyperedges;therefore,this paper proposes a framework for 3D hand pose estimation based on HGCN,which can better extract correlated relationships between adjacent and non-adjacent hand joints.To overcome the shortcomings of predefined hypergraph structures,a kind of dynamic hypergraph convolutional network is proposed,in which hyperedges are constructed dynamically based on hand joint feature similarity.To better explore the local semantic relationships between nodes,a kind of semantic dynamic hypergraph convolution is proposed.The proposed method is evaluated on publicly available benchmark datasets.Qualitative and quantitative experimental results both show that the proposed HGCN and improved methods for 3D hand pose estimation are better than GCN,and achieve state-of-the-art performance compared with existing methods.
基金the National Key Research and Development Program of China(No.2021ZD0112400)。
文摘This paper focuses on the problem of traffic flow forecasting,with the aim of forecasting future traffic conditions based on historical traffic data.This problem is typically tackled by utilizing spatio-temporal graph neural networks to model the intricate spatio-temporal correlations among traffic data.Although these methods have achieved performance improvements,they often suffer from the following limitations:These methods face challenges in modeling high-order correlations between nodes.These methods overlook the interactions between nodes at different scales.To tackle these issues,in this paper,we propose a novel model named multi-scale dynamic hypergraph convolutional network(MSDHGCN)for traffic flow forecasting.Our MSDHGCN can effectively model the dynamic higher-order relationships between nodes at multiple time scales,thereby enhancing the capability for traffic forecasting.Experiments on two real-world datasets demonstrate the effectiveness of the proposed method.
基金Supported by the Natural Science Foundation of Chongqing(CSTB2022NSCQ-MSX0884)。
文摘Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to certain conditions.This paper is to generalize the coprime labelings of graph to hypergraph.We give the definition of coprime labelings of hypergraph.By using Rosser-Schoenfeld's inequality and the coprime mapping theorem of Pomerance and Selfridge,we prove that some linear hypergraphs are prime.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.12247153,T2293771,and 12247101)the Zhejiang Provincial Natural Science Foundation of China(Grant No.LTGY24A050002)+3 种基金the Sichuan Science and Technology Program(Grant Nos.2024NSFSC1364 and 2023NSFSC1919)the Project of Huzhou Science and Technology Bureau(Grant No.2022YZ29)the UESTCYDRI research start-up(Grant No.U03210066)the New Cornerstone Science Foundation through the Xplorer Prize。
文摘Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities are widespread and significantly influence collective dynamics.Here,we extend the synchronization alignment function framework to hypergraphs of arbitrary order by leveraging the multi-order Laplacian matrix to encode higher-order interactions.Our findings reveal that the upper bound of synchronous behavior is determined by the maximum eigenvalue of the multi-order Laplacian matrix.Furthermore,we decompose the contribution of each hyperedge to this eigenvalue and utilize it as a basis for designing an eigenvalue-based topology modification algorithm.This algorithm effectively enhances the upper bound of synchronous behavior without altering the total number of higher-order interactions.Our study provides new insights into dynamical optimization and topology tuning in hypergraphs,advancing the understanding of the interplay between higher-order interactions and collective dynamics.
基金Project supported by the National Natural Science Foundation of China(Grant No.62166010)the Guangxi Natural Science Foundation(Grant No.2023GXNSFAA026087).
文摘Hypergraphs can accurately capture complex higher-order relationships,but it is challenging to identify their important nodes.In this paper,an improved PageRank(ImPageRank)algorithm is designed to identify important nodes in a directed hypergraph.The algorithm introduces the Jaccard similarity of directed hypergraphs.By comparing the numbers of common neighbors between nodes with the total number of their neighbors,the Jaccard similarity measure takes into account the similarity between nodes that are not directly connected,and can reflect the potential correlation between nodes.An improved susceptible–infected(SI)model in directed hypergraph is proposed,which considers nonlinear propagation mode and more realistic propagation mechanism.In addition,some important node evaluation methods are transferred from undirected hypergraphs and applied to directed hypergraphs.Finally,the ImPageRank algorithm is used to evaluate the performance of the SI model,network robustness and monotonicity.Simulations of real networks demonstrate the excellent performance of the proposed algorithm and provide a powerful framework for identifying important nodes in directed hypergraphs.
基金the National Key Research and Development Program of China(No.2021ZD0112400)。
文摘Unlike traditional video cameras,event cameras capture asynchronous event streams in which each event encodes pixel location,triggers’timestamps,and the polarity of brightness changes.In this paper,we introduce a novel hypergraph-based framework for moving object classification.Specifically,we capture moving objects with an event camera,to perceive and collect asynchronous event streams in a high temporal resolution.Unlike stacked event frames,we encode asynchronous event data into a hypergraph,fully mining the high-order correlation of event data,and designing a mixed convolutional hypergraph neural network for training to achieve a more efficient and accurate motion target recognition.The experimental results show that our method has a good performance in moving object classification(e.g.,gait identification).
文摘Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers are focusing on the centrality problem in hypergraphs.Specifically,researchers are tackling the challenge of utilizing higher-order structures to effectively define centrality metrics.This paper presents a novel approach,LGK,derived from the K-shell decomposition method,which incorporates both global and local perspectives.Empirical evaluations indicate that the LGK method provides several advantages,including reduced time complexity and improved accuracy in identifying critical nodes in hypergraphs.
基金Supported by the Key R&D Program of Gansu Province(No.23YFGA0063)the Key Talent Project of Gansu Province(No.2024RCXM57,2024RCXM22)the Major Science and Technology Special Program of Gansu Province(No.25ZYJA037).
文摘Traffic flow prediction is a crucial element of intelligent transportation systems.However,accu-rate traffic flow prediction is quite challenging because of its highly nonlinear,complex,and dynam-ic characteristics.To address the difficulties in simultaneously capturing local and global dynamic spatiotemporal correlations in traffic flow,as well as the high time complexity of existing models,a multi-head flow attention-based local-global dynamic hypergraph convolution(MFA-LGDHC)pre-diction model is proposed.which consists of multi-head flow attention(MHFA)mechanism,graph convolution network(GCN),and local-global dynamic hypergraph convolution(LGHC).MHFA is utilized to extract the time dependency of traffic flow and reduce the time complexity of the model.GCN is employed to catch the spatial dependency of traffic flow.LGHC utilizes down-sampling con-volution and isometric convolution to capture the local and global spatial dependencies of traffic flow.And dynamic hypergraph convolution is used to model the dynamic higher-order relationships of the traffic road network.Experimental results indicate that the MFA-LGDHC model outperforms current popular baseline models and exhibits good prediction performance.
文摘现有的电子健康记录(electronic health records,EHR)的图表示学习方法多依赖单个患者的局部信息,忽视了群体患者在疾病演化和诊疗路径上的潜在关联,从而限制了模型的泛化性与鲁棒性.针对这一问题,本文提出一种混合多层级图神经网络(hybrid multi-level graph neural network,H-MGNN)模型,并将其应用于重症监护室(intensive care unit,ICU)患者的死亡预测.该模型通过构建宏观层面的患者关系图(patient-patient graph,P-P)、微观层面的分类-笔记-词汇超图(taxonomy-note-word hypergraph,T-N-W),结合超图的时序依赖关系,实现多尺度上的患者特征融合.同时,本文设计了融合算法(hybrid embedding,Hybrid-E),用于提取和整合患者嵌入的潜在特征,以提升预测准确性.实验结果表明,H-MGNN在MIMIC-Ⅲ(medical information mart for intensive care Ⅲ)数据集上的住院死亡率预测等任务中显著优于现有方法,验证了其在复杂EHR数据挖掘中的有效性和先进性.
