PaperlayerView exact revision on arXiv

Source-linked AI summary

Semi-Supervised Graph Classification: A Hierarchical Graph Perspective

Jia Li, Yu Rong, Hong Cheng, Helen Meng, Wenbing Huang, Junzhou Huang

arXiv:1904.05003v1cs.CVcs.LG

TL;DR

The paper asks how to classify graph instances when those instances are nodes in a connected hierarchical graph and labels are scarce. It proposes SAGE with the iterative SEAL-C/AI framework, combining graph-instance and hierarchical-level classifiers. On synthetic and Tencent QQ data, SEAL-C/AI outperform competing methods in accuracy/Macro-F1, while the construction of the hierarchical graph remains data-dependent.

  • Problem

    The paper addresses semi-supervised classification of unlabeled graph instances connected in a hierarchical graph when only limited labels are available.

  • Method

    SAGE embeds arbitrary-sized graph instances into fixed-length vectors, while SEAL-C/AI iteratively update graph-instance and hierarchical-level classifiers.

  • Results

    SEAL-C/AI outperform competing methods in accuracy/Macro-F1 on synthetic graphs and Tencent QQ group data; their reported Macro-F1 scores are 70.8% and 73.2% with 2.6% labeled instances.

  • Takeaways & Limitations

    The approach uses both graph-instance structure and inter-instance connections while producing fixed-length embeddings and interpretable node-importance representations.

  • Takeaways & Limitations

    Constructing the hierarchical graph is data dependent because the connection threshold affects edge density and classification performance.

Abstract

from arXiv · show

Node classification and graph classification are two graph learning problems that predict the class label of a node and the class label of a graph respectively. A node of a graph usually represents a real-world entity, e.g., a user in a social network, or a protein in a protein-protein interaction network. In this work, we consider a more challenging but practically useful setting, in which a node itself is a graph instance. This leads to a hierarchical graph perspective which arises in many domains such as social network, biological network and document collection. For example, in a social network, a group of people with shared interests forms a user group, whereas a number of user groups are interconnected via interactions or common members. We study the node classification problem in the hierarchical graph where a `node' is a graph instance, e.g., a user group in the above example. As labels are usually limited in real-world data, we design two novel semi-supervised solutions named \underline{SE}mi-supervised gr\underline{A}ph c\underline{L}assification via \underline{C}autious/\underline{A}ctive \underline{I}teration (or SEAL-C/AI in short). SEAL-C/AI adopt an iterative framework that takes turns to build or update two classifiers, one working at the graph instance level and the other at the hierarchical graph level. To simplify the representation of the hierarchical graph, we propose a novel supervised, self-attentive graph embedding method called SAGE, which embeds graph instances of arbitrary size into fixed-length vectors. Through experiments on synthetic data and Tencent QQ group data, we demonstrate that SEAL-C/AI not only outperform competing methods by a significant margin in terms of accuracy/Macro-F1, but also generate meaningful interpretations of the learned representations.

1 INTRODUCTION

The paper frames classification where each node is itself a graph instance, creating a hierarchical graph whose inter-instance relationships matter. It addresses complex inputs and scarce labels with SAGE and iterative semi-supervised classifiers, achieving strong performance on synthetic and Tencent QQ data.

  • Problem: The paper studies semi-supervised classification in hierarchical graphs, where interconnected nodes are themselves graph instances.This representation captures relationships among graph instances instead of treating them independently.
  • Method: SAGE embeds arbitrary-sized graph instances into fixed-length vectors for classification.The method also supplies graph-instance predictions and supports meaningful representation interpretation.
  • Method: IC classifies graph instances, while HC classifies them using their embedding vectors and hierarchical connections.A disagreement loss encourages consistency between the two classifiers.
  • Method: SEAL-C/AI iteratively builds or updates IC and HC, using cautious pseudo-label selection or informative-instance annotation to address limited labels.The active-learning extension selects instances for manual annotation before updating the classifiers.
  • Results: 70.8% and 73.2% Macro-F1 were achieved by SEAL-C/AI, respectively, with only 2.6% labeled instances.The reported results state that both methods outperform competing approaches by a large margin.

2 PROBLEM DEFINITION

The paper models each graph instance through its internal objects, attributes, and connections, then links graph instances into a hierarchical graph. It uses available labels and hierarchical topology to classify unlabeled graph instances semi-supervisedly.

  • Graph representation: A graph instance is represented as g = (V,A,X), with nodes drawn from objects, an adjacency matrix A, and attribute matrix X.The node count is |V| = n, and X records attributes for all graph-instance nodes.
  • Hierarchical graph: A set of graph instances is interconnected through adjacency matrix Θ, forming a hierarchical graph.The hierarchy represents connectivity between graph instances in addition to their internal structure.
  • Classification task: The task predicts labels for unlabeled graph instances from labeled instances and hierarchical graph topology.The labeled and unlabeled sets are denoted G_l and G_u, with G = G_l ∪ G_u.
  • Example: In the social-network example, user groups have internal user connections and are linked by interactions or common members.Known game and non-game groups provide labels for inferring the labels of unknown groups.

3 METHODOLOGY

The methodology combines instance-level and hierarchical-graph classifiers with disagreement-aware semi-supervised iteration. SAGE converts arbitrary-sized graph instances into fixed-length, task-informed embeddings for hierarchical classification.

  • Classifier design: The framework builds classifiers IC for graph instances and HC for the hierarchical graph, with disagreement loss enforcing prediction consistency.IC processes individual graph instances, while HC uses their embeddings and inter-instance connections.
  • SAGE embedding: SAGE applies graph convolution, self-attention, and label-informed transformation to produce fixed-length embeddings and class probabilities.Self-attention learns node importance before aggregation into a unified representation.
  • SAGE embedding: SAGE addresses size and permutation invariance by making the embedding independent of node count and node ordering.Node importance is learned according to the task labels rather than a fixed node sequence.
  • Iterative optimization: The optimization alternates supervised-loss minimization with disagreement-aware updates because the joint problem is mixed, non-convex, and vulnerable to overfitting.The disagreement loss acts as a regularizer when labeled graph instances are scarce.
  • Semi-supervised iteration: SEAL-CI updates IC using increasingly larger sets of confident HC predictions, while SEAL-AI selects instances for manual annotation by maximizing disagreement-loss decrease.SEAL-CI fine-tunes from the previous iteration rather than retraining IC from scratch.
  • Complexity: The method has complexity O(E1(L + U)ϕ + E2rv), scaling linearly with graph-instance edges, inter-instance links, and the number of instances.The paper describes this as computationally comparable to GCN-based methods and more efficient than PSCN.

4 EXPERIMENTS

The experiments validate SAGE on PROTEINS and D&D, then evaluate SEAL-C/AI on synthetic and Tencent QQ group data.

  • SAGE is evaluated on the PROTEINS and D&D data sets.The study first tests the graph embedding algorithm before evaluating the full semi-supervised methods.
  • SEAL-C/AI is evaluated on synthetic data and Tencent QQ group data.

4.1 Performance of SAGE

SAGE is compared with graph kernels and deep learning methods on PROTEINS and D&D using repeated 10-fold cross-validation. It outperforms all listed baselines by 1.27%–5.59% in accuracy.

  • Baselines and data sets: SAGE is evaluated on PROTEINS and D&D against four graph kernels and two deep learning approaches.The compared kernels are SP, RW, GK, and WL; the deep learning methods are PATCHY-SAN and graph2vec.
  • Experimental setting: The experiments use 10-fold cross-validation, repeated 10 times per partition, and report average accuracy with standard deviation.
  • Implementation: SAGE uses a two-layer GCN architecture with 128 and 8 output channels, embedding dimension d = 64, and r = 16.The model also uses a 256-unit dense layer with dropout rate 0.5; the number of epochs is the only optimized hyperparameter.
  • Results: 1.27%–5.59%: SAGE outperforms all graph kernel and deep learning methods in accuracy.This result is reported for the PROTEINS and D&D experiments summarized in Table 2.

4.2 SEAL-C/AI on Synthetic Data

On synthetic data, the study visualizes SAGE embeddings and attention, then compares SEAL-C/AI with kernel, embedding, and graph-neural baselines under limited labels. SEAL-C/AI achieve the strongest performance, while the attention patterns highlight graph-structure-specific nodes.

  • Synthetic data generation: The synthetic hierarchical graph uses Cora’s topology and seven graph-generation algorithms to create graph instances representing seven classes.The generated instances include Watts-Strogatz, Tree, Erdős-Rényi, Barbell, Bipartite, Barabási-Albert, and Path graphs.
  • Embedding visualization: SAGE embeddings place graph instances so geometric distance reflects graph similarity, with graph types shown by color in a two-dimensional visualization.SAGE is trained on 1708 instances, and embeddings for 1000 testing instances are projected with t-SNE.
  • Attention analysis: SAGE highlights structure-specific nodes: tree leaves, high-degree Erdős-Rényi nodes within clusters, and bridge or path nodes in Barbell graphs.The examples are selected where SAGE predicts the graph class with confidence above 0.9.
  • Baselines and metrics: The comparison evaluates six baselines, including graph kernels, graph2vec-GCN, Cheby-GCN variants, and SAGE, using repeated average accuracy on synthetic data.Most methods use 300 training instances, while SEAL-AI and active-SAGE-Cheby use 140 labeled instances plus an active-learning budget of 160.
  • Results: SEAL-C/AI achieve the best performance, and both outperform SAGE significantly; SEAL-AI exceeds SEAL-CI by 1.2%.The results are reported for semi-supervised graph classification on the synthetic dataset.
  • Influence of labeled training instances: SEAL-C/AI outperform SAGE across all tested label sizes, while SEAL-AI benefits from iterations that identify informative training samples.SEAL-CI conditionally trusts GCN predictions, which may introduce noise into learning.

4.3 SEAL-C/AI on Tencent QQ Group

The Tencent QQ experiment evaluates SEAL-C/AI on a large hierarchical graph of QQ groups and users, comparing semi-supervised and active-learning variants against several baselines. SEAL-AI performs best, while the results also illustrate how group-link construction and learned attention support interpretation.

  • Dataset and construction: The dataset contains 37,836 QQ groups and 18,422,331 unique anonymized users, with 1,773 groups labeled “game” and the remainder “non-game”.The data also include 298,837,578 friend relationships.
  • Dataset and construction: QQ groups are graph instances whose users are connected by friendship, while groups are linked through common members in the hierarchical graph.User attributes populate each group’s attribute matrix.
  • Results: SEAL-AI outperforms SEAL-CI by 2.4% because cautious iteration introduces increasingly noisy pseudo-label updates, whereas active learning uses informative and correct labels.The false prediction rate within GCN’s λ most confident predictions reaches 2.4% when λ = 2000.
  • Interpretation: In one ego network, “game” groups have 34.5% density versus 8.8% for “non-game” groups, supporting common membership as a useful hierarchical-graph connection.The visualization also depicts learned node importance and node degree within the central group.
  • Construction caveat: The threshold for connecting groups is data dependent: changing from more than one common member to at least one raises edge density from 0.27% to 2.8%.The paper recommends selecting the threshold through a validation set.

5 RELATED WORK

Related work covers semi-supervised classification on networked data, graph representation learning, and active learning. The paper distinguishes its setting by treating each hierarchical-graph node as a variable-sized graph instance and by combining active learning with deep semi-supervised classification.

  • Semi-supervised networked data: Semi-supervised networked-data methods exploit network structure and assume it provides information beyond node attributes.Iterative classification methods repeatedly use neighborhood label estimates and node features.
  • Semi-supervised networked data: Deep networked-data methods combine network context with node features, including approaches that use GCN operators under supervised loss.The paper states that its problem differs because a node is no longer a fixed-size feature vector.
  • Variable-sized graph embedding: Graph representation learning transforms topological instances into fixed-size Euclidean vectors, with prior work moving from node embeddings toward whole-graph embeddings.Existing approaches include graph kernels, node-representation aggregation, ordering, and graph coarsening.
  • Variable-sized graph embedding: Prior whole-graph embedding methods can impose problem-specific node ordering or use clustering and max-pooling to obtain graph representations.These methods are presented as related approaches to embedding graph instances.
  • Active learning: Active learning has been used in collective classification, but the paper describes research combining active learning with deep semi-supervised learning as limited.SEAL-AI differs from the cited image-classification work by using selected samples to update its graph-classification framework.

6 CONCLUSION

The paper studies semi-supervised graph classification when hierarchical-graph nodes are themselves graph instances. It combines SAGE with alternating instance- and hierarchical-level classifiers, and reports stronger performance and interpretable representations on synthetic and Tencent QQ data.

  • Conclusion: SAGE embeds arbitrary-size graph instances into fixed-length vectors that provide a common classification input.It is described as supervised and self-attentive.
  • Conclusion: SEAL-C/AI alternately update graph instance-level classifier IC and hierarchical graph-level classifier HC using an enlarged training set.The framework is semi-supervised and exploits information at both levels.
  • Conclusion: Experiments on synthetic graphs and Tencent QQ group data show that SEAL-C/AI outperform competing methods by a significant margin in accuracy/Macro-F1.The paper also reports meaningful interpretations of learned graph-instance representations.
Loading 1904.05003v1…