title: A Consistent Diffusion-Based Algorithm for Semi-Supervised Classification on Graphs
authors: Nathan de Lara Thomas Bonald
text: 
  
  The effects of granulation and supergranulation on Earth-mass planet detectability in the habitable zone around F6-K4 stars.
      N. Meunier 1, A.-M. Lagrange 1 
    
      Received ; Accepted
  ============================================================================================================================
  
  
  
  
  Semi-supervised classification on graphs aims at assigning labels to all nodes of a graph based on the  labels known for a few nodes, called the seeds. The most popular algorithm relies on the principle of heat diffusion, where the labels of the seeds are spread by thermo-conductance and  the temperature of each node is used as a score function for each label. Using a simple block model, we prove that this algorithm is not consistent unless the temperatures of the nodes are centered before classification. We show that this simple modification of the algorithm is enough to get significant performance gains on real data.
  
  
  
  
  
  
  
  
  
  
  
  
  § INTRODUCTION
  
  
  Heat diffusion, describing by the evolution of temperature T in an isotropic material, is governed by the heat equation:
  
      ∂ T∂ t = αΔ T,
  
  where α  is the thermal conductivity of the material and Δ is the Laplace operator. 
  In  steady state, this equation simplifies to Δ T = 0 and the function T is said to be harmonic. The Dirichlet problem consists in finding the equilibrium in the presence of  boundary conditions, that is when the temperature T is fixed on the boundary of the region of interest.
  
  The principle of heat diffusion has proved instrumental in graph mining, using a discrete version of the heat equation (<ref>) <cit.>.
    It has been applied for  many different tasks, including   pattern matching  <cit.>,  ranking   <cit.>,  embedding   <cit.>,    clustering <cit.> and  classification <cit.>. In this paper, we focus on the classification task: given  labels known for some nodes of the graph, referred to as the seeds, how to infer the labels of the other nodes? The number of seeds is typically small compared to the total number of nodes (e.g., 1%), hence the name of  semi-supervised classification.
  
  
  The most popular algorithm for semi-supervised classification in graphs   is based on a discrete version of the Dirichlet problem, the seeds playing the role of  the “boundary” of the Dirichlet problem <cit.>. Specifically, one Dirichlet problem is solved per label, setting the  temperature of the corresponding seeds at 1 and the temperature of the other seeds as 0. Each node is then assigned the label with the highest temperature over the different Dirichlet problems. 
  In this paper, we prove on a simple block model that this vanilla algorithm is not consistent, unless the temperatures are centered before classification. Experiments show that this simple modification of the algorithm significantly improves classification scores  on real datasets.
  
  
   
  
  
  
  The rest of this paper is organized as follows. In section <ref>, we introduce the Dirichlet problem on graphs. Section <ref> describes our algorithm for   node classification. The analysis showing the 
  consistency of our algorithm on a simple block model is presented in 
  section <ref>.  Section <ref> presents the experiments and section <ref> concludes the paper.
  
  
  
  
  
  § DIRICHLET PROBLEM ON GRAPHS
  
  
  
  In this section, we introduce the Dirichlet problem on graphs 
  and characterize the solution, which will be used in the analysis. 
  
  
  
   §.§ Heat equation
  
  
  
  Consider a graph G with n nodes indexed from 1 to n. Denote by A its adjacency matrix. This is a symmetric, binary matrix.   Let d = A1 be the degree vector, which is assumed positive, and D = diag(d). The Laplacian matrix is defined by
  
      L = D - A.
  
  
  Now let  S be some strict subset  of {1, …, n} and assume that the temperature of each
  node i ∈ S is set at some fixed value T_i. 
  We are interested in the evolution of the temperatures of the other nodes. Heat exchanges occur through each edge of the graph proportionally to the temperature difference between the corresponding nodes. Then,
  
      ∀ i ∉ S,   dT_idt = j=1n∑A_ij(T_j - T_i),
  
  that is
  
      ∀ i ∉ S,  dT_idt = -(LT)_i,
  
  where T is the vector of temperatures. This is the heat equation in discrete space, where  -L plays the role of the Laplace operator in (<ref>). At equilibrium, T satisfies Laplace’s equation:
  
      ∀ i ∉ S,   (LT)_i = 0.
  
  We say that the vector T is harmonic. With the boundary conditions T_i for all i ∈ S, this defines a Dirichlet problem in discrete space. Observe that Laplace's equation (<ref>) can be written equivalently:
  
      ∀ i ∉ S,   T_i = (PT)_i,
  
  where P =D^-1A is the transition matrix of the random walk in the graph.
  
  
  
   §.§ Random walk
  
  
  Consider a random walk in the graph G with a probability of moving from node i to node j equal to A_ij/d_i. Let X_0, X_1, X_2, … be the sequence of nodes visited by  the random walk. This defines a    Markov chain  on {1,…,n} with  transition 
  matrix P= D^-1 A.
  
   Observing that L = D(I - P), Laplace’s equation can be written equivalently
  
      ∀ i ∉ S,   T_i = (PT)_i.
  
  In other words, the temperature of each node i∉S   at equilibrium is the average of the temperature of its neighbors.  This implies in particular that  the solution to the Dirichlet problem is unique, provided that 
  the graph is connected. For the sake of completeness, we 
    provide a  proof of this result in the considered discrete case:
  
  
  If the graph is connected, there is at most one solution to the Dirichlet problem.
  
  
  
   
      We first prove that
       the maximum and the minimum of the vector T are achieved on the boundary S. Let i be any node such that T_i is maximum. If i ∉ S, it follows from (<ref>) that T_j is maximum for all neighbors j of i. If no such node belongs to S, we apply again this argument until we reach a node in S. Such a node exists because the graph is connected. It achieves the maximum of the vector T. The proof is similar for the minimum.
      
      Now consider two solutions T, T' to Laplace’s equation. Then Δ = T' - T is a solution of Laplace’s equation with the boundary condition Δ_i = 0 for all i ∈ S. We deduce that Δ_i = 0 for all i (because both the maximum and the minimum are equal to 0), that is T'=T.
  
  
  
  Now let P_ij^S
  be the probability that the random walk first hits the set S in node j when starting from node i. Observe that P^S is a stochastic matrix, with P_ij^S = δ_ij (Kronecker delta) for all i ∈ S. By first-step analysis, we have:
  
  
      ∀ i ∉ S,    P_ij^S = k=1n∑P_ikP_kj^S.
  
  
  The following  result provides a simple interpretation of  the solution to the Dirichlet problem  in terms of  random walk in the graph: the temperature of any node is the  average of the temperatures of the nodes at the boundary, weighted by the probabilities of reaching each of these nodes first:
  
      
      The solution to the Dirichlet problem is
      
      ∀ i ∉ S,    T_i = j ∈ S∑P_ij^ST_j.
  
  
  
  
      The vector T defined by (<ref>) satisfies for all i∉S:
      
      j=1n∑P_ijT_j = j=1n∑P_ijk ∈ S∑P_jk^ST_k = k ∈ S∑P_ik^ST_k = T_i,
  
      where we have used (<ref>). Thus, T satisfies (<ref>). The proof then follows from Proposition <ref>.
  
  
  
  
  
  
   §.§ Solution to the Dirichlet problem
  
  
  
  We now characterize the solution to the Dirichlet problem in discrete space. Without any loss of generality, we assume that nodes with unknown temperatures (i.e., not in S) are indexed from 1 to n-s so that the vector of temperatures can be written
  
      T = [ X; Y ],
  
  where X is the unknown vector of temperatures at equilibrium, of dimension n-s. Writing 
  the transition matrix in block form as
  
      P = [ Q R; · · ],
  
  it follows from (<ref>) that:
  
      X = QX + RY,
  
  so that:
  
      X = (I-Q)^-1RY.
  
  Note that the inverse of the matrix I-Q exists whenever  the graph is connected, which implies that  the matrix Q is  sub-stochastic with spectral radius strictly less than 1 <cit.>.
  
  
  
  
  The exact solution (<ref>) requires to solve a (potentially large) linear system. In practice, a very good approximation is provided by a few iterations of (<ref>), the rate of convergence  depending on the spectral radius of the  matrix Q. The small-world property of real graphs suggests that a few iterations are enough in practice  <cit.>. 
  This will be confirmed by the experiments.
  
  
  
  
  
  
  
   §.§ Extensions
  
  
  
  The results apply to
  weighted graphs, with a positive weight assigned to each edge. This weight  can then be  interpreted as the thermal conductivity of the edge in the diffusion process. 
  Interestingly, the results also apply to directed graphs. Indeed, a directed graph G of n nodes, with  adjacency matrix A,   can be considered as a bipartite graph of 2n nodes, with adjacency matrix:
  
      [   0   A; A^T   0 ]
  
  The diffusion can be applied to this bipartite graph, which is undirected. Observe that 
  each node of the directed graph G is duplicated in the bipartite graph and is thus characterized by 2 temperatures, one as heat source (for outgoing edges) and one as heat destination (for incoming edges). 
  It is not necessary for the directed graph to be  strongly connected; only the associate bipartite graph needs to be connected. 
  
  
  
  
  
  
  § NODE CLASSIFICATION ALGORITHM
  
  
  
  In this section, we introduce a node classification algorithm based on  the Dirichlet problem.
  The objective is  to infer the labels of all nodes given the  labels of a few nodes called the seeds.
  Our algorithm is a simple modification of the popular method proposed by <cit.>. Specifically, we propose to center  temperatures  before classification.
  
  
  
  
  
   §.§ Binary classification
  
  
  When there are only two different labels, the classification can be done by solving  one Dirichlet problem.
  The idea is to use the seeds with label 1 as hot sources, setting their temperature at 1, and   the seeds with label 2 as cold sources, setting their temperature at 0.
  The solution to this Dirichlet problem gives temperatures between 0 and 1, as illustrated by Figure <ref>.
  
  
  
  
  
  A natural approach, proposed by <cit.>, consists in assigning label 1 to all nodes with temperature above 0.5 and label 2 to other nodes. The analysis of section <ref> suggests that it is preferable to set the threshold to the mean temperature, 
  
      T̅ = 1/n∑_i=1^n T_i.
  
  Specifically, all nodes with temperature above T̅ are assigned  label 1, the other are assigned  label 2. Equivalently, temperatures are centered before classification: after centering, nodes with positive temperature are  assigned  label 1, the others are assigned  label 2.
  
  
  Note that the temperature of each node can be used to assess the confidence in the classification: the closer the temperature to  the mean, the lower the confidence.
  This is illustrated by Figure <ref> (the lighter the color, the lower the confidence). In this case, only one node is misclassified and has indeed a temperature close to the mean.
  
  
  
  
  
  
   §.§ Multi-class classification
  
  In the presence of more than 2 labels, we use 
   a one-against-all strategy: the seeds of each label alternately serve as hot sources (temperature 1) while all the other seeds serve as cold sources (temperature 0). After centering the temperatures (so that the mean temperature of each diffusion is equal to 0), each node is assigned  the label that maximizes its temperature. This algorithm, we refer to as Dirichlet classifier, is parameter-free.
  
  
  
  
  The key difference with the vanilla method lies in temperature centering (line 9 of the algorithm). Another variant proposed by <cit.> consists in rescaling   the temperature vector  by the  weight of the considered label in the seeds (see equation (9) in their paper).
  
  
  
  
    
  Preprocessing
  A standard preprocessing for semi-supervised learning on graphs is to disconnect all seeds belonging to different classes and connect members of the same class <cit.>. This is, of course, compatible with the proposed algorithm.
  
  
  
  
   §.§ Time complexity
  
  
  The time complexity depends on the algorithm used to solve the Dirichlet problem. We here focus on the approximate solution by successive iterations of (<ref>).
  Let m be the number of edges of the graph. Using the  Compressed Sparse Row format for the adjacency matrix, each matrix-vector product  has a complexity of O(m). The complexity of Algorithm <ref> is then O(NKm), where N is the number of iterations.  Note that the K Dirichlet problems are independent and can thus be computed in parallel.
  
  
  
  
  § ANALYSIS
  
  
  
  In this section, we prove the consistency of Algorithm <ref> on a simple block model. In particular, we highlight the importance of temperature centering in the analysis.
  
  
  
   §.§ Block model
  
  
  Consider a graph of n nodes consisting of K blocks  of respective sizes n_1,…,n_K, forming a partition of the set of nodes.  There are  s_1,…,s_K seeds in these blocks, which are respectively  assigned labels 1,…,K. Intra-block edges have weight p and inter-block edges have weight q. 
  We expect  the algorithm to assign label k to all nodes of  block k whenever p>q, for all k=1,…,K. 
  
  
  
   §.§ Dirichlet problem
  
  
  Consider  the Dirichlet problem when  the temperature of the s_1 seeds of block 1 is set to 1 and the temperature  of the other seeds is set to 0. We have an explicit  solution to this Dirichlet problem, whose proof is provided in the appendix.
  
  
  
  Let T_k be the temperature of non-seed nodes of  block k at equilibrium. We have:
      
      (s_1(p-q) + nq) T_1     = s_1 (p-q) + nT̅ q,
      
      (s_k(p-q) + nq) T_k     = nT̅ q     k=2,…,K,
  
  where T̅ is the average temperature, given by:
  
      T̅ = (s_1/nn_1(p-q) + nq/ s_1(p-q) + nq) / (1-∑_k=1^K (n_k - s_k)q/s_k(p-q)+nq).
  
  
  
  
  
  
  
   §.§ Classification
  
  
  
  We now state the main result of the paper: the Dirichlet classifier is a consistent algorithm for the block model, in the sense that all nodes are correctly classified whenever p> q. 
  
  
  If p> q, then x_i=k for all non-seed nodes i of each block k,  for any parameters n_1,…,n_K (block sizes) and s_1,…,s_K (numbers of seeds).
  
  
  
  Let δ^(1)_k = T_k - T̅ be the deviation of temperature of non-seed nodes of block k for the Dirichlet problem associated with label 1.
      In view of Lemma <ref>, we have:
  
      (s_1(p-q) + nq) δ^(1)_1     = s_1 (p-q) (1-T̅),
      
      (s_k(p-q) + nq)δ^(1)_k     = -s_k(p-q) T̅     k=2,…,K,
  
  For p>q, using the fact that T̅∈ (0,1), we get δ^(1)_1 > 0 and δ^(1)_k<0 for all k=2,…,K. By symmetry, for each label l = 1,…,K,
  δ^(l)_l > 0 and δ^(l)_k<0 for all k l.
  We deduce that for each block k, x_i=max_lδ^(l)_k = k for all non-seed nodes i of  block k.
  
  
  
  Observe that the temperature centering is critical for consistency. In the absence of centering,  non-seed nodes of block 1 are correctly classified if and only if their temperature is the highest in the Dirichlet problem associated with label 1.
  In view of Lemma <ref>, this means that for all k=2,…,K,
  
      s_1 q n_1(p-q) + nq/s_1(p-q) + nq + s_1(p-q)(1-∑_j=1^K (n_j - s_j)q/s_j(p-q)+nq)
      > s_k q n_k(p-q) + nq/s_k(p-q) + nq.
  
  This condition might be violated even if p>q, depending on the parameters  n_1,…,n_K and s_1,…,s_K. 
  In the practically interesting case where s_1 << n_1,…,s_K << n_K for instance (low fractions of seeds), the condition requires:
  
      s_1  (n_1(p-q) + nq) > s_k  (n_k(p-q) + nq).
  
  For blocks of same size, this means that only blocks with the largest number of seeds are correctly classified.  The classifier is biased towards labels with a large number of seeds. This sensitivity of the vanilla algorithm to the  label distribution  of seeds will be confirmed in the experiments on real graphs.
  
  
  
  
  
  § EXPERIMENTS
  
  
  
  In this section, we show the impact of temperature centering on the quality of classification using both synthetic and real data.
  We do not provide a general benchmark of classification methods as the focus of the paper is on the impact of temperature centering in heat diffusion methods. 
  We focus on 3 algorithms: the vanilla algorithm (without temperature centering), the weighted version proposed by <cit.> (also without temperature centering) and our algorithm (with temperature centering).
  
  All datasets and codes are available online[<https://github.com/nathandelara/Dirichlet>], making the experiments fully reproducible.
  
  
  
  
  
  
   §.§ Synthetic data
  
  
  We first use the stochastic block model (SBM) <cit.> to generate graphs with an underlying structure in clusters. This is the stochastic version of the block model used in the analysis. There are K blocks of respective sizes n_1,…,n_K. Nodes of the same block are connected with probability  p while nodes in different blocks are connected probability q.
  We denote by s_k the number of  seeds in block k and by s  the total number of seeds.
  
  We first compare the performance of the algorithms on a binary classification task (K=2) for a graph of n=10 000 nodes with p=10^-3 and q=10^-4, in two different settings:
  
  
    * Seed asymmetry: Both blocks have the same size   n_1= n_2 = 5000 but different numbers of seeds, with s_1/s_2 ∈{1, 2, …,10} and   s_2 = 250 (5% of nodes in block 2).
  
    * Block size asymmetry: The blocks have different sizes with 
  ratio
  n_1/n_2 ∈{1, 2, …, 10} and seeds in proportion to these sizes, with a total of s= 1 000 seeds (10% of nodes). 
  
  
  For each configuration, the experiment is repeated 10 times. Randomness comes both from the generation of the graph and from the selection of the seeds. We report the F1-scores in Figure <ref> (average ± standard deviation). Observe that the variability of the results is very low due to the relatively large size of the graph. As expected, the centered version is much more robust to both types of asymmetry. Besides, in case of asymmetry in the  seeds, the weighted version of the algorithm tends to amplify the bias and leads to lower scores  than the vanilla version.
  
  
  
  
  We show in Figure <ref> the same type of results for K = 10 blocks and p=5.10^-2. For the block size asymmetry, the  size of blocks 2,…,10 is set to 1 000.
  
  
  
  
  
  
   §.§ Real data
  
  
  
  We  use datasets from the NetSet[<https://netset.telecom-paris.fr/>] and SNAP[<https://snap.stanford.edu/data/>] collections (see 
  Table <ref>).
  
  
  
  
  These datasets can be categorized into 3 groups:
  
  
    * Citations networks: Cora (CO) and CiteSeer (CS) are citation networks between scientific publications. These are standard  datasets for node classification <cit.>. 
  
  
    * Wikipedia graphs: Wikipedia for schools (WS) <cit.>, Wikipedia vitals (WV) and Wikilinks (WL) are graphs of hyperlinks between different selections of Wikipedia pages. In WS and WV, pages are labeled by category (People, History, Geography...). For WL, pages are labeled through clusters of  words used in these articles.
  As these graphs are directed, we use the extension of the algorithm described in <ref>, with nodes considered as heat sources.
  
  
  
  
    * Social networks: DBLP and Amazon are social networks with partial ground-truth communities <cit.>. As nodes are partially labeled and some nodes have  several labels,  the results for these datasets are presented separately, with specific  experiments based on binary classification.
  
  
  
  
  
  
  
  
  
  
  
  
  For the citation networks and the Wikipedia graphs, we  compare the classification performance of the algorithms in terms of  macro-F1 score and two seeding policies:
  
  
    * Uniform sampling, where seeds are sampled uniformly at random.
  
    * Degree sampling, where seeds are sampled in  proportion to their degrees.
  
  
  In both cases, the seeds represent 1%  of the total number of nodes in the graph.
  The process is repeated 10 times for each configuration. We defer the results for the weighted version of the algorithm to the supplementary material as they are very close to those obtained with the vanilla algorithm.
  
  We report the results in Tables <ref> and <ref> for uniform sampling  and degree sampling, respectively. We see that centered version outperforms the vanilla one by a significant margin.
  
  
  
  
  
  
  
  
  For the social networks, we perform independent binary classifications for each of the 3 dominant labels and average the scores. As these datasets have only a few labeled nodes, we consider the most favorable scenario where   seeds are sampled in proportion to the labels.
  Seeds  still represent 1% of the nodes. The results are shown in Table <ref>.
  
  
  
  
  
  Finally, we assess the classification performance of the algorithms in the case of seed asymmetry. Specifically, we first sample s = 1% of the nodes uniformly at random and  progressively increase the number of seeds for the dominant class of each dataset, say label 1.
  
  The process is repeated 10 times for each configuration. Figure <ref> shows the  macro-F1 scores. We see that the performance of the centered algorithm remains steady in the presence of seed asymmetry.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Sensitivity
  
  
  
  We now assess the sensitivity of the algorithms to the   seed distribution among the labels. Figure <ref> shows the impact of the number of seeds for the top label of each dataset, say label 1, on the performance of the algorithm, the other being fixed at 1% as before. The number of iterations is N = 10. We see that MD is approximately insensitive to the distribution of the seeds and outperforms the other two algorithms in most cases.
  
  
  
  
  
  
  
  
  
  
  § CONCLUSION
  
  
  
  We have proposed a novel approach to node classification based on heat diffusion. Specifically, we propose to center the temperatures of each solution to the  Dirichlet problem before classification. We have proved the consistency of this algorithm on a simple block model and we have shown  that it drastically improves classification performance on real datasets with respect to the vanilla version.
  
  
  In future work, we plan to extend this algorithm to soft classification, using the centered temperatures to get a confidence score for each node of the graph. Another interesting research perspective is to extend our proof of consistency of the algorithm to stochastic block models.
  
  
  
  
  named
  
  
  
  
  
  
  
  
  § APPENDIX: PROOF OF LEMMA <REF>
  
  
  
  In view of (2), we have:
  
      (n_1(p-q) + nq) T_1 = s_1 p + (n_1-s_1)pT_1 + ∑_j 1 (n_j - s_j) qT_j,
         (n_k(p-q) + nq) T_k = s_1 q + (n_k-s_k)pT_k + ∑_j k (n_j - s_j) qT_j,   k=2,…,K.
  
  We deduce:
  
      (s_1(p-q) + nq) T_1     = s_1 p + Vq,
      
      (s_k(p-q) + nq) T_k     = s_1 q + Vq     k=2,…,K.
  
  with 
  
      V = ∑_j=1^K  (n_j - s_j) T_j.
  
  The proof then follows from the fact that 
  
      n T̅ =  s_1 + ∑_j=1^K  (n_j - s_j) T_j = s_1 + V.
  
  
  
  
  
  