Source-linked AI summary
Active Learning for Graph Embedding
Hongyun Cai, Vincent W. Zheng, Kevin Chen-Chuan Chang
TL;DR
Semi-supervised graph embedding assumes labelled nodes are available, although labelling all training data can be impractical. AGE selects informative nodes using graph centrality and learned-embedding criteria, with time-sensitive weights that shift focus as training progresses. Experiments on three public datasets report that AGE outperforms other baselines in node classification.
Problem
Semi-supervised graph embedding assumes labelled training nodes are given, but labelling all data can be impractical, making budgeted node selection important.
Source: §1 · p. 1Method
AGE selects nodes using uncertainty, embedding representativeness, and graph centrality, shifting criterion weights from centrality toward embedding-based scores during training.
Source: §1 · pp. 1–2Results
AGE outperforms all other baselines in node classification across the three evaluated datasets, and adding graph centrality to entropy and density improves average MacroF1 by 2% and MicroF1 by 0.9%.
Source: §5.4 · pp. 6–7Takeaways & Limitations
The experiments support combining graph-based and embedding-based query criteria with time-sensitive weights for active graph embedding.
Source: §1 · p. 2, §5.3 · p. 6, §6 · p. 7The authors note that uncertainty sampling may find noisy nodes.
Source: §4.2.2 · p. 4
Abstract
from arXiv · showhide
Graph embedding provides an efficient solution for graph analysis by converting the graph into a low-dimensional space which preserves the structure information. In contrast to the graph structure data, the i.i.d. node embedding can be processed efficiently in terms of both time and space. Current semi-supervised graph embedding algorithms assume the labelled nodes are given, which may not be always true in the real world. While manually label all training data is inapplicable, how to select the subset of training data to label so as to maximize the graph analysis task performance is of great importance. This motivates our proposed active graph embedding (AGE) framework, in which we design a general active learning query strategy for any semi-supervised graph embedding algorithm. AGE selects the most informative nodes as the training labelled nodes based on the graphical information (i.e., node centrality) as well as the learnt node embedding (i.e., node classification uncertainty and node embedding representativeness). Different query criteria are combined with the time-sensitive parameters which shift the focus from graph based query criteria to embedding based criteria as the learning progresses. Experiments have been conducted on three public data sets and the results verified the effectiveness of each component of our query strategy and the power of combining them using time-sensitive parameters. Our code is available online at: https://github.com/vwz/AGE.
1 INTRODUCTION
Semi-supervised graph embedding relies on labelled nodes, but labelling all training data can be impractical, making selection under a fixed budget important. AGE combines graph-based and embedding-based query criteria, shifting their weights as training progresses; experiments on three public citation datasets report advantages over other active-learning algorithms and a pipeline baseline.
1 INTRODUCTION
- Graph embedding maps graphs to low-dimensional representations that preserve structure and support efficient downstream analysis.The cited examples include node classification, node clustering, and link prediction.Source: §1 · p. 1
- Selecting labelled nodes under a fixed budget matters because labelling all training data may be impractical, and different labelled sets can yield different embedding performance.The problem is challenging because query selection must account for graph structure and coordinate active learning with graph embedding.Source: §1 · p. 1
- AGE combines uncertainty, information density, and PageRank centrality scores, querying at each training epoch and shifting weight from centrality toward embedding-based scores over time.Uncertainty uses information entropy; uncertainty and information density are calculated from the learned embeddings.Source: §1 · pp. 1–2
- The paper reports AGE’s superiority over other active-learning algorithms and a pipeline baseline in experiments on three public citation datasets.The contribution summary also reports studying the impact of the three informativeness criteria.Source: §1 · p. 2
2 RELATED WORK
Prior work spans graph embedding methods and active-learning query strategies. The paper positions AGE at their intersection: it uses graph structure and learned embeddings to select labelled nodes during representation learning.
2 RELATED WORK
- The related-work section reviews graph embedding and active learning as the two topics relevant to selecting labelled training instances under a fixed budget.Source: §2 · p. 2
2.1 Graph Embedding
- Earlier graph-embedding approaches include affinity-graph eigenvectors, proximity objectives, random-walk methods, and deep models; the paper adopts GCN as its example framework.The related-work discussion notes that unsupervised approaches do not fit the paper’s fixed-budget labelled-data setting.Source: §2.1 · p. 2
2.2 Active Learning
- Active learning query strategies are grouped as heterogeneity-, performance-, and representativeness-based, while AGE uses both graph structure and embeddings learned during training.Prior graph active-learning work used graph structure but did not learn node embeddings; the cited representation-learning approach was specific to text classifiers and not applicable to more general graph embedding such as GCN.Source: §2.2 · pp. 2–3
3 PRELIMINARY
The paper uses GCN as an example semi-supervised graph-embedding algorithm and formulates active graph embedding as selecting additional labelled nodes under a budget. Its model encodes graph structure directly rather than relying on explicit graph-based loss regularization.
3 PRELIMINARY
- The preliminary section introduces GCN and the notation used for the semi-supervised graph-embedding algorithm adopted in the framework.Source: §3 · p. 3
3.1 GCN
- GCN encodes graph structure directly in a neural network for semi-supervised node classification, avoiding explicit graph-based regularization in the loss.Its supervised loss is cross-entropy over labelled nodes.Source: §3.1 · p. 3
- The GCN propagation rule uses an adjacency matrix augmented with self-connections, and ReLU activations in all layers except the output layer.The output layer applies row-wise softmax to hidden activations transformed by a trainable hidden-to-output weight matrix.Source: §3.1 · p. 3
3.2 Problem Formulation
- The active graph embedding problem supplies a graph, its adjacency, degree and feature matrices, a labelling oracle, and budget B; the objective is to select B unlabelled nodes for labelling and training.The paper uses GCN as an example embedding algorithm for this objective.Source: §3.2 · p. 3
4 ACTIVE GRAPH EMBEDDING
AGE actively selects labelled training nodes under a fixed labelling budget, using uncertainty and representativeness criteria. It combines graph centrality with embedding-based scores, shifting their relative weights as learning progresses.
4 ACTIVE GRAPH EMBEDDING
- AGE selects labelled training nodes under a fixed budget, and its query strategy is intended to apply to any semi-supervised graph embedding algorithm.GCN is used as the example embedding method.Source: §4 · pp. 3–4
4.1 Active Graph Embedding Framework
- At each GCN epoch, AGE queries one or more unlabelled nodes, adds their labels to the training set, and repeats until convergence or the labelling budget is reached.When the budget is reached, GCN continues training without another query.Source: §4.1 · p. 4
4.2.1 Uncertainty.
- Uncertainty sampling uses information entropy of GCN class probabilities; higher entropy marks a node about which the model is more uncertain.Source: §4.2.1 · p. 4
4.2.2 Representativeness.
- Representativeness combines embedding-space information density with graph centrality, addressing uncertainty sampling’s risk of selecting noisy, unrepresentative regions.Density scores reflect proximity to the node’s cluster center; AGE uses PageRank centrality as its graph measure.Source: §4.2.2 · p. 4
4.3.1 Score Normalization.
- AGE converts the criteria scores to percentiles and selects the unlabelled node maximizing their weighted combination.The weights α, β, and γ sum to 1.Source: §4.3.1 · p. 4
4.3.2 Time-sensitive Parameters.
- Time-sensitive weights favor graph centrality early, then shift toward entropy and density as training progresses.The weights are drawn from beta distributions and normalized to sum to 1.Source: §4.3.2 · pp. 4–5
5 EXPERIMENTS
The experiments assess AGE’s design choices and compare it with other active-learning baselines. They examine centrality selection and time-sensitive criterion weighting, then evaluate comparative performance.
5 EXPERIMENTS
- The experiments test whether PageRank is an appropriate graph-centrality metric and whether time-sensitive parameters help combine query criteria.Source: §5 · p. 5
- A second objective is to compare AGE with other active-learning baselines.Source: §5 · p. 5
- The section introduces the experimental setup before analyzing the results.Source: §5 · p. 5
5.1 Set Up
The experiments use citation-network datasets, designated training, validation, and test nodes, and an initial labelled set followed by a fixed active-learning budget. Node-classification performance is assessed with MacroF1 and MicroF1.
5.1.1 Datasets.
- Experiments use the Citeseer, Cora, and Pubmed citation networks, with document bag-of-words features and undirected, unweighted citation edges.Source: §5.1.1 · p. 5
5.1.2 Dataset division for training, validation and testing.
- Each dataset uses 500 validation nodes, 1,000 test nodes, and the remaining nodes for training; validation sets are fixed across strategies and repeated ten times.The test instances match those used in.Source: §5.1.2 · p. 5
5.1.3 Initial labelled nodes sampling.
- The initial labelled set contains four randomly sampled nodes per class, and the active-learning budget makes total labelled-node counts equal across methods.The experiments repeat initial sampling 200 times and evaluate each algorithm 2,000 times across validation and initial-label sets.Source: §5.1.3 · p. 5
5.1.4 Evaluation metrics.
- Node-classification performance is evaluated using MacroF1 and MicroF1.Source: §5.1.4 · p. 5
5.2 Comparison of Graph Centrality Metrics
The section compares five graph centrality metrics and selects PageRank for AGE because it outperforms the alternatives on Citeseer and Cora, though betweenness is slightly better on Pubmed.
5.2 Comparison of Graph Centrality Metrics
- The comparison covers degree, closeness, betweenness, PageRank, and harmonic centrality.Source: §5.2 · p. 5
- PageRank outperforms the other centrality metrics on Citeseer and Cora, while betweenness is slightly better on Pubmed.PageRank's advantage over betweenness on Citeseer is 7.4% MacroF1 and 5.1% MicroF1; on Cora it is 5.7% MacroF1 and 2.8% MicroF1.Source: §5.2 · pp. 5–6
- PageRank is adopted as AGE's graph centrality metric based on its results across the three datasets.Source: §5.2 · p. 6
5.3 Effect of Time-sensitive Parameters
The section compares time-sensitive criterion weights with fixed weights and reports higher node-classification performance with time-sensitive parameters on Citeseer and Pubmed.
5.3 Effect of Time-sensitive Parameters
- For a fair comparison, γ is tuned within (0, 1) in 0.1 increments, while α and β are each calculated as 0.5 × (1 − γ).Source: §5.3 · p. 6
- Time-sensitive parameters improve performance over fixed parameters by 1.3% MacroF1 and 2% MicroF1 on Citeseer, and 1.4% MacroF1 and 1.7% MicroF1 on Pubmed.Source: §5.3 · p. 6
- The authors report that time-sensitive weights offer a more flexible way to balance criteria at different times than fixed weights.Source: §5.3 · p. 6
5.4 Comparison of AL Qery Strategies
AGE combines entropy, density, and graph centrality with time-sensitive weights; it outperforms the compared baselines in node classification across the three citation datasets.
5.4 Comparison of AL Qery Strategies
- Compared strategies include random, single-criterion and combined-criterion querying, fixed-weight AGE, time-sensitive AGE, and a pipeline baseline.The comparison also includes GCN trained with randomly sampled labeled nodes.Source: §5.4 · p. 6
- AGE beats the random baseline by 7.6% MacroF1 and 3.2% MicroF1 on Citeseer, 5.6% and 3.5% on Cora, and 4.9% and 4.0% on Pubmed.The paired values are MacroF1 and MicroF1, respectively.Source: §5.4 · p. 6
- Among individual criteria, information density is the most unstable and can reduce performance on Cora.Source: §5.4 · p. 6
- Adding graph centrality to entropy+density improves average performance by 2% MacroF1 and 0.9% MicroF1; time-sensitive parameters add 0.9% and 1.3%, respectively.Source: §5.4 · p. 7
- AGE also exceeds GCN by 0.3% MacroF1 and 2.2% MicroF1 on Citeseer, 3.5% and 3.7% on Cora, and 3.4% and 3.7% on Pubmed.The paired values are MacroF1 and MicroF1, respectively.Source: §5.4 · p. 7
- The pipeline approach performs unsatisfactorily; the authors suggest its initial labels may not let GCN learn embeddings informative enough to guide later queries.Source: §5.4 · pp. 6–7
6 CONCLUSIONS
The conclusion presents AGE as an active-learning framework for graph embedding that jointly selects labeled nodes and trains embeddings, evaluating its design on citation networks.
6 CONCLUSIONS
- AGE combines graph centrality with entropy- and density-based query criteria to select labeled nodes using graph structure and learned representations.Source: §6 · p. 7
- Queries occur at the end of each graph-embedding training epoch, with weights shifting from centrality toward embedding-based criteria as learning progresses.Source: §6 · p. 7
- Experiments on three public citation networks evaluate AGE through node classification and compare it with a pipeline baseline.The conclusion presents this comparison as evidence that active learning and graph embedding reinforce each other during training.Source: §6 · p. 7