Search

Hyperspectral Imagery (HSI) onboard target classification is a frequently used technique in remote sensing. Due to the small volume of labelled data, the classification of HSI has been a challenging subject in recent study. The graph neural network (GNN) has become a popular method for semi-supervised classification, and its use with hyperspectral images has gained a lot of interest. A graph filter or single graph neural network has been typically employed in the earlier GNN-based approaches, and it is used to obtain HSI characteristics. It has not fully utilized the benefits of different graph filters or graph neural networks. The issue of oversmoothing also persists with the classical GNNs. We propose a spectral filter and an autoregressive moving average filter for the multi-graph neural network; (SAF-GNN) to address such drawbacks as the one mentioned above. The first is excellent at extracting the nodes' spectral characteristics, and the second is effective at suppressing graph distortion. With the help of performance measures like overall accuracy (OA), individual class accuracy (ICA), and Kappa coefficient (KC), the performance of the proposed method was compared to that of other state-of-the-art methods. The result shows that the SAF-GNN provides an improvement in OA, ICA and KC of 2.21%, 7.93% and 0.025 for the cuprite dataset and 4.84%, 11.78% and 0.025 for the Pavia University dataset, respectively. Comparison results show that the proposed method is suitable for remote target classification problem. [ABSTRACT FROM AUTHOR]

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares and has been the focus of extensive research ever since. Many conjectures in this area roughly say that "every edge coloured graph of a certain type contains a rainbow matching using every colour." In this paper we introduce a versatile "sampling trick," which allows us to asymptotically solve some well-known conjectures and to obtain short proofs of old results. In particular: |$\bullet $| We give the first asymptotic proof of the "non-bipartite" Aharoni–Berger conjecture, solving two conjectures of Aharoni, Berger, Chudnovsky, and Zerbib. |$\bullet $| We give a very short asymptotic proof of Grinblat's conjecture (first obtained by Clemens, Ehrenmüller, and Pokrovskiy). Furthermore, we obtain a new asymptotically tight bound for Grinblat's problem as a function of edge multiplicity of the corresponding multigraph. |$\bullet $| We give the first asymptotic proof of a 30-year-old conjecture of Alspach. |$\bullet $| We give a simple proof of Pokrovskiy's asymptotic version of the Aharoni–Berger conjecture with greatly improved error term. [ABSTRACT FROM AUTHOR]

Next point-of-interest (POI) recommendation is important for users to help them find interesting venues to visit in the near future. Most previous work on this subject has incorporated geographical and temporal information into sequential patterns to predict next POIs. However, few studies have considered the influence of important factors such as users' reviews or POIs' popularity on sequential patterns, nor distinguished between factors of different importance for prediction. In addition, the relationships between entities in location-based social networks have been ignored in most previous work. To overcome these limitations, we proposed a model called MGCAN to flexibly incorporate various influential factors into different sequential patterns for next POI recommendation. We first used multiple graph convolutional networks and independent attention networks to model multiple sequential patterns with different influential factors. Furthermore, we designed corresponding modules to simultaneously capture general preferences of users and determine the impact of different influential factors on each user. Finally, we used multiple sequential patterns and the general preferences of users in the prediction module to predict the next POI. Experimental results on two datasets showed that the MGCAN model achieved better recommendation performance than benchmark models. [ABSTRACT FROM AUTHOR]

Friend recommendation from user trajectory is a vital real-world application of location-based social networks (LBSN) services. Previous statistical analysis indicated that social network relationships could explain 10% to 30% of human movement, especially long-distance travel. Therefore, it is necessary to recognize patterns from human mobility to assist the friend recommendation. However, previous works either modelled friendships and check-in records by simple graphs with only one connection between any two nodes or ignored a large amount of vital spatio-temporal information and semantic information in raw LBSN data. To overcome the limitation of the simple graph commonly seen in previous works, we leverage heterogeneous multigraph to model LBSN data and define various semantic connections between nodes. Against this background, we propose a Heterogeneous Multigraph Contrastive Learning (HMGCL) model to capture spatio-temporal characteristics of human trajectories for user node embedding learning. Extensive experiments show that our method outperforms the state-of-the-art approaches in six real-world city datasets. [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a multigraph. The cover index ε(G) of G is the greatest integer k for which there is a coloring of E with k colors such that each vertex of G is incident with at least one edge of each color. Let δ (G) be the minimum degree of G, and let Φ (G) be the codensity of G, defined by Φ (G) =min... where E+(U) is the set of all edges of G with at least one end in U. It is easy to see that ε (G) ≤ min{ δ (G),Φ (G)}. In 1978, Gupta proposed the following codensity conjecture: Every multigraph G satisfies ε (G) ≥ min{ δ (G) 1,Φ (G)}, which is the dual version of the Goldberg--Seymour conjecture on edge-colorings of multigraphs. In this note, we prove that ε (G) ≥ min{ δ (G) 1, ⌊ Φ (G)⌊ } if Φ (G) is not integral and ε (G) ≥ min{ δ (G) 2, ⌊ Φ (G)⌊ 1} otherwise. We also show that this codensity conjecture implies another conjecture concerning the cover index made by Gupta in 1967. [ABSTRACT FROM AUTHOR]

The final model for rail transportation is the introduction of full digitalization to support communication and transport services, which will be available to the public in the future. The process of digitalization is based on models that reproduce the real physical structures present in the transport network. Due to the high complexity of the structure and its mapping, it is necessary to find methods that automatically verify the proposed created model. This approach supports manual activities that, at this moment, are not sufficient. Automatization's description requires a formal approach. Such a description has been developed as part of a research project, "The Digital Railway. The digital twin of the ETCS application. Virtual prototyping and simulation of operational scenarios." In this paper, a formal model of the ETCS application has been proposed, and a formal approach to its verification is described. [ABSTRACT FROM AUTHOR]

Networks are now widely used to represent, quantify and model animal behaviour. These approaches have proved valuable in linking individual behaviours to emergent population level patterns and quantifying the implications of these population structures for wider ecological and evolutionary processes. However, there are diverse conceptual representations of network data and choosing the right tool to answer a particular question can be challenging. Here I provide an overview of different network representations, highlighting their potential applications in behavioural ecology and drawing attention to key resources to help with their implementation. My aim is to provide an accessible guide that helps behavioural ecologists take full advantage of the potential of the different ways in which their data can be used to generate social other networks. • A guide of different approaches to represent animal social network data. • An overview of how to employ and when best to use different network representations. • Introduction to less used methods such as multigraphs, and signed and ego networks. • Case study showing association data as bipartite, dyadic and higher-order networks. [ABSTRACT FROM AUTHOR]

A random two-cell embedding of a given graph $G$ is obtained by choosing a random local rotation around every vertex. We analyse the expected number of faces of such an embedding, which is equivalent to studying its average genus. In 1991, Stahl [5] proved that the expected number of faces in a random embedding of an arbitrary graph of order $n$ is at most $n\log (n)$. While there are many families of graphs whose expected number of faces is $\Theta (n)$ , none are known where the expected number would be super-linear. This led the authors of [1] to conjecture that there is a linear upper bound. In this note we confirm their conjecture by proving that for any $n$ -vertex multigraph, the expected number of faces in a random two-cell embedding is at most $2n\log (2\mu)$ , where $\mu$ is the maximum edge-multiplicity. This bound is best possible up to a constant factor. [ABSTRACT FROM AUTHOR]

Let K = K(a, p; λ1, λ2) be the multigraph with: the number of parts equal to p; the number of vertices in each part equal to a; the number of edges joining any two vertices of the same part equal to λ1; and the number of edges joining any two vertices of different parts equal to λ2. The existence of C4-factorizations of K has been settled when a is even; when a ≡ 1 (mod 4) with one exception; and for very few cases when a ≡ 3 (mod 4). The existence of Cz-factorizations of K has been settled when a ≡ 1 (mod z) and λ1 is even, and when a ≡ 0 (mod z). In this paper, we give a construction for Cz-factorizations of K for z = 2a when a is even. [ABSTRACT FROM AUTHOR]

Taxi demand prediction is essential to build efficient traffic transportation systems for smart city. It helps to properly allocate vehicles, ease the traffic pressure and improve passengers' experience. Traditional taxi demand prediction methods mostly rely on time-series forecasting techniques, which cannot model the nonlinearity embedded in data. Recent studies start to combine the Euclidean spatial features through grid-based methods. By considering the spatial correlations among different regions, we can capture how the temporal events have impacts on those with adjacent links or intersections and improve prediction precision. Some graph-based models are proposed to encode the non-Euclidean correlations as well. However, the temporal periodicity of data is often overlooked, and the study units are usually constructed as oversimplified grids. In this paper, we define places with specific semantic and humanistic experiences as study units, using a fuzzy set method based on adaptive kernel density estimation. Then, we introduce dual temporal gated multi-graph convolution network to predict the future taxi demand. Specifically, multi-graph convolution is used to model spatial correlations with graphs, including the neighborhood, functional similarities and landscape similarities based on street view images. As for the temporal dependencies modeling, we design the dual temporal gated branches to capture information hidden in both previous and periodic observations. Experiments on two real-world datasets show the effectiveness of our model over the baselines. [ABSTRACT FROM AUTHOR]

Let D = (d 1 , d 2 , ... , d n) and F = (f 1 , f 2 , ... , f n) be two sequences of positive integers. We consider the following decision problems: is there a (i) multigraph, (i i) loopless multigraph, (i i i) simple graph, (i v) cycle-free graph (forest or tree), (v) caterpillar G = (V , E) such that for all k , d (v k) = d k and ∑ w ∈ N (v k) d (w) = f k (d (v) is the degree of v and N (v) is the set of neighbors of v). Here we show that all these decision problems can be solved in polynomial time if Δ ≔ max k d k is bounded. The problems are converted into an integer programming feasibility problem in which both the number of variables and the number of inequalities depend only on Δ but not on n. The problem is motivated by NMR spectroscopy of hydrocarbons. The algorithm has been implemented in the ZIMPL language, and its applicability is demonstrated on trees up to n = 1000 vertices. The average reconstruction time for trees with 1000 vertices is still less than 40 ms. [ABSTRACT FROM AUTHOR]

We present a stock index prediction model based on a multi-time scale learning (MTSL) and the multi-graph attention network (MGAT) approach. Instead of dealing with individual stock markets, we consider a group of stock markets simultaneously and exploit the effects of their interactions when making predictions. Our model consists of a boosting Hodrick-Prescott (bHP) filter and MGATs, along with MTSL processes. The bHP filter decomposes the stock index series into the slow-varying growth trend and the fast-varying cyclical volatility for training the MGAT to facilitate the learning of multi-time scale data. The MGAT exploits the interplays of stock markets with three different types of graphs: a regionality graph that qualitatively describes the linkages among stock markets within the same region or similar financial systems; a correlativity graph that quantifies the Pearson correlation between stock markets; and a causality graph that measures the convergence cross mapping (CCM) causality between stock markets. Particularly, the last graph is essentially a directed graph, which captures the nonreciprocal relationship between different stock markets. Experimental results on real stock indices reveal the effectiveness and merit of the proposed model in comparison with other models adopted in this paper. [ABSTRACT FROM AUTHOR]

The aim of this manuscript is to prove some new fixed-point results for the two families of multivalued dominated-contractive maps defined on a closed ball in a complete multiplicative-metric space. The fixed-point theorems for multigraph-dominated maps are established. We also investigate the existence of fixed points of the two families of graphic contractions in a multiplicative-metric space. For illustration, an example is provided to clarify that the hypothesis of the obtained result is valid. Moreover, the applications of the obtained results to show the existence of solutions to the coupled systems of nonlinear Volterra-type integral equations and mappingal equations are presented as a confirmation of the novelty of our results. [ABSTRACT FROM AUTHOR]

We introduce first the spanning simplicial complex (SSC) of a multigraph G , which gives a generalization of the SSC associated with a simple graph G. Combinatorial properties are discussed for the SSC of a family of uni-cyclic multigraphs U n , m r with n edges including r multiple edges within and outside the cycle of length m , which are then used to compute the f -vector and Hilbert series of face ring k [ Δ s (U n , m r) ] for the SSC Δ s (U n , m r). Moreover, we find the associated primes of the facet ideal I F (Δ s (U n , m r)). Finally, we device a formula for homology groups of Δ s (U n , m r) and prove that the SSC of a family of uni-cyclic multigraphs is Cohen-Macaulay. [ABSTRACT FROM AUTHOR]

Traffic forecasting has always been an important part of intelligent transportation systems. At present, spatiotemporal graph neural networks are widely used to capture spatiotemporal dependencies. However, most spatiotemporal graph neural networks use a single predefined matrix or a single self-generated matrix. It is difficult to obtain deeper spatial information by only relying on a single adjacency matrix. In this paper, we present a progressive multi-graph convolutional network (PMGCN), which includes spatiotemporal attention, multi-graph convolution, and multi-scale convolution modules. Specifically, we use a new spatiotemporal attention multi-graph convolution that can extract extensive and comprehensive dynamic spatial dependence between nodes, in which multiple graph convolutions adopt progressive connections and spatiotemporal attention dynamically adjusts each item of the Chebyshev polynomial in graph convolutions. In addition, multi-scale time convolution was added to obtain an extensive and comprehensive dynamic time dependence from multiple receptive field features. We used real datasets to predict traffic speed and traffic flow, and the results were compared with a variety of typical prediction models. PMGCN has the smallest Mean Absolute Error (MAE), Root Mean Squared Error (RMSE), and Mean Absolute Percentage Error (MAPE) results under different horizons (H = 15 min, 30 min, 60 min), which shows the superiority of the proposed model. [ABSTRACT FROM AUTHOR]

Unitary coined discrete-time quantum walks (UCDTQW) constitute a universal model of computation, meaning that any computation done by a general purpose quantum computer can either be done using the UCDTQW framework. In the last decades, great progress has been made in this field by developing quantum walk-based algorithms that can outperform classical ones. However, current quantum computers work based on the quantum circuit model of computation, and the general mapping from one model to the other is still an open problem. In this work, we provide a matrix analysis of the unitary evolution operator of UCDTQW, which is composed at a time of a shift and a coin operators. We conceive the shift operator of the system as the unitary matrix form of the adjacency matrix associated with the graph on which the UCDTQW takes place, and provide a set of equations to transform the latter into the former and vice versa. However, this mapping modifies the structure of the original graph into a directed multigraph, by splitting single edges and arcs of the original graph into multiple arcs. Thus, the fact that any unitary operator has a quantum circuit representation means that any adjacency matrix that complies with the transformation equations will be automatically associated with a quantum circuit, and any quantum circuit acting on a bipartite system will be always associated with a directed multigraph. Finally, we extend the definition of the coin operator to a superposition of coins in such a way that each coin acts on different vertices of the directed multigraph on which the UCDTQW takes place, and provide a description of how this can be implemented in circuit form. [ABSTRACT FROM AUTHOR]

The prevalence of location-based social networks (LBSNs) provides an opportunity for human mobility behavior understanding and prediction. However, data quality issues (e.g., historical check-in POI missing, data sparsity) always limit the effectiveness of existing LBSN-oriented studies, e.g., next Point-of-Interest (POI) recommendation or prediction. In contrast to previous efforts in the above study, we focus on identifying missing POIs that the user has visited at a past specific time and develop a category-aware multigraph embedding (CAME) model. Specifically, CAME jointly captures temporal cyclic effect, user preference, and sequential transition pattern in a unified way by embedding five relational information graphs into a shared dimensional space from both POI- and category-instance levels. The proposed model also incorporates region-level spatial proximity to explore the geographical influence and derives the ranking score list of candidates for missing POI identification. Extensive experiments against state-of-the-art methods are conducted on two real datasets, and the experimental results show its superiority over other competitors. Significantly, the proposed model can be naturally extended to next POI recommendation and prediction tasks with competitive performances. [ABSTRACT FROM AUTHOR]

Graph theory has a significant impact and is crucial in the structure of many real-life situations. To simulate uncertainty and ambiguity, many extensions of graph theoretical notions were created. Planar graphs play a vital role in modelling which has the property of non-crossing edges. Although crossing edges benefit, they have some drawbacks, which paved the way for the introduction of planar graphs. The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph. The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs. The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs, a conceptual blending of Pythagorean Neutrosophic and Planar graphs. The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations. This paper investigates the Pythagorean Neutrosophic planar values, which form the edges of the Pythagorean neutrosophic graphs. The concept of Pythagorean Neutrosophic dual graphs, isomorphism, co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs. A decision-making algorithm was proposed with a numerical illustration by using the Pythagorean Neutrosophic fuzzy graph. [ABSTRACT FROM AUTHOR]

Mining frequent patterns in multigraphs is a challenging task in graph analysis with numerous real-world applications. This paper introduces a novel framework for frequent pattern mining on multi-graphs using the multi-SPMiner method. The approach is inspired by SPMiner, which was the first approach to employ deep learning in graph motif mining tasks. Multi-SPMiner builds on this foundation and focuses on the extraction of frequent motifs in single multi-graphs, specifically spatiotemporal graphs. Multi-SPMiner employs a two-step approach to extract the most frequent motifs in a graph with a high support value. In the first step, it embeds the nodes into an embedding order space, and in the second step, it performs a walk in the space to obtain the frequent motifs by iteratively growing the motif starting from a single node. The results obtained highlight the effectiveness of the proposed approach in identifying frequent motifs in single multigraphs, which is a crucial task in many real-world applications. Moreover, we demonstrate that our method is a generalization of SPMiner by testing it on single connection graphs. [ABSTRACT FROM AUTHOR]

A multigraph is a graph with possible multiple edges, but no loops. Let t be a positive integer. Let G t be the set of simple graphs (or multigraphs) such that for each G ∈ G t there exist at least t + 1 non-empty disjoint proper subsets V 1 , V 2 , ... , V t + 1 ⊆ V (G) satisfying V (G) ∖ (V 1 ∪ V 2 ∪ ⋯ ∪ V t + 1) ≠ ϕ and edge connectivity κ ′ (G) = e (V i , V (G) ∖ V i) for i = 1 , 2 , ... , t + 1. Let D (G) and A (G) denote the degree diagonal matrix and adjacency matrix of a simple graph (or a multigraph) G , and let μ i (G) be the i th largest eigenvalue of the Laplacian matrix L (G) = D (G) + A (G). In this paper, we investigate the relationship between μ n − 2 (G) and edge connectivity or spanning tree packing number of a graph G ∈ G 1 , respectively. We also give the relationship between μ n − 3 (G) and edge connectivity or spanning tree packing number of a graph G ∈ G 2 , respectively. Moreover, we generalize all the results about L (G) to a more general matrix a D (G) + A (G) , where a is a real number with a ≥ − 1. [ABSTRACT FROM AUTHOR]

The rise of battery-powered vehicles has led to many new technical and methodological hurdles. Among these, the efficient planning of an electric fleet to fulfill passenger transportation requests still represents a major challenge. This is because of the specific constraints of electric vehicles, bound by their battery autonomy and necessity of recharge planning, and the large scale of the operations, which challenges existing optimization algorithms. The purpose of this paper is to introduce a scalable column generation approach for routing and scheduling in this context. Our algorithm relies on four main ingredients: (i) a multigraph reformulation of the problem based on a characterization of nondominated charging arcs, (ii) an efficient bidirectional pricing algorithm using tight backward bounds, (iii) sparsification approaches permitting to decrease the size of the subjacent graphs dramatically, and (iv) a diving heuristic, which locates near-optimal solutions in a fraction of the time needed for a complete branch-and-price. Through extensive computational experiments, we demonstrate that our approach significantly outperforms previous algorithms for this setting, leading to accurate solutions for problems counting several hundreds of requests. Funding: This work was supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 08528/2018-2 and 315361/2020-4], Coordenação de Aperfeiçoamento de Pessoal de Nível Superior [Finance Code 001], and Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro [Grants E-26/010.002232/2019 and E-26/202.790/2019]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.1199. [ABSTRACT FROM AUTHOR]

Traffic speed prediction is a crucial task of the intelligent traffic system. However, due to the highly nonlinear temporal patterns and non-static spatial dependence of traffic data, timely and accurate traffic forecasting remains a challenge. The existing methods usually use a static adjacency matrix to model spatial dependence while ignoring the spatial dynamic characteristics of the road network.Meanwhile, the dynamic influence of different time steps on the prediction target is ignored. Thus, we propose a dynamic multi-graph convolution recurrent neural network (DMGCRNN), which models the dynamic correlations of road networks over time based on various information of road network. Dynamic correlation is an essential factor for accurate traffic prediction, because it reflects the change of the traffic conditions in real-time. In this model, we design a dynamic graph construction method, which utilizes the local temporal and spatial characteristics of each road segment to construct dynamic graphs. Then, a dynamic multi-graph convolution fusion module is proposed, which considers the dynamic characteristics of spatial correlations and global information to model the dynamic trend of spatial dependence. Moreover, by combing the global context information, temporal attention is provided to capture the dynamic temporal dependence among different time steps. The experimental results from two real-world traffic datasets demonstrate that our method outperforms the state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Summary: Parallelization is an optimization technique that is playing an increasingly vital role in software applications. Discovering the potential parallelism in sequential programs is of primary importance for parallelization. To this end, various tools have been created to obtain parallelizable targets by analyzing the dependencies in sequential programs. However, the majority are constructed based on manually designed dependence analysis rules. Consequently, they must follow some constraints, which limit the scope of their program analysis capability. Furthermore, constructing a dependency analysis rule is a complicated and highly sophisticated endeavor. In this study, we exploit the fact that neural network models can learn the potential features of programs to tackle the parallelism discovery task in an end‐to‐end manner. Specifically, we developed a multigraph learning architecture on top of multiple abstract code representations in a complementary manner. In the architecture, we equip code representations with different neural network models in a targeted manner, including a deep convolutional neural network for analyzing both control and data flows and a novel neural network for learning the abstract syntax trees. Experimental results obtained on a common parallelism discovery dataset indicate that the developed multigraph learning architecture can learn potential parallelism patterns in sequential programs with high accuracy and efficiency. [ABSTRACT FROM AUTHOR]

We consider the problem of optimal distribution of assignments between workers on machines. Workers can exchange machines with the aim of saving the total time to execute the assignments, compared to their initial distribution. It is proved that the corresponding cooperative game has a non-empty c-core and is totally balanced. Based on the Hungarian method of solving the assignment problem, an algorithm for constructing an imputation from the c-core is formulated. In the case of an integer characteristic function, the algorithm constructs an imputation from the c-core with integer components. This result is generalized to the case of arbitrary totally balanced games of three and four persons, as well as for symmetric games. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the concept of using multiple parameters to find the optimal path in the multigraph. Multiple parameters indicate the number of parameters used in compiling a network. To be compiled into an edge weight of a multigraph involves converting the parameters into the same quantity without losing meaning. Here, the interval-valued intuitionistic fuzzy approach is used to perform the conversion. We will obtain the optimal multigraph path using a multiple-parameter transportation problem. [ABSTRACT FROM AUTHOR]

A new mathematical model of transportation along the transport network represented by an undirected multigraph is formulated. A new criterion for the optimality of cargo carriages schedule is proposed. The criterion in addition to the time characteristics of transportation includes their cost, the number of undelivered cargoes. The problem to find the optimal schedule is formulated as a problem of mixed integer linear programming. Various variants of the algorithm for searching for an approximate solution to the problem are proposed. Informative examples are considered. [ABSTRACT FROM AUTHOR]

The Goldberg–Seymour Conjecture for f $f$‐colorings states that the f $f$‐chromatic index of a loopless multigraph is essentially determined by either a weighted maximum degree or a weighted maximum density parameter. We introduce an oriented version of f $f$‐colorings, where now each color class of the edge‐coloring is required to be orientable in such a way that every vertex v $v$ has indegree and outdegree at most some specified values g(v) $g(v)$ and h(v) $h(v)$. We prove that the associated (g,h) $(g,h)$‐oriented chromatic index satisfies a Goldberg–Seymour formula. We then present simple applications of this result to variations of f $f$‐colorings. In particular, we show that the Linear Arboricity Conjecture holds for k $k$‐degenerate loopless multigraphs when the maximum degree is at least 4k−2 $4k-2$, improving a recent bound by Chen, Hao, and Yu for simple graphs. Finally, we demonstrate that the (g,h) $(g,h)$‐oriented chromatic index is always equal to its list coloring analogue. [ABSTRACT FROM AUTHOR]

The European Railway Agency has formulated assumptions for a target model of rail transport. Its important premise is digitalization to support the communication and transport services that the railways will make available to the public in the future. Part of the digitalization process is the digital description of the railway infrastructure in a formalized form to allow algorithmic processing. The formal description of infrastructure is not a new issue. However, attempts made so far have not resulted in a permanent definition of a generally accessible formalism allowing for a coherent representation of the physical railway infrastructure in a digital form. This paper presents the results of work carried out within the research project Digital Railway-The Digital Twin of the ETCS Application-Virtual Prototyping and Simulation of Operational Scenarios. [ABSTRACT FROM AUTHOR]

Graph contrastive learning has been successfully applied in text classification due to its remarkable ability for self-supervised node representation learning. However, explicit graph augmentations may lead to a loss of semantics in the contrastive views. Secondly, existing methods tend to overlook edge features and the varying significance of node features during multi-graph learning. Moreover, the contrastive loss suffer from false negatives. To address these limitations, we propose a novel method of contrastive multi-graph learning with neighbor hierarchical sifting for semi-supervised text classification, namely ConNHS. Specifically, we exploit core features to form a multi-relational text graph, enhancing semantic connections among texts. By separating text graphs, we provide diverse views for contrastive learning. Our approach ensures optimal preservation of the graph information, minimizing data loss and distortion. Then, we separately execute relation-aware propagation and cross-graph attention propagation, which effectively leverages the varying correlations between nodes and edge features while harmonizing the information fusion across graphs. Subsequently, we present the neighbor hierarchical sifting loss (NHS) to refine the negative selection. For one thing, following the homophily assumption, NHS masks first-order neighbors of the anchor and positives from being negatives. For another, NHS excludes the high-order neighbors analogous to the anchor based on their similarities. Consequently, it effectively reduces the occurrence of false negatives, preventing the expansion of the distance between similar samples in the embedding space. Our experiments on ThuCNews, SogouNews, 20 Newsgroups, and Ohsumed datasets achieved 95.86%, 97.52%, 87.43%, and 70.65%, which demonstrates competitive results in semi-supervised text classification. • A novel graph-based method for semi-supervised text classification. • A multi-relational text graph based on multiple semantic associations among documents. • A multi-graph learning method consisting of the proposed RW-GCN and CGAN. • A graph contrastive learning approach with neighbor hierarchical sifting strategy. [ABSTRACT FROM AUTHOR]

For the application of social item recommendation, how to effectively dig out the implicit relationships between different items plays a crucial role in its performance. However, existing social item recommendation systems constructed their item graphs using a static method based on item features. Considering the fact that most items, such as live streams, can hardly be characterized with limited number of feature tags in reality, the static construction methods make it hard to accurately grasp the underlying item–item relationships. To address the problem, we propose an item graph generation method based on Recommendation Feedback and Dynamic Adaptive Training (RFDAT) to achieve an efficient social item recommendation. Specifically, a multi-task learning technique is leveraged to concurrently predict the item graph and user–item interaction graph, allowing the recommendation task itself to directly participate in the dynamic construction process of the item graph, which is adaptively constructed based on feedback from recommendation results iteratively during the training procedure. Compared with the static construction methods, this allows us to fully explore item–item relationships and item feature representations, therefore improving recommendation accuracy. Furthermore, a lightweight graph convolutional denoising and fusion method based on Laplacian smoothing filter is employed to achieve deep interaction and fusion among multi-graph features, and effectively mitigate the influence of noise in the process of feature learning. Finally, extensive experimental results on four public datasets show that compared with eight state-of-the-art methods, our proposed method achieves improvements of 4.97%, 2.90%, 2.03%, and 4.82% in the important evaluation metric NDCG@10 on Yelp, Ciao, LastFM, and Douban datasets, respectively. It also illustrates very competitive performance against these baselines in the recommendation accuracy for cold users and the recommendation rate for cold items. • A novel framework based on recommendation feedback and dynamic item graph generation. • An MTL learning approach to dynamic adaptive training for social item recommendation. • A LSGC-based embedding propagation approach for multi-graph feature fusion. • Extensive experiments were made to validate the efficacy of the proposed method. [ABSTRACT FROM AUTHOR]

Convolutional neural networks (CNNs) have shown remarkable performance in the field of infrared small target detection. However, due to the limitation of local receptive field, existing methods find it challenging to effectively model the contextual information associated with small targets. In this paper, we propose a Graph-based Context Learning Network (GCLNet) that addresses this issue by integrating global graph reasoning with local feature learning to perceive context information across multiple scales. Specifically, local feature learning blocks are embedded into the encoder to extract detailed textures that are crucial for small targets detection. At deep layers, the multiple graph reasoning module leverages a multi-graph interaction structure to promote significant information transfer, allowing for the optimization of global context learning. Moreover, the patch-based graph reasoning module divides the low-level features into multiple patches where the context information is explored to capture the saliency of small targets. The experimental results demonstrate that the proposed method outperforms the state-of-the-art methods, achieving the intersection over union (IoU) of 80.26% and 94.84% on the NUAA-SIRST and NUDT-SIRST datasets, respectively. Our code will be available at https://github.com/studymonster0/GCLNet. [ABSTRACT FROM AUTHOR]

We compare the topological Milnor fibration and the motivic Milnor fibre of a regular complex function with only normal crossing singularities by introducing their common extension: the complete Milnor fibration. We give two equivalent constructions: the first one extending the classical Kato–Nakayama log-space, and the second one, more geometric, based on the real oriented multigraph construction, a version of the real oriented deformation to the normal cone. As an application, we recover A'Campo's model of the topological Milnor fibration, by quotienting the motivic Milnor fibration with suitable powers of R > 0 , and show that it determines the classical motivic Milnor fibre. We also give precise formulae expressing how the introduced objects change under blowings-up. As an application, we show that the motivic Milnor fibre is well-defined as an element of a suitable Grothendieck ring without requiring that the Lefschetz motive be invertible. [ABSTRACT FROM AUTHOR]

Recently, recommending bundles - sets of items that complement each other - instead of individual items to users has drawn much attention in both academia and industry. Models based on Graph Neural Networks (GNNs) for bundle recommendation have achieved great success in capturing users' preferences by modeling pairwise correlations among users, bundles, and items via information propagation on graphs. However, a notable limitation lies in their insufficient focus on explicitly modeling intricate ternary relationships. Additionally, the loose combination of node embeddings from different graphs tends to introduce noise, as it fails to consider disparities among the graphs. To this end, we propose a novel approach called Adaptive Multi-Graph Contrastive Learning for Bundle Recommendation (AMCBR). Specifically, AMCBR models ternary interactions by constructing multiple graphs, including a bundle preference graph based on direct user-bundle interactions, a collaborative neighborhoods graph featuring user-level and bundle-level subgraphs, and an item-level preference hypergraph capturing indirect user-bundle relationships through items. Then, (hyper)graph convolution is applied to each (hyper)graph to encode diverse potential preferences into node embeddings. To enhance the model's robustness, an adaptive aggregation module is employed to assign varying weights to node embeddings from different graphs during the fusion process, which enriches the semantic and comprehensive information in the embeddings while mitigating potential noise. Finally, a contrastive learning strategy is proposed to jointly optimize the model, strengthening collaborative links between individual graphs. Extensive experiments on three real datasets demonstrate that AMCBR can outperform the state-of-the-art baselines on the Top-K recommendations. [Display omitted] • Three different graphs are constructed to model complex relationships. • We use a hypergraph to capture the higher-order relation between users and bundles. • The adaptive aggregation module can allocate varied weights to node representations. • Multi-graph contrastive learning can strengthen the graphs' collaborative connection. [ABSTRACT FROM AUTHOR]

• A data-driven machine learning framework is presented for radius prediction in three-roller bending of thin-walled parts. • Graph-based analysis for coupling relationships between various influence factors through multi-graph attention mechanism. • In-depth exploration for cumulative deformation law between multiple passes through temporal convolutional network. Three-roller bending is the key production process for aerospace products, which forms thin-walled parts into a curved shape with a specific radius through multiple passes of these parts between loaded rollers. Radius prediction is of great importance for reasonable bending process control for desired curves. However, due to the various influence factors and the complicated interaction between successive passes, it prevents high accuracy of radius prediction. The prediction model based on multi-graph attention temporal convolutional network is therefore proposed to deal with these challenges. First, multiple graphs are constructed from multi-pass observations from three-roller bending process, with each graph representing the influencing factors of a specific pass. Second, graph attention mechanism explores the coupling effects of influence factors on the radius and realizes the extraction of key factors for each graph. Third, temporal convolutional network reveals the interaction between successive passes by establishing the connection between different graphs, and provides the radius prediction at each pass. In comparative experiments based on simulated data and experimental data collected from real cases, the results demonstrate the higher prediction accuracy of the proposed method over traditional methods. [ABSTRACT FROM AUTHOR]

Predicting drug–drug interactions (DDIs) is crucial for understanding and preventing adverse drug reactions (ADRs). However, most existing methods inadequately explore the interactive information between drugs in a self-supervised manner, limiting our comprehension of drug–drug associations. This paper introduces EDDINet : E nhancing D rug- D rug I nteraction Prediction via Information Flow and Consensus-Constrained Multi-Graph Contrastive Learning for precise DDI prediction. We first present a cross-modal information-flow mechanism to integrate diverse drug features, enriching the structural insights conveyed by the drug feature vector. Next, we employ contrastive learning to filter various biological networks, enhancing the model's robustness. Additionally, we propose a consensus regularization framework that collaboratively trains multi-view models, producing high-quality drug representations. To unify drug representations derived from different biological information, we utilize an attention mechanism for DDI prediction. Extensive experiments demonstrate that EDDINet surpasses state-of-the-art unsupervised models and outperforms some supervised baseline models in DDI prediction tasks. Our approach shows significant advantages and holds promising potential for advancing DDI research and improving drug safety assessments. Our codes are available at: https://github.com/95LY/EDDINet_code. • EDDINet is proposed via Information Flow and Consensus-Constrained Multi-Graph Contrastive Learning. • Introduce the cross-modal information-flow mechanism to facilitate the information across various drug features. • EDDINet surpasses state-of-the-art unsupervised models and even outperforms some supervised baseline models in DDI prediction tasks. [ABSTRACT FROM AUTHOR]

Motivated by the critical need for unmanned aerial vehicles (UAVs) to patrol grid systems in hazardous and dynamically changing environments, this study addresses a routing problem aimed at minimizing the time-average Age of Information (AoI) for edges in general graphs. We establish a lower bound for all feasible patrol policies and demonstrate that this bound is tight when the graph contains an Eulerian cycle. For graphs without Eulerian cycles, it becomes challenging to identify the optimal patrol strategy due to the extensive range of feasible options. Our analysis shows that restricting the strategy to periodic sequences still results in an exponentially large number of possible strategies. To address this complexity, we introduce two polynomial-time approximation schemes, each involving a two-step process: constructing multigraphs first and then embedding Eulerian cycles within these multigraphs. We prove that both schemes achieve an approximation ratio of 2. Further, both analytical and numerical results suggest that evenly and sparsely distributing edge visits within a periodic route significantly reduces the average AoI compared to strategies that merely minimize the route travel distance. Building on this insight, we propose a heuristic method that not only maintains the approximation ratio of 2 but also ensures robust performance across varying random graphs. • Age of Information for edges in general graphs is rigorously defined. • A lower bound for all the feasible policies is derived. • Two approximation schemes that achieve an approximation ratio of 2 are provided. • A heuristic approach that has an approximation ratio of 2 and robust average performance is provided. [ABSTRACT FROM AUTHOR]

Let ℓ and p be two distinct primes. We study the p-adic valuation of the number of spanning trees in an abelian ℓ -tower of connected multigraphs. This is analogous to the classical theorem of Washington–Sinnott on the growth of the p-part of the class group in a cyclotomic Z ℓ -extension of abelian extensions of Q . Furthermore, we show that under certain hypotheses, the number of primes dividing the number of spanning trees is unbounded in such a tower. [ABSTRACT FROM AUTHOR]

Accurate passenger flow forecasting in urban rail transit (URT) could provide a vital reference for operators' timely operation management. However, due to the enormous scale of the metro network, it is unwise to forecast passenger flows at the station scale individually. In this paper, a forecasting framework is proposed for network-scale forecasting tasks considering both accuracy and efficiency. There are mainly three stages in the forecasting framework. Firstly, three kinds of similarity measurements are presented regarding the adjacent similarity, geographic location similarity, and trend similarity. Secondly, three similarity graphs are formed by combining the three kinds of similarity measurements and flow time series. Thirdly, the multigraph network is applied to perform passenger flow forecasting. The experimental results indicated that the proposed method performs relatively accurately for the network-scale prediction with economic time costs. Specifically, the proposed model could acquire the feasible forecasts compared with the best disaggregate model using less than half of calculation costs, and above 10% reduction in root-mean squared error (RMSE) compared with the best aggregate model in the benchmark trials. Extensive contrast experiments were conducted to investigate the sensitivity and interpretability of the proposed model. [ABSTRACT FROM AUTHOR]

Consider the switch chain on the set of d-regular bipartite graphs on n vertices with 3 ≤ d ≤ n c , for a small universal constant c > 0 . We prove that the chain satisfies a Poincaré inequality with a constant of order O(nd); moreover, when d is fixed, we establish a log-Sobolev inequality for the chain with a constant of order O d (n log n) . We show that both results are optimal. The Poincaré inequality implies that in the regime 3 ≤ d ≤ n c the mixing time of the switch chain is at most O ( (n d) 2 log (n d)) , improving on the previously known bound O ( (n d) 13 log (n d)) due to Kannan et al. (Rand Struct Algorithm 14(4):293–308, 1999) and O (n 7 d 18 log (n d)) obtained by Dyer et al. (Sampling hypergraphs with given degrees (preprint). arXiv:2006.12021). The log-Sobolev inequality that we establish for constant d implies a bound O (n log 2 n) on the mixing time of the chain which, up to the log n factor, captures a conjectured optimal bound. Our proof strategy relies on building, for any fixed function on the set of d-regular bipartite simple graphs, an appropriate extension to a function on the set of multigraphs given by the configuration model. We then establish a comparison procedure with the well studied random transposition model in order to obtain the corresponding functional inequalities. While our method falls into a rich class of comparison techniques for Markov chains on different state spaces, the crucial feature of the method—dealing with chains with a large distortion between their stationary measures—is a novel addition to the theory. [ABSTRACT FROM AUTHOR]

This article addresses the distributed consensus problem for linear multi‐agent systems (MASs) with undirected connected communication topology and saturation limits on the controller input. The networked system has been modeled using a multigraph consisting of directed self‐loops. We first represent the saturated control scheme using a polytopic formulation, for appropriate consideration of the control input. Subsequently, we derive sufficient conditions for design of a robust static output feedback controller to achieve consensus of the MAS. The synthesis problem is formulated in the form of linear matrix inequalities for H∞$$ {H}_{\infty } $$ controller design. Next, the leader‐follower topology is considered, with a single leader, for which it is shown that the same controller design technique applies, under a multigraph with single self‐loop. Finally, we validate the theoretical results using numerical examples and further simulate the designed control method on a network of spring‐mass systems. [ABSTRACT FROM AUTHOR]

Within a large database G containing graphs with labeled nodes and directed, multi-edges; how can we detect the anomalous graphs? Most existing work are designed for plain (unlabeled) and/or simple (unweighted) graphs. We introduce CODEtect, the first approach that addresses the anomaly detection task for graph databases with such complex nature. To this end, it identifies a small representative set S of structural patterns (i.e., node-labeled network motifs) that losslessly compress database G as concisely as possible. Graphs that do not compress well are flagged as anomalous. CODEtect exhibits two novel building blocks: (i) a motif-based lossless graph encoding scheme, and (ii) fast memory-efficient search algorithms for S. We show the effectiveness of CODEtect on transaction graph databases from three different corporations and statistically similar synthetic datasets, where existing baselines adjusted for the task fall behind significantly, across different types of anomalies and performance metrics. [ABSTRACT FROM AUTHOR]

A 2-dimensional direction-length framework (G , p) consists of a multigraph G = (V ; D , L) with realisation p : V → R 2 . The edges of G represent geometric constraints: edges in L have fixed length, and edges in D have fixed gradient. A direction-length framework (G , p) is globally rigid if every (G , q) which satisfies the same geometric constraints as (G , p) can be obtained from (G , p) by an isometry of the plane. We characterise global rigidity for the class of 2-dimensional direction-length frameworks (G , p) for which p is generic and the rigidity matroid of G is connected. Specifically, we show that such frameworks are globally rigid if and only if both D and L are non-empty, and every 2-separation of G is direction-balanced. This extends previous work by Jackson and Jordán (2010). [ABSTRACT FROM AUTHOR]

POI(Point of Interest) recommendation is a basic and on-going issue in LBSN (Location-based Social Network) services. In this paper, a novel POI recommendation approach which is based on LBSN and multi-graph fusion is proposed. First, we take advantages of the graph neural network to construct user-POI interaction graph based on the rating data of users and construct user social graph based on the user social networks. First-order friends and high-order friends will be considered simultaneously in the user social graph. And then, we present a spectral cluster-based algorithm to gain the latent vector of the POI in location space. After this, the graph neural network is used to learn the information above. Lastly, we predict the score based on the aforementioned information and pick out the top- k POIs with the highest scores to form a recommendation list. Extensive experiments conducted on real datasets demonstrated that the method proposed in this paper can effectively generate the embedding vectors of users and POIs, and can achieve high recommendation accuracy as well. [ABSTRACT FROM AUTHOR]

Graph convolutional networks (GCNs) have become a popular tool for learning unstructured graph data due to their powerful learning ability. Many researchers have been interested in fusing topological structures and node features to extract the correlation information for classification tasks. However, it is inadequate to integrate the embedding from topology and feature spaces to gain the most correlated information. At the same time, most GCN-based methods assume that the topology graph or feature graph is compatible with the properties of GCNs, but this is usually not satisfied since meaningless, missing, or even unreal edges are very common in actual graphs. To obtain a more robust and accurate graph structure, we intend to construct an adaptive graph with topology and feature graphs. We propose Multi-graph Fusion Graph Convolutional Networks with pseudo-label supervision (MFGCN), which learn a connected embedding by fusing the multi-graphs and node features. We can obtain the final node embedding for semi-supervised node classification by propagating node features over multi-graphs. Furthermore, to alleviate the problem of labels missing in semi-supervised classification, a pseudo-label generation mechanism is proposed to generate more reliable pseudo-labels based on the similarity of node features. Extensive experiments on six benchmark datasets demonstrate the superiority of MFGCN over state-of-the-art classification methods. [ABSTRACT FROM AUTHOR]

The chromatic index χ ′ (G) of a graph G is the least number of colors assigned to the edges of G such that no two adjacent edges receive the same color. The total chromatic number χ ″ (G) of a graph G is the least number of colors assigned to the edges and vertices of G such that no two adjacent edges receive the same color, no two adjacent vertices receive the same color and no edge has the same color as its two endpoints. The chromatic index and the total chromatic number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory. By definition, χ ′ (G) ≤ χ ″ (G) for every graph G. In 1984, Goldberg conjectured that for any multigraph G , if χ ′ (G) ≥ Δ (G) + 3 then χ ″ (G) = χ ′ (G). In this paper, we show that Goldberg's conjecture is asymptotically true. More specifically, we prove that for a multigraph G with maximum degree Δ sufficiently large, χ ″ (G) = χ ′ (G) provided χ ′ (G) ≥ Δ + 10 Δ 35 / 36. When χ ′ (G) ≥ Δ (G) + 2 , the chromatic index χ ′ (G) is completely determined by the fractional chromatic index. Consequently, the total chromatic number χ ″ (G) can be computed in polynomial-time in this case. [ABSTRACT FROM AUTHOR]

Let Pk+1 denote a path of length k, Cl denote a cycle of length l, and Kn(λ) denote the complete multigraph on n vertices in which every pair of distinct vertices is joined by λ edges. In this paper, we proved that the necessary conditions are also sufficient for a {P4;C6}- decomposition of Kn(λ). [ABSTRACT FROM AUTHOR]

We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multigraph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A 7/4-approximation algorithm for the same problem was presented recently; see Cheriyan et al. [Math. Program., 182 (2020), pp. 315--354]. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems. [ABSTRACT FROM AUTHOR]

The passenger flow prediction of the public metro system is a core and critical part of the intelligent transportation system, and is essential for traffic management, metro planning, and emergency safety measures. Most methods chose the recent segment from historical data as input to predict the future traffic flow; however, this would lead to the loss of the inherent characteristic information of the metro passenger flow's daily morning and evening peak. Therefore, this study aggregates the recent-term and long-term information and use a long-term Gated Convolutional Neural Network (Gated CNN) to extract the temporal feature from the complex historical data. On the other hand, typical models did not consider the different spatial dependencies between different metro stations; this work proposes various adjacent relationships to characterize the degree of association between nodes. In order to extract spatial and temporal features at the same time, the historical data of recent-term and long-term is merged together to extract spatial features through a multi-graph neural network module. By combining Gated CNN and multi-graph module, we propose a multi-time multi-graph neural network named MTMGNN for metro passenger flow prediction. The result of our experiment on real-world datasets shows that our model MTMGNN is better than all state-of-art methods. [ABSTRACT FROM AUTHOR]

Given a sequence k:=(k1,...,ks) of natural numbers and a graph G, let F(G;k) denote the number of colourings of the edges of G with colours 1,...,s such that, for every c∈{1,...,s}, the edges of colour c contain no clique of order kc. Write F(n;k) to denote the maximum of F(G;k) over all graphs G on n vertices. This problem was first considered by Erdős and Rothschild in 1974, but it has been solved only for a very small number of non-trivial cases. In previous work with Yilma, we constructed a finite optimisation problem whose maximum is equal to the limit of log2F(n;k)/(n2) as n tends to infinity and proved a stability theorem for complete multipartite graphs G. In this paper we provide a sufficient condition on k which guarantees a general stability theorem for any graph G, describing the asymptotic structure of G on n vertices with F(G;k)=F(n;k)⋅2o(n2) in terms of solutions to the optimisation problem. We apply our theorem to systematically recover existing stability results as well as all cases with s=2. The proof uses a novel version of symmetrisation on edge-coloured weighted multigraphs. [ABSTRACT FROM AUTHOR]

Representation learning of graphs in the form of graph embeddings is an extensively studies area, especially for simple networks, to help with different downstream applications such as node clustering, link prediction, and node classification. In this paper, we propose MG2Vec+, a method that generates node embeddings for a multigraph, a network structure comprising multiple types of edges between pairs of nodes. MG2Vec+ uses multi-headed attention layers to aggregate multiple types of edge-relations that can exist among nodes. The parameters are learned using a graph likelihood loss function which ensures that the sum of attention scores for high-priority nodes is larger as compared to low-priority nodes. We compare MG2Vec+ with nine existing baseline methods after modifying them to our setting on four real-world datasets. MG2Vec+ outperforms the competing methods when evaluated on two downstream tasks: (1) link prediction, and (2) multi-class node classification. It is able to achieve a 5.88% higher AUC-ROC score than the best baseline for link prediction and 9.52% higher classification accuracy than the best baseline for the multi-class node classification task. The superiority of MG2Vec+ can be explained by its principled way of capturing multi-relational contexts and learning them in an unsupervised manner with the same set of parameters using graph likelihood loss. [ABSTRACT FROM AUTHOR]