=Paper=
{{Paper
|id=Vol-3828/ISWC2024_paper_1
|storemode=property
|title=Compressing Multi-Modal Temporal Knowledge Graphs of Videos
|pdfUrl=https://ceur-ws.org/Vol-3828/paper1.pdf
|volume=Vol-3828
|authors=Shusaku Egami,Takanori Ugai,Ken Fukuda
|dblpUrl=https://dblp.org/rec/conf/semweb/EgamiUF24
}}
==Compressing Multi-Modal Temporal Knowledge Graphs of Videos==
https://ceur-ws.org/Vol-3828/paper1.pdf
Compressing Multi-Modal Temporal Knowledge
Graphs of Videos
Shusaku Egami1 , Takanori Ugai2,1 and Ken Fukuda1,*
1
National Institute of Advanced Industrial Science and Technology (AIST), Tokyo, Japan
2
Fujitsu Limited, Kanagawa, Japan
Abstract
The construction of multi-modal temporal knowledge graphs (MMTKGs) that ground non-symbolic and
time-series data, such as videos, into entities in the graph is still in the early stages. Hence, there is a lack
of discussion about compressing and publishing MMTKG with huge data size. In this paper, we propose
compression methods for MMTKGs of videos based on splitting images and inference rules and conduct
experiments to evaluate their performance. As a result, our methods reduced the size of the MMTKGs by
27.7-36.1%. This study contributes to reducing the cost of distributing large MMTKGs on the web.
Keywords
Multi-Modal Knowledge Graph, RDF Compression, Video Dataset, Temporal Knowledge Graph
1. Introduction
Multi-modal knowledge graphs (MMKGs) [1, 2], which ground non-symbolic data into symbolic
entities, have attracted attention as datasets for semantic and conceptual processing across
modalities. However, constructing and publishing multi-modal temporal knowledge graphs
(MMTKG) that ground multi-modal and time-series data, such as videos, into entities in the
graph is still in the early stages.
Typical MMKGs describe multi-modal contents by URLs or file paths. This approach may not
be suitable for the permanent publication of MMKGs as the multi-modal contents may become
inaccessible due to broken links. This issue could potentially be resolved by encoding the fileβs
binary data as an entity in the KG [3, 4]. However, building an MMTKG that describes the
content of a video in fine-grained time intervals, such as in seconds or video frames, would
result in huge data size, making it expensive to publish and share.
We proposed methods compressing MMTKGs of videos and conducted experiments to deter-
mine their effectiveness. We focused on two types of MMTKGs: KGs with video frame images
encoded in Base64 and KGs with entire video files encoded in Base64. The proposed methods
include differential compression based on knowledge representation of splitting video frame
images and reduction of redundant triples based on inference rules. The results demonstrated
that our compression methods reduced the size of the MMTKGs by 27.7-36.1%. This study
contributes to reducing the cost of distributing large MMTKGs on the web.
Posters, Demos, and Industry Tracks at ISWC 2024, November 13-15, 2024, Baltimore, USA
*
Corresponding author.
$ s-egami@aist.go.jp (S. Egami); ugai@fujitsu.com (T. Ugai); ken.fukuda@aist.go.jp (K. Fukuda)
Β© 2024 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Figure 1: Overview of multi-modal temporal knowledge graph compression
2. Related Work
Zhu et al. [1] and Chen et al. [2] comprehensively surveyed and summarized works on MMKGs.
Typical multimodal knowledge graphs are MMpedia [5] and IMGpedia [6], which ground images
to entities in the graph. VisionKG [7] is an MMKG containing bounding boxes (bboxes) of
objects extracted from various image datasets such as MS-COCO [8], CIFAR [9], and PASCAL
VOC [10]. These MMKGs represent images by URIs or file paths. Studies on video KGs have
evolved in the context of video indexing and retrieval [11, 12, 13]. VEKG [14] is an MMKG
based on the extracted events from videos, bboxes, and image features. However, the data is
not publicly available. There have been a lot of studies of compression methods for KGs [15].
However, MMKGs for videos are not covered.
3. Approach
MMKGs usually describe images and videos by URIs or file paths, which causes broken links to
multi-modal files. Thus, we focus on permanently accessible MMTKGs that embed multi-modal
files in a KG as an entity, and propose compression methods for these MMTKGs.
3.1. Data preparation
As an example, we constructed MMTKGs of indoor daily activities from multi-modal data of
videos, text, and JSON output by VirtualHome-AIST1 [16], as shown in the upper left of Figure 1.
The multi-modal data was output every five frames. The dataset contains over 3,500 videos,
which include both fixed camera views and third-person views of the camera moving. The
average video length is 64.2 seconds, with a maximum of 268.9 seconds and a minimum of
12.5 seconds. We prepared two types of MMTKGs: a KG with every five video frame images
encoded in Base64 described as literal values (i.e., image-embedded MMTKG), and a KG with
videos encoded in Base64 described as literal values (i.e., video-embedded MMTKG). We reused
the Multimedia Semantic Sensor Network (MSSN) ontology [17] and VirtualHome2KG [18]
ontology for schema design.
3.2. MMTKG compression
3.2.1. Compressing image-embedded MMTKG
If the MMTKG contains video frame image data, each video frame image is first compressed as
a JPEG. Next, each image is split into a grid. The grid image is encoded in Base64 and described
in the knowledge representation as shown in the upper right of Figure 1. Here, if there is no
difference between the grid image of the current frame and the grid image at the same position
in the previous frame, the entity and the literal value of the current grid image are not created,
and those of the previous frame are reused.
3.2.2. Compressing video-embedded MMTKG
We adopted MPEG-4 [19] to reduce the video data size. Each video frame entity has a frame
number instead of having a Base64 value, and the video entity has a Base64 value for the com-
pressed video. It is possible to extract arbitrary frame images from the video using FFmpeg [20].
The MMTKG size can be further reduced, but long videos take a longer time to decompress.
3.2.3. Removing redundant triples using inference rules
The MMTKGs have redundant triples if the 2D bboxes are not changed. We reduced the number
of entities and triples by referring to the previous entities if the current 2D bboxes have not
changed since the previous frame.
Moreover, inspired by the approach of removing triples that can be inferred from the
rules [21], we create only the relation equivalentFrame(πππ , πππ ) between previous frame entity
πππ and current frame entity πππ when all 2D bboxes are not changed from the previous frame.
We defined the rule as follows: hasMediaDescriptor(πππ , πππππ₯ ) β§ equivalentFrame(πππ , πππ )
β hasMediaDescriptor(πππ , πππππ₯ ). Similarly, for grid images, we removed triples that
β
can be inferred from the following rule: image(πππ , ππππππ ) β§ equivalentImage(πππ , πππ ) β β
image(πππ , ππππππ ). Note that the image property here refers to a split image.
1
https://github.com/aistairc/virtualhome_aist
Table 1 Table 2
Image-embedded MMTKG Video-embedded MMTKG
MMTKG # of triples Size [GB] MMTKG # of triples Size [GB]
raw 134,945,485 62.0 raw 131,786,665 17.3
3Γ3 grid 64,242,296 41.8 (-32.5%) w/o redundant triples 37,646,681 12.5 (-27.7%)
4Γ4 grid 78,384,156 39.6 (-36.1%) w/o redundant triples
36,284,402 12.4 (-28.3%)
5Γ5 grid 96,401,621 39.9 (-35.6%) and triples can be inferred
4. Result
Tables 1 and 2 show the results of the compression experiments. Our methods achieved data
size reductions of 36.1% for image-embedded MMTKG and 28.3% for video-embedded MMTKG.
There is a trade-off between the number of grid divisions and the number of triples. The best
strategy is 4 Γ 4. In this study, we experimented with π Γ π grid divisions; however, experiments
with πΓπ grid divisions are also necessary for a more detailed analysis. We published MMTKGs
in a permanently accessible format.2 In addition, tools for decoding and extracting images and
videos from compressed MMTKG are available.3
5. Discussion
We proposed compression methods for two types of MMTKGs: image-embedded and video-
embedded MMTKGs. The former MMTKGs can display arbitrary images on the web using HTML
![]()
tags without decoding the videos. The latter MMTKGs can apply video compression
methods, and if the video is decoded, any frame can be extracted based on the frame number of
the image. These MMTKGs can help create benchmark datasets for vision-language models since
it is possible to extract arbitrary text and images using SPARQL queries [16]. The compression
method for image-embedded MMTKGs might be effective for image stream data in which no
video file is created. In contrast, the compression method for video-embedded MMTKGs is more
effective when video files are available. Our compression methods for MMTKGs are effective
for fixed-camera view videos but are less effective for first-person view videos.
6. Conclusion
We proposed compression methods for two types of permanently available MMTKGs in which
video data are directly embedded as literal values. As a result, our methods achieved data size
reductions of 36.1% for image-embedded MMTKG and 28.3% for video-embedded MMTKG. The
two MMTKG datasets and the tools are available on GitHub. In the future, we will consider
combining our methods with other RDF compression methods [22, 23].
Acknowledgments
This paper is based on results obtained from a project, JPNP20006, commissioned by the New
Energy and Industrial Technology Development Organization (NEDO), and JSPS KAKENHI
Grant Number JP22K18008 and JP23H03688.
2
https://github.com/aistairc/vhakg
3
https://github.com/aistairc/vhakg-tools
References
[1] X. Zhu, Z. Li, X. Wang, X. Jiang, P. Sun, X. Wang, Y. Xiao, N. J. Yuan, Multi-Modal Knowledge
Graph Construction and Application: A Survey, IEEE TRANSACTIONS ON KNOWLEDGE AND
DATA ENGINEERING 36 (2024).
[2] Z. Chen, Y. Zhang, Y. Fang, Y. Geng, L. Guo, X. Chen, Q. Li, W. Zhang, J. Chen, Y. Zhu, et al., Knowl-
edge graphs meet multi-modal learning: A comprehensive survey, arXiv preprint arXiv:2402.05391
(2024).
[3] X. Wilcke, P. Bloem, V. De Boer, The knowledge graph as the default data model for learning on
heterogeneous knowledge, Data Science 1 (2017) 39β57.
[4] P. Bloem, X. Wilcke, L. van Berkel, V. de Boer, kgbench: A collection of knowledge graph datasets
for evaluating relational and multimodal machine learning, in: R. Verborgh, K. Hose, H. Paulheim,
P.-A. Champin, M. Maleshkova, O. Corcho, P. Ristoski, M. Alam (Eds.), The Semantic Web, Springer
International Publishing, Cham, 2021, pp. 614β630.
[5] Y. Wu, X. Wu, J. Li, Y. Zhang, H. Wang, W. Du, Z. He, J. Liu, T. Ruan, MMpedia: A Large-Scale
Multi-modal Knowledge Graph, in: T. R. Payne, V. Presutti, G. Qi, M. Poveda-VillalΓ³n, G. Stoilos,
L. Hollink, Z. Kaoudi, G. Cheng, J. Li (Eds.), The Semantic Web β ISWC 2023, Springer Nature
Switzerland, Cham, 2023, pp. 18β37. doi:10.1007/978-3-031-47243-5_2.
[6] S. Ferrada, B. Bustos, A. Hogan, IMGpedia: A Linked Dataset with Content-Based Analysis of
Wikimedia Images, in: C. dβAmato, M. Fernandez, V. Tamma, F. Lecue, P. CudrΓ©-Mauroux, J. Sequeda,
C. Lange, J. Heflin (Eds.), The Semantic Web β ISWC 2017, Springer International Publishing, Cham,
2017, pp. 84β93. doi:10.1007/978-3-319-68204-4_8.
[7] J. Yuan, A. Le-Tuan, M. Nguyen-Duc, T.-K. Tran, M. Hauswirth, D. Le-Phuoc, VisionKG: Unleashing
the Power of Visual Datasets via Knowledge Graph, in: A. MeroΓ±o PeΓ±uela, A. Dimou, R. Troncy,
O. Hartig, M. Acosta, M. Alam, H. Paulheim, P. Lisena (Eds.), The Semantic Web, Springer Nature
Switzerland, Cham, 2024, pp. 75β93. doi:10.1007/978-3-031-60635-9_5.
[8] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. DollΓ‘r, C. L. Zitnick, Microsoft
COCO: Common Objects in Context, in: D. Fleet, T. Pajdla, B. Schiele, T. Tuytelaars (Eds.), Computer
Vision β ECCV 2014, Springer International Publishing, Cham, 2014, pp. 740β755. doi:10.1007/
978-3-319-10602-1_48.
[9] A. Krizhevsky, G. Hinton, et al., Learning multiple layers of features from tiny images (2009).
[10] M. Everingham, L. Van Gool, C. K. I. Williams, J. Winn, A. Zisserman, The Pascal Visual Object
Classes (VOC) Challenge, International Journal of Computer Vision 88 (2010) 303β338. doi:10.
1007/s11263-009-0275-4.
[11] L. F. Sikos, Rdf-powered semantic video annotation tools with concept mapping to linked data for
next-generation video indexing: a comprehensive review, Multimedia Tools and Applications 76
(2017) 14437β14460.
[12] K. Fukuda, J. Vizcarra, S. Nishimura, Massive semantic video annotation in high-end customer
service, in: F. F.-H. Nah, K. Siau (Eds.), HCI in Business, Government and Organizations, Springer
International Publishing, Cham, 2020, pp. 46β58.
[13] J. Vizcarra, S. Nishimura, K. Fukuda, Ontology-based human behavior indexing with multimodal
video data, in: 2021 IEEE 15th International Conference on Semantic Computing (ICSC), 2021, pp.
262β267. doi:10.1109/ICSC50631.2021.00052.
[14] P. Yadav, E. Curry, Vekg: Video event knowledge graph to represent video streams for complex
event pattern matching, in: 2019 First International Conference on Graph Computing (GC), 2019,
pp. 13β20. doi:10.1109/GC46384.2019.00011.
[15] M. Besta, T. Hoefler, Survey and taxonomy of lossless graph compression and space-efficient graph
representations, 2019. arXiv:1806.01799.
[16] S. Egami, T. Ugai, S. N. N. Htun, K. Fukuda, VHAKG: A multi-modal knowledge graph based on
synchronized multi-view videos of daily activities, in: Proceedings of the 33rd ACM International
Conference on Information and Knowledge Management, 2024. To appear.
[17] C. Angsuchotmetee, R. Chbeir, Y. Cardinale, MSSN-Onto: An ontology-based approach for flexible
event processing in Multimedia Sensor Networks, Future Generation Computer Systems 108 (2020)
1140β1158. doi:10.1016/j.future.2018.01.044.
[18] S. Egami, T. Ugai, M. Oono, K. Kitamura, K. Fukuda, Synthesizing Event-Centric Knowledge Graphs
of Daily Activities Using Virtual Space, IEEE Access 11 (2023) 23857β23873. doi:10.1109/ACCESS.
2023.3253807.
[19] T. Ebrahimi, C. Horne, Mpeg-4 natural video coding β an overview, Signal Processing: Image Com-
munication 15 (2000) 365β385. doi:https://doi.org/10.1016/S0923-5965(99)00054-5.
[20] FFmpeg Team, FFmpeg, 2000. URL: https://ffmpeg.org/, accessed: 2024-05-27.
[21] A. K. Joshi, P. Hitzler, G. Dong, Logical linked data compression, in: P. Cimiano, O. Corcho,
V. Presutti, L. Hollink, S. Rudolph (Eds.), The Semantic Web: Semantics and Big Data, Springer
Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 170β184.
[22] J. D. FernΓ‘ndez, M. A. MartΓnez-Prieto, C. Gutierrez, Compact representation of large rdf data sets
for publishing and exchange, in: P. F. Patel-Schneider, Y. Pan, P. Hitzler, P. Mika, L. Zhang, J. Z. Pan,
I. Horrocks, B. Glimm (Eds.), The Semantic Web β ISWC 2010, Springer Berlin Heidelberg, Berlin,
Heidelberg, 2010, pp. 193β208.
[23] N. FernΓ‘ndez, J. Arias, L. SΓ‘nchez, D. Fuentes-Lorenzo, Γ. Corcho, Rdsz: An approach for lossless
rdf stream compression, in: V. Presutti, C. dβAmato, F. Gandon, M. dβAquin, S. Staab, A. Tordai
(Eds.), The Semantic Web: Trends and Challenges, Springer International Publishing, Cham, 2014,
pp. 52β67.