{'fraction_non_alphanumeric': 0.027268385864374405, 'fraction_numerical': 0.006733524355300859, 'mean_word_length': 4.609697294401286, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distilling Self-Knowledge From Contrastive Links to Classify Graph Nodes Without Passing Messages

Nowadays, Graph Neural Networks (GNNs) following the Message Passing paradigm become the dominant way to learn on graphic data. Models in this paradigm have to spend extra space to look up adjacent nodes with adjacency matrices and extra time to aggregate multiple messages from adjacent nodes. To address this issue, we develop a method called LinkDist that distils self-knowledge from connected node pairs into a Multi-Layer Perceptron (MLP) without the need to aggregate messages. Experiment with 8 real-world datasets shows the MLP derived from LinkDist can predict the label of a node without knowing its adjacencies but achieve comparable accuracy against GNNs in the contexts of semi- and full-supervised node classification. Moreover, LinkDist benefits from its Non-Message Passing paradigm that we can also distil self-knowledge from arbitrarily sampled node pairs in a contrastive way to further boost the performance of LinkDist.


Introduction
Graphs are universal representations for many real-world data containing pairwise relationship. For example, academic papers and their citation relationship can construct a graph, where the papers are represented as nodes with their encoded abstracts as node features. If one paper cites another, their nodes are connected in that graph. Graphs like this are usually called citation networks [15]. Likewise, we have co-purchase networks [14], co-authorship networks [16], protein-protein interaction networks (PPI), post-post co-comment networks [8], and so on [17].
Due to the wide application of graphs, researchers propose more and more methods to mine information from graphs. A well-investigated family of methods is Graph Neural Networks (GNNs) [18]. They combine node features and the structural information of graphs to study the representations of nodes for downstream tasks, such as Node Classification where the goal is to classify nodes by assigning proper labels to them.
Many Graph Neural Networks follow the Message Passing paradigm [5] which contains three steps: 1. Each node passes its representation to its adjacent nodes 2. Each node aggregates the representations it receives 3. Each node transforms the aggregated information to get its newest representation For example, a layer in Graph Convolutional Network (GCN) [12] aggregates each node's received messages by computing their average and transforms the averaged messages with a linear transformation.
This paradigm applies Neural Networks to graphs and makes learning on graphs flexible and powerful. However, it still has some drawbacks.
• Predicting a single node's label has to aggregate information from multiple adjacent nodes, making the computation heavy and costing extra space to look up adjacent nodes (usually with the adjacency matrix).
• Passing messages is not easy in practice. For batching purposes, we have to group nodes by their degrees (as the number of their adjacent nodes) and invokes message passing group by group if the graph is too large to manipulate its adjacency matrix.
• Relying on information from adjacent nodes takes the graph time and effort to propagate messages onto all nodes when new nodes or new edges are inserted.
One way to rectify some of the aforementioned issues is Knowledge Distillation [6]. Knowledge Distillation is to transfer the knowledge from a well-trained teacher network to a smaller student network for deployment purposes. For example, when the spaces and computing resources on devices are too limited to store adjacency matrices or aggregate multiple messages timely, we can distil the knowledge from a trained GCN into a Multi-Layer Perceptron (MLP) [2] and deploy the MLP alone onto those devices. The deployed MLP can predict without the need to aggregate information from adjacent nodes, thus it can be light-weighted and fast. However, when graphs change, the MLP still has to study the updated knowledge about every single node from the GCN again. This makes Knowledge Distillation hard to apply to dynamic graphs.
However, we observe that the MLP distilled from a trained GCN can sometimes outperform the original GCN, as our experiment in Section 4 shows. It suggests that Message Passing may not be essential if we can find a way to distil the structural knowledge into MLPs. Inspired by this, we propose to distil knowledge from node pairs. Specifically, we predict the label of a node by its features with an MLP and predict the label of its adjacent node with a forked layer. In the meantime, we maximize the agreement of these two predictions by distilling their knowledge into each other. After that, we omit the forked layer and get an MLP that contains distilled structural knowledge. This method, named LinkDist, is light-weighted, fast, and easy to implement. When graphs change, LinkDist adjusts its parameters instead of propagating messages to all nodes. While addressing all the three challenges in Message Passing, the Node Classification experiment in Section 4 shows that the MLPs derived from LinkDist can predict with comparable accuracy against GNNs.

Related Works
Self-Knowledge Distillation Besides the Teacher-Student scheme of Knowledge Distillation, a similar technique known as Self-Knowledge Distillation [21] regularizes a model by distilling its own knowledge without teacher models. An effective way to achieve this is to induce predictions that are consistent with relevant data such as the universal label distribution of same-labelled nodes [20]. Our method LinkDist works similarly. It distils its own knowledge by predicting the label of a node consistently with both the node itself and its adjacent nodes.
Contrastive Learning Contrastive Learning [13] is a technique that learns to distinguish data points without labels by pulling similar points together and pushing dissimilar points away. Likewise, we propose a contrastive way to train LinkDist. While we distil self-knowledge by minimizing the difference of predictions made with two connected nodes, we also maximize the difference of predictions made with two arbitrarily sampled nodes. Besides, different from Contrastive Learning that learns without labels, we pull predictions made with connected nodes to the ground-truth labels and push predictions made with arbitrarily sampled node pairs away from them.

Our Method: LinkDist
In this section, we describe LinkDist that leverages a forked Multi-Layer Perceptron to produce predictions on nodes both from their features and from their locality. It is trained by iterating on the edge set and distilling self-knowledge from links to induce consistent predictions. We then propose a method of contrastive training to distil knowledge from links that do not exist. After training, we evaluate LinkDist in two modes. One is faster, and one is more accurate.

Forked Multi-Layer Perceptron
Our objective is to learn a mapping M : x → (z, s) that receives the features x of a node v and predicts both the node's label y and the label of its adjacent node. In graphic data, aggregating messages from adjacent nodes can help a node to determine its label. Vice versa, it is reasonable to partly recover the label of adjacent node with features of a node.
The mapping M : x → (z, s) can be implemented as a forked Multi-Layer Perceptron with hidden layers, an output layer, and an inference layer. We feed a node v's features x into the hidden layers, encoding them into a hidden representation h. Then, the output layer and the inference layer use the hidden representation h to produce the logits z, s of label distributions respectively, where z is the approximation of v's label y and s is the possible label distribution of v's adjacent node.

The Training of LinkDist
We illustrate the training of LinkDist in Figure 1. In the training phase, we iterate on the edge set E = {(v i , v j ), · · ·} and feed the features x i , x j of each node pair (v i , v j ) into the forked MLP, getting the approximations z i , z j of their labels y i , y j and the approximations s i , s j of their adjacent nodes' labels.

Ground-Truth Label Supervision
If the node v i is assigned with a ground-truth label y i , we supervise z i by minimizing its Cross-Entropy loss with y i . Since v i and v j are each other's adjancet nodes, the label y i is also the possible distribution of s j , so we also supervise s j with y i . Likewise, if the node v j is assigned with a ground-truth label y j , we supervise both z j and s i with y j .
In addition, the label distribution of the edge set that we iterate on is different from that of the node set. To predict labels of nodes in the node set, we assign weights y n /y e to labels when computing the Cross-Entropy loss L CE , where y n is the label distribution in the training set and y e is the label distribution in the edge set with unlabelled nodes masked.
Link Distillation For each node, we have two predictions of its label from different sources. One is from its features. Another one is from its adjacent node. By minimizing their difference L M SE measured with Mean Square Error, we can distil knowledge from both of them into each other, maximizing the agreement of predicting the label of a node by its feature information and by the structural knowledge from its adjacent node.
In total, we optimize L CE + α · L M SE to cast both ground-truth label supervision and link distillation. By default, we set the hyperparameter α = 1 − n e /e where n e is the times that labelled nodes appear Since the node v k is not likely to connect v i , we push s i away from z k and y k by maximizing their differences measured by Mean Square Error and Cross-Entropy respectively. Likewise, we push s k away from z i and y i .
in the edge set. In other words, the more labelled nodes containing supervising information we have, the less important the knowledge inferred from adjacent nodes is.

Contrastive Training With Negative Links
To leverage node pairs that are not connected, we propose a method of contrastive training as illustrated in Figure 2. We sample arbitrary pairs of nodes to construct negative links [7] and feed the features x i , x k of each node pair (v i , v k ) into the forked MLP, getting the approximations z i , z k of their labels y i , y k and the approximations s i , s k of their adjacent nodes' labels.
While we supervise z i with y i and supervise z k with y k as we do in the previous section 3.2, we maximize the Cross-Entropy of s i , z k and the Cross-Entropy of s k , z i . This is because node v k is arbitrarily sampled that it is not likely to connect v i . Therefore, the approximation z i of node v i 's label is probably different from the approximation s k of labels assigned to node v k 's adjacent nodes and z k is probably different from s i . Likewise, we maximize the MSE of z i , s k and the MSE of z k , s i to distil self-knowledge from negative links.
This contrastive training method has to be adopted with the training process described in the previous section 3.2. In this work, we name the contrastively trained model CoLinkDist.

Two Evaluating Modes of LinkDist
The forked MLP in LinkDist outputs the label distribution z of the node with its output layer and the label distribution s of the node's adjacent node with its inference layer. When omitting the inference layer and its output s, the forked MLP becomes an MLP, but with structural knowledge distilled from links. The MLPs derived from LinkDist and CoLinkDist, named LinkDistMLP and CoLinkDistMLP, can classify graph nodes fast without aggregating messages from their adjacent nodes, thus they can be light-weighted to deploy without adjacency matrices or other nodes' features. Moreover, the experiment in Section 4 shows the accuracy of LinkDistMLP outperforms that of vanilla MLPs by large margins, approaching the accuracy of GCNs.
When adjacency matrices and features of adjacent nodes are available, LinkDist can also utilize Message Passing to boost its accuracy. It combines the prediction from the node v i itself and the predictions from its adjacent nodes to estimate its possible labeŷ i with: is the set of nodes that are adjacent to node v i .

Experiment: Node Classification
In this section, we conduct the Node Classification experiment on 8 real-world datasets. The code to reproduce this work is published at https://github.com/cf020031308/LinkDist.

Datasets
To fully evaluate our method, we experiment with 8 real-world datasets including 4 citation networks, 2 co-purchase networks and 2 co-authorship networks. They are Cora, Citeseer, Pubmed [15], Cora Full [3], Amazon Photo, Amazon Computer [14], Coauthor CS and Coauthor Physics [16]. These datasets are very different in many respects. We summarize them in Table 1.
Semi-and Full-Supervised Among the 8 datasets, Cora, Citeseer and Pubmed are distributed with their predefined dataset splits. In detail, in each of these 3 datasets, the training set contains 20 nodes from each class, the validation set contains 500 nodes and the testing set contains 1000 nodes. On Cora, Citeseer and Pubmed, we accordingly use these splits to do the semi-supervised Node Classification experiment. On other datasets, we split nodes into training sets, validation sets and testing sets exactly like on Cora, Citeseer and Pubmed. In particular, we randomly select at most 20 nodes from each class to construct the training set, 500 nodes to construct the validation set, and 1000 nodes to construct the testing set.
In addition to this semi-supervised setting, we further split each dataset with the full-supervised setting. Specifically, we randomly select 60% of the nodes in a dataset to construct its training set. Then, we equally divide the rest nodes into a validation set and a testing set.
Transductive and Inductive In the semi-supervised Node Classification, we experiment with both the transductive setting and the inductive setting. With the transductive setting, methods use all nodes features and connections in the training phase. With the inductive setting, nodes in the two evaluation sets (the validation set and the testing set) are masked in the training phase. So are connections that have endpoints in the evaluation sets. This setting meets practical scenarios where graphs are consistently expanding with new nodes [4].
In the full-supervised Node Classification, the majority of nodes are either in the evaluation sets or connected with nodes from the evaluation sets. So we experiment with only the transductive setting.

Baselines
We implement 3 methods as baselines.
Graph Convolutional Network (GCN) LinkDist working in Message Passing paradigm can utilize all the information that most GNNs use. So we compare LinkDist against GCN to examine its applicability in common situations. Due to the inductive setting, we implement GCN with its normalized adjacency matrix as (D + I) −1 (A + I) instead of (D + I) − 1 2 (A + I)(D + I) − 1 2 . I is the identity matrix, A is the adjacency matrix, and D is a diagonal matrix where each diagonal entry d i is the degree of node v i .

Multi-Layer Perceptron (MLP)
In Non-Message Passing mode, LinkDistMLP works just like an MLP. However, with knowledge distilled from links, LinkDistMLP should go beyond it. So we place an MLP here to act as the lower limit of the LinkDistMLP.

MLP distilled from GCN (GCN2MLP)
We teach an MLP the soft label logits of all nodes outside the evaluation sets predicted by a trained GCN. The distilled MLP has an identical structure to both the MLP and the LinkDistMLP but inherits the structural knowledge from GCNs. We think it is a proper benchmark for LinkDistMLP to measure how far it is from 'the perfection'.
All implementations of MLP and GCN have 3 full-connected layers. The LinkDist has 2 hidden layers, 1 output layer and 1 inference layer, all implemented as full-connected layers. Hidden representations within all layers have the identical size 256. There are 1 Batch Normalization [10], 1 Layer Normalization [1], 1 Dropout [9] with 0.5 possibilities to erase a position and 1 LeakyReLU [19] activator between every two layers.
All the methods can be divided into two groups by whether a method leverages information from adjacent nodes in the evaluation phase. MLP, GCN2MLP, LinkDistMLP, and CoLinkDistMLP involve no Message Passing, whereas GCN, LinkDist, and CoLinkDist do.

Results
We use Adam [11] with a learning rate of 0.01 to optimize parameters. The GCN is trained in full batches. The MLP and the LinkDist are trained in mini-batches with the batch size set to 1024. Since the MLP and the GCN iterates on the node set while the LinkDist iterate on the edge set, we train the former two models for 200 epochs but train the LinkDist for about 200/d epochs whered is the average degree of the graph.
After every epoch of training, we evaluate the method on the two evaluation sets, producing a pair of accuracy scores. After running, we get the testing set accuracy score paired with the highest Table 2: Accuracy Scores (%) in the semi-supervised and inductive Node Classification. Methods are divided into two groups by whether the method aggregates messages from adjacent nodes in the evaluation phase. We bold the highest accuracy for every dataset in each group.

Method
Cora   validation set accuracy score as the score of the evaluated method. We run every method on every dataset 10 times and record the average score in Table 2, Table 3, and Table 4.
From those tables, we can see that the LinkDistMLP can outperform the same-structured MLP on almost all 8 datasets by large margins. While the LinkDistMLP predicts with only the features of the central node, it still matches the GCN in the inductive setting and even exceeds the GCN in the other two settings. Moreover, utilizing Message Passing (LinkDist) and training contrastively (CoLinkDistMLP, CoLinkDist) can both consistently boost the accuracy. This indicates the success of distilling self-knowledge from node pairs and that the LinkDists are competitive methods with GNNs in the Node Classification tasks.
We also notice that the GCN2MLP behaves very well in the semi-supervised setting, especially in the inductive setting where there's still a gap between LinkDistMLPs and the GCN2MLP, as Table 2 and Table 3 show. However, in the full-supervised setting as Table 4 shows, the accuracy of the GCN2MLP is almost the same as that of the MLP. It is far worse than that of the GCN and the LinkDists. This is because the GCN2MLP in the semi-supervised setting gains additional knowledge from nodes that are outside of the training set, whereas in the full-supervised setting, all nodes are either in the training set or in the evaluation sets. There is no much additional knowledge to distil.
We tend to experiment with the PPI dataset [8], where the training set is formed up with several complete graphs and the trained methods are required to classify nodes on completely unseen graphs, but find that the hyperparameter α in the LinkDist become 0 and LinkDist degenerated into a vanilla MLP. In other words, LinkDist may have problems to induce on entirely unseen graphs.

Conclusions
In this work, we propose a novel way named LinkDist to classify nodes on graphs without the need of passing messages.
Semi-and full-supervised Node Classification experiments show that LinkDist can predict with comparable accuracy against GNNs even without information from adjacent nodes.
LinkDist can be very practical because it rectifies the three issues of Message Passing: • LinkDist learns in mini-batches of edges. It requires less space than using adjacency matrices and can be implemented easily for large graphs.
• LinkDist can be deployed to devices with limited resources, predicting fast like MLPs but accurately like GNNs, without the need to store adjacent nodes and their features.
• When new nodes or new edges are inserted, LinkDist updates the predictions of existing nodes by optimizing its learnable parameters, instead of propagating information to all nodes.
While LinkDist in Message Passing mode (LinkDist and CoLinkDist) can produce very competitive accuracy with GNNs, there's still a gap between LinkDist in non-Message Passing mode (LinkDistMLP and CoLinkDistMLP) and GCN2MLP, if experimenting with the inductive setting. It shows the power of networks as simple as MLPs and points out the potential of LinkDist. In the future, we may investigate to find more effective solutions to distil knowledge into MLPs to narrow the gap.

Broader Impact
This work addresses the issues of Message Passing that are widely adopted in Graph Neural Networks. The proposed LinkDist is a general-purpose method. It may reduce the cost of mining information from graphic data in existing applications. To the best of our knowledge, it has no foreseeable negative societal impacts.