PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Topological Representation for Networks via Hierarchical Sampling

Guoji Fu, Chengbin Hou, Xin Yao

arXiv:1902.06684v1cs.SIcs.LGstat.ML

TL;DR

Many network representation methods preserve local topology but fail to capture global structure, limiting their representation of relationships across communities. HSRL recursively compresses networks using community awareness, learns embeddings at each level, and concatenates them. The paper reports statistically significant link-prediction improvements over DeepWalk, node2vec, LINE, and HARP on five real-world datasets.

  • Problem

    Many existing network representation learning methods preserve local topology but fail to capture global topological information.

    Source: §I · p. 1

  • Method

    HSRL recursively compresses a network with a community-aware strategy, learns embeddings for each compressed network using an existing NRL method, and concatenates the embeddings.

    Source: §I · p. 2, B. Representation Learning · p. 4

  • Results

    HSRL statistically significantly outperforms DeepWalk, node2vec, LINE, and HARP on link prediction across five real-world datasets.

    Source: §I · p. 2

  • Takeaways & Limitations

    HSRL embeddings are reported to encode local and global topology, and HSRL improves link-prediction performance over the named baselines on the evaluated datasets.

    Source: §I · p. 2

Abstract

from arXiv · show

The topological information is essential for studying the relationship between nodes in a network. Recently, Network Representation Learning (NRL), which projects a network into a low-dimensional vector space, has been shown their advantages in analyzing large-scale networks. However, most existing NRL methods are designed to preserve the local topology of a network, they fail to capture the global topology. To tackle this issue, we propose a new NRL framework, named HSRL, to help existing NRL methods capture both the local and global topological information of a network. Specifically, HSRL recursively compresses an input network into a series of smaller networks using a community-awareness compressing strategy. Then, an existing NRL method is used to learn node embeddings for each compressed network. Finally, the node embeddings of the input network are obtained by concatenating the node embeddings from all compressed networks. Empirical studies for link prediction on five real-world datasets demonstrate the advantages of HSRL over state-of-the-art methods.

I. INTRODUCTION

Network representation learning scales analysis by mapping nodes to low-dimensional vectors, but many methods preserve local topology while missing global relationships. HSRL recursively compresses networks with community awareness, learns embeddings at each level, and concatenates them; the paper reports significant link-prediction gains over four baselines on five datasets.

  • The paper frames local topology as useful for identifying strongly connected neighborhoods and global topology as useful for relationships between communities.Source: §I · p. 1
  • Existing NRL methods such as DeepWalk, node2vec, and LINE capture local relationships but fail to represent global topology.The paper notes that their approaches focus on nearby nodes, with LINE measuring relationships at most two hops away.Source: §I · p. 1
  • HSRL recursively compresses the input network using community awareness, learns embeddings for each compressed network, and concatenates them for the original nodes.Source: §I · p. 2
  • The authors mathematically show that HSRL embeddings explicitly encode local and global topological information.Source: §I · p. 2
  • HSRL statistically significantly outperforms DeepWalk, node2vec, LINE, and HARP on link prediction across five real-world datasets.Source: §I · p. 2

II. RELATED WORK

Related work contrasts scalable methods that capture local proximity with hierarchical compression intended to represent global structure. The preliminary section defines the network and modularity concepts and formulates hierarchical sampling and representation learning through level-wise compression and concatenated embeddings.

II. RELATED WORK

  • DeepWalk, node2vec, and LINE scale to large networks but focus on local neighborhoods or proximities no more than two hops away.Source: §II · p. 2
  • HARP recursively compresses networks with edge and star collapsing, but may merge nodes from different communities and may initialize learning in a bad local minimum.The paper says link prediction needs both local and global topology, including shared neighborhoods and communities.Source: §II · p. 2

III. PRELIMINARY AND PROBLEM DEFINITION

  • A network is defined as nodes V and edges E, with weighted edges and symmetry conditions specified for undirected and directed networks.Source: §III · p. 2
  • Modularity compares within-community edge density with between-community edge density; higher modularity corresponds to denser within-community and sparser between-community connections.Source: §III · pp. 2–3
  • Hierarchical sampling yields compressed networks G0 through GK that represent global topology at different levels.Source: §III · p. 3
  • Hierarchical network representation learning applies an NRL mapping to each compressed network and concatenates the resulting embeddings into the original network's node embeddings.Source: §III · p. 3

IV. HSRL

HSRL combines community-aware hierarchical compression with representation learning at each level to preserve hierarchical topology in low-dimensional node embeddings.

  • HSRL has two parts: hierarchical sampling discovers hierarchical topology through community-aware compression, and representation learning learns low-dimensional embeddings that preserve it.Source: §IV · p. 3
  • Hierarchical sampling compresses a network into multiple networks, while representation learning operates on those compressed levels.Source: §IV · p. 3
  • The framework's stated aim is to preserve hierarchical topological information in low-dimensional node embeddings.Source: §IV · p. 3

A. Hierarchical Sampling

Hierarchical sampling compresses a network by detecting communities and aggregating each community into a node, repeating the process to represent global topology at successive levels.

A. Hierarchical Sampling

  • Communities at different natural organization levels, including communities divided into sub-communities, provide the successive levels used in compression.Source: A. Hierarchical Sampling · p. 3
  • At each level, modularity optimization merges connected nodes into a community when the merge improves modularity, repeating until a local maximum is reached.Source: A. Hierarchical Sampling · p. 3
  • Node aggregation creates a new network whose nodes represent the detected communities and whose edge weights sum connections between the corresponding communities.Source: A. Hierarchical Sampling · p. 3
  • Repeating modularity optimization and node aggregation produces compressed networks that reveal the input network's hierarchical global topology.Source: A. Hierarchical Sampling · p. 3

B. Representation Learning

HSRL learns embeddings on each compressed network and concatenates hierarchical-community embeddings to represent each original node. The paper states that this construction preserves local and hierarchical global topology.

B. Representation Learning

  • A node’s embedding is the concatenation of embeddings for the hierarchical communities it belongs to, learned on compressed networks.The paper says any NRL method can be used to learn embeddings on each compressed network.Source: B. Representation Learning · p. 4
  • Nodes in the same hierarchical communities receive similar embeddings, with similarity increasing as they share more communities.The paper links this property to preserving relationships between densely connected nodes and local topology.Source: B. Representation Learning · p. 4
  • Embedding cosine similarity is proportional to the summed similarities of the nodes’ hierarchical-community embeddings.Consequently, nodes in similar hierarchical communities can have similar embeddings regardless of their distance in the original network.Source: B. Representation Learning · pp. 4–5

V. EXPERIMENTS

The experiments evaluate HSRL on the link prediction task using five real-world datasets.

V. EXPERIMENTS

  • HSRL is evaluated on the link prediction task using five real-world datasets.The paper states that source code is available at its GitHub repository.Source: §V · p. 5
  • The authors report that the source code is available at the HSRL GitHub repository.The passage provides the repository URL: https://github.com/fuguoji/HSRL.Source: §V · p. 5

A. Datasets

The evaluation uses five real-world datasets spanning user-interest, friendship, bibliographic, and user-business networks.

A. Datasets

  • The five evaluation datasets are Movielens, MIT, DBLP, Douban, and Yelp.The paper says these datasets are commonly used in network representation learning.Source: A. Datasets · p. 5
  • DBLP is a computer-science bibliographic network spanning database, data mining, machine learning, and information retrieval.Its nodes include authors, papers, venues, and terms.Source: A. Datasets · p. 5
  • Movielens and Douban are user-movie interest networks, while MIT is a Facebook friendship network from 100 American colleges and universities at one point in time.Movielens has users, movies, and terms; Douban has users, movies, actors, and directors; MIT contains users.Source: A. Datasets · p. 5
  • Yelp is an American user-business network whose nodes include users, businesses, locations, and business categories.Source: A. Datasets · p. 5

B. Baselines

The baselines include three single-network representation learners and HARP, which recursively compresses networks and uses embeddings from one level to initialize the next. Parameter settings are reported for DeepWalk-, node2vec-, and LINE-based variants.

B. Baselines

  • DeepWalk samples node sequences with random walks and learns embeddings by treating sequences as sentences and nodes as words.Source: B. Baselines · p. 5
  • DeepWalk, node2vec, and LINE are compared alongside HARP; HARP recursively compresses networks and initializes each level’s embeddings from the previous level.DeepWalk uses random walks and Skip-Gram; node2vec uses biased walks trading off DFS and BFS; LINE preserves first- and second-order proximities.Source: B. Baselines · p. 5

C. Parameter Settings

  • DeepWalk-, node2vec-, and LINE-based HSRL and HARP variants use representation size d = 64 and learning rate η = 0.025.The largest HSRL compression level K is 3 for each variant; DeepWalk and node2vec variants also use t = 10, l = 40, and w = 5, while LINE variants use λ = 5.Source: C. Parameter Settings · p. 5

D. Hierarchical Sampling for Networks

Hierarchical sampling compresses networks while retaining community and hierarchical structure. In link prediction, HSRL outperforms baselines across the tested datasets.

D. Hierarchical Sampling for Networks

E. Link Prediction

  • HSRL significantly outperforms all baselines on all datasets; on Douban, HSRL(DW), HSRL(N2V), and HSRL(LINE) improve over baselines by 18.4%, 30.5%, and 17.5%, respectively.The link-prediction results are reported as AUC.Source: E. Link Prediction · p. 6, Table II · p. 6
  • On the small, dense MIT network, HARP works better than DeepWalk and node2vec, but its results are worse than original NRL methods on four other datasets.The paper attributes HARP's weakness to compressed networks that may not reveal global topology and may mislead embedding initialization, especially for large networks and highly non-convex objectives such as LINE.Source: E. Link Prediction · p. 6
  • HSRL improvements are larger on DBLP, Yelp, and Douban than on Movielens and MIT, indicating stronger gains on large-scale networks.Source: E. Link Prediction · p. 6

F. Parameter Sensitivity Analysis

On DBLP link prediction, increasing embedding dimension and compression depth improves AUC until performance stabilizes beyond d=32 and K=3.

F. Parameter Sensitivity Analysis

  • With K fixed at 3, link-prediction AUC rises as embedding dimension d increases, then stabilizes when d exceeds 32.The paper states that small d is inadequate to embody rich network information, while further increases do not improve performance once d is large enough.Source: F. Parameter Sensitivity Analysis · p. 6
  • With d fixed at 64, AUC improves as compression depth K increases, then stabilizes when K exceeds 3.The paper links the plateau to DBLP no longer being compressible after level 3.Source: F. Parameter Sensitivity Analysis · pp. 6–7

G. Running Time

HSRL’s running time is at most three times that of other NRL methods and grows linearly with the corresponding baselines; the conclusions report that it significantly outperforms state-of-the-art algorithms on link prediction.

G. Running Time

  • HSRL’s actual running time is at most three times that of other NRL methods and grows linearly with the corresponding baselines as input networks grow.The experiments used a single machine with 32GB memory and 16 CPU cores at 3.2 GHZ.Source: Figure 7 · p. 7, G. Running Time · p. 7
  • Parallelizing training across compressed networks can reduce HSRL’s running time.Source: G. Running Time · p. 7

VI. CONCLUSIONS

  • HSRL combines community-awareness compression with embeddings learned at each compressed level, concatenating them to represent the original network.The conclusions report that HSRL significantly outperforms state-of-the-art algorithms on link prediction across various real-world networks.Source: §VI · p. 8
  • Future work includes combining HSRL with deep learning-based methods and extending it to heterogeneous, attributed, and dynamic networks.Source: §VI · p. 8

Related papers

Loading 1902.06684v1…