PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding

Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, Zhuo Feng

arXiv:1910.02370v2cs.LGstat.ML

TL;DR

Graph embedding methods may omit node attributes, be affected by feature noise, or fail to scale to large graphs. GraphZoom fuses attributes and topology, spectrally coarsens the graph, and refines embeddings from the coarsest level. Across evaluated tasks, it improves accuracy while accelerating embedding by up to 40.8×.

  • Problem

    Some graph embedding methods omit node attributes, others can suffer from noisy node features, and computational and storage costs limit scaling to large graphs.

    Source: §1 · pp. 1–2

  • Method

    GraphZoom fuses node attributes and topology, repeatedly coarsens the graph using spectral similarity, embeds at the coarsest level, and refines embeddings to the original graph.

    Source: §1 · p. 2

  • Results

    GraphZoom accelerates the entire embedding process by up to 40.8× while producing similar or better accuracy than state-of-the-art techniques.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The framework is agnostic to the embedding method and supports plug-and-play use of existing transductive or inductive unsupervised methods.

    Source: §1 · p. 2

    GraphZoom does not preserve node-label information in the coarsened graph; support for supervised embedding models is described as a possible extension.

    Source: §2 · p. 2

Abstract

from arXiv · show

Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, existing graph embedding models either fail to incorporate node attribute information during training or suffer from node attribute noise, which compromises the accuracy. Moreover, very few of them scale to large graphs due to their high computational complexity and memory usage. In this paper we propose GraphZoom, a multi-level framework for improving both accuracy and scalability of unsupervised graph embedding algorithms. GraphZoom first performs graph fusion to generate a new graph that effectively encodes the topology of the original graph and the node attribute information. This fused graph is then repeatedly coarsened into much smaller graphs by merging nodes with high spectral similarities. GraphZoom allows any existing embedding methods to be applied to the coarsened graph, before it progressively refine the embeddings obtained at the coarsest level to increasingly finer graphs. We have evaluated our approach on a number of popular graph datasets for both transductive and inductive tasks. Our experiments show that GraphZoom can substantially increase the classification accuracy and significantly accelerate the entire graph embedding process by up to 40.8x, when compared to the state-of-the-art unsupervised embedding methods.

1 INTRODUCTION

Graph embedding methods face accuracy limitations when they omit node attributes or encounter noisy features, while computational and storage costs constrain scalability. GraphZoom combines graph fusion, spectral coarsening, embedding, and refinement to address both accuracy and scalability.

1 INTRODUCTION

  • Random-walk methods such as DeepWalk and node2vec omit node attributes, while GCNs can suffer from high-frequency noise; large-graph methods also face high computation and storage costs.Stacked GNN layers require many intermediate neighbor embeddings, increasing computation and memory use.Source: §1 · pp. 1–2
  • Earlier multi-level methods addressed embedding quality or scalability separately, and existing coarsening approaches had limitations in training cost, accuracy, or refinement.Chen et al. (2018) and Fu et al. (2019) add training at every level; Liang et al. (2018) use GCN refinement, while Akbas & Aktas (2019) lack proper refinement.Source: §1 · p. 2
  • GraphZoom fuses node attributes with graph topology, coarsens the fused graph by spectral similarity, embeds at the coarsest level, and refines embeddings back to the original graph.The refinement applies a graph filter to smooth embeddings over the graph.Source: §1 · p. 2
  • Evaluations cover transductive citation networks, inductive PPI and Reddit classification, and Friendster scalability; GraphZoom improves classification accuracy over all baseline embedding methods in both task types.Friendster contains 8 million nodes and 400 million edges.Source: §1 · p. 2
  • GraphZoom accelerates embedding by up to 40.8× while producing similar or better accuracy, with relative accuracy increases up to 19.4% and execution-time reductions of at least 2×.Its coarsening reduces runtime without losing key spectral properties, and the framework can incorporate existing unsupervised embedding methods in a plug-and-play manner.Source: §1 · p. 2

2 RELATED WORK

Prior multi-level graph embedding work has pursued quality and scalability through different strategies, while graph filtering has been used to smooth graph signals. GraphZoom draws on both areas for unsupervised embedding.

2 RELATED WORK

  • GraphZoom does not preserve node-label information in the coarsened graph, though the authors believe it can be extended to support supervised embedding models.GAT (Gulcehre et al., 2019) and PPNP are named as possible supervised models.Source: §2 · p. 2
  • Multi-level methods either focus on quality without scalability or embed only the coarsest graph without proper refinement; MILE uses costly GCN refinement that can perform poorly with multiple layers.Chen et al. (2018), Lin et al. (2019), and Fu et al. (2019) focus on quality; Zhang et al. (2018b) and Akbas & Aktas (2019) target scalability; Liang et al. (2018) propose MILE.Source: §2 · p. 3
  • Graph filters operate on graph-defined signals; prior work uses them for denoising, simplifying GCNs, and improving embeddings, while GraphZoom smooths intermediate embeddings during refinement.Maehara (2019) links GCN filtering to removal of high-frequency feature noise; Li et al. (2019) apply generalized filters to embedding models.Source: §2 · p. 3

3 GRAPHZOOM FRAMEWORK

GraphZoom combines graph fusion, spectral coarsening, embedding on the coarsest graph, and iterative refinement back to the original graph.

3 GRAPHZOOM FRAMEWORK

  • The four-phase framework fuses attributes with topology, coarsens the fused graph, embeds at the coarsest level, and iteratively refines embeddings on finer graphs.The refinement proceeds until embeddings for the original graph are obtained.Source: §3 · pp. 3–4

3.1 PHASE 1: GRAPH FUSION

  • Attribute vectors define a weighted k-nearest-neighbor graph, which is combined with the topology graph by a weighted sum to balance both information sources.The approximate kNN construction uses coarsening to restrict neighbor comparisons within clusters, targeting nearly linear time when cluster size is much smaller than the graph.Source: §3.1 · p. 4

3.2 PHASE 2: SPECTRAL COARSENING

  • Local spectral coarsening smooths random vectors to approximate low-frequency Laplacian components, then aggregates neighboring nodes with correlated embeddings into successively smaller graphs.The aggregation scheme is linear in the number of fused-graph edges and is intended to preserve spectral properties.Source: §3.2 · pp. 4–5

3.3 PHASE 3: GRAPH EMBEDDING

  • At the coarsest level, any unsupervised embedding method can produce the node embeddings.Source: §3.3 · p. 5

3.4 PHASE 4: EMBEDDING REFINEMENT

  • Coarse embeddings are projected onto finer graphs and refined by Laplacian smoothing; a spectral filter approximates the costly inversion, and repeated sparse multiplications recover original-graph embeddings without training.The filter uses a power of the normalized, self-loop-adjusted adjacency matrix.Source: §3.4 · pp. 5–6

4 EXPERIMENTS

Experiments evaluate GraphZoom on transductive and inductive benchmarks and Friendster, comparing accuracy and runtime with embedding and multi-level baselines. Results report accuracy and speed gains, while ablations find distinct contributions from fusion, coarsening, and refinement.

4.1 EXPERIMENTAL SETUP

  • The evaluation covers transductive citation and Friendster datasets, inductive PPI and Reddit, and compares with embedding, multi-level, and GraphSAGE baselines.Experiments also evaluate Friendster’s scalability on a graph with 8 million nodes and 400 million edges.Source: §4 · p. 6, §4.1 · pp. 6–7

4.2 PERFORMANCE AND SCALABILITY OF GRAPHZOOM

  • GraphZoom gains 8.3%, 10.4%, and 19.4% in classification accuracy over DeepWalk and node2vec on Cora, Pubmed, and Citeseer, with up to 40.8× runtime reduction.For inductive tasks, it outperforms baselines by 3.4% on PPI and 3.3% on Reddit, with speedup up to 7.6×.Source: §4.2 · p. 7, Table 2 · p. 8, Table 3 · p. 9
  • At matched coarsening levels, GraphZoom achieves better accuracy and speedup than MILE across datasets; MILE accuracy can decline as coarsening increases.With node2vec on Pubmed, MILE accuracy drops from 0.708 to 0.618.Source: §4.2 · p. 8, Table 2 · p. 8
  • On Friendster, GraphZoom improves Micro-F1 by up to 47.6% over MILE and 49.9% over DeepWalk, with speedup up to 119.8×.As coarsening increases, speedup rises while embedding accuracy decreases gracefully.Source: §4.2 · p. 9, Figure 2 · p. 9

4.3 ABLATION ANALYSIS ON GRAPHZOOM KERNELS

  • GraphZoom refinement improves on MILE refinement, especially at larger coarsening levels; its coarsening also improves quality, and combining both kernels performs best among MILE and GraphZoom kernel combinations.Adding fusion further improves classification accuracy by a large margin by incorporating topology and node attributes.Source: §4.3 · p. 10, Figure 3 · p. 10

5 CONCLUSIONS

GraphZoom is a multi-level framework for improving the accuracy and scalability of unsupervised graph embedding. It fuses node attributes with graph topology, coarsens the graph, embeds at the coarsest level, and refines embeddings; experiments report improved accuracy and speed.

5 CONCLUSIONS

  • GraphZoom combines node attributes and topology, spectrally coarsens the resulting graph, embeds at the coarsest level, and iteratively refines embeddings with graph filters.Source: §5 · p. 10
  • Experiments on popular datasets show improvements in both classification accuracy and embedding speed.Source: §5 · p. 10
  • Propagating node labels to the coarsest graph is identified as future work toward supporting supervised graph embedding.Source: §5 · p. 10

APPENDIX A DETAILS OF DATASETS

The appendix describes the datasets and baselines used, along with feature handling for integrating GraphSAGE and DGI with GraphZoom.

APPENDIX A DETAILS OF DATASETS

  • Cora, Citeseer, Pubmed, and Friendster are used for transductive evaluation, while PPI and Reddit are used for inductive evaluation.Friendster has 8 million nodes and 400 million edges; PPI and Reddit use separate train/test splits.Source: Appendix A · p. 13

APPENDIX B DETAILS OF BASELINES

  • The baselines include random-walk embedding methods, DGI, GraphSAGE, and multi-level frameworks HARP and MILE.MILE coarsens the graph, embeds at the coarsest level, then uses GCN refinement; HARP is run with its implementation's fixed coarsening level.Source: Appendix B · p. 13

APPENDIX C INTEGRATE GRAPHZOOM WITH GRAPHSAGE AND DGI

  • For GraphSAGE and DGI, GraphZoom maps node features onto coarsened graphs; DGI embeddings are concatenated with coarsest-level features to retain local information.The concatenation is featurewise.Source: Appendix C · p. 13

APPENDIX D GRAPH SIZE AT DIFFERENT COARSENING LEVEL

This appendix identifies node counts by GraphZoom coarsening level and describes coarsening as a locality-preserving mapping from original nodes to super-nodes.

APPENDIX D GRAPH SIZE AT DIFFERENT COARSENING LEVEL

  • Table 4 reports the number of nodes at each GraphZoom coarsening level; a dash denotes fewer than 50 nodes.Source: Table 4 · p. 14

APPENDIX F SPECTRAL COARSENING

  • Coarsening reduces graph size while aiming to maintain similar structure, mapping each reduced node to a small set of adjacent nodes in the preceding graph.Source: Appendix F · p. 14
  • The mapping operator is a binary matrix that maps nodes to super-nodes and preserves locality by keeping each aggregated node set connected.Source: Appendix F · p. 14

APPENDIX G CPU TIME OF EACH GRAPHZOOM KERNEL

The appendix reports that the embedding kernel dominates GraphZoom's CPU time and discusses how self-loops tune its refinement filter. Choosing the self-loop weight appropriately helps target high-frequency components, while an excessively large weight weakens noise removal.

APPENDIX G CPU TIME OF EACH GRAPHZOOM KERNEL

  • The GraphZoom embedding kernel dominates CPU time, and increasing coarsening level can reduce its cost; the other kernels are described as efficient.Source: Appendix G · p. 16, Figure 4 · p. 16

APPENDIX H GRAPH FILTERS AND LAPLACIAN EIGENVALUES

  • Adding self-loops shifts Laplacian eigenvalues toward zero, allowing the refinement band-stop filter to attenuate high-frequency components when σ is chosen appropriately.The paper uses σ = 2.0 in its experiments.Source: Appendix H · p. 16
  • If σ is too large, most eigenvalues approach zero and the graph filter becomes less effective at removing noise.Source: Appendix H · p. 16

APPENDIX I SPEEDUP OF GRAPHZOOM KERNELS COMPARED TO MILE

GraphZoom’s coarsening and refinement kernels achieve the greatest speedups, while adding fusion trades some speed for better embedding quality.

APPENDIX I SPEEDUP OF GRAPHZOOM KERNELS COMPARED TO MILE

  • Coarsening plus refinement achieves the greatest CPU-time speedups among the compared kernel combinations.The comparison uses DeepWalk as the basic embedding method on Cora, Citeseer, and Pubmed.Source: Appendix I · p. 16
  • Adding the fusion kernel lowers speedups by a small margin but further boosts embedding quality.The comparison identifies a trade-off between embedding quality and runtime efficiency.Source: Appendix I · pp. 16–17
  • For the highest graph-embedding quality, the comparison recommends including the fusion kernel.Source: Appendix I · p. 17

APPENDIX J MORE RESULTS ON PPI DATASETS

On PPI, GraphZoom embeddings remain better than GraphSAGE embeddings as coarsening levels increase; even a 120-node coarsened graph beats the original-graph GraphSAGE baseline.

APPENDIX J MORE RESULTS ON PPI DATASETS

  • With increasing coarsening levels, GraphZoom embeddings remain better than GraphSAGE embeddings using different aggregation functions.Source: Appendix J · p. 17, Figure 7 · p. 18
  • Figure 7 compares GraphZoom and GraphSAGE on PPI.Source: Figure 7 · p. 18
  • GraphZoom’s embedding results remain better than GraphSAGE’s baseline with different aggregation functions, even at level 5, where the coarsened graph has 120 nodes versus GraphSAGE’s original graph with 14,755 nodes.Source: Appendix J · pp. 17–18

APPENDIX K MORE RESULTS ON NON-ATTRIBUTED DATASETS

On non-attributed PPI and Wiki datasets, GraphZoom without fusion improves DeepWalk at the first coarsening level, while further coarsening increases speedup and may reduce performance.

APPENDIX K MORE RESULTS ON NON-ATTRIBUTED DATASETS

  • For link prediction on PPI and Wiki, GraphZoom improves performance by 18.5% with speedup up to 52.0×.Node embeddings are transformed into edge embeddings using the Hadamard operator.Source: Appendix K · p. 19, Table 6 · p. 19
  • Without fusion, GraphZoom improves DeepWalk performance at the first coarsening level on non-attributed PPI and Wiki datasets.Source: Appendix K · p. 19, Table 5 · p. 19
  • Further increasing the coarsening level yields much larger speedup, though performance may drop a little.Source: Appendix K · p. 19

APPENDIX L SENSITIVITY ANALYSIS OF GRAPH FUSION KERNEL

The fusion weight β balances node-attribute and graph-topology information; the best tested value differs across datasets, while the experiments use β = 1.

APPENDIX L SENSITIVITY ANALYSIS OF GRAPH FUSION KERNEL

  • The fusion weight β balances attribute and topology information: too small loses attribute information, while too large undermines topology.The fusion is defined as Afusion = Atopo + βAfeat.Source: Appendix L · p. 19
  • β = 1 achieves the best performance on Cora and Pubmed, while β = 0.5 is best on Citeseer.The tested β values range from 0.1 to 3.Source: Figure 8 · p. 19, Appendix L · p. 20
  • The experiments use β = 1 across datasets.Source: Appendix L · p. 20

Related papers

Loading 1910.02370v2…