Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approach
Authors: Qitian Wu
Chenxiao Yang
Junchi Yan
Venue: NeurIPS 2021 Poster (2021)
Keywords: Open-World Extrapolation
Graph Representation Learning
Feature Embedding Learning
Graph Neural Networks

Abstract: We target open-world feature extrapolation problem where the feature space of input data goes through expansion and a model trained on partially observed features needs to handle new features in test data without further retraining. The problem is of much significance for dealing with features incrementally collected from different fields. To this end, we propose a new learning paradigm with graph representation and learning. Our framework contains two modules: 1) a backbone network (e.g., feedforward neural nets) as a lower model takes features as input and outputs predicted labels; 2) a graph neural network as an upper model learns to extrapolate embeddings for new features via message passing over a feature-data graph built from observed data. Based on our framework, we design two training strategies, a self-supervised approach and an inductive learning approach, to endow the model with extrapolation ability and alleviate feature-level over-fitting. We also provide theoretical analysis on the generalization error on test data with new features, which dissects the impact of training features and algorithms on generalization performance. Our experiments over several classification datasets and large-scale advertisement click prediction datasets demonstrate that our model can produce effective embeddings for unseen features and significantly outperforms baseline methods that adopt KNN and local aggregation.

Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approach
Qitian Wu, Chenxiao Yang, Junchi Yan"
Department of Computer Science and Engineering MoE Key Lab of Artificial Intelligence, Al Institute Shanghai Jiao Tong University
{echo740, chr26195, yanjunchi/ssjtu. eew.gjtt.uuuu..... edu cn
Abstract
We target open-world feature extrapolation problem where the feature space of input data goes through expansion and a model trained on partially observed features needs to handle new features in test data without further retraining. The problem is of much significance for dealing with features incrementally collected from different fields. To this end, we propose new learning paradigm with graph representation and learning. Our framework contains two modules: 1) backbone network (e.g.. feedforward neural nets) as lower model takes features as input and outputs predicted labels; 2) graph neural network as upper model Iearns message passing over feature-
extrapolate embeddings for new features data graph built from observed data. Based on our framework, we design two training strategies, a self-supervised approach and an inductive learning approach, to endow the model with extrapolation ability and alleviate feature-level wver-fitting. We also provide theoretical analysis on the generalization error on test data with new features, which dissects the impact of training features and algorithms on generalization performance. Our experiments over several classification datasets and large-scale advertisement click prediction datasets demonstrate that our model can produce effective embeddings for unseen features and significantly outperforms baseline methods that adopt KNN and local aggregation.
Introduction
Learning a mapping from observation x (a vector of attribute features) to label y is fundamental and pervasive problem in ML community, with extensive applications spanning from classifica- tion/regression tasks for tabular data to advertisement click prediction 23
38
1
37 27 item
recommendation 26 52
53 question answering 22 11 or AI more broadly. Existing ap-
proaches focus on fixed input feature space shared by training and test data. Nevertheless, practical MI. systems interact with a dynamic open-world where features are incrementally collected. For example, in eroommenderadvvertiseeene before for current prediction tasks. Also, with the advances of multi-modal recognition (45] and federated learning [D) it is requirement for model trained with partial features to incorporate new features from other fields for decision decision-making making on a target task.
systems, there often occur new user profile features unseen
A challenge stems from the fact that off-the-shelf neural network models cannot deal with new features without re-training on new data, As shown in Fig, ()) neural network builds mapping from input features to a hidden representation through a weight matrix in the first layer. Given new features as input, the network needs to be augmented with new weight parameters and cannot map the new features to desirable position in latent space if without re-training.
Junchi Yan is the corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

fectures
label
Training
Inference
memory
concept
embs
observation
age
age
F12
training date
P22
edo
festure's eeli
P32
edu
inome =7
test data
parcept ion
(2) deaiiaatioon on
(esoonn mg
deccaicn
(6) Limitation of noural network models for open-world feature extrapolation
(b) A new approach inspired by luman's thinking
Figure 1: (a) The open-world feature extrapolation problem is defined over training data with partial features and test data with augmented feature space. Existing neural models cannot deal with new features without re- re-training. (b) Oue approach has an analogy to thinking process in human's 's brain. Imagine person trained on using features age, to predict one's 's income and tested on test cases with a new feature edu. There are four processes from acquiring observation to giving final prediction.
However, model re- re-training would be tricky and bring up several issues. First, re-training a model with both previous and new features would be highly time-consuming and cannot meet the requirement for online systems. Alternatively, one can re-train a trained model only on new features, which will induce risks for over-fitting new data or forgetting previous data.
Different from machines, fortunately, humans are often equipped with the ability for extrapolating to unseen features and distill the knowledge in new information for solving a target task without any re-training on new data. The inherent gap between existing ML approaches and human intelligence raises a research question: Can we design a ML model that trained on one set of features and able to generalize to combine new unseen features for the same task without further training?
To find desirable solutions to this non-trivial question is challenging. Let us resort to how humans think and act in physical world scenarios. Imagine that we are well trained on predicting a person's 's income with one's s age and occupation from historical records. Now we are asked estimate the income of a new person with his/her age, occ. and education (a new feature). We can modularize the process in brain systems that distill and leverage the knowledge in new observations into four steps, as shown in Fig. [b). 1) Perception: the observations are recognized by our senses; 2) Abstraction: the perceived information is aligned with concepts our cognition; 3) Reasoning: we search similar concepts and observations in our memory to understand and absorb the new knowledge; 4) Decision: with new understanding and abstraction, we make final decisions for the prediction.
The above human's thinking process inspires the methodology in our paper where we propose a new learning paradigm for open-world feature extrapolation. Our proposed framework contains two modules: a backbone network, which can be a feedforward neural network, and graph neural network. The backbone network first maps input features to embeddings, which can be seen as perception from observation. 2) We then treat observed data matrix (each row represents a feature vector for one instance) as a feature-data bipartite graph. which explicitly define proximity and locality structures among features and instances. Then graph neural network is harnessed for neural message passing over adjacent features and instances in a latent space (abstraction). 3) The GNN will inductively compute embeddings for new features based on those of existing ones, mimicking the reasoning process from familiar concepts to new ones in our brain. 4) The newly obtained embeddings that capture both semantics and feature-level relations will be used to obtain hidden representations of new data with unseen features and make final decisions.
To endow the model with ability for extrapolation to new features, we propose two training algorithms, one by self-supervised learning and one by inductive learning. The proposed model and its learning algorithm can easily scale to large-scale dataset (with millions of features and instances) via mini- batch training. We also provide theoretical analysis on the generalization error on test data with new features, which allows us to dissect the impact of training features and algorithms on generalization performance. To verify our approach, we conduct extensive experiments on several real-world datasets, including six classification datasets from biology, engineering and social domains with diverse features, as well as two large-scale datasets for advertisement click prediction. Our model is trained on training data using partial features and tested on test data with a mixture of seen and unseen features. The results demonstrate that 1) our approach consistently outperform models not using new features for inference; 2) our approach achieves averagely 29.8% higher Accuracy than baseline methods using KNN, pooling or local aggregation for feature extrapolation; 3) our approach even exceeds models using incremental training new features, yielding average 4.1% higher Accuracy.
2

---

Our contributions are: 1) We formulate open-world feature extrapolation problem and show that it is feasible extend neural models for extrapolating to new features without re- re-training; 2) We propose a new graph-learning model and two training algorithms for feature extrapolation problem; 3) Our theoretical analysis shows that the generalization error for data with new features relies on the number of training features and the randomness in training algorithms; 4) We conduct comprehensive experiments and show the effectiveness, applicality and scalability of proposed method.
2 Methodology
We focus on attribute features input in this paper. An input instance is vector r; [rim 1d where each entry Tim denotes a raw feature (like age, occ., edu., etc.). If Tim is a discrete/categorical raw feature with R.m possible values, its space is integer set 10, 1,... R... 1}. rim is contin- uous one, a common practice is to convert it into a discrete feature within space {0, 1,... Rm -1 by evenly division
m= R
A or log transformation
2
We call R., as cardinality for m-th raw feature.
For Tim with cardinality Rm convert it into Rm -dimensional one-hot vector x;" where the unique I indexes the value. In this way, one can convert an input r, into a concatenation of one-hot vectors:
An effective way to handle attribute features is via one-hot encoding 13
24 17
X; = [x],,"
x where S Vm S d, x E {0,1) is a one-hot vector. (I)
Use Izj denote the j-th entry of x, and we call each Zij as feature in this paper. Assume D = Em=1 Rm denotes the number of features and, as reminder, d is the number of raw features.
We next give formal definition for oprn-world feature extrapolation problem in this paper: given training data {(x, yi)he,, where X; E Xer = {0. 1)P. ys E y and 1rr is a set of indices, we aim to learn model that can generalize to test data (xv, Me Ee where X E Xne- {0, 1) ye E y and Le another set indices. We term Xx, as training feature space and Xte as test feature space. We assume 1) the label space y is shared by training and test data, and 2) Xer Nee. i.c., test feature space is an extension of training feature space. The feature space expansion stems from two possible causes: 1) there appear raw features incrementally collected from other fields (i.c., d increases) or 2) there appear new values out of the known space of existing raw features (i.e., Rm increases).
2.1 Proposed Model
Our model contains three parts: 1) feature representation that builds a bipartite feature-data graph from input data; 2) a backbone network which is essentially a neural network model that predicts the labels when fed with input data; 3) a GNN model that inductively compute features' embeddings based on their proximity and local structures to achieve feature extrapolation.
Feature Representation with Graphs. We stack the feature vectors of all the training data as a matrix X,, = [x, E {0, NDD where N [t.l. Then we treat each feature and instance as nodes and construct bipartite graph between them. Formally, we define a node set Fir U Jer where For { with f, the j-th feature and Itr for J {o,),² with o, the i-th instance in training set. The binary matrix X constitutes an adjacency matrix where the non-zero entries indicate edges connecting two nodes in Fir and It., respectively. The induced feature-data bipartite graph will play an important role in our extrapolation approach. The representation is flexible for variable-size feature set, enabling our model handle test data X E (0, 1) which gives X.c [Xy]VE
Backbone Networks. We next consider a prediction model ha(-) as a backbone network that maps data features x; to predicted label ÿ.. Without loss of generality, default choice for he is feedforward neural network. The first layer serves as an embedding layer which shrinks x; into a H- dimensional hidden vector z; x, W where W 1 denotes weight matrix. The subsequent network (called classifier) is often a stack of neural layers that predicts label ÿ; = FFN(2;; (z; Φ). We use the notation ÿ h(x;; Φ, W) to highlight two sets of parameters and 0 (Ø, w].
Notice that the matrix multiplication in the embedding layer is equivalent a two-step procedure: 1) lookup of feature embeddings and 2) permutation-iinvaiial aggregation. More specifically, we consider W as a stack of weight vectors W = [[ where w, E RIIH corresponds to the embedding of feature fj. The non-zero entries in x; will index the corresponding rows of W and induce set of embeddings (z,"' 1d Jm=1 where z is the embedding given by x." (i.c., one-hot vector
3

---

+
0
exatiig nWN
fexture vestorn,
erbedding mahnx W
ckessiiction leyer
eebenddng laskip
aggegenion
Tectore
Backbone network:
embedding layer classifier
(b) Equivalent embedding layer
(c) Handling features in test data
An illustration for the feasibility of extrapolation for new feature space with neural network models. (a) The backbone network is feedforward neural network that is fed with input feature vector and outputs predicted label Øt The first layer can be seen as an embedding layer where an embedding matrix multiplied with the input vector obtain an intermediate hidden representation 2, (b) The embedding layer can be equivalently replaced by an embedding lookup and an aggregation over indexed feature embeddings. The aggregation is permutation-invaaiian w.r.t. the order of input features. (c) The permutation -nvvariant property enables the model to handle variable-length input feature vector (new features may come from unseen values of existing raw features or unseen raw features), The problem boils down to learning new features' embeddinngs.
Figure 2:
of m-th raw feature). Then the hidden vector of i-th instance can be obtained by aggregation, i.e., 2; Em==
m== z.th which is permutation-invarian w.r.t. the order of feature embeddings in (z," )d A more intuitive illustration is presented in Fig. 2
mm==1
The permutation-invartie property opens a way for handling variable-length feature vectors Xy [56] Essentially, on condition that we have embeddings for input features, we can add them up to get a exed-dimensional hidden representation z, as input for the subsequent classifier. Therefore, the problem boils down to learning feature embeddings, especially how to extrapolate for embeddings of new features based on those of existing ones.
Remark. Instead of using sum aggregation, some existing architectures consider concatenation of d embedding vectors z,"'s, which is essentially equivalent more details). Therefore, the permutation-invariie property holds for widely adopted deep models.
aggregation (see Appendix for
GNN for Feature Extrapolation. We proceed propose graph neural networks (GNN) model for embedding learning with the feature-data graph. Our key insight is that the bipartite graph explicitly embodies features' co-occurrence in observed instances, which reflects the proximity among features. Once we conduct message passing for feature embeddings over the graph structures, the embeddings of similar features be leveraged to compute and update each feature's 's embedding. The model can learn to extrapolate for new features' embeddings using those of existing features with locality structures in data-driven manner. The message passing over the defined graph representation is inductive w.r.t. variable-sized feature nodes and instance nodes, which enables the model to tackle new feature space with distinct feature sizes and supports.
Specifically, we consider the embeddings w as an initial state w (()) for node fy in Ftr. The initial
states of instance nodes are set as zero vectors with equal dimension as the feature nodes, i.e. s The interaction between two sets of nodes {w and J can be modeled via graph neural networks where the node states in the /-th layer are updated by
12
s; (1) POWC (s) (1-1), --GG(A (1-1) H aa = =1)
(1) COMB (W] (1-1) ACG((s) (1-1) HIk 1)))
where p()) IR HxH a weight matrix and we do not use non-linearity since it would degrade the set its initial state zero vector W = O. The GNN model outputs updated embeddings for feature nodes and we further use them as the feature embeddings in the backbone network. Fig. presents the feedforward computation of proposed model. Formally, with L-layer GNN, the GNN network g gives updated feature embeddings
performance empirically. For any new feature fy- in test data, (0)
W [w] j p- = g (WW, X:w) and then the backbone network outputs prediction 9. = h(x;; ó, W) where X = X,y for training, X X,e for test and {P()) 1/ denotes g's parameters..

---

observed data matelk
GNN messsae passing
bockbone network
f
f2
Js
44
0
1
BO
PS3
02
0g
0
1
04
0
0
1
Tootune
dissification
Figure 3: Feedforward of our model with input }x we build a feature-date graph between feature nodes { and instance nodes }. A GNN is used to inductively compute features' embeddings via message passing and backbone network uses the updated embeddings to predict labels (vi)-
:
fold split AA AAAA LA AAA
Drep
fu f
k-shot somple A
DrapEidge
AATA П
GNIN model
Bockbooee Network
1
f Fa
GNN model
Backdoone networkk
mc
updatt
Slow upciate
self-supervised leuming for feature extrapolation
(b) inductive learning for feature extrapolation
Figure 4: Illustration of two proposed training approaches: (a) celf-supervised learning with n-fold splitting (n = 4), and (b) inductive learning with k-shot sampling (k = 3). The two methods differ in configuration of proxy data, and both consider asynchronous updating rule: the backbone network is updated with --ld proxy data before the GNN network is updated once with an accumulated loss.
2.2 Model Learning
We next discuss approaches for model training. In order to enable the model to extrapolate for new features, we put forward two useful strategies. 1) Proxy training data: we only use partial features from training set as observed ones for each update. 2) Asynchronous updates: we decouple the training of backbone network and GNN network and using different updating speeds for them in a nested manner (see Fig. F. Based on these, we proceed to propose two specific training approaches.
Self-supervised Learning with N-fold Splits. To mimic new features in the future, we can mask some observed features and let the model use the remaining features to estimate the embeddings of the masked ones. For given feature set Fir {fg)== of data Jic,,,. we consider an n-fold splitting method: in each iteration the features are first randomly shuffled and evenly divided into disjoint subsets. denoted by {F [F.)" We then consider asynchronous updating rule for two networks: each iteration contains n times updates for backbone network and one update for GNN model. For the s-th update of the backbone, we mask features in F. and set the initial states of masked features as zero vectors before fed into GNN. The GNN network will use the adjacency matrix X to compute updated embeddings for the masked features. The embedding layer will be composed of updated embeddings of masked features and initial embeddings of the remaining features, based on which the backbone network outputs prediction ú: for each x; and compute the loss function C. t Eier, (14, ú: (where I(---) can be cross- cross-entropy for classification). After n-step updates for backbone network, we use the accumulated loss C Σ" L, to update GNN model. The training procedure will repeat the above process until a given time budget.
Inductive Learning with K-shot Samples. Alternatively, we can sample over the feature set and only expose partial features to the model for each update. For the s-th update, we randomly sample k raw feature from input data which induces new feature set F,, C F.r and extract the corresponding columns of Xtr [x.]iEr,r to form a proxy data matrix X, E {0, 1) Nx(Fl (where each instance contains F&] features). Then X, is fed into GNN to obtain updated embeddings of features in F,, based which the backbone network outputs prediction for each instance using features in F..
By contrast, the n-fold splitting contributes to better training stability since the model is updated on each feature in each iteration, while the inductive learning adds more randomness which can help to enhance model's generalization. We will further compare them our experiments.
DropEdge for Regularization. In order to further alleviate over-fitting on training features, we use the DropEdge 40 to regularize our model. We consider a threshold p and randomly set nonzero
2 Note that we still use supervised labels for loss though we call this approach as self-supervised learning. One can also directly sample certain ratio of features from Fir. which might lead large variance.
5

---

entries in Xtr (for self-supervised) or X, (for inductive) as zero for each feedforward computation,
X = DROPEDGE Xtr, P) {aag [aa E Xtr, Cij > p), where eij ~ U(0, 1).
(3)
Scaling to Large Systems. To handle prohibitively large datasets for practical systems, we can divide data matrix into mini-batches along the instance dimension. Then, we feed each mini-batch into the model for once model training (including feature-level sampling/slliting, as shown in Fig. $ or inference. Since the number of nonzero features for each instance is no more than d (a relatively small value), the edge number in each mini-batch will be controlled within ((Bd) (assume mini- batch contains B instances). Hence, the space cost can be effectively controlled using instance-level mini-batch partition. Yet, note that B could not be arbitrarily small in order to guarantee sufficient message passing over diverse instances. We present the complete training algorithm in Appendix B where the model trained end-to-end using self-supervised or inductive learning approaches.
Generalization Analysis
In this section, we analyze the generalization error test data with new features. We simplify the settings for analysis: 1) the backbone network a two-layer FNN (an embedding layer W & RRxx plus colleceeddee layer & E R !x with sigmoid output; 2) the GNN network is L-layer GCN which takes mean pooling aggregation over neighbored nodes without linear transformation and non-linearity in each layer; 3) the training algorithm is SGD. With above settings, the model can be written as 01 = o
X W where (i) contains all the X 's that appear in
the L-hop neighbors of x, in the fcature-data graph, = 2- 1 and oe E E is a weight that quantifies influence of x; X through I-llaye mean-pooling graph convolution. More details for the derivation are in Appendix C Also, we focus our analysis on the case inductive learning and the results be extended to self-supervised approach, which leave for future work.
The data generation process can be described as follows. First, features fj's are sampled from an unknown distribution F and form a feature set P.r = (f) Then data ((x,, (x),,,)) are sampled from a distribution Dr,, whose support over Xr,,, x y, and define X,r (e,, and Yor = {y4 heh. Using vi = [0, w). the model can be denoted by Ý = x/) (with simplification from Y = (0ihee = [h(x;; v²) her) with loss function C(Y, Y) = T Eier (JV, 9.).
Recall that in training stage, we randomly partition the instances in Xxr into mini-batches with size B and each mini-batch further samples raw features to form a feature subset F.. In each update. the model is exposed to B x [F& sub-matrix from X5, as proxy training data and uses it for once feedforward and backward computation. With given training data (Xtr, Y.r), we define S as a set of all the proxy data sub-mutric mabricsss that could be exposed to the model during the training
d!
S = (X,, Mi), (x2, Y2), (xms Ym), ... (X,, YM,}, where M x O (d - kd]-k)k!
The training process can be seen as sequence of operations each of which samples sub-matrix from S as proxy data in an i.i.d. manner and computes gradients for one SGD update (more discussions in Appendix C Define As learning algorithm trained on S, which gives trained model 1xX; vis simplified as li. The generalization error R(hs) can be defined as
R(hs) Ex,, [C(Y, h(x;; vss)).
where the expectation contains two stages of sampling: 1) feature set F = [[ is sampled according to ʃj ~ F, and 2) data (X, Y) is sampled according to (x, W:) ~ Dr. The empirical risk that our approach optimizes with the training data would be
Remp (hs)
1 M
Σ
C(Ym: helhhhXX h(Xmitii ws)).
(5)
We study the expected generalization gap
EA - Remp (hs));
(6)
where the expectation is taken over the randomness of As stemming from sampling for SGD updates.

---

Base-MN
Average-NN NN
KNN-NN
Pooling-NN
INL NN
FATE-NN
DracieNN
Gene
Protein
Robot
Accurayy
Accuracy
2.2
1.5
05
03
04
6.
0.5
6.1
0.3
0.4
65
3.5
67
9.8
Observed ratio
Observed ratio
Observed ratlo
Drive
Calls
Github
Accirscy
05
Accuracy
Observed
Figure 5: Accuracy/ROC-AUC results for UCI datasets with 30% ~ 80% observed features for training. We run each experiment five times with different random seeds and report averaged scores.
We assume that the loss function Uyy. D.) is Lipschitz-comtinuous and smooth w.r.t the model output Di. Concretely, we have 1) [()) - Hly, (')-) S 3) 31 f")) and 2) Vily, J(-)
be satisfied by widely used loss functions such as cross-entropy and MSE. Then we have the following result (see Appendix for proof).
[l(y.'(()) S 8 (+)))) v.(().. Such condition
Theorem 1. Assume the loss function is bounded by Uyt 9:) I X. For a learning algorithm trained on data (X Y with T iterations of SGD updates, with probability at least 1 6, have
d= Ba(R(hs) - (emm((hs) s 0 ( ) (01 (2) (0 +2)
(18) 2M
The generalization gap depends on the number of raw features in training data and the size of S. The latter determined by configuration of proxy training data, particular, sampling over training features. If the sampling introduces more randomness (e.g. h = d/2), S would become larger, contributing to tighter gap. However, a large S would also lead to large variance in training and amplify optimization error. Therefore, there exists trade-off w.r.t. how to sample/split observed features in training stage. Furthermore, the generalization gap also depends on d, and a larger would result looser bound (since one often has T > d). This is because a larger would require to deal with more features. As the network becomes wider and complex, it would be more prone for over-fitting
4 Experiments
We apply our model FATE (for FeATure Extrapolation Networks) on real-world datasets. First, we consider six classification datasets from UCI Machine Learning Repository [1] Gene, Protein, Robot, Drive, Calls and Github, as collected from domains like biology, engineering and social networks. The feature numbers are ranged from 219 to 4006 and the instance numbers vary from 1080 to 58509, We consider two large-scale datasets Avazu and Criteo from real-world online advertisement system whose goal is to predict the Click-Throus two datasets have ~ 40 million clicking/non-cliee -oiciiinnniingggg records as instances and ~ 2 million features. More dataset information and implementation details are in Appendix D and respectively. The implementation codes are public available at https: //github. com/
Rate (CTR) of exposed advertisement to users. The
4.1 Experiment UCI Datasets
Setup. We randomly split all the instances into training/vaidaaionntce data with the ratio 6:2:2. Then we randomly select certain ratio (30% ~ 80%) of features as observed ones and use the remaining as unobserved ones. The model is trained with the observed features of training instances and tested with all the features of testing data. We adopt Accuracy metric for datasets with more than two classes (Gene, Protein, Robot, Drive and Calls) and ROC-AUC for Github with two classes.
Implementation. We specify FATE in the following ways. 1) Backbone: 3-layer feedforward NN. 2) GNN: a 4-layer GCN.3) 3) Training: self-supervised learning with n-fold splits. Several baselines are considered for comparison and their architectures are all specified as 3-layer feedforward NN. First,
7

---

Table 1: ROC-AUC results for 8 test splits (TI-T8) on Avazu and Critco datasets.
Dataset
Backbone
Model
T1
T2
T3
T4
T5
T6
T8
Overall
Base
0.666
0.680
0.691
0.694
0.699
0.703
0.705
0.705
0.693 + 0.012
NN
Pooling
0.655
0.671
0.683
0.683
0.689
0.694
0.697
0.697
0.684 0.011
FATE
0.689
0.699
0.708
0.710
0.715
0.720
0.721
0.721
0,710 = 0.010
Avazu
Base
0.675
0.684
0.694
0.697
0.699
0.706
0.708
0.706
0.697 = 0.009
DcepFM
Pooling
0.666
0.676
0.685
0.685
0.688
0.693
0.694
0.694
0.685 + 0.009
FATE
0.692
0.702
0.711
0.714
0.718
0.722
0.724
0.724
0.713 = 0.010
Base
0.761
0.761
0.763
0.763
0.765
0.766
0.766
0.766
0.764 + 0.002
NN
Pooling
0.761
0.762
0.764
0.763
0.766
0.767
0.768
0.768
0.765 = 0.001
Criteo
FATE
0.770
0.769
0.771
0.772
0.773
0.774
0.774
0.774
0.772 + 0.001
Base
0.772
0.771
0.772
0.772
0.774
0.774
0.774
0.774
0.773 + 0.001
DcepFM
Pooling
0.772
0.772
0.773
0.774
0.776
0.776
0.776
0.776
0.774 + 0.002
FATE
0.781
0.780
0.782
0.782
0.784
0.784
0.784
0.784
0.783 + 0.001
Base-NN, Average-NN, Pooling-NN and KNN-NN are all trained on training instances with observed features. Then Base-NN only uses test instances' observed features for inference. Average-NN uses averaged embeddings of observed features as those of unobserved ones. Pooling-NN (resp. KNN-NN) computes embeddings for unobserved features via replacing our GNN with mean pooling aggregation over neighborhoods (resp. KNN aggregation over all the observed ones). Furthermore, we consider Oracle-NN using all the features of training data for training and INL-NN that is first trained on training data with observed features and then re-trained on training data with the remaining features.
Results and Discussions. Fig. reports the mean Accuracy/ROC-AUC of five trials with different ratios of observed features ranging from 0.3 to 0.8. FATE achieves averagely 7.3% higher Accuracy and 1.3% higher ROC-AUC over Base-NN which uses partial features for inference. The improve- ments are statistically significant under 95% confidence level. The results show that FATE can learn effective embeddings for new features that contribute to better performance for classification. Further- more, FATE achieves averagely 29.8% higher Accuracy and 0.5% higher ROC-AUC over baselines Average-NN, KNN-NN and Pooling-NN. These baseline methods perform worse than Na especially when observed features are few, which suggests that directly aggregating embeddings of observed features for extrapolation would degrade the performance. By contrast, FATE possesses superior capability for extrapolating to new unseen features. Even with 30% observed features the model is able to distill the useful knowledge from 70% unobserved features without re-training, providing decent classification performance. Notably, compared with INL-NN, FATE even achieves higher accuracy in most cases with a 4.1% Accuracy improvement on average. The possible reason is that INL-NN is prone for over-fitting on new data and forgetting the previous one. Finally, FATE achieves very close performance to Oracle-NN when using sufficient observed features and can even slightly exceeds it with 80% features in Gene, Robot and Github. In fact, the GNN network in FATE can not only achieve feature extrapolation, but also capture feature-level relations, which could be another merit of our method.
4.2 Experiment on CTR Prediction
Setup. We split the dataset in chronological order to simulate real-world cases. For Avazu dataset which contains time information in ten days, we use the data of first/second day for training/validation and the data of the third to tenth days for test. For Criteo dataset whose records are given in temporal order, split the dataset into ten continual subsets with equal size and use the first/second subset for training/validation and the third to tenth subsets for test. With such data splitting, we can naturally obtain validation/test data with mixture of seen and unseen features in the training data (the new features come from new values out of the known range of raw features). For Avazu/Criteo, there are ~0.66~11.3 million features in training data, ~0.2/~0.4 million new features in validation data and totally ~ 1/~w0.8 million new features in all the test splits. We use ROC-AUC as evaluation metric.
Implementation Details. We consider two specifications for our backbone: 1) 3-layer feedfoward NN. and 2) DeepFM [17] a widely used model for advertisement click prediction considering inter-feature interactions over NN. The GNN is 2-layer GraphSAGE model. The training method is inductive learning with k-shot samples and mini- partition. Also, we compare with baselines Base and Pooling. The KNN method would suffer from scalability issue in the two large datasets.
Results and Discussions. Table reports the ROC-AUC results for different test splits, which show that FATE significantly outperforms Base and Pooling in all the test splits using NN and
8

---

Geme
Protein
Robot
Drive
Calls
Github
Gracle
FATE
-1
6
Figure 6: Visualization for t-SNE embeddings of FATE-NN's and Oracle-NN's produced feature embeddings. We mark observed features with red and the remaining ones with blue nodes.
DeepFM as backnones. Overall, compared with Base, FATE improves the ROC-AUC by 0.017/0.016 (resp. 0.008/0.01 with NN/DeepFM as the backbone Avazu (resp. Criteo). Note that even an improvement of 0.004 for ROC-AUC is considered significant in click prediction tasks [3] The results show that FATE can combine useful information in new features collected in the future for the target task without further training and has promising power for enhancing the real-world systems interacting with open world. Compared with Pooling, FATE achieves significant AUC improvements on two datasets. The reason is that directly using average pooling to replace the GNN convolution would lead to limited capacity and weakens its ability for effective concept abstraction and reasoning.
4.3 Further Discussions
Scalability, We study model's scalability w.r.t. different batch sizes B and number of features D in which show that our training and inference time/space scale linearly Criteo dataset.
Fig. 6 Hand] 7
Ablation Studies. Table also provides ablation studies, which show that 1) the DropEdge operation can help regularize the training and bring up higher test accuracy; 2) using asynchronous updates for two networks leads to performance gain over joint training: 3) the n-fold splitting and k-shot sampling will outperform each other in different cases and both exceeds leave-one-our partition. Table 4 compares using different sampling size for inductive learning approach on Avazu and Criteo, which verify our theoretical analysis in Section See more discussions in Appendix F
Visualization. Fig. 6 visualizes the produced feature embeddings by FATE-NN and Oracle-NN. It unveils two interesting insights that can interpret why FATE can sometimes outperform Oracle that uses all the features for training. First, FATE-NN's produced embeddings for observed and unobserved features possess more dissimilar distributions in latent space, compared to Oracle-NN. Notice that features' embeddings are used for the backbone network to compute intermediate hidden representation for each instance. Such phenomenon implies that FATE manages to extract more informative knowledge from new features. Second, the embeddings of FATE-NN form some particular structures (clusters, lines or curves) rather than uniformly distribute over the 2-D plane like Oracle- NN. The reason that the GNN network leverages locality structures among features for further abstraction which explicitly encodes feature-level relations and could help downstream classification.
5 Connection to Other Learning Paradigms
Our introduced problem setting, ppendworld feature extrapolation (OFE), can be treated as an instantiation of out-of-distribution generalization N [3] or domain shift problem, focusing distribution shift led by feature space expansion. We next discuss the relationships of our problem setting and our model FATE with domain adaption (DA), continual learning (CL), open-set learning (OSL.) and zero-shot learning (ZSL... In general, OFF is orthogonal to these problems and opens a new direction that can potentially have promising intersections with the well-established ones.
Domain Adaption adapts a model trained on source domain to target with different distribution 57 BI. Our problem OFE is different from DA in two aspects: 1) the label space/distribution of training and test data is the same for OFE, while DA often mostly considers different label distributions for source and target domains; 2) OFE focus combining new features that are related to the current task, while DA considers different tasks from different domains.
4 S 2
16.
Continual Learning, or lifelong learning, aims at enabling a single model to learn from a stream By contrast, there are
of data from different tasks that cannot be seen at one time 39 two-fold differences of OFE. First, OFE does not allow finetuning further retraining on new data,
36 35

---

which can be more challenging than CL. Second, CL mostly assume each piece of data in the stream from different tasks with different labels handle. The key challenge of CL is the catastrophic forgetting (39 35 that requires the model to balance a trade-off between previous and new tasks, while FATE free from such issue nature since we do not require incremental learning.
Open-set Learning is another line of researches that relate with us. Differently, open-set recognition mostly focus on expansion of label sets G 6 to study feature set expansion, formulate it as OFE and further solve it via graph learning.
To our best knowledge, we are the first
Zero-shot Learning. Our problem setting is also linked with few-shot/zero-sher learning. In NLP domains, some studies focus on dealing with rare entities exposed in limited times or new entities unseen by training +
6D] Similar problems are also encoutered and explored in cold-start
One common nature of these works aim at inferring the embeddings for new entities based some 'held-out' ones. With a similar end and distinct methodological aspect, a recent study (50) explores a new possibility via learning a latent graph between existing entities (users) and newly arrived ones through attention mechanism for inductive representation learning. The core technical contributions of our work lie in the unique problem setting which stays focused on feature space expansion (domain shift) and the proposed feature-level sampling/partition training strategy, backed up with our theoretical insights.
recommender systems where there are also new users/items unseen before [51 19 50.
Extension and Outlooks. Our work be extended to solve more problems and push the develop- ment in broader areas. First, the input feature vectors can be replaced by feature maps given by CNN word/sentence embeddings by Transformer [46] for handling multi-modal data in the context Admittedly, our formulation assumes multi-hot feature vectors input, which is common practice for handling attribute features but not often the case for other data format (like vision or texts). For practitioners who would like to apply FATE to broader areas, one can extend our graph representation and GNN model directly handle continuous features by treating feature values as edge weights as is done by (55]. Second, as shown in our experiments, the classification layers can be replaced by more complex models
of federated learning [29] or multi-view learning |5 G
with inter- feature interactions [24 28 22 27 or advanced architectures 10 48
for more sufficient
feature- -astere-wise interaction and improving the expressiveness.
6 Conclusion
We present new framework to address new features unseen in training, by formulating it as the open-world feature extrapolation problem. We target the problem via graph representation learning by treating observed data feature-data graph and further harness GNN to inductively compute embeddings for new features with those of existing ones, mimicking abstraction and reasoning process in human's 's brain. We also propose two training strategies for effective feature extrapolation learning. Our theoretical results show that generalization error depends on training features and learning algorithms. Experiments verify its effectiveness and scalability to large-scale systems.
Potential Societal Impacts. When learning mapping from features labels, the model is risk of focusing on dominant features from majority groups and ignoring scarce features from minority ones. Potential extended works of much significance are to develop debiased methods for feature extrapolation. We believe Al models can be guided to promote social justice and well-being.
Acknowledgments and Disclosure of Funding
This work was partly supported by National Key Research and Development Program of China (2020AAA0107600), Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102), and NSFC (61972250, 72061 127003).
References
[1] A. Asuncion and Newman, Uci machine learning repository. 2007.
[2] B. B. Avants, N. Tustison, and J. R. Stone. Similarity-driven multi-view embeddings from high-dimensional biomedical data. Nature Computational Science, 1:143-152, 2021.
10

---

[3] D. Baptista, P. G. Ferreira, and M. Rocha. Deep learning for drug response prediction in cancer. Briefings Bioinform, 22(1):36--379 2021.
[4] S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. W. Vaughan. A theory of learning from different domains. Machine learning, 19(1-1)151-175, 2010.
[5] A. Bendale and T. E. Boult. Towards open world recognition. In Conference on Computer Vision and Pattern Recognition, pages
2015.
[6] A. Bendale and T. E. Boult. Towards open set deep networks. In Conference on Computer Vision and Puttern Recognition, pages 1563-1572, 2016.
[7] G. Blanchard, G. Lee, and C. Scott. Generalizing from several related classification tasks to a new unlabeled sample. In Advances in Neural Information Processing Systems (NeurIPS), pages 2178-2186, 2011.
[8] J. Blitzer, K. Crammer, A. Kulesza, F. Pereira, and J. Wortman. Learning bounds for domain adaptation. In Advances in Neural Information Processing Systems, pages 129-136, 2007.
[9] O. Bousquet and A. Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
[10] H. G. KJ, and C. KJ. Self-organizing feature maps identify proteins critical to learning in mouse model of down syndrome. PLoS ONE, 10(6), 2015.
[11] W. Chen, M. Chang, Schlinger, W. Y. Wang. and W. W. Cohen. Open question answering over tables and text. In International Conference Learming Representations, 2021.
[12] W. Chen, Zha, Z. Chen, W. Xiong. Wang, and W. Y. Wang. Hybridqa: A dataset of multi- hop question answering over tabular and textual data. In Conference on Empirical Methods in Natural Language Processing, pages 1026-10366 2020.
[13] H. Cheng, L. Koc, J. Harmsen, T. Shaked, T. Chandra, H. Aradhye, G. Anderson, G. Corrado, W. Chai, M. Ispir, R. Anil, Z. Haque, L. Hong. V. Jain, X. Liu, and H. Shah. Wide & deep learning for recommender systems. In Workshop on Deep Learning for Recommender Systems, pages 7-10, 2016.
[14] Covington, J. Adams, and E. Sargin. Deep neural networks for youtube recommendations. In Conference on Recommender Systems, pages 191-198, 2016.
[15] Y. Ganin and V. S. Lempitsky. Unsupervised domain adaptation by backpropagation. In International Conference Machine Learning, pages 1180-1189, 2015.
[16) Y. Ganin, E. Ustinova, Ajakan, P. Germain, H. Larochelle, F. Laviolette, Marchand, and V. S. Lempitsky. Domain-adversarial training of neural networks. The Journal of Machine Learning Research, 17:59:1-59:35, 2016.
[17) H. Guo, R. Tang, Y. Ye, Z. Li, and X. He. Deepfm: A fnctorization-machie based neural network for CTR prediction. In International Joint Conference on Artificial Intelligence, pages 7725-1731, 2017.
[18] W. L. Hamilton, Z. Ying, and J. Leskovee. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
[19] B. Hao, J. Zhang, H. Yin, C. Li, and H. Chen. Pre-training graph neural networks for cold-start users and items representation. In ACM International Conference on Web Search and Data Mining, pages 265-273, 2021.
[20] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, pages 12344, 2016.
[21] M. Hassen and P. K. Chan. Learning a neural-network-bbased representation for open set recognition. In International Conference Data Mining, pages 154-162, 2020.
11

---

[22] X. He and T. Chua. Neural factorization machines for sparse predictive analytics. In Inter- national Conference on Research and Development Information Retrieval, pages 355-364, 2017.
[23] Y. Juan, Y. Zhuang, W. Chin, and C. Lin. Field-aware factorization machines for CTR prediction. In Conference on Recommender Systems, pages 43-50, 2016.
[24] Y. Juan, Y. Zhuang, W. Chin, and C. Lin. Field-aware factorization machines for CTR prediction. In Conference on Recommender Systems, pages 43-50, 2016.
[25] T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[26] Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. Computer, 4008):30-37, 2009.
[27] Z. Li, J. Zhang, Y. Gong, Y. Yao, and Q. Wu. Field-wise learning for multi-field categorical data. In Advances in Neural Information Processing Systems, pages 6639-6669, 2020.
[28] J. Lian, X. Zhou, F. Zhang, Z. Chen, X. Xie, and G. Sun. xdeepfm: Combining explicit and implicit feature interactions for recommender systems. In International Conference on Knowledge Discovery & Data Mining, pages 1754-1763, 2018.
[29] P. P. Liang, T. Liu, Z. Liu, R. Salakhutdinov, and L. Morency. Think locally, act globally: Federated learning with local and global representations. CoRR, abs/2001.01522, 001522,, 2020.
[30] L. Logeswaran, M. Chang, K. Lee, K. Toutanova, J. Devlin, and H. Lec. Zero-shot entity linking by reading entity descriptions. In A. Korhonen, D. R. Traum, and L. Marquez, editors, Conference of the Association for Computational Linguistics, pages 3449-3460, 2019.
[31] M. Long, Z. Cao, Wang, and M. Jordan. Conditional adversarial domain adaptation. In Advances in Neural Information Processing Systems, pages 1647-1657, 2018.
[32] Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In Conference on Learning Theory, 2009.
[33] K. Muandet, D. Balduzzi, and B. Schölkopf. Domain generalization via invariant feature representation. In International Conference on Machine Learning (ICML), pages 10-18, 2013.
[34] P. Oza and V. M. Patel. C2AE: Conference on Computer Vision and Pattern Recognition, pages 2307-2316. Computer Vision Foundation IEEE, 2019.
class conditioned auto-encoder for open-set recognition. In
[35] G. Parisi, Kemker, Part, C. Kanan, and S. Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 113:54-71, 2019.
[36] G. Parisi, J. Tani, C. Weber, and S. Wermter. Lifelong learning of human actions with deep neural network self-organizattio. Neural Networks, 96:137-149, 2017.
[37] S. Rendle. Factorization machines. In International Conference Data Mining, pages 995-1000, 2010.
[38] M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: estimating the click thicuhthrough rate for new ads. In The Web Conference, pages 521-530, 2007.
[39] A. V. Robins. Catastrophic forgetting in neural networks: the role of rehearsal mechanisms. In First New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems, ANNES '93, Dunedin, New Zealand, November 24-26, 1993, pages 65-68. IEEE, 1993.
[40] Y. Rong, W. Huang, T. Xu, and J. Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
12

---

[41] B. Rozemberezki, C. Allen, and R. Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021.
[42] A. A. Rusu, C. Rabinowitz, G. Desjardins, H. Soyer, J. Kirkpatrick, K. Kavukcuoglu,
R. Pascanu, and R. Hadsell. Progressive neural networks. CoRR, abs/ (bs//666..0471, 2016.
[43] T. Schick and H. Schütze. Rare words: A major problem for contextualized embeddings and how to fix it by attentive mimicking. In AAAI Conference on Artificial Intelligence, pages 8766 8774, 2020.
[44] I.. Shu, H. Xu, and B. Liu. DOC: deep open classification of text documents. In Conference on Empirical Methods in Natural Language Processing, pages 2911-2911 2017.
[45] Y. H. Tsai, P. P. Liang, A. Zadeh, L. Morency, and R. Salakhutdinov. Learning factorized multimodal representations. In International Conference on Learning Representations. Open- Review.net, 2019.
[46] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998-6098 2017.
[47] S. Verma and Z. Zhang, Stability and generalization of graph convolutional neural networks. In International Conference on Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[48] Q. Wu, L. Jiang, X. Gao, X. Yang, and G. Chen. Feature evolution based multi-task learning for collaborative filtering with social trust. In International Joint Conference on Artificial Intelligence, pages 3877-3883, 2019.
[49] Q. Wu, H. Zhang. X. Gao, He, P. Weng, H. Gao, and G. Chen. Dual graph attention networks for deep latent representation of multifaceted social effects in recommender systems. In The Web Conference, pages 2091-2102, 2019.
[50] Q Wu, H. Zhang, X. Gao, J. Yan, and H. Zha. Towards open-world recommendation: An inductive model-based collaborative filtering approach. In International Conference on Machine Learning, pages 1 11329-1 1139,, 2021.
[51] T. Wu, E. K. I. Chio, H. Cheng, Y. Du. S. Rendle, D. Kuzmin, R. Agarwal, L. Zhang, J. R. Anderson, S. Singh, T. Chandra, E. H. Chi, W. Li, A. Kumar, X. Ma, A. Soares, N. Jindal, and P. Cao. Zero-shot heterogeneous transfer learning from recommender systems to cold-start search retrieval. ACM International Conference on Information and Knowledge Management, 2020.
pages
[52] M. Xu, R. Jin, and Z. Zhou. Speedup matrix completion with side information: Application to lulti-label learning. In Advances in Neural Information Processing Systems, pages 2301-2309, 2013.
[53] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolu- tional neural networks for web-scale recommender systems. In International Conference on Knowledge Discovery & Data Mining, pages 974 993,993,11 2018.
[54] R. Yoshihashi, W. Shao, R. Kawakami, S. You, M. lida, and T. Naemura. Classification- reconstruction learning for open-set recognition. In Conference on Computer Vision and Puttern Recognition, pages 4016-4025, 2019..
[55] You, X. Ma, D. Ding, M. Kochenderfer, and Leskovec. Handling missing data with graph representation learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[56] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Póezos, R. Salakhutdinov, and A. J. Smola. Deep sets. In Advances in Neural Information Processing Systems, pages 3391-3401, 2017.
[57] H. Zhao, S. Zhang, G. Wu, J. M. E. Moura, J. P. Costeira, and G. J. Gordon. Adversarial multiple source domain adaptation. Advances Neural Information P Processing Systems, pages 1568-8579, 2018.
13


Reviews:
[{"review_id": "mgRXFugwpX", "reviewer": "Reviewer_tu7i", "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.\n\nTo 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.\n\nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n[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.\n\n[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).\n\n[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).\n\n[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.\n\n[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.\n\nQuality: I looked over the theory and experiments quickly and most of it appeared correct. I have a few questions about the generalization error result. \n1) 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.\n2) Why do the bounds not scale with the sample size for each X_m? (i.e. where is |I| or N?)\n3) 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.\n4) 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. \n\n\nClarity: this paper was enjoyable to read aside from a few grammatical errors that can be fixed easily.\n\nSignificance: 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed limitations and societal impacts.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical concerns with this submission.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "K6pY34x5gFG", "reviewer": "Reviewer_fz9M", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "4b9FHQf4TX", "reviewer": "Reviewer_T7WN", "summary": "This paper tackles the unseen features with their extrapolation method from seen features, which is an important problem in machine learning.\n* The authors first formulate the problem of open-world feature extrapolation that aims to deal with features unobserved at training while observed at inference.\n* 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.\n* 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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n* 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.\n* 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.\n* The authors make an effort to analyze the generalization behavior of the proposed method, which is quite related to the empirical results.\n* The proposed method shows performance improvements from baselines on two different datasets.\n* The paper is well written, and the figures support the contents of the main paper well.\n\n### Weaknesses\n* 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).\n\n### Related Work\n* These two relevant works [1, 2] should be discussed.\n  * 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.\n  * 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.\n\n### Clarity\n* 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.\n\n### Suggestions (or Questions)\n* 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.\n* 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.\n\n### Typo\n* In the caption of Figure 1, (b) Oue approach.\n* In Figure 5, there is no blue color on the visualization example, while the caption mentions blue.\n\n---\n\n[1] Baek et al. Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction. NeurIPS 2020.\n\n[2] You et al. Handling Missing Data with Graph Representation Learning. NeurIPS 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "0AoSY8ACj-", "reviewer": "Reviewer_2Jqz", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThe 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.\n\nIt 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.\n\nPermutation 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.\n\nFigure 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.\n\nIt would be great to add error bars in Figure 4 to show the significance of difference between different methods.\n\n\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)