Notes on: Henaff, M., Bruna, J., & LeCun, Y. (2015): Deep convolutional networks on graph-structured data

Table of Contents

Notation

  • henaff15_deep_convol_networ_graph_struc_data_e10e2b430f95617381cdd6d6b52aed29fb971dff.png denotes the number of nodes in the graph henaff15_deep_convol_networ_graph_struc_data_2de98136973021abb46a5a3fc1e4318bafb84264.png
  • henaff15_deep_convol_networ_graph_struc_data_fe7108f38f2db55db9cb7eee3f63077437a2e510.png represents the similarity matrix
  • henaff15_deep_convol_networ_graph_struc_data_b689cba8d7566f6adaf605a844e193a27e155078.png is the diagonal matrix of the form henaff15_deep_convol_networ_graph_struc_data_d29a75ca8ffaea4f234b1451854838a2c5f23cf0.png
  • henaff15_deep_convol_networ_graph_struc_data_9dfb630910b0b3d2a61cb5f1673b9adaa08fe150.png denotes the graph Laplacian
  • henaff15_deep_convol_networ_graph_struc_data_3bf4c35313913cf9c95a16513f62ef5ae7786255.png denotes the eigenvectors of henaff15_deep_convol_networ_graph_struc_data_9dfb630910b0b3d2a61cb5f1673b9adaa08fe150.png
  • henaff15_deep_convol_networ_graph_struc_data_65585df84336bbdfc4d5bfe4a183081e5bd179bb.png denotes the spectral multipliers
  • henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png denotes input
  • henaff15_deep_convol_networ_graph_struc_data_4a309801aa2babe507297312149a1723e03148ec.png denotes the Fourier Transform of henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png
  • henaff15_deep_convol_networ_graph_struc_data_00cee89d5264afc8d6543507af3d302628b27552.png denotes a graph convolution layer with henaff15_deep_convol_networ_graph_struc_data_094b02afce734f4ce51933d0093ef3d2da9f8123.png feature maps / channels
  • henaff15_deep_convol_networ_graph_struc_data_cdfb5d2706ae636cb207968cb8ec4441e57bb3b9.png denotes a fully connected layer with henaff15_deep_convol_networ_graph_struc_data_094b02afce734f4ce51933d0093ef3d2da9f8123.png hidden units
  • henaff15_deep_convol_networ_graph_struc_data_82ad3594b4ba02518ae5655e1d4025dbd1024953.png denotes the # of free parameters

Prereqs

Let henaff15_deep_convol_networ_graph_struc_data_a5177eee309f705d90af4a252c1cb0e6a1e3a05d.png be a graph with vertices henaff15_deep_convol_networ_graph_struc_data_79dc7b66c784a82e557ef3df794e82b67a292b17.png and edges henaff15_deep_convol_networ_graph_struc_data_fbe98aaf8359e7eed3ba031caeaf6a3c13ae8690.png. Let henaff15_deep_convol_networ_graph_struc_data_cb0a1040f2b77f33bf4b7df0b4d580c8dc9ab91e.png be a function of the vertices taking values in a ring henaff15_deep_convol_networ_graph_struc_data_6dd4ec21f92a21e77e43374b4c7fd1cc8c2234c6.png.

Then, the discrete Laplacian operator henaff15_deep_convol_networ_graph_struc_data_dc844651ed5589f123223a58245001884fe7ef68.png acting on henaff15_deep_convol_networ_graph_struc_data_2a275ba57b65332c8eb71ed5f6713abb5db0e66b.png is defined by

henaff15_deep_convol_networ_graph_struc_data_4ffb9fe68b45689e80fcfabb479190d8a15415df.png

where henaff15_deep_convol_networ_graph_struc_data_05a9bb367330a21ffdeda41292446dae5d8aea7d.png is the graph distance between vertices henaff15_deep_convol_networ_graph_struc_data_fe480f547555026d210b55b5d4ef758235f32832.png and henaff15_deep_convol_networ_graph_struc_data_ebac26f7eba81eb516f423f028596d8e6018aa7a.png, or for a weighted graph:

henaff15_deep_convol_networ_graph_struc_data_cfa3880488ce8627b39508e967b313ecdceaf892.png

where henaff15_deep_convol_networ_graph_struc_data_88c3c96e4177142152da60e77dbe8f57889b12c8.png is the weight value on th edge henaff15_deep_convol_networ_graph_struc_data_12c81491d85a844d19aefc0ab61a970a6780ab78.png.

Thus, this is a sum over the nearest neighbors of the vertex henaff15_deep_convol_networ_graph_struc_data_ebac26f7eba81eb516f423f028596d8e6018aa7a.png.

For a graph of a finite number of edges and vertices, this definition is identical to the graph Laplacian.

Spectral networks

  • Generalizes a conv. net through Graph Fourier Transform, which is in turn defined via a generalization of the Laplacian operator on the grid to the graph Laplacian

Let henaff15_deep_convol_networ_graph_struc_data_fe7108f38f2db55db9cb7eee3f63077437a2e510.png be a henaff15_deep_convol_networ_graph_struc_data_4345c31c4feb55aa8ad2b29c0fb2f160026b7ff0.png similiarity matrix representing an undirected graph henaff15_deep_convol_networ_graph_struc_data_2de98136973021abb46a5a3fc1e4318bafb84264.png, and let

henaff15_deep_convol_networ_graph_struc_data_3720ef963350f376a1a4550cf340f4711be9a2cd.png

be it's (normalized) graph Laplacian with henaff15_deep_convol_networ_graph_struc_data_015d5a8ef99cb41fcb71f32e4a18d3ba7e890df3.png and eigenvectors henaff15_deep_convol_networ_graph_struc_data_3bf4c35313913cf9c95a16513f62ef5ae7786255.png.

Then a graph convolution of input signals henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png with filters henaff15_deep_convol_networ_graph_struc_data_bed561b338628a088ae69301d4bba9fd83a70bd2.png on henaff15_deep_convol_networ_graph_struc_data_2de98136973021abb46a5a3fc1e4318bafb84264.png is defined by

henaff15_deep_convol_networ_graph_struc_data_16508340514cd65adb870ddce38588aad618fcb7.png

where henaff15_deep_convol_networ_graph_struc_data_9614489c6ea0bf61e8d0d12bf6f5e161c9486733.png represents a point-wise product, and henaff15_deep_convol_networ_graph_struc_data_7083259f29256d7f0845c7bc3801223eabf76ba4.png the convolution operation, which is defined for a graph as above.

  • Unitary matrix henaff15_deep_convol_networ_graph_struc_data_5760e806c8eb938d6a2563d076feec6ab9f9cafc.png plays the role of the Fourier Transform in henaff15_deep_convol_networ_graph_struc_data_de0b57391ed8b0d9becf399c343de2bf83467ce1.png
  • In the case where henaff15_deep_convol_networ_graph_struc_data_fe7108f38f2db55db9cb7eee3f63077437a2e510.png represents the lattice, from the definition of henaff15_deep_convol_networ_graph_struc_data_9dfb630910b0b3d2a61cb5f1673b9adaa08fe150.png we recover the discrete Laplacian operator henaff15_deep_convol_networ_graph_struc_data_dc844651ed5589f123223a58245001884fe7ef68.png
  • Laplacian commutes with the "translation operator", which is diagonalized in the Fourier basis
  • Follows that eigenvectors of henaff15_deep_convol_networ_graph_struc_data_dc844651ed5589f123223a58245001884fe7ef68.png are given by the DFT matrix

Thus (apparently), learing filters on a graph thus amounts to learning spectral multipliers henaff15_deep_convol_networ_graph_struc_data_65585df84336bbdfc4d5bfe4a183081e5bd179bb.png

henaff15_deep_convol_networ_graph_struc_data_495fc4a72e55d903070c7cbef9b01db3a0a09627.png

Multi-channel input

If henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png is a signal with henaff15_deep_convol_networ_graph_struc_data_f75d7681f9d0acecef24eb637ee201aa5b39199a.png input channels and henaff15_deep_convol_networ_graph_struc_data_e10e2b430f95617381cdd6d6b52aed29fb971dff.png locations, we apply the transformation henaff15_deep_convol_networ_graph_struc_data_5760e806c8eb938d6a2563d076feec6ab9f9cafc.png on each channel, and then use multipliers henaff15_deep_convol_networ_graph_struc_data_5cfb2eecf0b7db1acbd1571a02b1abf69a1c679e.png (which is a matrix, rather than a vector as for single-channel).

Expressing spatial localization of filters

  • Seek to express spatial localization of filters in terms of their spectral multipliers
  • In the grid (NOT a graph), smoothness in the "frequency domain" corresponds to the spatial decay, since

    henaff15_deep_convol_networ_graph_struc_data_61128003f38c2b9bd70b9febdf8b76235e03bd6e.png

    where henaff15_deep_convol_networ_graph_struc_data_4a309801aa2babe507297312149a1723e03148ec.png is the Fourier transform of henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png.

    • Other paper suggests similiar approach; using a smoothing kernel henaff15_deep_convol_networ_graph_struc_data_2f165a391b91b9672fb287118fc220d0ae88f1fe.png, such as splines, and searching for spectral multipliers of the form

      henaff15_deep_convol_networ_graph_struc_data_0fd17b7965dc05724fb3c6fd61ec42321cd73ec5.png

Algorithm

  1. Given GTF matrix henaff15_deep_convol_networ_graph_struc_data_5760e806c8eb938d6a2563d076feec6ab9f9cafc.png, interpolation kernel henaff15_deep_convol_networ_graph_struc_data_e0d338c35ccdc1e620f4e3958e6572de918c6d7f.png, weights henaff15_deep_convol_networ_graph_struc_data_fe480f547555026d210b55b5d4ef758235f32832.png.
  2. Forward Pass:
  3. Fetch input batch henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png and gradients w.r.t. outputs henaff15_deep_convol_networ_graph_struc_data_fb1268dffea8cc6b3cd20b272672c1c948c5e83b.png
  4. Compute interpolated weights henaff15_deep_convol_networ_graph_struc_data_21dead4a24081be825dafe817308bbf90b95a03c.png
  5. Compute output: henaff15_deep_convol_networ_graph_struc_data_d76a8ed053f2b007a8b86c514f399d83042cc842.png
  6. Backward Pass:
  7. Compute gradient w.r.t. input: henaff15_deep_convol_networ_graph_struc_data_e7c78ae6eb96cdf9a924137d76f6ed803259198a.png
  8. Compute gradient w.r.t. interpolated weights: henaff15_deep_convol_networ_graph_struc_data_0cc7ff3890a73047fe4cdc7e5bd457cf7155f0c4.png
  9. Compute gradient w.r.t. weights henaff15_deep_convol_networ_graph_struc_data_3fca1f1129eb645fb1839f43eab1fa95caf6b018.png

DONE What's the "translation operator" on a graph?

Surely the "translation operator" is just henaff15_deep_convol_networ_graph_struc_data_3c314f80373742988ad542a6d4ce66a111b17847.png.

DONE Better understand what the Laplacian operator henaff15_deep_convol_networ_graph_struc_data_dc844651ed5589f123223a58245001884fe7ef68.png is on a graph