Localized Linear Regression in Networked Data
Alexander Jung Nguyen Tran


	Metrics, quantization and registration in varifold spaces
    Nicolas Charon
    
=========================================================



The network Lasso (nLasso) has been proposed recently as an efficient learning algorithm for massive networked data sets 
(big data over networks). It extends the well-known least absolute shrinkage and selection operator (Lasso) from learning 
sparse (generalized) linear models to network models. Efficient implementations of the nLasso have been obtained using 
convex optimization methods lending to scalable message passing protocols. In this paper, we analyze the statistical properties 
of nLasso when applied to localized linear regression problems involving networked data. Our main result is a sufficient 
condition on the network structure and available label information such that nLasso accurately learns a localized linear regression 
model from a few labeled data points. We also provide an implementation of nLasso for localized linear regression by specializing 
a primal-dual method for solving the convex (non-smooth) nLasso problem.






§ INTRODUCTION



The data arising in many important application domains can be modeled efficiently using some network structure. 
Examples of such networked data are found in signal processing where signal samples can be arranged as a chain, 
in image processing with pixels arranged on a grid, in wireless sensor networks where measurements conform to sensor 
proximity <cit.>. Organizing data using networks 
is also used in knowledge bases (graphs) whose items are linked by relations <cit.>.  

In what follows, we will represent networked data using an undirected “empirical graph”. The nodes of the empirical graph 
represent individual data points (e.g., one image out of an entire collection) which are connected by edges according to some 
notion of similarity. This similarity might be induced by domain knowledge (e.g., friendship relations in 
social networks) or via probabilistic models ( <cit.>. 

Beside their network structure, data points are typically characterized by features and labels. The features of data points 
are quantities that can be measured or computed efficiently (in an automated fashion). In contrast, the labels of data points 
are costly to acquire, involving human expert labor. 


We consider regression problems within which data points are characterized by features and a numeric label (or target). The 
goal is to learn an accurate predictor which maps the features of a data point to a predicted label. The learning of the predictor 
is based on the availability of a few data points with known labels. Facing partially labeled data is common since the acquisition 
of reliable label information is often costly (involving human expert labor). 



Accurate learning is particularly challenging in the high-dimensional regime <cit.>. 



Here, a key obstacle is the lack of a sufficient amount of samples which can be 
considered i.i.d. Using a network structure allows then to borrow statistical strength from different “groups” of samples which 
are not exactly i.i.d., but still statistically similar to some extent. 

The learning of an accurate predictor from a small number of labeled data points is enabled by exploiting the tendency of 
well-connected data points to have similar statistical properties. Such a clustering assumption, which underlies most (semi-) supervised 
machine learning methods <cit.>, requires any reasonable predictor to be nearly constant 
over well-connected subsets (clusters) of data points. The clustering assumption motivates the network Lasso (nLasso) as a form 
of empirical risk minimization <cit.>. 







Contribution. While several implementations of nLasso have been proposed and analyzed (see <cit.>), 
little is known about the accuracy of nLasso in regression problems. The main contribution of this paper is a sufficient condition on the network 
topology and available label information such that the nLasso accurately learns a predictor from a small number of labeled data points. 
To this end, we apply (an extension of) the network compatibility condition (NCC) introduced in <cit.>. 

We demonstrate theoretically and empirically, that the NCC guarantees that nLasso learns an accurate predictor 
which conforms with the clustering hypothesis. Our theoretical findings help to design sampling schemes 
which identify those data points whose labels would provide the most information about the labels of the other data 
points <cit.>.   

Notation. 
The identity matrix of size d×d is denoted 𝐈_d. The positive part of some real number a∈ℝ is (a)_+=max{a, 0}. The Euclidean 
norm of a vector =(x_1,…,x_)^T is √(∑_r=1^ x_r^2). 
For a positive definite matrix 𝐂, we define the induced norm _𝐂√(^T𝐂). 
We will need the vector-valued clipping function 𝒯^(λ)() λ/ for ≥λ and 
𝒯^(λ)() otherwise. The soft-thresholding operator is 𝒮(x;τ) sign(x) (|x|- τ)_+. 




















§ PROBLEM FORMULATION



We consider networked data modelled by an undirected “empirical” graph =(,,) 
whose nodes ={1,…,} represent individual data points. The undirected edges 
 encode some domain-specific notion of similarity between data points. The similarity between 
nodes i,j∈ connected by the edge {i,j}∈ is quantified by a positive edge weight 
A_ij. We collect the weights (with A_ij=0 if nodes i,j∈ are not connected by an 
edge), into the weight matrix ∈ℝ_+^×. 



In addition to the graph structure , datasets typically convey additional information 
about the data points. Let us assume that each individual data point i ∈ is 
characterized by a feature vectors ^()∈ℝ^ and a 
numeric label y^()∈ℝ. The features ^() can be 
determined easily for any data point. In contrast, acquisition of labels y^() is 
difficult (requiring human expert labor). Our approach allows to have access 
only to the labels of a small training set ={_1,…,_}⊆.  

We relate features ^() and labels y^() using the linear model 



    y^() = ( ^())^T^()+ε^(),
 
with some (unknown) weight vector ^() for each node ∈. 
The noise component ε^() in (<ref>) summarizes any labeling 
our modeling errors. 



Thus, we assign each data point with an individual 
linear model (<ref>). For high-dimensional data (feature vector length ) this  
would result in overfitting unless we leverage the information contained in the network structure relating 
different data points. As we demonstrate theoretically and empirically, enforcing the (estimates of the) weight 
vectors ^() to be similar for well-connected data points allows to accurately 
learn the linear models (<ref>) for the entire dataset. 




We will apply nLasso to the available labels y^() for the training set to obtain an estimate ^() for the 
weight vector ^() at each node ∈. The estimates ^() define a predictor which maps 
the node ∈ to the predicted label 

    ŷ^()( ^())^T^().


The predictions ŷ^() will be accurate, i.e., the prediction error ŷ^() - y^() will be small, 
if the estimation error ^()-^() is small. Our main result (see Theorem <ref>) 
provides a sufficient condition on the structure of the empirical graph  and the training set  such that the 
estimation error is small. 

We interpret the weight vectors ^() as the values of a graph signal : →ℝ^ which 
assigns node ∈ the vector ∈ℝ^. 
The set of all vector-valued graph signals is denoted 

    {: →ℝ^: i ↦}.
  
Each graph signal ∈ represents a predictor which maps a node with features
  to the predicted label (<ref>). 

	
Given partially labeled networked data, we aim at leaning a predictor ∈ whose predictions (<ref>) agree 
with the labels  of labeled data points in the training set . In particular, we aim at learning a predictor having a small training error 

    E()   ∑_∈| y^() - ŷ^()| 
     (<ref>)=∑_∈| y^() - ( ^())^T^()|.
 
We use the absolute value loss since it somewhat simplifies our analysis. However, we expect no big 
challenges in extending our analysis to nLasso using different loss functions, such as the squared 
error loss. The absolute value loss is actually preferred for learning linear regression models (<ref>) 
when the noise ^() is expected to contain only a few large values, known as 
“salt and pepper” noise in image processing <cit.>. 






§ NETWORK LASSO




The criterion (<ref>) by itself is not enough for guiding the learning of a predictor 
 since (<ref>) completely ignores the weights  
at unlabeled nodes ∈∖. Therefore, we need to impose some
additional structure on the predictor . To this end, we require the predictor 
 to conform with the cluster structure of the empirical graph  <cit.>.  

The extend by which a predictor ∈ conforms with  can be 
measured by the total variation (TV)



    _ TV   ∑_{i,j}∈_ij[j] - .

If the weights  are approximately constant over well-connected subsets of nodes, the predictor 
∈ has small TV _ TV. The restriction of (<ref>) 
to a subset 𝒮⊆ of edges is denoted _𝒮∑_{i,j}∈𝒮_ij[j] -.

	
We are led naturally to learning a predictor  via the  regularized empirical risk minimization (ERM)



    ∈_∈E()  + λ_ TV,

which is a special case of nLasso <cit.>. 
The parameter λ>0 in (<ref>) allows to trade small TV  _ TV against small error 
E() (<ref>). The choice of λ can be guided by cross validation 
<cit.>. Alternatively the choice of λ can be guided by our analysis of the 
nLasso estimation error (see discussion after Theorem <ref>). 
	
Note that nLasso (<ref>) does not enforce the labels  themselves to be clustered. Instead, 
it requires the predictor , which is used to obtain predictions (<ref>), to be 
clustered. 
	
It will be convenient to reformulate (<ref>) using vector notation. To this end, we represent a graph signal ∈ 
as the vector

    = (([1])^T, … ,([])^T)^T ∈ℝ^.

and define the block matrix ∈ℝ^× (with =||)

    _e,i = _ij𝐈_    e={i,j}∈, i<j
    
    -_ij𝐈_    e={i,j}∈, i>j
    0    otherwise.

Applying the matrix 𝐃 to a graph signal vector  (<ref>) 
results in a partitioned vector 𝐃 whose eth block is given by _ij ( - [j])  (see (<ref>)). 
Using (<ref>) and (<ref>), we can 
reformulate the nLasso (<ref>) as

    ∈_∈ℝ^   h() + g().

Here, 



    h()     = E()  and   g() λ∑_e=1^^(e)
       =( (^(1))^T,…,(^())^T)^T∈ℝ^.


	
	
	
	
	




§ PRIMAL-DUAL METHOD



The nLasso (<ref>) is a convex optimization problem with a non-smooth objective 
function which rules out the use of gradient descent methods <cit.>. However, 
the objective function is highly structured since it is the sum of two components h() 
and g(), which can be optimized efficiently when considered separately. 
Such composite functions can be optimized efficiently using proximal splitting methods <cit.>.
 
We apply the proximal method proposed in <cit.> 
which is based on reformulating (<ref>) as a saddle-point problem  

    min_∈ℝ^max_∈ℝ^^T  + h() - g^*(),

with the convex conjugate  g^* of g <cit.>.

Solutions (, ) of (<ref>) are characterized by <cit.> 

    -^T ∈∂ h()∈∂ g^*().

The coupled conditions (<ref>) are, in turn, equivalent to

    -𝐓^T ∈(𝐈+𝐓∂ h) ()+Σ∈(𝐈+Σ∂ g^*)(),

with positive definite matrices Σ∈ℝ^×, 𝐓∈ℝ^×. 
In principle, the matrices Σ, 𝐓 in (<ref>) can be chosen arbitrarily. 
It will prove convenient to choose them as

    Σ= diag{σ^()𝐈_}_=1^𝐓= diag{τ^()𝐈_}_=1^
 
with scalars {σ^()}_=1^ and {τ^()}_∈ as specified below. 

The optimality condition (<ref>) for nLasso (<ref>) 
lends naturally to the following coupled fixed point iterations <cit.>

    _k+1   = (𝐈+𝐓∂ h)^-1 (_k-𝐓^T _k)  
    _k+1   = (𝐈+Σ∂ g^*)^-1 (_k+Σ (2_k+1-_k)).


The update (<ref>) involves the resolvent operator 

    (𝐈+Σ∂ g^*)^-1 () =_' ∈ℝ^ g^*(') + (1/2)' -^2_Σ^-1.

The convex conjugate g^* of g (see (<ref>)) can be decomposed 
as g^*()=∑_e=1^ g_2^*(^(e)) with the 
convex conjugate g_2^* of g_2() λ. Combining the fact that 
Σ is a block diagonal matrix with the Moreau decomposition <cit.>, 
it can be shown that = (𝐈_+Σ∂ g^*)^-1 () (see (<ref>))
with  


    = ( ( ^(1))^T,…,(^())^T)^T𝐜^(e)𝒯^(λ)(^(e)).

 








Similar to the update (<ref>), also the update (<ref>) decomposes into 
independent updates of the weight vectors  

    ^()=^()_k-∑_j > iτ^(j) A_i,j^(j)_k+∑_i > jτ^(j) A_i,j^(j)_k

yielding the updated weight vectors ^()_k+1  = ^() for each node ∈. 
In particular, for unlabeled nodes ∉, the update (<ref>) reduces to 
^()=^(). For labeled nodes ∈, using elementary sub-gradient calculus, 
we obtain 

    ^()    = 𝐱^()(ỹ+𝒮(w̃-ỹ;τ^())) 
        + (𝐈-(1/^()^2) ^()(^())^T)^()

with ỹ y^()/^()^2 and w̃(^())^T^() / ^()^2. 
Inserting (<ref>) and (<ref>) into the 
fixed point iteration (<ref>), (<ref>) results in Alg. <ref> for solving the nLasso (<ref>). 

If the matrices Σ and 𝐓 using in (<ref>) satisfy

    Σ^1/2𝐓^1/2^2 <1,

the sequences obtained from iterating (<ref>) and (<ref>) converge to a saddle point of 
the problem (<ref>) <cit.>. 
The condition (<ref>) is ensured by choosing Σ and 𝐓 
according to (<ref>) using σ^()=1/(2_) and τ^()η / d^(), 
with (weighted) node degree d^()=∑_j≠_,j and some constant η<1 <cit.>. 



Another instance of a proximal method is the alternating direction method of multipliers (ADMM) <cit.>, 
which has been applied to (a more general formulation of) the nLasso in <cit.>. In 
contrast, to the primal-dual method used in Alg. <ref>, the ADMM implementation 
involves a tuning parameter. The optimum choice for this tuning parameter is non-trivial and typically 
requires a grid search <cit.>. However, we expect that Alg. <ref> and 
the ADMM implementation of <cit.> (when specialized to (<ref>)) 
to have similar computational requirements. 








§ ERROR ANALYSIS FOR NLASSO
 



In order to analyze the statistical properties of Alg. <ref> we need to understand the 
structure of the solutions to the nLasso problem (<ref>). To this end, will use a simple but useful 
model of piece-wise constant weight vectors     

    ^()=∑_l=1^F^(l)ℐ_^(l)[].
  
with fixed vectors ^(l)∈ℝ^, for l=1,…,F, and the indicator function ℐ_[] ∈{0,1} with 
ℐ_[] = 1 if and only if ∈⊆. 
Here, we use a partition = {^(1),…,^(F)} of the nodes  in the empirical graph 
into disjoint subsets (clusters) ^(l). 



The model (<ref>), which generalizes the piece-wise constant signal model 
(see <cit.>), embodies a clustering assumption that well-connected nodes 
in the empirical graph should have similar relations between features and labels <cit.>. 

Note that our analysis allows for an arbitrary choice of clusters ^(l) in (<ref>). 
However, our results are most useful when the sets ^(l) reflect the intrinsic cluster structure of the empirical 
graph  such that the TV _ TV (see (<ref>)) is small.



We now introduce the network compatibility condition (NCC), which generalizes the 
compatibility conditions for Lasso type estimators <cit.> of ordinary sparse signals. 
Our main contribution is to show that the NCC guarantees the accuracy of the nLasso (<ref>) 
solutions, as obtained using Alg. <ref>. 


 

Consider a networked dataset with empirical graph = (, ,). The nodes are characterized by 
feature vectors ^()∈ℝ^ and grouped according to a fixed partition ={^(1),…,^(F)}. 
The labels y^() of nodes are observed only on the training set ⊆. 
The training set is said to satisfy NCC, with constants K,L>0, if 



    K ∑_∈| ( ^())^T^()|  +  _≥ (L/√())  _∂
 
for any graph signal ∈ (see (<ref>)). 
 
We highlight that the NCC (constants) depend jointly on the training set  
and the  network structure of . While enlarging the training set can only improve 
the NCC constants (smaller K), the precise quantification of this improvement is difficult.
 
As shown in <cit.>, the NCC is satisfied if there exists a sufficiently 
large network flow between sampled nodes. Thus, given a dataset with empirical graph , the NCC 
can be verified using network flow algorithms (see Section <ref> and <cit.>). 

Our main theoretical result is that if the sampling set satisfies the NCC (see Definition <ref>), any solution of 
(<ref>) is close to the true underlying weight vectors (see (<ref>), (<ref>)). 


 

Consider a partially labeled networked dataset with empirical graph  with features ^() known for all nodes 
and labels y^() which are known only for the nodes ∈. We assume a linear model (<ref>) 
with true weights ^() piece-wise constant (<ref>). 
If the sampling set  satisfies NCC with parameters L > √() and K > 0, then any solution  
of nLasso (<ref>) with the choice λ 1/K satisfies  

    -_ TV≤ K (1+4√()/(L-√()))  ∑_∈ |^()| .
 

According to Theorem <ref>, the choice for the nLasso parameter λ in (<ref>) can be based 
on the NCC constant K (see (<ref>)) via setting λ=1/K. For this 
choice, given the training set  satisfies the NCC with parameters K and L, the nLasso error 
- is bounded according to (<ref>). 

Note that the bound (<ref>) does neither explicitly involve the size =|| 
of the training set , nor the overall size  of the empirical graph (or dataset). However, the relative 
size m/ of the training set will influence the probability that the NCC is satisfied (such that the bound 
(<ref>) applies at all). 

We highlight that the nLasso (<ref>) does not require the partition  used for our signal model 
(<ref>). This partition is only used for the analysis of nLasso (<ref>). 
Moreover, if the true underlying graph signal is of the form (<ref>) and nLasso 
accurately learns this signal, we can obtain the partition  by thresholding the edge-wise differences 
^()-^(j) for ij∈ <cit.>. 





§ NUMERICAL EXPERIMENTS
 

In order to verify our theoretical findings (see Theorem <ref>), we have applied Alg. <ref> to two particular 
datasets. The first dataset is synthetically generated based on an empirical graph which consists of two well-connected 
clusters. We also consider a dataset obtained from temperature 
measurements at various locations in Finland.[The source code for our numerical experiments can be found under <https://github.com/alexjungaalto/ResearchPublic/tree/master/LocalizedLinReg>.]




Two-Cluster Dataset. We generate the empirical graph  (=80) by sparsely connecting two random graphs ^(1) 
and ^(2), each of size /2 and with average degree 10. 

The nodes of  are assigned feature vectors ^()∈ℝ^2 
obtained by i.i.d. random vectors uniformly distributed on the unit sphere {∈ℝ^2: =1}. 
The labels y^() of the nodes i∈ are generated according to the linear model (<ref>) 
with zero noise ε^()=0 and piecewise constant weight vectors 𝐰^() 
(see (<ref>)). We assume that the labels y^() are known for the nodes in 
the training set which includes three data points from each cluster, i.e., |∩^(1)|= |∩^(2)|=3. 

Using <cit.> it can be shown that the training set  satisfies NCC with 
L>√()=√(2) if there exists a sufficiently large network flow between the labeled node 
i∈^(l)∩ and the boundary edges ∂{{i,j}∈: i ∈^(1), j ∈^(2)} 
between the two clusters. In particular, let ρ^(l) denote the normalized flow value from the labeled nodes 
in cluster ^(l) and the cluster boundary, normalized by the boundary size |∂|. The NCC is satisfied 
with L>√(2) if ρ^(l)>√(2) for l=1,2. 


In Fig. <ref>, we depict the normalized mean squared error (NMSE) ε-^2_2 / ^2_2 
incurred by Alg. <ref> (averaged over 10 i.i.d. simulation runs) for varying connectivity, as 
measured by the empirical average ρ̅ of ρ^(1) and ρ^(2) (having same distribution). Note that 
Fig. <ref> agrees with Theorem <ref> which predicts Alg. <ref> is accurate if NCC holds (ρ̅>√(2) ). 













Weather Data. In this experiment, we consider a networked dataset whose empirical graph  represents 
Finnish weather stations (see Fig. <ref>), which are initially connected by an edge to their K=3 nearest 
neighbors. The feature vector ^(i)∈ℝ^3 of node i∈ contains the local (daily mean) 
temperature for the preceding three days. The label y^(i)∈ℝ is the current day-average temperature. 

We use Alg. <ref> to learn the weight vectors ^(i) for a localized linear model (<ref>). 
For the sake of illustration we focus on the weather stations in the capital region around Helsinki (indicated by a red cross in Fig. <ref>). 
These stations are represented by nodes ={23,18,22,15,12,13,9,7,5} and we assume that labels y^(i) are available for all 
nodes outside  and for the nodes i∈{12,13,15}⊆. Thus, for more than half of the nodes in  we do 
not know the labels y^(i) but predict them via (<ref>) with the weight vectors ^(i) 
obtained from Alg. <ref> (using λ=1/7 and a fixed number of 10^4 iterations). The normalized 
average squared prediction error is  ≈ 10^-1 and only slightly larger than the prediction error incurred by fitting 
a single linear model to the cluster  using a least absolute deviation regression method <cit.>. 



§ ACKNOWLEDGMENTS

We thank Roope Tervo from the Finnish Meteorological Institute for helping with gathering the weather data. 


IEEEtran






§ PROOF OF THEOREM <REF>
 



In order to proof Theorem <ref>, we consider an arbitrary but fixed nLasso solution = ( ( ^(1))^T,…,  ( ^())^T)^T 
(see (<ref>)) and denote the estimation error between ^() 
and the true underlying weights ^() (see (<ref>)) as ^()^() - ^(). 

By the definition of nLasso (<ref>),

    ∑_∈ |ŷ^()-y^()| +λ_ TV≤∑_∈ |^()|_1 +λ_ TV.
 
Since the true weight vectors ^() are piece-wise constant (see (<ref>)),  
_=0 and _=_. 
Using the decomposition property and triangle inequality for the TV in (<ref>), 

    ∑_∈ |ŷ^()-y^()|+λ_≤∑_∈ |^()| +λ_∂-λ_∂

and, in turn, 



    ∑_∈ |ŷ^()- y^()|+λ_≤∑_∈ |^()| +λ_∂.

We conclude from (<ref>) that



    _   ≤ (1/λ) ∑_∈|^()| + _∂,

Thus, for small noise ^() (see (<ref>)), the nLasso estimation error  is piece-wise constant. 
However, it remains to control the size of the error for which we will invoke the NCC <ref>. 

We can develop the LHS of (<ref>) as 

    ∑_∈ |ŷ^()-y^() |    (<ref>),(<ref>)=∑_∈| ( ^())^T^() - ^()| 
       ≥∑_∈| ( ^())^T^()| -∑_∈ |^()|,

where we have used the triangle inequality in the last step. 





Combining (<ref>) with (<ref>), 

    ∑_∈| ( ^())^T^()|+λ_≤ 2 ∑_∈ |^()| +λ_∂.

Since we assume NNC holds for , (<ref>) yields

    (L/√()) _∂≤ K  ∑_∈| ( ^())^T^()| +_.
 
Inserting (<ref>) into (<ref>) and using λ 1/K, yields 

    λ(L/√()-1)_∂≤ 2  ∑_∈ |^() |.
  
Combining (<ref>) with (<ref>) yields  

    _ TV   =_+_∂
       (<ref>)≤ (1/λ) ∑_∈ |^()|_1 + 2 _∂
       (<ref>)≤ ( (1/λ) +4√()/λ/(L-√())) ∑_∈ |^() |.
 



