Edge Sampling of Graphs: Graph Signal Processing Approach With Edge Smoothness
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929420200050688 |
|---|---|
| author | Yanagiya, Kenta Yamada, Koki Katsuhara, Yasuo Takatani, Tomoya Tanaka, Yuichi |
| author_facet | Yanagiya, Kenta Yamada, Koki Katsuhara, Yasuo Takatani, Tomoya Tanaka, Yuichi |
| contents | Finding important edges in a graph is a crucial problem for various research fields, such as network epidemics, signal processing, machine learning, and sensor networks. In this paper, we tackle the problem based on sampling theory on graphs. We convert the original graph to a line graph where its nodes and edges, respectively, represent the original edges and the connections between the edges. We then perform node sampling of the line graph based on the edge smoothness assumption: This process selects the most critical edges in the original graph. We present a general framework of edge sampling based on graph sampling theory and reveal a theoretical relationship between the degree of the original graph and the line graph. We also propose an acceleration method for edge sampling in the proposed framework by using the relationship between two types of Laplacian of the node and edge domains. Experimental results in synthetic and real-world graphs validate the effectiveness of our approach against some alternative edge selection methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10149 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge Sampling of Graphs: Graph Signal Processing Approach With Edge Smoothness Yanagiya, Kenta Yamada, Koki Katsuhara, Yasuo Takatani, Tomoya Tanaka, Yuichi Signal Processing Finding important edges in a graph is a crucial problem for various research fields, such as network epidemics, signal processing, machine learning, and sensor networks. In this paper, we tackle the problem based on sampling theory on graphs. We convert the original graph to a line graph where its nodes and edges, respectively, represent the original edges and the connections between the edges. We then perform node sampling of the line graph based on the edge smoothness assumption: This process selects the most critical edges in the original graph. We present a general framework of edge sampling based on graph sampling theory and reveal a theoretical relationship between the degree of the original graph and the line graph. We also propose an acceleration method for edge sampling in the proposed framework by using the relationship between two types of Laplacian of the node and edge domains. Experimental results in synthetic and real-world graphs validate the effectiveness of our approach against some alternative edge selection methods. |
| title | Edge Sampling of Graphs: Graph Signal Processing Approach With Edge Smoothness |
| topic | Signal Processing |
| url | https://arxiv.org/abs/2407.10149 |