Top

Journal of Scientific Computing

Published in:

01-04-2018

Computing the p-Spectral Radii of Uniform Hypergraphs with Applications

Authors: Jingya Chang, Weiyang Ding, Liqun Qi, Hong Yan

Published in: Journal of Scientific Computing | Issue 1/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The p-spectral radius of a uniform hypergraph covers many important concepts, such as Lagrangian and spectral radius of the hypergraph, and is crucial for solving spectral extremal problems of hypergraphs. In this paper, we establish a spherically constrained maximization model and propose a first-order conjugate gradient algorithm to compute the p-spectral radius of a uniform hypergraph (CSRH). By the semialgebraic nature of the adjacency tensor of a uniform hypergraph, CSRH is globally convergent and obtains the global maximizer with a high probability. When computing the spectral radius of the adjacency tensor of a uniform hypergraph, CSRH outperforms existing approaches. Furthermore, CSRH is competent to calculate the p-spectral radius of a hypergraph with millions of vertices and to approximate the Lagrangian of a hypergraph. Finally, we show that the CSRH method is capable of ranking real-world data set based on solutions generated by the p-spectral radius model.

next article Computing the Level Set Convex Hull

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

http://www.informatik.uni-trier.de/ley/db/.

We would like to thank Dr. Xutao Li for providing the database.

Absil, P.-A., Mahony, R., Andrews, B.: Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16(2), 531–547 (2005)MathSciNetCrossRefMATH

Agarwal, S., Lim, J., Zelnik-Manor, L., Perona, P., Kriegman, D., Belongie, S.: Beyond pairwise clustering. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), vol 2, pp. 838–845. IEEE (2005)

Bader, B.W. , Kolda, T.G. et al.: Matlab tensor toolbox version 2.6. Available online, February (2015) URL http://www.sandia.gov/~tgkolda/TensorToolbox/

Bolte, J., Daniilidis, A., Lewis, A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2006)MathSciNetCrossRefMATH

Bretto, A., Gillibert, L.: Hypergraph-based image representation. In: International Workshop on Graph-Based Representations in Pattern Recognition, pp. 1–11. Springer (2005)

Brown, W., Simonovits, M.: Digraph extremal problems, hypergraph extremal problems, and the densities of graph structures. Discret. Math. 48(2–3), 147–162 (1984)MathSciNetCrossRefMATH

Caraceni, A.: Lagrangians of hypergraphs, URL http://alessandracaraceni.altervista.org/MyWordpress/wp-content/uploads/2014/05/Hypergraph_Lagrangians.pdf (2011). [Online; Accessed 26 Jan 2017]

Chang, J., Chen, Y., Qi, L.: Computing eigenvalues of large scale sparse tensors arising from a hypergraph. SIAM J. Sci. Comput. 38(6), A3618–A3643 (2016)MathSciNetCrossRefMATH

Chang, K.C., Pearson, K., Zhang, T.: Perron–Frobenius theorem for nonnegative tensors. Commun. Math. Sci. 6(2), 507–520 (2008)MathSciNetCrossRefMATH

10.

Chen, L., Han, L., Zhou, L.: Computing tensor eigenvalues via homotopy methods. SIAM J. Matrix Anal. Appl. 37(1), 290–319 (2016a)MathSciNetCrossRefMATH

11.

Chen, Y., Dai, Y.-H., Han, D.: Fiber orientation distribution estimation using a Peaceman–Rachford splitting method. SIAM J. Imaging Sci. 9(2), 573–604 (2016b)MathSciNetCrossRefMATH

12.

Chen, Y., Qi, L., Wang, Q.: Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors. J. Comput. Appl. Math. 302, 356–368 (2016c)MathSciNetCrossRefMATH

13.

Cooper, J., Dutle, A.: Spectra of uniform hypergraphs. Linear Algebra Appl. 436(9), 3268–3292 (2012)MathSciNetCrossRefMATH

14.

Cui, C.-F., Dai, Y.-H., Nie, J.: All real eigenvalues of symmetric tensors. SIAM J. Matrix Anal. Appl. 35(4), 1582–1601 (2014)MathSciNetCrossRefMATH

15.

Ding, C., He, X., Husbands, P., Zha, H. Simon, H.D.: Pagerank, hits and a unified framework for link analysis. In: Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 353–354. ACM (2002)

16.

Ding, W., Qi, L., Wei, Y.: Fast Hankel tensor-vector product and its application to exponential data fitting. Numer. Linear Algebra Appl. 22(5), 814–832 (2015)MathSciNetCrossRefMATH

17.

Ducournau, A., Rital, S., Bretto, A., Laget, B.: A multilevel spectral hypergraph partitioning approach for color image segmentation. In: 2009 IEEE International Conference on Signal and Image Processing Applications (ICSIPA), pp. 419–424. IEEE (2009)

18.

Ducournau, A., Bretto, A., Rital, S., Laget, B.: A reductive approach to hypergraph clustering: an application to image segmentation. Pattern Recognit. 45(7), 2788–2803 (2012)CrossRefMATH

19.

Erdös, P., Stone, A.H.: On the structure of linear graphs. Bull. Am. Math. Soc. 52, 1087–1091 (1946)MathSciNetCrossRefMATH

20.

Frankl, P., Füredi, Z.: Extremal problems whose solutions are the blowups of the small Witt-designs. J. Comb. Theory Ser. A 52(1), 129–147 (1989)MathSciNetCrossRefMATH

21.

Frankl, P., Rödl, V.: Hypergraphs do not jump. Combinatorica 4(2–3), 149–159 (1984)MathSciNetCrossRefMATH

22.

Frankl, P., Peng, Y., Rödl, V., Talbot, J.: A note on the jumping constant conjecture of Erdős. J. Comb. Theory Ser. B 97(2), 204–216 (2007)CrossRefMATH

23.

Gunopulos, D., Mannila, H., Khardon, R., Toivonen, H.: Data mining, hypergraph transversals, and machine learning. In: Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 209–216. ACM (1997)

24.

Hager, W.W., Zhang, H.: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16(1), 170–192 (2005)MathSciNetCrossRefMATH

25.

Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2(1), 35–58 (2006)MathSciNetMATH

26.

Hu, S., Qi, L.: The Laplacian of a uniform hypergraph. J. Comb. Optim. 29(2), 331–366 (2015)MathSciNetCrossRefMATH

27.

Huang, Y., Liu, Q., Zhang, S., Metaxas, D.N.: Image retrieval via probabilistic hypergraph ranking. In: 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3376–3383. IEEE (2010)

28.

Kang, L., Nikiforov, V., Yuan, X.: The \(p\)-spectral radius of \(k\)-partite and \(k\)-chromatic uniform hypergraphs. Linear Algebra Appl. 478, 81–107 (2015)MathSciNetCrossRefMATH

29.

Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: applications in VLSI domain. IEEE T. VLSI Syst. 7(1), 69–79 (1999)CrossRef

30.

Keevash, P.: Hypergraph Turán problems. Surv. combinatorics 392, 83–140 (2011)MATH

31.

Keevash, P., Lenz, J., Mubayi, D.: Spectral extremal problems for hypergraphs. SIAM J. Discrete Math. 28(4), 1838–1854 (2014)MathSciNetCrossRefMATH

32.

Klamt, S., Haus, U.-U., Theis, F.: Hypergraphs and cellular networks. PLoS Comput. Biol. 5(5), e1000385 (2009)MathSciNetCrossRef

33.

Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. Appl. 32(4), 1095–1124 (2011)MathSciNetCrossRefMATH

34.

Kolda, T.G., Mayo, J.R.: An adaptive shifted power method for computing generalized tensor eigenpairs. SIAM J. Matrix Anal. Appl. 35(4), 1563–1581 (2014)MathSciNetCrossRefMATH

35.

Kolda, T.G., Bader, B.W., Kenny, J.P.: Higher-order web link analysis using multilinear algebra. In: Fifth IEEE International Conference on Data Mining (ICDM’05), p. 8. IEEE (2005)

36.

Konstantinova, E.V., Skorobogatov, V.A.: Application of hypergraph theory in chemistry. Discrete Math. 235(13), 365–383 (2001). Combinatorics (Prague, 1998)

37.

Krohn-Grimberghe, A., Drumond, L., Freudenthaler, C., Schmidt-Thieme, L.: Multi-relational matrix factorization using Bayesian personalized ranking for social network data. In: Proceedings of the fifth ACM international conference on Web search and data mining, pp. 173–182. ACM (2012)

38.

Li, H., Shao, J.-Y., Qi, L.: The extremal spectral radii of \(k\)-uniform supertrees. J. Comb. Optim. 32(3), 741–764 (2016)MathSciNetCrossRefMATH

39.

Li, X., Hu, W., Shen, C., Dick, A., Zhang, Z.: Context-aware hypergraph construction for robust spectral clustering. IEEE T. Knowl. Data En. 26(10), 2588–2597 (2014)CrossRef

40.

Liu, Y., Shao, J., Xiao, J., Wu, F., Zhuang, Y.: Hypergraph spectral hashing for image retrieval with heterogeneous social contexts. Neurocomputing 119, 49–58 (2013)CrossRef

41.

Lu, L., Man, S.: Connected hypergraphs with small spectral radius. Linear Algebra Appl. 509, 206–227 (2016)MathSciNetCrossRefMATH

42.

Michoel, T., Nachtergaele, B.: Alignment and integration of complex networks by hypergraph-based spectral clustering. Phys. Rev. E 86(5), 056111 (2012)CrossRef

43.

Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17, 533–540 (1965)CrossRefMATH

44.

Mubayi, D.: A hypergraph extension of Turán’s theorem. J. Comb. Theory Ser. B 96(1), 122–134 (2006)MathSciNetCrossRefMATH

45.

Ng, M., Qi, L., Zhou, G.: Finding the largest eigenvalue of a nonnegative tensor. SIAM J. Matrix Anal. Appl. 31(3), 1090–1099 (2009)MathSciNetCrossRefMATH

46.

Ng, M.K.-P., Li, X., Ye, Y.: Multirank: co-ranking for objects and relations in multi-relational data. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1217–1225. ACM (2011)

47.

Nikiforov, V.: Bounds on graph eigenvalues II. Linear Algebra Appl. 427(2–3), 183–189 (2007)MathSciNetCrossRefMATH

48.

Nikiforov, V.: An analytic theory of extremal hypergraph problems. arXiv preprint arXiv:1305.1073, (2013)

49.

Nikiforov, V.: Analytic methods for uniform hypergraphs. Linear Algebra Appl. 457, 455–535 (2014)MathSciNetCrossRefMATH

50.

Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)MATH

51.

Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: bringing order to the web. (1999)

52.

Pearson, K.J., Zhang, T.: On spectral hypergraph theory of the adjacency tensor. Graphs Comb. 30(5), 1233–1248 (2014)MathSciNetCrossRefMATH

53.

Peng, Y.: Using Lagrangians of hypergraphs to find non-jumping numbers I. Ann. Comb. 12(3), 307–324 (2008)MathSciNetCrossRefMATH

54.

Peng, Y., Zhao, C.: Generating non-jumping numbers recursively. Discret. Appl. Math. 156(10), 1856–1864 (2008)MathSciNetCrossRefMATH

55.

Pliakos, K., Kotropoulos, C.: Weight estimation in hypergraph learning. In: 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1161–1165. IEEE (2015)

56.

Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40(6), 1302–1324 (2005)MathSciNetCrossRefMATH

57.

Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. Society for Industrial and Applied Mathematics, Philadephia (2017)CrossRefMATH

58.

Rohe, K., Chatterjee, S., Yu, B.: Spectral clustering and the high-dimensional stochastic blockmodel. Ann. Stat. 39(4), 1878–1915 (2011)MathSciNetCrossRefMATH

59.

Sidorenko, A.F.: The maximal number of edges in a homogeneous hypergraph containing no prohibited subgraphs. Math. Notes 41(3), 247–259 (1987)CrossRefMATH

60.

Sun, L., Ji, S. Ye, J.: Hypergraph spectral learning for multi-label classification. In: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 668–676. ACM (2008)

61.

Talbot, J.: Lagrangians of hypergraphs. Comb. Probab. Comput. 11(2), 199–216 (2002)MathSciNetCrossRefMATH

62.

Turán, P.: Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48, 436–452 (1941)MathSciNetMATH

63.

Turán, P.: Research problems. MTA Mat. Kutató Int. Közl 6, 417–423 (1961)

64.

Xie, J., Chang, A.: On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs. Linear Algebra Appl. 439(8), 2195–2204 (2013)MathSciNetCrossRefMATH

65.

Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3), 1758–1789 (2013)MathSciNetCrossRefMATH

66.

Yue, J., Zhang, L., Lu, M.: Largest adjacency, signless Laplacian, and Laplacian H-eigenvalues of loose paths. Front. Math. China 11(3), 623–645 (2016)MathSciNetCrossRefMATH

67.

Zhou, D., Huang, J., Schölkopf, B.: Learning with hypergraphs: clustering, classification, and embedding. In: Advances in Neural Information Processing Systems, pp. 1601–1608. (2006)

68.

Zhuang, Y., Liu, Y., Wu, F., Zhang, Y., Shao, J.: Hypergraph spectral hashing for similarity search of social image. In: Proceedings of the 19th ACM International Conference on Multimedia, pp. 1457–1460. ACM (2011)

Title: Computing the p-Spectral Radii of Uniform Hypergraphs with Applications
Authors: Jingya Chang
Weiyang Ding
Liqun Qi
Hong Yan
Publication date: 01-04-2018
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 1/2018
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-017-0520-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2018

Finite Volume HWENO Schemes for Nonconvex Conservation Laws

Energy Stability Analysis of Some Fully Discrete Numerical Schemes for Incompressible Navier–Stokes Equations on Staggered Grids

An Efficient Semi-implicit Solver for Direct Numerical Simulation of Compressible Flows at All Speeds

A Parallel Method for Earth Mover’s Distance

Order Barrier for Low-Storage DIRK Methods with Positive Weights

Integer Matrix Approximation and Data Mining

Premium Partner