Matching Convolutional Neural Networks without Priors about Data
Carlos Eduardo Rosar Kos Lassance Jean-Charles Vialatte Vincent Gripon

Slowdown of the surface diffusion during early stages of bacterial colonization
    C. Cassier-Chauvat
    December 30, 2023
===============================================================================




  
  
  
  
  
  We propose an extension of Convolutional Neural Networks (CNNs) to graph-structured data, including strided convolutions and data augmentation on graphs.
  Our method matches the accuracy of state-of-the-art CNNs when applied on images, without any prior about their 2D regular structure.
  On fMRI data, we obtain a significant gain in accuracy compared with existing graph-based alternatives.




§ INTRODUCTION


Convolutional Neural Networks (CNNs) <cit.> have been able to surpass traditional machine learning methods in various image based tasks <cit.>. 
This is possible as they exploit the learning capabilities of deep neural networks while also taking advantage of the intrinsic regular 2D structure of the data. But when data lacks regular structure <cit.>, there is no natural notion of convolutions, stride/pooling or data augmentation. Such irregularities occur in various domains covering social networks to neuroscience, internet of things, citation graphs, point cloud manifolds…The question of developing solutions that are counterparts of CNNs in irregular domains has recently been a very active field of research.

In this paper we introduce a method that extends CNNs to irregular domains. Contrary to many alternative works, we ensure that our proposed methodology matches the performance of CNNs when applied to regular domains, even without knowledge of the underlying structure. To that end, we infer a graph to represent the topology of the data. From this graph, we infer translations. The weight-sharing schemes of our proposed convolutional layers are then defined based on those translations, as well as data-augmentation and stride.

At the end of the process, the obtained architecture is very similar to a traditional CNN and can thus be trained using the same routines and libraries, and equivalent computational and memory footprints. We first perform experiments on the CIFAR-10 dataset without knowledge about the fact it is made of images. We show that our method is able to reach performance similar to state-of-art CNNs, thus implying that – at least for regular domains – it allows to completely leverage the underlying structure. Then, we perform experiments on an irregular neuroscience dataset and demonstrate a gain in performance compared with completely unstructured deep learning methods and alternative graph-based CNNs.






§ RELATED WORK


Deep learning on graphs can refer to three distinct problems: classification of graphs, of nodes in a graph, or of signals on graphs. In this paper, we are interested only in the latter task that is to leverage the graph structure of signals in deep learning models, by redefining the convolutional layer. Such methods have already been proposed in the literature. We distinguish two categories of solutions.

In the first category, convolution is defined as pointwise multiplication in the spectral domain of the graph, which is defined using the Laplace-Beltrami operator <cit.>. This method originated the first spectral graph CNNs <cit.>. An approximation of the spectral graph convolution using Chebychev polynomials has been proposed <cit.>, and has the advantage to be both faster and localized in the vertex domain. Another variant with Cayley polynomials <cit.> also localizes the convoluted filter in the spectral domain.

In the second category, convolution is defined directly in the vertex domain. These works were originally motivated by chemistry datasets <cit.>. Convolution is defined as a function of the kernel weights and neighboring vertices (the receptive field), usually based on dot products. As such, it retains the property of being localized and of sharing weights. But there remains the need to specify how the shared weights are allocated in this receptive field <cit.>. This allocation can depend on an arbitrary order <cit.>, on the number of hops <cit.>, on both vertices and their neighbors <cit.>, on another learned kernel <cit.>, on an attention mechanism <cit.>, on pattern identification <cit.>, or on translation identification <cit.>. All these methods also differ in the function that maps the receptive fields and the weight kernel to the neuron's outputs. But in the end, these definitions overlap. That is why some authors have proposed unified frameworks <cit.>.



We tackle another point. Given a dataset with no structure between the features of the input vectors, our goal is to demonstrate that we can still define meaningful convolutional, stride/pooling layers. The first step to determine whether the results obtained on unstructured data is satisfactory or not is to stress it on regular data while disregarding its structure. We deal with this step on image datasets. Even though some previous works match the performance of CNNs on image datasets, ours is the first that can do it without structure prior.



§ METHODOLOGY



Our method is based on <cit.>, where the authors have introduced a way to infer a graph from training signals, then translations from the obtained graph to design ad-hoc CNNs. We extend this approach and design strided convolutions along graph downscaling, data augmentation and convolutions on downscaled graphs. Figure <ref> depicts the proposed method.





 §.§ Background





Define a graph G = ⟨ V, E ⟩ with V the set of vertices, and E ⊆V2 the set of edges. We suppose the graph is connected, as conversely the process can be applied to each connected component of G. We denote by d the max degree of the graph and n = |V| the number of vertices.

The authors of <cit.> propose to inductively define translations as functions from vertices to vertices as follows:

Candidate-translation

  A candidate-translation is a function ϕ: U → V, where U ⊂ V and such that:
  
  
  * ϕ is injective:

  ∀ v,v' ∈ U, ϕ(v) = ϕ(v') ⇒ v = v',
  
  * ϕ is edge-constrained:

  ∀ v ∈ U, (v,ϕ(v)) ∈ E,
  
  * ϕ is strongly neighborhood-preserving:

  ∀ v,v' ∈ U, (v,v')∈ E ⇔ (ϕ(v),ϕ(v')) ∈ E.

  


The cardinal |V-U| is called the loss of ϕ.
Two candidate-translations ϕ and ϕ' are said to be aligned if ∃ v∈ V, ϕ(v) = ϕ'(v).
We define N_r(v) as the set of vertices that are at most r-hop away from a vertex v ∈ V.


Translation

  A translation in a graph G is a candidate-translation such that there is no aligned translation with a strictly smaller loss, or is the identity function.



Note that if the graph is a 2D grid, obtained translations are exactly natural translations on images <cit.>.


Local translation

A local translation of center v ∈ V is a translation in the subgraph of G induced by N_2(v), that has v in its definition domain.



As local translations can't be used to design data augmentation and convolutions on downscaled graphs, we also design proxies to global translations.


Proxy-translations

A family of proxy-translations (ψ_p)_p=0,..κ-1 initialized by v_0 ∈ V is defined algorithmically as follows:


  * We place an indexing kernel on N_1(v_0) i.e.
 N_1(v_0) = {v_0, v_1, ..., v_κ-1} with ∀ p, ψ_p(v_0) = v_p,

  * We move this kernel using each local translation ϕ of center v_0: ∀ p, ψ_p(ϕ(v_0)) = ϕ(v_p),

  * We repeat 2) from each new center reached until saturation. If a center is being reached again, we keep the indexing that minimizes the sum of losses of the local translations that has lead to it.






 §.§ Efficiently Finding Translations



Finding translations is an NP-complete problem <cit.>, such that for large graphs the method is not suitable. 
In order to break down complexity, the authors of <cit.> propose to search for local translations. They also introduce approximate translations which we omit for the sake of simplicity, but the description would be similar. We describe in three steps how we efficiently find proxy-translations.


First step: finding local translations

For each vertex v ∈ G, we identify all local translations using a bruteforce algorithm. This process requires finding all translations in all induced subgraphs. There are n such subgraphs, each one contains at most d local translations. Finding a translation can be performed by looking at all possible injections from 1-hop vertices around the central vertex to any vertex that is at most 2-hops away. We conclude that it requires at most 𝒪(nd d^2(d+1)) elementary operations and is thus linear with the order of the graph. On the other hand, it suggests that sparsity of the graph is a key criterion in order to maintain the complexity reasonable.

Figure <ref> depicts an example of a grid graph and the induced subgraph around vertex v_0. Figure <ref> depicts all obtained translations in the induced subgraph.






Second step: using local translations to move a small localized kernel around G

Given an arbitrary[In practice we run several experiments while changing the initial vertex and keep the best obtained result.] vertex v_0 ∈ V, we place an indexing kernel on N_1(v_0) i.e. N_1(v_0) = {v_0, v_1, ..., v_κ-1}. Then we move it using every local translations of center v_0, repeating this process for each center that is reached for the first time. We stop when the kernel has been moved everywhere in the graph. In case of multiple paths leading to the same destination, we keep the indexing that minimizes the sum of loss of the series of local translations. We henceforth obtain an indexing of at most κ objects of N_1(v) for every v ∈ V.

This process is depicted in Figure <ref>. Since it requires moving the kernel everywhere, its complexity is 𝒪(n d^2).




Final step: identifying proxy-translations in G

Finally, by looking at the indexings obtained in the previous step, we obtain a family of proxy-translations defined globally on G. More precisely, each index defines its own proxy-translation. Note that they are not translations because only the local properties have been propagated through the second step, so there can exist aligned candidates with smaller losses. Because of the constraint to keep the paths with the minimum sum of losses, they are good proxies to translations on G.

An illustration on a grid graph is given in Figure <ref>. The complexity is 𝒪(nd). Overall, all three steps are linear in n.





 §.§ Extended Convolution Layers



Let (ψ_p)_p=0,..,κ-1 be the proxy-translations identified on G with the convention that ψ_0 = id is the identity function, and where κ is the number of weights in the indexing kernel.

The operation of the extended convolution layer centered on the vertex v ∈ V is defined as:


    𝐲_v = h(∑_p=0^κ-1w_p 𝐱_ϕ_p(v) + b)


where h is the activation function, b is the bias term, 𝐱_ = 0 and:

    {[ ϕ_p(v) = ψ_p(v)          ψ_p  v;    ϕ_p(v) = ∉ V                ;                 ]..


Note that we defined convolution layers using the formalism of proxy-translations, but they can also be defined using only the formalism of local translations <cit.>.



 §.§ Extended Data Augmentation


Once translations are obtained on G, one can use them to move training vectors, artificially creating new ones. Note that this type of data-augmentation is poorer than for images since no flipping, scaling or rotations are used.



 §.§ Extended Downscaling Layers


Downscaling is a tricky part of the process because it supposes one can somehow regularly sample vectors. As a matter of fact, a nonregular sampling is likely to produce a highly irregular downscaled graph, on which looking for translations irremediably leads to poor accuracy, as we noticed in our experiments.

We rather define the translations of the strided graph using the previously found proxy-translations on G.


First step: extended convolution with stride r



Given an arbitrary initial vertex v_0 ∈ V, the set of kept vertices V_↓ r is defined inductively as follows:


  * V_↓ r^0 = {v_0},

  * ∀ t ∈ℕ, V_↓ r^t+1 = V_↓ r^t ∪{v ∈ V, ∀ v' ∈ V_↓^t, v ∉N_r-1(v') ∃ v' ∈ V_↓ r^t, v ∈ N_r(v') }.


This sequence is nondecreasing and bounded by V, so it eventually becomes stationary and we obtain V_↓ r = lim_tV_↓ r^t. Figure <ref> illustrate the first downscaling V_↓ 2 on a grid graph. 

The output neurons of the extended convolution layer with stride r are V_↓ r.


Second step: convolutions for the strided graph

Using the proxy-translations on G, we move a localized r-hop indexing kernel over G. At each location, we associate the vertices of V_↓ r with indices of the kernel, thus obtaining what we define as induced _↓ r-translations on the set V_↓ r. In other words, when the kernel is centered on v_0, if v_1 ∈ V_↓ r is associated with the index p_0, we obtain ϕ_p_0^↓ r(v_0) = v_1. Subsequent convolutions at lower scales are defined using these induced _↓ r-translations similarly to Subsection C.









§ EXPERIMENTS



To validate our method we performed experiments with two different datasets, CIFAR-10 <cit.> and PINES fMRI dataset <cit.>. The code is available at https://github.com/brain-bzh/MCNNgithub.com/brain-bzh/MCNN.



 §.§ CIFAR-10


On the CIFAR-10 dataset, our models are based on a variant of a deep residual network, namely PreActResNet18<cit.>. We tested different combinations of graph support and data augmentation. For the graph support, we use either a regular 2D grid or either an inferred graph obtained by keeping the four neighbours that covary the most. Table <ref> summarizes out results. In particular, it is interesting to note that results obtained without any structure prior (91.07%) are only 2.7% away from the baseline using classical CNNs on images (93.80%). This gap is even smaller (less than 1%) when using the grid prior. Also, without priors our method significantly outperforms the others. 





 §.§ PINES fMRI



The PINES dataset consists of fMRI scans on 182 subjects, during an emotional picture rating task<cit.>. We fetched individual first-level statistical maps (beta images) for the minimal and maximal ratings from <https://neurovault.org/collections/1964/>, to generate the dataset. Full brain data was masked on the MNI template and resampled to a 16mm cubic grid, in order to reduce dimensionality of the dataset while keeping a regular geometrical structure. Final volumes used for classification contain 369 signals for each subject and rating. 

We used a shallow network. The results on Table <ref> show that our method was able to improve over CNNs, MLPs and other graph-based extended convolutional neural networks.






§ CONCLUSION


We proposed a new methodology that extends classical convolutional neural networks to irregular domains represented by a graph.
The methodology scales linearly well with the order of the graph. Moreover, training can be performed using existing libraries for deep learning.

We performed experiments and showed that our method is able to match performance of classical convolutional neural networks on images without explicit knowledge about the underlying regular 2D structure. It also significantly outperforms existing extended convolutional neural networks alternatives based on graphs.
We also demonstrated the ability of the method to adapt to slightly irregular domains by performing experiments on a neuroimage dataset.

However, the main limitation is that on highly irregular domains, the obtained translations aren't very helpful to design meaningful convolutions, especially if the degree of the graph varies a lot. Hence this requires to add constraints to the graph inferring step to obtain an exploitable graph if it is not.

Future work includes extending to highly irregular domains, which might require to revisit the definitions of translations. 



§ ACKNOWLEDGEMENTS


This work was funded in part with the support of Région Bretagne and computations were performed with the use of  Nvidia GPUs, courtesy of Nvidia.

IEEEtran


