Learning Strong Graph Neural Networks with Weak Information
Graph Neural Networks (GNNs) have exhibited impressive performance in many
graph learning tasks. Nevertheless, the performance of GNNs can deteriorate
when the input graph data suffer from weak information, i.e., incomplete
structure, incomplete features, and insufficient labels. Most prior studies,
which attempt to learn from the graph data with a specific type of weak
information, are far from effective in dealing with the scenario where diverse
data deficiencies exist and mutually affect each other. To fill the gap, in
this paper, we aim to develop an effective and principled approach to the
problem of graph learning with weak information (GLWI). Based on the findings
from our empirical analysis, we derive two design focal points for solving the
problem of GLWI, i.e., enabling long-range propagation in GNNs and allowing
information propagation to those stray nodes isolated from the largest
connected component. Accordingly, we propose D$^2$PT, a dual-channel GNN
framework that performs long-range information propagation not only on the
input graph with incomplete structure, but also on a global graph that encodes
global semantic similarities. We further develop a prototype contrastive
alignment algorithm that aligns the class-level prototypes learned from two
channels, such that the two different information propagation processes can
mutually benefit from each other and the finally learned model can well handle
the GLWI problem. Extensive experiments on eight real-world benchmark datasets
demonstrate the effectiveness and efficiency of our proposed methods in various
GLWI scenarios.
Yixin Liu, Kaize Ding, Jianling Wang, Vincent Lee, Huan Liu, Shirui Pan
# Learning Strong Graph Neural Networks with Weak Information

###### Abstract.

Graph Neural Networks (GNNs) have exhibited impressive performance in many graph learning tasks. Nevertheless, the performance of GNNs can deteriorate when the input graph data suffer from weak information, i.e., incomplete structure, incomplete features, and insufficient labels. Most prior studies, which attempt to learn from the graph data with a specific type of weak information, are far from effective in dealing with the scenario where diverse data deficiencies exist and mutually affect each other. To fill the gap, in this paper, we aim to develop an effective and principled approach to the problem of graph learning with weak information (GLWI). Based on the findings from our empirical analysis, we derive two design focal points for solving the problem of GLWI, i.e., enabling long-range propagation in GNNs and allowing information propagation to those stray nodes isolated from the largest connected component. Accordingly, we propose D\({}^{2}\)PT, a dual-channel GNN framework that performs long-range information propagation not only on the input graph with incomplete structure, but also on a global graph that encodes global semantic similarities. We further develop a prototype contrastive alignment algorithm that aligns the class-level prototypes learned from two channels, such that the two different information propagation processes can mutually benefit from each other and the finally learned model can well handle the GLWI problem. Extensive experiments on eight real-world benchmark datasets demonstrate the effectiveness and efficiency of our proposed methods in various GLWI scenarios.

Graph Neural Networks, Missing Data, Few-Label Learning +
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote † †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote † †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote †: Shirui Pan is the corresponding author.

+
Footnote † †: Shirui Pan is the corresponding author.

+
Footnote † †: Shirui Pan is the corresponding author.

+
Footnote † † †: Shirui Pan is the corresponding author.

+
Footnote † † † †: Shirui Pan is the corresponding author.

+
Footnote †
real-world scenarios. To bridge the gap, a natural research question is: "Can we design a universal and effective GNN for graph learning with weak information (GLWI)?"

To answer this question, in this paper, we first conduct a comprehensive analysis to investigate the performance of GNNs when learning with weak information. With empirical discussion, we find information propagation, the fundamental operation in GNNs, plays a crucial role in mitigating the data incompleteness. However, the limitations of model architectures and deficiencies of data hinder conventional GNNs to execute effective information propagation on incomplete data. From the perspective of model architectures, we pinpoint that GNNs with _long-range propagation_ enable sufficient information communication, which not only helps recover missing data but also further exploits the observed information. From the perspective of data, we ascribe the performance degradation of graph learning with extremely weak information (Fig. 1(e)) to the incomplete graph structure. Concretely, the scattered nodes isolated from the largest connected component (i.e., _stray nodes_) lead to ineffective information propagation, which impedes feature imputation and supervision signal spreading. These empirical findings shed light on the key criteria that help improve GNNs to handle the GLWI problem.

Following the above design principles, we propose a powerful yet efficient GNN model, _Dual-channel Diffused Propagation then Transformation_ (D\({}^{2}\)PT for short), for GLWI. Our theme is to enable effective information propagation on graph data with weak information by conducting efficient long-range propagation and relieving the stray node problem. More specifically, to enhance the expressive capability and reduce the computational cost of long-range message passing, we design a graph diffusion-based backbone model termed DPT which enables effective message passing while preserving high running efficiency. To allow information propagation on stray nodes, based on propagated features, we further learns a global graph by connecting nodes sharing similar semantics from a global view. We apply dual-channel training and contrastive prototype alignment mechanisms to D\({}^{2}\)PT, which fully leverages the knowledge of the global graph to optimize the DPT backbone. Extensive experiments on 8 real-world benchmark datasets demonstrate the effectiveness, generalization capability, and efficiency of D\({}^{2}\)PT.

To summarize, our paper makes the following contributions:

* **Problem.** We make the first attempt to investigate the graph learning problem with extremely weak information where structure, features, and labels are incomplete simultaneously, advancing existing research scope from a single angle to multiple intertwined perspectives as a whole.
* **Analysis.** We provide a comprehensive analysis to investigate the impact of data deficiency on GNNs, which further guides our algorithm designs against GLWI problem.
* **Algorithms.** We propose a novel method termed D\({}^{2}\)PT, which provides a universal, effective, and efficient solution for diverse GLWI scenarios.
* **Experiments.** We conduct extensive experiments to demonstrate that D\({}^{2}\)PT can offer superior performance over baseline methods in multiple GLWI tasks.

## 2. Related Works

### Graph Neural Networks

Graph neural networks (GNNs) are a family of neural networks that learn complex dependencies in graph-structured data [25; 56; 51; 5]. Based on the message passing paradigm, existing GNNs are composed of two types of atomic operations: propagation (P) that aggregates representations to adjacent nodes and transformation (T) that updates node representations with learnable non-linear mappings [52; 59; 60]. Different GNNs have their specific designs of P/T functions and orders of P/T operations [51]. Commonly used P functions include averaging [25], summation [52], and attention [45], while T is often defined as perceptron layer(s) [19; 50]. To organize P/T operations, the majority of GNNs follow a PPT scheme, where multiple entangled "P-T" layers are sequentially stacked [19; 52; 45; 5]. There are also some GNNs that execute multi-round P/T operation first, and execute another type of operation in the following step, i.e., PPTT scheme [68; 50] and TPP scheme [6; 15]. Recently efforts extend GNNs to various learning scenarios, such as unsupervised representation learning [65; 67], adversarial attack [55; 57], and architecture search [63; 64].

### Graph Learning with Weak Information

Graph learning with weak information (GLWI) aims to learn graph machine learning models when input graph data with 1) incomplete structure, 2) incomplete features, and/or 3) insufficient labels. Most existing works focus on learning GNNs on graphs with data insufficiency in a single aspect.

To handle _incomplete structure_, **graph structure learning** aims to jointly learn an optimized graph structure along with the backbone GNN [30; 70]. As representative methods, LDS [14] and GEN [49] use Bernoulli model and stochastic block model respectively to parameterize the adjacency matrix, and train the probabilistic models along with the backbone GNNs. IDGL [4] and Simp-GCN [23] introduce metric learning technique to revise the original graph structure. Pro-GNN [24] directly models the adjacency matrix with learnable parameters and learns it with GNN alternatively.

To resolve _incomplete features_, **attribute completion** aims to recover the missing data from the existing ones [3; 10]. Spinelli et al. [38] first apply a GNN-based autoencoder for missing data imputation. SAT [3] introduces a feature-structure distribution matching mechanism to the node attribute completion model. GCN\({}_{MF}\)[40] uses Gaussian Mixture Model to transform the incomplete features at the first layer of GNN. HGNN-AC [22] employs topological embeddings to benefit attribute completion.

Figure 1. Sketch maps of graph data with (a) ideal information, (b) weak structure, (c) weak features, (d) weak labels, and (e) extremely weak information.
A line of studies termed **label-efficient graph learning** propose to learn GNN models from data with _insufficient labels_[(8; 7; 28; 39)]. IGCN [(28)] is a pioneering work that applies a label-aware low-pass graph filter on GNNs to achieve label efficiency. M3S [(39)] leverages clustering technique to provide extra supervision signals and trains the model in a multi-stage manner. CGPN [(46)] utilizes Poisson network and contrastive learning for label-efficient graph learning. Meta-PN [(8)] generates high-quality pseudo labels with label propagation strategy to augment the scarce training samples.

Despite their success in handling GLWI from a single aspect, to the best of our knowledge, none of the existing works has jointly considered the data insufficiency from three aspects. Moreover, with carefully-crafted learning procedures, most of them require high computational costs for training, damaging their running efficiency on large-scale graphs. To bridge the gaps, in this paper, we aim to propose a general, efficient, and effective approach for GLWI.

## 3. Preliminaries

**Notations**. We consider an attributed and undirected graph as \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})=(\mathbf{A},\mathbf{X})\), where \(\mathcal{V}=\{v_{1},\cdots,v_{n}\}\) is the node set with size \(n\), \(\mathcal{E}\) is the edge set with size \(m\), \(\mathbf{A}\in\{0,1\}^{n\times n}\) is the binary adjacency matrix (where the \(i\), \(j\)-th entry \(\mathbf{A}_{ij}=1\) means \(v_{i}\) and \(v_{j}\) are connected and vice versa), and \(\mathbf{X}\in\mathbb{R}^{n\times d}\) is the feature matrix (where the \(i\)-th row \(\mathbf{X}_{i}\) is the \(d\)-dimensional feature vector of node \(v_{i}\)). The label of \(\mathcal{G}\) is represented by a label matrix \(\mathbf{Y}\in\mathbb{R}^{n\times c}\), where \(c\) is the number of classes, each row is a one-hot vector, and the \(i\), \(j\)-th entry \(\mathbf{Y}_{ij}=1\) indicates that node \(v_{i}\) belongs to the \(j\)-th class and vice versa. The neighbor set of node \(v_{i}\) is represented by \(\mathbf{\mathcal{N}}_{v_{i}}=\{v_{j}|\mathbf{A}_{ij}=1\}\). The normalized adjacency matrix is represented by \(\tilde{\mathbf{A}}=\mathbf{D}^{-1/2}\mathbf{AD}^{-1/2}\), where \(\mathbf{D}\) is the diagonal degree matrix \(\mathbf{D}_{ii}=\sum_{j}\mathbf{A}_{ij}\).

**Graph neural networks (GNNs)**. Following the message passing paradigm, GNNs can be defined as the stacked combination of two fundamental operations: **propagation** (\(\mathsf{P}\)) that aggregates the representations of each node to its neighboring nodes and **transformation** (\(\mathsf{T}\)) that transforms the node representations with non-linear mappings [(59)]. With \(\mathbf{h}_{i}^{(i)}\) and \(\mathbf{h}_{i}^{(o)}\) as the input and output representations of node \(v_{i}\) respectively, the \(\mathsf{P}\) operation can be formulated by \(\mathbf{h}_{i}^{(o)}\leftarrow\mathsf{P}(\mathbf{h}_{i}^{(i)},\{\mathbf{h}_{ i}^{(i)}|v_{j}\in\mathbf{\mathcal{N}}_{v_{i}}\})\), and the \(\mathsf{T}\) operation can be formulated by \(\mathbf{h}_{i}^{(o)}\leftarrow\mathsf{T}(\mathbf{h}_{i}^{(i)})\). Taking GCN [(25)] as an implementation, the \(\mathsf{P}\) and \(\mathsf{T}\) can be written as \(\mathbf{h}_{i}^{(o)}=\sum_{j}\tilde{\mathbf{A}}_{ij}\mathbf{h}_{j}^{(i)}\) and \(\mathbf{h}_{i}^{(o)}=\sigma(\mathbf{Wh}_{i}^{(i)})\), where \(\mathbf{W}\) is a learnable parameter matrix and \(\sigma(\cdot)\) is a non-linear activation function.

According to the manner of stacking \(\mathsf{P}\) and \(\mathsf{T}\) operations, GNNs can be divided into two categories: entangled GNNs (\(\mathsf{PTPT}\)) and disentangled GNNs (\(\mathsf{PTPT}\) or \(\mathsf{TPP}\)) [(60)]. For example, a two-layer GCN [(25)] is an entangled GNN that can be written as \(\mathbf{H}^{(o)}=\mathsf{GCN}(\mathbf{H}^{(i)})=\mathsf{P}(\mathsf{T}( \mathsf{P}(\mathsf{T}(\mathbf{H}^{(i)}))))\), where \(\mathsf{P}\) and \(\mathsf{T}\) are stacked alternatively and in couples. A two-layer SGC [(50)] is a disentangled \(\mathsf{PTPT}\) GNN that can be written as \(\mathbf{H}^{(o)}=\mathsf{SGC}(\mathbf{H}^{(i)})=\mathsf{T}(\mathsf{P}(\mathsf{ P}(\mathbf{H}^{(i)})))\), where \(\mathsf{T}\) is executed after all \(\mathsf{P}\) are finished. Given a GNN, we define the iteration times of \(\mathsf{P}\) and \(\mathsf{T}\) as its **propagation step**\(s_{\mathsf{P}}\) and **transformation step**\(s_{\mathsf{T}}\), respectively.

**Semi-supervised node classification**. In this paper, we focus on the semi-supervised node classification task, which is an essential and widespread task in graph machine learning [(19; 14; 19; 25; 39; 45; 50)]. In this task, only the labels of a small fraction of nodes \(\mathcal{V}_{L}\subset\mathcal{V}\) are available for model training, and the goal in inference phase is to predict the labels of unlabeled nodes \(\mathcal{V}_{U}\subset\mathcal{V}\), w.r.t. \(\mathcal{V}_{U}\cap\mathcal{V}_{L}=\emptyset\). We denote the training labels as \(\mathbf{Y}_{L}\in\mathbb{R}^{n_{L}\times c}\) where \(n_{L}=|\mathcal{V}_{L}|\).

**Graph learning with weak information (GLWI)**. To formulate GLWI, we first define ideal graph data for semi-supervised node classification under some ideal conditions.

Definition 3.1 (ideal graph data).: Let ideal graph data be \(\hat{\mathcal{D}}=(\hat{\mathcal{G}},\hat{\mathbf{Y}}_{L})=((\mathcal{V},\hat{ \mathcal{E}},\hat{\mathbf{X}}),\hat{\mathbf{Y}}_{L})\), where \(\hat{\mathcal{E}}\) is an ideal edge set that contains all necessary links, \(\hat{\mathbf{X}}\) is an ideal feature matrix that contains all informative features, and \(\hat{\mathbf{Y}}_{L}\) is an ideal label matrix that contains adequate labels (with number \(\hat{n}_{L}\)) with a balanced distribution.

Note that ideal graph data is a perfect case for graph learning. In real-world scenarios, the data for model training (i.e., observed graph data) are sometimes incomplete and insufficient. Specifically, the structure can be incomplete in graph data with an _incomplete edge set_\(\hat{\mathcal{E}}\in\hat{\mathcal{E}}\) that contains limited edges to provide adequate information for graph learning. Meanwhile, some critical elements in the feature matrix are missing, which can be represented by an _incomplete feature matrix_\(\hat{\mathbf{X}}=\mathbf{M}\odot\hat{\mathbf{X}}\), where \(\mathbf{M}\in\{0,1\}^{n\times d}\) is the missing mask matrix. Besides, the available labels for model training can be scarce, indicating an _insufficient label matrix_\(\hat{\mathbf{Y}}_{L}\) with training number \(\hat{n}_{L}\ll\hat{n}_{L}\). Based on the above definitions, the basic GLWI scenarios can be formulated by:

Definition 3.2 (Basic GLWI scenarios).: Let graph data with weak structure, weak features, and weak labels be \(\mathcal{D}_{\text{ws}}=((\mathcal{V},\hat{\mathcal{E}},\hat{\mathbf{X}}),\hat{ \mathbf{Y}}_{L})\), \(\mathcal{D}_{\text{wf}}=((\mathcal{V},\hat{\mathcal{E}},\hat{\mathbf{X}}),\hat{ \mathbf{Y}}_{L})\), and \(\mathcal{D}_{\text{wf}}=((\mathcal{V},\hat{\mathcal{E}},\hat{\mathbf{X}}),\hat{ \mathbf{Y}}_{L})\), respectively. The targets in graph learning with weak structure, weak features, and weak labels scenarios are to predict the labels of unlabeled nodes \(\mathcal{V}_{U}\) with \(\mathcal{D}_{\text{ws}}\), \(\mathcal{D}_{\text{wf}}\), and \(\mathcal{D}_{\text{wf}}\) for model training, respectively. These three scenarios are defined as basic GLWI scenarios.

In the real world, the data deficiencies often occur, more or less, in three aspects simultaneously, leading to the more intractable extreme GLWI scenario:

Definition 3.3 (Extreme GLWI scenario).: Let graph data with extremely weak information be \(\mathcal{D}_{\text{x}}=((\mathcal{V},\hat{\mathcal{E}},\hat{\mathbf{X}}),\hat{ \mathbf{Y}}_{L})\). The target in extreme GLWI scenario is to predict the labels of unlabeled nodes \(\mathcal{V}_{U}\) with \(\mathcal{D}_{\text{x}}\) for model training.

Notably, in basic scenarios, the graph data only has one type of weak information; on the contrary, the structure, features, and labels are all deficient in extreme scenario. Due to the mutual effects among different data deficiency, extreme scenario is **more challenging** than basic scenarios.

## 4. Design Motivation and Analysis

In this section, we expose the key to solving the GLWI problem is to execute _effective information propagation_ in GNNs. Firstly, we discuss the critical roles of information propagation in handling graph data with weak information. Then, with empirical analysis, we find two crucial criteria that enable effective information propagation and hence benefit GLWI, i.e., employing long-range propagation and alleviating the stray node problem.
### Roles of Information Propagation in GLWI

In GNNs, propagation is a fundamental operation that transmits information along edges in graph-structured data (G
GNNs with larger \(s_{p}\) can generally perform better on basic GLWI scenarios;

**Discussion.** 1) Based on homophily assumption (Zhou et al., 2017; Zhang et al., 2018; Zhang et al., 2019; Zhang et al., 2019), we deduce that nodes with similar features/labels tend to be connected in graph topology, supporting the effectiveness of long-range propagation in feature imputation and supervision signal spreading. However, if \(s_{p}\) is overlarge, noisy information would inevitably occur in receptive fields, which may degrade the performance. During grid search, we also find that \(\text{SGC}(s_{p}=10)\) performs worse than \(\text{SGC}(s_{p}=5)\), indicating that \(s_{p}\) should be kept within an appropriate range. Here, we would like to point out that the default \(s_{p}=2\) for most GNNs is usually ineffective for GLWI. 2) A large \(s_{p}\) tends to aggravate the over-smoothing issue (Zhou et al., 2017; Zhang et al., 2019). In our experiments, we find that graph diffusion mechanism can alleviate the issue by adding ego information at each propagation step with residual connection (Han et al., 2017; Zhang et al., 2019), which allows larger \(s_{p}\) while preserving high performance.

**Summary:** With empirical analysis, we derive _Criterion 1_ to _handle GLWI problem: enabling long-range propagation leads to effective information propagation, which further alleviates the deficiency in structure, features, and labels._

### Stray Nodes Hinder GLWI

In the above subsection, we demonstrate that larger \(s_{p}\) leads to effective information propagation and hence benefits basic GLWI scenarios. Then, we are curious about _how do large-\(s_{p}\) models perform in the scenarios where data insufficiency in features/labels/structure are entangled?_ To answer this question, we conduct experiments (detailed settings are in Appendix A.2) to compare the performance of \(\text{APPNP}(s_{p}=20)\) on graph data with different combinations of weak features (WF), weak labels (WL), and weak structure (WS). From the results in Fig. 2(d), we witness sharp decreases in performance when data are with multiple types of deficiencies. Even with a larger propagation step, unfortunately, conventional GNNs still suffer from the extremely weak information in graph data.

Based on the results, one might ask: does larger \(s_{p}\) make information propagation effective enough for extreme GLWI scenario? Recalling that graph structure provides the "bridges" for information propagation, we speculate the quality of graph structure can also affect the effectiveness of information propagation. Some clues can be found in Fig. 2(d): among the two-aspect combination scenarios, "WF+WS" and "WL+WS" have severer performance degradation than "WF+WL", which indicates the incomplete graph structure (WS) is the major factor hindering GLWI.

To understand how weak structure hinders GLWI, we first investigate the difference between ideal structures and weak structures1. By comparing the distributions of node connection in ideal and incomplete structures, we have an interesting observation: as shown in the upper of Fig. 3(a), in ideal structures, the vast majority of nodes are connected together to form the largest connected component (LCC); in contrast, in weak structures, there exist more stray subgraphs composed of few nodes and more isolated nodes that are even independent to other nodes. On Cora dataset, we visualize the distribution of nodes from connected components with different sizes in the lower of Fig. 3(a). We can demonstrate that in ideal structure, over 90% (2485 out of 2708) of nodes are included in LCC, while this percentage decreases to 64.9% in weak structure. Moreover, about 18% of nodes in weak structure are isolated, while no isolated node exists in ideal structure.

Footnote 1: In the case study, we construct weak structures by randomly removing 50% of edges.

For simplicity, we denote _stray nodes_ as the nodes from stray subgraphs and the isolated nodes, and denote _LCC nodes_ as the nodes within LCC. With empirical analysis, we find that in extreme GLWI scenario, information propagation is ineffective on stray nodes, leading to sub-optimal performance in extreme GLWI scenario.

**Stray nodes hinder feature completion.** In Sec. 4.1, we illustrate that GNNs are able to complete the features with contextual knowledge via recurrent propagation. However, for stray nodes, the missing information is hard to be filled with limited contextual nodes. As shown in the upper of Fig. 3(b), if a specific feature is missing in all nodes within a stray subgraph, it cannot be completed by propagation, even if we increase \(s_{p}\). For the isolated nodes, the propagation is unable to complete their features, which is a worse case. In Table 1, we show the average L2 distance between raw features and the features after propagation in \(\text{SGC}\)(Zhang et al., 2019). We find that the distances on LCC nodes are 2x-9x larger than those on stray nodes, demonstrating that LCC nodes receive much more completion than stray ones.

**Stray nodes hinder supervision signal spreading.** In Sec. 4.1, we point out that GNNs also play the role of spreading supervision signals from labeled nodes to unlabeled nodes. Unfortunately, if all the nodes in a stray subgraph are unlabeled, the supervision single is hard to reach them via propagation (e.g., the nodes with "?" in the lower of Fig. 3(b)). Meanwhile, for the labeled stray nodes, the supervision signals are also trapped in the small connected components and then cannot be propagated to most nodes. In this case, when labeled nodes are extremely scarce, a large number of nodes would be out of the coverage of supervision. As illustrated in Table 1, on APPNP (Han et al., 2017), the test accuracy on LCC nodes is 13.4%

\begin{table}
\begin{tabular}{l|c c|c c} \hline \multirow{2}{*}{Dataset} & \multicolumn{2}{c|}{L2 distance} & \multicolumn{2}{c}{Test accuracy} \\ \cline{2-5}  & LCC nodes & stray nodes & LCC nodes & stray nodes \\ \hline Cora & 2.7870 & 1.0889 & 62.79 & 39.12 \\ CiteSeer & 3.7238 & 1.7312 & 56.82 & 35.99 \\ PubMed & 0.2553 & 0.0278 & 67.54 & 59.93 \\ \hline \end{tabular}
\end{table}
Table 1. Comparison between LCC and stray nodes w.r.t. feature-wise distance/accuracy in extreme GLWI scenario. Experimental details please find in Appendix A.3.

Figure 3. Sketch maps to illustrate stray node problem.
-60.5% higher than the stray nodes, which indicates that stray nodes are more potential to be misclassified due to the lack of supervision.

**Challenge.** Although the stray nodes are easy to be identified in an incomplete graph, it is of great difficulty to handle stray nodes in GLWI. A feasible solution is to connect the stray nodes to LCC. However, directly linking irrelevant nodes together may introduce noisy edges to the original graph, which further harms the feature imputation and label spreading. Moreover, when features and labels are deficient, it is hard to determine how to build the connections between the stray nodes and other nodes.

**Summary:** By investigating how incomplete structure affect feature imputation and supervision signal spreading, we can summarize _Criterion 2: the key to handling extreme GLWI scenario is to address the ineffective information propagation problem on the stray nodes isolated from LCC._

## 5. Methodology

From the analysis in Sec. 4, we pinpoint that the key to addressing GLWI problem is to enable effective information propagation. To this end, we can design GNN models for GLWI following two crucial criteria: _Criterion 1 - enabling long-range propagation_ and _Criterion 2 - handling stray node problem_. With the guidance of _Criterion 1_, in this section, we first present a strong base model termed DPT, a large-\(s_{p}\) GNN that balances the effectiveness and efficiency. Then, following _Criterion 2_, we further propose D\({}^{2}\)PT by introducing a dual-channel architecture with an augmented global graph, which relieves the stray node problem.

### Diffused Propagation then Transformation

Motivated by _Criterion 1_, enlarging the propagation step \(s_{p}\) is critical for effective information propagation; however, the growing computational complexity with the increase of \(s_{p}\) is also non-negligible. For entangled GNNs (e.g., GCN (Golov
an augmented global graph alongside the original graph, and then extract knowledge from the global graph during model training.

In D\({}^{2}\)PT, we employ k-nearest neighbor (kNN) graph as the global graph, which ensures that each node has at least \(k\) neighbors. To leverage the features completed by DPT, we construct kNN graph from the propagated features matrix \(\overline{\mathbf{X}}\) instead of raw features \(\mathbf{X}\). In concrete, the kNN adjacency matrix is written by:

\[\mathbf{A}^{\prime},\text{ where }\mathbf{A}^{\prime}_{ij}=\begin{cases}1,& \text{s}(\overline{\mathbf{X}}_{i},\overline{\mathbf{X}}_{j})\geq\min(\tau( \overline{\mathbf{X}}_{i},k),\tau(\overline{\mathbf{X}}_{j},k)),\\ 0,&\text{otherwise},\end{cases} \tag{3}\]

where \(\text{s}(\overline{\mathbf{X}}_{i},\overline{\mathbf{X}}_{j})\) is the similarity between vectors \(\overline{\mathbf{X}}_{i}\) and \(\overline{\mathbf{X}}_{j}\), and \(\tau(\overline{\mathbf{X}}_{i},k)\) returns the similarity between \(\overline{\mathbf{X}}_{i}\) and its \(k\)-th similar row vector in \(\overline{\mathbf{X}}\). Here \(\mathbf{A}^{\prime}\) is inherently symmetric.

Then, in a parallel manner, we execute DPT on the original graph as well as the global graph simultaneously. For the original channel, the computation follows Sec. 5.1. For the global channel, by replacing the adjacency matrix in Eq. (1) to \(\mathbf{\hat{A}}^{\prime}=\mathbf{D}^{\prime-1/2}\mathbf{A}^{\prime}\mathbf{D }^{\prime-1/2}\), we calculate the global propagated features \(\overline{\mathbf{X}}^{\prime}\). After acquiring the output \(\overline{\mathbf{Y}}^{\prime}\) via Eq. (2), we can finally compute the loss function \(\mathcal{L}^{\prime}_{ce}\) at the global channel. By training the shared-weight MLP model with \(\mathcal{L}_{ce}\) and \(\mathcal{L}^{\prime}_{ce}\) jointly, D\({}^{2}\)PT is able to capture informative knowledge from two graph views and alleviate the affect by stray nodes. Since \(\overline{\mathbf{X}}^{\prime}\) can also be pre-computed before training, D\({}^{2}\)PT inherits the high efficiency of DPT.

**Contrastive Prototype Alignment.** Now we can train the backbone DPT model on both the original and global views. However, the naive dual-channel pipeline has two limitations. First, although original and global channels share model parameters, the generated representations, especially those of stray nodes, can be significantly different due to input structure differences. Consequently, the model may fail to capture common knowledge from both views or even be confused by the disordered supervision signals. Second, both \(\mathcal{L}_{ce}\) and \(\mathcal{L}^{\prime}_{ce}\) are computed based on labeled nodes, leading to the potential over-fitting problem when training samples are scarce.

To bridge the gaps, we introduce a contrastive prototype alignment loss that enhances the semantic consistency between two channels and, at the same time, extracts supervision signals from unlabeled samples. At the first step, we employ a linear projection layer to map the representations \(\mathbf{H}\) and \(\mathbf{H}^{\prime}\) into latent embeddings \(\mathbf{Z}=\mathbf{H}\mathbf{W}_{3}\) and \(\mathbf{Z}^{\prime}=\mathbf{H}^{\prime}\mathbf{W}_{3}\). Then, for each class \(j\in[1,\cdots,c]\), we acquire its prototype (Vaswani et al., 2017; Wang et al., 2017) by calculating the weighted average of latent embeddings:

\[\mathbf{p}_{j}=\sum\nolimits_{\begin{subarray}{c}i\text{argmax}(\overline{ \mathbf{Y}}_{i})=j\end{subarray}}\frac{s_{i}Z_{i}}{S_{j}},\quad\mathbf{p}^{ \prime}_{j}=\sum\nolimits_{\begin{subarray}{c}i\text{argmax}(\overline{ \mathbf{Y}}_{i})=j\end{subarray}}\frac{s_{i}Z^{\prime}_{i}}{S_{j}}, \tag{4}\]

where weight \(s_{i}=1\) for labeled nodes and \(s_{i}=\max(\overline{\mathbf{Y}}_{i})\) (i.e., the confidence in prediction) for unlabeled nodes and \(S_{j}\) is the sum of weight \(s_{i}\) of all nodes allocated to class \(j\). Once the prototypes are computed, we regularize the prototypes from two channels with an Info-NCE-based (Chen et al., 2017) contrastive prototype alignment loss:

\[\mathcal{L}_{cpa}=-\frac{1}{2c}\sum_{j=1}^{c}\left(\log\frac{\text{f}(\mathbf{ p}_{j},\mathbf{p}^{\prime}_{j})}{\sum_{q\neq j}\text{f}(\mathbf{p}_{j}, \mathbf{p}^{\prime}_{q})}+\log\frac{\text{f}(\mathbf{p}_{j},\mathbf{p}^{ \prime}_{j})}{\sum_{q\neq j}\text{f}(\mathbf{p}_{q},\mathbf{p}^{\prime}_{j})} \right), \tag{5}\]

where \(\text{f}(\mathbf{a},\mathbf{b})=\text{e}^{\text{cos}(\mathbf{a},\mathbf{b})/ \tau}\), \(\text{cos}(\cdot,\cdot)\) is the cosine similarity function, and \(\tau\) is the temperature hyper-parameter. \(\mathcal{L}_{cpa}\) increases the agreement between the representations of original and global views on labeled and unlabeled nodes, which helps the model distill informative knowledge from the global view, especially for the stray nodes. Moreover, compared to traditional sample-wise contrastive loss (Chen et al., 2017), \(\mathcal{L}_{cpa}\) enables the model to learn class-level information and further leverage labels, and also enjoys much lower time complexity (\(O(ec^{2})\) rather than \(O(en^{2})\)).

**Learning Objective.** By combining the above three losses with trade-off coefficients \(\gamma_{1}\) and \(\gamma_{2}\), the overall objective of D\({}^{2}\)PT is:

\[\mathcal{L}=\mathcal{L}_{ce}+\gamma_{1}\mathcal{L}^{\prime}_{ce}+\gamma_{2} \mathcal{L}_{cpa}. \tag{6}\]

**Scalability Extension.** In order to adapt D\({}^{2}\)PT to large-scale graphs efficiently, we introduce the following mechanisms.

1) To reduce the cost of computing kNN graphs, based on locality-sensitive approximation (Kang et al., 2017; Wang et al., 2017), we design a global approximation algorithm to efficiently construct globally connected kNN graphs. The core idea is to approximate local kNN twice with different batch splits and integrate two kNN graphs into a connected global graph. Detailed algorithm please see Appendix C.1.

2) To reduce the computational cost of training phase, we adopt a mini-batch semi-supervised learning strategy. In each epoch, we only sample a batch of unlabeled nodes \(\mathcal{V}_{B}\) (\(\left\{\mathcal{V}_{B}\right\}=n_{B}\ll n\)) along with labeled nodes \(\mathcal{V}_{L}\) for model training. In this case, \(\mathcal{L}_{cpa}\) is calculated on \(\mathcal{V}_{L}\cup\mathcal{V}_{B}\) instead of all nodes, which significantly saves the requirement on memory and time. Finally, the time complexity per training epoch is \(O(e(n_{L}+n_{B})(e+d+c)+c^{2}e)\). The detailed complexity analysis is given in Appendix C.3, and the overall algorithm of DPT is in Appendix C.2.

## 6. Experiments

In this section, we perform an extensive empirical evaluation of our methods (DPT and D\({}^{2}\)PT) on various GLWI scenarios. Our experiments seek to answer the following questions:

**RQ1:** How _effective_ are our methods in extreme GLWI scenario?

**RQ2:** Can our methods _generally perform well_ in various basic GLWI scenarios?

**RQ3:** How _efficient_ are our methods in terms of times and space?

**RQ4:** How do the key designs and hyper-parameters influence the performance of our methods?

### Experimental Setups

**Datasets.** We adopt 8 publicly available real-world graph datasets for evaluation, including Cora (Vaswani et al., 2017), CiteSeer (Vaswani et al., 2017), PubMed (Vaswani et al., 2017), Amazon Photo (Vaswani et al., 2017), Amazon Computers (Vaswani et al., 2017), CoAuthor CS (Vaswani et al., 2017), CoAuthor Physics (Vaswani et al., 2017), and ogbn-arxiv (Vaswani et al., 2017). More details and statistics of datasets are summarized in Appendix D.1.

**GLWI scenario implementations.** We simulate various GLWI scenarios by applying stochastic perturbation on graph data and limiting the number of training nodes. Specifically, to build weak structure, we randomly remove 50% of edges from the original graph structure. To construct weak features, we randomly replace 50% of entries in the feature matrix with 0. For datasets except ogbn-arxiv, we randomly select 5 nodes per class to form the training set in weak-label scenario, while this number in other scenarios
is 20. We sample 30 nodes per class for validation and the rest for testing. For ogbn-arxiv dataset, we randomly select 2% nodes for training with weak labels, and the validation and testing sets follow the official setting (Krizhevsky et al., 2014). In extreme scenario, we construct the insufficient structure, features, and labels via the above strategies respectively and combine them together.

**Baselines.** We compare our methods with four groups of baselines: 1) conventional GNNs, including GCN (Krizhevsky et al., 2014), GAT (Krizhevsky et al., 2014), APPNP (Krizhevsky et al., 2014), and SGC (Krizhevsky et al., 2014); 2) GNNs with graph structure learning, including Prony-GNN (Krizhevsky et al., 2014), IDGL (Chen et al., 2016), GEN (Chen et al., 2016), and SimP-GCN (Krizhevsky et al., 2014); 3) GNNs with feature completion, including GINN (Zhu et al., 2017) and GCN\({}_{MF}\)(Chen et al., 2016); 4) label-efficient GNNs, including M3S (Zhu et al., 2017), CGPN (Chen et al., 2016), Meta-PN (Chen et al., 2017), and GRAND (Krizhevsky et al., 2014). In the efficiency analysis, we consider four scalable GNNs, including GraphSAGE (Krizhevsky et al., 2014), ClusterGCN (Chen et al., 2016), PPRGo (Chen et al., 2016), and GAMLP (Chen et al., 2016).

**Experimental Details.** For all experiments, we report the averaged test accuracy and standard deviation over 5 trials. For our methods, we perform grid search to select the best hyper-parameters on validation set. We also search for optimal hyper-parameters for baseline methods during reproduction. More implementation details are demonstrated in Appendix D.2. Our code is available at [https://github.com/yixinliu233/D2PT](https://github.com/yixinliu233/D2PT).
features, and labels, and report the results in Table 3, 4, and 5, respectively. From the results, we find that D\({}^{2}\)PT generally outperforms the baseline methods in all scenarios. Moreover, our base model DPT also achieves competitive performance, especially on data with weak features. The superior performance illustrates the powerful generalization capability of our proposed methods in learning from graph data with different imperfections.

### Efficiency Analysis (RQ3)

We analyze the efficiency of DPT and D\({}^{2}\)PT on ogbn-arxiv dataset in terms of running time per epoch and memory usage on graphic cards. The results are shown in Fig. 5 where DPT\({}^{*}\) and D\({}^{2}\)PT\({}^{*}\) indicate the models that save full data into graphic cards for efficient validation and testing. From Fig. 5(a), we find that D\({}^{2}\)PT enjoys high running efficiency and state-of-the-art performance compared to baselines. For instance, D\({}^{2}\)PT is 3.69x faster than APPNP, 30x faster than GAT, and 225x faster than Meta-PN. Meanwhile, DPT has extremely high efficiency (close to SGC) while still achieving excellent performance. From the perspective of memory usage, thanks to the adjacency decoupling and mini-batch semi-supervised learning designs, the memory usages of D\({}^{2}\)PT and DPT are smaller than 2000MB, which verifies their space efficiency. Even if we load the full dataset for efficient evaluation, their memory usages are still comparable to most baselines. An interesting finding is that two large-\(s_{p}\) scalable GNNs, PPRGo and GAMLP, also yield competitive performance, illustrating the advantage of long-range propagation in GLWI scenarios.

### Ablation and Parameter Studies (RQ4)

**Effect of key components.** We illustrate the effect of dual-channel training and contrastive prototype alignment by removing the corresponding losses. As is shown in the middle block of Table 6, both of these designs give significant performance improvement over the base model, and the contrastive prototype alignment seems to contribute more. Moreover, D\({}^{2}\)PT, which jointly considers both of them, produces the best results.

**Selection of global graph.** Besides generating kNN graph from \(\overline{\mathbf{X}}\), we also attempt two alternative strategies: generating kNN graph from raw features (kNN from \(\mathbf{X}\)) and directly using raw features as the augmented data (Aug. w/o prop). From Table 6, we can observe that these strategies produce poor performance. The observation demonstrates the high quality of the kNN graph from \(\overline{\mathbf{X}}\) where features are completed by long-range propagation.

**Effect of propagation step.** To study the impact of propagation step \(s_{p}\), we tune the iteration number \(T\) (\(T=s_{p}\) in our methods) from 1 to 50 on two datasets. As shown in Fig. 6(a), the performance of DPT and D\({}^{2}\)PT generally increases with the growth of \(T\). The results verify our statement that GNNs with long-range propagation tend to perform better in GLWI scenarios. Also, we can find that the accuracy becomes stable when \(T\geq 20\), indicating that a moderate propagation step can provide sufficient information for GLWI.

**Visualization.** For qualitative analysis, we provide visualizations of the learned representations \(\mathbf{H}\) via t-SNE (Wang et al., 2017). The results on Cora dataset are presented in Fig.6(b) where nodes in the same color are from the same class. We can observe that the result from DPT, where nodes with different labels are mixed together, is not satisfactory enough. The possible reason is that the embeddings of stray nodes are less distinguishable in the latent space. By introducing the global graph with \(\mathcal{L}_{ce}^{*}\) or \(\mathcal{L}_{cpa}\), the decision boundary becomes clearer in (ii) and (iii). With the guidance of two auxiliary losses, D\({}^{2}\)PT performs best, proved by the more compact structure and distinct boundary of the learned representations in (iv).

\begin{table}
\begin{tabular}{l|c c c} \hline \hline Methods & Cora & CiteSeer & PubMed \\ \hline D\({}^{2}\)PT & 66.00\(\pm\)1.20 & 56.99\(\pm\)2.23 & 66.43\(\pm\)2.45 \\ \hline w/o \(\mathcal{L}_{ce}^{*}\) & 61.97\(\pm\)5.22 & 53.56\(\pm\)0.04 & 64.33\(\pm\)2.87 \\ w/o \(\mathcal{L}_{cepa}\) & 61.00\(\pm\)1.77 & 48.37\(\pm\)5.23 & 63.97\(\pm\)5.18 \\ Base (DPT) & 56.37\(\pm\)5.97 & 46.06\(\pm\)4.56 & 65.08\(\pm\)3.13 \\ \hline kNN from X & 54.52\(\pm\)3.22 & 40.56\(\pm\)3.01 & 63.29\(\pm\)4.78 \\ Aug. w/o prop & 52.68\(\pm\)5.51 & 41.22\(\pm\)4.04 & 64.56\(\pm\)3.51 \\ \hline \hline \end{tabular}
\end{table}
Table 6. Performance of D\({}^{2}\)PT and its variants.

Figure 5. Efficiency analysis on ogbn-arxiv dataset.

\begin{table}
\begin{tabular}{l|c c} \hline \hline Methods & Cora & CiteSeer & PubMed \\ \hline GAT & 74.39\(\pm\)1.97 & 57.62\(\pm\)3.69 & 68.98\(\pm\)3.39 \\ APPNP & 78.08\(\pm\)2.39 & 56.20\(\pm\)5.33 & 71.30\(\pm\)3.11 \\ SGC & 76.28\(\pm\)2.13 & 57.99\(\pm\)3.90 & 66.45\(\pm\)4.69 \\ \hline M3S & 76.30\(\pm\)3.08 & 64.17\(\pm\)2.43 & 69.45\(\pm\)5.48 \\ CGPN & 76.09\(\pm\)1.75 & 64.84\(\pm\)2.56 & 69.94\(\pm\)3.25 \\ Meta-PN & 77.83\(\pm\)1.76 & 61.86\(\pm\)3.82 & 71.96\(\pm\)3.46 \\ GRAND & 78.09\(\pm\)1.96 & 59.52\(\pm\)0.45 & 69.17\(\pm\)3.53 \\ \hline DPT & 77.55\(\pm\)2.40 & 60.11\(\pm\)2.30 & 70.07\(\pm\)2.40 \\ D\({}^{2}\)PT & 79.00\(\pm\)2.05 & 67.94\(\pm\)1.14 & 72.17\(\pm\)1.79 \\ \hline \hline \end{tabular}
\end{table}
Table 5. Results in terms of classification accuracy in graph learning with weak labels.

Figure 6. Parameter study and visualization results.
## 7. Conclusion

In this paper, we make the first attempt towards graph learning with weak information (GLWI), a practical yet challenging learning problem on graph-structured data with incomplete structure, features, and labels. With discussion and empirical analysis, we expose the key to addressing GLWI problem is effective information propagation, and figure out two crucial criteria for model design: enabling long-range propagation and handling stray nodes. Following these criteria, we propose a novel GNN model termed D\({}^{2}\)PT that enjoys high efficiency for long-range propagation and solves stray node problem with an augmented global graph and dual-channel architecture. Extensive experiments demonstrate the effectiveness of D\({}^{2}\)PT in multiple GLWI scenarios. In the future, promising follow-up directions include: 1) exploring GLWI for data with more challenging data deficiencies, such as noisy features, noisy edges, and imbalanced label distribution; 2) applying GLWI to more downstream tasks, e.g., graph classification and link prediction; and 3) unsupervised graph learning for incomplete data.

###### Acknowledgements.

 This work is supported by ARC Future Fellowship (No. FT210100097), Amazon Research Award, NSF (No. 2229461), and ONR (No. N00014-21-1-4002).
