Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution
Authors: Chao Chen
Haoyu Geng
Gang Zeng
Zhaobing Han
Hua Chai
Xiaokang Yang
Junchi Yan
Venue: ICLR 2023 poster (2023)
Keywords: inductive one-bit matrix completion
graph signal sampling

Abstract: Inductive one-bit matrix completion is motivated by modern applications such as recommender systems, where new users would appear at test stage with the ratings consisting of only ones and no zeros. We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph, then learn structural graph properties to recover the function from its values on certain vertices --- the problem of graph signal sampling. We propose a class of regularization functionals that takes into account discrete random label noise in the graph vertex domain, then develop the GS-IMC approach which biases the reconstruction towards functions that vary little between adjacent vertices for noise reduction. Theoretical result shows that accurate reconstructions can be achieved under mild conditions. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain and builds upon a prediction-correction update algorithm to obtain the unbiased and minimum-variance reconstruction. Both GS-IMC and BGS-IMC have closed-form solutions and thus are highly scalable in large data. Experiments show that our methods achieve state-of-the-art performance on public benchmarks.

Published as a conference paper at ICLR 2023
GRAPH SIGNAL SAMPLING FOR INDUCTIVE ONE-BIT MATRIX COMPLETION: A SROSED-FORM, SOLUTION
Chao Chen', Haoyu Geng', Gang Zeng², Zhaobing Han?
Hua Chai?, Xiaokang Yang', Junchi Yan
1 MMoE Key Lab of Artificial Intelligence, Shanghai Jiao Tong University
Didi Chuxing
(chao.chen) junchii 8sjju. edu. en
Code: https://gi thub. com/ www.ccchllliocccc (0w.:001116//10M---0000
ABSTRACT
Inductive one-bit matrix completion is motivated by modern applications such as recommender systems, where new users would appear at test stage with the ratings consisting of only ones and no zeros. We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items function (graph sig- nal) on the vertices an item-item graph, then learn structural graph properties recover the function from its values certain vertices the problem of graph signal sampling. We propose a class of regularization functionals that takes into account discrete random label noise in the graph vertex domain, then develop the GS-IMC approach which biases the reconstruction towards functions that vary little between adjacent vertices for noise reduction. Theoretical result shows that accurate reconstructions can be achieved under mild conditions. For the online set- ting, develop Bayesian extension, i.e BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain and builds upon prediction- correction update algorithm to obtain the unbiased and manimum--vriiang recon- struction. Both GS-IMC and BGS-IMC have closed-form solutions and thus are highly scalable large data as verified on public benchmarks.
INTRODUCTION
In domains such recommender systems and social networks, only "likes" (i.e., ones) are observed in the system and service providers (e.g, Netflix) are interested discovering potential "likes" for existing users stimulate demand. This motivates the problem of 1-bit matrix completion (OBMC), of which the goal is to recover missing values in an n-by-m item-user matrix R E (0, 1 1 We note that R.j 1 means that item is rated by user j. but R,,, unknown which is mixture of unobserved positive examples and true negative examples.
is essentially unlabeled or
However, in real world new users, who are not exposed to the model during training, may appear at testing stage. This fact stimulates the development of inductive 1-bit matrix completion, which aims to recover unseen vector y {0. 13" from partial positive entries 24 S {ily,, 1} test time. Fig. 1(a) emphasizes the difference between conventional and inductive approaches. More formally, let Me {0, 1] (m++()+ denote the underlying matrix, where only subset of positive examples / is randomly sampled from [M, =, n. j. m) such that R., =1 for je E and R,,; =0 otherwise. Consider (m+1)-th column y out of matrix R. we likewise denote its observations s; =1 for E Ω4 and s; 00 otherwise.
note that the sampling process here assumes that there exists a random label noise which flips a to 0 with probability p. or equivalently s y + & where
& 1 for E Gily; = 1} 2+, and & otherwise.
Fig. ((a) presents an example of y. to better understand their relationships.
Fundamentally, the reconstruction of true y from corrupted bears resemblance with graph signal sampling. Fig. 1(b) shows that the item-user rating matrix R can be used to define a homogeneous
Junnhi Yan is the correspondence author who is also with Shanghai AI Laboratory. The work was in part supported by NSFC (62222607), STCSM (22511105100)

---

Published as a conference paper at ICLR 2023
User
Item
matrx:
R
column
noise
Graph Signal
Homogeneous Gruph
1
0
0
0
1
?
anknown
train-
1
0
X
1
?
?
1
?
siped oa
testing
1
?
prevent testing stage
truth y
obvorvation present tettting stage
(a) 1-Bit Matrix Completion
inductive matrix complettio
(b) Graph Signal Sampling
Figure 1: (a) Conventional 1-bit matrix completion focuses on recovering missing values in matrix R. while inductive approaches aim to recover new column y from observations s that are observed at testing stage. & denotes discrete noise that randomly flips ones to zeros. (b) Our GS-IMC approach, which regards y as a signal residing on nodes of a homogeneous item-item graph, aims to reconstruct true signal y from its observed values (orange colored) on a subset of nodes (gray shadowed).
item-item graph (see Sec 3.1), such that user ratings y /s on items can be regarded as signals residing on graph nodes. The reconstruction of bandlimited graph signals from certain subsets of vertices (see Sec 2) has been extensively studied in graph signal sampling (Pesenson, 2000; 2008).
Despite popularity areas such as image processing (Shuman et al., 2013: Pang & Cheung, 2017; Cheung et al., 2018) and matrix completion (Romero et al., 2016; Mao et al., 2018; McNeil et al., 2021), graph signal sampling appears less studied in the specific inductive one bit matrix completion problem focused in this paper (see Appendix A for detailed related works). Probably most closely related to our approach are MRFCF (Steck, 2019) and SGMC (Chen et al., 2021) which formulate their solutions as spectral graph filerr, However, we argue that these methods are orthogonal to us since they focus on optimizing the rank minimization problem, whereas we optimize the functional minimization problem, thereby making it more convinient and straightforward to process and ana- lyze the matrix data with certex-frequency analysis (Hammond et al., 2011; I; Shuman et al., 2013), time-variant analysis (Mao et al., 2018; McNeil et al., 2021), smoothing and filtering (Kalman, 1960; Khan & Moura, 2008). Furthermore, (Steck, 2019; Chen et al., 2021) can be incorporated as special cases of our unified graph signal sampling framework (see Appendix B for detailed discussions).
Another emerging line of research has focused on learning the mapping from side information (or content features) latent factors (Jain & Dhillon, 2013; Xu et al., 2013; Ying et al., 2018; Zhong et al., 2019). However, it has been recently shown (Zhang & Chen, 2020; Ledent et al., 2021; Wu al., 2021) that in general this family of algorithms would possibly suffer inferior expressiveness when high-quality content is not available. Further, collecting personal data is likely to be unlawful as well as breach of the data minimization principle in GDPR (Voigt & Von dem Bussche, 2017).
Much effort has also been made to leverage the advanced graph neural networks (GNN) for improve- ments. van den Berg et al. (2017) represent the data matrix R by a bipartite graph then generalize the representations to unseen nodes by summing the embeddings over the neighbors. Zhang & Chen (2020) develop graph neural networks which encode the subgraphs around an edge into latent factors then decode the factors back to the value on the edge. Besides, Wu et al. (2021) consider the problem in a downsampled homogeneous graph (i.c., user-user graph in recommender systems) then exploit attention networks to yield inductive representations. The key advantage of our approach is not only the closed form solution which takes a small fraction of training time required for GNNs, but also theory results that guarantee accurate reconstruction and provide guidance for practical applications.
We emphasize the challenges when connecting ideas and methods of graph signal sampling with in- ductive I-bit matrix completion 1-bit quantization and online learning. Specifically, 1-bit quanti- zation raises challenges for formulating the underlying optimization problems: minimizing squared loss on the observed positive examples 24 yields a degenerate solution the vector with all en- tries equal to one achieves zero loss; minimizing squared loss on the corrupted data s introduces the systematic error due to the random label noise & Eq. (1). To address the issue, we represent the observed data R as a homogeneous graph, then devise broader class of regularization functionals on graphs to mitigate the impact of discrete random noise &. Existing theory for total variation de- noising (Sadhanala et al., 2016; 2017) and graph regularization (Belkin et al., 2004; Huang et al., 201 1), which takes into account continuous Gaussian noise, does not sufficiently address recover- ability in inductive 1-bit matrix completion (see Sec 3.4). We finally mange to derive closed-fore solution, entitled Graph Sampling for Inductive (1-bit) Matrix Completion GS-IME which biases the reconstruction towards functions that vary little between adjacent vertices for noise reduction.
2

---

Published as a conference paper at ICLR 2023
For online learning, existing matrix factorization methods (Devooght al., 2015; Volkovs & Yu, 2015; He et al., 2016) incrementally update model parameters via gradient descent, requiring an expensive line search to set the best learning rate. To scale up to large data, we develop a Bayesian extension called BGS-IMC where a prediction-correctinn the prediction given new incoming data. The prediction step tracks the evolution of the optimization problem such that the predicted iterate does not drift away from the optimum, while the correction step adjusts for the distance between current prediction and the new information at each step. The advantage over baselines is that BGS-IMC considers the uncertainties in the graph Fourier domain, algorithm can efficiently provide the unbiased and
algorithm is devised to instantly refreshes
and the prediction-coreet predictions in closed form, without using gradient descent techniques. The contributions are:
New Inductive 1-bit Matrix Completion Framework. We propose and technically manage (for the first time to our best knowledge) to introduce graph signal sampling to inductive 1-bit ma- trix completion. It opens the possibility of benefiting the analysis and processing of the matrix with signal processing toolbox including vertex-frequent
analysis (Hammond et al., 10 Shu- man et al., 2013), time-variant analysis (Mao al., 2018; McNeil et al., 2021), smoothing and filtering (Kalman, 1960; Khan & Moura, 2008) etc. We believe that our unified framework can serve as a new paradigm for 1-bit matrix completion, especially large-scale and dynamic systems. Generalized Closed-form Solution. We derive a novel closed-form solution (i.e., GS-IMC) in the graph signal sampling framework, which incorporates existing closed-form solutions special cases, c.g., (Chen et al., 2021; Steck, 2019). GS-IMC is learned from only positive data with discrete random noise. This is one of key differences to typical denoising methods (Sadhanala et al., 2016) where efforts are spent on removing continuous Gaussian noise from a real-valued signal.
Robustness Enhancement. We consider the online learning scenario and construct a Bayesian extension, i.c., BGS -MC where a new predcciion-coreccti algorithm is proposed to instantly yield unbiased and minimum-variane show that BGS-IMC is more cost-effective than many neural models such as SASREC (Kang & McAuley, 2018), BERTAREC (Sun et al., 2019) and GREC (Yuan et al., 2020). We believe that this proves a potential for the future application of graph signal sampling to sequential recommendation. Theoretical Guarantee and Empirical Effectiveness. We extend Paley-Wiente theorem of (Pe- senson, 2009) real-valued data to uosttie-unlabbllled data with statistical noise. The theory shows that under mild conditions, unseen rows and columns in training can be recovered from a certain subset of their values that is present test time. Empirical results on real-world data show that our methods achieve state-of oh- performance for the challenging inductive Top-N ranking tasks.
predictions given new incoming data. Experiments in Appendix
2 PRELIMINARIES
In this section, we introduce the notions and provide the necessary background of graph sampling theory. Let G = (V, E, w) denote weighted, undirected and connected graph, where V is set of vertices with V = n, E is set of edges formed by the pairs of vertices and the positive weight w(u, v) on each edge is function of the similarity between vertices u and
Space (g) is the Hilbert space of all real-valued functions f: V - IK with the following norm:
|| [|
Σ VEV
(F())
and the discrete Laplace operator E, is defined by the formula (Chung & Graham, 1997):
f(v)
f(u)
Lf(v)
w(u,v) u)
f L2(
Vd(r)
Vd(w)
Vd(u)
(E)(
where (v) signifies the neighborhood of node and d(v) - EveN(w) w(u, v) is the degree of v.
Definition (Graph Fourier Transform). Given a function or signal f in (2)) the graph Fourier transform and its inverse (Shuman al., 2013) can be defined follows:
fg Uf and f= Uf,
(3)
3

---

Published as a conference paper at ICLR 2023
Table I: Regularization functions, operators, kernels with free parameters 7 2 0,
Function
Operator
Filter Kemel
Tikhonov Regularization (Tikhonov, 1963)
R(A) = 7>
R(L) et
H(A) 1/(1+AA)
Diffusion Process (Streock & Varadhan, 1969)
RIA) exp()/2A)
R ex2()
H(A] 1/lexp() +)
One-Step Random Walk (Pearson, 1905)
R(A) = (a - A]
R.L
[al ----i L)
H(A) (a A)f (a x
Inverse Cosine (MacLane, 1947)
R(A) Am/1)1
R(L) (cos La/1)"
H(A) A0//1)
where U represents eigenfunctions of discrete Laplace operator E. fg denotes the signal in the graph Fourier domain and fc((i) = (f, u.) signifies the information at the frequency Ar"
Definition 2 (Bandlimiteness)) E L2( is called w- w-bannlimited function if its Fourier transform f has support in [0.w], and w-baanllimited functions form the Paley- Miieee space (9) Definition 3 (Graph Signal Sampling). Given y (G), on the vertices Q4 by minimizing below objective (Pesenson, 2000; 2008), with positive scalar k:
be recovered from its values
min FEL2(C)
|| [ ||
s.b., f(v) = y()), Vu E 2++
Recall that the observation in inductive 1-bit matrix completion consists of only ones and no zeros (i.e.. y for Ω24) and || ||= 0. It is obvious that minimizing the loss on the observed entries corresponding to ones. produces degenerate solution the vector with all entries equal to one achieves zero loss. From this point of view, existing theory for sampling real-valued signals (Pesenson, 2000; 2008) not well suited the inductive 1-bit matrix completion problem.
3 CLOSED-FORM SOLUTION FOR 1-BIT MATRIX COMPLETION
This section builds a unified graph signal sampling framework for inductive 1-bit matrix completion that can inductively recover y from positive ones set Ω4. The rational behind our framework is that the rows that have similar observations are likely to have similar reconstructions. This makes a lot of sense in practice, for example a user (column) is likely to give similar items (rows) similar scores in recommender systems. To achieve this, we need to construct a homogeneous graph G where the connected vertices represent the rows which have similar observations, that we can design a class of graph regularized functionals that encourage adjacent vertices on graph G to have similar reconstructed values. In particular, we mange to provide closed-form solution the matrix completion problem (entitled GS-IMC), together with theoretical bounds and insights.
3.1 GRAPH DEFINITION
We begin with the introduction of two different kinds of methods to construct homogeneous graphs by using the zero-one matrix R E TR=xx; (i) following the definition of hypergraphs (Zhou et al., 2007), matrix R. can be regarded as the incidence matrix, so to formulate the hypergraph Lapla- cian matrix as L == I D., R/RDD e R D. 1/2 where D E R (D. E Rm is the diagonal degree matrix of vertices (edges); and (ii) for regular graphs, one of the most popular approaches is to utilize the covariance hetween rows to form the adjacent matrix A., = Cov Cov(R, (R,, R,) for i #
so that we can define the graph Laplacian matrix as L = 1,,1/2A00 AD, 1/2
3.2 GRAPH SIGNAL SAMPLING FRAMEWORK
Given a graph G = (V, F), any real-valued column y E R can be viewed as a function on 9 that maps from V to R. and specifically the i-th vector component y; is equivalent to the function value (i) at the i-th vertex. Now it is obvious that the problem of inductive matrix completion, of which the goal is to recover column y from its values on entries 244, bears a resemblance the problem of graph signal sampling that aims to recover function y from its values on vertices Ω4.
However, most of existing graph signal sampling methods (Romero et al., 2016; Mao et al., 2018; McNeil et al., 2021) yield degenerated solutions when applying them to the 1-bit matrix completion problem. A popular heuristic is to treat some or all of zeros as negative examples Q_ then to recover y by optimizing the following functional minimization problem, given any k 2 2 N:
|| [R(t)]*r] fe (g))(G)
min
s.L.,
sn fn ||se
(5)
'To be consistent with (Shuman et al., 2013), (I-th column of matrix U) is the 1-th eigenvector associated with the eigenvalue At, and the graph Laplacian eigenvalues carry a notion of frequency.
4

---

Published as a conference paper at ICLR 2023
Very- High Degree Vertiess
High Degree Vertiees
Medium Degree Vertioes
Lowe Degroe Vertines
0.08
0.03
0.00
0.02
0.303
001
0.01
Ace
A150
ApM
App
Auce
Auee
App
A/e0 Auc 2ut 200
Asso
Figure 2: Recall results on Netflix data of very-high degree vertices (left), high degree vertices (left middle), medium degree vertices (right middle) and low degree vertices (right) for top-100 ranking tasks, where Aςo on the x-axis corresponds to the assumption of space PW (9) or namely we use the eigenfunctions whose eigenvalues are not greater than Aso to make predictions. The results show that low(high) -freueerrrryyy functions
functionn reflect user preferences on the popular (cold) items.
where recall that y É is the observed data corrupted by discrete random noise &, and sq (fn) signifies the values of (f) only on f2 = Q2 UΩ_; R(E) = E, R (uju denotes the regularized Laplace operator in which } and } are respectively the eigenvalues and cigenfunctions of operator t.. It is worth noting that s(i) = y(i) + E(i) = 0 for i E Ω is not the true negative data, and hence Ω will introduce the systematic bias when there exists i Ω that (6) 1.
The choice of regularization function R(A) needs to account for two critical criteria: 1) The result- ing regularization operator R(t) needs to be semi-positive definite. 2) As mentioned before, we expect the reconstruction ý to have similar values on adjacent nodes, so that the uneven functions should be penalized more than even functions. To account for this, we adopt the family of positive, monotonically increasing functions (Smola & Kondor, 2003) as present in Table 1.
To the end, we summarize two natural questions concerning our framework: What are the benefits from introducing the regularized Laplacian penalty? It is obvious that minimizing the discrepancy between Sq and fn does not provide the generalization ability to recover unknown values on the rest vertices V - f2 and Theorem 4 and 5 answer the question by examining the error bounds. 2) What kind R(E) constitutes a reasonable choice? It has been studied in (Huang et al., 2011) that R(E.) is most appropriate if it is unbiased, and an unbiased R(E.) reduces variance without incurring any bias on the estimator. We also highlight the empirical study in Appendix C that evaluates how the performance is affected by the definition of graph G and regularization function R()).
3.3 CLOOSED-FORM SOLUTION
In what follows, we aim to provide a closed-form solution for our unified framework by treating all of the zeros negative examples, i.e., s(u) = 1 for e E 22 and s(v) = 0 otherwise. Then by using the method of Lagrange multipliers, we reformulate Eq. (5) to the following problem:
(f, R(E))) + 1 f||-
min fELa(G) 2
(6)
where & is hyperparameter. Obviously, this problem has closed-form solution:
y = I R(L)/() s = EE (1+ (1+B(N)/))uuu) u.))) s = HHL)s,,
(7)
where (LL) E, (A)))(uu with kernel (A/ = 1 1+ R(A)/sp, and we exemplify H (A) when xp in Table I. From the viewpoint of spectral graph theory, our GS-IMC approach is essentially spectral graph filter that amplifies(attenuatee) the contributions of (ow(hig)-frrqueng functions.
Remark. To understand low- frequeeuy and high-frequee frequency functions, Figure presents case studies in the context of recommender systems on the Netflix prize data (Bennett et al., 2007). Specifically, we divide the vertices (items) into four classes: very-high degree (> 5000), high degree (> 2000), medium degree (> 100) and low degree vertices. Then, we report the recall results of all the four classes in different Paley-Wo Paley-Wiener spaces PW PWAzo (9),
PW Xonoa (9) for top-100 ranking predic- tion. The interesting observation is: (1) the low- cww-frequency functions with eigenvalues less than Aι00 contribute nothing to low degree vertices; and (2) the high-freug frequuncy functions whose eigenvalues very-high degree vertices. This
greater than Asoo do not help increase the performance finding implies that www(hhhhh-ffuuuueeee functions reflect the user preferences on the popular(cold) items. From this viewpoint, the model defined in Eq. (7) aims exploit the items with high click- through rate with high certainty, which makes sense in commercial applications.
5

---

Published as a conference paper at ICLR 2023
3.4 ERROR ANALYSIS
Our GS-IMC approach defined in Eq. (7) bears a similarity to total variation denoising (Sadhanala et al., 2016; 2017), graph-constrained regularization (Belkin et al., 2004; 2006), and particularly Laplacian shrinkage methods (Huang et al., 2011). However, we argue that the proposed GS-IMC approach is fundamentally different from previous works. Specifically, they operate real-valued data while GS-IMC deals with positive- positive-unlabeled data. We believe that our problem setting is more complicated, since the unlabeled data is mixture of unobserved positive examples and true negative examples. In addition, existing methods analyze the recoverability considering statistical noise to be continuous Gaussian, e.g., Theorem 3 (Sadhanala et al., 2016), Theorem 1.1 (Pesenson, 2009) etc.
However, we study upper bound of GS-IMC in the presence of discrete random label noise &. Specif- ically, Theorem 4 extends Paley- -iiener theorem of (Pesenson, 2009) on real-valued data positive- unlabelled data, showing that a bandlimited function can be recovered from its values on certain set f2. Theorem 5 takes into account statistical noise& and shows that a bandlimited function y can be accurately reconstructed if C² = C > O is constant, not growing with n.
Theorem 4 (Error Analysis, extension of Theorem 1.1 in (Pesenson, 2009)). Given R(A) with < R(A) on graph G G= (V. E), assume that Q = V Q admits the Poincare inequality || Φ || A Lo for any o E (52 with A > 0, thenfoor any y E PG) with 0 < w S RRw) < 1/A
y - Ev Il 2 ( & yy
and y= lim Vk
(8)
where k is a pre-specified hyperparameter and ÿt is the solution of Eq. (5) with 0.
Remark. Theorem 4 indicates that better estimate of y can be achieved by simply using higher k but there a trade-off between accuracy of the estimate on one hand, and complexity and numerical stability on the other. We found by experiments that GS-IMC with k = 1 can achieve SOTA results for inductive top-N recommendation on benchmarks. We provide more discussions in Appendix G.
Theorem (Error Analysis, with label noise). Suppose that & is the random noise with flip rate and positive X .... S >n are eigenvalues of Laplacian E,, then for any function y E PW (9).
E [MSSEY so S C2 n
P R(())(1 + R(X)/(}²
1 )
where C² = R[() || y 112, &p is the regularization parameter and ý is defined in Eq. (7).
Remark. Theorem shows that for a constant C, C > 0 (not growing with n), the reconstruction error converges to zero as is large enough. Also, the reconstruction error decreases with R(w) declining which means low-frequency functions can recovered more easily than high-frequency functions. We provide more discussions yp, p in Appendix H.
4 BAYESIAN GS-IMC FOR ONLINE LEARNING
In general, an inductive learning approach such as GAT (Veličković et al., 2017) and SAGE (Hamil- ton et al., 2017), etc., can naturally cope with the online learning scenario where the prediction is refreshed given a newly observed example. Essentially, GS-IMC is an inductive learning approach that can update the prediction, more effective than previous matrix completion methods (Devooght et al., 2015; He et al., 2016). Let As denote newly coming data that might be one-hot as in Fig. 3(a), ý denotes original prediction based on data s, then we can efficiently update ý ý Ynew as follows:
y neww ((L)(s + As) = y H(t)As.
(10)
However, we argue that GS-IMC ingests the new data in unrealistic, suboptimal way. Specifically, does not take into account the model uncertainties, assuming that the observed positive data is noise-free. This assumption limits model's fidelity and flexibility for real applications. In addition, it assigns a uniform weight to each sample, assuming that the innovation, i.e., the difference between the current a priori prediction and the current observation information, is equal for all samples.
4.1 PROBLEM FORMULATION
To model the uncertainties, we denote a measurement by z= Uý (Fourier basis U) which represents prediction ý in the graph Fourier domain and we assume that is determined by stochastic process.

---

Published as conference paper at ICLR 2023
Graph Vertex 9=
H())s
nnew
Domain (Eq. 10)
+H(4)As
GFT
GFT
Graph Fourier z= Uy Domain (Eq. 11-12)
new
newly ås coming data
++v
transition
Maae
nnw
colurn
column Snew
As
Mecasrrement
+AAS
(a) Online Learning Scenario
(b) BGS-IMC
Figure 3: (a) Online learning scenario requires the model to refresh the predictions based on newly coming data As that is one-hot (orange colored). (b) GS-IMC deals with this problem in graph vertex domain using Eq. (10), while BGS-IMC operates in graph Fourier domain. The measurement z/Znew is graph Fourier transformation
the prediction y/y new and we assume hidden states x/Xnew determine these measurements under noise V. To achieve this, x/ X'ew should obey the evolution of ÿ / /eew and thus Eq. (11) represents Eq. (10) under noise v graph Fourier domain.
In Fig. 3(b), measurement z is governed by hidden state and noise captures the data uncertainties in an implicit manner. The choice of state transition equation need to account for two critical criteria: (1) the model uncertainties need to be considered. (2) the transition from state x to state Xnew need to represent the evolution of predictions y/y, defined in Eq. (10).
To account for this, we propose Bayesian extension of GS-IMC, entitled BGS-IMC, which siders the stochastic filtering problem in dynamic state-space form:
Xnew x FAs +
(1I)
nnw
Xnew +
(12)
where Eq. (11) essentially follows Eq. (10) in the graph Fourier domain, i.c., multiplying both sides of Eq. (10) by U. In control theory, F UH.) called the input matrix and As represents system input vector. The state equation (11) describes how the true state Xnew evolves under the impact the process noise v ~ (O, E,,, and the measurement equation (12) characterizes how a measurement Znew = - (s - As) the true state Xnew is corrupted by the measurement noise ~ (0,, E.). It is worth noting that larger determinant of Σn means that data points are more dispersed, while for E, large determinant implies that BGS BGS-IMC is not sufficiently expressive and it is better to measurement for decision making, i.c., BGS- BGS-IMC is reduced to GS-IMC.
Using Bayes rule, the posterior is given by:
p( new As, Znew) X pl Znew Xnew )eX As),
(13)
where p[Znew Xnew) and p( Xnew As) follow Gauss-Markov process.
4.2 PREDICTION CORRECTION CHERRCTIONCOOREECTIO
UPDATE ALGORITHM
To make an accurate prediction, we propose a prediction-correctoon update algorithm, resembling workhorse Kalman filtering-based based approaches (Kalman, 1960; Wiener et al., 1964). To our knowl- edge, the class of completion, despite its popularity in time-series forecasting (Simonetto al., 2016; de Bézenac et al., 2020) and computer vision (Matthies et al., 1989; Scharstein & Szeliski, 2002).
methods appears less studied in the domain of 1-bit matrix
In the prediction step, follow the evolution of the state as defined in Eq. (11) to compute the mean and the covariance of conditional p( p(Xnewl As):
E X/x As
FAs Xnew and Var(Xnew As) + Σ, = P
(14)
where & is the estimate state of x and P is the estimate covariance, i.e.. P= E(x x) x) while Xnew, Pnww are the extrapolated estimate state and covariance respectively. Meanwhile, is easy to obtain the mean and the covariance of conditional p(Znew Knew):
Zuew Xnew] Xnew + vl Xnew and Var(Znew (xew)) E'vD T E.. (15)
In the correction step, combine Eq. (13) with Eq. (14) and (15):
pl p(Xnew As, Znow) exp ((xuew Znow) En (Xnew- Znew) ) (Xnew Xnew TP
TP new (Xuew Xnew))

---

Published as a conference paper at ICLR 2023
By solving 2 In p(xnew As, Znew) ) /xxnew O, we have the following corrected estimate state Xuew and covariance P Puew, where we recall that the new measurement is defined as Znew U (s s + As):
Xnew Xnew + K (Znew Xnew
(16)
P new (I K)P new (T 1--K K) + KKEK
(17)
K P new (P new + E
(18)
where K is the Kalman gain and Znew Xnew is called the innovation. It is worth noting that Eq. (16) adjusts the predicted iterate Xnew in terms of the innovation, the key difference to GS-IMC and existing methods, e.g., GAT (Veličković al., 2017) and SAGE (Hamilton et al., 2017).
Remark. The BGS-IMC approach is highly scalable in Paley-Wiener spaces. Let (g) be the span of k (& n)) eigenfunctions whose eigenvalues are no greater than w, then the transition matrix F in (11) is b--by- and every covariance matrix is of size k x k. Computationally, when P. Ey, Σ, are diagonal, it takes O(k2) time to compute nnew and P new. and (nnk) time for New and P pew- The total time complexity Onk + k²), linear the number of vertices n. Further, Proposition shows that &new in (16) is an unbiased and minimum-variance estimator.
Proposition Given an observation As, provided F is known, Nnew obtained in Eq. (16) is the optimal linear estimator in the sense that it is unbiased and minimum- vinimum-vvriance.
To summarize, the complete procedure of BGS-IMC is to first specify E Ev, P using prior knowl- edge, then to calculate extrapolated state Xnew using (14), and finally to obtain Xnew using (16) so that we have the updated model prediction as Ynew new that ingests the new observation.
EXPERIMENT
This section evaluates GS-IMC (in Section 3) and BGS-IMC (in Section 4) on real-world datasets. All the experiments conducted on the machines with Xeon 3175X CPU, 128G memory and P40 GPU with 24 GB memory. The source code and models will be made publicly available.
5.1
EXPERIMENTAL SETUP
We adopt three large real-world datasets widely used for evaluating recommendation algorithms: (1) Koubei (1, 828, 250 ratings of 212, 831 users and 10, 213 items); (2) Tmall (7, 632, 826 ratings of 327,497 users and 21, 876 items); (3) Netflix (100, 444, 166 ratings of 400, 498 users and 770 items). For each dataset, we follow the experimental protocols in (Liang et al., 2018; Wu et al., 2017a) for inductive top-N ranking, where the users are split into craining/vlidaaiion/ees set with ratio 8 1: 1. Then, we use all the data from the training users to optimize the model parameters. In the testing phase, sort all interactions of the validation/test users in chronological order, holding out the last one interaction for testing and inductively generating necessary representations using the rest data. The results in terms of hit-rate (HR) and normalized discounted cumulative gain (NDCG) are reported on the test set for the model which delivers the best results on the validation set.
We implement our method in Apache Spark with Intel MKL, where matrix computation is paral- lelized and distributed. In experiments, we denote item-user rating matrix by R and further define the Laplacian t. = I D. 1/2 RRD, R D 1/2 We set a=4, 7=1, ==11 for GS-IMC, while we set the covariance to =,= 'I and initialize P using the validation data for BGS-IMC. In the test stage, if user has |S2] training interactions, BGS-IMC uses first | interactions to produce initial state x, then feed last interaction to simulate the online update.
In the literature, there few of existing works that enable inductive inference for topN ranking only using the ratings. To make thorough comparisons, we prefer to strengthen IDCF with GCMC for the improved performance (IDCF+ for short) rather than report the results of IDCF (Wu al., 2021) and GCMC (van den Berg et al., 2017) as individuals. Furthermore, we study their performance with different graph neural networks including Che (Defferrard et al., 2016), GAT (Veličković et al., 2017), GraphSage (Hamilton et al., 2017). SGC (Wu et al., 2019) and ARMA (Bianchi et al., 2021). We adopt the Adam optimizer (Kingma & Ba, 2015) with the learning rate decayed by 0.98 every epoch. We search by grid the learning rate and Le regularizer in {0.1, 0.01, ... 0.00001) J. the dropout rate over {0.1, 0.2....................... 0.7] and the latent factor size ranging (32, 64....,5122 for the op- timal performance. In addition, 2019) and SGMC (Chen et al., 2021 1) which are most closely related to our proposed method. The software provided by the authors is used in the experiments.
also report the results of the shallow models i.., MRCF (Steck,
8

---

Published as a conference paper at ICLR 2023
Table 2: Hit-Rate results against the baselines for inductive top-N ranking. Note that SGMC (Chen et al., 2021) is a special case of our method using the cut-off regularization, and MRFCF (Steck, 2019) is the full rank version of our method with (one-step) random walk regularization. The stan- dard errors of the ranking metrics are less than 0.005 for all the three datasets.
Koubei, Density=0.00
0.%%
Tmall, Density=0 10%
Netlixx Density=1 41%
Model
H8
H@
H8 100
H8:0
18:50
18 100
H@:0
H@:50
It@100
IDCF (Wa al., 2021)
0.14305
0.20335
0.24285
0.16100
0.27690
0.34573
0,08805
0.19788
0.29330
IAT (Veličković et 2017)
0.19715
0.26440
0.30125
0.20033
0.32710
0.39037
0.08712
0.19387
0.27228
INCV4GraphSAGG (Homilion et al, 2017)
0.20800
0,22225
D. 303054
0.19395
0.32733
0.39367
0,08580
0.19187
0.26972
IDCP&SGC (Wa et al., 2019)
0.200990
0.26230
0.30335
0.19211
0,32493
0.38927
0,08062
0.18080
0.26720
IDC++ChdyNee (Delferard al. 2016)
0.20515
0.28100
0.32385
0.18163
0.32017
0.39417
0,08735
0.19335
0.27470
IDCYARMA (Blanchi et al., 2021)
0,20745
0.27750
0.31895
0.17833
0.31567
0.39140
0.08610
0.19128
0.27812
MRFCF (Steck, 2019)
0.17710
0.19300
0.19570
0.19123
0.28943
0.29260
0,08738
0.19488
0.29048
SGMC (Chen 2021)
0,23290
0.31655
0.3500
0.13560
0.31070
0.40790
0.09710
0.22735
0,32193
GS-IMC (ours, See 9)
0,23460
0.31995
0.35065
0.13677
0.31027
0,40760
0.09725
0.22733
0.32225
BGS-IMC (ours, Sec 4)
0.24390
0.32545
0.35345
0.16733
0.34313
0.43690
0.09988
0.23390
0.33063
3: NDCG results of GS-IMC and BGS-IMC the baselines for inductive top-N ranking.
Kouhel, Density-0) 0887%
Tmall, Density-O 10%
Netfli, Density- 411%
Model
10
N6:50
N 100
N
N6t50
Ne:00
N6
N6:50
Ne:00
IDCF" (Wa et 2021)
0.13128
0.13992
0.14523
0.10220
0.12707
0.13821
0.05054
0.07402
0.08941
IDCF+GAT (Volickovié el al,, 2017)
0,15447
0.16938
0.17534
0,10564
0.13378
0.14393
0,04958
0.07250
0.06518
IDCF-GruphSAGE (Hamilion et al., 2017)
0.15787
0.17156
0.17701
0.10393
0.13352
0.14417
0,04904
0.07155
0.08419
IDCF+SGC (Wa 2019)
0.15537
0.16818
0.17548
0.10287
0.13208
0.14260
0.01883
0.06665
0.08456
ChehyCe (Deffemard et al., 2016)
0.15784
0.17406
0.18055
0.09916
0.12955
0.14175
0.04996
0.07268
0.08582
IDC+AAMA (Bianchi et al., 2021)
0.158.30
0.17320
0.17954
0.09731
0.12628
0.15829
0.04940
0.07192
0.08526
MRFCF (Steck, 2019)
0.10057
0.10410
0.10502
0.0WW67
0,11223
0.11275
0,05235
0.08047
0.05544
SGMC (Chen et al., 2021)
0.16418
0.18301
0.18764
0.07285
0.11110
0.12685
0.05402
0.8181
0.09710
GS-IMC (ours, Sec 3)
0,17057
0.18970
0.19168
0.07357
0.11115
0.12661
0,05501
0.08181
0.09759
BGS-IMC (ours, Sec
0.17909
0,19680
0.20134
0,09222
0.13082
0.14551
0,05593
0,08400
0.09982
We omit the results of Markov chain Monte Carlo based FISM (He & McAuley, 2016), variational auto-encoder based MultVAE (Liang et al., 2018), scalable Collrank (Wu et al., 2017b), graph neural networks GCMC (van den Berg et al., 2017) and NGCF (Wang et al., 2019), as their accuracies were found below on par in SGMC (Chen et al., 2021) and IDCF (Wu al., 2021).
5.2 ACCURACY COMPARISON
In this section, GS-IMC and BGS-IMC assume that the underlying signal is Auco-bandlimitedd and we compare them with eight state-of-the-are graph based baselines, including spatial graph models (i.e., IDCF (Wu et al., 2021), IDCF+GAT (Veličković et al., 2017), IDCF+GraphS (Hamilton et al., 2017)), approximate spectral graph models with high-order polynomials (i.e., IDCF+SGC (Wu et al., 2019). IDCF+ChebyNet (Defferrard et al., 2016), IDCF+ARMA (Bianchi et al., 2021)) and exact spectral graph models (i.e., MRFCF (Steck, 2019) and SGMC (Chen al., 2021))
In Table and Table 3, the results on the real-world Koubei, Tmall and Netflix show that BGS-IMC outperforms all the baselines on all the datasets. Note that MRFCF (Steck, 2019) is the full rank version of GS-IMC with (one-step) random walk regularization. We can see that MRFCF underper- forms its counterpart on all the three datasets, which demonstrates the advantage of the bandlimited assumption for inductive top-N ranking tasks. Further, BGS-IMC consistently outperforms GS-IMC on all three datasets by margin which proves the efficacy of the prediction-correet incremental updates. Additionally, we provide extensive ablation studies in Appendix C, scalability studies in Appendix D and more comparisons with SOTA sequential models in Appendix E.
algorithm for
To summarize. the reason why the proposed method can further improve the prediction accuracy due to 1) GS-IMC exploits the structural information in the 1-bit matrix to mitigate the negative influence of discrete label noise in the graph vertex domain; and 2) BGS-IMC further improves the prediction accuracy by considering continuous Gaussian noise in the graph Fourier domain and yielding unbiased and minimum-variance predictions using prediction-correction update algorithm.
6 CONCLUSION
We have introduced a unified graph signal sampling framework for inductive 1-bit matrix comple- tion, together with theoretical bounds and insights. Specifically, GS-IMC is devised to learn the structural information in the 1-bit matrix to mitigate the negative influence of discrete label noise in the graph vertex domain. Second, BGS-IMC takes into account the model uncertainties in the graph Fourier domain and provides a prediction-correctio annimum-varriace reconstructions. Both GS-IMC and BGS-IMC have closed-form solutions and are highly scalable. Experiments on the task of inductive top-N ranking have shown the supremacy.
update algorithm to obtain the unbiased and

---

Published as a conference paper at ICLR 2023
REFERENCES
Aamir Anis, Akshay Gadde, and Antonio Ortega. Efficient sampling set selection for bandlimited graph signals using graph spectral proxies. IEEE Transactions Signal Processing, 64(14): 3775-3789, 2016. 18
Mikhail Belkin, Irina Matveeva, and Partha Niyogi. Regularization and semi-supervised learning on large graphs. In Proceedings of International Conference on Computational Learning Theory (COLT '04), pp. 624-638- Springer, 2004. 2, 6
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7(11), 2006.
James Bennett, Stan Lanning, et al. The netflix prize. In Proceedings of KDD Cup and Workshop, volume 2007, pp. 35, 2007. 5
Kirell Benzi, Vassiis Kalofolias, Xavier Bresson, and Pierre Vandergheynst. Song recommendation with non-negative matrix factorization and graph total variation. In Proceedings of the Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP '16), pp. 2439-2444 IEEE, 2016.116111 14
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021. 8, 9, 14
Chao Chen, Dongsheng Li, Junchi Yan, Hanchi Huang, and Xiaokang Yang. Scalable and explain- able 1-bit matrix completion via graph signal learning. In Proceedings of the AAAI Conference Artificial Intelligence (AAAI 22), 2021. 2, 3, 8, 9, 15, 17
Gene Cheung, Enrico Magli, Yuichi Tanaka, and Michael K Ng. Graph spectral image processing. Proceedings the the IEEE, 106(5):907-930, 2018.
Kai-Yan Rai-Yang Chiang, Inderjit S Dhillon, and Cho-Jui Hsieh. Using side information to reliably learn low-rank matrices from missing and corrupted observations. The Journal of Machine Learning Research. (9)):3005--339, 2018. 14
Fan RK Chung and Fan Chung Graham. Spectral graph theory. American Mathematical Soc., 1997. 3
Emmanuel de Bézenac, Syama Sundar Rangapuram, Konstantinos Benidis, Michael Bohlke- Schneider, Richard Kurle, Lorenzo Stella, Hilaf Hasson, Patrick Gallinari, and Tim Januschowski. Normalizing kalman filters for multivariate time series analysis. In Proceedings of the Anmual Conference Neural Information Processing Systems (NeurIPS '20), volume 33, pp. 2995- 3007, 2020. 7
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS 166) pp. 3844-3852, 2016. 8, 9, 14, 17
Robin Devooght, Nicolas Kourtellis, and Amin Mantrach. Dynamic matrix factorization with priors on unknown values. In Proceedings of the ACM SIGKDD international conference on knowledge discovery and data mining (KDD '15), pp. 189-198, 2015. 3,
Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik. Spectral grouping using the nystrom method. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214 225, 2004. 17
Pere Giménez-Febrer, Alba Pages-Zamora, and Georgios B Giannakis. Matrix completion and trapolation via kernel regression. IEEE Transactions on Signal Processing, 67:5004-5017, 2019.
14
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS 17), pp. 1025-1035, 2017. 6, 8, 9, 14, 18
10

---

Published as a conference paper at ICLR 2023
David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129-1500 2011. 2, 3, 15
Ruining He and Julian McAuley. Fusing similarity models with markov chains for sparse sequential recommendation. In Proceedings of the IEEE International Conference on Data Mining (ICDM '16). pp. 191-200, 2016.
Xiangnan He, Hanwang Zhang, Min-Yen Kan, and Tat-Seng Chua. Fast matrix factorization for online recommendation with implicit feedback. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '16), pp. 549-558, 2016. 3, 14
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. Lightgnn: Simplifying and powering graph convolution network for recommendation. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '20), pp. 639-648, 2020. 14
Jian Huang, Shuangge Ma. Hongzhe Li, and Cun-Hui Zhang. The sparse laplacian shrinkage esti- mator for high-dimensional regression. Annals of statistics, 39(4), 2011. 2, 5,
Prateek Jain and Inderjit S Dhillon. Provable inductive matrix completion. arXiv preprint arXiv: 13066./306.00 1e..130660220 0626, 2013. 2,
Rudolph Emil Kalman. new approach to linear filtering and prediction problems. Journal of basic Engineering, 82(1):35-45, 1960. 2. 3, 15
Wang-Cheng Kang and Julian McAuley. Self-attentive sequential recommendation. In Proceedings of the IEEE International Conference on Data Mining (ICDM '18), pp. 197-206. IEEE, 2018. 3, 18
Usman Khan and José MF Moura. Distributing the kalman filter for large-scale systems. IEEE
Transactions on Signal Processing, 56(10):4919 4935, 2008. 2, 3, 15
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of
the International Conference on Learning Representations (ICLR '5), 2015. 8
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the International Conference Learning Representations (ICLR '16), 2016. 14
Antoine Ledent, Rodrigo Alves, Yunwen Lei, and Marius Kloft. Fine-grained generalization analy- sis of inductive matrix completion. In Proceedings of the Annual Conference on Neural Informa- tion Processing Systems (NeurIPS '21), 2021. 2, 14
Dawen Liang, Rahul G Krishnan, Matthew D Hoffman, and Tony Jebara. Variational autoencoders for collaborative filtering. In Proceedings of the Web Conference (WWW '18), pp. 689-698, 2018. 8.9.25 22
Gerald R MacLane. Concerning the uniformization of certain reimann surfaces allied the inverse- cosine and inverse-gamma surfaces. Transactions of the American Mathematical Society, 62(1): 99-113, 1947. 4
Xianghui Mao, Kai Qiu, Tiejian Li, and Yuantao Gu. Spatio-temporal signal recovery based on low rank and differential smoothness. IEEE Transactions on Signal Processing, 66(23):6281-6296 2018. 2, 4, 14, 15
Larry Matthies, Takeo Kanade, and Richard Szeliski. Kalman filter-based algorithms for estimating depth from image sequences. International Journal of Computer Vision, 3(3):209-22) 1989. 7
Peter S Maybeck. Stochastic models, estimation, and control. Academic press, 1982. 21
Maxwell J McNeil, Lin Zhang, and Petko Bogdanov. Temporal graph signal decomposition. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD (2/). pp. 1191-1201, 2021. 2, 3,3, 14, 15
11

---

Published as a conference paper at ICLR 2023
Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5)8808-828) 2018. 18
Jiahao Pang and Gene Cheung. Graph laplacian regularization for image denoising: Analysis in the continuous domain. IEEE Transactions on Image Processing, 26(4): 2017. 2
Karl Pearson. The problem of the random walk. Nature, 72(18655:294-2994 1905. 4
Isaac Pesenson. A sampling theorem homogeneous manifolds. Transactions of the American
Mathematical Society, 352(9))4257-426) 2000. 2, 4, 14
Transactions of the Isaac Pesenson. Variational splines and paley-wiener spaces combinatorial graphs. Constructive
Isaac Pesenson. Sampling in paley-wiener spaces combinatorial graphs.
American Mathematical Society, 360:5603-5677, 2008. 2, 4, 14, 19, 20
Approximation, 29(1):1-21, 2009. 3, 6, 19, 20
Daniel Romero, Meng Ma. and Georgios B Giannakis. Kemel-based reconstruction of graph signals. IEEE Transactions on Signal Processing, 65(3):764-778. 2016. 2, 4, 14
Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan Tibshirani. Total variation classes beyond 1d: Minimax rates, and the limitations of linear smoothers. Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS' 16), 29, 2016. 2,
Veeranjaneyulu Sadhanala, Yu-Xiang Wang, James L. Sharpnack, and Ryan J Tibshirani. Higher- order total variation classes on grids: Minimax theory and trend filtering methods. Proceedings of the Annual Conference Neural Information Processing Systems (NeurIPS '07), 30, 2017. 2,
Daniel Scharstein and Richard Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International journal of computer vision, 47(1):7-42, 2002. 7
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to net- works and other irregular domains. IEEE Signal Processing Magazine, 30(3):83 98, 2013. 2,3, 4, 15
Andrea Simonetto, Aryan Mokhtari, Alec Koppel, Geert Leus, and Alejandro Ribeiro. A class of prediction-correction methods for time-varying convex optimization. IEEE Transactions on Signal Processing, 64(17):45764451, 2016. 7
Alexander Smola and Risi Kondor. Kernels and regularization on graphs. Learning Theory and
Kernel Machines, pp. 144 158, 2003. 5
Harald Steck. Markov random fields for collaborative filtering. In Proceedings of the Annual Con- ference on Neural Information Processing Systems (NeurIPS '19), pp. 1474-5485, 2019. 2, 3, 8, 9, 15, 22
Daniel Stroock and Srinivasa RS Varadhan. Diffusion processes with continuous coefficients, Communications on Pure and Applied Mathematics, 22(3):345 1969. 4
Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequen- tial recommendation with bidirectional encoder representations from transformer. In Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM '19), pp. 1441-1450, 2019. 3, 18
Andrei Nikolaevich Tikhonov. On the solution of ill posed problems and the method of regulariza- tion. Doklady Akademii Nauk, 151(3):5015504, 1963. 4
Rianne van den Berg. Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv:
2017. 8, 9, 14
12

---

Published as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the International Conference on Learning Representations (ICLR 17), 2017. 6, 9, 14, 18
Paul Voigt and Axel Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, Ist Ed., Cham: Springer International Publishing, 10, 2017. 2, 14
Maksims Volkovs and Guang Wei Yu. Effective latent models for binary feedback in recommender systems. In Proceedings of the international ACM SIGIR conference on research and development in information retrieval (SIGIR '15), pp. 313-322, 2015.
Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua. Neural graph collabo- rative filtering. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR '19). pp. 165-174, 2019. 9
Norbert Wiener et al. Extrapolation, interpolation, and smoothing of stationary time series: with engineering applications, volume 8. MIT Press, 1964. 7
Chao-Yual Wu, Amr Ahmed, Alex Beutel, Alexander J Smola, and How Jing. Recurrent recom- mender networks. In Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM '17), pp. 495-503 7a. 8
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In Proceedings of the International Conference on Machine Learning (ICMI. 119), pp. 6861-6871, 2019. 8, 14
Liwei Wu, Cho-Jui Hsieh, and James Sharpnack. Large-scale collaborative ranking in near-linear time. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '17), pp. 515-524, 2017b. 9
Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Junchi Yan, and Hongyuan Zha. Towards open-world recommendation: An inductive model-based collaborative filtering approach. In Proceedings of the International Conference on Machine Learning (ICML '21), pp. 11329- -1339, 2021. 2, 8, 9,
14, 17, 23
Miao Xu, Rong Jin, and Zhi-Hua Zhou. Speedup matrix completion with side information: Appli- cation to multi-label learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS 11), pp. 2301-2309, 2013. 2, 14
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.
Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '18), pp. 974-983, 2018. 2, 14
Fajie Yuan, Xiangnan He, Haochuan Jiang, Guibing Guo, Jian Xiong, Zhezhao Xu, and Yilin Xiong. Future data helps training: Modeling future contexts for session-based recommendation. In Pro- ceedings of the Web Conference (WWW 20), pp. 303-313, 2020. 18
Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In Proceedings of the International Conference on Learning Representations (ICLR '20), 2020. 2,
Kai Zhong, Zhao Song, Prateek Jain, and Inderjit S Dhillon. Provable non-linear inductive matrix completion. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS 19), 2019. 2, 14
Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf. Learning with hypergraphs: Clustering, classification, and embedding. In Proceedings of the Annual Conference on Neural Information Processing Systems (NIPS '07), pp. 1601-1608, 2007. 4, 15
13

---

Published as a conference paper at ICLR 2023
In Appendix, we present the detailed related works in Appendix A, generalization of SGMC and MRFCF in Appendix B, extensive ablation studies in Appendix C and scalability studies in Ap- pendix D, limitation and future work in Appendix F, proofs of theoretical results in Appendix G I and more implementation details in Appendix J.
A RELATED WORK
Inductive matrix completion. There has been a flurry of research on problem of inductive matrix completion (Chiang al., 2018; Jain & Dhillon, 2013; Xu et al., 2013; Zhong et al., 2019), which leverage side information (or content features) in the form of feature vectors to predict inductively on new rows and columns. The intuition behind this family of algorithms is to learn mappings from the feature space to the latent factor space, such that inductive matrix completion methods can adapt new rows and columns without retraining. However, it has been recently shown (Zhang & Chen, 2020; Ledent et al., 2021; Wu et al., 2021) that inductive matrix completion methods provide limited performance due the inferior expressiveness of the feature space. On the other hand, the prediction accuracy has strong constraints on the content quality, but in practice the high quality content is becoming hard collect due to legal risks (Voigt & Von dem Bussche, 2017). By contrast, one advantage of our approach is the capacity of inductive learning without using side information.
Graph neural networks. Inductive representation learning over graph structured data has received significant attention recently due to its ubiquitous applicability. Among the existing works, Graph- SAGE (Hamilton et al., 2017) and GAT (Veličković et al., 2017) propose to generate embeddings for previously unseen data by sampling and aggregating features from a node's local neighbors. In the meantime, various approaches such as ChebyNet (Defferrard et al., 2016) and GCN (Kipf & Welling, 2016) exploit convolutional neural networks to capture sophisticated feature information but are generally less scalable. To address the scalability issue, Wu et al. (2019) develop simpli- fied graph convolutional networks (SGCN) which utilize polynomial filters to simulate the stacked graph convolutional layers. Furthermore, Bianchi et al. (2021) extend auto-regressive moving aver- age (ARMA) filters to convolutional layers for broader frequency responses.
To leverage recent advance in graph neural networks, lightGCN (He et al., 2020), GCMC (van den Berg et al., 2017) and PinSAGE (Ying et al., 2018) represent the matrix by a bipartite graph then generalize the representations to unseen nodes by summing the content-based embeddings over the neighbors. Differently, IGMC (Zhang & Chen, 2020) trains graph neural networks which encode the subgraphs around an edge into latent factors then decode the factors back to the value on the edge. Recently, IDCF (Wu et al., 2021) studies the prohlem in a downsampled homogeneous graph (i.e., user-user graph in recommender systems) then applies attention networks to yield inductive representations. Probably most closely related to our approach are IDCF (Wu et al., 2021) and IGMC (Zhang & Chen, 2020) which do not assume any side information, such as user profiles and item properties. The key advantage of our approach is not only the closed form solution for efficient GNNs training, but also the theoretical results which guarantee the reconstruction of unseen rows and columns and the practical guidance for potential improvements.
Graph signal sampling. In general, graph signal sampling aims reconstruct real-valued functions defined on the vertices (i.e., graph signals) from their values on certain subset of vertices. Existing approaches commonly build upon the assumption of bandlinitedness, by which the signal of interest lies in the span of leading cigenfunctions of the graph Laplacian (Pesenson, 2000; 2008). It is worth noting that we are not the first consider the connections between graph signal sampling and matrix completion, as recent work by Romero et al. (Romero et al., 2016) has proposed a unifying kernel based framework to broaden both of graph signal sampling and matrix completion perspectives. However, we argue that Romero's 's work and its successors (Benzi et al., 2016; Mao et al., 2018; McNeil et al., 2021) are orthogonal to our approach as they mainly focus on real-valued matrix completion in the transductive manner. Specifically, our approach concerns two challenging problems when connecting the ideas and methods of graph signal sampling with inductive onc-bit matrix completion one-bit quantization and online learning.
To satisfy the requirement of online learning, existing works learn the parameters for new rows and columns by performing either stochastic gradient descent used in MCEX (Giménez-Febree et al., 2019), or alternating least squares used in eALS (He et al., 2016). The advantage of BGS-IMC is three fold: (i) BGS-IMC has closed form solutions, bypassing the well-known difficulty for tuning
14

---

Published as a conference paper at ICLR 2023
learning rate; and (ii) BGS-IMC considers the random Gaussian noise in the graph Fourier domain, characterizing the uncertainties in the measurement and modeling; (iii) cercctioonnoorcttionn algo- rithm, resembling Kalman filtering, can provide unbiased and Aunimum-variane reconstructions.
Probably most closely related to our approach are SGMC (Chen et al., 2021) and MRFCF (Steck, 2019) in the sense that both of them formulate their solutions spectral graph filters and can be regarded as methods for data filtering in domains of discrete signal processing. More specifically, SGMC optimizes latent factors V, U by minimizing the normalized matrix reconstruction error:
min U.V
D
D. 1/2 RD, -V ll.
s.t. || U
||ا
V ||
(19)
while MRFCF minimizes the following matrix reconstruction error:
min R +X | X
s.t. diag (X) 0,
(20)
where the diagonal entries of parameter X is forced to zero. It is obvious now that both SGMC and MRFCF focus on minimizing the matrix reconstruction problem. This is one of the key differences to our graph signal sampling framework which optimizes the functional minimization problem as defined in Eq. 5. We argue that our problem formulation more suitable for the problem of inductive one-bit matrix completion, since it focuses on the reconstruction of bandlimited functions, no matter the function observed in the training or at test time. Perhaps more importantly, both methods (Chen et al., 2021; Steck, 2019) can be included special cases of our framework. We believe that unified framework cross graph signal sampling and inductive matrix completion could benefit both fields, since the modeling knowledge from both domains can be more deeply shared.
Ad Advantages of graph signal sampling perspectives. A graph signal sampling perspective requires to model 1-bit matrix data signals graph and formulate the objective in the functional space. Doing so opens the possibility of processing, filtering and analyzing the matrix data with vertex- frequency analysis (Hammond et al., 2011; Shuman et al., 2013). fimevvariant analysis (Mao al., 2018; McNeil et al., 2021), smoothing and filtering (Kalman, 1960; Khan & Moura, 2008) etc. In this paper, technically explore the of graph spectral filters to inductively recover the missing values of matrix, halman-filterin based approach to deal with the streaming data in online learning scenario, and vertex-frequeccy analysis to discover the advantages of dynamic BERT4REC model over static BGS-IMC model. We believe that our graph signal sampling framework can serve as new paradigm for 1-bit matrix completion, especially in large-scale and dynamic systems.
B GENERALIZING SGMC AND MRFCF
This section shows how GS-IMC generalizes SGMC (Chen et al., 2021) and MRFCF (Steck, 2019).
GS-IMC generalizes SGMC. Given the observation R. follow standard routine of hypergraph (Zhou et al., 2007) to calculate the hypergraph Laplacian matrix L = I - D, R/D R D.
where D, (D.) is the diagonal degree matrix of vertices (edges). Then the rank-k approximation
(see Eq. (9) in (Chen et al., 2021)) is equivalent to our result using bandlimited norm R(A) = A Rg and R()) so otherwise,
y Σ (1 R(Xi)//))uuu u s= Σ Uuu S.U.S
where we set 4 and 1om R(A)/== for A and matrix Up comprises k leading cigenvectors whose cigenvalues are less than or equal to dg-
GS-IMC generalizes MRFCE Given R, we simply adopt the correlation relationship construct the affinity matrix and define the Laplacian as L = 21 D. 1/2RR D Then the matrix approximation (see Eq. (4) in (Steck, 2019)) is equivalent
GS-IMC approach using one-step
15

---

Published as a conference paper at ICLR 2023
random walk norm,
y Σ [
a )
1 )nim
Σ
x x yuis
1
(a+ 1)1 1 }
[I - (a-- RR D!!/
where we set yp and a 2 Amax is pre-specified parameter for the random walk regularization.
C ABLATION STUDIES
This study evaluates how GS-IMC and BGS-IMC perform with different choice of the regularization function and the graph definition. In the following, we assume the underlying signal to recover is in the Faley-Wiene' space PW X (G), and hence we only take the first 1000 cigenfunctions whose eigenvalues are not greater than X1000 to make predictions.
C.I IMPACT OF REGULARIZATION FUNCTIONS
Table 4 and show that for the proposed GS- models, Tikhonov regularization produces the best HR and NDCG results on both Koubei and Netflix, while Diffusion process regularization performs the best on Tmall. Meanwhile, BGS-IMC with random walk regularization achieves the best HR and NDCG results on Koubei, while Tikhonov regularization and Diffusion process regularization are best on Tmall and Netflix. Perhaps more importantly, BGS-IMC consistently outperforms GS-IMC on all three datasets by margin which proves the efficacy the prediction-correction algorithm.
We highlight the reason why BGS-IMC can further improve the performance of GS-IMC is due to the fact that BGS-IMC considers Gaussian noise in the Fourier domain and the prediction- cetrrcionnoooecttionn update algorithm is capable of providing unbiased and moniimum-varianne predictions.
Table 4: Hit-Rate of GS-IMC, BGS-IMC with different regularization R(A) for inductive top-N ranking. Overall, BGS-IMC consistently outperforms GS-IMC. The standard errors of the ranking metrics are less than 0.005 for all the three datasets.
Koubel, Density 08%
Tmall, Density=O. 10%
Netflis, Density=1.441%
Model
H6:50
H@10
H@10
100
GS-IMC-TIE DS-IMMC-Tibbooov (Sec. 3)
0.23430
0.31995
0.35065
0.13363
0.30630
0.40370
0.09725
0.22733
0.32190
DS--IMC-Diflusine Process (Sec.
0,23460
0.31440
0.34370
0.13677
0.30863
0.40390
0.09678
0.21980
0.31750
GS-IMC-Randon Walk (Sec. 3)
0.23360
0.31860
0.34935
0.13423
0.30853
0.40550
0,09660
0.22528
0.32235
GS-IMC-Imeerse Cosine (Sec. 3)
0,23300
0.31710
0.34645
0.13537
0.31027
0.40760
0.09675
0.22575
0.32225
DUS-IMCCTikkonee (Sec.
0.32320
0.16733
0.43690
0,09988
0,23390
0.33063
AGS-IMC-Diffussn Process (Sec. 4)
0.24388
0.32185
0.34910
0.16680
0.34263
0.43317
0.09853
0.22630
0.32450
BGS-IMC- RaS-dMM-Random Walk (Sec. 4)
0,24390
0.32545
0.35345
0.16303
0.34127
0.43447
0.09825
0.23028
0.32973
BGS-IMC-Inveree Cosine (Scc. 4)
0.24275
0.32405
0.35130
0.16567
0.34303
0.43637
0.09945
0.23260
0.33055
Table 5: NDCG of GM-IMC IMC with different regularization for inductive top-N ranking.
Koubei, Density=O 08%
Tmall, Density=O.10% 10%
Netllis, Density=1.41%
Model
N6:50
N@
N@10
N6:50
N6 100
N@
N@:0
N@
GS-IMC-Tik (Sec. 3)
0,17057
0.19970
0.19468
0.07174
0.10940
0.12519
0.05399
0.08181
0.09709
GS-IMC-DifTusion
3)
0.16943
0.18742
0.19219
0.11115
0.12661
0.05504
0.08134
0.09713
CS-IMCCRandom Walk (Scc. 3)
0.16846
0.15753
0.19253
0.07208
0.11011
0.12582
0.05452
0.08158
0.09759
GS-IMC-Inverse Cosine (Sec.
0,16560
0.15553
0.18930
0.07265
0.11083
0.12660
0.05410
0.08173
0.09734
MTT.-MMC- (Soc.
0.17540
0.09144
0.13021
0.06535
0.09982
BGS-IMC-Diffusim Process (Sec. 4)
0.17909
1969664
0.20108
0.09222
0.13082
0.14551
0,05393
0.08321
0.09909
BGS-IMC-Rande Walk 4)
0,17854
0.19680
0.20134
0.08956
0.12873
0. 1.14887
0.05533
0.08349
0.09958
BGS-IMC-Inveers Cosine (Soc. 4)
0.17625
0.19451
0.19894
0.09094
0.12992
0. 0.145007
0.05546
0.08394
0.09964
16

---

Published as a conference paper at ICLR 2023
Table 6: HR, NDCG on the Netflix prize data of GS-IMC (w/ random walk regularization), where
we adopt different methods for constructing the homogeneous graph for inductive top-N ranking.
HR@ 10
HR 100
NDCG@10
NDCG@50
NDCG@ 100
GS-IMC w/ Hypergraph
0.0066000000006
0.22328+00 0002
0 0.3233+0000011
005452-00004
0.06155-000004
0,09759+00 0000
GS-IMC w/ Covariance 0.09767=#0.001
0.2238
0.31312+0.0052
0.05454-0.0005
0.08171
0.09613+000007
C.2 IMPACT OF GRAPH DEFINITIONS
Table 6 present the HR and NDCG results of GS-IMC with one-step random walk regularization on the Netflix prize data. To avoid the clutter, we omit the results of GS-IMC with other regularization functions, since their results share the same trends. It seems that the regular graph that use covariance matrix as the affinity matrix has better HR and NDCG results when recommending 10 and 50 items, while the hypergraph helps achieve better results when recommending 100 items.
D SCALABILITY STUDIES
The solution for either GS- IM- or BGS-IMC requires to compute leading eigenvetors whose eigen- values are less than or equal to pre-specified w. However, one might argue that it is computationally intractable on the industry-scale datasets. To address the concerns, one feasible approach to perform the Nyström (Fowlkes et al., 2004) method to obtain the leading eigenvectors. For the com- pleteness of the paper, we present the pseudo-code of the approximate cigendecomposition (Chen et al., 2021) in Algorithm 1, of which the computational complexity is O + k²) where is the number of columns in E., is the number of sampled columns and le is the number of eigenvectors to compute. This reduces the overhead from (nn)) O + 1-²), linear the number of rows.
To evaluate how the proposed GS- IMC and BGS- IMC methods perform with the approximate eigen- vectors, we conduct the experiments on the largest Netflix prize data. Table 7 reports the HR, NDCG and runtime results for the standard GS-IMC and BGS-IMC methods, and their scalable versions entitled GS-IMCs and BGS-IMCs. To make the comparison complete, we also present the results of neural IDCF (Wu et al., 2021) model equipped with ChebyNet (Defferrard et al., 2016). It is obvious that the standard GS-IMC and BGS-IMC methods consume only small fraction of train- ing time, required by graph neural networks. Meanwhile, GS-IMCs achieves comparable ranking
Algorithm Approximate Eigendecomposition
Require: n 1 matrix derived from columns sampled from n kernel matrix without replacement, / x matrix A composed of the intersection of these columns, / x matrix W, rank k. the oversampling parameter p and the number of power iterations q.
Ensure: approximate eigenvalues Σ and eigenvectors Ú.
1: Generate a random Gaussian matrix E ( then compute the sample matrix A
2: Perform QR- DR-Decomposition on A UΩ to obtain an orthonormal matrix Q that satisfies the equa- tion A QQ A then solve ZQ Ω = Q WS.
3: Compute the eigenvalue decomposition on the (k + p)-by-(k + p) matrix Z, i.e.,
Uz Uz T to obtain Uw = QU l.: k] and Ew Σz|: k, k).
4: Return Σ Ew. Ú CA 1 E. 1/2
Table 7: Hit-Rate, NDCG and Runtime of the enhanced IDCF (Wu et al., 2021) model equipped with ChebyNet (Defferrard et al., 2016), GS-IMC, BGS-IMC (w/ random walk regularization) and their scalable versions (i.c., GS-IMCs and BGS-IMCs) for inductive top-N ranking Netflix data.
HR8110
50
100
NDCG 10
NDCG@50
NDCG 100
Runtime
IDCF NhebyNett
0.0066
0.19335400042
0.0057
0.099911000010
0.08582440.003
GS-IMC
0.000000.0006
0,222244000022
0.32235-00001
0.05452:0.0004
0.0015--0.0004
0.0975010.0000
12.0 min
GS-IMCs
0.00600000007
0192
$31994-0.0015
0.05352+0.006
0.08135-0.0066
0.19657+000002
1.5 min
BGS-IMC
0.00968_000006
0.2339010.0005
0.00063_000009
0.0559330..000
0000000000004
BGS-IMCs
0.10005
0.2531840.0014
0.32750-0.0020
0.05508++0.006
0.08365
0.99690+000001
2.0 min
17

---

Published as a conference paper at ICLR 2023
GS-IMC
BGS-IMC
BERTAREC
Energy
0.025
0.025
0.000
0.000
0.000
Apm
Apa00
Apn
Auamn
Aga
Agn
Age
Asco
Auaa
Figure 4: Spectrum analysis for static GS-IMC, BGS-IMC and dynamic BERTAREC on the Koubei dataset. Compared to BERTAREC, the energy of GS-IMC and BGS-IMC is concentrated on the low frequencies since the high-frequency functions are highly penalized during minimization.
performance to GS-IMC, while improving the efficiency by 8X. Likewise, BGS-IMCs enjoys the improvement in the system scalability without significant loss in prediction accuracy. The overall results demonstrate that GS-IMC and BGS-IMC are highly scalable in very large data.
E SPECTRUM ANALYSIS AND DISCUSSION WITH SEQUENTIAL MODELS
We compare BGS-IMC with recent sequential recommendation models, including Transformer-based SAS-
Table 8: Comparisons to neural sequential models for the task of inductive top-N ranking on Koubei.
Model
BERTAREC
SASREC
GREC
BGS-IMC
REC (Kang & McAuley, 2018), BERT-based BERTAREC (Sun al., 2019) and causal CNN based GREC (Yuan et al., 2020). We choose embedding size of 256 and search the optimal Each model is configured using the same parameters provided by the original paper i.c., two attention blocks with one head for SAS- REC, three attention blocks with eight heads for BERT4REC and six dilated CNNs with degrees 2,2,,,4, 4, 4, 4,8 for GREC.
H& 10
0.23760
0.23015
0.22405
0.24390
H@50
0.32385
0.30500
0.30065
0.32545
@@
0.35965
0.34735
0,34350
0,35345
N@ 10
0.18822
0.18496
0.18118
0.17854
N@50
0.20663
0.20137
0,19816
0.19680
by grid. N@ 100
0.21402
0,20819
0,20583
0,20134
Runtime
89 min
37 min
27 min
83 sec
Table 8 presents HR and NDCG results on Koubei for inductive top-N ranking. Note that BGS-IMC only accepts the most recent behavior to update the obsolete state for incremental learning, whereas SASREC, BERT4REC and GREC focus on modeling the dynamic patterns in the sequence. Hence, such a comparison is not in favor of BGS-IN IMC. Interestingly, we see that static BGS-IMC achieves comparable HR results to SOTA sequential models, while consuming small fraction of running time. From this viewpoint, BGS-IMC is more cost-effective than the compared methods.
To fully understand the performance gap in NDCG, we analyze GS-IMC, BGS-IMC and the best baseline BERT4REC in the graph spectral domain, where we limit the &g norm of each user's spectral signals to one and visualize their averaged values Figure 4. As expected, the energy of GS-IMC and BGS-IMC is concentrated on the low frequencies, since the high-frequency functions are highly penalized during minimization. Furthermore, the proposed prediction-correcte increases the energy of high-frequency functions. This bears similarity with BERT4REC of which high-frequency functions are not constrained and can aggressively raise the rankings of unpopular items. This explains why BERT4REC and BGS-IMC have better NDCGs than GS-IMC.
update algorithm
F LIMITATION AND FUTURE WORK
Limitation on sequence modeling. The proposed BGS-IMC method is simple and cannot capture the sophisticated dynamics in the sequence. However, we believe that our work opens the possibil- ity of benefiting sequential recommendation with graph signal processing techniques, for example extended Kalman filter, KalmanNet and Particle filter.
Limitation on sample complexity. The sample complexity is not provided in the paper, and we believe that this an open problem due to the lack of regularity the graph which prevent us from defining the idea of sampling "every other node" (the reader is referred to (Anis et al., 2016; Ortega et al., 2018) for more details).
Future work on deep graph learning. Though GS-IMC and BGS-IMC are mainly compared with neural graph models, we note that our approach can help improve the performance of existing graph neural networks including GAT (Veličković et al., 2017) and SAGE (Hamilton et al., 2017), etc. We summarize the following directions for future works: 1) It is interesting to see how GS-IMC takes advantage of content features. One feasible idea is
GS-IMC multi-scale wavelets which
18

---

Published as a conference paper at ICLR 2023
can be easily adapted to graph neural networks; 2) BGS-IMC also be utilized to optimize the aggregation module for the improved robustness, as every neighbor's representation can be viewed as measurement of the query node's representation.
G PROOF OF THEOREM
Proof. This proof is analogous to Theorem 1.1 in (Pesenson, 2009), where we extend their results from Sobolev norm to broader class of positive, monotonically increasing functionals.
Proof of the first part of the Theorem
Suppose that the Laplacian operator t. has bounded inverse and the fitting error = O, if y E PW (9) and ys interpolate y on A Lo for any o E L2( Then y - yı (2(2)) and we have
V -2e and Q admits the Poincare inequality Ø ||
ly yxl = Al| - --)lll
At this point, we can apply Lemma 7 with = a and Φ = y - yk. It gives the following inequality
y y& I| A || - 9k) ||
for all k= = 0, Since R(A) is positive and monotonically increasing function, it gives
* Ly - ýx) I| A || R(E)*(y - -9x) Il
Because the interpolant ys minimize the norm || R(L)* ||, we have
|| IR() 5ta) ||s|| R( + || R( Ils 2 R(E) || As for functions y E (9) PW H(w) ((w (9) the Bernstein inequality in Lemma holds
R(E) IlS R(w)* k y Il, N.
Putting everything together, we conclude the first part of Theorem 4: Proof of the second part of the Theorem 4. Since AR(w) < holds, it gives the following limit
|| y - yz | (AR(w) |l y (R,))( < 1, E
(21)
lim (AR(w))* O and lim y ÿx 1S 0
k-000
k-000
With non-negativity of the norm, we have
lly jxll 1ll 2 O. This implies the second part of the Theorem
(22)
lim yk- k-000
(23)
Lemma 7 (restated from Lemma 4.1 in (Pesenson, 2009)). Suppose that bounded self- adjoint positive definite operator in Hilbert space (z) and || Φ || a EΦ || holds true for any Lg( and a positive scalar a > then for all k 2 = O, 1,..., the following inequality holds true
Φll S a ||
(24)
Lemma 8 (restated from Theorem 2.1 in (Pesenson, 2008)). A function f E L2(g) belongs to PW (G) if and only if the following Bernstein inequality holds true for all E R_
tyy || w" | |l.
(25)
19

---

Published as a conference paper at ICLR 2023
G.1 EXTRA DISCUSSION
In (Pesenson, 2008), the complementary set S = Ωg = V - S2 which admits Poincare inequality is called the A-set. Theorem 4 in our paper and Theorem 1.1 in (Pesenson, 2009) state that bandlimited functions y E PWW can be reconstructed from their values on a uniqueness set S = V-S. S. To better understand the concept of A-set, we restate Lemma 9 from (Pesenson, 2008) which presents the conditions for A-set. It is worth pointing out that (i) the second condition suggests that the vertices from A-set would likely be sparsely connected with the uniqueness set S2; and (ii) the vertices in A-set are disconnected with each other or isolated in the subgraph constructed by the vertices S, otherwise there always exists a non-zero function & E L2(S), || & || which makes L& ||= O. Lemma' 9 (restated from Lemma 3.6 in (Pesenson, 2008)). Suppose that for a set of vertices S SC.. V (finite or infinite) the following holds true:
1. every point from S is adjacent to a point from the boundary bS, the set of all vertices in V which not in S but adjacent vertex in S:
2. for every S there exists least one adjacent point un E bS whose adjacency set intersects S only over v;
3. the number A = supres d(u) is finite;
Then the set S is A-set which admits the Poincare inequality
|| & I| Lo 11. L2(S).
(26)
our experiments for recommender systems, each user's ratings might not comply with Poincare inequality. This is because there exists some users who prefer niche products/movies (low-degree nodes). As shown in Fig. 2, user preferences on low-degree nodes are determined by high-frequent functions. When R(w) is not large enough, Poincare inequality does not hold for such users. This also explains why our model performs poorly for cold items.
In
Regarding to choice of parameter k. empirical results show that using k 2 2 does not help improve the performance, and note that when k is large enough, all kernels will be reduced to bandlimited norm, i.e., R[(A) if S A S 1, since the gap between eigenvalues shrinks.
H PROOF OF THEOREM
Proof. Let & denote the random label noise which flips to O with rate p. assume that the sample s = y + E is observed from y under noise E, then for a graph spectral filter H = (I R(L)/p)- with positive & > 0, we have
MSE(Y, })
1 E y n E H + (I- H,) IP.
H + E) 112
(27)
n
where the last inequality holds due to the triangular property of matrix norm.
To bound E
H 11?, let C2 (w)((w) y |]. then
E
H 2 Σ p(H p(H (.(..) x -1)2 + (1 p) (H p.(r.0) x 0)2
y(m)=1
Σ
H (())) = =
Hpy I|2
= p
y(u)=1
(6)
P H₂Y 1|== sup p H Rl.RR-1220 1/2 1/2(1.)2 112 ||
sup
[C
pC max
H 1/2(()()
max =pc
1
I.... m (1 + R()))/p)² R(Ns)
S R(A))( + 2(
(28)
20

---

Published as a conference paper at ICLR 2023
where (a) follows the definition of the flip random noise and (b) holds the fact that y is in the Paley-Witse Wiener space (9). As for the second term,
Hpyy 1
sup
(I-H,)y 1|
(a)
| (I-H,)R 1/2 (L)z 1|?
sup
||
Og
(
C. max
(1
1
1+ R(W))/ R(A)
Ch
R(A)/²
40 I=l...,7
(R(A))/4 +12
(h) C2
(29)
4Gp
where (a) holds due to the fact that the eigenvectors of H are the eigenvectors of R(F.); and (b)
follows the simple upper bound x/(1 + x)²² - 1/4 for x 2 O.
By combing everything together, conclude the result
E MSE(y,
Ch
R(A)) R()1))2 + )
PC²
(30)
H.1 EXTRA DISCUSSION
Choosing to balance the two terms on the right-hand side above gives D0 co for < 1/8 and
1 1+A0 R(A1)/p' = =2p1/3 1/3 for 2 1/8. Plugging in this choice, we have the upper bound if p 2 1
8
E MSE(X, 8) S 4R(A))
(3p - -1),
(31)
and if < a.4 then the upper bound is
Chi
E MSE(y,
8)
(32)
4R(X))
This result implies that not greater than 1/8, and need to be carefully tuned when the flip rate is greater than 1/8.
large &o to obtain accurate reconstruction when the flip rate p is
I PROOF OF PROPOSITION 6
As below we present the proof in a Bayesian framework, and the reader referred to (Maybeck, 1982) for geometrical interpretation of Monte Carlo estimate statistics.
Proof of the minimal variance
To minimize the estimate variance, we need to minimize the main diagonal of the covariance P Pnew:
trace P Puew] trace - (I-K)P (I- K)T + K.,
Then, differentiate the trace of P new with respect to K
d trace P new
d trace
2KP new
2P new
trace 2K
The optimal K which minimizes the variance should satisfy d trace(P new )/dK/ = 0, then it gives
K(I P new)
P new-
21

---

Published as a conference paper at ICLR 2023
U1
11
u
U2
Transductive ranking
(b) Inductive ranking
Figure 5: Evaluation protocols, where the users in top block (green) are used for training and the ones in bottom block (pink) are used for evaluation. (a) transductive ranking, where the model performance is evaluated based on the users already known during the model training; (b) inductive ranking, the model performance evaluated using the users unseen during the model training.
This implies that the variance of estimate Xnew minimized when K P new (I + P Pnew)_
Proof of the unbiasedness
Suppose that the obsolete estimate unbiased, i.c. IEX x, then using Eq. (11) we have
E
[new)
E(x + FAs)
FAS
Xnew
Because of Eq. (12) and the measurement noise has zero mean, gives
E
Znew
E
Xnew v) Xnew
Putting everything together, we conclude the following result
E &new
E Xnew + K(Znew
&new)
K ((Xnew Xnew) Xnew
(33)
This implies that the estimate state Knew is unbiased.
IMPLEMENTATION DETAILS
In this section, we present the details for our implementation in Section incluudnn the additional dataset details, evaluation protocols, model architectures in order for reproducibility. All the experi- ments are conducted on the machines with Xeon 3175X CPU, 128G memory and P40 GPU with 24 GB memory. The configurations of our environments and packages are listed below:
Ubuntu 16.04
CUDA 10.2
Python 3.7
Tensorflow 1.15.3
Pytorch 1.10
DGL 0.7.1
NumPy 1.19.0 with MKL Intel
J.1 ADDITIONAL DATASET DETAILS
We use three roaldworld datasets which are processed in line with (Liang et al., 2018; Steck, 2019): (1) for 2oubei², keep users with at least records and items that have been purchased by least 100 users; and (2) for Tmall?, we keep users who click at least 10 items and items which have been seen by least 200 users; and (3) for Netflix we keep all of the users and items. In addition, chose the random seed as 9876 when splitting the users into training/validationn validationn/ess sets.
hhtrp::/tianchii.o wwtp::hhwh.illuuuoo.aoaooeeo comm///ttte//aaaaaaaaa/laalaaasa 'httpss/ttiacchii wwwpiiiaaaaaiiiaa..aaa.. http://wwm//maaeeeaaaaaaaaaaaaaa http::///waggl..cooo//e/eeiiiice
22

---

Published as a conference paper at ICLR 2023
J.2 EVALUATION PROTOCOLS
In Figure 5, we illustrate the difference between the transductive ranking and inductive ranking evaluation protocols. In the transductive ranking problem, the model performance is evaluated the users already known during the model training, whereas the model performance evaluated on the unseen users in the inductive ranking problems. It worth noting that in the testing phrase, we sort all interactions of the validation/test users in chronological order, holding out the last one interaction for testing and inductively generating necessary representations on the rest data. In a nutshell, we evaluate our approach and the baselines for the challenging inductive next-item prediction problem.
J.3 EVALUATION METRICS
We adopt hit-rate (HR) and normalized discounted cumulative gain (NDCG) to evaluate the model performance. Suppose that the model provide N recommended items for user u as Ry, let T, denote the interacted items of the user, then HR is computed as follows:
HR@N E,, 1T..
(34)
where | is equal to 1 if set Ω is not empty and is equal to 0 otherwise. NDCG evaluates ranking performance by taking the positions of correct items into consideration:
1 N
NDCG@N = DCG@N
(35)
Z
lo
where Z is the normalized constant that represents the maximum values of DCG@N for T..
J.4 GRAPH LAPLACIAN
Let R denote the item-user rating matrix, D, and D. denotes the diagonal degrec matrix of vertices and edges respectively, then graph Laplacian matrix used in our experiments defined as follows:
I=I-D T. 1//22
(36)
where I is identity matrix.
J.5 DISCUSSION ON PREDICTION FUNCTIONS
In experiments, we focus making personalized recommendations to the users, so that interested in the ranks of the items for each user. Specifically, for top-k ranking problem we choose the items with the k k-largest predicted ratings,
Recommendation@k- = max
Σ y(v).
(37)
10|=k vEO,ugR
More importantly, our proposed method is also suitable for the link prediction problem, where the goal is classify whether an edge between two vertices exists or not. This can be done by choosing splitting point to partition the candidate edges into two parts. There are many different ways of choosing such splitting point. One can select the optimal splitting point based on the ROC or AUC results on the validation set.
J.6 MODEL ARCHITECTURES
As mentioned before, equip IDCF (Wu et al., 2021) with different GNN architectures as the backbone. Here we introduce the details for them.
GAT. We use the GATComy layer available in DGL for implementation. description as below:
The detailed architecture
A sequence of one-layer GATCom with four heads.
Add self-loop and use batch normalization for graph convolution in each layer.
23

---

Published as a conference paper at ICLR 2023
Use tanh the activation.
Use inner product between user embedding and item embedding ranking score.
GraphSAGE. We the SAGECom layer available in DGL for implementation. The detailed
architecture description as below:
sequence of two-layer SAGEConv.
Add self-loop and use batch normalization for graph convolution each layer.
Use ReLU as the activation.
Use inner product between user embedding and item embedding as ranking score.
SGC. We use the SGCom layer available in DGL for implementation. The detailed architecture description is as below:
One-layer SGConv with two hops.
Add self-loop and use batch normalization for graph convolution in each layer.
Use ReLU the activation.
Use inner product between user embedding and item embedding as ranking score.
ChebyNet. We the ChebConv layer available in DGL for implementation. The detailed archi- tecture description is as below:
One-layer ChebConv with two hops.
Add self-loop and use batch normalization for graph convolution in each layer.
Use ReLU as the activation.
Use inner product between user embedding and item embedding as ranking score.
We use the ARMAConv layer available in DGL for implementation. The detailed architec- ture description below:
ARMA.
One-layer ARMACon with hops.
Add self-loop and use batch normalization for graph convolution each layer.
Use tanh as the activation.
Use inner product between user embedding and item embedding as ranking score.
We also summarize the implementation details of the compared sequential baselines as follows.
SASREC. We use the software provided by the authors for experiments. The detailed architecture description as below:
A sequence of two-block Transformer with one head.
Use maximum sequence length
Use inner product between user embedding and item embedding as ranking score.
BERTAREC. We use the software provided by the authors for experiments. The detailed architec-
ture description is as below:
A sequence of three-blocd block Transformer with eight heads.
Use maximum sequence length to 30 with the masked probability 0.2.
Use inner product between user embedding and item embedding as ranking score.
24

---

Published as a conference paper at ICLR 2023
We use the software provided by the authors for experiments. The detailed architecture description as below:
GREC.'
A sequence of six-layer dilated CNN with degree 2, 4,
Use maximum sequence length 30 with the masked probability 0.2.
Use inner product between user embedding and item embedding as ranking score.
GS-IMC
Energy
0.025
0.000
Ao
X200
A400
A600
A
A1000
Figure 6: Spectrum analysis for static GS-IMC, of which the energy is concentrated on the low frequencies since the high-frequency functions are highly penalized during minimization.
BGS-IMC
Energy
0.025
0.000
A200
A400
A600
Aso0
A1000
Figure 7: Spectrum analysis for static BMC-IMC, of which the energy is concentrated on the low frequencies since the high-frequee frequeryy functions are highly penalized during minimization.
BERT4REC
Energy
0.025
0.000
X200
A400
X
A
A1000
Figure 8: Spectrum analysis for sequential BERT4REC, which the high- frequency functions are not highly penalized and can aggressively raise the rankings of unpopular items.
25


Reviews:
[{"review_id": "ezhRXJO-Le", "reviewer": "Reviewer_rJLs", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 1, "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": "", "summary_of_the_paper": "The paper studies the problem of one-bit matrix completion. The paper claims to propose a unified graph signal sampling framework that enjoys the benefits of graph signal analysis and processing. The authors provide some theorems related to the quality of reconstruction.", "summary_of_the_review": "The paper is hard to understand in the current shape.", "strength_and_weaknesses": "Due to either: the lack of my knowledge in this area, or: the writing of the paper, I cannot understand what problem this paper tries to solve. I understand what one-bit matrix completion is, but I do not understand, at least from the first three Sections, how it is \"unified\" with graph signals or graph Laplacians. This is reflected in my confidence rating. \n\nSee Clarity, Quality, Novelty And Reproducibility for details.\n\n- How should readers interpret the conditions in Theorem 3 and 4? Can the authors provide some examples in which they hold? Do these conditions hold in the experiments?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Zc_g_HWPwT", "reviewer": "Reviewer_fzvN", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "Authors extend graph signal processing techniques to cope with discrete random label noise. \n", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strength: Authors consider a useful application of graph signal processing to recommender systems. \n\nWeaknesses: \n* The main contributions of the paper are unclear. Is it a novel graph signal model ? Is it a novel graph signal recovery method (Eq. (5)) ? \n\n* At least in its application to recommender systems I would like to see a comparison of the proposed methods with existing network Lasso methods as proposed e.g. in \n\nN. Tran, H. Ambos and A. Jung, \"Classifying Partially Labeled Networked Data VIA Logistic Network Lasso,\" ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 3832-3836, doi: 10.1109/ICASSP40776.2020.9054408.\n\nA. Jung, \"Networked Exponential Families for Big Data Over Networks,\" in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.\n\n* Theorem 3 needs more discussion. How to choose the parameter k ? How restrictive is the Poincare condition ? Is this condition satisfied in the numerical experiments ? \n\n* The problem formulation needs to be made more precise and placed earlier in the paper. Currently it seems only described in Section 4.1. which is too late. \n\n* What is \\hat{y} in (9) ? \n\n* Pls explain more clearly the probability distribution underlying the expectation in Eq. (9). \n\n* Pls discuss more explicitly how the graph (Laplacian) has been obtained for the numerical experiments. \n\n* \"The classical sampling theorem states that functions...\" what is the \"classical sampling theorem\" ? \n\n\nminor errors: \n\n* \"...the testing phrase,..\" \n\n* \"..experiments, we define the hypergraph using matrix R..\" unclear what the matrix R is/how obtained. \n\n* \"..methods are not well suited to our 1-bit matrix completion problem due to the issues of 1-bit quantization...\" pls try to be more specific. what are these \"issues\" ? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R6O7BufEZZy", "reviewer": "Reviewer_idfJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The authors propose a graph signal sampling approach to matrix completion/recommendation systems. They propose regularization approaches for noise reduction, and also provide a Bayesian extension that takes into account model uncertainty. They show that their approaches are scalable and provide both theoretical guarantees as well as experimental evaluations.  ", "summary_of_the_review": "Overall, the authors proposed a reasonable and novel method for inductive 1-bit matrix completion using ideas from graph signal sampling. The main issue currently is their exposition. It could be a good paper if the authors improve their exposition, especially on their motivation of the inductive 1-bit matrix completion problem as well as their description of their \"Bayesian\" model. ", "strength_and_weaknesses": "Strengths: \n\n- The study cited many of the related prior art in a very comprehensive manner\n- The core idea of the graph signal sampling approach + regularization is very natural, and admit simple closed form solutions\n- reasonable error analysis is given for the method \n- extensive experiments, with good results obtained for the proposed method against competitors \n\n\nWeaknesses: \n\n- the paper jumps directly into describing the problem of inductive 1-bit matrix completion. The motivation is insufficient in my opinion given that this is a very specific problem. I suggest that the authors spend a paragraph at the beginning talking about WHY the 1-bit formulation is helpful and why inductive matrix completion is useful so a broader audience can be reached. \n\n- The \"Bayesian\" formulation, is not described clearly and sufficiently. The authors jump straight to describing a stochastic filtering problem and their prediction correction algorithm. There is minimal description of notation, and there is 0 discussion of model choice and why this model is sensible and as well as the choice of parameters such as Sigma_nu and Sigma_eta. For those who are not familiar with this model/literature, it can be very confusing what the prior is and why the proposed filtering algorithm works.\n\n- Without more significant exposition for the Bayesian model, the current Bayesian model reads more like a distraction from the main theme of the paper.\n\nI think the paper's readability and clarity would be greatly improved if the authors address the two issues above. \n\n\nMinor Typos:\n\nI think in the first paragraph of the first page, \"a subset of positive examples phi randomly sampled from {(i, j) | ... .}\" I think inside the set, in addition to j \\leq m, there should also be i \\leq n\n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QAP-P-kh7t", "reviewer": "Reviewer_ZrCo", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies the problem of one-bit completion: the task is to recover a vector $y \\in \\\\{0, 1\\\\}^n$ from the observation of a subset of its positive entries. The model assume that there exists a matrix $R \\in \\\\{0, 1\\\\}^{m \\times n}$ containing additional information about the model, e.g. $m$ previous partial observations of similar data.\n\nThe main idea is that this matrix $R$ can be turned into a graph on $n$ vertices, whose weights represent the similarity between vertices. The completion problem can thus be cast as a graph signal sampling problem using the laplacian $L$ of the graph: the general assumption is that $y$ is mostly concentrated on the low-frequency eigenvectors of $L$. \n\nNext, the authors study the on-line version of this problem, where the observations can be noisy. In this case, they propose a Bayesian algorithm that assumes the noise is Gaussian in the Fourier basis of $L$. This is an adaptation of prediction-correction-update algorithms to the case of (0, 1) observations.\n\nFinally, they propose several experiments to gauge the performance of their algorithms. The first part compares it to other graph-based methods, and the second part to more complicated (e.g. transformer-based) sequential recommendation algorithms. In the first case, the Bayesian version BGS-IMC is shown to mostly outperform its counterparts, while in the second case, the performance is comparable (sometimes slightly worse) than other architectures but the runtime is much lower.", "summary_of_the_review": "This is a very interesting paper, that introduces a framework for one-bit completion that's both efficient and comparable to SOTA accuracy. However, it is for now not accessible beyond a very small subset of experts, and needs clarity changes to broaden its appeal.", "strength_and_weaknesses": "The main strengths of the proposed algorithms are their scalability and explainability: since they are fairly simple to implement (the first one even has a closed-form solution), they are much faster than heavier neural network counterparts; and on the other hand even the learned elements of the algorithms (such as the covariance matrices of BGS-IMC) can have interesting interpretations. The algorithms are quite thoroughly studied, with ablation and scalability studies performed in the appendix.\n\nOn the other hand, the paper is very hermetic for people that are not familiar with the setting and state of the art; it took me quite a long time to grasp the exact setting of the original problem. The introduction to BGS-IMC suffers the same problem : it is hard to understand exactly what $\\Delta s$ is, and why the model is setup that way. Overall, this paper needs significant work to make it accessible beyond non-experts of the field.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster