I know that a neural-network architecture is mostly based on the problem itself and the types of input/output, but still - there's always a "square one" when starting to build one. So my question is - given a input dataset of MxN (M is the number of records, N is the number of features) and a C possible output classes - is there a thumb-rule to how many layers/units should we start with?
This question has been answered in detail on CrossValidated: How to choose the number of hidden layers and nodes in a feedforward neural network?
However, let me add my own two cents:
There is no magic rule for choosing the best neural network architecture, but if you can find an architecture someone has used to solve a similar problem this is often an excellent starting point.
The best places to look are official or unofficial examples using popular neural network libraries such as Keras, PyTorch, or Tensorflow, and architectures described in academic literature. keras/examples on github is a great resource.
These architectures were likely chosen after lots of trial and error, so most of the work will have been done for you.
I read a paper exploring the idea of using neural networks to design other neural networks, by exploring which configuration of nodes and layers was the most efficient.
Here's the page where you can download a PDF.
Following @Imran's answer, I found this paper in one of in the comments of the CrossValidated post he linked to. Besides an attempt to find the right architecture using Genetic Models (instead of using a rule-of-thumb), section 2.1 gives some theoretical bounds to how many hidden units should be in a one/two-hidden-layers system.
EDIT: I've tested this theorem, and found out that using Genetic Models is just as good as selecting a random architecture.