PaperlayerView exact revision on arXiv

Source-linked AI summary

DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification

Jun Wu, Jingrui He, Jiejun Xu

arXiv:1906.02319v1cs.LGstat.ML

TL;DR

Existing graph neural networks have limited theoretical guidance, do not explicitly preserve degree-specific structure, and offer unclear graph-level pooling explanations. DEMO-Net addresses these gaps with degree-specific multi-task convolution and Hilbert-kernel graph pooling, with experiments demonstrating effectiveness and efficiency.

  • Problem

    Existing graph neural networks have limited analysis of convolution properties, lose degree-specific graph structure, and lack clear theoretical explanations for graph-level pooling schemes.

  • Method

    DEMO-Net uses degree-specific multi-task graph convolution motivated by the Weisfeiler-Lehman test and introduces graph pooling in a degree-specific Hilbert kernel space.

  • Results

    Experiments on node and graph classification benchmarks demonstrate DEMO-Net's effectiveness and efficiency, while its convolution satisfies seed-oriented, degree-aware, and order-free properties.

  • Takeaways & Limitations

    DEMO-Net explicitly preserves degree-specific neighborhood structures for node and graph representation learning and can scale linearly with nodes and edges when T ≪ n and T ≪ m.

  • Takeaways & Limitations

    Partitioning many distinct node degrees into buckets to reduce tasks and improve robustness is left for future work.

Abstract

from arXiv · show

Graph data widely exist in many high-impact applications. Inspired by the success of deep learning in grid-structured data, graph neural network models have been proposed to learn powerful node-level or graph-level representation. However, most of the existing graph neural networks suffer from the following limitations: (1) there is limited analysis regarding the graph convolution properties, such as seed-oriented, degree-aware and order-free; (2) the node's degree-specific graph structure is not explicitly expressed in graph convolution for distinguishing structure-aware node neighborhoods; (3) the theoretical explanation regarding the graph-level pooling schemes is unclear. To address these problems, we propose a generic degree-specific graph neural network named DEMO-Net motivated by Weisfeiler-Lehman graph isomorphism test that recursively identifies 1-hop neighborhood structures. In order to explicitly capture the graph topology integrated with node attributes, we argue that graph convolution should have three properties: seed-oriented, degree-aware, order-free. To this end, we propose multi-task graph convolution where each task represents node representation learning for nodes with a specific degree value, thus leading to preserving the degree-specific graph structure. In particular, we design two multi-task learning methods: degree-specific weight and hashing functions for graph convolution. In addition, we propose a novel graph-level pooling/readout scheme for learning graph representation provably lying in a degree-specific Hilbert kernel space. The experimental results on several node and graph classification benchmark data sets demonstrate the effectiveness and efficiency of our proposed DEMO-Net over state-of-the-art graph neural network models.

1 INTRODUCTION

Graph neural networks learn node and graph representations by combining local graph structure with node attributes, but existing methods provide limited theoretical guidance and do not explicitly preserve degree-specific neighborhoods. DEMO-Net addresses these gaps with degree-specific convolutions and pooling motivated by the Weisfeiler–Lehman test.

  • Motivation: Graph neural networks aggregate and transform local-neighborhood features for node representations, then pool node representations into graph-level vectors for classification.These representations have achieved state-of-the-art performance in node and graph classification tasks.
  • Limitations: Existing methods have limited analysis of convolution properties and can lose degree-specific structure by mixing neighborhood attributes through Laplacian smoothing.The paper illustrates that structurally different nodes may receive similar representations under first-order proximity.
  • Design principles: DEMO-Net argues that graph convolution should be seed-oriented, degree-aware, and order-free, following the perspective of the Weisfeiler–Lehman graph isomorphism test.These properties are intended to map different neighborhoods to different feature representations.
  • DEMO-Net: DEMO-Net uses degree-specific multi-task graph convolution, with separate representation-learning tasks for nodes sharing specific degree values.The model assumes nodes with the same degree value share the same graph convolution.
  • Graph representation: The model introduces degree-specific graph pooling and theoretically places its graph representation in an RKHS induced by a degree-specific Weisfeiler–Lehman graph kernel.This explicitly incorporates degree-specific structure into graph-level representation learning.
  • Evaluation: Experiments on node and graph classification benchmarks demonstrate DEMO-Net’s effectiveness and efficiency.The paper presents the result as an empirical comparison across several benchmark datasets.

2 RELATED WORK

Related work frames graph neural networks as local message-passing models whose theory, degree-specific structure preservation, and graph-level pooling remain incompletely understood. The paper positions its degree-specific pooling method as a response to the latter gap.

  • Graph neural networks: Most graph neural networks recursively aggregate continuous features from local neighborhoods and can be viewed as message-passing neural networks.They generally operate in the node domain to extract spatial topological information.
  • Theoretical analysis: Existing graph neural network architectures have limited theoretical analysis explaining their performance or guiding new methodologies.Prior work has analyzed phenomena such as Laplacian-smoothing-induced over-smoothing and RKHS representations.
  • Graph-level pooling: Graph-level pooling compresses node representations into graph representations while commonly using mean, max, or sum functions for computational efficiency.Maintaining invariance to node order is a central challenge for graph-level pooling.
  • Research gap: Very little prior work explicitly considers degree-specific graph structures in graph representation learning.The proposed pooling method addresses this by compressing learned node representations according to degree values.

3 PRELIMINARIES

This section defines node- and graph-level representation learning and reviews how GNNs aggregate neighborhood information, connecting these operations to the 1-dimensional Weisfeiler–Lehman test.

  • Problem Definition: Node-level learning maps each node in an attributed graph to an embedding where structurally different local neighborhoods should be separated.
  • Problem Definition: Graph-level learning maps each attributed graph to an embedding where graphs with different topological structures should be separated.
  • Graph Neural Networks: The WL perspective frames GNN aggregation as feature relabeling and motivates analysis of how degree and neighbor order affect learned subtree representations.
  • Graph Neural Networks: GNN feature aggregation initializes node attributes, detects 1-hop neighborhoods, and recursively transforms neighborhood information into node representations.
  • Graph Neural Networks: Mean and max aggregation are invariant to neighbor order, while LSTM aggregation requires random permutation to adapt ordered processing to unordered neighborhoods.
  • Graph Neural Networks: A k-layer GNN learns a representation of a depth-k subtree rooted at the seed through recursive neighborhood aggregation.

4 PROPOSED MODEL: DEMO-NET

DEMO-Net learns node and graph representations with degree-specific graph convolution motivated by Weisfeiler-Lehman subtree distinctions. Its design uses seed-oriented, degree-aware, order-free aggregation, multi-task weight or hashing functions, and degree-specific graph pooling.

  • Model motivation: DEMO-Net maps different local subtrees to different feature vectors while treating neighbor permutations as equivalent.This follows the injective aggregation perspective associated with Weisfeiler-Lehman graph isomorphism testing.
  • Graph convolution properties: Its graph convolution is designed to be seed-oriented, degree-aware, and order-free.Seed attributes and degrees distinguish subtrees, whereas neighbor ordering does not.
  • Degree-specific aggregation: DEMO-Net formulates degree-specific neighborhood aggregation as multi-task feature learning, with each task representing nodes sharing a degree value.The approach is intended to preserve degree-specific graph structure during representation learning.
  • Degree-specific aggregation: The model combines shared global weights with degree-specific local weight or hashing functions to learn common and degree-specific neighborhood structures.Hashing is introduced to make multi-task learning efficient when graphs contain many degree values.
  • Discussion: Hashing supports large-scale multi-task learning, while partitioning degree values into buckets is left as future work.The proposed bucket heuristic is suggested as a possible way to improve robustness to noisy graph structure or source-network labels.
  • Graph representation learning: The graph-level representation is theoretically placed in the reproducing kernel Hilbert space of a degree-specific Weisfeiler-Lehman kernel.The paper contrasts this degree-specific kernel space with the standard WL subtree kernel, which cannot measure graph similarity for continuous node attributes.
  • Discussion: DEMO-Net explicitly preserves degree-specific neighborhood structure, and its graph convolution has time complexity linear in the numbers of nodes and edges.The comparison reports that existing models do not capture all three desired properties, particularly degree-specific structure.

5 EXPERIMENTAL RESULTS

Experiments evaluate DEMO-Net on node and graph classification, structural-role identification, and efficiency using social, air-traffic, bioinformatics, and synthetic networks. DEMO-Net generally outperforms comparison methods while retaining favorable scaling.

  • 5.1 Experiment Setup: Experiments use seven node-classification datasets spanning social and air-traffic networks, plus four bioinformatics graph-classification benchmarks.Air-traffic node labels reflect airport activity; bioinformatics graphs include MUTAG, PTC, PROTEINS, and ENZYMES.
  • 5.2 Node Classification: Node-classification results show DEMO-Net models significantly outperform graph-neural-network baselines, with at least 10% higher mean accuracy.Results use repeated train/validation/test splits and report mean accuracy with standard variance.
  • 5.2 Node Classification: DEMO-Net models outperform RolX, struc2vec, and GraphWAVE across the evaluated Brazil and USA air-traffic train-test splits.Unlike these unsupervised baselines, DEMO-Net incorporates both topology and node attributes.
  • 5.3 Graph Classification: Degree-specific graph-level pooling improves performance over mean pooling in most cases, while DEMO-Net remains comparable to other graph neural networks and DeepWL.The comparison covers MUTAG, PTC, PROTEINS, and ENZYMES.
  • 5.4 Efficiency: Each DEMO-Net(hash) layer has complexity O(nFF′ + mF′) when T ≤ n, while DEMO-Net(weight) scales linearly when T ≪ n and T ≪ m.Here n and m are node and edge counts, and T is the number of degree-value tasks.
  • 5.4 Efficiency: Running time is linear in the number of nodes, and DEMO-Net models are much more efficient than GAT on node classification.Wall-clock time per epoch includes forward pass, loss calculation, and backward pass.

6 CONCLUSIONS

The paper concludes that DEMO-Net uses degree-specific convolution and pooling to represent node and graph structure. Experiments support its effectiveness, while the conclusion summarizes the model and its degree-specific Hilbert-kernel interpretation.

  • 6 CONCLUSIONS: DEMO-Net formulates feature aggregation as multi-task learning organized by node degree to preserve degree-specific graph structure.The model targets both node and graph classification.
  • 6 CONCLUSIONS: The proposed convolution is designed to be seed-oriented, degree-aware, and order-free, reflecting the Weisfeiler-Lehman perspective.These properties are intended to map different subtrees to different feature representations.
  • 6 CONCLUSIONS: The graph-level pooling method yields graph representations that provably lie in a degree-specific Hilbert kernel space.The paper identifies this space through its degree-specific Weisfeiler-Lehman graph kernel.
  • 6 CONCLUSIONS: Experiments on real networks demonstrate the effectiveness of DEMO-Net for the paper’s node- and graph-representation objectives.The conclusion states this result without narrowing it to a single dataset or metric.

A APPENDIX FOR REPRODUCIBILITY

The appendix supplies reproducibility details and proofs for DEMO-Net’s degree-specific representation and kernel-space claims. It formalizes injective subtree mappings, reference-graph constructions, and the RKHS result.

  • Proofs: The appendix defines an injective encoding that maps structurally distinct subtrees to different feature vectors.Seed features and degree-specific neighborhood features are combined before an injective map into R^d.
  • Proofs: The construction partitions natural numbers by degree values and assigns symmetric injective mappings to degree-specific neighbor sets.This supports distinct representations for neighborhoods associated with different degree values.
  • Kernel Analysis: The graph representation hG belongs to the RKHS induced by Kσ,DWL.This is established using the reference graph construction and the composed kernel.
  • Kernel Analysis: The appendix expresses graph convolution outputs through kernel compositions involving the activation kernel and degree-specific Weisfeiler-Lehman kernel.The reference graph is constructed from model parameters and the activation function.
  • Degree-Specific Convolution: The degree-specific weight formulation uses degree-dependent parameters and concatenates seed and neighborhood features.The appendix notes that the resulting feature element lies in either the seed or neighborhood feature contribution.
  • Assumption: The appendix’s stated assumption for one case is that node features equal the sum of neighborhood features.This assumption is explicitly flagged in the proof discussion.
Loading 1906.02319v1…