Complex Networks & Their Applications XII

Graph Neural Network (GNN) research has produced strategies to modify a graph’s edges using gradients from a trained GNN, with the goal of network design. However, the factors which govern gradient-based editing are understudied, obscuring why edges are chosen and if edits are grounded in an edge’s importance. Thus, we begin by analyzing the gradient computation in previous works, elucidating the factors that influence edits and highlighting the potential over-reliance on structural properties. Specifically, we find that edges can achieve high gradients due to structural biases, rather than importance, leading to erroneous edits when the factors are unrelated to the design task. To improve editing, we propose ORE, an iterative editing method that (a) edits the highest scoring edges and (b) re-embeds the edited graph to refresh gradients, leading to less biased edge choices. We empirically study ORE through a set of proposed design tasks, each with an external validation method, demonstrating that ORE improves upon previous methods by up to 50%.

In recent years, Graph Neural Networks (GNNs) have undergone rapid development and have become an essential tool for building representations of complex relational data. Large real-world graphs, characterised by sparsity in relations and features, necessitate dedicated tools that existing dense tensor-centred approaches cannot easily provide. To address this need, we introduce a GNNs module in Scikit-network, a Python package for graph analysis, leveraging sparse matrices for both graph structures and features. Our contribution enhances GNNs efficiency without requiring access to significant computational resources, unifies graph analysis algorithms and GNNs in the same framework, and prioritises user-friendliness.

The use of Graph Neural Networks (GNNs) in time series analysis is on the rise, yet the application of GNN Graph Classification in this field remains in its early stages. In our research, we repurpose GNN Graph Classification, traditionally rooted in disciplines like biology and chemistry, to delve into the intricacies of time series datasets. We demonstrate how graphs are constructed within individual time series and across multiple datasets, highlighting the versatility of GNN techniques beyond their standard applications. A key observation in our study was the sensitivity of the GNN Graph Classification model to graph topology. While initially seen as a potential concern for model robustness, this sensitivity turned out to be beneficial for pinpointing outliers. Our findings underscore the innovation of applying GNN Graph Classification to time series analysis, unlocking new dimensions in data interpretation. This research lays the groundwork for integrating these methodologies, indicating vast potential for their wider application and opening up promising avenues for future exploration.

Graph Neural Networks (GNNs) extend basic Neural Networks (NNs) by additionally making use of graph structure based on the relational inductive bias (edge bias), rather than treating the nodes as collections of independent and identically distributed (i.i.d.) samples. Though GNNs are believed to outperform basic NNs in real-world tasks, it is found that in some cases, GNNs have little performance gain or even underperform graph-agnostic NNs. To identify these cases, based on graph signal processing and statistical hypothesis testing, we propose two measures which analyze the cases in which the edge bias in features and labels does not provide advantages. Based on the measures, a threshold value can be given to predict the potential performance advantages of graph-aware models over graph-agnostic models.

The performance limit of deep Graph Convolutional Networks (GCNs) are pervasively thought to be caused by the inherent limitations of the GCN layers, such as their insufficient expressive power. However, if this were true, modifying only the training procedure for a given architecture would not likely to enhance performance. Contrary to this belief, our paper demonstrates several ways to achieve such improvements. We begin by highlighting the training challenges of GCNs from the perspective of graph signal energy loss. More specifically, we find that the loss of energy in the backward pass during training hinders the learning of the layers closer to the input. To address this, we propose several strategies to mitigate the training problem by slightly modifying the GCN operator, from the energy perspective. After empirical validation, we confirm that these changes of operator lead to significant decrease in the training difficulties and notable performance boost, without changing the composition of parameters. With these, we conclude that the root cause of the problem is more likely the training difficulty than the others.

A recommender system based on Graph Neural Networks can effectively capture user-item interactions through the graph structure, leading to highly personalized and relevant recommendations. However, existing works adapting Graph Neural Networks (GNN) to recommendations struggle with the cold-start problem. Indeed, it is difficult to make accurate recommendations for new users or items with little or no interaction data. Building on previous work, we introduce an Enhanced Mutual Interaction Graph Attention Network (E-MIGAN) for this purpose. It is based on self-supervised representation learning on a large-scale bipartite graph. It is composed of three components: i) The attention network module that learns attention weights for each node and its neighbors, ii) The mutual interaction module computes a mutual interaction matrix for each node and its neighbors on each item, which encodes the pairwise interactions, and iii) A Content-Based Embedding model, which overcomes the cold start issue. The empirical study on real-world datasets proves that E-MIGAN achieves state-of-the-art performance, demonstrating its effectiveness in capturing complex interactions in graph-structured data.

Graph neural networks (GNNs) have shown promise in addressing graph-related problems, including node classification. However, in real-world scenarios, data often exhibits an imbalanced, sometimes highly-skewed, distribution with dominant classes representing the majority, where certain classes are severely underrepresented. This leads to a suboptimal performance of standard GNNs on imbalanced graphs. In this paper, we introduce a unique approach that tackles imbalanced classification on graphs by considering graph heterophily. We investigate the intricate relationship between class imbalance and graph heterophily, revealing that minority classes not only exhibit a scarcity of samples but also manifest lower levels of homophily, facilitating the propagation of erroneous information among neighboring nodes. Drawing upon this insight, we propose an efficient method, called Fast Im-GBK, which integrates an imbalance classification strategy with heterophily-aware GNNs to effectively address the class imbalance problem while significantly reducing training time. Our experiments on real-world graphs demonstrate our model’s superiority in classification performance and efficiency for node classification tasks compared to existing baselines.

Time series forecasting lies at the core of important real-world applications in many fields of science and engineering. The abundance of large time series datasets that consist of complex patterns and long-term dependencies has led to the development of various neural network architectures. Graph neural network approaches, which jointly learn a graph structure based on the correlation of raw values of multivariate time series while forecasting, have recently seen great success. However, such solutions are often costly to train and difficult to scale. In this paper, we propose TimeGNN, a method that learns dynamic temporal graph representations that can capture the evolution of inter-series patterns along with the correlations of multiple series. TimeGNN achieves inference times 4 to 80 times faster than other state-of-the-art graph-based methods while achieving comparable forecasting performance.

Graph Neural Networks (GNNs) have demonstrated state-of-the-art performance in various graph representation learning tasks. Recently, studies revealed their vulnerability to adversarial attacks. While the available attack strategies are based on applying perturbations on existing graphs within a specific budget, proposed defense mechanisms successfully guard against this type of attack. This paper proposes a new perspective founded on unrestricted adversarial examples. We propose to produce adversarial attacks by generating completely new data points instead of perturbing existing ones. We introduce a framework, so-called UnboundAttack, leveraging the advancements in graph generation to produce graphs preserving the semantics of the available training data while misleading the targeted classifier. Importantly, our method does not assume any knowledge about the underlying architecture. Finally, we validate the effectiveness of our proposed method in a realistic setting related to molecular graphs.

Graph Neural Networks (GNNs) have improved unsupervised community detection of clustered nodes due to their ability to encode the dual dimensionality of the connectivity and feature information spaces of graphs. Identifying the latent communities has many practical applications from social networks to genomics. Current benchmarks of real world performance are confusing due to the variety of decisions influencing the evaluation of GNNs at this task. To address this, we propose a framework to establish a common evaluation protocol. We motivate and justify it by demonstrating the differences with and without the protocol. The W Randomness Coefficient is a metric proposed for assessing the consistency of algorithm rankings to quantify the reliability of results under the presence of randomness. We find that by ensuring the same evaluation criteria is followed, there may be significant differences from the reported performance of methods at this task, but a more complete evaluation and comparison of methods is possible.

It is common to use the projection of a bipartite network to measure a unipartite network of interest. For example, scientific collaboration networks are often measured using a co-authorship network, which is the projection of a bipartite author-paper network. Caution is required when interpreting the edge weights that appear in such projections. However, backbone models offer a solution by providing a formal statistical method for evaluating when an edge in a projection is statistically significantly strong. In this paper, we propose an extension to the existing Stochastic Degree Sequence Model (SDSM) that allows the null model to include edge constraints (EC) such as prohibited edges. We demonstrate the new SDSM-EC in toy data and empirical data on young children’s’ play interactions, illustrating how it correctly omits noisy edges from the backbone.

We explore two questions related to sampling and minorities in attributed networks with homophily. The first question is to investigate sampling schemes which favor minority attribute nodes and which give preference to “more popular” nodes having higher centrality measures in the network. A data study shows the efficiency of Page-rank and walk-based network sampling schemes on a directed network model and a real-world network with small minorities. The second question concerns the effect of homophily and out-degrees of nodes on the relative ranking of minorities compared to majorities in degree-based sampling. Several synthetic network configurations are considered and the conditions for minority nodes to have a higher relative rank are investigated numerically. The results are also assessed with real-world networks.

This paper proposes a novel framework for empirically assessing the effect of network characteristics on the performance of pretrained link prediction models. In link prediction, the task is to predict missing or future links in a given network dataset. We focus on the pretrained setting, in which such a predictive model is trained on one dataset, and employed on another dataset. The framework allows one to overcome a number of nontrivial challenges in adequately testing the performance of such a pretrained model in a proper cross-validated setting. Experiments are performed on a corpus of 49 structurally diverse real-world complex network datasets from various domains with up to hundreds of thousands of nodes and edges. Overall results indicate that the extent to which a network is clustered is strongly related to whether this network is a suitable candidate to create a pretrained model on. Moreover, we systematically assessed the relationship between topological similarity and performance difference of pretrained models and a model trained on the same data. We find that similar network pairs in terms of clustering coefficient, and to a lesser extent degree assortativity and gini coefficient, yield minimal performance difference. The findings presented in this work pave the way for automated model selection based on topological similarity of the networks, as well as larger-scale deployment of pretrained link prediction models for transfer learning.

For many natural language processing systems, the extraction of temporal links and associations from clinical narratives has been a critical challenge. To understand such processes, we must be aware of the occurrences of events and their time or temporal aspect by constructing a chronology for the sequence of events. The primary objective of temporal relation extraction is to identify relationships and correlations between entities, events, and expressions. We propose a novel architecture leveraging Transformer based graph neural network by combining textual data with event graph embeddings for predicting temporal links across events, entities, document creation time and expressions. We demonstrate our preliminary findings on i2b2 temporal relations corpus for predicting BEFORE, AFTER and OVERLAP links with event graph for correct set of relations. Comparison with various Biomedical-BERT embedding types were benchmarked yielding best performance on PubMed BERT with language model masking (LMM) mechanism on our methodology. This illustrates the effectiveness of our proposed strategy.

Healthcare professionals are required to adhere to strict precautions. Thus, continuous monitoring, compliance with safety standards, and prompt care are essential. Hospitals employ various methods and devices to ensure the patient’s well-being. However, many of these efforts are compromised when the observation is neglected. This paper presents an effective approach to enable doctors (or) supervisors to track and forecast the patient’s health condition during the treatment. The approach leverages the concept of Internet of Things (IoT) for seamless data acquisition, data analytics for visualization, and machine learning (ML) to train models with the acquired data for future prediction of similar conditions. For monitoring, sensors are used to collect data such as the ambient state and the location to verify that the patient (or) person under observation is within the expected range using range detection techniques supported by Bluetooth master-slave communication. Computations are performed in the backend such that the alerts are notified based on the conditions assigned to the respective patients. In case of emergency, we can reliably predict the condition of a patient with improved accuracy. Moreover, the stored data is fed to an ML framework for data training and ML modeling. Therefore, this design can serve as an optimal model to address the much-needed advancement in healthcare.

This paper presents findings from the “Estimating the Economic and Health Burdens of HIV in Semi-Urban and Rural Illinois" survey conducted in downstate Illinois, USA. The survey targeted hidden and hard-to-reach communities of HIV-positive individuals and their partners. The study utilizes network science techniques, including community detection and visualization, to analyze the social, medical, and economic forces influencing three underserved communities: African Americans, HIV-positive individuals, and those facing worsened economic situations due to COVID-19. The analysis reveals disparities in healthcare access, discrimination, and economic challenges faced by these communities. The paper highlights the value of network analysis in interpreting smaller datasets and calls for further collaborations and research using the freely available survey data and analysis materials.

Generative AI models, known for their capacity to generate intricate and realistic data, have rapidly found applications across various domains. Yet, doubts linger regarding the full scope of their hallucinatory capabilities and the reliability of their outcomes. These concerns underscore the need for rigorous analysis and validation of generative AI models. This study employs network analysis to explore the inherent characteristics of generative AI models, focusing on their deviations and disparities between generated and actual content. Using GPT3.5 and RoBERTa, we analyze tweets, vocabulary, and emotion networks from their outputs. Although network comparison demonstrated hallucination, non-classification, and instability patterns in GPT-3.5 compared to RoBERTa as a baseline, both models exhibit promise and room for improvement.

Regressions trained to predict the future activity of social media users need rich features for accurate predictions. Many advanced models exist to generate such features; however, the time complexities of their computations are often prohibitive when they run on enormous data-sets. Some studies have shown that simple semantic network features can be rich enough to use for regressions without requiring complex computations. We propose a method for using semantic networks as user-level features for machine learning tasks. We conducted an experiment using a semantic network of 1037 Twitter hashtags from a corpus of 3.7 million tweets related to the 2022 French presidential election. A bipartite graph is formed where hashtags are nodes and weighted edges connect the hashtags reflecting the number of Twitter users that interacted with both hashtags. The graph is then transformed into a maximum-spanning tree with the most popular hashtag as its root node to construct a hierarchy amongst the hashtags. We then provide a vector feature for each user based on this tree. To validate the usefulness of our semantic feature we performed a regression experiment to predict the response rate of each user with six emotions like anger, enjoyment, or disgust. Our semantic feature performs well with the regression with most emotions having $$R^2$$ R 2 above 0.5. These results suggest that our semantic feature could be considered for use in further experiments predicting social media response on big data-sets.

Information over-squashing occurs under inefficient information propagation between distant nodes on networks, which can significantly impact graph neural network (GNN) training. Rewiring is a preprocessing procedure applied to the input network to mitigate this problem. In this paper, we investigate discrete analogues of various notions of curvature to model information flow on networks and rewire them. We show that classical notions of curvature achieve state-of-the-art performance in GNN training accuracy on a wide variety of real-world datasets. Moreover, these classical notions exhibit a clear advantage in computational runtime by several orders of magnitude.

In scenarios where objects are characterized by a combination of rigid and flexible features, we consider the problem of identifying a natural set of rigid clusters, along with a network model of flexible states per cluster. Our approach proves effective within the Allais paradox context. Our algorithm, applied to data collected in an experiment, identified personality clusters and emotion states within each cluster. This model outperforms alternative clustering models in capturing information regarding participants’ choices. Beyond the current scope, our approach is applicable to other data-sets with combined rigid-flexible attributes. Beyond prediction, a strategy that aims to achieve a result by influencing a flexible state holds the promise of enhanced effectiveness when it is tailored to a cluster.

Social media platforms like Twitter revolutionized online communication. But this new era of interaction has brought with it a challenge—the widespread presence and influence of bot accounts. These bots are rapidly evolving, making traditional detection methods increasingly ineffective and allowing malicious actors to influence public discourse. While existing bot detection methods report high performance, such results might actually be connected to shortcomings in dataset collection and labeling practices, rather than reflecting their true ability to detect bots, casting doubt on their true reliability. Our study introduces higher-order behavior-based relations, including Co-Retweet, and Co-Hashtag, derived from the TwiBot-22 dataset. By leveraging these new relations in the BotRGCN architecture, we shift the emphasis from isolated accounts to coordinated group dynamics, making it more challenging for bot developers to evade detection. This strategy not only acknowledges the limitations and inherent biases presented in existing bot detection techniques, but also presents a way to address them. Our experiments support this approach as a promising way forward to tackle challenges in bot detection.

Network completion is more challenging than link prediction, as it aims to infer both missing links and nodes. Although various methods exist for this problem, few utilize structural information-specifically, the similarity of local connection patterns. In this study, we introduce a model called C-GIN, which captures local structural patterns in the observed portions of a network using a Graph Auto-Encoder equipped with a Graph Isomorphism Network. This model generalizes these patterns to complete the entire graph. Experimental results on both synthetic and real-world networks across diverse domains indicate that C-GIN not only requires less information but also outperforms baseline prediction models in most cases. Additionally, we propose a metric known as “Reachable Clustering Coefficient (RCC)” based on network structure. Experiments reveal that C-GIN performs better on networks with higher Reachable CC values.

The task of semi-supervised classification aims at assigning labels to all nodes of a graph based on the labels known for a few nodes, called the seeds. One of the most popular algorithms relies on the principle of heat diffusion, where the labels of the seeds are spread by thermo-conductance and the temperature of each node at equilibrium is used as a score function for each label. In this paper, we prove that this algorithm is not consistent unless the temperatures of the nodes at equilibrium are centered before scoring. This crucial step does not only make the algorithm provably consistent on a block model but brings significant performance gains on real graphs.

Topological Data Analysis is a field of great interest in many applications such as finance or neuroscience. The goal of the present paper is to propose a novel approach to building simplicial complexes that capture the multiway ordered interactions in the components of high-dimensional time series using the theory of Signatures. Signatures represent one of the most powerful transforms for extracting group-wise structural features and we put them to work in the task of discovering statistically meaningful simplices from a complex that we estimate sequentially. Numerical experiments on an fMRI dataset illustrates the efficiency and relevance of our approach.

We examine the sensitivity of community-structured graph spectra to graph size, block size and inter-block edge probability. We use the Planted Partition Model because of its transparency. While this generative model may seem simplistic, it allows us to isolate the effects of graph and block size, edge probabilities and, consequently, vertex degree distribution on spectra. These sensitivities to key graph characteristics also generalize beyond Planted Partition Model graphs, because they are based on graph structure. Notably, our results show that eigenvalues converge to those of a complete graph, with increases in graph size or inter-block edge probability. Such convergence severely limits the use of spectral techniques.

Given the rising prevalence of disinformation and fake news online, the detection of fake news in social media posts has become an essential task in the field of social network analysis and NLP. In this paper, we propose a fake detection model named, FakEDAMR that encodes textual content using the Abstract Meaning Representation (AMR) graph, a semantic representation of natural language that captures the underlying meaning of a sentence. The graphical representation of textual content holds longer relation dependency in very few distances. A new fake news dataset, FauxNSA, has been created using tweets from the Twitter platform related to ‘Nupur Sharma’ and ‘Agniveer’ political controversy. We embed each sentence of the tweet using an AMR graph and then use this in combination with textual features to classify fake news. Experimental results on publicly and proposed datasets with two different sets show that adding AMR graph features improves F1-score and accuracy significantly. (Code and Dataset: https://github.com/shubhamgpt007/FakedAMR )

This paper addresses the critical task of evaluating the visual quality of triangular mesh models. We introduce an innovative approach that leverages weighted graphs for this purpose. Motivated by the growing need for accurate quality assessment in various fields, including computer graphics and 3D modeling, our methodology begins by generating saliency maps for each distorted mesh model. These models are subsequently transformed into a network representation, where mesh vertices are nodes and mesh edges are edges in the graph. The determination of vertex weights relies on the salience values. We then extract a wide range of topological properties and compute statistical measures to create a signature vector. To predict the quality score, we rigorously evaluate the performance of three regression algorithms. Experiments span four publicly available databases designed for mesh model quality assessment. Results demonstrate that the proposed approach excels in this task, showcasing remarkable correlations with subjective evaluations. This preliminary analysis paves the way for further research to address potential limitations and explore additional applications of mesh network representation.

A fast and accurate stand-alone face recognition system is crucial for surveillance purposes; however, it is also important to keep the costs as low as possible. Herein, we address this issue by proposing a preliminary analysis of embedded Machine Learning techniques by using Erdős-Rényi sparse random networks. The idea is to develop a compact and reliable ANN to conduct a multi-class classification of low-resolution face images to simulate the scenario of having cheap security cameras with an embedded ANN. The study considered two architectures (ResNet, and AlexNet inspired CNNs) with a sparsity level varied up to 90%. To achieve comparable results, the image resolution was varied from $$32\times 32$$ 32 × 32 up to $$96\times 96$$ 96 × 96 . The analyses unveiled that for low-resolution images, the best trade-off between accuracy and sparsity level has been achieved with ResNet architectures and a sparsity level of 70% outperforming the benchmark (i.e., with no sparsity).

Distance computation is a fundamental problem in algorithmic graph theory with broad applications across various fields. Distance labeling is the method of assigning a label $$\ell $$ ℓ to each node in a given graph G such that the distance between any pair of nodes u, v can be efficiently computed (or approximated) using only their labels $$\ell (u)$$ ℓ ( u ) and $$\ell (v)$$ ℓ ( v ) . Minimizing the size of these labels is of crucial importance for performance. In this paper, we address this challenge by introducing a novel learning-based approach to distance labeling inspired by collaborative filtering. This approach achieves superior performance compared to the theoretical baseline on label size with a trade-off in distance approximation error on special graph classes such as cycles and trees. We also report promising experimental results on general graphs that obtain lower error than cycles and trees.

This research demonstrates how recommendation algorithms can shape public discourse and attitudes on morally charged topics. Our study provides an in-depth analysis of the moral, emotional, and network dimensions of Youtube’s recommended videos related to the China-Uyghur issue. We investigated the spread of moral themes and whether the algorithm favors videos with certain emotional feelings. Additionally, we conducted a detailed network analysis to spot the most influential videos and see how the themes change as the recommendations change. We found that as the algorithm recommends more videos, the emotional diversity of the recommendations tends to drift towards positive emotions and away from negative ones. Likewise, there is a decreasing focus on moral dilemmas as one moves through the recommended content. In simple terms, our study shows how YouTube’s recommendations may influence viewers’ feelings and beliefs. Our network analysis reveals which videos are driving the shift in morality and emotion and how the main discussion points change as more videos are suggested. Through this, we hope to better understand the inherent biases in recommendation engines, especially when they are dealing with emotionally charged and morally complex topics.

Speech enhancement is a key component in voice communication technology as it serves as an important pre-processing step for systems such as acoustic echo cancellation, speech separation, speech conversions, etc. A low-latency speech enhancement algorithm is desirable since long latency means delaying the entire system’s response. In STFT-based systems, reducing algorithmic latency by using smaller STFT window sizes leads to significant degradation in speech quality. By introducing a simple additional compensation window along with the original short main window in the analysis step of STFT, we preserve signal quality – comparable to that of the original high latency system while reducing the algorithmic latency from 42 ms to 5 ms. Experiments on the full-band VCD dataset and a large full-band Microsoft’s internal dataset show the effectiveness of the proposed method.

With SINr, we introduced a way to design graph and word embeddings based on community detection. Contrary to deep learning approaches, this approach does not require much compute and was proven to be at the state-of-the-art for interpretability in the context of word embeddings. In this paper, we investigate how filtering communities detected on word co-occurrence networks can improve performances of the approach. Community detection algorithms tend to uncover communities whose size follows a power-law distribution. Naturally, the number of activations per dimensions in SINr follows a power-law: a few dimensions are activated by many words, and many dimensions are activated by a few words. By filtering this distribution, removing part of its head and tail, we show improvement on intrinsic evaluation of the embedding while dividing their dimensionality by five. In addition, we show that these results are stable through several runs, thus defining a subset of distinctive features to describe a given corpus.

Drug discovery focuses on understanding different types of interactions from drug-drug interactions (DDIs) to drug-food interactions (DFIs). The main purpose of DFI is to discover how a particular food affects drug absorption, side effects and its effectiveness. The study of drug-food interactions (DFIs) can provide valuable insight into optimizing patient care, adjusting dosages, and improving patient safety.In this work, we propose a novel workflow where we aim to use a community-based recommender system to infer and identify novel DFIs while incorporating the concept of community profiling and leveraging the power of Graph Neural Networks. We conduct experiments on the DrugBank dataset and use FooDB dataset to learn more about food constituents. Our experiments reveal significant improvements over a number of the latest approaches designed for DFI identification. The findings substantiate that the utilization of multiple graphs to leverage diverse forms of relationships holds the potential to yield better recommendations by extracting complex relationships through the community structure.

For analysing real-world networks, graph representation learning is a popular tool. These methods, such as a graph autoencoder (GAE), typically rely on low-dimensional representations, also called embeddings, which are obtained through minimising a loss function; these embeddings are used with a decoder for downstream tasks such as node classification and edge prediction. While GAEs tend to be fairly accurate, they suffer from scalability issues. For improved speed, a Local2Global approach, which combines graph patch embeddings based on eigenvector synchronisation, was shown to be fast and achieve good accuracy. Here we propose L2G2G, a Local2Global method which improves GAE accuracy without sacrificing scalability. This improvement is achieved by dynamically synchronising the latent node representations, while training the GAEs. It also benefits from the decoder computing an only local patch loss. Hence, aligning the local embeddings in each epoch utilises more information from the graph than a single post-training alignment does, while maintaining scalability. We illustrate on synthetic benchmarks, as well as real-world examples, that L2G2G achieves higher accuracy than the standard Local2Global approach and scales efficiently on the larger data sets. We find that for large and dense networks, it even outperforms the slow, but assumed more accurate, GAEs.

This work delves into the dynamic landscape of Knowledge Graph-to-text generation, where structured knowledge graphs are transformed into coherent natural language text. Three key architectural paradigms are explored: Graph Neural Networks (GNNs), Graph Transformers (GTs), and linearization with sequence-to-sequence models. We discuss the advantages and limitations of these architectures, and we do some experiments on these architectures. Performance evaluations on WebNLG V.2 demonstrate the superiority of sequence-to-sequence Transformer-based models, especially when enriched with structural information from the graph. Despite being unsupervised, the CycleGT model also outperforms GNNs and GTs. However, practical constraints, such as computational efficiency and model validity, make sequence-to-sequence models the preferred choice for real-time conversational agents. Future research directions include enhancing the efficiency of GNNs and GTs, addressing scalability issues, handling multimodal knowledge graphs, improving interpretability, and devising data labeling strategies for domain-specific models. Cross-lingual and multilingual extensions can further broaden the applicability of these models in diverse linguistic contexts. In conclusion, the choice of architecture should align with specific task requirements and application constraints, and the field offers promising prospects for continued innovation and refinement.

Networks provide a very understandable representation of the data in which we get information about the relationships between pairs of nodes. For this representation, we can use one of the powerful analytical tools, 2D visualization. In visualization, networks have an alternative vector representation to which a wide range of machine learning methods can be applied. More generally, networks can be transformed to a low-dimensional space by network embedding methods. In this paper, we present a new embedding method that uses a non-symmetric dependency to find the distance between nodes and applies an iterative procedure to find a satisfactory distribution of nodes in space. Using experiments with small networks and dimension 2, we show the effectiveness of this method and discuss its properties.

Network embedding, a technique that transforms the nodes and edges of a network into low-dimensional vector representations while preserving relevant structural and semantic information, has gained prominence in recent years. Community structure is one of the most prevalent features of networks, and ensuring its preservation is crucial to represent the network in a lower-dimensional space accurately. While the core objective of network embedding is to bring related nodes in the original network close together in a lower-dimensional space, common classification metrics overlook community structure preservation. This work addresses the need for a comprehensive analysis of network embedding algorithms at the community level. On a set of synthetic networks that span strong to weak community structure strengths, we showcase the variability in the performance of network embedding techniques across mesoscopic metrics. Additionally, we highlight that the mesoscopic metrics are not highly correlated with the classification metrics. The community structure can further diminish the correlation as its strength weakens.

Shortest path computation is one of the most fundamental and well-studied problems in algorithmic graph theory, though it becomes more complex when graph components are susceptible to failure. This research utilizes a Distance Sensitivity Oracle (DSO) for efficiently querying replacement paths in graphs with potential failures to avoid inefficiently recomputing them after every outage with traditional techniques. By leveraging technologies such as node2vec, graph attention networks, and multi-layer perceptrons, the study pioneers a method to identify pivot nodes that lead to replacement paths closely resembling optimal solutions with deep learning. Tests on real-world network demonstrate replacement paths that are longer by merely a few percentages compared to the optimal solution.