PaperlayerView exact revision on arXiv

Source-linked AI summary

Propagation Kernels

Marion Neumann, Roman Garnett, Christian Bauckhage, Kristian Kersting

arXiv:1410.3314v1stat.MLcs.LG

TL;DR

Graph kernels need to compare structured data when node information is incomplete, uncertain, noisy, or continuous. This paper introduces propagation kernels, which monitor information spread through graphs and compare intermediate distributions. The authors report competitive accuracy with state-of-the-art kernels and better runtime than recently developed efficient and scalable graph kernels.

  • Problem

    Existing graph kernels often assume unlabeled graphs or complete discrete labels and have limited support for partially observed, uncertain, noisy, or continuous information.

  • Method

    Propagation kernels initialize node label or attribute distributions, propagate them through graph edges, and compare the resulting distributions across iterations.

  • Results

    Propagation kernels are competitive in accuracy with state-of-the-art kernels and outperform recently developed efficient and scalable graph kernels in runtime across several classification benchmarks.

  • Takeaways & Limitations

    The framework can be adapted to graph types and applications that were previously intractable for graph kernels, including regular large graphs such as image grids.

  • Takeaways & Limitations

    The framework allows label and attribute information to be absent or only partially observed, but its general definition does not require both information types to be present.

Abstract

from arXiv · show

We introduce propagation kernels, a general graph-kernel framework for efficiently measuring the similarity of structured data. Propagation kernels are based on monitoring how information spreads through a set of given graphs. They leverage early-stage distributions from propagation schemes such as random walks to capture structural information encoded in node labels, attributes, and edge information. This has two benefits. First, off-the-shelf propagation schemes can be used to naturally construct kernels for many graph types, including labeled, partially labeled, unlabeled, directed, and attributed graphs. Second, by leveraging existing efficient and informative propagation schemes, propagation kernels can be considerably faster than state-of-the-art approaches without sacrificing predictive performance. We will also show that if the graphs at hand have a regular structure, for instance when modeling image or video data, one can exploit this regularity to scale the kernel computation to large databases of graphs with thousands of nodes. We support our contributions by exhaustive experiments on a number of real-world graphs from a variety of application domains.

1 Introduction

Propagation kernels address the difficulty of learning from graphs with diverse, incomplete, uncertain, or continuous node and edge information. They monitor information propagation to construct flexible graph similarities, using efficient computation to support large and novel applications.

  • Motivation: Real-world structured data often contains graphs with rich, partially available, uncertain, noisy, or continuous node and edge information.Examples include semantically annotated images, sensor-derived point clouds, and text entities backed by structured networks.
  • Motivation: Existing graph kernels commonly assume unlabeled graphs or complete discrete labels, while methods for continuous attributes have only recently received greater attention.These approaches are therefore not broadly designed for the varied information conditions found in real-world graphs.
  • Approach: Propagation kernels initialize node label or attribute distributions, iteratively propagate them along edges, and compare induced node distributions between graphs.Maintaining distributions allows uncertain information to be represented during propagation.
  • Approach: Locality-sensitive hashing bins propagated distributions into graph feature vectors in time linear in the total number of nodes, avoiding all-pairs node-distribution comparisons.The hash values can preserve total variation and Hellinger probability distances.
  • Contributions: The framework extends propagation kernels from discrete labels to continuous attributes and supports propagation schemes for numerous graph classes.The propagation scheme can be selected according to the input graph type.
  • Evaluation: Propagation kernels are evaluated on bioinformatics benchmarks and applications including plant-disease image classification and 3d object category prediction.The experiments assess feasibility and performance on large real-world graph databases.

2 Kernels and Graphs

Propagation kernels connect graph kernels with kernels on graphs, probability distributions, and structured sets. Their distinguishing strategy is to compare information distributions generated during propagation rather than relying only on converged outcomes.

  • Research connections: Propagation kernels relate graph-kernel research to kernels between graphs, kernels between nodes, and kernels between probability distributions.They therefore draw on multiple established lines of kernel research.
  • Graph-kernel families: Walk-, path-, and limited-subgraph-based graph kernels capture graph structure through different structural units.These categories include several established graph-kernel families.
  • Partially labeled graphs: WL kernels are generally competitive in performance and runtime but are designed for fully labeled graphs, leaving large partially labeled graphs difficult to compare.Marking every unlabeled node with one unique symbol is one proposed extension, but it collapses all unlabeled nodes together.
  • Kernels on graphs: Kernels on graphs use local-neighborhood similarity, including probabilities that labels encountered during parallel random walks coincide.Related methods also use random walks in relaxation-labeling and node-label prediction.
  • Distribution and set kernels: Propagation kernels differ from convergence-based distribution kernels by counting common sub-distributions induced after each propagation iteration.Hash kernels instead directly approximate kernel values between structured sets, whereas propagation kernels hash distributions and derive count features.

3 Information Propagation on Graphs

Information propagation on graphs is modeled with random walks that spread labels or attributes through graph structure. Propagation kernels use the evolving intermediate distributions, including before convergence, to represent graph structure.

  • Random-walk propagation: Propagation kernels compare node label or attribute distributions after each step of an appropriate random walk.The framework builds on label diffusion and label propagation methods used for node-level learning.
  • Graph representation: Graphs are represented with vertices, weighted adjacency structure, and possibly partially observed labels or continuous node attributes.Labels are nominal values, while attributes are continuous vectors.
  • Markov random walks: A random walk is a Markov process whose one-step transition probabilities depend only on the current node and are represented by a row-normalized transition matrix.The transition matrix is derived from the weighted adjacency matrix.
  • Label diffusion: Label diffusion initializes observed nodes with concentrated label distributions and monitors the labels encountered by random walks leaving each node.Each node receives a feature vector describing its label distribution.
  • Absorbing walks: Absorbing random walks modify transitions so that walks remain at designated absorbing nodes once encountered.In label propagation, labeled nodes can serve as absorbing states and unlabeled nodes receive propagated label distributions.
  • Propagation schemes: Propagation kernels can use different random-walk schemes, including diffusion, label propagation, and partially absorbing walks, depending on graph type.The framework does not require one specific propagation scheme.
  • Early stopping: Because non-absorbing random walks converge to an uninformative constant steady state, propagation kernels use the distribution evolution up to a given length through early stopping.The kernel sums contributions from intermediate distributions rather than only the limiting distribution.

4 Propagation Kernel Framework

Propagation kernels compare graphs by propagating node information, comparing resulting distributions, and accumulating kernel contributions across iterations. Binning and counting make these comparisons scalable while preserving positive semidefiniteness.

  • General definition: Propagation kernels define graph similarity from node information that evolves through information propagation across a sequence of graph states.The node kernel compares propagated label and attribute distributions at each iteration, and contributions are combined across iterations.
  • General definition: Propagation kernels support label-only, attribute-only, or combined node kernels, with positive semidefinite label and attribute kernels yielding a positive semidefinite graph kernel.When attributes are absent, the node kernel reduces to the label kernel.
  • General definition: The framework initializes node distributions, propagates them along edges, compares induced distributions, and aggregates count-feature kernel contributions.The general computation is summarized by Algorithm 1 and illustrated for binary labels with one iteration of label propagation.
  • Runtime complexity: Binning node information and counting bin strengths reduces pairwise feature computation from O(n_i n_j) to O(n_i + n_j), followed by a base-kernel computation over bins.For a linear base kernel, the final operation is an outer product of count vectors; one iteration over all graphs costs O(n^2 n⋆).
  • Runtime complexity: Feature computation propagates information in O((k + D)M) = O(M) per propagation step, repeated t_max − 1 times, where M is the total number of edges.The edge-based cost is typically below a dense O(N^2) operation because graphs usually contain far fewer edges than node pairs.

5 Propagation Kernel Component 1: Node Kernel

The node-kernel component compares propagated label distributions and continuous attributes by quantizing information into bins. Locality-sensitive hashing supports efficient comparisons under total variation, Hellinger, and related distances.

  • Definitions: Propagation kernels use node kernels to compare label distributions and attribute information after propagation.The framework permits kernels based on labels, continuous attributes, or propagated attribute distributions.
  • Locality-sensitive hashing: Locality-sensitive hashing maps similar distributions or attribute values to integer-valued bins, enabling binary node kernels based on equality of hash values.The hash function is applied to label distributions, direct continuous attributes, or transformed distributions depending on the chosen metric.
  • Attribute kernels: Continuous attributes can use a simple equality-based hash kernel, a thresholded Gaussian, a Gaussian kernel, or products of one-dimensional kernels for higher-dimensional attributes.Each attribute dimension may use its own locality-sensitive hash function.
  • Locality-sensitive hashing: The hashing procedure selects a random projection according to the metric, adds a random offset, and assigns each projected value to a bin of width w.Gaussian projections are used for ℓ2 or Hellinger metrics, while Cauchy-based projections are used for ℓ1 or total variation metrics.
  • Locality-sensitive hashing: For discrete label distributions, total variation hashing uses direct vectors, whereas Hellinger hashing applies a square-root transformation before locality-sensitive hashing.Total variation is half the ℓ1 metric, while Hellinger is a scaled ℓ2 metric after the square-root map.

6 Propagation Kernel Component 2: Propagation Scheme

Propagation kernels adapt their propagation scheme to graph type, supporting labeled, partially labeled, directed, weighted, attributed, and regular grid graphs. For continuous attributes and grid structures, distributions are propagated efficiently while preserving useful structural information.

  • Propagation kernels choose propagation schemes suited to the graph dataset, including random-walk-based label diffusion and label propagation.The framework explicitly covers fully labeled, unlabeled, partially labeled, directed, attributed, and regular grid graphs.
  • Partially labeled graphs use label propagation, which restores originally observed labels before each propagation iteration.Unknown-node labels are initialized separately, while labeled-node information is pushed back during propagation.
  • The attributed-graph variant p2k compares both label arrangements and attribute arrangements when measuring graph similarity.Its algorithm hashes label and attribute distributions jointly before adding each iteration’s kernel contribution.
  • Attributed graphs propagate continuous information by representing node attributes as Gaussian mixtures whose weights move across graph edges.Each mixture component shares a covariance matrix, and the initial weight matrix is the identity.
  • Grid graphs replace label diffusion with discrete convolution to reduce the memory burden of propagation on large image-like graphs.For a 100 × 100-pixel patch with an 8-neighborhood, the naïve approach requires 2.4 million floating-point units per graph.
  • Convolution-based grid propagation is translation invariant and, with circularly symmetric neighborhoods, also 90-degree rotation invariant.These invariances support image-based texture classification and permit extensions using locally adaptive filters.

7 Experimental Evaluation

The evaluation examines propagation kernels across labeled, attributed, image, and point-cloud graph datasets, including parameter sensitivity, runtime, accuracy, and flexibility. Results show that propagation kernels are efficient and broadly applicable, with competitive classification performance across benchmark and novel applications.

  • Datasets: The experiments span labeled bioinformatics graphs, attributed chemical and synthetic graphs, semantic image graphs, textures, plant-disease images, and 3D point-cloud object graphs.The datasets distinguish labeled and attributed graphs, while image datasets use pixel-grid graphs and general graphs have varying node degrees.
  • Parameter Analysis: 88.2% to 82.9%: normalizing the kernel matrix reduced mutag accuracy, while incorporating graph structure improved performance by 1.5%.The preferred normalization depends on the task: normalized kernels are used for object-scale invariance, whereas unnormalized kernels are used for chemical compounds.
  • Benchmark Classification: On labeled graphs, propagation kernels were faster than state-of-the-art graph kernels while achieving comparable classification performance.Weisfeiler–Lehman performed best on nci1 and nci109, but propagation kernels ranked second and were computed over one minute faster.
  • Novel Applications: 75.4% to 80.7%: adding object curvature attributes improved 3D point-cloud classification across 11 categories with 40 training examples per query object.Only Weisfeiler–Lehman was feasible among the baseline kernels, and it had poor performance; the other listed baselines exceeded resource or time limits.
  • Novel Applications: 82.5% average accuracy on plants approached the 83.7% best reported result, while propagation kernels remained feasible on huge image datasets without extensive feature tuning.The paper concludes that propagation kernels are flexible and efficient across the evaluated applications.

8 Conclusion

Propagation kernels use random-walk-style propagation to compare structural similarities through induced distributions. Experiments find competitive accuracy and faster runtime, while future work extends the framework beyond classification.

  • Propagation kernels count common sub-distributions produced during each iteration of inference in two graphs.This connects graph-kernel similarity to graph-based learning through propagation.
  • Propagation kernels achieve competitive accuracy with state-of-the-art kernels on classification benchmarks of labeled and attributed graphs.
  • Propagation kernels outperform recently developed efficient and scalable graph kernels in runtime.
  • The framework can be adapted to applications that were previously intractable for graph kernels because it is tied to the propagation scheme.
  • The results are directly applicable to regression, clustering, and ranking, while message-based probabilistic inference could extend the approach to graphical models.

A Runtimes for Partially Labeled Graphs

Figure 8 reports average runtime in seconds over 10 msrc21 instances with 50% labeled nodes across kernel iterations 0–10, comparing pk with two wl variants.

  • Figure 8 measures average runtime in seconds over 10 msrc21 instances with 50% labeled nodes.
  • Runtime is reported for kernel iterations from 0 to 10.
  • The comparison includes pk, wl treating unlabeled nodes as an additional label, and lp+wl using hard labels from converged label propagation.

B Detailed Results on Attributed Graphs

The attributed-graph results report runtime and accuracy measurements under specified experimental settings, with a 72-hour cutoff for unfinished computations.

  • Runtime measurements use cputime reported in seconds, minutes, or hours, with tmax = 10 for pks, hmax = 10 for wl, and k = 7 for csm.Computations used 3.4 GHz Intel Core i7 processors; csm's Java implementation limits direct runtime comparison.
  • Computations marked TIME did not finish within 72h.
  • Attributed-graph accuracies are reported as averages ± standard error from 10-fold cross-validation over 10 runs.
Loading 1410.3314v1…