University of Minnesota
CSci 8363 - Linear Algebra in Data Exploration
index.php
    Intro - Examples. classintro.pdf - Class Introduction (Boley)

    Topics
    review of linear algebra for graphs
    *  synmetric eigenvalues
    *  courant fisher
    graph properties via linear algebra
    *  clustering ; mixing
    *  Laplacian: clustering, commute/hitting time
    *  averaging (heat equ) minimum energy on edges.

    Tutorial

  1. Lx = b Laplacian Solvers and Their Algorithmic Applications
    by Nisheeth K. Vishnoi
    Foundations and Trends R(C) in Theoretical Computer Science Vol. 8, Nos. 1-2 (2012) 1-141
    https://theory.epfl.ch/vishnoi/Lxb-Web.pdf
    DOI: DOI: 10.1561/0400000054
    tutorial-style.
    2013

    Importance Measures

  2. Normalized cuts and image segmentation ;
    by Shi, J. and Malik, J. ;
    Pattern Analysis and Machine Intelligence, IEEE Transactions on vol 22#8:88-905, Aug 2000 ;
    note: detailed intro
    http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf ;

  3. A Survey of Eigenvector Methods for Web Information Retrieval ;
    by Amy N. Langville and Carl D. Meyer ;
    SIAM Review, Vol. 47, No. 1 (Mar., 2005), pp. 135-161 ;
    note: HITS Pagerank SALSA
    http://www.jstor.org/stable/20453606?seq=24#page_scan_tab_contents
    http://www.jstor.org/stable/pdf/20453606.pdf;
    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.141.8006&rep=rep1&type=pdf

  4. Laplacians of graphs and Cheeger inequalities ;
    by Fan Chung ;
    note: theory isoparimetric number. mentions expander graphs
    http://www.math.ucsd.edu/~fan/wp/cheeger.pdf ;

  5. Network Properties Revealed through Matrix Functions. ;
    by E Estrada, D Higham. ;
    SIAM Review (2010) ;
    note: centrality+commincability+betweenness; spectral clustering; resolvant vs exponential
    "https://epubs.siam.org/doi/10.1137/090761070"

  6. Fast matrix computations for pairwise and columnwise commute times and Katz scores ;
    by F Bonchi, P Esfandiar, DF Gleich, C Greif
    http://arxiv.org/pdf/1104.3791 ;
    note: Katz scores using Lanczos and theory of moments. (refers to Fouss)

  7. Maintaining the duality of closeness and betweenness centrality
    by Ulrik Brandes & Stephen P.Borgatti & Linton C.Freeman
    Social Networks 44 pp. 153-159
    https://www.sciencedirect.com/science/article/pii/S0378873315000738
    DOI: https://doi.org/10.1016/j.socnet.2015.08.003
    tensor of shortest paths.
    2016

  8. Commute times for a directed graph using an asymmetric Laplacian. ;
    by Boley, D., Ranjan, G., Zhang, Z.-L. ;
    Linear Algebra and Appl., 435, 224-242. (2011). ;
    note: mainly showing how certain commutes quantities for undirected graphs work also for digraphs
    http://www.sciencedirect.com/science/article/pii/S0024379511000668
    http://www-users.cs.umn.edu/~boley/publications/papers/Laplacian10-LAA.pdf;

  9. Learning from Labeled and Unlabeled Data on a Directed Graph
    by Dengyong Zhou & Jiayuan Huang & Bernhard Scholkopf
    ICML '05:
    https://is.mpg.de/fileadmin/user_upload/files/publications/ICMLGRAPH_3518[0].pdf
    | https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.294.7765&rep=rep1&type=pdf
    "https://pure.mpg.de/rest/items/item_1791381_2/component/file_3175263/content"
    "https://www.semanticscholar.org/paper/Learning-from-labeled-and-unlabeled-data-on-a-graph-Zhou-Huang/df95ae968cb0b722143f6000fa0dc7ce21cc35e2"

  10. Markov fundamental tensor and its applications to network analysis.
    by G. Golnari, Z.-L. Zhang, & D. Boley.
    Linear Algebra and Appl., 564:126--158, 2019.
    "https://www.sciencedirect.com/science/article/abs/pii/S0024379518305470"

    Fast Solvers for Laplacian Systems

  11. Graph Sparsification by Effective Resistances
    by Daniel A. Spielman, Nikhil Srivastava
    https://arxiv.org/abs/0803.0929

  12. A nearly-mlogn time solver for SDD linear systems
    by Ioannis Koutis & Gary Miller & Richard Peng
    FOCS11
    https://arxiv.org/abs/1102.4842

  13. Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
    by Rasmus Kyng, Sushant Sachdeva
    2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
    arxiv.org/abs/1605.02353
    2016

  14. On the Limiting Behavior of Parameter-Dependent Network Centrality Measures
    by Michele Benzi & Christine Klymko
    SIMAX 36 2 pp. 686-706
    https://epubs.siam.org/doi/abs/10.1137/130950550
    DOI: https://doi.org/10.1137/130950550
    2015
    presented in 2019

  15. Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
    by Mikhail Belkin & Partha Niyogi
    Neural Computation 15 pp. 1373-1396
    http://www2.imm.dtu.dk/projects/manifold/Papers/Laplacian.pdf;
    https://www.mitpressjournals.org/doi/pdf/10.1162/089976603321780317
    2003
    presented in 2019

    Deep Neural Networks for Structured/Graph Data

  16. Gradient-Based Learning Applied to Document Recognition
    by Yan LeCun, Leon Bottou Yoshua Bengio, Patrick Haffner
    Proc. IEEE, November 1998.
    http://yann.lecun.com/exdb/publis/pdf/lecun-01a.pdf

  17. ImageNet Classification with Deep Convolutional Neural Networks
    by Alex Krizhevsky, Ilya Sutskever, Geoffrey E. Hinton
    NIPS 2012.
    https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks
    === NIPS-2012-imagenet-classification-with-deep-convolutional-neural-networks-Paper.pdf ===

    =====
    tutorial on CNNs: https://ujjwalkarn.me/2016/08/11/intuitive-explanation-convnets/
    tutoral on NN+ back-prop: https://ujjwalkarn.me/2016/08/09/quick-intro-neural-networks/
    =====

  18. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
    by Michael Defferrard and Xavier Bresson and Pierre Vandergheynst
    https://arxiv.org/abs/1606.09375

  19. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
    by Chaoyue Liu & Libin Zhu & Mikhail Belkin
    https://arxiv.org/abs/2003.00307

  20. Convolutional Networks and Applications in Vision
    by Yann LeCun & Koray Kavukvuoglu & Clement Farabet
    Proc. International Symposium on Circuits and Systems (ISCAS'10) (IEEE)
    http://yann.lecun.com/exdb/publis/pdf/lecun-iscas-10.pdf
    2010
    presented in 2019

  21. Deep Convolutional Networks on Graph-Structured Data
    by Mikael Henaff & Joan Bruna & Yann LeCun
    https://arxiv.org/abs/1506.05163
    2015

  22. Spectral networks and deep locally connected networks on graphs
    by Joan Bruna & Wojciech Zaremba & Arthur Szlam & and Yann LeCun
    Proceedings of the 2nd International Conference on Learning Representations
    https://arxiv.org/abs/1312.6203
    2013

  23. node2vec: Scalable Feature Learning for Networks
    by Aditya Grover & Jure Leskovec
    KDD
    https://cs.stanford.edu/~jure/pubs/node2vec-kdd16.pdf
    2016
    presented in 2019

  24. Variational graph auto-encoders
    by Thomas Kipf & Max Welling
    NIPS
    https://arxiv.org/abs/1611.07308
    2016

    Matrix Sketching

  25. Simple and deterministic matrix sketching
    by Edo Liberty
    KDD '13:
    "https://www.cs.yale.edu/homes/el327/papers/simpleMatrixSketching.pdf"

  26. Practical Sketching Algorithms for Low-Rank Matrix Approximation
    by Joel A. Tropp & Alp Yurtsever & Madeleine Udell & Andvolkan Cevher
    SIMAX Vol. 38, No. 4, pp. 1454-1485
    https://epubs.siam.org/doi/epdf/10.1137/17M1111590
    | https://epubs.siam.org/doi/abs/10.1137/17M1111590
    2017

  27. Matrix sketching for supervised classification with imbalanced classes
    by Falcone, Roberta & Anderlucci, Laura & Montanari, Angela
    Data Mining and Knowledge Discovery 36 1 pp. 174-208
    https://link.springer.com/article/10.1007/s10618-021-00791-3
    | https://doi.org/10.1007/s10618-021-00791-3
    2022

  28. Semi-Supervised Classification with Graph Convolutional Networks
    by Thomas N. Kipf & Max Welling
    ICLR 2017
    https://arxiv.org/abs/1609.02907
    2017

  29. Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
    by Chaoyue Liu & Libin Zhu & Mikhail Belkin
    ICLR 2017
    https://arxiv.org/abs/2003.00307
    2017

  30. Graphs Neural Networks
    by Thomas N. Kipf
    Web tutorial, Sept 2016
    https://tkipf.github.io/graph-convolutional-networks/

  31. A Light-Weight Multi-Objective Asynchronous Hyper-Parameter Optimizer
    by Gabriel Maher & Stephen Boyd & Mykel Kochenderfer & Cristian Matache & Dylan Reuter & Alex Ulitsky & Slava Yukhymuk & Leonid Kopman
    arXiv:2202.07735, 2022
    https://arxiv.org/abs/2202.07735

  32. DeepWalk: Online Learning of Social Representations
    by Bryan Perozzi & Rami Al-Rfou & Steven Skiena.
    arXiv:1403.6652 (2014)
    https://arxiv.org/abs/1403.6652

  33. Attention Is All You Need
    by Ashish Vaswani & Noam Shazeer & Niki Parmar & Jakob Uszkoreit &Llion Jones & Aidan N. Gomez & Lukasz Kaiser & Illia Polosukhin
    arXiv:1706.03762 (2017)
    https://arxiv.org/abs/1706.03762

  34. RapidEELS: machine learning for denoising and classification in rapid acquisition electron energy loss spectroscopy
    by Cassandra M. Pate & James L. Hart & Mitra L. Taheri.
    Scientific Reports volume 11, Article number: 19515 (2021)
    https://doi.org/10.1038/s41598-021-97668-8

  35. Discovering faster matrix multiplication algorithms with reinforcement learning
    by Alhussein Fawzi & Matej Balog & Aja Huang & Thomas Hubert & Bernardino Romera-Paredes & Mohammadamin Barekatain & Alexander Novikov & Francisco J. R. Ruiz & Julian Schrittwieser & Grzegorz Swirszcz & David Silver &Demis Hassabis & Pushmeet Kohli.
    Nature volume 610, pages 47-53 (2022)
    https://doi.org/10.1038/s41586-022-05172-4

  36. Hypergraph clustering by iteratively reweighted modularity maximization
    by Tarun Kumar & Sankaran Vaidyanathan & Harini Ananthapadmanabhan & Srinivasan Parthasarathy & Balaraman Ravindran
    Applied Network Science volume 5, Article number: 52 (2020)
    https://doi.org/10.1007/s41109-020-00300-3

  37. Deep Contextualized Word Representations
    by Matthew E. Peters & Mark Neumann & Mohit Iyyer & Matt Gardner & Christopher Clark & Kenton Lee & Luke Zettlemoyer
    arXiv:1802.05365
    https://arxiv.org/abs/1802.05365

  38. On Fast Computation of Directed Graph Laplacian Pseudo-Inverse
    by Daniel Boley
    Linear Algebra and its Applications, Volume 623, 15 August 2021, Pages 128-148
    https://doi.org/10.1016/j.laa.2020.10.018
    https://arxiv.org/abs/1802.05365

  39. Dual octree graph networks for learning adaptive volumetric shape representations
    by Peng-Shuai Wang & Yang Liu & Xin Tong
    ACM Transactions on GraphicsVolume 41Issue 4July 2022 Article No.: 103pp 1–15
    https://doi.org/10.1145/3528223.3530087
    https://arxiv.org/abs/2205.02825