Nathan De Lara
email: nathan.delara@telecom-paris.fr

Thomas Bonald
email: thomas.bonald@telecom-paris.fr

A Consistent Diffusion-Based Algorithm for Semi-Supervised Classification on Graphs

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, ( 1
)
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 ( 1) [START_REF] Imre | Diffusion kernels on graphs and other discrete structures[END_REF]. It has been applied for many different tasks, including pattern matching [START_REF] Thanou | Learning heat diffusion graphs[END_REF], ranking [START_REF] Ma | Mining social networks using heat diffusion processes for marketing candidates selection[END_REF][START_REF] Ma | Mining web graphs for recommendations[END_REF], embedding [START_REF] Donnat | Learning structural node embeddings via diffusion wavelets[END_REF], clustering [START_REF] Tremblay | Graph wavelets for multiscale community mining[END_REF] and classification [START_REF] Zhu | Semi-supervised learning with graphs[END_REF][START_REF] Merkurjev | A semi-supervised heat kernel pagerank MBO algorithm for data classification[END_REF][START_REF] Berberidis | Adadif: Adaptive diffusions for efficient semi-supervised learning over graphs[END_REF][START_REF] Li | Semi-supervised learning on graph with an alternating diffusion process[END_REF]. 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 [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF]. 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 2, we introduce the Dirichlet problem on graphs. Section 3 describes our algorithm for node classification. The analysis showing the consistency of our algorithm on a simple block model is presented in section 4. Section 5 presents the experiments and section 6 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 i dt = n j=1 A ij (T j -T i ), that is ∀i / ∈ S, dT i dt = -(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 (1). At equilibrium, T satisfies Laplace's equation:

∀i / ∈ S, (LT ) i = 0. (2)
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 (2) can be written equivalently:

∀i / ∈ S, T i = (P T ) i ,

(3) where P = D -1 A is the transition matrix of the random walk in the graph.

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 ns so that the vector of temperatures can be written

T = X Y ,
where X is the unknown vector of temperatures at equilibrium, of dimension ns. Writing the transition matrix in block form as

P = Q R • • ,
it follows from (3) that: X = QX + RY, (4) so that: X = (I -Q) -1 RY.

(5) 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 [START_REF] Rk | Spectral graph theory[END_REF].

The exact solution (5) requires to solve a (potentially large) linear system. In practice, a very good approximation is provided by a few iterations of (4), 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 [START_REF] Duncan | Collective dynamics of small-world networks[END_REF]]. 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 [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF]. 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 1. A natural approach, proposed by [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF], consists in assigning label 1 to all nodes with temperature above 0.5 and label 2 to other nodes. The analysis of section 4 suggests that it is preferable to set the threshold to the mean temperature,

T = 1 n n i=1 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 1 (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.

Algorithm 1 Dirichlet classifier

Require: Seed set S and associated labels y ∈ {1, . . . , K}.

1: for k in {1, . . . , K} do 2:

T S = 0.

3:

for i ∈ S do 4:
if y i = k then 5:

T S i = 1. 6: end if 7:
end for 8:

T (k) ← Dirichlet(S, T S ).

9:

∆ (k) ← T (k) -mean(T (k)
) 10: end for 11: for i ∈ S do 12:

x i = arg max k=1,...,K (∆ (k) i ) 13: end for 14: return x, labels of nodes outside S

The key difference with the vanilla method lies in temperature centering (line 9 of the algorithm). Another variant proposed by [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF] consists in rescaling the temperature vector by the weight of the considered label in the seeds (see equation ( 9) in their paper).

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 (4). 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 1 is then O(N Km), 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 1 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. Lemma 1. 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) + n T q, (s k (p -q) + nq)T k = n T q k = 2, . . . , K,
where T is the average temperature, given by:

T = s 1 n n 1 (p -q) + nq s 1 (p -q) + nq / 1 - K k=1 (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.

Theorem 1. 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).

Proof. 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 1, 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 = arg 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, nonseed 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 1, 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 - K j=1 (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 [START_REF] Zhu | Semi-supervised learning using gaussian fields and harmonic functions[END_REF] (also without temperature centering) and our algorithm (with temperature centering).

All datasets and codes are available online1 , making the experiments fully reproducible.

Synthetic data

We first use the stochastic block model (SBM) [START_REF] Edoardo M Airoldi | Mixed membership stochastic blockmodels[END_REF] 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 2 (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 3 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 2 and SNAP 3 collections (see Table 1).

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 [START_REF] Fey | Splinecnn: Fast geometric deep learning with continuous b-spline kernels[END_REF][START_REF] Huang | Adaptive sampling towards fast graph representation learning[END_REF][START_REF] Wijesinghe | Dfnets: Spectral cnns for graphs with feedback-looped filters[END_REF]. Wikipedia graphs: Wikipedia for schools (WS) [START_REF] Haruechaiyasak | Article recommendation based on a topic model for wikipedia selection for schools[END_REF], 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 §2.3, with nodes considered as heat sources. • Social networks: DBLP and Amazon are social networks with partial ground-truth communities [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]. 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 2 and3 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 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 4 shows the macro-F1 scores. We see that the performance of the centered algorithm remains steady in the presence of seed asymmetry.

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.

  (a) Ground truth. (b) Solution to the Dirichlet problem.

Figure 1 :

 1 Figure 1: Binary classification of the Karate Club graph [Zachary, 1977] with 2 seeds (indicated with a black circle). Red nodes have label 1, blue nodes have label 2.

Figure 2 :

 2 Figure 2: Binary classification performance on the SBM.

Figure 3 :

 3 Figure 3: Multi-label classification performance on the SBM.

Figure 4 :

 4 Figure 4: Impact of the fraction of seeds for label 1 on macro-F1 score (mean ± standard deviation).

Table 1 :

 1 Datasets.

	dataset	# nodes	# edges	# classes (%) labeled
	CO	2 708	10 556	7	100
	CS	3 264	9 072	6	100
	WS	4 403	112 834	16	100
	WV	10 012	792 091	11	100
	WL	3 210 346 67 196 296	10	100
	DBLP	317 080	2 099 732	5000	29
	Amazon	334 863	1 851 744	5000	5

Table 2 :

 2 Macro-F1 scores (mean ± standard deviation) with uniform seed sampling.

	algorithm	CO	CS	WS	WV	WL
	Vanilla	0.19 ± 0.12	0.17 ± 0.04	0.04 ± 0.02	0.09 ± 0.04	0.19 ± 0.01
	Centered 0.42 ± 0.18 0.36 ± 0.04 0.16 ± 0.11 0.55 ± 0.03 0.51 ± 0.01

Table 3 :

 3 Macro-F1 scores (mean ± standard deviation) with degree seed sampling. Centered 0.51 ± 0.08 0.26 ± 0.13 0.06 ± 0.04 0.48 ± 0.02 0.45 ± 0.00 favorable scenario where seeds are sampled in proportion to the labels. Seeds still represent 1% of the nodes. The results are shown in Table4.

	algorithm	CO	CS	WS	WV	WL
	Vanilla	0.30 ± 0.08	0.16 ± 0.07	0.02 ± 0.01	0.10 ± 0.04	0.34 ± 0.00

Table 4 :

 4 Macro-F1 scores (mean ± standard deviation) with balanced seed sampling.

	algorithm	DBLP	Amazon
	Vanilla	0.04 ± 0.00	0.05 ± 0.01
	Centered 0.19 ± 0.01 0.18 ± 0.02

Preprint. Under review.

https://github.com/nathandelara/Dirichlet

https://netset.telecom-paris.fr/

https://snap.stanford.edu/data/

Appendix: Proof of Lemma 1

Proof. In view of (2), we have:

We deduce:

(n j -s j )T j .

The proof then follows from the fact that

(n j -s j )T j = s 1 + V.