{'fraction_non_alphanumeric': 0.036232732381175366, 'fraction_numerical': 0.014223835167408102, 'mean_word_length': 4.304253337472835, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
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: 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) [Kondor and Lafferty, 2002]. It has been applied for many different tasks, including pattern matching [Thanou et al., 2017], ranking [Ma et al., 2008[Ma et al., , 2011, embedding [Donnat et al., 2018], clustering [Tremblay and Borgnat, 2014] and classification [Zhu, 2005;Merkurjev et al., 2016;Berberidis et al., 2018;Li et al., 2019]. 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 [Zhu et al., 2003]. 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 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, 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: 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: 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 n − s so that the vector of temperatures can be written where X is the unknown vector of temperatures at equilibrium, of dimension n − s. Writing the transition matrix in block form as it follows from (3) that: 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 [Chung, 1997].
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 [Watts and Strogatz, 1998]. 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: 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 Zhu et al. [2003]. 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 Zhu et al. [2003], 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, Specifically, all nodes with temperature aboveT 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.
if y i = k then 5: end for 8: The key difference with the vanilla method lies in temperature centering (line 9 of the algorithm). Another variant proposed by Zhu et al. [2003] 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: whereT is the average temperature, given by:

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: For p > q, using the fact thatT ∈ (0, 1), we get δ 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, 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: 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 [Zhu et al., 2003] (also without temperature centering) and our algorithm (with temperature centering).
All datasets and codes are available online 1 , making the experiments fully reproducible.

Synthetic data
We first use the stochastic block model (SBM) [Airoldi et al., 2008] 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).
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 [Fey et al., 2018;Huang et al., 2018;Wijesinghe and Wang, 2019].    [Haruechaiyasak and Damrongrat, 2008], 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 [Leskovec and Krevl, 2014]. 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 and 3 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.  Figure 4: Impact of the fraction of seeds for label 1 on macro-F1 score (mean ± standard deviation).

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.