Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper introduces the “open-world feature extrapolation” setting where models are trained on a set of features but introduced to additional features as time goes on or at deployment. This is a reasonable assumption in practice, as ML frameworks in practice are constantly updated with new items (such as recommender systems with new products, new users). Naively, one could retrain on the existing features and the new features, but this is time-consuming and infeasible for online settings; one could also retrain on solely the new features but this poses the risk of forgetting existing features or overfitting.

To address this, the paper introduces FATE, a framework that can handle new features at test time without retraining the model. A neural network can be viewed as an embedding layer plus a classifier. The embedding layer maps the input features x to a H-dimensional hidden vector z, so the technical challenge is to find a weight embedding (for x to z) for new features, given existing features. The paper uses GNN message-passing over a feature-data graph (feature nodes and instance nodes) to learn these. To train the model, two approaches are presented – self-supervised learning where a portion of the features are withheld and whose embeddings are estimated by the model using the other features; and inductive learning where a k-subset of the features are sampled.

The paper presents a theoretical result on the generalization error (under the inductive learning approach) as well as experiments comparing against baselines that either incorporate the new features in other ways or do not at all.
main_review: Originality: this paper’s setting is distinct from other settings with shifts and expansions in distributions and/or their support. It does seem similar to the cold start problem in recommendation systems and “tail” entities in problems like named entity disambiguation  (perhaps with a stricter requirement of no retraining, vs in general how to handle rare items). In all of these cases there are some “features” that are rare and thus may not be seen at training. In the NLP space, something like [1]  aims to infer embeddings of rare words given embeddings of frequent words, while [2] tackles the tail by leveraging additional reasoning patterns. There has also been work in the zero-shot setting [3, 4], and in recommendation systems [5] uses a bipartite user-item graph and GNNs for the cold start problem. I thus recommend having more related work in the above vein comparing both methods and motivation.

[1] Timo Schick and Hinrich Schütze. 2020. Rare words: A major problem for contextualized embeddings and how to fix it by attentive mimicking. In Proceedingsof the AAAI Conference on Artificial Intelligence, Vol. 34. 8766–8774.

[2] Laurel Orr, Megan Leszczynski, Simran Arora, Sen Wu, Neel Guha, Xiao Ling,and Christopher Re. 2020. Bootleg: Chasing the Tail with Self-Supervised Named Entity Disambiguation. arXiv preprint arXiv:2010.10363(2020).

[3] Lajanugen Logeswaran, Ming-Wei Chang, Kenton Lee, Kristina Toutanova, Ja-cob Devlin, and Honglak Lee. 2019. Zero-shot entity linking by reading entity descriptions. arXiv preprint arXiv:1906.07348(2019).

[4] Tao Wu, Ellie Ka-In Chio, Heng-Tze Cheng, Yu Du, Steffen Rendle, Dima Kuzmin,Ritesh Agarwal, Li Zhang, John Anderson, Sarvjeet Singh, et al. 2020. Zero-Shot Heterogeneous Transfer Learning from Recommender Systems to Cold-Start Search Retrieval. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2821–2828.

[5] Bowen Hao, Jing Zhang, Hongzhi Yin, Cuiping Li, and Hong Chen. 2021. Pre-training Graph Neural Networks for Cold-Start Users and Items Representation. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining. 265-273.

Quality: I looked over the theory and experiments quickly and most of it appeared correct. I have a few questions about the generalization error result. 
1) Theorem 1 describes the generalization error on the test data with new features. I am guessing this is reflected through the expectation in eq 4 being over the feature set F, in addition to (X, Y). However, I don’t completely understand how the proofs in the Appendix address randomness over F.
2) Why do the bounds not scale with the sample size for each X_m? (i.e. where is |I| or N?)
3) Why does the stability parameter \gamma increase with more iterations? It seems unusual to me that the dependency on d scales exponentially with the number of iterations T.
4) Theorem 1 and Table 4 suggest that the number of raw features k plays an important role, but it is not clear where k is in the bound. 


Clarity: this paper was enjoyable to read aside from a few grammatical errors that can be fixed easily.

Significance: the paper tackles a significant problem. As we think about models “in-the-wild” that deal with dynamic data, it is crucial to understand how to continuously incorporate new information efficiently and accurately.

limitations_and_societal_impact: The authors have adequately addressed limitations and societal impacts.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper studies the “open-world” feature extrapolation problem and develops a neural model that can extrapolate to new features without any retraining. They provide a graph model for this problem, and a few standard theoretical results.
main_review: The idea in this work is interesting, though the actual setup comes with many assumptions and limitations. It seems the contribution of this work is more on the problem side, as the proposed approach is simply based on standard methods. Also, there are some works that seem closely related in spirit, “Latent Graph Predictor Factorization Machine (LGPFM) for modeling feature interactions weight”, “Deep Relational Factorization Machines”, “Feature Interaction-aware Graph Neural Networks”. There are likely others that are also missing from the related work, and should be discussed, and the differences clarified. What is the time and space complexity? And how does it compare to other related methods?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper formulates the feature extrapolation problem and proposes a novel framework to tackle it. By definition in the paper, the feature extrapolation problem emerges when, during test time, feature space extends beyond training set either due to the collection of new raw features or feature values going beyond its range. To handle such problems without requiring retraining a model in the occurrence of new features, the authors proposes to jointly train the backbone network, which performs the main classification task, and a GNN, which serves as a middleman to map the raw features to the input of the backbone network. This GNN is trained to find the co-occurrence relationships among feature values and extrapolate the representation for new features. Theoretical analysis was conducted to study the generalization error of the learning algorithm. Empirical study was carried out to demonstrate the effectiveness of the framework in solving tasks from real-world application.
main_review: Overall, the paper is very well written and easy to follow. Formulation of the problem, proposed model and learning procedure are all clearly stated with minimal ambiguity. The proposed method is a reasonable solution to the problem. Empirical study shows a clear picture that the proposed method can utilize new features in test time without retraining of the backbone network.

The feature extrapolation problem formulated in this paper is quite interesting. The proposed method can handle two ways that feature space of test data extends beyond training data (1) there is a new feature available on test data; and (2) the range of values of an existing feature extend beyond its range on training data. Both cases may emerge in reality and the proposed method is useful to address such problems.

It seems that bin size used to quantizing continuous features plays a role in deciding the sparsity of the feature adjacency matrix which further affects the message passing on GNN. A finer-grained quantization preserves more information but leads to a sparser adjacency matrix. The paper can be strengthened by discussing such trade-off and its impact on the performance.

Permutation invariant aggregation provides the advantage that the final classifier network may consume feature vectors of variable lengths. Yet, this position information is lost during this transformation. In fact, when raw features are discretized and converted to embeddings, we also lost the knowledge about whether two feature embeddings come from the same raw feature.

Figure 5: the caption says “​​We mark observed features with red and the remaining ones with blue nodes.” There’s no blue nodes. It's probably a typo.

It would be great to add error bars in Figure 4 to show the significance of difference between different methods.







limitations_and_societal_impact: As stated in the paper, this work focuses on handling attribute features. The proposed method does not extend to problems in domains such as NLP and computer vision straightforwardly.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles the unseen features with their extrapolation method from seen features, which is an important problem in machine learning.
* The authors first formulate the problem of open-world feature extrapolation that aims to deal with features unobserved at training while observed at inference.
* The authors propose to generate embedding for new features with inductive graph neural networks, where the graph-structured is constructed from features and instances of the observed training data.
* The authors theoretically analyze the generalization gap of the proposed method, and show that the number of features and the size of subsets for training data are important ingredients.
main_review: ### Strengths
* The problem of open-world feature extrapolation the authors introduce is a novel, interesting, and important direction for practical machine learning systems, since many new features are emerging in the real-world.
* The authors solve the proposed problem with a graph neural network (GNN) that can consider relevant seen features for extrapolating unseen features during neighborhood aggregation steps, which is convincing for tackling unseen. To be more specific, the authors divide the matrix multiplication from input features to latent features into two steps, in which I enjoy the concept of feature embedding with its replacing method using GNNs.
* The authors make an effort to analyze the generalization behavior of the proposed method, which is quite related to the empirical results.
* The proposed method shows performance improvements from baselines on two different datasets.
* The paper is well written, and the figures support the contents of the main paper well.

### Weaknesses
* The concept of extrapolating knowledge from seen to unseen with GNNs is not new, and there are few relevant work that the authors need to discuss (See Related Work below for details).

### Related Work
* These two relevant works [1, 2] should be discussed.
  * The first work [1] aims to embed unseen knowledge with inductive and transductive GNNs, while using meta-learning to simulate the unseen during training, compared to the authors' training schemes that divide or sample the whole observed training set to make the unseen.
  * The second work [2] aims to represent missing values in features with graph neural networks, while not tackling disjoint feature sets from training as the authors' one though.

### Clarity
* This paper is overally well written, however, there is an unclear part: how can we use the updated feature embeddings from GNNs $\hat{W}$ in the embedding layer. When I read the text in line 155, I think all the embeddings from GNN $\hat{W}$ are used as parameters for the embedding layer. However, the sentence in line 172 describes that the only used parameters for the embedding layer are the updated embeddings of masked features, not of all features. However, in line 181, I feel that the inductive learning scheme uses all updated embeddings, which is different from the description of line 172.

### Suggestions (or Questions)
* Most of the results in section 4.2 are in the supplementary file. It is better to state the location of the results, when the reference letters (e.g., Fig. 6) are given. At first glance, I think that the Figure 6 is in the main paper.
* In line 88, is there any reason to convert a continuous feature to a discrete one? I think this scheme results in the loss of information.

### Typo
* In the caption of Figure 1, (b) Oue approach.
* In Figure 5, there is no blue color on the visualization example, while the caption mentions blue.

---

[1] Baek et al. Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction. NeurIPS 2020.

[2] You et al. Handling Missing Data with Graph Representation Learning. NeurIPS 2020.
limitations_and_societal_impact: The authors clearly outline the limitation and potential societal impact of their work in the conclusion section, and I'm satisfied with them.
review_title: null

Meta-review: Overall, this paper’s reviews have reached a consensus. Three of the reviewers wish for the paper to be accepted, in particular after some high-quality clarifications from the authors. I agree with this decision. There is only one reviewer who is opposed, but that reviewer’s disagreement is based on a potential similarity between the paper and previous work, which the authors have successfully dispelled. I assume the reviewer is comfortable with this response; in any case, there are clearly sufficient distinctions from prior work and sufficient novelty here. 

From my own read, I think this paper identifies a fairly neat problem setting (ie, feature space expansion at test time) and makes it concrete, then offers reasonable solutions to it. The problem is a practical one, but it hasn’t been tackled in this exact form before (at least, to the best of my knowledge). While theoretically the problem could be posed in a far more general framework on domain shift, it would be hard to find a good solution. The current identification leads to some pretty nice results, and it could serve to drive a bunch of new research questions and solutions.

Decision: Accept (Poster)