More Like this

1. The Dual Graph Shift Operator: Identifying the Support of the Frequency Domain

   https://doi.org/10.1007/s00041-021-09850-1  

   Leus, Geert; Segarra, Santiago; Ribeiro, Alejandro; Marques, Antonio G. (June 2021, Journal of Fourier Analysis and Applications)

   null (Ed.)

   Abstract Contemporary data is often supported by an irregular structure, which can be conveniently captured by a graph. Accounting for this graph support is crucial to analyze the data, leading to an area known as graph signal processing (GSP). The two most important tools in GSP are the graph shift operator (GSO), which is a sparse matrix accounting for the topology of the graph, and the graph Fourier transform (GFT), which maps graph signals into a frequency domain spanned by a number of graph-related Fourier-like basis vectors. This alternative representation of a graph signal is denominated the graph frequency signal. Several attempts have been undertaken in order to interpret the support of this graph frequency signal, but they all resulted in a one-dimensional interpretation. However, if the support of the original signal is captured by a graph, why would the graph frequency signal have a simple one-dimensional support? Departing from existing work, we propose an irregular support for the graph frequency signal, which we coin dual graph. A dual GSO leads to a better interpretation of the graph frequency signal and its domain, helps to understand how the different graph frequencies are related and clustered, enables the development of better graph filters and filter banks, and facilitates the generalization of classical SP results to the graph domain. 

   more » « less
2. Data Augmentation for Deep Graph Learning: A Survey

   https://doi.org/10.1145/3575637.3575646  

   Ding, Kaize; Xu, Zhe; Tong, Hanghang; Liu, Huan (November 2022, ACM SIGKDD Explorations Newsletter)

   Graph neural networks, a powerful deep learning tool to model graph-structured data, have demonstrated remarkable performance on numerous graph learning tasks. To address the data noise and data scarcity issues in deep graph learning, the research on graph data augmentation has intensified lately. However, conventional data augmentation methods can hardly handle graph-structured data which is defined in non-Euclidean space with multi-modality. In this survey, we formally formulate the problem of graph data augmentation and further review the representative techniques and their applications in different deep graph learning problems. Specifically, we first propose a taxonomy for graph data augmentation techniques and then provide a structured review by categorizing the related work based on the augmented information modalities. Moreover, we summarize the applications of graph data augmentation in two representative problems in data-centric deep graph learning: (1) reliable graph learning which focuses on enhancing the utility of input graph as well as the model capacity via graph data augmentation; and (2) low-resource graph learning which targets on enlarging the labeled training data scale through graph data augmentation. For each problem, we also provide a hierarchical problem taxonomy and review the existing literature related to graph data augmentation. Finally, we point out promising research directions and the challenges in future research. 

   more » « less
3. BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers

   https://doi.org/10.14778/3665844.3665859  

   Wheatman, Brian; Dong, Xiaojun; Shen, Zheqi; Dhulipala, Laxman; Łącki, Jakub; Pandey, Prashant; Xu, Helen (May 2024, Proceedings of the VLDB Endowment)

   A fundamental building block in any graph algorithm is agraph container -- a data structure used to represent the graph. Ideally, a graph container enables efficient access to the underlying graph, has low space usage, and supports updating the graph efficiently. In this paper, we conduct an extensive empirical evaluation of graph containers designed to support running algorithms on large graphs. To our knowledge, this is the firstapples-to-applescomparison of graph containers rather than overall systems, which include confounding factors such as differences in algorithm implementations and infrastructure. We measure the running time of 10 highly-optimized algorithms across over 20 different containers and 10 graphs. Somewhat surprisingly, we find that the average algorithm running time does not differ much across containers, especially those that support dynamic updates. Specifically, a simple container based on an off-the-shelf B-tree is only 1.22× slower on average than a highly optimized static one. Moreover, we observe that simplifying a graph-container Application Programming Interface (API) to only a few simple functions incurs a mere 1.16× slowdown compared to a complete API. Finally, we also measure batch-insert throughput in dynamic-graph containers for a full picture of their performance. To perform the benchmarks, we introduce BYO, a unified framework that standardizes evaluations of graph-algorithm performance across different graph containers. BYO extends the Graph Based Benchmark Suite (Dhulipala et al. 18), a state-of-the-art graph algorithm benchmark, to easily plug into different dynamic graph containers and enable fair comparisons between them on a large suite of graph algorithms. While several graph algorithm benchmarks have been developed to date, to the best of our knowledge, BYO is the first system designed to benchmark graph containers. 

   more » « less
4. ENERGY COMPACTION FILTERS ON GRAPHS

   https://doi.org/10.1109/GlobalSIP.2018.8646570  

   Teke, Oguzhan; Vaidyanathan, P. P. (November 2018, IEEE Global Conference on Signal and Information Processing)

   In classical signal processing spectral concentration is an important problem that was first formulated and analyzed by Slepian. The solution to this problem gives the optimal FIR filter that can confine the largest amount of energy in a specific bandwidth for a given filter order. The solution is also known as the prolate sequence. This study investigates the same problem for polynomial graph filters. The problem is formulated in both graph-free and graph-dependent fashions. The graph-free formulation assumes a continuous graph spectrum, in which case it becomes the polynomial concentration problem. This formulation has a universal approach that provides a theoretical reference point. However, in reality graphs have discrete spectrum. The graph-dependent formulation assumes that the eigenvalues of the graph are known and formulates the energy compaction problem accordingly. When the eigenvalues of the graph have a uniform distribution, the graph-dependent formulation is shown to be asymptotically equivalent to the graph-free formulation. However, in reality eigenvalues of a graph tend to have different densities across the spectrum. Thus, the optimal filter depends on the underlying graph operator, and a filter cannot be universally optimal for every graph. 

   more » « less
5. Joint 3D Human Shape Recovery and Pose Estimation from a Single Image with Bilayer Graph

   https://doi.org/10.1109/3DV53792.2021.00060  

   Yu, Xin; van Baar, Jeroen; Chen, Siheng (December 2021, 2021 International Conference on 3D Vision (3DV))

   The ability to estimate the 3D human shape and pose from images can be useful in many contexts. Recent approaches have explored using graph convolutional networks and achieved promising results. The fact that the 3D shape is represented by a mesh, an undirected graph, makes graph convolutional networks a natural fit for this problem. However, graph convolutional networks have limited representation power Information from nodes in the graph is passed to connected neighbors, and propagation of information requires successive graph convolutions. To overcome this limitation, we propose a dual-scale graph approach. We use a coarse graph, derived from a dense graph, to estimate the human’s 3D pose, and the dense graph to estimate the 3D shape. Information in coarse graphs can be propagated over longer distances compared to dense graphs. In addition, information about pose can guide to recover local shape detail and vice versa. We recognize that the connection between coarse and dense is itself a graph, and introduce graph fusion blocks to exchange information between graphs with different scales. We train our model end-to-end and show that we can achieve state-of-the-art results for several evaluation datasets. The code is available at the following link, https://github.com/yuxwind/BiGraphBody. 

   more » « less