{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:57:07Z","timestamp":1760151427692,"version":"build-2065373602"},"reference-count":53,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T00:00:00Z","timestamp":1646611200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007219","name":"Shanghai Municipal Natural Science Foundation","doi-asserted-by":"publisher","award":["No. 19ZR1404700"],"award-info":[{"award-number":["No. 19ZR1404700"]}],"id":[{"id":"10.13039\/100007219","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Beyond pairwise relationships, interactions among groups of agents do exist in many real-world applications, but they are difficult to capture by conventional graph models. Generalized from graphs, hypergraphs have been introduced to describe such high-order group interactions. Inspired by graph signal processing (GSP) theory, an existing hypergraph signal processing (HGSP) method presented a spectral analysis framework relying on the orthogonal CP decomposition of adjacency tensors. However, such decomposition may not exist even for supersymmetric tensors. In this paper, we propose a high-order total variation (HOTV) form of a hypergraph signal (HGS) as its smoothness measure, which is a hyperedge-wise measure aggregating all signal values in each hyperedge instead of a pairwise one in most existing work. Further, we propose an HGS analysis framework based on the Tucker decomposition of the hypergraph Laplacian induced by the aforementioned HOTV. We construct an orthonormal basis from the HOTV, by which a new spectral transformation of the HGS is introduced. Then, we design hypergraph filters in both vertex and spectral domains correspondingly. Finally, we illustrate the advantages of the proposed framework by applications in label learning.<\/jats:p>","DOI":"10.3390\/sym14030543","type":"journal-article","created":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T01:50:53Z","timestamp":1646790653000},"page":"543","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Analysis of Hypergraph Signals via High-Order Total Variation"],"prefix":"10.3390","volume":"14","author":[{"given":"Ruyuan","family":"Qu","sequence":"first","affiliation":[{"name":"School of Information Science and Technology, Fudan University, Shanghai 200433, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7095-0621","authenticated-orcid":false,"given":"Hui","family":"Feng","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Fudan University, Shanghai 200433, China"},{"name":"Shanghai Institute of Intelligent Electronics & Systems, Shanghai 200433, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0808-8572","authenticated-orcid":false,"given":"Chongbin","family":"Xu","sequence":"additional","affiliation":[{"name":"Key Laboratory for Information Science of Electromagnetic Waves (MoE), School of Information Science and Technology, Fudan University, Shanghai 200433, China"}]},{"given":"Bo","family":"Hu","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Fudan University, Shanghai 200433, China"},{"name":"Shanghai Institute of Intelligent Electronics & Systems, Shanghai 200433, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,7]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1109\/MSP.2012.2235192","article-title":"The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains","volume":"30","author":"Shuman","year":"2013","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"3042","DOI":"10.1109\/TSP.2014.2321121","article-title":"Discrete signal processing on graphs: Frequency analysis","volume":"62","author":"Sandryhaila","year":"2014","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1109\/JPROC.2018.2820126","article-title":"Graph Signal Processing: Overview, Challenges, and Applications","volume":"106","author":"Ortega","year":"2018","journal-title":"Proc. IEEE"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1126\/science.aad9029","article-title":"Higher-order organization of complex networks","volume":"353","author":"Benson","year":"2016","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"33816","DOI":"10.1103\/PhysRevA.101.033816","article-title":"Quantum experiments and hypergraphs: Multiphoton sources for quantum interference, quantum computation, and quantum entanglement","volume":"101","author":"Gu","year":"2020","journal-title":"Phys. Rev. A"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1016\/0029-5582(66)91016-9","article-title":"Three-alpha-particle resonances via the Fadeev equation","volume":"84","author":"Duck","year":"1966","journal-title":"Nucl. Phys."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"74504","DOI":"10.1063\/1.2170091","article-title":"Van der Waals forces between nanoclusters: Importance of many-body effects","volume":"124","author":"Kim","year":"2006","journal-title":"J. Chem. Phys."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"20140873","DOI":"10.1098\/rsif.2014.0873","article-title":"Homological scaffolds of brain functional networks","volume":"11","author":"Petri","year":"2014","journal-title":"J. R. Soc. Interface"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10827-017-0672-6","article-title":"Cliques and cavities in the human connectome","volume":"44","author":"Sizemore","year":"2018","journal-title":"J. Comput. Neurosci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1086\/284111","article-title":"Arguments in Favor of Higher Order Interactions","volume":"121","author":"Abrams","year":"1983","journal-title":"Am. Nat."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"0062","DOI":"10.1038\/s41559-016-0062","article-title":"Higher-order interactions capture unexplained complexity in diverse communities","volume":"1","author":"Mayfield","year":"2017","journal-title":"Nat. Ecol. Evol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1038\/nature23273","article-title":"Higher-order interactions stabilize dynamics in competitive network models","volume":"548","author":"Grilli","year":"2017","journal-title":"Nature"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1111\/ele.13765","article-title":"The context dependency of pollinator interference: How environmental conditions and co-foraging species impact floral visitation","volume":"24","author":"Ayers","year":"2021","journal-title":"Ecol. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1016\/j.tibtech.2014.04.007","article-title":"Signaling hypergraphs","volume":"32","author":"Ritz","year":"2014","journal-title":"Trends Biotechnol."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Sanchez-Gorostiaga, A., Baji\u0107, D., Osborne, M.L., Poyatos, J.F., and Sanchez, A. (2018). High-order interactions dominate the functional landscape of microbial consortia. bioRxiv, 333534.","DOI":"10.1101\/333534"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2020.05.004","article-title":"Networks beyond pairwise interactions: Structure and dynamics","volume":"874","author":"Battiston","year":"2020","journal-title":"Phys. Rep."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1093","DOI":"10.1038\/s41567-021-01371-4","article-title":"The physics of higher-order interactions in complex systems","volume":"17","author":"Battiston","year":"2021","journal-title":"Nat. Phys."},{"key":"ref_18","unstructured":"Berge, C. (1973). Graphs and Hypergraphs, North-Holland Pub. Co."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"3268","DOI":"10.1016\/j.laa.2011.11.018","article-title":"Spectra of uniform hypergraphs","volume":"436","author":"Cooper","year":"2012","journal-title":"Linear Algebra Appl."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.4310\/CMS.2014.v12.n6.a3","article-title":"H+-eigenvalues of Laplacian tensor and signless Laplacians","volume":"12","author":"Qi","year":"2014","journal-title":"Commun. Math. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.laa.2016.12.022","article-title":"Spectra of general hypergraphs","volume":"518","author":"Banerjee","year":"2017","journal-title":"Linear Algebra Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1007\/s10878-011-9407-1","article-title":"Algebraic connectivity of an even uniform hypergraph","volume":"24","author":"Hu","year":"2012","journal-title":"J. Comb. Optim."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1137\/19M1291601","article-title":"Hypergraph clustering using a new laplacian tensor with applications in image processing","volume":"13","author":"Chang","year":"2020","journal-title":"SIAM J. Imag. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.endm.2018.11.012","article-title":"On Adjacency and e-Adjacency in General Hypergraphs: Towards a New e-Adjacency Tensor","volume":"70","author":"Ouvrard","year":"2018","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1109\/JIOT.2019.2950213","article-title":"Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications","volume":"7","author":"Zhang","year":"2020","journal-title":"IEEE Internet Things"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Afshar, A., Perros, I., Ho, J.C., Khalil, E.B., Sunderam, V., Dilkina, B., and Xiong, L. (2017, January 7\u201310). CP-ORTHO: An Orthogonal Tensor Factorization Framework for Spatio-Temporal Data. Proceedings of the GIS Proc. ACM International Symposium on Advances in Geographic Information Systems, SIGSPATIAL\u201917, Redondo Beach, CA, USA.","DOI":"10.1145\/3139958.3140047"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1137\/07070111X","article-title":"Tensor decompositions and applications","volume":"51","author":"Kolda","year":"2009","journal-title":"SIAM Rev."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1254","DOI":"10.1137\/060661569","article-title":"Symmetric Tensors and Symmetric Tensor Rank","volume":"30","author":"Comon","year":"2008","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_29","unstructured":"Hein, M., Setzer, S., Jost, L., and Rangapuram, S.S. (2013). The total variation on hypergraphs-learning on hypergraphs revisited. Adv. Neural Inf. Process. Syst., 26, Available online: https:\/\/proceedings.neurips.cc\/paper\/2013\/hash\/8a3363abe792db2d8761d6403605aeb7-Abstract.html."},{"key":"ref_30","first-page":"2710","article-title":"Learning on Hypergraphs With Sparsity","volume":"43","author":"Nguyen","year":"2021","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1109\/43.784130","article-title":"Multilevel spectral hypergraph partitioning with arbitrary vertex sizes","volume":"18","author":"Zien","year":"1999","journal-title":"IEEE Trans. Comput. Des. Integr. Circuits Syst."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Zhou, D., Huang, J., and Sch\u00f6lkopf, B. (2006, January 4\u20137). Learning with Hypergraphs: Clustering, Classification, and Embedding. Proceedings of the 19th International Conference on Neural Information Processing Systems, Vancouver, BC, Canada.","DOI":"10.7551\/mitpress\/7503.003.0205"},{"key":"ref_33","first-page":"17","article-title":"Higher order learning with graphs","volume":"Volume 148","author":"Agarwal","year":"2006","journal-title":"Proceedings of the 23rd International Conference on Machine Learning ( ICML \u201906)"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Barbarossa, S., and Tsitsvero, M. (2016, January 20\u201325). An introduction to hypergraph signal processing. Proceedings of the 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Shanghai, China.","DOI":"10.1109\/ICASSP.2016.7472914"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2992","DOI":"10.1109\/TSP.2020.2981920","article-title":"Topological Signal Processing over Simplicial Complexes","volume":"68","author":"Barbarossa","year":"2020","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Qu, R., He, J., Feng, H., Xu, C., and Hu, B. (2021, January 6\u201312). Regularized recovery by multi-order partial hypergraph total variation. Proceedings of the ICASSP\u20142021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Virtual.","DOI":"10.1109\/ICASSP39728.2021.9414277"},{"key":"ref_37","unstructured":"Bourbaki, N. (1989). Elements of Mathematics, Algebra I, Chapter 1\u20133, Springer."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2710","DOI":"10.1137\/090774823","article-title":"Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods","volume":"32","author":"Ng","year":"2010","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler","year":"1973","journal-title":"Czechoslov. Math. J."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"39","DOI":"10.2298\/AADM150218006B","article-title":"On the laplacian spectra of product graphs","volume":"9","author":"Barik","year":"2015","journal-title":"Appl. Anal. Discret. Math."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1137\/S0895479801387413","article-title":"On the best rank-1 approximation of higher-order supersymmetric tensors","volume":"23","author":"Kofidis","year":"2002","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_42","first-page":"2002","article-title":"Random walks on hypergraphs with edge-dependent vertex weights","volume":"Volume 97","author":"Chaudhuri","year":"2019","journal-title":"Proceedings of the 36th International Conference on Machine Learning (ICML 2019)"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"2837","DOI":"10.1109\/TMM.2019.2909860","article-title":"Adaptive Hypergraph Embedded Semi-Supervised Multi-Label Image Annotation","volume":"21","author":"Tang","year":"2019","journal-title":"IEEE Trans. Multimed."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"3262","DOI":"10.1109\/TIP.2012.2190083","article-title":"Adaptive hypergraph learning and its application in image classification","volume":"21","author":"Yu","year":"2012","journal-title":"IEEE Trans. Image Process."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"2564","DOI":"10.1109\/TKDE.2015.2415497","article-title":"Visual Classification by \u21131-Hypergraph Modeling","volume":"27","author":"Wang","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"5957","DOI":"10.1109\/TIP.2018.2862625","article-title":"Inductive Multi-Hypergraph Learning and Its Application on View-Based 3D Object Classification","volume":"27","author":"Zhang","year":"2018","journal-title":"IEEE Trans. Image Process."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Van Lierde, H., and Chow, T.W.S. (2017, January 25\u201327). A Hypergraph Model for Incorporating Social Interactions in Collaborative Filtering. Proceedings of the 2017 International Conference on Data Mining, Communications and Information Technology (DMCIT 2017), Phuket, Thailand.","DOI":"10.1145\/3089871.3089886"},{"key":"#cr-split#-ref_48.1","unstructured":"Carlos, S., and Torgo, L. (2021). An Ensemble Hypergraph Learning Framework for Recommendation. Discovery Science, Proceedings of the 24th International Conference, DS 2021"},{"key":"#cr-split#-ref_48.2","unstructured":"Halifax, NS, Canada, 11-13 October 2021, Springer International Publishing."},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Czerniak, J., and Zarzycki, H. (2003). Application of rough sets in the presumptive diagnosis of urinary system diseases. Artificial Intelligence and Security in Computing Systems, Springer.","DOI":"10.1007\/978-1-4419-9226-0_5"},{"key":"ref_50","unstructured":"Dua, D., and Graff, C. (2019). UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences."},{"key":"ref_51","unstructured":"Bertsekas, D.P. (1999). Nonlinear Programming, Athena Scientific."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1016\/j.jsc.2005.05.007","article-title":"Eigenvalues of a real supersymmetric tensor","volume":"40","author":"Qi","year":"2005","journal-title":"J. Symb. Comput."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/3\/543\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:33:19Z","timestamp":1760135599000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/14\/3\/543"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,7]]},"references-count":53,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,3]]}},"alternative-id":["sym14030543"],"URL":"https:\/\/doi.org\/10.3390\/sym14030543","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2022,3,7]]}}}