The normal Perl idiom is to use named parameters and create a hash. Something like this:

package Edge;
sub new {
    my ($class, %param) = @_;
    bless {
        map { $_ => $param{$_} } qw(from_node to_node label)
    }, $class;
};

use Data::Dumper;
print Dumper(Edge->new);
print Dumper(Edge->new(from_node => 'foo', to_node => 'bar'));
print Dumper(Edge->new(from_node => 'foo', to_node => 'bar', label => 
+'ni'));

__END__
Produces:
$VAR1 = bless( {
                 'to_node' => undef,
                 'from_node' => undef,
                 'label' => undef
               }, 'Edge' );
$VAR1 = bless( {
                 'to_node' => 'bar',
                 'from_node' => 'foo',
                 'label' => undef
               }, 'Edge' );
$VAR1 = bless( {
                 'to_node' => 'bar',
                 'from_node' => 'foo',
                 'label' => 'ni'
               }, 'Edge' );
[download]

This gives you extra flexibility since you do not tie yourself down to a specific number or order of parameters. In Perl6 it will even be efficient :-)