Node classification in heterophilous graphs, where connected nodes often have different characteristics, which presents a significant challenge. We introduce HAPPY, which combines heterophily-aware random walks with targeted subgraph extraction. Our approach enhances Personalized PageRank by incorporating both label and feature diversity into the random walk process. Through theoretical analysis, we demonstrate that HAPPY effectively captures both homophilous and heterophilous relationships. Comprehensive experiments validate our method’s state-of-the-art performance across challenging heterophilous benchmarks.

The pervasive issue of missing data in statistical analysis and data science significantly impacts the integrity and accuracy of Time-Series Cross-Sectional (TSCS) datasets, extensively used in domains like health sciences and sensor applications. Traditional imputation methods are often inadequate for these datasets as they fail to address the complexities arising from cross-sectional and temporal data gaps. This paper introduces BiTSNet (Bipartite Time Series Network for Data Imputation), a novel approach designed to tackle the unique challenges of TSCS datasets by leveraging a dual representation of data. BiTSNet models cross-sectional time series data as sequences of bipartite graphs, where each graph represents a specific time step, and feature values are depicted as edge weights. Thus, missing values are interpreted as missing edge feature values, allowing BiTSNet to comprehensively capture spatial relationships within each time step and temporal relationships across steps. The framework uses Graph Neural Networks (GNNs) to process spatial dependencies within these bipartite graph representations and employs Recurrent Neural Networks (RNNs) to handle temporal dependencies. This integration enables BiTSNet to learn the intricate intra-time step relationships and the inter-time step dynamics effectively. Our approach not only preserves the longitudinal and cross-sectional integrity of the data but also ensures the production of valid and insightful conclusions from the enriched dataset. We evaluated BiTSNet on several datasets and compared it against the state-of-the-art approaches with encouraging results.

Node classification in graphs, particularly those exhibiting heterophily, poses significant challenges for traditional methodologies. These include various graph neural network variants and approaches that simplify graph convolutions. This paper proposes a novel approach called nCASH, which combines an innovative label propagation method that utilizes features to compute soft labels and node homophily scores. It also incorporates multi-filter spectral convolutions and a redefined Laplacian matrix tailored for heterophilic graphs. nCASH allows for different types of feature transformations; each region of the graph is characterized by its homophily scores, which dictate the type of filter applied. Low-pass filters are used in homophilous regions, and high-pass filters in heterophilous regions to accentuate differences. nCASH, free from extensive training requirements, relies on sparse matrix multiplications. This enhances scalability and efficiency. Empirical results demonstrate the effectiveness of this approach, showing improvements in classification accuracy on several state-of-the-art heterophilic datasets.

Community detection algorithms that analyze networks to identify communities of nodes are an essential part of the network analysis toolkit used daily by different analysts (e.g., data scientists and law enforcement). However, there is not enough awareness that members of a community$\mathscr {C}$(either revealed or not) inside a network$G$could act strategically to evade such tools either for legitimate (e.g., activist groups in authoritarian regimes) or malicious (e.g., terrorists) purpose. Community deception offers this possibility. By identifying a certain number of$\mathscr {C}$’s member connections to be rewired, community deception algorithms can successfully hide a community that wants to stay below the radar of detection techniques. However, the state-of-the-art deception approaches have focused on networks without attributes, although real-world networks (e.g., Facebook) include attributes (e.g., age and sex) that play a central role in detecting more accurate communities. This article faces three novel challenges introduced when designing deception techniques for networks with attributes. The first concerns how to model and encode attributes most flexibly. The second is about framing attribute-aware community deception as an optimization problem. Finally, the challenge of solving the optimization problem by leveraging network topology and attributes also arises. We leverage a simple way to model network attributes as edge weights, a novel optimization function called community diffusion, and Diffuser a greedy algorithm to optimize diffusion, to solve the above challenges. We evaluated Diffuser against several community detection algorithms and compared it with state-of-the-art deception approaches on various real-world networks. From the evaluation, we can draw two main observations. First, adopting attribute-oblivious deception techniques leads to unsatisfactory results. Second, community diffusion as an optimization function specific to attributed networks is preferred to community safeness, the state-of-the-art deception optimization function, even when recasting the latter as an attribute-aware function.

Recent research has highlighted the importance of maintaining user privacy on online social networks. Specifically, despite their appealing applications, community detection algorithms expose personal relationships that might be misused against social network members. This concern has opened a new research area called community deception, which is about hiding the members of a target community from community detection algorithms. State-of-the-art deception methods only look at how community members must perform edge updates to guarantee some level of hiding. This article introduces node-centric deception, a novel approach considering nodes entering and leaving a target community. We theoretically study the effect of node updates by leveraging node safeness as a deception optimization function. Based on this analysis, we present an effective heuristic capable of hiding the target community with minimal node operations. We evaluated our approach against several community detection algorithms and compared it with state-of-the-art deception algorithms with encouraging results.

Temporal changes in data set the need for the development of knowledge representation techniques able to capture these dynamics. Temporal Knowledge Graphs (TKGs) have emerged as a reference tool to represent dynamic, structured and machine-interpretable knowledge that evolves over time. However, characterizing the evolution of TKGs in a meaningful and human-understandable way remains a significant challenge. In this short paper, we argue that Linear Temporal Logic (LTL), with its expressive temporal constructs, is a promising approach for capturing a wide range of temporal behaviors and high-level evolutionary patterns occurring in TKGs.

Graph Neural Networks (GNNs) have become increasingly popular for their ability to capture complex relationships within graphs by aggregating node neighbor information. However, in graphs exhibiting high levels of heterophily relevant distant nodes are missed during neighbor aggregation, thus limiting the GNN performance in tasks like node classification. To tackle the problem of incorporating long-range relevant neighbors into the GNN node aggregation mechanism, this paper introduces the Overlay Graph Neural Networks (OGN) model. OGN is inspired by P2P overlay networks, where the idea is to find neighbor peers (nodes) that, although not directly connected to a given node (a peer), are semantically similar and could favorably improve both query routing and query results. In our context, the network is the graph, and the routing is the message passing a GNN performs to aggregate node features. OGN networks are built by stacking one or more overlay layers, each taking as input the graph and a node feature matrix either available or derivable (e.g., by analyzing the graph’s structure). Each overlay layer combines base embeddings, learned by considering node features and short-range node neighbors, with overlay embeddings computed by projecting nodes with similar features close in an overlay space and then aggregating (overlay) neighbor nodes via a sliding window attention mechanism. Base and overlay embeddings are combined to capture nodes’ immediate and global context in a graph. We evaluate OGN in a node classification task using state-of-the-art benchmarks and show that OGN is competitive with the advantage of being easily portable to any existing GNN model.

Techniques to hide a community from community detection algorithms are emerging as a new way to protect the privacy of users. Existing techniques either adapt optimization criteria derived from community detection (e.g., minimizing instead of maximizing modularity) or define new ones (e.g., community safeness) to identify a set of updates (e.g., edge addition/deletions) that deceive community detection algorithms from recovering the original structure of a target community C. However, all existing approaches do not take into account the fact that network's edges can be weighted to take into account node similarity or relation strength. The goal of this paper is to present SECRETORUM, a novel community deception approach for community deception in weighted networks.

Most of the existing deep-learning-based network analysis techniques focus on the problem of learning low-dimensional node representations. However, networks can also be seen in the light of edges interlinking pairs of nodes. The broad goal of this paper is to introduce a deep-learning framework focused on computing edge-centric network embeddings. We present a novel approach called ECNE, which instead of computing edge embeddings by aggregating node embeddings, computes them directly. ECNE leverages the notion of line graph of a graph coupled with an edge weighting mechanism to preserve the dynamic of the original graph in the line graph. We show that ECNE brings benefits wrt the state-of-the-art.

Graph embedding techniques allow to learn high-quality feature vectors from graph structures and are useful in a variety of tasks, from node classification to clustering. Existing approaches have only focused on learning feature vectors for the nodes and predicates in a knowledge graph. To the best of our knowledge, none of them has tackled the problem of directly learning triple embeddings. The approaches that are closer to this task have focused on homogeneous graphs involving only one type of edge and obtain edge embeddings by applying some operation (e.g., average) on the embeddings of the endpoint nodes. The goal of this paper is to introduce Triple2Vec, a new technique to directly embed knowledge graph triples. We leverage the idea of line graph of a graph and extend it to the context of knowledge graphs. We introduce an edge weighting mechanism for the line graph based on semantic proximity. Embeddings are finally generated by adopting the SkipGram model, where sentences are replaced with graph walks. We evaluate our approach on different real-world knowledge graphs and compared it with related work. We also show an application of triple embeddings in the context of user-item recommendations.

We present RARL, an approach to discover rules of the form body ⇒ head in large knowledge bases (KBs) that typically include a set of terminological facts (TBox) and a set of TBox-compliant assertional facts (ABox). RARL's main intuition is to learn rules by leveraging TBox-information and the semantic relatedness between the predicate(s) in the atoms of the body and the predicate in the head. RARL uses an efficient relatedness-driven TBox traversal algorithm, which given an input rule head, generates the set of most semantically related candidate rule bodies. Then, rule confidence is computed in the ABox based on a set of positive and negative examples. Decoupling candidate generation and rule quality assessment offers greater flexibility than previous work.

We tackle fact checking using Knowledge Graphs (KGs) as a source of background knowledge. Our approach leverages the KG schema to generate candidate evidence patterns, that is, schema-level paths that capture the semantics of a target fact in alternative ways. Patterns verified in the data are used to both assemble semantic evidence for a fact and provide a numerical assessment of its truthfulness. We present efficient algorithms to generate and verify evidence patterns, and assemble evidence. We also provide a translation of the core of our algorithms into the SPARQL query language. Not only our approach is faster than the state of the art and offers comparable accuracy, but it can also use any SPARQL-enabled KG.

In this paper, we research the community deception problem. Tackling this problem consists in developing techniques to hide a target community (C) from community detection algorithms. This need emerges whenever a group (e.g., activists, police enforcements, or network participants in general) want to observe and cooperate in a social network while avoiding to be detected. We introduce and formalize the community deception problem and devise an efficient algorithm that allows to achieve deception by identifying a certain number (b) of C's members connections to be rewired. Deception can be practically achieved in social networks like Facebook by friending or unfriending network members as indicated by our algorithm. We compare our approach with another technique based on modularity. By considering a variety of (large) real networks, we provide a systematic evaluation of the robustness of community detection algorithms to deception techniques. Finally, we open some challenging research questions about the design of detection algorithms robust to deception techniques.

The Semantic Web is commonly interpreted under the open-world assumption, meaning that information available (e.g., in a data source) captures only a subset of the reality. Therefore, there is no certainty about whether the available information provides a complete representation of the reality. The broad aim of this article is to contribute a formal study of how to describe the completeness of parts of the Semantic Web stored in RDF data sources. We introduce a theoretical framework allowing augmentation of RDF data sources with statements, also expressed in RDF, about their completeness. One immediate benefit of this framework is that now query answers can be complemented with information about their completeness. We study the impact of completeness statements on the complexity of query answering by considering different fragments of the SPARQL language, including the RDFS entailment regime, and the federated scenario. We implement an efficient method for reasoning about query completeness and provide an experimental evaluation in the presence of large sets of completeness statements.

The management of uncertainty is crucial when harvesting structured content from unstructured and noisy sources. Knowledge Graphs ( KGs ) are a prominent example. KGs maintain both numerical and non-numerical facts, with the support of an underlying schema. These facts are usually accompanied by a confidence score that witnesses how likely is for them to hold. Despite their popularity, most of existing KGs focus on static data thus impeding the availabilityof timewise knowledge. What is missing is a comprehensive solution for the management of uncertain and temporal data in KGs . The goal of this paper is to fill this gap. We rely on two main ingredients. The first is a numerical extension of Markov Logic Networks (MLNs) that provide the necessary underpinning to formalize the syntax and semantics of uncertain temporal KGs . The second is a set of Datalog constraints with inequalities that extend the underlying schema of the KGs and help to detect inconsistencies. From a theoretical point of view, we discuss the complexity of two important classes of queries for uncertain temporal KGs: maximuma-posteriori and conditional probability inference. Due to the hardness of these problems and the fact that MLN solvers do not scale well, we also explore the usage of Probabilistic Soft Logics (PSL) as a practical tool to support our reasoning tasks. We report on an experimental evaluation comparing the MLN and PSL approaches.

The management of uncertainty is crucial when harvesting structured content from unstructured and noisy sources. Knowledge Graphs ( kg s), maintaining both numerical and non-numerical facts supported by an underlying schema, are a prominent example. Knowledge Graph management is challenging because: (i) most of existing kg s focus on static data, thus impeding the availability of timewise knowledge; (ii) facts in kg s are usually accompanied by a confidence score, which witnesses how likely it is for them to hold. We demonstrate T e C o R e , a system for temporal inference and conflict resolution in uncertain temporal knowledge graphs ( utkg s). At the heart of T e C o R e are two state-of-the-art probabilistic reasoners that are able to deal with temporal constraints efficiently. While one is scalable, the other can cope with more expressive constraints. The demonstration will focus on enabling users and applications to find inconsistencies in utkg s. T e C o R e provides an interface allowing to select utkg s and editing constraints; shows the maximal consistent subset of the utkg , and displays statistics (e.g., number of noisy facts removed) about the debugging process.

We demonstrate RECAP, a tool that explains relatedness between entities in Knowledge Graphs (KGs) and implements a query by relatedness paradigm that allows to retrieve entities related to those in input. One of the peculiarities of RECAP is that it does not require any data preprocessing and can combine knowledge from multiple KGs. The underlying algorithmic techniques are reduced to the execution of SPARQL queries plus some local refinement. This makes the tool readily available on a large variety of KGs accessible via SPARQL endpoints. To show the general applicability of the tool, we will cover a set of use cases drawn from a variety of knowledge domains (e.g., biology, movies, co-authorship networks) and report on the concrete usage of RECAP in the SENSE4US FP7 project. We will underline the technical aspects of the system and give details on its implementation. The target audience of the demo includes both researchers and practitioners and aims at reporting on the benefits of RECAP in practical knowledge discovery applications.

We introduce Extended Property Paths (EPPs), a significant enhancement of SPARQL property paths. EPPs allow to capture in a succinct way a larger class of navigational queries than property paths. We present the syntax and formal semantics of EPPs and introduce two different evaluation strategies. The first is based on an algorithm implemented in a custom query processor. The second strategy leverages a translation algorithm of EPPs into SPARQL queries that can be executed on existing SPARQL processors. We compare the two evaluation strategies on real data to highlight their pros and cons.

We demonstrate S+EPPs, a system that provides fast construction of bisimulation summaries using graph analytics platforms, and then enhances existing SPARQL engines to support summary-based exploration and navigational query optimization. The construction component adds a novel optimization to a parallel bisimulation algorithm implemented on a multi-core graph processing framework. We show that for several large, disk resident, real world graphs, full summary construction can be completed in roughly the same time as the data load. The query translation component supports Extended Property Paths (EPPs), an enhancement of SPARQL 1.1 property paths that can express a significantly larger class of navigational queries. EPPs are implemented via rewritings into a widely used SPARQL subset. The optimization component can (transparently to users) translate EPPs defined on instance graphs into EPPs that take advantage of bisimulation summaries. S+EPPs combines the query and optimization translations to enable summary-based optimization of graph traversal queries on top of off-the-shelf SPARQL processors. The demonstration showcases the construction of bisimulation summaries of graphs (ranging from millions to billions of edges), together with the exploration benefits and the navigational query speedups obtained by leveraging summaries stored alongside the original datasets.

The Web of Linked Data is a huge graph of distributed and interlinked datasources fueled by structured information. This new environment calls for formal languages and tools to automatize navigation across datasources (nodes in such graph) and enable semantic-aware and Web-scale search mechanisms. In this article we introduce a declarative navigational language for the Web of Linked Data graph called N auti LOD. N auti LOD enables one to specify datasources via the intertwining of navigation and querying capabilities. It also features a mechanism to specify actions (e.g., send notification messages) that obtain their parameters from datasources reached during the navigation. We provide a formalization of the N auti LOD semantics, which captures both nodes and fragments of the Web of Linked Data. We present algorithms to implement such semantics and study their computational complexity. We discuss an implementation of the features of N auti LOD in a tool called swget, which exploits current Web technologies and protocols. We report on the evaluation of swget and its comparison with related work. Finally, we show the usefulness of capturing Web fragments by providing examples in different knowledge domains.

This paper presents GuLP a graph query language that enables to declaratively express preferences. Preferences enable to order the answers to a query and can be stated in terms of nodes/edge attributes and complex paths. We present the formal syntax and semantics of GuLP and a polynomial time algorithm for evaluating GuLP expressions. We describe an implementation of GuLP in the GuLP-it system, which is available for download. We evaluate the GuLP-it system on real-world and synthetic data.

This paper presents REWOrD, an approach to compute semantic relatedness between entities in the Web of Data representing real word concepts. REWOrD exploits the graph nature of RDF data and the SPARQL query language to access this data. Through simple queries, REWOrD constructs weighted vectors keeping the informativeness of RDF predicates used to make statements about the entities being compared. The most informative path is also considered to further refine informativeness. Relatedness is then computed by the cosine of the weighted vectors. Differently from previous approaches based on Wikipedia, REWOrD does not require any prepro- cessing or custom data transformation. Indeed, it can lever- age whatever RDF knowledge base as a source of background knowledge. We evaluated REWOrD in different settings by using a new dataset of real word entities and investigate its flexibility. As compared to related work on classical datasets, REWOrD obtains comparable results while, on one side, it avoids the burden of preprocessing and data transformation and, on the other side, it provides more flexibility and applicability in a broad range of domains.

The massive semantic data sources linked in the Web of Data give new meaning to old features like navigation; introduce new challenges like semantic specification of Web fragments; and make it possible to specify actions relying on semantic data. In this paper we introduce a declarative language to face these challenges. Based on navigational features, it is designed to specify fragments of the Web of Data and actions to be performed based on these data. We implement it in a centralized fashion, and show its power and performance. Finally, we explore the same ideas in a distributed setting, showing their feasibility, potentialities and challenges.

The increasing number of available online services demands distributed architectures to promote scalability as well as semantics to enable their precise and efficient retrieval. Two common approaches toward this goal are Semantic Overlay Networks (SONs) and Distributed Hash Tables (DHTs) with semantic extensions. This paper presents ERGOT, a system that combines DHTs and SONs to enable semantic-based service discovery in distributed infrastructures such as Grids and Clouds. ERGOT takes advantage of semantic annotations that enrich service specifications in two ways: (i) services are advertised in the DHT on the basis of their annotations, thus allowing to establish a SON among service providers, (ii) annotations enable semantic-based service matchmaking, using a novel similarity measure between service requests and descriptions. Experimental evaluations confirmed the efficiency of ERGOT in terms of accuracy of search and network traffic.

The soaring number of available online services calls for distributed architectures to promote scalability, fault- tolerance and semantics; to provide meaningful descriptions of services; and to support their efficient retrieval. Current approaches exploit either Semantic Overlay Networks (SONs) or Distributed Hash Tables (DHTs) sweetened with some ”semantic sugar.” SONs enable semantic driven query answering but are less scalable than DHTs, which on their turn, feature efficient but semantic-free query answering based on ”exact” match. This paper presents the ERGOT system combining DHTs and SONs to enable distributed and semantic-based service discovery. A preliminary evaluation of the system performance shows the suitability of the approach both in terms of recall and number of messages.