{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:03:01Z","timestamp":1760058181799,"version":"build-2065373602"},"reference-count":57,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T00:00:00Z","timestamp":1741910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Spanish government","award":["PID2022-142516OB-I00"],"award-info":[{"award-number":["PID2022-142516OB-I00"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we define and characterize the embedding of edges and higher-order entities in directed graphs (digraphs) and relate these embeddings to those of nodes. Our edge-centric approach consists of the following: (a) Embedding line digraphs (or their iterated versions); (b) Exploiting the rank properties of these embeddings to show that edge\/path similarity can be posed as a linear combination of node similarities; (c) Solving scalability issues through digraph sparsification; (d) Evaluating the performance of these embeddings for classification and clustering. We commence by identifying the motive behind the need for edge-centric approaches. Then we proceed to introduce all the elements of the approach, and finally, we validate it. Our edge-centric embedding entails a top-down mining of links, instead of inferring them from the similarities of node embeddings. This analysis is key to discovering inter-subgraph links that hold the whole graph connected, i.e., central edges. Using directed graphs (digraphs) allows us to cluster edge-like hubs and authorities. In addition, since directed edges inherit their labels from destination (origin) nodes, their embedding provides a proxy representation for node classification and clustering as well. This representation is obtained by embedding the line digraph of the original one. The line digraph provides nice formal properties with respect to the original graph; in particular, it produces more entropic latent spaces. With these properties at hand, we can relate edge embeddings to node embeddings. The main contribution of this paper is to set and prove the linearity theorem, which poses each element of the transition matrix for an edge embedding as a linear combination of the elements of the transition matrix for the node embedding. As a result, the rank preservation property explains why embedding the line digraph and using the labels of the destination nodes provides better classification and clustering performances than embedding the nodes of the original graph. In other words, we do not only facilitate edge mining but enforce node classification and clustering. However, computing the line digraph is challenging, and a sparsification strategy is implemented for the sake of scalability. Our experimental results show that the line digraph representation of the sparsified input graph is quite stable as we increase the sparsification level, and also that it outperforms the original (node-centric) representation. For the sake of simplicity, our theorem relies on node2vec-like (factorization) embeddings. However, we also include several experiments showing how line digraphs may improve the performance of Graph Neural Networks (GNNs), also following the principle of maximum entropy.<\/jats:p>","DOI":"10.3390\/e27030304","type":"journal-article","created":{"date-parts":[[2025,3,14]],"date-time":"2025-03-14T07:02:16Z","timestamp":1741935736000},"page":"304","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Edge-Centric Embeddings of Digraphs: Properties and Stability Under Sparsification"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-8733-2072","authenticated-orcid":false,"given":"Ahmed","family":"Begga","sequence":"first","affiliation":[{"name":"Department of Computer Science and Artificial Intelligence, University of Alicante, 03690 Alicante, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3238-4021","authenticated-orcid":false,"given":"Francisco","family":"Escolano Ruiz","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Artificial Intelligence, University of Alicante, 03690 Alicante, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4757-5587","authenticated-orcid":false,"given":"Miguel \u00c1ngel","family":"Lozano","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Artificial Intelligence, University of Alicante, 03690 Alicante, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,14]]},"reference":[{"key":"ref_1","unstructured":"Kipf, T.N., and Welling, M. (2017, January 24\u201326). Semi-Supervised Classification with Graph Convolutional Networks. Proceedings of the International Conference on Learning Representations (ICLR), Toulon, France."},{"key":"ref_2","unstructured":"Veli\u010dkovi\u0107, P., Cucurull, G., Casanova, A., Romero, A., Li\u00f2, P., and Bengio, Y. (May, January 30). Graph Attention Networks. Proceedings of the International Conference on Learning Representations, Vancouver, BC, Canada."},{"key":"ref_3","unstructured":"Klicpera, J., Bojchevski, A., and G\u00fcnnemann, S. (2018). Personalized Embedding Propagation: Combining Neural Networks on Graphs with Personalized PageRank. arXiv."},{"key":"ref_4","first-page":"1025","article-title":"Inductive representation learning on large graphs","volume":"30","author":"Hamilton","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6295","DOI":"10.1007\/s10462-022-10321-2","article-title":"A survey of graph neural networks in various learning paradigms: Methods, applications, and challenges","volume":"56","author":"Waikhom","year":"2023","journal-title":"Artif. Intell. Rev."},{"key":"ref_6","unstructured":"Veli\u010dkovi\u0107, P., Badia, A.P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R., and Blundell, C. (2022). The CLRS Algorithmic Reasoning Benchmark. arXiv."},{"key":"ref_7","unstructured":"Markeeva, L., McLeish, S., Ibarz, B., Bounsi, W., Kozlova, O., Vitvitskyi, A., Blundell, C., Goldstein, T., Schwarzschild, A., and Veli\u010dkovi\u0107, P. (2024). The CLRS-Text Algorithmic Reasoning Language Benchmark. arXiv."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Ou, M., Cui, P., Pei, J., Zhang, Z., and Zhu, W. (2016, January 13\u201317). Asymmetric Transitivity Preserving Graph Embedding. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/2939672.2939751"},{"key":"ref_9","first-page":"395","article-title":"Node Representation Learning for Directed Graphs","volume":"Volume 11906","author":"Brefeld","year":"2019","journal-title":"Proceedings of the ECML\/PKDD (1)"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2447","DOI":"10.1016\/j.laa.2012.10.022","article-title":"Ranking hubs and authorities using matrix functions","volume":"438","author":"Benzi","year":"2013","journal-title":"Linear Algebra Its Appl."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wang, Y., Wang, D., Liu, H., Hu, B., Yan, Y., Zhang, Q., and Zhang, Z. (2024, January 25\u201329). Optimizing Long-tailed Link Prediction in Graph Neural Networks through Structure Representation Enhancement. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD \u201924, Barcelona, Spain.","DOI":"10.1145\/3637528.3671864"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Grover, A., and Leskovec, J. (2016, January 13\u201317). node2vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA.","DOI":"10.1145\/2939672.2939754"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Perozzi, B., Al-Rfou, R., and Skiena, S. (2014, January 24\u201327). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD \u201914, New York, NY, USA.","DOI":"10.1145\/2623330.2623732"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., and Mei, Q. (2015, January 18\u201322). LINE: Large-scale Information Network Embedding. Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy.","DOI":"10.1145\/2736277.2741093"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., and Tang, J. (2018, January 5\u20139). Network Embedding As Matrix Factorization: Unifying DeepWalk, LINE, PTE, and Node2Vec. Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM \u201918, Marina Del Rey, CA, USA.","DOI":"10.1145\/3159652.3159706"},{"key":"ref_16","unstructured":"Chen, S., Niu, S., Akoglu, L., Kovacevic, J., and Faloutsos, C. (2017). Fast, Warped Graph Embedding: Unifying Framework and One-Click Algorithm. arXiv."},{"key":"ref_17","unstructured":"Beaini, D., Passaro, S., L\u00e9tourneau, V., Hamilton, W., Corso, G., and Li\u00f3, P. (2021, January 18\u201324). Directional Graph Networks. Proceedings of the 38th International Conference on Machine Learning, Virtual."},{"key":"ref_18","unstructured":"Chien, E., Peng, J., Li, P., and Milenkovic, O. (2021, January 3\u20137). Adaptive Universal Generalized PageRank Graph Neural Network. Proceedings of the International Conference on Learning Representations, Virtual."},{"key":"ref_19","unstructured":"Abboud, R., Dimitrov, R., and Ceylan, I.I. (2022, January 9\u201312). Shortest Path Networks for Graph Property Prediction. Proceedings of the First Learning on Graphs Conference, Virtual."},{"key":"ref_20","unstructured":"Song, Y., Zhou, C., Wang, X., and Lin, Z. (2023, January 1\u20135). Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing. Proceedings of the Eleventh International Conference on Learning Representations, Kigali, Rwanda."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"106830","DOI":"10.1016\/j.neunet.2024.106830","article-title":"Node classification in the heterophilic regime via diffusion-jump GNNs","volume":"181","author":"Begga","year":"2025","journal-title":"Neural Netw."},{"key":"ref_22","unstructured":"Chen, Z., Li, L., and Bruna, J. (2019, January 6\u20139). Supervised Community Detection with Line Graph Neural Networks. Proceedings of the International Conference on Learning Representations, New Orleans, LA, USA."},{"key":"ref_23","unstructured":"Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (2017). PRUNE: Preserving Proximity and Global Ranking for Network Embedding. Advances in Neural Information Processing Systems 30, Curran Associates, Inc."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Wang, X., Cui, P., Wang, J., Pei, J., Zhu, W., and Yang, S. (2017, January 4\u20139). Community Preserving Network Embedding. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI\u201917, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.10488"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"7075","DOI":"10.1109\/TPAMI.2020.3029762","article-title":"Co-embedding of Nodes and Edges with Graph Neural Networks","volume":"45","author":"Jiang","year":"2020","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1935","DOI":"10.1109\/TNNLS.2020.2995483","article-title":"Network Together: Node Classification via Cross-Network Deep Network Embedding","volume":"32","author":"Shen","year":"2021","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Escolano, F., Suau, P., and Bonev, B. (2009). Information Theory in Computer Vision and Pattern Recognition, Springer Publishing Company, Incorporated. [1st ed.].","DOI":"10.1007\/978-1-84882-297-9"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1142\/S0219265903000933","article-title":"Algebraic Properties of a Digraph and its Line Digraph","volume":"4","author":"Balbuena","year":"2003","journal-title":"J. Interconnect. Netw."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1016\/j.laa.2013.11.026","article-title":"Flanders theorem for many matrices under commutativity assumptions","volume":"443","author":"Lippert","year":"2014","journal-title":"Linear Algebra Its Appl."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1080\/00029890.1996.12004788","article-title":"The Relationship Between AB and BA","volume":"103","author":"Johnson","year":"1996","journal-title":"Am. Math. Mon."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1023\/A:1023012502046","article-title":"Families of Line-Graphs and Their Quantization","volume":"111","author":"Pakonski","year":"2003","journal-title":"J. Stat. Phys."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.physrep.2011.01.002","article-title":"Continuous-time quantum walks: Models for coherent transport on complex networks","volume":"502","author":"Blumen","year":"2011","journal-title":"Phys. Rep."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"030103","DOI":"10.1103\/PhysRevE.83.030103","article-title":"Maximal-entropy random walks in complex networks with limited information","volume":"83","author":"Sinatra","year":"2011","journal-title":"Phys. Rev. E"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Fiol, M., Alegre, I., and Yebra, J. (1983, January 22\u201326). Line Digraph Iterations and the (d,k) Problem for Directed Graphs. Proceedings of the 10th Annual Symposium on Computer Architecture, Washington, DC, USA.","DOI":"10.1145\/800046.801653"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/j.laa.2017.04.036","article-title":"Iterated line digraphs are asymptotically dense","volume":"529","year":"2017","journal-title":"Linear Algebra Its Appl."},{"key":"ref_36","unstructured":"Levy, O., and Goldberg, Y. (2014, January 8\u201313). Neural Word Embedding as Implicit Matrix Factorization. Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, Montreal, QC, Canada."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.patcog.2019.02.012","article-title":"Dirichlet densifiers for improved commute times estimation","volume":"91","author":"Curado","year":"2019","journal-title":"Pattern Recognit."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/j.patrec.2019.06.001","article-title":"Dirichlet densifier bounds: Densifying beyond the spectral gap constraint","volume":"125","author":"Curado","year":"2019","journal-title":"Pattern Recognit. Lett."},{"key":"ref_39","unstructured":"Bojchevski, A., and G\u00fcnnemann, S. (2019, January 9\u201315). Adversarial Attacks on Node Embeddings via Graph Poisoning. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, CA, USA."},{"key":"ref_40","first-page":"1","article-title":"Moore graphs and beyond: A survey of the degree\/diameter problem","volume":"20","author":"Miller","year":"2013","journal-title":"Electron. J. Comb."},{"key":"ref_41","unstructured":"Yin, Z., and Shen, Y. (2018, January 3\u20138). On the Dimensionality of Word Embedding. Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS\u201918, Montr\u00e9al, QC, Canada."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Fan, C., Zeng, L., Ding, Y., Chen, M., Sun, Y., and Liu, Z. (2019, January 3\u20137). Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach. Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM \u201919, Beijing, China.","DOI":"10.1145\/3357384.3357979"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1145\/324133.324140","article-title":"Authoritative Sources in a Hyperlinked Environment","volume":"46","author":"Kleinberg","year":"1999","journal-title":"J. ACM"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1137\/08074489X","article-title":"Spectral Sparsification of Graphs","volume":"40","author":"Spielman","year":"2011","journal-title":"SIAM J. Comput."},{"key":"ref_45","unstructured":"Cheng, D., Cheng, Y., Liu, Y., Peng, R., and Teng, S.H. (2015). Spectral Sparsification of Random-Walk Matrix Polynomials. arXiv."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Kelner, J.A., Peebles, J., Peng, R., Rao, A.B., Sidford, A., and Vladu, A. (2016). Almost-Linear-Time Algorithms for Markov Chains and New Spectral Primitives for Directed Graphs. arXiv.","DOI":"10.1145\/3055399.3055463"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1080\/15427951.2006.10129130","article-title":"Stability and Similarity of Link Analysis Ranking Algorithms","volume":"3","author":"Donato","year":"2006","journal-title":"Internet Math."},{"key":"ref_48","first-page":"93","article-title":"Collective Classification in Network Data","volume":"29","author":"Sen","year":"2008","journal-title":"AI Mag."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1093\/nar\/gkm1001","article-title":"The BioGRID Interaction Database: 2008 update","volume":"36","author":"Breitkreutz","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"ref_50","unstructured":"McAuley, J., and Leskovec, J. (2012, January 3\u20136). Learning to Discover Social Circles in Ego Networks. Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012, Lake Tahoe, NV, USA."},{"key":"ref_51","unstructured":"Leskovec, J., and Krevl, A. (2025, March 10). SNAP Datasets: Stanford Large Network Dataset Collection. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Song, H.H., Cho, T.W., Dave, V., Zhang, Y., and Qiu, L. (2009, January 4\u20136). Scalable Proximity Estimation and Link Prediction in Online Social Networks. Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, Chicago, IL, USA.","DOI":"10.1145\/1644893.1644932"},{"key":"ref_53","unstructured":"Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., and Dahl, G.E. (2017). Neural Message Passing for Quantum Chemistry. arXiv."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"106207","DOI":"10.1016\/j.neunet.2024.106207","article-title":"A Comprehensive Survey on Deep Graph Representation Learning","volume":"173","author":"Ju","year":"2024","journal-title":"Neural Netw."},{"key":"ref_55","unstructured":"Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Yu, P.S. (2019). A Comprehensive Survey on Graph Neural Networks. arXiv."},{"key":"ref_56","unstructured":"Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (2017, January 4\u20139). Deep Sets. Proceedings of the 31st International Conference on Neural Information Processing Systems, Long Beach, CA, USA."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"624","DOI":"10.1137\/16M1073376","article-title":"Sensitivity of Mixing Times in Eulerian Digraphs","volume":"32","author":"Boczkowski","year":"2018","journal-title":"SIAM J. Discret. Math."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/3\/304\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:53:41Z","timestamp":1760028821000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/3\/304"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,14]]},"references-count":57,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["e27030304"],"URL":"https:\/\/doi.org\/10.3390\/e27030304","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,3,14]]}}}