Venue: ICLR 2017 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
This paper discusses ways to enforce invariance in neural networks using weight sharing.  The authors formalize a way for feature functions to be invariant to a collection of relations and the main invariance studied is a “set-invariant” function, which is used in an anomaly detection setting and a point cloud classification problem.  

“Invariance” is, at a high level, an important issue of course, since we don’t want to spend parameters to model spurious ordering relationships, which may potentially be quite wasteful and I like the formalization of invariance presented in this paper.  However, there are a few weaknesses that I feel prevent this from being a strong submission.  First, the exposition is too abstract and this paper could really use a running and *concrete* example starting from the very beginning.

Second, “set invariance”, which is the main type of invariance studied in the paper is defined via the author’s formalization of invariance, but is never explicitly related to what I might think of as “set invariance” — e.g. to permutations of input or output dimensions.  Explicitly defining set invariance in some other way, then relating it to the  “structural invariance” formulation may be a better way to explain things.  It is never made clear, for example, why Figure 1(b) is *the* set data-structure.

I like the discussion of compositionality of structures (one question I have here is: are the resulting compositional structures are still valid as structures?).  But the authors have ignored the other kind of compositionality that is important to neural networks — specifically that relating the proposed notion of invariance to function composition seems important — i.e. under what conditions do compositions of invariant functions remain invariant?  And  It is clear to me that just by having one layer of invariance in a network doesn’t make the entire network invariant, for example.  So if we look at the anomaly detection network at the end for example, is it clear that the final predictor is “set invariant” in some sense?  

Regarding experiments, there are no baselines presented for anomaly detection.  Baselines *are* presented in the point cloud classification problem, but the results of the proposed model are not the best, and this should be addressed.  (I should say that I don’t know enough about the dataset to say whether these are exactly fair comparisons or not).  It is also never really made clear why set invariance is a desirable property for a point cloud classification setting.  As a suggestion: try a network that uses a fully connected layer at the end, but uses data augmentation to enforce set invariance.  Also, what about classical set kernels?

Other random things:
* Example 2.2: Shouldn’t |S|=5 in the case of left-right and up-down symmetry?
* “Parameters shared within a relation” is vague and undefined.
* Why is “set convolution” called “set convolution” in the appendix?  What is convolutional about it?
* Is there a relationship to symmetric function theory?

review_title: Interesting formalization of invariance in neural networks, but too abstract and weak experimental results

final_score: rating: 5: Marginally below acceptance threshold
review_content: Pros : 
- New and clear formalism for invariance on signals with known structure
- Good numerical results

Cons :
- The structure must be specified.
- The set structure dataset is too simple
- There is a gap between the large (and sometimes complex) theory introduced and the numerical experiments ; consequently a new reader could be lost since examples might be missing

Besides, from a personal point of view, I think the topic of the paper and its content could be suitable for a big conference as the author improves its content.  Thus, if rejected, I think you should not consider the workshop option for your paper if you wish to publish it later in a conference, because big conferences might consider the workshop papers of ICLR as publications. (that's an issue I had to deal with at some points)
review_title: A promising work!

final_score: rating: 6: Marginally above acceptance threshold
review_content: Pros:
* Part of the paper addresses an industrially important topic, namely how to make deep networks work properly on point clouds, i.e. in many (most?) potential applications they should be invariant to permutations of the points within the cloud, as well as rigid transformations of the cloud (depends on the application).
* The authors propose a formalism for dealing with compositions of different kinds of invariance.

Cons:
* For me the explanation of the generalization is really hard to follow. For me, the paper would be stronger if were less broad, but went into more depth for the permutation-invariance case.
* It is very easy to sit down and come up with network structures that are permutation invariant. It seems the author tried a few networks in the family (a few different point cloud sizes, a couple options for the number of parameters, averaging vs. max in the set, dropout vs. no dropout), but unless the space is more completely and systematically explored, there's not much reason for a practitioner to use the proposed structure vs. some other random structure they cook up that is also permutation invariant. i.e. what about just using a FC layer that is shared between the points instead of your three "set invariant" layers? Seems simpler, more general, and also permutation invariant...
* It is not clear to me how valuable the author's definition of "minimally invariant" is. Is a sufficiently large composition of "set invariant" layers a universal approximator for permutation invariant functions?
* I'm concerned that proposed "set invariant layer" might be strongly variant to spatial transformations, as well as vulnerable to large outliers. In particular there is a term that subtracts a corner of the clouds bounding box (i.e. the max over set operator inside the first layer), before the cloud goes through a learned affine transform and pixelwise nonlinearity. Seems like that could saturate the whole network...

I'm reviewing with low confidence, because there's a chance the formalism in the first part of the paper is more valuable than I realize; I haven't fully understood it. 
review_title: Excellent choice of topic, but more work is needed for the results to be actionable.

final_score: rating: 7: Good paper, accept
review_content: This review is only an informed guess - unfortunately I cannot assess the paper due to my lack of understanding of the paper. 
I have spent several hours trying to read this paper - but it has not been possible for me to follow - partially due to my own limitations, but also I think due to an overly abstract level of presentation. The paper is clearly written, but in the same way that a N. Bourbaki book is clearly written.

I would prefer to leave the accept/reject decision to the other reviewers who may have a better understanding - even if the authors had made a serious mistake, I would not be able to tell. My proposal is positive because the paper is apparently clearly written and the empirical evaluation is quite promising. But some effort will be needed in order to address the broader audience that could potentially be interested in the topic. 

I therefore would like to provide feedback only at the level of presentation. 

My main source of problems is that the authors do not try to ground their abstract formalism with concrete examples; when the examples show up it is by "revelation" rather than by explaining how they connect to the previous concepts. 

The one example that could unlock most people's understanding is how convolution, or inner product operations connect with the setting described here. For what I know convolution is tied with space (or time) and is understood as an equivariant operation - shifting the signal shifts the output. 
It is not explained how the '(x, x')' pairs used by the authors in order to build relations, structures and then to define invariance relate to this setting. 
Going from sets, to relations, to functions, to operators, and then to shift-invariant operators (convolutions) involves many steps, and some hand-holding is needed.

Why is the 3x3 convolution associated to 9 relations? 
Are these relations referring to the input at a given coordinate and its contribution to the output? (w_{offset} x_{i-offset})? In that case, why is there a backward arrow from the center node to the other nodes? And why are there arrows across nodes? 
What is a Cardinal and what is a Cartesian convolution in signal processing terms? (clearly these are not standard terms). 
Are we talking about separable filters? 
What are the X and Square symbols in Figure 2? And what are the horizontal and vertical sub-graphs standing for? What is x_1 and what is x_{11},x_{1,2},x_{1,3} and what is the relationship between them?

I realize that to the authors these questions may seem to be trivial and left as  homework for the reader. But I think part of publishing a paper is doing a big part of the homework for the readers so that it becomes easy to get the idea. 

Clearly the authors target the more general case - but spending some time to explain how the particular case is an instance of the the general case would be a good use of space. 

I would propose that the authors explain what are  x, x_{I}, and x_{S} for the simplest possible example, e.g. convolving a 1x5 signal with a 1x3 filter, how the convolution filter parameters show up in the function f, as well as how the spatial invariance (or, equivariance) of convolution is reflected here. 
review_title: interesting topic, but hard to follow for a non-expert 

final_score: rating: null
review_content: If I understand correctly, one issue with the invariance to permutation of the graph is that one can loose discriminative information (example 4.3). Might it be possible to recover the loss of information due to the averaging?

I understand why one needs a set structure for the set anomaly detection, but not for the point cloud detection. Indeed, in the anomaly detection case, the objective of the problem is to seprate the set E of faces into E\{x} and {x} where x is the anomaly, and E\{x} is invariant by permutations. But, in the point cloud detection, I would have expected the final objective to be invariant by any permutations of the points. I guess I am doing a logical error, could you correct me? Is it to avoid discriminability issues? Why did you chose this graph? In this case, can we interpret your model as a graph convolution, with the edges at x being {(x,x'),x'\neq x}?

If the relational dependencies are not given, could they be learned?

Thanks.
review_title: Set structure questions

Meta-review: This paper studies neural models that can be applied to set-structured inputs and thus require permutation invariance or equivariance. After a first section that introduces necessary and sufficient conditions for permutation invariance/equivariance, the authors present experiments in supervised and semi-supervised learning on point-cloud data as well as cosmology data.
 
 The reviewers agreed that this is a very promising line of work and acknowledged the effort of the authors to improve their paper after the initial discussion phase. However, they also agree that the work appears to be missing more convincing numerical experiments and insights on the choice of neural architectures in the class of permutation-covariant. 
 
 In light of these reviews, the AC invites their work to the workshop track. 
 Also, I would like to emphasize an aspect of this work that I think should be addressed in the subsequent revision.
 
 As the authors rightfully show (thm 2.1), permutation equivariance puts very strong constraints in the class of 1-layer networks. This theorem, while rigorous, reflects a simple algebraic property of matrices that commute with permutation matrices. It is therefore not very surprising, and the resulting architecture relatively obvious. So much so that it already exists in the literature. In fact, it is a particular instance of the graph neural network model of Scarselli et al. '09 (http://ieeexplore.ieee.org/abstract/document/4700287/) when you consider a complete graph, which has been used in the setup of full set equivariance for example in 'Learning Multiagent communication with backpropagation', Sukhbaatar et al NIPS'16; see also 'Order Matters: sequence to sequence for sets', Vinyals et al. https://arxiv.org/abs/1511.06391. 
 The general question of how to model point-cloud data, or more generally data defined over graphs, with neural networks is progressing rapidly; see for example https://arxiv.org/abs/1611.08097 for a recent survey.
 
 The question then is what is the contribution of the present work relative to this line of work. The authors should answer this question explicitly in the revised manuscript, either with a new application of the model, or with theory that advances our understanding of these models, or with new numerical applications.
Decision: Invite to Workshop Track