Graph coarsening: from scientific computing to machine learning. (English) Zbl 1484.65322
Summary: The general method of graph coarsening or graph reduction has been a remarkably useful and ubiquitous tool in scientific computing and it is now just starting to have a similar impact in machine learning. The goal of this paper is to take a broad look into coarsening techniques that have been successfully deployed in scientific computing and see how similar principles are finding their way in more recent applications related to machine learning. In scientific computing, coarsening plays a central role in algebraic multigrid methods as well as the related class of multilevel incomplete LU factorizations. In machine learning, graph coarsening goes under various names, e.g., graph downsampling or graph reduction. Its goal in most cases is to replace some original graph by one which has fewer nodes, but whose structure and characteristics are similar to those of the original graph. As will be seen, a common strategy in these methods is to rely on spectral properties to define the coarse graph.
MSC:
| 65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |
| 65F10 | Iterative numerical methods for linear systems |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 94C15 | Applications of graph theory to circuits and networks |
Keywords:
graph coarsening; graphs and networks; coarsening; multilevel methods; hierarchical methods. graph neural networksReferences:
| [1] | Ahmed, A., Shervashidze, N., Narayanamurthy, S., Josifovski, V., Smola, A.J.: Distributed large-scale natural graph factorization. In: Proceedings of the 22nd International Conference on World Wide Web, WWW ’13, New York, NY, USA, ACM, pp. 37-48 (2013) |
| [2] | Althöfer, I.; Das, G.; Dobkin, D.; Joseph, D.; Soares, J., On sparse spanners of weighted graphs, Discrete Comput. Geom., 9, 81-100 (1993) · Zbl 0762.05039 |
| [3] | Aspvall, B.; Gilbert, JR, Graph coloring using eigenvalue decomposition, SIAM J. Algebr. Discrete Methods, 5, 526-538 (1984) · Zbl 0554.05048 |
| [4] | Axelsson, O.; Larin, M., An algebraic multilevel iteration method for finite element matrices, J. Comput. Appl. Math., 89, 135-153 (1997) · Zbl 0941.65036 |
| [5] | Axelsson, O.; Neytcheva, M., Algebraic multilevel iteration method for Stieltjes matrices, Numer. Linear Algebra Appl., 1, 213-236 (1994) · Zbl 0837.65024 |
| [6] | Axelsson, O., Polman, B.: A robust preconditioner based on algebraic substructuring and two-level grids. In: W. Hackbusch (ed.) Robust Multigrid Methods. Proceedings, Kiel, January 1988. Notes on Numerical Fluid Mechanics, vol. 23, Vieweg, Braunschweig, pp. 1-26 (1988) · Zbl 0672.65014 |
| [7] | Axelsson, O.; Vassilevski, P., Algebraic multilevel preconditioning methods. I, Numer. Math., 56, 157-177 (1989) · Zbl 0661.65110 |
| [8] | Axelsson, O.; Vassilevski, P., A survey of multilevel preconditioned iterative methods, BIT, 29, 769-793 (1989) · Zbl 0694.65009 |
| [9] | Axelsson, O.; Vassilevski, P., Algebraic multilevel preconditioning methods. II, SIAM J. Numer. Anal., 27, 1569-1590 (1990) · Zbl 0715.65091 |
| [10] | Bakhvalov, NS, On the convergence of a relaxation method with natural constraints on the elliptic operator, USSR Comput. Math. Math. Phys., 6, 101-135 (1966) · Zbl 0154.41002 |
| [11] | Bank, RE; Wagner, C., Multilevel ILU decomposition, Numerische Mathematik, 82, 543-576 (1999) · Zbl 0938.65063 |
| [12] | Barnard, ST; Simon, HD, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Concurr. Pract. Exp., 6, 101-107 (1994) |
| [13] | Batson, J.; Spielman, DA; Srivastava, N.; Teng, S-H, Spectral sparsification of graphs: theory and algorithms, Commun. ACM, 56, 87-94 (2013) |
| [14] | Belkin, M.; Niyogi, P.; Dietterich, G.; Becker, S.; Ghahramani, Z., Laplacian eigenmaps and spectral techniques for embedding and clustering, Advances in Neural Information Processing Systems (2002), Cambridge: MIT Press, Cambridge |
| [15] | Belkin, M.; Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput., 15, 1373-1396 (2003) · Zbl 1085.68119 |
| [16] | Benczúr, A.A., Karger, D.R.: Approximating s-t minimum cuts in Õ(n2) time. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, New York, NY, USA, Association for Computing Machinery, pp. 47-55 (1996) · Zbl 0924.68150 |
| [17] | Benzi, M.; Joubert, W.; Mateescu, G., Numerical experiments with parallel orderings for ILU preconditioners, Electron. Trans. Numer. Anal., 8, 88-114 (1999) · Zbl 0923.65012 |
| [18] | Benzi, M.; Szyld, DB; van Duin, A., Orderings for incomplete factorizations of nonsymmtric matrices, SIAM J. Sci. Comput., 20, 1652-1670 (1999) · Zbl 0940.65033 |
| [19] | Benzi, M., T \(\mathring{u}\) ma: orderings for factorized sparse approximate inverse preconditioners, SIAM J. Sci. Comput., 21, 1851-1868 (2000) · Zbl 0959.65047 |
| [20] | Bishop, C.M.: Pattern Recognition and Machine Learning. Springer, Information Science and Statistics (2006) · Zbl 1107.68072 |
| [21] | Bollhöfer, M., A robust ILU with pivoting based on monitoring the growth of the inverse factors, Linear Algebra Appl., 338, 201-213 (2001) · Zbl 0991.65028 |
| [22] | Bollhöfer, M.; Grote, MJ; Schenk, O., Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media, SIAM J. Sci. Comput., 31, 3781-3805 (2009) · Zbl 1203.65273 |
| [23] | Botta, E.; Wubs, F., Matrix renumbering ILU: an effective algebraic multilevel ILU, SIAM J. Matrix Anal. Appl., 20, 1007-1026 (1999) · Zbl 0937.65057 |
| [24] | Brandt, A., Multi-level adaptive solutions to boundary-value problems, Math. Comput., 31, 290-333 (1977) · Zbl 0373.65054 |
| [25] | Brandt, A.; Barth, T.; Chan, T.; Haimes, R., Multiscale scientific computation: review 2001, Multiscale and Multiresolution Methods, Vol. 20 of Lecture Notes in Computational Science and Engineering, 3-95 (2002), Berlin: Springer, Berlin · Zbl 0989.65140 |
| [26] | Bridson, R., Tang, W.P.: Ordering, anisotropy, and factored sparse approximate inverses. SIAM J. Sci. Comput. 21 (1999) · Zbl 0955.65018 |
| [27] | Bridson, R., Tang, W.P.: A structural diagnosis of some IC orderings. SIAM J. Sci. Comput. 22 (2001) · Zbl 0988.65035 |
| [28] | Briggs, WL; Henson, VE; Mc Cormick, SF, A Multigrid Tutorial (2000), Philadelphia: SIAM, Philadelphia · Zbl 0958.65128 |
| [29] | Bronstein, MM; Bruna, J.; LeCun, Y.; Szlam, A.; Vandergheynst, P., Geometric deep learning: going beyond Euclidean data, IEEE Signal Process. Mag., 34, 18-42 (2017) |
| [30] | Bruna, J., Zaremba, W., Szlam, A., LeCun, Y.: Spectral networks and locally connected networks on graphs In: International Conference on Learning Representations (ICLR2014), CBLS (2014) |
| [31] | Burt, PJ; Adelson, EH; Fischler, MA; Firschein, O., The Laplacian pyramid as a compact image code, Readings in Computer Vision, 671-679 (1987), San Francisco: Morgan Kaufmann, San Francisco |
| [32] | Cangea, C., Velickovic, P., Jovanovic, N., Kipf, T., Liò, P.: Towards sparse hierarchical graph classifiers. arXiv:abs/1811.01287 (2018) |
| [33] | Cao, S., Lu, W., Xu, Q.: Grarep: learning graph representations with global structural information. In: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM ’15, New York, NY, USA, ACM, pp. 891-900 (2015) |
| [34] | Chandra, AK; Raghavan, P.; Ruzzo, WL; Smolensky, R.; Tiwari, P., The electrical resistance of a graph captures its commute and cover times, Comput. Complexity, 6, 312-340 (1996) · Zbl 0905.60049 |
| [35] | Chen, H., Perozzi, B., Hu, Y., Skiena, S.: HARP: hierarchical representation learning for networks. In: Proceedings of the Conference on Artificial Intelligence, vol. 32 (2018) |
| [36] | Chen, J.; Safro, I., Algebraic distance on graphs, SIAM J. Sci. Comput., 33, 3468-3490 (2011) · Zbl 1235.05042 |
| [37] | Chen, K., Matrix Preconditioning Techniques and Applications (2005), Cambridge: Cambridge University Press, Cambridge · Zbl 1079.65057 |
| [38] | Chow, E.; Saad, Y., Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math., 86, 387-414 (1997) · Zbl 0891.65028 |
| [39] | Clift, S.; Tang, W., Weighted graph based ordering techniques for preconditioned conjugate gradient methods, BIT, 35, 30-47 (1995) · Zbl 0839.65110 |
| [40] | D’Azevedo, E.; Forsyth, P.; Tang, W., Ordering methods for preconditioned conjugate gradient methods applied to unstructured grid problems, SIAM J. Matrix Anal. Appl., 13, 944-961 (1992) · Zbl 0760.65028 |
| [41] | Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, Red Hook, NY, USA, Curran Associates Inc., pp. 3844-3852 (2016) |
| [42] | Deng, C., Zhao, Z., Wang, Y., Zhang, Z., Feng, Z.: Graphzoom: a multi-level spectral approach for accurate and scalable graph embedding. In: International Conference on Learning Representations (2020) |
| [43] | Dhillon, IS; Guan, Y.; Kulis, B., Weighted graph cuts without eigenvectors a multilevel approach, IEEE Trans. Pattern Anal. Mach. Intell., 29, 1944-1957 (2007) |
| [44] | Dobson, PD; Doig, AJ, Distinguishing enzyme structures from non-enzymes without alignments, J. Mol. Biol., 330, 771-783 (2003) |
| [45] | Doi, S., Lichnewsky, A.: A graph theory approach for analyzing the effects of ordering on ILU preconditioning. Technical Report 1452, INRIA, Rocquencourt, France (1991) |
| [46] | Dorfler, F.; Bullo, F., Kron reduction of graphs with applications to electrical networks, IEEE Trans. Circuits Syst. I Reg. Pap., 60, 150-163 (2013) · Zbl 1468.94590 |
| [47] | Drineas, P.; Magdon-Ismail, M.; Mahoney, MW; Woodruff, DP, Fast approximation of matrix coherence and statistical leverage, J. Mach. Learn. Res., 13, 3475-3506 (2012) · Zbl 1437.65030 |
| [48] | Duvenaud, D.K., Maclaurin, D., Iparraguirre, J., Bombarell, R., Hirzel, T., Aspuru-Guzik, A., Adams, R.P.: Convolutional networks on graphs for learning molecular fingerprints. In: Advances in Neural Information Processing Systems, pp. 2224-2232 (2015) |
| [49] | Ellens, W.; Spieksma, F.; Van Mieghem, P.; Jamakovic, A.; Kooij, R., Effective graph resistance, Linear Algebra Appl., 435, 2491-2506 (2011) · Zbl 1222.05155 |
| [50] | Fahrbach, M., Goranci, G., Peng, R., Sachdeva, S., Wang, C.: Faster graph embeddings via coarsening. In: Proceedings of the 37th International Conference on Machine Learning (2020) |
| [51] | Fan, W., Li, J., Wang, X., Wu, Y.: Query preserving graph compression. In: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pp. 157-168 (2012) |
| [52] | Fiedler, M., Algebraic connectivity of graphs, Czechoslov. Math. J., 23, 298-305 (1973) · Zbl 0265.05119 |
| [53] | Gao, H., Ji, S.: Graph u-nets. In: ICML (2019) |
| [54] | Goldfarb, D., Modification methods for inverting matrices and solving systems of linear algebraic equations, Math. Comput., 26, 829-852 (1972) · Zbl 0268.65026 |
| [55] | Golub, GH; Loan, CFV, Matrix Computations (2013), Baltimore: Johns Hopkins University Press, Baltimore · Zbl 1268.65037 |
| [56] | Goyal, P.; Ferrara, E., Graph embedding techniques, applications, and performance: a survey, Knowl. Based Syst., 151, 78-94 (2018) |
| [57] | Grover, A., Leskovec, J.: Node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, New York, NY, USA, ACM, pp. 855-864 (2016) |
| [58] | Hackbusch, W.: Multi-grid Methods and Applications. Springer Series in Computational Mathematics, vol. 4. Springer, Berlin (1985) · Zbl 0595.65106 |
| [59] | Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, pp. 1024-1034 (2017) |
| [60] | Hamilton, W.L., Ying, R., Leskovec, J.: Representation Learning on Graphs: Methods and Applications (2017) |
| [61] | Henaff, M., Bruna, J., LeCun, Y.: Deep convolutional networks on graph-structured data (2015) |
| [62] | Hermsdorff, G.B., Gunderson, L.: A unifying framework for spectrum-preserving graph sparsification and coarsening. In: Advances in Neural Information Processing Systems, pp. 7736-7747 (2019) |
| [63] | Hu, YF; Blake, RJ, Load balancing for unstructured mesh applications, 117-148 (2001), Commack: Nova Science Publishers Inc, Commack |
| [64] | Jin, Y., Loukas, A., JaJa, J.: Graph coarsening with preserved spectral properties. In: International Conference on Artificial Intelligence and Statistics, PMLR, pp. 4452-4462 (2020) |
| [65] | Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: Foundations of Computer Science (FOCS), IEEE 55th Annual Symposium on IEEE 2014, pp. 561-570 (2014) · Zbl 1359.68295 |
| [66] | Karger, D.R.: Random sampling in cut, flow, and network design problems. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’94, New York, NY, USA, Association for Computing Machinery, pp. 648-657 (1994) · Zbl 1344.68275 |
| [67] | Karypis, G., Kumar, V.: Multilevel graph partitioning schemes. In: Proceedings of 24th International Conference Par. Proc., III. CRC Press, pp. 113-122 (1995) |
| [68] | Kernighan, BW; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 29, 291-307 (1970) · Zbl 0333.05001 |
| [69] | Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks (2016) |
| [70] | Knyazev, B., Taylor, G.W., Amer, M.R.: Understanding attention and generalization in graph neural networks (2019) |
| [71] | Krauthgamer, R.: Sketching graphs and combinatorial optimization (invited talk. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020) |
| [72] | Kron, G., Tensor Analysis of Networks (1939), New York: Wiley, New York · JFM 65.1516.01 |
| [73] | Lee, J., Lee, I., Kang, J.: Self-attention graph pooling. In: ICML (2019) |
| [74] | Liang, J., Gurukar, S., Parthasarathy, S.: MILE: a multi-level framework for scalable graph embedding. arXiv:1802.09612 [cs.AI] (2018) |
| [75] | Liu, Y.; Safavi, T.; Dighe, A.; Koutra, D., Graph summarization methods and applications: a survey, ACM Comput. Surv. (CSUR), 51, 1-34 (2018) |
| [76] | Loukas, A., Graph reduction with spectral and cut guarantees, J. Mach. Learn. Res., 20, 1-42 (2019) · Zbl 1434.68366 |
| [77] | Ma, T., Chen, J.: Unsupervised learning of graph hierarchical abstractions with differentiable coarsening and optimal transport. In: Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (2021) |
| [78] | MacLachlan, S.; Osei-Kuffuor, D.; Saad, Y., Modification and compensation strategies for threshold-based incomplete factorizations, SIAM J. Sci. Comput., 34, A48-A75 (2012) · Zbl 1241.65032 |
| [79] | MacLachlan, S.; Saad, Y., Greedy coarsening strategies for non-symmetric problems, SIAM J. Sci. Comput., 29, 2115-2143 (2007) · Zbl 1149.65022 |
| [80] | MacLachlan, S.; Saad, Y., A greedy strategy for coarse-grid selection, SIAM J. Sci. Comput., 29, 1825-1853 (2007) · Zbl 1154.65016 |
| [81] | Martin, RM, Electronic Structure, Basic Theory and Practical Methods (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1152.74303 |
| [82] | Mayer, J., A multilevel Crout ILU preconditioner with pivoting and row permutation, Numerical Linear Algebra Appl., 14, 771-789 (2007) · Zbl 1199.65091 |
| [83] | Monti, F., Boscaini, D., Masci, J., Rodola, E., Svoboda, J., Bronstein, M.M.: Geometric deep learning on graphs and manifolds using mixture model CNNS. In: The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2017) |
| [84] | Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., Grohe, M.: Weisfeiler and leman go neural: higher-order graph neural networks. In: AAAI, pp. 4602-4609 (2019) |
| [85] | Muresan, AC; Notay, Y., Analysis of aggregation-based multigrid, SIAM J. Sci. Comput., 30, 1082-1103 (2008) · Zbl 1163.65092 |
| [86] | Navlakha, S., Rastogi, R., Shrivastava, N.: Graph summarization with bounded error. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 419-432 (2008) |
| [87] | Newman, ME, A measure of betweenness centrality based on random walks, Soc. Netw., 27, 39-54 (2005) |
| [88] | Niepert, M., Ahmed, M., Kutzkov, K.: Learning convolutional neural networks for graphs. In: Proceedings of the 33rd International Conference on International Conference on Machine Learning—vol. 48, ICML’16, JMLR.org, pp. 2014-2023 (2016) |
| [89] | Notay, Y., An aggregation-based algebraic multigrid method, Electron. Trans. Numer. Anal., 37, 123-146 (2010) · Zbl 1206.65133 |
| [90] | Osei-Kuffuor, D.; Li, R.; Saad, Y., Matrix reordering using multilevel graph coarsening for ILU preconditioning, SIAM J. Sci. Comput., 37, A391-A419 (2015) · Zbl 1315.65033 |
| [91] | Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701-710 (2014) |
| [92] | Pothen, A.; Simon, H.; Liou, K-P, Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11, 430-452 (1990) · Zbl 0711.65034 |
| [93] | Powers, D.: Evaluation: from precision, recall and f-factor to roc, informedness, markedness & correlation. Mach. Learn. Technol. 2, 37-63 (2008) |
| [94] | Quiring, B.; Vassilevski, PS, Multilevel graph embedding, Numer. Linear Algebra Appl., 28, e2326 (2021) · Zbl 07361105 |
| [95] | Fang, H.R., Saad, Y.: Hypergraph-based multilevel matrix approximation for text information retrieval. In: Proceedings of the ACM International Conference on Information and Knowledge Management, 2010, J.H. et al., ed., pp. 1597-1600 (2010) |
| [96] | Fang, H.R., Sakellaridi, S., Saad, Y.: Multilevel manifold learning with application to spectral clustering. In: Proceedings of the ACM International Conference on Information and Knowledge Management, 2010, J.H. et al., ed., pp. 419-428 (2010) |
| [97] | Ranjan, G.; Zhang, Z-L, Geometry of complex networks and topological centrality, Physica A Stat. Mech. Appl., 392, 3833-3845 (2013) · Zbl 1395.05163 |
| [98] | Ron, D.; Safro, I.; Brandt, A., Relaxation-based coarsening and multiscale graph organization, SIAM Multiscale Model. Simul., 9, 407-423 (2011) · Zbl 1219.68125 |
| [99] | Roth, R., On the eigenvectors belonging to the minimum eigenvalue of an essentially nonnegative symmetric matrix with bipartite graph, Linear Algebra Appl., 118, 1-10 (1989) · Zbl 0668.15005 |
| [100] | Roweis, S.; Saul, L., Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 2323-2326 (2000) |
| [101] | Ruge, A., Stüben, K.: Algebraic multigrid. In: S.McCormick (ed.) Multigrid Methods, vol. 3 of Frontiers in Applied Mathematics, SIAM, ch. 4, pp. 73-130 (1987) · Zbl 0659.65094 |
| [102] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelpha: SIAM, Philadelpha · Zbl 1031.65046 |
| [103] | Saad, Y., Multilevel ILU with reorderings for diagonal dominance, SIAM J. Sci. Comput., 27, 1032-1057 (2005) · Zbl 1091.65034 |
| [104] | Saad, Y., Numerical Methods for Large Eigenvalue Problems-Classics Edition (2011), Philadelphia: SIAM, Philadelphia · Zbl 1242.65068 |
| [105] | Saad, Y., Suchomel, B.: ARMS: an algebraic recursive multilevel solver for general sparse linear systems. Numer. Linear Algebra Appl. 9 (2002) · Zbl 1071.65001 |
| [106] | Sakellaridi, S., Fang, H.R., Saad, Y.: Graph-based multilevel dimensionality reduction with applications to eigenfaces and latent semantic indexing. In: Proceedings of International Conference Machine Learning Applications (ICMLA), 2008, M.A. Wani, ed., IEEE Computer Society, pp. 194-200 (2008) |
| [107] | Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Galligher, B.; Eliassi-Rad, T., Collective classification in network data, AI Mag., 29, 93-93 (2008) |
| [108] | Shin, D-H; Qian, D.; Zhang, J., Cascading effects in interdependent networks, IEEE Netw., 28, 82-87 (2014) |
| [109] | Shuman, DI; Faraji, MJ; Vandergheynst, P., A multiscale pyramid transform for graph signals, IEEE Trans. Signal Process., 64, 2119-2134 (2016) · Zbl 1414.94566 |
| [110] | Shuman, DI; Narang, SK; Frossard, P.; Ortega, A.; Vandergheynst, P., The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30, 83-98 (2013) |
| [111] | Simonovsky, M., Komodakis, N.: Dynamic edge-conditioned filters in convolutional neural networks on graphs. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3693-3702 (2017) |
| [112] | Spielman, DA; Srivastava, N., Graph sparsification by effective resistances, SIAM J. Comput., 40, 1913-1926 (2011) · Zbl 1237.05129 |
| [113] | Spielman, DA; Teng, S-H, Spectral sparsification of graphs, SIAM J. Comput., 40, 981-1025 (2011) · Zbl 1228.68040 |
| [114] | Stewart, WJ, Introduction to the Numerical Solution of Markov Chains (1994), Princeton: Princeton University Press, Princeton · Zbl 0821.65099 |
| [115] | Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: Line: Large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, WWW ’15, Republic and Canton of Geneva, CHE, International World Wide Web Conferences Steering Committee, pp. 1067-1077 (2015) |
| [116] | Trottenberg, U.; Oosterlee, C.; Schüller, A., Multigrid (2001), San Diego: Academic Press, San Diego · Zbl 0976.65106 |
| [117] | Van Mieghem, P.; Devriendt, K.; Cetinay, H., Pseudoinverse of the Laplacian and best spreader node in a network, Phys. Rev. E, 96, 032311 (2017) |
| [118] | Vannieuwenhoven, N.; Meerbergen, K., IMF: an incomplete multifrontal LU-factorization for element-structured sparse linear systems, SIAM J. Sci. Comput., 35, A270-A293 (2013) · Zbl 1264.65039 |
| [119] | Vaněk, P.; Brezina, M.; Mandel, J., Convergence of algebraic multigrid based on smoothed aggregation, Numerische Mathematik, 88, 559-579 (2001) · Zbl 0992.65139 |
| [120] | Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 179-196 (1996) · Zbl 0851.65087 |
| [121] | Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., Bengio, Y.: Graph attention networks (2017) |
| [122] | Wale, N., Karypis, G.: Comparison of descriptor spaces for chemical compound retrieval and classification. In: Sixth International Conference on Data Mining (ICDM’06), pp. 678-689 (2006) |
| [123] | Wang, X., Cui, P., Wang, J., Pei, J., Zhu, W., Yang, S.: Community preserving network embedding. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), pp. 203-209 (2017) |
| [124] | Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? (2018) |
| [125] | Yanardag, P., Vishwanathan, S.: Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, New York, NY, USA, Association for Computing Machinery, pp. 1365-1374 (2015) |
| [126] | Ying, R., You, J., Morris, C., Ren, X., Hamilton, W. L., Leskovec, J.: Hierarchical graph representation learning with differentiable pooling. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, USA, Curran Associates Inc., pp. 4805-4815 (2018) |
| [127] | Zhang, M., Cui, Z., Neumann, M., Chen, Y.: An end-to-end deep learning architecture for graph classification. In: AAAI (2018) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
