PaperlayerView exact revision on arXiv

Source-linked AI summary

COSINE: Compressive Network Embedding on Large-scale Information Networks

Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Maosong Sun, Zhichong Fang, Bo Zhang, Leyu Lin

arXiv:1812.08972v1cs.SIcs.LG

TL;DR

Large-scale network embedding is constrained by memory-intensive per-node parameters and slow training. COSINE uses graph-partition-guided parameter sharing to build compact embeddings. Across reported tasks, it improves embedding performance while reducing running time under equal memory usage.

  • Problem

    Large-scale networks make per-node embedding storage memory-intensive, while existing methods also face undertrained low-degree nodes and long training times.

    Source: §1 · p. 1

  • Method

    COSINE uses graph partitioning to guide parameter sharing among node groups, incorporating structural information into network embedding.

    Source: §1 · p. 2

  • Results

    Up to 25% higher AUC in link prediction, up to 23% higher micro-f1 in multi-label classification, and 30% to 70% lower running time are reported with equal memory usage.

    Source: §1 · p. 2

  • Takeaways & Limitations

    COSINE is presented as a way to learn high-quality large-scale network embeddings with limited memory and shorter training time.

    Source: §1 · p. 2, §6 · p. 12

    COSINE assumes nodes can be grouped so their embeddings are partially close and the groups preserve node information.

    Source: §1 · p. 1

Abstract

from arXiv · show

There is recently a surge in approaches that learn low-dimensional embeddings of nodes in networks. As there are many large-scale real-world networks, it's inefficient for existing approaches to store amounts of parameters in memory and update them edge after edge. With the knowledge that nodes having similar neighborhood will be close to each other in embedding space, we propose COSINE (COmpresSIve NE) algorithm which reduces the memory footprint and accelerates the training process by parameters sharing among similar nodes. COSINE applies graph partitioning algorithms to networks and builds parameter sharing dependency of nodes based on the result of partitioning. With parameters sharing among similar nodes, COSINE injects prior knowledge about higher structural information into training process which makes network embedding more efficient and effective. COSINE can be applied to any embedding lookup method and learn high-quality embeddings with limited memory and shorter training time. We conduct experiments of multi-label classification and link prediction, where baselines and our model have the same memory usage. Experimental results show that COSINE gives baselines up to 23% increase on classification and up to 25% increase on link prediction. Moreover, time of all representation learning methods using COSINE decreases from 30% to 70%.

1 INTRODUCTION

Large-scale networks challenge embedding methods through memory demands, sparse-node cold starts, and slow training. COSINE uses graph-partition-guided parameter sharing to improve embedding quality and training efficiency under limited memory.

1 INTRODUCTION

  • Existing embedding methods struggle with large networks because per-node vectors consume memory, low-degree nodes may be undertrained, and training takes time.A 100-million-node network with 128-dimensional floating-point vectors requires more than 100GB for its embedding matrix.Source: §1 · p. 1
  • COSINE assumes groups can capture partially shared node embeddings while preserving information about the nodes.The framework is presented as compatible with most existing network embedding algorithms.Source: §1 · pp. 1–2
  • Sharing can increase vector dimensions without extra memory, let an edge update several groups, and provide low-degree nodes with more training.The paper also describes sharing as structural prior knowledge that reduces the number of training samples needed.Source: §1 · p. 2
  • Up to 25% higher AUC in link prediction and up to 23% higher micro-f1 in multi-label classification; running time decreases 30% to 70%.The comparisons use three embedding methods on three large-scale networks, with baselines and COSINE using the same memory.Source: §1 · p. 2
  • COSINE shares embedding parameters among groups of nodes identified through graph partitioning, incorporating higher-order structure before training.Its computation is contrasted with conventional embedding construction in Fig. 1, where the number of groups is much smaller than the number of nodes.Source: §1 · p. 2, Figure 1 · p. 2

2 RELATED WORK

The related work reviews network-analysis tasks, embedding methods, graph partitioning, and model compression. It positions COSINE alongside lookup-based embeddings and prior compression approaches.

2 RELATED WORK

  • The related-work overview connects network representation learning with applications such as link prediction, vertex classification, and graph partitioning.It introduces prior work across the tasks and methods reviewed in the subsections.Source: §2 · p. 2

2.1 Link Prediction

  • Link prediction estimates the likelihood of edges; prior approaches use topology, node and edge context, attributes, matrix or tensor factorization, and meta-paths.The section frames link prediction as a social recommendation problem.Source: §2.1 · p. 2

2.2 Vertex Classification

  • Vertex classification assigns vertices to one or more groups, with prior work spanning iterative methods, handcrafted features, and node embeddings paired with classifiers.The reviewed embedding approaches are described as computationally efficient and robust to data sparsity.Source: §2.2 · p. 2

2.3 Network Representation Learning

  • Network representation learning maps nodes to low-dimensional vectors; lookup methods store per-node vectors, while GCN and GraphSAGE aggregate neighborhood information with shared parameters.HARP and MILE coarsen or refine graphs but retain embedding lookup, unlike COSINE's parameter-sharing framework.Source: §2.3 · p. 3

2.4 Graph Partitioning

  • Graph partitioning divides vertices into disjoint sets while seeking balanced set sizes and minimizing the total weight of cut edges.The section reviews systems including Metis, Scotch, KaHIP, ParMetis, mt-metis, KaFFPa, and ParHIP.Source: §2.4 · p. 3

2.5 Model Compression

  • Model compression reduces model size while aiming to preserve accuracy; reviewed approaches include low-rank factorization, pruning, and quantization.The section also describes compression methods for word embeddings, including character-based models, basis vectors, and quantization.Source: §2.5 · p. 3

3 PROBLEM DEFINITION

The section defines compressive network embedding as learning compact node representations through shared parameters. It identifies how to separate shared from independent embedding parts and combine them for each node.

3 PROBLEM DEFINITION

  • Network embedding maps nodes in a graph to a low-dimensional vector space, while conventional approaches independently store |V| × d parameters.The paper motivates sharing by the redundancy it hypothesizes in independent embeddings of similar nodes.Source: §3 · p. 3
  • The problem is to find shared and independent embedding parts for similar nodes and combine them into each node's representation.Nodes in the same groups may still have different preferences, which the model must learn.Source: §3 · p. 4
  • Compressive network embedding seeks a model with fewer than d|V| parameters that still represents each node with a d-dimensional vector.Traditional lookup methods store |V| vectors of dimension d.Source: §3 · p. 4

4 METHOD

COSINE combines graph partitioning, group mapping, group aggregation, and an embedding objective to share parameters among structurally related nodes. This framework adapts existing network-embedding methods to limited-memory training.

4 METHOD

  • COSINE maps each node to a set of groups, aggregates their embeddings into node representations, and trains them with existing network-embedding objectives.The framework’s stages are graph partitioning, group mapping, aggregation, and objective-based training.Source: §4 · p. 4

4.1 Graph Partitioning

  • Graph partitioning assigns nodes to roughly equal-sized groups, encouraging more within-group edges and fewer between-group edges for parameter sharing.Non-overlapping methods are chosen because they allow a limit on the number of groups assigned to each node.Source: §4.1 · p. 4

4.2 Group Mapping

  • Random walks sample neighboring groups beyond a node’s initial partition, and the most frequent groups are selected to form its group set.Walks can revisit vertices, giving more attention to them, and can run simultaneously on the network.Source: §4.2 · pp. 4–5

4.3 Group Aggregation

  • A weighted average combines group embeddings into a node representation while remaining invariant to the order of groups.The framework uses a learned aggregation kernel rather than an order-invariant RNN, which would require costly permutation augmentation.Source: §4.3 · p. 5

4.4 Objective Function and Optimization

  • COSINE can use different embedding objectives; with SGNS, it updates group embeddings and aggregation kernels, adjusting the learning rate to stabilize shared-parameter updates.The learning rate for group embeddings is reduced when the aggregation-kernel norm is large.Source: §4.4 · p. 6

5 EXPERIMENTS

Across three large-scale social networks, COSINE improves embedding quality at the same memory usage while reducing running time. The experiments assess multi-label classification and link prediction using three embedding methods.

5 EXPERIMENTS

  • COSINE improves embedding quality at the same memory usage and reduces running time across experiments on three large-scale social networks.The evaluation applies COSINE to three embedding lookup methods and assesses multi-label classification and link prediction.Source: §5 · p. 6

5.1 Datasets

  • The evaluation covers YouTube, Flickr, and Yelp, with network overviews provided in Table 1.The datasets contain user nodes and social relations; their labels represent user interests or reviewed business categories.Source: §5.1 · p. 6, Table 1 · p. 6

5.2 Baselines and Experimental Settings

  • For fair memory-matched evaluation, uncompressed models use dimension 100 and compressed models dimension 8, with group counts adjusted per dataset to equalize memory; each node's group-set size is 5.Source: §5.2 · p. 7

5.3 Link Prediction

COSINE improves link-prediction performance over baseline methods, with especially large gains reported for LINE on YouTube. The evaluation compares node-similarity scores using AUC and MRR.

5.3 Link Prediction

  • The test set consists of 10% randomly removed links; embeddings from the remaining network produce similarity scores for predicting potential links.The authors evaluate three score functions: L1-norm, L2-norm, and dot product.Source: §5.3 · p. 7
  • AUC measures how often an unobserved link scores above a nonexistent link, while MRR assesses the ranks of unobserved links against same-head nonexistent links.MRR averages reciprocal ranks over sampled unobserved links.Source: §5.3 · p. 7
  • Nearly 4% AUC gain and over 7% MRR gain over the best baseline for LINE with COSINE on YouTube.The authors report that COSINE consistently and significantly improves all baseline methods on link prediction.Source: §5.3 · p. 7
  • Dot product is the best score function; COSINE-LINE is best on Yelp and COSINE-N2V on Flickr, with COSINE giving the best AUC and MRR results overall.The authors interpret the results as evidence that encoding high-order proximity before training is essential for precise node-similarity measurement.Source: §5.3 · p. 7

5.4 Multi-Label Classification

COSINE improves classification results across the reported datasets and offers a framework for sharing embedding parameters. The reported gains vary by dataset, while the authors also discuss sparse-network performance and model capacity under limited memory.

5.4 Multi-Label Classification

  • The evaluation uses sampled training nodes and a one-vs-rest SVM on network embeddings, varying the training ratio from 1% to 10%.The remaining nodes are held out for testing, and the classifier uses L2 regularization.Source: §5.4 · p. 7
  • At least 13% Micro-F1 and 24% Macro-F1 gains over all baselines on YouTube; on Flickr, gains are at least 2% and 6%, respectively.The reported gains are for COSINE on node classification.Source: §5.4 · p. 8
  • On Yelp, classification scores change little as the training ratio grows; despite weak structure-label relations, COSINE helps baselines extract the available label information.The authors relate the Yelp classification results to link-prediction results indicating high-quality embeddings on that dataset.Source: §5.4 · p. 8
  • For sparse YouTube, COSINE's encoding of high-order proximity helps LINE2nd achieve performance comparable to DeepWalk and node2vec.The authors note that LINE2nd performs poorly on sparse networks such as YouTube.Source: §5.4 · p. 8
  • For node2vec with COSINE, the best return parameter q is no more than 1 across all evaluated networks, which the authors interpret as local structure being less useful for training.The authors connect this observation to sharing parameters among nodes in the same local structure.Source: §5.4 · p. 8
  • COSINE encodes high-order proximity before training to guide parameter sharing, improving baseline capacity under limited memory across sparse and dense networks.The authors report that the framework works with all baseline methods.Source: §5.4 · p. 8

5.5 Scalability

COSINE models reach classification and link-prediction convergence with fewer training samples than uncompressed models. Across datasets, compressed models consistently reduce sample requirements and produce more stable best-sample choices across tasks.

5.5 Scalability

  • 40% gain: COSINE-LINE with 10 epochs outperforms LINE with 90 epochs on classification.Compressed classification models grow faster and converge before uncompressed models.Source: §5.5 · p. 8
  • Compressed link-prediction models converge before uncompressed models, although their growth speeds are nearly the same.Their initial performance differs even before training, unlike classification, where initial scores match.Source: §5.5 · p. 8
  • Compressed models consistently and significantly reduce training samples, and their best sample counts are closer across the two tasks within a dataset.The authors attribute reduced sample needs to graph partitioning encoding high-order proximity before training, which baselines struggle to learn.Source: §5.5 · pp. 9–10
  • Graph partitioning and parameter sharing help baselines learn faster from data and reduce the training samples needed.The section evaluates performance versus training samples for classification and link prediction on Youtube, and summarizes best sample counts for LINE and DeepWalk across three datasets.Source: §5.5 · pp. 8–10

5.6 Time Efficiency

COSINE reduces embedding runtime through fewer training samples and parameter sharing, with reported gains across large networks and methods. Preprocessing overhead is small in some datasets and can be reused across models.

5.6 Time Efficiency

  • At least 20%: COSINE reduces LINE convergence time on each of three datasets.COSINE-DW also reduces DeepWalk runtime by needing fewer walks to converge, which lowers walking time; node2vec shows a similar result.Source: §5.6 · p. 10
  • 70%: On Yelp, adding preprocessing overhead to COSINE-LINE still reduces total time by 70%.Preprocessing influence is much smaller on Youtube and Flickr, and group mappings can be reused by later models.Source: §5.6 · p. 10
  • COSINE-DW’s runtime comparison separates DeepWalk and COSINE-DW in the figure’s panels.The section attributes acceleration to reduced training samples and parameter sharing.Source: §5.6 · p. 10, Figure 6 · p. 11

5.7 Different Partitioning Algorithms

The partitioning algorithms yield similar classification performance, while ParHIP and mt-metis outperform KaFFPa on link prediction. COSINE selects mt-metis for its speed and competitive performance.

5.7 Different Partitioning Algorithms

  • Three partitioners have similar classification performance, while ParHIP and mt-metis outperform KaFFPa on link prediction.The comparison uses COSINE-LINE2nd on Youtube; the authors describe overall performance differences as tiny.Source: §5.7 · p. 11
  • Nearly 10%: Multi-threaded mt-metis takes nearly 10% of KaFFPa’s time to partition the tested networks.ParHIP and KaFFPa times are close; ParHIP is faster on Youtube and Flickr, while KaFFPa is faster on Yelp.Source: §5.7 · p. 11
  • mt-metis is selected for COSINE because it takes less time and gives competitive performance.The experiments use eight threads for mt-metis; ParHIP’s large partition count increases inter-process communication, and single-process execution was fastest for it.Source: §5.7 · p. 11

5.8 Parameter Sensitivity

COSINE’s group-mapping parameters trade local-structure information and effective sharing against noise and redundancy. The experiments use five walks of length and five groups per node, while mapping time scales linearly with walks per vertex.

5.8 Parameter Sensitivity

  • Above 60 walks per vertex, classification gains slow; the experiments use γ = 100 for time efficiency.More neighborhood samples improve performance by helping build more suitable node group sets; mapping time grows linearly with γ, and 100 walks per node takes 55 seconds for one million nodes using eight threads.Source: §5.8 · p. 12
  • Walk length k = 5 performs best: shorter walks miss high-order proximity, while longer walks add unrelated nodes and noise.The comparison varies walk length and node group-set size while keeping memory usage the same.Source: §5.8 · p. 12
  • The experiments set n = 5 and k = 5 for effectiveness and efficiency; smaller per-node n cannot ensure effective parameter sharing, while larger values cause redundancy from repeated elements in neighboring groups.Source: §5.8 · p. 12

6 CONCLUSION AND FUTURE WORK

COSINE uses graph partitioning to share embedding parameters, reducing embedding-lookup redundancy while improving embedding quality and reducing runtime. Future work targets more efficient partitioning and adapting the group-mapping algorithm for heterogeneous information networks.

6 CONCLUSION AND FUTURE WORK

  • COSINE uses graph partitioning for parameter sharing, reducing embedding-lookup redundancy while improving embedding quality and reducing running time.The approach aims to learn high-quality large-scale embeddings with limited memory and use training samples to accelerate learning.Source: §6 · p. 12
  • The three tested partitioning algorithms provide competitive results against uncompressed methods, motivating work on more efficient parameter-sharing partitioning.Source: §6 · p. 12
  • Extending COSINE to heterogeneous information networks will require adjusting group mapping to incorporate heterogeneous information comprehensively.Source: §6 · p. 12
Loading 1812.08972v1…