基于重要性采样的超图网络高效表示方法
作者:
作者简介:

邵豪(1995-), 男, 博士生, 主要研究领域为深度学习, 图嵌入, 数据挖掘;王伦文(1966-), 男, 博士, 教授, 博士生导师, 主要研究领域为机器学习, 智能信息处理;朱然刚(1979-), 男, 博士, 讲师, 主要研究领域为数据挖掘, 网络结构分析;刘辉(1983-), 男, 博士, 讲师, 主要研究领域为自然语言处理.

通讯作者:

王伦文, E-mail: eei_wanglunwen@163.com

中图分类号:

TP18

基金项目:

国家自然科学基金(61602491); 安徽省自然科学基金(2008085QF326)


Importance Sampling Based Efficient Representation for Hypergraph Networks
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [41]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    现有的超图网络表示方法需要分析全批量节点和超边以实现跨层递归扩展邻域, 这会带来巨大的计算开销, 且因过度扩展导致更低的泛化精度. 为解决这一问题, 提出一种基于重要性采样的超图表示方法. 首先, 它将节点和超边看作是两组符合特定概率测度的独立同分布样本, 用积分形式解释超图的结构特征交互; 其次, 设计带可学习参数的邻域重要性采样规则, 根据节点和超边的物理关系和特征计算采样概率, 逐层递归采集固定数目的对象, 构造一个更小的采样邻接矩阵; 最终, 利用蒙特卡洛方法近似估计整个超图的空间特征. 此外, 借鉴PINN的优势, 将需要缩减的方差作为物理约束加入到超图神经网络中, 以获取更具泛化能力的采样规则. 多个数据集上的广泛实验表明, 所提出的方法能够获得更准确的超图表示结果, 同时具有更快的收敛速度.

    Abstract:

    Existing hypergraph network representation methods need to analyze the full batch nodes and hyperedges to recursively extend the neighbors across layers, which brings huge computational costs and leads to lower generalization accuracy due to over-expansion. To solve this problem, this study proposes a hypergraph network representation method based on importance sampling. First, the method treats nodes and hyperedges as two sets of independent identically distributed samples that satisfy specific probability measures and interprets the structural feature interactions of the hypergraph in an integral form. Second, it designs a neighbor importance sampling rule with learnable parameters and calculates sampling probabilities based on the physical relations and features of nodes and hyperedges. A fixed number of objects are recursively acquired layer by layer to construct a smaller sampled adjacency matrix. Finally, the spatial features of the entire hypergraph are approximated using Monte Carlo methods. In addition, with the advantage of physically informed neural networks, the sampling variance that needs to be reduced is added to the hypergraph neural network as a physical constraint to obtain sampling rules with better generalization capability. Extensive experiments on multiple datasets show that the method proposed in this study can obtain more accurate hypergraph representation results with a faster convergence rate.

    参考文献
    [1] Alvarez-Rodriguez U, Battiston F, de Arruda GF, Moreno Y, Perc M, Latora V. Evolutionary dynamics of higher-order interactions in social networks. Nature Human Behaviour, 2021, 5(5): 586–595. [doi: 10.1038/s41562-020-01024-1]
    [2] Battiston F, Amico E, Barrat A, Bianconi G, de Arruda GF, Franceschiello B, Iacopini I, Kéfi S, Latora V, Moreno Y, Murray MM, Peixoto TP, Vaccarino F, Petri G. The physics of higher-order interactions in complex systems. Nature Physics, 2021, 17(10): 1093–1098. [doi: 10.1038/s41567-021-01371-4]
    [3] 胡秉德, 王新根, 王新宇, 宋明黎, 陈纯. 超图学习综述: 算法分类与应用分析. 软件学报, 2022, 33(2): 498–523. http://www.jos.org.cn/1000-9825/6353.htm
    Hu BD, Wang XG, Wang XY, Song ML, Chen C. Survey on hypergraph learning: Algorithm classification and application analysis. Ruan Jian Xue Bao/Journal of Software, 2022, 33(2): 498–523 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6353.htm
    [4] Gao Y, Zhang ZZ, Lin HJ, Zhao XB, Du SY, Zou CQ. Hypergraph learning: Methods and practices. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022, 44(5): 2548–2566. [doi: 10.1109/TPAMI.2020.3039374]
    [5] 吴安彪, 袁野, 马玉亮, 王国仁. 时序图节点嵌入策略的研究. 软件学报, 2021, 32(3): 650–668. http://www.jos.org.cn/1000-9825/6173.htm
    Wu AB, Yuan Y, Ma YL, Wang GR. Node embedding research over temporal graph. Ruan Jian Xue Bao/Journal of Software, 2021, 32(3): 650–668 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6173.htm
    [6] Ran YJ, Liu TY, Jia T, Xu XK. A novel similarity measure for mining missing links in long-path networks. Chinese Physics B, 2022, 31(6): 068902. [doi: 10.1088/1674-1056/ac4483]
    [7] 张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法. 电子学报, 2021, 49(11): 2101–2107. [doi: 10.12263/DZXB.20201094]
    Zhang L, Liu Q, Yang SS, Yang HP, Cheng F, Ma HP. A dual representation-based multi-objective evolutionary algorithm for overlapping community detection. Acta Electronica Sinica, 2021, 49(11): 2101–2107 (in Chinese with English abstract). [doi: 10.12263/DZXB.20201094]
    [8] Song GJ, Zhang YZ, Xu LJ, Lu HB. Domain adaptive network embedding. IEEE Transactions on Big Data, 2022, 8(5): 1220–1232. [doi: 10.1109/TBDATA.2020.3034201]
    [9] Yin N, Feng FL, Luo ZG, Zhang X, Wang WJ, Luo X, Chen C, Hua XS. Dynamic hypergraph convolutional network. In: Proc. of the 38th IEEE Int’l Conf. on Data Engineering. Kuala Lumpur: IEEE, 2022. 1621–1634.
    [10] Saha SS, Sharma K, Panda SK. On the Laplacian spectrum of k-uniform hypergraphs. Linear Algebra and its Applications, 2022, 655: 1–27. [doi: 10.1016/j.laa.2022.09.004]
    [11] Javidian MA, Wang ZY, Lu LY, Valtorta M. On a hypergraph probabilistic graphical model. Annals of Mathematics and Artificial Intelligence, 2020, 88(9): 1003–1033. [doi: 10.1007/s10472-020-09701-7]
    [12] Feng YF, You HX, Zhang ZZ, Ji RR, Gao Y. Hypergraph neural networks. In: Proc. of the 33rd AAAI Conf. on Artificial Intelligence. Honolulu: AAAI Press, 2019. 3558–3565.
    [13] Chen J, Ma TF, Xiao C. FastGCN: Fast learning with graph convolutional networks via importance sampling. In: Proc. of the 6th Int’l Conf. on Learning Representations. Vancouver: OpenReview.net, 2018.
    [14] Maleki S, Saless D, Wall DP, Pingali K. HyperNetVec: Fast and scalable hierarchical embedding for hypergraphs. In: Proc. of the 7th Int’l Conf. on Network Science. Porto: Springer, 2022. 169–183.
    [15] Yang YZ, Hu M, Huang TY. Influential nodes identification in complex networks based on global and local information. Chinese Physics B, 2020, 29(8): 088903. [doi: 10.1088/1674-1056/ab969f]
    [16] Bai S, Zhang FH, Torr PHS. Hypergraph convolution and hypergraph attention. Pattern Recognition, 2021, 110: 107637. [doi: 10.1016/j.patcog.2020.107637]
    [17] Deng Y. Recommender systems based on graph embedding techniques: A review. IEEE Access, 2022, 10: 51587–51633. [doi: 10.1109/ACCESS.2022.3174197]
    [18] Kahalé N. On the effective dimension and multilevel Monte Carlo. Operations Research Letters, 2022, 50(4): 415–421. [doi: 10.1016/j.orl.2022.06.001]
    [19] Wu Y, Yu W, Wang XJ, Shen AT. The rate of complete consistency for recursive probability density estimator under strong mixing samples. Statistics & Probability Letters, 2021, 176: 13. [doi: 10.1016/J.SPL.2021.109130]
    [20] Tabandeh A, Jia GF, Gardoni P. A review and assessment of importance sampling methods for reliability analysis. Structural Safety, 2022, 97: 102216. [doi: 10.1016/J.STRUSAFE.2022.102216]
    [21] Shi CY, Zhang Q, Chu TG. Effect of observation time on source identification of diffusion in complex networks. Chinese Physics B, 2022, 31(7): 070203. [doi: 10.1088/1674-1056/ac5985]
    [22] ?kten G, Liu YN. Randomized quasi-Monte Carlo methods in global sensitivity analysis. Reliability Engineering & System Safety, 2021, 210: 107520. [doi: 10.1016/j.ress.2021.107520]
    [23] Chibisov DM. Bernoulli's law of large numbers and the strong law of large numbers. Theory of Probability & its Applications, 2016, 60(2): 318–319. [doi: 10.1137/S0040585X97T987696]
    [24] Yu XJ, Nott DJ, Tran MN, Klein N. Assessment and adjustment of approximate inference algorithms using the law of total variance. Journal of Computational and Graphical Statistics, 2021, 30(4): 977–990. [doi: 10.1080/10618600.2021.1880921]
    [25] Krauth W. Event-chain monte carlo: Foundations, applications, and prospects. Frontiers in Physics, 2021, 9: 663457. [doi: 10.3389/FPHY.2021.663457]
    [26] Craiu RV, Gustafson P, Rosenthal JS. Reflections on bayesian inference and markov chain monte carlo. Canadian Journal of Statistics, 2022, 50(4): 1213–1227. [doi: 10.1002/cjs.11707]
    [27] Huang WB, Zhang T, Rong Y, Huang JZ. Adaptive sampling towards fast graph representation learning. In: Proc. of the 32nd In’l Conf. on Neural Information Processing Systems. Montréal: Curran Associates Inc., 2018. 4563–4572.
    [28] Peng P, Pan JG, Xu H, Feng XL. RPINNs: Rectified-physics informed neural networks for solving stationary partial differential equations. Computers & Fluids, 2022, 245: 105583. [doi: 10.1016/J.COMPFLUID.2022.105583]
    [29] Angrish A, Bharadwaj A, Starly B. MVCNN++: Computer-aided design model shape classification and retrieval using multi-view convolutional neural networks. Journal of Computing and Information Science in Engineering, 2021, 21(1): 011001. [doi: 10.1115/1.4047486]
    [30] Feng YF, Zhang ZZ, Zhao XB, Ji RR, Gao Y. GVCNN: Group-view convolutional neural networks for 3D shape recognition. In: Proc. of the 31st IEEE/CVF Conf. on Computer Vision and Pattern Recognition. Salt Lake City: IEEE, 2018. 264–272.
    [31] Wu ZH, Pan SR, Chen FW, Long GD, Zhang CQ, Yu PS. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2021, 32(1): 4–24. [doi: 10.1109/TNNLS.2020.2978386]
    [32] Tu K, Cui P, Wang X, Wang F, Zhu WW. Structural deep embedding for hyper-networks. In: Proc. of the 32nd AAAI Conf. on Artificial Intelligence, the 30th Innovative Applications of Artificial Intelligence Conf. and the 8th AAAI Symp. on Educational Advances in Artificial Intelligence. New Orleans: AAAI Press, 2018. 53.
    [33] dE Albuquerque Filho JE, Brand?o LCP, Fernandes BJT, Maciel AMA. A review of neural networks for anomaly detection. IEEE Access, 2022, 10: 112342–112367. [doi: 10.1109/ACCESS.2022.3216007]
    [34] Huang J, Chen C, Ye FH, Wu JJ, Zheng ZB, Ling GH. Hyper2vec: Biased random walk for hyper-network embedding. In: Proc. of the 24th Int’l Conf. on Database Systems for Advanced Applications. Chiang Mai: Springer, 2019. 273–277.
    [35] Du XB, Yan JC, Zhang R, Zha HY. Cross-network skip-gram embedding for joint network alignment and link prediction. IEEE Transactions on Knowledge and Data Engineering, 2022, 34(3): 1080–1095. [doi: 10.1109/TKDE.2020.2997861]
    [36] Jin TS, Dai HQ, Cao LJ, Zhang BC, Huang FY, Gao Y, Ji RR. Deepwalk-aware graph convolutional networks. Science China Information Sciences, 2022, 65(5): 152104. [doi: 10.1007/s11432-020-3318-5]
    [37] Yadati N, Nimishakavi M, Yadav P, Nitin V, Louis A, Talukdar P. HyperGCN: A new method of training graph convolutional networks on hypergraphs. In: Proc. of the 33rd Int’l Conf. on Neural Information Processing Systems. Vancouver, 2019. 135.
    [38] Yan XQ, Hu SZ, Mao YQ, Ye YD, Yu H. Deep multi-view learning methods: A review. Neurocomputing, 2021, 448: 106–129. [doi: 10.1016/j.neucom.2021.03.090]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

邵豪,王伦文,朱然刚,刘辉.基于重要性采样的超图网络高效表示方法.软件学报,2024,35(9):4390-4407

复制
分享
文章指标
  • 点击次数:583
  • 下载次数: 1733
  • HTML阅读次数: 611
  • 引用次数: 0
历史
  • 收稿日期:2023-01-19
  • 最后修改日期:2023-03-14
  • 在线发布日期: 2023-10-25
  • 出版日期: 2024-09-06
文章二维码
您是第19701247位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号