K. M. Abadir and J. R. Magnus, Matrix algebra, 2005.
DOI : 10.1017/CBO9780511810800

P. Boldi, V. Lonati, M. Santini, and S. Vigna, Graph fibrations, graph isomorphism, and PageRank. RAIRO-Theoretical Informatics and Applications, pp.227-253, 2006.

M. M. Bronstein, J. Bruna, Y. Lecun, A. Szlam, and P. Vandergheynst, Geometric Deep Learning: Going beyond Euclidean data, IEEE Signal Processing Magazine, vol.34, issue.4, 2016.
DOI : 10.1109/MSP.2017.2693418

J. Bruna, W. Zaremba, A. Szlam, and Y. Lecun, Spectral networks and locally connected networks on graphs, 2013.

S. Chandra and I. Kokkinos, Fast, Exact and Multi-scale Inference for Semantic Image Segmentation with Deep Gaussian CRFs, ECCV, pp.402-418, 2016.
DOI : 10.1109/ICCV.2015.304

URL : https://hal.archives-ouvertes.fr/hal-01410872

O. Chapelle, J. Weston, and B. Scholkopf, Cluster kernels for semisupervised learning, NIPS, issue.5, pp.601-608, 2003.

O. Chum, J. Philbin, J. Sivic, M. Isard, and A. Zisserman, Total Recall: Automatic Query Expansion with a Generative Feature Model for Object Retrieval, 2007 IEEE 11th International Conference on Computer Vision, 2007.
DOI : 10.1109/ICCV.2007.4408891

F. R. Chung, Spectral graph theory, 1997.
DOI : 10.1090/cbms/092

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, Massachusetts Institute of Technology, vol.5, issue.6, 2009.

M. Defferrard, X. Bresson, and P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering, NIPS, pp.3837-3845, 2016.

M. Donoser and H. Bischof, Diffusion Processes for Retrieval Revisited, 2013 IEEE Conference on Computer Vision and Pattern Recognition, p.5, 2013.
DOI : 10.1109/CVPR.2013.174

P. Drineas and M. W. Mahoney, On the Nyström method for approximating a gram matrix for improved kernel-based learning, Journal of Machine Learning Research, vol.6, issue.2, pp.2153-2175, 2005.

Y. Fujiwara, M. Nakatsuji, M. Onizuka, and M. Kitsuregawa, Fast and exact top-k search for random walk with restart, Proceedings of the VLDB Endowment, pp.442-453, 2012.
DOI : 10.14778/2140436.2140441

A. Gordo, J. Almazan, J. Revaud, and D. Larlus, Deep Image Retrieval: Learning Global Representations for Image Search, 2016.
DOI : 10.1109/CVPR.2014.180

A. Gordo, J. Almazan, J. Revaud, and D. Larlus, End-to-end learning of deep visual representations for image retrieval. arXiv preprint, 2016.

L. Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.11, pp.1768-1783, 2006.
DOI : 10.1109/TPAMI.2006.233

W. Hackbusch, Iterative solution of large sparse systems of equations, 1994.

N. Halko, P. Martinsson, and J. A. Tropp, Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Review, vol.53, issue.2, pp.217-288, 2004.
DOI : 10.1137/090771806

D. K. Hammond, P. Vandergheynst, and R. Gribonval, Wavelets on graphs via spectral graph theory, Applied and Computational Harmonic Analysis, vol.30, issue.2, pp.129-150, 2011.
DOI : 10.1016/j.acha.2010.04.005

URL : https://hal.archives-ouvertes.fr/inria-00541855

K. He, X. Zhang, S. Ren, and J. Sun, Deep Residual Learning for Image Recognition, 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
DOI : 10.1109/CVPR.2016.90

M. Henaff, J. Bruna, and Y. Lecun, Deep convolutional networks on graph-structured data. arXiv preprint

C. H. Hubbell, An Input-Output Approach to Clique Identification, Sociometry, vol.28, issue.4, 1965.
DOI : 10.2307/2785990

A. Iscen, T. Furon, V. Gripon, M. Rabbat, and H. Jégou, Memory Vectors for Similarity Search in High-Dimensional Spaces, IEEE Transactions on Big Data, vol.4, issue.1, 2018.
DOI : 10.1109/TBDATA.2017.2677964

URL : https://hal.archives-ouvertes.fr/hal-01481220

A. Iscen, G. Tolias, Y. Avrithis, T. Furon, and O. Chum, Efficient Diffusion on Region Manifolds: Recovering Small Objects with Compact CNN Representations, 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2008.
DOI : 10.1109/CVPR.2017.105

URL : https://hal.archives-ouvertes.fr/hal-01505470

H. Jégou, M. Douze, and C. Schmid, Product Quantization for Nearest Neighbor Search, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, issue.1, pp.117-128, 2011.
DOI : 10.1109/TPAMI.2010.57

J. Jung, K. Shin, L. Sael, and U. Kang, Random Walk with Restart on Large Graphs Using Block Elimination, ACM Transactions on Database Systems, vol.41, issue.2, p.12, 2016.
DOI : 10.1145/2396761.2398450

J. Kandola, J. Shawe-taylor, and N. Cristianini, Learning semantic similarity, NIPS, 2002.

U. Kang and C. Faloutsos, Beyond 'Caveman Communities': Hubs and Spokes for Graph Compression and Mining, 2011 IEEE 11th International Conference on Data Mining, pp.300-309, 2011.
DOI : 10.1109/ICDM.2011.26

L. Katz, A new status index derived from sociometric analysis, Psychometrika, vol.13, issue.1, pp.39-43, 1953.
DOI : 10.1007/BF02289026

T. H. Kim, K. M. Lee, and S. U. Lee, Generative Image Segmentation Using Random Walks with Restart, ECCV, pp.264-275, 2008.
DOI : 10.1109/ICCV.2001.937655

R. Kondor and J. , Vert. Diffusion kernels. Kernel Methods in Computational Biology, issue.5, pp.171-192, 2004.

R. I. Kondor and J. Lafferty, Diffusion kernels on graphs and other discrete structures, ICML, 2002.

J. A. Lee and M. Verleysen, Nonlinear dimensionality reduction, 2007.
DOI : 10.1007/978-0-387-39351-3

URL : https://hal.archives-ouvertes.fr/hal-01517215

F. Monti, D. Boscaini, J. Masci, E. Rodoì-a, J. Svoboda et al., Geometric deep learning on graphs and manifolds using mixture model cnns. arXiv preprint, 2016.

N. Murray and F. Perronnin, Generalized Max Pooling, 2014 IEEE Conference on Computer Vision and Pattern Recognition, 2006.
DOI : 10.1109/CVPR.2014.317

B. Nadler, S. Lafon, R. R. Coifman, and I. G. Kevrekidis, Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators, NIPS, issue.5, 2005.

J. Nocedal and S. Wright, Numerical optimization, 2006.
DOI : 10.1007/b98874

A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing: Pearson New International Edition, 2010.

L. Page, S. Brin, R. Motwani, and T. Winograd, The PageRank citation ranking: bringing order to the web, p.5, 1999.

J. Pan, H. Yang, C. Faloutsos, and P. Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining , KDD '04, p.5, 2004.
DOI : 10.1145/1014052.1014135

J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, Object retrieval with large vocabularies and fast spatial matching, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383172

J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, Lost in quantization: Improving particular object retrieval in large scale image databases, 2008 IEEE Conference on Computer Vision and Pattern Recognition, 2008.
DOI : 10.1109/CVPR.2008.4587635

URL : http://www.di.ens.fr/willow/pdfs/philbin08.pdf

G. Puy, S. Kitic, and P. Pérez, Unifying local and non-local signal processing with graph cnns, 2017.

D. Qin, S. Gammeter, L. Bossard, T. Quack, and L. Van-gool, Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors, CVPR 2011, 2011.
DOI : 10.1109/CVPR.2011.5995373

F. Radenovi´cradenovi´c, G. Tolias, and O. Chum, CNN image retrieval learns from bow: Unsupervised fine-tuning with hard examples, ECCV, 2008.

A. S. Razavian, J. Sullivan, S. Carlsson, and A. Maki, [Paper] Visual Instance Retrieval with Deep Convolutional Networks, ITE Transactions on Media Technology and Applications, vol.4, issue.3, pp.251-258, 2016.
DOI : 10.3169/mta.4.251

URL : https://www.jstage.jst.go.jp/article/mta/4/3/4_251/_pdf

V. Rokhlin, A. Szlam, and M. Tygert, A Randomized Algorithm for Principal Component Analysis, SIAM Journal on Matrix Analysis and Applications, vol.31, issue.3, pp.1100-1124, 2009.
DOI : 10.1137/080736417

S. Roux, N. Tremblay, P. Borgnat, P. Abry, H. Wendt et al., Multiscale anisotropic texture unsupervised clustering for photographic paper, 2015 IEEE International Workshop on Information Forensics and Security (WIFS), pp.1-6, 2015.
DOI : 10.1109/WIFS.2015.7368593

URL : https://hal.archives-ouvertes.fr/hal-01511889

H. Rue and L. Held, Gaussian Markov random fields: theory and applications, 2005.
DOI : 10.1201/9780203492024

A. Sandryhaila and J. M. Moura, Discrete Signal Processing on Graphs, IEEE Transactions on Signal Processing, vol.61, issue.7, pp.611644-1656, 2005.
DOI : 10.1109/TSP.2013.2238935

URL : http://arxiv.org/pdf/1210.4752.pdf

J. R. Seeley, The net of reciprocal influence; a problem in treating sociometric data., Canadian Journal of Psychology Revue Canadienne de Psychologie, vol.3, issue.4, p.234, 1949.
DOI : 10.1037/h0084096

J. Shawe-taylor and N. Cristianini, Kernel methods for pattern analysis, 2004.
DOI : 10.1017/CBO9780511809682

X. Shen, Z. Lin, J. Brandt, and Y. Wu, Spatially-Constrained Similarity Measurefor Large-Scale Object Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.36, issue.6, pp.1229-1241, 2014.
DOI : 10.1109/TPAMI.2013.237

D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Processing Magazine, vol.30, issue.3, pp.83-98, 2013.
DOI : 10.1109/MSP.2012.2235192

D. I. Shuman, P. Vandergheynst, and P. Frossard, Chebyshev polynomial approximation for distributed signal processing, International Conference on Distributed Computing in Sensor Systems and Workshops, pp.1-8, 2011.
DOI : 10.1109/dcoss.2011.5982158

URL : http://arxiv.org/pdf/1105.1891.pdf

K. Simonyan and A. Zisserman, Very deep convolutional networks for large-scale image recognition. ICLR, 2014.

A. J. Smola and R. Kondor, Kernels and Regularization on Graphs, Learning Theory and Kernel Machines, pp.144-158, 2003.
DOI : 10.1007/978-3-540-45167-9_12

URL : http://mlg.anu.edu.au/~smola/./papers/SmoKon03.ps

A. J. Smola, B. Scholkopf, and K. Muller, The connection between regularization operators and support vector kernels, Neural Networks, vol.11, issue.4, pp.637-649, 1998.
DOI : 10.1016/S0893-6080(98)00032-X

URL : http://cbio.ensmp.fr/~jvert/svn/bibli/local/Smola1998connection.pdf

M. F. Tappen, C. Liu, E. H. Adelson, and W. T. Freeman, Learning Gaussian Conditional Random Fields for Low-Level Vision, 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp.1-8, 2007.
DOI : 10.1109/CVPR.2007.382979

URL : http://www.cs.ucf.edu/%7Emtappen/out_papers/cvpr07_distrib.pdf

G. Tolias, R. Sicre, and H. Jégou, Particular object retrieval with integral max-pooling of cnn activations, 2016.

H. Tong, C. Faloutsos, and J. Y. Pan, Fast Random Walk with Restart and Its Applications, Sixth International Conference on Data Mining (ICDM'06), pp.613-622, 2006.
DOI : 10.1109/ICDM.2006.70

URL : http://www2.cs.uh.edu/~ceick/7363/Papers/tong.pdf

L. N. Trefethen, D. Bau, and I. , Numerical linear algebra. SIAM, issue.2, 1997.

N. Tremblay and P. Borgnat, Graph Wavelets for Multiscale Community Mining, IEEE Transactions on Signal Processing, vol.62, issue.20, pp.5227-5239, 2014.
DOI : 10.1109/TSP.2014.2345355

S. Vigna, Spectral ranking. arXiv preprint, p.5, 2009.

S. V. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borgwardt, Graph kernels, Journal of Machine Learning Research, vol.11, issue.5, pp.1201-1242, 2010.

M. Wainwright and M. Jordan, Graphical Models, Exponential Families, and Variational Inference, Machine Learning, 2008.
DOI : 10.1561/2200000001

S. Wang and S. Jiang, INSTRE, ACM Transactions on Multimedia Computing, Communications, and Applications, vol.11, issue.3, p.37, 2015.
DOI : 10.1109/TPAMI.2009.132

R. Witten and E. Candes, Randomized Algorithms for Low-Rank Matrix Factorizations: Sharp Performance Bounds, Algorithmica, vol.25, issue.1, 2013.
DOI : 10.1016/j.acha.2007.12.002

D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, Learning with local and global consistency, NIPS, p.5, 2003.

D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Schölkopf, Ranking on data manifolds, NIPS, 2003.

X. Zhu, Z. Ghahramani, and J. Lafferty, Semi-supervised learning using Gaussian fields and harmonic functions, ICML, 2003.

X. Zhu, J. Kandola, J. Lafferty, and Z. Ghahramani, Graph kernels by spectral transforms, Semi-Supervised Learning, pp.277-291, 2006.

X. Zhu, J. D. Lafferty, and Z. Ghahramani, Semi-supervised Learning, 2003.
DOI : 10.3115/981658.981684

URL : https://hal.archives-ouvertes.fr/hal-01961357