14 papers · ranked by Valyu relevance
Martin Rektoris, Milan Papež, Václav Šmídl, Tomáš Pevný
Deep generative models (DGMs) for graphs achieve impressively high expressive power thanks to very efficient and scalable neural networks. However, these networks contain non-linearities that prevent analytical computation of many standard probabilistic inference queries, i.e., these DGMs are considered intractable.…
Anton Tsitsulin, Bryan Perozzi
In this work, we introduce the Graph Lottery Ticket (GLT) Hypothesis – that there is an extremely sparse backbone for every graph, and that graph learning algorithms attain comparable performance when trained on that subgraph as on the full graph. We identify and systematically study 8 key metrics of interest that…
Sevvandi Kandanaarachchi, Cheng Soon Ong
Social networks have a small number of large hubs, and a large number of small dense communities. We propose a generative model that captures both hub and dense structures. Based on recent results about graphons on line graphs, our model is a graphon mixture, enabling us to generate sequences of graphs where each graph…
Swati Goswami, Asit Kumar Das, Subhas C. Nandy
A majority of real-life networks are weighted and sparse. The present article aims at characterization of weighted networks based on sparsity, as an indicator of inherent diversity of different network parameters. The measure called sparsity index defined on ordered degree sequence of simple networks is extended and…
Sevvandi Kandanaarachchi, Cheng Soon Ong
We consider the problem of estimating graph limits, known as graphons, from observations of sequences of sparse finite graphs. In this paper we show a simple method that can shed light on a subset of sparse graphs. The method involves mapping the original graphs to their line graphs. We show that graphs satisfying a…
Saikat Chatterjee, Magnus Jansson, Martin Sundin, Arun Venkitaraman
—Graphs are naturally sparse objects that are used to study many problems involving networks, for example, distributed learning and graph signal processing. In some cases, the graph is not given, but must be learned from the problem and available data. Often it is desirable to learn sparse graphs. However, making a…
Guibin Zhang, Yanwei Yue, Kun Wang, Junfeng Fang + 6 more
Semantic and Topological Awareness Authors: ['Guibin Zhang' 'Yanwei Yue' 'Kun Wang' 'Junfeng Fang' 'Yongduo Sui' 'Kai Wang' 'Yuxuan Liang' 'Dawei Cheng' 'Shirui Pan' 'Tianlong Chen'] Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs.…
Xihan Qin, Cencheng Shen
| Abstract: | Graph is a ubiquitous representation of data in various research fields, and graph embedding is a | | --- | --- | | | prevalent machine learning technique for capturing key features and generating fixed-sized attributes. | | | However, most state-of-the-art graph embedding methods are computationally and…
Ryan Wickman, Xiaofei Zhang, Weizi Li
—The interconnectedness and interdependence of modern graphs are growing ever more complex, causing enormous resources for processing, storage, communication, and decision-making of these graphs. In this work, we focus on the task graph sparsification: an edge-reduced graph of a similar structure to the original graph…
Gal Morgenstern, Tirza Routtenberg
—This paper investigates the recovery of a nodedomain sparse graph signal from the output of a graph filter. This problem, which is often referred to as the identification of the source of a diffused sparse graph signal, is seminal in the field of graph signal processing (GSP). Sparse graph signals can be used in the…
Swati Goswami, C. A. Murthy, Asit Kumar Das
This article examines the application of a popular measure of sparsity, Gini Index, on network graphs. A wide variety of network graphs happen to be sparse. But the index with which sparsity is commonly measured in network graphs is edge density, reflecting the proportion of the sum of the degrees of all nodes in the…
Peter Eades, Quan Nguyen, Seok-Hee Hong
Spectral sparsification is a general technique developed by Spielman et al. to reduce the number of edges in a graph while retaining its structural properties. We investigate the use of spectral sparsification to produce good visual representations of big graphs. We evaluate spectral sparsification approaches on…
Aristides Gionis, Polina Rozenshtein, Nikolaj Tatti, Evimaria Terzi
In this paper, we consider a novel formulation of the network-sparsification problem. In addition to the network, we also consider as input a set of communities. The goal is to sparsify the network so as to preserve the network structure with respect to the given communities. We introduce two variants of the…
Ariful Azad, Aydın Buluç
—We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including…